# HG changeset patch
# User dl
# Date 1527050811 25200
# Node ID 45093fb73c6d0ba65e823c1a75c7a69b241302ed
# Parent  7b259287cdd20f6ef907d8c0f07ff195e3c00579
8202685: Optimize ArrayList subList replaceAll
Reviewed-by: martin, psandoz, igerasim, redestad, dholmes, smarks, jrose, plevart

diff -r 7b259287cdd2 -r 45093fb73c6d src/java.base/share/classes/java/util/ArrayList.java
--- a/src/java.base/share/classes/java/util/ArrayList.java	Tue May 22 16:19:31 2018 -0700
+++ b/src/java.base/share/classes/java/util/ArrayList.java	Tue May 22 21:46:51 2018 -0700
@@ -1221,6 +1221,10 @@
             return true;
         }
 
+        public void replaceAll(UnaryOperator<E> operator) {
+            root.replaceAllRange(operator, offset, offset + size);
+        }
+
         public boolean removeAll(Collection<?> c) {
             return batchRemove(c, false);
         }
@@ -1724,15 +1728,18 @@
 
     @Override
     public void replaceAll(UnaryOperator<E> operator) {
+        replaceAllRange(operator, 0, size);
+        modCount++;
+    }
+
+    private void replaceAllRange(UnaryOperator<E> operator, int i, int end) {
         Objects.requireNonNull(operator);
         final int expectedModCount = modCount;
         final Object[] es = elementData;
-        final int size = this.size;
-        for (int i = 0; modCount == expectedModCount && i < size; i++)
+        for (; modCount == expectedModCount && i < end; i++)
             es[i] = operator.apply(elementAt(es, i));
         if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
-        modCount++;
     }
 
     @Override
diff -r 7b259287cdd2 -r 45093fb73c6d test/jdk/java/util/concurrent/tck/Collection8Test.java
--- a/test/jdk/java/util/concurrent/tck/Collection8Test.java	Tue May 22 16:19:31 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/Collection8Test.java	Tue May 22 21:46:51 2018 -0700
@@ -616,15 +616,32 @@
     public void testRemoveAfterForEachRemaining() {
         Collection c = impl.emptyCollection();
         ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        ArrayList copy = new ArrayList();
+        boolean ordered = c.spliterator().hasCharacteristics(Spliterator.ORDERED);
         testCollection: {
             int n = 3 + rnd.nextInt(2);
-            for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
+            for (int i = 0; i < n; i++) {
+                Object x = impl.makeElement(i);
+                c.add(x);
+                copy.add(x);
+            }
             Iterator it = c.iterator();
-            assertTrue(it.hasNext());
-            assertEquals(impl.makeElement(0), it.next());
-            assertTrue(it.hasNext());
-            assertEquals(impl.makeElement(1), it.next());
-            it.forEachRemaining(e -> assertTrue(c.contains(e)));
+            if (ordered) {
+                if (rnd.nextBoolean()) assertTrue(it.hasNext());
+                assertEquals(impl.makeElement(0), it.next());
+                if (rnd.nextBoolean()) assertTrue(it.hasNext());
+                assertEquals(impl.makeElement(1), it.next());
+            } else {
+                if (rnd.nextBoolean()) assertTrue(it.hasNext());
+                assertTrue(copy.contains(it.next()));
+                if (rnd.nextBoolean()) assertTrue(it.hasNext());
+                assertTrue(copy.contains(it.next()));
+            }
+            if (rnd.nextBoolean()) assertTrue(it.hasNext());
+            it.forEachRemaining(
+                e -> {
+                    assertTrue(c.contains(e));
+                    assertTrue(copy.contains(e));});
             if (testImplementationDetails) {
                 if (c instanceof java.util.concurrent.ArrayBlockingQueue) {
                     assertIteratorExhausted(it);
@@ -634,14 +651,17 @@
                         break testCollection;
                     }
                     assertEquals(n - 1, c.size());
-                    for (int i = 0; i < n - 1; i++)
-                        assertTrue(c.contains(impl.makeElement(i)));
-                    assertFalse(c.contains(impl.makeElement(n - 1)));
+                    if (ordered) {
+                        for (int i = 0; i < n - 1; i++)
+                            assertTrue(c.contains(impl.makeElement(i)));
+                        assertFalse(c.contains(impl.makeElement(n - 1)));
+                    }
                 }
             }
         }
         if (c instanceof Deque) {
             Deque d = (Deque) impl.emptyCollection();
+            assertTrue(ordered);
             int n = 3 + rnd.nextInt(2);
             for (int i = 0; i < n; i++) d.add(impl.makeElement(i));
             Iterator it = d.descendingIterator();
@@ -959,6 +979,25 @@
         } catch (java.io.NotSerializableException acceptable) {}
     }
 
+    public void DISABLED_testReplaceAllIsNotStructuralModification() {
+        Collection c = impl.emptyCollection();
+        if (!(c instanceof List))
+            return;
+        List list = (List) c;
+        ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        for (int n = rnd.nextInt(2, 10); n--> 0; )
+            list.add(impl.makeElement(rnd.nextInt()));
+        ArrayList copy = new ArrayList(list);
+        int size = list.size(), half = size / 2;
+        Iterator it = list.iterator();
+        for (int i = 0; i < half; i++)
+            assertEquals(it.next(), copy.get(i));
+        list.replaceAll(n -> n);
+        // ConcurrentModificationException must not be thrown here.
+        for (int i = half; i < size; i++)
+            assertEquals(it.next(), copy.get(i));
+    }
+
 //     public void testCollection8DebugFail() {
 //         fail(impl.klazz().getSimpleName());
 //     }