1 /*

     2  * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.

     8  *

     9  * This code is distributed in the hope that it will be useful, but WITHOUT

    10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    12  * version 2 for more details (a copy is included in the LICENSE file that

    13  * accompanied this code).

    14  *

    15  * You should have received a copy of the GNU General Public License version

    16  * 2 along with this work; if not, write to the Free Software Foundation,

    17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    18  *

    19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    20  * or visit www.oracle.com if you need additional information or have any

    21  * questions.

    22  */

    23 

    24 /**

    25  * @test

    26  * @bug 8005698

    27  * @run testng SpliteratorCollisions

    28  * @summary Spliterator traversing and splitting hash maps containing colliding hashes

    29  * @author Brent Christian

    30  */

    31 

    32 import org.testng.annotations.DataProvider;

    33 import org.testng.annotations.Test;

    34 

    35 import java.util.ArrayDeque;

    36 import java.util.ArrayList;

    37 import java.util.Arrays;

    38 import java.util.Collection;

    39 import java.util.Collections;

    40 import java.util.Deque;

    41 import java.util.HashMap;

    42 import java.util.HashSet;

    43 import java.util.LinkedHashMap;

    44 import java.util.LinkedHashSet;

    45 import java.util.List;

    46 import java.util.Map;

    47 import java.util.Spliterator;

    48 import java.util.TreeSet;

    49 import java.util.function.Consumer;

    50 import java.util.function.Function;

    51 import java.util.function.LongConsumer;

    52 import java.util.function.Supplier;

    53 import java.util.function.UnaryOperator;

    54 

    55 import static org.testng.Assert.*;

    56 import static org.testng.Assert.assertEquals;

    57 

    58 @Test

    59 public class SpliteratorCollisions {

    60 

    61     private static List<Integer> SIZES = Arrays.asList(0, 1, 10, 100, 1000);

    62 

    63     private static class SpliteratorDataBuilder<T> {

    64         List<Object[]> data;

    65         List<T> exp;

    66         Map<T, T> mExp;

    67 

    68         SpliteratorDataBuilder(List<Object[]> data, List<T> exp) {

    69             this.data = data;

    70             this.exp = exp;

    71             this.mExp = createMap(exp);

    72         }

    73 

    74         Map<T, T> createMap(List<T> l) {

    75             Map<T, T> m = new LinkedHashMap<>();

    76             for (T t : l) {

    77                 m.put(t, t);

    78             }

    79             return m;

    80         }

    81 

    82         void add(String description, Collection<?> expected, Supplier<Spliterator<?>> s) {

    83             description = joiner(description).toString();

    84             data.add(new Object[]{description, expected, s});

    85         }

    86 

    87         void add(String description, Supplier<Spliterator<?>> s) {

    88             add(description, exp, s);

    89         }

    90 

    91         void addCollection(Function<Collection<T>, ? extends Collection<T>> c) {

    92             add("new " + c.apply(Collections.<T>emptyList()).getClass().getName() + ".spliterator()",

    93                 () -> c.apply(exp).spliterator());

    94         }

    95 

    96         void addList(Function<Collection<T>, ? extends List<T>> l) {

    97             // @@@ If collection is instance of List then add sub-list tests

    98             addCollection(l);

    99         }

   100 

   101         void addMap(Function<Map<T, T>, ? extends Map<T, T>> m) {

   102             String description = "new " + m.apply(Collections.<T, T>emptyMap()).getClass().getName();

   103             add(description + ".keySet().spliterator()", () -> m.apply(mExp).keySet().spliterator());

   104             add(description + ".values().spliterator()", () -> m.apply(mExp).values().spliterator());

   105             add(description + ".entrySet().spliterator()", mExp.entrySet(), () -> m.apply(mExp).entrySet().spliterator());

   106         }

   107 

   108         StringBuilder joiner(String description) {

   109             return new StringBuilder(description).

   110                     append(" {").

   111                     append("size=").append(exp.size()).

   112                     append("}");

   113         }

   114     }

   115 

   116     static Object[][] spliteratorDataProvider;

   117 

   118     @DataProvider(name = "HashableIntSpliterator")

   119     public static Object[][] spliteratorDataProvider() {

   120         if (spliteratorDataProvider != null) {

   121             return spliteratorDataProvider;

   122         }

   123 

   124         List<Object[]> data = new ArrayList<>();

   125         for (int size : SIZES) {

   126             List<HashableInteger> exp = listIntRange(size, false);

   127             SpliteratorDataBuilder<HashableInteger> db = new SpliteratorDataBuilder<>(data, exp);

   128 

   129             // Maps

   130             db.addMap(HashMap::new);

   131             db.addMap(LinkedHashMap::new);

   132 

   133             // Collections that use HashMap

   134             db.addCollection(HashSet::new);

   135             db.addCollection(LinkedHashSet::new);

   136             db.addCollection(TreeSet::new);

   137         }

   138         return spliteratorDataProvider = data.toArray(new Object[0][]);

   139     }

   140 

   141     static Object[][] spliteratorDataProviderWithNull;

   142 

   143     @DataProvider(name = "HashableIntSpliteratorWithNull")

   144     public static Object[][] spliteratorNullDataProvider() {

   145         if (spliteratorDataProviderWithNull != null) {

   146             return spliteratorDataProviderWithNull;

   147         }

   148 

   149         List<Object[]> data = new ArrayList<>();

   150         for (int size : SIZES) {

   151             List<HashableInteger> exp = listIntRange(size, true);

   152             exp.add(0, null);

   153             SpliteratorDataBuilder<HashableInteger> db = new SpliteratorDataBuilder<>(data, exp);

   154 

   155             // Maps

   156             db.addMap(HashMap::new);

   157             db.addMap(LinkedHashMap::new);

   158             // TODO: add this back in if we decide to keep TreeBin in WeakHashMap

   159             //db.addMap(WeakHashMap::new);

   160 

   161             // Collections that use HashMap

   162             db.addCollection(HashSet::new);

   163             db.addCollection(LinkedHashSet::new);

   164 //            db.addCollection(TreeSet::new);

   165 

   166         }

   167         return spliteratorDataProviderWithNull = data.toArray(new Object[0][]);

   168     }

   169 

   170     final static class HashableInteger implements Comparable<HashableInteger> {

   171 

   172         final int value;

   173         final int hashmask; //yes duplication

   174 

   175         HashableInteger(int value, int hashmask) {

   176             this.value = value;

   177             this.hashmask = hashmask;

   178         }

   179 

   180         @Override

   181         public boolean equals(Object obj) {

   182             if (obj instanceof HashableInteger) {

   183                 HashableInteger other = (HashableInteger) obj;

   184 

   185                 return other.value == value;

   186             }

   187 

   188             return false;

   189         }

   190 

   191         @Override

   192         public int hashCode() {

   193             return value % hashmask;

   194         }

   195 

   196         @Override

   197         public int compareTo(HashableInteger o) {

   198             return value - o.value;

   199         }

   200 

   201         @Override

   202         public String toString() {

   203             return Integer.toString(value);

   204         }

   205     }

   206 

   207     private static List<HashableInteger> listIntRange(int upTo, boolean withNull) {

   208         List<HashableInteger> exp = new ArrayList<>();

   209         if (withNull) {

   210             exp.add(null);

   211         }

   212         for (int i = 0; i < upTo; i++) {

   213             exp.add(new HashableInteger(i, 10));

   214         }

   215         return Collections.unmodifiableList(exp);

   216     }

   217 

   218     @Test(dataProvider = "HashableIntSpliterator")

   219     @SuppressWarnings({"unchecked", "rawtypes"})

   220     public void testNullPointerException(String description, Collection exp, Supplier<Spliterator> s) {

   221         executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining(null));

   222         executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance(null));

   223     }

   224 

   225     @Test(dataProvider = "HashableIntSpliteratorWithNull")

   226     @SuppressWarnings({"unchecked", "rawtypes"})

   227     public void testNullPointerExceptionWithNull(String description, Collection exp, Supplier<Spliterator> s) {

   228         executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining(null));

   229         executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance(null));

   230     }

   231 

   232 

   233     @Test(dataProvider = "HashableIntSpliterator")

   234     @SuppressWarnings({"unchecked", "rawtypes"})

   235     public void testForEach(String description, Collection exp, Supplier<Spliterator> s) {

   236         testForEach(exp, s, (Consumer<Object> b) -> b);

   237     }

   238 

   239     @Test(dataProvider = "HashableIntSpliteratorWithNull")

   240     @SuppressWarnings({"unchecked", "rawtypes"})

   241     public void testForEachWithNull(String description, Collection exp, Supplier<Spliterator> s) {

   242         testForEach(exp, s, (Consumer<Object> b) -> b);

   243     }

   244 

   245 

   246     @Test(dataProvider = "HashableIntSpliterator")

   247     @SuppressWarnings({"unchecked", "rawtypes"})

   248     public void testTryAdvance(String description, Collection exp, Supplier<Spliterator> s) {

   249         testTryAdvance(exp, s, (Consumer<Object> b) -> b);

   250     }

   251 

   252     @Test(dataProvider = "HashableIntSpliteratorWithNull")

   253     @SuppressWarnings({"unchecked", "rawtypes"})

   254     public void testTryAdvanceWithNull(String description, Collection exp, Supplier<Spliterator> s) {

   255         testTryAdvance(exp, s, (Consumer<Object> b) -> b);

   256     }

   257 

   258 /* skip this test until 8013649 is fixed

   259     @Test(dataProvider = "HashableIntSpliterator")

   260     @SuppressWarnings({"unchecked", "rawtypes"})

   261     public void testMixedTryAdvanceForEach(String description, Collection exp, Supplier<Spliterator> s) {

   262         testMixedTryAdvanceForEach(exp, s, (Consumer<Object> b) -> b);

   263     }

   264 

   265     @Test(dataProvider = "HashableIntSpliteratorWithNull")

   266     @SuppressWarnings({"unchecked", "rawtypes"})

   267     public void testMixedTryAdvanceForEachWithNull(String description, Collection exp, Supplier<Spliterator> s) {

   268         testMixedTryAdvanceForEach(exp, s, (Consumer<Object> b) -> b);

   269     }

   270 */

   271 

   272     @Test(dataProvider = "HashableIntSpliterator")

   273     @SuppressWarnings({"unchecked", "rawtypes"})

   274     public void testSplitAfterFullTraversal(String description, Collection exp, Supplier<Spliterator> s) {

   275         testSplitAfterFullTraversal(s, (Consumer<Object> b) -> b);

   276     }

   277 

   278     @Test(dataProvider = "HashableIntSpliteratorWithNull")

   279     @SuppressWarnings({"unchecked", "rawtypes"})

   280     public void testSplitAfterFullTraversalWithNull(String description, Collection exp, Supplier<Spliterator> s) {

   281         testSplitAfterFullTraversal(s, (Consumer<Object> b) -> b);

   282     }

   283 

   284 

   285     @Test(dataProvider = "HashableIntSpliterator")

   286     @SuppressWarnings({"unchecked", "rawtypes"})

   287     public void testSplitOnce(String description, Collection exp, Supplier<Spliterator> s) {

   288         testSplitOnce(exp, s, (Consumer<Object> b) -> b);

   289     }

   290 

   291     @Test(dataProvider = "HashableIntSpliteratorWithNull")

   292     @SuppressWarnings({"unchecked", "rawtypes"})

   293     public void testSplitOnceWithNull(String description, Collection exp, Supplier<Spliterator> s) {

   294         testSplitOnce(exp, s, (Consumer<Object> b) -> b);

   295     }

   296 

   297     @Test(dataProvider = "HashableIntSpliterator")

   298     @SuppressWarnings({"unchecked", "rawtypes"})

   299     public void testSplitSixDeep(String description, Collection exp, Supplier<Spliterator> s) {

   300         testSplitSixDeep(exp, s, (Consumer<Object> b) -> b);

   301     }

   302 

   303     @Test(dataProvider = "HashableIntSpliteratorWithNull")

   304     @SuppressWarnings({"unchecked", "rawtypes"})

   305     public void testSplitSixDeepWithNull(String description, Collection exp, Supplier<Spliterator> s) {

   306         testSplitSixDeep(exp, s, (Consumer<Object> b) -> b);

   307     }

   308 

   309     @Test(dataProvider = "HashableIntSpliterator")

   310     @SuppressWarnings({"unchecked", "rawtypes"})

   311     public void testSplitUntilNull(String description, Collection exp, Supplier<Spliterator> s) {

   312         testSplitUntilNull(exp, s, (Consumer<Object> b) -> b);

   313     }

   314 

   315     @Test(dataProvider = "HashableIntSpliteratorWithNull")

   316     @SuppressWarnings({"unchecked", "rawtypes"})

   317     public void testSplitUntilNullWithNull(String description, Collection exp, Supplier<Spliterator> s) {

   318         testSplitUntilNull(exp, s, (Consumer<Object> b) -> b);

   319     }

   320 

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

   322             Collection<T> exp,

   323             Supplier<S> supplier,

   324             UnaryOperator<Consumer<T>> boxingAdapter) {

   325         S spliterator = supplier.get();

   326         long sizeIfKnown = spliterator.getExactSizeIfKnown();

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

   328 

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

   330         spliterator = supplier.get();

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

   332         spliterator.forEachRemaining(addToFromForEach);

   333 

   334         // Assert that forEach now produces no elements

   335         spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));

   336         // Assert that tryAdvance now produce no elements

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

   338 

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

   340         if (sizeIfKnown >= 0) {

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

   342         }

   343         if (exp.contains(null)) {

   344             assertTrue(fromForEach.contains(null));

   345         }

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

   347 

   348         assertContents(fromForEach, exp, isOrdered);

   349     }

   350 

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

   352             Collection<T> exp,

   353             Supplier<S> supplier,

   354             UnaryOperator<Consumer<T>> boxingAdapter) {

   355         S spliterator = supplier.get();

   356         long sizeIfKnown = spliterator.getExactSizeIfKnown();

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

   358 

   359         spliterator = supplier.get();

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

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

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

   363 

   364         // Assert that forEach now produces no elements

   365         spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));

   366         // Assert that tryAdvance now produce no elements

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

   368 

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

   370         if (sizeIfKnown >= 0) {

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

   372         }

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

   374 

   375         assertContents(fromTryAdvance, exp, isOrdered);

   376     }

   377 

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

   379             Collection<T> exp,

   380             Supplier<S> supplier,

   381             UnaryOperator<Consumer<T>> boxingAdapter) {

   382         S spliterator = supplier.get();

   383         long sizeIfKnown = spliterator.getExactSizeIfKnown();

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

   385 

   386         // tryAdvance first few elements, then forEach rest

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

   388         spliterator = supplier.get();

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

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

   391         spliterator.forEachRemaining(addToDest);

   392 

   393         // Assert that forEach now produces no elements

   394         spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));

   395         // Assert that tryAdvance now produce no elements

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

   397 

   398         if (sizeIfKnown >= 0) {

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

   400         }

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

   402 

   403         if (isOrdered) {

   404             assertEquals(dest, exp);

   405         }

   406         else {

   407             assertContentsUnordered(dest, exp);

   408         }

   409     }

   410 

   411     private static <T, S extends Spliterator<T>> void testSplitAfterFullTraversal(

   412             Supplier<S> supplier,

   413             UnaryOperator<Consumer<T>> boxingAdapter) {

   414         // Full traversal using tryAdvance

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

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

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

   418         assertNull(split);

   419 

   420         // Full traversal using forEach

   421         spliterator = supplier.get();

   422         spliterator.forEachRemaining(boxingAdapter.apply(e -> {

   423         }));

   424         split = spliterator.trySplit();

   425         assertNull(split);

   426 

   427         // Full traversal using tryAdvance then forEach

   428         spliterator = supplier.get();

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

   430         spliterator.forEachRemaining(boxingAdapter.apply(e -> {

   431         }));

   432         split = spliterator.trySplit();

   433         assertNull(split);

   434     }

   435 

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

   437             Collection<T> exp,

   438             Supplier<S> supplier,

   439             UnaryOperator<Consumer<T>> boxingAdapter) {

   440         S spliterator = supplier.get();

   441         long sizeIfKnown = spliterator.getExactSizeIfKnown();

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

   443 

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

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

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

   447         long s1Size = s1.getExactSizeIfKnown();

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

   449 

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

   451         if (s2 != null)

   452             s2.forEachRemaining(addToFromSplit);

   453         s1.forEachRemaining(addToFromSplit);

   454 

   455         if (sizeIfKnown >= 0) {

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

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

   458                 assertEquals(sizeIfKnown, s1Size + s2Size);

   459         }

   460         assertContents(fromSplit, exp, isOrdered);

   461     }

   462 

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

   464             Collection<T> exp,

   465             Supplier<S> supplier,

   466             UnaryOperator<Consumer<T>> boxingAdapter) {

   467         S spliterator = supplier.get();

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

   469 

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

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

   472             spliterator = supplier.get();

   473 

   474             assertSpliterator(spliterator);

   475 

   476             // verify splitting with forEach

   477             visit(depth, 0, dest, spliterator, boxingAdapter, spliterator.characteristics(), false);

   478             assertContents(dest, exp, isOrdered);

   479 

   480             // verify splitting with tryAdvance

   481             dest.clear();

   482             spliterator = supplier.get();

   483             visit(depth, 0, dest, spliterator, boxingAdapter, spliterator.characteristics(), true);

   484             assertContents(dest, exp, isOrdered);

   485         }

   486     }

   487 

   488     private static <T, S extends Spliterator<T>> void visit(int depth, int curLevel,

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

   490                                                             int rootCharacteristics, boolean useTryAdvance) {

   491         if (curLevel < depth) {

   492             long beforeSize = spliterator.getExactSizeIfKnown();

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

   494             if (split != null) {

   495                 assertSpliterator(split, rootCharacteristics);

   496                 assertSpliterator(spliterator, rootCharacteristics);

   497 

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

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

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

   501                 }

   502                 visit(depth, curLevel + 1, dest, split, boxingAdapter, rootCharacteristics, useTryAdvance);

   503             }

   504             visit(depth, curLevel + 1, dest, spliterator, boxingAdapter, rootCharacteristics, useTryAdvance);

   505         }

   506         else {

   507             long sizeIfKnown = spliterator.getExactSizeIfKnown();

   508             if (useTryAdvance) {

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

   510                 int count = 0;

   511                 while (spliterator.tryAdvance(addToDest)) {

   512                     ++count;

   513                 }

   514 

   515                 if (sizeIfKnown >= 0)

   516                     assertEquals(sizeIfKnown, count);

   517 

   518                 // Assert that forEach now produces no elements

   519                 spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e)));

   520 

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

   522                 assertNull(split);

   523             }

   524             else {

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

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

   527                 spliterator.forEachRemaining(addToLeafDest);

   528 

   529                 if (sizeIfKnown >= 0)

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

   531 

   532                 // Assert that forEach now produces no elements

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

   534 

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

   536                 assertNull(split);

   537 

   538                 dest.addAll(leafDest);

   539             }

   540         }

   541     }

   542 

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

   544             Collection<T> exp,

   545             Supplier<S> supplier,

   546             UnaryOperator<Consumer<T>> boxingAdapter) {

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

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

   549         assertSpliterator(s);

   550 

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

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

   553 

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

   555         assertContents(splits, exp, isOrdered);

   556     }

   557 

   558     private static class SplitNode<T> {

   559         // Constant for every node

   560         final Consumer<T> c;

   561         final int rootCharacteristics;

   562 

   563         final Spliterator<T> s;

   564 

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

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

   567         }

   568 

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

   570             this.c = c;

   571             this.rootCharacteristics = rootCharacteristics;

   572             this.s = s;

   573         }

   574 

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

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

   577         }

   578     }

   579 

   580     /**

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

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

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

   584      */

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

   586 

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

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

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

   590         // for a spliterator that is badly behaved.

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

   592         stack.push(e);

   593 

   594         int iteration = 0;

   595         while (!stack.isEmpty()) {

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

   597 

   598             e = stack.pop();

   599             Spliterator<T> parentAndRightSplit = e.s;

   600 

   601             long parentEstimateSize = parentAndRightSplit.estimateSize();

   602             assertTrue(parentEstimateSize >= 0,

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

   604 

   605             long parentSize = parentAndRightSplit.getExactSizeIfKnown();

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

   607             if (leftSplit == null) {

   608                 parentAndRightSplit.forEachRemaining(e.c);

   609                 continue;

   610             }

   611 

   612             assertSpliterator(leftSplit, e.rootCharacteristics);

   613             assertSpliterator(parentAndRightSplit, e.rootCharacteristics);

   614 

   615             if (parentEstimateSize != Long.MAX_VALUE && leftSplit.estimateSize() > 0 && parentAndRightSplit.estimateSize() > 0) {

   616                 assertTrue(leftSplit.estimateSize() < parentEstimateSize,

   617                            String.format("Left split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));

   618                 assertTrue(parentAndRightSplit.estimateSize() < parentEstimateSize,

   619                            String.format("Right split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));

   620             }

   621             else {

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

   623                            String.format("Left split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));

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

   625                            String.format("Right split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));

   626             }

   627 

   628             long leftSize = leftSplit.getExactSizeIfKnown();

   629             long rightSize = parentAndRightSplit.getExactSizeIfKnown();

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

   631                 assertEquals(parentSize, leftSize + rightSize,

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

   633                                            leftSize, rightSize, parentSize));

   634 

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

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

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

   638         }

   639     }

   640 

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

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

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

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

   645         }

   646         assertSpliterator(s);

   647     }

   648 

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

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

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

   652         }

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

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

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

   656         }

   657         try {

   658             s.getComparator();

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

   660         } catch (IllegalStateException e) {

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

   662         }

   663     }

   664 

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

   666         if (isOrdered) {

   667             assertEquals(actual, expected);

   668         }

   669         else {

   670             assertContentsUnordered(actual, expected);

   671         }

   672     }

   673 

   674     private static<T> void assertContentsUnordered(Iterable<T> actual, Iterable<T> expected) {

   675         assertEquals(toBoxedMultiset(actual), toBoxedMultiset(expected));

   676     }

   677 

   678     private static <T> Map<T, HashableInteger> toBoxedMultiset(Iterable<T> c) {

   679         Map<T, HashableInteger> result = new HashMap<>();

   680         c.forEach((Consumer) e -> {

   681             if (result.containsKey((T)e)) {

   682                 result.put((T)e, new HashableInteger(((HashableInteger)result.get(e)).value + 1, 10));

   683             } else {

   684                 result.put((T)e, new HashableInteger(1, 10));

   685             }

   686         });

   687         return result;

   688     }

   689 

   690     private void executeAndCatch(Class<? extends Exception> expected, Runnable r) {

   691         Exception caught = null;

   692         try {

   693             r.run();

   694         }

   695         catch (Exception e) {

   696             caught = e;

   697         }

   698 

   699         assertNotNull(caught,

   700                       String.format("No Exception was thrown, expected an Exception of %s to be thrown",

   701                                     expected.getName()));

   702         assertTrue(expected.isInstance(caught),

   703                    String.format("Exception thrown %s not an instance of %s",

   704                                  caught.getClass().getName(), expected.getName()));

   705     }

   706 

   707 }