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