JDK-6800572 : Removing elements from views of NavigableMap implementations does not always work correctly.
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util
  • Affected Version: 6
  • Priority: P4
  • Status: Resolved
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2009-02-03
  • Updated: 2010-04-02
  • Resolved: 2009-04-11
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availabitlity Release.

To download the current JDK release, click here.
JDK 7
7 b55Fixed
Related Reports
Relates :  
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
EVALUATION Replace use of new TreeSet with new KeySet
2009-03-25

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