# HG changeset patch # User redestad # Date 1511190101 -3600 # Mon Nov 20 16:01:41 2017 +0100 # Node ID 15663ec3c162efac8c816af2a3af91eaabafe724 # Parent 4fab795915b645475a8ed94c46e2c9ae3f27409c imported patch immu0 diff --git a/src/java.base/share/classes/java/util/ImmutableCollections.java b/src/java.base/share/classes/java/util/ImmutableCollections.java --- a/src/java.base/share/classes/java/util/ImmutableCollections.java +++ b/src/java.base/share/classes/java/util/ImmutableCollections.java @@ -59,6 +59,8 @@ SALT = (int)((nt >>> 32) ^ nt); } + private static final Object NULL = new Object(); + /** No instances. */ private ImmutableCollections() { } @@ -86,55 +88,25 @@ @Override public void sort(Comparator c) { throw uoe(); } } - static final class List0 extends AbstractImmutableList { - private static final List0 INSTANCE = new List0<>(); + static final List EMPTY_LIST = new ListN<>(); - @SuppressWarnings("unchecked") - static List0 instance() { - return (List0) INSTANCE; - } + static final Set EMPTY_SET = new SetN<>(); - private List0() { } + static final Map EMPTY_MAP = new MapN<>(); - @Override - public int size() { - return 0; - } + @SuppressWarnings("unchecked") + static List emptyList() { + return (List) EMPTY_LIST; + } - @Override - public E get(int index) { - Objects.checkIndex(index, 0); // always throws IndexOutOfBoundsException - return null; // but the compiler doesn't know this - } + @SuppressWarnings("unchecked") + static Set emptySet() { + return (Set) EMPTY_SET; + } - @Override - public Iterator 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_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; - } + @SuppressWarnings("unchecked") + static Map emptyMap() { + return (Map) EMPTY_MAP; } static final class List1 extends AbstractImmutableList { @@ -175,52 +147,6 @@ } } - static final class List2 extends AbstractImmutableList { - @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; - } - } - - @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 extends AbstractImmutableList { @Stable private final E[] elements; @@ -287,51 +213,6 @@ @Override public boolean retainAll(Collection c) { throw uoe(); } } - static final class Set0 extends AbstractImmutableSet { - private static final Set0 INSTANCE = new Set0<>(); - - @SuppressWarnings("unchecked") - static Set0 instance() { - return (Set0) 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 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 extends AbstractImmutableSet { @Stable private final E e0; @@ -369,75 +250,6 @@ } } - static final class Set2 extends AbstractImmutableSet { - @Stable - final E e0; - @Stable - final E e1; - - Set2(E e0, E e1) { - if (e0.equals(Objects.requireNonNull(e1))) { // implicit nullcheck of e0 - throw new IllegalArgumentException("duplicate element: " + e0); - } - - if (SALT >= 0) { - this.e0 = e0; - this.e1 = e1; - } else { - this.e0 = e1; - this.e1 = e0; - } - } - - @Override - public int size() { - return 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(); - } - - @Override - public Iterator iterator() { - return new Iterator() { - private int idx = 0; - - @Override - public boolean hasNext() { - return idx < 2; - } - - @Override - public E next() { - if (idx == 0) { - idx = 1; - return e0; - } else if (idx == 1) { - idx = 2; - return e1; - } else { - throw new NoSuchElementException(); - } - } - }; - } - - private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { - throw new InvalidObjectException("not serial proxy"); - } - - private Object writeReplace() { - 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 @@ -474,7 +286,8 @@ @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 @@ -565,47 +378,6 @@ @Override public void replaceAll(BiFunction f) { throw uoe(); } } - static final class Map0 extends AbstractImmutableMap { - private static final Map0 INSTANCE = new Map0<>(); - - @SuppressWarnings("unchecked") - static Map0 instance() { - return (Map0) INSTANCE; - } - - private Map0() { } - - @Override - public Set> 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 extends AbstractImmutableMap { @Stable private final K k0; @@ -658,7 +430,6 @@ static final class MapN extends AbstractImmutableMap { @Stable final Object[] table; // pairs of key, value - @Stable final int size; // number of pairs MapN(Object... input) { @@ -689,7 +460,8 @@ @Override public boolean containsKey(Object o) { - return probe(o) >= 0; // implicit nullcheck of o + Objects.requireNonNull(0); + return size > 0 && probe(o) >= 0; } @Override @@ -718,6 +490,9 @@ @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]; @@ -948,7 +723,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 { diff --git a/src/java.base/share/classes/java/util/List.java b/src/java.base/share/classes/java/util/List.java --- a/src/java.base/share/classes/java/util/List.java +++ b/src/java.base/share/classes/java/util/List.java @@ -787,7 +787,7 @@ * @since 9 */ static List of() { - return ImmutableCollections.List0.instance(); + return ImmutableCollections.emptyList(); } /** @@ -820,7 +820,7 @@ * @since 9 */ static List of(E e1, E e2) { - return new ImmutableCollections.List2<>(e1, e2); + return new ImmutableCollections.ListN<>(e1, e2); } /** @@ -1030,11 +1030,9 @@ static List 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]); - case 2: - return new ImmutableCollections.List2<>(elements[0], elements[1]); default: return new ImmutableCollections.ListN<>(elements); } diff --git a/src/java.base/share/classes/java/util/Map.java b/src/java.base/share/classes/java/util/Map.java --- a/src/java.base/share/classes/java/util/Map.java +++ b/src/java.base/share/classes/java/util/Map.java @@ -1286,7 +1286,7 @@ * @since 9 */ static Map of() { - return ImmutableCollections.Map0.instance(); + return ImmutableCollections.emptyMap(); } /** @@ -1603,7 +1603,7 @@ @SuppressWarnings("varargs") static Map ofEntries(Entry... entries) { if (entries.length == 0) { // implicit null check of entries - return ImmutableCollections.Map0.instance(); + return ImmutableCollections.emptyMap(); } else if (entries.length == 1) { return new ImmutableCollections.Map1<>(entries[0].getKey(), entries[0].getValue()); diff --git a/src/java.base/share/classes/java/util/Set.java b/src/java.base/share/classes/java/util/Set.java --- a/src/java.base/share/classes/java/util/Set.java +++ b/src/java.base/share/classes/java/util/Set.java @@ -448,7 +448,7 @@ * @since 9 */ static Set of() { - return ImmutableCollections.Set0.instance(); + return ImmutableCollections.emptySet(); } /** @@ -480,7 +480,7 @@ * @since 9 */ static Set of(E e1, E e2) { - return new ImmutableCollections.Set2<>(e1, e2); + return new ImmutableCollections.SetN<>(e1, e2); } /** @@ -691,11 +691,9 @@ static Set 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]); - case 2: - return new ImmutableCollections.Set2<>(elements[0], elements[1]); default: return new ImmutableCollections.SetN<>(elements); } # HG changeset patch # User redestad # Date 1511196859 -3600 # Mon Nov 20 17:54:19 2017 +0100 # Node ID 5fd20486d4c1d62f09231cd4e3a3d0d625a5449b # Parent 15663ec3c162efac8c816af2a3af91eaabafe724 imported patch listn diff --git a/src/java.base/share/classes/java/util/AbstractList.java b/src/java.base/share/classes/java/util/AbstractList.java --- a/src/java.base/share/classes/java/util/AbstractList.java +++ b/src/java.base/share/classes/java/util/AbstractList.java @@ -341,6 +341,7 @@ } private class Itr implements Iterator { + /** * Index of element to be returned by subsequent call to next. */ diff --git a/src/java.base/share/classes/java/util/ImmutableCollections.java b/src/java.base/share/classes/java/util/ImmutableCollections.java --- a/src/java.base/share/classes/java/util/ImmutableCollections.java +++ b/src/java.base/share/classes/java/util/ImmutableCollections.java @@ -74,20 +74,6 @@ // ---------- List Implementations ---------- - abstract static class AbstractImmutableList extends AbstractList - implements RandomAccess, Serializable { - @Override public boolean add(E e) { throw uoe(); } - @Override public boolean addAll(Collection c) { throw uoe(); } - @Override public boolean addAll(int index, Collection 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 filter) { throw uoe(); } - @Override public void replaceAll(UnaryOperator operator) { throw uoe(); } - @Override public boolean retainAll(Collection c) { throw uoe(); } - @Override public void sort(Comparator c) { throw uoe(); } - } - static final List EMPTY_LIST = new ListN<>(); static final Set EMPTY_SET = new SetN<>(); @@ -109,95 +95,394 @@ return (Map) EMPTY_MAP; } - static final class List1 extends AbstractImmutableList { - @Stable - private final E e0; + static final class ListN extends AbstractCollection + implements List, RandomAccess, Serializable { - List1(E e0) { - this.e0 = Objects.requireNonNull(e0); + // 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 c) { throw uoe(); } + @Override public boolean addAll(int index, Collection 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 filter) { throw uoe(); } + @Override public void replaceAll(UnaryOperator 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 c) { throw uoe(); } + + @Override + public int indexOf(Object o) { + Objects.requireNonNull(o); + ListIterator it = listIterator(); + while (it.hasNext()) { + if (o.equals(it.next())) { + return it.previousIndex(); + } + } + return -1; } @Override - public int size() { - return 1; + public int lastIndexOf(Object o) { + Objects.requireNonNull(o); + ListIterator it = listIterator(); + while (it.hasNext()) { + if (o.equals(it.next())) { + return it.previousIndex(); + } + } + return -1; } @Override + public boolean equals(Object o) { + if (o == this) { + return true; + } + + if (!(o instanceof List)) { + return false; + } + + if (!(o instanceof ListN)) { + ListN other = (ListN)o; + return this.e0.equals(other.e0) && this.e1.equals(e1); + } + + ListIterator e1 = listIterator(); + ListIterator e2 = ((List) o).listIterator(); + 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()); + } + + @Override + public List 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(this, fromIndex, toIndex); + } + } + + private static class SubList extends AbstractList implements RandomAccess { + private final List 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 c) { throw uoe(); } + @Override public boolean addAll(int index, Collection 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 filter) { throw uoe(); } + @Override public void replaceAll(UnaryOperator 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 c) { throw uoe(); } + + /** + * Constructs a sublist of an arbitrary AbstractList, which is + * not a SubList itself. + */ + public SubList(List root, int fromIndex, int toIndex) { + this.root = root; + this.offset = fromIndex; + this.size = toIndex - fromIndex; + } + + /** + * Constructs a sublist of another SubList. + */ + protected SubList(SubList 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, size); + return root.get(offset + index); + } + + public int size() { + return size; + } + + protected void removeRange(int fromIndex, int toIndex) { + throw uoe(); + } + + public Iterator iterator() { + return listIterator(); + } + + public ListIterator listIterator(int index) { + rangeCheck(index); + + return new ListIterator() { + private final ListIterator i = + root.listIterator(offset + index); + + public boolean hasNext() { + return nextIndex() < size; + } + + 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 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; + } + } + + @Stable + private final Object e0; + + @Stable + private final Object e1; + + private final int size; + + @SafeVarargs + ListN(E... input) { + if (input.length == 1) { + e0 = Objects.requireNonNull(input[0]); + e1 = NULL; + size = 1; + } else if (input.length == 2) { + e0 = Objects.requireNonNull(input[0]); + e1 = Objects.requireNonNull(input[1]); + size = 2; + } else { + e0 = NULL; + // 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.e1 = tmp; + size = input.length; + } + } + + @Override + public boolean isEmpty() { + return size() == 0; + } + + @Override + @SuppressWarnings("unchecked") + public int size() { + return size; + } + + @Override + @SuppressWarnings("unchecked") public E get(int index) { - Objects.checkIndex(index, 1); - return e0; + int size = size(); + Objects.checkIndex(index, size); // IOOBE if size == 0, or size == 1 and index == 1 + if (size <= 2) { + if (index == 0) { + return (E)e0; + } else { + return (E)e1; + } + } else { + return ((E[]) e1)[index]; + } + } + + @Override + @SuppressWarnings("unchecked") + public boolean contains(Object o) { + int size = size(); + Objects.requireNonNull(o); + if (size == 1) { + return o.equals(e0); + } else if (size == 2) { + return o.equals(e0) || o.equals(e1); + } else { + for (E e : (E[])e1) { + if (o.equals(e)) { // implicit nullcheck of o + return true; + } + } + return false; + } + } + + @Override + @SuppressWarnings("unchecked") + public int hashCode() { + int size = size(); + if (size == 1) { + return 31 + e0.hashCode(); + } else if (size == 2) { + return (31 + e0.hashCode()) * 31 + e1.hashCode(); + } + + int hash = 1; + for (E e : (E[])e1) { + hash = 31 * hash + e.hashCode(); + } + return hash; + } + + @Override + public Iterator iterator() { + return new Itr(); + } + + @Override + public ListIterator listIterator() { + return listIterator(0); + } + + @Override + public ListIterator listIterator(final int index) { + Objects.checkIndex(index, size()); + return new ListItr(index); + } + + private class Itr implements Iterator { + Itr() { + size = size(); + } + + int cursor = 0; + + private final int size; + + public boolean hasNext() { + return cursor != size; + } + + public E next() { + try { + int i = cursor; + E next = get(i); + cursor = i + 1; + return next; + } catch (IndexOutOfBoundsException e) { + throw new NoSuchElementException(); + } + } + + public void remove() { + throw uoe(); + } + } + + private class ListItr extends Itr implements ListIterator { + ListItr(int index) { + cursor = index; + } + + public boolean hasPrevious() { + return cursor != 0; + } + + 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(); + } } 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, 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 ListN extends AbstractImmutableList { - @Stable - private final E[] elements; - - @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]); + int size = size(); + if (size == 1) { + return new CollSer(CollSer.IMM_LIST, (E)e0); + } else if (size == 2) { + return new CollSer(CollSer.IMM_LIST, (E)e0, (E)e1); + } else { + return new CollSer(CollSer.IMM_LIST, (E[])e1); } - this.elements = tmp; - } - - @Override - public int size() { - return elements.length; - } - - @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"); - } - - private Object writeReplace() { - return new CollSer(CollSer.IMM_LIST, elements); } } diff --git a/src/java.base/share/classes/java/util/List.java b/src/java.base/share/classes/java/util/List.java --- a/src/java.base/share/classes/java/util/List.java +++ b/src/java.base/share/classes/java/util/List.java @@ -803,7 +803,7 @@ * @since 9 */ static List of(E e1) { - return new ImmutableCollections.List1<>(e1); + return new ImmutableCollections.ListN<>(e1); } /** @@ -1031,8 +1031,6 @@ switch (elements.length) { // implicit null check of elements case 0: return ImmutableCollections.emptyList(); - case 1: - return new ImmutableCollections.List1<>(elements[0]); default: return new ImmutableCollections.ListN<>(elements); }