--- jsr166/src/test/tck/ConcurrentLinkedDequeTest.java	2017/08/04 03:30:21	1.29
+++ jsr166/src/test/tck/ConcurrentLinkedDequeTest.java	2018/06/22 00:04:58	1.33
@@ -13,7 +13,10 @@ import java.util.Iterator;
 import java.util.NoSuchElementException;
 import java.util.Queue;
 import java.util.Random;
+import java.util.concurrent.CompletableFuture;
 import java.util.concurrent.ConcurrentLinkedDeque;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.concurrent.atomic.LongAdder;
 
 import junit.framework.Test;
 
@@ -659,9 +662,11 @@ public class ConcurrentLinkedDequeTest e
      */
     public void testToArray() {
         ConcurrentLinkedDeque q = populatedDeque(SIZE);
-        Object[] o = q.toArray();
-        for (int i = 0; i < o.length; i++)
-            assertSame(o[i], q.poll());
+        Object[] a = q.toArray();
+        assertSame(Object[].class, a.getClass());
+        for (Object o : a)
+            assertSame(o, q.poll());
+        assertTrue(q.isEmpty());
     }
 
     /**
@@ -672,8 +677,9 @@ public class ConcurrentLinkedDequeTest e
         Integer[] ints = new Integer[SIZE];
         Integer[] array = q.toArray(ints);
         assertSame(ints, array);
-        for (int i = 0; i < ints.length; i++)
-            assertSame(ints[i], q.poll());
+        for (Integer o : ints)
+            assertSame(o, q.poll());
+        assertTrue(q.isEmpty());
     }
 
     /**
@@ -682,7 +688,7 @@ public class ConcurrentLinkedDequeTest e
     public void testToArray_NullArg() {
         ConcurrentLinkedDeque q = populatedDeque(SIZE);
         try {
-            q.toArray(null);
+            q.toArray((Object[])null);
             shouldThrow();
         } catch (NullPointerException success) {}
     }
@@ -905,4 +911,107 @@ public class ConcurrentLinkedDequeTest e
             } catch (NullPointerException success) {}
         }
     }
+
+    void runAsync(Runnable r1, Runnable r2) {
+        boolean b = ThreadLocalRandom.current().nextBoolean();
+        CompletableFuture<Void> f1 = CompletableFuture.runAsync(b ? r1 : r2);
+        CompletableFuture<Void> f2 = CompletableFuture.runAsync(b ? r2 : r1);
+        f1.join();
+        f2.join();
+    }
+
+    /**
+     * Non-traversing Deque operations are linearizable.
+     * https://bugs.openjdk.java.net/browse/JDK-8188900
+     * ant -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ConcurrentLinkedDequeTest -Djsr166.methodFilter=testBug8188900 tck
+     */
+    public void testBug8188900() {
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        final LongAdder nulls = new LongAdder(), zeros = new LongAdder();
+        for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
+            ConcurrentLinkedDeque<Integer> d = new ConcurrentLinkedDeque<>();
+
+            boolean peek = rnd.nextBoolean();
+            Runnable getter = () -> {
+                Integer x = peek ? d.peekFirst() : d.pollFirst();
+                if (x == null) nulls.increment();
+                else if (x == 0) zeros.increment();
+                else
+                    throw new AssertionError(
+                        String.format(
+                            "unexpected value %d after %d nulls and %d zeros",
+                            x, nulls.sum(), zeros.sum()));
+            };
+
+            Runnable adder = () -> { d.addFirst(0); d.addLast(42); };
+
+            runAsync(getter, adder);
+        }
+    }
+
+    /**
+     * Reverse direction variant of testBug8188900
+     */
+    public void testBug8188900_reverse() {
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        final LongAdder nulls = new LongAdder(), zeros = new LongAdder();
+        for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
+            ConcurrentLinkedDeque<Integer> d = new ConcurrentLinkedDeque<>();
+
+            boolean peek = rnd.nextBoolean();
+            Runnable getter = () -> {
+                Integer x = peek ? d.peekLast() : d.pollLast();
+                if (x == null) nulls.increment();
+                else if (x == 0) zeros.increment();
+                else
+                    throw new AssertionError(
+                        String.format(
+                            "unexpected value %d after %d nulls and %d zeros",
+                            x, nulls.sum(), zeros.sum()));
+            };
+
+            Runnable adder = () -> { d.addLast(0); d.addFirst(42); };
+
+            runAsync(getter, adder);
+        }
+    }
+
+    <T> T chooseRandomly(T... choices) {
+        return choices[ThreadLocalRandom.current().nextInt(choices.length)];
+    }
+
+    /**
+     * Non-traversing Deque operations (that return null) are linearizable.
+     * Don't return null when the deque is observably never empty.
+     * https://bugs.openjdk.java.net/browse/JDK-8189387
+     * ant -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ConcurrentLinkedDequeTest -Djsr166.methodFilter=testBug8189387 tck
+     */
+    public void testBug8189387() {
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        Object x = new Object();
+        for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
+            ConcurrentLinkedDeque<Object> d = new ConcurrentLinkedDeque<>();
+            Runnable add = chooseRandomly(
+                () -> d.addFirst(x),
+                () -> d.offerFirst(x),
+                () -> d.addLast(x),
+                () -> d.offerLast(x));
+
+            Runnable get = chooseRandomly(
+                () -> assertFalse(d.isEmpty()),
+                () -> assertSame(x, d.peekFirst()),
+                () -> assertSame(x, d.peekLast()),
+                () -> assertSame(x, d.pollFirst()),
+                () -> assertSame(x, d.pollLast()));
+
+            Runnable addRemove = chooseRandomly(
+                () -> { d.addFirst(x); d.pollLast(); },
+                () -> { d.offerFirst(x); d.removeFirst(); },
+                () -> { d.offerLast(x); d.removeLast(); },
+                () -> { d.addLast(x); d.pollFirst(); });
+
+            add.run();
+            runAsync(get, addRemove);
+        }
+    }
 }