1 /*
   2  * Copyright (c) 2005, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 /*
  25  * @test
  26  * @bug     6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464
  27  *          4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753
  28  *          6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215
  29  *          4802647 7123424 8024709
  30  * @summary Run many tests on many Collection and Map implementations
  31  * @author  Martin Buchholz
  32  * @modules java.base/java.util:open
  33  * @run main MOAT
  34  * @key randomness
  35  */
  36 
  37 /* Mother Of All (Collection) Tests
  38  *
  39  * Testing of collection classes is often spotty, because many tests
  40  * need to be performed on many implementations, but the onus on
  41  * writing the tests falls on the engineer introducing the new
  42  * implementation.
  43  *
  44  * The idea of this mega-test is that:
  45  *
  46  * An engineer adding a new collection implementation could simply add
  47  * their new implementation to a list of implementations in this
  48  * test's main method.  Any general purpose Collection<Integer> or
  49  * Map<Integer,Integer> class is appropriate.
  50  *
  51  * An engineer fixing a regression could add their regression test here and
  52  * simultaneously test all other implementations.
  53  */
  54 
  55 import java.io.*;
  56 import java.util.*;
  57 import java.util.concurrent.*;
  58 import static java.util.Collections.*;
  59 import java.lang.reflect.*;
  60 
  61 public class MOAT {
  62     // Collections under test must not be initialized to contain this value,
  63     // and maps under test must not contain this value as a key.
  64     // It's used as a sentinel for absent-element testing.
  65     static final int ABSENT_VALUE = 778347983;
  66 
  67     static final Integer[] integerArray;
  68     static {
  69         Integer[] ia = new Integer[20];
  70         // fill with 1..20 inclusive
  71         for (int i = 0; i < ia.length; i++) {
  72             ia[i] = i + 1;
  73         }
  74         integerArray = ia;
  75     }
  76 
  77     public static void realMain(String[] args) {
  78 
  79         testCollection(new NewAbstractCollection<Integer>());
  80         testCollection(new NewAbstractSet<Integer>());
  81         testCollection(new LinkedHashSet<Integer>());
  82         testCollection(new HashSet<Integer>());
  83         testCollection(new Vector<Integer>());
  84         testCollection(new Vector<Integer>().subList(0,0));
  85         testCollection(new ArrayDeque<Integer>());
  86         testCollection(new ArrayList<Integer>());
  87         testCollection(new ArrayList<Integer>().subList(0,0));
  88         testCollection(new LinkedList<Integer>());
  89         testCollection(new LinkedList<Integer>().subList(0,0));
  90         testCollection(new TreeSet<Integer>());
  91         testCollection(Collections.checkedList(new ArrayList<Integer>(), Integer.class));
  92         testCollection(Collections.synchronizedList(new ArrayList<Integer>()));
  93         testCollection(Collections.checkedSet(new HashSet<Integer>(), Integer.class));
  94         testCollection(Collections.checkedSortedSet(new TreeSet<Integer>(), Integer.class));
  95         testCollection(Collections.checkedNavigableSet(new TreeSet<Integer>(), Integer.class));
  96         testCollection(Collections.synchronizedSet(new HashSet<Integer>()));
  97         testCollection(Collections.synchronizedSortedSet(new TreeSet<Integer>()));
  98         testCollection(Collections.synchronizedNavigableSet(new TreeSet<Integer>()));
  99 
 100         testCollection(new CopyOnWriteArrayList<Integer>());
 101         testCollection(new CopyOnWriteArrayList<Integer>().subList(0,0));
 102         testCollection(new CopyOnWriteArraySet<Integer>());
 103         testCollection(new PriorityQueue<Integer>());
 104         testCollection(new PriorityBlockingQueue<Integer>());
 105         testCollection(new ArrayBlockingQueue<Integer>(20));
 106         testCollection(new LinkedBlockingQueue<Integer>(20));
 107         testCollection(new LinkedBlockingDeque<Integer>(20));
 108         testCollection(new ConcurrentLinkedDeque<Integer>());
 109         testCollection(new ConcurrentLinkedQueue<Integer>());
 110         testCollection(new LinkedTransferQueue<Integer>());
 111         testCollection(new ConcurrentSkipListSet<Integer>());
 112         testCollection(Arrays.asList(new Integer(42)));
 113         testCollection(Arrays.asList(1,2,3));
 114         testCollection(nCopies(25,1));
 115         testImmutableList(nCopies(25,1));
 116 
 117         testMap(new HashMap<Integer,Integer>());
 118         testMap(new LinkedHashMap<Integer,Integer>());
 119 
 120         // TODO: Add reliable support for WeakHashMap.
 121         // This test is subject to very rare failures because the GC
 122         // may remove unreferenced-keys from the map at any time.
 123         // testMap(new WeakHashMap<Integer,Integer>());
 124 
 125         testMap(new IdentityHashMap<Integer,Integer>());
 126         testMap(new TreeMap<Integer,Integer>());
 127         testMap(new Hashtable<Integer,Integer>());
 128         testMap(new ConcurrentHashMap<Integer,Integer>(10, 0.5f));
 129         testMap(new ConcurrentSkipListMap<Integer,Integer>());
 130         testMap(Collections.checkedMap(new HashMap<Integer,Integer>(), Integer.class, Integer.class));
 131         testMap(Collections.checkedSortedMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));
 132         testMap(Collections.checkedNavigableMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class));
 133         testMap(Collections.synchronizedMap(new HashMap<Integer,Integer>()));
 134         testMap(Collections.synchronizedSortedMap(new TreeMap<Integer,Integer>()));
 135         testMap(Collections.synchronizedNavigableMap(new TreeMap<Integer,Integer>()));
 136 
 137         // Unmodifiable wrappers
 138         testImmutableSet(unmodifiableSet(new HashSet<>(Arrays.asList(1,2,3))));
 139         testImmutableList(unmodifiableList(Arrays.asList(1,2,3)));
 140         testImmutableMap(unmodifiableMap(Collections.singletonMap(1,2)));
 141         testCollMutatorsAlwaysThrow(unmodifiableSet(new HashSet<>(Arrays.asList(1,2,3))));
 142         testCollMutatorsAlwaysThrow(unmodifiableSet(Collections.emptySet()));
 143         testEmptyCollMutatorsAlwaysThrow(unmodifiableSet(Collections.emptySet()));
 144         testListMutatorsAlwaysThrow(unmodifiableList(Arrays.asList(1,2,3)));
 145         testListMutatorsAlwaysThrow(unmodifiableList(Collections.emptyList()));
 146         testEmptyListMutatorsAlwaysThrow(unmodifiableList(Collections.emptyList()));
 147         testMapMutatorsAlwaysThrow(unmodifiableMap(Collections.singletonMap(1,2)));
 148         testMapMutatorsAlwaysThrow(unmodifiableMap(Collections.emptyMap()));
 149         testEmptyMapMutatorsAlwaysThrow(unmodifiableMap(Collections.emptyMap()));
 150 
 151         // Empty collections
 152         final List<Integer> emptyArray = Arrays.asList(new Integer[]{});
 153         testCollection(emptyArray);
 154         testEmptyList(emptyArray);
 155         THROWS(IndexOutOfBoundsException.class, () -> emptyArray.set(0,1));
 156         THROWS(UnsupportedOperationException.class, () -> emptyArray.add(0,1));
 157 
 158         List<Integer> noOne = nCopies(0,1);
 159         testCollection(noOne);
 160         testEmptyList(noOne);
 161         testImmutableList(noOne);
 162 
 163         Set<Integer> emptySet = emptySet();
 164         testCollection(emptySet);
 165         testEmptySet(emptySet);
 166         testEmptySet(EMPTY_SET);
 167         testEmptySet(Collections.emptySet());
 168         testEmptySet(Collections.emptySortedSet());
 169         testEmptySet(Collections.emptyNavigableSet());
 170         testImmutableSet(emptySet);
 171 
 172         List<Integer> emptyList = emptyList();
 173         testCollection(emptyList);
 174         testEmptyList(emptyList);
 175         testEmptyList(EMPTY_LIST);
 176         testEmptyList(Collections.emptyList());
 177         testImmutableList(emptyList);
 178 
 179         Map<Integer,Integer> emptyMap = emptyMap();
 180         testMap(emptyMap);
 181         testEmptyMap(emptyMap);
 182         testEmptyMap(EMPTY_MAP);
 183         testEmptyMap(Collections.emptyMap());
 184         testEmptyMap(Collections.emptySortedMap());
 185         testEmptyMap(Collections.emptyNavigableMap());
 186         testImmutableMap(emptyMap);
 187         testImmutableMap(Collections.emptyMap());
 188         testImmutableMap(Collections.emptySortedMap());
 189         testImmutableMap(Collections.emptyNavigableMap());
 190 
 191         // Singleton collections
 192         Set<Integer> singletonSet = singleton(1);
 193         equal(singletonSet.size(), 1);
 194         testCollection(singletonSet);
 195         testImmutableSet(singletonSet);
 196 
 197         List<Integer> singletonList = singletonList(1);
 198         equal(singletonList.size(), 1);
 199         testCollection(singletonList);
 200         testImmutableList(singletonList);
 201         testImmutableList(singletonList.subList(0,1));
 202         testImmutableList(singletonList.subList(0,1).subList(0,1));
 203         testEmptyList(singletonList.subList(0,0));
 204         testEmptyList(singletonList.subList(0,0).subList(0,0));
 205 
 206         Map<Integer,Integer> singletonMap = singletonMap(1,2);
 207         equal(singletonMap.size(), 1);
 208         testMap(singletonMap);
 209         testImmutableMap(singletonMap);
 210 
 211         // Immutable List
 212         testEmptyList(List.of());
 213         testListMutatorsAlwaysThrow(List.of());
 214         testEmptyListMutatorsAlwaysThrow(List.of());
 215         for (List<Integer> list : Arrays.asList(
 216                 List.<Integer>of(),
 217                 List.of(1),
 218                 List.of(1, 2),
 219                 List.of(1, 2, 3),
 220                 List.of(1, 2, 3, 4),
 221                 List.of(1, 2, 3, 4, 5),
 222                 List.of(1, 2, 3, 4, 5, 6),
 223                 List.of(1, 2, 3, 4, 5, 6, 7),
 224                 List.of(1, 2, 3, 4, 5, 6, 7, 8),
 225                 List.of(1, 2, 3, 4, 5, 6, 7, 8, 9),
 226                 List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),
 227                 List.of(integerArray))) {
 228             testCollection(list);
 229             testImmutableList(list);
 230             testListMutatorsAlwaysThrow(list);
 231         }
 232 
 233         // Immutable Set
 234         testEmptySet(Set.of());
 235         testCollMutatorsAlwaysThrow(Set.of());
 236         testEmptyCollMutatorsAlwaysThrow(Set.of());
 237         for (Set<Integer> set : Arrays.asList(
 238                 Set.<Integer>of(),
 239                 Set.of(1),
 240                 Set.of(1, 2),
 241                 Set.of(1, 2, 3),
 242                 Set.of(1, 2, 3, 4),
 243                 Set.of(1, 2, 3, 4, 5),
 244                 Set.of(1, 2, 3, 4, 5, 6),
 245                 Set.of(1, 2, 3, 4, 5, 6, 7),
 246                 Set.of(1, 2, 3, 4, 5, 6, 7, 8),
 247                 Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9),
 248                 Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),
 249                 Set.of(integerArray))) {
 250             testCollection(set);
 251             testImmutableSet(set);
 252             testCollMutatorsAlwaysThrow(set);
 253         }
 254 
 255         // Immutable Map
 256 
 257         @SuppressWarnings("unchecked")
 258         Map.Entry<Integer,Integer>[] ea = (Map.Entry<Integer,Integer>[])new Map.Entry<?,?>[20];
 259         for (int i = 0; i < ea.length; i++) {
 260             ea[i] = Map.entry(i+1, i+101);
 261         }
 262 
 263         testEmptyMap(Map.of());
 264         testMapMutatorsAlwaysThrow(Map.of());
 265         testEmptyMapMutatorsAlwaysThrow(Map.of());
 266         for (Map<Integer,Integer> map : Arrays.asList(
 267                 Map.<Integer,Integer>of(),
 268                 Map.of(1, 101),
 269                 Map.of(1, 101, 2, 202),
 270                 Map.of(1, 101, 2, 202, 3, 303),
 271                 Map.of(1, 101, 2, 202, 3, 303, 4, 404),
 272                 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505),
 273                 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606),
 274                 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707),
 275                 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808),
 276                 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909),
 277                 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909, 10, 1010),
 278                 Map.ofEntries(ea))) {
 279             testMap(map);
 280             testImmutableMap(map);
 281             testMapMutatorsAlwaysThrow(map);
 282         }
 283     }
 284 
 285     private static void checkContainsSelf(Collection<Integer> c) {
 286         check(c.containsAll(c));
 287         check(c.containsAll(Arrays.asList(c.toArray())));
 288         check(c.containsAll(Arrays.asList(c.toArray(new Integer[0]))));
 289     }
 290 
 291     private static void checkContainsEmpty(Collection<Integer> c) {
 292         check(c.containsAll(new ArrayList<Integer>()));
 293     }
 294 
 295     private static void checkUnique(Set<Integer> s) {
 296         for (Integer i : s) {
 297             int count = 0;
 298             for (Integer j : s) {
 299                 if (Objects.equals(i,j))
 300                     ++count;
 301             }
 302             check(count == 1);
 303         }
 304     }
 305 
 306     private static <T> void testEmptyCollection(Collection<T> c) {
 307         check(c.isEmpty());
 308         equal(c.size(), 0);
 309         equal(c.toString(),"[]");
 310         equal(c.toArray().length, 0);
 311         equal(c.toArray(new Object[0]).length, 0);
 312         check(c.toArray(new Object[]{42})[0] == null);
 313 
 314         Object[] a = new Object[1]; a[0] = Boolean.TRUE;
 315         equal(c.toArray(a), a);
 316         equal(a[0], null);
 317         testEmptyIterator(c.iterator());
 318     }
 319 
 320     static <T> void testEmptyIterator(final Iterator<T> it) {
 321         if (rnd.nextBoolean())
 322             check(! it.hasNext());
 323 
 324         THROWS(NoSuchElementException.class, () -> it.next());
 325 
 326         try { it.remove(); }
 327         catch (IllegalStateException ignored) { pass(); }
 328         catch (UnsupportedOperationException ignored) { pass(); }
 329         catch (Throwable t) { unexpected(t); }
 330 
 331         if (rnd.nextBoolean())
 332             check(! it.hasNext());
 333     }
 334 
 335     private static void testEmptyList(List<?> c) {
 336         testEmptyCollection(c);
 337         equal(c.hashCode(), 1);
 338         equal2(c, Collections.<Integer>emptyList());
 339     }
 340 
 341     private static <T> void testEmptySet(Set<T> c) {
 342         testEmptyCollection(c);
 343         equal(c.hashCode(), 0);
 344         equal2(c, Collections.<Integer>emptySet());
 345         if (c instanceof NavigableSet<?>)
 346             testEmptyIterator(((NavigableSet<T>)c).descendingIterator());
 347     }
 348 
 349     private static void testImmutableCollection(final Collection<Integer> c) {
 350         THROWS(UnsupportedOperationException.class,
 351                () -> c.add(99),
 352                () -> c.addAll(singleton(99)));
 353         if (! c.isEmpty()) {
 354             final Integer first = c.iterator().next();
 355             THROWS(UnsupportedOperationException.class,
 356                    () -> c.clear(),
 357                    () -> c.remove(first),
 358                    () -> c.removeAll(singleton(first)),
 359                    () -> c.retainAll(emptyList()));
 360         }
 361     }
 362 
 363     private static void testImmutableSet(final Set<Integer> c) {
 364         testImmutableCollection(c);
 365     }
 366 
 367     private static void testImmutableList(final List<Integer> c) {
 368         testList(c);
 369         testImmutableCollection(c);
 370         THROWS(UnsupportedOperationException.class,
 371                () -> c.set(0,42),
 372                () -> c.add(0,42),
 373                () -> c.addAll(0,singleton(86)));
 374         if (! c.isEmpty())
 375             THROWS(UnsupportedOperationException.class,
 376                    () -> { Iterator<Integer> it = c.iterator();
 377                            it.next();
 378                            it.remove(); },
 379                    () -> { ListIterator<Integer> it = c.listIterator();
 380                            it.next();
 381                            it.remove(); });
 382     }
 383 
 384     /**
 385      * Test that calling a mutator always throws UOE, even if the mutator
 386      * wouldn't actually do anything, given its arguments.
 387      *
 388      * @param c the collection instance to test
 389      */
 390     private static void testCollMutatorsAlwaysThrow(Collection<Integer> c) {
 391         THROWS(UnsupportedOperationException.class,
 392                 () -> c.addAll(Collections.emptyList()),
 393                 () -> c.remove(ABSENT_VALUE),
 394                 () -> c.removeAll(Collections.emptyList()),
 395                 () -> c.removeIf(x -> false),
 396                 () -> c.retainAll(c));
 397     }
 398 
 399     /**
 400      * Test that calling a mutator always throws UOE, even if the mutator
 401      * wouldn't actually do anything on an empty collection.
 402      *
 403      * @param c the collection instance to test, must be empty
 404      */
 405     private static void testEmptyCollMutatorsAlwaysThrow(Collection<Integer> c) {
 406         if (! c.isEmpty()) {
 407             fail("collection is not empty");
 408         }
 409         THROWS(UnsupportedOperationException.class,
 410                 () -> c.clear());
 411     }
 412 
 413     /**
 414      * As above, for a list.
 415      *
 416      * @param c the list instance to test
 417      */
 418     private static void testListMutatorsAlwaysThrow(List<Integer> c) {
 419         testCollMutatorsAlwaysThrow(c);
 420         THROWS(UnsupportedOperationException.class,
 421                 () -> c.addAll(0, Collections.emptyList()));
 422     }
 423 
 424     /**
 425      * As above, for an empty list.
 426      *
 427      * @param c the list instance to test, must be empty
 428      */
 429     private static void testEmptyListMutatorsAlwaysThrow(List<Integer> c) {
 430         if (! c.isEmpty()) {
 431             fail("list is not empty");
 432         }
 433         testEmptyCollMutatorsAlwaysThrow(c);
 434         THROWS(UnsupportedOperationException.class,
 435                 () -> c.replaceAll(x -> x),
 436                 () -> c.sort(null));
 437     }
 438 
 439     /**
 440      * As above, for a map.
 441      *
 442      * @param m the map instance to test
 443      */
 444     private static void testMapMutatorsAlwaysThrow(Map<Integer,Integer> m) {
 445         THROWS(UnsupportedOperationException.class,
 446                 () -> m.compute(ABSENT_VALUE, (k, v) -> null),
 447                 () -> m.computeIfAbsent(ABSENT_VALUE, k -> null),
 448                 () -> m.computeIfPresent(ABSENT_VALUE, (k, v) -> null),
 449                 () -> m.merge(ABSENT_VALUE, 0, (k, v) -> null),
 450                 () -> m.putAll(Collections.emptyMap()),
 451                 () -> m.remove(ABSENT_VALUE),
 452                 () -> m.remove(ABSENT_VALUE, 0),
 453                 () -> m.replace(ABSENT_VALUE, 0),
 454                 () -> m.replace(ABSENT_VALUE, 0, 1));
 455     }
 456 
 457     /**
 458      * As above, for an empty map.
 459      *
 460      * @param map the map instance to test, must be empty
 461      */
 462     private static void testEmptyMapMutatorsAlwaysThrow(Map<Integer,Integer> m) {
 463         if (! m.isEmpty()) {
 464             fail("map is not empty");
 465         }
 466         THROWS(UnsupportedOperationException.class,
 467                 () -> m.clear(),
 468                 () -> m.replaceAll((k, v) -> v));
 469     }
 470 
 471     private static void clear(Collection<Integer> c) {
 472         try { c.clear(); }
 473         catch (Throwable t) { unexpected(t); }
 474         testEmptyCollection(c);
 475     }
 476 
 477     private static <K,V> void testEmptyMap(final Map<K,V> m) {
 478         check(m.isEmpty());
 479         equal(m.size(), 0);
 480         equal(m.toString(),"{}");
 481         testEmptySet(m.keySet());
 482         testEmptySet(m.entrySet());
 483         testEmptyCollection(m.values());
 484 
 485         try { check(! m.containsValue(null)); }
 486         catch (NullPointerException ignored) { /* OK */ }
 487         try { check(! m.containsKey(null)); }
 488         catch (NullPointerException ignored) { /* OK */ }
 489         check(! m.containsValue(1));
 490         check(! m.containsKey(1));
 491     }
 492 
 493     private static void testImmutableMap(final Map<Integer,Integer> m) {
 494         THROWS(UnsupportedOperationException.class,
 495                () -> m.put(1,1),
 496                () -> m.putAll(singletonMap(1,1)));
 497         if (! m.isEmpty()) {
 498             final Integer first = m.keySet().iterator().next();
 499             THROWS(UnsupportedOperationException.class,
 500                    () -> m.remove(first),
 501                    () -> m.clear());
 502             final Map.Entry<Integer,Integer> me
 503                 = m.entrySet().iterator().next();
 504             Integer key = me.getKey();
 505             Integer val = me.getValue();
 506             THROWS(UnsupportedOperationException.class,
 507                    () -> me.setValue(3));
 508             equal(key, me.getKey());
 509             equal(val, me.getValue());
 510         }
 511         testImmutableSet(m.keySet());
 512         testImmutableCollection(m.values());
 513         //testImmutableSet(m.entrySet());
 514     }
 515 
 516     private static void clear(Map<?,?> m) {
 517         try { m.clear(); }
 518         catch (Throwable t) { unexpected(t); }
 519         testEmptyMap(m);
 520     }
 521 
 522     private static void oneElement(Collection<Integer> c) {
 523         clear(c);
 524         try {
 525             check(c.add(-42));
 526             equal(c.toString(), "[-42]");
 527             if (c instanceof Set) check(! c.add(-42));
 528         } catch (Throwable t) { unexpected(t); }
 529         check(! c.isEmpty()); check(c.size() == 1);
 530     }
 531 
 532     private static boolean supportsAdd(Collection<Integer> c) {
 533         try { check(c.add(ABSENT_VALUE)); }
 534         catch (UnsupportedOperationException t) { return false; }
 535         catch (Throwable t) { unexpected(t); }
 536 
 537         try {
 538             check(c.contains(ABSENT_VALUE));
 539             check(c.remove(ABSENT_VALUE));
 540         } catch (Throwable t) { unexpected(t); }
 541         return true;
 542     }
 543 
 544     private static boolean supportsRemove(Collection<Integer> c) {
 545         try { check(! c.remove(ABSENT_VALUE)); }
 546         catch (UnsupportedOperationException t) { return false; }
 547         catch (Throwable t) { unexpected(t); }
 548         return true;
 549     }
 550 
 551     // 6260652: (coll) Arrays.asList(x).toArray().getClass()
 552     //          should be Object[].class
 553     // Fixed in jdk9, but not jdk8 ...
 554     static final boolean needToWorkAround6260652 =
 555         Arrays.asList("").toArray().getClass() != Object[].class;
 556 
 557     private static void checkFunctionalInvariants(Collection<Integer> c) {
 558         try {
 559             checkContainsSelf(c);
 560             checkContainsEmpty(c);
 561             check(c.size() != 0 ^ c.isEmpty());
 562             check(! c.contains(ABSENT_VALUE));
 563 
 564             {
 565                 int size = 0;
 566                 for (Integer i : c) size++;
 567                 check(c.size() == size);
 568             }
 569 
 570             if (c instanceof Set) {
 571                 checkUnique((Set<Integer>)c);
 572             }
 573 
 574             check(c.toArray().length == c.size());
 575             check(c.toArray().getClass() == Object[].class
 576                   ||
 577                   (needToWorkAround6260652 &&
 578                    c.getClass().getName().equals("java.util.Arrays$ArrayList")));
 579             for (int size : new int[]{0,1,c.size(), c.size()+1}) {
 580                 Integer[] a = c.toArray(new Integer[size]);
 581                 check((size > c.size()) || a.length == c.size());
 582                 int i = 0; for (Integer j : c) check(a[i++] == j);
 583                 check((size <= c.size()) || (a[c.size()] == null));
 584                 check(a.getClass() == Integer[].class);
 585             }
 586 
 587             check(c.equals(c));
 588             if (c instanceof Serializable) {
 589                 //System.out.printf("Serializing %s%n", c.getClass().getName());
 590                 try {
 591                     Object clone = serialClone(c);
 592                     equal(c instanceof Serializable,
 593                           clone instanceof Serializable);
 594                     equal(c instanceof RandomAccess,
 595                           clone instanceof RandomAccess);
 596                     if ((c instanceof List) || (c instanceof Set))
 597                         equal(c, clone);
 598                     else
 599                         equal(new HashSet<Integer>(c),
 600                               new HashSet<Integer>(serialClone(c)));
 601                 } catch (Error xxx) {
 602                     if (! (xxx.getCause() instanceof NotSerializableException))
 603                         throw xxx;
 604                 }
 605             }
 606         }
 607         catch (Throwable t) { unexpected(t); }
 608     }
 609 
 610     //----------------------------------------------------------------
 611     // If add(null) succeeds, contains(null) & remove(null) should succeed
 612     //----------------------------------------------------------------
 613     private static void testNullElement(Collection<Integer> c) {
 614 
 615         try {
 616             check(c.add(null));
 617             if (c.size() == 1)
 618                 equal(c.toString(), "[null]");
 619             try {
 620                 checkFunctionalInvariants(c);
 621                 check(c.contains(null));
 622                 check(c.remove(null));
 623             }
 624             catch (Throwable t) { unexpected(t); }
 625         }
 626         catch (NullPointerException e) { /* OK */ }
 627         catch (Throwable t) { unexpected(t); }
 628     }
 629 
 630     //----------------------------------------------------------------
 631     // If add("x") succeeds, contains("x") & remove("x") should succeed
 632     //----------------------------------------------------------------
 633     @SuppressWarnings("unchecked")
 634     private static void testStringElement(Collection<Integer> c) {
 635         Collection x = (Collection)c; // Make type-unsafe
 636         try {
 637             check(x.add("x"));
 638             try {
 639                 check(x.contains("x"));
 640                 check(x.remove("x"));
 641             } catch (Throwable t) { unexpected(t); }
 642         }
 643         catch (ClassCastException e) { /* OK */ }
 644         catch (Throwable t) { unexpected(t); }
 645     }
 646 
 647     private static void testConcurrentCollection(Collection<Integer> c) {
 648         try {
 649             c.add(1);
 650             Iterator<Integer> it = c.iterator();
 651             check(it.hasNext());
 652             clear(c);
 653             check(it.next() instanceof Integer); // No CME
 654             check(c.isEmpty());
 655         }
 656         catch (Throwable t) { unexpected(t); }
 657     }
 658 
 659     private static void testQueue(Queue<Integer> q) {
 660         q.clear();
 661         for (int i = 0; i < 5; i++) {
 662             testQueueAddRemove(q, null);
 663             testQueueAddRemove(q, 537);
 664             q.add(i);
 665         }
 666         equal(q.size(), 5);
 667         checkFunctionalInvariants(q);
 668         q.poll();
 669         equal(q.size(), 4);
 670         checkFunctionalInvariants(q);
 671         if ((q instanceof LinkedBlockingQueue)   ||
 672             (q instanceof LinkedBlockingDeque)   ||
 673             (q instanceof ConcurrentLinkedDeque) ||
 674             (q instanceof ConcurrentLinkedQueue)) {
 675             testQueueIteratorRemove(q);
 676         }
 677     }
 678 
 679     private static void testQueueAddRemove(final Queue<Integer> q,
 680                                            final Integer e) {
 681         final List<Integer> originalContents = new ArrayList<>(q);
 682         final boolean isEmpty = q.isEmpty();
 683         final boolean isList = (q instanceof List);
 684         final List asList = isList ? (List) q : null;
 685         check(!q.contains(e));
 686         try {
 687             q.add(e);
 688         } catch (NullPointerException npe) {
 689             check(e == null);
 690             return;                     // Null elements not supported
 691         }
 692         check(q.contains(e));
 693         check(q.remove(e));
 694         check(!q.contains(e));
 695         equal(new ArrayList<Integer>(q), originalContents);
 696 
 697         if (q instanceof Deque<?>) {
 698             final Deque<Integer> deq = (Deque<Integer>) q;
 699             final List<Integer> singleton = Collections.singletonList(e);
 700 
 701             // insert, query, remove element at head
 702             if (isEmpty) {
 703                 THROWS(NoSuchElementException.class,
 704                        () -> deq.getFirst(),
 705                        () -> deq.element(),
 706                        () -> deq.iterator().next());
 707                 check(deq.peekFirst() == null);
 708                 check(deq.peek() == null);
 709             } else {
 710                 check(deq.getFirst() != e);
 711                 check(deq.element() != e);
 712                 check(deq.iterator().next() != e);
 713                 check(deq.peekFirst() != e);
 714                 check(deq.peek() != e);
 715             }
 716             check(!deq.contains(e));
 717             check(!deq.removeFirstOccurrence(e));
 718             check(!deq.removeLastOccurrence(e));
 719             if (isList) {
 720                 check(asList.indexOf(e) == -1);
 721                 check(asList.lastIndexOf(e) == -1);
 722             }
 723             switch (rnd.nextInt(isList ? 4 : 3)) {
 724             case 0: deq.addFirst(e); break;
 725             case 1: check(deq.offerFirst(e)); break;
 726             case 2: deq.push(e); break;
 727             case 3: asList.add(0, e); break;
 728             default: throw new AssertionError();
 729             }
 730             check(deq.peekFirst() == e);
 731             check(deq.getFirst() == e);
 732             check(deq.element() == e);
 733             check(deq.peek() == e);
 734             check(deq.iterator().next() == e);
 735             check(deq.contains(e));
 736             if (isList) {
 737                 check(asList.get(0) == e);
 738                 check(asList.indexOf(e) == 0);
 739                 check(asList.lastIndexOf(e) == 0);
 740                 check(asList.subList(0, 1).equals(singleton));
 741             }
 742             switch (rnd.nextInt(isList ? 11 : 9)) {
 743             case 0: check(deq.pollFirst() == e); break;
 744             case 1: check(deq.removeFirst() == e); break;
 745             case 2: check(deq.remove() == e); break;
 746             case 3: check(deq.pop() == e); break;
 747             case 4: check(deq.removeFirstOccurrence(e)); break;
 748             case 5: check(deq.removeLastOccurrence(e)); break;
 749             case 6: check(deq.remove(e)); break;
 750             case 7: check(deq.removeAll(singleton)); break;
 751             case 8: Iterator it = deq.iterator(); it.next(); it.remove(); break;
 752             case 9: asList.remove(0); break;
 753             case 10: asList.subList(0, 1).clear(); break;
 754             default: throw new AssertionError();
 755             }
 756             if (isEmpty) {
 757                 THROWS(NoSuchElementException.class,
 758                        () -> deq.getFirst(),
 759                        () -> deq.element(),
 760                        () -> deq.iterator().next());
 761                 check(deq.peekFirst() == null);
 762                 check(deq.peek() == null);
 763             } else {
 764                 check(deq.getFirst() != e);
 765                 check(deq.element() != e);
 766                 check(deq.iterator().next() != e);
 767                 check(deq.peekFirst() != e);
 768                 check(deq.peek() != e);
 769             }
 770             check(!deq.contains(e));
 771             check(!deq.removeFirstOccurrence(e));
 772             check(!deq.removeLastOccurrence(e));
 773             if (isList) {
 774                 check(isEmpty || asList.get(0) != e);
 775                 check(asList.indexOf(e) == -1);
 776                 check(asList.lastIndexOf(e) == -1);
 777             }
 778             equal(new ArrayList<Integer>(deq), originalContents);
 779 
 780             // insert, query, remove element at tail
 781             if (isEmpty) {
 782                 check(deq.peekLast() == null);
 783                 THROWS(NoSuchElementException.class, () -> deq.getLast());
 784             } else {
 785                 check(deq.peekLast() != e);
 786                 check(deq.getLast() != e);
 787             }
 788             switch (rnd.nextInt(isList ? 6 : 4)) {
 789             case 0: deq.addLast(e); break;
 790             case 1: check(deq.offerLast(e)); break;
 791             case 2: check(deq.add(e)); break;
 792             case 3: deq.addAll(singleton); break;
 793             case 4: asList.addAll(deq.size(), singleton); break;
 794             case 5: asList.add(deq.size(), e); break;
 795             default: throw new AssertionError();
 796             }
 797             check(deq.peekLast() == e);
 798             check(deq.getLast() == e);
 799             check(deq.contains(e));
 800             if (isList) {
 801                 ListIterator it = asList.listIterator(asList.size());
 802                 check(it.previous() == e);
 803                 check(asList.get(asList.size() - 1) == e);
 804                 check(asList.indexOf(e) == asList.size() - 1);
 805                 check(asList.lastIndexOf(e) == asList.size() - 1);
 806                 int size = asList.size();
 807                 check(asList.subList(size - 1, size).equals(singleton));
 808             }
 809             switch (rnd.nextInt(isList ? 8 : 6)) {
 810             case 0: check(deq.pollLast() == e); break;
 811             case 1: check(deq.removeLast() == e); break;
 812             case 2: check(deq.removeFirstOccurrence(e)); break;
 813             case 3: check(deq.removeLastOccurrence(e)); break;
 814             case 4: check(deq.remove(e)); break;
 815             case 5: check(deq.removeAll(singleton)); break;
 816             case 6: asList.remove(asList.size() - 1); break;
 817             case 7:
 818                 ListIterator it = asList.listIterator(asList.size());
 819                 it.previous();
 820                 it.remove();
 821                 break;
 822             default: throw new AssertionError();
 823             }
 824             if (isEmpty) {
 825                 check(deq.peekLast() == null);
 826                 THROWS(NoSuchElementException.class, () -> deq.getLast());
 827             } else {
 828                 check(deq.peekLast() != e);
 829                 check(deq.getLast() != e);
 830             }
 831             check(!deq.contains(e));
 832             equal(new ArrayList<Integer>(deq), originalContents);
 833 
 834             // Test operations on empty deque
 835             switch (rnd.nextInt(isList ? 4 : 2)) {
 836             case 0: deq.clear(); break;
 837             case 1:
 838                 Iterator it = deq.iterator();
 839                 while (it.hasNext()) {
 840                     it.next();
 841                     it.remove();
 842                 }
 843                 break;
 844             case 2: asList.subList(0, asList.size()).clear(); break;
 845             case 3:
 846                 ListIterator lit = asList.listIterator(asList.size());
 847                 while (lit.hasPrevious()) {
 848                     lit.previous();
 849                     lit.remove();
 850                 }
 851                 break;
 852             default: throw new AssertionError();
 853             }
 854             testEmptyCollection(deq);
 855             check(!deq.iterator().hasNext());
 856             if (isList) {
 857                 check(!asList.listIterator().hasPrevious());
 858                 THROWS(NoSuchElementException.class,
 859                        () -> asList.listIterator().previous());
 860             }
 861             THROWS(NoSuchElementException.class,
 862                    () -> deq.iterator().next(),
 863                    () -> deq.element(),
 864                    () -> deq.getFirst(),
 865                    () -> deq.getLast(),
 866                    () -> deq.pop(),
 867                    () -> deq.remove(),
 868                    () -> deq.removeFirst(),
 869                    () -> deq.removeLast());
 870 
 871             check(deq.poll() == null);
 872             check(deq.pollFirst() == null);
 873             check(deq.pollLast() == null);
 874             check(deq.peek() == null);
 875             check(deq.peekFirst() == null);
 876             check(deq.peekLast() == null);
 877             check(!deq.removeFirstOccurrence(e));
 878             check(!deq.removeLastOccurrence(e));
 879 
 880             check(deq.addAll(originalContents) == !isEmpty);
 881             equal(new ArrayList<Integer>(deq), originalContents);
 882             check(!deq.addAll(Collections.<Integer>emptyList()));
 883             equal(new ArrayList<Integer>(deq), originalContents);
 884         }
 885     }
 886 
 887     private static void testQueueIteratorRemove(Queue<Integer> q) {
 888         System.err.printf("testQueueIteratorRemove %s%n",
 889                           q.getClass().getSimpleName());
 890         q.clear();
 891         for (int i = 0; i < 5; i++)
 892             q.add(i);
 893         Iterator<Integer> it = q.iterator();
 894         check(it.hasNext());
 895         for (int i = 3; i >= 0; i--)
 896             q.remove(i);
 897         equal(it.next(), 0);
 898         equal(it.next(), 4);
 899 
 900         q.clear();
 901         for (int i = 0; i < 5; i++)
 902             q.add(i);
 903         it = q.iterator();
 904         equal(it.next(), 0);
 905         check(it.hasNext());
 906         for (int i = 1; i < 4; i++)
 907             q.remove(i);
 908         equal(it.next(), 1);
 909         equal(it.next(), 4);
 910     }
 911 
 912     private static void testList(final List<Integer> l) {
 913         //----------------------------------------------------------------
 914         // 4802633: (coll) AbstractList.addAll(-1,emptyCollection)
 915         // doesn't throw IndexOutOfBoundsException
 916         //----------------------------------------------------------------
 917         try {
 918             l.addAll(-1, Collections.<Integer>emptyList());
 919             fail("Expected IndexOutOfBoundsException not thrown");
 920         }
 921         catch (UnsupportedOperationException ignored) {/* OK */}
 922         catch (IndexOutOfBoundsException ignored) {/* OK */}
 923         catch (Throwable t) { unexpected(t); }
 924 
 925 //      equal(l instanceof Serializable,
 926 //            l.subList(0,0) instanceof Serializable);
 927         if (l.subList(0,0) instanceof Serializable)
 928             check(l instanceof Serializable);
 929 
 930         equal(l instanceof RandomAccess,
 931               l.subList(0,0) instanceof RandomAccess);
 932 
 933         l.iterator();
 934         l.listIterator();
 935         l.listIterator(0);
 936         l.listIterator(l.size());
 937         THROWS(IndexOutOfBoundsException.class,
 938                () -> l.listIterator(-1),
 939                () -> l.listIterator(l.size() + 1));
 940 
 941         if (l instanceof AbstractList) {
 942             try {
 943                 int size = l.size();
 944                 AbstractList<Integer> abList = (AbstractList<Integer>) l;
 945                 Method m = AbstractList.class.getDeclaredMethod("removeRange", new Class[] { int.class, int.class });
 946                 m.setAccessible(true);
 947                 m.invoke(abList, new Object[] { 0, 0 });
 948                 m.invoke(abList, new Object[] { size, size });
 949                 equal(size, l.size());
 950             }
 951             catch (UnsupportedOperationException ignored) {/* OK */}
 952             catch (Throwable t) { unexpected(t); }
 953         }
 954     }
 955 
 956     private static void testCollection(Collection<Integer> c) {
 957         try { testCollection1(c); }
 958         catch (Throwable t) { unexpected(t); }
 959     }
 960 
 961     private static void testCollection1(Collection<Integer> c) {
 962 
 963         System.out.println("\n==> " + c.getClass().getName());
 964 
 965         checkFunctionalInvariants(c);
 966 
 967         if (! supportsAdd(c)) return;
 968         //System.out.println("add() supported");
 969 
 970         if (c instanceof NavigableSet) {
 971             System.out.println("NavigableSet tests...");
 972 
 973             NavigableSet<Integer> ns = (NavigableSet<Integer>)c;
 974             testNavigableSet(ns);
 975             testNavigableSet(ns.headSet(6, false));
 976             testNavigableSet(ns.headSet(5, true));
 977             testNavigableSet(ns.tailSet(0, false));
 978             testNavigableSet(ns.tailSet(1, true));
 979             testNavigableSet(ns.subSet(0, false, 5, true));
 980             testNavigableSet(ns.subSet(1, true, 6, false));
 981         }
 982 
 983         if (c instanceof Queue)
 984             testQueue((Queue<Integer>)c);
 985 
 986         if (c instanceof List)
 987             testList((List<Integer>)c);
 988 
 989         check(supportsRemove(c));
 990 
 991         try {
 992             oneElement(c);
 993             checkFunctionalInvariants(c);
 994         }
 995         catch (Throwable t) { unexpected(t); }
 996 
 997         clear(c);      testNullElement(c);
 998         oneElement(c); testNullElement(c);
 999 
1000         clear(c);      testStringElement(c);
1001         oneElement(c); testStringElement(c);
1002 
1003         if (c.getClass().getName().matches(".*concurrent.*"))
1004             testConcurrentCollection(c);
1005 
1006         //----------------------------------------------------------------
1007         // The "all" operations should throw NPE when passed null
1008         //----------------------------------------------------------------
1009         {
1010             clear(c);
1011             try {
1012                 c.removeAll(null);
1013                 fail("Expected NullPointerException");
1014             }
1015             catch (NullPointerException e) { pass(); }
1016             catch (Throwable t) { unexpected(t); }
1017 
1018             oneElement(c);
1019             try {
1020                 c.removeAll(null);
1021                 fail("Expected NullPointerException");
1022             }
1023             catch (NullPointerException e) { pass(); }
1024             catch (Throwable t) { unexpected(t); }
1025 
1026             clear(c);
1027             try {
1028                 c.retainAll(null);
1029                 fail("Expected NullPointerException");
1030             }
1031             catch (NullPointerException e) { pass(); }
1032             catch (Throwable t) { unexpected(t); }
1033 
1034             oneElement(c);
1035             try {
1036                 c.retainAll(null);
1037                 fail("Expected NullPointerException");
1038             }
1039             catch (NullPointerException e) { pass(); }
1040             catch (Throwable t) { unexpected(t); }
1041 
1042             oneElement(c);
1043             try {
1044                 c.addAll(null);
1045                 fail("Expected NullPointerException");
1046             }
1047             catch (NullPointerException e) { pass(); }
1048             catch (Throwable t) { unexpected(t); }
1049 
1050             oneElement(c);
1051             try {
1052                 c.containsAll(null);
1053                 fail("Expected NullPointerException");
1054             }
1055             catch (NullPointerException e) { pass(); }
1056             catch (Throwable t) { unexpected(t); }
1057         }
1058     }
1059 
1060     //----------------------------------------------------------------
1061     // Map
1062     //----------------------------------------------------------------
1063     private static void checkFunctionalInvariants(Map<Integer,Integer> m) {
1064         check(m.keySet().size() == m.entrySet().size());
1065         check(m.keySet().size() == m.size());
1066         checkFunctionalInvariants(m.keySet());
1067         checkFunctionalInvariants(m.values());
1068         check(m.size() != 0 ^ m.isEmpty());
1069         check(! m.containsKey(ABSENT_VALUE));
1070 
1071         if (m instanceof Serializable) {
1072             //System.out.printf("Serializing %s%n", m.getClass().getName());
1073             try {
1074                 Object clone = serialClone(m);
1075                 equal(m instanceof Serializable,
1076                       clone instanceof Serializable);
1077                 equal(m, clone);
1078             } catch (Error xxx) {
1079                 if (! (xxx.getCause() instanceof NotSerializableException))
1080                     throw xxx;
1081             }
1082         }
1083     }
1084 
1085     private static void testMap(Map<Integer,Integer> m) {
1086         System.out.println("\n==> " + m.getClass().getName());
1087 
1088         if (m instanceof ConcurrentMap)
1089             testConcurrentMap((ConcurrentMap<Integer,Integer>) m);
1090 
1091         if (m instanceof NavigableMap) {
1092             System.out.println("NavigableMap tests...");
1093 
1094             NavigableMap<Integer,Integer> nm =
1095                 (NavigableMap<Integer,Integer>) m;
1096             testNavigableMapRemovers(nm);
1097             testNavigableMap(nm);
1098             testNavigableMap(nm.headMap(6, false));
1099             testNavigableMap(nm.headMap(5, true));
1100             testNavigableMap(nm.tailMap(0, false));
1101             testNavigableMap(nm.tailMap(1, true));
1102             testNavigableMap(nm.subMap(1, true, 6, false));
1103             testNavigableMap(nm.subMap(0, false, 5, true));
1104         }
1105 
1106         checkFunctionalInvariants(m);
1107 
1108         if (supportsClear(m)) {
1109             try { clear(m); }
1110             catch (Throwable t) { unexpected(t); }
1111         }
1112 
1113         if (supportsPut(m)) {
1114             try {
1115                 check(m.put(3333, 77777) == null);
1116                 check(m.put(9134, 74982) == null);
1117                 check(m.get(9134) == 74982);
1118                 check(m.put(9134, 1382) == 74982);
1119                 check(m.get(9134) == 1382);
1120                 check(m.size() == 2);
1121                 checkFunctionalInvariants(m);
1122                 checkNPEConsistency(m);
1123             }
1124             catch (Throwable t) { unexpected(t); }
1125         }
1126     }
1127 
1128     private static boolean supportsPut(Map<Integer,Integer> m) {
1129         // We're asking for .equals(...) semantics
1130         if (m instanceof IdentityHashMap) return false;
1131 
1132         try { check(m.put(ABSENT_VALUE,12735) == null); }
1133         catch (UnsupportedOperationException t) { return false; }
1134         catch (Throwable t) { unexpected(t); }
1135 
1136         try {
1137             check(m.containsKey(ABSENT_VALUE));
1138             check(m.remove(ABSENT_VALUE) != null);
1139         } catch (Throwable t) { unexpected(t); }
1140         return true;
1141     }
1142 
1143     private static boolean supportsClear(Map<?,?> m) {
1144         try { m.clear(); }
1145         catch (UnsupportedOperationException t) { return false; }
1146         catch (Throwable t) { unexpected(t); }
1147         return true;
1148     }
1149 
1150     //----------------------------------------------------------------
1151     // ConcurrentMap
1152     //----------------------------------------------------------------
1153     private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) {
1154         System.out.println("ConcurrentMap tests...");
1155 
1156         try {
1157             clear(m);
1158 
1159             check(m.putIfAbsent(18357,7346) == null);
1160             check(m.containsKey(18357));
1161             check(m.putIfAbsent(18357,8263) == 7346);
1162             try { m.putIfAbsent(18357,null); fail("NPE"); }
1163             catch (NullPointerException t) { }
1164             check(m.containsKey(18357));
1165 
1166             check(! m.replace(18357,8888,7777));
1167             check(m.containsKey(18357));
1168             try { m.replace(18357,null,7777); fail("NPE"); }
1169             catch (NullPointerException t) { }
1170             check(m.containsKey(18357));
1171             check(m.get(18357) == 7346);
1172             check(m.replace(18357,7346,5555));
1173             check(m.replace(18357,5555,7346));
1174             check(m.get(18357) == 7346);
1175 
1176             check(m.replace(92347,7834) == null);
1177             try { m.replace(18357,null); fail("NPE"); }
1178             catch (NullPointerException t) { }
1179             check(m.replace(18357,7346) == 7346);
1180             check(m.replace(18357,5555) == 7346);
1181             check(m.get(18357) == 5555);
1182             check(m.replace(18357,7346) == 5555);
1183             check(m.get(18357) == 7346);
1184 
1185             check(! m.remove(18357,9999));
1186             check(m.get(18357) == 7346);
1187             check(m.containsKey(18357));
1188             check(! m.remove(18357,null)); // 6272521
1189             check(m.get(18357) == 7346);
1190             check(m.remove(18357,7346));
1191             check(m.get(18357) == null);
1192             check(! m.containsKey(18357));
1193             check(m.isEmpty());
1194 
1195             m.putIfAbsent(1,2);
1196             check(m.size() == 1);
1197             check(! m.remove(1,null));
1198             check(! m.remove(1,null));
1199             check(! m.remove(1,1));
1200             check(m.remove(1,2));
1201             check(m.isEmpty());
1202 
1203             testEmptyMap(m);
1204         }
1205         catch (Throwable t) { unexpected(t); }
1206     }
1207 
1208     private static void throwsConsistently(Class<? extends Throwable> k,
1209                                            Iterable<Fun> fs) {
1210         List<Class<? extends Throwable>> threw = new ArrayList<>();
1211         for (Fun f : fs)
1212             try { f.f(); threw.add(null); }
1213             catch (Throwable t) {
1214                 check(k.isAssignableFrom(t.getClass()));
1215                 threw.add(t.getClass());
1216             }
1217         if (new HashSet<Object>(threw).size() != 1)
1218             fail(threw.toString());
1219     }
1220 
1221     private static <T> void checkNPEConsistency(final Map<T,Integer> m) {
1222         m.clear();
1223         final ConcurrentMap<T,Integer> cm = (m instanceof ConcurrentMap)
1224             ? (ConcurrentMap<T,Integer>) m
1225             : null;
1226         List<Fun> fs = new ArrayList<>();
1227         fs.add(() -> check(! m.containsKey(null)));
1228         fs.add(() -> equal(m.remove(null), null));
1229         fs.add(() -> equal(m.get(null), null));
1230         if (cm != null)
1231             fs.add(() -> check(! cm.remove(null,null)));
1232         throwsConsistently(NullPointerException.class, fs);
1233 
1234         fs.clear();
1235         final Map<T,Integer> sm = singletonMap(null,1);
1236         fs.add(() -> { equal(m.put(null,1), null); m.clear();});
1237         fs.add(() -> { m.putAll(sm); m.clear();});
1238         if (cm != null) {
1239             fs.add(() -> check(! cm.remove(null,null)));
1240             fs.add(() -> equal(cm.putIfAbsent(null,1), 1));
1241             fs.add(() -> equal(cm.replace(null,1), null));
1242             fs.add(() -> equal(cm.replace(null,1, 1), 1));
1243         }
1244         throwsConsistently(NullPointerException.class, fs);
1245     }
1246 
1247     //----------------------------------------------------------------
1248     // NavigableMap
1249     //----------------------------------------------------------------
1250     private static void
1251         checkNavigableMapKeys(NavigableMap<Integer,Integer> m,
1252                               Integer i,
1253                               Integer lower,
1254                               Integer floor,
1255                               Integer ceiling,
1256                               Integer higher) {
1257         equal(m.lowerKey(i),   lower);
1258         equal(m.floorKey(i),   floor);
1259         equal(m.ceilingKey(i), ceiling);
1260         equal(m.higherKey(i),  higher);
1261     }
1262 
1263     private static void
1264         checkNavigableSetKeys(NavigableSet<Integer> m,
1265                               Integer i,
1266                               Integer lower,
1267                               Integer floor,
1268                               Integer ceiling,
1269                               Integer higher) {
1270         equal(m.lower(i),   lower);
1271         equal(m.floor(i),   floor);
1272         equal(m.ceiling(i), ceiling);
1273         equal(m.higher(i),  higher);
1274     }
1275 
1276     static final Random rnd = new Random();
1277     static void equalNext(final Iterator<?> it, Object expected) {
1278         if (rnd.nextBoolean())
1279             check(it.hasNext());
1280         equal(it.next(), expected);
1281     }
1282 
1283     static void equalMaps(Map m1, Map m2) {
1284         equal(m1, m2);
1285         equal(m2, m1);
1286         equal(m1.size(), m2.size());
1287         equal(m1.isEmpty(), m2.isEmpty());
1288         equal(m1.toString(), m2.toString());
1289         check(Arrays.equals(m1.entrySet().toArray(), m2.entrySet().toArray()));
1290     }
1291 
1292     @SuppressWarnings({"unchecked", "rawtypes"})
1293     static void testNavigableMapRemovers(NavigableMap m)
1294     {
1295         final Map emptyMap = new HashMap();
1296 
1297         final Map singletonMap = new HashMap();
1298         singletonMap.put(1, 2);
1299 
1300         abstract class NavigableMapView {
1301             abstract NavigableMap view(NavigableMap m);
1302         }
1303 
1304         NavigableMapView[] views = {
1305             new NavigableMapView() { NavigableMap view(NavigableMap m) {
1306                 return m; }},
1307             new NavigableMapView() { NavigableMap view(NavigableMap m) {
1308                 return m.headMap(99, true); }},
1309             new NavigableMapView() { NavigableMap view(NavigableMap m) {
1310                 return m.tailMap(-99, false); }},
1311             new NavigableMapView() { NavigableMap view(NavigableMap m) {
1312                 return m.subMap(-99, true, 99, false); }},
1313         };
1314 
1315         abstract class Remover {
1316             abstract void remove(NavigableMap m, Object k, Object v);
1317         }
1318 
1319         Remover[] removers = {
1320             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1321                 equal(m.remove(k), v); }},
1322 
1323             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1324                 equal(m.descendingMap().remove(k), v); }},
1325             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1326                 equal(m.descendingMap().headMap(-86, false).remove(k), v); }},
1327             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1328                 equal(m.descendingMap().tailMap(86, true).remove(k), v); }},
1329 
1330             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1331                 equal(m.headMap(86, true).remove(k), v); }},
1332             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1333                 equal(m.tailMap(-86, true).remove(k), v); }},
1334             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1335                 equal(m.subMap(-86, false, 86, true).remove(k), v); }},
1336 
1337             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1338                 check(m.keySet().remove(k)); }},
1339             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1340                 check(m.navigableKeySet().remove(k)); }},
1341 
1342             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1343                 check(m.navigableKeySet().headSet(86, true).remove(k)); }},
1344             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1345                 check(m.navigableKeySet().tailSet(-86, false).remove(k)); }},
1346             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1347                 check(m.navigableKeySet().subSet(-86, true, 86, false)
1348                       .remove(k)); }},
1349 
1350             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1351                 check(m.descendingKeySet().headSet(-86, false).remove(k)); }},
1352             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1353                 check(m.descendingKeySet().tailSet(86, true).remove(k)); }},
1354             new Remover() { void remove(NavigableMap m, Object k, Object v) {
1355                 check(m.descendingKeySet().subSet(86, true, -86, false)
1356                       .remove(k)); }},
1357         };
1358 
1359         for (NavigableMapView view : views) {
1360             for (Remover remover : removers) {
1361                 try {
1362                     m.clear();
1363                     equalMaps(m, emptyMap);
1364                     equal(m.put(1, 2), null);
1365                     equalMaps(m, singletonMap);
1366                     NavigableMap v = view.view(m);
1367                     remover.remove(v, 1, 2);
1368                     equalMaps(m, emptyMap);
1369                 } catch (Throwable t) { unexpected(t); }
1370             }
1371         }
1372     }
1373 
1374     private static void testNavigableMap(NavigableMap<Integer,Integer> m)
1375     {
1376         clear(m);
1377         checkNavigableMapKeys(m, 1, null, null, null, null);
1378 
1379         equal(m.put(1, 2), null);
1380         equal(m.put(3, 4), null);
1381         equal(m.put(5, 9), null);
1382 
1383         equal(m.put(1, 2), 2);
1384         equal(m.put(3, 4), 4);
1385         equal(m.put(5, 6), 9);
1386 
1387         checkNavigableMapKeys(m, 0, null, null,    1,    1);
1388         checkNavigableMapKeys(m, 1, null,    1,    1,    3);
1389         checkNavigableMapKeys(m, 2,    1,    1,    3,    3);
1390         checkNavigableMapKeys(m, 3,    1,    3,    3,    5);
1391         checkNavigableMapKeys(m, 5,    3,    5,    5, null);
1392         checkNavigableMapKeys(m, 6,    5,    5, null, null);
1393 
1394         for (final Iterator<Integer> it :
1395                  (Iterator<Integer>[])
1396                  new Iterator<?>[] {
1397                      m.descendingKeySet().iterator(),
1398                      m.navigableKeySet().descendingIterator()}) {
1399             equalNext(it, 5);
1400             equalNext(it, 3);
1401             equalNext(it, 1);
1402             check(! it.hasNext());
1403             THROWS(NoSuchElementException.class, () -> it.next());
1404         }
1405 
1406         {
1407             final Iterator<Map.Entry<Integer,Integer>> it
1408                 = m.descendingMap().entrySet().iterator();
1409             check(it.hasNext()); equal(it.next().getKey(), 5);
1410             check(it.hasNext()); equal(it.next().getKey(), 3);
1411             check(it.hasNext()); equal(it.next().getKey(), 1);
1412             check(! it.hasNext());
1413             THROWS(NoSuchElementException.class, () -> it.next());
1414         }
1415 
1416         prepMapForDescItrTests(m);
1417         checkDescItrRmFirst(m.keySet(), m.navigableKeySet().descendingIterator());
1418         prepMapForDescItrTests(m);
1419         checkDescItrRmMid(m.keySet(), m.navigableKeySet().descendingIterator());
1420         prepMapForDescItrTests(m);
1421         checkDescItrRmLast(m.keySet(), m.navigableKeySet().descendingIterator());
1422 
1423         prepMapForDescItrTests(m);
1424         checkDescItrRmFirst(m.keySet(), m.descendingMap().keySet().iterator());
1425         prepMapForDescItrTests(m);
1426         checkDescItrRmMid(m.keySet(), m.descendingMap().keySet().iterator());
1427         prepMapForDescItrTests(m);
1428         checkDescItrRmLast(m.keySet(), m.descendingMap().keySet().iterator());
1429 
1430         prepMapForDescItrTests(m);
1431         checkDescItrRmFirst(m.keySet(), m.descendingKeySet().iterator());
1432         prepMapForDescItrTests(m);
1433         checkDescItrRmMid(m.keySet(), m.descendingKeySet().iterator());
1434         prepMapForDescItrTests(m);
1435         checkDescItrRmLast(m.keySet(), m.descendingKeySet().iterator());
1436 
1437         prepMapForDescItrTests(m);
1438         checkDescItrRmFirst(m.values(), m.descendingMap().values().iterator());
1439         prepMapForDescItrTests(m);
1440         checkDescItrRmMid(m.values(), m.descendingMap().values().iterator());
1441         prepMapForDescItrTests(m);
1442         checkDescItrRmLast(m.values(), m.descendingMap().values().iterator());
1443 
1444         prepMapForDescItrTests(m);
1445         checkDescItrRmFirst((Collection)m.entrySet(),
1446                             m.descendingMap().entrySet().iterator());
1447         prepMapForDescItrTests(m);
1448         checkDescItrRmMid((Collection)m.entrySet(),
1449                           m.descendingMap().entrySet().iterator());
1450         prepMapForDescItrTests(m);
1451         checkDescItrRmLast((Collection)m.entrySet(),
1452                            m.descendingMap().entrySet().iterator());
1453     }
1454 
1455     private static void testNavigableSet(NavigableSet<Integer> s) {
1456         clear(s);
1457         checkNavigableSetKeys(s, 1, null, null, null, null);
1458 
1459         check(s.add(1));
1460         check(s.add(3));
1461         check(s.add(5));
1462 
1463         check(! s.add(1));
1464         check(! s.add(3));
1465         check(! s.add(5));
1466 
1467         checkNavigableSetKeys(s, 0, null, null,    1,    1);
1468         checkNavigableSetKeys(s, 1, null,    1,    1,    3);
1469         checkNavigableSetKeys(s, 2,    1,    1,    3,    3);
1470         checkNavigableSetKeys(s, 3,    1,    3,    3,    5);
1471         checkNavigableSetKeys(s, 5,    3,    5,    5, null);
1472         checkNavigableSetKeys(s, 6,    5,    5, null, null);
1473 
1474         for (final Iterator<Integer> it :
1475                  (Iterator<Integer>[])
1476                  new Iterator<?>[] {
1477                      s.descendingIterator(),
1478                      s.descendingSet().iterator()}) {
1479             equalNext(it, 5);
1480             equalNext(it, 3);
1481             equalNext(it, 1);
1482             check(! it.hasNext());
1483             THROWS(NoSuchElementException.class, () -> it.next());
1484         }
1485 
1486         prepSetForDescItrTests(s);
1487         checkDescItrRmFirst(s, s.descendingIterator());
1488         prepSetForDescItrTests(s);
1489         checkDescItrRmMid(s, s.descendingIterator());
1490         prepSetForDescItrTests(s);
1491         checkDescItrRmLast(s, s.descendingIterator());
1492 
1493         prepSetForDescItrTests(s);
1494         checkDescItrRmFirst(s, s.descendingSet().iterator());
1495         prepSetForDescItrTests(s);
1496         checkDescItrRmMid(s, s.descendingSet().iterator());
1497         prepSetForDescItrTests(s);
1498         checkDescItrRmLast(s, s.descendingSet().iterator());
1499     }
1500 
1501     private static void prepSetForDescItrTests(Set s) {
1502         clear(s);
1503         check(s.add(1));
1504         check(s.add(3));
1505         check(s.add(5));
1506     }
1507 
1508     private static void prepMapForDescItrTests(Map m) {
1509         clear(m);
1510         equal(m.put(1, 2), null);
1511         equal(m.put(3, 4), null);
1512         equal(m.put(5, 9), null);
1513     }
1514 
1515     //--------------------------------------------------------------------
1516     // Check behavior of descending iterator when first element is removed
1517     //--------------------------------------------------------------------
1518     private static <T> void checkDescItrRmFirst(Collection<T> ascColl,
1519                                                 Iterator<T> descItr) {
1520         T[] expected = (T[]) ascColl.toArray();
1521         int idx = expected.length -1;
1522 
1523         equalNext(descItr, expected[idx--]);
1524         descItr.remove();
1525         while (idx >= 0 && descItr.hasNext()) {
1526             equalNext(descItr, expected[idx--]);
1527         }
1528         equal(descItr.hasNext(), false);
1529         equal(idx, -1);
1530     }
1531 
1532     //-----------------------------------------------------------------------
1533     // Check behavior of descending iterator when a middle element is removed
1534     //-----------------------------------------------------------------------
1535     private static <T> void checkDescItrRmMid(Collection<T> ascColl,
1536                                               Iterator<T> descItr) {
1537         T[] expected = (T[]) ascColl.toArray();
1538         int idx = expected.length -1;
1539 
1540         while (idx >= expected.length / 2) {
1541             equalNext(descItr, expected[idx--]);
1542         }
1543         descItr.remove();
1544         while (idx >= 0 && descItr.hasNext()) {
1545             equalNext(descItr, expected[idx--]);
1546         }
1547         equal(descItr.hasNext(), false);
1548         equal(idx, -1);
1549     }
1550 
1551     //-----------------------------------------------------------------------
1552     // Check behavior of descending iterator when the last element is removed
1553     //-----------------------------------------------------------------------
1554     private static <T> void checkDescItrRmLast(Collection<T> ascColl,
1555                                                Iterator<T> descItr) {
1556         T[] expected = (T[]) ascColl.toArray();
1557         int idx = expected.length -1;
1558 
1559         while (idx >= 0 && descItr.hasNext()) {
1560             equalNext(descItr, expected[idx--]);
1561         }
1562         equal(idx, -1);
1563         equal(descItr.hasNext(), false);
1564         descItr.remove();
1565         equal(ascColl.contains(expected[0]), false);
1566     }
1567 
1568     //--------------------- Infrastructure ---------------------------
1569     static volatile int passed = 0, failed = 0;
1570     static void pass() { passed++; }
1571     static void fail() { failed++; Thread.dumpStack(); }
1572     static void fail(String msg) { System.out.println(msg); fail(); }
1573     static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
1574     static void check(boolean cond) { if (cond) pass(); else fail(); }
1575     static void equal(Object x, Object y) {
1576         if (x == null ? y == null : x.equals(y)) pass();
1577         else {System.out.println(x + " not equal to " + y); fail();}}
1578     static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
1579     public static void main(String[] args) throws Throwable {
1580         try { realMain(args); } catch (Throwable t) { unexpected(t); }
1581 
1582         System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
1583         if (failed > 0) throw new Exception("Some tests failed");
1584     }
1585     interface Fun {void f() throws Throwable;}
1586     private static void THROWS(Class<? extends Throwable> k, Fun... fs) {
1587           for (Fun f : fs)
1588               try { f.f(); fail("Expected " + k.getName() + " not thrown"); }
1589               catch (Throwable t) {
1590                   if (k.isAssignableFrom(t.getClass())) pass();
1591                   else unexpected(t);}}
1592     static byte[] serializedForm(Object obj) {
1593         try {
1594             ByteArrayOutputStream baos = new ByteArrayOutputStream();
1595             new ObjectOutputStream(baos).writeObject(obj);
1596             return baos.toByteArray();
1597         } catch (IOException e) { throw new Error(e); }}
1598     static Object readObject(byte[] bytes)
1599         throws IOException, ClassNotFoundException {
1600         InputStream is = new ByteArrayInputStream(bytes);
1601         return new ObjectInputStream(is).readObject();}
1602     @SuppressWarnings("unchecked")
1603     static <T> T serialClone(T obj) {
1604         try { return (T) readObject(serializedForm(obj)); }
1605         catch (Exception e) { throw new Error(e); }}
1606     private static class NewAbstractCollection<E> extends AbstractCollection<E> {
1607         ArrayList<E> list = new ArrayList<>();
1608         public boolean remove(Object obj) {
1609             return list.remove(obj);
1610         }
1611         public boolean add(E e) {
1612             return list.add(e);
1613         }
1614         public Iterator<E> iterator() {
1615             return list.iterator();
1616         }
1617         public int size() {
1618             return list.size();
1619         }
1620     }
1621     private static class NewAbstractSet<E> extends AbstractSet<E> {
1622         HashSet<E> set = new HashSet<>();
1623         public boolean remove(Object obj) {
1624             return set.remove(obj);
1625         }
1626         public boolean add(E e) {
1627             return set.add(e);
1628         }
1629         public Iterator<E> iterator() {
1630             return set.iterator();
1631         }
1632         public int size() {
1633             return set.size();
1634         }
1635     }
1636 
1637 }