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 nonNullEntries = lastEntryForEachKey(nonNullEntries, size); 566 localSize = nonNullEntries.length; 567 } 568 Arrays.sort( 569 nonNullEntries, 570 0, 571 localSize, 572 Ordering.from(valueComparator).onResultOf(Maps.<V>valueFunction())); 573 localEntries = (@Nullable Entry<K, V>[]) nonNullEntries; 574 } 575 entriesUsed = true; 576 return RegularImmutableMap.fromEntryArray(localSize, localEntries, throwIfDuplicateKeys); 577 } 578 579 /** 580 * Returns a newly-created immutable map. The iteration order of the returned map is the order 581 * in which entries were inserted into the builder, unless {@link #orderEntriesByValue} was 582 * called, in which case entries are sorted by value. 583 * 584 * <p>Prefer the equivalent method {@link #buildOrThrow()} to make it explicit that the method 585 * will throw an exception if there are duplicate keys. The {@code build()} method will soon be 586 * deprecated. 587 * 588 * @throws IllegalArgumentException if duplicate keys were added 589 */ 590 public ImmutableMap<K, V> build() { 591 return buildOrThrow(); 592 } 593 594 /** 595 * Returns a newly-created immutable map, or throws an exception if any key was added more than 596 * once. The iteration order of the returned map is the order in which entries were inserted 597 * into the builder, unless {@link #orderEntriesByValue} was called, in which case entries are 598 * sorted by value. 599 * 600 * @throws IllegalArgumentException if duplicate keys were added 601 * @since 31.0 602 */ 603 public ImmutableMap<K, V> buildOrThrow() { 604 return build(true); 605 } 606 607 /** 608 * Returns a newly-created immutable map, using the last value for any key that was added more 609 * than once. The iteration order of the returned map is the order in which entries were 610 * inserted into the builder, unless {@link #orderEntriesByValue} was called, in which case 611 * entries are sorted by value. If a key was added more than once, it appears in iteration order 612 * based on the first time it was added, again unless {@link #orderEntriesByValue} was called. 613 * 614 * <p>In the current implementation, all values associated with a given key are stored in the 615 * {@code Builder} object, even though only one of them will be used in the built map. If there 616 * can be many repeated keys, it may be more space-efficient to use a {@link 617 * java.util.LinkedHashMap LinkedHashMap} and {@link ImmutableMap#copyOf(Map)} rather than 618 * {@code ImmutableMap.Builder}. 619 * 620 * @since 31.1 621 */ 622 public ImmutableMap<K, V> buildKeepingLast() { 623 return build(false); 624 } 625 626 @VisibleForTesting // only for testing JDK backed implementation 627 ImmutableMap<K, V> buildJdkBacked() { 628 checkState( 629 valueComparator == null, "buildJdkBacked is only for testing; can't use valueComparator"); 630 switch (size) { 631 case 0: 632 return of(); 633 case 1: 634 // requireNonNull is safe because the first `size` elements have been filled in. 635 Entry<K, V> onlyEntry = requireNonNull(entries[0]); 636 return of(onlyEntry.getKey(), onlyEntry.getValue()); 637 default: 638 entriesUsed = true; 639 return JdkBackedImmutableMap.create(size, entries, /* throwIfDuplicateKeys= */ true); 640 } 641 } 642 643 private static <K, V> Entry<K, V>[] lastEntryForEachKey(Entry<K, V>[] entries, int size) { 644 Set<K> seen = new HashSet<>(); 645 BitSet dups = new BitSet(); // slots that are overridden by a later duplicate key 646 for (int i = size - 1; i >= 0; i--) { 647 if (!seen.add(entries[i].getKey())) { 648 dups.set(i); 649 } 650 } 651 if (dups.isEmpty()) { 652 return entries; 653 } 654 @SuppressWarnings({"rawtypes", "unchecked"}) 655 Entry<K, V>[] newEntries = new Entry[size - dups.cardinality()]; 656 for (int inI = 0, outI = 0; inI < size; inI++) { 657 if (!dups.get(inI)) { 658 newEntries[outI++] = entries[inI]; 659 } 660 } 661 return newEntries; 662 } 663 } 664 665 /** 666 * Returns an immutable map containing the same entries as {@code map}. The returned map iterates 667 * over entries in the same order as the {@code entrySet} of the original map. If {@code map} 668 * somehow contains entries with duplicate keys (for example, if it is a {@code SortedMap} whose 669 * comparator is not <i>consistent with equals</i>), the results of this method are undefined. 670 * 671 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 672 * safe to do so. The exact circumstances under which a copy will or will not be performed are 673 * undocumented and subject to change. 674 * 675 * @throws NullPointerException if any key or value in {@code map} is null 676 */ 677 public static <K, V> ImmutableMap<K, V> copyOf(Map<? extends K, ? extends V> map) { 678 if ((map instanceof ImmutableMap) && !(map instanceof SortedMap)) { 679 @SuppressWarnings("unchecked") // safe since map is not writable 680 ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) map; 681 if (!kvMap.isPartialView()) { 682 return kvMap; 683 } 684 } else if (map instanceof EnumMap) { 685 @SuppressWarnings("unchecked") // safe since map is not writable 686 ImmutableMap<K, V> kvMap = 687 (ImmutableMap<K, V>) 688 copyOfEnumMap( 689 (EnumMap<?, ? extends V>) map); // hide K (violates bounds) from J2KT, preserve V. 690 return kvMap; 691 } 692 return copyOf(map.entrySet()); 693 } 694 695 /** 696 * Returns an immutable map containing the specified entries. The returned map iterates over 697 * entries in the same order as the original iterable. 698 * 699 * @throws NullPointerException if any key, value, or entry is null 700 * @throws IllegalArgumentException if two entries have the same key 701 * @since 19.0 702 */ 703 public static <K, V> ImmutableMap<K, V> copyOf( 704 Iterable<? extends Entry<? extends K, ? extends V>> entries) { 705 @SuppressWarnings("unchecked") // we'll only be using getKey and getValue, which are covariant 706 Entry<K, V>[] entryArray = (Entry<K, V>[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY); 707 switch (entryArray.length) { 708 case 0: 709 return of(); 710 case 1: 711 // requireNonNull is safe because the first `size` elements have been filled in. 712 Entry<K, V> onlyEntry = requireNonNull(entryArray[0]); 713 return of(onlyEntry.getKey(), onlyEntry.getValue()); 714 default: 715 /* 716 * The current implementation will end up using entryArray directly, though it will write 717 * over the (arbitrary, potentially mutable) Entry objects actually stored in entryArray. 718 */ 719 return RegularImmutableMap.fromEntries(entryArray); 720 } 721 } 722 723 private static <K extends Enum<K>, V> ImmutableMap<K, ? extends V> copyOfEnumMap( 724 EnumMap<?, ? extends V> original) { 725 @SuppressWarnings("unchecked") // the best we could do to make copyOf(Map) compile 726 EnumMap<K, V> copy = new EnumMap<>((EnumMap<K, ? extends V>) original); 727 for (Entry<K, V> entry : copy.entrySet()) { 728 checkEntryNotNull(entry.getKey(), entry.getValue()); 729 } 730 return ImmutableEnumMap.asImmutable(copy); 731 } 732 733 static final Entry<?, ?>[] EMPTY_ENTRY_ARRAY = new Entry<?, ?>[0]; 734 735 abstract static class IteratorBasedImmutableMap<K, V> extends ImmutableMap<K, V> { 736 abstract UnmodifiableIterator<Entry<K, V>> entryIterator(); 737 738 Spliterator<Entry<K, V>> entrySpliterator() { 739 return Spliterators.spliterator( 740 entryIterator(), 741 size(), 742 Spliterator.DISTINCT | Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.ORDERED); 743 } 744 745 @Override 746 ImmutableSet<K> createKeySet() { 747 return new ImmutableMapKeySet<>(this); 748 } 749 750 @Override 751 ImmutableSet<Entry<K, V>> createEntrySet() { 752 class EntrySetImpl extends ImmutableMapEntrySet<K, V> { 753 @Override 754 ImmutableMap<K, V> map() { 755 return IteratorBasedImmutableMap.this; 756 } 757 758 @Override 759 public UnmodifiableIterator<Entry<K, V>> iterator() { 760 return entryIterator(); 761 } 762 763 // redeclare to help optimizers with b/310253115 764 @SuppressWarnings("RedundantOverride") 765 @Override 766 @J2ktIncompatible // serialization 767 @GwtIncompatible // serialization 768 Object writeReplace() { 769 return super.writeReplace(); 770 } 771 } 772 return new EntrySetImpl(); 773 } 774 775 @Override 776 ImmutableCollection<V> createValues() { 777 return new ImmutableMapValues<>(this); 778 } 779 780 // redeclare to help optimizers with b/310253115 781 @SuppressWarnings("RedundantOverride") 782 @Override 783 @J2ktIncompatible // serialization 784 @GwtIncompatible // serialization 785 Object writeReplace() { 786 return super.writeReplace(); 787 } 788 } 789 790 ImmutableMap() {} 791 792 /** 793 * Guaranteed to throw an exception and leave the map unmodified. 794 * 795 * @throws UnsupportedOperationException always 796 * @deprecated Unsupported operation. 797 */ 798 @CanIgnoreReturnValue 799 @Deprecated 800 @Override 801 @DoNotCall("Always throws UnsupportedOperationException") 802 @CheckForNull 803 public final V put(K k, V v) { 804 throw new UnsupportedOperationException(); 805 } 806 807 /** 808 * Guaranteed to throw an exception and leave the map unmodified. 809 * 810 * @throws UnsupportedOperationException always 811 * @deprecated Unsupported operation. 812 */ 813 @CanIgnoreReturnValue 814 @Deprecated 815 @Override 816 @DoNotCall("Always throws UnsupportedOperationException") 817 @CheckForNull 818 public final V putIfAbsent(K key, V value) { 819 throw new UnsupportedOperationException(); 820 } 821 822 /** 823 * Guaranteed to throw an exception and leave the map unmodified. 824 * 825 * @throws UnsupportedOperationException always 826 * @deprecated Unsupported operation. 827 */ 828 @Deprecated 829 @Override 830 @DoNotCall("Always throws UnsupportedOperationException") 831 public final boolean replace(K key, V oldValue, V newValue) { 832 throw new UnsupportedOperationException(); 833 } 834 835 /** 836 * Guaranteed to throw an exception and leave the map unmodified. 837 * 838 * @throws UnsupportedOperationException always 839 * @deprecated Unsupported operation. 840 */ 841 @Deprecated 842 @Override 843 @CheckForNull 844 @DoNotCall("Always throws UnsupportedOperationException") 845 public final V replace(K key, V value) { 846 throw new UnsupportedOperationException(); 847 } 848 849 /** 850 * Guaranteed to throw an exception and leave the map unmodified. 851 * 852 * @throws UnsupportedOperationException always 853 * @deprecated Unsupported operation. 854 */ 855 @Deprecated 856 @Override 857 @DoNotCall("Always throws UnsupportedOperationException") 858 public final V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { 859 throw new UnsupportedOperationException(); 860 } 861 862 /** 863 * Guaranteed to throw an exception and leave the map unmodified. 864 * 865 * @throws UnsupportedOperationException always 866 * @deprecated Unsupported operation. 867 */ 868 @Deprecated 869 @Override 870 @DoNotCall("Always throws UnsupportedOperationException") 871 @CheckForNull 872 public final V computeIfPresent( 873 K key, BiFunction<? super K, ? super V, ? extends @Nullable V> remappingFunction) { 874 throw new UnsupportedOperationException(); 875 } 876 877 /** 878 * Guaranteed to throw an exception and leave the map unmodified. 879 * 880 * @throws UnsupportedOperationException always 881 * @deprecated Unsupported operation. 882 */ 883 @Deprecated 884 @Override 885 @DoNotCall("Always throws UnsupportedOperationException") 886 @CheckForNull 887 public final V compute( 888 K key, BiFunction<? super K, ? super @Nullable V, ? extends @Nullable V> remappingFunction) { 889 throw new UnsupportedOperationException(); 890 } 891 892 /** 893 * Guaranteed to throw an exception and leave the map unmodified. 894 * 895 * @throws UnsupportedOperationException always 896 * @deprecated Unsupported operation. 897 */ 898 @Deprecated 899 @Override 900 @DoNotCall("Always throws UnsupportedOperationException") 901 @CheckForNull 902 public final V merge( 903 K key, V value, BiFunction<? super V, ? super V, ? extends @Nullable V> function) { 904 throw new UnsupportedOperationException(); 905 } 906 907 /** 908 * Guaranteed to throw an exception and leave the map unmodified. 909 * 910 * @throws UnsupportedOperationException always 911 * @deprecated Unsupported operation. 912 */ 913 @Deprecated 914 @Override 915 @DoNotCall("Always throws UnsupportedOperationException") 916 public final void putAll(Map<? extends K, ? extends V> map) { 917 throw new UnsupportedOperationException(); 918 } 919 920 /** 921 * Guaranteed to throw an exception and leave the map unmodified. 922 * 923 * @throws UnsupportedOperationException always 924 * @deprecated Unsupported operation. 925 */ 926 @Deprecated 927 @Override 928 @DoNotCall("Always throws UnsupportedOperationException") 929 public final void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 930 throw new UnsupportedOperationException(); 931 } 932 933 /** 934 * Guaranteed to throw an exception and leave the map unmodified. 935 * 936 * @throws UnsupportedOperationException always 937 * @deprecated Unsupported operation. 938 */ 939 @Deprecated 940 @Override 941 @DoNotCall("Always throws UnsupportedOperationException") 942 @CheckForNull 943 public final V remove(@CheckForNull Object o) { 944 throw new UnsupportedOperationException(); 945 } 946 947 /** 948 * Guaranteed to throw an exception and leave the map unmodified. 949 * 950 * @throws UnsupportedOperationException always 951 * @deprecated Unsupported operation. 952 */ 953 @Deprecated 954 @Override 955 @DoNotCall("Always throws UnsupportedOperationException") 956 public final boolean remove(@CheckForNull Object key, @CheckForNull Object value) { 957 throw new UnsupportedOperationException(); 958 } 959 960 /** 961 * Guaranteed to throw an exception and leave the map unmodified. 962 * 963 * @throws UnsupportedOperationException always 964 * @deprecated Unsupported operation. 965 */ 966 @Deprecated 967 @Override 968 @DoNotCall("Always throws UnsupportedOperationException") 969 public final void clear() { 970 throw new UnsupportedOperationException(); 971 } 972 973 @Override 974 public boolean isEmpty() { 975 return size() == 0; 976 } 977 978 @Override 979 public boolean containsKey(@CheckForNull Object key) { 980 return get(key) != null; 981 } 982 983 @Override 984 public boolean containsValue(@CheckForNull Object value) { 985 return values().contains(value); 986 } 987 988 // Overriding to mark it Nullable 989 @Override 990 @CheckForNull 991 public abstract V get(@CheckForNull Object key); 992 993 /** 994 * @since 21.0 (but only since 23.5 in the Android <a 995 * href="https://github.com/google/guava#guava-google-core-libraries-for-java">flavor</a>). 996 * Note, however, that Java 8+ users can call this method with any version and flavor of 997 * Guava. 998 */ 999 @Override 1000 @CheckForNull 1001 public final V getOrDefault(@CheckForNull Object key, @CheckForNull V defaultValue) { 1002 /* 1003 * Even though it's weird to pass a defaultValue that is null, some callers do so. Those who 1004 * pass a literal "null" should probably just use `get`, but I would expect other callers to 1005 * pass an expression that *might* be null. This could happen with: 1006 * 1007 * - a `getFooOrDefault(@CheckForNull Foo defaultValue)` method that returns 1008 * `map.getOrDefault(FOO_KEY, defaultValue)` 1009 * 1010 * - a call that consults a chain of maps, as in `mapA.getOrDefault(key, mapB.getOrDefault(key, 1011 * ...))` 1012 * 1013 * So it makes sense for the parameter (and thus the return type) to be @CheckForNull. 1014 * 1015 * Two other points: 1016 * 1017 * 1. We'll want to use something like @PolyNull once we can make that work for the various 1018 * platforms we target. 1019 * 1020 * 2. Kotlin's Map type has a getOrDefault method that accepts and returns a "plain V," in 1021 * contrast to the "V?" type that we're using. As a result, Kotlin sees a conflict between the 1022 * nullness annotations in ImmutableMap and those in its own Map type. In response, it considers 1023 * the parameter and return type both to be platform types. As a result, Kotlin permits calls 1024 * that can lead to NullPointerException. That's unfortunate. But hopefully most Kotlin callers 1025 * use `get(key) ?: defaultValue` instead of this method, anyway. 1026 */ 1027 V result = get(key); 1028 // TODO(b/192579700): Use a ternary once it no longer confuses our nullness checker. 1029 if (result != null) { 1030 return result; 1031 } else { 1032 return defaultValue; 1033 } 1034 } 1035 1036 @LazyInit @RetainedWith @CheckForNull private transient ImmutableSet<Entry<K, V>> entrySet; 1037 1038 /** 1039 * Returns an immutable set of the mappings in this map. The iteration order is specified by the 1040 * method used to create this map. Typically, this is insertion order. 1041 */ 1042 @Override 1043 public ImmutableSet<Entry<K, V>> entrySet() { 1044 ImmutableSet<Entry<K, V>> result = entrySet; 1045 return (result == null) ? entrySet = createEntrySet() : result; 1046 } 1047 1048 abstract ImmutableSet<Entry<K, V>> createEntrySet(); 1049 1050 @LazyInit @RetainedWith @CheckForNull private transient ImmutableSet<K> keySet; 1051 1052 /** 1053 * Returns an immutable set of the keys in this map, in the same order that they appear in {@link 1054 * #entrySet}. 1055 */ 1056 @Override 1057 public ImmutableSet<K> keySet() { 1058 ImmutableSet<K> result = keySet; 1059 return (result == null) ? keySet = createKeySet() : result; 1060 } 1061 1062 /* 1063 * This could have a good default implementation of return new ImmutableKeySet<K, V>(this), 1064 * but ProGuard can't figure out how to eliminate that default when RegularImmutableMap 1065 * overrides it. 1066 */ 1067 abstract ImmutableSet<K> createKeySet(); 1068 1069 UnmodifiableIterator<K> keyIterator() { 1070 final UnmodifiableIterator<Entry<K, V>> entryIterator = entrySet().iterator(); 1071 return new UnmodifiableIterator<K>() { 1072 @Override 1073 public boolean hasNext() { 1074 return entryIterator.hasNext(); 1075 } 1076 1077 @Override 1078 public K next() { 1079 return entryIterator.next().getKey(); 1080 } 1081 }; 1082 } 1083 1084 Spliterator<K> keySpliterator() { 1085 return CollectSpliterators.map(entrySet().spliterator(), Entry::getKey); 1086 } 1087 1088 @LazyInit @RetainedWith @CheckForNull private transient ImmutableCollection<V> values; 1089 1090 /** 1091 * Returns an immutable collection of the values in this map, in the same order that they appear 1092 * in {@link #entrySet}. 1093 */ 1094 @Override 1095 public ImmutableCollection<V> values() { 1096 ImmutableCollection<V> result = values; 1097 return (result == null) ? values = createValues() : result; 1098 } 1099 1100 /* 1101 * This could have a good default implementation of {@code return new 1102 * ImmutableMapValues<K, V>(this)}, but ProGuard can't figure out how to eliminate that default 1103 * when RegularImmutableMap overrides it. 1104 */ 1105 abstract ImmutableCollection<V> createValues(); 1106 1107 // cached so that this.multimapView().inverse() only computes inverse once 1108 @LazyInit @CheckForNull private transient ImmutableSetMultimap<K, V> multimapView; 1109 1110 /** 1111 * Returns a multimap view of the map. 1112 * 1113 * @since 14.0 1114 */ 1115 public ImmutableSetMultimap<K, V> asMultimap() { 1116 if (isEmpty()) { 1117 return ImmutableSetMultimap.of(); 1118 } 1119 ImmutableSetMultimap<K, V> result = multimapView; 1120 return (result == null) 1121 ? (multimapView = 1122 new ImmutableSetMultimap<>(new MapViewOfValuesAsSingletonSets(), size(), null)) 1123 : result; 1124 } 1125 1126 @WeakOuter 1127 private final class MapViewOfValuesAsSingletonSets 1128 extends IteratorBasedImmutableMap<K, ImmutableSet<V>> { 1129 1130 @Override 1131 public int size() { 1132 return ImmutableMap.this.size(); 1133 } 1134 1135 @Override 1136 ImmutableSet<K> createKeySet() { 1137 return ImmutableMap.this.keySet(); 1138 } 1139 1140 @Override 1141 public boolean containsKey(@CheckForNull Object key) { 1142 return ImmutableMap.this.containsKey(key); 1143 } 1144 1145 @Override 1146 @CheckForNull 1147 public ImmutableSet<V> get(@CheckForNull Object key) { 1148 V outerValue = ImmutableMap.this.get(key); 1149 return (outerValue == null) ? null : ImmutableSet.of(outerValue); 1150 } 1151 1152 @Override 1153 boolean isPartialView() { 1154 return ImmutableMap.this.isPartialView(); 1155 } 1156 1157 @Override 1158 public int hashCode() { 1159 // ImmutableSet.of(value).hashCode() == value.hashCode(), so the hashes are the same 1160 return ImmutableMap.this.hashCode(); 1161 } 1162 1163 @Override 1164 boolean isHashCodeFast() { 1165 return ImmutableMap.this.isHashCodeFast(); 1166 } 1167 1168 @Override 1169 UnmodifiableIterator<Entry<K, ImmutableSet<V>>> entryIterator() { 1170 final Iterator<Entry<K, V>> backingIterator = ImmutableMap.this.entrySet().iterator(); 1171 return new UnmodifiableIterator<Entry<K, ImmutableSet<V>>>() { 1172 @Override 1173 public boolean hasNext() { 1174 return backingIterator.hasNext(); 1175 } 1176 1177 @Override 1178 public Entry<K, ImmutableSet<V>> next() { 1179 final Entry<K, V> backingEntry = backingIterator.next(); 1180 return new AbstractMapEntry<K, ImmutableSet<V>>() { 1181 @Override 1182 public K getKey() { 1183 return backingEntry.getKey(); 1184 } 1185 1186 @Override 1187 public ImmutableSet<V> getValue() { 1188 return ImmutableSet.of(backingEntry.getValue()); 1189 } 1190 }; 1191 } 1192 }; 1193 } 1194 1195 // redeclare to help optimizers with b/310253115 1196 @SuppressWarnings("RedundantOverride") 1197 @Override 1198 @J2ktIncompatible // serialization 1199 @GwtIncompatible // serialization 1200 Object writeReplace() { 1201 return super.writeReplace(); 1202 } 1203 } 1204 1205 @Override 1206 public boolean equals(@CheckForNull Object object) { 1207 return Maps.equalsImpl(this, object); 1208 } 1209 1210 abstract boolean isPartialView(); 1211 1212 @Override 1213 public int hashCode() { 1214 return Sets.hashCodeImpl(entrySet()); 1215 } 1216 1217 boolean isHashCodeFast() { 1218 return false; 1219 } 1220 1221 @Override 1222 public String toString() { 1223 return Maps.toStringImpl(this); 1224 } 1225 1226 /** 1227 * Serialized type for all ImmutableMap instances. It captures the logical contents and they are 1228 * reconstructed using public factory methods. This ensures that the implementation types remain 1229 * as implementation details. 1230 */ 1231 @J2ktIncompatible // serialization 1232 static class SerializedForm<K, V> implements Serializable { 1233 // This object retains references to collections returned by keySet() and value(). This saves 1234 // bytes when the both the map and its keySet or value collection are written to the same 1235 // instance of ObjectOutputStream. 1236 1237 // TODO(b/160980469): remove support for the old serialization format after some time 1238 private static final boolean USE_LEGACY_SERIALIZATION = true; 1239 1240 private final Object keys; 1241 private final Object values; 1242 1243 SerializedForm(ImmutableMap<K, V> map) { 1244 if (USE_LEGACY_SERIALIZATION) { 1245 Object[] keys = new Object[map.size()]; 1246 Object[] values = new Object[map.size()]; 1247 int i = 0; 1248 // "extends Object" works around https://github.com/typetools/checker-framework/issues/3013 1249 for (Entry<? extends Object, ? extends Object> entry : map.entrySet()) { 1250 keys[i] = entry.getKey(); 1251 values[i] = entry.getValue(); 1252 i++; 1253 } 1254 this.keys = keys; 1255 this.values = values; 1256 return; 1257 } 1258 this.keys = map.keySet(); 1259 this.values = map.values(); 1260 } 1261 1262 @SuppressWarnings("unchecked") 1263 final Object readResolve() { 1264 if (!(this.keys instanceof ImmutableSet)) { 1265 return legacyReadResolve(); 1266 } 1267 1268 ImmutableSet<K> keySet = (ImmutableSet<K>) this.keys; 1269 ImmutableCollection<V> values = (ImmutableCollection<V>) this.values; 1270 1271 Builder<K, V> builder = makeBuilder(keySet.size()); 1272 1273 UnmodifiableIterator<K> keyIter = keySet.iterator(); 1274 UnmodifiableIterator<V> valueIter = values.iterator(); 1275 1276 while (keyIter.hasNext()) { 1277 builder.put(keyIter.next(), valueIter.next()); 1278 } 1279 1280 return builder.buildOrThrow(); 1281 } 1282 1283 @SuppressWarnings("unchecked") 1284 final Object legacyReadResolve() { 1285 K[] keys = (K[]) this.keys; 1286 V[] values = (V[]) this.values; 1287 1288 Builder<K, V> builder = makeBuilder(keys.length); 1289 1290 for (int i = 0; i < keys.length; i++) { 1291 builder.put(keys[i], values[i]); 1292 } 1293 return builder.buildOrThrow(); 1294 } 1295 1296 /** 1297 * Returns a builder that builds the unserialized type. Subclasses should override this method. 1298 */ 1299 Builder<K, V> makeBuilder(int size) { 1300 return new Builder<>(size); 1301 } 1302 1303 private static final long serialVersionUID = 0; 1304 } 1305 1306 /** 1307 * Returns a serializable form of this object. Non-public subclasses should not override this 1308 * method. Publicly-accessible subclasses must override this method and should return a subclass 1309 * of SerializedForm whose readResolve() method returns objects of the subclass type. 1310 */ 1311 @J2ktIncompatible // serialization 1312 Object writeReplace() { 1313 return new SerializedForm<>(this); 1314 } 1315 1316 @J2ktIncompatible // java.io.ObjectInputStream 1317 private void readObject(ObjectInputStream stream) throws InvalidObjectException { 1318 throw new InvalidObjectException("Use SerializedForm"); 1319 } 1320 1321 private static final long serialVersionUID = 0xcafebabe; 1322}