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 35import static java.util.concurrent.TimeUnit.HOURS; 36import static java.util.concurrent.TimeUnit.MILLISECONDS; 37 38import java.util.ArrayList; 39import java.util.Arrays; 40import java.util.Collection; 41import java.util.Collections; 42import java.util.ConcurrentModificationException; 43import java.util.Deque; 44import java.util.HashSet; 45import java.util.Iterator; 46import java.util.List; 47import java.util.NoSuchElementException; 48import java.util.Queue; 49import java.util.Spliterator; 50import java.util.concurrent.BlockingDeque; 51import java.util.concurrent.BlockingQueue; 52import java.util.concurrent.ConcurrentLinkedQueue; 53import java.util.concurrent.CountDownLatch; 54import java.util.concurrent.Executors; 55import java.util.concurrent.ExecutorService; 56import java.util.concurrent.Future; 57import java.util.concurrent.Phaser; 58import java.util.concurrent.ThreadLocalRandom; 59import java.util.concurrent.atomic.AtomicBoolean; 60import java.util.concurrent.atomic.AtomicLong; 61import java.util.concurrent.atomic.AtomicReference; 62import java.util.function.Consumer; 63import java.util.function.Predicate; 64import java.util.stream.Collectors; 65 66import junit.framework.Test; 67 68/** 69 * Contains tests applicable to all jdk8+ Collection implementations. 70 * An extension of CollectionTest. 71 */ 72public 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(0L, MILLISECONDS)); 171 } 172 if (c instanceof BlockingDeque) { 173 BlockingDeque q = (BlockingDeque) c; 174 assertNull(q.pollFirst(0L, MILLISECONDS)); 175 assertNull(q.pollLast(0L, MILLISECONDS)); 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} 911