JDK-6197726 : (coll) IdentityHashMap.entrySet().toArray(T[] a) is incorrectly implemented
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 5.0,6
  • Priority: P3
  • Status: Closed
  • Resolution: Fixed
  • OS: generic,solaris_9,windows_xp
  • CPU: generic,x86,sparc
  • Submitted: 2004-11-19
  • Updated: 2012-10-08
  • Resolved: 2005-09-04
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
Other JDK 6
5.0u6Fixed 6 b51Fixed
Related Reports
Duplicate :  
JDK-6316004 - IdentityHashMap.EntrySet.toArray(Object[]) is broken
Relates :  
JDK-6312706 - (coll) Map entrySet iterators should return different entries on each call to next()
Relates :  
JDK-6232484 - (coll) ArrayList made from IdentityHashMap.entrySet() fails to create properly
Relates :  
JDK-5031890 - (coll spec) Collection toArray() does not specify empty collection behavior
Relates :  
JDK-6310858 - (coll) EnumMap.entrySet().toArray(T[] a) is incorrectly implemented
Description
FULL PRODUCT VERSION :
java version "1.5.0"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0-b64)
Java HotSpot(TM) Client VM (build 1.5.0-b64, mixed mode, sharing)

ADDITIONAL OS VERSION INFORMATION :
XP SP2

A DESCRIPTION OF THE PROBLEM :
(inbound IdentityHashMap ip)

int sz = ip.size();
Object [] entries = new Object[sz];
ip.entrySet().toArray(entries);

Entries contains nulls, even though there is room for entries in the given array.

Look at the implementation, we find this:

public <T> T[] toArray(T[] a) {
	    return (T[])toArray(); // !!!!
        }

Seems like it was never implemented, and a placeholder was left.


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
run code above

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
entries array should contain Map.Entry objects, not nulls.

ACTUAL -
entries array contains only nulls, as it is never written to.

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
IdentityHashMap im = new IdentityHashMap();
im.put(im,im);
Object [] o = new Object[1];
im.entrySet().toArray(o);


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

CUSTOMER SUBMITTED WORKAROUND :
never call toArray(object [])
Comments
EVALUATION The deeper problem of returning the same object on each call to next() is being addressed via 6312706. Most of the obvious manifestations of that behavior are being fixed here.
18-08-2005
EVALUATION Doug Lea suggested changing ArrayList(Collection) constructor to make it slightly more robust in the sense that the code would work if the argument was any other collection class having the same bug as IdentityHashMap. (Collection classes often get copied and modified)
15-08-2005
SUGGESTED FIX --- /u/martin/ws/mustang/src/share/classes/java/util/IdentityHashMap.java 2004-08-27 15:54:50.658979000 -0700 +++ /u/martin/ws/toArray/src/share/classes/java/util/IdentityHashMap.java 2005-08-07 22:56:46.405135000 -0700 @@ -1109,13 +1109,26 @@ } public Object[] toArray() { - List<Map.Entry<K,V>> c = new ArrayList<Map.Entry<K,V>>(size()); - for (Map.Entry<K,V> e : this) - c.add(new AbstractMap.SimpleEntry<K,V>(e)); - return c.toArray(); + int size = size(); + Object[] result = new Object[size]; + Iterator<Map.Entry<K,V>> it = iterator(); + for (int i=0; i < size; i++) + result[i] = new AbstractMap.SimpleEntry<K,V>(it.next()); + return result; } public <T> T[] toArray(T[] a) { - return (T[])toArray(); // !!!! + int size = size(); + if (a.length < size) + a = (T[])java.lang.reflect.Array + .newInstance(a.getClass().getComponentType(), size); + + Iterator<Map.Entry<K,V>> it = iterator(); + Object[] result = a; + for (int i=0; i<size; i++) + result[i] = new AbstractMap.SimpleEntry<K,V>(it.next()); + if (a.length > size) + a[size] = null; + return a; } } --- /u/martin/ws/mustang/test/java/util/IdentityHashMap/ToArray.java 2004-08-27 16:19:49.069257000 -0700 +++ /u/martin/ws/toArray/test/java/util/IdentityHashMap/ToArray.java 2005-08-07 22:56:46.955474000 -0700 @@ -1,16 +1,19 @@ /* - * @test 1.1 01/08/06 - * @bug 4485486 - * @summary IdentityHashMap's lack of internal entry objects caused the - * inherited (AbstractMap) version of toArray to return garbage - * when called on the entrySet view. - * @author Josh Bloch + * @test 1.2 05/08/07 + * @bug 4485486 6197726 + * @summary IdentityHashMap's entrySet toArray tests + * @author Josh Bloch, Martin Buchholz */ import java.util.*; public class ToArray { public static void main(String[] args) { + //---------------------------------------------------------------- + // IdentityHashMap's lack of internal entry objects caused + // the inherited (AbstractMap) version of toArray to + // return garbage when called on the entrySet view. + //---------------------------------------------------------------- Map m = new IdentityHashMap(); m.put("french", "connection"); m.put("polish", "sausage"); @@ -20,5 +23,28 @@ mArray[0].toString(); mArray[1].toString(); + + //---------------------------------------------------------------- + // IdentityHashMap.entrySet().toArray(T[] a) used to simply + // return toArray() ! + //---------------------------------------------------------------- + IdentityHashMap<Integer,Integer> map + = new IdentityHashMap<Integer,Integer>(); + Set<Map.Entry<Integer,Integer>> es = map.entrySet(); + if (es.toArray().length != 0) + throw new Error("non-empty"); + if (es.toArray(new Object[]{Boolean.TRUE})[0] != null) + throw new Error("non-null"); + map.put(7,49); + if (es.toArray().length != 1) + throw new Error("length"); + Object[] x = es.toArray(new Object[]{Boolean.TRUE, Boolean.TRUE}); + if (x[1] != null) + throw new Error("non-null"); + Map.Entry e = (Map.Entry) x[0]; + if (! e.getKey().equals(new Integer(7))) + throw new Error("bad key"); + if (! e.getValue().equals(new Integer(49))) + throw new Error("bad value"); } } --- /u/martin/ws/mustang/src/share/classes/java/util/ArrayList.java 2005-06-08 14:05:18.407383000 -0700 +++ /u/martin/ws/toArray/src/share/classes/java/util/ArrayList.java 2005-08-14 18:17:17.878695000 -0700 @@ -132,9 +132,8 @@ public ArrayList(Collection<? extends E> c) { size = c.size(); // Allow 10% room for growth - elementData = (E[])new Object[ - (int)Math.min((size*110L)/100,Integer.MAX_VALUE)]; - c.toArray(elementData); + int capacity = (int) Math.min((size*110L)/100, Integer.MAX_VALUE); + elementData = (E[]) c.toArray(new Object[capacity]); } /**
08-08-2005
EVALUATION I independently found this while examining 5031890 (coll spec) Collection toArray() does not specify empty collection behavior I have a nice test framework for testing this kind of stuff more globally, and have been working on toArray before, so I'm taking ownership of this bug.
06-08-2005
EVALUATION toArray() could indeed be more efficient and, more importantly, toArray(T[]) is not completely implemented. ###@###.### 2005-06-15 18:25:51 GMT
15-06-2005