1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.
   7  *
   8  * This code is distributed in the hope that it will be useful, but WITHOUT
   9  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  10  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  11  * version 2 for more details (a copy is included in the LICENSE file that
  12  * accompanied this code).
  13  *
  14  * You should have received a copy of the GNU General Public License version
  15  * 2 along with this work; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  17  *
  18  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  19  * or visit www.oracle.com if you need additional information or have any
  20  * questions.
  21  */
  22 
  23 /*
  24  * This file is available under and governed by the GNU General Public
  25  * License version 2 only, as published by the Free Software Foundation.
  26  * However, the following notice accompanied the original version of this
  27  * file:
  28  *
  29  * Written by Doug Lea and Martin Buchholz with assistance from
  30  * members of JCP JSR-166 Expert Group and released to the public
  31  * domain, as explained at
  32  * http://creativecommons.org/publicdomain/zero/1.0/
  33  */
  34 
  35 import static java.util.concurrent.TimeUnit.HOURS;
  36 import static java.util.concurrent.TimeUnit.MILLISECONDS;
  37 
  38 import java.util.ArrayDeque;
  39 import java.util.ArrayList;
  40 import java.util.Arrays;
  41 import java.util.Collection;
  42 import java.util.Collections;
  43 import java.util.ConcurrentModificationException;
  44 import java.util.Deque;
  45 import java.util.HashSet;
  46 import java.util.Iterator;
  47 import java.util.List;
  48 import java.util.NoSuchElementException;
  49 import java.util.Queue;
  50 import java.util.Set;
  51 import java.util.Spliterator;
  52 import java.util.concurrent.BlockingDeque;
  53 import java.util.concurrent.BlockingQueue;
  54 import java.util.concurrent.ConcurrentLinkedQueue;
  55 import java.util.concurrent.CountDownLatch;
  56 import java.util.concurrent.Executors;
  57 import java.util.concurrent.ExecutorService;
  58 import java.util.concurrent.Future;
  59 import java.util.concurrent.Phaser;
  60 import java.util.concurrent.ThreadLocalRandom;
  61 import java.util.concurrent.atomic.AtomicBoolean;
  62 import java.util.concurrent.atomic.AtomicLong;
  63 import java.util.concurrent.atomic.AtomicReference;
  64 import java.util.function.Consumer;
  65 import java.util.function.Predicate;
  66 import java.util.stream.Collectors;
  67 
  68 import junit.framework.Test;
  69 
  70 /**
  71  * Contains tests applicable to all jdk8+ Collection implementations.
  72  * An extension of CollectionTest.
  73  */
  74 public class Collection8Test extends JSR166TestCase {
  75     final CollectionImplementation impl;
  76 
  77     /** Tests are parameterized by a Collection implementation. */
  78     Collection8Test(CollectionImplementation impl, String methodName) {
  79         super(methodName);
  80         this.impl = impl;
  81     }
  82 
  83     public static Test testSuite(CollectionImplementation impl) {
  84         return parameterizedTestSuite(Collection8Test.class,
  85                                       CollectionImplementation.class,
  86                                       impl);
  87     }
  88 
  89     Object bomb() {
  90         return new Object() {
  91             @Override public boolean equals(Object x) { throw new AssertionError(); }
  92             @Override public int hashCode() { throw new AssertionError(); }
  93             @Override public String toString() { throw new AssertionError(); }
  94         };
  95     }
  96 
  97     /** Checks properties of empty collections. */
  98     public void testEmptyMeansEmpty() throws Throwable {
  99         Collection c = impl.emptyCollection();
 100         emptyMeansEmpty(c);
 101 
 102         if (c instanceof java.io.Serializable) {
 103             try {
 104                 emptyMeansEmpty(serialClonePossiblyFailing(c));
 105             } catch (java.io.NotSerializableException ex) {
 106                 // excusable when we have a serializable wrapper around
 107                 // a non-serializable collection, as can happen with:
 108                 // Vector.subList() => wrapped AbstractList$RandomAccessSubList
 109                 if (testImplementationDetails
 110                     && (! c.getClass().getName().matches(
 111                                 "java.util.Collections.*")))
 112                     throw ex;
 113             }
 114         }
 115 
 116         Collection clone = cloneableClone(c);
 117         if (clone != null)
 118             emptyMeansEmpty(clone);
 119     }
 120 
 121     void emptyMeansEmpty(Collection c) throws InterruptedException {
 122         assertTrue(c.isEmpty());
 123         assertEquals(0, c.size());
 124         assertEquals("[]", c.toString());
 125         if (c instanceof List<?>) {
 126             List x = (List) c;
 127             assertEquals(1, x.hashCode());
 128             assertEquals(x, Collections.emptyList());
 129             assertEquals(Collections.emptyList(), x);
 130             assertEquals(-1, x.indexOf(impl.makeElement(86)));
 131             assertEquals(-1, x.lastIndexOf(impl.makeElement(99)));
 132             assertThrows(
 133                 IndexOutOfBoundsException.class,
 134                 () -> x.get(0),
 135                 () -> x.set(0, impl.makeElement(42)));
 136         }
 137         else if (c instanceof Set<?>) {
 138             assertEquals(0, c.hashCode());
 139             assertEquals(c, Collections.emptySet());
 140             assertEquals(Collections.emptySet(), c);
 141         }
 142         {
 143             Object[] a = c.toArray();
 144             assertEquals(0, a.length);
 145             assertSame(Object[].class, a.getClass());
 146         }
 147         {
 148             Object[] a = new Object[0];
 149             assertSame(a, c.toArray(a));
 150         }
 151         {
 152             Integer[] a = new Integer[0];
 153             assertSame(a, c.toArray(a));
 154         }
 155         {
 156             Integer[] a = { 1, 2, 3};
 157             assertSame(a, c.toArray(a));
 158             assertNull(a[0]);
 159             assertSame(2, a[1]);
 160             assertSame(3, a[2]);
 161         }
 162         assertIteratorExhausted(c.iterator());
 163         Consumer alwaysThrows = e -> { throw new AssertionError(); };
 164         c.forEach(alwaysThrows);
 165         c.iterator().forEachRemaining(alwaysThrows);
 166         c.spliterator().forEachRemaining(alwaysThrows);
 167         assertFalse(c.spliterator().tryAdvance(alwaysThrows));
 168         if (c.spliterator().hasCharacteristics(Spliterator.SIZED))
 169             assertEquals(0, c.spliterator().estimateSize());
 170         assertFalse(c.contains(bomb()));
 171         assertFalse(c.remove(bomb()));
 172         if (c instanceof Queue) {
 173             Queue q = (Queue) c;
 174             assertNull(q.peek());
 175             assertNull(q.poll());
 176         }
 177         if (c instanceof Deque) {
 178             Deque d = (Deque) c;
 179             assertNull(d.peekFirst());
 180             assertNull(d.peekLast());
 181             assertNull(d.pollFirst());
 182             assertNull(d.pollLast());
 183             assertIteratorExhausted(d.descendingIterator());
 184             d.descendingIterator().forEachRemaining(alwaysThrows);
 185             assertFalse(d.removeFirstOccurrence(bomb()));
 186             assertFalse(d.removeLastOccurrence(bomb()));
 187         }
 188         if (c instanceof BlockingQueue) {
 189             BlockingQueue q = (BlockingQueue) c;
 190             assertNull(q.poll(randomExpiredTimeout(), randomTimeUnit()));
 191         }
 192         if (c instanceof BlockingDeque) {
 193             BlockingDeque q = (BlockingDeque) c;
 194             assertNull(q.pollFirst(randomExpiredTimeout(), randomTimeUnit()));
 195             assertNull(q.pollLast(randomExpiredTimeout(), randomTimeUnit()));
 196         }
 197     }
 198 
 199     public void testNullPointerExceptions() throws InterruptedException {
 200         Collection c = impl.emptyCollection();
 201         assertThrows(
 202             NullPointerException.class,
 203             () -> c.addAll(null),
 204             () -> c.containsAll(null),
 205             () -> c.retainAll(null),
 206             () -> c.removeAll(null),
 207             () -> c.removeIf(null),
 208             () -> c.forEach(null),
 209             () -> c.iterator().forEachRemaining(null),
 210             () -> c.spliterator().forEachRemaining(null),
 211             () -> c.spliterator().tryAdvance(null),
 212             () -> c.toArray(null));
 213 
 214         if (!impl.permitsNulls()) {
 215             assertThrows(
 216                 NullPointerException.class,
 217                 () -> c.add(null));
 218         }
 219         if (!impl.permitsNulls() && c instanceof Queue) {
 220             Queue q = (Queue) c;
 221             assertThrows(
 222                 NullPointerException.class,
 223                 () -> q.offer(null));
 224         }
 225         if (!impl.permitsNulls() && c instanceof Deque) {
 226             Deque d = (Deque) c;
 227             assertThrows(
 228                 NullPointerException.class,
 229                 () -> d.addFirst(null),
 230                 () -> d.addLast(null),
 231                 () -> d.offerFirst(null),
 232                 () -> d.offerLast(null),
 233                 () -> d.push(null),
 234                 () -> d.descendingIterator().forEachRemaining(null));
 235         }
 236         if (c instanceof BlockingQueue) {
 237             BlockingQueue q = (BlockingQueue) c;
 238             assertThrows(
 239                 NullPointerException.class,
 240                 () -> {
 241                     try { q.offer(null, 1L, HOURS); }
 242                     catch (InterruptedException ex) {
 243                         throw new AssertionError(ex);
 244                     }},
 245                 () -> {
 246                     try { q.put(null); }
 247                     catch (InterruptedException ex) {
 248                         throw new AssertionError(ex);
 249                     }});
 250         }
 251         if (c instanceof BlockingDeque) {
 252             BlockingDeque q = (BlockingDeque) c;
 253             assertThrows(
 254                 NullPointerException.class,
 255                 () -> {
 256                     try { q.offerFirst(null, 1L, HOURS); }
 257                     catch (InterruptedException ex) {
 258                         throw new AssertionError(ex);
 259                     }},
 260                 () -> {
 261                     try { q.offerLast(null, 1L, HOURS); }
 262                     catch (InterruptedException ex) {
 263                         throw new AssertionError(ex);
 264                     }},
 265                 () -> {
 266                     try { q.putFirst(null); }
 267                     catch (InterruptedException ex) {
 268                         throw new AssertionError(ex);
 269                     }},
 270                 () -> {
 271                     try { q.putLast(null); }
 272                     catch (InterruptedException ex) {
 273                         throw new AssertionError(ex);
 274                     }});
 275         }
 276     }
 277 
 278     public void testNoSuchElementExceptions() {
 279         Collection c = impl.emptyCollection();
 280         assertThrows(
 281             NoSuchElementException.class,
 282             () -> c.iterator().next());
 283 
 284         if (c instanceof Queue) {
 285             Queue q = (Queue) c;
 286             assertThrows(
 287                 NoSuchElementException.class,
 288                 () -> q.element(),
 289                 () -> q.remove());
 290         }
 291         if (c instanceof Deque) {
 292             Deque d = (Deque) c;
 293             assertThrows(
 294                 NoSuchElementException.class,
 295                 () -> d.getFirst(),
 296                 () -> d.getLast(),
 297                 () -> d.removeFirst(),
 298                 () -> d.removeLast(),
 299                 () -> d.pop(),
 300                 () -> d.descendingIterator().next());
 301         }
 302         if (c instanceof List) {
 303             List x = (List) c;
 304             assertThrows(
 305                 NoSuchElementException.class,
 306                 () -> x.iterator().next(),
 307                 () -> x.listIterator().next(),
 308                 () -> x.listIterator(0).next(),
 309                 () -> x.listIterator().previous(),
 310                 () -> x.listIterator(0).previous());
 311         }
 312     }
 313 
 314     public void testRemoveIf() {
 315         Collection c = impl.emptyCollection();
 316         boolean ordered =
 317             c.spliterator().hasCharacteristics(Spliterator.ORDERED);
 318         ThreadLocalRandom rnd = ThreadLocalRandom.current();
 319         int n = rnd.nextInt(6);
 320         for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
 321         AtomicReference threwAt = new AtomicReference(null);
 322         List orig = rnd.nextBoolean()
 323             ? new ArrayList(c)
 324             : Arrays.asList(c.toArray());
 325 
 326         // Merely creating an iterator can change ArrayBlockingQueue behavior
 327         Iterator it = rnd.nextBoolean() ? c.iterator() : null;
 328 
 329         ArrayList survivors = new ArrayList();
 330         ArrayList accepts = new ArrayList();
 331         ArrayList rejects = new ArrayList();
 332 
 333         Predicate randomPredicate = e -> {
 334             assertNull(threwAt.get());
 335             switch (rnd.nextInt(3)) {
 336             case 0: accepts.add(e); return true;
 337             case 1: rejects.add(e); return false;
 338             case 2: threwAt.set(e); throw new ArithmeticException();
 339             default: throw new AssertionError();
 340             }
 341         };
 342         try {
 343             try {
 344                 boolean modified = c.removeIf(randomPredicate);
 345                 assertNull(threwAt.get());
 346                 assertEquals(modified, accepts.size() > 0);
 347                 assertEquals(modified, rejects.size() != n);
 348                 assertEquals(accepts.size() + rejects.size(), n);
 349                 if (ordered) {
 350                     assertEquals(rejects,
 351                                  Arrays.asList(c.toArray()));
 352                 } else {
 353                     assertEquals(new HashSet(rejects),
 354                                  new HashSet(Arrays.asList(c.toArray())));
 355                 }
 356             } catch (ArithmeticException ok) {
 357                 assertNotNull(threwAt.get());
 358                 assertTrue(c.contains(threwAt.get()));
 359             }
 360             if (it != null && impl.isConcurrent())
 361                 // check for weakly consistent iterator
 362                 while (it.hasNext()) assertTrue(orig.contains(it.next()));
 363             switch (rnd.nextInt(4)) {
 364             case 0: survivors.addAll(c); break;
 365             case 1: survivors.addAll(Arrays.asList(c.toArray())); break;
 366             case 2: c.forEach(survivors::add); break;
 367             case 3: for (Object e : c) survivors.add(e); break;
 368             }
 369             assertTrue(orig.containsAll(accepts));
 370             assertTrue(orig.containsAll(rejects));
 371             assertTrue(orig.containsAll(survivors));
 372             assertTrue(orig.containsAll(c));
 373             assertTrue(c.containsAll(rejects));
 374             assertTrue(c.containsAll(survivors));
 375             assertTrue(survivors.containsAll(rejects));
 376             if (threwAt.get() == null) {
 377                 assertEquals(n - accepts.size(), c.size());
 378                 for (Object x : accepts) assertFalse(c.contains(x));
 379             } else {
 380                 // Two acceptable behaviors: entire removeIf call is one
 381                 // transaction, or each element processed is one transaction.
 382                 assertTrue(n == c.size() || n == c.size() + accepts.size());
 383                 int k = 0;
 384                 for (Object x : accepts) if (c.contains(x)) k++;
 385                 assertTrue(k == accepts.size() || k == 0);
 386             }
 387         } catch (Throwable ex) {
 388             System.err.println(impl.klazz());
 389             // c is at risk of corruption if we got here, so be lenient
 390             try { System.err.printf("c=%s%n", c); }
 391             catch (Throwable t) { t.printStackTrace(); }
 392             System.err.printf("n=%d%n", n);
 393             System.err.printf("orig=%s%n", orig);
 394             System.err.printf("accepts=%s%n", accepts);
 395             System.err.printf("rejects=%s%n", rejects);
 396             System.err.printf("survivors=%s%n", survivors);
 397             System.err.printf("threwAt=%s%n", threwAt.get());
 398             throw ex;
 399         }
 400     }
 401 
 402     /**
 403      * All elements removed in the middle of CONCURRENT traversal.
 404      */
 405     public void testElementRemovalDuringTraversal() {
 406         Collection c = impl.emptyCollection();
 407         ThreadLocalRandom rnd = ThreadLocalRandom.current();
 408         int n = rnd.nextInt(6);
 409         ArrayList copy = new ArrayList();
 410         for (int i = 0; i < n; i++) {
 411             Object x = impl.makeElement(i);
 412             copy.add(x);
 413             c.add(x);
 414         }
 415         ArrayList iterated = new ArrayList();
 416         ArrayList spliterated = new ArrayList();
 417         Spliterator s = c.spliterator();
 418         Iterator it = c.iterator();
 419         for (int i = rnd.nextInt(n + 1); --i >= 0; ) {
 420             assertTrue(s.tryAdvance(spliterated::add));
 421             if (rnd.nextBoolean()) assertTrue(it.hasNext());
 422             iterated.add(it.next());
 423         }
 424         Consumer alwaysThrows = e -> { throw new AssertionError(); };
 425         if (s.hasCharacteristics(Spliterator.CONCURRENT)) {
 426             c.clear();          // TODO: many more removal methods
 427             if (testImplementationDetails
 428                 && !(c instanceof java.util.concurrent.ArrayBlockingQueue)) {
 429                 if (rnd.nextBoolean())
 430                     assertFalse(s.tryAdvance(alwaysThrows));
 431                 else
 432                     s.forEachRemaining(alwaysThrows);
 433             }
 434             if (it.hasNext()) iterated.add(it.next());
 435             if (rnd.nextBoolean()) assertIteratorExhausted(it);
 436         }
 437         assertTrue(copy.containsAll(iterated));
 438         assertTrue(copy.containsAll(spliterated));
 439     }
 440 
 441     /**
 442      * Some elements randomly disappear in the middle of traversal.
 443      */
 444     public void testRandomElementRemovalDuringTraversal() {
 445         Collection c = impl.emptyCollection();
 446         ThreadLocalRandom rnd = ThreadLocalRandom.current();
 447         int n = rnd.nextInt(6);
 448         ArrayList copy = new ArrayList();
 449         for (int i = 0; i < n; i++) {
 450             Object x = impl.makeElement(i);
 451             copy.add(x);
 452             c.add(x);
 453         }
 454         ArrayList iterated = new ArrayList();
 455         ArrayList spliterated = new ArrayList();
 456         ArrayList removed = new ArrayList();
 457         Spliterator s = c.spliterator();
 458         Iterator it = c.iterator();
 459         if (! (s.hasCharacteristics(Spliterator.CONCURRENT) ||
 460                s.hasCharacteristics(Spliterator.IMMUTABLE)))
 461             return;
 462         for (int i = rnd.nextInt(n + 1); --i >= 0; ) {
 463             assertTrue(s.tryAdvance(e -> {}));
 464             if (rnd.nextBoolean()) assertTrue(it.hasNext());
 465             it.next();
 466         }
 467         Consumer alwaysThrows = e -> { throw new AssertionError(); };
 468         // TODO: many more removal methods
 469         if (rnd.nextBoolean()) {
 470             for (Iterator z = c.iterator(); z.hasNext(); ) {
 471                 Object e = z.next();
 472                 if (rnd.nextBoolean()) {
 473                     try {
 474                         z.remove();
 475                     } catch (UnsupportedOperationException ok) { return; }
 476                     removed.add(e);
 477                 }
 478             }
 479         } else {
 480             Predicate randomlyRemove = e -> {
 481                 if (rnd.nextBoolean()) { removed.add(e); return true; }
 482                 else return false;
 483             };
 484             c.removeIf(randomlyRemove);
 485         }
 486         s.forEachRemaining(spliterated::add);
 487         while (it.hasNext())
 488             iterated.add(it.next());
 489         assertTrue(copy.containsAll(iterated));
 490         assertTrue(copy.containsAll(spliterated));
 491         assertTrue(copy.containsAll(removed));
 492         if (s.hasCharacteristics(Spliterator.CONCURRENT)) {
 493             ArrayList iteratedAndRemoved = new ArrayList(iterated);
 494             ArrayList spliteratedAndRemoved = new ArrayList(spliterated);
 495             iteratedAndRemoved.retainAll(removed);
 496             spliteratedAndRemoved.retainAll(removed);
 497             assertTrue(iteratedAndRemoved.size() <= 1);
 498             assertTrue(spliteratedAndRemoved.size() <= 1);
 499             if (testImplementationDetails
 500                 && !(c instanceof java.util.concurrent.ArrayBlockingQueue))
 501                 assertTrue(spliteratedAndRemoved.isEmpty());
 502         }
 503     }
 504 
 505     /**
 506      * Various ways of traversing a collection yield same elements
 507      */
 508     public void testTraversalEquivalence() {
 509         Collection c = impl.emptyCollection();
 510         ThreadLocalRandom rnd = ThreadLocalRandom.current();
 511         int n = rnd.nextInt(6);
 512         for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
 513         ArrayList iterated = new ArrayList();
 514         ArrayList iteratedForEachRemaining = new ArrayList();
 515         ArrayList tryAdvanced = new ArrayList();
 516         ArrayList spliterated = new ArrayList();
 517         ArrayList splitonced = new ArrayList();
 518         ArrayList forEached = new ArrayList();
 519         ArrayList streamForEached = new ArrayList();
 520         ConcurrentLinkedQueue parallelStreamForEached = new ConcurrentLinkedQueue();
 521         ArrayList removeIfed = new ArrayList();
 522         for (Object x : c) iterated.add(x);
 523         c.iterator().forEachRemaining(iteratedForEachRemaining::add);
 524         for (Spliterator s = c.spliterator();
 525              s.tryAdvance(tryAdvanced::add); ) {}
 526         c.spliterator().forEachRemaining(spliterated::add);
 527         {                       // trySplit returns "strict prefix"
 528             Spliterator s1 = c.spliterator(), s2 = s1.trySplit();
 529             if (s2 != null) s2.forEachRemaining(splitonced::add);
 530             s1.forEachRemaining(splitonced::add);
 531         }
 532         c.forEach(forEached::add);
 533         c.stream().forEach(streamForEached::add);
 534         c.parallelStream().forEach(parallelStreamForEached::add);
 535         c.removeIf(e -> { removeIfed.add(e); return false; });
 536         boolean ordered =
 537             c.spliterator().hasCharacteristics(Spliterator.ORDERED);
 538         if (c instanceof List || c instanceof Deque)
 539             assertTrue(ordered);
 540         HashSet cset = new HashSet(c);
 541         assertEquals(cset, new HashSet(parallelStreamForEached));
 542         if (ordered) {
 543             assertEquals(iterated, iteratedForEachRemaining);
 544             assertEquals(iterated, tryAdvanced);
 545             assertEquals(iterated, spliterated);
 546             assertEquals(iterated, splitonced);
 547             assertEquals(iterated, forEached);
 548             assertEquals(iterated, streamForEached);
 549             assertEquals(iterated, removeIfed);
 550         } else {
 551             assertEquals(cset, new HashSet(iterated));
 552             assertEquals(cset, new HashSet(iteratedForEachRemaining));
 553             assertEquals(cset, new HashSet(tryAdvanced));
 554             assertEquals(cset, new HashSet(spliterated));
 555             assertEquals(cset, new HashSet(splitonced));
 556             assertEquals(cset, new HashSet(forEached));
 557             assertEquals(cset, new HashSet(streamForEached));
 558             assertEquals(cset, new HashSet(removeIfed));
 559         }
 560         if (c instanceof Deque) {
 561             Deque d = (Deque) c;
 562             ArrayList descending = new ArrayList();
 563             ArrayList descendingForEachRemaining = new ArrayList();
 564             for (Iterator it = d.descendingIterator(); it.hasNext(); )
 565                 descending.add(it.next());
 566             d.descendingIterator().forEachRemaining(
 567                 e -> descendingForEachRemaining.add(e));
 568             Collections.reverse(descending);
 569             Collections.reverse(descendingForEachRemaining);
 570             assertEquals(iterated, descending);
 571             assertEquals(iterated, descendingForEachRemaining);
 572         }
 573     }
 574 
 575     /**
 576      * Iterator.forEachRemaining has same behavior as Iterator's
 577      * default implementation.
 578      */
 579     public void testForEachRemainingConsistentWithDefaultImplementation() {
 580         Collection c = impl.emptyCollection();
 581         if (!testImplementationDetails
 582             || c.getClass() == java.util.LinkedList.class)
 583             return;
 584         ThreadLocalRandom rnd = ThreadLocalRandom.current();
 585         int n = 1 + rnd.nextInt(3);
 586         for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
 587         ArrayList iterated = new ArrayList();
 588         ArrayList iteratedForEachRemaining = new ArrayList();
 589         Iterator it1 = c.iterator();
 590         Iterator it2 = c.iterator();
 591         assertTrue(it1.hasNext());
 592         assertTrue(it2.hasNext());
 593         c.clear();
 594         Object r1, r2;
 595         try {
 596             while (it1.hasNext()) iterated.add(it1.next());
 597             r1 = iterated;
 598         } catch (ConcurrentModificationException ex) {
 599             r1 = ConcurrentModificationException.class;
 600             assertFalse(impl.isConcurrent());
 601         }
 602         try {
 603             it2.forEachRemaining(iteratedForEachRemaining::add);
 604             r2 = iteratedForEachRemaining;
 605         } catch (ConcurrentModificationException ex) {
 606             r2 = ConcurrentModificationException.class;
 607             assertFalse(impl.isConcurrent());
 608         }
 609         assertEquals(r1, r2);
 610     }
 611 
 612     /**
 613      * Calling Iterator#remove() after Iterator#forEachRemaining
 614      * should (maybe) remove last element
 615      */
 616     public void testRemoveAfterForEachRemaining() {
 617         Collection c = impl.emptyCollection();
 618         ThreadLocalRandom rnd = ThreadLocalRandom.current();
 619         testCollection: {
 620             int n = 3 + rnd.nextInt(2);
 621             for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
 622             Iterator it = c.iterator();
 623             assertTrue(it.hasNext());
 624             assertEquals(impl.makeElement(0), it.next());
 625             assertTrue(it.hasNext());
 626             assertEquals(impl.makeElement(1), it.next());
 627             it.forEachRemaining(e -> assertTrue(c.contains(e)));
 628             if (testImplementationDetails) {
 629                 if (c instanceof java.util.concurrent.ArrayBlockingQueue) {
 630                     assertIteratorExhausted(it);
 631                 } else {
 632                     try { it.remove(); }
 633                     catch (UnsupportedOperationException ok) {
 634                         break testCollection;
 635                     }
 636                     assertEquals(n - 1, c.size());
 637                     for (int i = 0; i < n - 1; i++)
 638                         assertTrue(c.contains(impl.makeElement(i)));
 639                     assertFalse(c.contains(impl.makeElement(n - 1)));
 640                 }
 641             }
 642         }
 643         if (c instanceof Deque) {
 644             Deque d = (Deque) impl.emptyCollection();
 645             int n = 3 + rnd.nextInt(2);
 646             for (int i = 0; i < n; i++) d.add(impl.makeElement(i));
 647             Iterator it = d.descendingIterator();
 648             assertTrue(it.hasNext());
 649             assertEquals(impl.makeElement(n - 1), it.next());
 650             assertTrue(it.hasNext());
 651             assertEquals(impl.makeElement(n - 2), it.next());
 652             it.forEachRemaining(e -> assertTrue(c.contains(e)));
 653             if (testImplementationDetails) {
 654                 it.remove();
 655                 assertEquals(n - 1, d.size());
 656                 for (int i = 1; i < n; i++)
 657                     assertTrue(d.contains(impl.makeElement(i)));
 658                 assertFalse(d.contains(impl.makeElement(0)));
 659             }
 660         }
 661     }
 662 
 663     /**
 664      * stream().forEach returns elements in the collection
 665      */
 666     public void testStreamForEach() throws Throwable {
 667         final Collection c = impl.emptyCollection();
 668         final AtomicLong count = new AtomicLong(0L);
 669         final Object x = impl.makeElement(1);
 670         final Object y = impl.makeElement(2);
 671         final ArrayList found = new ArrayList();
 672         Consumer<Object> spy = o -> found.add(o);
 673         c.stream().forEach(spy);
 674         assertTrue(found.isEmpty());
 675 
 676         assertTrue(c.add(x));
 677         c.stream().forEach(spy);
 678         assertEquals(Collections.singletonList(x), found);
 679         found.clear();
 680 
 681         assertTrue(c.add(y));
 682         c.stream().forEach(spy);
 683         assertEquals(2, found.size());
 684         assertTrue(found.contains(x));
 685         assertTrue(found.contains(y));
 686         found.clear();
 687 
 688         c.clear();
 689         c.stream().forEach(spy);
 690         assertTrue(found.isEmpty());
 691     }
 692 
 693     public void testStreamForEachConcurrentStressTest() throws Throwable {
 694         if (!impl.isConcurrent()) return;
 695         final Collection c = impl.emptyCollection();
 696         final long testDurationMillis = timeoutMillis();
 697         final AtomicBoolean done = new AtomicBoolean(false);
 698         final Object elt = impl.makeElement(1);
 699         final Future<?> f1, f2;
 700         final ExecutorService pool = Executors.newCachedThreadPool();
 701         try (PoolCleaner cleaner = cleaner(pool, done)) {
 702             final CountDownLatch threadsStarted = new CountDownLatch(2);
 703             Runnable checkElt = () -> {
 704                 threadsStarted.countDown();
 705                 while (!done.get())
 706                     c.stream().forEach(x -> assertSame(x, elt)); };
 707             Runnable addRemove = () -> {
 708                 threadsStarted.countDown();
 709                 while (!done.get()) {
 710                     assertTrue(c.add(elt));
 711                     assertTrue(c.remove(elt));
 712                 }};
 713             f1 = pool.submit(checkElt);
 714             f2 = pool.submit(addRemove);
 715             Thread.sleep(testDurationMillis);
 716         }
 717         assertNull(f1.get(0L, MILLISECONDS));
 718         assertNull(f2.get(0L, MILLISECONDS));
 719     }
 720 
 721     /**
 722      * collection.forEach returns elements in the collection
 723      */
 724     public void testForEach() throws Throwable {
 725         final Collection c = impl.emptyCollection();
 726         final AtomicLong count = new AtomicLong(0L);
 727         final Object x = impl.makeElement(1);
 728         final Object y = impl.makeElement(2);
 729         final ArrayList found = new ArrayList();
 730         Consumer<Object> spy = o -> found.add(o);
 731         c.forEach(spy);
 732         assertTrue(found.isEmpty());
 733 
 734         assertTrue(c.add(x));
 735         c.forEach(spy);
 736         assertEquals(Collections.singletonList(x), found);
 737         found.clear();
 738 
 739         assertTrue(c.add(y));
 740         c.forEach(spy);
 741         assertEquals(2, found.size());
 742         assertTrue(found.contains(x));
 743         assertTrue(found.contains(y));
 744         found.clear();
 745 
 746         c.clear();
 747         c.forEach(spy);
 748         assertTrue(found.isEmpty());
 749     }
 750 
 751     /** TODO: promote to a common utility */
 752     static <T> T chooseOne(T ... ts) {
 753         return ts[ThreadLocalRandom.current().nextInt(ts.length)];
 754     }
 755 
 756     /** TODO: more random adders and removers */
 757     static <E> Runnable adderRemover(Collection<E> c, E e) {
 758         return chooseOne(
 759             () -> {
 760                 assertTrue(c.add(e));
 761                 assertTrue(c.contains(e));
 762                 assertTrue(c.remove(e));
 763                 assertFalse(c.contains(e));
 764             },
 765             () -> {
 766                 assertTrue(c.add(e));
 767                 assertTrue(c.contains(e));
 768                 assertTrue(c.removeIf(x -> x == e));
 769                 assertFalse(c.contains(e));
 770             },
 771             () -> {
 772                 assertTrue(c.add(e));
 773                 assertTrue(c.contains(e));
 774                 for (Iterator it = c.iterator();; )
 775                     if (it.next() == e) {
 776                         try { it.remove(); }
 777                         catch (UnsupportedOperationException ok) {
 778                             c.remove(e);
 779                         }
 780                         break;
 781                     }
 782                 assertFalse(c.contains(e));
 783             });
 784     }
 785 
 786     /**
 787      * Concurrent Spliterators, once exhausted, stay exhausted.
 788      */
 789     public void testStickySpliteratorExhaustion() throws Throwable {
 790         if (!impl.isConcurrent()) return;
 791         if (!testImplementationDetails) return;
 792         final ThreadLocalRandom rnd = ThreadLocalRandom.current();
 793         final Consumer alwaysThrows = e -> { throw new AssertionError(); };
 794         final Collection c = impl.emptyCollection();
 795         final Spliterator s = c.spliterator();
 796         if (rnd.nextBoolean()) {
 797             assertFalse(s.tryAdvance(alwaysThrows));
 798         } else {
 799             s.forEachRemaining(alwaysThrows);
 800         }
 801         final Object one = impl.makeElement(1);
 802         // Spliterator should not notice added element
 803         c.add(one);
 804         if (rnd.nextBoolean()) {
 805             assertFalse(s.tryAdvance(alwaysThrows));
 806         } else {
 807             s.forEachRemaining(alwaysThrows);
 808         }
 809     }
 810 
 811     /**
 812      * Motley crew of threads concurrently randomly hammer the collection.
 813      */
 814     public void testDetectRaces() throws Throwable {
 815         if (!impl.isConcurrent()) return;
 816         final ThreadLocalRandom rnd = ThreadLocalRandom.current();
 817         final Collection c = impl.emptyCollection();
 818         final long testDurationMillis
 819             = expensiveTests ? LONG_DELAY_MS : timeoutMillis();
 820         final AtomicBoolean done = new AtomicBoolean(false);
 821         final Object one = impl.makeElement(1);
 822         final Object two = impl.makeElement(2);
 823         final Consumer checkSanity = x -> assertTrue(x == one || x == two);
 824         final Consumer<Object[]> checkArraySanity = array -> {
 825             // assertTrue(array.length <= 2); // duplicates are permitted
 826             for (Object x : array) assertTrue(x == one || x == two);
 827         };
 828         final Object[] emptyArray =
 829             (Object[]) java.lang.reflect.Array.newInstance(one.getClass(), 0);
 830         final List<Future<?>> futures;
 831         final Phaser threadsStarted = new Phaser(1); // register this thread
 832         final Runnable[] frobbers = {
 833             () -> c.forEach(checkSanity),
 834             () -> c.stream().forEach(checkSanity),
 835             () -> c.parallelStream().forEach(checkSanity),
 836             () -> c.spliterator().trySplit(),
 837             () -> {
 838                 Spliterator s = c.spliterator();
 839                 s.tryAdvance(checkSanity);
 840                 s.trySplit();
 841             },
 842             () -> {
 843                 Spliterator s = c.spliterator();
 844                 do {} while (s.tryAdvance(checkSanity));
 845             },
 846             () -> { for (Object x : c) checkSanity.accept(x); },
 847             () -> checkArraySanity.accept(c.toArray()),
 848             () -> checkArraySanity.accept(c.toArray(emptyArray)),
 849             () -> {
 850                 Object[] a = new Object[5];
 851                 Object three = impl.makeElement(3);
 852                 Arrays.fill(a, 0, a.length, three);
 853                 Object[] x = c.toArray(a);
 854                 if (x == a)
 855                     for (int i = 0; i < a.length && a[i] != null; i++)
 856                         checkSanity.accept(a[i]);
 857                     // A careful reading of the spec does not support:
 858                     // for (i++; i < a.length; i++) assertSame(three, a[i]);
 859                 else
 860                     checkArraySanity.accept(x);
 861                 },
 862             adderRemover(c, one),
 863             adderRemover(c, two),
 864         };
 865         final List<Runnable> tasks =
 866             Arrays.stream(frobbers)
 867             .filter(task -> rnd.nextBoolean()) // random subset
 868             .map(task -> (Runnable) () -> {
 869                      threadsStarted.arriveAndAwaitAdvance();
 870                      while (!done.get())
 871                          task.run();
 872                  })
 873             .collect(Collectors.toList());
 874         final ExecutorService pool = Executors.newCachedThreadPool();
 875         try (PoolCleaner cleaner = cleaner(pool, done)) {
 876             threadsStarted.bulkRegister(tasks.size());
 877             futures = tasks.stream()
 878                 .map(pool::submit)
 879                 .collect(Collectors.toList());
 880             threadsStarted.arriveAndDeregister();
 881             Thread.sleep(testDurationMillis);
 882         }
 883         for (Future future : futures)
 884             assertNull(future.get(0L, MILLISECONDS));
 885     }
 886 
 887     /**
 888      * Spliterators are either IMMUTABLE or truly late-binding or, if
 889      * concurrent, use the same "late-binding style" of returning
 890      * elements added between creation and first use.
 891      */
 892     public void testLateBindingStyle() {
 893         if (!testImplementationDetails) return;
 894         if (impl.klazz() == ArrayList.class) return; // for jdk8
 895         // Immutable (snapshot) spliterators are exempt
 896         if (impl.emptyCollection().spliterator()
 897             .hasCharacteristics(Spliterator.IMMUTABLE))
 898             return;
 899         final Object one = impl.makeElement(1);
 900         {
 901             final Collection c = impl.emptyCollection();
 902             final Spliterator split = c.spliterator();
 903             c.add(one);
 904             assertTrue(split.tryAdvance(e -> { assertSame(e, one); }));
 905             assertFalse(split.tryAdvance(e -> { throw new AssertionError(); }));
 906             assertTrue(c.contains(one));
 907         }
 908         {
 909             final AtomicLong count = new AtomicLong(0);
 910             final Collection c = impl.emptyCollection();
 911             final Spliterator split = c.spliterator();
 912             c.add(one);
 913             split.forEachRemaining(
 914                 e -> { assertSame(e, one); count.getAndIncrement(); });
 915             assertEquals(1L, count.get());
 916             assertFalse(split.tryAdvance(e -> { throw new AssertionError(); }));
 917             assertTrue(c.contains(one));
 918         }
 919     }
 920 
 921     /**
 922      * Spliterator.getComparator throws IllegalStateException iff the
 923      * spliterator does not report SORTED.
 924      */
 925     public void testGetComparator_IllegalStateException() {
 926         Collection c = impl.emptyCollection();
 927         Spliterator s = c.spliterator();
 928         boolean reportsSorted = s.hasCharacteristics(Spliterator.SORTED);
 929         try {
 930             s.getComparator();
 931             assertTrue(reportsSorted);
 932         } catch (IllegalStateException ex) {
 933             assertFalse(reportsSorted);
 934         }
 935     }
 936 
 937     public void testCollectionCopies() throws Exception {
 938         ThreadLocalRandom rnd = ThreadLocalRandom.current();
 939         Collection c = impl.emptyCollection();
 940         for (int n = rnd.nextInt(4); n--> 0; )
 941             c.add(impl.makeElement(rnd.nextInt()));
 942         assertEquals(c, c);
 943         if (c instanceof List)
 944             assertCollectionsEquals(c, new ArrayList(c));
 945         else if (c instanceof Set)
 946             assertCollectionsEquals(c, new HashSet(c));
 947         else if (c instanceof Deque)
 948             assertCollectionsEquivalent(c, new ArrayDeque(c));
 949 
 950         Collection clone = cloneableClone(c);
 951         if (clone != null) {
 952             assertSame(c.getClass(), clone.getClass());
 953             assertCollectionsEquivalent(c, clone);
 954         }
 955         try {
 956             Collection serialClone = serialClonePossiblyFailing(c);
 957             assertSame(c.getClass(), serialClone.getClass());
 958             assertCollectionsEquivalent(c, serialClone);
 959         } catch (java.io.NotSerializableException acceptable) {}
 960     }
 961 
 962 //     public void testCollection8DebugFail() {
 963 //         fail(impl.klazz().getSimpleName());
 964 //     }
 965 }