8193128: Reduce number of implementation classes returned by List/Set/Map.of()
authorredestad
Sat, 09 Dec 2017 03:33:39 +0100
changeset 49283 a14ede52a278
parent 49282 271ef464fb3a
child 49284 a51ca91c2cde
8193128: Reduce number of implementation classes returned by List/Set/Map.of() 8191418: List.of().indexOf(null) doesn't throw NullPointerException Reviewed-by: smarks, jrose, martin, plevart
src/java.base/share/classes/java/util/AbstractSet.java
src/java.base/share/classes/java/util/ImmutableCollections.java
src/java.base/share/classes/java/util/List.java
src/java.base/share/classes/java/util/Map.java
src/java.base/share/classes/java/util/Set.java
test/jdk/java/util/Collection/MOAT.java
test/jdk/java/util/Collection/SetFactories.java
test/jdk/java/util/List/ListFactories.java
test/jdk/java/util/Map/MapFactories.java
--- a/src/java.base/share/classes/java/util/AbstractSet.java	Thu Mar 22 09:07:08 2018 -0700
+++ b/src/java.base/share/classes/java/util/AbstractSet.java	Sat Dec 09 03:33:39 2017 +0100
@@ -93,9 +93,7 @@
             return false;
         try {
             return containsAll(c);
-        } catch (ClassCastException unused)   {
-            return false;
-        } catch (NullPointerException unused) {
+        } catch (ClassCastException | NullPointerException unused) {
             return false;
         }
     }
--- a/src/java.base/share/classes/java/util/ImmutableCollections.java	Thu Mar 22 09:07:08 2018 -0700
+++ b/src/java.base/share/classes/java/util/ImmutableCollections.java	Sat Dec 09 03:33:39 2017 +0100
@@ -70,46 +70,297 @@
 
     static UnsupportedOperationException uoe() { return new UnsupportedOperationException(); }
 
-    // ---------- List Implementations ----------
-
-    abstract static class AbstractImmutableList<E> extends AbstractList<E>
-                                                implements RandomAccess, Serializable {
+    static abstract class AbstractImmutableCollection<E> extends AbstractCollection<E> {
+        // all mutating methods throw UnsupportedOperationException
         @Override public boolean add(E e) { throw uoe(); }
         @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
-        @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); }
         @Override public void    clear() { throw uoe(); }
         @Override public boolean remove(Object o) { throw uoe(); }
         @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
         @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
+        @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
+    }
+
+    // ---------- List Implementations ----------
+
+    @SuppressWarnings("unchecked")
+    static <E> List<E> emptyList() {
+        return (List<E>) ListN.EMPTY_LIST;
+    }
+
+    static abstract class AbstractImmutableList<E> extends AbstractImmutableCollection<E>
+            implements List<E>, RandomAccess {
+
+        // all mutating methods throw UnsupportedOperationException
+        @Override public void    add(int index, E element) { throw uoe(); }
+        @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); }
+        @Override public E       remove(int index) { throw uoe(); }
         @Override public void    replaceAll(UnaryOperator<E> operator) { throw uoe(); }
-        @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
+        @Override public E       set(int index, E element) { throw uoe(); }
         @Override public void    sort(Comparator<? super E> c) { throw uoe(); }
+
+        @Override
+        public List<E> subList(int fromIndex, int toIndex) {
+            int size = size();
+            subListRangeCheck(fromIndex, toIndex, size);
+            return SubList.fromList(this, fromIndex, toIndex);
+        }
+
+        static void subListRangeCheck(int fromIndex, int toIndex, int size) {
+            if (fromIndex < 0)
+                throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
+            if (toIndex > size)
+                throw new IndexOutOfBoundsException("toIndex = " + toIndex);
+            if (fromIndex > toIndex)
+                throw new IllegalArgumentException("fromIndex(" + fromIndex +
+                        ") > toIndex(" + toIndex + ")");
+        }
+
+        @Override
+        public Iterator<E> iterator() {
+            return new ListItr<E>(this, size());
+        }
+
+        @Override
+        public ListIterator<E> listIterator() {
+            return listIterator(0);
+        }
+
+        @Override
+        public ListIterator<E> listIterator(final int index) {
+            int size = size();
+            if (index < 0 || index > size) {
+                throw outOfBounds(index);
+            }
+            return new ListItr<E>(this, size, index);
+        }
+
+        @Override
+        public boolean equals(Object o) {
+            if (o == this) {
+                return true;
+            }
+
+            if (!(o instanceof List)) {
+                return false;
+            }
+
+            Iterator<?> oit = ((List<?>) o).iterator();
+            for (int i = 0, s = size(); i < s; i++) {
+                if (!oit.hasNext() || !get(i).equals(oit.next())) {
+                    return false;
+                }
+            }
+            return !oit.hasNext();
+        }
+
+        @Override
+        public int indexOf(Object o) {
+            Objects.requireNonNull(o);
+            for (int i = 0, s = size(); i < s; i++) {
+                if (o.equals(get(i))) {
+                    return i;
+                }
+            }
+            return -1;
+        }
+
+        @Override
+        public int lastIndexOf(Object o) {
+            Objects.requireNonNull(o);
+            for (int i = size() - 1; i >= 0; i--) {
+                if (o.equals(get(i))) {
+                    return i;
+                }
+            }
+            return -1;
+        }
+
+        @Override
+        public int hashCode() {
+            int hash = 1;
+            for (int i = 0, s = size(); i < s; i++) {
+                hash = 31 * hash + get(i).hashCode();
+            }
+            return hash;
+        }
+
+        @Override
+        public boolean contains(Object o) {
+            return indexOf(o) >= 0;
+        }
+
+        IndexOutOfBoundsException outOfBounds(int index) {
+            return new IndexOutOfBoundsException("Index: " + index + " Size: " + size());
+        }
     }
 
