1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.
   7  *
   8  * This code is distributed in the hope that it will be useful, but WITHOUT
   9  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  10  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  11  * version 2 for more details (a copy is included in the LICENSE file that
  12  * accompanied this code).
  13  *
  14  * You should have received a copy of the GNU General Public License version
  15  * 2 along with this work; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  17  *
  18  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  19  * or visit www.oracle.com if you need additional information or have any
  20  * questions.
  21  */
  22 
  23 /*
  24  * This file is available under and governed by the GNU General Public
  25  * License version 2 only, as published by the Free Software Foundation.
  26  * However, the following notice accompanied the original version of this
  27  * file:
  28  *
  29  * Written by Doug Lea and Martin Buchholz with assistance from
  30  * members of JCP JSR-166 Expert Group and released to the public
  31  * domain, as explained at
  32  * http://creativecommons.org/publicdomain/zero/1.0/
  33  * Other contributors include Andrew Wright, Jeffrey Hayes,
  34  * Pat Fisher, Mike Judd.
  35  */
  36 
  37 /*
  38  * @test
  39  * @summary JSR-166 tck tests, in a number of variations.
  40  *          The first is the conformance testing variant,
  41  *          while others also test implementation details.
  42  * @build *
  43  * @modules java.management
  44  * @run junit/othervm/timeout=1000 JSR166TestCase
  45  * @run junit/othervm/timeout=1000
  46  *      --add-opens java.base/java.util.concurrent=ALL-UNNAMED
  47  *      --add-opens java.base/java.lang=ALL-UNNAMED
  48  *      -Djsr166.testImplementationDetails=true
  49  *      JSR166TestCase
  50  * @run junit/othervm/timeout=1000
  51  *      --add-opens java.base/java.util.concurrent=ALL-UNNAMED
  52  *      --add-opens java.base/java.lang=ALL-UNNAMED
  53  *      -Djsr166.testImplementationDetails=true
  54  *      -Djava.util.concurrent.ForkJoinPool.common.parallelism=0
  55  *      JSR166TestCase
  56  * @run junit/othervm/timeout=1000
  57  *      --add-opens java.base/java.util.concurrent=ALL-UNNAMED
  58  *      --add-opens java.base/java.lang=ALL-UNNAMED
  59  *      -Djsr166.testImplementationDetails=true
  60  *      -Djava.util.concurrent.ForkJoinPool.common.parallelism=1
  61  *      -Djava.util.secureRandomSeed=true
  62  *      JSR166TestCase
  63  * @run junit/othervm/timeout=1000/policy=tck.policy
  64  *      --add-opens java.base/java.util.concurrent=ALL-UNNAMED
  65  *      --add-opens java.base/java.lang=ALL-UNNAMED
  66  *      -Djsr166.testImplementationDetails=true
  67  *      JSR166TestCase
  68  */
  69 
  70 import static java.util.concurrent.TimeUnit.MILLISECONDS;
  71 import static java.util.concurrent.TimeUnit.MINUTES;
  72 import static java.util.concurrent.TimeUnit.NANOSECONDS;
  73 
  74 import java.io.ByteArrayInputStream;
  75 import java.io.ByteArrayOutputStream;
  76 import java.io.ObjectInputStream;
  77 import java.io.ObjectOutputStream;
  78 import java.lang.management.ManagementFactory;
  79 import java.lang.management.LockInfo;
  80 import java.lang.management.ThreadInfo;
  81 import java.lang.management.ThreadMXBean;
  82 import java.lang.reflect.Constructor;
  83 import java.lang.reflect.Method;
  84 import java.lang.reflect.Modifier;
  85 import java.security.CodeSource;
  86 import java.security.Permission;
  87 import java.security.PermissionCollection;
  88 import java.security.Permissions;
  89 import java.security.Policy;
  90 import java.security.ProtectionDomain;
  91 import java.security.SecurityPermission;
  92 import java.util.ArrayList;
  93 import java.util.Arrays;
  94 import java.util.Collection;
  95 import java.util.Collections;
  96 import java.util.Date;
  97 import java.util.Deque;
  98 import java.util.Enumeration;
  99 import java.util.HashSet;
 100 import java.util.Iterator;
 101 import java.util.List;
 102 import java.util.NoSuchElementException;
 103 import java.util.PropertyPermission;
 104 import java.util.Set;
 105 import java.util.concurrent.BlockingQueue;
 106 import java.util.concurrent.Callable;
 107 import java.util.concurrent.CountDownLatch;
 108 import java.util.concurrent.CyclicBarrier;
 109 import java.util.concurrent.ExecutionException;
 110 import java.util.concurrent.Executor;
 111 import java.util.concurrent.Executors;
 112 import java.util.concurrent.ExecutorService;
 113 import java.util.concurrent.ForkJoinPool;
 114 import java.util.concurrent.Future;
 115 import java.util.concurrent.FutureTask;
 116 import java.util.concurrent.RecursiveAction;
 117 import java.util.concurrent.RecursiveTask;
 118 import java.util.concurrent.RejectedExecutionException;
 119 import java.util.concurrent.RejectedExecutionHandler;
 120 import java.util.concurrent.Semaphore;
 121 import java.util.concurrent.ScheduledExecutorService;
 122 import java.util.concurrent.ScheduledFuture;
 123 import java.util.concurrent.SynchronousQueue;
 124 import java.util.concurrent.ThreadFactory;
 125 import java.util.concurrent.ThreadLocalRandom;
 126 import java.util.concurrent.ThreadPoolExecutor;
 127 import java.util.concurrent.TimeUnit;
 128 import java.util.concurrent.TimeoutException;
 129 import java.util.concurrent.atomic.AtomicBoolean;
 130 import java.util.concurrent.atomic.AtomicReference;
 131 import java.util.regex.Pattern;
 132 
 133 import junit.framework.Test;
 134 import junit.framework.TestCase;
 135 import junit.framework.TestResult;
 136 import junit.framework.TestSuite;
 137 
 138 /**
 139  * Base class for JSR166 Junit TCK tests.  Defines some constants,
 140  * utility methods and classes, as well as a simple framework for
 141  * helping to make sure that assertions failing in generated threads
 142  * cause the associated test that generated them to itself fail (which
 143  * JUnit does not otherwise arrange).  The rules for creating such
 144  * tests are:
 145  *
 146  * <ol>
 147  *
 148  * <li>All code not running in the main test thread (manually spawned threads
 149  * or the common fork join pool) must be checked for failure (and completion!).
 150  * Mechanisms that can be used to ensure this are:
 151  *   <ol>
 152  *   <li>Signalling via a synchronizer like AtomicInteger or CountDownLatch
 153  *    that the task completed normally, which is checked before returning from
 154  *    the test method in the main thread.
 155  *   <li>Using the forms {@link #threadFail}, {@link #threadAssertTrue},
 156  *    or {@link #threadAssertNull}, (not {@code fail}, {@code assertTrue}, etc.)
 157  *    Only the most typically used JUnit assertion methods are defined
 158  *    this way, but enough to live with.
 159  *   <li>Recording failure explicitly using {@link #threadUnexpectedException}
 160  *    or {@link #threadRecordFailure}.
 161  *   <li>Using a wrapper like CheckedRunnable that uses one the mechanisms above.
 162  *   </ol>
 163  *
 164  * <li>If you override {@link #setUp} or {@link #tearDown}, make sure
 165  * to invoke {@code super.setUp} and {@code super.tearDown} within
 166  * them. These methods are used to clear and check for thread
 167  * assertion failures.
 168  *
 169  * <li>All delays and timeouts must use one of the constants {@code
 170  * SHORT_DELAY_MS}, {@code SMALL_DELAY_MS}, {@code MEDIUM_DELAY_MS},
 171  * {@code LONG_DELAY_MS}. The idea here is that a SHORT is always
 172  * discriminable from zero time, and always allows enough time for the
 173  * small amounts of computation (creating a thread, calling a few
 174  * methods, etc) needed to reach a timeout point. Similarly, a SMALL
 175  * is always discriminable as larger than SHORT and smaller than
 176  * MEDIUM.  And so on. These constants are set to conservative values,
 177  * but even so, if there is ever any doubt, they can all be increased
 178  * in one spot to rerun tests on slower platforms.
 179  *
 180  * <li>All threads generated must be joined inside each test case
 181  * method (or {@code fail} to do so) before returning from the
 182  * method. The {@code joinPool} method can be used to do this when
 183  * using Executors.
 184  *
 185  * </ol>
 186  *
 187  * <p><b>Other notes</b>
 188  * <ul>
 189  *
 190  * <li>Usually, there is one testcase method per JSR166 method
 191  * covering "normal" operation, and then as many exception-testing
 192  * methods as there are exceptions the method can throw. Sometimes
 193  * there are multiple tests per JSR166 method when the different
 194  * "normal" behaviors differ significantly. And sometimes testcases
 195  * cover multiple methods when they cannot be tested in isolation.
 196  *
 197  * <li>The documentation style for testcases is to provide as javadoc
 198  * a simple sentence or two describing the property that the testcase
 199  * method purports to test. The javadocs do not say anything about how
 200  * the property is tested. To find out, read the code.
 201  *
 202  * <li>These tests are "conformance tests", and do not attempt to
 203  * test throughput, latency, scalability or other performance factors
 204  * (see the separate "jtreg" tests for a set intended to check these
 205  * for the most central aspects of functionality.) So, most tests use
 206  * the smallest sensible numbers of threads, collection sizes, etc
 207  * needed to check basic conformance.
 208  *
 209  * <li>The test classes currently do not declare inclusion in
 210  * any particular package to simplify things for people integrating
 211  * them in TCK test suites.
 212  *
 213  * <li>As a convenience, the {@code main} of this class (JSR166TestCase)
 214  * runs all JSR166 unit tests.
 215  *
 216  * </ul>
 217  */
 218 public class JSR166TestCase extends TestCase {
 219     private static final boolean useSecurityManager =
 220         Boolean.getBoolean("jsr166.useSecurityManager");
 221 
 222     protected static final boolean expensiveTests =
 223         Boolean.getBoolean("jsr166.expensiveTests");
 224 
 225     /**
 226      * If true, also run tests that are not part of the official tck
 227      * because they test unspecified implementation details.
 228      */
 229     protected static final boolean testImplementationDetails =
 230         Boolean.getBoolean("jsr166.testImplementationDetails");
 231 
 232     /**
 233      * If true, report on stdout all "slow" tests, that is, ones that
 234      * take more than profileThreshold milliseconds to execute.
 235      */
 236     private static final boolean profileTests =
 237         Boolean.getBoolean("jsr166.profileTests");
 238 
 239     /**
 240      * The number of milliseconds that tests are permitted for
 241      * execution without being reported, when profileTests is set.
 242      */
 243     private static final long profileThreshold =
 244         Long.getLong("jsr166.profileThreshold", 100);
 245 
 246     /**
 247      * The number of repetitions per test (for tickling rare bugs).
 248      */
 249     private static final int runsPerTest =
 250         Integer.getInteger("jsr166.runsPerTest", 1);
 251 
 252     /**
 253      * The number of repetitions of the test suite (for finding leaks?).
 254      */
 255     private static final int suiteRuns =
 256         Integer.getInteger("jsr166.suiteRuns", 1);
 257 
 258     /**
 259      * Returns the value of the system property, or NaN if not defined.
 260      */
 261     private static float systemPropertyValue(String name) {
 262         String floatString = System.getProperty(name);
 263         if (floatString == null)
 264             return Float.NaN;
 265         try {
 266             return Float.parseFloat(floatString);
 267         } catch (NumberFormatException ex) {
 268             throw new IllegalArgumentException(
 269                 String.format("Bad float value in system property %s=%s",
 270                               name, floatString));
 271         }
 272     }
 273 
 274     private static final ThreadMXBean THREAD_MXBEAN
 275         = ManagementFactory.getThreadMXBean();
 276 
 277     /**
 278      * The scaling factor to apply to standard delays used in tests.
 279      * May be initialized from any of:
 280      * - the "jsr166.delay.factor" system property
 281      * - the "test.timeout.factor" system property (as used by jtreg)
 282      *   See: http://openjdk.java.net/jtreg/tag-spec.html
 283      * - hard-coded fuzz factor when using a known slowpoke VM
 284      */
 285     private static final float delayFactor = delayFactor();
 286 
 287     private static float delayFactor() {
 288         float x;
 289         if (!Float.isNaN(x = systemPropertyValue("jsr166.delay.factor")))
 290             return x;
 291         if (!Float.isNaN(x = systemPropertyValue("test.timeout.factor")))
 292             return x;
 293         String prop = System.getProperty("java.vm.version");
 294         if (prop != null && prop.matches(".*debug.*"))
 295             return 4.0f; // How much slower is fastdebug than product?!
 296         return 1.0f;
 297     }
 298 
 299     public JSR166TestCase() { super(); }
 300     public JSR166TestCase(String name) { super(name); }
 301 
 302     /**
 303      * A filter for tests to run, matching strings of the form
 304      * methodName(className), e.g. "testInvokeAll5(ForkJoinPoolTest)"
 305      * Usefully combined with jsr166.runsPerTest.
 306      */
 307     private static final Pattern methodFilter = methodFilter();
 308 
 309     private static Pattern methodFilter() {
 310         String regex = System.getProperty("jsr166.methodFilter");
 311         return (regex == null) ? null : Pattern.compile(regex);
 312     }
 313 
 314     // Instrumentation to debug very rare, but very annoying hung test runs.
 315     static volatile TestCase currentTestCase;
 316     // static volatile int currentRun = 0;
 317     static {
 318         Runnable wedgedTestDetector = new Runnable() { public void run() {
 319             // Avoid spurious reports with enormous runsPerTest.
 320             // A single test case run should never take more than 1 second.
 321             // But let's cap it at the high end too ...
 322             final int timeoutMinutesMin = Math.max(runsPerTest / 60, 1)
 323                 * Math.max((int) delayFactor, 1);
 324             final int timeoutMinutes = Math.min(15, timeoutMinutesMin);
 325             for (TestCase lastTestCase = currentTestCase;;) {
 326                 try { MINUTES.sleep(timeoutMinutes); }
 327                 catch (InterruptedException unexpected) { break; }
 328                 if (lastTestCase == currentTestCase) {
 329                     System.err.printf(
 330                         "Looks like we're stuck running test: %s%n",
 331                         lastTestCase);
 332 //                     System.err.printf(
 333 //                         "Looks like we're stuck running test: %s (%d/%d)%n",
 334 //                         lastTestCase, currentRun, runsPerTest);
 335 //                     System.err.println("availableProcessors=" +
 336 //                         Runtime.getRuntime().availableProcessors());
 337 //                     System.err.printf("cpu model = %s%n", cpuModel());
 338                     dumpTestThreads();
 339                     // one stack dump is probably enough; more would be spam
 340                     break;
 341                 }
 342                 lastTestCase = currentTestCase;
 343             }}};
 344         Thread thread = new Thread(wedgedTestDetector, "WedgedTestDetector");
 345         thread.setDaemon(true);
 346         thread.start();
 347     }
 348 
 349 //     public static String cpuModel() {
 350 //         try {
 351 //             java.util.regex.Matcher matcher
 352 //               = Pattern.compile("model name\\s*: (.*)")
 353 //                 .matcher(new String(
 354 //                     java.nio.file.Files.readAllBytes(
 355 //                         java.nio.file.Paths.get("/proc/cpuinfo")), "UTF-8"));
 356 //             matcher.find();
 357 //             return matcher.group(1);
 358 //         } catch (Exception ex) { return null; }
 359 //     }
 360 
 361     public void runBare() throws Throwable {
 362         currentTestCase = this;
 363         if (methodFilter == null
 364             || methodFilter.matcher(toString()).find())
 365             super.runBare();
 366     }
 367 
 368     protected void runTest() throws Throwable {
 369         for (int i = 0; i < runsPerTest; i++) {
 370             // currentRun = i;
 371             if (profileTests)
 372                 runTestProfiled();
 373             else
 374                 super.runTest();
 375         }
 376     }
 377 
 378     protected void runTestProfiled() throws Throwable {
 379         for (int i = 0; i < 2; i++) {
 380             long startTime = System.nanoTime();
 381             super.runTest();
 382             long elapsedMillis = millisElapsedSince(startTime);
 383             if (elapsedMillis < profileThreshold)
 384                 break;
 385             // Never report first run of any test; treat it as a
 386             // warmup run, notably to trigger all needed classloading,
 387             if (i > 0)
 388                 System.out.printf("%s: %d%n", toString(), elapsedMillis);
 389         }
 390     }
 391 
 392     /**
 393      * Runs all JSR166 unit tests using junit.textui.TestRunner.
 394      */
 395     public static void main(String[] args) {
 396         main(suite(), args);
 397     }
 398 
 399     static class PithyResultPrinter extends junit.textui.ResultPrinter {
 400         PithyResultPrinter(java.io.PrintStream writer) { super(writer); }
 401         long runTime;
 402         public void startTest(Test test) {}
 403         protected void printHeader(long runTime) {
 404             this.runTime = runTime; // defer printing for later
 405         }
 406         protected void printFooter(TestResult result) {
 407             if (result.wasSuccessful()) {
 408                 getWriter().println("OK (" + result.runCount() + " tests)"
 409                     + "  Time: " + elapsedTimeAsString(runTime));
 410             } else {
 411                 getWriter().println("Time: " + elapsedTimeAsString(runTime));
 412                 super.printFooter(result);
 413             }
 414         }
 415     }
 416 
 417     /**
 418      * Returns a TestRunner that doesn't bother with unnecessary
 419      * fluff, like printing a "." for each test case.
 420      */
 421     static junit.textui.TestRunner newPithyTestRunner() {
 422         junit.textui.TestRunner runner = new junit.textui.TestRunner();
 423         runner.setPrinter(new PithyResultPrinter(System.out));
 424         return runner;
 425     }
 426 
 427     /**
 428      * Runs all unit tests in the given test suite.
 429      * Actual behavior influenced by jsr166.* system properties.
 430      */
 431     static void main(Test suite, String[] args) {
 432         if (useSecurityManager) {
 433             System.err.println("Setting a permissive security manager");
 434             Policy.setPolicy(permissivePolicy());
 435             System.setSecurityManager(new SecurityManager());
 436         }
 437         for (int i = 0; i < suiteRuns; i++) {
 438             TestResult result = newPithyTestRunner().doRun(suite);
 439             if (!result.wasSuccessful())
 440                 System.exit(1);
 441             System.gc();
 442             System.runFinalization();
 443         }
 444     }
 445 
 446     public static TestSuite newTestSuite(Object... suiteOrClasses) {
 447         TestSuite suite = new TestSuite();
 448         for (Object suiteOrClass : suiteOrClasses) {
 449             if (suiteOrClass instanceof TestSuite)
 450                 suite.addTest((TestSuite) suiteOrClass);
 451             else if (suiteOrClass instanceof Class)
 452                 suite.addTest(new TestSuite((Class<?>) suiteOrClass));
 453             else
 454                 throw new ClassCastException("not a test suite or class");
 455         }
 456         return suite;
 457     }
 458 
 459     public static void addNamedTestClasses(TestSuite suite,
 460                                            String... testClassNames) {
 461         for (String testClassName : testClassNames) {
 462             try {
 463                 Class<?> testClass = Class.forName(testClassName);
 464                 Method m = testClass.getDeclaredMethod("suite");
 465                 suite.addTest(newTestSuite((Test)m.invoke(null)));
 466             } catch (ReflectiveOperationException e) {
 467                 throw new AssertionError("Missing test class", e);
 468             }
 469         }
 470     }
 471 
 472     public static final double JAVA_CLASS_VERSION;
 473     public static final String JAVA_SPECIFICATION_VERSION;
 474     static {
 475         try {
 476             JAVA_CLASS_VERSION = java.security.AccessController.doPrivileged(
 477                 new java.security.PrivilegedAction<Double>() {
 478                 public Double run() {
 479                     return Double.valueOf(System.getProperty("java.class.version"));}});
 480             JAVA_SPECIFICATION_VERSION = java.security.AccessController.doPrivileged(
 481                 new java.security.PrivilegedAction<String>() {
 482                 public String run() {
 483                     return System.getProperty("java.specification.version");}});
 484         } catch (Throwable t) {
 485             throw new Error(t);
 486         }
 487     }
 488 
 489     public static boolean atLeastJava6()  { return JAVA_CLASS_VERSION >= 50.0; }
 490     public static boolean atLeastJava7()  { return JAVA_CLASS_VERSION >= 51.0; }
 491     public static boolean atLeastJava8()  { return JAVA_CLASS_VERSION >= 52.0; }
 492     public static boolean atLeastJava9()  { return JAVA_CLASS_VERSION >= 53.0; }
 493     public static boolean atLeastJava10() { return JAVA_CLASS_VERSION >= 54.0; }
 494     public static boolean atLeastJava11() { return JAVA_CLASS_VERSION >= 55.0; }
 495     public static boolean atLeastJava12() { return JAVA_CLASS_VERSION >= 56.0; }
 496     public static boolean atLeastJava13() { return JAVA_CLASS_VERSION >= 57.0; }
 497     public static boolean atLeastJava14() { return JAVA_CLASS_VERSION >= 58.0; }
 498     public static boolean atLeastJava15() { return JAVA_CLASS_VERSION >= 59.0; }
 499     public static boolean atLeastJava16() { return JAVA_CLASS_VERSION >= 60.0; }
 500     public static boolean atLeastJava17() { return JAVA_CLASS_VERSION >= 61.0; }
 501 
 502     /**
 503      * Collects all JSR166 unit tests as one suite.
 504      */
 505     public static Test suite() {
 506         // Java7+ test classes
 507         TestSuite suite = newTestSuite(
 508             ForkJoinPoolTest.suite(),
 509             ForkJoinTaskTest.suite(),
 510             RecursiveActionTest.suite(),
 511             RecursiveTaskTest.suite(),
 512             LinkedTransferQueueTest.suite(),
 513             PhaserTest.suite(),
 514             ThreadLocalRandomTest.suite(),
 515             AbstractExecutorServiceTest.suite(),
 516             AbstractQueueTest.suite(),
 517             AbstractQueuedSynchronizerTest.suite(),
 518             AbstractQueuedLongSynchronizerTest.suite(),
 519             ArrayBlockingQueueTest.suite(),
 520             ArrayDequeTest.suite(),
 521             ArrayListTest.suite(),
 522             AtomicBooleanTest.suite(),
 523             AtomicIntegerArrayTest.suite(),
 524             AtomicIntegerFieldUpdaterTest.suite(),
 525             AtomicIntegerTest.suite(),
 526             AtomicLongArrayTest.suite(),
 527             AtomicLongFieldUpdaterTest.suite(),
 528             AtomicLongTest.suite(),
 529             AtomicMarkableReferenceTest.suite(),
 530             AtomicReferenceArrayTest.suite(),
 531             AtomicReferenceFieldUpdaterTest.suite(),
 532             AtomicReferenceTest.suite(),
 533             AtomicStampedReferenceTest.suite(),
 534             ConcurrentHashMapTest.suite(),
 535             ConcurrentLinkedDequeTest.suite(),
 536             ConcurrentLinkedQueueTest.suite(),
 537             ConcurrentSkipListMapTest.suite(),
 538             ConcurrentSkipListSubMapTest.suite(),
 539             ConcurrentSkipListSetTest.suite(),
 540             ConcurrentSkipListSubSetTest.suite(),
 541             CopyOnWriteArrayListTest.suite(),
 542             CopyOnWriteArraySetTest.suite(),
 543             CountDownLatchTest.suite(),
 544             CountedCompleterTest.suite(),
 545             CyclicBarrierTest.suite(),
 546             DelayQueueTest.suite(),
 547             EntryTest.suite(),
 548             ExchangerTest.suite(),
 549             ExecutorsTest.suite(),
 550             ExecutorCompletionServiceTest.suite(),
 551             FutureTaskTest.suite(),
 552             HashtableTest.suite(),
 553             LinkedBlockingDequeTest.suite(),
 554             LinkedBlockingQueueTest.suite(),
 555             LinkedListTest.suite(),
 556             LockSupportTest.suite(),
 557             PriorityBlockingQueueTest.suite(),
 558             PriorityQueueTest.suite(),
 559             ReentrantLockTest.suite(),
 560             ReentrantReadWriteLockTest.suite(),
 561             ScheduledExecutorTest.suite(),
 562             ScheduledExecutorSubclassTest.suite(),
 563             SemaphoreTest.suite(),
 564             SynchronousQueueTest.suite(),
 565             SystemTest.suite(),
 566             ThreadLocalTest.suite(),
 567             ThreadPoolExecutorTest.suite(),
 568             ThreadPoolExecutorSubclassTest.suite(),
 569             ThreadTest.suite(),
 570             TimeUnitTest.suite(),
 571             TreeMapTest.suite(),
 572             TreeSetTest.suite(),
 573             TreeSubMapTest.suite(),
 574             TreeSubSetTest.suite(),
 575             VectorTest.suite());
 576 
 577         // Java8+ test classes
 578         if (atLeastJava8()) {
 579             String[] java8TestClassNames = {
 580                 "ArrayDeque8Test",
 581                 "Atomic8Test",
 582                 "CompletableFutureTest",
 583                 "ConcurrentHashMap8Test",
 584                 "CountedCompleter8Test",
 585                 "DoubleAccumulatorTest",
 586                 "DoubleAdderTest",
 587                 "ForkJoinPool8Test",
 588                 "ForkJoinTask8Test",
 589                 "HashMapTest",
 590                 "LinkedBlockingDeque8Test",
 591                 "LinkedBlockingQueue8Test",
 592                 "LinkedHashMapTest",
 593                 "LongAccumulatorTest",
 594                 "LongAdderTest",
 595                 "SplittableRandomTest",
 596                 "StampedLockTest",
 597                 "SubmissionPublisherTest",
 598                 "ThreadLocalRandom8Test",
 599                 "TimeUnit8Test",
 600             };
 601             addNamedTestClasses(suite, java8TestClassNames);
 602         }
 603 
 604         // Java9+ test classes
 605         if (atLeastJava9()) {
 606             String[] java9TestClassNames = {
 607                 "AtomicBoolean9Test",
 608                 "AtomicInteger9Test",
 609                 "AtomicIntegerArray9Test",
 610                 "AtomicLong9Test",
 611                 "AtomicLongArray9Test",
 612                 "AtomicReference9Test",
 613                 "AtomicReferenceArray9Test",
 614                 "ExecutorCompletionService9Test",
 615                 "ForkJoinPool9Test",
 616             };
 617             addNamedTestClasses(suite, java9TestClassNames);
 618         }
 619 
 620         return suite;
 621     }
 622 
 623     /** Returns list of junit-style test method names in given class. */
 624     public static ArrayList<String> testMethodNames(Class<?> testClass) {
 625         Method[] methods = testClass.getDeclaredMethods();
 626         ArrayList<String> names = new ArrayList<>(methods.length);
 627         for (Method method : methods) {
 628             if (method.getName().startsWith("test")
 629                 && Modifier.isPublic(method.getModifiers())
 630                 // method.getParameterCount() requires jdk8+
 631                 && method.getParameterTypes().length == 0) {
 632                 names.add(method.getName());
 633             }
 634         }
 635         return names;
 636     }
 637 
 638     /**
 639      * Returns junit-style testSuite for the given test class, but
 640      * parameterized by passing extra data to each test.
 641      */
 642     public static <ExtraData> Test parameterizedTestSuite
 643         (Class<? extends JSR166TestCase> testClass,
 644          Class<ExtraData> dataClass,
 645          ExtraData data) {
 646         try {
 647             TestSuite suite = new TestSuite();
 648             Constructor c =
 649                 testClass.getDeclaredConstructor(dataClass, String.class);
 650             for (String methodName : testMethodNames(testClass))
 651                 suite.addTest((Test) c.newInstance(data, methodName));
 652             return suite;
 653         } catch (ReflectiveOperationException e) {
 654             throw new AssertionError(e);
 655         }
 656     }
 657 
 658     /**
 659      * Returns junit-style testSuite for the jdk8 extension of the
 660      * given test class, but parameterized by passing extra data to
 661      * each test.  Uses reflection to allow compilation in jdk7.
 662      */
 663     public static <ExtraData> Test jdk8ParameterizedTestSuite
 664         (Class<? extends JSR166TestCase> testClass,
 665          Class<ExtraData> dataClass,
 666          ExtraData data) {
 667         if (atLeastJava8()) {
 668             String name = testClass.getName();
 669             String name8 = name.replaceAll("Test$", "8Test");
 670             if (name.equals(name8)) throw new AssertionError(name);
 671             try {
 672                 return (Test)
 673                     Class.forName(name8)
 674                     .getMethod("testSuite", dataClass)
 675                     .invoke(null, data);
 676             } catch (ReflectiveOperationException e) {
 677                 throw new AssertionError(e);
 678             }
 679         } else {
 680             return new TestSuite();
 681         }
 682     }
 683 
 684     // Delays for timing-dependent tests, in milliseconds.
 685 
 686     public static long SHORT_DELAY_MS;
 687     public static long SMALL_DELAY_MS;
 688     public static long MEDIUM_DELAY_MS;
 689     public static long LONG_DELAY_MS;
 690 
 691     /**
 692      * A delay significantly longer than LONG_DELAY_MS.
 693      * Use this in a thread that is waited for via awaitTermination(Thread).
 694      */
 695     public static long LONGER_DELAY_MS;
 696 
 697     private static final long RANDOM_TIMEOUT;
 698     private static final long RANDOM_EXPIRED_TIMEOUT;
 699     private static final TimeUnit RANDOM_TIMEUNIT;
 700     static {
 701         ThreadLocalRandom rnd = ThreadLocalRandom.current();
 702         long[] timeouts = { Long.MIN_VALUE, -1, 0, 1, Long.MAX_VALUE };
 703         RANDOM_TIMEOUT = timeouts[rnd.nextInt(timeouts.length)];
 704         RANDOM_EXPIRED_TIMEOUT = timeouts[rnd.nextInt(3)];
 705         TimeUnit[] timeUnits = TimeUnit.values();
 706         RANDOM_TIMEUNIT = timeUnits[rnd.nextInt(timeUnits.length)];
 707     }
 708 
 709     /**
 710      * Returns a timeout for use when any value at all will do.
 711      */
 712     static long randomTimeout() { return RANDOM_TIMEOUT; }
 713 
 714     /**
 715      * Returns a timeout that means "no waiting", i.e. not positive.
 716      */
 717     static long randomExpiredTimeout() { return RANDOM_EXPIRED_TIMEOUT; }
 718 
 719     /**
 720      * Returns a random non-null TimeUnit.
 721      */
 722     static TimeUnit randomTimeUnit() { return RANDOM_TIMEUNIT; }
 723 
 724     /**
 725      * Returns a random boolean; a "coin flip".
 726      */
 727     static boolean randomBoolean() {
 728         return ThreadLocalRandom.current().nextBoolean();
 729     }
 730 
 731     /**
 732      * Returns a random element from given choices.
 733      */
 734     <T> T chooseRandomly(List<T> choices) {
 735         return choices.get(ThreadLocalRandom.current().nextInt(choices.size()));
 736     }
 737 
 738     /**
 739      * Returns a random element from given choices.
 740      */
 741     <T> T chooseRandomly(T... choices) {
 742         return choices[ThreadLocalRandom.current().nextInt(choices.length)];
 743     }
 744 
 745     /**
 746      * Returns the shortest timed delay. This can be scaled up for
 747      * slow machines using the jsr166.delay.factor system property,
 748      * or via jtreg's -timeoutFactor: flag.
 749      * http://openjdk.java.net/jtreg/command-help.html
 750      */
 751     protected long getShortDelay() {
 752         return (long) (50 * delayFactor);
 753     }
 754 
 755     /**
 756      * Sets delays as multiples of SHORT_DELAY.
 757      */
 758     protected void setDelays() {
 759         SHORT_DELAY_MS = getShortDelay();
 760         SMALL_DELAY_MS  = SHORT_DELAY_MS * 5;
 761         MEDIUM_DELAY_MS = SHORT_DELAY_MS * 10;
 762         LONG_DELAY_MS   = SHORT_DELAY_MS * 200;
 763         LONGER_DELAY_MS = 2 * LONG_DELAY_MS;
 764     }
 765 
 766     private static final long TIMEOUT_DELAY_MS
 767         = (long) (12.0 * Math.cbrt(delayFactor));
 768 
 769     /**
 770      * Returns a timeout in milliseconds to be used in tests that verify
 771      * that operations block or time out.  We want this to be longer
 772      * than the OS scheduling quantum, but not too long, so don't scale
 773      * linearly with delayFactor; we use "crazy" cube root instead.
 774      */
 775     static long timeoutMillis() {
 776         return TIMEOUT_DELAY_MS;
 777     }
 778 
 779     /**
 780      * Returns a new Date instance representing a time at least
 781      * delayMillis milliseconds in the future.
 782      */
 783     Date delayedDate(long delayMillis) {
 784         // Add 1 because currentTimeMillis is known to round into the past.
 785         return new Date(System.currentTimeMillis() + delayMillis + 1);
 786     }
 787 
 788     /**
 789      * The first exception encountered if any threadAssertXXX method fails.
 790      */
 791     private final AtomicReference<Throwable> threadFailure
 792         = new AtomicReference<>(null);
 793 
 794     /**
 795      * Records an exception so that it can be rethrown later in the test
 796      * harness thread, triggering a test case failure.  Only the first
 797      * failure is recorded; subsequent calls to this method from within
 798      * the same test have no effect.
 799      */
 800     public void threadRecordFailure(Throwable t) {
 801         System.err.println(t);
 802         if (threadFailure.compareAndSet(null, t))
 803             dumpTestThreads();
 804     }
 805 
 806     public void setUp() {
 807         setDelays();
 808     }
 809 
 810     void tearDownFail(String format, Object... args) {
 811         String msg = toString() + ": " + String.format(format, args);
 812         System.err.println(msg);
 813         dumpTestThreads();
 814         throw new AssertionError(msg);
 815     }
 816 
 817     /**
 818      * Extra checks that get done for all test cases.
 819      *
 820      * Triggers test case failure if any thread assertions have failed,
 821      * by rethrowing, in the test harness thread, any exception recorded
 822      * earlier by threadRecordFailure.
 823      *
 824      * Triggers test case failure if interrupt status is set in the main thread.
 825      */
 826     public void tearDown() throws Exception {
 827         Throwable t = threadFailure.getAndSet(null);
 828         if (t != null) {
 829             if (t instanceof Error)
 830                 throw (Error) t;
 831             else if (t instanceof RuntimeException)
 832                 throw (RuntimeException) t;
 833             else if (t instanceof Exception)
 834                 throw (Exception) t;
 835             else
 836                 throw new AssertionError(t.toString(), t);
 837         }
 838 
 839         if (Thread.interrupted())
 840             tearDownFail("interrupt status set in main thread");
 841 
 842         checkForkJoinPoolThreadLeaks();
 843     }
 844 
 845     /**
 846      * Finds missing PoolCleaners
 847      */
 848     void checkForkJoinPoolThreadLeaks() throws InterruptedException {
 849         Thread[] survivors = new Thread[7];
 850         int count = Thread.enumerate(survivors);
 851         for (int i = 0; i < count; i++) {
 852             Thread thread = survivors[i];
 853             String name = thread.getName();
 854             if (name.startsWith("ForkJoinPool-")) {
 855                 // give thread some time to terminate
 856                 thread.join(LONG_DELAY_MS);
 857                 if (thread.isAlive())
 858                     tearDownFail("Found leaked ForkJoinPool thread thread=%s",
 859                                  thread);
 860             }
 861         }
 862 
 863         if (!ForkJoinPool.commonPool()
 864             .awaitQuiescence(LONG_DELAY_MS, MILLISECONDS))
 865             tearDownFail("ForkJoin common pool thread stuck");
 866     }
 867 
 868     /**
 869      * Just like fail(reason), but additionally recording (using
 870      * threadRecordFailure) any AssertionError thrown, so that the
 871      * current testcase will fail.
 872      */
 873     public void threadFail(String reason) {
 874         try {
 875             fail(reason);
 876         } catch (AssertionError fail) {
 877             threadRecordFailure(fail);
 878             throw fail;
 879         }
 880     }
 881 
 882     /**
 883      * Just like assertTrue(b), but additionally recording (using
 884      * threadRecordFailure) any AssertionError thrown, so that the
 885      * current testcase will fail.
 886      */
 887     public void threadAssertTrue(boolean b) {
 888         try {
 889             assertTrue(b);
 890         } catch (AssertionError fail) {
 891             threadRecordFailure(fail);
 892             throw fail;
 893         }
 894     }
 895 
 896     /**
 897      * Just like assertFalse(b), but additionally recording (using
 898      * threadRecordFailure) any AssertionError thrown, so that the
 899      * current testcase will fail.
 900      */
 901     public void threadAssertFalse(boolean b) {
 902         try {
 903             assertFalse(b);
 904         } catch (AssertionError fail) {
 905             threadRecordFailure(fail);
 906             throw fail;
 907         }
 908     }
 909 
 910     /**
 911      * Just like assertNull(x), but additionally recording (using
 912      * threadRecordFailure) any AssertionError thrown, so that the
 913      * current testcase will fail.
 914      */
 915     public void threadAssertNull(Object x) {
 916         try {
 917             assertNull(x);
 918         } catch (AssertionError fail) {
 919             threadRecordFailure(fail);
 920             throw fail;
 921         }
 922     }
 923 
 924     /**
 925      * Just like assertEquals(x, y), but additionally recording (using
 926      * threadRecordFailure) any AssertionError thrown, so that the
 927      * current testcase will fail.
 928      */
 929     public void threadAssertEquals(long x, long y) {
 930         try {
 931             assertEquals(x, y);
 932         } catch (AssertionError fail) {
 933             threadRecordFailure(fail);
 934             throw fail;
 935         }
 936     }
 937 
 938     /**
 939      * Just like assertEquals(x, y), but additionally recording (using
 940      * threadRecordFailure) any AssertionError thrown, so that the
 941      * current testcase will fail.
 942      */
 943     public void threadAssertEquals(Object x, Object y) {
 944         try {
 945             assertEquals(x, y);
 946         } catch (AssertionError fail) {
 947             threadRecordFailure(fail);
 948             throw fail;
 949         } catch (Throwable fail) {
 950             threadUnexpectedException(fail);
 951         }
 952     }
 953 
 954     /**
 955      * Just like assertSame(x, y), but additionally recording (using
 956      * threadRecordFailure) any AssertionError thrown, so that the
 957      * current testcase will fail.
 958      */
 959     public void threadAssertSame(Object x, Object y) {
 960         try {
 961             assertSame(x, y);
 962         } catch (AssertionError fail) {
 963             threadRecordFailure(fail);
 964             throw fail;
 965         }
 966     }
 967 
 968     /**
 969      * Calls threadFail with message "should throw exception".
 970      */
 971     public void threadShouldThrow() {
 972         threadFail("should throw exception");
 973     }
 974 
 975     /**
 976      * Calls threadFail with message "should throw" + exceptionName.
 977      */
 978     public void threadShouldThrow(String exceptionName) {
 979         threadFail("should throw " + exceptionName);
 980     }
 981 
 982     /**
 983      * Records the given exception using {@link #threadRecordFailure},
 984      * then rethrows the exception, wrapping it in an AssertionError
 985      * if necessary.
 986      */
 987     public void threadUnexpectedException(Throwable t) {
 988         threadRecordFailure(t);
 989         t.printStackTrace();
 990         if (t instanceof RuntimeException)
 991             throw (RuntimeException) t;
 992         else if (t instanceof Error)
 993             throw (Error) t;
 994         else
 995             throw new AssertionError("unexpected exception: " + t, t);
 996     }
 997 
 998     /**
 999      * Delays, via Thread.sleep, for the given millisecond delay, but
1000      * if the sleep is shorter than specified, may re-sleep or yield
1001      * until time elapses.  Ensures that the given time, as measured
1002      * by System.nanoTime(), has elapsed.
1003      */
1004     static void delay(long millis) throws InterruptedException {
1005         long nanos = millis * (1000 * 1000);
1006         final long wakeupTime = System.nanoTime() + nanos;
1007         do {
1008             if (millis > 0L)
1009                 Thread.sleep(millis);
1010             else // too short to sleep
1011                 Thread.yield();
1012             nanos = wakeupTime - System.nanoTime();
1013             millis = nanos / (1000 * 1000);
1014         } while (nanos >= 0L);
1015     }
1016 
1017     /**
1018      * Allows use of try-with-resources with per-test thread pools.
1019      */
1020     class PoolCleaner implements AutoCloseable {
1021         private final ExecutorService pool;
1022         public PoolCleaner(ExecutorService pool) { this.pool = pool; }
1023         public void close() { joinPool(pool); }
1024     }
1025 
1026     /**
1027      * An extension of PoolCleaner that has an action to release the pool.
1028      */
1029     class PoolCleanerWithReleaser extends PoolCleaner {
1030         private final Runnable releaser;
1031         public PoolCleanerWithReleaser(ExecutorService pool, Runnable releaser) {
1032             super(pool);
1033             this.releaser = releaser;
1034         }
1035         public void close() {
1036             try {
1037                 releaser.run();
1038             } finally {
1039                 super.close();
1040             }
1041         }
1042     }
1043 
1044     PoolCleaner cleaner(ExecutorService pool) {
1045         return new PoolCleaner(pool);
1046     }
1047 
1048     PoolCleaner cleaner(ExecutorService pool, Runnable releaser) {
1049         return new PoolCleanerWithReleaser(pool, releaser);
1050     }
1051 
1052     PoolCleaner cleaner(ExecutorService pool, CountDownLatch latch) {
1053         return new PoolCleanerWithReleaser(pool, releaser(latch));
1054     }
1055 
1056     Runnable releaser(final CountDownLatch latch) {
1057         return new Runnable() { public void run() {
1058             do { latch.countDown(); }
1059             while (latch.getCount() > 0);
1060         }};
1061     }
1062 
1063     PoolCleaner cleaner(ExecutorService pool, AtomicBoolean flag) {
1064         return new PoolCleanerWithReleaser(pool, releaser(flag));
1065     }
1066 
1067     Runnable releaser(final AtomicBoolean flag) {
1068         return new Runnable() { public void run() { flag.set(true); }};
1069     }
1070 
1071     /**
1072      * Waits out termination of a thread pool or fails doing so.
1073      */
1074     void joinPool(ExecutorService pool) {
1075         try {
1076             pool.shutdown();
1077             if (!pool.awaitTermination(2 * LONG_DELAY_MS, MILLISECONDS)) {
1078                 try {
1079                     threadFail("ExecutorService " + pool +
1080                                " did not terminate in a timely manner");
1081                 } finally {
1082                     // last resort, for the benefit of subsequent tests
1083                     pool.shutdownNow();
1084                     pool.awaitTermination(MEDIUM_DELAY_MS, MILLISECONDS);
1085                 }
1086             }
1087         } catch (SecurityException ok) {
1088             // Allowed in case test doesn't have privs
1089         } catch (InterruptedException fail) {
1090             threadFail("Unexpected InterruptedException");
1091         }
1092     }
1093 
1094     /**
1095      * Like Runnable, but with the freedom to throw anything.
1096      * junit folks had the same idea:
1097      * http://junit.org/junit5/docs/snapshot/api/org/junit/gen5/api/Executable.html
1098      */
1099     interface Action { public void run() throws Throwable; }
1100 
1101     /**
1102      * Runs all the given actions in parallel, failing if any fail.
1103      * Useful for running multiple variants of tests that are
1104      * necessarily individually slow because they must block.
1105      */
1106     void testInParallel(Action ... actions) {
1107         ExecutorService pool = Executors.newCachedThreadPool();
1108         try (PoolCleaner cleaner = cleaner(pool)) {
1109             ArrayList<Future<?>> futures = new ArrayList<>(actions.length);
1110             for (final Action action : actions)
1111                 futures.add(pool.submit(new CheckedRunnable() {
1112                     public void realRun() throws Throwable { action.run();}}));
1113             for (Future<?> future : futures)
1114                 try {
1115                     assertNull(future.get(LONG_DELAY_MS, MILLISECONDS));
1116                 } catch (ExecutionException ex) {
1117                     threadUnexpectedException(ex.getCause());
1118                 } catch (Exception ex) {
1119                     threadUnexpectedException(ex);
1120                 }
1121         }
1122     }
1123 
1124     /** Returns true if thread info might be useful in a thread dump. */
1125     static boolean threadOfInterest(ThreadInfo info) {
1126         final String name = info.getThreadName();
1127         String lockName;
1128         if (name == null)
1129             return true;
1130         if (name.equals("Signal Dispatcher")
1131             || name.equals("WedgedTestDetector"))
1132             return false;
1133         if (name.equals("Reference Handler")) {
1134             // Reference Handler stacktrace changed in JDK-8156500
1135             StackTraceElement[] stackTrace; String methodName;
1136             if ((stackTrace = info.getStackTrace()) != null
1137                 && stackTrace.length > 0
1138                 && (methodName = stackTrace[0].getMethodName()) != null
1139                 && methodName.equals("waitForReferencePendingList"))
1140                 return false;
1141             // jdk8 Reference Handler stacktrace
1142             if ((lockName = info.getLockName()) != null
1143                 && lockName.startsWith("java.lang.ref"))
1144                 return false;
1145         }
1146         if ((name.equals("Finalizer") || name.equals("Common-Cleaner"))
1147             && (lockName = info.getLockName()) != null
1148             && lockName.startsWith("java.lang.ref"))
1149             return false;
1150         if (name.startsWith("ForkJoinPool.commonPool-worker")
1151             && (lockName = info.getLockName()) != null
1152             && lockName.startsWith("java.util.concurrent.ForkJoinPool"))
1153             return false;
1154         return true;
1155     }
1156 
1157     /**
1158      * A debugging tool to print stack traces of most threads, as jstack does.
1159      * Uninteresting threads are filtered out.
1160      */
1161     static void dumpTestThreads() {
1162         SecurityManager sm = System.getSecurityManager();
1163         if (sm != null) {
1164             try {
1165                 System.setSecurityManager(null);
1166             } catch (SecurityException giveUp) {
1167                 return;
1168             }
1169         }
1170 
1171         System.err.println("------ stacktrace dump start ------");
1172         for (ThreadInfo info : THREAD_MXBEAN.dumpAllThreads(true, true))
1173             if (threadOfInterest(info))
1174                 System.err.print(info);
1175         System.err.println("------ stacktrace dump end ------");
1176 
1177         if (sm != null) System.setSecurityManager(sm);
1178     }
1179 
1180     /**
1181      * Checks that thread eventually enters the expected blocked thread state.
1182      */
1183     void assertThreadBlocks(Thread thread, Thread.State expected) {
1184         // always sleep at least 1 ms, with high probability avoiding
1185         // transitory states
1186         for (long retries = LONG_DELAY_MS * 3 / 4; retries-->0; ) {
1187             try { delay(1); }
1188             catch (InterruptedException fail) {
1189                 throw new AssertionError("Unexpected InterruptedException", fail);
1190             }
1191             Thread.State s = thread.getState();
1192             if (s == expected)
1193                 return;
1194             else if (s == Thread.State.TERMINATED)
1195                 fail("Unexpected thread termination");
1196         }
1197         fail("timed out waiting for thread to enter thread state " + expected);
1198     }
1199 
1200     /**
1201      * Returns the thread's blocker's class name, if any, else null.
1202      */
1203     String blockerClassName(Thread thread) {
1204         ThreadInfo threadInfo; LockInfo lockInfo;
1205         if ((threadInfo = THREAD_MXBEAN.getThreadInfo(thread.getId(), 0)) != null
1206             && (lockInfo = threadInfo.getLockInfo()) != null)
1207             return lockInfo.getClassName();
1208         return null;
1209     }
1210 
1211     /**
1212      * Checks that future.get times out, with the default timeout of
1213      * {@code timeoutMillis()}.
1214      */
1215     void assertFutureTimesOut(Future future) {
1216         assertFutureTimesOut(future, timeoutMillis());
1217     }
1218 
1219     /**
1220      * Checks that future.get times out, with the given millisecond timeout.
1221      */
1222     void assertFutureTimesOut(Future future, long timeoutMillis) {
1223         long startTime = System.nanoTime();
1224         try {
1225             future.get(timeoutMillis, MILLISECONDS);
1226             shouldThrow();
1227         } catch (TimeoutException success) {
1228         } catch (Exception fail) {
1229             threadUnexpectedException(fail);
1230         }
1231         assertTrue(millisElapsedSince(startTime) >= timeoutMillis);
1232         assertFalse(future.isDone());
1233     }
1234 
1235     /**
1236      * Fails with message "should throw exception".
1237      */
1238     public void shouldThrow() {
1239         fail("Should throw exception");
1240     }
1241 
1242     /**
1243      * Fails with message "should throw " + exceptionName.
1244      */
1245     public void shouldThrow(String exceptionName) {
1246         fail("Should throw " + exceptionName);
1247     }
1248 
1249     /**
1250      * The maximum number of consecutive spurious wakeups we should
1251      * tolerate (from APIs like LockSupport.park) before failing a test.
1252      */
1253     static final int MAX_SPURIOUS_WAKEUPS = 10;
1254 
1255     /**
1256      * The number of elements to place in collections, arrays, etc.
1257      */
1258     public static final int SIZE = 20;
1259 
1260     // Some convenient Integer constants
1261 
1262     public static final Integer zero  = new Integer(0);
1263     public static final Integer one   = new Integer(1);
1264     public static final Integer two   = new Integer(2);
1265     public static final Integer three = new Integer(3);
1266     public static final Integer four  = new Integer(4);
1267     public static final Integer five  = new Integer(5);
1268     public static final Integer six   = new Integer(6);
1269     public static final Integer seven = new Integer(7);
1270     public static final Integer eight = new Integer(8);
1271     public static final Integer nine  = new Integer(9);
1272     public static final Integer m1  = new Integer(-1);
1273     public static final Integer m2  = new Integer(-2);
1274     public static final Integer m3  = new Integer(-3);
1275     public static final Integer m4  = new Integer(-4);
1276     public static final Integer m5  = new Integer(-5);
1277     public static final Integer m6  = new Integer(-6);
1278     public static final Integer m10 = new Integer(-10);
1279 
1280     /**
1281      * Runs Runnable r with a security policy that permits precisely
1282      * the specified permissions.  If there is no current security
1283      * manager, the runnable is run twice, both with and without a
1284      * security manager.  We require that any security manager permit
1285      * getPolicy/setPolicy.
1286      */
1287     public void runWithPermissions(Runnable r, Permission... permissions) {
1288         SecurityManager sm = System.getSecurityManager();
1289         if (sm == null) {
1290             r.run();
1291         }
1292         runWithSecurityManagerWithPermissions(r, permissions);
1293     }
1294 
1295     /**
1296      * Runs Runnable r with a security policy that permits precisely
1297      * the specified permissions.  If there is no current security
1298      * manager, a temporary one is set for the duration of the
1299      * Runnable.  We require that any security manager permit
1300      * getPolicy/setPolicy.
1301      */
1302     public void runWithSecurityManagerWithPermissions(Runnable r,
1303                                                       Permission... permissions) {
1304         SecurityManager sm = System.getSecurityManager();
1305         if (sm == null) {
1306             Policy savedPolicy = Policy.getPolicy();
1307             try {
1308                 Policy.setPolicy(permissivePolicy());
1309                 System.setSecurityManager(new SecurityManager());
1310                 runWithSecurityManagerWithPermissions(r, permissions);
1311             } finally {
1312                 System.setSecurityManager(null);
1313                 Policy.setPolicy(savedPolicy);
1314             }
1315         } else {
1316             Policy savedPolicy = Policy.getPolicy();
1317             AdjustablePolicy policy = new AdjustablePolicy(permissions);
1318             Policy.setPolicy(policy);
1319 
1320             try {
1321                 r.run();
1322             } finally {
1323                 policy.addPermission(new SecurityPermission("setPolicy"));
1324                 Policy.setPolicy(savedPolicy);
1325             }
1326         }
1327     }
1328 
1329     /**
1330      * Runs a runnable without any permissions.
1331      */
1332     public void runWithoutPermissions(Runnable r) {
1333         runWithPermissions(r);
1334     }
1335 
1336     /**
1337      * A security policy where new permissions can be dynamically added
1338      * or all cleared.
1339      */
1340     public static class AdjustablePolicy extends java.security.Policy {
1341         Permissions perms = new Permissions();
1342         AdjustablePolicy(Permission... permissions) {
1343             for (Permission permission : permissions)
1344                 perms.add(permission);
1345         }
1346         void addPermission(Permission perm) { perms.add(perm); }
1347         void clearPermissions() { perms = new Permissions(); }
1348         public PermissionCollection getPermissions(CodeSource cs) {
1349             return perms;
1350         }
1351         public PermissionCollection getPermissions(ProtectionDomain pd) {
1352             return perms;
1353         }
1354         public boolean implies(ProtectionDomain pd, Permission p) {
1355             return perms.implies(p);
1356         }
1357         public void refresh() {}
1358         public String toString() {
1359             List<Permission> ps = new ArrayList<>();
1360             for (Enumeration<Permission> e = perms.elements(); e.hasMoreElements();)
1361                 ps.add(e.nextElement());
1362             return "AdjustablePolicy with permissions " + ps;
1363         }
1364     }
1365 
1366     /**
1367      * Returns a policy containing all the permissions we ever need.
1368      */
1369     public static Policy permissivePolicy() {
1370         return new AdjustablePolicy
1371             // Permissions j.u.c. needs directly
1372             (new RuntimePermission("modifyThread"),
1373              new RuntimePermission("getClassLoader"),
1374              new RuntimePermission("setContextClassLoader"),
1375              // Permissions needed to change permissions!
1376              new SecurityPermission("getPolicy"),
1377              new SecurityPermission("setPolicy"),
1378              new RuntimePermission("setSecurityManager"),
1379              // Permissions needed by the junit test harness
1380              new RuntimePermission("accessDeclaredMembers"),
1381              new PropertyPermission("*", "read"),
1382              new java.io.FilePermission("<<ALL FILES>>", "read"));
1383     }
1384 
1385     /**
1386      * Sleeps until the given time has elapsed.
1387      * Throws AssertionError if interrupted.
1388      */
1389     static void sleep(long millis) {
1390         try {
1391             delay(millis);
1392         } catch (InterruptedException fail) {
1393             throw new AssertionError("Unexpected InterruptedException", fail);
1394         }
1395     }
1396 
1397     /**
1398      * Spin-waits up to the specified number of milliseconds for the given
1399      * thread to enter a wait state: BLOCKED, WAITING, or TIMED_WAITING.
1400      * @param waitingForGodot if non-null, an additional condition to satisfy
1401      */
1402     void waitForThreadToEnterWaitState(Thread thread, long timeoutMillis,
1403                                        Callable<Boolean> waitingForGodot) {
1404         for (long startTime = 0L;;) {
1405             switch (thread.getState()) {
1406             default: break;
1407             case BLOCKED: case WAITING: case TIMED_WAITING:
1408                 try {
1409                     if (waitingForGodot == null || waitingForGodot.call())
1410                         return;
1411                 } catch (Throwable fail) { threadUnexpectedException(fail); }
1412                 break;
1413             case TERMINATED:
1414                 fail("Unexpected thread termination");
1415             }
1416 
1417             if (startTime == 0L)
1418                 startTime = System.nanoTime();
1419             else if (millisElapsedSince(startTime) > timeoutMillis) {
1420                 assertTrue(thread.isAlive());
1421                 if (waitingForGodot == null
1422                     || thread.getState() == Thread.State.RUNNABLE)
1423                     fail("timed out waiting for thread to enter wait state");
1424                 else
1425                     fail("timed out waiting for condition, thread state="
1426                          + thread.getState());
1427             }
1428             Thread.yield();
1429         }
1430     }
1431 
1432     /**
1433      * Spin-waits up to the specified number of milliseconds for the given
1434      * thread to enter a wait state: BLOCKED, WAITING, or TIMED_WAITING.
1435      */
1436     void waitForThreadToEnterWaitState(Thread thread, long timeoutMillis) {
1437         waitForThreadToEnterWaitState(thread, timeoutMillis, null);
1438     }
1439 
1440     /**
1441      * Spin-waits up to LONG_DELAY_MS milliseconds for the given thread to
1442      * enter a wait state: BLOCKED, WAITING, or TIMED_WAITING.
1443      */
1444     void waitForThreadToEnterWaitState(Thread thread) {
1445         waitForThreadToEnterWaitState(thread, LONG_DELAY_MS, null);
1446     }
1447 
1448     /**
1449      * Spin-waits up to LONG_DELAY_MS milliseconds for the given thread to
1450      * enter a wait state: BLOCKED, WAITING, or TIMED_WAITING,
1451      * and additionally satisfy the given condition.
1452      */
1453     void waitForThreadToEnterWaitState(Thread thread,
1454                                        Callable<Boolean> waitingForGodot) {
1455         waitForThreadToEnterWaitState(thread, LONG_DELAY_MS, waitingForGodot);
1456     }
1457 
1458     /**
1459      * Spin-waits up to LONG_DELAY_MS milliseconds for the current thread to
1460      * be interrupted.  Clears the interrupt status before returning.
1461      */
1462     void awaitInterrupted() {
1463         for (long startTime = 0L; !Thread.interrupted(); ) {
1464             if (startTime == 0L)
1465                 startTime = System.nanoTime();
1466             else if (millisElapsedSince(startTime) > LONG_DELAY_MS)
1467                 fail("timed out waiting for thread interrupt");
1468             Thread.yield();
1469         }
1470     }
1471 
1472     /**
1473      * Returns the number of milliseconds since time given by
1474      * startNanoTime, which must have been previously returned from a
1475      * call to {@link System#nanoTime()}.
1476      */
1477     static long millisElapsedSince(long startNanoTime) {
1478         return NANOSECONDS.toMillis(System.nanoTime() - startNanoTime);
1479     }
1480 
1481     /**
1482      * Checks that timed f.get() returns the expected value, and does not
1483      * wait for the timeout to elapse before returning.
1484      */
1485     <T> void checkTimedGet(Future<T> f, T expectedValue, long timeoutMillis) {
1486         long startTime = System.nanoTime();
1487         T actual = null;
1488         try {
1489             actual = f.get(timeoutMillis, MILLISECONDS);
1490         } catch (Throwable fail) { threadUnexpectedException(fail); }
1491         assertEquals(expectedValue, actual);
1492         if (millisElapsedSince(startTime) > timeoutMillis/2)
1493             throw new AssertionError("timed get did not return promptly");
1494     }
1495 
1496     <T> void checkTimedGet(Future<T> f, T expectedValue) {
1497         checkTimedGet(f, expectedValue, LONG_DELAY_MS);
1498     }
1499 
1500     /**
1501      * Returns a new started daemon Thread running the given runnable.
1502      */
1503     Thread newStartedThread(Runnable runnable) {
1504         Thread t = new Thread(runnable);
1505         t.setDaemon(true);
1506         t.start();
1507         return t;
1508     }
1509 
1510     /**
1511      * Returns a new started daemon Thread running the given action,
1512      * wrapped in a CheckedRunnable.
1513      */
1514     Thread newStartedThread(Action action) {
1515         return newStartedThread(checkedRunnable(action));
1516     }
1517 
1518     /**
1519      * Waits for the specified time (in milliseconds) for the thread
1520      * to terminate (using {@link Thread#join(long)}), else interrupts
1521      * the thread (in the hope that it may terminate later) and fails.
1522      */
1523     void awaitTermination(Thread thread, long timeoutMillis) {
1524         try {
1525             thread.join(timeoutMillis);
1526         } catch (InterruptedException fail) {
1527             threadUnexpectedException(fail);
1528         }
1529         if (thread.getState() != Thread.State.TERMINATED) {
1530             String detail = String.format(
1531                     "timed out waiting for thread to terminate, thread=%s, state=%s" ,
1532                     thread, thread.getState());
1533             try {
1534                 threadFail(detail);
1535             } finally {
1536                 // Interrupt thread __after__ having reported its stack trace
1537                 thread.interrupt();
1538             }
1539         }
1540     }
1541 
1542     /**
1543      * Waits for LONG_DELAY_MS milliseconds for the thread to
1544      * terminate (using {@link Thread#join(long)}), else interrupts
1545      * the thread (in the hope that it may terminate later) and fails.
1546      */
1547     void awaitTermination(Thread t) {
1548         awaitTermination(t, LONG_DELAY_MS);
1549     }
1550 
1551     // Some convenient Runnable classes
1552 
1553     public abstract class CheckedRunnable implements Runnable {
1554         protected abstract void realRun() throws Throwable;
1555 
1556         public final void run() {
1557             try {
1558                 realRun();
1559             } catch (Throwable fail) {
1560                 threadUnexpectedException(fail);
1561             }
1562         }
1563     }
1564 
1565     Runnable checkedRunnable(Action action) {
1566         return new CheckedRunnable() {
1567             public void realRun() throws Throwable {
1568                 action.run();
1569             }};
1570     }
1571 
1572     public abstract class ThreadShouldThrow extends Thread {
1573         protected abstract void realRun() throws Throwable;
1574 
1575         final Class<?> exceptionClass;
1576 
1577         <T extends Throwable> ThreadShouldThrow(Class<T> exceptionClass) {
1578             this.exceptionClass = exceptionClass;
1579         }
1580 
1581         public final void run() {
1582             try {
1583                 realRun();
1584             } catch (Throwable t) {
1585                 if (! exceptionClass.isInstance(t))
1586                     threadUnexpectedException(t);
1587                 return;
1588             }
1589             threadShouldThrow(exceptionClass.getSimpleName());
1590         }
1591     }
1592 
1593     public abstract class CheckedInterruptedRunnable implements Runnable {
1594         protected abstract void realRun() throws Throwable;
1595 
1596         public final void run() {
1597             try {
1598                 realRun();
1599             } catch (InterruptedException success) {
1600                 threadAssertFalse(Thread.interrupted());
1601                 return;
1602             } catch (Throwable fail) {
1603                 threadUnexpectedException(fail);
1604             }
1605             threadShouldThrow("InterruptedException");
1606         }
1607     }
1608 
1609     public abstract class CheckedCallable<T> implements Callable<T> {
1610         protected abstract T realCall() throws Throwable;
1611 
1612         public final T call() {
1613             try {
1614                 return realCall();
1615             } catch (Throwable fail) {
1616                 threadUnexpectedException(fail);
1617             }
1618             throw new AssertionError("unreached");
1619         }
1620     }
1621 
1622     public static class NoOpRunnable implements Runnable {
1623         public void run() {}
1624     }
1625 
1626     public static class NoOpCallable implements Callable {
1627         public Object call() { return Boolean.TRUE; }
1628     }
1629 
1630     public static final String TEST_STRING = "a test string";
1631 
1632     public static class StringTask implements Callable<String> {
1633         final String value;
1634         public StringTask() { this(TEST_STRING); }
1635         public StringTask(String value) { this.value = value; }
1636         public String call() { return value; }
1637     }
1638 
1639     public Callable<String> latchAwaitingStringTask(final CountDownLatch latch) {
1640         return new CheckedCallable<String>() {
1641             protected String realCall() {
1642                 try {
1643                     latch.await();
1644                 } catch (InterruptedException quittingTime) {}
1645                 return TEST_STRING;
1646             }};
1647     }
1648 
1649     public Runnable countDowner(final CountDownLatch latch) {
1650         return new CheckedRunnable() {
1651             public void realRun() throws InterruptedException {
1652                 latch.countDown();
1653             }};
1654     }
1655 
1656     class LatchAwaiter extends CheckedRunnable {
1657         static final int NEW = 0;
1658         static final int RUNNING = 1;
1659         static final int DONE = 2;
1660         final CountDownLatch latch;
1661         int state = NEW;
1662         LatchAwaiter(CountDownLatch latch) { this.latch = latch; }
1663         public void realRun() throws InterruptedException {
1664             state = 1;
1665             await(latch);
1666             state = 2;
1667         }
1668     }
1669 
1670     public LatchAwaiter awaiter(CountDownLatch latch) {
1671         return new LatchAwaiter(latch);
1672     }
1673 
1674     public void await(CountDownLatch latch, long timeoutMillis) {
1675         boolean timedOut = false;
1676         try {
1677             timedOut = !latch.await(timeoutMillis, MILLISECONDS);
1678         } catch (Throwable fail) {
1679             threadUnexpectedException(fail);
1680         }
1681         if (timedOut)
1682             fail("timed out waiting for CountDownLatch for "
1683                  + (timeoutMillis/1000) + " sec");
1684     }
1685 
1686     public void await(CountDownLatch latch) {
1687         await(latch, LONG_DELAY_MS);
1688     }
1689 
1690     public void await(Semaphore semaphore) {
1691         boolean timedOut = false;
1692         try {
1693             timedOut = !semaphore.tryAcquire(LONG_DELAY_MS, MILLISECONDS);
1694         } catch (Throwable fail) {
1695             threadUnexpectedException(fail);
1696         }
1697         if (timedOut)
1698             fail("timed out waiting for Semaphore for "
1699                  + (LONG_DELAY_MS/1000) + " sec");
1700     }
1701 
1702     public void await(CyclicBarrier barrier) {
1703         try {
1704             barrier.await(LONG_DELAY_MS, MILLISECONDS);
1705         } catch (Throwable fail) {
1706             threadUnexpectedException(fail);
1707         }
1708     }
1709 
1710 //     /**
1711 //      * Spin-waits up to LONG_DELAY_MS until flag becomes true.
1712 //      */
1713 //     public void await(AtomicBoolean flag) {
1714 //         await(flag, LONG_DELAY_MS);
1715 //     }
1716 
1717 //     /**
1718 //      * Spin-waits up to the specified timeout until flag becomes true.
1719 //      */
1720 //     public void await(AtomicBoolean flag, long timeoutMillis) {
1721 //         long startTime = System.nanoTime();
1722 //         while (!flag.get()) {
1723 //             if (millisElapsedSince(startTime) > timeoutMillis)
1724 //                 throw new AssertionError("timed out");
1725 //             Thread.yield();
1726 //         }
1727 //     }
1728 
1729     public static class NPETask implements Callable<String> {
1730         public String call() { throw new NullPointerException(); }
1731     }
1732 
1733     public Runnable possiblyInterruptedRunnable(final long timeoutMillis) {
1734         return new CheckedRunnable() {
1735             protected void realRun() {
1736                 try {
1737                     delay(timeoutMillis);
1738                 } catch (InterruptedException ok) {}
1739             }};
1740     }
1741 
1742     /**
1743      * For use as ThreadFactory in constructors
1744      */
1745     public static class SimpleThreadFactory implements ThreadFactory {
1746         public Thread newThread(Runnable r) {
1747             return new Thread(r);
1748         }
1749     }
1750 
1751     public interface TrackedRunnable extends Runnable {
1752         boolean isDone();
1753     }
1754 
1755     public static class TrackedNoOpRunnable implements Runnable {
1756         public volatile boolean done = false;
1757         public void run() {
1758             done = true;
1759         }
1760     }
1761 
1762     /**
1763      * Analog of CheckedRunnable for RecursiveAction
1764      */
1765     public abstract class CheckedRecursiveAction extends RecursiveAction {
1766         protected abstract void realCompute() throws Throwable;
1767 
1768         @Override protected final void compute() {
1769             try {
1770                 realCompute();
1771             } catch (Throwable fail) {
1772                 threadUnexpectedException(fail);
1773             }
1774         }
1775     }
1776 
1777     /**
1778      * Analog of CheckedCallable for RecursiveTask
1779      */
1780     public abstract class CheckedRecursiveTask<T> extends RecursiveTask<T> {
1781         protected abstract T realCompute() throws Throwable;
1782 
1783         @Override protected final T compute() {
1784             try {
1785                 return realCompute();
1786             } catch (Throwable fail) {
1787                 threadUnexpectedException(fail);
1788             }
1789             throw new AssertionError("unreached");
1790         }
1791     }
1792 
1793     /**
1794      * For use as RejectedExecutionHandler in constructors
1795      */
1796     public static class NoOpREHandler implements RejectedExecutionHandler {
1797         public void rejectedExecution(Runnable r,
1798                                       ThreadPoolExecutor executor) {}
1799     }
1800 
1801     /**
1802      * A CyclicBarrier that uses timed await and fails with
1803      * AssertionErrors instead of throwing checked exceptions.
1804      */
1805     public static class CheckedBarrier extends CyclicBarrier {
1806         public CheckedBarrier(int parties) { super(parties); }
1807 
1808         public int await() {
1809             try {
1810                 return super.await(LONGER_DELAY_MS, MILLISECONDS);
1811             } catch (TimeoutException timedOut) {
1812                 throw new AssertionError("timed out");
1813             } catch (Exception fail) {
1814                 throw new AssertionError("Unexpected exception: " + fail, fail);
1815             }
1816         }
1817     }
1818 
1819     void checkEmpty(BlockingQueue q) {
1820         try {
1821             assertTrue(q.isEmpty());
1822             assertEquals(0, q.size());
1823             assertNull(q.peek());
1824             assertNull(q.poll());
1825             assertNull(q.poll(randomExpiredTimeout(), randomTimeUnit()));
1826             assertEquals(q.toString(), "[]");
1827             assertTrue(Arrays.equals(q.toArray(), new Object[0]));
1828             assertFalse(q.iterator().hasNext());
1829             try {
1830                 q.element();
1831                 shouldThrow();
1832             } catch (NoSuchElementException success) {}
1833             try {
1834                 q.iterator().next();
1835                 shouldThrow();
1836             } catch (NoSuchElementException success) {}
1837             try {
1838                 q.remove();
1839                 shouldThrow();
1840             } catch (NoSuchElementException success) {}
1841         } catch (InterruptedException fail) { threadUnexpectedException(fail); }
1842     }
1843 
1844     void assertSerialEquals(Object x, Object y) {
1845         assertTrue(Arrays.equals(serialBytes(x), serialBytes(y)));
1846     }
1847 
1848     void assertNotSerialEquals(Object x, Object y) {
1849         assertFalse(Arrays.equals(serialBytes(x), serialBytes(y)));
1850     }
1851 
1852     byte[] serialBytes(Object o) {
1853         try {
1854             ByteArrayOutputStream bos = new ByteArrayOutputStream();
1855             ObjectOutputStream oos = new ObjectOutputStream(bos);
1856             oos.writeObject(o);
1857             oos.flush();
1858             oos.close();
1859             return bos.toByteArray();
1860         } catch (Throwable fail) {
1861             threadUnexpectedException(fail);
1862             return new byte[0];
1863         }
1864     }
1865 
1866     void assertImmutable(Object o) {
1867         if (o instanceof Collection) {
1868             assertThrows(
1869                 UnsupportedOperationException.class,
1870                 () -> ((Collection) o).add(null));
1871         }
1872     }
1873 
1874     @SuppressWarnings("unchecked")
1875     <T> T serialClone(T o) {
1876         T clone = null;
1877         try {
1878             ObjectInputStream ois = new ObjectInputStream
1879                 (new ByteArrayInputStream(serialBytes(o)));
1880             clone = (T) ois.readObject();
1881         } catch (Throwable fail) {
1882             threadUnexpectedException(fail);
1883         }
1884         if (o == clone) assertImmutable(o);
1885         else assertSame(o.getClass(), clone.getClass());
1886         return clone;
1887     }
1888 
1889     /**
1890      * A version of serialClone that leaves error handling (for
1891      * e.g. NotSerializableException) up to the caller.
1892      */
1893     @SuppressWarnings("unchecked")
1894     <T> T serialClonePossiblyFailing(T o)
1895         throws ReflectiveOperationException, java.io.IOException {
1896         ByteArrayOutputStream bos = new ByteArrayOutputStream();
1897         ObjectOutputStream oos = new ObjectOutputStream(bos);
1898         oos.writeObject(o);
1899         oos.flush();
1900         oos.close();
1901         ObjectInputStream ois = new ObjectInputStream
1902             (new ByteArrayInputStream(bos.toByteArray()));
1903         T clone = (T) ois.readObject();
1904         if (o == clone) assertImmutable(o);
1905         else assertSame(o.getClass(), clone.getClass());
1906         return clone;
1907     }
1908 
1909     /**
1910      * If o implements Cloneable and has a public clone method,
1911      * returns a clone of o, else null.
1912      */
1913     @SuppressWarnings("unchecked")
1914     <T> T cloneableClone(T o) {
1915         if (!(o instanceof Cloneable)) return null;
1916         final T clone;
1917         try {
1918             clone = (T) o.getClass().getMethod("clone").invoke(o);
1919         } catch (NoSuchMethodException ok) {
1920             return null;
1921         } catch (ReflectiveOperationException unexpected) {
1922             throw new Error(unexpected);
1923         }
1924         assertNotSame(o, clone); // not 100% guaranteed by spec
1925         assertSame(o.getClass(), clone.getClass());
1926         return clone;
1927     }
1928 
1929     public void assertThrows(Class<? extends Throwable> expectedExceptionClass,
1930                              Action... throwingActions) {
1931         for (Action throwingAction : throwingActions) {
1932             boolean threw = false;
1933             try { throwingAction.run(); }
1934             catch (Throwable t) {
1935                 threw = true;
1936                 if (!expectedExceptionClass.isInstance(t))
1937                     throw new AssertionError(
1938                             "Expected " + expectedExceptionClass.getName() +
1939                             ", got " + t.getClass().getName(),
1940                             t);
1941             }
1942             if (!threw)
1943                 shouldThrow(expectedExceptionClass.getName());
1944         }
1945     }
1946 
1947     public void assertIteratorExhausted(Iterator<?> it) {
1948         try {
1949             it.next();
1950             shouldThrow();
1951         } catch (NoSuchElementException success) {}
1952         assertFalse(it.hasNext());
1953     }
1954 
1955     public <T> Callable<T> callableThrowing(final Exception ex) {
1956         return new Callable<T>() { public T call() throws Exception { throw ex; }};
1957     }
1958 
1959     public Runnable runnableThrowing(final RuntimeException ex) {
1960         return new Runnable() { public void run() { throw ex; }};
1961     }
1962 
1963     /** A reusable thread pool to be shared by tests. */
1964     static final ExecutorService cachedThreadPool =
1965         new ThreadPoolExecutor(0, Integer.MAX_VALUE,
1966                                1000L, MILLISECONDS,
1967                                new SynchronousQueue<Runnable>());
1968 
1969     static <T> void shuffle(T[] array) {
1970         Collections.shuffle(Arrays.asList(array), ThreadLocalRandom.current());
1971     }
1972 
1973     /**
1974      * Returns the same String as would be returned by {@link
1975      * Object#toString}, whether or not the given object's class
1976      * overrides toString().
1977      *
1978      * @see System#identityHashCode
1979      */
1980     static String identityString(Object x) {
1981         return x.getClass().getName()
1982             + "@" + Integer.toHexString(System.identityHashCode(x));
1983     }
1984 
1985     // --- Shared assertions for Executor tests ---
1986 
1987     /**
1988      * Returns maximum number of tasks that can be submitted to given
1989      * pool (with bounded queue) before saturation (when submission
1990      * throws RejectedExecutionException).
1991      */
1992     static final int saturatedSize(ThreadPoolExecutor pool) {
1993         BlockingQueue<Runnable> q = pool.getQueue();
1994         return pool.getMaximumPoolSize() + q.size() + q.remainingCapacity();
1995     }
1996 
1997     @SuppressWarnings("FutureReturnValueIgnored")
1998     void assertNullTaskSubmissionThrowsNullPointerException(Executor e) {
1999         try {
2000             e.execute((Runnable) null);
2001             shouldThrow();
2002         } catch (NullPointerException success) {}
2003 
2004         if (! (e instanceof ExecutorService)) return;
2005         ExecutorService es = (ExecutorService) e;
2006         try {
2007             es.submit((Runnable) null);
2008             shouldThrow();
2009         } catch (NullPointerException success) {}
2010         try {
2011             es.submit((Runnable) null, Boolean.TRUE);
2012             shouldThrow();
2013         } catch (NullPointerException success) {}
2014         try {
2015             es.submit((Callable) null);
2016             shouldThrow();
2017         } catch (NullPointerException success) {}
2018 
2019         if (! (e instanceof ScheduledExecutorService)) return;
2020         ScheduledExecutorService ses = (ScheduledExecutorService) e;
2021         try {
2022             ses.schedule((Runnable) null,
2023                          randomTimeout(), randomTimeUnit());
2024             shouldThrow();
2025         } catch (NullPointerException success) {}
2026         try {
2027             ses.schedule((Callable) null,
2028                          randomTimeout(), randomTimeUnit());
2029             shouldThrow();
2030         } catch (NullPointerException success) {}
2031         try {
2032             ses.scheduleAtFixedRate((Runnable) null,
2033                                     randomTimeout(), LONG_DELAY_MS, MILLISECONDS);
2034             shouldThrow();
2035         } catch (NullPointerException success) {}
2036         try {
2037             ses.scheduleWithFixedDelay((Runnable) null,
2038                                        randomTimeout(), LONG_DELAY_MS, MILLISECONDS);
2039             shouldThrow();
2040         } catch (NullPointerException success) {}
2041     }
2042 
2043     void setRejectedExecutionHandler(
2044         ThreadPoolExecutor p, RejectedExecutionHandler handler) {
2045         p.setRejectedExecutionHandler(handler);
2046         assertSame(handler, p.getRejectedExecutionHandler());
2047     }
2048 
2049     void assertTaskSubmissionsAreRejected(ThreadPoolExecutor p) {
2050         final RejectedExecutionHandler savedHandler = p.getRejectedExecutionHandler();
2051         final long savedTaskCount = p.getTaskCount();
2052         final long savedCompletedTaskCount = p.getCompletedTaskCount();
2053         final int savedQueueSize = p.getQueue().size();
2054         final boolean stock = (p.getClass().getClassLoader() == null);
2055 
2056         Runnable r = () -> {};
2057         Callable<Boolean> c = () -> Boolean.TRUE;
2058 
2059         class Recorder implements RejectedExecutionHandler {
2060             public volatile Runnable r = null;
2061             public volatile ThreadPoolExecutor p = null;
2062             public void reset() { r = null; p = null; }
2063             public void rejectedExecution(Runnable r, ThreadPoolExecutor p) {
2064                 assertNull(this.r);
2065                 assertNull(this.p);
2066                 this.r = r;
2067                 this.p = p;
2068             }
2069         }
2070 
2071         // check custom handler is invoked exactly once per task
2072         Recorder recorder = new Recorder();
2073         setRejectedExecutionHandler(p, recorder);
2074         for (int i = 2; i--> 0; ) {
2075             recorder.reset();
2076             p.execute(r);
2077             if (stock && p.getClass() == ThreadPoolExecutor.class)
2078                 assertSame(r, recorder.r);
2079             assertSame(p, recorder.p);
2080 
2081             recorder.reset();
2082             assertFalse(p.submit(r).isDone());
2083             if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2084             assertSame(p, recorder.p);
2085 
2086             recorder.reset();
2087             assertFalse(p.submit(r, Boolean.TRUE).isDone());
2088             if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2089             assertSame(p, recorder.p);
2090 
2091             recorder.reset();
2092             assertFalse(p.submit(c).isDone());
2093             if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2094             assertSame(p, recorder.p);
2095 
2096             if (p instanceof ScheduledExecutorService) {
2097                 ScheduledExecutorService s = (ScheduledExecutorService) p;
2098                 ScheduledFuture<?> future;
2099 
2100                 recorder.reset();
2101                 future = s.schedule(r, randomTimeout(), randomTimeUnit());
2102                 assertFalse(future.isDone());
2103                 if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2104                 assertSame(p, recorder.p);
2105 
2106                 recorder.reset();
2107                 future = s.schedule(c, randomTimeout(), randomTimeUnit());
2108                 assertFalse(future.isDone());
2109                 if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2110                 assertSame(p, recorder.p);
2111 
2112                 recorder.reset();
2113                 future = s.scheduleAtFixedRate(r, randomTimeout(), LONG_DELAY_MS, MILLISECONDS);
2114                 assertFalse(future.isDone());
2115                 if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2116                 assertSame(p, recorder.p);
2117 
2118                 recorder.reset();
2119                 future = s.scheduleWithFixedDelay(r, randomTimeout(), LONG_DELAY_MS, MILLISECONDS);
2120                 assertFalse(future.isDone());
2121                 if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2122                 assertSame(p, recorder.p);
2123             }
2124         }
2125 
2126         // Checking our custom handler above should be sufficient, but
2127         // we add some integration tests of standard handlers.
2128         final AtomicReference<Thread> thread = new AtomicReference<>();
2129         final Runnable setThread = () -> thread.set(Thread.currentThread());
2130 
2131         setRejectedExecutionHandler(p, new ThreadPoolExecutor.AbortPolicy());
2132         try {
2133             p.execute(setThread);
2134             shouldThrow();
2135         } catch (RejectedExecutionException success) {}
2136         assertNull(thread.get());
2137 
2138         setRejectedExecutionHandler(p, new ThreadPoolExecutor.DiscardPolicy());
2139         p.execute(setThread);
2140         assertNull(thread.get());
2141 
2142         setRejectedExecutionHandler(p, new ThreadPoolExecutor.CallerRunsPolicy());
2143         p.execute(setThread);
2144         if (p.isShutdown())
2145             assertNull(thread.get());
2146         else
2147             assertSame(Thread.currentThread(), thread.get());
2148 
2149         setRejectedExecutionHandler(p, savedHandler);
2150 
2151         // check that pool was not perturbed by handlers
2152         assertEquals(savedTaskCount, p.getTaskCount());
2153         assertEquals(savedCompletedTaskCount, p.getCompletedTaskCount());
2154         assertEquals(savedQueueSize, p.getQueue().size());
2155     }
2156 
2157     void assertCollectionsEquals(Collection<?> x, Collection<?> y) {
2158         assertEquals(x, y);
2159         assertEquals(y, x);
2160         assertEquals(x.isEmpty(), y.isEmpty());
2161         assertEquals(x.size(), y.size());
2162         if (x instanceof List) {
2163             assertEquals(x.toString(), y.toString());
2164         }
2165         if (x instanceof List || x instanceof Set) {
2166             assertEquals(x.hashCode(), y.hashCode());
2167         }
2168         if (x instanceof List || x instanceof Deque) {
2169             assertTrue(Arrays.equals(x.toArray(), y.toArray()));
2170             assertTrue(Arrays.equals(x.toArray(new Object[0]),
2171                                      y.toArray(new Object[0])));
2172         }
2173     }
2174 
2175     /**
2176      * A weaker form of assertCollectionsEquals which does not insist
2177      * that the two collections satisfy Object#equals(Object), since
2178      * they may use identity semantics as Deques do.
2179      */
2180     void assertCollectionsEquivalent(Collection<?> x, Collection<?> y) {
2181         if (x instanceof List || x instanceof Set)
2182             assertCollectionsEquals(x, y);
2183         else {
2184             assertEquals(x.isEmpty(), y.isEmpty());
2185             assertEquals(x.size(), y.size());
2186             assertEquals(new HashSet(x), new HashSet(y));
2187             if (x instanceof Deque) {
2188                 assertTrue(Arrays.equals(x.toArray(), y.toArray()));
2189                 assertTrue(Arrays.equals(x.toArray(new Object[0]),
2190                                          y.toArray(new Object[0])));
2191             }
2192         }
2193     }
2194 }