RFR 8206123 : ArrayDeque created with default constructor can only hold 15 elements

[Martin Buchholz]

Hi Ivan,

Thanks for finding this bug - I'll take the blame.

Forgive my pushiness - I'd like to do a friendly takeover of this. As
penance I ported the similar WhiteBox test from ConcurrentHashMap to
ArrayDeque.  I would elide the comment in the default constructor.  And we
can delete our noreg label.

Index: src/main/java/util/ArrayDeque.java
===================================================================
RCS file:
/export/home/jsr166/jsr166/jsr166/src/main/java/util/ArrayDeque.java,v
retrieving revision 1.133
diff -u -r1.133 ArrayDeque.java
--- src/main/java/util/ArrayDeque.java 24 Feb 2018 22:04:18 -0000 1.133
+++ src/main/java/util/ArrayDeque.java 30 Jun 2018 17:07:46 -0000
@@ -181,7 +181,7 @@
      * sufficient to hold 16 elements.
      */
     public ArrayDeque() {
-        elements = new Object[16];
+        elements = new Object[16 + 1];
     }

     /**
Index: src/test/jtreg/util/ArrayDeque/WhiteBox.java
===================================================================
RCS file: src/test/jtreg/util/ArrayDeque/WhiteBox.java
diff -N src/test/jtreg/util/ArrayDeque/WhiteBox.java
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ src/test/jtreg/util/ArrayDeque/WhiteBox.java 30 Jun 2018 17:07:46 -0000
@@ -0,0 +1,125 @@
+/*
+ * Written by Martin Buchholz with assistance from members of JCP
+ * JSR-166 Expert Group and released to the public domain, as
+ * explained at http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+/*
+ * @test
+ * @modules java.base/java.util:open
+ * @run testng WhiteBox
+ * @summary White box tests of implementation details
+ */
+
+import static org.testng.Assert.*;
+import org.testng.annotations.Test;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.lang.invoke.MethodHandles;
+import java.lang.invoke.VarHandle;
+import java.util.ArrayDeque;
+import java.util.concurrent.ThreadLocalRandom;
+
+ at Test
+public class WhiteBox {
+    final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+    final VarHandle ELEMENTS, HEAD, TAIL;
+
+    WhiteBox() throws ReflectiveOperationException {
+        Class<?> klazz = ArrayDeque.class;
+        MethodHandles.Lookup lookup
+            = MethodHandles.privateLookupIn(klazz, MethodHandles.lookup());
+        ELEMENTS = lookup.findVarHandle(klazz, "elements", Object[].class);
+        HEAD = lookup.findVarHandle(klazz, "head", int.class);
+        TAIL = lookup.findVarHandle(klazz, "tail", int.class);
+    }
+
+    Object[] elements(ArrayDeque d) { return (Object[]) ELEMENTS.get(d); }
+    int head(ArrayDeque d) { return (int) HEAD.get(d); }
+    int tail(ArrayDeque d) { return (int) TAIL.get(d); }
+
+    void checkCapacity(ArrayDeque d, int capacity) {
+        assertTrue(d.isEmpty());
+        assertEquals(0, head(d));
+        assertEquals(0, tail(d));
+        assertInvariants(d);
+        Object[] initialElements = elements(d);
+
+        assertInvariants(d);
+        for (int i = capacity; i--> 0; ) {
+            d.add(rnd.nextInt(42));
+            assertSame(elements(d), initialElements);
+            assertInvariants(d);
+        }
+        d.add(rnd.nextInt(42));
+        assertNotSame(elements(d), initialElements);
+    }
+
+    @Test
+    public void defaultConstructor() {
+        checkCapacity(new ArrayDeque(), 16);
+    }
+
+    @Test
+    public void shouldNotResizeWhenInitialCapacityProvided() {
+        int initialCapacity = rnd.nextInt(1, 20);
+        checkCapacity(new ArrayDeque(initialCapacity), initialCapacity);
+    }
+
+    byte[] serialBytes(Object o) {
+        try {
+            ByteArrayOutputStream bos = new ByteArrayOutputStream();
+            ObjectOutputStream oos = new ObjectOutputStream(bos);
+            oos.writeObject(o);
+            oos.flush();
+            oos.close();
+            return bos.toByteArray();
+        } catch (Exception fail) {
+            throw new AssertionError(fail);
+        }
+    }
+
+    @SuppressWarnings("unchecked")
+    <T> T serialClone(T o) {
+        try {
+            ObjectInputStream ois = new ObjectInputStream
+                (new ByteArrayInputStream(serialBytes(o)));
+            T clone = (T) ois.readObject();
+            assertNotSame(o, clone);
+            assertSame(o.getClass(), clone.getClass());
+            return clone;
+        } catch (Exception fail) {
+            throw new AssertionError(fail);
+        }
+    }
+
+    @Test
+    public void testSerialization() {
+        ArrayDeque[] ds = { new ArrayDeque(), new
ArrayDeque(rnd.nextInt(20)) };
+        for (ArrayDeque d : ds) {
+            if (rnd.nextBoolean()) d.add(99);
+            ArrayDeque clone = serialClone(d);
+            assertInvariants(clone);
+            assertNotSame(elements(d), elements(clone));
+            assertEquals(d, clone);
+        }
+    }
+
+    /** Checks conditions which should always be true. */
+    void assertInvariants(ArrayDeque d) {
+        final Object[] elements = elements(d);
+        final int head = head(d);
+        final int tail = tail(d);
+        final int capacity = elements.length;
+        assertTrue(0 <= head && head < capacity);
+        assertTrue(0 <= tail && tail < capacity);
+        assertTrue(capacity > 0);
+        assertTrue(d.size() < capacity);
+        assertTrue(head == tail || elements[head] != null);
+        assertNull(elements[tail]);
+        assertTrue(head == tail || elements[Math.floorMod(tail - 1,
capacity)] != null);
+    }
+}


On Fri, Jun 29, 2018 at 7:21 PM, Ivan Gerasimov <ivan.gerasimov at oracle.com>
wrote:

> Hello!
>
> The spec states that an ArrayDeque created with the default constructor
> should be able to hold 16 elements.
>
> https://docs.oracle.com/javase/10/docs/api/java/util/ArrayDe
> que.html#%3Cinit%3E()
> """
> Constructs an empty array deque with an initial capacity sufficient to
> hold 16 elements.
> """
>
> In the constructor an array of size 16 is created:
>         elements = new Object[16];
>
> However, one element must always be null:
>     /**
>      * The array in which the elements of the deque are stored.
>      * All array cells not holding deque elements are always null.
>      * The array always has at least one null slot (at tail).
>      */
>     transient Object[] elements;
>
> which leaves us space for only 15 elements, contrarily to what the spec
> promises.
>
>
> Would you please help review a trivial fix?
>
> BUGURL: https://bugs.openjdk.java.net/browse/JDK-8206123
> WEBREV: http://cr.openjdk.java.net/~igerasim/8206123/00/webrev/
>
> Thanks in advance!
>
> --
> With kind regards,
> Ivan Gerasimov
>
>