changeset 49708:260bf39376a4

8200258: Improve CopyOnWriteArrayList subList code Reviewed-by: martin, psandoz, smarks
author dl
date Tue, 10 Apr 2018 11:33:29 -0700
parents 79d2c9da2c26
children b5705ade8c8d
files src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java test/jdk/java/util/Collection/IteratorMicroBenchmark.java test/jdk/java/util/Collection/RemoveMicroBenchmark.java test/jdk/java/util/concurrent/tck/Collection8Test.java test/jdk/java/util/concurrent/tck/CopyOnWriteArrayListTest.java test/jdk/java/util/concurrent/tck/CopyOnWriteArraySetTest.java test/jdk/java/util/concurrent/tck/JSR166TestCase.java test/jdk/java/util/concurrent/tck/LinkedListTest.java test/jdk/java/util/concurrent/tck/VectorTest.java
diffstat 9 files changed, 1390 insertions(+), 770 deletions(-) [+]
line wrap: on
line diff
--- a/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java	Tue Apr 10 11:29:37 2018 -0700
+++ b/src/java.base/share/classes/java/util/concurrent/CopyOnWriteArrayList.java	Tue Apr 10 11:33:29 2018 -0700
@@ -35,7 +35,6 @@
 package java.util.concurrent;
 
 import java.lang.reflect.Field;
-import java.util.AbstractList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Comparator;
@@ -134,17 +133,17 @@
      * @throws NullPointerException if the specified collection is null
      */
     public CopyOnWriteArrayList(Collection<? extends E> c) {
-        Object[] elements;
+        Object[] es;
         if (c.getClass() == CopyOnWriteArrayList.class)
-            elements = ((CopyOnWriteArrayList<?>)c).getArray();
+            es = ((CopyOnWriteArrayList<?>)c).getArray();
         else {
-            elements = c.toArray();
+            es = c.toArray();
             // defend against c.toArray (incorrectly) not returning Object[]
             // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
-            if (elements.getClass() != Object[].class)
-                elements = Arrays.copyOf(elements, elements.length, Object[].class);
+            if (es.getClass() != Object[].class)
+                es = Arrays.copyOf(es, es.length, Object[].class);
         }
-        setArray(elements);
+        setArray(es);
     }
 
     /**
@@ -180,20 +179,19 @@
      * static version of indexOf, to allow repeated calls without
      * needing to re-acquire array each time.
      * @param o element to search for
-     * @param elements the array
-     * @param index first index to search
-     * @param fence one past last index to search
+     * @param es the array
+     * @param from first index to search
+     * @param to one past last index to search
      * @return index of element, or -1 if absent
      */
