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 }