-    static final class List0<E> extends AbstractImmutableList<E> {
-        private static final List0<?> INSTANCE = new List0<>();
+    static final class ListItr<E> implements ListIterator<E> {
+
+        @Stable
+        private final List<E> list;
+
+        @Stable
+        private final int size;
+
+        private int cursor;
+
+        ListItr(List<E> list, int size) {
+            this(list, size, 0);
+        }
+
+        ListItr(List<E> list, int size, int index) {
+            this.list = list;
+            this.size = size;
+            this.cursor = index;
+        }
+
+        public boolean hasNext() {
+            return cursor != size;
+        }
 
-        @SuppressWarnings("unchecked")
-        static <T> List0<T> instance() {
-            return (List0<T>) INSTANCE;
+        public E next() {
+            try {
+                int i = cursor;
+                E next = list.get(i);
+                cursor = i + 1;
+                return next;
+            } catch (IndexOutOfBoundsException e) {
+                throw new NoSuchElementException();
+            }
+        }
+
+        public void remove() {
+            throw uoe();
+        }
+
+        public boolean hasPrevious() {
+            return cursor != 0;
+        }
+
+        public E previous() {
+            try {
+                int i = cursor - 1;
+                E previous = list.get(i);
+                cursor = i;
+                return previous;
+            } catch (IndexOutOfBoundsException e) {
+                throw new NoSuchElementException();
+            }
+        }
+
+        public int nextIndex() {
+            return cursor;
+        }
+
+        public int previousIndex() {
+            return cursor - 1;
+        }
+
+        public void set(E e) {
+            throw uoe();
         }
 
-        private List0() { }
+        public void add(E e) {
+            throw uoe();
+        }
+    }
+
+    static final class SubList<E> extends AbstractImmutableList<E>
+            implements RandomAccess {
+
+        @Stable
+        private final List<E> root;
+
+        @Stable
+        private final int offset;
+
+        @Stable
+        private final int size;
+
+        private SubList(List<E> root, int offset, int size) {
+            this.root = root;
+            this.offset = offset;
+            this.size = size;
+        }
+
+        /**
+         * Constructs a sublist of another SubList.
+         */
+        static <E> SubList<E> fromSubList(SubList<E> parent, int fromIndex, int toIndex) {
+            return new SubList<E>(parent.root, parent.offset + fromIndex, toIndex - fromIndex);
+        }
+
+        /**
+         * Constructs a sublist of an arbitrary AbstractImmutableList, which is
+         * not a SubList itself.
+         */
+        static <E> SubList<E> fromList(List<E> list, int fromIndex, int toIndex) {
+            return new SubList<E>(list, fromIndex, toIndex - fromIndex);
+        }
+
+        public E get(int index) {
+            Objects.checkIndex(index, size);
+            return root.get(offset + index);
+        }
+
+        public int size() {
+            return size;
+        }
+
+        public Iterator<E> iterator() {
+            return new ListItr<E>(this, size());
+        }
+
+        public ListIterator<E> listIterator(int index) {
+            rangeCheck(index);
+            return new ListItr<E>(this, size(), index);
+        }
+
+        public List<E> subList(int fromIndex, int toIndex) {
+            subListRangeCheck(fromIndex, toIndex, size);
+            return SubList.fromSubList(this, fromIndex, toIndex);
+        }
+
+        private void rangeCheck(int index) {
+            if (index < 0 || index > size) {
+                throw outOfBounds(index);
+            }
+        }
+    }
+
+    static final class List12<E> extends AbstractImmutableList<E>
+            implements Serializable {
+
+        @Stable
+        private final E e0;
+
+        @Stable
+        private final E e1;
+
+        List12(E e0) {
+            this.e0 = Objects.requireNonNull(e0);
+            this.e1 = null;
+        }
+
+        List12(E e0, E e1) {
+            this.e0 = Objects.requireNonNull(e0);
+            this.e1 = Objects.requireNonNull(e1);
+        }
 
         @Override
         public int size() {
-            return 0;
+            return e1 != null ? 2 : 1;
         }
 
         @Override
         public E get(int index) {
-            Objects.checkIndex(index, 0); // always throws IndexOutOfBoundsException
-            return null;                  // but the compiler doesn't know this
-        }
-
-        @Override
-        public Iterator<E> iterator() {
-            return Collections.emptyIterator();
+            if (index == 0) {
+                return e0;
+            } else if (index == 1 && e1 != null) {
+                return e1;
+            }
+            throw outOfBounds(index);
         }
 
         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
@@ -117,111 +368,20 @@
         }
 
         private Object writeReplace() {
-            return new CollSer(CollSer.IMM_LIST);
-        }
-
-        @Override
-        public boolean contains(Object o) {
-            Objects.requireNonNull(o);
-            return false;
-        }
-
-        @Override
-        public boolean containsAll(Collection<?> o) {
-            return o.isEmpty(); // implicit nullcheck of o
-        }
-
-        @Override
-        public int hashCode() {
-            return 1;
-        }
-    }
-
-    static final class List1<E> extends AbstractImmutableList<E> {
-        @Stable
-        private final E e0;
-
-        List1(E e0) {
-            this.e0 = Objects.requireNonNull(e0);
-        }
-
-        @Override
-        public int size() {
-            return 1;
-        }
-
-        @Override
-        public E get(int index) {
-            Objects.checkIndex(index, 1);
-            return e0;
-        }
-
-        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
-            throw new InvalidObjectException("not serial proxy");
-        }
-
-        private Object writeReplace() {
-            return new CollSer(CollSer.IMM_LIST, e0);
-        }
-
-        @Override
-        public boolean contains(Object o) {
-            return o.equals(e0); // implicit nullcheck of o
-        }
-
-        @Override
-        public int hashCode() {
-            return 31 + e0.hashCode();
-        }
-    }
-
-    static final class List2<E> extends AbstractImmutableList<E> {
-        @Stable
-        private final E e0;
-        @Stable
-        private final E e1;
-
-        List2(E e0, E e1) {
-            this.e0 = Objects.requireNonNull(e0);
-            this.e1 = Objects.requireNonNull(e1);
-        }
-
-        @Override
-        public int size() {
-            return 2;
-        }
-
-        @Override
-        public E get(int index) {
-            Objects.checkIndex(index, 2);
-            if (index == 0) {
-                return e0;
-            } else { // index == 1
-                return e1;
+            if (e1 == null) {
+                return new CollSer(CollSer.IMM_LIST, e0);
+            } else {
+                return new CollSer(CollSer.IMM_LIST, e0, e1);
             }
         }
 
-        @Override
-        public boolean contains(Object o) {
-            return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
-        }
-
-        @Override
-        public int hashCode() {
-            int hash = 31 + e0.hashCode();
-            return 31 * hash + e1.hashCode();
-        }
-
-        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
-            throw new InvalidObjectException("not serial proxy");
-        }
-
-        private Object writeReplace() {
-            return new CollSer(CollSer.IMM_LIST, e0, e1);
-        }
     }
 
