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