6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present

[Joshua Bloch]

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 at 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 at 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 at 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.
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20080420/f15c8f0e/attachment.html>