-    static final class ListN<E> extends AbstractImmutableList<E> {
+    static final class ListN<E> extends AbstractImmutableList<E>
+            implements Serializable {
+
+        static final List<?> EMPTY_LIST = new ListN<>();
+
         @Stable
         private final E[] elements;
 
@@ -233,7 +393,12 @@
             for (int i = 0; i < input.length; i++) {
                 tmp[i] = Objects.requireNonNull(input[i]);
             }
-            this.elements = tmp;
+            elements = tmp;
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return size() == 0;
         }
 
         @Override
@@ -243,29 +408,9 @@
 
         @Override
         public E get(int index) {
-            Objects.checkIndex(index, elements.length);
             return elements[index];
         }
 
-        @Override
-        public boolean contains(Object o) {
-            for (E e : elements) {
-                if (o.equals(e)) { // implicit nullcheck of o
-                    return true;
-                }
-            }
-            return false;
-        }
-
-        @Override
-        public int hashCode() {
-            int hash = 1;
-            for (E e : elements) {
-                hash = 31 * hash + e.hashCode();
-            }
-            return hash;
-        }
-
         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
             throw new InvalidObjectException("not serial proxy");
         }
@@ -277,105 +422,52 @@
 
     // ---------- Set Implementations ----------
 
-    abstract static class AbstractImmutableSet<E> extends AbstractSet<E> implements Serializable {
-        @Override public boolean add(E e) { throw uoe(); }
-        @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
-        @Override public void    clear() { throw uoe(); }
-        @Override public boolean remove(Object o) { throw uoe(); }
-        @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
-        @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
-        @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
-    }
-
-    static final class Set0<E> extends AbstractImmutableSet<E> {
-        private static final Set0<?> INSTANCE = new Set0<>();
-
-        @SuppressWarnings("unchecked")
-        static <T> Set0<T> instance() {
-            return (Set0<T>) INSTANCE;
-        }
-
-        private Set0() { }
+    static abstract class AbstractImmutableSet<E> extends AbstractImmutableCollection<E>
+            implements Set<E> {
 
         @Override
-        public int size() {
-            return 0;
-        }
+        public boolean equals(Object o) {
+            if (o == this) {
+                return true;
+            } else if (!(o instanceof Set)) {
+                return false;
+            }
 
-        @Override
-        public boolean contains(Object o) {
-            Objects.requireNonNull(o);
-            return false;
-        }
-
-        @Override
-        public boolean containsAll(Collection<?> o) {
-            return o.isEmpty(); // implicit nullcheck of o
+            Collection<?> c = (Collection<?>) o;
+            if (c.size() != size()) {
+                return false;
+            }
+            for (Object e : c) {
+                if (e == null || !contains(e)) {
+                    return false;
+                }
+            }
+            return true;
         }
 
         @Override
-        public Iterator<E> iterator() {
-            return Collections.emptyIterator();
-        }
-
-        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
-            throw new InvalidObjectException("not serial proxy");
-        }
-
-        private Object writeReplace() {
-            return new CollSer(CollSer.IMM_SET);
-        }
-
-        @Override
-        public int hashCode() {
-            return 0;
-        }
+        public abstract int hashCode();
     }
 
-    static final class Set1<E> extends AbstractImmutableSet<E> {
-        @Stable
-        private final E e0;
-
-        Set1(E e0) {
-            this.e0 = Objects.requireNonNull(e0);
-        }
-
-        @Override
-        public int size() {
-            return 1;
-        }
-
-        @Override
-        public boolean contains(Object o) {
-            return o.equals(e0); // implicit nullcheck of o
-        }
-
-        @Override
-        public Iterator<E> iterator() {
-            return Collections.singletonIterator(e0);
-        }
-
-        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
-            throw new InvalidObjectException("not serial proxy");
-        }
-
-        private Object writeReplace() {
-            return new CollSer(CollSer.IMM_SET, e0);
-        }
-
-        @Override
-        public int hashCode() {
-            return e0.hashCode();
-        }
+    @SuppressWarnings("unchecked")
+    static <E> Set<E> emptySet() {
+        return (Set<E>) SetN.EMPTY_SET;
     }
 
-    static final class Set2<E> extends AbstractImmutableSet<E> {
+    static final class Set12<E> extends AbstractImmutableSet<E>
+            implements Serializable {
+
         @Stable
         final E e0;
         @Stable
         final E e1;
 
-        Set2(E e0, E e1) {
+        Set12(E e0) {
+            this.e0 = Objects.requireNonNull(e0);
+            this.e1 = null;
+        }
+
+        Set12(E e0, E e1) {
             if (e0.equals(Objects.requireNonNull(e1))) { // implicit nullcheck of e0
                 throw new IllegalArgumentException("duplicate element: " + e0);
             }
@@ -391,7 +483,7 @@
 
         @Override
         public int size() {
-            return 2;
+            return (e1 == null) ? 1 : 2;
         }
 
         @Override
@@ -401,26 +493,26 @@
 
         @Override
         public int hashCode() {
-            return e0.hashCode() + e1.hashCode();
+            return e0.hashCode() + (e1 == null ? 0 : e1.hashCode());
         }
 
         @Override
         public Iterator<E> iterator() {
-            return new Iterator<E>() {
-                private int idx = 0;
+            return new Iterator<>() {
+                private int idx = size();
 
                 @Override
                 public boolean hasNext() {
-                    return idx < 2;
+                    return idx > 0;
                 }
 
                 @Override
                 public E next() {
-                    if (idx == 0) {
-                        idx = 1;
+                    if (idx == 1) {
+                        idx = 0;
                         return e0;
-                    } else if (idx == 1) {
-                        idx = 2;
+                    } else if (idx == 2) {
+                        idx = 1;
                         return e1;
                     } else {
                         throw new NoSuchElementException();
@@ -434,7 +526,11 @@
         }
 
         private Object writeReplace() {
-            return new CollSer(CollSer.IMM_SET, e0, e1);
+            if (e1 == null) {
+                return new CollSer(CollSer.IMM_SET, e0);
+            } else {
+                return new CollSer(CollSer.IMM_SET, e0, e1);
+            }
         }
     }
 
@@ -444,7 +540,11 @@
      * least one null is always present.
      * @param <E> the element type
      */
-    static final class SetN<E> extends AbstractImmutableSet<E> {
+    static final class SetN<E> extends AbstractImmutableSet<E>
+            implements Serializable {
+
+        static final Set<?> EMPTY_SET = new SetN<>();
+
         @Stable
         final E[] elements;
         @Stable
@@ -474,12 +574,13 @@
 
         @Override
         public boolean contains(Object o) {
-            return probe(o) >= 0; // implicit nullcheck of o
+            Objects.requireNonNull(o);
+            return size > 0 && probe(o) >= 0;
         }
 
         @Override
         public Iterator<E> iterator() {
-            return new Iterator<E>() {
+            return new Iterator<>() {
                 private int idx = 0;
 
                 @Override
@@ -549,6 +650,11 @@
 
     // ---------- Map Implementations ----------
 
+    @SuppressWarnings("unchecked")
+    static <K,V> Map<K,V> emptyMap() {
+        return (Map<K,V>) MapN.EMPTY_MAP;
+    }
+
     abstract static class AbstractImmutableMap<K,V> extends AbstractMap<K,V> implements Serializable {
         @Override public void clear() { throw uoe(); }
         @Override public V compute(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
@@ -565,47 +671,6 @@
         @Override public void replaceAll(BiFunction<? super K,? super V,? extends V> f) { throw uoe(); }
     }
 
-    static final class Map0<K,V> extends AbstractImmutableMap<K,V> {
-        private static final Map0<?,?> INSTANCE = new Map0<>();
-
-        @SuppressWarnings("unchecked")
-        static <K,V> Map0<K,V> instance() {
-            return (Map0<K,V>) INSTANCE;
-        }
-
-        private Map0() { }
-
-        @Override
-        public Set<Map.Entry<K,V>> entrySet() {
-            return Set.of();
-        }
-
-        @Override
-        public boolean containsKey(Object o) {
-            Objects.requireNonNull(o);
-            return false;
-        }
-
-        @Override
-        public boolean containsValue(Object o) {
-            Objects.requireNonNull(o);
-            return false;
-        }
-
-        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
-            throw new InvalidObjectException("not serial proxy");
-        }
-
-        private Object writeReplace() {
-            return new CollSer(CollSer.IMM_MAP);
-        }
-
-        @Override
-        public int hashCode() {
-            return 0;
-        }
-    }
-
     static final class Map1<K,V> extends AbstractImmutableMap<K,V> {
         @Stable
         private final K k0;
@@ -656,8 +721,12 @@
      * @param <V> the value type
      */
     static final class MapN<K,V> extends AbstractImmutableMap<K,V> {
+
+        static final Map<?,?> EMPTY_MAP = new MapN<>();
+
         @Stable
         final Object[] table; // pairs of key, value
+
         @Stable
         final int size; // number of pairs
 
@@ -689,14 +758,16 @@
 
         @Override
         public boolean containsKey(Object o) {
-            return probe(o) >= 0; // implicit nullcheck of o
+            Objects.requireNonNull(o);
+            return size > 0 && probe(o) >= 0;
         }
 
         @Override
         public boolean containsValue(Object o) {
+            Objects.requireNonNull(o);
             for (int i = 1; i < table.length; i += 2) {
                 Object v = table[i];
-                if (v != null && o.equals(v)) { // implicit nullcheck of o
+                if (v != null && o.equals(v)) {
                     return true;
                 }
             }
@@ -718,6 +789,10 @@
         @Override
         @SuppressWarnings("unchecked")
         public V get(Object o) {
+            if (size == 0) {
+                Objects.requireNonNull(o);
+                return null;
+            }
             int i = probe(o);
             if (i >= 0) {
                 return (V)table[i+1];
@@ -733,7 +808,7 @@
 
         @Override
         public Set<Map.Entry<K,V>> entrySet() {
-            return new AbstractSet<Map.Entry<K,V>>() {
+            return new AbstractSet<>() {
                 @Override
                 public int size() {
                     return MapN.this.size;
@@ -741,7 +816,7 @@
 
                 @Override
                 public Iterator<Map.Entry<K,V>> iterator() {
-                    return new Iterator<Map.Entry<K,V>>() {
+                    return new Iterator<>() {
                         int idx = 0;
 
                         @Override
@@ -948,7 +1023,7 @@
                     return Set.of(array);
                 case IMM_MAP:
                     if (array.length == 0) {
-                        return ImmutableCollections.Map0.instance();
+                        return ImmutableCollections.emptyMap();
                     } else if (array.length == 2) {
                         return new ImmutableCollections.Map1<>(array[0], array[1]);
                     } else {
--- a/src/java.base/share/classes/java/util/List.java	Thu Mar 22 09:07:08 2018 -0700
+++ b/src/java.base/share/classes/java/util/List.java	Sat Dec 09 03:33:39 2017 +0100
@@ -788,7 +788,7 @@
      * @since 9
      */
     static <E> List<E> of() {
-        return ImmutableCollections.List0.instance();
+        return ImmutableCollections.emptyList();
     }
 
     /**
@@ -804,7 +804,7 @@
      * @since 9
      */
     static <E> List<E> of(E e1) {
-        return new ImmutableCollections.List1<>(e1);
+        return new ImmutableCollections.List12<>(e1);
     }
 
     /**
@@ -821,7 +821,7 @@
      * @since 9
      */
     static <E> List<E> of(E e1, E e2) {
-        return new ImmutableCollections.List2<>(e1, e2);
+        return new ImmutableCollections.List12<>(e1, e2);
     }
 
     /**
@@ -1031,11 +1031,11 @@
     static <E> List<E> of(E... elements) {
         switch (elements.length) { // implicit null check of elements
             case 0:
-                return ImmutableCollections.List0.instance();
+                return ImmutableCollections.emptyList();
             case 1:
-                return new ImmutableCollections.List1<>(elements[0]);
+                return new ImmutableCollections.List12<>(elements[0]);
             case 2:
-                return new ImmutableCollections.List2<>(elements[0], elements[1]);
+                return new ImmutableCollections.List12<>(elements[0], elements[1]);
             default:
                 return new ImmutableCollections.ListN<>(elements);
         }
--- a/src/java.base/share/classes/java/util/Map.java	Thu Mar 22 09:07:08 2018 -0700
+++ b/src/java.base/share/classes/java/util/Map.java	Sat Dec 09 03:33:39 2017 +0100
@@ -1287,7 +1287,7 @@
      * @since 9
      */
     static <K, V> Map<K, V> of() {
-        return ImmutableCollections.Map0.instance();
+        return ImmutableCollections.emptyMap();
     }
 
     /**
@@ -1604,11 +1604,11 @@
     @SuppressWarnings("varargs")
     static <K, V> Map<K, V> ofEntries(Entry<? extends K, ? extends V>... entries) {
         if (entries.length == 0) { // implicit null check of entries array
-            return ImmutableCollections.Map0.instance();
+            return ImmutableCollections.emptyMap();
         } else if (entries.length == 1) {
             // implicit null check of the array slot
             return new ImmutableCollections.Map1<>(entries[0].getKey(),
-                                                   entries[0].getValue());
+                    entries[0].getValue());
         } else {
             Object[] kva = new Object[entries.length << 1];
             int a = 0;
--- a/src/java.base/share/classes/java/util/Set.java	Thu Mar 22 09:07:08 2018 -0700
+++ b/src/java.base/share/classes/java/util/Set.java	Sat Dec 09 03:33:39 2017 +0100
@@ -449,7 +449,7 @@
      * @since 9
      */
     static <E> Set<E> of() {
-        return ImmutableCollections.Set0.instance();
+        return ImmutableCollections.emptySet();
     }
 
     /**
@@ -464,7 +464,7 @@
      * @since 9
      */
     static <E> Set<E> of(E e1) {
-        return new ImmutableCollections.Set1<>(e1);
+        return new ImmutableCollections.Set12<>(e1);
     }
 
     /**
@@ -481,7 +481,7 @@
      * @since 9
      */
     static <E> Set<E> of(E e1, E e2) {
-        return new ImmutableCollections.Set2<>(e1, e2);
+        return new ImmutableCollections.Set12<>(e1, e2);
     }
 
     /**
@@ -692,11 +692,11 @@
     static <E> Set<E> of(E... elements) {
         switch (elements.length) { // implicit null check of elements
             case 0:
-                return ImmutableCollections.Set0.instance();
+                return ImmutableCollections.emptySet();
             case 1:
-                return new ImmutableCollections.Set1<>(elements[0]);
+                return new ImmutableCollections.Set12<>(elements[0]);
             case 2:
-                return new ImmutableCollections.Set2<>(elements[0], elements[1]);
+                return new ImmutableCollections.Set12<>(elements[0], elements[1]);
             default:
                 return new ImmutableCollections.SetN<>(elements);
         }
--- a/test/jdk/java/util/Collection/MOAT.java	Thu Mar 22 09:07:08 2018 -0700
+++ b/test/jdk/java/util/Collection/MOAT.java	Sat Dec 09 03:33:39 2017 +0100
@@ -26,7 +26,7 @@
  * @bug     6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464
  *          4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753
  *          6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215
- *          4802647 7123424 8024709
+ *          4802647 7123424 8024709 8193128
  * @summary Run many tests on many Collection and Map implementations
  * @author  Martin Buchholz
  * @modules java.base/java.util:open
@@ -212,8 +212,11 @@
 
         // Immutable List
         testEmptyList(List.of());
+        testEmptyList(List.of().subList(0,0));
         testListMutatorsAlwaysThrow(List.of());
+        testListMutatorsAlwaysThrow(List.<Integer>of().subList(0,0));
         testEmptyListMutatorsAlwaysThrow(List.of());
+        testEmptyListMutatorsAlwaysThrow(List.<Integer>of().subList(0,0));
         for (List<Integer> list : Arrays.asList(
                 List.<Integer>of(),
                 List.of(1),
@@ -230,6 +233,17 @@
             testCollection(list);
             testImmutableList(list);
             testListMutatorsAlwaysThrow(list);
+            if (list.size() >= 1) {
+                // test subLists
+                List<Integer> headList = list.subList(0, list.size() - 1);
+                List<Integer> tailList = list.subList(1, list.size());
+                testCollection(headList);
+                testCollection(tailList);
+                testImmutableList(headList);
+                testImmutableList(tailList);
+                testListMutatorsAlwaysThrow(headList);
+                testListMutatorsAlwaysThrow(tailList);
+            }
         }
 
         List<Integer> listCopy = List.copyOf(Arrays.asList(1, 2, 3));
@@ -243,6 +257,44 @@
         testImmutableList(listCollected);
         testListMutatorsAlwaysThrow(listCollected);
 
+        // List indexOf / lastIndexOf
+
+        // 0 element
+        System.out.println("testListIndexOf size 0");
+        testListIndexOf(-1, -1);
+
+        System.out.println("testListIndexOf size 1");
+        testListIndexOf(-1, -1, 0);
+        testListIndexOf(0, 0, 1);
+
+        System.out.println("testListIndexOf size 2");
+        testListIndexOf(-1, -1, 0, 0);
+        testListIndexOf(0, 0, 1, 0);
+        testListIndexOf(0, 1, 1, 1);
+        testListIndexOf(1, 1, 0, 1);
+
+
+        System.out.println("testListIndexOf size 3");
+        testListIndexOf(-1, -1, 0, 0, 0);
+        testListIndexOf(0, 0, 1, 0, 0);
+        testListIndexOf(0, 1, 1, 1, 0);
+        testListIndexOf(1, 2, 0, 1, 1);
+        testListIndexOf(2, 2, 0, 0, 1);
+
+        System.out.println("testListIndexOf size N");
+        testListIndexOf(-1, -1, 0, 0, 0, 0, 0, 0, 0);
+        testListIndexOf(2, 6, 0, 0, 1, 0, 1, 0, 1);
+        testListIndexOf(4, 4, 0, 0, 0, 0, 1, 0, 0);
+        testListIndexOf(0, 6, 1, 1, 1, 1, 1, 1, 1);
+        testListIndexOf(0, 7, 1, 1, 1, 1, 1, 1, 1, 1);
+        testListIndexOf(0, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1);
+        testListIndexOf(0, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
+        testListIndexOf(0, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
+        testListIndexOf(0, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
+        testListIndexOf(0, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
+        testListIndexOf(12, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1);
+        testListIndexOf(-1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
+
         // Immutable Set
         testEmptySet(Set.of());
         testCollMutatorsAlwaysThrow(Set.of());
@@ -963,6 +1015,37 @@
         equal(it.next(), 4);
     }
 
+    // for any array of integer values, check that the result of lastIndexOf(1)
+    // and indexOf(1) match assumptions for all types of List<Integer> we can
+    // construct
+    private static void testListIndexOf(final int index,
+                                        final int lastIndex,
+                                        final Integer ... values) {
+        if (values.length == 0) {
+            checkListIndexOf(emptyList(), index, lastIndex);
+        } else if (values.length == 1) {
+            checkListIndexOf(singletonList(values[0]), index, lastIndex);
+            checkListIndexOf(nCopies(25, values[0]), index, lastIndex == 0 ? 24 : -1);
+        }
+        List<Integer> l = List.of(values);
+        checkListIndexOf(l, index, lastIndex);
+        checkListIndexOf(Arrays.asList(values), index, lastIndex);
+        checkListIndexOf(new ArrayList(l), index, lastIndex);
+        checkListIndexOf(new LinkedList(l), index, lastIndex);
+        checkListIndexOf(new Vector(l), index, lastIndex);
+        checkListIndexOf(new CopyOnWriteArrayList(l), index, lastIndex);
+    }
+
+    private static void checkListIndexOf(final List<Integer> list,
+                                         final int index,
+                                         final int lastIndex) {
+        String msg = list.getClass().toString();
+        equal(list.indexOf(1), index, msg);
+        equal(list.lastIndexOf(1), lastIndex, msg);
+        equal(list.subList(0, list.size()).indexOf(1), index, msg);
+        equal(list.subList(0, list.size()).lastIndexOf(1), lastIndex, msg);
+    }
+
     private static void testList(final List<Integer> l) {
         //----------------------------------------------------------------
         // 4802633: (coll) AbstractList.addAll(-1,emptyCollection)
@@ -1629,6 +1712,9 @@
     static void equal(Object x, Object y) {
         if (x == null ? y == null : x.equals(y)) pass();
         else {System.out.println(x + " not equal to " + y); fail();}}
+    static void equal(Object x, Object y, String msg) {
+        if (x == null ? y == null : x.equals(y)) pass();
+        else {System.out.println(x + " not equal to " + y + " : " + msg); fail();}}
     static void equal2(Object x, Object y) {equal(x, y); equal(y, x);}
     public static void main(String[] args) throws Throwable {
         try { realMain(args); } catch (Throwable t) { unexpected(t); }
--- a/test/jdk/java/util/Collection/SetFactories.java	Thu Mar 22 09:07:08 2018 -0700
+++ b/test/jdk/java/util/Collection/SetFactories.java	Sat Dec 09 03:33:39 2017 +0100
@@ -266,6 +266,11 @@
         Set.of((Object[])null);
     }
 
+    @Test(dataProvider="all", expectedExceptions=NullPointerException.class)
+    public void containsNullShouldThrowNPE(Set<String> act, Set<String> exp) {
+        act.contains(null);
+    }
+
     @Test(dataProvider="all")
     public void serialEquality(Set<String> act, Set<String> exp) {
         // assume that act.equals(exp) tested elsewhere
--- a/test/jdk/java/util/List/ListFactories.java	Thu Mar 22 09:07:08 2018 -0700
+++ b/test/jdk/java/util/List/ListFactories.java	Sat Dec 09 03:33:39 2017 +0100
@@ -26,6 +26,7 @@
 import java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
+import java.io.Serializable;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
@@ -72,7 +73,7 @@
     @DataProvider(name="empty")
     public Iterator<Object[]> empty() {
         return Collections.singletonList(
-            a(List.of(), Collections.emptyList())
+            a(List.of(), asList())
         ).iterator();
     }
 
@@ -104,11 +105,50 @@
         ).iterator();
     }
 
+    @DataProvider(name="sublists")
+    public Iterator<Object[]> sublists() {
+        return asList(
+            a(List.<String>of().subList(0,0),
+               asList()),
+            a(List.of("a").subList(0,0),
+               asList("a").subList(0,0)),
+            a(List.of("a", "b").subList(0,1),
+               asList("a", "b").subList(0,1)),
+            a(List.of("a", "b", "c").subList(1,3),
+               asList("a", "b", "c").subList(1,3)),
+            a(List.of("a", "b", "c", "d").subList(0,4),
+               asList("a", "b", "c", "d").subList(0,4)),
+            a(List.of("a", "b", "c", "d", "e").subList(0,3),
+               asList("a", "b", "c", "d", "e").subList(0,3)),
+            a(List.of("a", "b", "c", "d", "e", "f").subList(3, 5),
+               asList("a", "b", "c", "d", "e", "f").subList(3, 5)),
+            a(List.of("a", "b", "c", "d", "e", "f", "g").subList(0, 7),
+               asList("a", "b", "c", "d", "e", "f", "g").subList(0, 7)),
+            a(List.of("a", "b", "c", "d", "e", "f", "g", "h").subList(0, 0),
+               asList("a", "b", "c", "d", "e", "f", "g", "h").subList(0, 0)),
+            a(List.of("a", "b", "c", "d", "e", "f", "g", "h", "i").subList(4, 5),
+               asList("a", "b", "c", "d", "e", "f", "g", "h", "i").subList(4, 5)),
+            a(List.of("a", "b", "c", "d", "e", "f", "g", "h", "i", "j").subList(1,10),
+               asList("a", "b", "c", "d", "e", "f", "g", "h", "i", "j").subList(1,10)),
+            a(List.of(stringArray).subList(5, NUM_STRINGS),
+               asList(Arrays.copyOfRange(stringArray, 5, NUM_STRINGS)))
+                ).iterator();
+    }
+
     @DataProvider(name="all")
     public Iterator<Object[]> all() {
         List<Object[]> all = new ArrayList<>();
         empty().forEachRemaining(all::add);
         nonempty().forEachRemaining(all::add);
+        sublists().forEachRemaining(all::add);
+        return all.iterator();
+    }
+
+    @DataProvider(name="nonsublists")
+    public Iterator<Object[]> nonsublists() {
+        List<Object[]> all = new ArrayList<>();
+        empty().forEachRemaining(all::add);
+        nonempty().forEachRemaining(all::add);
         return all.iterator();
     }
 
@@ -212,7 +252,29 @@
         assertEquals(list, Arrays.asList(stringArray));
     }
 
-    @Test(dataProvider="all")
+    @Test(dataProvider="all", expectedExceptions=NullPointerException.class)
+    public void containsNullShouldThrowNPE(List<String> act, List<String> exp) {
+        act.contains(null);
+    }
+
+    @Test(dataProvider="all", expectedExceptions=NullPointerException.class)
+    public void indexOfNullShouldThrowNPE(List<String> act, List<String> exp) {
+        act.indexOf(null);
+    }
+
+    @Test(dataProvider="all", expectedExceptions=NullPointerException.class)
+    public void lastIndexOfNullShouldThrowNPE(List<String> act, List<String> exp) {
+        act.lastIndexOf(null);
+    }
+
+    // List.of().subList views should not be Serializable
+    @Test(dataProvider="sublists")
+    public void isNotSerializable(List<String> act, List<String> exp) {
+        assertFalse(act instanceof Serializable);
+    }
+
+    // ... but List.of() should be
+    @Test(dataProvider="nonsublists")
     public void serialEquality(List<String> act, List<String> exp) {
         // assume that act.equals(exp) tested elsewhere
         List<String> copy = serialClone(act);
--- a/test/jdk/java/util/Map/MapFactories.java	Thu Mar 22 09:07:08 2018 -0700
+++ b/test/jdk/java/util/Map/MapFactories.java	Sat Dec 09 03:33:39 2017 +0100
@@ -376,6 +376,16 @@
         Map.ofEntries((Map.Entry<?,?>[])null);
     }
 
+    @Test(dataProvider="all", expectedExceptions=NullPointerException.class)
+    public void containsValueNullShouldThrowNPE(Map<Integer,String> act, Map<Integer,String> exp) {
+        act.containsValue(null);
+    }
+
+    @Test(dataProvider="all", expectedExceptions=NullPointerException.class)
+    public void containsKeyNullShouldThrowNPE(Map<Integer,String> act, Map<Integer,String> exp) {
+        act.containsKey(null);
+    }
+
     @Test(dataProvider="all")
     public void serialEquality(Map<Integer, String> act, Map<Integer, String> exp) {
         // assume that act.equals(exp) tested elsewhere