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

Ivan Gerasimov ivan.gerasimov at oracle.com
Sat Jun 30 21:58:58 UTC 2018


Hi Martin!


On 6/30/18 10:29 AM, Martin Buchholz wrote:
> 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.

Sure, no problem!  I reassigned the bug to you.

> I would elide the comment in the default constructor.  And we can 
> delete our noreg label.
>
Sounds good!  If there is a test, then no need for a comment.

With kind regards,
Ivan

> 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.java24 Feb 2018 22:04:18 -00001.133
> +++ src/main/java/util/ArrayDeque.java30 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/null1 Jan 1970 00:00:00 -0000
> +++ src/test/jtreg/util/ArrayDeque/WhiteBox.java30 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 <mailto: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/ArrayDeque.html#%3Cinit%3E()
>     <https://docs.oracle.com/javase/10/docs/api/java/util/ArrayDeque.html#%3Cinit%3E%28%29>
>     """
>     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
>     <https://bugs.openjdk.java.net/browse/JDK-8206123>
>     WEBREV: http://cr.openjdk.java.net/~igerasim/8206123/00/webrev/
>     <http://cr.openjdk.java.net/%7Eigerasim/8206123/00/webrev/>
>
>     Thanks in advance!
>
>     -- 
>     With kind regards,
>     Ivan Gerasimov
>
>

-- 
With kind regards,
Ivan Gerasimov



More information about the core-libs-dev mailing list