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

[Doug Lea]

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 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.
>>
>