/* * Copyright (c) 2005, 2011, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ /* * @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 6691215 * 4802647 7123424 * @summary Run many tests on many Collection and Map implementations * @author Martin Buchholz * @run main MOAT */ /* Mother Of All (Collection) Tests * * Testing of collection classes is often spotty, because many tests * need to be performed on many implementations, but the onus on * writing the tests falls on the engineer introducing the new * implementation. * * The idea of this mega-test is that: * * An engineer adding a new collection implementation could simply add * their new implementation to a list of implementations in this * test's main method. Any general purpose Collection or * Map class is appropriate. * * An engineer fixing a regression could add their regression test here and * simultaneously test all other implementations. */ import java.io.*; import java.util.*; import java.util.concurrent.*; import static java.util.Collections.*; public class MOAT { public static void realMain(String[] args) { testCollection(new NewAbstractCollection()); testCollection(new NewAbstractSet()); testCollection(new LinkedHashSet()); testCollection(new HashSet()); testCollection(new Vector()); testCollection(new Vector().subList(0,0)); testCollection(new ArrayDeque()); testCollection(new ArrayList()); testCollection(new ArrayList().subList(0,0)); testCollection(new LinkedList()); testCollection(new LinkedList().subList(0,0)); testCollection(new TreeSet()); testCollection(Collections.checkedList(new ArrayList(), Integer.class)); testCollection(Collections.synchronizedList(new ArrayList())); testCollection(Collections.checkedSet(new HashSet(), Integer.class)); testCollection(Collections.checkedSortedSet(new TreeSet(), Integer.class)); testCollection(Collections.checkedNavigableSet(new TreeSet(), Integer.class)); testCollection(Collections.synchronizedSet(new HashSet())); testCollection(Collections.synchronizedSortedSet(new TreeSet())); testCollection(Collections.synchronizedNavigableSet(new TreeSet())); testCollection(new CopyOnWriteArrayList()); testCollection(new CopyOnWriteArrayList().subList(0,0)); testCollection(new CopyOnWriteArraySet()); testCollection(new PriorityQueue()); testCollection(new PriorityBlockingQueue()); testCollection(new ArrayBlockingQueue(20)); testCollection(new LinkedBlockingQueue(20)); testCollection(new LinkedBlockingDeque(20)); testCollection(new ConcurrentLinkedDeque()); testCollection(new ConcurrentLinkedQueue()); testCollection(new LinkedTransferQueue()); testCollection(new ConcurrentSkipListSet()); testCollection(Arrays.asList(new Integer(42))); testCollection(Arrays.asList(1,2,3)); testCollection(nCopies(25,1)); testImmutableList(nCopies(25,1)); testImmutableList(unmodifiableList(Arrays.asList(1,2,3))); testMap(new HashMap()); testMap(new LinkedHashMap()); testMap(new WeakHashMap()); testMap(new IdentityHashMap()); testMap(new TreeMap()); testMap(new Hashtable()); testMap(new ConcurrentHashMap(10, 0.5f)); testMap(new ConcurrentSkipListMap()); testMap(Collections.checkedMap(new HashMap(), Integer.class, Integer.class)); testMap(Collections.checkedSortedMap(new TreeMap(), Integer.class, Integer.class)); testMap(Collections.checkedNavigableMap(new TreeMap(), Integer.class, Integer.class)); testMap(Collections.synchronizedMap(new HashMap())); testMap(Collections.synchronizedSortedMap(new TreeMap())); testMap(Collections.synchronizedNavigableMap(new TreeMap())); // Empty collections final List emptyArray = Arrays.asList(new Integer[]{}); testCollection(emptyArray); testEmptyList(emptyArray); THROWS(IndexOutOfBoundsException.class, new Fun(){void f(){ emptyArray.set(0,1); }}); THROWS(UnsupportedOperationException.class, new Fun(){void f(){ emptyArray.add(0,1); }}); List noOne = nCopies(0,1); testCollection(noOne); testEmptyList(noOne); testImmutableList(noOne); Set emptySet = emptySet(); testCollection(emptySet); testEmptySet(emptySet); testEmptySet(EMPTY_SET); testEmptySet(Collections.emptySet()); testEmptySet(Collections.emptySortedSet()); testEmptySet(Collections.emptyNavigableSet()); testImmutableSet(emptySet); List emptyList = emptyList(); testCollection(emptyList); testEmptyList(emptyList); testEmptyList(EMPTY_LIST); testEmptyList(Collections.emptyList()); testImmutableList(emptyList); Map emptyMap = emptyMap(); testMap(emptyMap); testEmptyMap(emptyMap); testEmptyMap(EMPTY_MAP); testEmptyMap(Collections.emptyMap()); testEmptyMap(Collections.emptySortedMap()); testEmptyMap(Collections.emptyNavigableMap()); testImmutableMap(emptyMap); testImmutableMap(Collections.emptyMap()); testImmutableMap(Collections.emptySortedMap()); testImmutableMap(Collections.emptyNavigableMap()); // Singleton collections Set singletonSet = singleton(1); equal(singletonSet.size(), 1); testCollection(singletonSet); testImmutableSet(singletonSet); List singletonList = singletonList(1); equal(singletonList.size(), 1); testCollection(singletonList); testImmutableList(singletonList); testImmutableList(singletonList.subList(0,1)); testImmutableList(singletonList.subList(0,1).subList(0,1)); testEmptyList(singletonList.subList(0,0)); testEmptyList(singletonList.subList(0,0).subList(0,0)); Map singletonMap = singletonMap(1,2); equal(singletonMap.size(), 1); testMap(singletonMap); testImmutableMap(singletonMap); } private static void checkContainsSelf(Collection c) { check(c.containsAll(c)); check(c.containsAll(Arrays.asList(c.toArray()))); check(c.containsAll(Arrays.asList(c.toArray(new Integer[0])))); } private static void checkContainsEmpty(Collection c) { check(c.containsAll(new ArrayList())); } private static void testEmptyCollection(Collection c) { check(c.isEmpty()); equal(c.size(), 0); equal(c.toString(),"[]"); equal(c.toArray().length, 0); equal(c.toArray(new Object[0]).length, 0); check(c.toArray(new Object[]{42})[0] == null); Object[] a = new Object[1]; a[0] = Boolean.TRUE; equal(c.toArray(a), a); equal(a[0], null); testEmptyIterator(c.iterator()); } static void testEmptyIterator(final Iterator it) { if (rnd.nextBoolean()) check(! it.hasNext()); THROWS(NoSuchElementException.class, new Fun(){void f(){ it.next(); }}); try { it.remove(); } catch (IllegalStateException _) { pass(); } catch (UnsupportedOperationException _) { pass(); } catch (Throwable t) { unexpected(t); } if (rnd.nextBoolean()) check(! it.hasNext()); } private static void testEmptyList(List c) { testEmptyCollection(c); equal(c.hashCode(), 1); equal2(c, Collections.emptyList()); } private static void testEmptySet(Set c) { testEmptyCollection(c); equal(c.hashCode(), 0); equal2(c, Collections.emptySet()); if (c instanceof NavigableSet) testEmptyIterator(((NavigableSet)c).descendingIterator()); } private static void testImmutableCollection(final Collection c) { THROWS(UnsupportedOperationException.class, new Fun(){void f(){ c.add(99); }}, new Fun(){void f(){ c.addAll(singleton(99)); }}); if (! c.isEmpty()) { final Integer first = c.iterator().next(); THROWS(UnsupportedOperationException.class, new Fun(){void f(){ c.clear(); }}, new Fun(){void f(){ c.remove(first); }}, new Fun(){void f(){ c.removeAll(singleton(first)); }}, new Fun(){void f(){ c.retainAll(emptyList()); }} ); } } private static void testImmutableSet(final Set c) { testImmutableCollection(c); } private static void testImmutableList(final List c) { testList(c); testImmutableCollection(c); THROWS(UnsupportedOperationException.class, new Fun(){void f(){ c.set(0,42); }}, new Fun(){void f(){ c.add(0,42); }}, new Fun(){void f(){ c.addAll(0,singleton(86)); }}); if (! c.isEmpty()) THROWS(UnsupportedOperationException.class, new Fun(){void f(){ Iterator it = c.iterator(); it.next(); it.remove();}}, new Fun(){void f(){ ListIterator it = c.listIterator(); it.next(); it.remove();}}); } private static void clear(Collection c) { try { c.clear(); } catch (Throwable t) { unexpected(t); } testEmptyCollection(c); } private static void testEmptyMap(final Map m) { check(m.isEmpty()); equal(m.size(), 0); equal(m.toString(),"{}"); 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 m) { THROWS(UnsupportedOperationException.class, new Fun(){void f(){ m.put(1,1); }}, new Fun(){void f(){ m.putAll(singletonMap(1,1)); }}); if (! m.isEmpty()) { final Integer first = m.keySet().iterator().next(); THROWS(UnsupportedOperationException.class, new Fun(){void f(){ m.remove(first); }}, new Fun(){void f(){ m.clear(); }}); final Map.Entry me = m.entrySet().iterator().next(); Integer key = me.getKey(); Integer val = me.getValue(); THROWS(UnsupportedOperationException.class, new Fun(){void f(){ me.setValue(3); }}); equal(key, me.getKey()); equal(val, me.getValue()); } testImmutableSet(m.keySet()); testImmutableCollection(m.values()); //testImmutableSet(m.entrySet()); } private static void clear(Map m) { try { m.clear(); } catch (Throwable t) { unexpected(t); } testEmptyMap(m); } private static void oneElement(Collection c) { clear(c); try { check(c.add(-42)); equal(c.toString(), "[-42]"); if (c instanceof Set) check(! c.add(-42)); } catch (Throwable t) { unexpected(t); } check(! c.isEmpty()); check(c.size() == 1); } private static boolean supportsAdd(Collection c) { try { check(c.add(778347983)); } catch (UnsupportedOperationException t) { return false; } catch (Throwable t) { unexpected(t); } try { check(c.contains(778347983)); check(c.remove(778347983)); } catch (Throwable t) { unexpected(t); } return true; } private static boolean supportsRemove(Collection c) { try { check(! c.remove(19134032)); } catch (UnsupportedOperationException t) { return false; } catch (Throwable t) { unexpected(t); } return true; } private static void checkFunctionalInvariants(Collection c) { try { checkContainsSelf(c); checkContainsEmpty(c); check(c.size() != 0 ^ c.isEmpty()); { int size = 0; for (Integer i : c) size++; check(c.size() == size); } check(c.toArray().length == c.size()); check(c.toArray().getClass() == Object[].class || // !!!! // 6260652: (coll) Arrays.asList(x).toArray().getClass() // should be Object[].class (c.getClass().getName().equals("java.util.Arrays$ArrayList")) ); for (int size : new int[]{0,1,c.size(), c.size()+1}) { Integer[] a = c.toArray(new Integer[size]); check((size > c.size()) || a.length == c.size()); int i = 0; for (Integer j : c) check(a[i++] == j); check((size <= c.size()) || (a[c.size()] == null)); check(a.getClass() == Integer[].class); } check(c.equals(c)); if (c instanceof Serializable) { //System.out.printf("Serializing %s%n", c.getClass().getName()); try { Object clone = serialClone(c); equal(c instanceof Serializable, clone instanceof Serializable); equal(c instanceof RandomAccess, clone instanceof RandomAccess); if ((c instanceof List) || (c instanceof Set)) equal(c, clone); else equal(new HashSet(c), new HashSet(serialClone(c))); } catch (Error xxx) { if (! (xxx.getCause() instanceof NotSerializableException)) throw xxx; } } } catch (Throwable t) { unexpected(t); } } //---------------------------------------------------------------- // If add(null) succeeds, contains(null) & remove(null) should succeed //---------------------------------------------------------------- private static void testNullElement(Collection c) { try { check(c.add(null)); if (c.size() == 1) equal(c.toString(), "[null]"); try { checkFunctionalInvariants(c); check(c.contains(null)); check(c.remove(null)); } catch (Throwable t) { unexpected(t); } } catch (NullPointerException e) { /* OK */ } catch (Throwable t) { unexpected(t); } } //---------------------------------------------------------------- // If add("x") succeeds, contains("x") & remove("x") should succeed //---------------------------------------------------------------- @SuppressWarnings("unchecked") private static void testStringElement(Collection c) { Collection x = (Collection)c; // Make type-unsafe try { check(x.add("x")); try { check(x.contains("x")); check(x.remove("x")); } catch (Throwable t) { unexpected(t); } } catch (ClassCastException e) { /* OK */ } catch (Throwable t) { unexpected(t); } } private static void testConcurrentCollection(Collection c) { try { c.add(1); Iterator it = c.iterator(); check(it.hasNext()); clear(c); check(it.next() instanceof Integer); // No CME check(c.isEmpty()); } catch (Throwable t) { unexpected(t); } } private static void testQueue(Queue q) { q.clear(); for (int i = 0; i < 5; i++) { testQueueAddRemove(q, null); testQueueAddRemove(q, 537); q.add(i); } equal(q.size(), 5); checkFunctionalInvariants(q); q.poll(); equal(q.size(), 4); checkFunctionalInvariants(q); if ((q instanceof LinkedBlockingQueue) || (q instanceof LinkedBlockingDeque) || (q instanceof ConcurrentLinkedDeque) || (q instanceof ConcurrentLinkedQueue)) { testQueueIteratorRemove(q); } } private static void testQueueAddRemove(final Queue q, final Integer e) { final List originalContents = new ArrayList(q); final boolean isEmpty = q.isEmpty(); final boolean isList = (q instanceof List); final List asList = isList ? (List) q : null; check(!q.contains(e)); try { q.add(e); } catch (NullPointerException npe) { check(e == null); return; // Null elements not supported } check(q.contains(e)); check(q.remove(e)); check(!q.contains(e)); equal(new ArrayList(q), originalContents); if (q instanceof Deque) { final Deque deq = (Deque) q; final List singleton = Collections.singletonList(e); // insert, query, remove element at head if (isEmpty) { THROWS(NoSuchElementException.class, new Fun(){void f(){ deq.getFirst(); }}, new Fun(){void f(){ deq.element(); }}, new Fun(){void f(){ deq.iterator().next(); }}); check(deq.peekFirst() == null); check(deq.peek() == null); } else { check(deq.getFirst() != e); check(deq.element() != e); check(deq.iterator().next() != e); check(deq.peekFirst() != e); check(deq.peek() != e); } check(!deq.contains(e)); check(!deq.removeFirstOccurrence(e)); check(!deq.removeLastOccurrence(e)); if (isList) { check(asList.indexOf(e) == -1); check(asList.lastIndexOf(e) == -1); } switch (rnd.nextInt(isList ? 4 : 3)) { case 0: deq.addFirst(e); break; case 1: check(deq.offerFirst(e)); break; case 2: deq.push(e); break; case 3: asList.add(0, e); break; default: throw new AssertionError(); } check(deq.peekFirst() == e); check(deq.getFirst() == e); check(deq.element() == e); check(deq.peek() == e); check(deq.iterator().next() == e); check(deq.contains(e)); if (isList) { check(asList.get(0) == e); check(asList.indexOf(e) == 0); check(asList.lastIndexOf(e) == 0); check(asList.subList(0, 1).equals(singleton)); } switch (rnd.nextInt(isList ? 11 : 9)) { case 0: check(deq.pollFirst() == e); break; case 1: check(deq.removeFirst() == e); break; case 2: check(deq.remove() == e); break; case 3: check(deq.pop() == e); break; case 4: check(deq.removeFirstOccurrence(e)); break; case 5: check(deq.removeLastOccurrence(e)); break; case 6: check(deq.remove(e)); break; case 7: check(deq.removeAll(singleton)); break; case 8: Iterator it = deq.iterator(); it.next(); it.remove(); break; case 9: asList.remove(0); break; case 10: asList.subList(0, 1).clear(); break; default: throw new AssertionError(); } if (isEmpty) { THROWS(NoSuchElementException.class, new Fun(){void f(){ deq.getFirst(); }}, new Fun(){void f(){ deq.element(); }}, new Fun(){void f(){ deq.iterator().next(); }}); check(deq.peekFirst() == null); check(deq.peek() == null); } else { check(deq.getFirst() != e); check(deq.element() != e); check(deq.iterator().next() != e); check(deq.peekFirst() != e); check(deq.peek() != e); } check(!deq.contains(e)); check(!deq.removeFirstOccurrence(e)); check(!deq.removeLastOccurrence(e)); if (isList) { check(isEmpty || asList.get(0) != e); check(asList.indexOf(e) == -1); check(asList.lastIndexOf(e) == -1); } equal(new ArrayList(deq), originalContents); // insert, query, remove element at tail if (isEmpty) { check(deq.peekLast() == null); THROWS(NoSuchElementException.class, new Fun(){void f(){ deq.getLast(); }}); } else { check(deq.peekLast() != e); check(deq.getLast() != e); } switch (rnd.nextInt(isList ? 6 : 4)) { case 0: deq.addLast(e); break; case 1: check(deq.offerLast(e)); break; case 2: check(deq.add(e)); break; case 3: deq.addAll(singleton); break; case 4: asList.addAll(deq.size(), singleton); break; case 5: asList.add(deq.size(), e); break; default: throw new AssertionError(); } check(deq.peekLast() == e); check(deq.getLast() == e); check(deq.contains(e)); if (isList) { ListIterator it = asList.listIterator(asList.size()); check(it.previous() == e); check(asList.get(asList.size() - 1) == e); check(asList.indexOf(e) == asList.size() - 1); check(asList.lastIndexOf(e) == asList.size() - 1); int size = asList.size(); check(asList.subList(size - 1, size).equals(singleton)); } switch (rnd.nextInt(isList ? 8 : 6)) { case 0: check(deq.pollLast() == e); break; case 1: check(deq.removeLast() == e); break; case 2: check(deq.removeFirstOccurrence(e)); break; case 3: check(deq.removeLastOccurrence(e)); break; case 4: check(deq.remove(e)); break; case 5: check(deq.removeAll(singleton)); break; case 6: asList.remove(asList.size() - 1); break; case 7: ListIterator it = asList.listIterator(asList.size()); it.previous(); it.remove(); break; default: throw new AssertionError(); } if (isEmpty) { check(deq.peekLast() == null); THROWS(NoSuchElementException.class, new Fun(){void f(){ deq.getLast(); }}); } else { check(deq.peekLast() != e); check(deq.getLast() != e); } check(!deq.contains(e)); equal(new ArrayList(deq), originalContents); // Test operations on empty deque switch (rnd.nextInt(isList ? 4 : 2)) { case 0: deq.clear(); break; case 1: Iterator it = deq.iterator(); while (it.hasNext()) { it.next(); it.remove(); } break; case 2: asList.subList(0, asList.size()).clear(); break; case 3: ListIterator lit = asList.listIterator(asList.size()); while (lit.hasPrevious()) { lit.previous(); lit.remove(); } break; default: throw new AssertionError(); } testEmptyCollection(deq); check(!deq.iterator().hasNext()); if (isList) { check(!asList.listIterator().hasPrevious()); THROWS(NoSuchElementException.class, new Fun(){void f(){ asList.listIterator().previous(); }}); } THROWS(NoSuchElementException.class, new Fun(){void f(){ deq.iterator().next(); }}, new Fun(){void f(){ deq.element(); }}, new Fun(){void f(){ deq.getFirst(); }}, new Fun(){void f(){ deq.getLast(); }}, new Fun(){void f(){ deq.pop(); }}, new Fun(){void f(){ deq.remove(); }}, new Fun(){void f(){ deq.removeFirst(); }}, new Fun(){void f(){ deq.removeLast(); }}); check(deq.poll() == null); check(deq.pollFirst() == null); check(deq.pollLast() == null); check(deq.peek() == null); check(deq.peekFirst() == null); check(deq.peekLast() == null); check(!deq.removeFirstOccurrence(e)); check(!deq.removeLastOccurrence(e)); check(deq.addAll(originalContents) == !isEmpty); equal(new ArrayList(deq), originalContents); check(!deq.addAll(Collections.emptyList())); equal(new ArrayList(deq), originalContents); } } private static void testQueueIteratorRemove(Queue q) { System.err.printf("testQueueIteratorRemove %s%n", q.getClass().getSimpleName()); q.clear(); for (int i = 0; i < 5; i++) q.add(i); Iterator it = q.iterator(); check(it.hasNext()); for (int i = 3; i >= 0; i--) q.remove(i); equal(it.next(), 0); equal(it.next(), 4); q.clear(); for (int i = 0; i < 5; i++) q.add(i); it = q.iterator(); equal(it.next(), 0); check(it.hasNext()); for (int i = 1; i < 4; i++) q.remove(i); equal(it.next(), 1); equal(it.next(), 4); } private static void testList(final List l) { //---------------------------------------------------------------- // 4802633: (coll) AbstractList.addAll(-1,emptyCollection) // doesn't throw IndexOutOfBoundsException //---------------------------------------------------------------- try { l.addAll(-1, Collections.emptyList()); fail("Expected IndexOutOfBoundsException not thrown"); } catch (UnsupportedOperationException _) {/* OK */} catch (IndexOutOfBoundsException _) {/* OK */} catch (Throwable t) { unexpected(t); } // equal(l instanceof Serializable, // l.subList(0,0) instanceof Serializable); if (l.subList(0,0) instanceof Serializable) check(l instanceof Serializable); equal(l instanceof RandomAccess, l.subList(0,0) instanceof RandomAccess); } private static void testCollection(Collection c) { try { testCollection1(c); } catch (Throwable t) { unexpected(t); } } private static void testCollection1(Collection c) { System.out.println("\n==> " + c.getClass().getName()); checkFunctionalInvariants(c); if (! supportsAdd(c)) return; //System.out.println("add() supported"); if (c instanceof NavigableSet) { System.out.println("NavigableSet tests..."); NavigableSet ns = (NavigableSet)c; testNavigableSet(ns); testNavigableSet(ns.headSet(6, false)); testNavigableSet(ns.headSet(5, true)); testNavigableSet(ns.tailSet(0, false)); testNavigableSet(ns.tailSet(1, true)); testNavigableSet(ns.subSet(0, false, 5, true)); testNavigableSet(ns.subSet(1, true, 6, false)); } if (c instanceof Queue) testQueue((Queue)c); if (c instanceof List) testList((List)c); check(supportsRemove(c)); try { oneElement(c); checkFunctionalInvariants(c); } catch (Throwable t) { unexpected(t); } clear(c); testNullElement(c); oneElement(c); testNullElement(c); clear(c); testStringElement(c); oneElement(c); testStringElement(c); if (c.getClass().getName().matches(".*concurrent.*")) testConcurrentCollection(c); //---------------------------------------------------------------- // The "all" operations should throw NPE when passed null //---------------------------------------------------------------- { clear(c); try { c.removeAll(null); fail("Expected NullPointerException"); } catch (NullPointerException e) { pass(); } catch (Throwable t) { unexpected(t); } oneElement(c); try { c.removeAll(null); fail("Expected NullPointerException"); } catch (NullPointerException e) { pass(); } catch (Throwable t) { unexpected(t); } clear(c); try { c.retainAll(null); fail("Expected NullPointerException"); } catch (NullPointerException e) { pass(); } catch (Throwable t) { unexpected(t); } oneElement(c); try { c.retainAll(null); fail("Expected NullPointerException"); } catch (NullPointerException e) { pass(); } catch (Throwable t) { unexpected(t); } oneElement(c); try { c.addAll(null); fail("Expected NullPointerException"); } catch (NullPointerException e) { pass(); } catch (Throwable t) { unexpected(t); } oneElement(c); try { c.containsAll(null); fail("Expected NullPointerException"); } catch (NullPointerException e) { pass(); } catch (Throwable t) { unexpected(t); } } } //---------------------------------------------------------------- // Map //---------------------------------------------------------------- private static void checkFunctionalInvariants(Map m) { check(m.keySet().size() == m.entrySet().size()); check(m.keySet().size() == m.size()); checkFunctionalInvariants(m.keySet()); checkFunctionalInvariants(m.values()); check(m.size() != 0 ^ m.isEmpty()); } private static void testMap(Map m) { System.out.println("\n==> " + m.getClass().getName()); if (m instanceof ConcurrentMap) testConcurrentMap((ConcurrentMap) m); if (m instanceof NavigableMap) { System.out.println("NavigableMap tests..."); NavigableMap nm = (NavigableMap) m; testNavigableMapRemovers(nm); testNavigableMap(nm); testNavigableMap(nm.headMap(6, false)); testNavigableMap(nm.headMap(5, true)); testNavigableMap(nm.tailMap(0, false)); testNavigableMap(nm.tailMap(1, true)); testNavigableMap(nm.subMap(1, true, 6, false)); testNavigableMap(nm.subMap(0, false, 5, true)); } checkFunctionalInvariants(m); if (supportsClear(m)) { try { clear(m); } catch (Throwable t) { unexpected(t); } } if (supportsPut(m)) { try { check(m.put(3333, 77777) == null); check(m.put(9134, 74982) == null); check(m.get(9134) == 74982); check(m.put(9134, 1382) == 74982); check(m.get(9134) == 1382); check(m.size() == 2); checkFunctionalInvariants(m); checkNPEConsistency(m); } catch (Throwable t) { unexpected(t); } } } private static boolean supportsPut(Map m) { // We're asking for .equals(...) semantics if (m instanceof IdentityHashMap) return false; try { check(m.put(778347983,12735) == null); } catch (UnsupportedOperationException t) { return false; } catch (Throwable t) { unexpected(t); } try { check(m.containsKey(778347983)); check(m.remove(778347983) != null); } catch (Throwable t) { unexpected(t); } return true; } private static boolean supportsClear(Map m) { try { m.clear(); } catch (UnsupportedOperationException t) { return false; } catch (Throwable t) { unexpected(t); } return true; } //---------------------------------------------------------------- // ConcurrentMap //---------------------------------------------------------------- private static void testConcurrentMap(ConcurrentMap m) { System.out.println("ConcurrentMap tests..."); try { clear(m); check(m.putIfAbsent(18357,7346) == null); check(m.containsKey(18357)); check(m.putIfAbsent(18357,8263) == 7346); try { m.putIfAbsent(18357,null); fail("NPE"); } catch (NullPointerException t) { } check(m.containsKey(18357)); check(! m.replace(18357,8888,7777)); check(m.containsKey(18357)); try { m.replace(18357,null,7777); fail("NPE"); } catch (NullPointerException t) { } check(m.containsKey(18357)); check(m.get(18357) == 7346); check(m.replace(18357,7346,5555)); check(m.replace(18357,5555,7346)); check(m.get(18357) == 7346); check(m.replace(92347,7834) == null); try { m.replace(18357,null); fail("NPE"); } catch (NullPointerException t) { } check(m.replace(18357,7346) == 7346); check(m.replace(18357,5555) == 7346); check(m.get(18357) == 5555); check(m.replace(18357,7346) == 5555); check(m.get(18357) == 7346); check(! m.remove(18357,9999)); check(m.get(18357) == 7346); check(m.containsKey(18357)); check(! m.remove(18357,null)); // 6272521 check(m.get(18357) == 7346); check(m.remove(18357,7346)); check(m.get(18357) == null); check(! m.containsKey(18357)); check(m.isEmpty()); m.putIfAbsent(1,2); check(m.size() == 1); check(! m.remove(1,null)); check(! m.remove(1,null)); check(! m.remove(1,1)); check(m.remove(1,2)); check(m.isEmpty()); testEmptyMap(m); } catch (Throwable t) { unexpected(t); } } private static void throwsConsistently(Class k, Iterable fs) { List> threw = new ArrayList>(); for (Fun f : fs) try { f.f(); threw.add(null); } catch (Throwable t) { check(k.isAssignableFrom(t.getClass())); threw.add(t.getClass()); } if (new HashSet(threw).size() != 1) fail(threw.toString()); } private static void checkNPEConsistency(final Map m) { m.clear(); final ConcurrentMap cm = (m instanceof ConcurrentMap) ? (ConcurrentMap) m : null; List fs = new ArrayList(); fs.add(new Fun(){void f(){ check(! m.containsKey(null));}}); fs.add(new Fun(){void f(){ equal(m.remove(null), null);}}); fs.add(new Fun(){void f(){ equal(m.get(null), null);}}); if (cm != null) { fs.add(new Fun(){void f(){ check(! cm.remove(null,null));}});} throwsConsistently(NullPointerException.class, fs); fs.clear(); final Map sm = singletonMap(null,1); fs.add(new Fun(){void f(){ equal(m.put(null,1), null); m.clear();}}); fs.add(new Fun(){void f(){ m.putAll(sm); m.clear();}}); if (cm != null) { fs.add(new Fun(){void f(){ check(! cm.remove(null,null));}}); fs.add(new Fun(){void f(){ equal(cm.putIfAbsent(null,1), 1);}}); fs.add(new Fun(){void f(){ equal(cm.replace(null,1), null);}}); fs.add(new Fun(){void f(){ equal(cm.replace(null,1, 1), 1);}}); } throwsConsistently(NullPointerException.class, fs); } //---------------------------------------------------------------- // NavigableMap //---------------------------------------------------------------- private static void checkNavigableMapKeys(NavigableMap m, Integer i, Integer lower, Integer floor, Integer ceiling, Integer higher) { equal(m.lowerKey(i), lower); equal(m.floorKey(i), floor); equal(m.ceilingKey(i), ceiling); equal(m.higherKey(i), higher); } private static void checkNavigableSetKeys(NavigableSet m, Integer i, Integer lower, Integer floor, Integer ceiling, Integer higher) { equal(m.lower(i), lower); equal(m.floor(i), floor); equal(m.ceiling(i), ceiling); equal(m.higher(i), higher); } static final Random rnd = new Random(); static void equalNext(final Iterator it, Object expected) { if (rnd.nextBoolean()) check(it.hasNext()); equal(it.next(), expected); } static 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())); } @SuppressWarnings({"unchecked", "rawtypes"}) static void testNavigableMapRemovers(NavigableMap m) { 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); } } } } private static void testNavigableMap(NavigableMap m) { clear(m); checkNavigableMapKeys(m, 1, null, null, null, null); equal(m.put(1, 2), null); equal(m.put(3, 4), null); equal(m.put(5, 9), null); equal(m.put(1, 2), 2); equal(m.put(3, 4), 4); equal(m.put(5, 6), 9); checkNavigableMapKeys(m, 0, null, null, 1, 1); checkNavigableMapKeys(m, 1, null, 1, 1, 3); checkNavigableMapKeys(m, 2, 1, 1, 3, 3); checkNavigableMapKeys(m, 3, 1, 3, 3, 5); checkNavigableMapKeys(m, 5, 3, 5, 5, null); checkNavigableMapKeys(m, 6, 5, 5, null, null); for (final Iterator it : (Iterator[]) new Iterator[] { m.descendingKeySet().iterator(), m.navigableKeySet().descendingIterator()}) { equalNext(it, 5); equalNext(it, 3); equalNext(it, 1); check(! it.hasNext()); THROWS(NoSuchElementException.class, new Fun(){void f(){it.next();}}); } { final Iterator> it = m.descendingMap().entrySet().iterator(); check(it.hasNext()); equal(it.next().getKey(), 5); check(it.hasNext()); equal(it.next().getKey(), 3); check(it.hasNext()); equal(it.next().getKey(), 1); check(! it.hasNext()); THROWS(NoSuchElementException.class, new Fun(){void f(){it.next();}}); } } private static void testNavigableSet(NavigableSet s) { clear(s); checkNavigableSetKeys(s, 1, null, null, null, null); check(s.add(1)); check(s.add(3)); check(s.add(5)); check(! s.add(1)); check(! s.add(3)); check(! s.add(5)); checkNavigableSetKeys(s, 0, null, null, 1, 1); checkNavigableSetKeys(s, 1, null, 1, 1, 3); checkNavigableSetKeys(s, 2, 1, 1, 3, 3); checkNavigableSetKeys(s, 3, 1, 3, 3, 5); checkNavigableSetKeys(s, 5, 3, 5, 5, null); checkNavigableSetKeys(s, 6, 5, 5, null, null); for (final Iterator it : (Iterator[]) new Iterator[] { s.descendingIterator(), s.descendingSet().iterator()}) { equalNext(it, 5); equalNext(it, 3); equalNext(it, 1); check(! it.hasNext()); THROWS(NoSuchElementException.class, new Fun(){void f(){it.next();}}); } } //--------------------- Infrastructure --------------------------- static volatile int passed = 0, failed = 0; static void pass() { passed++; } static void fail() { failed++; Thread.dumpStack(); } static void fail(String msg) { System.out.println(msg); fail(); } static void unexpected(Throwable t) { failed++; t.printStackTrace(); } static void check(boolean cond) { if (cond) pass(); else fail(); } static void equal(Object x, Object y) { if (x == null ? y == null : x.equals(y)) pass(); else {System.out.println(x + " not equal to " + y); fail();}} static void equal2(Object x, Object y) {equal(x, y); equal(y, x);} public static void main(String[] args) throws Throwable { try { realMain(args); } catch (Throwable t) { unexpected(t); } System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); if (failed > 0) throw new Exception("Some tests failed"); } private static abstract class Fun {abstract void f() throws Throwable;} private static void THROWS(Class k, Fun... fs) { for (Fun f : fs) try { f.f(); fail("Expected " + k.getName() + " not thrown"); } catch (Throwable t) { if (k.isAssignableFrom(t.getClass())) pass(); else unexpected(t);}} static byte[] serializedForm(Object obj) { try { ByteArrayOutputStream baos = new ByteArrayOutputStream(); new ObjectOutputStream(baos).writeObject(obj); return baos.toByteArray(); } catch (IOException e) { throw new Error(e); }} static Object readObject(byte[] bytes) throws IOException, ClassNotFoundException { InputStream is = new ByteArrayInputStream(bytes); return new ObjectInputStream(is).readObject();} @SuppressWarnings("unchecked") static T serialClone(T obj) { try { return (T) readObject(serializedForm(obj)); } catch (Exception e) { throw new Error(e); }} private static class NewAbstractCollection extends AbstractCollection { ArrayList list = new ArrayList<>(); public boolean remove(Object obj) { return list.remove(obj); } public boolean add(E e) { return list.add(e); } public Iterator iterator() { return list.iterator(); } public int size() { return list.size(); } } private static class NewAbstractSet extends AbstractSet { HashSet set = new HashSet<>(); public boolean remove(Object obj) { return set.remove(obj); } public boolean add(E e) { return set.add(e); } public Iterator iterator() { return set.iterator(); } public int size() { return set.size(); } } }