NavigableMap implementation bugs

[Martin Buchholz]

Doug and Josh and Chris,

(Chris, please file a bug)

TreeMap.navigableKeySet().subSet(x,y).remove(o)
fails because TreeMap.KeySet.subset calls the
TreeSet(NavigableMap<E,Object>)
constructor, and that requires an argument map
not containing arbitrary value objects for correctness.
This correctness is probably only
noticed in the return value from remove being incorrect.

In the case of ConcurrentSkipListMap, the correctness
issue is even more serious, since remove(existing element)
fails to remove it.

It's not obvious how to best fix it.  The TreeSet(NavigableMap)
and ConcurrentSkipListMap(NavigableMap) constructors
simply cannot be used to get views of non-empty maps.
It's clear that the usual straightforward but tedious solution
will work, but is there an elegant solution?

(Curiously, this is one of the rare times where
generics compiler warnings caught a genuine bug!
It's a mistake in this case to force a NavigableMap<K,V>
into a NavigableMap<K,Object>)

Most of the hits below are bugs:

 $ find -name '*Map.java' | xargs grep -E 'new (TreeSet|ConcurrentSkipListSet)'
./TreeMap.java:            return new TreeSet<E>(m.subMap(fromElement,
fromInclusive,
./TreeMap.java:            return new TreeSet<E>(m.headMap(toElement,
inclusive));
./TreeMap.java:            return new
TreeSet<E>(m.tailMap(fromElement, inclusive));
./TreeMap.java:            return new TreeSet(m.descendingMap());
./concurrent/ConcurrentSkipListMap.java:            return new
ConcurrentSkipListSet<E>
./concurrent/ConcurrentSkipListMap.java:            return new
ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive));
./concurrent/ConcurrentSkipListMap.java:            return new
ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive));
./concurrent/ConcurrentSkipListMap.java:            return new
ConcurrentSkipListSet(m.descendingMap());

Test case follows:

/*
 * Copyright 2008 Sun Microsystems, Inc.  All Rights Reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 * CA 95054 USA or visit www.sun.com if you need additional information or
 * have any questions.
 */

/*
 * @test
 * @summary navigableMap.keyset().subSet().remove(x)
 * @author  Martin Buchholz
 */

import java.util.Collection;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.concurrent.ConcurrentSkipListMap;

public class Bug12 {
    void test(String[] args) throws Throwable {
        testNavigableMap(new TreeMap<Integer,Integer>());
        testNavigableMap(new ConcurrentSkipListMap<Integer,Integer>());
    }

    void checkEmpty(Collection<?> c) {
        check(c.isEmpty());
        check(c.size() == 0);
        check(! c.iterator().hasNext());
    }

    void checkEmpty(NavigableMap<?,?> m) {
        check(m.isEmpty());
        check(m.size() == 0);
        checkEmpty(m.keySet());
        checkEmpty(m.values());
        checkEmpty(m.entrySet());
    }

    void testNavigableMap(NavigableMap<Integer,Integer> m) {
        System.out.printf("Testing %s%n", m.getClass());
        checkEmpty(m);
        equal(m.put(1,2),null);
        equal(m.put(1,3),2);
        equal(m.remove(1),3);
        checkEmpty(m);
        equal(m.put(1,2),null);
        check(m.navigableKeySet().remove(1));
        checkEmpty(m);
        equal(m.put(1,2),null);
        check(m.navigableKeySet().headSet(3).remove(1));
        checkEmpty(m);
        equal(m.put(1,2),null);
        check(m.navigableKeySet().tailSet(-3).remove(1));
        checkEmpty(m);
        equal(m.put(1,2),null);
        check(m.navigableKeySet().subSet(-3,3).remove(1));
        checkEmpty(m);
        equal(m.put(1,2),null);
        check(m.isEmpty());
    }

    //--------------------- 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);}
    public static void main(String[] args) throws Throwable {
        Class<?> k = new Object(){}.getClass().getEnclosingClass();
        try {k.getMethod("instanceMain",String[].class)
                .invoke( k.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");}
}