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

[Martin Buchholz]

[+dmitry.miltsov]

On Mon, Apr 21, 2008 at 4:00 AM, Doug Lea <dl at 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 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.
> > >
> > >
> >
> >
>
>