-    private static int indexOf(Object o, Object[] elements,
-                               int index, int fence) {
+    private static int indexOfRange(Object o, Object[] es, int from, int to) {
         if (o == null) {
-            for (int i = index; i < fence; i++)
-                if (elements[i] == null)
+            for (int i = from; i < to; i++)
+                if (es[i] == null)
                     return i;
         } else {
-            for (int i = index; i < fence; i++)
-                if (o.equals(elements[i]))
+            for (int i = from; i < to; i++)
+                if (o.equals(es[i]))
                     return i;
         }
         return -1;
@@ -202,18 +200,19 @@
     /**
      * static version of lastIndexOf.
      * @param o element to search for
-     * @param elements the array
-     * @param index first index to search
+     * @param es the array
+     * @param from index of first element of range, last element to search
+     * @param to one past last element of range, first element to search
      * @return index of element, or -1 if absent
      */
-    private static int lastIndexOf(Object o, Object[] elements, int index) {
+    private static int lastIndexOfRange(Object o, Object[] es, int from, int to) {
         if (o == null) {
-            for (int i = index; i >= 0; i--)
-                if (elements[i] == null)
+            for (int i = to - 1; i >= from; i--)
+                if (es[i] == null)
                     return i;
         } else {
-            for (int i = index; i >= 0; i--)
-                if (o.equals(elements[i]))
+            for (int i = to - 1; i >= from; i--)
+                if (o.equals(es[i]))
                     return i;
         }
         return -1;
@@ -228,16 +227,15 @@
      * @return {@code true} if this list contains the specified element
      */
     public boolean contains(Object o) {
-        Object[] elements = getArray();
-        return indexOf(o, elements, 0, elements.length) >= 0;
+        return indexOf(o) >= 0;
     }
 
     /**
      * {@inheritDoc}
      */
     public int indexOf(Object o) {
-        Object[] elements = getArray();
-        return indexOf(o, elements, 0, elements.length);
+        Object[] es = getArray();
+        return indexOfRange(o, es, 0, es.length);
     }
 
     /**
@@ -256,16 +254,16 @@
      * @throws IndexOutOfBoundsException if the specified index is negative
      */
     public int indexOf(E e, int index) {
-        Object[] elements = getArray();
-        return indexOf(e, elements, index, elements.length);
+        Object[] es = getArray();
+        return indexOfRange(e, es, index, es.length);
     }
 
     /**
      * {@inheritDoc}
      */
     public int lastIndexOf(Object o) {
-        Object[] elements = getArray();
-        return lastIndexOf(o, elements, elements.length - 1);
+        Object[] es = getArray();
+        return lastIndexOfRange(o, es, 0, es.length);
     }
 
     /**
@@ -285,8 +283,8 @@
      *         than or equal to the current size of this list
      */
     public int lastIndexOf(E e, int index) {
-        Object[] elements = getArray();
-        return lastIndexOf(e, elements, index);
+        Object[] es = getArray();
+        return lastIndexOfRange(e, es, 0, index + 1);
     }
 
     /**
@@ -322,8 +320,7 @@
      * @return an array containing all the elements in this list
      */
     public Object[] toArray() {
-        Object[] elements = getArray();
-        return Arrays.copyOf(elements, elements.length);
+        return getArray().clone();
     }
 
     /**
@@ -366,12 +363,12 @@
      */
     @SuppressWarnings("unchecked")
     public <T> T[] toArray(T[] a) {
-        Object[] elements = getArray();
-        int len = elements.length;
+        Object[] es = getArray();
+        int len = es.length;
         if (a.length < len)
-            return (T[]) Arrays.copyOf(elements, len, a.getClass());
+            return (T[]) Arrays.copyOf(es, len, a.getClass());
         else {
-            System.arraycopy(elements, 0, a, 0, len);
+            System.arraycopy(es, 0, a, 0, len);
             if (a.length > len)
                 a[len] = null;
             return a;
@@ -406,17 +403,13 @@
      */
     public E set(int index, E element) {
         synchronized (lock) {
-            Object[] elements = getArray();
-            E oldValue = elementAt(elements, index);
+            Object[] es = getArray();
+            E oldValue = elementAt(es, index);
 
             if (oldValue != element) {
-                int len = elements.length;
-                Object[] newElements = Arrays.copyOf(elements, len);
-                newElements[index] = element;
-                setArray(newElements);
-            } else {
-                // Not quite a no-op; ensures volatile write semantics
-                setArray(elements);
+                es = es.clone();
+                es[index] = element;
+                setArray(es);
             }
             return oldValue;
         }
@@ -430,11 +423,11 @@
      */
     public boolean add(E e) {
         synchronized (lock) {
-            Object[] elements = getArray();
-            int len = elements.length;
-            Object[] newElements = Arrays.copyOf(elements, len + 1);
-            newElements[len] = e;
-            setArray(newElements);
+            Object[] es = getArray();
+            int len = es.length;
+            es = Arrays.copyOf(es, len + 1);
+            es[len] = e;
+            setArray(es);
             return true;
         }
     }
@@ -448,18 +441,18 @@
      */
     public void add(int index, E element) {
         synchronized (lock) {
-            Object[] elements = getArray();
-            int len = elements.length;
+            Object[] es = getArray();
+            int len = es.length;
             if (index > len || index < 0)
                 throw new IndexOutOfBoundsException(outOfBounds(index, len));
             Object[] newElements;
             int numMoved = len - index;
             if (numMoved == 0)
-                newElements = Arrays.copyOf(elements, len + 1);
+                newElements = Arrays.copyOf(es, len + 1);
             else {
                 newElements = new Object[len + 1];
-                System.arraycopy(elements, 0, newElements, 0, index);
-                System.arraycopy(elements, index, newElements, index + 1,
+                System.arraycopy(es, 0, newElements, 0, index);
+                System.arraycopy(es, index, newElements, index + 1,
                                  numMoved);
             }
             newElements[index] = element;
@@ -476,19 +469,20 @@
      */
     public E remove(int index) {
         synchronized (lock) {
-            Object[] elements = getArray();
-            int len = elements.length;
-            E oldValue = elementAt(elements, index);
+            Object[] es = getArray();
+            int len = es.length;
+            E oldValue = elementAt(es, index);
             int numMoved = len - index - 1;
+            Object[] newElements;
             if (numMoved == 0)
-                setArray(Arrays.copyOf(elements, len - 1));
+                newElements = Arrays.copyOf(es, len - 1);
             else {
-                Object[] newElements = new Object[len - 1];
-                System.arraycopy(elements, 0, newElements, 0, index);
-                System.arraycopy(elements, index + 1, newElements, index,
+                newElements = new Object[len - 1];
+                System.arraycopy(es, 0, newElements, 0, index);
+                System.arraycopy(es, index + 1, newElements, index,
                                  numMoved);
-                setArray(newElements);
             }
+            setArray(newElements);
             return oldValue;
         }
     }
@@ -507,7 +501,7 @@
      */
     public boolean remove(Object o) {
         Object[] snapshot = getArray();
-        int index = indexOf(o, snapshot, 0, snapshot.length);
+        int index = indexOfRange(o, snapshot, 0, snapshot.length);
         return index >= 0 && remove(o, snapshot, index);
     }
 
@@ -532,7 +526,7 @@
                     return false;
                 if (current[index] == o)
                     break findIndex;
-                index = indexOf(o, current, index, len);
+                index = indexOfRange(o, current, index, len);
                 if (index < 0)
                     return false;
             }
@@ -560,19 +554,19 @@
      */
     void removeRange(int fromIndex, int toIndex) {
         synchronized (lock) {
-            Object[] elements = getArray();
-            int len = elements.length;
+            Object[] es = getArray();
+            int len = es.length;
 
             if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
                 throw new IndexOutOfBoundsException();
             int newlen = len - (toIndex - fromIndex);
             int numMoved = len - toIndex;
             if (numMoved == 0)
-                setArray(Arrays.copyOf(elements, newlen));
+                setArray(Arrays.copyOf(es, newlen));
             else {
                 Object[] newElements = new Object[newlen];
-                System.arraycopy(elements, 0, newElements, 0, fromIndex);
-                System.arraycopy(elements, toIndex, newElements,
+                System.arraycopy(es, 0, newElements, 0, fromIndex);
+                System.arraycopy(es, toIndex, newElements,
                                  fromIndex, numMoved);
                 setArray(newElements);
             }
@@ -587,7 +581,7 @@
      */
     public boolean addIfAbsent(E e) {
         Object[] snapshot = getArray();
-        return indexOf(e, snapshot, 0, snapshot.length) < 0
+        return indexOfRange(e, snapshot, 0, snapshot.length) < 0
             && addIfAbsent(e, snapshot);
     }
 
@@ -606,7 +600,7 @@
                     if (current[i] != snapshot[i]
                         && Objects.equals(e, current[i]))
                         return false;
-                if (indexOf(e, current, common, len) >= 0)
+                if (indexOfRange(e, current, common, len) >= 0)
                         return false;
             }
             Object[] newElements = Arrays.copyOf(current, len + 1);
@@ -627,10 +621,10 @@
      * @see #contains(Object)
      */
     public boolean containsAll(Collection<?> c) {
-        Object[] elements = getArray();
-        int len = elements.length;
+        Object[] es = getArray();
+        int len = es.length;
         for (Object e : c) {
-            if (indexOf(e, elements, 0, len) < 0)
+            if (indexOfRange(e, es, 0, len) < 0)
                 return false;
         }
         return true;
@@ -694,18 +688,18 @@
         if (cs.length == 0)
             return 0;
         synchronized (lock) {
-            Object[] elements = getArray();
-            int len = elements.length;
+            Object[] es = getArray();
+            int len = es.length;
             int added = 0;
             // uniquify and compact elements in cs
             for (int i = 0; i < cs.length; ++i) {
                 Object e = cs[i];
-                if (indexOf(e, elements, 0, len) < 0 &&
-                    indexOf(e, cs, 0, added) < 0)
+                if (indexOfRange(e, es, 0, len) < 0 &&
+                    indexOfRange(e, cs, 0, added) < 0)
                     cs[added++] = e;
             }
             if (added > 0) {
-                Object[] newElements = Arrays.copyOf(elements, len + added);
+                Object[] newElements = Arrays.copyOf(es, len + added);
                 System.arraycopy(cs, 0, newElements, len, added);
                 setArray(newElements);
             }
@@ -739,15 +733,16 @@
         if (cs.length == 0)
             return false;
         synchronized (lock) {
-            Object[] elements = getArray();
-            int len = elements.length;
+            Object[] es = getArray();
+            int len = es.length;
+            Object[] newElements;
             if (len == 0 && cs.getClass() == Object[].class)
-                setArray(cs);
+                newElements = cs;
             else {
-                Object[] newElements = Arrays.copyOf(elements, len + cs.length);
+                newElements = Arrays.copyOf(es, len + cs.length);
                 System.arraycopy(cs, 0, newElements, len, cs.length);
-                setArray(newElements);
             }
+            setArray(newElements);
             return true;
         }
     }
@@ -771,8 +766,8 @@
     public boolean addAll(int index, Collection<? extends E> c) {
         Object[] cs = c.toArray();
         synchronized (lock) {
-            Object[] elements = getArray();
-            int len = elements.length;
+            Object[] es = getArray();
+            int len = es.length;
             if (index > len || index < 0)
                 throw new IndexOutOfBoundsException(outOfBounds(index, len));
             if (cs.length == 0)
@@ -780,11 +775,11 @@
             int numMoved = len - index;
             Object[] newElements;
             if (numMoved == 0)
-                newElements = Arrays.copyOf(elements, len + cs.length);
+                newElements = Arrays.copyOf(es, len + cs.length);
             else {
                 newElements = new Object[len + cs.length];
-                System.arraycopy(elements, 0, newElements, 0, index);
-                System.arraycopy(elements, index,
+                System.arraycopy(es, 0, newElements, 0, index);
+                System.arraycopy(es, index,
                                  newElements, index + cs.length,
                                  numMoved);
             }
@@ -866,14 +861,14 @@
     }
 
     public void replaceAll(UnaryOperator<E> operator) {
-        Objects.requireNonNull(operator);
         synchronized (lock) {
-            replaceAll(operator, 0, getArray().length);
+            replaceAllRange(operator, 0, getArray().length);
         }
     }
 
-    void replaceAll(UnaryOperator<E> operator, int i, int end) {
+    void replaceAllRange(UnaryOperator<E> operator, int i, int end) {
         // assert Thread.holdsLock(lock);
+        Objects.requireNonNull(operator);
         final Object[] es = getArray().clone();
         for (; i < end; i++)
             es[i] = operator.apply(elementAt(es, i));
@@ -882,12 +877,12 @@
 
     public void sort(Comparator<? super E> c) {
         synchronized (lock) {
-            sort(c, 0, getArray().length);
+            sortRange(c, 0, getArray().length);
         }
     }
 
     @SuppressWarnings("unchecked")
-    void sort(Comparator<? super E> c, int i, int end) {
+    void sortRange(Comparator<? super E> c, int i, int end) {
         // assert Thread.holdsLock(lock);
         final Object[] es = getArray().clone();
         Arrays.sort(es, i, end, (Comparator<Object>)c);
@@ -908,12 +903,12 @@
 
         s.defaultWriteObject();
 
-        Object[] elements = getArray();
+        Object[] es = getArray();
         // Write out array length
-        s.writeInt(elements.length);
+        s.writeInt(es.length);
 
         // Write out all elements in the proper order.
-        for (Object element : elements)
+        for (Object element : es)
             s.writeObject(element);
     }
 
@@ -935,12 +930,12 @@
         // Read in array length and allocate array
         int len = s.readInt();
         SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, len);
-        Object[] elements = new Object[len];
+        Object[] es = new Object[len];
 
         // Read in all elements in the proper order.
         for (int i = 0; i < len; i++)
-            elements[i] = s.readObject();
-        setArray(elements);
+            es[i] = s.readObject();
+        setArray(es);
     }
 
     /**
@@ -986,6 +981,15 @@
         return !it.hasNext();
     }
 
+    private static int hashCodeOfRange(Object[] es, int from, int to) {
+        int hashCode = 1;
+        for (int i = from; i < to; i++) {
+            Object x = es[i];
+            hashCode = 31 * hashCode + (x == null ? 0 : x.hashCode());
+        }
+        return hashCode;
+    }
+
     /**
      * Returns the hash code value for this list.
      *
@@ -994,10 +998,8 @@
      * @return the hash code value for this list
      */
     public int hashCode() {
-        int hashCode = 1;
-        for (Object x : getArray())
-            hashCode = 31 * hashCode + (x == null ? 0 : x.hashCode());
-        return hashCode;
+        Object[] es = getArray();
+        return hashCodeOfRange(es, 0, es.length);
     }
 
     /**
@@ -1037,12 +1039,12 @@
      * @throws IndexOutOfBoundsException {@inheritDoc}
      */
     public ListIterator<E> listIterator(int index) {
-        Object[] elements = getArray();
-        int len = elements.length;
+        Object[] es = getArray();
+        int len = es.length;
         if (index < 0 || index > len)
             throw new IndexOutOfBoundsException(outOfBounds(index, len));
 
-        return new COWIterator<E>(elements, index);
+        return new COWIterator<E>(es, index);
     }
 
     /**
@@ -1070,9 +1072,9 @@
         /** Index of element to be returned by subsequent call to next.  */
         private int cursor;
 
-        COWIterator(Object[] elements, int initialCursor) {
+        COWIterator(Object[] es, int initialCursor) {
             cursor = initialCursor;
-            snapshot = elements;
+            snapshot = es;
         }
 
         public boolean hasNext() {
@@ -1102,7 +1104,7 @@
         }
 
         public int previousIndex() {
-            return cursor-1;
+            return cursor - 1;
         }
 
         /**
@@ -1133,14 +1135,13 @@
         }
 
         @Override
-        @SuppressWarnings("unchecked")
         public void forEachRemaining(Consumer<? super E> action) {
             Objects.requireNonNull(action);
             final int size = snapshot.length;
-            for (int i = cursor; i < size; i++) {
-                action.accept((E) snapshot[i]);
-            }
+            int i = cursor;
             cursor = size;
+            for (; i < size; i++)
+                action.accept(elementAt(snapshot, i));
         }
     }
 
@@ -1161,136 +1162,264 @@
      */
     public List<E> subList(int fromIndex, int toIndex) {
         synchronized (lock) {
-            Object[] elements = getArray();
-            int len = elements.length;
-            if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
+            Object[] es = getArray();
+            int len = es.length;
+            int size = toIndex - fromIndex;
+            if (fromIndex < 0 || toIndex > len || size < 0)
                 throw new IndexOutOfBoundsException();
-            return new COWSubList<E>(this, fromIndex, toIndex);
+            return new COWSubList(es, fromIndex, size);
         }
     }
 
     /**
      * Sublist for CopyOnWriteArrayList.
      */
-    private static class COWSubList<E>
-        extends AbstractList<E>
-        implements RandomAccess
-    {
-        private final CopyOnWriteArrayList<E> l;
+    private class COWSubList implements List<E>, RandomAccess {
         private final int offset;
         private int size;
         private Object[] expectedArray;
 
-        // only call this holding l's lock
-        COWSubList(CopyOnWriteArrayList<E> list,
-                   int fromIndex, int toIndex) {
-            // assert Thread.holdsLock(list.lock);
-            l = list;
-            expectedArray = l.getArray();
-            offset = fromIndex;
-            size = toIndex - fromIndex;
+        COWSubList(Object[] es, int offset, int size) {
+            // assert Thread.holdsLock(lock);
+            expectedArray = es;
+            this.offset = offset;
+            this.size = size;
         }
 
-        // only call this holding l's lock
         private void checkForComodification() {
-            // assert Thread.holdsLock(l.lock);
-            if (l.getArray() != expectedArray)
+            // assert Thread.holdsLock(lock);
+            if (getArray() != expectedArray)
                 throw new ConcurrentModificationException();
         }
 
         private Object[] getArrayChecked() {
-            // assert Thread.holdsLock(l.lock);
-            Object[] a = l.getArray();
+            // assert Thread.holdsLock(lock);
+            Object[] a = getArray();
             if (a != expectedArray)
                 throw new ConcurrentModificationException();
             return a;
         }
 
-        // only call this holding l's lock
         private void rangeCheck(int index) {
-            // assert Thread.holdsLock(l.lock);
+            // assert Thread.holdsLock(lock);
             if (index < 0 || index >= size)
                 throw new IndexOutOfBoundsException(outOfBounds(index, size));
         }
 
+        private void rangeCheckForAdd(int index) {
+            // assert Thread.holdsLock(lock);
+            if (index < 0 || index > size)
+                throw new IndexOutOfBoundsException(outOfBounds(index, size));
+        }
+
+        public Object[] toArray() {
+            final Object[] es;
+            final int offset;
+            final int size;
+            synchronized (lock) {
+                es = getArrayChecked();
+                offset = this.offset;
+                size = this.size;
+            }
+            return Arrays.copyOfRange(es, offset, offset + size);
+        }
+
+        @SuppressWarnings("unchecked")
+        public <T> T[] toArray(T[] a) {
+            final Object[] es;
+            final int offset;
+            final int size;
+            synchronized (lock) {
+                es = getArrayChecked();
+                offset = this.offset;
+                size = this.size;
+            }
+            if (a.length < size)
+                return (T[]) Arrays.copyOfRange(
+                        es, offset, offset + size, a.getClass());
+            else {
+                System.arraycopy(es, offset, a, 0, size);
+                if (a.length > size)
+                    a[size] = null;
+                return a;
+            }
+        }
+
+        public int indexOf(Object o) {
+            final Object[] es;
+            final int offset;
+            final int size;
+            synchronized (lock) {
+                es = getArrayChecked();
+                offset = this.offset;
+                size = this.size;
+            }
+            int i = indexOfRange(o, es, offset, offset + size);
+            return (i == -1) ? -1 : i - offset;
+        }
+
+        public int lastIndexOf(Object o) {
+            final Object[] es;
+            final int offset;
+            final int size;
+            synchronized (lock) {
+                es = getArrayChecked();
+                offset = this.offset;
+                size = this.size;
+            }
+            int i = lastIndexOfRange(o, es, offset, offset + size);
+            return (i == -1) ? -1 : i - offset;
+        }
+
+        public boolean contains(Object o) {
+            return indexOf(o) >= 0;
+        }
+
+        public boolean containsAll(Collection<?> c) {
+            final Object[] es;
+            final int offset;
+            final int size;
+            synchronized (lock) {
+                es = getArrayChecked();
+                offset = this.offset;
+                size = this.size;
+            }
+            for (Object o : c)
+                if (indexOfRange(o, es, offset, offset + size) < 0)
+                    return false;
+            return true;
+        }
+
+        public boolean isEmpty() {
+            return size() == 0;
+        }
+
+        public String toString() {
+            return Arrays.toString(toArray());
+        }
+
+        public int hashCode() {
+            final Object[] es;
+            final int offset;
+            final int size;
+            synchronized (lock) {
+                es = getArrayChecked();
+                offset = this.offset;
+                size = this.size;
+            }
+            return hashCodeOfRange(es, offset, offset + size);
+        }
+
+        public boolean equals(Object o) {
+            if (o == this)
+                return true;
+            if (!(o instanceof List))
+                return false;
+            Iterator<?> it = ((List<?>)o).iterator();
+
+            final Object[] es;
+            final int offset;
+            final int size;
+            synchronized (lock) {
+                es = getArrayChecked();
+                offset = this.offset;
+                size = this.size;
+            }
+
+            for (int i = offset, end = offset + size; i < end; i++)
+                if (!it.hasNext() || !Objects.equals(es[i], it.next()))
+                    return false;
+            return !it.hasNext();
+        }
+
         public E set(int index, E element) {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 rangeCheck(index);
                 checkForComodification();
-                E x = l.set(offset + index, element);
-                expectedArray = l.getArray();
+                E x = CopyOnWriteArrayList.this.set(offset + index, element);
+                expectedArray = getArray();
                 return x;
             }
         }
 
         public E get(int index) {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 rangeCheck(index);
                 checkForComodification();
-                return l.get(offset + index);
+                return CopyOnWriteArrayList.this.get(offset + index);
             }
         }
 
         public int size() {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 checkForComodification();
                 return size;
             }
         }
 
         public boolean add(E element) {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 checkForComodification();
-                l.add(offset + size, element);
-                expectedArray = l.getArray();
+                CopyOnWriteArrayList.this.add(offset + size, element);
+                expectedArray = getArray();
                 size++;
             }
             return true;
         }
 
         public void add(int index, E element) {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 checkForComodification();
-                if (index < 0 || index > size)
-                    throw new IndexOutOfBoundsException
-                        (outOfBounds(index, size));
-                l.add(offset + index, element);
-                expectedArray = l.getArray();
+                rangeCheckForAdd(index);
+                CopyOnWriteArrayList.this.add(offset + index, element);
+                expectedArray = getArray();
                 size++;
             }
         }
 
         public boolean addAll(Collection<? extends E> c) {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 final Object[] oldArray = getArrayChecked();
-                boolean modified = l.addAll(offset + size, c);
-                size += (expectedArray = l.getArray()).length - oldArray.length;
+                boolean modified =
+                    CopyOnWriteArrayList.this.addAll(offset + size, c);
+                size += (expectedArray = getArray()).length - oldArray.length;
+                return modified;
+            }
+        }
+
+        public boolean addAll(int index, Collection<? extends E> c) {
+            synchronized (lock) {
+                rangeCheckForAdd(index);
+                final Object[] oldArray = getArrayChecked();
+                boolean modified =
+                    CopyOnWriteArrayList.this.addAll(offset + index, c);
+                size += (expectedArray = getArray()).length - oldArray.length;
                 return modified;
             }
         }
 
         public void clear() {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 checkForComodification();
-                l.removeRange(offset, offset + size);
-                expectedArray = l.getArray();
+                removeRange(offset, offset + size);
+                expectedArray = getArray();
                 size = 0;
             }
         }
 
         public E remove(int index) {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 rangeCheck(index);
                 checkForComodification();
-                E result = l.remove(offset + index);
-                expectedArray = l.getArray();
+                E result = CopyOnWriteArrayList.this.remove(offset + index);
+                expectedArray = getArray();
                 size--;
                 return result;
             }
         }
 
         public boolean remove(Object o) {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 checkForComodification();
                 int index = indexOf(o);
                 if (index == -1)
@@ -1301,36 +1430,35 @@
         }
 
         public Iterator<E> iterator() {
-            synchronized (l.lock) {
-                checkForComodification();
-                return new COWSubListIterator<E>(l, 0, offset, size);
-            }
+            return listIterator(0);
+        }
+
+        public ListIterator<E> listIterator() {
+            return listIterator(0);
         }
 
         public ListIterator<E> listIterator(int index) {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 checkForComodification();
-                if (index < 0 || index > size)
-                    throw new IndexOutOfBoundsException
-                        (outOfBounds(index, size));
-                return new COWSubListIterator<E>(l, index, offset, size);
+                rangeCheckForAdd(index);
+                return new COWSubListIterator<E>(
+                    CopyOnWriteArrayList.this, index, offset, size);
             }
         }
 
         public List<E> subList(int fromIndex, int toIndex) {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 checkForComodification();
                 if (fromIndex < 0 || toIndex > size || fromIndex > toIndex)
                     throw new IndexOutOfBoundsException();
-                return new COWSubList<E>(l, fromIndex + offset,
-                                         toIndex + offset);
+                return new COWSubList(expectedArray, fromIndex + offset, toIndex - fromIndex);
             }
         }
 
         public void forEach(Consumer<? super E> action) {
             Objects.requireNonNull(action);
             int i, end; final Object[] es;
-            synchronized (l.lock) {
+            synchronized (lock) {
                 es = getArrayChecked();
                 i = offset;
                 end = i + size;
@@ -1340,19 +1468,18 @@
         }
 
         public void replaceAll(UnaryOperator<E> operator) {
-            Objects.requireNonNull(operator);
-            synchronized (l.lock) {
+            synchronized (lock) {
                 checkForComodification();
-                l.replaceAll(operator, offset, offset + size);
-                expectedArray = l.getArray();
+                replaceAllRange(operator, offset, offset + size);
+                expectedArray = getArray();
             }
         }
 
         public void sort(Comparator<? super E> c) {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 checkForComodification();
-                l.sort(c, offset, offset + size);
-                expectedArray = l.getArray();
+                sortRange(c, offset, offset + size);
+                expectedArray = getArray();
             }
         }
 
@@ -1372,16 +1499,17 @@
         }
 
         private boolean bulkRemove(Predicate<? super E> filter) {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 final Object[] oldArray = getArrayChecked();
-                boolean modified = l.bulkRemove(filter, offset, offset + size);
-                size += (expectedArray = l.getArray()).length - oldArray.length;
+                boolean modified = CopyOnWriteArrayList.this.bulkRemove(
+                    filter, offset, offset + size);
+                size += (expectedArray = getArray()).length - oldArray.length;
                 return modified;
             }
         }
 
         public Spliterator<E> spliterator() {
-            synchronized (l.lock) {
+            synchronized (lock) {
                 return Spliterators.spliterator(
                         getArrayChecked(), offset, offset + size,
                         Spliterator.IMMUTABLE | Spliterator.ORDERED);
@@ -1398,7 +1526,7 @@
         COWSubListIterator(List<E> l, int index, int offset, int size) {
             this.offset = offset;
             this.size = size;
-            it = l.listIterator(index+offset);
+            it = l.listIterator(index + offset);
         }
 
         public boolean hasNext() {
@@ -1447,7 +1575,7 @@
         @SuppressWarnings("unchecked")
         public void forEachRemaining(Consumer<? super E> action) {
             Objects.requireNonNull(action);
-            while (nextIndex() < size) {
+            while (hasNext()) {
                 action.accept(it.next());
             }
         }
--- a/test/jdk/java/util/Collection/IteratorMicroBenchmark.java	Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/Collection/IteratorMicroBenchmark.java	Tue Apr 10 11:33:29 2018 -0700
@@ -36,6 +36,7 @@
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Deque;
+import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
@@ -55,6 +56,7 @@
 import java.util.concurrent.ThreadLocalRandom;
 import java.util.concurrent.TimeUnit;
 import java.util.concurrent.atomic.LongAdder;
+import java.util.function.UnaryOperator;
 import java.util.regex.Pattern;
 import java.util.stream.Stream;
 
@@ -75,6 +77,13 @@
         public Job(String name) { this.name = name; }
         public String name() { return name; }
         public abstract void work() throws Throwable;
+        public void run() {
+            try { work(); }
+            catch (Throwable ex) {
+                // current job cannot always be deduced from stacktrace.
+                throw new RuntimeException("Job failed: " + name(), ex);
+            }
+        }
     }
 
     final int iterations;
@@ -102,6 +111,7 @@
     static void forceFullGc() {
         CountDownLatch finalizeDone = new CountDownLatch(1);
         WeakReference<?> ref = new WeakReference<Object>(new Object() {
+            @SuppressWarnings("deprecation")
             protected void finalize() { finalizeDone.countDown(); }});
         try {
             for (int i = 0; i < 10; i++) {
@@ -123,7 +133,7 @@
      * compiling everything worth compiling.
      * Returns array of average times per job per run.
      */
-    long[] time0(List<Job> jobs) throws Throwable {
+    long[] time0(List<Job> jobs) {
         final int size = jobs.size();
         long[] nanoss = new long[size];
         for (int i = 0; i < size; i++) {
@@ -132,7 +142,7 @@
             long totalTime;
             int runs = 0;
             long startTime = System.nanoTime();
-            do { job.work(); runs++; }
+            do { job.run(); runs++; }
             while ((totalTime = System.nanoTime() - startTime) < warmupNanos);
             nanoss[i] = totalTime/runs;
         }
@@ -211,10 +221,6 @@
             System.out.println("the answer");
     }
 
-    private static <T> List<T> asSubList(List<T> list) {
-        return list.subList(0, list.size());
-    }
-
     private static <T> Iterable<T> backwards(final List<T> list) {
         return new Iterable<T>() {
             public Iterator<T> iterator() {
@@ -241,11 +247,32 @@
         new IteratorMicroBenchmark(args).run();
     }
 
+    HashMap<Class<?>, String> goodClassName = new HashMap<>();
+
+    String goodClassName(Class<?> klazz) {
+        return goodClassName.computeIfAbsent(
+            klazz,
+            k -> {
+                String simple = k.getSimpleName();
+                return (simple.equals("SubList")) // too simple!
+                    ? k.getName().replaceFirst(".*\\.", "")
+                    : simple;
+            });
+    }
+
+    static List<Integer> makeSubList(List<Integer> list) {
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        int size = list.size();
+        if (size <= 2) return list.subList(0, size);
+        List<Integer> subList = list.subList(rnd.nextInt(0, 2),
+                                             size - rnd.nextInt(0, 2));
+        List<Integer> copy = new ArrayList<>(list);
+        subList.clear();
+        subList.addAll(copy);
+        return subList;
+    }
+
     void run() throws Throwable {
-//         System.out.printf(
-//             "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n",
-//             iterations, size, warmupSeconds, nameFilter);
-
         final ArrayList<Integer> al = new ArrayList<>(size);
 
         // Populate collections with random data
@@ -265,10 +292,14 @@
 
         ArrayList<Job> jobs = Stream.<Collection<Integer>>of(
                 al, ad, abq,
+                makeSubList(new ArrayList<>(al)),
                 new LinkedList<>(al),
+                makeSubList(new LinkedList<>(al)),
                 new PriorityQueue<>(al),
                 new Vector<>(al),
+                makeSubList(new Vector<>(al)),
                 new CopyOnWriteArrayList<>(al),
+                makeSubList(new CopyOnWriteArrayList<>(al)),
                 new ConcurrentLinkedQueue<>(al),
                 new ConcurrentLinkedDeque<>(al),
                 new LinkedBlockingQueue<>(al),
@@ -294,16 +325,25 @@
     Stream<Job> jobs(Collection<Integer> x) {
         return concatStreams(
             collectionJobs(x),
+
             (x instanceof Deque)
             ? dequeJobs((Deque<Integer>)x)
             : Stream.empty(),
+
             (x instanceof List)
             ? listJobs((List<Integer>)x)
             : Stream.empty());
     }
 
+    Object sneakyAdder(int[] sneakySum) {
+        return new Object() {
+            public int hashCode() { throw new AssertionError(); }
+            public boolean equals(Object z) {
+                sneakySum[0] += (int) z; return false; }};
+    }
+
     Stream<Job> collectionJobs(Collection<Integer> x) {
-        String klazz = x.getClass().getSimpleName();
+        final String klazz = goodClassName(x.getClass());
         return Stream.of(
             new Job(klazz + " iterate for loop") {
                 public void work() throws Throwable {
@@ -345,22 +385,28 @@
             new Job(klazz + " contains") {
                 public void work() throws Throwable {
                     int[] sum = new int[1];
-                    Object y = new Object() {
-                        public boolean equals(Object z) {
-                            sum[0] += (int) z; return false; }};
+                    Object sneakyAdder = sneakyAdder(sum);
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        if (x.contains(y)) throw new AssertionError();
+                        if (x.contains(sneakyAdder)) throw new AssertionError();
+                        check.sum(sum[0]);}}},
+            new Job(klazz + " containsAll") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    Collection<Object> sneakyAdderCollection =
+                        Collections.singleton(sneakyAdder(sum));
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        if (x.containsAll(sneakyAdderCollection))
+                            throw new AssertionError();
                         check.sum(sum[0]);}}},
             new Job(klazz + " remove(Object)") {
                 public void work() throws Throwable {
                     int[] sum = new int[1];
-                    Object y = new Object() {
-                        public boolean equals(Object z) {
-                            sum[0] += (int) z; return false; }};
+                    Object sneakyAdder = sneakyAdder(sum);
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        if (x.remove(y)) throw new AssertionError();
+                        if (x.remove(sneakyAdder)) throw new AssertionError();
                         check.sum(sum[0]);}}},
             new Job(klazz + " forEach") {
                 public void work() throws Throwable {
@@ -446,7 +492,7 @@
     }
 
     Stream<Job> dequeJobs(Deque<Integer> x) {
-        String klazz = x.getClass().getSimpleName();
+        String klazz = goodClassName(x.getClass());
         return Stream.of(
             new Job(klazz + " descendingIterator() loop") {
                 public void work() throws Throwable {
@@ -466,48 +512,50 @@
     }
 
     Stream<Job> listJobs(List<Integer> x) {
-        String klazz = x.getClass().getSimpleName();
+        final String klazz = goodClassName(x.getClass());
         return Stream.of(
-            new Job(klazz + " subList toArray()") {
+            new Job(klazz + " listIterator forward loop") {
                 public void work() throws Throwable {
-                    int size = x.size();
                     for (int i = 0; i < iterations; i++) {
-                        int total = Stream.of(x.subList(0, size / 2),
-                                              x.subList(size / 2, size))
-                            .mapToInt(subList -> {
-                                int sum = 0;
-                                for (Object o : subList.toArray())
-                                    sum += (Integer) o;
-                                return sum; })
-                            .sum();
-                        check.sum(total);}}},
-            new Job(klazz + " subList toArray(a)") {
+                        int sum = 0;
+                        ListIterator<Integer> it = x.listIterator();
+                        while (it.hasNext())
+                            sum += it.next();
+                        check.sum(sum);}}},
+            new Job(klazz + " listIterator backward loop") {
                 public void work() throws Throwable {
-                    int size = x.size();
                     for (int i = 0; i < iterations; i++) {
-                        int total = Stream.of(x.subList(0, size / 2),
-                                              x.subList(size / 2, size))
-                            .mapToInt(subList -> {
-                                int sum = 0;
-                                Integer[] a = new Integer[subList.size()];
-                                for (Object o : subList.toArray(a))
-                                    sum += (Integer) o;
-                                return sum; })
-                            .sum();
-                        check.sum(total);}}},
-            new Job(klazz + " subList toArray(empty)") {
+                        int sum = 0;
+                        ListIterator<Integer> it = x.listIterator(x.size());
+                        while (it.hasPrevious())
+                            sum += it.previous();
+                        check.sum(sum);}}},
+            new Job(klazz + " indexOf") {
                 public void work() throws Throwable {
-                    int size = x.size();
-                    Integer[] empty = new Integer[0];
+                    int[] sum = new int[1];
+                    Object sneakyAdder = sneakyAdder(sum);
                     for (int i = 0; i < iterations; i++) {
-                        int total = Stream.of(x.subList(0, size / 2),
-                                              x.subList(size / 2, size))
-                            .mapToInt(subList -> {
-                                int sum = 0;
-                                for (Object o : subList.toArray(empty))
-                                    sum += (Integer) o;
-                                return sum; })
-                            .sum();
-                        check.sum(total);}}});
+                        sum[0] = 0;
+                        if (x.indexOf(sneakyAdder) != -1)
+                            throw new AssertionError();
+                        check.sum(sum[0]);}}},
+            new Job(klazz + " lastIndexOf") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    Object sneakyAdder = sneakyAdder(sum);
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        if (x.lastIndexOf(sneakyAdder) != -1)
+                            throw new AssertionError();
+                        check.sum(sum[0]);}}},
+            new Job(klazz + " replaceAll") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    UnaryOperator<Integer> sneakyAdder =
+                        x -> { sum[0] += x; return x; };
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.replaceAll(sneakyAdder);
+                        check.sum(sum[0]);}}});
     }
 }
--- a/test/jdk/java/util/Collection/RemoveMicroBenchmark.java	Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/Collection/RemoveMicroBenchmark.java	Tue Apr 10 11:33:29 2018 -0700
@@ -27,7 +27,7 @@
  * @run main RemoveMicroBenchmark iterations=1 size=8 warmup=0
  */
 
-import static java.util.stream.Collectors.toList;
+import static java.util.stream.Collectors.toCollection;
 
 import java.lang.ref.WeakReference;
 import java.util.ArrayDeque;
@@ -35,6 +35,7 @@
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Deque;
+import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
@@ -47,6 +48,7 @@
 import java.util.concurrent.BlockingQueue;
 import java.util.concurrent.ConcurrentLinkedDeque;
 import java.util.concurrent.ConcurrentLinkedQueue;
+import java.util.concurrent.CopyOnWriteArrayList;
 import java.util.concurrent.CountDownLatch;
 import java.util.concurrent.LinkedBlockingDeque;
 import java.util.concurrent.LinkedBlockingQueue;
@@ -55,7 +57,7 @@
 import java.util.concurrent.ThreadLocalRandom;
 import java.util.concurrent.TimeUnit;
 import java.util.regex.Pattern;
-import java.util.function.Supplier;
+import java.util.stream.Stream;
 
 /**
  * Usage: [iterations=N] [size=N] [filter=REGEXP] [warmup=SECONDS]
@@ -72,25 +74,38 @@
         public Job(String name) { this.name = name; }
         public String name() { return name; }
         public abstract void work() throws Throwable;
+        public void run() {
+            try { work(); }
+            catch (Throwable ex) {
+                // current job cannot always be deduced from stacktrace.
+                throw new RuntimeException("Job failed: " + name(), ex);
+            }
+        }
     }
 
     final int iterations;
     final int size;             // number of elements in collections
     final double warmupSeconds;
     final long warmupNanos;
-    final Pattern filter;       // select subset of Jobs to run
+    final Pattern nameFilter;   // select subset of Jobs to run
     final boolean reverse;      // reverse order of Jobs
     final boolean shuffle;      // randomize order of Jobs
 
+    final ArrayList<Integer> elements; // contains size random Integers
+
     RemoveMicroBenchmark(String[] args) {
         iterations    = intArg(args, "iterations", 10_000);
         size          = intArg(args, "size", 1000);
         warmupSeconds = doubleArg(args, "warmup", 7.0);
-        filter        = patternArg(args, "filter");
+        nameFilter    = patternArg(args, "filter");
         reverse       = booleanArg(args, "reverse");
         shuffle       = booleanArg(args, "shuffle");
 
         warmupNanos = (long) (warmupSeconds * (1000L * 1000L * 1000L));
+
+        elements = ThreadLocalRandom.current().ints(size)
+            .mapToObj(x -> x)
+            .collect(toCollection(ArrayList::new));
     }
 
     // --------------- GC finalization infrastructure ---------------
@@ -99,6 +114,7 @@
     static void forceFullGc() {
         CountDownLatch finalizeDone = new CountDownLatch(1);
         WeakReference<?> ref = new WeakReference<Object>(new Object() {
+            @SuppressWarnings("deprecation")
             protected void finalize() { finalizeDone.countDown(); }});
         try {
             for (int i = 0; i < 10; i++) {
@@ -120,7 +136,7 @@
      * compiling everything worth compiling.
      * Returns array of average times per job per run.
      */
-    long[] time0(List<Job> jobs) throws Throwable {
+    long[] time0(List<Job> jobs) {
         final int size = jobs.size();
         long[] nanoss = new long[size];
         for (int i = 0; i < size; i++) {
@@ -129,7 +145,7 @@
             long totalTime;
             int runs = 0;
             long startTime = System.nanoTime();
-            do { job.work(); runs++; }
+            do { job.run(); runs++; }
             while ((totalTime = System.nanoTime() - startTime) < warmupNanos);
             nanoss[i] = totalTime/runs;
         }
@@ -203,22 +219,11 @@
         throw new IllegalArgumentException(val);
     }
 
-    private static List<Job> filter(Pattern filter, List<Job> jobs) {
-        return (filter == null) ? jobs
-            : jobs.stream()
-            .filter(job -> filter.matcher(job.name()).find())
-            .collect(toList());
-    }
-
     private static void deoptimize(int sum) {
         if (sum == 42)
             System.out.println("the answer");
     }
 
-    private static <T> List<T> asSubList(List<T> list) {
-        return list.subList(0, list.size());
-    }
-
     private static <T> Iterable<T> backwards(final List<T> list) {
         return new Iterable<T>() {
             public Iterator<T> iterator() {
@@ -245,66 +250,99 @@
         new RemoveMicroBenchmark(args).run();
     }
 
+    HashMap<Class<?>, String> goodClassName = new HashMap<>();
+
+    String goodClassName(Class<?> klazz) {
+        return goodClassName.computeIfAbsent(
+            klazz,
+            k -> {
+                String simple = k.getSimpleName();
+                return (simple.equals("SubList")) // too simple!
+                    ? k.getName().replaceFirst(".*\\.", "")
+                    : simple;
+            });
+    }
+
+    static List<Integer> makeSubList(List<Integer> list) {
+        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        int size = rnd.nextInt(4);
+        for (int i = size; i--> 0; )
+            list.add(rnd.nextInt());
+        int index = rnd.nextInt(size + 1);
+        return list.subList(index, index);
+    }
+
+    private static <T> List<T> asSubList(List<T> list) {
+        return list.subList(0, list.size());
+    }
+
+    @SafeVarargs @SuppressWarnings("varargs")
+    private <T> Stream<T> concatStreams(Stream<T> ... streams) {
+        return Stream.of(streams).flatMap(s -> s);
+    }
+
+    Class<?> topLevelClass(Object x) {
+        for (Class<?> k = x.getClass();; ) {
+            Class<?> enclosing = k.getEnclosingClass();
+            if (enclosing == null)
+                return k;
+            k = enclosing;
+        }
+    }
+
     void run() throws Throwable {
-//         System.out.printf(
-//             "iterations=%d size=%d, warmup=%1g, filter=\"%s\"%n",
-//             iterations, size, warmupSeconds, filter);
-
-        final ArrayList<Integer> al = new ArrayList<>(size);
-
-        // Populate collections with random data
-        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
-        for (int i = 0; i < size; i++)
-            al.add(rnd.nextInt(size));
-
-        ArrayList<Job> jobs = new ArrayList<>();
-
-        List.<Collection<Integer>>of(
-            new ArrayList<>(),
-            new LinkedList<>(),
-            new Vector<>(),
-            new ArrayDeque<>(),
-            new PriorityQueue<>(),
-            new ArrayBlockingQueue<>(al.size()),
-            new ConcurrentLinkedQueue<>(),
-            new ConcurrentLinkedDeque<>(),
-            new LinkedBlockingQueue<>(),
-            new LinkedBlockingDeque<>(),
-            new LinkedTransferQueue<>(),
-            new PriorityBlockingQueue<>()).forEach(
-                x -> {
-                    String klazz = x.getClass().getSimpleName();
-                    jobs.addAll(collectionJobs(klazz, () -> x, al));
-                    if (x instanceof Queue) {
-                        Queue<Integer> queue = (Queue<Integer>) x;
-                        jobs.addAll(queueJobs(klazz, () -> queue, al));
-                    }
-                    if (x instanceof Deque) {
-                        Deque<Integer> deque = (Deque<Integer>) x;
-                        jobs.addAll(dequeJobs(klazz, () -> deque, al));
-                    }
-                    if (x instanceof BlockingQueue) {
-                        BlockingQueue<Integer> q = (BlockingQueue<Integer>) x;
-                        jobs.addAll(blockingQueueJobs(klazz, () -> q, al));
-                    }
-                    if (x instanceof BlockingDeque) {
-                        BlockingDeque<Integer> q = (BlockingDeque<Integer>) x;
-                        jobs.addAll(blockingDequeJobs(klazz, () -> q, al));
-                    }
-                    if (x instanceof List) {
-                        List<Integer> list = (List<Integer>) x;
-                        jobs.addAll(
-                            collectionJobs(
-                                klazz + " subList",
-                                () -> list.subList(0, x.size()),
-                                al));
-                    }
-                });
+        ArrayList<Job> jobs = Stream.<Collection<Integer>>of(
+                new ArrayList<>(),
+                makeSubList(new ArrayList<>()),
+                new LinkedList<>(),
+                makeSubList(new LinkedList<>()),
+                new Vector<>(),
+                makeSubList(new Vector<>()),
+                new CopyOnWriteArrayList<>(),
+                makeSubList(new CopyOnWriteArrayList<>()),
+                new ArrayDeque<>(),
+                new PriorityQueue<>(),
+                new ArrayBlockingQueue<>(elements.size()),
+                new ConcurrentLinkedQueue<>(),
+                new ConcurrentLinkedDeque<>(),
+                new LinkedBlockingQueue<>(),
+                new LinkedBlockingDeque<>(),
+                new LinkedTransferQueue<>(),
+                new PriorityBlockingQueue<>())
+            .flatMap(x -> jobs(x))
+            .filter(job ->
+                nameFilter == null || nameFilter.matcher(job.name()).find())
+            .collect(toCollection(ArrayList::new));
 
         if (reverse) Collections.reverse(jobs);
         if (shuffle) Collections.shuffle(jobs);
 
-        time(filter(filter, jobs));
+        time(jobs);
+    }
+
+    Stream<Job> jobs(Collection<Integer> x) {
+        return concatStreams(
+            collectionJobs(x),
+
+            (CopyOnWriteArrayList.class.isAssignableFrom(topLevelClass(x)))
+            ? Stream.empty()
+            : iteratorRemoveJobs(x),
+
+            (x instanceof Queue)
+            ? queueJobs((Queue<Integer>)x)
+            : Stream.empty(),
+
+            (x instanceof Deque)
+            ? dequeJobs((Deque<Integer>)x)
+            : Stream.empty(),
+
+            (x instanceof BlockingQueue)
+            ? blockingQueueJobs((BlockingQueue<Integer>)x)
+            : Stream.empty(),
+
+            (x instanceof BlockingDeque)
+            ? blockingDequeJobs((BlockingDeque<Integer>)x)
+            : Stream.empty());
     }
 
     Collection<Integer> universeRecorder(int[] sum) {
@@ -323,75 +361,81 @@
             }};
     }
 
-    List<Job> collectionJobs(
-        String description,
-        Supplier<Collection<Integer>> supplier,
-        ArrayList<Integer> al) {
-        return List.of(
-            new Job(description + " removeIf") {
+    Stream<Job> collectionJobs(Collection<Integer> x) {
+        final String klazz = goodClassName(x.getClass());
+        return Stream.of(
+            new Job(klazz + " removeIf") {
                 public void work() throws Throwable {
-                    Collection<Integer> x = supplier.get();
                     int[] sum = new int[1];
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        x.addAll(al);
+                        x.addAll(elements);
                         x.removeIf(n -> { sum[0] += n; return true; });
                         check.sum(sum[0]);}}},
-            new Job(description + " removeIf rnd-two-pass") {
+            new Job(klazz + " removeIf rnd-two-pass") {
                 public void work() throws Throwable {
                     ThreadLocalRandom rnd = ThreadLocalRandom.current();
-                    Collection<Integer> x = supplier.get();
                     int[] sum = new int[1];
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        x.addAll(al);
+                        x.addAll(elements);
                         x.removeIf(n -> {
                             boolean b = rnd.nextBoolean();
                             if (b) sum[0] += n;
                             return b; });
                         x.removeIf(n -> { sum[0] += n; return true; });
                         check.sum(sum[0]);}}},
-            new Job(description + " removeAll") {
+            new Job(klazz + " removeAll") {
                 public void work() throws Throwable {
-                    Collection<Integer> x = supplier.get();
                     int[] sum = new int[1];
                     Collection<Integer> universe = universeRecorder(sum);
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        x.addAll(al);
+                        x.addAll(elements);
                         x.removeAll(universe);
                         check.sum(sum[0]);}}},
-            new Job(description + " retainAll") {
+            new Job(klazz + " retainAll") {
                 public void work() throws Throwable {
-                    Collection<Integer> x = supplier.get();
                     int[] sum = new int[1];
                     Collection<Integer> empty = emptyRecorder(sum);
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        x.addAll(al);
+                        x.addAll(elements);
                         x.retainAll(empty);
                         check.sum(sum[0]);}}},
-            new Job(description + " Iterator.remove") {
+            new Job(klazz + " clear") {
                 public void work() throws Throwable {
-                    Collection<Integer> x = supplier.get();
                     int[] sum = new int[1];
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        x.addAll(al);
+                        x.addAll(elements);
+                        x.forEach(e -> sum[0] += e);
+                        x.clear();
+                        check.sum(sum[0]);}}});
+    }
+
+    Stream<Job> iteratorRemoveJobs(Collection<Integer> x) {
+        final String klazz = goodClassName(x.getClass());
+        return Stream.of(
+             new Job(klazz + " Iterator.remove") {
+                public void work() throws Throwable {
+                    int[] sum = new int[1];
+                    for (int i = 0; i < iterations; i++) {
+                        sum[0] = 0;
+                        x.addAll(elements);
                         Iterator<Integer> it = x.iterator();
                         while (it.hasNext()) {
                             sum[0] += it.next();
                             it.remove();
                         }
                         check.sum(sum[0]);}}},
-            new Job(description + " Iterator.remove-rnd-two-pass") {
+            new Job(klazz + " Iterator.remove-rnd-two-pass") {
                 public void work() throws Throwable {
                     ThreadLocalRandom rnd = ThreadLocalRandom.current();
-                    Collection<Integer> x = supplier.get();
                     int[] sum = new int[1];
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        x.addAll(al);
+                        x.addAll(elements);
                         for (Iterator<Integer> it = x.iterator();
                              it.hasNext(); ) {
                             Integer e = it.next();
@@ -405,129 +449,103 @@
                             sum[0] += it.next();
                             it.remove();
                         }
-                        check.sum(sum[0]);}}},
-            new Job(description + " clear") {
+                        check.sum(sum[0]);}}});
+    }
+
+    Stream<Job> queueJobs(Queue<Integer> x) {
+        final String klazz = goodClassName(x.getClass());
+        return Stream.of(
+            new Job(klazz + " poll()") {
                 public void work() throws Throwable {
-                    Collection<Integer> x = supplier.get();
                     int[] sum = new int[1];
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        x.addAll(al);
-                        x.forEach(e -> sum[0] += e);
-                        x.clear();
-                        check.sum(sum[0]);}}});
-    }
-
-    List<Job> queueJobs(
-        String description,
-        Supplier<Queue<Integer>> supplier,
-        ArrayList<Integer> al) {
-        return List.of(
-            new Job(description + " poll()") {
-                public void work() throws Throwable {
-                    Queue<Integer> x = supplier.get();
-                    int[] sum = new int[1];
-                    for (int i = 0; i < iterations; i++) {
-                        sum[0] = 0;
-                        x.addAll(al);
+                        x.addAll(elements);
                         for (Integer e; (e = x.poll()) != null; )
                             sum[0] += e;
                         check.sum(sum[0]);}}});
     }
 
-    List<Job> dequeJobs(
-        String description,
-        Supplier<Deque<Integer>> supplier,
-        ArrayList<Integer> al) {
-        return List.of(
-            new Job(description + " descendingIterator().remove") {
+    Stream<Job> dequeJobs(Deque<Integer> x) {
+        final String klazz = goodClassName(x.getClass());
+        return Stream.of(
+            new Job(klazz + " descendingIterator().remove") {
                 public void work() throws Throwable {
-                    Deque<Integer> x = supplier.get();
                     int[] sum = new int[1];
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        x.addAll(al);
+                        x.addAll(elements);
                         Iterator<Integer> it = x.descendingIterator();
                         while (it.hasNext()) {
                             sum[0] += it.next();
                             it.remove();
                         }
                         check.sum(sum[0]);}}},
-            new Job(description + " pollFirst()") {
+            new Job(klazz + " pollFirst()") {
                 public void work() throws Throwable {
-                    Deque<Integer> x = supplier.get();
                     int[] sum = new int[1];
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        x.addAll(al);
+                        x.addAll(elements);
                         for (Integer e; (e = x.pollFirst()) != null; )
                             sum[0] += e;
                         check.sum(sum[0]);}}},
-            new Job(description + " pollLast()") {
+            new Job(klazz + " pollLast()") {
                 public void work() throws Throwable {
-                    Deque<Integer> x = supplier.get();
                     int[] sum = new int[1];
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        x.addAll(al);
+                        x.addAll(elements);
                         for (Integer e; (e = x.pollLast()) != null; )
                             sum[0] += e;
                         check.sum(sum[0]);}}});
     }
 
-    List<Job> blockingQueueJobs(
-        String description,
-        Supplier<BlockingQueue<Integer>> supplier,
-        ArrayList<Integer> al) {
-        return List.of(
-            new Job(description + " drainTo(sink)") {
+    Stream<Job> blockingQueueJobs(BlockingQueue<Integer> x) {
+        final String klazz = goodClassName(x.getClass());
+        return Stream.of(
+            new Job(klazz + " drainTo(sink)") {
                 public void work() throws Throwable {
-                    BlockingQueue<Integer> x = supplier.get();
                     ArrayList<Integer> sink = new ArrayList<>();
                     int[] sum = new int[1];
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
                         sink.clear();
-                        x.addAll(al);
+                        x.addAll(elements);
                         x.drainTo(sink);
                         sink.forEach(e -> sum[0] += e);
                         check.sum(sum[0]);}}},
-            new Job(description + " drainTo(sink, n)") {
+            new Job(klazz + " drainTo(sink, n)") {
                 public void work() throws Throwable {
-                    BlockingQueue<Integer> x = supplier.get();
                     ArrayList<Integer> sink = new ArrayList<>();
                     int[] sum = new int[1];
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
                         sink.clear();
-                        x.addAll(al);
-                        x.drainTo(sink, al.size());
+                        x.addAll(elements);
+                        x.drainTo(sink, elements.size());
                         sink.forEach(e -> sum[0] += e);
                         check.sum(sum[0]);}}});
     }
 
-    List<Job> blockingDequeJobs(
-        String description,
-        Supplier<BlockingDeque<Integer>> supplier,
-        ArrayList<Integer> al) {
-        return List.of(
-            new Job(description + " timed pollFirst()") {
+    Stream<Job> blockingDequeJobs(BlockingDeque<Integer> x) {
+        final String klazz = goodClassName(x.getClass());
+        return Stream.of(
+            new Job(klazz + " timed pollFirst()") {
                 public void work() throws Throwable {
-                    BlockingDeque<Integer> x = supplier.get();
                     int[] sum = new int[1];
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        x.addAll(al);
+                        x.addAll(elements);
                         for (Integer e; (e = x.pollFirst(0L, TimeUnit.DAYS)) != null; )
                             sum[0] += e;
                         check.sum(sum[0]);}}},
-            new Job(description + " timed pollLast()") {
+            new Job(klazz + " timed pollLast()") {
                 public void work() throws Throwable {
-                    BlockingDeque<Integer> x = supplier.get();
                     int[] sum = new int[1];
                     for (int i = 0; i < iterations; i++) {
                         sum[0] = 0;
-                        x.addAll(al);
+                        x.addAll(elements);
                         for (Integer e; (e = x.pollLast(0L, TimeUnit.DAYS)) != null; )
                             sum[0] += e;
                         check.sum(sum[0]);}}});
--- a/test/jdk/java/util/concurrent/tck/Collection8Test.java	Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/Collection8Test.java	Tue Apr 10 11:33:29 2018 -0700
@@ -35,6 +35,7 @@
 import static java.util.concurrent.TimeUnit.HOURS;
 import static java.util.concurrent.TimeUnit.MILLISECONDS;
 
+import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
@@ -46,6 +47,7 @@
 import java.util.List;
 import java.util.NoSuchElementException;
 import java.util.Queue;
+import java.util.Set;
 import java.util.Spliterator;
 import java.util.concurrent.BlockingDeque;
 import java.util.concurrent.BlockingQueue;
@@ -86,8 +88,9 @@
 
     Object bomb() {
         return new Object() {
-            public boolean equals(Object x) { throw new AssertionError(); }
-            public int hashCode() { throw new AssertionError(); }
+            @Override public boolean equals(Object x) { throw new AssertionError(); }
+            @Override public int hashCode() { throw new AssertionError(); }
+            @Override public String toString() { throw new AssertionError(); }
         };
     }
 
@@ -119,6 +122,23 @@
         assertTrue(c.isEmpty());
         assertEquals(0, c.size());
         assertEquals("[]", c.toString());
+        if (c instanceof List<?>) {
+            List x = (List) c;
+            assertEquals(1, x.hashCode());
+            assertEquals(x, Collections.emptyList());
+            assertEquals(Collections.emptyList(), x);
+            assertEquals(-1, x.indexOf(impl.makeElement(86)));
+            assertEquals(-1, x.lastIndexOf(impl.makeElement(99)));
+            assertThrows(
+                IndexOutOfBoundsException.class,
+                () -> x.get(0),
+                () -> x.set(0, impl.makeElement(42)));
+        }
+        else if (c instanceof Set<?>) {
+            assertEquals(0, c.hashCode());
+            assertEquals(c, Collections.emptySet());
+            assertEquals(Collections.emptySet(), c);
+        }
         {
             Object[] a = c.toArray();
             assertEquals(0, a.length);
@@ -279,6 +299,16 @@
                 () -> d.pop(),
                 () -> d.descendingIterator().next());
         }
+        if (c instanceof List) {
+            List x = (List) c;
+            assertThrows(
+                NoSuchElementException.class,
+                () -> x.iterator().next(),
+                () -> x.listIterator().next(),
+                () -> x.listIterator(0).next(),
+                () -> x.listIterator().previous(),
+                () -> x.listIterator(0).previous());
+        }
     }
 
     public void testRemoveIf() {
@@ -904,6 +934,31 @@
         }
     }
 
+    public void testCollectionCopies() throws Exception {
+        ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        Collection c = impl.emptyCollection();
+        for (int n = rnd.nextInt(4); n--> 0; )
+            c.add(impl.makeElement(rnd.nextInt()));
+        assertEquals(c, c);
+        if (c instanceof List)
+            assertCollectionsEquals(c, new ArrayList(c));
+        else if (c instanceof Set)
+            assertCollectionsEquals(c, new HashSet(c));
+        else if (c instanceof Deque)
+            assertCollectionsEquivalent(c, new ArrayDeque(c));
+
+        Collection clone = cloneableClone(c);
+        if (clone != null) {
+            assertSame(c.getClass(), clone.getClass());
+            assertCollectionsEquivalent(c, clone);
+        }
+        try {
+            Collection serialClone = serialClonePossiblyFailing(c);
+            assertSame(c.getClass(), serialClone.getClass());
+            assertCollectionsEquivalent(c, serialClone);
+        } catch (java.io.NotSerializableException acceptable) {}
+    }
+
 //     public void testCollection8DebugFail() {
 //         fail(impl.klazz().getSimpleName());
 //     }
--- a/test/jdk/java/util/concurrent/tck/CopyOnWriteArrayListTest.java	Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/CopyOnWriteArrayListTest.java	Tue Apr 10 11:33:29 2018 -0700
@@ -36,12 +36,13 @@
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.Iterator;
-import java.util.LinkedList;
 import java.util.List;
 import java.util.ListIterator;
 import java.util.NoSuchElementException;
 import java.util.concurrent.CopyOnWriteArrayList;
+import java.util.concurrent.ThreadLocalRandom;
 
 import junit.framework.Test;
 
@@ -61,7 +62,12 @@
         }
         class SubListImplementation extends Implementation {
             public List emptyCollection() {
-                return super.emptyCollection().subList(0, 0);
+                List list = super.emptyCollection();
+                ThreadLocalRandom rnd = ThreadLocalRandom.current();
+                if (rnd.nextBoolean())
+                    list.add(makeElement(rnd.nextInt()));
+                int i = rnd.nextInt(list.size() + 1);
+                return list.subList(i, i);
             }
         }
         return newTestSuite(
@@ -70,67 +76,67 @@
                 CollectionTest.testSuite(new SubListImplementation()));
     }
 
-    static CopyOnWriteArrayList<Integer> populatedArray(int n) {
-        CopyOnWriteArrayList<Integer> a = new CopyOnWriteArrayList<>();
-        assertTrue(a.isEmpty());
+    static CopyOnWriteArrayList<Integer> populatedList(int n) {
+        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
+        assertTrue(list.isEmpty());
         for (int i = 0; i < n; i++)
-            a.add(i);
-        assertFalse(a.isEmpty());
-        assertEquals(n, a.size());
-        return a;
+            list.add(i);
+        assertEquals(n <= 0, list.isEmpty());
+        assertEquals(n, list.size());
+        return list;
     }
 
-    static CopyOnWriteArrayList<Integer> populatedArray(Integer[] elements) {
-        CopyOnWriteArrayList<Integer> a = new CopyOnWriteArrayList<>();
-        assertTrue(a.isEmpty());
+    static CopyOnWriteArrayList<Integer> populatedList(Integer[] elements) {
+        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
+        assertTrue(list.isEmpty());
         for (Integer element : elements)
-            a.add(element);
-        assertFalse(a.isEmpty());
-        assertEquals(elements.length, a.size());
-        return a;
+            list.add(element);
+        assertFalse(list.isEmpty());
+        assertEquals(elements.length, list.size());
+        return list;
     }
 
     /**
      * a new list is empty
      */
     public void testConstructor() {
-        CopyOnWriteArrayList a = new CopyOnWriteArrayList();
-        assertTrue(a.isEmpty());
+        List list = new CopyOnWriteArrayList();
+        assertTrue(list.isEmpty());
     }
 
     /**
      * new list contains all elements of initializing array
      */
     public void testConstructor2() {
-        Integer[] ints = new Integer[SIZE];
+        Integer[] elts = new Integer[SIZE];
         for (int i = 0; i < SIZE - 1; ++i)
-            ints[i] = new Integer(i);
-        CopyOnWriteArrayList a = new CopyOnWriteArrayList(ints);
+            elts[i] = i;
+        List list = new CopyOnWriteArrayList(elts);
         for (int i = 0; i < SIZE; ++i)
-            assertEquals(ints[i], a.get(i));
+            assertEquals(elts[i], list.get(i));
     }
 
     /**
      * new list contains all elements of initializing collection
      */
     public void testConstructor3() {
-        Integer[] ints = new Integer[SIZE];
+        Integer[] elts = new Integer[SIZE];
         for (int i = 0; i < SIZE - 1; ++i)
-            ints[i] = new Integer(i);
-        CopyOnWriteArrayList a = new CopyOnWriteArrayList(Arrays.asList(ints));
+            elts[i] = i;
+        List list = new CopyOnWriteArrayList(Arrays.asList(elts));
         for (int i = 0; i < SIZE; ++i)
-            assertEquals(ints[i], a.get(i));
+            assertEquals(elts[i], list.get(i));
     }
 
     /**
      * addAll adds each element from the given collection, including duplicates
      */
     public void testAddAll() {
-        CopyOnWriteArrayList full = populatedArray(3);
-        assertTrue(full.addAll(Arrays.asList(three, four, five)));
-        assertEquals(6, full.size());
-        assertTrue(full.addAll(Arrays.asList(three, four, five)));
-        assertEquals(9, full.size());
+        List list = populatedList(3);
+        assertTrue(list.addAll(Arrays.asList(three, four, five)));
+        assertEquals(6, list.size());
+        assertTrue(list.addAll(Arrays.asList(three, four, five)));
+        assertEquals(9, list.size());
     }
 
     /**
@@ -138,46 +144,46 @@
      * already exist in the List
      */
     public void testAddAllAbsent() {
-        CopyOnWriteArrayList full = populatedArray(3);
+        CopyOnWriteArrayList list = populatedList(3);
         // "one" is duplicate and will not be added
-        assertEquals(2, full.addAllAbsent(Arrays.asList(three, four, one)));
-        assertEquals(5, full.size());
-        assertEquals(0, full.addAllAbsent(Arrays.asList(three, four, one)));
-        assertEquals(5, full.size());
+        assertEquals(2, list.addAllAbsent(Arrays.asList(three, four, one)));
+        assertEquals(5, list.size());
+        assertEquals(0, list.addAllAbsent(Arrays.asList(three, four, one)));
+        assertEquals(5, list.size());
     }
 
     /**
      * addIfAbsent will not add the element if it already exists in the list
      */
     public void testAddIfAbsent() {
-        CopyOnWriteArrayList full = populatedArray(SIZE);
-        full.addIfAbsent(one);
-        assertEquals(SIZE, full.size());
+        CopyOnWriteArrayList list = populatedList(SIZE);
+        list.addIfAbsent(one);
+        assertEquals(SIZE, list.size());
     }
 
     /**
      * addIfAbsent adds the element when it does not exist in the list
      */
     public void testAddIfAbsent2() {
-        CopyOnWriteArrayList full = populatedArray(SIZE);
-        full.addIfAbsent(three);
-        assertTrue(full.contains(three));
+        CopyOnWriteArrayList list = populatedList(SIZE);
+        list.addIfAbsent(three);
+        assertTrue(list.contains(three));
     }
 
     /**
      * clear removes all elements from the list
      */
     public void testClear() {
-        CopyOnWriteArrayList full = populatedArray(SIZE);
-        full.clear();
-        assertEquals(0, full.size());
+        List list = populatedList(SIZE);
+        list.clear();
+        assertEquals(0, list.size());
     }
 
     /**
      * Cloned list is equal
      */
     public void testClone() {
-        CopyOnWriteArrayList l1 = populatedArray(SIZE);
+        CopyOnWriteArrayList l1 = populatedList(SIZE);
         CopyOnWriteArrayList l2 = (CopyOnWriteArrayList)(l1.clone());
         assertEquals(l1, l2);
         l1.clear();
@@ -188,33 +194,33 @@
      * contains is true for added elements
      */
     public void testContains() {
-        CopyOnWriteArrayList full = populatedArray(3);
-        assertTrue(full.contains(one));
-        assertFalse(full.contains(five));
+        List list = populatedList(3);
+        assertTrue(list.contains(one));
+        assertFalse(list.contains(five));
     }
 
     /**
      * adding at an index places it in the indicated index
      */
     public void testAddIndex() {
-        CopyOnWriteArrayList full = populatedArray(3);
-        full.add(0, m1);
-        assertEquals(4, full.size());
-        assertEquals(m1, full.get(0));
-        assertEquals(zero, full.get(1));
+        List list = populatedList(3);
+        list.add(0, m1);
+        assertEquals(4, list.size());
+        assertEquals(m1, list.get(0));
+        assertEquals(zero, list.get(1));
 
-        full.add(2, m2);
-        assertEquals(5, full.size());
-        assertEquals(m2, full.get(2));
-        assertEquals(two, full.get(4));
+        list.add(2, m2);
+        assertEquals(5, list.size());
+        assertEquals(m2, list.get(2));
+        assertEquals(two, list.get(4));
     }
 
     /**
      * lists with same elements are equal and have same hashCode
      */
     public void testEquals() {
-        CopyOnWriteArrayList a = populatedArray(3);
-        CopyOnWriteArrayList b = populatedArray(3);
+        List a = populatedList(3);
+        List b = populatedList(3);
         assertTrue(a.equals(b));
         assertTrue(b.equals(a));
         assertTrue(a.containsAll(b));
@@ -239,15 +245,15 @@
      * containsAll returns true for collections with subset of elements
      */
     public void testContainsAll() {
-        CopyOnWriteArrayList full = populatedArray(3);
-        assertTrue(full.containsAll(Arrays.asList()));
-        assertTrue(full.containsAll(Arrays.asList(one)));
-        assertTrue(full.containsAll(Arrays.asList(one, two)));
-        assertFalse(full.containsAll(Arrays.asList(one, two, six)));
-        assertFalse(full.containsAll(Arrays.asList(six)));
+        List list = populatedList(3);
+        assertTrue(list.containsAll(Arrays.asList()));
+        assertTrue(list.containsAll(Arrays.asList(one)));
+        assertTrue(list.containsAll(Arrays.asList(one, two)));
+        assertFalse(list.containsAll(Arrays.asList(one, two, six)));
+        assertFalse(list.containsAll(Arrays.asList(six)));
 
         try {
-            full.containsAll(null);
+            list.containsAll(null);
             shouldThrow();
         } catch (NullPointerException success) {}
     }
@@ -256,37 +262,81 @@
      * get returns the value at the given index
      */
     public void testGet() {
-        CopyOnWriteArrayList full = populatedArray(3);
-        assertEquals(0, full.get(0));
+        List list = populatedList(3);
+        assertEquals(0, list.get(0));
     }
 
     /**
-     * indexOf gives the index for the given object
+     * indexOf(Object) returns the index of the first occurrence of the
+     * specified element in this list, or -1 if this list does not
+     * contain the element
      */
     public void testIndexOf() {
-        CopyOnWriteArrayList full = populatedArray(3);
-        assertEquals(1, full.indexOf(one));
-        assertEquals(-1, full.indexOf("puppies"));
+        List list = populatedList(3);
+        assertEquals(-1, list.indexOf(-42));
+        int size = list.size();
+        for (int i = 0; i < size; i++) {
+            assertEquals(i, list.indexOf(i));
+            assertEquals(i, list.subList(0, size).indexOf(i));
+            assertEquals(i, list.subList(0, i + 1).indexOf(i));
+            assertEquals(-1, list.subList(0, i).indexOf(i));
+            assertEquals(0, list.subList(i, size).indexOf(i));
+            assertEquals(-1, list.subList(i + 1, size).indexOf(i));
+        }
+
+        list.add(1);
+        assertEquals(1, list.indexOf(1));
+        assertEquals(1, list.subList(0, size + 1).indexOf(1));
+        assertEquals(0, list.subList(1, size + 1).indexOf(1));
+        assertEquals(size - 2, list.subList(2, size + 1).indexOf(1));
+        assertEquals(0, list.subList(size, size + 1).indexOf(1));
+        assertEquals(-1, list.subList(size + 1, size + 1).indexOf(1));
     }
 
     /**
-     * indexOf gives the index based on the given index
-     * at which to start searching
+     * indexOf(E, int) returns the index of the first occurrence of the
+     * specified element in this list, searching forwards from index,
+     * or returns -1 if the element is not found
      */
     public void testIndexOf2() {
-        CopyOnWriteArrayList full = populatedArray(3);
-        assertEquals(1, full.indexOf(one, 0));
-        assertEquals(-1, full.indexOf(one, 2));
+        CopyOnWriteArrayList list = populatedList(3);
+        int size = list.size();
+        assertEquals(-1, list.indexOf(-42, 0));
+
+        // we might expect IOOBE, but spec says otherwise
+        assertEquals(-1, list.indexOf(0, size));
+        assertEquals(-1, list.indexOf(0, Integer.MAX_VALUE));
+
+        assertThrows(
+            IndexOutOfBoundsException.class,
+            () -> list.indexOf(0, -1),
+            () -> list.indexOf(0, Integer.MIN_VALUE));
+
+        for (int i = 0; i < size; i++) {
+            assertEquals(i, list.indexOf(i, 0));
+            assertEquals(i, list.indexOf(i, i));
+            assertEquals(-1, list.indexOf(i, i + 1));
+        }
+
+        list.add(1);
+        assertEquals(1, list.indexOf(1, 0));
+        assertEquals(1, list.indexOf(1, 1));
+        assertEquals(size, list.indexOf(1, 2));
+        assertEquals(size, list.indexOf(1, size));
     }
 
     /**
      * isEmpty returns true when empty, else false
      */
     public void testIsEmpty() {
-        CopyOnWriteArrayList empty = new CopyOnWriteArrayList();
-        CopyOnWriteArrayList full = populatedArray(SIZE);
+        List empty = new CopyOnWriteArrayList();
         assertTrue(empty.isEmpty());
+        assertTrue(empty.subList(0, 0).isEmpty());
+
+        List full = populatedList(SIZE);
         assertFalse(full.isEmpty());
+        assertTrue(full.subList(0, 0).isEmpty());
+        assertTrue(full.subList(SIZE, SIZE).isEmpty());
     }
 
     /**
@@ -305,7 +355,7 @@
         for (int i = 0; i < SIZE; i++)
             elements[i] = i;
         shuffle(elements);
-        Collection<Integer> full = populatedArray(elements);
+        Collection<Integer> full = populatedList(elements);
 
         Iterator it = full.iterator();
         for (int j = 0; j < SIZE; j++) {
@@ -327,8 +377,8 @@
      * iterator.remove throws UnsupportedOperationException
      */
     public void testIteratorRemove() {
-        CopyOnWriteArrayList full = populatedArray(SIZE);
-        Iterator it = full.iterator();
+        CopyOnWriteArrayList list = populatedList(SIZE);
+        Iterator it = list.iterator();
         it.next();
         try {
             it.remove();
@@ -341,42 +391,78 @@
      */
     public void testToString() {
         assertEquals("[]", new CopyOnWriteArrayList().toString());
-        CopyOnWriteArrayList full = populatedArray(3);
-        String s = full.toString();
+        List list = populatedList(3);
+        String s = list.toString();
         for (int i = 0; i < 3; ++i)
             assertTrue(s.contains(String.valueOf(i)));
-        assertEquals(new ArrayList(full).toString(),
-                     full.toString());
+        assertEquals(new ArrayList(list).toString(),
+                     list.toString());
     }
 
     /**
-     * lastIndexOf returns the index for the given object
+     * lastIndexOf(Object) returns the index of the last occurrence of
+     * the specified element in this list, or -1 if this list does not
+     * contain the element
      */
     public void testLastIndexOf1() {
-        CopyOnWriteArrayList full = populatedArray(3);
-        full.add(one);
-        full.add(three);
-        assertEquals(3, full.lastIndexOf(one));
-        assertEquals(-1, full.lastIndexOf(six));
+        List list = populatedList(3);
+        assertEquals(-1, list.lastIndexOf(-42));
+        int size = list.size();
+        for (int i = 0; i < size; i++) {
+            assertEquals(i, list.lastIndexOf(i));
+            assertEquals(i, list.subList(0, size).lastIndexOf(i));
+            assertEquals(i, list.subList(0, i + 1).lastIndexOf(i));
+            assertEquals(-1, list.subList(0, i).lastIndexOf(i));
+            assertEquals(0, list.subList(i, size).lastIndexOf(i));
+            assertEquals(-1, list.subList(i + 1, size).lastIndexOf(i));
+        }
+
+        list.add(1);
+        assertEquals(size, list.lastIndexOf(1));
+        assertEquals(size, list.subList(0, size + 1).lastIndexOf(1));
+        assertEquals(1, list.subList(0, size).lastIndexOf(1));
+        assertEquals(0, list.subList(1, 2).lastIndexOf(1));
+        assertEquals(-1, list.subList(0, 1).indexOf(1));
     }
 
     /**
-     * lastIndexOf returns the index from the given starting point
+     * lastIndexOf(E, int) returns the index of the last occurrence of the
+     * specified element in this list, searching backwards from index, or
+     * returns -1 if the element is not found
      */
     public void testLastIndexOf2() {
-        CopyOnWriteArrayList full = populatedArray(3);
-        full.add(one);
-        full.add(three);
-        assertEquals(3, full.lastIndexOf(one, 4));
-        assertEquals(-1, full.lastIndexOf(three, 3));
+        CopyOnWriteArrayList list = populatedList(3);
+
+        // we might expect IOOBE, but spec says otherwise
+        assertEquals(-1, list.lastIndexOf(0, -1));
+
+        int size = list.size();
+        assertThrows(
+            IndexOutOfBoundsException.class,
+            () -> list.lastIndexOf(0, size),
+            () -> list.lastIndexOf(0, Integer.MAX_VALUE));
+
+        for (int i = 0; i < size; i++) {
+            assertEquals(i, list.lastIndexOf(i, i));
+            assertEquals(list.indexOf(i), list.lastIndexOf(i, i));
+            if (i > 0)
+                assertEquals(-1, list.lastIndexOf(i, i - 1));
+        }
+        list.add(one);
+        list.add(three);
+        assertEquals(1, list.lastIndexOf(one, 1));
+        assertEquals(1, list.lastIndexOf(one, 2));
+        assertEquals(3, list.lastIndexOf(one, 3));
+        assertEquals(3, list.lastIndexOf(one, 4));
+        assertEquals(-1, list.lastIndexOf(three, 3));
     }
 
     /**
      * listIterator traverses all elements
      */
     public void testListIterator1() {
-        CopyOnWriteArrayList full = populatedArray(SIZE);
-        ListIterator i = full.listIterator();
+        List list = populatedList(SIZE);
+        ListIterator i = list.listIterator();
         int j;
         for (j = 0; i.hasNext(); j++)
             assertEquals(j, i.next());
@@ -387,8 +473,8 @@
      * listIterator only returns those elements after the given index
      */
     public void testListIterator2() {
-        CopyOnWriteArrayList full = populatedArray(3);
-        ListIterator i = full.listIterator(1);
+        List list = populatedList(3);
+        ListIterator i = list.listIterator(1);
         int j;
         for (j = 0; i.hasNext(); j++)
             assertEquals(j + 1, i.next());
@@ -401,10 +487,10 @@
     public void testRemove_int() {
         int SIZE = 3;
         for (int i = 0; i < SIZE; i++) {
-            CopyOnWriteArrayList full = populatedArray(SIZE);
-            assertEquals(i, full.remove(i));
-            assertEquals(SIZE - 1, full.size());
-            assertFalse(full.contains(new Integer(i)));
+            List list = populatedList(SIZE);
+            assertEquals(i, list.remove(i));
+            assertEquals(SIZE - 1, list.size());
+            assertFalse(list.contains(new Integer(i)));
         }
     }
 
@@ -414,11 +500,11 @@
     public void testRemove_Object() {
         int SIZE = 3;
         for (int i = 0; i < SIZE; i++) {
-            CopyOnWriteArrayList full = populatedArray(SIZE);
-            assertFalse(full.remove(new Integer(-42)));
-            assertTrue(full.remove(new Integer(i)));
-            assertEquals(SIZE - 1, full.size());
-            assertFalse(full.contains(new Integer(i)));
+            List list = populatedList(SIZE);
+            assertFalse(list.remove(new Integer(-42)));
+            assertTrue(list.remove(new Integer(i)));
+            assertEquals(SIZE - 1, list.size());
+            assertFalse(list.contains(new Integer(i)));
         }
         CopyOnWriteArrayList x = new CopyOnWriteArrayList(Arrays.asList(4, 5, 6));
         assertTrue(x.remove(new Integer(6)));
@@ -434,30 +520,34 @@
      * removeAll removes all elements from the given collection
      */
     public void testRemoveAll() {
-        CopyOnWriteArrayList full = populatedArray(3);
-        assertTrue(full.removeAll(Arrays.asList(one, two)));
-        assertEquals(1, full.size());
-        assertFalse(full.removeAll(Arrays.asList(one, two)));
-        assertEquals(1, full.size());
+        List list = populatedList(3);
+        assertTrue(list.removeAll(Arrays.asList(one, two)));
+        assertEquals(1, list.size());
+        assertFalse(list.removeAll(Arrays.asList(one, two)));
+        assertEquals(1, list.size());
     }
 
     /**
      * set changes the element at the given index
      */
     public void testSet() {
-        CopyOnWriteArrayList full = populatedArray(3);
-        assertEquals(2, full.set(2, four));
-        assertEquals(4, full.get(2));
+        List list = populatedList(3);
+        assertEquals(2, list.set(2, four));
+        assertEquals(4, list.get(2));
     }
 
     /**
      * size returns the number of elements
      */
     public void testSize() {
-        CopyOnWriteArrayList empty = new CopyOnWriteArrayList();
-        CopyOnWriteArrayList full = populatedArray(SIZE);
+        List empty = new CopyOnWriteArrayList();
+        assertEquals(0, empty.size());
+        assertEquals(0, empty.subList(0, 0).size());
+
+        List full = populatedList(SIZE);
         assertEquals(SIZE, full.size());
-        assertEquals(0, empty.size());
+        assertEquals(0, full.subList(0, 0).size());
+        assertEquals(0, full.subList(SIZE, SIZE).size());
     }
 
     /**
@@ -473,7 +563,7 @@
         for (int i = 0; i < SIZE; i++)
             elements[i] = i;
         shuffle(elements);
-        Collection<Integer> full = populatedArray(elements);
+        Collection<Integer> full = populatedList(elements);
 
         assertTrue(Arrays.equals(elements, full.toArray()));
         assertSame(Object[].class, full.toArray().getClass());
@@ -501,7 +591,7 @@
         for (int i = 0; i < SIZE; i++)
             elements[i] = i;
         shuffle(elements);
-        Collection<Integer> full = populatedArray(elements);
+        Collection<Integer> full = populatedList(elements);
 
         Arrays.fill(a, 42);
         assertTrue(Arrays.equals(elements, full.toArray(a)));
@@ -527,7 +617,7 @@
      * sublists contains elements at indexes offset from their base
      */
     public void testSubList() {
-        CopyOnWriteArrayList a = populatedArray(10);
+        List a = populatedList(10);
         assertTrue(a.subList(1,1).isEmpty());
         for (int j = 0; j < 9; ++j) {
             for (int i = j ; i < 10; ++i) {
@@ -544,6 +634,11 @@
         assertEquals(a.get(4), m1);
         s.clear();
         assertEquals(7, a.size());
+
+        assertThrows(
+            IndexOutOfBoundsException.class,
+            () -> s.get(0),
+            () -> s.set(0, 42));
     }
 
     // Exception tests
@@ -553,231 +648,72 @@
      * can not store the objects inside the list
      */
     public void testToArray_ArrayStoreException() {
-        CopyOnWriteArrayList c = new CopyOnWriteArrayList();
-        c.add("zfasdfsdf");
-        c.add("asdadasd");
-        try {
-            c.toArray(new Long[5]);
-            shouldThrow();
-        } catch (ArrayStoreException success) {}
+        List list = new CopyOnWriteArrayList();
+        // Integers are not auto-converted to Longs
+        list.add(86);
+        list.add(99);
+        assertThrows(
+            ArrayStoreException.class,
+            () -> list.toArray(new Long[0]),
+            () -> list.toArray(new Long[5]));
+    }
+
+    void testIndexOutOfBoundsException(List list) {
+        int size = list.size();
+        assertThrows(
+            IndexOutOfBoundsException.class,
+            () -> list.get(-1),
+            () -> list.get(size),
+            () -> list.set(-1, "qwerty"),
+            () -> list.set(size, "qwerty"),
+            () -> list.add(-1, "qwerty"),
+            () -> list.add(size + 1, "qwerty"),
+            () -> list.remove(-1),
+            () -> list.remove(size),
+            () -> list.addAll(-1, Collections.emptyList()),
+            () -> list.addAll(size + 1, Collections.emptyList()),
+            () -> list.listIterator(-1),
+            () -> list.listIterator(size + 1),
+            () -> list.subList(-1, size),
+            () -> list.subList(0, size + 1));
+
+        // Conversely, operations that must not throw
+        list.addAll(0, Collections.emptyList());
+        list.addAll(size, Collections.emptyList());
+        list.add(0, "qwerty");
+        list.add(list.size(), "qwerty");
+        list.get(0);
+        list.get(list.size() - 1);
+        list.set(0, "azerty");
+        list.set(list.size() - 1, "azerty");
+        list.listIterator(0);
+        list.listIterator(list.size());
+        list.subList(0, list.size());
+        list.remove(list.size() - 1);
     }
 
     /**
-     * get throws an IndexOutOfBoundsException on a negative index
+     * IndexOutOfBoundsException is thrown when specified
      */
-    public void testGet1_IndexOutOfBoundsException() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.get(-1);
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
+    public void testIndexOutOfBoundsException() {
+        ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        List x = populatedList(rnd.nextInt(5));
+        testIndexOutOfBoundsException(x);
 
-    /**
-     * get throws an IndexOutOfBoundsException on a too high index
-     */
-    public void testGet2_IndexOutOfBoundsException() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.get(list.size());
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
-
-    /**
-     * set throws an IndexOutOfBoundsException on a negative index
-     */
-    public void testSet1_IndexOutOfBoundsException() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.set(-1, "qwerty");
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
-
-    /**
-     * set throws an IndexOutOfBoundsException on a too high index
-     */
-    public void testSet2() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.set(list.size(), "qwerty");
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
-
-    /**
-     * add throws an IndexOutOfBoundsException on a negative index
-     */
-    public void testAdd1_IndexOutOfBoundsException() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.add(-1, "qwerty");
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
-
-    /**
-     * add throws an IndexOutOfBoundsException on a too high index
-     */
-    public void testAdd2_IndexOutOfBoundsException() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.add(list.size() + 1, "qwerty");
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
-
-    /**
-     * remove throws an IndexOutOfBoundsException on a negative index
-     */
-    public void testRemove1_IndexOutOfBounds() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.remove(-1);
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
-
-    /**
-     * remove throws an IndexOutOfBoundsException on a too high index
-     */
-    public void testRemove2_IndexOutOfBounds() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.remove(list.size());
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
-
-    /**
-     * addAll throws an IndexOutOfBoundsException on a negative index
-     */
-    public void testAddAll1_IndexOutOfBoundsException() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.addAll(-1, new LinkedList());
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
-
-    /**
-     * addAll throws an IndexOutOfBoundsException on a too high index
-     */
-    public void testAddAll2_IndexOutOfBoundsException() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.addAll(list.size() + 1, new LinkedList());
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
-
-    /**
-     * listIterator throws an IndexOutOfBoundsException on a negative index
-     */
-    public void testListIterator1_IndexOutOfBoundsException() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.listIterator(-1);
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
-
-    /**
-     * listIterator throws an IndexOutOfBoundsException on a too high index
-     */
-    public void testListIterator2_IndexOutOfBoundsException() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.listIterator(list.size() + 1);
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
-
-    /**
-     * subList throws an IndexOutOfBoundsException on a negative index
-     */
-    public void testSubList1_IndexOutOfBoundsException() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.subList(-1, list.size());
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
-
-    /**
-     * subList throws an IndexOutOfBoundsException on a too high index
-     */
-    public void testSubList2_IndexOutOfBoundsException() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.subList(0, list.size() + 1);
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
-    }
-
-    /**
-     * subList throws IndexOutOfBoundsException when the second index
-     * is lower then the first
-     */
-    public void testSubList3_IndexOutOfBoundsException() {
-        CopyOnWriteArrayList c = populatedArray(5);
-        List[] lists = { c, c.subList(1, c.size() - 1) };
-        for (List list : lists) {
-            try {
-                list.subList(list.size() - 1, 1);
-                shouldThrow();
-            } catch (IndexOutOfBoundsException success) {}
-        }
+        int start = rnd.nextInt(x.size() + 1);
+        int end = rnd.nextInt(start, x.size() + 1);
+        assertThrows(
+            IndexOutOfBoundsException.class,
+            () -> x.subList(start, start - 1));
+        List subList = x.subList(start, end);
+        testIndexOutOfBoundsException(x);
     }
 
     /**
      * a deserialized/reserialized list equals original
      */
     public void testSerialization() throws Exception {
-        List x = populatedArray(SIZE);
+        List x = populatedList(SIZE);
         List y = serialClone(x);
 
         assertNotSame(x, y);
--- a/test/jdk/java/util/concurrent/tck/CopyOnWriteArraySetTest.java	Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/CopyOnWriteArraySetTest.java	Tue Apr 10 11:33:29 2018 -0700
@@ -49,7 +49,16 @@
         main(suite(), args);
     }
     public static Test suite() {
-        return new TestSuite(CopyOnWriteArraySetTest.class);
+        class Implementation implements CollectionImplementation {
+            public Class<?> klazz() { return CopyOnWriteArraySet.class; }
+            public Set emptyCollection() { return new CopyOnWriteArraySet(); }
+            public Object makeElement(int i) { return i; }
+            public boolean isConcurrent() { return true; }
+            public boolean permitsNulls() { return true; }
+        }
+        return newTestSuite(
+                CopyOnWriteArraySetTest.class,
+                CollectionTest.testSuite(new Implementation()));
     }
 
     static CopyOnWriteArraySet<Integer> populatedSet(int n) {
--- a/test/jdk/java/util/concurrent/tck/JSR166TestCase.java	Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/JSR166TestCase.java	Tue Apr 10 11:33:29 2018 -0700
@@ -93,11 +93,14 @@
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Date;
+import java.util.Deque;
 import java.util.Enumeration;
+import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.NoSuchElementException;
 import java.util.PropertyPermission;
+import java.util.Set;
 import java.util.concurrent.BlockingQueue;
 import java.util.concurrent.Callable;
 import java.util.concurrent.CountDownLatch;
@@ -475,6 +478,7 @@
     public static boolean atLeastJava8()  { return JAVA_CLASS_VERSION >= 52.0; }
     public static boolean atLeastJava9()  { return JAVA_CLASS_VERSION >= 53.0; }
     public static boolean atLeastJava10() { return JAVA_CLASS_VERSION >= 54.0; }
+    public static boolean atLeastJava11() { return JAVA_CLASS_VERSION >= 55.0; }
 
     /**
      * Collects all JSR166 unit tests as one suite.
@@ -1473,26 +1477,6 @@
         }
     }
 
-    public abstract class RunnableShouldThrow implements Runnable {
-        protected abstract void realRun() throws Throwable;
-
-        final Class<?> exceptionClass;
-
-        <T extends Throwable> RunnableShouldThrow(Class<T> exceptionClass) {
-            this.exceptionClass = exceptionClass;
-        }
-
-        public final void run() {
-            try {
-                realRun();
-                threadShouldThrow(exceptionClass.getSimpleName());
-            } catch (Throwable t) {
-                if (! exceptionClass.isInstance(t))
-                    threadUnexpectedException(t);
-            }
-        }
-    }
-
     public abstract class ThreadShouldThrow extends Thread {
         protected abstract void realRun() throws Throwable;
 
@@ -2098,4 +2082,42 @@
         assertEquals(savedCompletedTaskCount, p.getCompletedTaskCount());
         assertEquals(savedQueueSize, p.getQueue().size());
     }
+
+    void assertCollectionsEquals(Collection<?> x, Collection<?> y) {
+        assertEquals(x, y);
+        assertEquals(y, x);
+        assertEquals(x.isEmpty(), y.isEmpty());
+        assertEquals(x.size(), y.size());
+        if (x instanceof List) {
+            assertEquals(x.toString(), y.toString());
+        }
+        if (x instanceof List || x instanceof Set) {
+            assertEquals(x.hashCode(), y.hashCode());
+        }
+        if (x instanceof List || x instanceof Deque) {
+            assertTrue(Arrays.equals(x.toArray(), y.toArray()));
+            assertTrue(Arrays.equals(x.toArray(new Object[0]),
+                                     y.toArray(new Object[0])));
+        }
+    }
+
+    /**
+     * A weaker form of assertCollectionsEquals which does not insist
+     * that the two collections satisfy Object#equals(Object), since
+     * they may use identity semantics as Deques do.
+     */
+    void assertCollectionsEquivalent(Collection<?> x, Collection<?> y) {
+        if (x instanceof List || x instanceof Set)
+            assertCollectionsEquals(x, y);
+        else {
+            assertEquals(x.isEmpty(), y.isEmpty());
+            assertEquals(x.size(), y.size());
+            assertEquals(new HashSet(x), new HashSet(y));
+            if (x instanceof Deque) {
+                assertTrue(Arrays.equals(x.toArray(), y.toArray()));
+                assertTrue(Arrays.equals(x.toArray(new Object[0]),
+                                         y.toArray(new Object[0])));
+            }
+        }
+    }
 }
--- a/test/jdk/java/util/concurrent/tck/LinkedListTest.java	Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/LinkedListTest.java	Tue Apr 10 11:33:29 2018 -0700
@@ -37,7 +37,9 @@
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.LinkedList;
+import java.util.List;
 import java.util.NoSuchElementException;
+import java.util.concurrent.ThreadLocalRandom;
 
 import junit.framework.Test;
 
@@ -49,14 +51,19 @@
     public static Test suite() {
         class Implementation implements CollectionImplementation {
             public Class<?> klazz() { return LinkedList.class; }
-            public Collection emptyCollection() { return new LinkedList(); }
+            public List emptyCollection() { return new LinkedList(); }
             public Object makeElement(int i) { return i; }
             public boolean isConcurrent() { return false; }
             public boolean permitsNulls() { return true; }
         }
         class SubListImplementation extends Implementation {
-            public Collection emptyCollection() {
-                return new LinkedList().subList(0, 0);
+            public List emptyCollection() {
+                List list = super.emptyCollection();
+                ThreadLocalRandom rnd = ThreadLocalRandom.current();
+                if (rnd.nextBoolean())
+                    list.add(makeElement(rnd.nextInt()));
+                int i = rnd.nextInt(list.size() + 1);
+                return list.subList(i, i);
             }
         }
         return newTestSuite(
--- a/test/jdk/java/util/concurrent/tck/VectorTest.java	Tue Apr 10 11:29:37 2018 -0700
+++ b/test/jdk/java/util/concurrent/tck/VectorTest.java	Tue Apr 10 11:33:29 2018 -0700
@@ -32,8 +32,13 @@
  * http://creativecommons.org/publicdomain/zero/1.0/
  */
 
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
 import java.util.Vector;
-import java.util.List;
+import java.util.concurrent.ThreadLocalRandom;
 
 import junit.framework.Test;
 
@@ -52,7 +57,12 @@
         }
         class SubListImplementation extends Implementation {
             public List emptyCollection() {
-                return super.emptyCollection().subList(0, 0);
+                List list = super.emptyCollection();
+                ThreadLocalRandom rnd = ThreadLocalRandom.current();
+                if (rnd.nextBoolean())
+                    list.add(makeElement(rnd.nextInt()));
+                int i = rnd.nextInt(list.size() + 1);
+                return list.subList(i, i);
             }
         }
         return newTestSuite(
@@ -61,6 +71,393 @@
                 CollectionTest.testSuite(new SubListImplementation()));
     }
 
+    static Vector<Integer> populatedList(int n) {
+        Vector<Integer> list = new Vector<>();
+        assertTrue(list.isEmpty());
+        for (int i = 0; i < n; i++)
+            list.add(i);
+        assertEquals(n <= 0, list.isEmpty());
+        assertEquals(n, list.size());
+        return list;
+    }
+
+    /**
+     * addAll adds each element from the given collection, including duplicates
+     */
+    public void testAddAll() {
+        List list = populatedList(3);
+        assertTrue(list.addAll(Arrays.asList(three, four, five)));
+        assertEquals(6, list.size());
+        assertTrue(list.addAll(Arrays.asList(three, four, five)));
+        assertEquals(9, list.size());
+    }
+
+    /**
+     * clear removes all elements from the list
+     */
+    public void testClear() {
+        List list = populatedList(SIZE);
+        list.clear();
+        assertEquals(0, list.size());
+    }
+
+    /**
+     * Cloned list is equal
+     */
+    public void testClone() {
+        Vector l1 = populatedList(SIZE);
+        Vector l2 = (Vector)(l1.clone());
+        assertEquals(l1, l2);
+        l1.clear();
+        assertFalse(l1.equals(l2));
+    }
+
+    /**
+     * contains is true for added elements
+     */
+    public void testContains() {
+        List list = populatedList(3);
+        assertTrue(list.contains(one));
+        assertFalse(list.contains(five));
+    }
+
+    /**
+     * adding at an index places it in the indicated index
+     */
+    public void testAddIndex() {
+        List list = populatedList(3);
+        list.add(0, m1);
+        assertEquals(4, list.size());
+        assertEquals(m1, list.get(0));
+        assertEquals(zero, list.get(1));
+
+        list.add(2, m2);
+        assertEquals(5, list.size());
+        assertEquals(m2, list.get(2));
+        assertEquals(two, list.get(4));
+    }
+
+    /**
+     * lists with same elements are equal and have same hashCode
+     */
+    public void testEquals() {
+        List a = populatedList(3);
+        List b = populatedList(3);
+        assertTrue(a.equals(b));
+        assertTrue(b.equals(a));
+        assertTrue(a.containsAll(b));
+        assertTrue(b.containsAll(a));
+        assertEquals(a.hashCode(), b.hashCode());
+        a.add(m1);
+        assertFalse(a.equals(b));
+        assertFalse(b.equals(a));
+        assertTrue(a.containsAll(b));
+        assertFalse(b.containsAll(a));
+        b.add(m1);
+        assertTrue(a.equals(b));
+        assertTrue(b.equals(a));
+        assertTrue(a.containsAll(b));
+        assertTrue(b.containsAll(a));
+        assertEquals(a.hashCode(), b.hashCode());
+
+        assertFalse(a.equals(null));
+    }
+
+    /**
+     * containsAll returns true for collections with subset of elements
+     */
+    public void testContainsAll() {
+        List list = populatedList(3);
+        assertTrue(list.containsAll(Arrays.asList()));
+        assertTrue(list.containsAll(Arrays.asList(one)));
+        assertTrue(list.containsAll(Arrays.asList(one, two)));
+        assertFalse(list.containsAll(Arrays.asList(one, two, six)));
+        assertFalse(list.containsAll(Arrays.asList(six)));
+
+        try {
+            list.containsAll(null);
+            shouldThrow();
+        } catch (NullPointerException success) {}
+    }
+
+    /**
+     * get returns the value at the given index
+     */
+    public void testGet() {
+        List list = populatedList(3);
+        assertEquals(0, list.get(0));
+    }
+
+    /**
+     * indexOf(Object) returns the index of the first occurrence of the
+     * specified element in this list, or -1 if this list does not
+     * contain the element
+     */
+    public void testIndexOf() {
+        List list = populatedList(3);
+        assertEquals(-1, list.indexOf(-42));
+        int size = list.size();
+        for (int i = 0; i < size; i++) {
+            assertEquals(i, list.indexOf(i));
+            assertEquals(i, list.subList(0, size).indexOf(i));
+            assertEquals(i, list.subList(0, i + 1).indexOf(i));
+            assertEquals(-1, list.subList(0, i).indexOf(i));
+            assertEquals(0, list.subList(i, size).indexOf(i));
+            assertEquals(-1, list.subList(i + 1, size).indexOf(i));
+        }
+
+        list.add(1);
+        assertEquals(1, list.indexOf(1));
+        assertEquals(1, list.subList(0, size + 1).indexOf(1));
+        assertEquals(0, list.subList(1, size + 1).indexOf(1));
+        assertEquals(size - 2, list.subList(2, size + 1).indexOf(1));
+        assertEquals(0, list.subList(size, size + 1).indexOf(1));
+        assertEquals(-1, list.subList(size + 1, size + 1).indexOf(1));
+    }
+
+    /**
+     * indexOf(E, int) returns the index of the first occurrence of the
+     * specified element in this list, searching forwards from index,
+     * or returns -1 if the element is not found
+     */
+    public void testIndexOf2() {
+        Vector list = populatedList(3);
+        int size = list.size();
+        assertEquals(-1, list.indexOf(-42, 0));
+
+        // we might expect IOOBE, but spec says otherwise
+        assertEquals(-1, list.indexOf(0, size));
+        assertEquals(-1, list.indexOf(0, Integer.MAX_VALUE));
+
+        assertThrows(
+            IndexOutOfBoundsException.class,
+            () -> list.indexOf(0, -1),
+            () -> list.indexOf(0, Integer.MIN_VALUE));
+
+        for (int i = 0; i < size; i++) {
+            assertEquals(i, list.indexOf(i, 0));
+            assertEquals(i, list.indexOf(i, i));
+            assertEquals(-1, list.indexOf(i, i + 1));
+        }
+
+        list.add(1);
+        assertEquals(1, list.indexOf(1, 0));
+        assertEquals(1, list.indexOf(1, 1));
+        assertEquals(size, list.indexOf(1, 2));
+        assertEquals(size, list.indexOf(1, size));
+    }
+
+    /**
+     * isEmpty returns true when empty, else false
+     */
+    public void testIsEmpty() {
+        List empty = new Vector();
+        assertTrue(empty.isEmpty());
+        assertTrue(empty.subList(0, 0).isEmpty());
+
+        List full = populatedList(SIZE);
+        assertFalse(full.isEmpty());
+        assertTrue(full.subList(0, 0).isEmpty());
+        assertTrue(full.subList(SIZE, SIZE).isEmpty());
+    }
+
+    /**
+     * iterator of empty collection has no elements
+     */
+    public void testEmptyIterator() {
+        Collection c = new Vector();
+        assertIteratorExhausted(c.iterator());
+    }
+
+    /**
+     * lastIndexOf(Object) returns the index of the last occurrence of
+     * the specified element in this list, or -1 if this list does not
+     * contain the element
+     */
+    public void testLastIndexOf1() {
+        List list = populatedList(3);
+        assertEquals(-1, list.lastIndexOf(-42));
+        int size = list.size();
+        for (int i = 0; i < size; i++) {
+            assertEquals(i, list.lastIndexOf(i));
+            assertEquals(i, list.subList(0, size).lastIndexOf(i));
+            assertEquals(i, list.subList(0, i + 1).lastIndexOf(i));
+            assertEquals(-1, list.subList(0, i).lastIndexOf(i));
+            assertEquals(0, list.subList(i, size).lastIndexOf(i));
+            assertEquals(-1, list.subList(i + 1, size).lastIndexOf(i));
+        }
+
+        list.add(1);
+        assertEquals(size, list.lastIndexOf(1));
+        assertEquals(size, list.subList(0, size + 1).lastIndexOf(1));
+        assertEquals(1, list.subList(0, size).lastIndexOf(1));
+        assertEquals(0, list.subList(1, 2).lastIndexOf(1));
+        assertEquals(-1, list.subList(0, 1).indexOf(1));
+    }
+
+    /**
+     * lastIndexOf(E, int) returns the index of the last occurrence of the
+     * specified element in this list, searching backwards from index, or
+     * returns -1 if the element is not found
+     */
+    public void testLastIndexOf2() {
+        Vector list = populatedList(3);
+
+        // we might expect IOOBE, but spec says otherwise
+        assertEquals(-1, list.lastIndexOf(0, -1));
+
+        int size = list.size();
+        assertThrows(
+            IndexOutOfBoundsException.class,
+            () -> list.lastIndexOf(0, size),
+            () -> list.lastIndexOf(0, Integer.MAX_VALUE));
+
+        for (int i = 0; i < size; i++) {
+            assertEquals(i, list.lastIndexOf(i, i));
+            assertEquals(list.indexOf(i), list.lastIndexOf(i, i));
+            if (i > 0)
+                assertEquals(-1, list.lastIndexOf(i, i - 1));
+        }
+        list.add(one);
+        list.add(three);
+        assertEquals(1, list.lastIndexOf(one, 1));
+        assertEquals(1, list.lastIndexOf(one, 2));
+        assertEquals(3, list.lastIndexOf(one, 3));
+        assertEquals(3, list.lastIndexOf(one, 4));
+        assertEquals(-1, list.lastIndexOf(three, 3));
+    }
+
+    /**
+     * size returns the number of elements
+     */
+    public void testSize() {
+        List empty = new Vector();
+        assertEquals(0, empty.size());
+        assertEquals(0, empty.subList(0, 0).size());
+
+        List full = populatedList(SIZE);
+        assertEquals(SIZE, full.size());
+        assertEquals(0, full.subList(0, 0).size());
+        assertEquals(0, full.subList(SIZE, SIZE).size());
+    }
+
+    /**
+     * sublists contains elements at indexes offset from their base
+     */
+    public void testSubList() {
+        List a = populatedList(10);
+        assertTrue(a.subList(1,1).isEmpty());
+        for (int j = 0; j < 9; ++j) {
+            for (int i = j ; i < 10; ++i) {
+                List b = a.subList(j,i);
+                for (int k = j; k < i; ++k) {
+                    assertEquals(new Integer(k), b.get(k-j));
+                }
+            }
+        }
+
+        List s = a.subList(2, 5);
+        assertEquals(3, s.size());
+        s.set(2, m1);
+        assertEquals(a.get(4), m1);
+        s.clear();
+        assertEquals(7, a.size());
+
+        assertThrows(
+            IndexOutOfBoundsException.class,
+            () -> s.get(0),
+            () -> s.set(0, 42));
+    }
+
+    /**
+     * toArray throws an ArrayStoreException when the given array
+     * can not store the objects inside the list
+     */
+    public void testToArray_ArrayStoreException() {
+        List list = new Vector();
+        // Integers are not auto-converted to Longs
+        list.add(86);
+        list.add(99);
+        assertThrows(
+            ArrayStoreException.class,
+            () -> list.toArray(new Long[0]),
+            () -> list.toArray(new Long[5]));
+    }
+
+    void testIndexOutOfBoundsException(List list) {
+        int size = list.size();
+        assertThrows(
+            IndexOutOfBoundsException.class,
+            () -> list.get(-1),
+            () -> list.get(size),
+            () -> list.set(-1, "qwerty"),
+            () -> list.set(size, "qwerty"),
+            () -> list.add(-1, "qwerty"),
+            () -> list.add(size + 1, "qwerty"),
+            () -> list.remove(-1),
+            () -> list.remove(size),
+            () -> list.addAll(-1, Collections.emptyList()),
+            () -> list.addAll(size + 1, Collections.emptyList()),
+            () -> list.listIterator(-1),
+            () -> list.listIterator(size + 1),
+            () -> list.subList(-1, size),
+            () -> list.subList(0, size + 1));
+
+        // Conversely, operations that must not throw
+        list.addAll(0, Collections.emptyList());
+        list.addAll(size, Collections.emptyList());
+        list.add(0, "qwerty");
+        list.add(list.size(), "qwerty");
+        list.get(0);
+        list.get(list.size() - 1);
+        list.set(0, "azerty");
+        list.set(list.size() - 1, "azerty");
+        list.listIterator(0);
+        list.listIterator(list.size());
+        list.subList(0, list.size());
+        list.remove(list.size() - 1);
+    }
+
+    /**
+     * IndexOutOfBoundsException is thrown when specified
+     */
+    public void testIndexOutOfBoundsException() {
+        ThreadLocalRandom rnd = ThreadLocalRandom.current();
+        List x = populatedList(rnd.nextInt(5));
+        testIndexOutOfBoundsException(x);
+
+        int start = rnd.nextInt(x.size() + 1);
+        int end = rnd.nextInt(start, x.size() + 1);
+
+        // Vector#subList spec deviates slightly from List#subList spec
+        assertThrows(
+            IllegalArgumentException.class,
+            () -> x.subList(start, start - 1));
+
+        List subList = x.subList(start, end);
+        testIndexOutOfBoundsException(x);
+    }
+
+    /**
+     * a deserialized/reserialized list equals original
+     */
+    public void testSerialization() throws Exception {
+        List x = populatedList(SIZE);
+        List y = serialClone(x);
+
+        assertNotSame(x, y);
+        assertEquals(x.size(), y.size());
+        assertEquals(x.toString(), y.toString());
+        assertTrue(Arrays.equals(x.toArray(), y.toArray()));
+        assertEquals(x, y);
+        assertEquals(y, x);
+        while (!x.isEmpty()) {
+            assertFalse(y.isEmpty());
+            assertEquals(x.remove(0), y.remove(0));
+        }
+        assertTrue(y.isEmpty());
+    }
+
     /**
      * tests for setSize()
      */