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             SystemTest.suite(),
 606             ThreadLocalTest.suite(),
 607             ThreadPoolExecutorTest.suite(),
 608             ThreadPoolExecutorSubclassTest.suite(),
 609             ThreadTest.suite(),
 610             TimeUnitTest.suite(),
 611             TreeMapTest.suite(),
 612             TreeSetTest.suite(),
 613             TreeSubMapTest.suite(),
 614             TreeSubSetTest.suite(),
 615             VectorTest.suite());
 616 
 617         // Java8+ test classes
 618         if (atLeastJava8()) {
 619             String[] java8TestClassNames = {
 620                 "ArrayDeque8Test",
 621                 "Atomic8Test",
 622                 "CompletableFutureTest",
 623                 "ConcurrentHashMap8Test",
 624                 "CountedCompleter8Test",
 625                 "DoubleAccumulatorTest",
 626                 "DoubleAdderTest",
 627                 "ForkJoinPool8Test",
 628                 "ForkJoinTask8Test",
 629                 "HashMapTest",
 630                 "LinkedBlockingDeque8Test",
 631                 "LinkedBlockingQueue8Test",
 632                 "LinkedHashMapTest",
 633                 "LongAccumulatorTest",
 634                 "LongAdderTest",
 635                 "SplittableRandomTest",
 636                 "StampedLockTest",
 637                 "SubmissionPublisherTest",
 638                 "ThreadLocalRandom8Test",
 639                 "TimeUnit8Test",
 640             };
 641             addNamedTestClasses(suite, java8TestClassNames);
 642         }
 643 
 644         // Java9+ test classes
 645         if (atLeastJava9()) {
 646             String[] java9TestClassNames = {
 647                 "AtomicBoolean9Test",
 648                 "AtomicInteger9Test",
 649                 "AtomicIntegerArray9Test",
 650                 "AtomicLong9Test",
 651                 "AtomicLongArray9Test",
 652                 "AtomicReference9Test",
 653                 "AtomicReferenceArray9Test",
 654                 "ExecutorCompletionService9Test",
 655                 "ForkJoinPool9Test",
 656             };
 657             addNamedTestClasses(suite, java9TestClassNames);
 658         }
 659 
 660         if (atLeastJava19()) {
 661             String[] java19TestClassNames = {
 662                 "ForkJoinPool19Test",
 663             };
 664             addNamedTestClasses(suite, java19TestClassNames);
 665         }
 666 
 667         if (atLeastJava20()) {
 668             String[] java20TestClassNames = {
 669                 "ForkJoinPool20Test",
 670             };
 671             addNamedTestClasses(suite, java20TestClassNames);
 672         }
 673 
 674         return suite;
 675     }
 676 
 677     /** Returns list of junit-style test method names in given class. */
 678     public static ArrayList<String> testMethodNames(Class<?> testClass) {
 679         Method[] methods = testClass.getDeclaredMethods();
 680         ArrayList<String> names = new ArrayList<>(methods.length);
 681         for (Method method : methods) {
 682             if (method.getName().startsWith("test")
 683                 && Modifier.isPublic(method.getModifiers())
 684                 // method.getParameterCount() requires jdk8+
 685                 && method.getParameterTypes().length == 0) {
 686                 names.add(method.getName());
 687             }
 688         }
 689         return names;
 690     }
 691 
 692     /**
 693      * Returns junit-style testSuite for the given test class, but
 694      * parameterized by passing extra data to each test.
 695      */
 696     public static <ExtraData> Test parameterizedTestSuite
 697         (Class<? extends JSR166TestCase> testClass,
 698          Class<ExtraData> dataClass,
 699          ExtraData data) {
 700         try {
 701             TestSuite suite = new TestSuite();
 702             Constructor c =
 703                 testClass.getDeclaredConstructor(dataClass, String.class);
 704             for (String methodName : testMethodNames(testClass))
 705                 suite.addTest((Test) c.newInstance(data, methodName));
 706             return suite;
 707         } catch (ReflectiveOperationException e) {
 708             throw new AssertionError(e);
 709         }
 710     }
 711 
 712     /**
 713      * Returns junit-style testSuite for the jdk8 extension of the
 714      * given test class, but parameterized by passing extra data to
 715      * each test.  Uses reflection to allow compilation in jdk7.
 716      */
 717     public static <ExtraData> Test jdk8ParameterizedTestSuite
 718         (Class<? extends JSR166TestCase> testClass,
 719          Class<ExtraData> dataClass,
 720          ExtraData data) {
 721         if (atLeastJava8()) {
 722             String name = testClass.getName();
 723             String name8 = name.replaceAll("Test$", "8Test");
 724             if (name.equals(name8)) throw new AssertionError(name);
 725             try {
 726                 return (Test)
 727                     Class.forName(name8)
 728                     .getMethod("testSuite", dataClass)
 729                     .invoke(null, data);
 730             } catch (ReflectiveOperationException e) {
 731                 throw new AssertionError(e);
 732             }
 733         } else {
 734             return new TestSuite();
 735         }
 736     }
 737 
 738     // Delays for timing-dependent tests, in milliseconds.
 739 
 740     public static long SHORT_DELAY_MS;
 741     public static long SMALL_DELAY_MS;
 742     public static long MEDIUM_DELAY_MS;
 743     public static long LONG_DELAY_MS;
 744 
 745     /**
 746      * A delay significantly longer than LONG_DELAY_MS.
 747      * Use this in a thread that is waited for via awaitTermination(Thread).
 748      */
 749     public static long LONGER_DELAY_MS;
 750 
 751     private static final long RANDOM_TIMEOUT;
 752     private static final long RANDOM_EXPIRED_TIMEOUT;
 753     private static final TimeUnit RANDOM_TIMEUNIT;
 754     static {
 755         ThreadLocalRandom rnd = ThreadLocalRandom.current();
 756         long[] timeouts = { Long.MIN_VALUE, -1, 0, 1, Long.MAX_VALUE };
 757         RANDOM_TIMEOUT = timeouts[rnd.nextInt(timeouts.length)];
 758         RANDOM_EXPIRED_TIMEOUT = timeouts[rnd.nextInt(3)];
 759         TimeUnit[] timeUnits = TimeUnit.values();
 760         RANDOM_TIMEUNIT = timeUnits[rnd.nextInt(timeUnits.length)];
 761     }
 762 
 763     /**
 764      * Returns a timeout for use when any value at all will do.
 765      */
 766     static long randomTimeout() { return RANDOM_TIMEOUT; }
 767 
 768     /**
 769      * Returns a timeout that means "no waiting", i.e. not positive.
 770      */
 771     static long randomExpiredTimeout() { return RANDOM_EXPIRED_TIMEOUT; }
 772 
 773     /**
 774      * Returns a random non-null TimeUnit.
 775      */
 776     static TimeUnit randomTimeUnit() { return RANDOM_TIMEUNIT; }
 777 
 778     /**
 779      * Returns a random boolean; a "coin flip".
 780      */
 781     static boolean randomBoolean() {
 782         return ThreadLocalRandom.current().nextBoolean();
 783     }
 784 
 785     /**
 786      * Returns a random element from given choices.
 787      */
 788     <T> T chooseRandomly(List<T> choices) {
 789         return choices.get(ThreadLocalRandom.current().nextInt(choices.size()));
 790     }
 791 
 792     /**
 793      * Returns a random element from given choices.
 794      */
 795     @SuppressWarnings("unchecked")
 796     <T> T chooseRandomly(T... choices) {
 797         return choices[ThreadLocalRandom.current().nextInt(choices.length)];
 798     }
 799 
 800     /**
 801      * Returns the shortest timed delay. This can be scaled up for
 802      * slow machines using the jsr166.delay.factor system property,
 803      * or via jtreg's -timeoutFactor: flag.
 804      * https://openjdk.org/jtreg/command-help.html
 805      */
 806     protected long getShortDelay() {
 807         return (long) (50 * delayFactor);
 808     }
 809 
 810     /**
 811      * Sets delays as multiples of SHORT_DELAY.
 812      */
 813     protected void setDelays() {
 814         SHORT_DELAY_MS = getShortDelay();
 815         SMALL_DELAY_MS  = SHORT_DELAY_MS * 5;
 816         MEDIUM_DELAY_MS = SHORT_DELAY_MS * 10;
 817         LONG_DELAY_MS   = SHORT_DELAY_MS * 200;
 818         LONGER_DELAY_MS = 2 * LONG_DELAY_MS;
 819     }
 820 
 821     private static final long TIMEOUT_DELAY_MS
 822         = (long) (12.0 * Math.cbrt(delayFactor));
 823 
 824     /**
 825      * Returns a timeout in milliseconds to be used in tests that verify
 826      * that operations block or time out.  We want this to be longer
 827      * than the OS scheduling quantum, but not too long, so don't scale
 828      * linearly with delayFactor; we use "crazy" cube root instead.
 829      */
 830     static long timeoutMillis() {
 831         return TIMEOUT_DELAY_MS;
 832     }
 833 
 834     /**
 835      * Returns a new Date instance representing a time at least
 836      * delayMillis milliseconds in the future.
 837      */
 838     Date delayedDate(long delayMillis) {
 839         // Add 1 because currentTimeMillis is known to round into the past.
 840         return new Date(System.currentTimeMillis() + delayMillis + 1);
 841     }
 842 
 843     /**
 844      * The first exception encountered if any threadAssertXXX method fails.
 845      */
 846     private final AtomicReference<Throwable> threadFailure
 847         = new AtomicReference<>(null);
 848 
 849     /**
 850      * Records an exception so that it can be rethrown later in the test
 851      * harness thread, triggering a test case failure.  Only the first
 852      * failure is recorded; subsequent calls to this method from within
 853      * the same test have no effect.
 854      */
 855     public void threadRecordFailure(Throwable t) {
 856         System.err.println(t);
 857         if (threadFailure.compareAndSet(null, t))
 858             dumpTestThreads();
 859     }
 860 
 861     public void setUp() {
 862         setDelays();
 863     }
 864 
 865     void tearDownFail(String format, Object... args) {
 866         String msg = toString() + ": " + String.format(format, args);
 867         System.err.println(msg);
 868         dumpTestThreads();
 869         throw new AssertionError(msg);
 870     }
 871 
 872     /**
 873      * Extra checks that get done for all test cases.
 874      *
 875      * Triggers test case failure if any thread assertions have failed,
 876      * by rethrowing, in the test harness thread, any exception recorded
 877      * earlier by threadRecordFailure.
 878      *
 879      * Triggers test case failure if interrupt status is set in the main thread.
 880      */
 881     public void tearDown() throws Exception {
 882         Throwable t = threadFailure.getAndSet(null);
 883         if (t != null) {
 884             if (t instanceof Error)
 885                 throw (Error) t;
 886             else if (t instanceof RuntimeException)
 887                 throw (RuntimeException) t;
 888             else if (t instanceof Exception)
 889                 throw (Exception) t;
 890             else
 891                 throw new AssertionError(t.toString(), t);
 892         }
 893 
 894         if (Thread.interrupted())
 895             tearDownFail("interrupt status set in main thread");
 896 
 897         checkForkJoinPoolThreadLeaks();
 898     }
 899 
 900     /**
 901      * Finds missing PoolCleaners
 902      */
 903     void checkForkJoinPoolThreadLeaks() throws InterruptedException {
 904         Thread[] survivors = new Thread[7];
 905         int count = Thread.enumerate(survivors);
 906         for (int i = 0; i < count; i++) {
 907             Thread thread = survivors[i];
 908             String name = thread.getName();
 909             if (name.startsWith("ForkJoinPool-")) {
 910                 // give thread some time to terminate
 911                 thread.join(LONG_DELAY_MS);
 912                 if (thread.isAlive())
 913                     tearDownFail("Found leaked ForkJoinPool thread thread=%s",
 914                                  thread);
 915             }
 916         }
 917 
 918         if (!ForkJoinPool.commonPool()
 919             .awaitQuiescence(LONG_DELAY_MS, MILLISECONDS))
 920             tearDownFail("ForkJoin common pool thread stuck");
 921     }
 922 
 923     /**
 924      * Just like fail(reason), but additionally recording (using
 925      * threadRecordFailure) any AssertionError thrown, so that the
 926      * current testcase will fail.
 927      */
 928     public void threadFail(String reason) {
 929         try {
 930             fail(reason);
 931         } catch (AssertionError fail) {
 932             threadRecordFailure(fail);
 933             throw fail;
 934         }
 935     }
 936 
 937     /**
 938      * Just like assertTrue(b), but additionally recording (using
 939      * threadRecordFailure) any AssertionError thrown, so that the
 940      * current testcase will fail.
 941      */
 942     public void threadAssertTrue(boolean b) {
 943         try {
 944             assertTrue(b);
 945         } catch (AssertionError fail) {
 946             threadRecordFailure(fail);
 947             throw fail;
 948         }
 949     }
 950 
 951     /**
 952      * Just like assertFalse(b), but additionally recording (using
 953      * threadRecordFailure) any AssertionError thrown, so that the
 954      * current testcase will fail.
 955      */
 956     public void threadAssertFalse(boolean b) {
 957         try {
 958             assertFalse(b);
 959         } catch (AssertionError fail) {
 960             threadRecordFailure(fail);
 961             throw fail;
 962         }
 963     }
 964 
 965     /**
 966      * Just like assertNull(x), but additionally recording (using
 967      * threadRecordFailure) any AssertionError thrown, so that the
 968      * current testcase will fail.
 969      */
 970     public void threadAssertNull(Object x) {
 971         try {
 972             assertNull(x);
 973         } catch (AssertionError fail) {
 974             threadRecordFailure(fail);
 975             throw fail;
 976         }
 977     }
 978 
 979     /**
 980      * Just like assertEquals(x, y), but additionally recording (using
 981      * threadRecordFailure) any AssertionError thrown, so that the
 982      * current testcase will fail.
 983      */
 984     public void threadAssertEquals(long x, long y) {
 985         try {
 986             assertEquals(x, y);
 987         } catch (AssertionError fail) {
 988             threadRecordFailure(fail);
 989             throw fail;
 990         }
 991     }
 992 
 993     /**
 994      * Just like assertEquals(x, y), but additionally recording (using
 995      * threadRecordFailure) any AssertionError thrown, so that the
 996      * current testcase will fail.
 997      */
 998     public void threadAssertEquals(Object x, Object y) {
 999         try {
1000             assertEquals(x, y);
1001         } catch (AssertionError fail) {
1002             threadRecordFailure(fail);
1003             throw fail;
1004         } catch (Throwable fail) {
1005             threadUnexpectedException(fail);
1006         }
1007     }
1008 
1009     /**
1010      * Just like assertSame(x, y), but additionally recording (using
1011      * threadRecordFailure) any AssertionError thrown, so that the
1012      * current testcase will fail.
1013      */
1014     public void threadAssertSame(Object x, Object y) {
1015         try {
1016             assertSame(x, y);
1017         } catch (AssertionError fail) {
1018             threadRecordFailure(fail);
1019             throw fail;
1020         }
1021     }
1022 
1023     /**
1024      * Calls threadFail with message "should throw exception".
1025      */
1026     public void threadShouldThrow() {
1027         threadFail("should throw exception");
1028     }
1029 
1030     /**
1031      * Calls threadFail with message "should throw" + exceptionName.
1032      */
1033     public void threadShouldThrow(String exceptionName) {
1034         threadFail("should throw " + exceptionName);
1035     }
1036 
1037     /**
1038      * Records the given exception using {@link #threadRecordFailure},
1039      * then rethrows the exception, wrapping it in an AssertionError
1040      * if necessary.
1041      */
1042     public void threadUnexpectedException(Throwable t) {
1043         threadRecordFailure(t);
1044         t.printStackTrace();
1045         if (t instanceof RuntimeException)
1046             throw (RuntimeException) t;
1047         else if (t instanceof Error)
1048             throw (Error) t;
1049         else
1050             throw new AssertionError("unexpected exception: " + t, t);
1051     }
1052 
1053     /**
1054      * Delays, via Thread.sleep, for the given millisecond delay, but
1055      * if the sleep is shorter than specified, may re-sleep or yield
1056      * until time elapses.  Ensures that the given time, as measured
1057      * by System.nanoTime(), has elapsed.
1058      */
1059     static void delay(long millis) throws InterruptedException {
1060         long nanos = millis * (1000 * 1000);
1061         final long wakeupTime = System.nanoTime() + nanos;
1062         do {
1063             if (millis > 0L)
1064                 Thread.sleep(millis);
1065             else // too short to sleep
1066                 Thread.yield();
1067             nanos = wakeupTime - System.nanoTime();
1068             millis = nanos / (1000 * 1000);
1069         } while (nanos >= 0L);
1070     }
1071 
1072     /**
1073      * Allows use of try-with-resources with per-test thread pools.
1074      */
1075     class PoolCleaner implements AutoCloseable {
1076         private final ExecutorService pool;
1077         public PoolCleaner(ExecutorService pool) { this.pool = pool; }
1078         public void close() { joinPool(pool); }
1079     }
1080 
1081     /**
1082      * An extension of PoolCleaner that has an action to release the pool.
1083      */
1084     class PoolCleanerWithReleaser extends PoolCleaner {
1085         private final Runnable releaser;
1086         public PoolCleanerWithReleaser(ExecutorService pool, Runnable releaser) {
1087             super(pool);
1088             this.releaser = releaser;
1089         }
1090         public void close() {
1091             try {
1092                 releaser.run();
1093             } finally {
1094                 super.close();
1095             }
1096         }
1097     }
1098 
1099     PoolCleaner cleaner(ExecutorService pool) {
1100         return new PoolCleaner(pool);
1101     }
1102 
1103     PoolCleaner cleaner(ExecutorService pool, Runnable releaser) {
1104         return new PoolCleanerWithReleaser(pool, releaser);
1105     }
1106 
1107     PoolCleaner cleaner(ExecutorService pool, CountDownLatch latch) {
1108         return new PoolCleanerWithReleaser(pool, releaser(latch));
1109     }
1110 
1111     Runnable releaser(final CountDownLatch latch) {
1112         return new Runnable() { public void run() {
1113             do { latch.countDown(); }
1114             while (latch.getCount() > 0);
1115         }};
1116     }
1117 
1118     PoolCleaner cleaner(ExecutorService pool, AtomicBoolean flag) {
1119         return new PoolCleanerWithReleaser(pool, releaser(flag));
1120     }
1121 
1122     Runnable releaser(final AtomicBoolean flag) {
1123         return new Runnable() { public void run() { flag.set(true); }};
1124     }
1125 
1126     /**
1127      * Waits out termination of a thread pool or fails doing so.
1128      */
1129     void joinPool(ExecutorService pool) {
1130         try {
1131             pool.shutdown();
1132             if (!pool.awaitTermination(20 * LONG_DELAY_MS, MILLISECONDS)) {
1133                 try {
1134                     threadFail("ExecutorService " + pool +
1135                                " did not terminate in a timely manner");
1136                 } finally {
1137                     // last resort, for the benefit of subsequent tests
1138                     pool.shutdownNow();
1139                     pool.awaitTermination(MEDIUM_DELAY_MS, MILLISECONDS);
1140                 }
1141             }
1142         } catch (SecurityException ok) {
1143             // Allowed in case test doesn't have privs
1144         } catch (InterruptedException fail) {
1145             threadFail("Unexpected InterruptedException");
1146         }
1147     }
1148 
1149     /**
1150      * Like Runnable, but with the freedom to throw anything.
1151      * junit folks had the same idea:
1152      * http://junit.org/junit5/docs/snapshot/api/org/junit/gen5/api/Executable.html
1153      */
1154     interface Action { public void run() throws Throwable; }
1155 
1156     /**
1157      * Runs all the given actions in parallel, failing if any fail.
1158      * Useful for running multiple variants of tests that are
1159      * necessarily individually slow because they must block.
1160      */
1161     void testInParallel(Action ... actions) {
1162         ExecutorService pool = Executors.newCachedThreadPool();
1163         try (PoolCleaner cleaner = cleaner(pool)) {
1164             ArrayList<Future<?>> futures = new ArrayList<>(actions.length);
1165             for (final Action action : actions)
1166                 futures.add(pool.submit(new CheckedRunnable() {
1167                     public void realRun() throws Throwable { action.run();}}));
1168             for (Future<?> future : futures)
1169                 try {
1170                     assertNull(future.get(LONG_DELAY_MS, MILLISECONDS));
1171                 } catch (ExecutionException ex) {
1172                     threadUnexpectedException(ex.getCause());
1173                 } catch (Exception ex) {
1174                     threadUnexpectedException(ex);
1175                 }
1176         }
1177     }
1178 
1179     /** Returns true if thread info might be useful in a thread dump. */
1180     static boolean threadOfInterest(ThreadInfo info) {
1181         final String name = info.getThreadName();
1182         String lockName;
1183         if (name == null)
1184             return true;
1185         if (name.equals("Signal Dispatcher")
1186             || name.equals("WedgedTestDetector"))
1187             return false;
1188         if (name.equals("Reference Handler")) {
1189             // Reference Handler stacktrace changed in JDK-8156500
1190             StackTraceElement[] stackTrace; String methodName;
1191             if ((stackTrace = info.getStackTrace()) != null
1192                 && stackTrace.length > 0
1193                 && (methodName = stackTrace[0].getMethodName()) != null
1194                 && methodName.equals("waitForReferencePendingList"))
1195                 return false;
1196             // jdk8 Reference Handler stacktrace
1197             if ((lockName = info.getLockName()) != null
1198                 && lockName.startsWith("java.lang.ref"))
1199                 return false;
1200         }
1201         if ((name.equals("Finalizer") || name.equals("Common-Cleaner"))
1202             && (lockName = info.getLockName()) != null
1203             && lockName.startsWith("java.lang.ref"))
1204             return false;
1205         if (name.startsWith("ForkJoinPool.commonPool-worker")
1206             && (lockName = info.getLockName()) != null
1207             && lockName.startsWith("java.util.concurrent.ForkJoinPool"))
1208             return false;
1209         return true;
1210     }
1211 
1212     /**
1213      * A debugging tool to print stack traces of most threads, as jstack does.
1214      * Uninteresting threads are filtered out.
1215      */
1216     @SuppressWarnings("removal")
1217     static void dumpTestThreads() {
1218         SecurityManager sm = System.getSecurityManager();
1219         if (sm != null) {
1220             try {
1221                 System.setSecurityManager(null);
1222             } catch (SecurityException giveUp) {
1223                 return;
1224             }
1225         }
1226 
1227         System.err.println("------ stacktrace dump start ------");
1228         for (ThreadInfo info : THREAD_MXBEAN.dumpAllThreads(true, true))
1229             if (threadOfInterest(info))
1230                 System.err.print(info);
1231         System.err.println("------ stacktrace dump end ------");
1232 
1233         if (sm != null) System.setSecurityManager(sm);
1234     }
1235 
1236     /**
1237      * Checks that thread eventually enters the expected blocked thread state.
1238      */
1239     void assertThreadBlocks(Thread thread, Thread.State expected) {
1240         // always sleep at least 1 ms, with high probability avoiding
1241         // transitory states
1242         for (long retries = LONG_DELAY_MS * 3 / 4; retries-->0; ) {
1243             try { delay(1); }
1244             catch (InterruptedException fail) {
1245                 throw new AssertionError("Unexpected InterruptedException", fail);
1246             }
1247             Thread.State s = thread.getState();
1248             if (s == expected)
1249                 return;
1250             else if (s == Thread.State.TERMINATED)
1251                 fail("Unexpected thread termination");
1252         }
1253         fail("timed out waiting for thread to enter thread state " + expected);
1254     }
1255 
1256     /**
1257      * Returns the thread's blocker's class name, if any, else null.
1258      */
1259     String blockerClassName(Thread thread) {
1260         ThreadInfo threadInfo; LockInfo lockInfo;
1261         if ((threadInfo = THREAD_MXBEAN.getThreadInfo(thread.getId(), 0)) != null
1262             && (lockInfo = threadInfo.getLockInfo()) != null)
1263             return lockInfo.getClassName();
1264         return null;
1265     }
1266 
1267     /**
1268      * Checks that future.get times out, with the default timeout of
1269      * {@code timeoutMillis()}.
1270      */
1271     void assertFutureTimesOut(Future<?> future) {
1272         assertFutureTimesOut(future, timeoutMillis());
1273     }
1274 
1275     /**
1276      * Checks that future.get times out, with the given millisecond timeout.
1277      */
1278     void assertFutureTimesOut(Future<?> future, long timeoutMillis) {
1279         long startTime = System.nanoTime();
1280         try {
1281             future.get(timeoutMillis, MILLISECONDS);
1282             shouldThrow();
1283         } catch (TimeoutException success) {
1284         } catch (Exception fail) {
1285             threadUnexpectedException(fail);
1286         }
1287         assertTrue(millisElapsedSince(startTime) >= timeoutMillis);
1288         assertFalse(future.isDone());
1289     }
1290 
1291     /**
1292      * Fails with message "should throw exception".
1293      */
1294     public void shouldThrow() {
1295         fail("Should throw exception");
1296     }
1297 
1298     /**
1299      * Fails with message "should throw " + exceptionName.
1300      */
1301     public void shouldThrow(String exceptionName) {
1302         fail("Should throw " + exceptionName);
1303     }
1304 
1305     /**
1306      * The maximum number of consecutive spurious wakeups we should
1307      * tolerate (from APIs like LockSupport.park) before failing a test.
1308      */
1309     static final int MAX_SPURIOUS_WAKEUPS = 10;
1310 
1311     /**
1312      * The number of elements to place in collections, arrays, etc.
1313      * Must be at least ten;
1314      */
1315     public static final int SIZE = 32;
1316 
1317     static Item[] seqItems(int size) {
1318         Item[] s = new Item[size];
1319         for (int i = 0; i < size; ++i)
1320             s[i] = new Item(i);
1321         return s;
1322     }
1323     static Item[] negativeSeqItems(int size) {
1324         Item[] s = new Item[size];
1325         for (int i = 0; i < size; ++i)
1326             s[i] = new Item(-i);
1327         return s;
1328     }
1329 
1330     // Many tests rely on defaultItems all being sequential nonnegative
1331     public static final Item[] defaultItems = seqItems(SIZE);
1332 
1333     static Item itemFor(int i) { // check cache for defaultItems
1334         Item[] items = defaultItems;
1335         return (i >= 0 && i < items.length) ? items[i] : new Item(i);
1336     }
1337 
1338     public static final Item zero  = defaultItems[0];
1339     public static final Item one   = defaultItems[1];
1340     public static final Item two   = defaultItems[2];
1341     public static final Item three = defaultItems[3];
1342     public static final Item four  = defaultItems[4];
1343     public static final Item five  = defaultItems[5];
1344     public static final Item six   = defaultItems[6];
1345     public static final Item seven = defaultItems[7];
1346     public static final Item eight = defaultItems[8];
1347     public static final Item nine  = defaultItems[9];
1348     public static final Item ten   = defaultItems[10];
1349 
1350     public static final Item[] negativeItems = negativeSeqItems(SIZE);
1351 
1352     public static final Item minusOne   = negativeItems[1];
1353     public static final Item minusTwo   = negativeItems[2];
1354     public static final Item minusThree = negativeItems[3];
1355     public static final Item minusFour  = negativeItems[4];
1356     public static final Item minusFive  = negativeItems[5];
1357     public static final Item minusSix   = negativeItems[6];
1358     public static final Item minusSeven = negativeItems[7];
1359     public static final Item minusEight = negativeItems[8];
1360     public static final Item minusNone  = negativeItems[9];
1361     public static final Item minusTen   = negativeItems[10];
1362 
1363     // elements expected to be missing
1364     public static final Item fortytwo = new Item(42);
1365     public static final Item eightysix = new Item(86);
1366     public static final Item ninetynine = new Item(99);
1367 
1368     // Interop across Item, int
1369 
1370     static void mustEqual(Item x, Item y) {
1371         if (x != y)
1372             assertEquals(x.value, y.value);
1373     }
1374     static void mustEqual(Item x, int y) {
1375         assertEquals(x.value, y);
1376     }
1377     static void mustEqual(int x, Item y) {
1378         assertEquals(x, y.value);
1379     }
1380     static void mustEqual(int x, int y) {
1381         assertEquals(x, y);
1382     }
1383     static void mustEqual(Object x, Object y) {
1384         if (x != y)
1385             assertEquals(x, y);
1386     }
1387     static void mustEqual(int x, Object y) {
1388         if (y instanceof Item)
1389             assertEquals(x, ((Item)y).value);
1390         else fail();
1391     }
1392     static void mustEqual(Object x, int y) {
1393         if (x instanceof Item)
1394             assertEquals(((Item)x).value, y);
1395         else fail();
1396     }
1397     static void mustEqual(boolean x, boolean y) {
1398         assertEquals(x, y);
1399     }
1400     static void mustEqual(long x, long y) {
1401         assertEquals(x, y);
1402     }
1403     static void mustEqual(double x, double y) {
1404         assertEquals(x, y);
1405     }
1406     static void mustContain(Collection<Item> c, int i) {
1407         assertTrue(c.contains(itemFor(i)));
1408     }
1409     static void mustContain(Collection<Item> c, Item i) {
1410         assertTrue(c.contains(i));
1411     }
1412     static void mustNotContain(Collection<Item> c, int i) {
1413         assertFalse(c.contains(itemFor(i)));
1414     }
1415     static void mustNotContain(Collection<Item> c, Item i) {
1416         assertFalse(c.contains(i));
1417     }
1418     static void mustRemove(Collection<Item> c, int i) {
1419         assertTrue(c.remove(itemFor(i)));
1420     }
1421     static void mustRemove(Collection<Item> c, Item i) {
1422         assertTrue(c.remove(i));
1423     }
1424     static void mustNotRemove(Collection<Item> c, int i) {
1425         assertFalse(c.remove(itemFor(i)));
1426     }
1427     static void mustNotRemove(Collection<Item> c, Item i) {
1428         assertFalse(c.remove(i));
1429     }
1430     static void mustAdd(Collection<Item> c, int i) {
1431         assertTrue(c.add(itemFor(i)));
1432     }
1433     static void mustAdd(Collection<Item> c, Item i) {
1434         assertTrue(c.add(i));
1435     }
1436     static void mustOffer(Queue<Item> c, int i) {
1437         assertTrue(c.offer(itemFor(i)));
1438     }
1439     static void mustOffer(Queue<Item> c, Item i) {
1440         assertTrue(c.offer(i));
1441     }
1442 
1443     /**
1444      * Runs Runnable r with a security policy that permits precisely
1445      * the specified permissions.  If there is no current security
1446      * manager, the runnable is run twice, both with and without a
1447      * security manager.  We require that any security manager permit
1448      * getPolicy/setPolicy.
1449      */
1450     @SuppressWarnings("removal")
1451     public void runWithPermissions(Runnable r, Permission... permissions) {
1452         SecurityManager sm = System.getSecurityManager();
1453         if (sm == null) {
1454             r.run();
1455         }
1456         runWithSecurityManagerWithPermissions(r, permissions);
1457     }
1458 
1459     /**
1460      * Runs Runnable r with a security policy that permits precisely
1461      * the specified permissions.  If there is no current security
1462      * manager, a temporary one is set for the duration of the
1463      * Runnable.  We require that any security manager permit
1464      * getPolicy/setPolicy.
1465      */
1466     @SuppressWarnings("removal")
1467     public void runWithSecurityManagerWithPermissions(Runnable r,
1468                                                       Permission... permissions) {
1469         if (!useSecurityManager) return;
1470         SecurityManager sm = System.getSecurityManager();
1471         if (sm == null) {
1472             Policy savedPolicy = Policy.getPolicy();
1473             try {
1474                 Policy.setPolicy(permissivePolicy());
1475                 System.setSecurityManager(new SecurityManager());
1476                 runWithSecurityManagerWithPermissions(r, permissions);
1477             } catch (UnsupportedOperationException ok) {
1478             } finally {
1479                 try {
1480                     System.setSecurityManager(null);
1481                     Policy.setPolicy(savedPolicy);
1482                 } catch (Exception ok) {
1483                 }
1484             }
1485         } else {
1486             Policy savedPolicy = Policy.getPolicy();
1487             AdjustablePolicy policy = new AdjustablePolicy(permissions);
1488             Policy.setPolicy(policy);
1489 
1490             try {
1491                 r.run();
1492             } finally {
1493                 policy.addPermission(new SecurityPermission("setPolicy"));
1494                 Policy.setPolicy(savedPolicy);
1495             }
1496         }
1497     }
1498 
1499     /**
1500      * Runs a runnable without any permissions.
1501      */
1502     public void runWithoutPermissions(Runnable r) {
1503         runWithPermissions(r);
1504     }
1505 
1506     /**
1507      * A security policy where new permissions can be dynamically added
1508      * or all cleared.
1509      */
1510     @SuppressWarnings("removal")
1511     public static class AdjustablePolicy extends java.security.Policy {
1512         Permissions perms = new Permissions();
1513         AdjustablePolicy(Permission... permissions) {
1514             for (Permission permission : permissions)
1515                 perms.add(permission);
1516         }
1517         void addPermission(Permission perm) { perms.add(perm); }
1518         void clearPermissions() { perms = new Permissions(); }
1519         public PermissionCollection getPermissions(CodeSource cs) {
1520             return perms;
1521         }
1522         public PermissionCollection getPermissions(ProtectionDomain pd) {
1523             return perms;
1524         }
1525         public boolean implies(ProtectionDomain pd, Permission p) {
1526             return perms.implies(p);
1527         }
1528         public void refresh() {}
1529         public String toString() {
1530             List<Permission> ps = new ArrayList<>();
1531             for (Enumeration<Permission> e = perms.elements(); e.hasMoreElements();)
1532                 ps.add(e.nextElement());
1533             return "AdjustablePolicy with permissions " + ps;
1534         }
1535     }
1536 
1537     /**
1538      * Returns a policy containing all the permissions we ever need.
1539      */
1540     @SuppressWarnings("removal")
1541     public static Policy permissivePolicy() {
1542         return new AdjustablePolicy
1543             // Permissions j.u.c. needs directly
1544             (new RuntimePermission("modifyThread"),
1545              new RuntimePermission("getClassLoader"),
1546              new RuntimePermission("setContextClassLoader"),
1547              // Permissions needed to change permissions!
1548              new SecurityPermission("getPolicy"),
1549              new SecurityPermission("setPolicy"),
1550              new RuntimePermission("setSecurityManager"),
1551              // Permissions needed by the junit test harness
1552              new RuntimePermission("accessDeclaredMembers"),
1553              new PropertyPermission("*", "read"),
1554              new java.io.FilePermission("<<ALL FILES>>", "read"));
1555     }
1556 
1557     /**
1558      * Sleeps until the given time has elapsed.
1559      * Throws AssertionError if interrupted.
1560      */
1561     static void sleep(long millis) {
1562         try {
1563             delay(millis);
1564         } catch (InterruptedException fail) {
1565             throw new AssertionError("Unexpected InterruptedException", fail);
1566         }
1567     }
1568 
1569     /**
1570      * Spin-waits up to the specified number of milliseconds for the given
1571      * thread to enter a wait state: BLOCKED, WAITING, or TIMED_WAITING.
1572      * @param waitingForGodot if non-null, an additional condition to satisfy
1573      */
1574     void waitForThreadToEnterWaitState(Thread thread, long timeoutMillis,
1575                                        Callable<Boolean> waitingForGodot) {
1576         for (long startTime = 0L;;) {
1577             switch (thread.getState()) {
1578             default: break;
1579             case BLOCKED: case WAITING: case TIMED_WAITING:
1580                 try {
1581                     if (waitingForGodot == null || waitingForGodot.call())
1582                         return;
1583                 } catch (Throwable fail) { threadUnexpectedException(fail); }
1584                 break;
1585             case TERMINATED:
1586                 fail("Unexpected thread termination");
1587             }
1588 
1589             if (startTime == 0L)
1590                 startTime = System.nanoTime();
1591             else if (millisElapsedSince(startTime) > timeoutMillis) {
1592                 assertTrue(thread.isAlive());
1593                 if (waitingForGodot == null
1594                     || thread.getState() == Thread.State.RUNNABLE)
1595                     fail("timed out waiting for thread to enter wait state");
1596                 else
1597                     fail("timed out waiting for condition, thread state="
1598                          + thread.getState());
1599             }
1600             Thread.yield();
1601         }
1602     }
1603 
1604     /**
1605      * Spin-waits up to the specified number of milliseconds for the given
1606      * thread to enter a wait state: BLOCKED, WAITING, or TIMED_WAITING.
1607      */
1608     void waitForThreadToEnterWaitState(Thread thread, long timeoutMillis) {
1609         waitForThreadToEnterWaitState(thread, timeoutMillis, null);
1610     }
1611 
1612     /**
1613      * Spin-waits up to LONG_DELAY_MS milliseconds for the given thread to
1614      * enter a wait state: BLOCKED, WAITING, or TIMED_WAITING.
1615      */
1616     void waitForThreadToEnterWaitState(Thread thread) {
1617         waitForThreadToEnterWaitState(thread, LONG_DELAY_MS, null);
1618     }
1619 
1620     /**
1621      * Spin-waits up to LONG_DELAY_MS milliseconds for the given thread to
1622      * enter a wait state: BLOCKED, WAITING, or TIMED_WAITING,
1623      * and additionally satisfy the given condition.
1624      */
1625     void waitForThreadToEnterWaitState(Thread thread,
1626                                        Callable<Boolean> waitingForGodot) {
1627         waitForThreadToEnterWaitState(thread, LONG_DELAY_MS, waitingForGodot);
1628     }
1629 
1630     /**
1631      * Spin-waits up to LONG_DELAY_MS milliseconds for the current thread to
1632      * be interrupted.  Clears the interrupt status before returning.
1633      */
1634     void awaitInterrupted() {
1635         for (long startTime = 0L; !Thread.interrupted(); ) {
1636             if (startTime == 0L)
1637                 startTime = System.nanoTime();
1638             else if (millisElapsedSince(startTime) > LONG_DELAY_MS)
1639                 fail("timed out waiting for thread interrupt");
1640             Thread.yield();
1641         }
1642     }
1643 
1644     /**
1645      * Returns the number of milliseconds since time given by
1646      * startNanoTime, which must have been previously returned from a
1647      * call to {@link System#nanoTime()}.
1648      */
1649     static long millisElapsedSince(long startNanoTime) {
1650         return NANOSECONDS.toMillis(System.nanoTime() - startNanoTime);
1651     }
1652 
1653     /**
1654      * Checks that timed f.get() returns the expected value, and does not
1655      * wait for the timeout to elapse before returning.
1656      */
1657     <T> void checkTimedGet(Future<T> f, T expectedValue, long timeoutMillis) {
1658         long startTime = System.nanoTime();
1659         T actual = null;
1660         try {
1661             actual = f.get(timeoutMillis, MILLISECONDS);
1662         } catch (Throwable fail) { threadUnexpectedException(fail); }
1663         assertEquals(expectedValue, actual);
1664         if (millisElapsedSince(startTime) > timeoutMillis/2)
1665             throw new AssertionError("timed get did not return promptly");
1666     }
1667 
1668     <T> void checkTimedGet(Future<T> f, T expectedValue) {
1669         checkTimedGet(f, expectedValue, LONG_DELAY_MS);
1670     }
1671 
1672     /**
1673      * Returns a new started daemon Thread running the given runnable.
1674      */
1675     Thread newStartedThread(Runnable runnable) {
1676         Thread t = new Thread(runnable);
1677         t.setDaemon(true);
1678         t.start();
1679         return t;
1680     }
1681 
1682     /**
1683      * Returns a new started daemon Thread running the given action,
1684      * wrapped in a CheckedRunnable.
1685      */
1686     Thread newStartedThread(Action action) {
1687         return newStartedThread(checkedRunnable(action));
1688     }
1689 
1690     /**
1691      * Waits for the specified time (in milliseconds) for the thread
1692      * to terminate (using {@link Thread#join(long)}), else interrupts
1693      * the thread (in the hope that it may terminate later) and fails.
1694      */
1695     void awaitTermination(Thread thread, long timeoutMillis) {
1696         try {
1697             thread.join(timeoutMillis);
1698         } catch (InterruptedException fail) {
1699             threadUnexpectedException(fail);
1700         }
1701         if (thread.getState() != Thread.State.TERMINATED) {
1702             String detail = String.format(
1703                     "timed out waiting for thread to terminate, thread=%s, state=%s" ,
1704                     thread, thread.getState());
1705             try {
1706                 threadFail(detail);
1707             } finally {
1708                 // Interrupt thread __after__ having reported its stack trace
1709                 thread.interrupt();
1710             }
1711         }
1712     }
1713 
1714     /**
1715      * Waits for LONG_DELAY_MS milliseconds for the thread to
1716      * terminate (using {@link Thread#join(long)}), else interrupts
1717      * the thread (in the hope that it may terminate later) and fails.
1718      */
1719     void awaitTermination(Thread t) {
1720         awaitTermination(t, LONG_DELAY_MS);
1721     }
1722 
1723     // Some convenient Runnable classes
1724 
1725     public abstract class CheckedRunnable implements Runnable {
1726         protected abstract void realRun() throws Throwable;
1727 
1728         public final void run() {
1729             try {
1730                 realRun();
1731             } catch (Throwable fail) {
1732                 threadUnexpectedException(fail);
1733             }
1734         }
1735     }
1736 
1737     Runnable checkedRunnable(Action action) {
1738         return new CheckedRunnable() {
1739             public void realRun() throws Throwable {
1740                 action.run();
1741             }};
1742     }
1743 
1744     public abstract class ThreadShouldThrow extends Thread {
1745         protected abstract void realRun() throws Throwable;
1746 
1747         final Class<?> exceptionClass;
1748 
1749         <T extends Throwable> ThreadShouldThrow(Class<T> exceptionClass) {
1750             this.exceptionClass = exceptionClass;
1751         }
1752 
1753         public final void run() {
1754             try {
1755                 realRun();
1756             } catch (Throwable t) {
1757                 if (! exceptionClass.isInstance(t))
1758                     threadUnexpectedException(t);
1759                 return;
1760             }
1761             threadShouldThrow(exceptionClass.getSimpleName());
1762         }
1763     }
1764 
1765     public abstract class CheckedInterruptedRunnable implements Runnable {
1766         protected abstract void realRun() throws Throwable;
1767 
1768         public final void run() {
1769             try {
1770                 realRun();
1771             } catch (InterruptedException success) {
1772                 threadAssertFalse(Thread.interrupted());
1773                 return;
1774             } catch (Throwable fail) {
1775                 threadUnexpectedException(fail);
1776             }
1777             threadShouldThrow("InterruptedException");
1778         }
1779     }
1780 
1781     public abstract class CheckedCallable<T> implements Callable<T> {
1782         protected abstract T realCall() throws Throwable;
1783 
1784         public final T call() {
1785             try {
1786                 return realCall();
1787             } catch (Throwable fail) {
1788                 threadUnexpectedException(fail);
1789             }
1790             throw new AssertionError("unreached");
1791         }
1792     }
1793 
1794     public static class NoOpRunnable implements Runnable {
1795         public void run() {}
1796     }
1797 
1798     public static class NoOpCallable implements Callable<Object> {
1799         public Object call() { return Boolean.TRUE; }
1800     }
1801 
1802     public static final String TEST_STRING = "a test string";
1803 
1804     public static class StringTask implements Callable<String> {
1805         final String value;
1806         public StringTask() { this(TEST_STRING); }
1807         public StringTask(String value) { this.value = value; }
1808         public String call() { return value; }
1809     }
1810 
1811     public Callable<String> latchAwaitingStringTask(final CountDownLatch latch) {
1812         return new CheckedCallable<String>() {
1813             protected String realCall() {
1814                 try {
1815                     latch.await();
1816                 } catch (InterruptedException quittingTime) {}
1817                 return TEST_STRING;
1818             }};
1819     }
1820 
1821     public Runnable countDowner(final CountDownLatch latch) {
1822         return new CheckedRunnable() {
1823             public void realRun() throws InterruptedException {
1824                 latch.countDown();
1825             }};
1826     }
1827 
1828     class LatchAwaiter extends CheckedRunnable {
1829         static final int NEW = 0;
1830         static final int RUNNING = 1;
1831         static final int DONE = 2;
1832         final CountDownLatch latch;
1833         int state = NEW;
1834         LatchAwaiter(CountDownLatch latch) { this.latch = latch; }
1835         public void realRun() throws InterruptedException {
1836             state = 1;
1837             await(latch);
1838             state = 2;
1839         }
1840     }
1841 
1842     public LatchAwaiter awaiter(CountDownLatch latch) {
1843         return new LatchAwaiter(latch);
1844     }
1845 
1846     public void await(CountDownLatch latch, long timeoutMillis) {
1847         boolean timedOut = false;
1848         try {
1849             timedOut = !latch.await(timeoutMillis, MILLISECONDS);
1850         } catch (Throwable fail) {
1851             threadUnexpectedException(fail);
1852         }
1853         if (timedOut)
1854             fail("timed out waiting for CountDownLatch for "
1855                  + (timeoutMillis/1000) + " sec");
1856     }
1857 
1858     public void await(CountDownLatch latch) {
1859         await(latch, LONG_DELAY_MS);
1860     }
1861 
1862     public void await(Semaphore semaphore) {
1863         boolean timedOut = false;
1864         try {
1865             timedOut = !semaphore.tryAcquire(LONG_DELAY_MS, MILLISECONDS);
1866         } catch (Throwable fail) {
1867             threadUnexpectedException(fail);
1868         }
1869         if (timedOut)
1870             fail("timed out waiting for Semaphore for "
1871                  + (LONG_DELAY_MS/1000) + " sec");
1872     }
1873 
1874     public void await(CyclicBarrier barrier) {
1875         try {
1876             barrier.await(LONG_DELAY_MS, MILLISECONDS);
1877         } catch (Throwable fail) {
1878             threadUnexpectedException(fail);
1879         }
1880     }
1881 
1882 //     /**
1883 //      * Spin-waits up to LONG_DELAY_MS until flag becomes true.
1884 //      */
1885 //     public void await(AtomicBoolean flag) {
1886 //         await(flag, LONG_DELAY_MS);
1887 //     }
1888 
1889 //     /**
1890 //      * Spin-waits up to the specified timeout until flag becomes true.
1891 //      */
1892 //     public void await(AtomicBoolean flag, long timeoutMillis) {
1893 //         long startTime = System.nanoTime();
1894 //         while (!flag.get()) {
1895 //             if (millisElapsedSince(startTime) > timeoutMillis)
1896 //                 throw new AssertionError("timed out");
1897 //             Thread.yield();
1898 //         }
1899 //     }
1900 
1901     public static class NPETask implements Callable<String> {
1902         public String call() { throw new NullPointerException(); }
1903     }
1904 
1905     public Runnable possiblyInterruptedRunnable(final long timeoutMillis) {
1906         return new CheckedRunnable() {
1907             protected void realRun() {
1908                 try {
1909                     delay(timeoutMillis);
1910                 } catch (InterruptedException ok) {}
1911             }};
1912     }
1913 
1914     /**
1915      * For use as ThreadFactory in constructors
1916      */
1917     public static class SimpleThreadFactory implements ThreadFactory {
1918         public Thread newThread(Runnable r) {
1919             return new Thread(r);
1920         }
1921     }
1922 
1923     public interface TrackedRunnable extends Runnable {
1924         boolean isDone();
1925     }
1926 
1927     public static class TrackedNoOpRunnable implements Runnable {
1928         public volatile boolean done = false;
1929         public void run() {
1930             done = true;
1931         }
1932     }
1933 
1934     /**
1935      * Analog of CheckedRunnable for RecursiveAction
1936      */
1937     public abstract class CheckedRecursiveAction extends RecursiveAction {
1938         protected abstract void realCompute() throws Throwable;
1939 
1940         @Override protected final void compute() {
1941             try {
1942                 realCompute();
1943             } catch (Throwable fail) {
1944                 threadUnexpectedException(fail);
1945             }
1946         }
1947     }
1948 
1949     /**
1950      * Analog of CheckedCallable for RecursiveTask
1951      */
1952     public abstract class CheckedRecursiveTask<T> extends RecursiveTask<T> {
1953         protected abstract T realCompute() throws Throwable;
1954 
1955         @Override protected final T compute() {
1956             try {
1957                 return realCompute();
1958             } catch (Throwable fail) {
1959                 threadUnexpectedException(fail);
1960             }
1961             throw new AssertionError("unreached");
1962         }
1963     }
1964 
1965     /**
1966      * For use as RejectedExecutionHandler in constructors
1967      */
1968     public static class NoOpREHandler implements RejectedExecutionHandler {
1969         public void rejectedExecution(Runnable r,
1970                                       ThreadPoolExecutor executor) {}
1971     }
1972 
1973     /**
1974      * A CyclicBarrier that uses timed await and fails with
1975      * AssertionErrors instead of throwing checked exceptions.
1976      */
1977     public static class CheckedBarrier extends CyclicBarrier {
1978         public CheckedBarrier(int parties) { super(parties); }
1979 
1980         public int await() {
1981             try {
1982                 return super.await(LONGER_DELAY_MS, MILLISECONDS);
1983             } catch (TimeoutException timedOut) {
1984                 throw new AssertionError("timed out");
1985             } catch (Exception fail) {
1986                 throw new AssertionError("Unexpected exception: " + fail, fail);
1987             }
1988         }
1989     }
1990 
1991     void checkEmpty(BlockingQueue<?> q) {
1992         try {
1993             assertTrue(q.isEmpty());
1994             assertEquals(0, q.size());
1995             assertNull(q.peek());
1996             assertNull(q.poll());
1997             assertNull(q.poll(randomExpiredTimeout(), randomTimeUnit()));
1998             assertEquals(q.toString(), "[]");
1999             assertTrue(Arrays.equals(q.toArray(), new Object[0]));
2000             assertFalse(q.iterator().hasNext());
2001             try {
2002                 q.element();
2003                 shouldThrow();
2004             } catch (NoSuchElementException success) {}
2005             try {
2006                 q.iterator().next();
2007                 shouldThrow();
2008             } catch (NoSuchElementException success) {}
2009             try {
2010                 q.remove();
2011                 shouldThrow();
2012             } catch (NoSuchElementException success) {}
2013         } catch (InterruptedException fail) { threadUnexpectedException(fail); }
2014     }
2015 
2016     void assertSerialEquals(Object x, Object y) {
2017         assertTrue(Arrays.equals(serialBytes(x), serialBytes(y)));
2018     }
2019 
2020     void assertNotSerialEquals(Object x, Object y) {
2021         assertFalse(Arrays.equals(serialBytes(x), serialBytes(y)));
2022     }
2023 
2024     byte[] serialBytes(Object o) {
2025         try {
2026             ByteArrayOutputStream bos = new ByteArrayOutputStream();
2027             ObjectOutputStream oos = new ObjectOutputStream(bos);
2028             oos.writeObject(o);
2029             oos.flush();
2030             oos.close();
2031             return bos.toByteArray();
2032         } catch (Throwable fail) {
2033             threadUnexpectedException(fail);
2034             return new byte[0];
2035         }
2036     }
2037 
2038     @SuppressWarnings("unchecked")
2039     void assertImmutable(Object o) {
2040         if (o instanceof Collection) {
2041             assertThrows(
2042                 UnsupportedOperationException.class,
2043                 () -> ((Collection) o).add(null));
2044         }
2045     }
2046 
2047     @SuppressWarnings("unchecked")
2048     <T> T serialClone(T o) {
2049         T clone = null;
2050         try {
2051             ObjectInputStream ois = new ObjectInputStream
2052                 (new ByteArrayInputStream(serialBytes(o)));
2053             clone = (T) ois.readObject();
2054         } catch (Throwable fail) {
2055             threadUnexpectedException(fail);
2056         }
2057         if (o == clone) assertImmutable(o);
2058         else assertSame(o.getClass(), clone.getClass());
2059         return clone;
2060     }
2061 
2062     /**
2063      * A version of serialClone that leaves error handling (for
2064      * e.g. NotSerializableException) up to the caller.
2065      */
2066     @SuppressWarnings("unchecked")
2067     <T> T serialClonePossiblyFailing(T o)
2068         throws ReflectiveOperationException, java.io.IOException {
2069         ByteArrayOutputStream bos = new ByteArrayOutputStream();
2070         ObjectOutputStream oos = new ObjectOutputStream(bos);
2071         oos.writeObject(o);
2072         oos.flush();
2073         oos.close();
2074         ObjectInputStream ois = new ObjectInputStream
2075             (new ByteArrayInputStream(bos.toByteArray()));
2076         T clone = (T) ois.readObject();
2077         if (o == clone) assertImmutable(o);
2078         else assertSame(o.getClass(), clone.getClass());
2079         return clone;
2080     }
2081 
2082     /**
2083      * If o implements Cloneable and has a public clone method,
2084      * returns a clone of o, else null.
2085      */
2086     @SuppressWarnings("unchecked")
2087     <T> T cloneableClone(T o) {
2088         if (!(o instanceof Cloneable)) return null;
2089         final T clone;
2090         try {
2091             clone = (T) o.getClass().getMethod("clone").invoke(o);
2092         } catch (NoSuchMethodException ok) {
2093             return null;
2094         } catch (ReflectiveOperationException unexpected) {
2095             throw new Error(unexpected);
2096         }
2097         assertNotSame(o, clone); // not 100% guaranteed by spec
2098         assertSame(o.getClass(), clone.getClass());
2099         return clone;
2100     }
2101 
2102     public void assertThrows(Class<? extends Throwable> expectedExceptionClass,
2103                              Action... throwingActions) {
2104         for (Action throwingAction : throwingActions) {
2105             boolean threw = false;
2106             try { throwingAction.run(); }
2107             catch (Throwable t) {
2108                 threw = true;
2109                 if (!expectedExceptionClass.isInstance(t))
2110                     throw new AssertionError(
2111                             "Expected " + expectedExceptionClass.getName() +
2112                             ", got " + t.getClass().getName(),
2113                             t);
2114             }
2115             if (!threw)
2116                 shouldThrow(expectedExceptionClass.getName());
2117         }
2118     }
2119 
2120     public void assertIteratorExhausted(Iterator<?> it) {
2121         try {
2122             it.next();
2123             shouldThrow();
2124         } catch (NoSuchElementException success) {}
2125         assertFalse(it.hasNext());
2126     }
2127 
2128     public <T> Callable<T> callableThrowing(final Exception ex) {
2129         return new Callable<T>() { public T call() throws Exception { throw ex; }};
2130     }
2131 
2132     public Runnable runnableThrowing(final RuntimeException ex) {
2133         return new Runnable() { public void run() { throw ex; }};
2134     }
2135 
2136     /** A reusable thread pool to be shared by tests. */
2137     static final ExecutorService cachedThreadPool =
2138         new ThreadPoolExecutor(0, Integer.MAX_VALUE,
2139                                1000L, MILLISECONDS,
2140                                new SynchronousQueue<Runnable>());
2141 
2142     static <T> void shuffle(T[] array) {
2143         Collections.shuffle(Arrays.asList(array), ThreadLocalRandom.current());
2144     }
2145 
2146     /**
2147      * Returns the same String as would be returned by {@link
2148      * Object#toString}, whether or not the given object's class
2149      * overrides toString().
2150      *
2151      * @see System#identityHashCode
2152      */
2153     static String identityString(Object x) {
2154         return x.getClass().getName()
2155             + "@" + Integer.toHexString(System.identityHashCode(x));
2156     }
2157 
2158     // --- Shared assertions for Executor tests ---
2159 
2160     /**
2161      * Returns maximum number of tasks that can be submitted to given
2162      * pool (with bounded queue) before saturation (when submission
2163      * throws RejectedExecutionException).
2164      */
2165     static final int saturatedSize(ThreadPoolExecutor pool) {
2166         BlockingQueue<Runnable> q = pool.getQueue();
2167         return pool.getMaximumPoolSize() + q.size() + q.remainingCapacity();
2168     }
2169 
2170     @SuppressWarnings("FutureReturnValueIgnored")
2171     void assertNullTaskSubmissionThrowsNullPointerException(Executor e) {
2172         try {
2173             e.execute((Runnable) null);
2174             shouldThrow();
2175         } catch (NullPointerException success) {}
2176 
2177         if (! (e instanceof ExecutorService)) return;
2178         ExecutorService es = (ExecutorService) e;
2179         try {
2180             es.submit((Runnable) null);
2181             shouldThrow();
2182         } catch (NullPointerException success) {}
2183         try {
2184             es.submit((Runnable) null, Boolean.TRUE);
2185             shouldThrow();
2186         } catch (NullPointerException success) {}
2187         try {
2188             es.submit((Callable<?>) null);
2189             shouldThrow();
2190         } catch (NullPointerException success) {}
2191 
2192         if (! (e instanceof ScheduledExecutorService)) return;
2193         ScheduledExecutorService ses = (ScheduledExecutorService) e;
2194         try {
2195             ses.schedule((Runnable) null,
2196                          randomTimeout(), randomTimeUnit());
2197             shouldThrow();
2198         } catch (NullPointerException success) {}
2199         try {
2200             ses.schedule((Callable<?>) null,
2201                          randomTimeout(), randomTimeUnit());
2202             shouldThrow();
2203         } catch (NullPointerException success) {}
2204         try {
2205             ses.scheduleAtFixedRate((Runnable) null,
2206                                     randomTimeout(), LONG_DELAY_MS, MILLISECONDS);
2207             shouldThrow();
2208         } catch (NullPointerException success) {}
2209         try {
2210             ses.scheduleWithFixedDelay((Runnable) null,
2211                                        randomTimeout(), LONG_DELAY_MS, MILLISECONDS);
2212             shouldThrow();
2213         } catch (NullPointerException success) {}
2214     }
2215 
2216     void setRejectedExecutionHandler(
2217         ThreadPoolExecutor p, RejectedExecutionHandler handler) {
2218         p.setRejectedExecutionHandler(handler);
2219         assertSame(handler, p.getRejectedExecutionHandler());
2220     }
2221 
2222     void assertTaskSubmissionsAreRejected(ThreadPoolExecutor p) {
2223         final RejectedExecutionHandler savedHandler = p.getRejectedExecutionHandler();
2224         final long savedTaskCount = p.getTaskCount();
2225         final long savedCompletedTaskCount = p.getCompletedTaskCount();
2226         final int savedQueueSize = p.getQueue().size();
2227         final boolean stock = (p.getClass().getClassLoader() == null);
2228 
2229         Runnable r = () -> {};
2230         Callable<Boolean> c = () -> Boolean.TRUE;
2231 
2232         class Recorder implements RejectedExecutionHandler {
2233             public volatile Runnable r = null;
2234             public volatile ThreadPoolExecutor p = null;
2235             public void reset() { r = null; p = null; }
2236             public void rejectedExecution(Runnable r, ThreadPoolExecutor p) {
2237                 assertNull(this.r);
2238                 assertNull(this.p);
2239                 this.r = r;
2240                 this.p = p;
2241             }
2242         }
2243 
2244         // check custom handler is invoked exactly once per task
2245         Recorder recorder = new Recorder();
2246         setRejectedExecutionHandler(p, recorder);
2247         for (int i = 2; i--> 0; ) {
2248             recorder.reset();
2249             p.execute(r);
2250             if (stock && p.getClass() == ThreadPoolExecutor.class)
2251                 assertSame(r, recorder.r);
2252             assertSame(p, recorder.p);
2253 
2254             recorder.reset();
2255             assertFalse(p.submit(r).isDone());
2256             if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2257             assertSame(p, recorder.p);
2258 
2259             recorder.reset();
2260             assertFalse(p.submit(r, Boolean.TRUE).isDone());
2261             if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2262             assertSame(p, recorder.p);
2263 
2264             recorder.reset();
2265             assertFalse(p.submit(c).isDone());
2266             if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2267             assertSame(p, recorder.p);
2268 
2269             if (p instanceof ScheduledExecutorService) {
2270                 ScheduledExecutorService s = (ScheduledExecutorService) p;
2271                 ScheduledFuture<?> future;
2272 
2273                 recorder.reset();
2274                 future = s.schedule(r, randomTimeout(), randomTimeUnit());
2275                 assertFalse(future.isDone());
2276                 if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2277                 assertSame(p, recorder.p);
2278 
2279                 recorder.reset();
2280                 future = s.schedule(c, randomTimeout(), randomTimeUnit());
2281                 assertFalse(future.isDone());
2282                 if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2283                 assertSame(p, recorder.p);
2284 
2285                 recorder.reset();
2286                 future = s.scheduleAtFixedRate(r, randomTimeout(), LONG_DELAY_MS, MILLISECONDS);
2287                 assertFalse(future.isDone());
2288                 if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2289                 assertSame(p, recorder.p);
2290 
2291                 recorder.reset();
2292                 future = s.scheduleWithFixedDelay(r, randomTimeout(), LONG_DELAY_MS, MILLISECONDS);
2293                 assertFalse(future.isDone());
2294                 if (stock) assertTrue(!((FutureTask) recorder.r).isDone());
2295                 assertSame(p, recorder.p);
2296             }
2297         }
2298 
2299         // Checking our custom handler above should be sufficient, but
2300         // we add some integration tests of standard handlers.
2301         final AtomicReference<Thread> thread = new AtomicReference<>();
2302         final Runnable setThread = () -> thread.set(Thread.currentThread());
2303 
2304         setRejectedExecutionHandler(p, new ThreadPoolExecutor.AbortPolicy());
2305         try {
2306             p.execute(setThread);
2307             shouldThrow();
2308         } catch (RejectedExecutionException success) {}
2309         assertNull(thread.get());
2310 
2311         setRejectedExecutionHandler(p, new ThreadPoolExecutor.DiscardPolicy());
2312         p.execute(setThread);
2313         assertNull(thread.get());
2314 
2315         setRejectedExecutionHandler(p, new ThreadPoolExecutor.CallerRunsPolicy());
2316         p.execute(setThread);
2317         if (p.isShutdown())
2318             assertNull(thread.get());
2319         else
2320             assertSame(Thread.currentThread(), thread.get());
2321 
2322         setRejectedExecutionHandler(p, savedHandler);
2323 
2324         // check that pool was not perturbed by handlers
2325         assertEquals(savedTaskCount, p.getTaskCount());
2326         assertEquals(savedCompletedTaskCount, p.getCompletedTaskCount());
2327         assertEquals(savedQueueSize, p.getQueue().size());
2328     }
2329 
2330     void assertCollectionsEquals(Collection<?> x, Collection<?> y) {
2331         assertEquals(x, y);
2332         assertEquals(y, x);
2333         assertEquals(x.isEmpty(), y.isEmpty());
2334         assertEquals(x.size(), y.size());
2335         if (x instanceof List) {
2336             assertEquals(x.toString(), y.toString());
2337         }
2338         if (x instanceof List || x instanceof Set) {
2339             assertEquals(x.hashCode(), y.hashCode());
2340         }
2341         if (x instanceof List || x instanceof Deque) {
2342             assertTrue(Arrays.equals(x.toArray(), y.toArray()));
2343             assertTrue(Arrays.equals(x.toArray(new Object[0]),
2344                                      y.toArray(new Object[0])));
2345         }
2346     }
2347 
2348     /**
2349      * A weaker form of assertCollectionsEquals which does not insist
2350      * that the two collections satisfy Object#equals(Object), since
2351      * they may use identity semantics as Deques do.
2352      */
2353     void assertCollectionsEquivalent(Collection<?> x, Collection<?> y) {
2354         if (x instanceof List || x instanceof Set)
2355             assertCollectionsEquals(x, y);
2356         else {
2357             assertEquals(x.isEmpty(), y.isEmpty());
2358             assertEquals(x.size(), y.size());
2359             assertEquals(new HashSet<Object>(x), new HashSet<Object>(y));
2360             if (x instanceof Deque) {
2361                 assertTrue(Arrays.equals(x.toArray(), y.toArray()));
2362                 assertTrue(Arrays.equals(x.toArray(new Object[0]),
2363                                          y.toArray(new Object[0])));
2364             }
2365         }
2366     }
2367 }