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