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