--- jsr166/src/test/tck/JSR166TestCase.java 2015/10/03 19:39:16 1.154 +++ jsr166/src/test/tck/JSR166TestCase.java 2017/01/04 06:09:58 1.216 @@ -6,7 +6,36 @@ * Pat Fisher, Mike Judd. */ +/* + * @test + * @summary JSR-166 tck tests (conformance testing mode) + * @build * + * @modules java.management + * @run junit/othervm/timeout=1000 JSR166TestCase + */ + +/* + * @test + * @summary JSR-166 tck tests (whitebox tests allowed) + * @build * + * @modules java.base/java.util.concurrent:open + * java.management + * @run junit/othervm/timeout=1000 + * -Djsr166.testImplementationDetails=true + * JSR166TestCase + * @run junit/othervm/timeout=1000 + * -Djsr166.testImplementationDetails=true + * -Djava.util.concurrent.ForkJoinPool.common.parallelism=0 + * JSR166TestCase + * @run junit/othervm/timeout=1000 + * -Djsr166.testImplementationDetails=true + * -Djava.util.concurrent.ForkJoinPool.common.parallelism=1 + * -Djava.util.secureRandomSeed=true + * JSR166TestCase + */ + import static java.util.concurrent.TimeUnit.MILLISECONDS; +import static java.util.concurrent.TimeUnit.MINUTES; import static java.util.concurrent.TimeUnit.NANOSECONDS; import java.io.ByteArrayInputStream; @@ -19,6 +48,8 @@ import java.lang.management.ThreadMXBean import java.lang.reflect.Constructor; import java.lang.reflect.Method; import java.lang.reflect.Modifier; +import java.nio.file.Files; +import java.nio.file.Paths; import java.security.CodeSource; import java.security.Permission; import java.security.PermissionCollection; @@ -28,6 +59,8 @@ import java.security.ProtectionDomain; import java.security.SecurityPermission; import java.util.ArrayList; import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; import java.util.Date; import java.util.Enumeration; import java.util.Iterator; @@ -47,10 +80,14 @@ import java.util.concurrent.RecursiveAct import java.util.concurrent.RecursiveTask; import java.util.concurrent.RejectedExecutionHandler; import java.util.concurrent.Semaphore; +import java.util.concurrent.SynchronousQueue; import java.util.concurrent.ThreadFactory; +import java.util.concurrent.ThreadLocalRandom; import java.util.concurrent.ThreadPoolExecutor; import java.util.concurrent.TimeoutException; +import java.util.concurrent.atomic.AtomicBoolean; import java.util.concurrent.atomic.AtomicReference; +import java.util.regex.Matcher; import java.util.regex.Pattern; import junit.framework.AssertionFailedError; @@ -108,8 +145,7 @@ import junit.framework.TestSuite; * methods as there are exceptions the method can throw. Sometimes * there are multiple tests per JSR166 method when the different * "normal" behaviors differ significantly. And sometimes testcases - * cover multiple methods when they cannot be tested in - * isolation. + * cover multiple methods when they cannot be tested in isolation. * *
  • The documentation style for testcases is to provide as javadoc * a simple sentence or two describing the property that the testcase @@ -172,6 +208,44 @@ public class JSR166TestCase extends Test private static final int suiteRuns = Integer.getInteger("jsr166.suiteRuns", 1); + /** + * Returns the value of the system property, or NaN if not defined. + */ + private static float systemPropertyValue(String name) { + String floatString = System.getProperty(name); + if (floatString == null) + return Float.NaN; + try { + return Float.parseFloat(floatString); + } catch (NumberFormatException ex) { + throw new IllegalArgumentException( + String.format("Bad float value in system property %s=%s", + name, floatString)); + } + } + + /** + * The scaling factor to apply to standard delays used in tests. + * May be initialized from any of: + * - the "jsr166.delay.factor" system property + * - the "test.timeout.factor" system property (as used by jtreg) + * See: http://openjdk.java.net/jtreg/tag-spec.html + * - hard-coded fuzz factor when using a known slowpoke VM + */ + private static final float delayFactor = delayFactor(); + + private static float delayFactor() { + float x; + if (!Float.isNaN(x = systemPropertyValue("jsr166.delay.factor"))) + return x; + if (!Float.isNaN(x = systemPropertyValue("test.timeout.factor"))) + return x; + String prop = System.getProperty("java.vm.version"); + if (prop != null && prop.matches(".*debug.*")) + return 4.0f; // How much slower is fastdebug than product?! + return 1.0f; + } + public JSR166TestCase() { super(); } public JSR166TestCase(String name) { super(name); } @@ -187,7 +261,52 @@ public class JSR166TestCase extends Test return (regex == null) ? null : Pattern.compile(regex); } + // Instrumentation to debug very rare, but very annoying hung test runs. + static volatile TestCase currentTestCase; + // static volatile int currentRun = 0; + static { + Runnable checkForWedgedTest = new Runnable() { public void run() { + // Avoid spurious reports with enormous runsPerTest. + // A single test case run should never take more than 1 second. + // But let's cap it at the high end too ... + final int timeoutMinutes = + Math.min(15, Math.max(runsPerTest / 60, 1)); + for (TestCase lastTestCase = currentTestCase;;) { + try { MINUTES.sleep(timeoutMinutes); } + catch (InterruptedException unexpected) { break; } + if (lastTestCase == currentTestCase) { + System.err.printf( + "Looks like we're stuck running test: %s%n", + lastTestCase); +// System.err.printf( +// "Looks like we're stuck running test: %s (%d/%d)%n", +// lastTestCase, currentRun, runsPerTest); +// System.err.println("availableProcessors=" + +// Runtime.getRuntime().availableProcessors()); +// System.err.printf("cpu model = %s%n", cpuModel()); + dumpTestThreads(); + // one stack dump is probably enough; more would be spam + break; + } + lastTestCase = currentTestCase; + }}}; + Thread thread = new Thread(checkForWedgedTest, "checkForWedgedTest"); + thread.setDaemon(true); + thread.start(); + } + +// public static String cpuModel() { +// try { +// Matcher matcher = Pattern.compile("model name\\s*: (.*)") +// .matcher(new String( +// Files.readAllBytes(Paths.get("/proc/cpuinfo")), "UTF-8")); +// matcher.find(); +// return matcher.group(1); +// } catch (Exception ex) { return null; } +// } + public void runBare() throws Throwable { + currentTestCase = this; if (methodFilter == null || methodFilter.matcher(toString()).find()) super.runBare(); @@ -195,6 +314,7 @@ public class JSR166TestCase extends Test protected void runTest() throws Throwable { for (int i = 0; i < runsPerTest; i++) { + // currentRun = i; if (profileTests) runTestProfiled(); else @@ -223,6 +343,34 @@ public class JSR166TestCase extends Test main(suite(), args); } + static class PithyResultPrinter extends junit.textui.ResultPrinter { + PithyResultPrinter(java.io.PrintStream writer) { super(writer); } + long runTime; + public void startTest(Test test) {} + protected void printHeader(long runTime) { + this.runTime = runTime; // defer printing for later + } + protected void printFooter(TestResult result) { + if (result.wasSuccessful()) { + getWriter().println("OK (" + result.runCount() + " tests)" + + " Time: " + elapsedTimeAsString(runTime)); + } else { + getWriter().println("Time: " + elapsedTimeAsString(runTime)); + super.printFooter(result); + } + } + } + + /** + * Returns a TestRunner that doesn't bother with unnecessary + * fluff, like printing a "." for each test case. + */ + static junit.textui.TestRunner newPithyTestRunner() { + junit.textui.TestRunner runner = new junit.textui.TestRunner(); + runner.setPrinter(new PithyResultPrinter(System.out)); + return runner; + } + /** * Runs all unit tests in the given test suite. * Actual behavior influenced by jsr166.* system properties. @@ -234,7 +382,7 @@ public class JSR166TestCase extends Test System.setSecurityManager(new SecurityManager()); } for (int i = 0; i < suiteRuns; i++) { - TestResult result = junit.textui.TestRunner.run(suite); + TestResult result = newPithyTestRunner().doRun(suite); if (!result.wasSuccessful()) System.exit(1); System.gc(); @@ -318,6 +466,7 @@ public class JSR166TestCase extends Test AbstractQueuedLongSynchronizerTest.suite(), ArrayBlockingQueueTest.suite(), ArrayDequeTest.suite(), + ArrayListTest.suite(), AtomicBooleanTest.suite(), AtomicIntegerArrayTest.suite(), AtomicIntegerFieldUpdaterTest.suite(), @@ -340,6 +489,7 @@ public class JSR166TestCase extends Test CopyOnWriteArrayListTest.suite(), CopyOnWriteArraySetTest.suite(), CountDownLatchTest.suite(), + CountedCompleterTest.suite(), CyclicBarrierTest.suite(), DelayQueueTest.suite(), EntryTest.suite(), @@ -368,25 +518,30 @@ public class JSR166TestCase extends Test TreeMapTest.suite(), TreeSetTest.suite(), TreeSubMapTest.suite(), - TreeSubSetTest.suite()); + TreeSubSetTest.suite(), + VectorTest.suite()); // Java8+ test classes if (atLeastJava8()) { String[] java8TestClassNames = { + "ArrayDeque8Test", "Atomic8Test", "CompletableFutureTest", "ConcurrentHashMap8Test", - "CountedCompleterTest", + "CountedCompleter8Test", "DoubleAccumulatorTest", "DoubleAdderTest", "ForkJoinPool8Test", "ForkJoinTask8Test", + "LinkedBlockingDeque8Test", + "LinkedBlockingQueue8Test", "LongAccumulatorTest", "LongAdderTest", "SplittableRandomTest", "StampedLockTest", "SubmissionPublisherTest", "ThreadLocalRandom8Test", + "TimeUnit8Test", }; addNamedTestClasses(suite, java8TestClassNames); } @@ -394,7 +549,14 @@ public class JSR166TestCase extends Test // Java9+ test classes if (atLeastJava9()) { String[] java9TestClassNames = { - // Currently empty, but expecting varhandle tests + "AtomicBoolean9Test", + "AtomicInteger9Test", + "AtomicIntegerArray9Test", + "AtomicLong9Test", + "AtomicLongArray9Test", + "AtomicReference9Test", + "AtomicReferenceArray9Test", + "ExecutorCompletionService9Test", }; addNamedTestClasses(suite, java9TestClassNames); } @@ -405,7 +567,7 @@ public class JSR166TestCase extends Test /** Returns list of junit-style test method names in given class. */ public static ArrayList testMethodNames(Class testClass) { Method[] methods = testClass.getDeclaredMethods(); - ArrayList names = new ArrayList(methods.length); + ArrayList names = new ArrayList<>(methods.length); for (Method method : methods) { if (method.getName().startsWith("test") && Modifier.isPublic(method.getModifiers()) @@ -461,7 +623,6 @@ public class JSR166TestCase extends Test } else { return new TestSuite(); } - } // Delays for timing-dependent tests, in milliseconds. @@ -472,11 +633,13 @@ public class JSR166TestCase extends Test public static long LONG_DELAY_MS; /** - * Returns the shortest timed delay. This could - * be reimplemented to use for example a Property. + * Returns the shortest timed delay. This can be scaled up for + * slow machines using the jsr166.delay.factor system property, + * or via jtreg's -timeoutFactor: flag. + * http://openjdk.java.net/jtreg/command-help.html */ protected long getShortDelay() { - return 50; + return (long) (50 * delayFactor); } /** @@ -510,7 +673,7 @@ public class JSR166TestCase extends Test * The first exception encountered if any threadAssertXXX method fails. */ private final AtomicReference threadFailure - = new AtomicReference(null); + = new AtomicReference<>(null); /** * Records an exception so that it can be rethrown later in the test @@ -519,7 +682,8 @@ public class JSR166TestCase extends Test * the same test have no effect. */ public void threadRecordFailure(Throwable t) { - threadDump(); + System.err.println(t); + dumpTestThreads(); threadFailure.compareAndSet(null, t); } @@ -530,7 +694,7 @@ public class JSR166TestCase extends Test void tearDownFail(String format, Object... args) { String msg = toString() + ": " + String.format(format, args); System.err.println(msg); - threadDump(); + dumpTestThreads(); throw new AssertionFailedError(msg); } @@ -567,7 +731,7 @@ public class JSR166TestCase extends Test } /** - * Finds missing try { ... } finally { joinPool(e); } + * Finds missing PoolCleaners */ void checkForkJoinPoolThreadLeaks() throws InterruptedException { Thread[] survivors = new Thread[7]; @@ -726,51 +890,104 @@ public class JSR166TestCase extends Test /** * Delays, via Thread.sleep, for the given millisecond delay, but * if the sleep is shorter than specified, may re-sleep or yield - * until time elapses. + * until time elapses. Ensures that the given time, as measured + * by System.nanoTime(), has elapsed. */ static void delay(long millis) throws InterruptedException { - long startTime = System.nanoTime(); - long ns = millis * 1000 * 1000; - for (;;) { + long nanos = millis * (1000 * 1000); + final long wakeupTime = System.nanoTime() + nanos; + do { if (millis > 0L) Thread.sleep(millis); else // too short to sleep Thread.yield(); - long d = ns - (System.nanoTime() - startTime); - if (d > 0L) - millis = d / (1000 * 1000); - else - break; - } + nanos = wakeupTime - System.nanoTime(); + millis = nanos / (1000 * 1000); + } while (nanos >= 0L); } /** * Allows use of try-with-resources with per-test thread pools. */ - static class PoolCloser - implements AutoCloseable { - public final T pool; - public PoolCloser(T pool) { this.pool = pool; } + class PoolCleaner implements AutoCloseable { + private final ExecutorService pool; + public PoolCleaner(ExecutorService pool) { this.pool = pool; } public void close() { joinPool(pool); } } /** + * An extension of PoolCleaner that has an action to release the pool. + */ + class PoolCleanerWithReleaser extends PoolCleaner { + private final Runnable releaser; + public PoolCleanerWithReleaser(ExecutorService pool, Runnable releaser) { + super(pool); + this.releaser = releaser; + } + public void close() { + try { + releaser.run(); + } finally { + super.close(); + } + } + } + + PoolCleaner cleaner(ExecutorService pool) { + return new PoolCleaner(pool); + } + + PoolCleaner cleaner(ExecutorService pool, Runnable releaser) { + return new PoolCleanerWithReleaser(pool, releaser); + } + + PoolCleaner cleaner(ExecutorService pool, CountDownLatch latch) { + return new PoolCleanerWithReleaser(pool, releaser(latch)); + } + + Runnable releaser(final CountDownLatch latch) { + return new Runnable() { public void run() { + do { latch.countDown(); } + while (latch.getCount() > 0); + }}; + } + + PoolCleaner cleaner(ExecutorService pool, AtomicBoolean flag) { + return new PoolCleanerWithReleaser(pool, releaser(flag)); + } + + Runnable releaser(final AtomicBoolean flag) { + return new Runnable() { public void run() { flag.set(true); }}; + } + + /** * Waits out termination of a thread pool or fails doing so. */ - static void joinPool(ExecutorService pool) { + void joinPool(ExecutorService pool) { try { pool.shutdown(); - if (!pool.awaitTermination(2 * LONG_DELAY_MS, MILLISECONDS)) - fail("ExecutorService " + pool + - " did not terminate in a timely manner"); + if (!pool.awaitTermination(2 * LONG_DELAY_MS, MILLISECONDS)) { + try { + threadFail("ExecutorService " + pool + + " did not terminate in a timely manner"); + } finally { + // last resort, for the benefit of subsequent tests + pool.shutdownNow(); + pool.awaitTermination(MEDIUM_DELAY_MS, MILLISECONDS); + } + } } catch (SecurityException ok) { // Allowed in case test doesn't have privs } catch (InterruptedException fail) { - fail("Unexpected InterruptedException"); + threadFail("Unexpected InterruptedException"); } } - /** Like Runnable, but with the freedom to throw anything */ + /** + * Like Runnable, but with the freedom to throw anything. + * junit folks had the same idea: + * http://junit.org/junit5/docs/snapshot/api/org/junit/gen5/api/Executable.html + */ interface Action { public void run() throws Throwable; } /** @@ -779,9 +996,8 @@ public class JSR166TestCase extends Test * necessarily individually slow because they must block. */ void testInParallel(Action ... actions) { - try (PoolCloser poolCloser - = new PoolCloser<>(Executors.newCachedThreadPool())) { - ExecutorService pool = poolCloser.pool; + ExecutorService pool = Executors.newCachedThreadPool(); + try (PoolCleaner cleaner = cleaner(pool)) { ArrayList> futures = new ArrayList<>(actions.length); for (final Action action : actions) futures.add(pool.submit(new CheckedRunnable() { @@ -798,25 +1014,41 @@ public class JSR166TestCase extends Test } /** - * A debugging tool to print all stack traces, as jstack does. + * A debugging tool to print stack traces of most threads, as jstack does. * Uninteresting threads are filtered out. */ - static void threadDump() { + static void dumpTestThreads() { + SecurityManager sm = System.getSecurityManager(); + if (sm != null) { + try { + System.setSecurityManager(null); + } catch (SecurityException giveUp) { + return; + } + } + ThreadMXBean threadMXBean = ManagementFactory.getThreadMXBean(); System.err.println("------ stacktrace dump start ------"); for (ThreadInfo info : threadMXBean.dumpAllThreads(true, true)) { - String name = info.getThreadName(); + final String name = info.getThreadName(); + String lockName; if ("Signal Dispatcher".equals(name)) continue; if ("Reference Handler".equals(name) - && info.getLockName().startsWith("java.lang.ref.Reference$Lock")) + && (lockName = info.getLockName()) != null + && lockName.startsWith("java.lang.ref.Reference$Lock")) continue; if ("Finalizer".equals(name) - && info.getLockName().startsWith("java.lang.ref.ReferenceQueue$Lock")) + && (lockName = info.getLockName()) != null + && lockName.startsWith("java.lang.ref.ReferenceQueue$Lock")) + continue; + if ("checkForWedgedTest".equals(name)) continue; System.err.print(info); } System.err.println("------ stacktrace dump end ------"); + + if (sm != null) System.setSecurityManager(sm); } /** @@ -836,7 +1068,7 @@ public class JSR166TestCase extends Test delay(millis); assertTrue(thread.isAlive()); } catch (InterruptedException fail) { - fail("Unexpected InterruptedException"); + threadFail("Unexpected InterruptedException"); } } @@ -858,7 +1090,7 @@ public class JSR166TestCase extends Test for (Thread thread : threads) assertTrue(thread.isAlive()); } catch (InterruptedException fail) { - fail("Unexpected InterruptedException"); + threadFail("Unexpected InterruptedException"); } } @@ -1003,7 +1235,7 @@ public class JSR166TestCase extends Test } public void refresh() {} public String toString() { - List ps = new ArrayList(); + List ps = new ArrayList<>(); for (Enumeration e = perms.elements(); e.hasMoreElements();) ps.add(e.nextElement()); return "AdjustablePolicy with permissions " + ps; @@ -1033,7 +1265,7 @@ public class JSR166TestCase extends Test * Sleeps until the given time has elapsed. * Throws AssertionFailedError if interrupted. */ - void sleep(long millis) { + static void sleep(long millis) { try { delay(millis); } catch (InterruptedException fail) { @@ -1049,7 +1281,7 @@ public class JSR166TestCase extends Test * thread to enter a wait state: BLOCKED, WAITING, or TIMED_WAITING. */ void waitForThreadToEnterWaitState(Thread thread, long timeoutMillis) { - long startTime = System.nanoTime(); + long startTime = 0L; for (;;) { Thread.State s = thread.getState(); if (s == Thread.State.BLOCKED || @@ -1058,6 +1290,8 @@ public class JSR166TestCase extends Test return; else if (s == Thread.State.TERMINATED) fail("Unexpected thread termination"); + else if (startTime == 0L) + startTime = System.nanoTime(); else if (millisElapsedSince(startTime) > timeoutMillis) { threadAssertTrue(thread.isAlive()); return; @@ -1136,7 +1370,7 @@ public class JSR166TestCase extends Test } finally { if (t.getState() != Thread.State.TERMINATED) { t.interrupt(); - fail("Test timed out"); + threadFail("timed out waiting for thread to terminate"); } } } @@ -1284,24 +1518,43 @@ public class JSR166TestCase extends Test }}; } - public Runnable awaiter(final CountDownLatch latch) { - return new CheckedRunnable() { - public void realRun() throws InterruptedException { - await(latch); - }}; + class LatchAwaiter extends CheckedRunnable { + static final int NEW = 0; + static final int RUNNING = 1; + static final int DONE = 2; + final CountDownLatch latch; + int state = NEW; + LatchAwaiter(CountDownLatch latch) { this.latch = latch; } + public void realRun() throws InterruptedException { + state = 1; + await(latch); + state = 2; + } } - public void await(CountDownLatch latch) { + public LatchAwaiter awaiter(CountDownLatch latch) { + return new LatchAwaiter(latch); + } + + public void await(CountDownLatch latch, long timeoutMillis) { try { - assertTrue(latch.await(LONG_DELAY_MS, MILLISECONDS)); + if (!latch.await(timeoutMillis, MILLISECONDS)) + fail("timed out waiting for CountDownLatch for " + + (timeoutMillis/1000) + " sec"); } catch (Throwable fail) { threadUnexpectedException(fail); } } + public void await(CountDownLatch latch) { + await(latch, LONG_DELAY_MS); + } + public void await(Semaphore semaphore) { try { - assertTrue(semaphore.tryAcquire(LONG_DELAY_MS, MILLISECONDS)); + if (!semaphore.tryAcquire(LONG_DELAY_MS, MILLISECONDS)) + fail("timed out waiting for Semaphore for " + + (LONG_DELAY_MS/1000) + " sec"); } catch (Throwable fail) { threadUnexpectedException(fail); } @@ -1531,7 +1784,7 @@ public class JSR166TestCase extends Test * A CyclicBarrier that uses timed await and fails with * AssertionFailedErrors instead of throwing checked exceptions. */ - public class CheckedBarrier extends CyclicBarrier { + public static class CheckedBarrier extends CyclicBarrier { public CheckedBarrier(int parties) { super(parties); } public int await() { @@ -1595,12 +1848,22 @@ public class JSR166TestCase extends Test } } + void assertImmutable(final Object o) { + if (o instanceof Collection) { + assertThrows( + UnsupportedOperationException.class, + new Runnable() { public void run() { + ((Collection) o).add(null);}}); + } + } + @SuppressWarnings("unchecked") T serialClone(T o) { try { ObjectInputStream ois = new ObjectInputStream (new ByteArrayInputStream(serialBytes(o))); T clone = (T) ois.readObject(); + if (o == clone) assertImmutable(o); assertSame(o.getClass(), clone.getClass()); return clone; } catch (Throwable fail) { @@ -1609,6 +1872,46 @@ public class JSR166TestCase extends Test } } + /** + * A version of serialClone that leaves error handling (for + * e.g. NotSerializableException) up to the caller. + */ + @SuppressWarnings("unchecked") + T serialClonePossiblyFailing(T o) + throws ReflectiveOperationException, java.io.IOException { + ByteArrayOutputStream bos = new ByteArrayOutputStream(); + ObjectOutputStream oos = new ObjectOutputStream(bos); + oos.writeObject(o); + oos.flush(); + oos.close(); + ObjectInputStream ois = new ObjectInputStream + (new ByteArrayInputStream(bos.toByteArray())); + T clone = (T) ois.readObject(); + if (o == clone) assertImmutable(o); + assertSame(o.getClass(), clone.getClass()); + return clone; + } + + /** + * If o implements Cloneable and has a public clone method, + * returns a clone of o, else null. + */ + @SuppressWarnings("unchecked") + T cloneableClone(T o) { + if (!(o instanceof Cloneable)) return null; + final T clone; + try { + clone = (T) o.getClass().getMethod("clone").invoke(o); + } catch (NoSuchMethodException ok) { + return null; + } catch (ReflectiveOperationException unexpected) { + throw new Error(unexpected); + } + assertNotSame(o, clone); // not 100% guaranteed by spec + assertSame(o.getClass(), clone.getClass()); + return clone; + } + public void assertThrows(Class expectedExceptionClass, Runnable... throwingActions) { for (Runnable throwingAction : throwingActions) { @@ -1637,4 +1940,22 @@ public class JSR166TestCase extends Test } catch (NoSuchElementException success) {} assertFalse(it.hasNext()); } + + public Callable callableThrowing(final Exception ex) { + return new Callable() { public T call() throws Exception { throw ex; }}; + } + + public Runnable runnableThrowing(final RuntimeException ex) { + return new Runnable() { public void run() { throw ex; }}; + } + + /** A reusable thread pool to be shared by tests. */ + static final ExecutorService cachedThreadPool = + new ThreadPoolExecutor(0, Integer.MAX_VALUE, + 1000L, MILLISECONDS, + new SynchronousQueue()); + + static void shuffle(T[] array) { + Collections.shuffle(Arrays.asList(array), ThreadLocalRandom.current()); + } }