< 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


  55      */
  56     static final int SALT;
  57     static {
  58         long nt = System.nanoTime();
  59         SALT = (int)((nt >>> 32) ^ nt);
  60     }
  61 
  62     /** No instances. */
  63     private ImmutableCollections() { }
  64 
  65     /**
  66      * The reciprocal of load factor. Given a number of elements
  67      * to store, multiply by this factor to get the table size.
  68      */
  69     static final int EXPAND_FACTOR = 2;
  70 
  71     static UnsupportedOperationException uoe() { return new UnsupportedOperationException(); }
  72 
  73     // ---------- List Implementations ----------
  74 
  75     abstract static class AbstractImmutableList<E> extends AbstractList<E>
  76                                                 implements RandomAccess, Serializable {









  77         @Override public boolean add(E e) { throw uoe(); }

  78         @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
  79         @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); }
  80         @Override public void    clear() { throw uoe(); }
  81         @Override public boolean remove(Object o) { throw uoe(); }

  82         @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
  83         @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
  84         @Override public void    replaceAll(UnaryOperator<E> operator) { throw uoe(); }
  85         @Override public boolean retainAll(Collection<?> c) { throw uoe(); }

  86         @Override public void    sort(Comparator<? super E> c) { throw uoe(); }
  87     }
  88 
  89     static final class List0<E> extends AbstractImmutableList<E> {
  90         private static final List0<?> INSTANCE = new List0<>();













  91 
  92         @SuppressWarnings("unchecked")
  93         static <T> List0<T> instance() {
  94             return (List0<T>) INSTANCE;


  95         }

  96 
  97         private List0() { }







  98 
  99         @Override
 100         public int size() {
 101             return 0;
 102         }
 103 
 104         @Override






















































 105         public E get(int index) {
 106             Objects.checkIndex(index, 0); // always throws IndexOutOfBoundsException
 107             return null;                  // but the compiler doesn't know this








 108         }
 109 
 110         @Override
 111         public Iterator<E> iterator() {
 112             return Collections.emptyIterator();
 113         }
 114 
 115         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 116             throw new InvalidObjectException("not serial proxy");







 117         }
 118 
 119         private Object writeReplace() {
 120             return new CollSer(CollSer.IMM_LIST);











































 121         }
 122 
 123         @Override
 124         public boolean contains(Object o) {
 125             Objects.requireNonNull(o);
 126             return false;
 127         }
 128 
 129         @Override
 130         public boolean containsAll(Collection<?> o) {
 131             return o.isEmpty(); // implicit nullcheck of o
 132         }
 133 
 134         @Override
 135         public int hashCode() {
 136             return 1;

 137         }




 138     }
 139 
 140     static final class List1<E> extends AbstractImmutableList<E> {
 141         @Stable
 142         private final E e0;
 143 
 144         List1(E e0) {
 145             this.e0 = Objects.requireNonNull(e0);


 146         }
 147 
 148         @Override
 149         public int size() {
 150             return 1;






 151         }
 152 
 153         @Override
 154         public E get(int index) {
 155             Objects.checkIndex(index, 1);
 156             return e0;
 157         }
 158 
 159         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 160             throw new InvalidObjectException("not serial proxy");

 161         }
 162 
 163         private Object writeReplace() {
 164             return new CollSer(CollSer.IMM_LIST, e0);
 165         }
 166 
 167         @Override
 168         public boolean contains(Object o) {
 169             return o.equals(e0); // implicit nullcheck of o






 170         }
 171 


















 172         @Override
 173         public int hashCode() {
 174             return 31 + e0.hashCode();














 175         }

 176     }
 177 
 178     static final class List2<E> extends AbstractImmutableList<E> {







 179         @Stable
 180         private final E e0;

 181         @Stable
 182         private final E e1;
 183 
 184         List2(E e0, E e1) {





 185             this.e0 = Objects.requireNonNull(e0);
 186             this.e1 = Objects.requireNonNull(e1);
 187         }
 188 
 189         @Override

 190         public int size() {
 191             return 2;
 192         }
 193 
 194         @Override

 195         public E get(int index) {
 196             Objects.checkIndex(index, 2);
 197             if (index == 0) {
 198                 return e0;
 199             } else { // index == 1
 200                 return e1;
 201             }

 202         }
 203 
 204         @Override

 205         public boolean contains(Object o) {
 206             return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
 207         }
 208 
 209         @Override

 210         public int hashCode() {
 211             int hash = 31 + e0.hashCode();
 212             return 31 * hash + e1.hashCode();



 213         }
 214 
 215         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 216             throw new InvalidObjectException("not serial proxy");
 217         }
 218 

 219         private Object writeReplace() {



 220             return new CollSer(CollSer.IMM_LIST, e0, e1);
 221         }
 222     }

 223 
 224     static final class ListN<E> extends AbstractImmutableList<E> {

 225         @Stable
 226         private final E[] elements;
 227 










 228         @SafeVarargs
 229         ListN(E... input) {
 230             // copy and check manually to avoid TOCTOU
 231             @SuppressWarnings("unchecked")
 232             E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input
 233             for (int i = 0; i < input.length; i++) {
 234                 tmp[i] = Objects.requireNonNull(input[i]);
 235             }
 236             this.elements = tmp;
 237         }
 238 
 239         @Override






 240         public int size() {
 241             return elements.length;
 242         }
 243 
 244         @Override

 245         public E get(int index) {
 246             Objects.checkIndex(index, elements.length);
 247             return elements[index];
 248         }
 249 
 250         @Override

 251         public boolean contains(Object o) {

 252             for (E e : elements) {
 253                 if (o.equals(e)) { // implicit nullcheck of o
 254                     return true;
 255                 }
 256             }
 257             return false;
 258         }
 259 
 260         @Override

 261         public int hashCode() {
 262             int hash = 1;
 263             for (E e : elements) {
 264                 hash = 31 * hash + e.hashCode();
 265             }
 266             return hash;
 267         }
 268 
 269         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 270             throw new InvalidObjectException("not serial proxy");
 271         }
 272 

 273         private Object writeReplace() {
 274             return new CollSer(CollSer.IMM_LIST, elements);
 275         }
 276     }
 277 
 278     // ---------- Set Implementations ----------
 279 







 280     abstract static class AbstractImmutableSet<E> extends AbstractSet<E> implements Serializable {
 281         @Override public boolean add(E e) { throw uoe(); }
 282         @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
 283         @Override public void    clear() { throw uoe(); }
 284         @Override public boolean remove(Object o) { throw uoe(); }
 285         @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
 286         @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
 287         @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
 288     }
 289 
 290     static final class Set0<E> extends AbstractImmutableSet<E> {
 291         private static final Set0<?> INSTANCE = new Set0<>();
 292 
 293         @SuppressWarnings("unchecked")
 294         static <T> Set0<T> instance() {
 295             return (Set0<T>) INSTANCE;
 296         }
 297 
 298         private Set0() { }
 299 
 300         @Override
 301         public int size() {
 302             return 0;
 303         }
 304 
 305         @Override
 306         public boolean contains(Object o) {
 307             Objects.requireNonNull(o);
 308             return false;
 309         }
 310 
 311         @Override
 312         public boolean containsAll(Collection<?> o) {
 313             return o.isEmpty(); // implicit nullcheck of o
 314         }
 315 
 316         @Override
 317         public Iterator<E> iterator() {
 318             return Collections.emptyIterator();
 319         }
 320 
 321         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 322             throw new InvalidObjectException("not serial proxy");
 323         }
 324 
 325         private Object writeReplace() {
 326             return new CollSer(CollSer.IMM_SET);
 327         }
 328 
 329         @Override
 330         public int hashCode() {
 331             return 0;
 332         }
 333     }
 334 
 335     static final class Set1<E> extends AbstractImmutableSet<E> {
 336         @Stable
 337         private final E e0;
 338 
 339         Set1(E e0) {
 340             this.e0 = Objects.requireNonNull(e0);
 341         }
 342 
 343         @Override
 344         public int size() {
 345             return 1;
 346         }
 347 
 348         @Override
 349         public boolean contains(Object o) {
 350             return o.equals(e0); // implicit nullcheck of o
 351         }
 352 
 353         @Override
 354         public Iterator<E> iterator() {
 355             return Collections.singletonIterator(e0);
 356         }
 357 
 358         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 359             throw new InvalidObjectException("not serial proxy");
 360         }
 361 
 362         private Object writeReplace() {
 363             return new CollSer(CollSer.IMM_SET, e0);
 364         }
 365 
 366         @Override
 367         public int hashCode() {
 368             return e0.hashCode();
 369         }
 370     }
 371 
 372     static final class Set2<E> extends AbstractImmutableSet<E> {
 373         @Stable
 374         final E e0;
 375         @Stable
 376         final E e1;
 377 
 378         Set2(E e0, E e1) {





 379             if (e0.equals(Objects.requireNonNull(e1))) { // implicit nullcheck of e0
 380                 throw new IllegalArgumentException("duplicate element: " + e0);
 381             }
 382 
 383             if (SALT >= 0) {
 384                 this.e0 = e0;
 385                 this.e1 = e1;
 386             } else {
 387                 this.e0 = e1;
 388                 this.e1 = e0;
 389             }
 390         }
 391 
 392         @Override
 393         public int size() {
 394             return 2;
 395         }
 396 
 397         @Override
 398         public boolean contains(Object o) {
 399             return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
 400         }
 401 
 402         @Override
 403         public int hashCode() {
 404             return e0.hashCode() + e1.hashCode();
 405         }
 406 
 407         @Override
 408         public Iterator<E> iterator() {
 409             return new Iterator<E>() {
 410                 private int idx = 0;
 411 
 412                 @Override
 413                 public boolean hasNext() {
 414                     return idx < 2;
 415                 }
 416 
 417                 @Override
 418                 public E next() {
 419                     if (idx == 0) {
 420                         idx = 1;
 421                         return e0;
 422                     } else if (idx == 1) {
 423                         idx = 2;
 424                         return e1;
 425                     } else {
 426                         throw new NoSuchElementException();
 427                     }
 428                 }
 429             };
 430         }
 431 
 432         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 433             throw new InvalidObjectException("not serial proxy");
 434         }
 435 
 436         private Object writeReplace() {



 437             return new CollSer(CollSer.IMM_SET, e0, e1);
 438         }
 439     }

 440 
 441     /**
 442      * An array-based Set implementation. The element array must be strictly
 443      * larger than the size (the number of contained elements) so that at
 444      * least one null is always present.
 445      * @param <E> the element type
 446      */
 447     static final class SetN<E> extends AbstractImmutableSet<E> {
 448         @Stable
 449         final E[] elements;
 450         @Stable
 451         final int size;
 452 
 453         @SafeVarargs
 454         @SuppressWarnings("unchecked")
 455         SetN(E... input) {
 456             size = input.length; // implicit nullcheck of input
 457 
 458             elements = (E[])new Object[EXPAND_FACTOR * input.length];
 459             for (int i = 0; i < input.length; i++) {
 460                 E e = input[i];
 461                 int idx = probe(e); // implicit nullcheck of e
 462                 if (idx >= 0) {
 463                     throw new IllegalArgumentException("duplicate element: " + e);
 464                 } else {
 465                     elements[-(idx + 1)] = e;
 466                 }
 467             }
 468         }
 469 
 470         @Override
 471         public int size() {
 472             return size;
 473         }
 474 
 475         @Override
 476         public boolean contains(Object o) {
 477             return probe(o) >= 0; // implicit nullcheck of o

 478         }
 479 
 480         @Override
 481         public Iterator<E> iterator() {
 482             return new Iterator<E>() {
 483                 private int idx = 0;
 484 
 485                 @Override
 486                 public boolean hasNext() {
 487                     while (idx < elements.length) {
 488                         if (elements[idx] != null)
 489                             return true;
 490                         idx++;
 491                     }
 492                     return false;
 493                 }
 494 
 495                 @Override
 496                 public E next() {
 497                     if (! hasNext()) {


 532         }
 533 
 534         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 535             throw new InvalidObjectException("not serial proxy");
 536         }
 537 
 538         private Object writeReplace() {
 539             Object[] array = new Object[size];
 540             int dest = 0;
 541             for (Object o : elements) {
 542                 if (o != null) {
 543                     array[dest++] = o;
 544                 }
 545             }
 546             return new CollSer(CollSer.IMM_SET, array);
 547         }
 548     }
 549 
 550     // ---------- Map Implementations ----------
 551 







 552     abstract static class AbstractImmutableMap<K,V> extends AbstractMap<K,V> implements Serializable {
 553         @Override public void clear() { throw uoe(); }
 554         @Override public V compute(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
 555         @Override public V computeIfAbsent(K key, Function<? super K,? extends V> mf) { throw uoe(); }
 556         @Override public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
 557         @Override public V merge(K key, V value, BiFunction<? super V,? super V,? extends V> rf) { throw uoe(); }
 558         @Override public V put(K key, V value) { throw uoe(); }
 559         @Override public void putAll(Map<? extends K,? extends V> m) { throw uoe(); }
 560         @Override public V putIfAbsent(K key, V value) { throw uoe(); }
 561         @Override public V remove(Object key) { throw uoe(); }
 562         @Override public boolean remove(Object key, Object value) { throw uoe(); }
 563         @Override public V replace(K key, V value) { throw uoe(); }
 564         @Override public boolean replace(K key, V oldValue, V newValue) { throw uoe(); }
 565         @Override public void replaceAll(BiFunction<? super K,? super V,? extends V> f) { throw uoe(); }
 566     }
 567 
 568     static final class Map0<K,V> extends AbstractImmutableMap<K,V> {
 569         private static final Map0<?,?> INSTANCE = new Map0<>();
 570 
 571         @SuppressWarnings("unchecked")
 572         static <K,V> Map0<K,V> instance() {
 573             return (Map0<K,V>) INSTANCE;
 574         }
 575 
 576         private Map0() { }
 577 
 578         @Override
 579         public Set<Map.Entry<K,V>> entrySet() {
 580             return Set.of();
 581         }
 582 
 583         @Override
 584         public boolean containsKey(Object o) {
 585             Objects.requireNonNull(o);
 586             return false;
 587         }
 588 
 589         @Override
 590         public boolean containsValue(Object o) {
 591             Objects.requireNonNull(o);
 592             return false;
 593         }
 594 
 595         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 596             throw new InvalidObjectException("not serial proxy");
 597         }
 598 
 599         private Object writeReplace() {
 600             return new CollSer(CollSer.IMM_MAP);
 601         }
 602 
 603         @Override
 604         public int hashCode() {
 605             return 0;
 606         }
 607     }
 608 
 609     static final class Map1<K,V> extends AbstractImmutableMap<K,V> {
 610         @Stable
 611         private final K k0;
 612         @Stable
 613         private final V v0;
 614 
 615         Map1(K k0, V v0) {
 616             this.k0 = Objects.requireNonNull(k0);
 617             this.v0 = Objects.requireNonNull(v0);
 618         }
 619 
 620         @Override
 621         public Set<Map.Entry<K,V>> entrySet() {
 622             return Set.of(new KeyValueHolder<>(k0, v0));
 623         }
 624 
 625         @Override
 626         public boolean containsKey(Object o) {
 627             return o.equals(k0); // implicit nullcheck of o
 628         }


 641         }
 642 
 643         @Override
 644         public int hashCode() {
 645             return k0.hashCode() ^ v0.hashCode();
 646         }
 647     }
 648 
 649     /**
 650      * An array-based Map implementation. There is a single array "table" that
 651      * contains keys and values interleaved: table[0] is kA, table[1] is vA,
 652      * table[2] is kB, table[3] is vB, etc. The table size must be even. It must
 653      * also be strictly larger than the size (the number of key-value pairs contained
 654      * in the map) so that at least one null key is always present.
 655      * @param <K> the key type
 656      * @param <V> the value type
 657      */
 658     static final class MapN<K,V> extends AbstractImmutableMap<K,V> {
 659         @Stable
 660         final Object[] table; // pairs of key, value
 661         @Stable
 662         final int size; // number of pairs
 663 







 664         MapN(Object... input) {
 665             if ((input.length & 1) != 0) { // implicit nullcheck of input
 666                 throw new InternalError("length is odd");
 667             }
 668             size = input.length >> 1;
 669 
 670             int len = EXPAND_FACTOR * input.length;
 671             len = (len + 1) & ~1; // ensure table is even length
 672             table = new Object[len];
 673 
 674             for (int i = 0; i < input.length; i += 2) {
 675                 @SuppressWarnings("unchecked")
 676                     K k = Objects.requireNonNull((K)input[i]);
 677                 @SuppressWarnings("unchecked")
 678                     V v = Objects.requireNonNull((V)input[i+1]);
 679                 int idx = probe(k);
 680                 if (idx >= 0) {
 681                     throw new IllegalArgumentException("duplicate key: " + k);
 682                 } else {
 683                     int dest = -(idx + 1);
 684                     table[dest] = k;
 685                     table[dest+1] = v;
 686                 }
 687             }
 688         }
 689 
 690         @Override
 691         public boolean containsKey(Object o) {
 692             return probe(o) >= 0; // implicit nullcheck of o

 693         }
 694 
 695         @Override
 696         public boolean containsValue(Object o) {
 697             for (int i = 1; i < table.length; i += 2) {
 698                 Object v = table[i];
 699                 if (v != null && o.equals(v)) { // implicit nullcheck of o
 700                     return true;
 701                 }
 702             }
 703             return false;
 704         }
 705 
 706         @Override
 707         public int hashCode() {
 708             int hash = 0;
 709             for (int i = 0; i < table.length; i += 2) {
 710                 Object k = table[i];
 711                 if (k != null) {
 712                     hash += k.hashCode() ^ table[i + 1].hashCode();
 713                 }
 714             }
 715             return hash;
 716         }
 717 
 718         @Override
 719         @SuppressWarnings("unchecked")
 720         public V get(Object o) {



 721             int i = probe(o);
 722             if (i >= 0) {
 723                 return (V)table[i+1];
 724             } else {
 725                 return null;
 726             }
 727         }
 728 
 729         @Override
 730         public int size() {
 731             return size;
 732         }
 733 
 734         @Override
 735         public Set<Map.Entry<K,V>> entrySet() {
 736             return new AbstractSet<Map.Entry<K,V>>() {
 737                 @Override
 738                 public int size() {
 739                     return MapN.this.size;
 740                 }


 931      * @throws InvalidObjectException if the tag value is illegal or if an exception
 932      *         is thrown during creation of the collection
 933      * @throws ObjectStreamException if another serialization error has occurred
 934      * @since 9
 935      */
 936     private Object readResolve() throws ObjectStreamException {
 937         try {
 938             if (array == null) {
 939                 throw new InvalidObjectException("null array");
 940             }
 941 
 942             // use low order 8 bits to indicate "kind"
 943             // ignore high order 24 bits
 944             switch (tag & 0xff) {
 945                 case IMM_LIST:
 946                     return List.of(array);
 947                 case IMM_SET:
 948                     return Set.of(array);
 949                 case IMM_MAP:
 950                     if (array.length == 0) {
 951                         return ImmutableCollections.Map0.instance();
 952                     } else if (array.length == 2) {
 953                         return new ImmutableCollections.Map1<>(array[0], array[1]);
 954                     } else {
 955                         return new ImmutableCollections.MapN<>(array);
 956                     }
 957                 default:
 958                     throw new InvalidObjectException(String.format("invalid flags 0x%x", tag));
 959             }
 960         } catch (NullPointerException|IllegalArgumentException ex) {
 961             InvalidObjectException ioe = new InvalidObjectException("invalid object");
 962             ioe.initCause(ex);
 963             throw ioe;
 964         }
 965     }
 966 }


  55      */
  56     static final int SALT;
  57     static {
  58         long nt = System.nanoTime();
  59         SALT = (int)((nt >>> 32) ^ nt);
  60     }
  61 
  62     /** No instances. */
  63     private ImmutableCollections() { }
  64 
  65     /**
  66      * The reciprocal of load factor. Given a number of elements
  67      * to store, multiply by this factor to get the table size.
  68      */
  69     static final int EXPAND_FACTOR = 2;
  70 
  71     static UnsupportedOperationException uoe() { return new UnsupportedOperationException(); }
  72 
  73     // ---------- List Implementations ----------
  74 
  75     static final List<?> EMPTY_LIST = new ListN<>();
  76 
  77     @SuppressWarnings("unchecked")
  78     static <E> List<E> emptyList() {
  79         return (List<E>) EMPTY_LIST;
  80     }
  81 
  82     static abstract class AbstractImmutableList<E> extends AbstractCollection<E>
  83             implements List<E>, RandomAccess, Serializable {
  84 
  85         // all mutating methods throw UnsupportedOperationException
  86         @Override public boolean add(E e) { throw uoe(); }
  87         @Override public void    add(int index, E element) { throw uoe(); }
  88         @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
  89         @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); }
  90         @Override public void    clear() { throw uoe(); }
  91         @Override public boolean remove(Object o) { throw uoe(); }
  92         @Override public E       remove(int index) { throw uoe(); }
  93         @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
  94         @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
  95         @Override public void    replaceAll(UnaryOperator<E> operator) { throw uoe(); }
  96         @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
  97         @Override public E       set(int index, E element) { throw uoe(); }
  98         @Override public void    sort(Comparator<? super E> c) { throw uoe(); }

  99 
 100         @Override
 101         public int indexOf(Object o) {
 102             // Input should be checked for null, but this needs a CSR. See JDK-8191418
 103             if (o == null) {
 104                 return -1;
 105             }
 106             // Objects.requireNonNull(o);
 107             ListIterator<E> it = listIterator();
 108             while (it.hasNext()) {
 109                 if (o.equals(it.next())) {
 110                     return it.previousIndex();
 111                 }
 112             }
 113             return -1;
 114         }
 115 
 116         @Override
 117         public int lastIndexOf(Object o) {
 118             // Input should be checked for null, but this needs a CSR. See JDK-8191418
 119             if (o == null) {
 120                 return -1;
 121             }
 122             // Objects.requireNonNull(o);
 123 
 124             ListIterator<E> it = listIterator();
 125             while (it.hasNext()) {
 126                 if (o.equals(it.next())) {
 127                     return it.previousIndex();
 128                 }
 129             }
 130             return -1;
 131         }
 132 
 133         @Override
 134         public boolean isEmpty() {
 135             return size() == 0;
 136         }
 137 
 138         @Override
 139         public List<E> subList(int fromIndex, int toIndex) {
 140             int size = size();
 141             Objects.checkFromToIndex(fromIndex, toIndex, size);
 142             if (size == 0 || fromIndex == toIndex) {
 143                 return emptyList();
 144             } else if (size == 1) {
 145                 // checks above deal with corner cases subList(0,0) and subList(1,1)
 146                 // that would return the empty list
 147                 assert(fromIndex == 0 && toIndex == 1);
 148                 return this;
 149             } else {
 150                 return new SubList<E>(this, fromIndex, toIndex);
 151             }
 152         }
 153 
 154         private static class SubList<E> extends AbstractList<E> implements RandomAccess {
 155             private final List<E> root;
 156             private final int offset;
 157             int size;
 158 
 159             // all mutating methods throw UnsupportedOperationException
 160             @Override public boolean add(E e) { throw uoe(); }
 161             @Override public void    add(int index, E element) { throw uoe(); }
 162             @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
 163             @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); }
 164             @Override public void    clear() { throw uoe(); }
 165             @Override public boolean remove(Object o) { throw uoe(); }
 166             @Override public E       remove(int index) { throw uoe(); }
 167             @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
 168             @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
 169             @Override public void    replaceAll(UnaryOperator<E> operator) { throw uoe(); }
 170             @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
 171             @Override public E       set(int index, E element) { throw uoe(); }
 172             @Override public void    sort(Comparator<? super E> c) { throw uoe(); }
 173 
 174             /**
 175              * Constructs a sublist of an arbitrary AbstractList, which is
 176              * not a SubList itself.
 177              */
 178             public SubList(List<E> root, int fromIndex, int toIndex) {
 179                 this.root = root;
 180                 this.offset = fromIndex;
 181                 this.size = toIndex - fromIndex;
 182             }
 183 
 184             /**
 185              * Constructs a sublist of another SubList.
 186              */
 187             protected SubList(SubList<E> parent, int fromIndex, int toIndex) {
 188                 this.root = parent.root;
 189                 this.offset = parent.offset + fromIndex;
 190                 this.size = toIndex - fromIndex;
 191             }
 192 
 193             public E get(int index) {
 194                 Objects.checkIndex(index, size);
 195                 return root.get(offset + index);
 196             }
 197 
 198             public int size() {
 199                 return size;
 200             }
 201 
 202             protected void removeRange(int fromIndex, int toIndex) {
 203                 throw uoe();
 204             }
 205 

 206             public Iterator<E> iterator() {
 207                 return listIterator();
 208             }
 209 
 210             public ListIterator<E> listIterator(int index) {
 211                 rangeCheck(index);
 212 
 213                 return new ListIterator<E>() {
 214                     private final ListIterator<E> i =
 215                             root.listIterator(offset + index);
 216 
 217                     public boolean hasNext() {
 218                         return nextIndex() < size;
 219                     }
 220 
 221                     public E next() {
 222                         if (hasNext())
 223                             return i.next();
 224                         else
 225                             throw new NoSuchElementException();
 226                     }
 227 
 228                     public boolean hasPrevious() {
 229                         return previousIndex() >= 0;
 230                     }
 231 
 232                     public E previous() {
 233                         if (hasPrevious())
 234                             return i.previous();
 235                         else
 236                             throw new NoSuchElementException();
 237                     }
 238 
 239                     public int nextIndex() {
 240                         return i.nextIndex() - offset;
 241                     }
 242 
 243                     public int previousIndex() {
 244                         return i.previousIndex() - offset;
 245                     }
 246 
 247                     public void remove() { throw uoe(); }
 248                     public void set(E e) { throw uoe(); }
 249                     public void add(E e) { throw uoe(); }
 250                 };
 251             }
 252 
 253             public List<E> subList(int fromIndex, int toIndex) {
 254                 subListRangeCheck(fromIndex, toIndex, size);
 255                 return new SubList<>(this, fromIndex, toIndex);
 256             }
 257 
 258             private void rangeCheck(int index) {
 259                 if (index < 0 || index > size)
 260                     throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 261             }
 262 
 263             private String outOfBoundsMsg(int index) {
 264                 return "Index: "+index+", Size: "+size;
 265             }
 266         }
 267 
 268         @Override
 269         public Iterator<E> iterator() {
 270             return new Itr();

 271         }
 272 
 273         @Override
 274         public ListIterator<E> listIterator() {
 275             return listIterator(0);
 276         }
 277 
 278         @Override
 279         public ListIterator<E> listIterator(final int index) {
 280             Objects.checkIndex(index, size());
 281             return new ListItr(index);
 282         }
 283 
 284         private class Itr implements Iterator<E> {
 285             Itr() {
 286                 size = size();
 287             }
 288 
 289             int cursor = 0;


 290 
 291             private final int size;
 292 
 293             public boolean hasNext() {
 294                 return cursor != size;
 295             }
 296 
 297             public E next() {
 298                 try {
 299                     int i = cursor;
 300                     E next = get(i);
 301                     cursor = i + 1;
 302                     return next;
 303                 } catch (IndexOutOfBoundsException e) {
 304                     throw new NoSuchElementException();
 305                 }
 306             }
 307 
 308             public void remove() {
 309                 throw uoe();
 310             }

 311         }
 312 
 313         private class ListItr extends Itr implements ListIterator<E> {
 314             ListItr(int index) {
 315                 cursor = index;
 316             }
 317 
 318             public boolean hasPrevious() {
 319                 return cursor != 0;
 320             }
 321 
 322             public E previous() {
 323                 try {
 324                     int i = cursor - 1;
 325                     E previous = get(i);
 326                     cursor = i;
 327                     return previous;
 328                 } catch (IndexOutOfBoundsException e) {
 329                     throw new NoSuchElementException();
 330                 }
 331             }
 332 
 333             public int nextIndex() {
 334                 return cursor;
 335             }
 336 
 337             public int previousIndex() {
 338                 return cursor - 1;
 339             }
 340 
 341             public void set(E e) {
 342                 throw uoe();
 343             }
 344 
 345             public void add(E e) {
 346                 throw uoe();
 347             }
 348         }
 349 
 350 
 351         @Override
 352         public boolean equals(Object o) {
 353             if (o == this) {
 354                 return true;
 355             }
 356 
 357             if (!(o instanceof List)) {
 358                 return false;
 359             }
 360 
 361             Iterator<E> e1 = iterator();
 362             Iterator<?> e2 = ((List<?>) o).iterator();
 363             while (e1.hasNext() && e2.hasNext()) {
 364                 E o1 = e1.next();
 365                 Object o2 = e2.next();
 366                 if (!(o1==null ? o2==null : o1.equals(o2)))
 367                     return false;
 368             }
 369             return !(e1.hasNext() || e2.hasNext());
 370         }
 371 
 372         IndexOutOfBoundsException outOfBounds(int index) {
 373             return new IndexOutOfBoundsException("Index: " + index + " Size: " + size());
 374         }
 375 
 376     }
 377 
 378     static final class List12<E> extends AbstractImmutableList<E> {
 379 
 380         @Stable
 381         private final E e0;
 382 
 383         @Stable
 384         private final E e1;
 385 
 386         List12(E e0) {
 387             this.e0 = Objects.requireNonNull(e0);
 388             this.e1 = null;
 389         }
 390 
 391         List12(E e0, E e1) {
 392             this.e0 = Objects.requireNonNull(e0);
 393             this.e1 = Objects.requireNonNull(e1);
 394         }
 395 
 396         @Override
 397         @SuppressWarnings("unchecked")
 398         public int size() {
 399             return e1 != null ? 2 : 1;
 400         }
 401 
 402         @Override
 403         @SuppressWarnings("unchecked")
 404         public E get(int index) {

 405             if (index == 0) {
 406                 return e0;
 407             } else if (index == 1 && e1 != null) {
 408                 return e1;
 409             }
 410             throw outOfBounds(index);
 411         }
 412 
 413         @Override
 414         @SuppressWarnings("unchecked")
 415         public boolean contains(Object o) {
 416             return o.equals(e0) || o.equals(e1); // implicit null check of o
 417         }
 418 
 419         @Override
 420         @SuppressWarnings("unchecked")
 421         public int hashCode() {
 422             int hash = 31 + e0.hashCode();
 423             if (e1 != null) {
 424                 hash = 31 * hash + e1.hashCode();
 425             }
 426             return hash;
 427         }
 428 
 429         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 430             throw new InvalidObjectException("not serial proxy");
 431         }
 432 
 433         @SuppressWarnings("unchecked")
 434         private Object writeReplace() {
 435             if (e1 == null) {
 436                 return new CollSer(CollSer.IMM_LIST, e0);
 437             } else {
 438                 return new CollSer(CollSer.IMM_LIST, e0, e1);
 439             }
 440         }
 441     }
 442 
 443     static final class ListN<E> extends AbstractImmutableList<E> {
 444 
 445         @Stable
 446         private final E[] elements;
 447 
 448         @SuppressWarnings("unchecked")
 449         ListN(E e0) {
 450             elements = (E[])new Object[] { e0 };
 451         }
 452 
 453         @SuppressWarnings("unchecked")
 454         ListN(E e0, E e1) {
 455             elements = (E[])new Object[] { e0, e1 };
 456         }
 457 
 458         @SafeVarargs
 459         ListN(E... input) {
 460             // copy and check manually to avoid TOCTOU
 461             @SuppressWarnings("unchecked")
 462             E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input
 463             for (int i = 0; i < input.length; i++) {
 464                 tmp[i] = Objects.requireNonNull(input[i]);
 465             }
 466             elements = tmp;
 467         }
 468 
 469         @Override
 470         public boolean isEmpty() {
 471             return size() == 0;
 472         }
 473 
 474         @Override
 475         @SuppressWarnings("unchecked")
 476         public int size() {
 477             return elements.length;
 478         }
 479 
 480         @Override
 481         @SuppressWarnings("unchecked")
 482         public E get(int index) {

 483             return elements[index];
 484         }
 485 
 486         @Override
 487         @SuppressWarnings("unchecked")
 488         public boolean contains(Object o) {
 489             Objects.requireNonNull(o);
 490             for (E e : elements) {
 491                 if (o.equals(e)) {
 492                     return true;
 493                 }
 494             }
 495             return false;
 496         }
 497 
 498         @Override
 499         @SuppressWarnings("unchecked")
 500         public int hashCode() {
 501             int hash = 1;
 502             for (E e : elements) {
 503                 hash = 31 * hash + e.hashCode();
 504             }
 505             return hash;
 506         }
 507 
 508         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 509             throw new InvalidObjectException("not serial proxy");
 510         }
 511 
 512         @SuppressWarnings("unchecked")
 513         private Object writeReplace() {
 514             return new CollSer(CollSer.IMM_LIST, elements);
 515         }
 516     }
 517 
 518     // ---------- Set Implementations ----------
 519 
 520     static final Set<?> EMPTY_SET = new SetN<>();
 521 
 522     @SuppressWarnings("unchecked")
 523     static <E> Set<E> emptySet() {
 524         return (Set<E>) EMPTY_SET;
 525     }
 526 
 527     abstract static class AbstractImmutableSet<E> extends AbstractSet<E> implements Serializable {
 528         @Override public boolean add(E e) { throw uoe(); }
 529         @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
 530         @Override public void    clear() { throw uoe(); }
 531         @Override public boolean remove(Object o) { throw uoe(); }
 532         @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
 533         @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
 534         @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
 535     }
 536 
 537     static final class Set12<E> extends AbstractImmutableSet<E> {


















































































 538         @Stable
 539         final E e0;
 540         @Stable
 541         final E e1;
 542 
 543         Set12(E e0) {
 544             this.e0 = Objects.requireNonNull(e0);
 545             this.e1 = null;
 546         }
 547 
 548         Set12(E e0, E e1) {
 549             if (e0.equals(Objects.requireNonNull(e1))) { // implicit nullcheck of e0
 550                 throw new IllegalArgumentException("duplicate element: " + e0);
 551             }
 552 
 553             if (SALT >= 0) {
 554                 this.e0 = e0;
 555                 this.e1 = e1;
 556             } else {
 557                 this.e0 = e1;
 558                 this.e1 = e0;
 559             }
 560         }
 561 
 562         @Override
 563         public int size() {
 564             return (e1 == null) ? 1 : 2;
 565         }
 566 
 567         @Override
 568         public boolean contains(Object o) {
 569             return o.equals(e0) || o.equals(e1); // implicit nullcheck of o
 570         }
 571 
 572         @Override
 573         public int hashCode() {
 574             return e0.hashCode() + (e1 == null ? 0 : e1.hashCode());
 575         }
 576 
 577         @Override
 578         public Iterator<E> iterator() {
 579             return new Iterator<E>() {
 580                 private int idx = size();
 581 
 582                 @Override
 583                 public boolean hasNext() {
 584                     return idx > 0;
 585                 }
 586 
 587                 @Override
 588                 public E next() {
 589                     if (idx == 1) {
 590                         idx = 0;
 591                         return e0;
 592                     } else if (idx == 2) {
 593                         idx = 1;
 594                         return e1;
 595                     } else {
 596                         throw new NoSuchElementException();
 597                     }
 598                 }
 599             };
 600         }
 601 
 602         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 603             throw new InvalidObjectException("not serial proxy");
 604         }
 605 
 606         private Object writeReplace() {
 607             if (e1 == null) {
 608                 return new CollSer(CollSer.IMM_SET, e0);
 609             } else {
 610                 return new CollSer(CollSer.IMM_SET, e0, e1);
 611             }
 612         }
 613     }
 614 
 615     /**
 616      * An array-based Set implementation. The element array must be strictly
 617      * larger than the size (the number of contained elements) so that at
 618      * least one null is always present.
 619      * @param <E> the element type
 620      */
 621     static final class SetN<E> extends AbstractImmutableSet<E> {
 622         @Stable
 623         final E[] elements;
 624         @Stable
 625         final int size;
 626 
 627         @SafeVarargs
 628         @SuppressWarnings("unchecked")
 629         SetN(E... input) {
 630             size = input.length; // implicit nullcheck of input
 631 
 632             elements = (E[])new Object[EXPAND_FACTOR * input.length];
 633             for (int i = 0; i < input.length; i++) {
 634                 E e = input[i];
 635                 int idx = probe(e); // implicit nullcheck of e
 636                 if (idx >= 0) {
 637                     throw new IllegalArgumentException("duplicate element: " + e);
 638                 } else {
 639                     elements[-(idx + 1)] = e;
 640                 }
 641             }
 642         }
 643 
 644         @Override
 645         public int size() {
 646             return size;
 647         }
 648 
 649         @Override
 650         public boolean contains(Object o) {
 651             Objects.requireNonNull(0);
 652             return size > 0 && probe(o) >= 0; // implicit nullcheck of o
 653         }
 654 
 655         @Override
 656         public Iterator<E> iterator() {
 657             return new Iterator<E>() {
 658                 private int idx = 0;
 659 
 660                 @Override
 661                 public boolean hasNext() {
 662                     while (idx < elements.length) {
 663                         if (elements[idx] != null)
 664                             return true;
 665                         idx++;
 666                     }
 667                     return false;
 668                 }
 669 
 670                 @Override
 671                 public E next() {
 672                     if (! hasNext()) {


 707         }
 708 
 709         private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 710             throw new InvalidObjectException("not serial proxy");
 711         }
 712 
 713         private Object writeReplace() {
 714             Object[] array = new Object[size];
 715             int dest = 0;
 716             for (Object o : elements) {
 717                 if (o != null) {
 718                     array[dest++] = o;
 719                 }
 720             }
 721             return new CollSer(CollSer.IMM_SET, array);
 722         }
 723     }
 724 
 725     // ---------- Map Implementations ----------
 726 
 727     static final Map<?,?> EMPTY_MAP = new MapN<>();
 728 
 729     @SuppressWarnings("unchecked")
 730     static <K,V> Map<K,V> emptyMap() {
 731         return (Map<K,V>) EMPTY_MAP;
 732     }
 733 
 734     abstract static class AbstractImmutableMap<K,V> extends AbstractMap<K,V> implements Serializable {
 735         @Override public void clear() { throw uoe(); }
 736         @Override public V compute(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
 737         @Override public V computeIfAbsent(K key, Function<? super K,? extends V> mf) { throw uoe(); }
 738         @Override public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
 739         @Override public V merge(K key, V value, BiFunction<? super V,? super V,? extends V> rf) { throw uoe(); }
 740         @Override public V put(K key, V value) { throw uoe(); }
 741         @Override public void putAll(Map<? extends K,? extends V> m) { throw uoe(); }
 742         @Override public V putIfAbsent(K key, V value) { throw uoe(); }
 743         @Override public V remove(Object key) { throw uoe(); }
 744         @Override public boolean remove(Object key, Object value) { throw uoe(); }
 745         @Override public V replace(K key, V value) { throw uoe(); }
 746         @Override public boolean replace(K key, V oldValue, V newValue) { throw uoe(); }
 747         @Override public void replaceAll(BiFunction<? super K,? super V,? extends V> f) { throw uoe(); }
 748     }
 749 









































 750     static final class Map1<K,V> extends AbstractImmutableMap<K,V> {
 751         @Stable
 752         private final K k0;
 753         @Stable
 754         private final V v0;
 755 
 756         Map1(K k0, V v0) {
 757             this.k0 = Objects.requireNonNull(k0);
 758             this.v0 = Objects.requireNonNull(v0);
 759         }
 760 
 761         @Override
 762         public Set<Map.Entry<K,V>> entrySet() {
 763             return Set.of(new KeyValueHolder<>(k0, v0));
 764         }
 765 
 766         @Override
 767         public boolean containsKey(Object o) {
 768             return o.equals(k0); // implicit nullcheck of o
 769         }


 782         }
 783 
 784         @Override
 785         public int hashCode() {
 786             return k0.hashCode() ^ v0.hashCode();
 787         }
 788     }
 789 
 790     /**
 791      * An array-based Map implementation. There is a single array "table" that
 792      * contains keys and values interleaved: table[0] is kA, table[1] is vA,
 793      * table[2] is kB, table[3] is vB, etc. The table size must be even. It must
 794      * also be strictly larger than the size (the number of key-value pairs contained
 795      * in the map) so that at least one null key is always present.
 796      * @param <K> the key type
 797      * @param <V> the value type
 798      */
 799     static final class MapN<K,V> extends AbstractImmutableMap<K,V> {
 800         @Stable
 801         final Object[] table; // pairs of key, value

 802         final int size; // number of pairs
 803 
 804         MapN(K key, V value) {
 805             table = new Object[2];
 806             table[0] = key;
 807             table[1] = value;
 808             size = 1;
 809         }
 810 
 811         MapN(Object... input) {
 812             if ((input.length & 1) != 0) { // implicit nullcheck of input
 813                 throw new InternalError("length is odd");
 814             }
 815             size = input.length >> 1;
 816 
 817             int len = EXPAND_FACTOR * input.length;
 818             len = (len + 1) & ~1; // ensure table is even length
 819             table = new Object[len];
 820 
 821             for (int i = 0; i < input.length; i += 2) {
 822                 @SuppressWarnings("unchecked")
 823                     K k = Objects.requireNonNull((K)input[i]);
 824                 @SuppressWarnings("unchecked")
 825                     V v = Objects.requireNonNull((V)input[i+1]);
 826                 int idx = probe(k);
 827                 if (idx >= 0) {
 828                     throw new IllegalArgumentException("duplicate key: " + k);
 829                 } else {
 830                     int dest = -(idx + 1);
 831                     table[dest] = k;
 832                     table[dest+1] = v;
 833                 }
 834             }
 835         }
 836 
 837         @Override
 838         public boolean containsKey(Object o) {
 839             Objects.requireNonNull(0);
 840             return size > 0 && probe(o) >= 0;
 841         }
 842 
 843         @Override
 844         public boolean containsValue(Object o) {
 845             for (int i = 1; i < table.length; i += 2) {
 846                 Object v = table[i];
 847                 if (v != null && o.equals(v)) { // implicit nullcheck of o
 848                     return true;
 849                 }
 850             }
 851             return false;
 852         }
 853 
 854         @Override
 855         public int hashCode() {
 856             int hash = 0;
 857             for (int i = 0; i < table.length; i += 2) {
 858                 Object k = table[i];
 859                 if (k != null) {
 860                     hash += k.hashCode() ^ table[i + 1].hashCode();
 861                 }
 862             }
 863             return hash;
 864         }
 865 
 866         @Override
 867         @SuppressWarnings("unchecked")
 868         public V get(Object o) {
 869             if (size == 0) {
 870                 return null;
 871             }
 872             int i = probe(o);
 873             if (i >= 0) {
 874                 return (V)table[i+1];
 875             } else {
 876                 return null;
 877             }
 878         }
 879 
 880         @Override
 881         public int size() {
 882             return size;
 883         }
 884 
 885         @Override
 886         public Set<Map.Entry<K,V>> entrySet() {
 887             return new AbstractSet<Map.Entry<K,V>>() {
 888                 @Override
 889                 public int size() {
 890                     return MapN.this.size;
 891                 }


1082      * @throws InvalidObjectException if the tag value is illegal or if an exception
1083      *         is thrown during creation of the collection
1084      * @throws ObjectStreamException if another serialization error has occurred
1085      * @since 9
1086      */
1087     private Object readResolve() throws ObjectStreamException {
1088         try {
1089             if (array == null) {
1090                 throw new InvalidObjectException("null array");
1091             }
1092 
1093             // use low order 8 bits to indicate "kind"
1094             // ignore high order 24 bits
1095             switch (tag & 0xff) {
1096                 case IMM_LIST:
1097                     return List.of(array);
1098                 case IMM_SET:
1099                     return Set.of(array);
1100                 case IMM_MAP:
1101                     if (array.length == 0) {
1102                         return ImmutableCollections.emptyMap();
1103                     } else if (array.length == 2) {
1104                         return new ImmutableCollections.Map1<>(array[0], array[1]);
1105                     } else {
1106                         return new ImmutableCollections.MapN<>(array);
1107                     }
1108                 default:
1109                     throw new InvalidObjectException(String.format("invalid flags 0x%x", tag));
1110             }
1111         } catch (NullPointerException|IllegalArgumentException ex) {
1112             InvalidObjectException ioe = new InvalidObjectException("invalid object");
1113             ioe.initCause(ex);
1114             throw ioe;
1115         }
1116     }
1117 }
< prev index next >