United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
JDK-6800572 : Removing elements from views of NavigableMap implementations does not always work correctly.

Details
Type:
Bug
Submit Date:
2009-02-03
Status:
Resolved
Updated Date:
2010-04-02
Project Name:
JDK
Resolved Date:
2009-04-11
Component:
core-libs
OS:
generic
Sub-Component:
java.util
CPU:
generic
Priority:
P4
Resolution:
Fixed
Affected Versions:
6
Fixed Versions:

Related Reports
Backport:
Relates:

Sub Tasks

Description
As shown by this test case:

import java.util.*;
import java.util.concurrent.*;

@SuppressWarnings({"unchecked", "rawtypes"})
public class keyset {
    void test(String[] args) {
        test(new TreeMap());
        test(new ConcurrentSkipListMap());
    }

    void rm(Map m, Object k, Object v) {
        equal(m.remove(k), v);
    }

    void equalMaps(Map m1, Map m2) {
        equal(m1, m2);
        equal(m2, m1);
        equal(m1.size(), m2.size());
        equal(m1.isEmpty(), m2.isEmpty());
        equal(m1.toString(), m2.toString());
        check(Arrays.equals(m1.entrySet().toArray(), m2.entrySet().toArray()));
    }

    void test(final NavigableMap m) {
        System.out.println(m.getClass().getName());

        final Map emptyMap = new HashMap();

        final Map singletonMap = new HashMap();
        singletonMap.put(1, 2);

        abstract class NavigableMapView {
            abstract NavigableMap view(NavigableMap m);
        }

        NavigableMapView[] views = {
            new NavigableMapView() { NavigableMap view(NavigableMap m) {
                return m; }},
            new NavigableMapView() { NavigableMap view(NavigableMap m) {
                return m.headMap(99, true); }},
            new NavigableMapView() { NavigableMap view(NavigableMap m) {
                return m.tailMap(-99, false); }},
            new NavigableMapView() { NavigableMap view(NavigableMap m) {
                return m.subMap(-99, true, 99, false); }},
        };

        abstract class Remover {
            abstract void remove(NavigableMap m, Object k, Object v);
        }

        Remover[] removers = {
            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                equal(m.remove(k), v); }},

            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                equal(m.descendingMap().remove(k), v); }},
            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                equal(m.descendingMap().headMap(-86, false).remove(k), v); }},
            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                equal(m.descendingMap().tailMap(86, true).remove(k), v); }},

            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                equal(m.headMap(86, true).remove(k), v); }},
            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                equal(m.tailMap(-86, true).remove(k), v); }},
            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                equal(m.subMap(-86, false, 86, true).remove(k), v); }},

            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                check(m.keySet().remove(k)); }},
            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                check(m.navigableKeySet().remove(k)); }},

            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                check(m.navigableKeySet().headSet(86, true).remove(k)); }},
            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                check(m.navigableKeySet().tailSet(-86, false).remove(k)); }},
            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                check(m.navigableKeySet().subSet(-86, true, 86,
false).remove(k)); }},

            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                check(m.descendingKeySet().headSet(-86, false).remove(k)); }},
            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                check(m.descendingKeySet().tailSet(86, true).remove(k)); }},
            new Remover() { void remove(NavigableMap m, Object k, Object v) {
                check(m.descendingKeySet().subSet(86, true, -86,
false).remove(k)); }},
        };

        for (NavigableMapView view : views) {
            for (Remover remover : removers) {
                try {
                    m.clear();
                    equalMaps(m, emptyMap);
                    equal(m.put(1, 2), null);
                    equalMaps(m, singletonMap);
                    NavigableMap v = view.view(m);
                    remover.remove(v, 1, 2);
                    equalMaps(m, emptyMap);
                } catch (Throwable t) { unexpected(t); }
            }
        }
    }
    //--------------------- Infrastructure ---------------------------
    volatile int passed = 0, failed = 0;
    void pass() {passed++;}
    void fail() {failed++; Thread.dumpStack();}
    void fail(String msg) {System.err.println(msg); fail();}
    void unexpected(Throwable t) {failed++; t.printStackTrace();}
    void check(boolean cond) {if (cond) pass(); else fail();}
    void equal(Object x, Object y) {
        if (x == null ? y == null : x.equals(y)) pass();
        else fail(x + " not equal to " + y);}
    static Class<?> thisClass = new Object(){}.getClass().getEnclosingClass();
    public static void main(String[] args) throws Throwable {
        try {thisClass.getMethod("instanceMain",String[].class)
                .invoke(thisClass.newInstance(), (Object) args);}
        catch (Throwable e) {throw e.getCause();}}
    public void instanceMain(String[] args) throws Throwable {
        try {test(args);} catch (Throwable t) {unexpected(t);}
        System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
        if (failed > 0) throw new AssertionError("Some tests failed");}
}

                                    

