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