Name: gm110360			Date: 07/15/2002


FULL PRODUCT VERSION :
java version "1.4.0_01"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.0_01-b03)
Java HotSpot(TM) Client VM (build 1.4.0_01-b03, mixed mode)


FULL OPERATING SYSTEM VERSION :
glibc-2.2.4-24
Linux dhcp-168-239 2.4.7-10 #1 Thu Sep 6 17:27:27 EDT 2001
i686 unknown
Red Hat Linux release 7.2 (Enigma)

A DESCRIPTION OF THE PROBLEM :
There is a problem arising between the behavior of
WeakHashMap and the implementation of
ArrayList.addAll(Collection).

Sometimes the addAll call can cause a NoSuchElementException
to be thrown. This is at the mercy of timing in the garbage
collector. The reason is simple:

....
int numNew = c.size();
....
Iterator e = c.iterator();
for (int i = 0; i < numNew; i++) {
    elementData[size++] = e.next();
}
....

If Collection c is completely well-behaved, this is fine. If
it is e.g. the key set from a WeakHashMap, however, c.size()
may be greater than the number of times e.next() can safely
be called. The safe impl is this:

....
int numNew = c.size();
....
Iterator e = c.iterator();
while (e.hasNext()) {
    elementData[size++] = e.next();
}
....

I would suggest one of the following be done:

1. Patch ArrayList.addAll to use code like that suggested
above, i.e. be sure to always call Iterator.hasNext() before
calling Iterator.next(), and do not trust Collection.size()
to always be accurate. But there may be a performance
disadvantage to doing this.

2. Patch ArrayList.addAll to use the safer form only if the
collection is the key set (or value set or entry set) from a
WeakHashMap, otherwise use the faster form. A nice
compromise but will not solve the problem for third-party
(non-java.util.*) collection classes that use weak or soft
references, such as:

http://www.netbeans.org/source/browse/~checkout~/openide/src/org/openide/util/WeakSet.java

3. Document in ArrayList.addAll, and perhaps in other method
Javadoc, that it is unsafe to call the method with a
Collection parameter derived from a WeakHashMap. Also warn
in the Javadoc for WeakHashMap that its derived Set's are
unsuitable for being passed to certain methods.

  Bug originally observed unreproducibly in NetBeans IDE:

http://www.netbeans.org/issues/show_bug.cgi?id=25285

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Try running the demo class shown. On my machine, it shows
the exception about 50% of the time. Depends on timing factors.

EXPECTED VERSUS ACTUAL BEHAVIOR :
Expected result:

Always prints "OK".

Actual result:

Sometimes prints "OK". Sometimes dumps a stack trace.

ERROR MESSAGES/STACK TRACES THAT OCCUR :
Exception in thread "main" java.util.NoSuchElementException
	at java.util.WeakHashMap$HashIterator.nextEntry(WeakHashMap.java:736)
	at java.util.WeakHashMap$KeyIterator.next(WeakHashMap.java:767)
	at java.util.ArrayList.addAll(ArrayList.java:438)
	at WeakHashMapSynchTest.main(WeakHashMapSynchTest.java:8)


REPRODUCIBILITY :
This bug can be reproduced often.

---------- BEGIN SOURCE ----------
import java.util.*;
public class WeakHashMapSynchTest {
    public static void main(String[] args) {
        Map m = new WeakHashMap(100000);
        for (int i = 0; i < 100000; i++) {
            m.put(new Object(), Boolean.TRUE);
        }
        new ArrayList().addAll(m.keySet());
        System.out.println("OK.");
    }
}

---------- END SOURCE ----------

CUSTOMER WORKAROUND :
If you know about the bug, it is easy to work around, i.e.
it is mostly a matter of unmet expectations about the safety
of using the API. Rather than

WeakHashMap m;
ArrayList a;
a.addAll(m.keySet());

you can just do:

WeakHashMap m;
ArrayList a;
Iterator i = m.keySet().iterator();
while (i.hasNext()) a.add(i.next());
(Review ID: 158660) 
======================================================================