001/* 002 * Copyright (C) 2008 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkNotNull; 020import static com.google.common.base.Preconditions.checkState; 021import static com.google.common.collect.CollectPreconditions.checkEntryNotNull; 022import static com.google.common.collect.CollectPreconditions.checkNonnegative; 023import static java.util.Objects.requireNonNull; 024 025import com.google.common.annotations.GwtCompatible; 026import com.google.common.annotations.GwtIncompatible; 027import com.google.common.annotations.J2ktIncompatible; 028import com.google.common.annotations.VisibleForTesting; 029import com.google.errorprone.annotations.CanIgnoreReturnValue; 030import com.google.errorprone.annotations.DoNotCall; 031import com.google.errorprone.annotations.DoNotMock; 032import com.google.errorprone.annotations.concurrent.LazyInit; 033import com.google.j2objc.annotations.RetainedWith; 034import com.google.j2objc.annotations.WeakOuter; 035import java.io.InvalidObjectException; 036import java.io.ObjectInputStream; 037import java.io.Serializable; 038import java.util.Arrays; 039import java.util.BitSet; 040import java.util.Collection; 041import java.util.Collections; 042import java.util.Comparator; 043import java.util.EnumMap; 044import java.util.HashSet; 045import java.util.Iterator; 046import java.util.Map; 047import java.util.Set; 048import java.util.SortedMap; 049import java.util.Spliterator; 050import java.util.Spliterators; 051import java.util.function.BiFunction; 052import java.util.function.BinaryOperator; 053import java.util.function.Function; 054import java.util.stream.Collector; 055import java.util.stream.Collectors; 056import javax.annotation.CheckForNull; 057import org.checkerframework.checker.nullness.qual.Nullable; 058 059/** 060 * A {@link Map} whose contents will never change, with many other important properties detailed at 061 * {@link ImmutableCollection}. 062 * 063 * <p>See the Guava User Guide article on <a href= 064 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>. 065 * 066 * @author Jesse Wilson 067 * @author Kevin Bourrillion 068 * @since 2.0 069 */ 070@DoNotMock("Use ImmutableMap.of or another implementation") 071@GwtCompatible(serializable = true, emulated = true) 072@SuppressWarnings("serial") // we're overriding default serialization 073@ElementTypesAreNonnullByDefault 074public abstract class ImmutableMap<K, V> implements Map<K, V>, Serializable { 075 076 /** 077 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys 078 * and values are the result of applying the provided mapping functions to the input elements. 079 * Entries appear in the result {@code ImmutableMap} in encounter order. 080 * 081 * <p>If the mapped keys contain duplicates (according to {@link Object#equals(Object)}, an {@code 082 * IllegalArgumentException} is thrown when the collection operation is performed. (This differs 083 * from the {@code Collector} returned by {@link Collectors#toMap(Function, Function)}, which 084 * throws an {@code IllegalStateException}.) 085 * 086 * @since 21.0 087 */ 088 public static <T extends @Nullable Object, K, V> 089 Collector<T, ?, ImmutableMap<K, V>> toImmutableMap( 090 Function<? super T, ? extends K> keyFunction, 091 Function<? super T, ? extends V> valueFunction) { 092 return CollectCollectors.toImmutableMap(keyFunction, valueFunction); 093 } 094 095 /** 096 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys 097 * and values are the result of applying the provided mapping functions to the input elements. 098 * 099 * <p>If the mapped keys contain duplicates (according to {@link Object#equals(Object)}), the 100 * values are merged using the specified merging function. If the merging function returns {@code 101 * null}, then the collector removes the value that has been computed for the key thus far (though 102 * future occurrences of the key would reinsert it). 103 * 104 * <p>Entries will appear in the encounter order of the first occurrence of the key. 105 * 106 * @since 21.0 107 */ 108 public static <T extends @Nullable Object, K, V> 109 Collector<T, ?, ImmutableMap<K, V>> toImmutableMap( 110 Function<? super T, ? extends K> keyFunction, 111 Function<? super T, ? extends V> valueFunction, 112 BinaryOperator<V> mergeFunction) { 113 return CollectCollectors.toImmutableMap(keyFunction, valueFunction, mergeFunction); 114 } 115 116 /** 117 * Returns the empty map. This map behaves and performs comparably to {@link 118 * Collections#emptyMap}, and is preferable mainly for consistency and maintainability of your 119 * code. 120 * 121 * <p><b>Performance note:</b> the instance returned is a singleton. 122 */ 123 @SuppressWarnings("unchecked") 124 public static <K, V> ImmutableMap<K, V> of() { 125 return (ImmutableMap<K, V>) RegularImmutableMap.EMPTY; 126 } 127 128 /** 129 * Returns an immutable map containing a single entry. This map behaves and performs comparably to 130 * {@link Collections#singletonMap} but will not accept a null key or value. It is preferable 131 * mainly for consistency and maintainability of your code. 132 */ 133 public static <K, V> ImmutableMap<K, V> of(K k1, V v1) { 134 return ImmutableBiMap.of(k1, v1); 135 } 136 137 /** 138 * Returns an immutable map containing the given entries, in order. 139 * 140 * @throws IllegalArgumentException if duplicate keys are provided 141 */ 142 public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2) { 143 return RegularImmutableMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2)); 144 } 145 146 /** 147 * Returns an immutable map containing the given entries, in order. 148 * 149 * @throws IllegalArgumentException if duplicate keys are provided 150 */ 151 public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) { 152 return RegularImmutableMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3)); 153 } 154 155 /** 156 * Returns an immutable map containing the given entries, in order. 157 * 158 * @throws IllegalArgumentException if duplicate keys are provided 159 */ 160 public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 161 return RegularImmutableMap.fromEntries( 162 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4)); 163 } 164 165 /** 166 * Returns an immutable map containing the given entries, in order. 167 * 168 * @throws IllegalArgumentException if duplicate keys are provided 169 */ 170 public static <K, V> ImmutableMap<K, V> of( 171 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { 172 return RegularImmutableMap.fromEntries( 173 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5)); 174 } 175 176 /** 177 * Returns an immutable map containing the given entries, in order. 178 * 179 * @throws IllegalArgumentException if duplicate keys are provided 180 * @since 31.0 181 */ 182 public static <K, V> ImmutableMap<K, V> of( 183 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6) { 184 return RegularImmutableMap.fromEntries( 185 entryOf(k1, v1), 186 entryOf(k2, v2), 187 entryOf(k3, v3), 188 entryOf(k4, v4), 189 entryOf(k5, v5), 190 entryOf(k6, v6)); 191 } 192 193 /** 194 * Returns an immutable map containing the given entries, in order. 195 * 196 * @throws IllegalArgumentException if duplicate keys are provided 197 * @since 31.0 198 */ 199 public static <K, V> ImmutableMap<K, V> of( 200 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7) { 201 return RegularImmutableMap.fromEntries( 202 entryOf(k1, v1), 203 entryOf(k2, v2), 204 entryOf(k3, v3), 205 entryOf(k4, v4), 206 entryOf(k5, v5), 207 entryOf(k6, v6), 208 entryOf(k7, v7)); 209 } 210 211 /** 212 * Returns an immutable map containing the given entries, in order. 213 * 214 * @throws IllegalArgumentException if duplicate keys are provided 215 * @since 31.0 216 */ 217 public static <K, V> ImmutableMap<K, V> of( 218 K k1, 219 V v1, 220 K k2, 221 V v2, 222 K k3, 223 V v3, 224 K k4, 225 V v4, 226 K k5, 227 V v5, 228 K k6, 229 V v6, 230 K k7, 231 V v7, 232 K k8, 233 V v8) { 234 return RegularImmutableMap.fromEntries( 235 entryOf(k1, v1), 236 entryOf(k2, v2), 237 entryOf(k3, v3), 238 entryOf(k4, v4), 239 entryOf(k5, v5), 240 entryOf(k6, v6), 241 entryOf(k7, v7), 242 entryOf(k8, v8)); 243 } 244 245 /** 246 * Returns an immutable map containing the given entries, in order. 247 * 248 * @throws IllegalArgumentException if duplicate keys are provided 249 * @since 31.0 250 */ 251 public static <K, V> ImmutableMap<K, V> of( 252 K k1, 253 V v1, 254 K k2, 255 V v2, 256 K k3, 257 V v3, 258 K k4, 259 V v4, 260 K k5, 261 V v5, 262 K k6, 263 V v6, 264 K k7, 265 V v7, 266 K k8, 267 V v8, 268 K k9, 269 V v9) { 270 return RegularImmutableMap.fromEntries( 271 entryOf(k1, v1), 272 entryOf(k2, v2), 273 entryOf(k3, v3), 274 entryOf(k4, v4), 275 entryOf(k5, v5), 276 entryOf(k6, v6), 277 entryOf(k7, v7), 278 entryOf(k8, v8), 279 entryOf(k9, v9)); 280 } 281 282 /** 283 * Returns an immutable map containing the given entries, in order. 284 * 285 * @throws IllegalArgumentException if duplicate keys are provided 286 * @since 31.0 287 */ 288 public static <K, V> ImmutableMap<K, V> of( 289 K k1, 290 V v1, 291 K k2, 292 V v2, 293 K k3, 294 V v3, 295 K k4, 296 V v4, 297 K k5, 298 V v5, 299 K k6, 300 V v6, 301 K k7, 302 V v7, 303 K k8, 304 V v8, 305 K k9, 306 V v9, 307 K k10, 308 V v10) { 309 return RegularImmutableMap.fromEntries( 310 entryOf(k1, v1), 311 entryOf(k2, v2), 312 entryOf(k3, v3), 313 entryOf(k4, v4), 314 entryOf(k5, v5), 315 entryOf(k6, v6), 316 entryOf(k7, v7), 317 entryOf(k8, v8), 318 entryOf(k9, v9), 319 entryOf(k10, v10)); 320 } 321 322 // looking for of() with > 10 entries? Use the builder or ofEntries instead. 323 324 /** 325 * Returns an immutable map containing the given entries, in order. 326 * 327 * @throws IllegalArgumentException if duplicate keys are provided 328 * @since 31.0 329 */ 330 @SafeVarargs 331 public static <K, V> ImmutableMap<K, V> ofEntries(Entry<? extends K, ? extends V>... entries) { 332 @SuppressWarnings("unchecked") // we will only ever read these 333 Entry<K, V>[] entries2 = (Entry<K, V>[]) entries; 334 return RegularImmutableMap.fromEntries(entries2); 335 } 336 337 /** 338 * Verifies that {@code key} and {@code value} are non-null, and returns a new immutable entry 339 * with those values. 340 * 341 * <p>A call to {@link Entry#setValue} on the returned entry will always throw {@link 342 * UnsupportedOperationException}. 343 */ 344 static <K, V> Entry<K, V> entryOf(K key, V value) { 345 return new ImmutableMapEntry<>(key, value); 346 } 347 348 /** 349 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link 350 * Builder} constructor. 351 */ 352 public static <K, V> Builder<K, V> builder() { 353 return new Builder<>(); 354 } 355 356 /** 357 * Returns a new builder, expecting the specified number of entries to be added. 358 * 359 * <p>If {@code expectedSize} is exactly the number of entries added to the builder before {@link 360 * Builder#build} is called, the builder is likely to perform better than an unsized {@link 361 * #builder()} would have. 362 * 363 * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to, 364 * but not exactly, the number of entries added to the builder. 365 * 366 * @since 23.1 367 */ 368 public static <K, V> Builder<K, V> builderWithExpectedSize(int expectedSize) { 369 checkNonnegative(expectedSize, "expectedSize"); 370 return new Builder<>(expectedSize); 371 } 372 373 static void checkNoConflict( 374 boolean safe, String conflictDescription, Object entry1, Object entry2) { 375 if (!safe) { 376 throw conflictException(conflictDescription, entry1, entry2); 377 } 378 } 379 380 static IllegalArgumentException conflictException( 381 String conflictDescription, Object entry1, Object entry2) { 382 return new IllegalArgumentException( 383 "Multiple entries with same " + conflictDescription + ": " + entry1 + " and " + entry2); 384 } 385 386 /** 387 * A builder for creating immutable map instances, especially {@code public static final} maps 388 * ("constant maps"). Example: 389 * 390 * <pre>{@code 391 * static final ImmutableMap<String, Integer> WORD_TO_INT = 392 * new ImmutableMap.Builder<String, Integer>() 393 * .put("one", 1) 394 * .put("two", 2) 395 * .put("three", 3) 396 * .buildOrThrow(); 397 * }</pre> 398 * 399 * <p>For <i>small</i> immutable maps, the {@code ImmutableMap.of()} methods are even more 400 * convenient. 401 * 402 * <p>By default, a {@code Builder} will generate maps that iterate over entries in the order they 403 * were inserted into the builder, equivalently to {@code LinkedHashMap}. For example, in the 404 * above example, {@code WORD_TO_INT.entrySet()} is guaranteed to iterate over the entries in the 405 * order {@code "one"=1, "two"=2, "three"=3}, and {@code keySet()} and {@code values()} respect 406 * the same order. If you want a different order, consider using {@link ImmutableSortedMap} to 407 * sort by keys, or call {@link #orderEntriesByValue(Comparator)}, which changes this builder to 408 * sort entries by value. 409 * 410 * <p>Builder instances can be reused - it is safe to call {@link #buildOrThrow} multiple times to 411 * build multiple maps in series. Each map is a superset of the maps created before it. 412 * 413 * @since 2.0 414 */ 415 @DoNotMock 416 public static class Builder<K, V> { 417 @CheckForNull Comparator<? super V> valueComparator; 418 @Nullable Entry<K, V>[] entries; 419 int size; 420 boolean entriesUsed; 421 422 /** 423 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 424 * ImmutableMap#builder}. 425 */ 426 public Builder() { 427 this(ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY); 428 } 429 430 @SuppressWarnings({"unchecked", "rawtypes"}) 431 Builder(int initialCapacity) { 432 this.entries = new @Nullable Entry[initialCapacity]; 433 this.size = 0; 434 this.entriesUsed = false; 435 } 436 437 private void ensureCapacity(int minCapacity) { 438 if (minCapacity > entries.length) { 439 entries = 440 Arrays.copyOf( 441 entries, ImmutableCollection.Builder.expandedCapacity(entries.length, minCapacity)); 442 entriesUsed = false; 443 } 444 } 445 446 /** 447 * Associates {@code key} with {@code value} in the built map. If the same key is put more than 448 * once, {@link #buildOrThrow} will fail, while {@link #buildKeepingLast} will keep the last 449 * value put for that key. 450 */ 451 @CanIgnoreReturnValue 452 public Builder<K, V> put(K key, V value) { 453 ensureCapacity(size + 1); 454 Entry<K, V> entry = entryOf(key, value); 455 // don't inline this: we want to fail atomically if key or value is null 456 entries[size++] = entry; 457 return this; 458 } 459 460 /** 461 * Adds the given {@code entry} to the map, making it immutable if necessary. If the same key is 462 * put more than once, {@link #buildOrThrow} will fail, while {@link #buildKeepingLast} will 463 * keep the last value put for that key. 464 * 465 * @since 11.0 466 */ 467 @CanIgnoreReturnValue 468 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) { 469 return put(entry.getKey(), entry.getValue()); 470 } 471 472 /** 473 * Associates all of the given map's keys and values in the built map. If the same key is put 474 * more than once, {@link #buildOrThrow} will fail, while {@link #buildKeepingLast} will keep 475 * the last value put for that key. 476 * 477 * @throws NullPointerException if any key or value in {@code map} is null 478 */ 479 @CanIgnoreReturnValue 480 public Builder<K, V> putAll(Map<? extends K, ? extends V> map) { 481 return putAll(map.entrySet()); 482 } 483 484 /** 485 * Adds all of the given entries to the built map. If the same key is put more than once, {@link 486 * #buildOrThrow} will fail, while {@link #buildKeepingLast} will keep the last value put for 487 * that key. 488 * 489 * @throws NullPointerException if any key, value, or entry is null 490 * @since 19.0 491 */ 492 @CanIgnoreReturnValue 493 public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) { 494 if (entries instanceof Collection) { 495 ensureCapacity(size + ((Collection<?>) entries).size()); 496 } 497 for (Entry<? extends K, ? extends V> entry : entries) { 498 put(entry); 499 } 500 return this; 501 } 502 503 /** 504 * Configures this {@code Builder} to order entries by value according to the specified 505 * comparator. 506 * 507 * <p>The sort order is stable, that is, if two entries have values that compare as equivalent, 508 * the entry that was inserted first will be first in the built map's iteration order. 509 * 510 * @throws IllegalStateException if this method was already called 511 * @since 19.0 512 */ 513 @CanIgnoreReturnValue 514 public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) { 515 checkState(this.valueComparator == null, "valueComparator was already set"); 516 this.valueComparator = checkNotNull(valueComparator, "valueComparator"); 517 return this; 518 } 519 520 @CanIgnoreReturnValue 521 Builder<K, V> combine(Builder<K, V> other) { 522 checkNotNull(other); 523 ensureCapacity(this.size + other.size); 524 System.arraycopy(other.entries, 0, this.entries, this.size, other.size); 525 this.size += other.size; 526 return this; 527 } 528 529 private ImmutableMap<K, V> build(boolean throwIfDuplicateKeys) { 530 /* 531 * If entries is full, or if hash flooding is detected, then this implementation may end up 532 * using the entries array directly and writing over the entry objects with non-terminal 533 * entries, but this is safe; if this Builder is used further, it will grow the entries array 534 * (so it can't affect the original array), and future build() calls will always copy any 535 * entry objects that cannot be safely reused. 536 */ 537 switch (size) { 538 case 0: 539 return of(); 540 case 1: 541 // requireNonNull is safe because the first `size` elements have been filled in. 542 Entry<K, V> onlyEntry = requireNonNull(entries[0]); 543 return of(onlyEntry.getKey(), onlyEntry.getValue()); 544 default: 545 break; 546 } 547 // localEntries is an alias for the entries field, except if we end up removing duplicates in 548 // a copy of the entries array. Likewise, localSize is the same as size except in that case. 549 // It's possible to keep using this Builder after calling buildKeepingLast(), so we need to 550 // ensure that its state is not corrupted by removing duplicates that should cause a later 551 // buildOrThrow() to fail, or by changing the size. 552 @Nullable Entry<K, V>[] localEntries; 553 int localSize = size; 554 if (valueComparator == null) { 555 localEntries = entries; 556 } else { 557 if (entriesUsed) { 558 entries = Arrays.copyOf(entries, size); 559 } 560 @SuppressWarnings("nullness") // entries 0..localSize-1 are non-null 561 Entry<K, V>[] nonNullEntries = (Entry<K, V>[]) entries; 562 if (!throwIfDuplicateKeys) { 563 // We want to retain only the last-put value for any given key, before sorting. 564 // This could be improved, but orderEntriesByValue is rather rarely used anyway. 565 Entry<K, V>[] lastEntryForEachKey = lastEntryForEachKey(nonNullEntries, size); 566 if (lastEntryForEachKey != null) { 567 nonNullEntries = lastEntryForEachKey; 568 localSize = lastEntryForEachKey.length; 569 } 570 } 571 Arrays.sort( 572 nonNullEntries, 573 0, 574 localSize, 575 Ordering.from(valueComparator).onResultOf(Maps.<V>valueFunction())); 576 localEntries = (@Nullable Entry<K, V>[]) nonNullEntries; 577 } 578 entriesUsed = true; 579 return RegularImmutableMap.fromEntryArray(localSize, localEntries, throwIfDuplicateKeys); 580 } 581 582 /** 583 * Returns a newly-created immutable map. The iteration order of the returned map is the order 584 * in which entries were inserted into the builder, unless {@link #orderEntriesByValue} was 585 * called, in which case entries are sorted by value. 586 * 587 * <p>Prefer the equivalent method {@link #buildOrThrow()} to make it explicit that the method 588 * will throw an exception if there are duplicate keys. The {@code build()} method will soon be 589 * deprecated. 590 * 591 * @throws IllegalArgumentException if duplicate keys were added 592 */ 593 public ImmutableMap<K, V> build() { 594 return buildOrThrow(); 595 } 596 597 /** 598 * Returns a newly-created immutable map, or throws an exception if any key was added more than 599 * once. The iteration order of the returned map is the order in which entries were inserted 600 * into the builder, unless {@link #orderEntriesByValue} was called, in which case entries are 601 * sorted by value. 602 * 603 * @throws IllegalArgumentException if duplicate keys were added 604 * @since 31.0 605 */ 606 public ImmutableMap<K, V> buildOrThrow() { 607 return build(true); 608 } 609 610 /** 611 * Returns a newly-created immutable map, using the last value for any key that was added more 612 * than once. The iteration order of the returned map is the order in which entries were 613 * inserted into the builder, unless {@link #orderEntriesByValue} was called, in which case 614 * entries are sorted by value. If a key was added more than once, it appears in iteration order 615 * based on the first time it was added, again unless {@link #orderEntriesByValue} was called. 616 * 617 * <p>In the current implementation, all values associated with a given key are stored in the 618 * {@code Builder} object, even though only one of them will be used in the built map. If there 619 * can be many repeated keys, it may be more space-efficient to use a {@link 620 * java.util.LinkedHashMap LinkedHashMap} and {@link ImmutableMap#copyOf(Map)} rather than 621 * {@code ImmutableMap.Builder}. 622 * 623 * @since 31.1 624 */ 625 public ImmutableMap<K, V> buildKeepingLast() { 626 return build(false); 627 } 628 629 @VisibleForTesting // only for testing JDK backed implementation 630 ImmutableMap<K, V> buildJdkBacked() { 631 checkState( 632 valueComparator == null, "buildJdkBacked is only for testing; can't use valueComparator"); 633 switch (size) { 634 case 0: 635 return of(); 636 case 1: 637 // requireNonNull is safe because the first `size` elements have been filled in. 638 Entry<K, V> onlyEntry = requireNonNull(entries[0]); 639 return of(onlyEntry.getKey(), onlyEntry.getValue()); 640 default: 641 entriesUsed = true; 642 return JdkBackedImmutableMap.create(size, entries, /* throwIfDuplicateKeys= */ true); 643 } 644 } 645 646 /** 647 * Scans the first {@code size} elements of {@code entries} looking for duplicate keys. If 648 * duplicates are found, a new correctly-sized array is returned with the same elements (up to 649 * {@code size}), except containing only the last occurrence of each duplicate key. Otherwise 650 * {@code null} is returned. 651 */ 652 @CheckForNull 653 private static <K, V> Entry<K, V>[] lastEntryForEachKey(Entry<K, V>[] entries, int size) { 654 Set<K> seen = new HashSet<>(); 655 BitSet dups = new BitSet(); // slots that are overridden by a later duplicate key 656 for (int i = size - 1; i >= 0; i--) { 657 if (!seen.add(entries[i].getKey())) { 658 dups.set(i); 659 } 660 } 661 if (dups.isEmpty()) { 662 return null; 663 } 664 @SuppressWarnings({"rawtypes", "unchecked"}) 665 Entry<K, V>[] newEntries = new Entry[size - dups.cardinality()]; 666 for (int inI = 0, outI = 0; inI < size; inI++) { 667 if (!dups.get(inI)) { 668 newEntries[outI++] = entries[inI]; 669 } 670 } 671 return newEntries; 672 } 673 } 674 675 /** 676 * Returns an immutable map containing the same entries as {@code map}. The returned map iterates 677 * over entries in the same order as the {@code entrySet} of the original map. If {@code map} 678 * somehow contains entries with duplicate keys (for example, if it is a {@code SortedMap} whose 679 * comparator is not <i>consistent with equals</i>), the results of this method are undefined. 680 * 681 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 682 * safe to do so. The exact circumstances under which a copy will or will not be performed are 683 * undocumented and subject to change. 684 * 685 * @throws NullPointerException if any key or value in {@code map} is null 686 */ 687 public static <K, V> ImmutableMap<K, V> copyOf(Map<? extends K, ? extends V> map) { 688 if ((map instanceof ImmutableMap) && !(map instanceof SortedMap)) { 689 @SuppressWarnings("unchecked") // safe since map is not writable 690 ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) map; 691 if (!kvMap.isPartialView()) { 692 return kvMap; 693 } 694 } else if (map instanceof EnumMap) { 695 @SuppressWarnings("unchecked") // safe since map is not writable 696 ImmutableMap<K, V> kvMap = 697 (ImmutableMap<K, V>) 698 copyOfEnumMap( 699 (EnumMap<?, ? extends V>) map); // hide K (violates bounds) from J2KT, preserve V. 700 return kvMap; 701 } 702 return copyOf(map.entrySet()); 703 } 704 705 /** 706 * Returns an immutable map containing the specified entries. The returned map iterates over 707 * entries in the same order as the original iterable. 708 * 709 * @throws NullPointerException if any key, value, or entry is null 710 * @throws IllegalArgumentException if two entries have the same key 711 * @since 19.0 712 */ 713 public static <K, V> ImmutableMap<K, V> copyOf( 714 Iterable<? extends Entry<? extends K, ? extends V>> entries) { 715 @SuppressWarnings("unchecked") // we'll only be using getKey and getValue, which are covariant 716 Entry<K, V>[] entryArray = (Entry<K, V>[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY); 717 switch (entryArray.length) { 718 case 0: 719 return of(); 720 case 1: 721 // requireNonNull is safe because the first `size` elements have been filled in. 722 Entry<K, V> onlyEntry = requireNonNull(entryArray[0]); 723 return of(onlyEntry.getKey(), onlyEntry.getValue()); 724 default: 725 /* 726 * The current implementation will end up using entryArray directly, though it will write 727 * over the (arbitrary, potentially mutable) Entry objects actually stored in entryArray. 728 */ 729 return RegularImmutableMap.fromEntries(entryArray); 730 } 731 } 732 733 private static <K extends Enum<K>, V> ImmutableMap<K, ? extends V> copyOfEnumMap( 734 EnumMap<?, ? extends V> original) { 735 @SuppressWarnings("unchecked") // the best we could do to make copyOf(Map) compile 736 EnumMap<K, V> copy = new EnumMap<>((EnumMap<K, ? extends V>) original); 737 for (Entry<K, V> entry : copy.entrySet()) { 738 checkEntryNotNull(entry.getKey(), entry.getValue()); 739 } 740 return ImmutableEnumMap.asImmutable(copy); 741 } 742 743 static final Entry<?, ?>[] EMPTY_ENTRY_ARRAY = new Entry<?, ?>[0]; 744 745 abstract static class IteratorBasedImmutableMap<K, V> extends ImmutableMap<K, V> { 746 abstract UnmodifiableIterator<Entry<K, V>> entryIterator(); 747 748 Spliterator<Entry<K, V>> entrySpliterator() { 749 return Spliterators.spliterator( 750 entryIterator(), 751 size(), 752 Spliterator.DISTINCT | Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.ORDERED); 753 } 754 755 @Override 756 ImmutableSet<K> createKeySet() { 757 return new ImmutableMapKeySet<>(this); 758 } 759 760 @Override 761 ImmutableSet<Entry<K, V>> createEntrySet() { 762 class EntrySetImpl extends ImmutableMapEntrySet<K, V> { 763 @Override 764 ImmutableMap<K, V> map() { 765 return IteratorBasedImmutableMap.this; 766 } 767 768 @Override 769 public UnmodifiableIterator<Entry<K, V>> iterator() { 770 return entryIterator(); 771 } 772 773 // redeclare to help optimizers with b/310253115 774 @SuppressWarnings("RedundantOverride") 775 @Override 776 @J2ktIncompatible // serialization 777 @GwtIncompatible // serialization 778 Object writeReplace() { 779 return super.writeReplace(); 780 } 781 } 782 return new EntrySetImpl(); 783 } 784 785 @Override 786 ImmutableCollection<V> createValues() { 787 return new ImmutableMapValues<>(this); 788 } 789 790 // redeclare to help optimizers with b/310253115 791 @SuppressWarnings("RedundantOverride") 792 @Override 793 @J2ktIncompatible // serialization 794 @GwtIncompatible // serialization 795 Object writeReplace() { 796 return super.writeReplace(); 797 } 798 } 799 800 ImmutableMap() {} 801 802 /** 803 * Guaranteed to throw an exception and leave the map unmodified. 804 * 805 * @throws UnsupportedOperationException always 806 * @deprecated Unsupported operation. 807 */ 808 @CanIgnoreReturnValue 809 @Deprecated 810 @Override 811 @DoNotCall("Always throws UnsupportedOperationException") 812 @CheckForNull 813 public final V put(K k, V v) { 814 throw new UnsupportedOperationException(); 815 } 816 817 /** 818 * Guaranteed to throw an exception and leave the map unmodified. 819 * 820 * @throws UnsupportedOperationException always 821 * @deprecated Unsupported operation. 822 */ 823 @CanIgnoreReturnValue 824 @Deprecated 825 @Override 826 @DoNotCall("Always throws UnsupportedOperationException") 827 @CheckForNull 828 public final V putIfAbsent(K key, V value) { 829 throw new UnsupportedOperationException(); 830 } 831 832 /** 833 * Guaranteed to throw an exception and leave the map unmodified. 834 * 835 * @throws UnsupportedOperationException always 836 * @deprecated Unsupported operation. 837 */ 838 @Deprecated 839 @Override 840 @DoNotCall("Always throws UnsupportedOperationException") 841 public final boolean replace(K key, V oldValue, V newValue) { 842 throw new UnsupportedOperationException(); 843 } 844 845 /** 846 * Guaranteed to throw an exception and leave the map unmodified. 847 * 848 * @throws UnsupportedOperationException always 849 * @deprecated Unsupported operation. 850 */ 851 @Deprecated 852 @Override 853 @CheckForNull 854 @DoNotCall("Always throws UnsupportedOperationException") 855 public final V replace(K key, V value) { 856 throw new UnsupportedOperationException(); 857 } 858 859 /** 860 * Guaranteed to throw an exception and leave the map unmodified. 861 * 862 * @throws UnsupportedOperationException always 863 * @deprecated Unsupported operation. 864 */ 865 @Deprecated 866 @Override 867 @DoNotCall("Always throws UnsupportedOperationException") 868 public final V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { 869 throw new UnsupportedOperationException(); 870 } 871 872 /** 873 * Guaranteed to throw an exception and leave the map unmodified. 874 * 875 * @throws UnsupportedOperationException always 876 * @deprecated Unsupported operation. 877 */ 878 @Deprecated 879 @Override 880 @DoNotCall("Always throws UnsupportedOperationException") 881 @CheckForNull 882 public final V computeIfPresent( 883 K key, BiFunction<? super K, ? super V, ? extends @Nullable V> remappingFunction) { 884 throw new UnsupportedOperationException(); 885 } 886 887 /** 888 * Guaranteed to throw an exception and leave the map unmodified. 889 * 890 * @throws UnsupportedOperationException always 891 * @deprecated Unsupported operation. 892 */ 893 @Deprecated 894 @Override 895 @DoNotCall("Always throws UnsupportedOperationException") 896 @CheckForNull 897 public final V compute( 898 K key, BiFunction<? super K, ? super @Nullable V, ? extends @Nullable V> remappingFunction) { 899 throw new UnsupportedOperationException(); 900 } 901 902 /** 903 * Guaranteed to throw an exception and leave the map unmodified. 904 * 905 * @throws UnsupportedOperationException always 906 * @deprecated Unsupported operation. 907 */ 908 @Deprecated 909 @Override 910 @DoNotCall("Always throws UnsupportedOperationException") 911 @CheckForNull 912 public final V merge( 913 K key, V value, BiFunction<? super V, ? super V, ? extends @Nullable V> function) { 914 throw new UnsupportedOperationException(); 915 } 916 917 /** 918 * Guaranteed to throw an exception and leave the map unmodified. 919 * 920 * @throws UnsupportedOperationException always 921 * @deprecated Unsupported operation. 922 */ 923 @Deprecated 924 @Override 925 @DoNotCall("Always throws UnsupportedOperationException") 926 public final void putAll(Map<? extends K, ? extends V> map) { 927 throw new UnsupportedOperationException(); 928 } 929 930 /** 931 * Guaranteed to throw an exception and leave the map unmodified. 932 * 933 * @throws UnsupportedOperationException always 934 * @deprecated Unsupported operation. 935 */ 936 @Deprecated 937 @Override 938 @DoNotCall("Always throws UnsupportedOperationException") 939 public final void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 940 throw new UnsupportedOperationException(); 941 } 942 943 /** 944 * Guaranteed to throw an exception and leave the map unmodified. 945 * 946 * @throws UnsupportedOperationException always 947 * @deprecated Unsupported operation. 948 */ 949 @Deprecated 950 @Override 951 @DoNotCall("Always throws UnsupportedOperationException") 952 @CheckForNull 953 public final V remove(@CheckForNull Object o) { 954 throw new UnsupportedOperationException(); 955 } 956 957 /** 958 * Guaranteed to throw an exception and leave the map unmodified. 959 * 960 * @throws UnsupportedOperationException always 961 * @deprecated Unsupported operation. 962 */ 963 @Deprecated 964 @Override 965 @DoNotCall("Always throws UnsupportedOperationException") 966 public final boolean remove(@CheckForNull Object key, @CheckForNull Object value) { 967 throw new UnsupportedOperationException(); 968 } 969 970 /** 971 * Guaranteed to throw an exception and leave the map unmodified. 972 * 973 * @throws UnsupportedOperationException always 974 * @deprecated Unsupported operation. 975 */ 976 @Deprecated 977 @Override 978 @DoNotCall("Always throws UnsupportedOperationException") 979 public final void clear() { 980 throw new UnsupportedOperationException(); 981 } 982 983 @Override 984 public boolean isEmpty() { 985 return size() == 0; 986 } 987 988 @Override 989 public boolean containsKey(@CheckForNull Object key) { 990 return get(key) != null; 991 } 992 993 @Override 994 public boolean containsValue(@CheckForNull Object value) { 995 return values().contains(value); 996 } 997 998 // Overriding to mark it Nullable 999 @Override 1000 @CheckForNull 1001 public abstract V get(@CheckForNull Object key); 1002 1003 /** 1004 * @since 21.0 (but only since 23.5 in the Android <a 1005 * href="https://github.com/google/guava#guava-google-core-libraries-for-java">flavor</a>). 1006 * Note, however, that Java 8+ users can call this method with any version and flavor of 1007 * Guava. 1008 */ 1009 @Override 1010 @CheckForNull 1011 public final V getOrDefault(@CheckForNull Object key, @CheckForNull V defaultValue) { 1012 /* 1013 * Even though it's weird to pass a defaultValue that is null, some callers do so. Those who 1014 * pass a literal "null" should probably just use `get`, but I would expect other callers to 1015 * pass an expression that *might* be null. This could happen with: 1016 * 1017 * - a `getFooOrDefault(@CheckForNull Foo defaultValue)` method that returns 1018 * `map.getOrDefault(FOO_KEY, defaultValue)` 1019 * 1020 * - a call that consults a chain of maps, as in `mapA.getOrDefault(key, mapB.getOrDefault(key, 1021 * ...))` 1022 * 1023 * So it makes sense for the parameter (and thus the return type) to be @CheckForNull. 1024 * 1025 * Two other points: 1026 * 1027 * 1. We'll want to use something like @PolyNull once we can make that work for the various 1028 * platforms we target. 1029 * 1030 * 2. Kotlin's Map type has a getOrDefault method that accepts and returns a "plain V," in 1031 * contrast to the "V?" type that we're using. As a result, Kotlin sees a conflict between the 1032 * nullness annotations in ImmutableMap and those in its own Map type. In response, it considers 1033 * the parameter and return type both to be platform types. As a result, Kotlin permits calls 1034 * that can lead to NullPointerException. That's unfortunate. But hopefully most Kotlin callers 1035 * use `get(key) ?: defaultValue` instead of this method, anyway. 1036 */ 1037 V result = get(key); 1038 // TODO(b/192579700): Use a ternary once it no longer confuses our nullness checker. 1039 if (result != null) { 1040 return result; 1041 } else { 1042 return defaultValue; 1043 } 1044 } 1045 1046 @LazyInit @RetainedWith @CheckForNull private transient ImmutableSet<Entry<K, V>> entrySet; 1047 1048 /** 1049 * Returns an immutable set of the mappings in this map. The iteration order is specified by the 1050 * method used to create this map. Typically, this is insertion order. 1051 */ 1052 @Override 1053 public ImmutableSet<Entry<K, V>> entrySet() { 1054 ImmutableSet<Entry<K, V>> result = entrySet; 1055 return (result == null) ? entrySet = createEntrySet() : result; 1056 } 1057 1058 abstract ImmutableSet<Entry<K, V>> createEntrySet(); 1059 1060 @LazyInit @RetainedWith @CheckForNull private transient ImmutableSet<K> keySet; 1061 1062 /** 1063 * Returns an immutable set of the keys in this map, in the same order that they appear in {@link 1064 * #entrySet}. 1065 */ 1066 @Override 1067 public ImmutableSet<K> keySet() { 1068 ImmutableSet<K> result = keySet; 1069 return (result == null) ? keySet = createKeySet() : result; 1070 } 1071 1072 /* 1073 * This could have a good default implementation of return new ImmutableKeySet<K, V>(this), 1074 * but ProGuard can't figure out how to eliminate that default when RegularImmutableMap 1075 * overrides it. 1076 */ 1077 abstract ImmutableSet<K> createKeySet(); 1078 1079 UnmodifiableIterator<K> keyIterator() { 1080 final UnmodifiableIterator<Entry<K, V>> entryIterator = entrySet().iterator(); 1081 return new UnmodifiableIterator<K>() { 1082 @Override 1083 public boolean hasNext() { 1084 return entryIterator.hasNext(); 1085 } 1086 1087 @Override 1088 public K next() { 1089 return entryIterator.next().getKey(); 1090 } 1091 }; 1092 } 1093 1094 Spliterator<K> keySpliterator() { 1095 return CollectSpliterators.map(entrySet().spliterator(), Entry::getKey); 1096 } 1097 1098 @LazyInit @RetainedWith @CheckForNull private transient ImmutableCollection<V> values; 1099 1100 /** 1101 * Returns an immutable collection of the values in this map, in the same order that they appear 1102 * in {@link #entrySet}. 1103 */ 1104 @Override 1105 public ImmutableCollection<V> values() { 1106 ImmutableCollection<V> result = values; 1107 return (result == null) ? values = createValues() : result; 1108 } 1109 1110 /* 1111 * This could have a good default implementation of {@code return new 1112 * ImmutableMapValues<K, V>(this)}, but ProGuard can't figure out how to eliminate that default 1113 * when RegularImmutableMap overrides it. 1114 */ 1115 abstract ImmutableCollection<V> createValues(); 1116 1117 // cached so that this.multimapView().inverse() only computes inverse once 1118 @LazyInit @CheckForNull private transient ImmutableSetMultimap<K, V> multimapView; 1119 1120 /** 1121 * Returns a multimap view of the map. 1122 * 1123 * @since 14.0 1124 */ 1125 public ImmutableSetMultimap<K, V> asMultimap() { 1126 if (isEmpty()) { 1127 return ImmutableSetMultimap.of(); 1128 } 1129 ImmutableSetMultimap<K, V> result = multimapView; 1130 return (result == null) 1131 ? (multimapView = 1132 new ImmutableSetMultimap<>(new MapViewOfValuesAsSingletonSets(), size(), null)) 1133 : result; 1134 } 1135 1136 @WeakOuter 1137 private final class MapViewOfValuesAsSingletonSets 1138 extends IteratorBasedImmutableMap<K, ImmutableSet<V>> { 1139 1140 @Override 1141 public int size() { 1142 return ImmutableMap.this.size(); 1143 } 1144 1145 @Override 1146 ImmutableSet<K> createKeySet() { 1147 return ImmutableMap.this.keySet(); 1148 } 1149 1150 @Override 1151 public boolean containsKey(@CheckForNull Object key) { 1152 return ImmutableMap.this.containsKey(key); 1153 } 1154 1155 @Override 1156 @CheckForNull 1157 public ImmutableSet<V> get(@CheckForNull Object key) { 1158 V outerValue = ImmutableMap.this.get(key); 1159 return (outerValue == null) ? null : ImmutableSet.of(outerValue); 1160 } 1161 1162 @Override 1163 boolean isPartialView() { 1164 return ImmutableMap.this.isPartialView(); 1165 } 1166 1167 @Override 1168 public int hashCode() { 1169 // ImmutableSet.of(value).hashCode() == value.hashCode(), so the hashes are the same 1170 return ImmutableMap.this.hashCode(); 1171 } 1172 1173 @Override 1174 boolean isHashCodeFast() { 1175 return ImmutableMap.this.isHashCodeFast(); 1176 } 1177 1178 @Override 1179 UnmodifiableIterator<Entry<K, ImmutableSet<V>>> entryIterator() { 1180 final Iterator<Entry<K, V>> backingIterator = ImmutableMap.this.entrySet().iterator(); 1181 return new UnmodifiableIterator<Entry<K, ImmutableSet<V>>>() { 1182 @Override 1183 public boolean hasNext() { 1184 return backingIterator.hasNext(); 1185 } 1186 1187 @Override 1188 public Entry<K, ImmutableSet<V>> next() { 1189 final Entry<K, V> backingEntry = backingIterator.next(); 1190 return new AbstractMapEntry<K, ImmutableSet<V>>() { 1191 @Override 1192 public K getKey() { 1193 return backingEntry.getKey(); 1194 } 1195 1196 @Override 1197 public ImmutableSet<V> getValue() { 1198 return ImmutableSet.of(backingEntry.getValue()); 1199 } 1200 }; 1201 } 1202 }; 1203 } 1204 1205 // redeclare to help optimizers with b/310253115 1206 @SuppressWarnings("RedundantOverride") 1207 @Override 1208 @J2ktIncompatible // serialization 1209 @GwtIncompatible // serialization 1210 Object writeReplace() { 1211 return super.writeReplace(); 1212 } 1213 } 1214 1215 @Override 1216 public boolean equals(@CheckForNull Object object) { 1217 return Maps.equalsImpl(this, object); 1218 } 1219 1220 abstract boolean isPartialView(); 1221 1222 @Override 1223 public int hashCode() { 1224 return Sets.hashCodeImpl(entrySet()); 1225 } 1226 1227 boolean isHashCodeFast() { 1228 return false; 1229 } 1230 1231 @Override 1232 public String toString() { 1233 return Maps.toStringImpl(this); 1234 } 1235 1236 /** 1237 * Serialized type for all ImmutableMap instances. It captures the logical contents and they are 1238 * reconstructed using public factory methods. This ensures that the implementation types remain 1239 * as implementation details. 1240 */ 1241 @J2ktIncompatible // serialization 1242 static class SerializedForm<K, V> implements Serializable { 1243 // This object retains references to collections returned by keySet() and value(). This saves 1244 // bytes when the both the map and its keySet or value collection are written to the same 1245 // instance of ObjectOutputStream. 1246 1247 // TODO(b/160980469): remove support for the old serialization format after some time 1248 private static final boolean USE_LEGACY_SERIALIZATION = true; 1249 1250 private final Object keys; 1251 private final Object values; 1252 1253 SerializedForm(ImmutableMap<K, V> map) { 1254 if (USE_LEGACY_SERIALIZATION) { 1255 Object[] keys = new Object[map.size()]; 1256 Object[] values = new Object[map.size()]; 1257 int i = 0; 1258 // "extends Object" works around https://github.com/typetools/checker-framework/issues/3013 1259 for (Entry<? extends Object, ? extends Object> entry : map.entrySet()) { 1260 keys[i] = entry.getKey(); 1261 values[i] = entry.getValue(); 1262 i++; 1263 } 1264 this.keys = keys; 1265 this.values = values; 1266 return; 1267 } 1268 this.keys = map.keySet(); 1269 this.values = map.values(); 1270 } 1271 1272 @SuppressWarnings("unchecked") 1273 final Object readResolve() { 1274 if (!(this.keys instanceof ImmutableSet)) { 1275 return legacyReadResolve(); 1276 } 1277 1278 ImmutableSet<K> keySet = (ImmutableSet<K>) this.keys; 1279 ImmutableCollection<V> values = (ImmutableCollection<V>) this.values; 1280 1281 Builder<K, V> builder = makeBuilder(keySet.size()); 1282 1283 UnmodifiableIterator<K> keyIter = keySet.iterator(); 1284 UnmodifiableIterator<V> valueIter = values.iterator(); 1285 1286 while (keyIter.hasNext()) { 1287 builder.put(keyIter.next(), valueIter.next()); 1288 } 1289 1290 return builder.buildOrThrow(); 1291 } 1292 1293 @SuppressWarnings("unchecked") 1294 final Object legacyReadResolve() { 1295 K[] keys = (K[]) this.keys; 1296 V[] values = (V[]) this.values; 1297 1298 Builder<K, V> builder = makeBuilder(keys.length); 1299 1300 for (int i = 0; i < keys.length; i++) { 1301 builder.put(keys[i], values[i]); 1302 } 1303 return builder.buildOrThrow(); 1304 } 1305 1306 /** 1307 * Returns a builder that builds the unserialized type. Subclasses should override this method. 1308 */ 1309 Builder<K, V> makeBuilder(int size) { 1310 return new Builder<>(size); 1311 } 1312 1313 private static final long serialVersionUID = 0; 1314 } 1315 1316 /** 1317 * Returns a serializable form of this object. Non-public subclasses should not override this 1318 * method. Publicly-accessible subclasses must override this method and should return a subclass 1319 * of SerializedForm whose readResolve() method returns objects of the subclass type. 1320 */ 1321 @J2ktIncompatible // serialization 1322 Object writeReplace() { 1323 return new SerializedForm<>(this); 1324 } 1325 1326 @J2ktIncompatible // java.io.ObjectInputStream 1327 private void readObject(ObjectInputStream stream) throws InvalidObjectException { 1328 throw new InvalidObjectException("Use SerializedForm"); 1329 } 1330 1331 private static final long serialVersionUID = 0xcafebabe; 1332}