1 /* 2 * Copyright (c) 2016, 2020, 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.lang.reflect.Array; 35 import java.util.function.BiFunction; 36 import java.util.function.Function; 37 import java.util.function.Predicate; 38 import java.util.function.UnaryOperator; 39 import jdk.internal.misc.SharedSecrets; 40 import jdk.internal.vm.annotation.Stable; 41 42 /** 43 * Container class for immutable collections. Not part of the public API. 44 * Mainly for namespace management and shared infrastructure. 45 * 46 * Serial warnings are suppressed throughout because all implementation 47 * classes use a serial proxy and thus have no need to declare serialVersionUID. 48 */ 49 @SuppressWarnings("serial") 50 class ImmutableCollections { 51 /** 52 * A "salt" value used for randomizing iteration order. This is initialized once 53 * and stays constant for the lifetime of the JVM. It need not be truly random, but 54 * it needs to vary sufficiently from one run to the next so that iteration order 55 * will vary between JVM runs. 56 */ 57 private static final long SALT32L; 58 59 /** 60 * For set and map iteration, we will iterate in "reverse" stochastically, 61 * decided at bootstrap time. 62 */ 63 private static final boolean REVERSE; 64 static { 65 // to generate a reasonably random and well-mixed SALT, use an arbitrary 66 // value (a slice of pi), multiply with a random seed, then pick 67 // the mid 32-bits from the product. By picking a SALT value in the 68 // [0 ... 0xFFFF_FFFFL == 2^32-1] range, we ensure that for any positive 69 // int N, (SALT32L * N) >> 32 is a number in the [0 ... N-1] range. This 70 // property will be used to avoid more expensive modulo-based 71 // calculations. 72 long color = 0x243F_6A88_85A3_08D3L; // slice of pi 73 74 // BEGIN Android-changed: set seed directly, as CDS is not available. 75 // When running with -Xshare:dump, the VM will supply a "random" seed that's 76 // derived from the JVM build/version, so can we generate the exact same 77 // CDS archive for the same JDK build. This makes it possible to verify the 78 // consistency of the JDK build. 79 // long seed = CDS.getRandomSeedForDumping(); 80 // if (seed == 0) { 81 // seed = System.nanoTime(); 82 // } 83 long seed = System.nanoTime(); 84 // END Android-changed: set seed directly, as CDS is not available. 85 SALT32L = (int)((color * seed) >> 16) & 0xFFFF_FFFFL; 86 // use the lowest bit to determine if we should reverse iteration 87 REVERSE = (SALT32L & 1) == 0; 88 } 89 90 // BEGIN Android-changed: always initialize empty collections. 91 /* 92 * Constants following this might be initialized from the CDS archive via 93 * this array. 94 * 95 // private static Object[] archivedObjects; 96 */ 97 98 private static final Object EMPTY = new Object(); 99 static final ListN<?> EMPTY_LIST = new ListN<>(new Object[0], false); 100 static final ListN<?> EMPTY_LIST_NULLS = new ListN<>(new Object[0], true); 101 static final SetN<?> EMPTY_SET = new SetN<>(); 102 static final MapN<?,?> EMPTY_MAP = new MapN<>(); 103 104 /* 105 static { 106 CDS.initializeFromArchive(ImmutableCollections.class); 107 if (archivedObjects == null) { 108 EMPTY = new Object(); 109 EMPTY_LIST = new ListN<>(new Object[0], false); 110 EMPTY_LIST_NULLS = new ListN<>(new Object[0], true); 111 EMPTY_SET = new SetN<>(); 112 EMPTY_MAP = new MapN<>(); 113 archivedObjects = 114 new Object[] { EMPTY, EMPTY_LIST, EMPTY_LIST_NULLS, EMPTY_SET, EMPTY_MAP }; 115 } else { 116 EMPTY = archivedObjects[0]; 117 EMPTY_LIST = (ListN)archivedObjects[1]; 118 EMPTY_LIST_NULLS = (ListN)archivedObjects[2]; 119 EMPTY_SET = (SetN)archivedObjects[3]; 120 EMPTY_MAP = (MapN)archivedObjects[4]; 121 } 122 } 123 */ 124 // END Android-changed: always initialize empty collections. 125 126 // BEGIN Android-changed: JavaUtilCollectionAccess is not yet imported. 127 /* 128 static class Access { 129 static { 130 SharedSecrets.setJavaUtilCollectionAccess(new JavaUtilCollectionAccess() { 131 public <E> List<E> listFromTrustedArray(Object[] array) { 132 return ImmutableCollections.listFromTrustedArray(array); 133 } 134 public <E> List<E> listFromTrustedArrayNullsAllowed(Object[] array) { 135 return ImmutableCollections.listFromTrustedArrayNullsAllowed(array); 136 } 137 }); 138 } 139 } 140 */ 141 // END Android-changed: JavaUtilCollectionAccess is not yet imported. 142 143 /** No instances. */ ImmutableCollections()144 private ImmutableCollections() { } 145 146 /** 147 * The reciprocal of load factor. Given a number of elements 148 * to store, multiply by this factor to get the table size. 149 */ 150 static final int EXPAND_FACTOR = 2; 151 uoe()152 static UnsupportedOperationException uoe() { return new UnsupportedOperationException(); } 153 154 @jdk.internal.ValueBased 155 static abstract class AbstractImmutableCollection<E> extends AbstractCollection<E> { 156 // all mutating methods throw UnsupportedOperationException add(E e)157 @Override public boolean add(E e) { throw uoe(); } addAll(Collection<? extends E> c)158 @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); } clear()159 @Override public void clear() { throw uoe(); } remove(Object o)160 @Override public boolean remove(Object o) { throw uoe(); } removeAll(Collection<?> c)161 @Override public boolean removeAll(Collection<?> c) { throw uoe(); } removeIf(Predicate<? super E> filter)162 @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); } retainAll(Collection<?> c)163 @Override public boolean retainAll(Collection<?> c) { throw uoe(); } 164 } 165 166 // ---------- List Static Factory Methods ---------- 167 168 /** 169 * Copies a collection into a new List, unless the arg is already a safe, 170 * null-prohibiting unmodifiable list, in which case the arg itself is returned. 171 * Null argument or null elements in the argument will result in NPE. 172 * 173 * @param <E> the List's element type 174 * @param input the input array 175 * @return the new list 176 */ 177 @SuppressWarnings("unchecked") listCopy(Collection<? extends E> coll)178 static <E> List<E> listCopy(Collection<? extends E> coll) { 179 if (coll instanceof List12 || (coll instanceof ListN && ! ((ListN<?>)coll).allowNulls)) { 180 return (List<E>)coll; 181 } else { 182 return (List<E>)List.of(coll.toArray()); // implicit nullcheck of coll 183 } 184 } 185 186 /** 187 * Creates a new List from an untrusted array, creating a new array for internal 188 * storage, and checking for and rejecting null elements. 189 * 190 * @param <E> the List's element type 191 * @param input the input array 192 * @return the new list 193 */ 194 @SafeVarargs listFromArray(E... input)195 static <E> List<E> listFromArray(E... input) { 196 // copy and check manually to avoid TOCTOU 197 @SuppressWarnings("unchecked") 198 E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input 199 for (int i = 0; i < input.length; i++) { 200 tmp[i] = Objects.requireNonNull(input[i]); 201 } 202 return new ListN<>(tmp, false); 203 } 204 205 /** 206 * Creates a new List from a trusted array, checking for and rejecting null 207 * elements. 208 * 209 * <p>A trusted array has no references retained by the caller. It can therefore be 210 * safely reused as the List's internal storage, avoiding a defensive copy. The array's 211 * class must be Object[].class. This method is declared with a parameter type of 212 * Object... instead of E... so that a varargs call doesn't accidentally create an array 213 * of some class other than Object[].class. 214 * 215 * @param <E> the List's element type 216 * @param input the input array 217 * @return the new list 218 */ 219 @SuppressWarnings("unchecked") listFromTrustedArray(Object... input)220 static <E> List<E> listFromTrustedArray(Object... input) { 221 assert input.getClass() == Object[].class; 222 for (Object o : input) { // implicit null check of 'input' array 223 Objects.requireNonNull(o); 224 } 225 226 return switch (input.length) { 227 case 0 -> (List<E>) ImmutableCollections.EMPTY_LIST; 228 case 1 -> (List<E>) new List12<>(input[0]); 229 case 2 -> (List<E>) new List12<>(input[0], input[1]); 230 default -> (List<E>) new ListN<>(input, false); 231 }; 232 } 233 234 /** 235 * Creates a new List from a trusted array, allowing null elements. 236 * 237 * <p>A trusted array has no references retained by the caller. It can therefore be 238 * safely reused as the List's internal storage, avoiding a defensive copy. The array's 239 * class must be Object[].class. This method is declared with a parameter type of 240 * Object... instead of E... so that a varargs call doesn't accidentally create an array 241 * of some class other than Object[].class. 242 * 243 * <p>Avoids creating a List12 instance, as it cannot accommodate null elements. 244 * 245 * @param <E> the List's element type 246 * @param input the input array 247 * @return the new list 248 */ 249 @SuppressWarnings("unchecked") listFromTrustedArrayNullsAllowed(Object... input)250 static <E> List<E> listFromTrustedArrayNullsAllowed(Object... input) { 251 assert input.getClass() == Object[].class; 252 if (input.length == 0) { 253 return (List<E>) EMPTY_LIST_NULLS; 254 } else { 255 return new ListN<>((E[])input, true); 256 } 257 } 258 259 // ---------- List Implementations ---------- 260 261 @jdk.internal.ValueBased 262 static abstract class AbstractImmutableList<E> extends AbstractImmutableCollection<E> 263 implements List<E>, RandomAccess { 264 265 // all mutating methods throw UnsupportedOperationException add(int index, E element)266 @Override public void add(int index, E element) { throw uoe(); } addAll(int index, Collection<? extends E> c)267 @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); } remove(int index)268 @Override public E remove(int index) { throw uoe(); } replaceAll(UnaryOperator<E> operator)269 @Override public void replaceAll(UnaryOperator<E> operator) { throw uoe(); } set(int index, E element)270 @Override public E set(int index, E element) { throw uoe(); } sort(Comparator<? super E> c)271 @Override public void sort(Comparator<? super E> c) { throw uoe(); } 272 273 @Override subList(int fromIndex, int toIndex)274 public List<E> subList(int fromIndex, int toIndex) { 275 int size = size(); 276 subListRangeCheck(fromIndex, toIndex, size); 277 return SubList.fromList(this, fromIndex, toIndex); 278 } 279 subListRangeCheck(int fromIndex, int toIndex, int size)280 static void subListRangeCheck(int fromIndex, int toIndex, int size) { 281 if (fromIndex < 0) 282 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 283 if (toIndex > size) 284 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 285 if (fromIndex > toIndex) 286 throw new IllegalArgumentException("fromIndex(" + fromIndex + 287 ") > toIndex(" + toIndex + ")"); 288 } 289 290 @Override iterator()291 public Iterator<E> iterator() { 292 return new ListItr<E>(this, size()); 293 } 294 295 @Override listIterator()296 public ListIterator<E> listIterator() { 297 return listIterator(0); 298 } 299 300 @Override listIterator(final int index)301 public ListIterator<E> listIterator(final int index) { 302 int size = size(); 303 if (index < 0 || index > size) { 304 throw outOfBounds(index); 305 } 306 return new ListItr<E>(this, size, index); 307 } 308 309 @Override equals(Object o)310 public boolean equals(Object o) { 311 if (o == this) { 312 return true; 313 } 314 315 if (!(o instanceof List)) { 316 return false; 317 } 318 319 Iterator<?> oit = ((List<?>) o).iterator(); 320 for (int i = 0, s = size(); i < s; i++) { 321 if (!oit.hasNext() || !Objects.equals(get(i), oit.next())) { 322 return false; 323 } 324 } 325 return !oit.hasNext(); 326 } 327 328 @Override hashCode()329 public int hashCode() { 330 int hash = 1; 331 for (int i = 0, s = size(); i < s; i++) { 332 hash = 31 * hash + Objects.hashCode(get(i)); 333 } 334 return hash; 335 } 336 337 @Override contains(Object o)338 public boolean contains(Object o) { 339 return indexOf(o) >= 0; 340 } 341 outOfBounds(int index)342 IndexOutOfBoundsException outOfBounds(int index) { 343 return new IndexOutOfBoundsException("Index: " + index + " Size: " + size()); 344 } 345 } 346 347 static final class ListItr<E> implements ListIterator<E> { 348 349 @Stable 350 private final List<E> list; 351 352 @Stable 353 private final int size; 354 355 @Stable 356 private final boolean isListIterator; 357 358 private int cursor; 359 ListItr(List<E> list, int size)360 ListItr(List<E> list, int size) { 361 this.list = list; 362 this.size = size; 363 this.cursor = 0; 364 isListIterator = false; 365 } 366 ListItr(List<E> list, int size, int index)367 ListItr(List<E> list, int size, int index) { 368 this.list = list; 369 this.size = size; 370 this.cursor = index; 371 isListIterator = true; 372 } 373 hasNext()374 public boolean hasNext() { 375 return cursor != size; 376 } 377 next()378 public E next() { 379 try { 380 int i = cursor; 381 E next = list.get(i); 382 cursor = i + 1; 383 return next; 384 } catch (IndexOutOfBoundsException e) { 385 throw new NoSuchElementException(); 386 } 387 } 388 remove()389 public void remove() { 390 throw uoe(); 391 } 392 hasPrevious()393 public boolean hasPrevious() { 394 if (!isListIterator) { 395 throw uoe(); 396 } 397 return cursor != 0; 398 } 399 previous()400 public E previous() { 401 if (!isListIterator) { 402 throw uoe(); 403 } 404 try { 405 int i = cursor - 1; 406 E previous = list.get(i); 407 cursor = i; 408 return previous; 409 } catch (IndexOutOfBoundsException e) { 410 throw new NoSuchElementException(); 411 } 412 } 413 nextIndex()414 public int nextIndex() { 415 if (!isListIterator) { 416 throw uoe(); 417 } 418 return cursor; 419 } 420 previousIndex()421 public int previousIndex() { 422 if (!isListIterator) { 423 throw uoe(); 424 } 425 return cursor - 1; 426 } 427 set(E e)428 public void set(E e) { 429 throw uoe(); 430 } 431 add(E e)432 public void add(E e) { 433 throw uoe(); 434 } 435 } 436 437 static final class SubList<E> extends AbstractImmutableList<E> 438 implements RandomAccess { 439 440 @Stable 441 private final AbstractImmutableList<E> root; 442 443 @Stable 444 private final int offset; 445 446 @Stable 447 private final int size; 448 SubList(AbstractImmutableList<E> root, int offset, int size)449 private SubList(AbstractImmutableList<E> root, int offset, int size) { 450 assert root instanceof List12 || root instanceof ListN; 451 this.root = root; 452 this.offset = offset; 453 this.size = size; 454 } 455 456 /** 457 * Constructs a sublist of another SubList. 458 */ fromSubList(SubList<E> parent, int fromIndex, int toIndex)459 static <E> SubList<E> fromSubList(SubList<E> parent, int fromIndex, int toIndex) { 460 return new SubList<>(parent.root, parent.offset + fromIndex, toIndex - fromIndex); 461 } 462 463 /** 464 * Constructs a sublist of an arbitrary AbstractImmutableList, which is 465 * not a SubList itself. 466 */ fromList(AbstractImmutableList<E> list, int fromIndex, int toIndex)467 static <E> SubList<E> fromList(AbstractImmutableList<E> list, int fromIndex, int toIndex) { 468 return new SubList<>(list, fromIndex, toIndex - fromIndex); 469 } 470 get(int index)471 public E get(int index) { 472 Objects.checkIndex(index, size); 473 return root.get(offset + index); 474 } 475 size()476 public int size() { 477 return size; 478 } 479 iterator()480 public Iterator<E> iterator() { 481 return new ListItr<>(this, size()); 482 } 483 listIterator(int index)484 public ListIterator<E> listIterator(int index) { 485 rangeCheck(index); 486 return new ListItr<>(this, size(), index); 487 } 488 subList(int fromIndex, int toIndex)489 public List<E> subList(int fromIndex, int toIndex) { 490 subListRangeCheck(fromIndex, toIndex, size); 491 return SubList.fromSubList(this, fromIndex, toIndex); 492 } 493 rangeCheck(int index)494 private void rangeCheck(int index) { 495 if (index < 0 || index > size) { 496 throw outOfBounds(index); 497 } 498 } 499 allowNulls()500 private boolean allowNulls() { 501 return root instanceof ListN && ((ListN<?>)root).allowNulls; 502 } 503 504 @Override indexOf(Object o)505 public int indexOf(Object o) { 506 if (!allowNulls() && o == null) { 507 throw new NullPointerException(); 508 } 509 for (int i = 0, s = size(); i < s; i++) { 510 if (Objects.equals(o, get(i))) { 511 return i; 512 } 513 } 514 return -1; 515 } 516 517 @Override lastIndexOf(Object o)518 public int lastIndexOf(Object o) { 519 if (!allowNulls() && o == null) { 520 throw new NullPointerException(); 521 } 522 for (int i = size() - 1; i >= 0; i--) { 523 if (Objects.equals(o, get(i))) { 524 return i; 525 } 526 } 527 return -1; 528 } 529 530 @Override toArray()531 public Object[] toArray() { 532 Object[] array = new Object[size]; 533 for (int i = 0; i < size; i++) { 534 array[i] = get(i); 535 } 536 return array; 537 } 538 539 @Override 540 @SuppressWarnings("unchecked") toArray(T[] a)541 public <T> T[] toArray(T[] a) { 542 T[] array = a.length >= size ? a : 543 (T[])java.lang.reflect.Array 544 .newInstance(a.getClass().getComponentType(), size); 545 for (int i = 0; i < size; i++) { 546 array[i] = (T)get(i); 547 } 548 if (array.length > size) { 549 array[size] = null; // null-terminate 550 } 551 return array; 552 } 553 } 554 555 @jdk.internal.ValueBased 556 static final class List12<E> extends AbstractImmutableList<E> 557 implements Serializable { 558 559 @Stable 560 private final E e0; 561 562 @Stable 563 private final Object e1; 564 List12(E e0)565 List12(E e0) { 566 this.e0 = Objects.requireNonNull(e0); 567 // Use EMPTY as a sentinel for an unused element: not using null 568 // enables constant folding optimizations over single-element lists 569 this.e1 = EMPTY; 570 } 571 List12(E e0, E e1)572 List12(E e0, E e1) { 573 this.e0 = Objects.requireNonNull(e0); 574 this.e1 = Objects.requireNonNull(e1); 575 } 576 577 @Override size()578 public int size() { 579 return e1 != EMPTY ? 2 : 1; 580 } 581 582 @Override isEmpty()583 public boolean isEmpty() { 584 return false; 585 } 586 587 @Override 588 @SuppressWarnings("unchecked") get(int index)589 public E get(int index) { 590 if (index == 0) { 591 return e0; 592 } else if (index == 1 && e1 != EMPTY) { 593 return (E)e1; 594 } 595 throw outOfBounds(index); 596 } 597 598 @Override indexOf(Object o)599 public int indexOf(Object o) { 600 Objects.requireNonNull(o); 601 if (o.equals(e0)) { 602 return 0; 603 } else if (e1 != EMPTY && o.equals(e1)) { 604 return 1; 605 } else { 606 return -1; 607 } 608 } 609 610 @Override lastIndexOf(Object o)611 public int lastIndexOf(Object o) { 612 Objects.requireNonNull(o); 613 if (e1 != EMPTY && o.equals(e1)) { 614 return 1; 615 } else if (o.equals(e0)) { 616 return 0; 617 } else { 618 return -1; 619 } 620 } 621 622 @java.io.Serial readObject(ObjectInputStream in)623 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 624 throw new InvalidObjectException("not serial proxy"); 625 } 626 627 @java.io.Serial writeReplace()628 private Object writeReplace() { 629 if (e1 == EMPTY) { 630 return new CollSer(CollSer.IMM_LIST, e0); 631 } else { 632 return new CollSer(CollSer.IMM_LIST, e0, e1); 633 } 634 } 635 636 @Override toArray()637 public Object[] toArray() { 638 if (e1 == EMPTY) { 639 return new Object[] { e0 }; 640 } else { 641 return new Object[] { e0, e1 }; 642 } 643 } 644 645 @Override 646 @SuppressWarnings("unchecked") toArray(T[] a)647 public <T> T[] toArray(T[] a) { 648 int size = size(); 649 T[] array = a.length >= size ? a : 650 (T[])Array.newInstance(a.getClass().getComponentType(), size); 651 array[0] = (T)e0; 652 if (size == 2) { 653 array[1] = (T)e1; 654 } 655 if (array.length > size) { 656 array[size] = null; // null-terminate 657 } 658 return array; 659 } 660 } 661 662 @jdk.internal.ValueBased 663 static final class ListN<E> extends AbstractImmutableList<E> 664 implements Serializable { 665 666 @Stable 667 private final E[] elements; 668 669 @Stable 670 private final boolean allowNulls; 671 672 // caller must ensure that elements has no nulls if allowNulls is false ListN(E[] elements, boolean allowNulls)673 private ListN(E[] elements, boolean allowNulls) { 674 this.elements = elements; 675 this.allowNulls = allowNulls; 676 } 677 678 @Override isEmpty()679 public boolean isEmpty() { 680 return elements.length == 0; 681 } 682 683 @Override size()684 public int size() { 685 return elements.length; 686 } 687 688 @Override get(int index)689 public E get(int index) { 690 return elements[index]; 691 } 692 693 @java.io.Serial readObject(ObjectInputStream in)694 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 695 throw new InvalidObjectException("not serial proxy"); 696 } 697 698 @java.io.Serial writeReplace()699 private Object writeReplace() { 700 return new CollSer(allowNulls ? CollSer.IMM_LIST_NULLS : CollSer.IMM_LIST, elements); 701 } 702 703 @Override toArray()704 public Object[] toArray() { 705 return Arrays.copyOf(elements, elements.length); 706 } 707 708 @Override 709 @SuppressWarnings("unchecked") toArray(T[] a)710 public <T> T[] toArray(T[] a) { 711 int size = elements.length; 712 if (a.length < size) { 713 // Make a new array of a's runtime type, but my contents: 714 return (T[]) Arrays.copyOf(elements, size, a.getClass()); 715 } 716 System.arraycopy(elements, 0, a, 0, size); 717 if (a.length > size) { 718 a[size] = null; // null-terminate 719 } 720 return a; 721 } 722 723 @Override indexOf(Object o)724 public int indexOf(Object o) { 725 if (!allowNulls && o == null) { 726 throw new NullPointerException(); 727 } 728 Object[] es = elements; 729 for (int i = 0; i < es.length; i++) { 730 if (Objects.equals(o, es[i])) { 731 return i; 732 } 733 } 734 return -1; 735 } 736 737 @Override lastIndexOf(Object o)738 public int lastIndexOf(Object o) { 739 if (!allowNulls && o == null) { 740 throw new NullPointerException(); 741 } 742 Object[] es = elements; 743 for (int i = es.length - 1; i >= 0; i--) { 744 if (Objects.equals(o, es[i])) { 745 return i; 746 } 747 } 748 return -1; 749 } 750 } 751 752 // ---------- Set Implementations ---------- 753 754 @jdk.internal.ValueBased 755 static abstract class AbstractImmutableSet<E> extends AbstractImmutableCollection<E> 756 implements Set<E> { 757 758 @Override equals(Object o)759 public boolean equals(Object o) { 760 if (o == this) { 761 return true; 762 } else if (!(o instanceof Set)) { 763 return false; 764 } 765 766 Collection<?> c = (Collection<?>) o; 767 if (c.size() != size()) { 768 return false; 769 } 770 for (Object e : c) { 771 if (e == null || !contains(e)) { 772 return false; 773 } 774 } 775 return true; 776 } 777 778 @Override hashCode()779 public abstract int hashCode(); 780 } 781 782 @jdk.internal.ValueBased 783 static final class Set12<E> extends AbstractImmutableSet<E> 784 implements Serializable { 785 786 @Stable 787 private final E e0; 788 789 @Stable 790 private final Object e1; 791 Set12(E e0)792 Set12(E e0) { 793 this.e0 = Objects.requireNonNull(e0); 794 // Use EMPTY as a sentinel for an unused element: not using null 795 // enable constant folding optimizations over single-element sets 796 this.e1 = EMPTY; 797 } 798 Set12(E e0, E e1)799 Set12(E e0, E e1) { 800 if (e0.equals(Objects.requireNonNull(e1))) { // implicit nullcheck of e0 801 throw new IllegalArgumentException("duplicate element: " + e0); 802 } 803 804 this.e0 = e0; 805 this.e1 = e1; 806 } 807 808 @Override size()809 public int size() { 810 return (e1 == EMPTY) ? 1 : 2; 811 } 812 813 @Override isEmpty()814 public boolean isEmpty() { 815 return false; 816 } 817 818 @Override contains(Object o)819 public boolean contains(Object o) { 820 return o.equals(e0) || e1.equals(o); // implicit nullcheck of o 821 } 822 823 @Override hashCode()824 public int hashCode() { 825 return e0.hashCode() + (e1 == EMPTY ? 0 : e1.hashCode()); 826 } 827 828 @Override iterator()829 public Iterator<E> iterator() { 830 return new Iterator<>() { 831 private int idx = (e1 == EMPTY) ? 1 : 2; 832 833 @Override 834 public boolean hasNext() { 835 return idx > 0; 836 } 837 838 @Override 839 @SuppressWarnings("unchecked") 840 public E next() { 841 if (idx == 1) { 842 idx = 0; 843 return (REVERSE || e1 == EMPTY) ? e0 : (E)e1; 844 } else if (idx == 2) { 845 idx = 1; 846 return REVERSE ? (E)e1 : e0; 847 } else { 848 throw new NoSuchElementException(); 849 } 850 } 851 }; 852 } 853 854 @java.io.Serial readObject(ObjectInputStream in)855 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 856 throw new InvalidObjectException("not serial proxy"); 857 } 858 859 @java.io.Serial writeReplace()860 private Object writeReplace() { 861 if (e1 == EMPTY) { 862 return new CollSer(CollSer.IMM_SET, e0); 863 } else { 864 return new CollSer(CollSer.IMM_SET, e0, e1); 865 } 866 } 867 868 @Override toArray()869 public Object[] toArray() { 870 if (e1 == EMPTY) { 871 return new Object[] { e0 }; 872 } else if (REVERSE) { 873 return new Object[] { e1, e0 }; 874 } else { 875 return new Object[] { e0, e1 }; 876 } 877 } 878 879 @Override 880 @SuppressWarnings("unchecked") toArray(T[] a)881 public <T> T[] toArray(T[] a) { 882 int size = size(); 883 T[] array = a.length >= size ? a : 884 (T[])Array.newInstance(a.getClass().getComponentType(), size); 885 if (size == 1) { 886 array[0] = (T)e0; 887 } else if (REVERSE) { 888 array[0] = (T)e1; 889 array[1] = (T)e0; 890 } else { 891 array[0] = (T)e0; 892 array[1] = (T)e1; 893 } 894 if (array.length > size) { 895 array[size] = null; // null-terminate 896 } 897 return array; 898 } 899 } 900 901 902 /** 903 * An array-based Set implementation. The element array must be strictly 904 * larger than the size (the number of contained elements) so that at 905 * least one null is always present. 906 * @param <E> the element type 907 */ 908 @jdk.internal.ValueBased 909 static final class SetN<E> extends AbstractImmutableSet<E> 910 implements Serializable { 911 912 @Stable 913 final E[] elements; 914 915 @Stable 916 final int size; 917 918 @SafeVarargs 919 @SuppressWarnings("unchecked") 920 SetN(E... input) { 921 size = input.length; // implicit nullcheck of input 922 923 elements = (E[])new Object[EXPAND_FACTOR * input.length]; 924 for (int i = 0; i < input.length; i++) { 925 E e = input[i]; 926 int idx = probe(e); // implicit nullcheck of e 927 if (idx >= 0) { 928 throw new IllegalArgumentException("duplicate element: " + e); 929 } else { 930 elements[-(idx + 1)] = e; 931 } 932 } 933 } 934 935 @Override 936 public int size() { 937 return size; 938 } 939 940 @Override 941 public boolean isEmpty() { 942 return size == 0; 943 } 944 945 @Override 946 public boolean contains(Object o) { 947 Objects.requireNonNull(o); 948 return size > 0 && probe(o) >= 0; 949 } 950 951 private final class SetNIterator implements Iterator<E> { 952 953 private int remaining; 954 955 private int idx; 956 957 SetNIterator() { 958 remaining = size; 959 // pick a starting index in the [0 .. element.length-1] range 960 // randomly based on SALT32L 961 idx = (int) ((SALT32L * elements.length) >>> 32); 962 } 963 964 @Override 965 public boolean hasNext() { 966 return remaining > 0; 967 } 968 969 @Override 970 public E next() { 971 if (remaining > 0) { 972 E element; 973 int idx = this.idx; 974 int len = elements.length; 975 // step to the next element; skip null elements 976 do { 977 if (REVERSE) { 978 if (++idx >= len) { 979 idx = 0; 980 } 981 } else { 982 if (--idx < 0) { 983 idx = len - 1; 984 } 985 } 986 } while ((element = elements[idx]) == null); 987 this.idx = idx; 988 remaining--; 989 return element; 990 } else { 991 throw new NoSuchElementException(); 992 } 993 } 994 } 995 996 @Override 997 public Iterator<E> iterator() { 998 return new SetNIterator(); 999 } 1000 1001 @Override 1002 public int hashCode() { 1003 int h = 0; 1004 for (E e : elements) { 1005 if (e != null) { 1006 h += e.hashCode(); 1007 } 1008 } 1009 return h; 1010 } 1011 1012 // returns index at which element is present; or if absent, 1013 // (-i - 1) where i is location where element should be inserted. 1014 // Callers are relying on this method to perform an implicit nullcheck 1015 // of pe 1016 private int probe(Object pe) { 1017 int idx = Math.floorMod(pe.hashCode(), elements.length); 1018 while (true) { 1019 E ee = elements[idx]; 1020 if (ee == null) { 1021 return -idx - 1; 1022 } else if (pe.equals(ee)) { 1023 return idx; 1024 } else if (++idx == elements.length) { 1025 idx = 0; 1026 } 1027 } 1028 } 1029 1030 @java.io.Serial 1031 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 1032 throw new InvalidObjectException("not serial proxy"); 1033 } 1034 1035 @java.io.Serial 1036 private Object writeReplace() { 1037 Object[] array = new Object[size]; 1038 int dest = 0; 1039 for (Object o : elements) { 1040 if (o != null) { 1041 array[dest++] = o; 1042 } 1043 } 1044 return new CollSer(CollSer.IMM_SET, array); 1045 } 1046 1047 @Override 1048 public Object[] toArray() { 1049 Object[] array = new Object[size]; 1050 Iterator<E> it = iterator(); 1051 for (int i = 0; i < size; i++) { 1052 array[i] = it.next(); 1053 } 1054 return array; 1055 } 1056 1057 @Override 1058 @SuppressWarnings("unchecked") 1059 public <T> T[] toArray(T[] a) { 1060 T[] array = a.length >= size ? a : 1061 (T[])Array.newInstance(a.getClass().getComponentType(), size); 1062 Iterator<E> it = iterator(); 1063 for (int i = 0; i < size; i++) { 1064 array[i] = (T)it.next(); 1065 } 1066 if (array.length > size) { 1067 array[size] = null; // null-terminate 1068 } 1069 return array; 1070 } 1071 } 1072 1073 // ---------- Map Implementations ---------- 1074 1075 @jdk.internal.ValueBased 1076 abstract static class AbstractImmutableMap<K,V> extends AbstractMap<K,V> implements Serializable { 1077 @Override public void clear() { throw uoe(); } 1078 @Override public V compute(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); } 1079 @Override public V computeIfAbsent(K key, Function<? super K,? extends V> mf) { throw uoe(); } 1080 @Override public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); } 1081 @Override public V merge(K key, V value, BiFunction<? super V,? super V,? extends V> rf) { throw uoe(); } 1082 @Override public V put(K key, V value) { throw uoe(); } 1083 @Override public void putAll(Map<? extends K,? extends V> m) { throw uoe(); } 1084 @Override public V putIfAbsent(K key, V value) { throw uoe(); } 1085 @Override public V remove(Object key) { throw uoe(); } 1086 @Override public boolean remove(Object key, Object value) { throw uoe(); } 1087 @Override public V replace(K key, V value) { throw uoe(); } 1088 @Override public boolean replace(K key, V oldValue, V newValue) { throw uoe(); } 1089 @Override public void replaceAll(BiFunction<? super K,? super V,? extends V> f) { throw uoe(); } 1090 1091 /** 1092 * @implNote {@code null} values are disallowed in these immutable maps, 1093 * so we can improve upon the default implementation since a 1094 * {@code null} return from {@code get(key)} always means the default 1095 * value should be returned. 1096 */ 1097 @Override 1098 public V getOrDefault(Object key, V defaultValue) { 1099 V v; 1100 return ((v = get(key)) != null) 1101 ? v 1102 : defaultValue; 1103 } 1104 } 1105 1106 @jdk.internal.ValueBased 1107 static final class Map1<K,V> extends AbstractImmutableMap<K,V> { 1108 @Stable 1109 private final K k0; 1110 @Stable 1111 private final V v0; 1112 1113 Map1(K k0, V v0) { 1114 this.k0 = Objects.requireNonNull(k0); 1115 this.v0 = Objects.requireNonNull(v0); 1116 } 1117 1118 @Override 1119 public Set<Map.Entry<K,V>> entrySet() { 1120 return Set.of(new KeyValueHolder<>(k0, v0)); 1121 } 1122 1123 @Override 1124 public V get(Object o) { 1125 return o.equals(k0) ? v0 : null; // implicit nullcheck of o 1126 } 1127 1128 @Override 1129 public boolean containsKey(Object o) { 1130 return o.equals(k0); // implicit nullcheck of o 1131 } 1132 1133 @Override 1134 public boolean containsValue(Object o) { 1135 return o.equals(v0); // implicit nullcheck of o 1136 } 1137 1138 @Override 1139 public int size() { 1140 return 1; 1141 } 1142 1143 @Override 1144 public boolean isEmpty() { 1145 return false; 1146 } 1147 1148 @java.io.Serial 1149 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 1150 throw new InvalidObjectException("not serial proxy"); 1151 } 1152 1153 @java.io.Serial 1154 private Object writeReplace() { 1155 return new CollSer(CollSer.IMM_MAP, k0, v0); 1156 } 1157 1158 @Override 1159 public int hashCode() { 1160 return k0.hashCode() ^ v0.hashCode(); 1161 } 1162 } 1163 1164 /** 1165 * An array-based Map implementation. There is a single array "table" that 1166 * contains keys and values interleaved: table[0] is kA, table[1] is vA, 1167 * table[2] is kB, table[3] is vB, etc. The table size must be even. It must 1168 * also be strictly larger than the size (the number of key-value pairs contained 1169 * in the map) so that at least one null key is always present. 1170 * @param <K> the key type 1171 * @param <V> the value type 1172 */ 1173 @jdk.internal.ValueBased 1174 static final class MapN<K,V> extends AbstractImmutableMap<K,V> { 1175 1176 @Stable 1177 final Object[] table; // pairs of key, value 1178 1179 @Stable 1180 final int size; // number of pairs 1181 1182 MapN(Object... input) { 1183 if ((input.length & 1) != 0) { // implicit nullcheck of input 1184 throw new InternalError("length is odd"); 1185 } 1186 size = input.length >> 1; 1187 1188 int len = EXPAND_FACTOR * input.length; 1189 len = (len + 1) & ~1; // ensure table is even length 1190 table = new Object[len]; 1191 1192 for (int i = 0; i < input.length; i += 2) { 1193 @SuppressWarnings("unchecked") 1194 K k = Objects.requireNonNull((K)input[i]); 1195 @SuppressWarnings("unchecked") 1196 V v = Objects.requireNonNull((V)input[i+1]); 1197 int idx = probe(k); 1198 if (idx >= 0) { 1199 throw new IllegalArgumentException("duplicate key: " + k); 1200 } else { 1201 int dest = -(idx + 1); 1202 table[dest] = k; 1203 table[dest+1] = v; 1204 } 1205 } 1206 } 1207 1208 @Override 1209 public boolean containsKey(Object o) { 1210 Objects.requireNonNull(o); 1211 return size > 0 && probe(o) >= 0; 1212 } 1213 1214 @Override 1215 public boolean containsValue(Object o) { 1216 Objects.requireNonNull(o); 1217 for (int i = 1; i < table.length; i += 2) { 1218 Object v = table[i]; 1219 if (v != null && o.equals(v)) { 1220 return true; 1221 } 1222 } 1223 return false; 1224 } 1225 1226 @Override 1227 public int hashCode() { 1228 int hash = 0; 1229 for (int i = 0; i < table.length; i += 2) { 1230 Object k = table[i]; 1231 if (k != null) { 1232 hash += k.hashCode() ^ table[i + 1].hashCode(); 1233 } 1234 } 1235 return hash; 1236 } 1237 1238 @Override 1239 @SuppressWarnings("unchecked") 1240 public V get(Object o) { 1241 if (size == 0) { 1242 Objects.requireNonNull(o); 1243 return null; 1244 } 1245 int i = probe(o); 1246 if (i >= 0) { 1247 return (V)table[i+1]; 1248 } else { 1249 return null; 1250 } 1251 } 1252 1253 @Override 1254 public int size() { 1255 return size; 1256 } 1257 1258 @Override 1259 public boolean isEmpty() { 1260 return size == 0; 1261 } 1262 1263 class MapNIterator implements Iterator<Map.Entry<K,V>> { 1264 1265 private int remaining; 1266 1267 private int idx; 1268 1269 MapNIterator() { 1270 remaining = size; 1271 // pick an even starting index in the [0 .. table.length-1] 1272 // range randomly based on SALT32L 1273 idx = (int) ((SALT32L * (table.length >> 1)) >>> 32) << 1; 1274 } 1275 1276 @Override 1277 public boolean hasNext() { 1278 return remaining > 0; 1279 } 1280 1281 private int nextIndex() { 1282 int idx = this.idx; 1283 if (REVERSE) { 1284 if ((idx += 2) >= table.length) { 1285 idx = 0; 1286 } 1287 } else { 1288 if ((idx -= 2) < 0) { 1289 idx = table.length - 2; 1290 } 1291 } 1292 return this.idx = idx; 1293 } 1294 1295 @Override 1296 public Map.Entry<K,V> next() { 1297 if (remaining > 0) { 1298 int idx; 1299 while (table[idx = nextIndex()] == null) {} 1300 @SuppressWarnings("unchecked") 1301 Map.Entry<K,V> e = 1302 new KeyValueHolder<>((K)table[idx], (V)table[idx+1]); 1303 remaining--; 1304 return e; 1305 } else { 1306 throw new NoSuchElementException(); 1307 } 1308 } 1309 } 1310 1311 @Override 1312 public Set<Map.Entry<K,V>> entrySet() { 1313 return new AbstractSet<>() { 1314 @Override 1315 public int size() { 1316 return MapN.this.size; 1317 } 1318 1319 @Override 1320 public Iterator<Map.Entry<K,V>> iterator() { 1321 return new MapNIterator(); 1322 } 1323 1324 // Android-added: AbstractCollection#clear implementation is no-op when 1325 // collection is empty. Overriding this method to make Map.of().clear() 1326 // and Map.of().entrySet().clear() behaviour equal. 1327 @Override 1328 public void clear() { 1329 throw uoe(); 1330 } 1331 }; 1332 } 1333 1334 // returns index at which the probe key is present; or if absent, 1335 // (-i - 1) where i is location where element should be inserted. 1336 // Callers are relying on this method to perform an implicit nullcheck 1337 // of pk. 1338 private int probe(Object pk) { 1339 int idx = Math.floorMod(pk.hashCode(), table.length >> 1) << 1; 1340 while (true) { 1341 @SuppressWarnings("unchecked") 1342 K ek = (K)table[idx]; 1343 if (ek == null) { 1344 return -idx - 1; 1345 } else if (pk.equals(ek)) { 1346 return idx; 1347 } else if ((idx += 2) == table.length) { 1348 idx = 0; 1349 } 1350 } 1351 } 1352 1353 @java.io.Serial 1354 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 1355 throw new InvalidObjectException("not serial proxy"); 1356 } 1357 1358 @java.io.Serial 1359 private Object writeReplace() { 1360 Object[] array = new Object[2 * size]; 1361 int len = table.length; 1362 int dest = 0; 1363 for (int i = 0; i < len; i += 2) { 1364 if (table[i] != null) { 1365 array[dest++] = table[i]; 1366 array[dest++] = table[i+1]; 1367 } 1368 } 1369 return new CollSer(CollSer.IMM_MAP, array); 1370 } 1371 } 1372 } 1373 1374 // ---------- Serialization Proxy ---------- 1375 1376 /** 1377 * A unified serialization proxy class for the immutable collections. 1378 * 1379 * @serial 1380 * @since 9 1381 */ 1382 final class CollSer implements Serializable { 1383 @java.io.Serial 1384 private static final long serialVersionUID = 6309168927139932177L; 1385 1386 static final int IMM_LIST = 1; 1387 static final int IMM_SET = 2; 1388 static final int IMM_MAP = 3; 1389 static final int IMM_LIST_NULLS = 4; 1390 1391 /** 1392 * Indicates the type of collection that is serialized. 1393 * The low order 8 bits have the value 1 for an immutable 1394 * {@code List}, 2 for an immutable {@code Set}, 3 for 1395 * an immutable {@code Map}, and 4 for an immutable 1396 * {@code List} that allows null elements. 1397 * 1398 * Any other value causes an 1399 * {@link InvalidObjectException} to be thrown. The high 1400 * order 24 bits are zero when an instance is serialized, 1401 * and they are ignored when an instance is deserialized. 1402 * They can thus be used by future implementations without 1403 * causing compatibility issues. 1404 * 1405 * <p>The tag value also determines the interpretation of the 1406 * transient {@code Object[] array} field. 1407 * For {@code List} and {@code Set}, the array's length is the size 1408 * of the collection, and the array contains the elements of the collection. 1409 * Null elements are not allowed. For {@code Set}, duplicate elements 1410 * are not allowed. 1411 * 1412 * <p>For {@code Map}, the array's length is twice the number of mappings 1413 * present in the map. The array length is necessarily even. 1414 * The array contains a succession of key and value pairs: 1415 * {@code k1, v1, k2, v2, ..., kN, vN.} Nulls are not allowed, 1416 * and duplicate keys are not allowed. 1417 * 1418 * @serial 1419 * @since 9 1420 */ 1421 private final int tag; 1422 1423 /** 1424 * @serial 1425 * @since 9 1426 */ 1427 private transient Object[] array; 1428 1429 CollSer(int t, Object... a) { 1430 tag = t; 1431 array = a; 1432 } 1433 1434 /** 1435 * Reads objects from the stream and stores them 1436 * in the transient {@code Object[] array} field. 1437 * 1438 * @serialData 1439 * A nonnegative int, indicating the count of objects, 1440 * followed by that many objects. 1441 * 1442 * @param ois the ObjectInputStream from which data is read 1443 * @throws IOException if an I/O error occurs 1444 * @throws ClassNotFoundException if a serialized class cannot be loaded 1445 * @throws InvalidObjectException if the count is negative 1446 * @since 9 1447 */ 1448 @java.io.Serial 1449 private void readObject(ObjectInputStream ois) throws IOException, ClassNotFoundException { 1450 ois.defaultReadObject(); 1451 int len = ois.readInt(); 1452 1453 if (len < 0) { 1454 throw new InvalidObjectException("negative length " + len); 1455 } 1456 1457 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(ois, Object[].class, len); 1458 Object[] a = new Object[len]; 1459 for (int i = 0; i < len; i++) { 1460 a[i] = ois.readObject(); 1461 } 1462 1463 array = a; 1464 } 1465 1466 /** 1467 * Writes objects to the stream from 1468 * the transient {@code Object[] array} field. 1469 * 1470 * @serialData 1471 * A nonnegative int, indicating the count of objects, 1472 * followed by that many objects. 1473 * 1474 * @param oos the ObjectOutputStream to which data is written 1475 * @throws IOException if an I/O error occurs 1476 * @since 9 1477 */ 1478 @java.io.Serial 1479 private void writeObject(ObjectOutputStream oos) throws IOException { 1480 oos.defaultWriteObject(); 1481 oos.writeInt(array.length); 1482 for (int i = 0; i < array.length; i++) { 1483 oos.writeObject(array[i]); 1484 } 1485 } 1486 1487 /** 1488 * Creates and returns an immutable collection from this proxy class. 1489 * The instance returned is created as if by calling one of the 1490 * static factory methods for 1491 * <a href="List.html#unmodifiable">List</a>, 1492 * <a href="Map.html#unmodifiable">Map</a>, or 1493 * <a href="Set.html#unmodifiable">Set</a>. 1494 * This proxy class is the serial form for all immutable collection instances, 1495 * regardless of implementation type. This is necessary to ensure that the 1496 * existence of any particular implementation type is kept out of the 1497 * serialized form. 1498 * 1499 * @return a collection created from this proxy object 1500 * @throws InvalidObjectException if the tag value is illegal or if an exception 1501 * is thrown during creation of the collection 1502 * @throws ObjectStreamException if another serialization error has occurred 1503 * @since 9 1504 */ 1505 @java.io.Serial 1506 private Object readResolve() throws ObjectStreamException { 1507 try { 1508 if (array == null) { 1509 throw new InvalidObjectException("null array"); 1510 } 1511 1512 // use low order 8 bits to indicate "kind" 1513 // ignore high order 24 bits 1514 switch (tag & 0xff) { 1515 case IMM_LIST: 1516 return List.of(array); 1517 case IMM_LIST_NULLS: 1518 return ImmutableCollections.listFromTrustedArrayNullsAllowed( 1519 Arrays.copyOf(array, array.length, Object[].class)); 1520 case IMM_SET: 1521 return Set.of(array); 1522 case IMM_MAP: 1523 if (array.length == 0) { 1524 return ImmutableCollections.EMPTY_MAP; 1525 } else if (array.length == 2) { 1526 return new ImmutableCollections.Map1<>(array[0], array[1]); 1527 } else { 1528 return new ImmutableCollections.MapN<>(array); 1529 } 1530 default: 1531 throw new InvalidObjectException(String.format("invalid flags 0x%x", tag)); 1532 } 1533 } catch (NullPointerException|IllegalArgumentException ex) { 1534 InvalidObjectException ioe = new InvalidObjectException("invalid object"); 1535 ioe.initCause(ex); 1536 throw ioe; 1537 } 1538 } 1539 } 1540