SpliteratorCollisions.java revision 7899:02ce5a0e4b98 
1367SN/A/*
2462SN/A * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
3367SN/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4367SN/A *
5367SN/A * This code is free software; you can redistribute it and/or modify it
6367SN/A * under the terms of the GNU General Public License version 2 only, as
7367SN/A * published by the Free Software Foundation.
8367SN/A *
9367SN/A * This code is distributed in the hope that it will be useful, but WITHOUT
10367SN/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11367SN/A * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12367SN/A * version 2 for more details (a copy is included in the LICENSE file that
13367SN/A * accompanied this code).
14367SN/A *
15367SN/A * You should have received a copy of the GNU General Public License version
16367SN/A * 2 along with this work; if not, write to the Free Software Foundation,
17367SN/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18367SN/A *
19367SN/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20367SN/A * or visit www.oracle.com if you need additional information or have any
21367SN/A * questions.
22367SN/A */
23367SN/A
24367SN/A/**
25367SN/A * @test
26367SN/A * @bug 8005698
27367SN/A * @run testng SpliteratorCollisions
28367SN/A * @summary Spliterator traversing and splitting hash maps containing colliding hashes
29367SN/A * @author Brent Christian
30367SN/A */
31367SN/A
32367SN/Aimport org.testng.annotations.DataProvider;
33367SN/Aimport org.testng.annotations.Test;
34367SN/A
35367SN/Aimport java.util.ArrayDeque;
36367SN/Aimport java.util.ArrayList;
37367SN/Aimport java.util.Arrays;
38367SN/Aimport java.util.Collection;
39367SN/Aimport java.util.Collections;
40367SN/Aimport java.util.Deque;
41367SN/Aimport java.util.HashMap;
42367SN/Aimport java.util.HashSet;
43367SN/Aimport java.util.LinkedHashMap;
44367SN/Aimport java.util.LinkedHashSet;
45367SN/Aimport java.util.List;
46367SN/Aimport java.util.Map;
47367SN/Aimport java.util.Spliterator;
48367SN/Aimport java.util.TreeSet;
49367SN/Aimport java.util.function.Consumer;
50367SN/Aimport java.util.function.Function;
51367SN/Aimport java.util.function.Supplier;
52367SN/Aimport java.util.function.UnaryOperator;
53367SN/A
54367SN/Aimport static org.testng.Assert.*;
55367SN/Aimport static org.testng.Assert.assertEquals;
56367SN/A
57367SN/A@Test
58367SN/Apublic 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}
706