1 /* 2 * Copyright (c) 2016, 2017, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.util; 27 28 import java.io.IOException; 29 import java.io.InvalidObjectException; 30 import java.io.ObjectInputStream; 31 import java.io.ObjectOutputStream; 32 import java.io.ObjectStreamException; 33 import java.io.Serializable; 34 import java.util.function.BiFunction; 35 import java.util.function.Function; 36 import java.util.function.Predicate; 37 import java.util.function.UnaryOperator; 38 import jdk.internal.vm.annotation.Stable; 39 40 /** 41 * Container class for immutable collections. Not part of the public API. 42 * Mainly for namespace management and shared infrastructure. 43 * 44 * Serial warnings are suppressed throughout because all implementation 45 * classes use a serial proxy and thus have no need to declare serialVersionUID. 46 */ 47 @SuppressWarnings("serial") 48 class ImmutableCollections { 49 /** 50 * A "salt" value used for randomizing iteration order. This is initialized once 51 * and stays constant for the lifetime of the JVM. It need not be truly random, but 52 * it needs to vary sufficiently from one run to the next so that iteration order 53 * will vary between JVM runs. 54 */ 55 static final int SALT; 56 static { 57 long nt = System.nanoTime(); 58 SALT = (int)((nt >>> 32) ^ nt); 59 } 60 61 /** No instances. */ ImmutableCollections()62 private ImmutableCollections() { } 63 64 /** 65 * The reciprocal of load factor. Given a number of elements 66 * to store, multiply by this factor to get the table size. 67 */ 68 static final int EXPAND_FACTOR = 2; 69 uoe()70 static UnsupportedOperationException uoe() { return new UnsupportedOperationException(); } 71 72 // ---------- List Implementations ---------- 73 74 abstract static class AbstractImmutableList<E> extends AbstractList<E> 75 implements RandomAccess, Serializable { add(E e)76 @Override public boolean add(E e) { throw uoe(); } addAll(Collection<? extends E> c)77 @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); } addAll(int index, Collection<? extends E> c)78 @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); } clear()79 @Override public void clear() { throw uoe(); } remove(Object o)80 @Override public boolean remove(Object o) { throw uoe(); } removeAll(Collection<?> c)81 @Override public boolean removeAll(Collection<?> c) { throw uoe(); } removeIf(Predicate<? super E> filter)82 @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); } replaceAll(UnaryOperator<E> operator)83 @Override public void replaceAll(UnaryOperator<E> operator) { throw uoe(); } retainAll(Collection<?> c)84 @Override public boolean retainAll(Collection<?> c) { throw uoe(); } sort(Comparator<? super E> c)85 @Override public void sort(Comparator<? super E> c) { throw uoe(); } 86 } 87 88 static final class List0<E> extends AbstractImmutableList<E> { 89 private static final List0<?> INSTANCE = new List0<>(); 90 91 @SuppressWarnings("unchecked") instance()92 static <T> List0<T> instance() { 93 return (List0<T>) INSTANCE; 94 } 95 List0()96 private List0() { } 97 98 @Override size()99 public int size() { 100 return 0; 101 } 102 103 @Override get(int index)104 public E get(int index) { 105 Objects.checkIndex(index, 0); // always throws IndexOutOfBoundsException 106 return null; // but the compiler doesn't know this 107 } 108 109 @Override iterator()110 public Iterator<E> iterator() { 111 return Collections.emptyIterator(); 112 } 113 readObject(ObjectInputStream in)114 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 115 throw new InvalidObjectException("not serial proxy"); 116 } 117 writeReplace()118 private Object writeReplace() { 119 return new CollSer(CollSer.IMM_LIST); 120 } 121 122 @Override contains(Object o)123 public boolean contains(Object o) { 124 Objects.requireNonNull(o); 125 return false; 126 } 127 128 @Override containsAll(Collection<?> o)129 public boolean containsAll(Collection<?> o) { 130 return o.isEmpty(); // implicit nullcheck of o 131 } 132 133 @Override hashCode()134 public int hashCode() { 135 return 1; 136 } 137 } 138 139 static final class List1<E> extends AbstractImmutableList<E> { 140 @Stable 141 private final E e0; 142 List1(E e0)143 List1(E e0) { 144 this.e0 = Objects.requireNonNull(e0); 145 } 146 147 @Override size()148 public int size() { 149 return 1; 150 } 151 152 @Override get(int index)153 public E get(int index) { 154 Objects.checkIndex(index, 1); 155 return e0; 156 } 157 readObject(ObjectInputStream in)158 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 159 throw new InvalidObjectException("not serial proxy"); 160 } 161 writeReplace()162 private Object writeReplace() { 163 return new CollSer(CollSer.IMM_LIST, e0); 164 } 165 166 @Override contains(Object o)167 public boolean contains(Object o) { 168 return o.equals(e0); // implicit nullcheck of o 169 } 170 171 @Override hashCode()172 public int hashCode() { 173 return 31 + e0.hashCode(); 174 } 175 } 176 177 static final class List2<E> extends AbstractImmutableList<E> { 178 @Stable 179 private final E e0; 180 @Stable 181 private final E e1; 182 List2(E e0, E e1)183 List2(E e0, E e1) { 184 this.e0 = Objects.requireNonNull(e0); 185 this.e1 = Objects.requireNonNull(e1); 186 } 187 188 @Override size()189 public int size() { 190 return 2; 191 } 192 193 @Override get(int index)194 public E get(int index) { 195 Objects.checkIndex(index, 2); 196 if (index == 0) { 197 return e0; 198 } else { // index == 1 199 return e1; 200 } 201 } 202 203 @Override contains(Object o)204 public boolean contains(Object o) { 205 return o.equals(e0) || o.equals(e1); // implicit nullcheck of o 206 } 207 208 @Override hashCode()209 public int hashCode() { 210 int hash = 31 + e0.hashCode(); 211 return 31 * hash + e1.hashCode(); 212 } 213 readObject(ObjectInputStream in)214 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 215 throw new InvalidObjectException("not serial proxy"); 216 } 217 writeReplace()218 private Object writeReplace() { 219 return new CollSer(CollSer.IMM_LIST, e0, e1); 220 } 221 } 222 223 static final class ListN<E> extends AbstractImmutableList<E> { 224 @Stable 225 private final E[] elements; 226 227 @SafeVarargs ListN(E... input)228 ListN(E... input) { 229 // copy and check manually to avoid TOCTOU 230 @SuppressWarnings("unchecked") 231 E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input 232 for (int i = 0; i < input.length; i++) { 233 tmp[i] = Objects.requireNonNull(input[i]); 234 } 235 this.elements = tmp; 236 } 237 238 @Override size()239 public int size() { 240 return elements.length; 241 } 242 243 @Override get(int index)244 public E get(int index) { 245 Objects.checkIndex(index, elements.length); 246 return elements[index]; 247 } 248 249 @Override contains(Object o)250 public boolean contains(Object o) { 251 for (E e : elements) { 252 if (o.equals(e)) { // implicit nullcheck of o 253 return true; 254 } 255 } 256 return false; 257 } 258 259 @Override hashCode()260 public int hashCode() { 261 int hash = 1; 262 for (E e : elements) { 263 hash = 31 * hash + e.hashCode(); 264 } 265 return hash; 266 } 267 readObject(ObjectInputStream in)268 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 269 throw new InvalidObjectException("not serial proxy"); 270 } 271 writeReplace()272 private Object writeReplace() { 273 return new CollSer(CollSer.IMM_LIST, elements); 274 } 275 } 276 277 // ---------- Set Implementations ---------- 278 279 abstract static class AbstractImmutableSet<E> extends AbstractSet<E> implements Serializable { add(E e)280 @Override public boolean add(E e) { throw uoe(); } addAll(Collection<? extends E> c)281 @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); } clear()282 @Override public void clear() { throw uoe(); } remove(Object o)283 @Override public boolean remove(Object o) { throw uoe(); } removeAll(Collection<?> c)284 @Override public boolean removeAll(Collection<?> c) { throw uoe(); } removeIf(Predicate<? super E> filter)285 @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); } retainAll(Collection<?> c)286 @Override public boolean retainAll(Collection<?> c) { throw uoe(); } 287 } 288 289 static final class Set0<E> extends AbstractImmutableSet<E> { 290 private static final Set0<?> INSTANCE = new Set0<>(); 291 292 @SuppressWarnings("unchecked") instance()293 static <T> Set0<T> instance() { 294 return (Set0<T>) INSTANCE; 295 } 296 Set0()297 private Set0() { } 298 299 @Override size()300 public int size() { 301 return 0; 302 } 303 304 @Override contains(Object o)305 public boolean contains(Object o) { 306 Objects.requireNonNull(o); 307 return false; 308 } 309 310 @Override containsAll(Collection<?> o)311 public boolean containsAll(Collection<?> o) { 312 return o.isEmpty(); // implicit nullcheck of o 313 } 314 315 @Override iterator()316 public Iterator<E> iterator() { 317 return Collections.emptyIterator(); 318 } 319 readObject(ObjectInputStream in)320 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 321 throw new InvalidObjectException("not serial proxy"); 322 } 323 writeReplace()324 private Object writeReplace() { 325 return new CollSer(CollSer.IMM_SET); 326 } 327 328 @Override hashCode()329 public int hashCode() { 330 return 0; 331 } 332 } 333 334 static final class Set1<E> extends AbstractImmutableSet<E> { 335 @Stable 336 private final E e0; 337 Set1(E e0)338 Set1(E e0) { 339 this.e0 = Objects.requireNonNull(e0); 340 } 341 342 @Override size()343 public int size() { 344 return 1; 345 } 346 347 @Override contains(Object o)348 public boolean contains(Object o) { 349 return o.equals(e0); // implicit nullcheck of o 350 } 351 352 @Override iterator()353 public Iterator<E> iterator() { 354 return Collections.singletonIterator(e0); 355 } 356 readObject(ObjectInputStream in)357 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 358 throw new InvalidObjectException("not serial proxy"); 359 } 360 writeReplace()361 private Object writeReplace() { 362 return new CollSer(CollSer.IMM_SET, e0); 363 } 364 365 @Override hashCode()366 public int hashCode() { 367 return e0.hashCode(); 368 } 369 } 370 371 static final class Set2<E> extends AbstractImmutableSet<E> { 372 @Stable 373 final E e0; 374 @Stable 375 final E e1; 376 Set2(E e0, E e1)377 Set2(E e0, E e1) { 378 if (e0.equals(Objects.requireNonNull(e1))) { // implicit nullcheck of e0 379 throw new IllegalArgumentException("duplicate element: " + e0); 380 } 381 382 if (SALT >= 0) { 383 this.e0 = e0; 384 this.e1 = e1; 385 } else { 386 this.e0 = e1; 387 this.e1 = e0; 388 } 389 } 390 391 @Override size()392 public int size() { 393 return 2; 394 } 395 396 @Override contains(Object o)397 public boolean contains(Object o) { 398 return o.equals(e0) || o.equals(e1); // implicit nullcheck of o 399 } 400 401 @Override hashCode()402 public int hashCode() { 403 return e0.hashCode() + e1.hashCode(); 404 } 405 406 @Override iterator()407 public Iterator<E> iterator() { 408 return new Iterator<E>() { 409 private int idx = 0; 410 411 @Override 412 public boolean hasNext() { 413 return idx < 2; 414 } 415 416 @Override 417 public E next() { 418 if (idx == 0) { 419 idx = 1; 420 return e0; 421 } else if (idx == 1) { 422 idx = 2; 423 return e1; 424 } else { 425 throw new NoSuchElementException(); 426 } 427 } 428 }; 429 } 430 readObject(ObjectInputStream in)431 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 432 throw new InvalidObjectException("not serial proxy"); 433 } 434 writeReplace()435 private Object writeReplace() { 436 return new CollSer(CollSer.IMM_SET, e0, e1); 437 } 438 } 439 440 /** 441 * An array-based Set implementation. The element array must be strictly 442 * larger than the size (the number of contained elements) so that at 443 * least one null is always present. 444 * @param <E> the element type 445 */ 446 static final class SetN<E> extends AbstractImmutableSet<E> { 447 @Stable 448 final E[] elements; 449 @Stable 450 final int size; 451 452 @SafeVarargs 453 @SuppressWarnings("unchecked") SetN(E... input)454 SetN(E... input) { 455 size = input.length; // implicit nullcheck of input 456 457 elements = (E[])new Object[EXPAND_FACTOR * input.length]; 458 for (int i = 0; i < input.length; i++) { 459 E e = input[i]; 460 int idx = probe(e); // implicit nullcheck of e 461 if (idx >= 0) { 462 throw new IllegalArgumentException("duplicate element: " + e); 463 } else { 464 elements[-(idx + 1)] = e; 465 } 466 } 467 } 468 469 @Override size()470 public int size() { 471 return size; 472 } 473 474 @Override contains(Object o)475 public boolean contains(Object o) { 476 return probe(o) >= 0; // implicit nullcheck of o 477 } 478 479 @Override iterator()480 public Iterator<E> iterator() { 481 return new Iterator<E>() { 482 private int idx = 0; 483 484 @Override 485 public boolean hasNext() { 486 while (idx < elements.length) { 487 if (elements[idx] != null) 488 return true; 489 idx++; 490 } 491 return false; 492 } 493 494 @Override 495 public E next() { 496 if (! hasNext()) { 497 throw new NoSuchElementException(); 498 } 499 return elements[idx++]; 500 } 501 }; 502 } 503 504 @Override hashCode()505 public int hashCode() { 506 int h = 0; 507 for (E e : elements) { 508 if (e != null) { 509 h += e.hashCode(); 510 } 511 } 512 return h; 513 } 514 515 // returns index at which element is present; or if absent, 516 // (-i - 1) where i is location where element should be inserted. 517 // Callers are relying on this method to perform an implicit nullcheck 518 // of pe probe(Object pe)519 private int probe(Object pe) { 520 int idx = Math.floorMod(pe.hashCode() ^ SALT, elements.length); 521 while (true) { 522 E ee = elements[idx]; 523 if (ee == null) { 524 return -idx - 1; 525 } else if (pe.equals(ee)) { 526 return idx; 527 } else if (++idx == elements.length) { 528 idx = 0; 529 } 530 } 531 } 532 readObject(ObjectInputStream in)533 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 534 throw new InvalidObjectException("not serial proxy"); 535 } 536 writeReplace()537 private Object writeReplace() { 538 Object[] array = new Object[size]; 539 int dest = 0; 540 for (Object o : elements) { 541 if (o != null) { 542 array[dest++] = o; 543 } 544 } 545 return new CollSer(CollSer.IMM_SET, array); 546 } 547 } 548 549 // ---------- Map Implementations ---------- 550 551 abstract static class AbstractImmutableMap<K,V> extends AbstractMap<K,V> implements Serializable { 552 @Override public void clear() { throw uoe(); } 553 @Override public V compute(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); } 554 @Override public V computeIfAbsent(K key, Function<? super K,? extends V> mf) { throw uoe(); } 555 @Override public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); } 556 @Override public V merge(K key, V value, BiFunction<? super V,? super V,? extends V> rf) { throw uoe(); } 557 @Override public V put(K key, V value) { throw uoe(); } 558 @Override public void putAll(Map<? extends K,? extends V> m) { throw uoe(); } 559 @Override public V putIfAbsent(K key, V value) { throw uoe(); } 560 @Override public V remove(Object key) { throw uoe(); } 561 @Override public boolean remove(Object key, Object value) { throw uoe(); } 562 @Override public V replace(K key, V value) { throw uoe(); } 563 @Override public boolean replace(K key, V oldValue, V newValue) { throw uoe(); } 564 @Override public void replaceAll(BiFunction<? super K,? super V,? extends V> f) { throw uoe(); } 565 } 566 567 static final class Map0<K,V> extends AbstractImmutableMap<K,V> { 568 private static final Map0<?,?> INSTANCE = new Map0<>(); 569 570 @SuppressWarnings("unchecked") 571 static <K,V> Map0<K,V> instance() { 572 return (Map0<K,V>) INSTANCE; 573 } 574 575 private Map0() { } 576 577 @Override 578 public Set<Map.Entry<K,V>> entrySet() { 579 return Set.of(); 580 } 581 582 @Override 583 public boolean containsKey(Object o) { 584 Objects.requireNonNull(o); 585 return false; 586 } 587 588 @Override 589 public boolean containsValue(Object o) { 590 Objects.requireNonNull(o); 591 return false; 592 } 593 594 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 595 throw new InvalidObjectException("not serial proxy"); 596 } 597 598 private Object writeReplace() { 599 return new CollSer(CollSer.IMM_MAP); 600 } 601 602 @Override 603 public int hashCode() { 604 return 0; 605 } 606 } 607 608 static final class Map1<K,V> extends AbstractImmutableMap<K,V> { 609 @Stable 610 private final K k0; 611 @Stable 612 private final V v0; 613 614 Map1(K k0, V v0) { 615 this.k0 = Objects.requireNonNull(k0); 616 this.v0 = Objects.requireNonNull(v0); 617 } 618 619 @Override 620 public Set<Map.Entry<K,V>> entrySet() { 621 return Set.of(new KeyValueHolder<>(k0, v0)); 622 } 623 624 @Override 625 public boolean containsKey(Object o) { 626 return o.equals(k0); // implicit nullcheck of o 627 } 628 629 @Override 630 public boolean containsValue(Object o) { 631 return o.equals(v0); // implicit nullcheck of o 632 } 633 634 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 635 throw new InvalidObjectException("not serial proxy"); 636 } 637 638 private Object writeReplace() { 639 return new CollSer(CollSer.IMM_MAP, k0, v0); 640 } 641 642 @Override 643 public int hashCode() { 644 return k0.hashCode() ^ v0.hashCode(); 645 } 646 } 647 648 /** 649 * An array-based Map implementation. There is a single array "table" that 650 * contains keys and values interleaved: table[0] is kA, table[1] is vA, 651 * table[2] is kB, table[3] is vB, etc. The table size must be even. It must 652 * also be strictly larger than the size (the number of key-value pairs contained 653 * in the map) so that at least one null key is always present. 654 * @param <K> the key type 655 * @param <V> the value type 656 */ 657 static final class MapN<K,V> extends AbstractImmutableMap<K,V> { 658 @Stable 659 final Object[] table; // pairs of key, value 660 @Stable 661 final int size; // number of pairs 662 663 MapN(Object... input) { 664 if ((input.length & 1) != 0) { // implicit nullcheck of input 665 throw new InternalError("length is odd"); 666 } 667 size = input.length >> 1; 668 669 int len = EXPAND_FACTOR * input.length; 670 len = (len + 1) & ~1; // ensure table is even length 671 table = new Object[len]; 672 673 for (int i = 0; i < input.length; i += 2) { 674 @SuppressWarnings("unchecked") 675 K k = Objects.requireNonNull((K)input[i]); 676 @SuppressWarnings("unchecked") 677 V v = Objects.requireNonNull((V)input[i+1]); 678 int idx = probe(k); 679 if (idx >= 0) { 680 throw new IllegalArgumentException("duplicate key: " + k); 681 } else { 682 int dest = -(idx + 1); 683 table[dest] = k; 684 table[dest+1] = v; 685 } 686 } 687 } 688 689 @Override 690 public boolean containsKey(Object o) { 691 return probe(o) >= 0; // implicit nullcheck of o 692 } 693 694 @Override 695 public boolean containsValue(Object o) { 696 for (int i = 1; i < table.length; i += 2) { 697 Object v = table[i]; 698 if (v != null && o.equals(v)) { // implicit nullcheck of o 699 return true; 700 } 701 } 702 return false; 703 } 704 705 @Override 706 public int hashCode() { 707 int hash = 0; 708 for (int i = 0; i < table.length; i += 2) { 709 Object k = table[i]; 710 if (k != null) { 711 hash += k.hashCode() ^ table[i + 1].hashCode(); 712 } 713 } 714 return hash; 715 } 716 717 @Override 718 @SuppressWarnings("unchecked") 719 public V get(Object o) { 720 int i = probe(o); 721 if (i >= 0) { 722 return (V)table[i+1]; 723 } else { 724 return null; 725 } 726 } 727 728 @Override 729 public int size() { 730 return size; 731 } 732 733 @Override 734 public Set<Map.Entry<K,V>> entrySet() { 735 return new AbstractSet<Map.Entry<K,V>>() { 736 @Override 737 public int size() { 738 return MapN.this.size; 739 } 740 741 @Override 742 public Iterator<Map.Entry<K,V>> iterator() { 743 return new Iterator<Map.Entry<K,V>>() { 744 int idx = 0; 745 746 @Override 747 public boolean hasNext() { 748 while (idx < table.length) { 749 if (table[idx] != null) 750 return true; 751 idx += 2; 752 } 753 return false; 754 } 755 756 @Override 757 public Map.Entry<K,V> next() { 758 if (hasNext()) { 759 @SuppressWarnings("unchecked") 760 Map.Entry<K,V> e = 761 new KeyValueHolder<>((K)table[idx], (V)table[idx+1]); 762 idx += 2; 763 return e; 764 } else { 765 throw new NoSuchElementException(); 766 } 767 } 768 }; 769 } 770 }; 771 } 772 773 // returns index at which the probe key is present; or if absent, 774 // (-i - 1) where i is location where element should be inserted. 775 // Callers are relying on this method to perform an implicit nullcheck 776 // of pk. 777 private int probe(Object pk) { 778 int idx = Math.floorMod(pk.hashCode() ^ SALT, table.length >> 1) << 1; 779 while (true) { 780 @SuppressWarnings("unchecked") 781 K ek = (K)table[idx]; 782 if (ek == null) { 783 return -idx - 1; 784 } else if (pk.equals(ek)) { 785 return idx; 786 } else if ((idx += 2) == table.length) { 787 idx = 0; 788 } 789 } 790 } 791 792 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 793 throw new InvalidObjectException("not serial proxy"); 794 } 795 796 private Object writeReplace() { 797 Object[] array = new Object[2 * size]; 798 int len = table.length; 799 int dest = 0; 800 for (int i = 0; i < len; i += 2) { 801 if (table[i] != null) { 802 array[dest++] = table[i]; 803 array[dest++] = table[i+1]; 804 } 805 } 806 return new CollSer(CollSer.IMM_MAP, array); 807 } 808 } 809 } 810 811 // ---------- Serialization Proxy ---------- 812 813 /** 814 * A unified serialization proxy class for the immutable collections. 815 * 816 * @serial 817 * @since 9 818 */ 819 final class CollSer implements Serializable { 820 private static final long serialVersionUID = 6309168927139932177L; 821 822 static final int IMM_LIST = 1; 823 static final int IMM_SET = 2; 824 static final int IMM_MAP = 3; 825 826 /** 827 * Indicates the type of collection that is serialized. 828 * The low order 8 bits have the value 1 for an immutable 829 * {@code List}, 2 for an immutable {@code Set}, and 3 for 830 * an immutable {@code Map}. Any other value causes an 831 * {@link InvalidObjectException} to be thrown. The high 832 * order 24 bits are zero when an instance is serialized, 833 * and they are ignored when an instance is deserialized. 834 * They can thus be used by future implementations without 835 * causing compatibility issues. 836 * 837 * <p>The tag value also determines the interpretation of the 838 * transient {@code Object[] array} field. 839 * For {@code List} and {@code Set}, the array's length is the size 840 * of the collection, and the array contains the elements of the collection. 841 * Null elements are not allowed. For {@code Set}, duplicate elements 842 * are not allowed. 843 * 844 * <p>For {@code Map}, the array's length is twice the number of mappings 845 * present in the map. The array length is necessarily even. 846 * The array contains a succession of key and value pairs: 847 * {@code k1, v1, k2, v2, ..., kN, vN.} Nulls are not allowed, 848 * and duplicate keys are not allowed. 849 * 850 * @serial 851 * @since 9 852 */ 853 private final int tag; 854 855 /** 856 * @serial 857 * @since 9 858 */ 859 private transient Object[] array; 860 861 CollSer(int t, Object... a) { 862 tag = t; 863 array = a; 864 } 865 866 /** 867 * Reads objects from the stream and stores them 868 * in the transient {@code Object[] array} field. 869 * 870 * @serialData 871 * A nonnegative int, indicating the count of objects, 872 * followed by that many objects. 873 * 874 * @param ois the ObjectInputStream from which data is read 875 * @throws IOException if an I/O error occurs 876 * @throws ClassNotFoundException if a serialized class cannot be loaded 877 * @throws InvalidObjectException if the count is negative 878 * @since 9 879 */ 880 private void readObject(ObjectInputStream ois) throws IOException, ClassNotFoundException { 881 ois.defaultReadObject(); 882 int len = ois.readInt(); 883 884 if (len < 0) { 885 throw new InvalidObjectException("negative length " + len); 886 } 887 888 Object[] a = new Object[len]; 889 for (int i = 0; i < len; i++) { 890 a[i] = ois.readObject(); 891 } 892 893 array = a; 894 } 895 896 /** 897 * Writes objects to the stream from 898 * the transient {@code Object[] array} field. 899 * 900 * @serialData 901 * A nonnegative int, indicating the count of objects, 902 * followed by that many objects. 903 * 904 * @param oos the ObjectOutputStream to which data is written 905 * @throws IOException if an I/O error occurs 906 * @since 9 907 */ 908 private void writeObject(ObjectOutputStream oos) throws IOException { 909 oos.defaultWriteObject(); 910 oos.writeInt(array.length); 911 for (int i = 0; i < array.length; i++) { 912 oos.writeObject(array[i]); 913 } 914 } 915 916 /** 917 * Creates and returns an immutable collection from this proxy class. 918 * The instance returned is created as if by calling one of the 919 * static factory methods for 920 * <a href="List.html#immutable">List</a>, 921 * <a href="Map.html#immutable">Map</a>, or 922 * <a href="Set.html#immutable">Set</a>. 923 * This proxy class is the serial form for all immutable collection instances, 924 * regardless of implementation type. This is necessary to ensure that the 925 * existence of any particular implementation type is kept out of the 926 * serialized form. 927 * 928 * @return a collection created from this proxy object 929 * @throws InvalidObjectException if the tag value is illegal or if an exception 930 * is thrown during creation of the collection 931 * @throws ObjectStreamException if another serialization error has occurred 932 * @since 9 933 */ 934 private Object readResolve() throws ObjectStreamException { 935 try { 936 if (array == null) { 937 throw new InvalidObjectException("null array"); 938 } 939 940 // use low order 8 bits to indicate "kind" 941 // ignore high order 24 bits 942 switch (tag & 0xff) { 943 case IMM_LIST: 944 return List.of(array); 945 case IMM_SET: 946 return Set.of(array); 947 case IMM_MAP: 948 if (array.length == 0) { 949 return ImmutableCollections.Map0.instance(); 950 } else if (array.length == 2) { 951 return new ImmutableCollections.Map1<>(array[0], array[1]); 952 } else { 953 return new ImmutableCollections.MapN<>(array); 954 } 955 default: 956 throw new InvalidObjectException(String.format("invalid flags 0x%x", tag)); 957 } 958 } catch (NullPointerException|IllegalArgumentException ex) { 959 InvalidObjectException ioe = new InvalidObjectException("invalid object"); 960 ioe.initCause(ex); 961 throw ioe; 962 } 963 } 964 } 965