Comments
SUGGESTED FIX

==== //depot2/google_vendor_src_branch/openjdk6/trunk/jdk/src/share/classes/java/util/TreeMap.java#1
- /usr/local/google/home/martin/p4/openjdk/google_vendor_src_branch/openjdk6/trunk/jdk/src/share/classes/java/util/TreeMap.java
====
--- /tmp/g4-76709/cache/depot2/google_vendor_src_branch/openjdk6/trunk/jdk/src/share/classes/java/util/TreeMap.java#1	2009-02-01
15:09:33.000000000 -0800
+++ /usr/local/google/home/martin/p4/openjdk/google_vendor_src_branch/openjdk6/trunk/jdk/src/share/classes/java/util/TreeMap.java	2009-02-01
14:56:05.000000000 -0800
@@ -1068,14 +1068,14 @@
         }
         public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                       E toElement,   boolean toInclusive) {
-            return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
-                                           toElement,   toInclusive));
+            return new KeySet<E>(m.subMap(fromElement, fromInclusive,
+                                          toElement,   toInclusive));
         }
         public NavigableSet<E> headSet(E toElement, boolean inclusive) {
-            return new TreeSet<E>(m.headMap(toElement, inclusive));
+            return new KeySet<E>(m.headMap(toElement, inclusive));
         }
         public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
-            return new TreeSet<E>(m.tailMap(fromElement, inclusive));
+            return new KeySet<E>(m.tailMap(fromElement, inclusive));
         }
         public SortedSet<E> subSet(E fromElement, E toElement) {
             return subSet(fromElement, true, toElement, false);
@@ -1087,7 +1087,7 @@
             return tailSet(fromElement, true);
         }
         public NavigableSet<E> descendingSet() {
-            return new TreeSet(m.descendingMap());
+            return new KeySet(m.descendingMap());
         }
     }

==== //depot2/google_vendor_src_branch/openjdk6/trunk/jdk/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java#1
- /usr/local/google/home/martin/p4/openjdk/google_vendor_src_branch/openjdk6/trunk/jdk/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java
====
--- /tmp/g4-76709/cache/depot2/google_vendor_src_branch/openjdk6/trunk/jdk/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java#1	2009-02-01
15:09:33.000000000 -0800
+++ /usr/local/google/home/martin/p4/openjdk/google_vendor_src_branch/openjdk6/trunk/jdk/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java	2009-02-01
15:00:14.000000000 -0800
@@ -2394,15 +2394,14 @@
                                       boolean fromInclusive,
                                       E toElement,
                                       boolean toInclusive) {
-            return new ConcurrentSkipListSet<E>
-                (m.subMap(fromElement, fromInclusive,
-                          toElement,   toInclusive));
+            return new KeySet<E>(m.subMap(fromElement, fromInclusive,
+                                          toElement,   toInclusive));
         }
         public NavigableSet<E> headSet(E toElement, boolean inclusive) {
-            return new ConcurrentSkipListSet<E>(m.headMap(toElement,
inclusive));
+            return new KeySet<E>(m.headMap(toElement, inclusive));
         }
         public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
-            return new
ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive));
+            return new KeySet<E>(m.tailMap(fromElement, inclusive));
         }
         public NavigableSet<E> subSet(E fromElement, E toElement) {
             return subSet(fromElement, true, toElement, false);
@@ -2414,7 +2413,7 @@
             return tailSet(fromElement, true);
         }
         public NavigableSet<E> descendingSet() {
-            return new ConcurrentSkipListSet(m.descendingMap());
+            return new KeySet(m.descendingMap());
         }
     }
                                     
2009-02-03
EVALUATION

Replace use of new TreeSet with new KeySet
                                     
2009-03-25



Hardware and Software, Engineered to Work Together