6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present
It's a little disconcerting to still keep finding basic correctness bugs in core Collections classes. Here's a fix (again demonstrating that the Mother Of All Collections Tests is not thorough enough): Review requested from Chris Hegarty, Doug Lea # HG changeset patch # User martin # Date 1208733844 25200 # Node ID fd80580439549ed34473cfa973f34d29f9efd7a6 # Parent 8513593a57f180641d06cf535f1647cb9160f9e0 6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present Reviewed-by: Contributed-by: Scott Blum <scottb@google.com> diff --git a/src/share/classes/java/util/IdentityHashMap.java b/src/share/classes/java/util/IdentityHashMap.java --- a/src/share/classes/java/util/IdentityHashMap.java +++ b/src/share/classes/java/util/IdentityHashMap.java @@ -188,7 +188,6 @@ public class IdentityHashMap<K,V> /** * Use NULL_KEY for key if it is null. */ - private static Object maskNull(Object key) { return (key == null ? NULL_KEY : key); } @@ -378,8 +377,8 @@ public class IdentityHashMap<K,V> */ public boolean containsValue(Object value) { Object[] tab = table; - for (int i = 1; i < tab.length; i+= 2) - if (tab[i] == value) + for (int i = 1; i < tab.length; i += 2) + if (tab[i] == value && tab[i - 1] != null) return true; return false; @@ -905,7 +904,6 @@ public class IdentityHashMap<K,V> * view the first time this view is requested. The view is stateless, * so there's no reason to create more than one. */ - private transient Set<Map.Entry<K,V>> entrySet = null; /** diff --git a/test/java/util/Collection/MOAT.java b/test/java/util/Collection/MOAT.java --- a/test/java/util/Collection/MOAT.java +++ b/test/java/util/Collection/MOAT.java @@ -25,7 +25,7 @@ * @test * @bug 6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464 * 4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753 - * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 + * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215 * @summary Run many tests on many Collection and Map implementations * @author Martin Buchholz */ @@ -247,6 +247,13 @@ public class MOAT { testEmptySet(m.keySet()); testEmptySet(m.entrySet()); testEmptyCollection(m.values()); + + try { check(! m.containsValue(null)); } + catch (NullPointerException _) { /* OK */ } + try { check(! m.containsKey(null)); } + catch (NullPointerException _) { /* OK */ } + check(! m.containsValue(1)); + check(! m.containsKey(1)); } private static void testImmutableMap(final Map<Integer,Integer> m) { Martin On Sun, Apr 20, 2008 at 3:07 AM, Alan Bateman <Alan.Bateman@sun.com> wrote:
Joshua Bloch wrote:
Folks,
While we're at it, here's another Collections bug discovered recently by a
Googler (Scott Blum). The value of this expression should be false:
new IdentityHashMap().containsValue(null)
Unfortunately, it's true. Looking at the code for containsValue, it's
obvious what's wrong:
/** * Tests whether the specified object reference is a value in this
identity
* hash map. * * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * specified object reference * @see #containsKey(Object) */ public boolean containsValue(Object value) { Object[] tab = table; for (int i = 1; i < tab.length; i+= 2) if (tab[i] == value) return true;
return false; }
Empty entries are masquerading as entries mapping to null. The fix is
easy:
if (tab[i] == value)
becomes:
if (tab[i] == value && tab[i -1] != null)
(Recall that the null key (but not value) is proxied by NULL_KEY.)
Josh
I don't see this in the bug database so I've created the following so that it doesn't get lost: 6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present
-Alan.
Martin, A bit disconcerting, yes, but both of the recent discoveries are, in their own way, special cases: TreeMap: I rewrote this layer of it for Java 6, and the flaw is in a slightly obscure place. IdentityHashMap: The flaw is in a very obscure place. containsValue is infrequently used even for normal maps; this is an identity map. And it has identity value semantics, which is a bit odd. In a perfect world, we'd all write bug-free code, but hey, we've seen a binary search bug last a quarter of a century;) Josh On Sun, Apr 20, 2008 at 4:35 PM, Martin Buchholz <martinrb@google.com> wrote:
It's a little disconcerting to still keep finding basic correctness bugs in core Collections classes.
Here's a fix (again demonstrating that the Mother Of All Collections Tests is not thorough enough):
Review requested from Chris Hegarty, Doug Lea
# HG changeset patch # User martin # Date 1208733844 25200 # Node ID fd80580439549ed34473cfa973f34d29f9efd7a6 # Parent 8513593a57f180641d06cf535f1647cb9160f9e0 6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present Reviewed-by: Contributed-by: Scott Blum <scottb@google.com>
diff --git a/src/share/classes/java/util/IdentityHashMap.java b/src/share/classes/java/util/IdentityHashMap.java --- a/src/share/classes/java/util/IdentityHashMap.java +++ b/src/share/classes/java/util/IdentityHashMap.java @@ -188,7 +188,6 @@ public class IdentityHashMap<K,V> /** * Use NULL_KEY for key if it is null. */ - private static Object maskNull(Object key) { return (key == null ? NULL_KEY : key); } @@ -378,8 +377,8 @@ public class IdentityHashMap<K,V> */ public boolean containsValue(Object value) { Object[] tab = table; - for (int i = 1; i < tab.length; i+= 2) - if (tab[i] == value) + for (int i = 1; i < tab.length; i += 2) + if (tab[i] == value && tab[i - 1] != null) return true;
return false; @@ -905,7 +904,6 @@ public class IdentityHashMap<K,V> * view the first time this view is requested. The view is stateless, * so there's no reason to create more than one. */ - private transient Set<Map.Entry<K,V>> entrySet = null;
/** diff --git a/test/java/util/Collection/MOAT.java b/test/java/util/Collection/MOAT.java --- a/test/java/util/Collection/MOAT.java +++ b/test/java/util/Collection/MOAT.java @@ -25,7 +25,7 @@ * @test * @bug 6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464 * 4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753 - * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 + * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215 * @summary Run many tests on many Collection and Map implementations * @author Martin Buchholz */ @@ -247,6 +247,13 @@ public class MOAT { testEmptySet(m.keySet()); testEmptySet(m.entrySet()); testEmptyCollection(m.values()); + + try { check(! m.containsValue(null)); } + catch (NullPointerException _) { /* OK */ } + try { check(! m.containsKey(null)); } + catch (NullPointerException _) { /* OK */ } + check(! m.containsValue(1)); + check(! m.containsKey(1)); }
private static void testImmutableMap(final Map<Integer,Integer> m) {
Martin
On Sun, Apr 20, 2008 at 3:07 AM, Alan Bateman <Alan.Bateman@sun.com> wrote:
Joshua Bloch wrote:
Folks,
While we're at it, here's another Collections bug discovered recently
by a Googler (Scott Blum). The value of this expression should be false:
new IdentityHashMap().containsValue(null)
Unfortunately, it's true. Looking at the code for containsValue, it's
obvious what's wrong:
/** * Tests whether the specified object reference is a value in this
identity
* hash map. * * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * specified object reference * @see #containsKey(Object) */ public boolean containsValue(Object value) { Object[] tab = table; for (int i = 1; i < tab.length; i+= 2) if (tab[i] == value) return true;
return false; }
Empty entries are masquerading as entries mapping to null. The fix is
easy:
if (tab[i] == value)
becomes:
if (tab[i] == value && tab[i -1] != null)
(Recall that the null key (but not value) is proxied by NULL_KEY.)
Josh
I don't see this in the bug database so I've created the following so that it doesn't get lost: 6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present
-Alan.
Martin Buchholz wrote:
It's a little disconcerting to still keep finding basic correctness bugs in core Collections classes.
Here's a fix (again demonstrating that the Mother Of All Collections Tests is not thorough enough):
Further aside: MOAT ought to be rolled into TCK someday. It solely covers basic specified functionality.
Review requested from Chris Hegarty, Doug Lea
Yes, this looks OK to me.
# HG changeset patch # User martin # Date 1208733844 25200 # Node ID fd80580439549ed34473cfa973f34d29f9efd7a6 # Parent 8513593a57f180641d06cf535f1647cb9160f9e0 6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present Reviewed-by: Contributed-by: Scott Blum <scottb@google.com>
diff --git a/src/share/classes/java/util/IdentityHashMap.java b/src/share/classes/java/util/IdentityHashMap.java --- a/src/share/classes/java/util/IdentityHashMap.java +++ b/src/share/classes/java/util/IdentityHashMap.java @@ -188,7 +188,6 @@ public class IdentityHashMap<K,V> /** * Use NULL_KEY for key if it is null. */ - private static Object maskNull(Object key) { return (key == null ? NULL_KEY : key); } @@ -378,8 +377,8 @@ public class IdentityHashMap<K,V> */ public boolean containsValue(Object value) { Object[] tab = table; - for (int i = 1; i < tab.length; i+= 2) - if (tab[i] == value) + for (int i = 1; i < tab.length; i += 2) + if (tab[i] == value && tab[i - 1] != null) return true;
return false; @@ -905,7 +904,6 @@ public class IdentityHashMap<K,V> * view the first time this view is requested. The view is stateless, * so there's no reason to create more than one. */ - private transient Set<Map.Entry<K,V>> entrySet = null;
/** diff --git a/test/java/util/Collection/MOAT.java b/test/java/util/Collection/MOAT.java --- a/test/java/util/Collection/MOAT.java +++ b/test/java/util/Collection/MOAT.java @@ -25,7 +25,7 @@ * @test * @bug 6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464 * 4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753 - * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 + * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215 * @summary Run many tests on many Collection and Map implementations * @author Martin Buchholz */ @@ -247,6 +247,13 @@ public class MOAT { testEmptySet(m.keySet()); testEmptySet(m.entrySet()); testEmptyCollection(m.values()); + + try { check(! m.containsValue(null)); } + catch (NullPointerException _) { /* OK */ } + try { check(! m.containsKey(null)); } + catch (NullPointerException _) { /* OK */ } + check(! m.containsValue(1)); + check(! m.containsKey(1)); }
private static void testImmutableMap(final Map<Integer,Integer> m) {
Martin
On Sun, Apr 20, 2008 at 3:07 AM, Alan Bateman <Alan.Bateman@sun.com> wrote:
Joshua Bloch wrote:
Folks,
While we're at it, here's another Collections bug discovered recently by a Googler (Scott Blum). The value of this expression should be false: new IdentityHashMap().containsValue(null)
Unfortunately, it's true. Looking at the code for containsValue, it's obvious what's wrong: /** * Tests whether the specified object reference is a value in this identity * hash map. * * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * specified object reference * @see #containsKey(Object) */ public boolean containsValue(Object value) { Object[] tab = table; for (int i = 1; i < tab.length; i+= 2) if (tab[i] == value) return true;
return false; }
Empty entries are masquerading as entries mapping to null. The fix is easy: if (tab[i] == value)
becomes:
if (tab[i] == value && tab[i -1] != null)
(Recall that the null key (but not value) is proxied by NULL_KEY.)
Josh
I don't see this in the bug database so I've created the following so that it doesn't get lost: 6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present
-Alan.
[+dmitry.miltsov] On Mon, Apr 21, 2008 at 4:00 AM, Doug Lea <dl@cs.oswego.edu> wrote:
Martin Buchholz wrote:
It's a little disconcerting to still keep finding basic correctness bugs in core Collections classes.
Here's a fix (again demonstrating that the Mother Of All Collections Tests is not thorough enough):
Further aside: MOAT ought to be rolled into TCK someday. It solely covers basic specified functionality.
Yes, but.... This kind of cooperation has been inhibited in the past by geographic, organizational, and cultural divides between the TCK and JDK engineering teams. Dmitry, consider adding yourself to core-libs-dev and perhaps other relevant OpenJDK mailing lists. One cultural impediment appears to be the practice of dividing the functionality to be tested by class and method, making the testing effort for collection classes of order C*M, while MOAT's approach aims for an engineering effort of C+M. I'm sure we can find more bugs by extending MOAT to test more collection class implementations and more operations. Perhaps some refactoring to allow MOAT to be used to test 3rd party implementations? There's a career path in there somewhere. Martin
Review requested from Chris Hegarty, Doug Lea
Yes, this looks OK to me.
# HG changeset patch # User martin # Date 1208733844 25200 # Node ID fd80580439549ed34473cfa973f34d29f9efd7a6 # Parent 8513593a57f180641d06cf535f1647cb9160f9e0 6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present Reviewed-by: Contributed-by: Scott Blum <scottb@google.com>
diff --git a/src/share/classes/java/util/IdentityHashMap.java b/src/share/classes/java/util/IdentityHashMap.java --- a/src/share/classes/java/util/IdentityHashMap.java +++ b/src/share/classes/java/util/IdentityHashMap.java @@ -188,7 +188,6 @@ public class IdentityHashMap<K,V> /** * Use NULL_KEY for key if it is null. */ - private static Object maskNull(Object key) { return (key == null ? NULL_KEY : key); } @@ -378,8 +377,8 @@ public class IdentityHashMap<K,V> */ public boolean containsValue(Object value) { Object[] tab = table; - for (int i = 1; i < tab.length; i+= 2) - if (tab[i] == value) + for (int i = 1; i < tab.length; i += 2) + if (tab[i] == value && tab[i - 1] != null) return true;
return false; @@ -905,7 +904,6 @@ public class IdentityHashMap<K,V> * view the first time this view is requested. The view is stateless, * so there's no reason to create more than one. */ - private transient Set<Map.Entry<K,V>> entrySet = null;
/** diff --git a/test/java/util/Collection/MOAT.java b/test/java/util/Collection/MOAT.java --- a/test/java/util/Collection/MOAT.java +++ b/test/java/util/Collection/MOAT.java @@ -25,7 +25,7 @@ * @test * @bug 6207984 6272521 6192552 6269713 6197726 6260652 5073546
4137464
* 4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753 - * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 + * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215 * @summary Run many tests on many Collection and Map implementations * @author Martin Buchholz */ @@ -247,6 +247,13 @@ public class MOAT { testEmptySet(m.keySet()); testEmptySet(m.entrySet()); testEmptyCollection(m.values()); + + try { check(! m.containsValue(null)); } + catch (NullPointerException _) { /* OK */ } + try { check(! m.containsKey(null)); } + catch (NullPointerException _) { /* OK */ } + check(! m.containsValue(1)); + check(! m.containsKey(1)); }
private static void testImmutableMap(final Map<Integer,Integer> m) {
Martin
On Sun, Apr 20, 2008 at 3:07 AM, Alan Bateman <Alan.Bateman@sun.com> wrote:
Joshua Bloch wrote:
Folks,
While we're at it, here's another Collections bug discovered recently by a
Googler (Scott Blum). The value of this expression should be false:
new IdentityHashMap().containsValue(null)
Unfortunately, it's true. Looking at the code for containsValue, it's
obvious what's wrong:
/** * Tests whether the specified object reference is a value in this
identity
* hash map. * * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * specified object reference * @see #containsKey(Object) */ public boolean containsValue(Object value) { Object[] tab = table; for (int i = 1; i < tab.length; i+= 2) if (tab[i] == value) return true;
return false; }
Empty entries are masquerading as entries mapping to null. The fix is
easy:
if (tab[i] == value)
becomes:
if (tab[i] == value && tab[i -1] != null)
(Recall that the null key (but not value) is proxied by NULL_KEY.)
Josh
I don't see this in the bug database so I've created the following so that it doesn't get lost: 6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present
-Alan.
participants (3)
-
Doug Lea
-
Joshua Bloch
-
Martin Buchholz