1 /* 2 * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 /** 25 * @test 26 * @bug 8005698 27 * @run testng SpliteratorCollisions 28 * @summary Spliterator traversing and splitting hash maps containing colliding hashes 29 * @author Brent Christian 30 */ 31 32 import org.testng.annotations.DataProvider; 33 import org.testng.annotations.Test; 34 35 import java.util.ArrayDeque; 36 import java.util.ArrayList; 37 import java.util.Arrays; 38 import java.util.Collection; 39 import java.util.Collections; 40 import java.util.Deque; 41 import java.util.HashMap; 42 import java.util.HashSet; 43 import java.util.LinkedHashMap; 44 import java.util.LinkedHashSet; 45 import java.util.List; 46 import java.util.Map; 47 import java.util.Spliterator; 48 import java.util.TreeSet; 49 import java.util.function.Consumer; 50 import java.util.function.Function; 51 import java.util.function.LongConsumer; 52 import java.util.function.Supplier; 53 import java.util.function.UnaryOperator; 54 55 import static org.testng.Assert.*; 56 import static org.testng.Assert.assertEquals; 57 58 @Test 59 public class SpliteratorCollisions { 60 61 private static List<Integer> SIZES = Arrays.asList(0, 1, 10, 100, 1000); 62 63 private static class SpliteratorDataBuilder<T> { 64 List<Object[]> data; 65 List<T> exp; 66 Map<T, T> mExp; 67 68 SpliteratorDataBuilder(List<Object[]> data, List<T> exp) { 69 this.data = data; 70 this.exp = exp; 71 this.mExp = createMap(exp); 72 } 73 74 Map<T, T> createMap(List<T> l) { 75 Map<T, T> m = new LinkedHashMap<>(); 76 for (T t : l) { 77 m.put(t, t); 78 } 79 return m; 80 } 81 82 void add(String description, Collection<?> expected, Supplier<Spliterator<?>> s) { 83 description = joiner(description).toString(); 84 data.add(new Object[]{description, expected, s}); 85 } 86 87 void add(String description, Supplier<Spliterator<?>> s) { 88 add(description, exp, s); 89 } 90 91 void addCollection(Function<Collection<T>, ? extends Collection<T>> c) { 92 add("new " + c.apply(Collections.<T>emptyList()).getClass().getName() + ".spliterator()", 93 () -> c.apply(exp).spliterator()); 94 } 95 96 void addList(Function<Collection<T>, ? extends List<T>> l) { 97 // @@@ If collection is instance of List then add sub-list tests 98 addCollection(l); 99 } 100 101 void addMap(Function<Map<T, T>, ? extends Map<T, T>> m) { 102 String description = "new " + m.apply(Collections.<T, T>emptyMap()).getClass().getName(); 103 add(description + ".keySet().spliterator()", () -> m.apply(mExp).keySet().spliterator()); 104 add(description + ".values().spliterator()", () -> m.apply(mExp).values().spliterator()); 105 add(description + ".entrySet().spliterator()", mExp.entrySet(), () -> m.apply(mExp).entrySet().spliterator()); 106 } 107 108 StringBuilder joiner(String description) { 109 return new StringBuilder(description). 110 append(" {"). 111 append("size=").append(exp.size()). 112 append("}"); 113 } 114 } 115 116 static Object[][] spliteratorDataProvider; 117 118 @DataProvider(name = "HashableIntSpliterator") 119 public static Object[][] spliteratorDataProvider() { 120 if (spliteratorDataProvider != null) { 121 return spliteratorDataProvider; 122 } 123 124 List<Object[]> data = new ArrayList<>(); 125 for (int size : SIZES) { 126 List<HashableInteger> exp = listIntRange(size, false); 127 SpliteratorDataBuilder<HashableInteger> db = new SpliteratorDataBuilder<>(data, exp); 128 129 // Maps 130 db.addMap(HashMap::new); 131 db.addMap(LinkedHashMap::new); 132 133 // Collections that use HashMap 134 db.addCollection(HashSet::new); 135 db.addCollection(LinkedHashSet::new); 136 db.addCollection(TreeSet::new); 137 } 138 return spliteratorDataProvider = data.toArray(new Object[0][]); 139 } 140 141 static Object[][] spliteratorDataProviderWithNull; 142 143 @DataProvider(name = "HashableIntSpliteratorWithNull") 144 public static Object[][] spliteratorNullDataProvider() { 145 if (spliteratorDataProviderWithNull != null) { 146 return spliteratorDataProviderWithNull; 147 } 148 149 List<Object[]> data = new ArrayList<>(); 150 for (int size : SIZES) { 151 List<HashableInteger> exp = listIntRange(size, true); 152 exp.add(0, null); 153 SpliteratorDataBuilder<HashableInteger> db = new SpliteratorDataBuilder<>(data, exp); 154 155 // Maps 156 db.addMap(HashMap::new); 157 db.addMap(LinkedHashMap::new); 158 // TODO: add this back in if we decide to keep TreeBin in WeakHashMap 159 //db.addMap(WeakHashMap::new); 160 161 // Collections that use HashMap 162 db.addCollection(HashSet::new); 163 db.addCollection(LinkedHashSet::new); 164 // db.addCollection(TreeSet::new); 165 166 } 167 return spliteratorDataProviderWithNull = data.toArray(new Object[0][]); 168 } 169 170 final static class HashableInteger implements Comparable<HashableInteger> { 171 172 final int value; 173 final int hashmask; //yes duplication 174 175 HashableInteger(int value, int hashmask) { 176 this.value = value; 177 this.hashmask = hashmask; 178 } 179 180 @Override 181 public boolean equals(Object obj) { 182 if (obj instanceof HashableInteger) { 183 HashableInteger other = (HashableInteger) obj; 184 185 return other.value == value; 186 } 187 188 return false; 189 } 190 191 @Override 192 public int hashCode() { 193 return value % hashmask; 194 } 195 196 @Override 197 public int compareTo(HashableInteger o) { 198 return value - o.value; 199 } 200 201 @Override 202 public String toString() { 203 return Integer.toString(value); 204 } 205 } 206 207 private static List<HashableInteger> listIntRange(int upTo, boolean withNull) { 208 List<HashableInteger> exp = new ArrayList<>(); 209 if (withNull) { 210 exp.add(null); 211 } 212 for (int i = 0; i < upTo; i++) { 213 exp.add(new HashableInteger(i, 10)); 214 } 215 return Collections.unmodifiableList(exp); 216 } 217 218 @Test(dataProvider = "HashableIntSpliterator") 219 @SuppressWarnings({"unchecked", "rawtypes"}) 220 public void testNullPointerException(String description, Collection exp, Supplier<Spliterator> s) { 221 executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining(null)); 222 executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance(null)); 223 } 224 225 @Test(dataProvider = "HashableIntSpliteratorWithNull") 226 @SuppressWarnings({"unchecked", "rawtypes"}) 227 public void testNullPointerExceptionWithNull(String description, Collection exp, Supplier<Spliterator> s) { 228 executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining(null)); 229 executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance(null)); 230 } 231 232 233 @Test(dataProvider = "HashableIntSpliterator") 234 @SuppressWarnings({"unchecked", "rawtypes"}) 235 public void testForEach(String description, Collection exp, Supplier<Spliterator> s) { 236 testForEach(exp, s, (Consumer<Object> b) -> b); 237 } 238 239 @Test(dataProvider = "HashableIntSpliteratorWithNull") 240 @SuppressWarnings({"unchecked", "rawtypes"}) 241 public void testForEachWithNull(String description, Collection exp, Supplier<Spliterator> s) { 242 testForEach(exp, s, (Consumer<Object> b) -> b); 243 } 244 245 246 @Test(dataProvider = "HashableIntSpliterator") 247 @SuppressWarnings({"unchecked", "rawtypes"}) 248 public void testTryAdvance(String description, Collection exp, Supplier<Spliterator> s) { 249 testTryAdvance(exp, s, (Consumer<Object> b) -> b); 250 } 251 252 @Test(dataProvider = "HashableIntSpliteratorWithNull") 253 @SuppressWarnings({"unchecked", "rawtypes"}) 254 public void testTryAdvanceWithNull(String description, Collection exp, Supplier<Spliterator> s) { 255 testTryAdvance(exp, s, (Consumer<Object> b) -> b); 256 } 257 258 /* skip this test until 8013649 is fixed 259 @Test(dataProvider = "HashableIntSpliterator") 260 @SuppressWarnings({"unchecked", "rawtypes"}) 261 public void testMixedTryAdvanceForEach(String description, Collection exp, Supplier<Spliterator> s) { 262 testMixedTryAdvanceForEach(exp, s, (Consumer<Object> b) -> b); 263 } 264 265 @Test(dataProvider = "HashableIntSpliteratorWithNull") 266 @SuppressWarnings({"unchecked", "rawtypes"}) 267 public void testMixedTryAdvanceForEachWithNull(String description, Collection exp, Supplier<Spliterator> s) { 268 testMixedTryAdvanceForEach(exp, s, (Consumer<Object> b) -> b); 269 } 270 */ 271 272 @Test(dataProvider = "HashableIntSpliterator") 273 @SuppressWarnings({"unchecked", "rawtypes"}) 274 public void testSplitAfterFullTraversal(String description, Collection exp, Supplier<Spliterator> s) { 275 testSplitAfterFullTraversal(s, (Consumer<Object> b) -> b); 276 } 277 278 @Test(dataProvider = "HashableIntSpliteratorWithNull") 279 @SuppressWarnings({"unchecked", "rawtypes"}) 280 public void testSplitAfterFullTraversalWithNull(String description, Collection exp, Supplier<Spliterator> s) { 281 testSplitAfterFullTraversal(s, (Consumer<Object> b) -> b); 282 } 283 284 285 @Test(dataProvider = "HashableIntSpliterator") 286 @SuppressWarnings({"unchecked", "rawtypes"}) 287 public void testSplitOnce(String description, Collection exp, Supplier<Spliterator> s) { 288 testSplitOnce(exp, s, (Consumer<Object> b) -> b); 289 } 290 291 @Test(dataProvider = "HashableIntSpliteratorWithNull") 292 @SuppressWarnings({"unchecked", "rawtypes"}) 293 public void testSplitOnceWithNull(String description, Collection exp, Supplier<Spliterator> s) { 294 testSplitOnce(exp, s, (Consumer<Object> b) -> b); 295 } 296 297 @Test(dataProvider = "HashableIntSpliterator") 298 @SuppressWarnings({"unchecked", "rawtypes"}) 299 public void testSplitSixDeep(String description, Collection exp, Supplier<Spliterator> s) { 300 testSplitSixDeep(exp, s, (Consumer<Object> b) -> b); 301 } 302 303 @Test(dataProvider = "HashableIntSpliteratorWithNull") 304 @SuppressWarnings({"unchecked", "rawtypes"}) 305 public void testSplitSixDeepWithNull(String description, Collection exp, Supplier<Spliterator> s) { 306 testSplitSixDeep(exp, s, (Consumer<Object> b) -> b); 307 } 308 309 @Test(dataProvider = "HashableIntSpliterator") 310 @SuppressWarnings({"unchecked", "rawtypes"}) 311 public void testSplitUntilNull(String description, Collection exp, Supplier<Spliterator> s) { 312 testSplitUntilNull(exp, s, (Consumer<Object> b) -> b); 313 } 314 315 @Test(dataProvider = "HashableIntSpliteratorWithNull") 316 @SuppressWarnings({"unchecked", "rawtypes"}) 317 public void testSplitUntilNullWithNull(String description, Collection exp, Supplier<Spliterator> s) { 318 testSplitUntilNull(exp, s, (Consumer<Object> b) -> b); 319 } 320 321 private static <T, S extends Spliterator<T>> void testForEach( 322 Collection<T> exp, 323 Supplier<S> supplier, 324 UnaryOperator<Consumer<T>> boxingAdapter) { 325 S spliterator = supplier.get(); 326 long sizeIfKnown = spliterator.getExactSizeIfKnown(); 327 boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED); 328 329 ArrayList<T> fromForEach = new ArrayList<>(); 330 spliterator = supplier.get(); 331 Consumer<T> addToFromForEach = boxingAdapter.apply(fromForEach::add); 332 spliterator.forEachRemaining(addToFromForEach); 333 334 // Assert that forEach now produces no elements 335 spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e))); 336 // Assert that tryAdvance now produce no elements 337 spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e))); 338 339 // assert that size, tryAdvance, and forEach are consistent 340 if (sizeIfKnown >= 0) { 341 assertEquals(sizeIfKnown, exp.size()); 342 } 343 if (exp.contains(null)) { 344 assertTrue(fromForEach.contains(null)); 345 } 346 assertEquals(fromForEach.size(), exp.size()); 347 348 assertContents(fromForEach, exp, isOrdered); 349 } 350 351 private static <T, S extends Spliterator<T>> void testTryAdvance( 352 Collection<T> exp, 353 Supplier<S> supplier, 354 UnaryOperator<Consumer<T>> boxingAdapter) { 355 S spliterator = supplier.get(); 356 long sizeIfKnown = spliterator.getExactSizeIfKnown(); 357 boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED); 358 359 spliterator = supplier.get(); 360 ArrayList<T> fromTryAdvance = new ArrayList<>(); 361 Consumer<T> addToFromTryAdvance = boxingAdapter.apply(fromTryAdvance::add); 362 while (spliterator.tryAdvance(addToFromTryAdvance)) { } 363 364 // Assert that forEach now produces no elements 365 spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e))); 366 // Assert that tryAdvance now produce no elements 367 spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e))); 368 369 // assert that size, tryAdvance, and forEach are consistent 370 if (sizeIfKnown >= 0) { 371 assertEquals(sizeIfKnown, exp.size()); 372 } 373 assertEquals(fromTryAdvance.size(), exp.size()); 374 375 assertContents(fromTryAdvance, exp, isOrdered); 376 } 377 378 private static <T, S extends Spliterator<T>> void testMixedTryAdvanceForEach( 379 Collection<T> exp, 380 Supplier<S> supplier, 381 UnaryOperator<Consumer<T>> boxingAdapter) { 382 S spliterator = supplier.get(); 383 long sizeIfKnown = spliterator.getExactSizeIfKnown(); 384 boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED); 385 386 // tryAdvance first few elements, then forEach rest 387 ArrayList<T> dest = new ArrayList<>(); 388 spliterator = supplier.get(); 389 Consumer<T> addToDest = boxingAdapter.apply(dest::add); 390 for (int i = 0; i < 10 && spliterator.tryAdvance(addToDest); i++) { } 391 spliterator.forEachRemaining(addToDest); 392 393 // Assert that forEach now produces no elements 394 spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e))); 395 // Assert that tryAdvance now produce no elements 396 spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e))); 397 398 if (sizeIfKnown >= 0) { 399 assertEquals(sizeIfKnown, dest.size()); 400 } 401 assertEquals(dest.size(), exp.size()); 402 403 if (isOrdered) { 404 assertEquals(dest, exp); 405 } 406 else { 407 assertContentsUnordered(dest, exp); 408 } 409 } 410 411 private static <T, S extends Spliterator<T>> void testSplitAfterFullTraversal( 412 Supplier<S> supplier, 413 UnaryOperator<Consumer<T>> boxingAdapter) { 414 // Full traversal using tryAdvance 415 Spliterator<T> spliterator = supplier.get(); 416 while (spliterator.tryAdvance(boxingAdapter.apply(e -> { }))) { } 417 Spliterator<T> split = spliterator.trySplit(); 418 assertNull(split); 419 420 // Full traversal using forEach 421 spliterator = supplier.get(); 422 spliterator.forEachRemaining(boxingAdapter.apply(e -> { 423 })); 424 split = spliterator.trySplit(); 425 assertNull(split); 426 427 // Full traversal using tryAdvance then forEach 428 spliterator = supplier.get(); 429 spliterator.tryAdvance(boxingAdapter.apply(e -> { })); 430 spliterator.forEachRemaining(boxingAdapter.apply(e -> { 431 })); 432 split = spliterator.trySplit(); 433 assertNull(split); 434 } 435 436 private static <T, S extends Spliterator<T>> void testSplitOnce( 437 Collection<T> exp, 438 Supplier<S> supplier, 439 UnaryOperator<Consumer<T>> boxingAdapter) { 440 S spliterator = supplier.get(); 441 long sizeIfKnown = spliterator.getExactSizeIfKnown(); 442 boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED); 443 444 ArrayList<T> fromSplit = new ArrayList<>(); 445 Spliterator<T> s1 = supplier.get(); 446 Spliterator<T> s2 = s1.trySplit(); 447 long s1Size = s1.getExactSizeIfKnown(); 448 long s2Size = (s2 != null) ? s2.getExactSizeIfKnown() : 0; 449 450 Consumer<T> addToFromSplit = boxingAdapter.apply(fromSplit::add); 451 if (s2 != null) 452 s2.forEachRemaining(addToFromSplit); 453 s1.forEachRemaining(addToFromSplit); 454 455 if (sizeIfKnown >= 0) { 456 assertEquals(sizeIfKnown, fromSplit.size()); 457 if (s1Size >= 0 && s2Size >= 0) 458 assertEquals(sizeIfKnown, s1Size + s2Size); 459 } 460 assertContents(fromSplit, exp, isOrdered); 461 } 462 463 private static <T, S extends Spliterator<T>> void testSplitSixDeep( 464 Collection<T> exp, 465 Supplier<S> supplier, 466 UnaryOperator<Consumer<T>> boxingAdapter) { 467 S spliterator = supplier.get(); 468 boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED); 469 470 for (int depth=0; depth < 6; depth++) { 471 List<T> dest = new ArrayList<>(); 472 spliterator = supplier.get(); 473 474 assertSpliterator(spliterator); 475 476 // verify splitting with forEach 477 visit(depth, 0, dest, spliterator, boxingAdapter, spliterator.characteristics(), false); 478 assertContents(dest, exp, isOrdered); 479 480 // verify splitting with tryAdvance 481 dest.clear(); 482 spliterator = supplier.get(); 483 visit(depth, 0, dest, spliterator, boxingAdapter, spliterator.characteristics(), true); 484 assertContents(dest, exp, isOrdered); 485 } 486 } 487 488 private static <T, S extends Spliterator<T>> void visit(int depth, int curLevel, 489 List<T> dest, S spliterator, UnaryOperator<Consumer<T>> boxingAdapter, 490 int rootCharacteristics, boolean useTryAdvance) { 491 if (curLevel < depth) { 492 long beforeSize = spliterator.getExactSizeIfKnown(); 493 Spliterator<T> split = spliterator.trySplit(); 494 if (split != null) { 495 assertSpliterator(split, rootCharacteristics); 496 assertSpliterator(spliterator, rootCharacteristics); 497 498 if ((rootCharacteristics & Spliterator.SUBSIZED) != 0 && 499 (rootCharacteristics & Spliterator.SIZED) != 0) { 500 assertEquals(beforeSize, split.estimateSize() + spliterator.estimateSize()); 501 } 502 visit(depth, curLevel + 1, dest, split, boxingAdapter, rootCharacteristics, useTryAdvance); 503 } 504 visit(depth, curLevel + 1, dest, spliterator, boxingAdapter, rootCharacteristics, useTryAdvance); 505 } 506 else { 507 long sizeIfKnown = spliterator.getExactSizeIfKnown(); 508 if (useTryAdvance) { 509 Consumer<T> addToDest = boxingAdapter.apply(dest::add); 510 int count = 0; 511 while (spliterator.tryAdvance(addToDest)) { 512 ++count; 513 } 514 515 if (sizeIfKnown >= 0) 516 assertEquals(sizeIfKnown, count); 517 518 // Assert that forEach now produces no elements 519 spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e))); 520 521 Spliterator<T> split = spliterator.trySplit(); 522 assertNull(split); 523 } 524 else { 525 List<T> leafDest = new ArrayList<>(); 526 Consumer<T> addToLeafDest = boxingAdapter.apply(leafDest::add); 527 spliterator.forEachRemaining(addToLeafDest); 528 529 if (sizeIfKnown >= 0) 530 assertEquals(sizeIfKnown, leafDest.size()); 531 532 // Assert that forEach now produces no elements 533 spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e))); 534 535 Spliterator<T> split = spliterator.trySplit(); 536 assertNull(split); 537 538 dest.addAll(leafDest); 539 } 540 } 541 } 542 543 private static <T, S extends Spliterator<T>> void testSplitUntilNull( 544 Collection<T> exp, 545 Supplier<S> supplier, 546 UnaryOperator<Consumer<T>> boxingAdapter) { 547 Spliterator<T> s = supplier.get(); 548 boolean isOrdered = s.hasCharacteristics(Spliterator.ORDERED); 549 assertSpliterator(s); 550 551 List<T> splits = new ArrayList<>(); 552 Consumer<T> c = boxingAdapter.apply(splits::add); 553 554 testSplitUntilNull(new SplitNode<T>(c, s)); 555 assertContents(splits, exp, isOrdered); 556 } 557 558 private static class SplitNode<T> { 559 // Constant for every node 560 final Consumer<T> c; 561 final int rootCharacteristics; 562 563 final Spliterator<T> s; 564 565 SplitNode(Consumer<T> c, Spliterator<T> s) { 566 this(c, s.characteristics(), s); 567 } 568 569 private SplitNode(Consumer<T> c, int rootCharacteristics, Spliterator<T> s) { 570 this.c = c; 571 this.rootCharacteristics = rootCharacteristics; 572 this.s = s; 573 } 574 575 SplitNode<T> fromSplit(Spliterator<T> split) { 576 return new SplitNode<>(c, rootCharacteristics, split); 577 } 578 } 579 580 /** 581 * Set the maximum stack capacity to 0.25MB. This should be more than enough to detect a bad spliterator 582 * while not unduly disrupting test infrastructure given the test data sizes that are used are small. 583 * Note that j.u.c.ForkJoinPool sets the max queue size to 64M (1 << 26). 584 */ 585 private static final int MAXIMUM_STACK_CAPACITY = 1 << 18; // 0.25MB 586 587 private static <T> void testSplitUntilNull(SplitNode<T> e) { 588 // Use an explicit stack to avoid a StackOverflowException when testing a Spliterator 589 // that when repeatedly split produces a right-balanced (and maybe degenerate) tree, or 590 // for a spliterator that is badly behaved. 591 Deque<SplitNode<T>> stack = new ArrayDeque<>(); 592 stack.push(e); 593 594 int iteration = 0; 595 while (!stack.isEmpty()) { 596 assertTrue(iteration++ < MAXIMUM_STACK_CAPACITY, "Exceeded maximum stack modification count of 1 << 18"); 597 598 e = stack.pop(); 599 Spliterator<T> parentAndRightSplit = e.s; 600 601 long parentEstimateSize = parentAndRightSplit.estimateSize(); 602 assertTrue(parentEstimateSize >= 0, 603 String.format("Split size estimate %d < 0", parentEstimateSize)); 604 605 long parentSize = parentAndRightSplit.getExactSizeIfKnown(); 606 Spliterator<T> leftSplit = parentAndRightSplit.trySplit(); 607 if (leftSplit == null) { 608 parentAndRightSplit.forEachRemaining(e.c); 609 continue; 610 } 611 612 assertSpliterator(leftSplit, e.rootCharacteristics); 613 assertSpliterator(parentAndRightSplit, e.rootCharacteristics); 614 615 if (parentEstimateSize != Long.MAX_VALUE && leftSplit.estimateSize() > 0 && parentAndRightSplit.estimateSize() > 0) { 616 assertTrue(leftSplit.estimateSize() < parentEstimateSize, 617 String.format("Left split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize)); 618 assertTrue(parentAndRightSplit.estimateSize() < parentEstimateSize, 619 String.format("Right split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize)); 620 } 621 else { 622 assertTrue(leftSplit.estimateSize() <= parentEstimateSize, 623 String.format("Left split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize)); 624 assertTrue(parentAndRightSplit.estimateSize() <= parentEstimateSize, 625 String.format("Right split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize)); 626 } 627 628 long leftSize = leftSplit.getExactSizeIfKnown(); 629 long rightSize = parentAndRightSplit.getExactSizeIfKnown(); 630 if (parentSize >= 0 && leftSize >= 0 && rightSize >= 0) 631 assertEquals(parentSize, leftSize + rightSize, 632 String.format("exact left split size %d + exact right split size %d != parent exact split size %d", 633 leftSize, rightSize, parentSize)); 634 635 // Add right side to stack first so left side is popped off first 636 stack.push(e.fromSplit(parentAndRightSplit)); 637 stack.push(e.fromSplit(leftSplit)); 638 } 639 } 640 641 private static void assertSpliterator(Spliterator<?> s, int rootCharacteristics) { 642 if ((rootCharacteristics & Spliterator.SUBSIZED) != 0) { 643 assertTrue(s.hasCharacteristics(Spliterator.SUBSIZED), 644 "Child split is not SUBSIZED when root split is SUBSIZED"); 645 } 646 assertSpliterator(s); 647 } 648 649 private static void assertSpliterator(Spliterator<?> s) { 650 if (s.hasCharacteristics(Spliterator.SUBSIZED)) { 651 assertTrue(s.hasCharacteristics(Spliterator.SIZED)); 652 } 653 if (s.hasCharacteristics(Spliterator.SIZED)) { 654 assertTrue(s.estimateSize() != Long.MAX_VALUE); 655 assertTrue(s.getExactSizeIfKnown() >= 0); 656 } 657 try { 658 s.getComparator(); 659 assertTrue(s.hasCharacteristics(Spliterator.SORTED)); 660 } catch (IllegalStateException e) { 661 assertFalse(s.hasCharacteristics(Spliterator.SORTED)); 662 } 663 } 664 665 private static<T> void assertContents(Collection<T> actual, Collection<T> expected, boolean isOrdered) { 666 if (isOrdered) { 667 assertEquals(actual, expected); 668 } 669 else { 670 assertContentsUnordered(actual, expected); 671 } 672 } 673 674 private static<T> void assertContentsUnordered(Iterable<T> actual, Iterable<T> expected) { 675 assertEquals(toBoxedMultiset(actual), toBoxedMultiset(expected)); 676 } 677 678 private static <T> Map<T, HashableInteger> toBoxedMultiset(Iterable<T> c) { 679 Map<T, HashableInteger> result = new HashMap<>(); 680 c.forEach((Consumer) e -> { 681 if (result.containsKey((T)e)) { 682 result.put((T)e, new HashableInteger(((HashableInteger)result.get(e)).value + 1, 10)); 683 } else { 684 result.put((T)e, new HashableInteger(1, 10)); 685 } 686 }); 687 return result; 688 } 689 690 private void executeAndCatch(Class<? extends Exception> expected, Runnable r) { 691 Exception caught = null; 692 try { 693 r.run(); 694 } 695 catch (Exception e) { 696 caught = e; 697 } 698 699 assertNotNull(caught, 700 String.format("No Exception was thrown, expected an Exception of %s to be thrown", 701 expected.getName())); 702 assertTrue(expected.isInstance(caught), 703 String.format("Exception thrown %s not an instance of %s", 704 caught.getClass().getName(), expected.getName())); 705 } 706 707 }