1 /*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20
21 import com.google.common.annotations.GwtCompatible;
22 import com.google.errorprone.annotations.CanIgnoreReturnValue;
23 import com.google.errorprone.annotations.DoNotCall;
24 import com.google.errorprone.annotations.DoNotMock;
25 import java.io.Serializable;
26 import java.util.AbstractCollection;
27 import java.util.Collection;
28 import java.util.Collections;
29 import java.util.HashSet;
30 import java.util.Iterator;
31 import java.util.List;
32 import java.util.Spliterator;
33 import java.util.Spliterators;
34 import java.util.function.Predicate;
35 import javax.annotation.CheckForNull;
36 import org.checkerframework.checker.nullness.qual.Nullable;
37
38 /**
39 * A {@link Collection} whose contents will never change, and which offers a few additional
40 * guarantees detailed below.
41 *
42 * <p><b>Warning:</b> avoid <i>direct</i> usage of {@link ImmutableCollection} as a type (just as
43 * with {@link Collection} itself). Prefer subtypes such as {@link ImmutableSet} or {@link
44 * ImmutableList}, which have well-defined {@link #equals} semantics, thus avoiding a common source
45 * of bugs and confusion.
46 *
47 * <h3>About <i>all</i> {@code Immutable-} collections</h3>
48 *
49 * <p>The remainder of this documentation applies to every public {@code Immutable-} type in this
50 * package, whether it is a subtype of {@code ImmutableCollection} or not.
51 *
52 * <h4>Guarantees</h4>
53 *
54 * <p>Each makes the following guarantees:
55 *
56 * <ul>
57 * <li><b>Shallow immutability.</b> Elements can never be added, removed or replaced in this
58 * collection. This is a stronger guarantee than that of {@link
59 * Collections#unmodifiableCollection}, whose contents change whenever the wrapped collection
60 * is modified.
61 * <li><b>Null-hostility.</b> This collection will never contain a null element.
62 * <li><b>Deterministic iteration.</b> The iteration order is always well-defined, depending on
63 * how the collection was created. Typically this is insertion order unless an explicit
64 * ordering is otherwise specified (e.g. {@link ImmutableSortedSet#naturalOrder}). See the
65 * appropriate factory method for details. View collections such as {@link
66 * ImmutableMultiset#elementSet} iterate in the same order as the parent, except as noted.
67 * <li><b>Thread safety.</b> It is safe to access this collection concurrently from multiple
68 * threads.
69 * <li><b>Integrity.</b> This type cannot be subclassed outside this package (which would allow
70 * these guarantees to be violated).
71 * </ul>
72 *
73 * <h4>"Interfaces", not implementations</h4>
74 *
75 * <p>These are classes instead of interfaces to prevent external subtyping, but should be thought
76 * of as interfaces in every important sense. Each public class such as {@link ImmutableSet} is a
77 * <i>type</i> offering meaningful behavioral guarantees. This is substantially different from the
78 * case of (say) {@link HashSet}, which is an <i>implementation</i>, with semantics that were
79 * largely defined by its supertype.
80 *
81 * <p>For field types and method return types, you should generally use the immutable type (such as
82 * {@link ImmutableList}) instead of the general collection interface type (such as {@link List}).
83 * This communicates to your callers all of the semantic guarantees listed above, which is almost
84 * always very useful information.
85 *
86 * <p>On the other hand, a <i>parameter</i> type of {@link ImmutableList} is generally a nuisance to
87 * callers. Instead, accept {@link Iterable} and have your method or constructor body pass it to the
88 * appropriate {@code copyOf} method itself.
89 *
90 * <p>Expressing the immutability guarantee directly in the type that user code references is a
91 * powerful advantage. Although Java offers certain immutable collection factory methods, such as
92 * {@link Collections#singleton(Object)} and <a
93 * href="https://docs.oracle.com/javase/9/docs/api/java/util/Set.html#immutable">{@code Set.of}</a>,
94 * we recommend using <i>these</i> classes instead for this reason (as well as for consistency).
95 *
96 * <h4>Creation</h4>
97 *
98 * <p>Except for logically "abstract" types like {@code ImmutableCollection} itself, each {@code
99 * Immutable} type provides the static operations you need to obtain instances of that type. These
100 * usually include:
101 *
102 * <ul>
103 * <li>Static methods named {@code of}, accepting an explicit list of elements or entries.
104 * <li>Static methods named {@code copyOf} (or {@code copyOfSorted}), accepting an existing
105 * collection whose contents should be copied.
106 * <li>A static nested {@code Builder} class which can be used to populate a new immutable
107 * instance.
108 * </ul>
109 *
110 * <h4>Warnings</h4>
111 *
112 * <ul>
113 * <li><b>Warning:</b> as with any collection, it is almost always a bad idea to modify an element
114 * (in a way that affects its {@link Object#equals} behavior) while it is contained in a
115 * collection. Undefined behavior and bugs will result. It's generally best to avoid using
116 * mutable objects as elements at all, as many users may expect your "immutable" object to be
117 * <i>deeply</i> immutable.
118 * </ul>
119 *
120 * <h4>Performance notes</h4>
121 *
122 * <ul>
123 * <li>Implementations can be generally assumed to prioritize memory efficiency, then speed of
124 * access, and lastly speed of creation.
125 * <li>The {@code copyOf} methods will sometimes recognize that the actual copy operation is
126 * unnecessary; for example, {@code copyOf(copyOf(anArrayList))} should copy the data only
127 * once. This reduces the expense of habitually making defensive copies at API boundaries.
128 * However, the precise conditions for skipping the copy operation are undefined.
129 * <li><b>Warning:</b> a view collection such as {@link ImmutableMap#keySet} or {@link
130 * ImmutableList#subList} may retain a reference to the entire data set, preventing it from
131 * being garbage collected. If some of the data is no longer reachable through other means,
132 * this constitutes a memory leak. Pass the view collection to the appropriate {@code copyOf}
133 * method to obtain a correctly-sized copy.
134 * <li>The performance of using the associated {@code Builder} class can be assumed to be no
135 * worse, and possibly better, than creating a mutable collection and copying it.
136 * <li>Implementations generally do not cache hash codes. If your element or key type has a slow
137 * {@code hashCode} implementation, it should cache it itself.
138 * </ul>
139 *
140 * <h4>Example usage</h4>
141 *
142 * <pre>{@code
143 * class Foo {
144 * private static final ImmutableSet<String> RESERVED_CODES =
145 * ImmutableSet.of("AZ", "CQ", "ZX");
146 *
147 * private final ImmutableSet<String> codes;
148 *
149 * public Foo(Iterable<String> codes) {
150 * this.codes = ImmutableSet.copyOf(codes);
151 * checkArgument(Collections.disjoint(this.codes, RESERVED_CODES));
152 * }
153 * }
154 * }</pre>
155 *
156 * <h3>See also</h3>
157 *
158 * <p>See the Guava User Guide article on <a href=
159 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>.
160 *
161 * @since 2.0
162 */
163 @DoNotMock("Use ImmutableList.of or another implementation")
164 @GwtCompatible(emulated = true)
165 @SuppressWarnings("serial") // we're overriding default serialization
166 @ElementTypesAreNonnullByDefault
167 // TODO(kevinb): I think we should push everything down to "BaseImmutableCollection" or something,
168 // just to do everything we can to emphasize the "practically an interface" nature of this class.
169 public abstract class ImmutableCollection<E> extends AbstractCollection<E> implements Serializable {
170 /*
171 * We expect SIZED (and SUBSIZED, if applicable) to be added by the spliterator factory methods.
172 * These are properties of the collection as a whole; SIZED and SUBSIZED are more properties of
173 * the spliterator implementation.
174 */
175 static final int SPLITERATOR_CHARACTERISTICS =
176 Spliterator.IMMUTABLE | Spliterator.NONNULL | Spliterator.ORDERED;
177
178 ImmutableCollection() {}
179
180 /** Returns an unmodifiable iterator across the elements in this collection. */
181 @Override
182 public abstract UnmodifiableIterator<E> iterator();
183
184 @Override
185 public Spliterator<E> spliterator() {
186 return Spliterators.spliterator(this, SPLITERATOR_CHARACTERISTICS);
187 }
188
189 private static final Object[] EMPTY_ARRAY = {};
190
191 @Override
192 public final Object[] toArray() {
193 return toArray(EMPTY_ARRAY);
194 }
195
196 @CanIgnoreReturnValue
197 @Override
198 /*
199 * This suppression is here for two reasons:
200 *
201 * 1. Our checker says "found: T[]; required: T[]." That sounds bogus. I discuss a possible reason
202 * for this error in https://github.com/jspecify/checker-framework/issues/10.
203 *
204 * 2. `other[size] = null` is unsound. We could "fix" this by requiring callers to pass in an
205 * array with a nullable element type. But probably they usually want an array with a non-nullable
206 * type. That said, we could *accept* a `@Nullable T[]` (which, given that we treat arrays as
207 * covariant, would still permit a plain `T[]`) and return a plain `T[]`. But of course that would
208 * require its own suppression, since it is also unsound. toArray(T[]) is just a mess from a
209 * nullness perspective. The signature below at least has the virtue of being relatively simple.
210 */
211 @SuppressWarnings("nullness")
212 public final <T extends @Nullable Object> T[] toArray(T[] other) {
213 checkNotNull(other);
214 int size = size();
215
216 if (other.length < size) {
217 Object[] internal = internalArray();
218 if (internal != null) {
219 return Platform.copy(internal, internalArrayStart(), internalArrayEnd(), other);
220 }
221 other = ObjectArrays.newArray(other, size);
222 } else if (other.length > size) {
223 other[size] = null;
224 }
225 copyIntoArray(other, 0);
226 return other;
227 }
228
229 /** If this collection is backed by an array of its elements in insertion order, returns it. */
230 @CheckForNull
231 Object[] internalArray() {
232 return null;
233 }
234
235 /**
236 * If this collection is backed by an array of its elements in insertion order, returns the offset
237 * where this collection's elements start.
238 */
239 int internalArrayStart() {
240 throw new UnsupportedOperationException();
241 }
242
243 /**
244 * If this collection is backed by an array of its elements in insertion order, returns the offset
245 * where this collection's elements end.
246 */
247 int internalArrayEnd() {
248 throw new UnsupportedOperationException();
249 }
250
251 @Override
252 public abstract boolean contains(@CheckForNull Object object);
253
254 /**
255 * Guaranteed to throw an exception and leave the collection unmodified.
256 *
257 * @throws UnsupportedOperationException always
258 * @deprecated Unsupported operation.
259 */
260 @CanIgnoreReturnValue
261 @Deprecated
262 @Override
263 @DoNotCall("Always throws UnsupportedOperationException")
264 public final boolean add(E e) {
265 throw new UnsupportedOperationException();
266 }
267
268 /**
269 * Guaranteed to throw an exception and leave the collection unmodified.
270 *
271 * @throws UnsupportedOperationException always
272 * @deprecated Unsupported operation.
273 */
274 @CanIgnoreReturnValue
275 @Deprecated
276 @Override
277 @DoNotCall("Always throws UnsupportedOperationException")
278 public final boolean remove(@CheckForNull Object object) {
279 throw new UnsupportedOperationException();
280 }
281
282 /**
283 * Guaranteed to throw an exception and leave the collection unmodified.
284 *
285 * @throws UnsupportedOperationException always
286 * @deprecated Unsupported operation.
287 */
288 @CanIgnoreReturnValue
289 @Deprecated
290 @Override
291 @DoNotCall("Always throws UnsupportedOperationException")
292 public final boolean addAll(Collection<? extends E> newElements) {
293 throw new UnsupportedOperationException();
294 }
295
296 /**
297 * Guaranteed to throw an exception and leave the collection unmodified.
298 *
299 * @throws UnsupportedOperationException always
300 * @deprecated Unsupported operation.
301 */
302 @CanIgnoreReturnValue
303 @Deprecated
304 @Override
305 @DoNotCall("Always throws UnsupportedOperationException")
306 public final boolean removeAll(Collection<?> oldElements) {
307 throw new UnsupportedOperationException();
308 }
309
310 /**
311 * Guaranteed to throw an exception and leave the collection unmodified.
312 *
313 * @throws UnsupportedOperationException always
314 * @deprecated Unsupported operation.
315 */
316 @CanIgnoreReturnValue
317 @Deprecated
318 @Override
319 @DoNotCall("Always throws UnsupportedOperationException")
320 public final boolean removeIf(Predicate<? super E> filter) {
321 throw new UnsupportedOperationException();
322 }
323
324 /**
325 * Guaranteed to throw an exception and leave the collection unmodified.
326 *
327 * @throws UnsupportedOperationException always
328 * @deprecated Unsupported operation.
329 */
330 @Deprecated
331 @Override
332 @DoNotCall("Always throws UnsupportedOperationException")
333 public final boolean retainAll(Collection<?> elementsToKeep) {
334 throw new UnsupportedOperationException();
335 }
336
337 /**
338 * Guaranteed to throw an exception and leave the collection unmodified.
339 *
340 * @throws UnsupportedOperationException always
341 * @deprecated Unsupported operation.
342 */
343 @Deprecated
344 @Override
345 @DoNotCall("Always throws UnsupportedOperationException")
346 public final void clear() {
347 throw new UnsupportedOperationException();
348 }
349
350 /**
351 * Returns an {@code ImmutableList} containing the same elements, in the same order, as this
352 * collection.
353 *
354 * <p><b>Performance note:</b> in most cases this method can return quickly without actually
355 * copying anything. The exact circumstances under which the copy is performed are undefined and
356 * subject to change.
357 *
358 * @since 2.0
359 */
360 public ImmutableList<E> asList() {
361 switch (size()) {
362 case 0:
363 return ImmutableList.of();
364 case 1:
365 return ImmutableList.of(iterator().next());
366 default:
367 return new RegularImmutableAsList<E>(this, toArray());
368 }
369 }
370
371 /**
372 * Returns {@code true} if this immutable collection's implementation contains references to
373 * user-created objects that aren't accessible via this collection's methods. This is generally
374 * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid
375 * memory leaks.
376 */
377 abstract boolean isPartialView();
378
379 /**
380 * Copies the contents of this immutable collection into the specified array at the specified
381 * offset. Returns {@code offset + size()}.
382 */
383 @CanIgnoreReturnValue
384 int copyIntoArray(@Nullable Object[] dst, int offset) {
385 for (E e : this) {
386 dst[offset++] = e;
387 }
388 return offset;
389 }
390
391 Object writeReplace() {
392 // We serialize by default to ImmutableList, the simplest thing that works.
393 return new ImmutableList.SerializedForm(toArray());
394 }
395
396 /**
397 * Abstract base class for builders of {@link ImmutableCollection} types.
398 *
399 * @since 10.0
400 */
401 @DoNotMock
402 public abstract static class Builder<E> {
403 static final int DEFAULT_INITIAL_CAPACITY = 4;
404
405 static int expandedCapacity(int oldCapacity, int minCapacity) {
406 if (minCapacity < 0) {
407 throw new AssertionError("cannot store more than MAX_VALUE elements");
408 }
409 // careful of overflow!
410 int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
411 if (newCapacity < minCapacity) {
412 newCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
413 }
414 if (newCapacity < 0) {
415 newCapacity = Integer.MAX_VALUE;
416 // guaranteed to be >= newCapacity
417 }
418 return newCapacity;
419 }
420
421 Builder() {}
422
423 /**
424 * Adds {@code element} to the {@code ImmutableCollection} being built.
425 *
426 * <p>Note that each builder class covariantly returns its own type from this method.
427 *
428 * @param element the element to add
429 * @return this {@code Builder} instance
430 * @throws NullPointerException if {@code element} is null
431 */
432 @CanIgnoreReturnValue
433 public abstract Builder<E> add(E element);
434
435 /**
436 * Adds each element of {@code elements} to the {@code ImmutableCollection} being built.
437 *
438 * <p>Note that each builder class overrides this method in order to covariantly return its own
439 * type.
440 *
441 * @param elements the elements to add
442 * @return this {@code Builder} instance
443 * @throws NullPointerException if {@code elements} is null or contains a null element
444 */
445 @CanIgnoreReturnValue
446 public Builder<E> add(E... elements) {
447 for (E element : elements) {
448 add(element);
449 }
450 return this;
451 }
452
453 /**
454 * Adds each element of {@code elements} to the {@code ImmutableCollection} being built.
455 *
456 * <p>Note that each builder class overrides this method in order to covariantly return its own
457 * type.
458 *
459 * @param elements the elements to add
460 * @return this {@code Builder} instance
461 * @throws NullPointerException if {@code elements} is null or contains a null element
462 */
463 @CanIgnoreReturnValue
464 public Builder<E> addAll(Iterable<? extends E> elements) {
465 for (E element : elements) {
466 add(element);
467 }
468 return this;
469 }
470
471 /**
472 * Adds each element of {@code elements} to the {@code ImmutableCollection} being built.
473 *
474 * <p>Note that each builder class overrides this method in order to covariantly return its own
475 * type.
476 *
477 * @param elements the elements to add
478 * @return this {@code Builder} instance
479 * @throws NullPointerException if {@code elements} is null or contains a null element
480 */
481 @CanIgnoreReturnValue
482 public Builder<E> addAll(Iterator<? extends E> elements) {
483 while (elements.hasNext()) {
484 add(elements.next());
485 }
486 return this;
487 }
488
489 /**
490 * Returns a newly-created {@code ImmutableCollection} of the appropriate type, containing the
491 * elements provided to this builder.
492 *
493 * <p>Note that each builder class covariantly returns the appropriate type of {@code
494 * ImmutableCollection} from this method.
495 */
496 public abstract ImmutableCollection<E> build();
497 }
498 }