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