1 /*

     2  * Copyright (c) 2012, 2017, 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 package java.util;

    24 

    25 import java.util.function.*;

    26 import java.util.stream.LambdaTestHelpers;

    27 

    28 import static org.testng.Assert.*;

    29 

    30 /**

    31  * Assertion methods for spliterators, to be called from other tests

    32  */

    33 public class SpliteratorTestHelper {

    34 

    35     public interface ContentAsserter<T> {

    36         void assertContents(Collection<T> actual, Collection<T> expected, boolean isOrdered);

    37     }

    38 

    39     private static ContentAsserter<Object> DEFAULT_CONTENT_ASSERTER

    40             = SpliteratorTestHelper::assertContents;

    41 

    42     @SuppressWarnings("unchecked")

    43     private static <T> ContentAsserter<T> defaultContentAsserter() {

    44         return (ContentAsserter<T>) DEFAULT_CONTENT_ASSERTER;

    45     }

    46 

    47     public static void testSpliterator(Supplier<Spliterator<Integer>> supplier) {

    48         testSpliterator(supplier, defaultContentAsserter());

    49     }

    50 

    51     public static void testSpliterator(Supplier<Spliterator<Integer>> supplier,

    52                                        ContentAsserter<Integer> asserter) {

    53         testSpliterator(supplier, (Consumer<Integer> b) -> b, asserter);

    54     }

    55 

    56     public static void testIntSpliterator(Supplier<Spliterator.OfInt> supplier) {

    57         testIntSpliterator(supplier, defaultContentAsserter());

    58     }

    59 

    60     public static void testIntSpliterator(Supplier<Spliterator.OfInt> supplier,

    61                                           ContentAsserter<Integer> asserter) {

    62         testSpliterator(supplier, intBoxingConsumer(), asserter);

    63     }

    64 

    65     public static void testLongSpliterator(Supplier<Spliterator.OfLong> supplier) {

    66         testLongSpliterator(supplier, defaultContentAsserter());

    67     }

    68 

    69     public static void testLongSpliterator(Supplier<Spliterator.OfLong> supplier,

    70                                            ContentAsserter<Long> asserter) {

    71         testSpliterator(supplier, longBoxingConsumer(), asserter);

    72     }

    73 

    74     public static void testDoubleSpliterator(Supplier<Spliterator.OfDouble> supplier) {

    75         testDoubleSpliterator(supplier, defaultContentAsserter());

    76     }

    77 

    78     public static void testDoubleSpliterator(Supplier<Spliterator.OfDouble> supplier,

    79                                              ContentAsserter<Double> asserter) {

    80         testSpliterator(supplier, doubleBoxingConsumer(), asserter);

    81     }

    82 

    83     public static UnaryOperator<Consumer<Integer>> intBoxingConsumer() {

    84         class BoxingAdapter implements Consumer<Integer>, IntConsumer {

    85             private final Consumer<Integer> b;

    86 

    87             BoxingAdapter(Consumer<Integer> b) {

    88                 this.b = b;

    89             }

    90 

    91             @Override

    92             public void accept(Integer value) {

    93                 throw new IllegalStateException();

    94             }

    95 

    96             @Override

    97             public void accept(int value) {

    98                 b.accept(value);

    99             }

   100         }

   101 

   102         return b -> new BoxingAdapter(b);

   103     }

   104 

   105     public static UnaryOperator<Consumer<Long>> longBoxingConsumer() {

   106         class BoxingAdapter implements Consumer<Long>, LongConsumer {

   107             private final Consumer<Long> b;

   108 

   109             BoxingAdapter(Consumer<Long> b) {

   110                 this.b = b;

   111             }

   112 

   113             @Override

   114             public void accept(Long value) {

   115                 throw new IllegalStateException();

   116             }

   117 

   118             @Override

   119             public void accept(long value) {

   120                 b.accept(value);

   121             }

   122         }

   123 

   124         return b -> new BoxingAdapter(b);

   125     }

   126 

   127     public static UnaryOperator<Consumer<Double>> doubleBoxingConsumer() {

   128         class BoxingAdapter implements Consumer<Double>, DoubleConsumer {

   129             private final Consumer<Double> b;

   130 

   131             BoxingAdapter(Consumer<Double> b) {

   132                 this.b = b;

   133             }

   134 

   135             @Override

   136             public void accept(Double value) {

   137                 throw new IllegalStateException();

   138             }

   139 

   140             @Override

   141             public void accept(double value) {

   142                 b.accept(value);

   143             }

   144         }

   145 

   146         return b -> new BoxingAdapter(b);

   147     }

   148 

   149     public static <T, S extends Spliterator<T>> void testSpliterator(Supplier<S> supplier,

   150                                                               UnaryOperator<Consumer<T>> boxingAdapter,

   151                                                               ContentAsserter<T> asserter) {

   152         ArrayList<T> fromForEach = new ArrayList<>();

   153         Spliterator<T> spliterator = supplier.get();

   154         Consumer<T> addToFromForEach = boxingAdapter.apply(fromForEach::add);

   155         spliterator.forEachRemaining(addToFromForEach);

   156 

   157         Collection<T> exp = Collections.unmodifiableList(fromForEach);

   158 

   159         testNullPointerException(supplier);

   160         testForEach(exp, supplier, boxingAdapter, asserter);

   161         testTryAdvance(exp, supplier, boxingAdapter, asserter);

   162         testMixedTryAdvanceForEach(exp, supplier, boxingAdapter, asserter);

   163         testMixedTraverseAndSplit(exp, supplier, boxingAdapter, asserter);

   164         testSplitAfterFullTraversal(supplier, boxingAdapter);

   165         testSplitOnce(exp, supplier, boxingAdapter, asserter);

   166         testSplitSixDeep(exp, supplier, boxingAdapter, asserter);

   167         testSplitUntilNull(exp, supplier, boxingAdapter, asserter);

   168     }

   169 

   170     public static <T, S extends Spliterator<T>> void testForEach(

   171             Collection<T> exp,

   172             Supplier<S> supplier,

   173             UnaryOperator<Consumer<T>> boxingAdapter) {

   174         testForEach(exp, supplier, boxingAdapter, defaultContentAsserter());

   175     }

   176 

   177     public static <T, S extends Spliterator<T>> void testTryAdvance(

   178             Collection<T> exp,

   179             Supplier<S> supplier,

   180             UnaryOperator<Consumer<T>> boxingAdapter) {

   181         testTryAdvance(exp, supplier, boxingAdapter, defaultContentAsserter());

   182     }

   183 

   184     public static <T, S extends Spliterator<T>> void testMixedTryAdvanceForEach(

   185             Collection<T> exp,

   186             Supplier<S> supplier,

   187             UnaryOperator<Consumer<T>> boxingAdapter) {

   188         testMixedTryAdvanceForEach(exp, supplier, boxingAdapter, defaultContentAsserter());

   189     }

   190 

   191     public static <T, S extends Spliterator<T>> void testMixedTraverseAndSplit(

   192             Collection<T> exp,

   193             Supplier<S> supplier,

   194             UnaryOperator<Consumer<T>> boxingAdapter) {

   195         testMixedTraverseAndSplit(exp, supplier, boxingAdapter, defaultContentAsserter());

   196     }

   197 

   198     public static <T, S extends Spliterator<T>> void testSplitOnce(

   199             Collection<T> exp,

   200             Supplier<S> supplier,

   201             UnaryOperator<Consumer<T>> boxingAdapter) {

   202         testSplitOnce(exp, supplier, boxingAdapter, defaultContentAsserter());

   203     }

   204 

   205     public static <T, S extends Spliterator<T>> void testSplitSixDeep(

   206             Collection<T> exp,

   207             Supplier<S> supplier,

   208             UnaryOperator<Consumer<T>> boxingAdapter) {

   209         testSplitSixDeep(exp, supplier, boxingAdapter, defaultContentAsserter());

   210     }

   211 

   212     public static <T, S extends Spliterator<T>> void testSplitUntilNull(

   213             Collection<T> exp,

   214             Supplier<S> supplier,

   215             UnaryOperator<Consumer<T>> boxingAdapter) {

   216         testSplitUntilNull(exp, supplier, boxingAdapter, defaultContentAsserter());

   217     }

   218 

   219     private static <T, S extends Spliterator<T>> void testNullPointerException(Supplier<S> s) {

   220         S sp = s.get();

   221         // Have to check instances and use casts to avoid tripwire messages and

   222         // directly test the primitive methods

   223         if (sp instanceof Spliterator.OfInt) {

   224             Spliterator.OfInt psp = (Spliterator.OfInt) sp;

   225             assertThrowsNPE(() -> psp.forEachRemaining((IntConsumer) null));

   226             assertThrowsNPE(() -> psp.tryAdvance((IntConsumer) null));

   227         }

   228         else if (sp instanceof Spliterator.OfLong) {

   229             Spliterator.OfLong psp = (Spliterator.OfLong) sp;

   230             assertThrowsNPE(() -> psp.forEachRemaining((LongConsumer) null));

   231             assertThrowsNPE(() -> psp.tryAdvance((LongConsumer) null));

   232         }

   233         else if (sp instanceof Spliterator.OfDouble) {

   234             Spliterator.OfDouble psp = (Spliterator.OfDouble) sp;

   235             assertThrowsNPE(() -> psp.forEachRemaining((DoubleConsumer) null));

   236             assertThrowsNPE(() -> psp.tryAdvance((DoubleConsumer) null));

   237         }

   238         else {

   239             assertThrowsNPE(() -> sp.forEachRemaining(null));

   240             assertThrowsNPE(() -> sp.tryAdvance(null));

   241         }

   242     }

   243 

   244     private static <T, S extends Spliterator<T>> void testForEach(

   245             Collection<T> exp,

   246             Supplier<S> supplier,

   247             UnaryOperator<Consumer<T>> boxingAdapter,

   248             ContentAsserter<T> asserter) {

   249         S spliterator = supplier.get();

   250         long sizeIfKnown = spliterator.getExactSizeIfKnown();

   251         boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);

   252 

   253         ArrayList<T> fromForEach = new ArrayList<>();

   254         spliterator = supplier.get();

   255         Consumer<T> addToFromForEach = boxingAdapter.apply(fromForEach::add);

   256         spliterator.forEachRemaining(addToFromForEach);

   257 

   258         // Assert that forEach now produces no elements

   259         spliterator.forEachRemaining(boxingAdapter.apply(

   260                 e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));

   261         // Assert that tryAdvance now produce no elements

   262         spliterator.tryAdvance(boxingAdapter.apply(

   263                 e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e)));

   264 

   265         // assert that size, tryAdvance, and forEach are consistent

   266         if (sizeIfKnown >= 0) {

   267             assertEquals(sizeIfKnown, exp.size());

   268         }

   269         if (exp.contains(null)) {

   270             assertTrue(fromForEach.contains(null));

   271         }

   272         assertEquals(fromForEach.size(), exp.size());

   273 

   274         asserter.assertContents(fromForEach, exp, isOrdered);

   275     }

   276 

   277     private static <T, S extends Spliterator<T>> void testTryAdvance(

   278             Collection<T> exp,

   279             Supplier<S> supplier,

   280             UnaryOperator<Consumer<T>> boxingAdapter,

   281             ContentAsserter<T> asserter) {

   282         S spliterator = supplier.get();

   283         long sizeIfKnown = spliterator.getExactSizeIfKnown();

   284         boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);

   285 

   286         spliterator = supplier.get();

   287         ArrayList<T> fromTryAdvance = new ArrayList<>();

   288         Consumer<T> addToFromTryAdvance = boxingAdapter.apply(fromTryAdvance::add);

   289         while (spliterator.tryAdvance(addToFromTryAdvance)) { }

   290 

   291         // Assert that forEach now produces no elements

   292         spliterator.forEachRemaining(boxingAdapter.apply(

   293                 e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));

   294         // Assert that tryAdvance now produce no elements

   295         spliterator.tryAdvance(boxingAdapter.apply(

   296                 e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e)));

   297 

   298         // assert that size, tryAdvance, and forEach are consistent

   299         if (sizeIfKnown >= 0) {

   300             assertEquals(sizeIfKnown, exp.size());

   301         }

   302         assertEquals(fromTryAdvance.size(), exp.size());

   303 

   304         asserter.assertContents(fromTryAdvance, exp, isOrdered);

   305     }

   306 

   307     private static <T, S extends Spliterator<T>> void testMixedTryAdvanceForEach(

   308             Collection<T> exp,

   309             Supplier<S> supplier,

   310             UnaryOperator<Consumer<T>> boxingAdapter,

   311             ContentAsserter<T> asserter) {

   312         S spliterator = supplier.get();

   313         long sizeIfKnown = spliterator.getExactSizeIfKnown();

   314         boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);

   315 

   316         // tryAdvance first few elements, then forEach rest

   317         ArrayList<T> dest = new ArrayList<>();

   318         spliterator = supplier.get();

   319         Consumer<T> addToDest = boxingAdapter.apply(dest::add);

   320         for (int i = 0; i < 10 && spliterator.tryAdvance(addToDest); i++) { }

   321         spliterator.forEachRemaining(addToDest);

   322 

   323         // Assert that forEach now produces no elements

   324         spliterator.forEachRemaining(boxingAdapter.apply(

   325                 e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));

   326         // Assert that tryAdvance now produce no elements

   327         spliterator.tryAdvance(boxingAdapter.apply(

   328                 e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e)));

   329 

   330         if (sizeIfKnown >= 0) {

   331             assertEquals(sizeIfKnown, dest.size());

   332         }

   333         assertEquals(dest.size(), exp.size());

   334 

   335         asserter.assertContents(dest, exp, isOrdered);

   336     }

   337 

   338     private static <T, S extends Spliterator<T>> void testMixedTraverseAndSplit(

   339             Collection<T> exp,

   340             Supplier<S> supplier,

   341             UnaryOperator<Consumer<T>> boxingAdapter,

   342             ContentAsserter<T> asserter) {

   343         S spliterator = supplier.get();

   344         long sizeIfKnown = spliterator.getExactSizeIfKnown();

   345         boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);

   346 

   347         // tryAdvance first few elements, then forEach rest

   348         ArrayList<T> dest = new ArrayList<>();

   349         spliterator = supplier.get();

   350         Consumer<T> b = boxingAdapter.apply(dest::add);

   351 

   352         Spliterator<T> spl1, spl2, spl3;

   353         spliterator.tryAdvance(b);

   354         spl2 = spliterator.trySplit();

   355         if (spl2 != null) {

   356             spl2.tryAdvance(b);

   357             spl1 = spl2.trySplit();

   358             if (spl1 != null) {

   359                 spl1.tryAdvance(b);

   360                 spl1.forEachRemaining(b);

   361             }

   362             spl2.tryAdvance(b);

   363             spl2.forEachRemaining(b);

   364         }

   365         spliterator.tryAdvance(b);

   366         spl3 = spliterator.trySplit();

   367         if (spl3 != null) {

   368             spl3.tryAdvance(b);

   369             spl3.forEachRemaining(b);

   370         }

   371         spliterator.tryAdvance(b);

   372         spliterator.forEachRemaining(b);

   373 

   374         if (sizeIfKnown >= 0) {

   375             assertEquals(sizeIfKnown, dest.size());

   376         }

   377         assertEquals(dest.size(), exp.size());

   378 

   379         asserter.assertContents(dest, exp, isOrdered);

   380     }

   381 

   382     public static <T, S extends Spliterator<T>> void testSplitAfterFullTraversal(

   383             Supplier<S> supplier,

   384             UnaryOperator<Consumer<T>> boxingAdapter) {

   385         // Full traversal using tryAdvance

   386         Spliterator<T> spliterator = supplier.get();

   387         while (spliterator.tryAdvance(boxingAdapter.apply(e -> { }))) { }

   388         Spliterator<T> split = spliterator.trySplit();

   389         assertNull(split);

   390 

   391         // Full traversal using forEach

   392         spliterator = supplier.get();

   393         spliterator.forEachRemaining(boxingAdapter.apply(e -> { }));

   394         split = spliterator.trySplit();

   395         assertNull(split);

   396 

   397         // Full traversal using tryAdvance then forEach

   398         spliterator = supplier.get();

   399         spliterator.tryAdvance(boxingAdapter.apply(e -> { }));

   400         spliterator.forEachRemaining(boxingAdapter.apply(e -> { }));

   401         split = spliterator.trySplit();

   402         assertNull(split);

   403     }

   404 

   405     private static <T, S extends Spliterator<T>> void testSplitOnce(

   406             Collection<T> exp,

   407             Supplier<S> supplier,

   408             UnaryOperator<Consumer<T>> boxingAdapter,

   409             ContentAsserter<T> asserter) {

   410         S spliterator = supplier.get();

   411         long sizeIfKnown = spliterator.getExactSizeIfKnown();

   412         boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);

   413 

   414         ArrayList<T> fromSplit = new ArrayList<>();

   415         Spliterator<T> s1 = supplier.get();

   416         Spliterator<T> s2 = s1.trySplit();

   417         long s1Size = s1.getExactSizeIfKnown();

   418         long s2Size = (s2 != null) ? s2.getExactSizeIfKnown() : 0;

   419         Consumer<T> addToFromSplit = boxingAdapter.apply(fromSplit::add);

   420         if (s2 != null)

   421             s2.forEachRemaining(addToFromSplit);

   422         s1.forEachRemaining(addToFromSplit);

   423 

   424         if (sizeIfKnown >= 0) {

   425             assertEquals(sizeIfKnown, fromSplit.size());

   426             if (s1Size >= 0 && s2Size >= 0)

   427                 assertEquals(sizeIfKnown, s1Size + s2Size);

   428         }

   429 

   430         asserter.assertContents(fromSplit, exp, isOrdered);

   431     }

   432 

   433     private static <T, S extends Spliterator<T>> void testSplitSixDeep(

   434             Collection<T> exp,

   435             Supplier<S> supplier,

   436             UnaryOperator<Consumer<T>> boxingAdapter,

   437             ContentAsserter<T> asserter) {

   438         S spliterator = supplier.get();

   439         boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED);

   440 

   441         for (int depth=0; depth < 6; depth++) {

   442             List<T> dest = new ArrayList<>();

   443             spliterator = supplier.get();

   444 

   445             assertSpliterator(spliterator);

   446 

   447             // verify splitting with forEach

   448             splitSixDeepVisitor(depth, 0, dest, spliterator, boxingAdapter, spliterator.characteristics(), false);

   449             asserter.assertContents(dest, exp, isOrdered);

   450 

   451             // verify splitting with tryAdvance

   452             dest.clear();

   453             spliterator = supplier.get();

   454             splitSixDeepVisitor(depth, 0, dest, spliterator, boxingAdapter, spliterator.characteristics(), true);

   455             asserter.assertContents(dest, exp, isOrdered);

   456         }

   457     }

   458 

   459     private static <T, S extends Spliterator<T>>

   460     void splitSixDeepVisitor(int depth, int curLevel,

   461                              List<T> dest, S spliterator, UnaryOperator<Consumer<T>> boxingAdapter,

   462                              int rootCharacteristics, boolean useTryAdvance) {

   463         if (curLevel < depth) {

   464             long beforeSize = spliterator.getExactSizeIfKnown();

   465             Spliterator<T> split = spliterator.trySplit();

   466             if (split != null) {

   467                 assertSpliterator(split, rootCharacteristics);

   468                 assertSpliterator(spliterator, rootCharacteristics);

   469 

   470                 if ((rootCharacteristics & Spliterator.SUBSIZED) != 0 &&

   471                     (rootCharacteristics & Spliterator.SIZED) != 0) {

   472                     assertEquals(beforeSize, split.estimateSize() + spliterator.estimateSize());

   473                 }

   474                 splitSixDeepVisitor(depth, curLevel + 1, dest, split, boxingAdapter, rootCharacteristics, useTryAdvance);

   475             }

   476             splitSixDeepVisitor(depth, curLevel + 1, dest, spliterator, boxingAdapter, rootCharacteristics, useTryAdvance);

   477         }

   478         else {

   479             long sizeIfKnown = spliterator.getExactSizeIfKnown();

   480             if (useTryAdvance) {

   481                 Consumer<T> addToDest = boxingAdapter.apply(dest::add);

   482                 int count = 0;

   483                 while (spliterator.tryAdvance(addToDest)) {

   484                     ++count;

   485                 }

   486 

   487                 if (sizeIfKnown >= 0)

   488                     assertEquals(sizeIfKnown, count);

   489 

   490                 // Assert that forEach now produces no elements

   491                 spliterator.forEachRemaining(boxingAdapter.apply(

   492                         e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));

   493 

   494                 Spliterator<T> split = spliterator.trySplit();

   495                 assertNull(split);

   496             }

   497             else {

   498                 List<T> leafDest = new ArrayList<>();

   499                 Consumer<T> addToLeafDest = boxingAdapter.apply(leafDest::add);

   500                 spliterator.forEachRemaining(addToLeafDest);

   501 

   502                 if (sizeIfKnown >= 0)

   503                     assertEquals(sizeIfKnown, leafDest.size());

   504 

   505                 // Assert that forEach now produces no elements

   506                 spliterator.tryAdvance(boxingAdapter.apply(

   507                         e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e)));

   508 

   509                 Spliterator<T> split = spliterator.trySplit();

   510                 assertNull(split);

   511 

   512                 dest.addAll(leafDest);

   513             }

   514         }

   515     }

   516 

   517     private static <T, S extends Spliterator<T>> void testSplitUntilNull(

   518             Collection<T> exp,

   519             Supplier<S> supplier,

   520             UnaryOperator<Consumer<T>> boxingAdapter,

   521             ContentAsserter<T> asserter) {

   522         Spliterator<T> s = supplier.get();

   523         boolean isOrdered = s.hasCharacteristics(Spliterator.ORDERED);

   524         assertSpliterator(s);

   525 

   526         List<T> splits = new ArrayList<>();

   527         Consumer<T> c = boxingAdapter.apply(splits::add);

   528 

   529         testSplitUntilNull(new SplitNode<T>(c, s));

   530         asserter.assertContents(splits, exp, isOrdered);

   531     }

   532 

   533     private static class SplitNode<T> {

   534         // Constant for every node

   535         final Consumer<T> c;

   536         final int rootCharacteristics;

   537 

   538         final Spliterator<T> s;

   539 

   540         SplitNode(Consumer<T> c, Spliterator<T> s) {

   541             this(c, s.characteristics(), s);

   542         }

   543 

   544         private SplitNode(Consumer<T> c, int rootCharacteristics, Spliterator<T> s) {

   545             this.c = c;

   546             this.rootCharacteristics = rootCharacteristics;

   547             this.s = s;

   548         }

   549 

   550         SplitNode<T> fromSplit(Spliterator<T> split) {

   551             return new SplitNode<>(c, rootCharacteristics, split);

   552         }

   553     }

   554 

   555     /**

   556      * Set the maximum stack capacity to 0.25MB. This should be more than enough to detect a bad spliterator

   557      * while not unduly disrupting test infrastructure given the test data sizes that are used are small.

   558      * Note that j.u.c.ForkJoinPool sets the max queue size to 64M (1 << 26).

   559      */

   560     private static final int MAXIMUM_STACK_CAPACITY = 1 << 18; // 0.25MB

   561 

   562     private static <T> void testSplitUntilNull(SplitNode<T> e) {

   563         // Use an explicit stack to avoid a StackOverflowException when testing a Spliterator

   564         // that when repeatedly split produces a right-balanced (and maybe degenerate) tree, or

   565         // for a spliterator that is badly behaved.

   566         Deque<SplitNode<T>> stack = new ArrayDeque<>();

   567         stack.push(e);

   568 

   569         int iteration = 0;

   570         while (!stack.isEmpty()) {

   571             assertTrue(iteration++ < MAXIMUM_STACK_CAPACITY, "Exceeded maximum stack modification count of 1 << 18");

   572 

   573             e = stack.pop();

   574             Spliterator<T> parentAndRightSplit = e.s;

   575 

   576             long parentEstimateSize = parentAndRightSplit.estimateSize();

   577             assertTrue(parentEstimateSize >= 0,

   578                        String.format("Split size estimate %d < 0", parentEstimateSize));

   579 

   580             long parentSize = parentAndRightSplit.getExactSizeIfKnown();

   581             Spliterator<T> leftSplit = parentAndRightSplit.trySplit();

   582             if (leftSplit == null) {

   583                 parentAndRightSplit.forEachRemaining(e.c);

   584                 continue;

   585             }

   586 

   587             assertSpliterator(leftSplit, e.rootCharacteristics);

   588             assertSpliterator(parentAndRightSplit, e.rootCharacteristics);

   589 

   590             if (parentEstimateSize != Long.MAX_VALUE && leftSplit.estimateSize() > 0

   591                 && parentAndRightSplit.estimateSize() > 0) {

   592                 assertTrue(leftSplit.estimateSize() < parentEstimateSize,

   593                            String.format("Left split size estimate %d >= parent split size estimate %d",

   594                                          leftSplit.estimateSize(), parentEstimateSize));

   595                 assertTrue(parentAndRightSplit.estimateSize() < parentEstimateSize,

   596                            String.format("Right split size estimate %d >= parent split size estimate %d",

   597                                          leftSplit.estimateSize(), parentEstimateSize));

   598             }

   599             else {

   600                 assertTrue(leftSplit.estimateSize() <= parentEstimateSize,

   601                            String.format("Left split size estimate %d > parent split size estimate %d",

   602                                          leftSplit.estimateSize(), parentEstimateSize));

   603                 assertTrue(parentAndRightSplit.estimateSize() <= parentEstimateSize,

   604                            String.format("Right split size estimate %d > parent split size estimate %d",

   605                                          leftSplit.estimateSize(), parentEstimateSize));

   606             }

   607 

   608             long leftSize = leftSplit.getExactSizeIfKnown();

   609             long rightSize = parentAndRightSplit.getExactSizeIfKnown();

   610             if (parentSize >= 0 && leftSize >= 0 && rightSize >= 0)

   611                 assertEquals(parentSize, leftSize + rightSize,

   612                              String.format("exact left split size %d + exact right split size %d != parent exact split size %d",

   613                                            leftSize, rightSize, parentSize));

   614 

   615             // Add right side to stack first so left side is popped off first

   616             stack.push(e.fromSplit(parentAndRightSplit));

   617             stack.push(e.fromSplit(leftSplit));

   618         }

   619     }

   620 

   621     private static void assertSpliterator(Spliterator<?> s, int rootCharacteristics) {

   622         if ((rootCharacteristics & Spliterator.SUBSIZED) != 0) {

   623             assertTrue(s.hasCharacteristics(Spliterator.SUBSIZED),

   624                        "Child split is not SUBSIZED when root split is SUBSIZED");

   625         }

   626         assertSpliterator(s);

   627     }

   628 

   629     private static void assertSpliterator(Spliterator<?> s) {

   630         if (s.hasCharacteristics(Spliterator.SUBSIZED)) {

   631             assertTrue(s.hasCharacteristics(Spliterator.SIZED));

   632         }

   633         if (s.hasCharacteristics(Spliterator.SIZED)) {

   634             assertTrue(s.estimateSize() != Long.MAX_VALUE);

   635             assertTrue(s.getExactSizeIfKnown() >= 0);

   636         }

   637         try {

   638             s.getComparator();

   639             assertTrue(s.hasCharacteristics(Spliterator.SORTED));

   640         } catch (IllegalStateException e) {

   641             assertFalse(s.hasCharacteristics(Spliterator.SORTED));

   642         }

   643     }

   644 

   645     private static<T> void assertContents(Collection<T> actual, Collection<T> expected, boolean isOrdered) {

   646         if (isOrdered) {

   647             assertEquals(actual, expected);

   648         }

   649         else {

   650             LambdaTestHelpers.assertContentsUnordered(actual, expected);

   651         }

   652     }

   653 

   654     public static void assertThrowsNPE(ThrowingRunnable r) {

   655         assertThrows(NullPointerException.class, r);

   656     }

   657 

   658     public static<U> void mixedTraverseAndSplit(Consumer<U> b, Spliterator<U> splTop) {

   659         Spliterator<U> spl1, spl2, spl3;

   660         splTop.tryAdvance(b);

   661         spl2 = splTop.trySplit();

   662         if (spl2 != null) {

   663             spl2.tryAdvance(b);

   664             spl1 = spl2.trySplit();

   665             if (spl1 != null) {

   666                 spl1.tryAdvance(b);

   667                 spl1.forEachRemaining(b);

   668             }

   669             spl2.tryAdvance(b);

   670             spl2.forEachRemaining(b);

   671         }

   672         splTop.tryAdvance(b);

   673         spl3 = splTop.trySplit();

   674         if (spl3 != null) {

   675             spl3.tryAdvance(b);

   676             spl3.forEachRemaining(b);

   677         }

   678         splTop.tryAdvance(b);

   679         splTop.forEachRemaining(b);

   680     }

   681 

   682     public static void mixedTraverseAndSplit(IntConsumer b, Spliterator.OfInt splTop) {

   683         Spliterator.OfInt spl1, spl2, spl3;

   684         splTop.tryAdvance(b);

   685         spl2 = splTop.trySplit();

   686         if (spl2 != null) {

   687             spl2.tryAdvance(b);

   688             spl1 = spl2.trySplit();

   689             if (spl1 != null) {

   690                 spl1.tryAdvance(b);

   691                 spl1.forEachRemaining(b);

   692             }

   693             spl2.tryAdvance(b);

   694             spl2.forEachRemaining(b);

   695         }

   696         splTop.tryAdvance(b);

   697         spl3 = splTop.trySplit();

   698         if (spl3 != null) {

   699             spl3.tryAdvance(b);

   700             spl3.forEachRemaining(b);

   701         }

   702         splTop.tryAdvance(b);

   703         splTop.forEachRemaining(b);

   704     }

   705 

   706     public static void mixedTraverseAndSplit(LongConsumer b, Spliterator.OfLong splTop) {

   707         Spliterator.OfLong spl1, spl2, spl3;

   708         splTop.tryAdvance(b);

   709         spl2 = splTop.trySplit();

   710         if (spl2 != null) {

   711             spl2.tryAdvance(b);

   712             spl1 = spl2.trySplit();

   713             if (spl1 != null) {

   714                 spl1.tryAdvance(b);

   715                 spl1.forEachRemaining(b);

   716             }

   717             spl2.tryAdvance(b);

   718             spl2.forEachRemaining(b);

   719         }

   720         splTop.tryAdvance(b);

   721         spl3 = splTop.trySplit();

   722         if (spl3 != null) {

   723             spl3.tryAdvance(b);

   724             spl3.forEachRemaining(b);

   725         }

   726         splTop.tryAdvance(b);

   727         splTop.forEachRemaining(b);

   728     }

   729 

   730     public static void mixedTraverseAndSplit(DoubleConsumer b, Spliterator.OfDouble splTop) {

   731         Spliterator.OfDouble spl1, spl2, spl3;

   732         splTop.tryAdvance(b);

   733         spl2 = splTop.trySplit();

   734         if (spl2 != null) {

   735             spl2.tryAdvance(b);

   736             spl1 = spl2.trySplit();

   737             if (spl1 != null) {

   738                 spl1.tryAdvance(b);

   739                 spl1.forEachRemaining(b);

   740             }

   741             spl2.tryAdvance(b);

   742             spl2.forEachRemaining(b);

   743         }

   744         splTop.tryAdvance(b);

   745         spl3 = splTop.trySplit();

   746         if (spl3 != null) {

   747             spl3.tryAdvance(b);

   748             spl3.forEachRemaining(b);

   749         }

   750         splTop.tryAdvance(b);

   751         splTop.forEachRemaining(b);

   752     }

   753 

   754 }