< prev index next >

src/java.base/share/classes/java/util/ImmutableCollections.java

Print this page
rev 48077 : 8193128: Reduce number of implementation classes returned by List/Set/Map.of()
Reviewed-by: smarks

@@ -70,196 +70,435 @@
 
     static UnsupportedOperationException uoe() { return new UnsupportedOperationException(); }
 
     // ---------- List Implementations ----------
 
-    abstract static class AbstractImmutableList<E> extends AbstractList<E>
-                                                implements RandomAccess, Serializable {
+    static final List<?> EMPTY_LIST = new ListN<>();
+
+    @SuppressWarnings("unchecked")
+    static <E> List<E> emptyList() {
+        return (List<E>) EMPTY_LIST;
+    }
+
+    static abstract class AbstractImmutableList<E> extends AbstractCollection<E>
+            implements List<E>, RandomAccess, Serializable {
+
+        // all mutating methods throw UnsupportedOperationException
         @Override public boolean add(E e) { throw uoe(); }
+        @Override public void    add(int index, E element) { 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 E       remove(int index) { throw uoe(); }
         @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
         @Override public boolean removeIf(Predicate<? super E> filter) { 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(); }
-    }
 
-    static final class List0<E> extends AbstractImmutableList<E> {
-        private static final List0<?> INSTANCE = new List0<>();
+        @Override
+        public int indexOf(Object o) {
+            // Input should be checked for null, but this needs a CSR. See JDK-8191418
+            if (o == null) {
+                return -1;
+            }
+            // Objects.requireNonNull(o);
+            ListIterator<E> it = listIterator();
+            while (it.hasNext()) {
+                if (o.equals(it.next())) {
+                    return it.previousIndex();
+                }
+            }
+            return -1;
+        }
 
-        @SuppressWarnings("unchecked")
-        static <T> List0<T> instance() {
-            return (List0<T>) INSTANCE;
+        @Override
+        public int lastIndexOf(Object o) {
+            // Input should be checked for null, but this needs a CSR. See JDK-8191418
+            if (o == null) {
+                return -1;
         }
+            // Objects.requireNonNull(o);
 
-        private List0() { }
+            ListIterator<E> it = listIterator();
+            while (it.hasNext()) {
+                if (o.equals(it.next())) {
+                    return it.previousIndex();
+                }
+            }
+            return -1;
+        }
 
         @Override
-        public int size() {
-            return 0;
+        public boolean isEmpty() {
+            return size() == 0;
         }
 
         @Override
+        public List<E> subList(int fromIndex, int toIndex) {
+            int size = size();
+            Objects.checkFromToIndex(fromIndex, toIndex, size);
+            if (size == 0 || fromIndex == toIndex) {
+                return emptyList();
+            } else if (size == 1) {
+                // checks above deal with corner cases subList(0,0) and subList(1,1)
+                // that would return the empty list
+                assert(fromIndex == 0 && toIndex == 1);
+                return this;
+            } else {
+                return new SubList<E>(this, fromIndex, toIndex);
+            }
+        }
+
+        private static class SubList<E> extends AbstractList<E> implements RandomAccess {
+            private final List<E> root;
+            private final int offset;
+            int size;
+
+            // all mutating methods throw UnsupportedOperationException
+            @Override public boolean add(E e) { throw uoe(); }
+            @Override public void    add(int index, E element) { 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 E       remove(int index) { throw uoe(); }
+            @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
+            @Override public boolean removeIf(Predicate<? super E> filter) { 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(); }
+
+            /**
+             * Constructs a sublist of an arbitrary AbstractList, which is
+             * not a SubList itself.
+             */
+            public SubList(List<E> root, int fromIndex, int toIndex) {
+                this.root = root;
+                this.offset = fromIndex;
+                this.size = toIndex - fromIndex;
+            }
+
+            /**
+             * Constructs a sublist of another SubList.
+             */
+            protected SubList(SubList<E> parent, int fromIndex, int toIndex) {
+                this.root = parent.root;
+                this.offset = parent.offset + fromIndex;
+                this.size = toIndex - fromIndex;
+            }
+
         public E get(int index) {
-            Objects.checkIndex(index, 0); // always throws IndexOutOfBoundsException
-            return null;                  // but the compiler doesn't know this
+                Objects.checkIndex(index, size);
+                return root.get(offset + index);
+            }
+
+            public int size() {
+                return size;
+            }
+
+            protected void removeRange(int fromIndex, int toIndex) {
+                throw uoe();
         }
 
-        @Override
         public Iterator<E> iterator() {
-            return Collections.emptyIterator();
+                return listIterator();
         }
 
-        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
-            throw new InvalidObjectException("not serial proxy");
+            public ListIterator<E> listIterator(int index) {
+                rangeCheck(index);
+
+                return new ListIterator<E>() {
+                    private final ListIterator<E> i =
+                            root.listIterator(offset + index);
+
+                    public boolean hasNext() {
+                        return nextIndex() < size;
         }
 
-        private Object writeReplace() {
-            return new CollSer(CollSer.IMM_LIST);
+                    public E next() {
+                        if (hasNext())
+                            return i.next();
+                        else
+                            throw new NoSuchElementException();
+                    }
+
+                    public boolean hasPrevious() {
+                        return previousIndex() >= 0;
+                    }
+
+                    public E previous() {
+                        if (hasPrevious())
+                            return i.previous();
+                        else
+                            throw new NoSuchElementException();
+                    }
+
+                    public int nextIndex() {
+                        return i.nextIndex() - offset;
+                    }
+
+                    public int previousIndex() {
+                        return i.previousIndex() - offset;
+                    }
+
+                    public void remove() { throw uoe(); }
+                    public void set(E e) { throw uoe(); }
+                    public void add(E e) { throw uoe(); }
+                };
+            }
+
+            public List<E> subList(int fromIndex, int toIndex) {
+                subListRangeCheck(fromIndex, toIndex, size);
+                return new SubList<>(this, fromIndex, toIndex);
+            }
+
+            private void rangeCheck(int index) {
+                if (index < 0 || index > size)
+                    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+            }
+
+            private String outOfBoundsMsg(int index) {
+                return "Index: "+index+", Size: "+size;
+            }
         }
 
         @Override
-        public boolean contains(Object o) {
-            Objects.requireNonNull(o);
-            return false;
+        public Iterator<E> iterator() {
+            return new Itr();
         }
 
         @Override
-        public boolean containsAll(Collection<?> o) {
-            return o.isEmpty(); // implicit nullcheck of o
+        public ListIterator<E> listIterator() {
+            return listIterator(0);
         }
 
         @Override
-        public int hashCode() {
-            return 1;
+        public ListIterator<E> listIterator(final int index) {
+            Objects.checkIndex(index, size());
+            return new ListItr(index);
         }
+
+        private class Itr implements Iterator<E> {
+            Itr() {
+                size = size();
     }
 
-    static final class List1<E> extends AbstractImmutableList<E> {
-        @Stable
-        private final E e0;
+            int cursor = 0;
 
-        List1(E e0) {
-            this.e0 = Objects.requireNonNull(e0);
+            private final int size;
+
+            public boolean hasNext() {
+                return cursor != size;
         }
 
-        @Override
-        public int size() {
-            return 1;
+            public E next() {
+                try {
+                    int i = cursor;
+                    E next = get(i);
+                    cursor = i + 1;
+                    return next;
+                } catch (IndexOutOfBoundsException e) {
+                    throw new NoSuchElementException();
+                }
         }
 
-        @Override
-        public E get(int index) {
-            Objects.checkIndex(index, 1);
-            return e0;
+            public void remove() {
+                throw uoe();
+            }
         }
 
-        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
-            throw new InvalidObjectException("not serial proxy");
+        private class ListItr extends Itr implements ListIterator<E> {
+            ListItr(int index) {
+                cursor = index;
         }
 
-        private Object writeReplace() {
-            return new CollSer(CollSer.IMM_LIST, e0);
+            public boolean hasPrevious() {
+                return cursor != 0;
         }
 
-        @Override
-        public boolean contains(Object o) {
-            return o.equals(e0); // implicit nullcheck of o
+            public E previous() {
+                try {
+                    int i = cursor - 1;
+                    E previous = 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();
+            }
+
+            public void add(E e) {
+                throw uoe();
+            }
+        }
+
+
         @Override
-        public int hashCode() {
-            return 31 + e0.hashCode();
+        public boolean equals(Object o) {
+            if (o == this) {
+                return true;
+            }
+
+            if (!(o instanceof List)) {
+                return false;
+            }
+
+            Iterator<E> e1 = iterator();
+            Iterator<?> e2 = ((List<?>) o).iterator();
+            while (e1.hasNext() && e2.hasNext()) {
+                E o1 = e1.next();
+                Object o2 = e2.next();
+                if (!(o1==null ? o2==null : o1.equals(o2)))
+                    return false;
         }
+            return !(e1.hasNext() || e2.hasNext());
     }
 
-    static final class List2<E> extends AbstractImmutableList<E> {
+        IndexOutOfBoundsException outOfBounds(int index) {
+            return new IndexOutOfBoundsException("Index: " + index + " Size: " + size());
+        }
+
+    }
+
+    static final class List12<E> extends AbstractImmutableList<E> {
+
         @Stable
         private final E e0;
+
         @Stable
         private final E e1;
 
-        List2(E e0, 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
+        @SuppressWarnings("unchecked")
         public int size() {
-            return 2;
+            return e1 != null ? 2 : 1;
         }
 
         @Override
+        @SuppressWarnings("unchecked")
         public E get(int index) {
-            Objects.checkIndex(index, 2);
             if (index == 0) {
                 return e0;
-            } else { // index == 1
+            } else if (index == 1 && e1 != null) {
                 return e1;
             }
+            throw outOfBounds(index);
         }
 
         @Override
+        @SuppressWarnings("unchecked")
         public boolean contains(Object o) {
-            return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
+            return o.equals(e0) || o.equals(e1); // implicit null check of o
         }
 
         @Override
+        @SuppressWarnings("unchecked")
         public int hashCode() {
             int hash = 31 + e0.hashCode();
-            return 31 * hash + e1.hashCode();
+            if (e1 != null) {
+                hash = 31 * hash + e1.hashCode();
+            }
+            return hash;
         }
 
         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
             throw new InvalidObjectException("not serial proxy");
         }
 
+        @SuppressWarnings("unchecked")
         private Object writeReplace() {
+            if (e1 == null) {
+                return new CollSer(CollSer.IMM_LIST, e0);
+            } else {
             return new CollSer(CollSer.IMM_LIST, e0, e1);
         }
     }
+    }
 
     static final class ListN<E> extends AbstractImmutableList<E> {
+
         @Stable
         private final E[] elements;
 
+        @SuppressWarnings("unchecked")
+        ListN(E e0) {
+            elements = (E[])new Object[] { e0 };
+        }
+
+        @SuppressWarnings("unchecked")
+        ListN(E e0, E e1) {
+            elements = (E[])new Object[] { e0, e1 };
+        }
+
         @SafeVarargs
         ListN(E... input) {
             // copy and check manually to avoid TOCTOU
             @SuppressWarnings("unchecked")
             E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input
             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
+        @SuppressWarnings("unchecked")
         public int size() {
             return elements.length;
         }
 
         @Override
+        @SuppressWarnings("unchecked")
         public E get(int index) {
-            Objects.checkIndex(index, elements.length);
             return elements[index];
         }
 
         @Override
+        @SuppressWarnings("unchecked")
         public boolean contains(Object o) {
+            Objects.requireNonNull(o);
             for (E e : elements) {
-                if (o.equals(e)) { // implicit nullcheck of o
+                if (o.equals(e)) {
                     return true;
                 }
             }
             return false;
         }
 
         @Override
+        @SuppressWarnings("unchecked")
         public int hashCode() {
             int hash = 1;
             for (E e : elements) {
                 hash = 31 * hash + e.hashCode();
             }

@@ -268,116 +507,47 @@
 
         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
             throw new InvalidObjectException("not serial proxy");
         }
 
+        @SuppressWarnings("unchecked")
         private Object writeReplace() {
             return new CollSer(CollSer.IMM_LIST, elements);
         }
     }
 
     // ---------- Set Implementations ----------
 
+    static final Set<?> EMPTY_SET = new SetN<>();
+
+    @SuppressWarnings("unchecked")
+    static <E> Set<E> emptySet() {
+        return (Set<E>) EMPTY_SET;
+    }
+
     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() { }
-
-        @Override
-        public int size() {
-            return 0;
-        }
-
-        @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 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;
-        }
-    }
-
-    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();
-        }
-    }
-
-    static final class Set2<E> extends AbstractImmutableSet<E> {
+    static final class Set12<E> extends AbstractImmutableSet<E> {
         @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);
             }
 
             if (SALT >= 0) {

@@ -389,40 +559,40 @@
             }
         }
 
         @Override
         public int size() {
-            return 2;
+            return (e1 == null) ? 1 : 2;
         }
 
         @Override
         public boolean contains(Object o) {
             return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
         }
 
         @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;
+                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();
                     }
                 }

@@ -432,13 +602,17 @@
         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
             throw new InvalidObjectException("not serial proxy");
         }
 
         private Object writeReplace() {
+            if (e1 == null) {
+                return new CollSer(CollSer.IMM_SET, e0);
+            } else {
             return new CollSer(CollSer.IMM_SET, e0, e1);
         }
     }
+    }
 
     /**
      * An array-based Set implementation. The element array must be strictly
      * larger than the size (the number of contained elements) so that at
      * least one null is always present.

@@ -472,11 +646,12 @@
             return size;
         }
 
         @Override
         public boolean contains(Object o) {
-            return probe(o) >= 0; // implicit nullcheck of o
+            Objects.requireNonNull(0);
+            return size > 0 && probe(o) >= 0; // implicit nullcheck of o
         }
 
         @Override
         public Iterator<E> iterator() {
             return new Iterator<E>() {

@@ -547,10 +722,17 @@
         }
     }
 
     // ---------- Map Implementations ----------
 
+    static final Map<?,?> EMPTY_MAP = new MapN<>();
+
+    @SuppressWarnings("unchecked")
+    static <K,V> Map<K,V> emptyMap() {
+        return (Map<K,V>) 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(); }
         @Override public V computeIfAbsent(K key, Function<? super K,? extends V> mf) { throw uoe(); }
         @Override public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }

@@ -563,51 +745,10 @@
         @Override public V replace(K key, V value) { throw uoe(); }
         @Override public boolean replace(K key, V oldValue, V newValue) { throw uoe(); }
         @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;
         @Stable
         private final V v0;

@@ -656,13 +797,19 @@
      * @param <V> the value type
      */
     static final class MapN<K,V> extends AbstractImmutableMap<K,V> {
         @Stable
         final Object[] table; // pairs of key, value
-        @Stable
         final int size; // number of pairs
 
+        MapN(K key, V value) {
+            table = new Object[2];
+            table[0] = key;
+            table[1] = value;
+            size = 1;
+        }
+
         MapN(Object... input) {
             if ((input.length & 1) != 0) { // implicit nullcheck of input
                 throw new InternalError("length is odd");
             }
             size = input.length >> 1;

@@ -687,11 +834,12 @@
             }
         }
 
         @Override
         public boolean containsKey(Object o) {
-            return probe(o) >= 0; // implicit nullcheck of o
+            Objects.requireNonNull(0);
+            return size > 0 && probe(o) >= 0;
         }
 
         @Override
         public boolean containsValue(Object o) {
             for (int i = 1; i < table.length; i += 2) {

@@ -716,10 +864,13 @@
         }
 
         @Override
         @SuppressWarnings("unchecked")
         public V get(Object o) {
+            if (size == 0) {
+                return null;
+            }
             int i = probe(o);
             if (i >= 0) {
                 return (V)table[i+1];
             } else {
                 return null;

@@ -946,11 +1097,11 @@
                     return List.of(array);
                 case IMM_SET:
                     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 {
                         return new ImmutableCollections.MapN<>(array);
                     }
< prev index next >