Fix ArrayDeque's bug when expanding capacity.

Also fixes concurrent modification check for the case
when head > tail.

Bug: #9404
Bug-Link: https://github.com/gwtproject/gwt/issues/9404
Change-Id: I9e13b1c80ddad1c69d8863855d2f4f6fb62b1b6f

user/super/com/google/gwt/emul/java/util/ArrayDeque.java

diff --git a/user/super/com/google/gwt/emul/java/util/ArrayDeque.java b/user/super/com/google/gwt/emul/java/util/ArrayDeque.java
index 619b7e8..694593f 100644
--- a/user/super/com/google/gwt/emul/java/util/ArrayDeque.java
+++ b/user/super/com/google/gwt/emul/java/util/ArrayDeque.java
@@ -72,7 +72,6 @@
     @Override
     public void remove() {
       checkState(lastIndex >= 0);
-      checkConcurrentModification(head <= lastIndex && lastIndex < tail);
 
       if (removeAtIndex(lastIndex) < 0) {
         // if left-shifted, undo increment in next()
@@ -107,7 +106,6 @@
     @Override
     public void remove() {
       checkState(lastIndex >= 0);
-      checkConcurrentModification(head <= lastIndex && lastIndex < tail);
 
       if (removeAtIndex(lastIndex) > 0) {
         // if right-shifted, undo decrement in next()
@@ -382,11 +380,7 @@
     if (out.length < size) {
       out = ArrayHelper.createFrom(out, size);
     }
-    Object[] dest = out;
-    final int mask = size - 1;
-    for (int i = head, dstIdx = 0; dstIdx < size; i = (i + 1) & mask, ++dstIdx) {
-      dest[dstIdx] = array[i];
-    }
+    copyElements(out, size);
     if (out.length > size) {
       out[size] = null;
     }
@@ -423,6 +417,19 @@
   }
 
   /**
+   * Copies {@code count} ArrayDeque's elements to {@code dest} array.
+   * The method is safe to use when ArrayDeque's array has been rolled over,
+   * i.e. {@code head == tail}.
+   * It is assumed that {@code count < size()}.
+   */
+  private void copyElements(Object[] dest, int count) {
+    final int mask = array.length - 1;
+    for (int i = head, dstIdx = 0; dstIdx < count; i = (i + 1) & mask, ++dstIdx) {
+      dest[dstIdx] = array[i];
+    }
+  }
+
+  /**
    * Increase the capacity of this deque when full, i.e.,
    * when head and tail have wrapped around to become equal.
    */
@@ -435,11 +442,12 @@
     int newLength = nextArrayLength(numElements);
     if (head != 0) {
       E[] newArray = ArrayHelper.createFrom(array, newLength);
-      array = toArray(newArray);
+      copyElements(newArray, numElements);
+      array = newArray;
+      head = 0;
     } else {
       ArrayHelper.setLength(array, newLength);
     }
-    head = 0;
     tail = numElements;
   }
 
@@ -454,6 +462,9 @@
     final int mask = array.length - 1;
     int headDistance = (i - head) & mask;
     int tailDistance = (tail - i) & mask;
+    int size = (tail - head) & mask;
+
+    checkConcurrentModification(headDistance < size);
     if (headDistance >= tailDistance) {
       shiftLeftAtIndex(i);
       return -1;

user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java

diff --git a/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java b/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java
index 9915e2a..13e5a09 100644
--- a/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java
+++ b/user/test/com/google/gwt/emultest/java/util/ArrayDequeTest.java
@@ -822,6 +822,28 @@
     assertFalse(deque.removeLastOccurrence(null));
   }
 
+  public void testRolloverInvariants() {
+    ArrayDeque<Integer> deque = new ArrayDeque<>();
+
+    assertTrue(deque.add(1));
+    assertEquals(1, (int) deque.removeFirst());
+    for (int i = 0; i < 100; i++) {
+      assertTrue(deque.add(i));
+    }
+    assertNotNull(deque.peek());
+    assertFalse(deque.isEmpty());
+
+    Iterator<Integer> it = deque.iterator();
+    for (int i = 0; i < 100; i++) {
+      assertTrue(it.hasNext());
+      assertEquals(i, (int) it.next());
+      it.remove();
+    }
+    assertFalse(it.hasNext());
+    assertNull(deque.peek());
+    assertTrue(deque.isEmpty());
+  }
+
   /**
    * Null elements are prohibited in ArrayDeque.
    */