Debian Codegraph @

guava-testlib/src/com/google/common/collect/testing/SpliteratorTester.java

raw
1 /*
2 * Copyright (C) 2015 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.testing;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20 import static com.google.common.collect.testing.Helpers.assertEqualIgnoringOrder;
21 import static com.google.common.collect.testing.Helpers.assertEqualInOrder;
22 import static com.google.common.collect.testing.Platform.format;
23 import static java.util.Comparator.naturalOrder;
24 import static junit.framework.Assert.assertEquals;
25 import static junit.framework.Assert.assertFalse;
26 import static junit.framework.Assert.assertTrue;
27 import static junit.framework.Assert.fail;
28
29 import com.google.common.annotations.GwtCompatible;
30 import com.google.common.collect.ImmutableSet;
31 import com.google.common.collect.Ordering;
32 import com.google.common.primitives.Ints;
33 import com.google.errorprone.annotations.CanIgnoreReturnValue;
34 import java.util.ArrayList;
35 import java.util.Arrays;
36 import java.util.Comparator;
37 import java.util.EnumSet;
38 import java.util.List;
39 import java.util.Spliterator;
40 import java.util.function.Consumer;
41 import java.util.function.Function;
42 import java.util.function.Supplier;
43 import org.checkerframework.checker.nullness.qual.Nullable;
44
45 /** Tester for {@code Spliterator} implementations. */
46 @GwtCompatible
47 public final class SpliteratorTester<E> {
48 /** Return type from "contains the following elements" assertions. */
49 public interface Ordered {
50 /**
51 * Attests that the expected values must not just be present but must be present in the order
52 * they were given.
53 */
54 void inOrder();
55 }
56
57 private abstract static class GeneralSpliterator<E> {
58 final Spliterator<E> spliterator;
59
60 GeneralSpliterator(Spliterator<E> spliterator) {
61 this.spliterator = checkNotNull(spliterator);
62 }
63
64 abstract void forEachRemaining(Consumer<? super E> action);
65
66 abstract boolean tryAdvance(Consumer<? super E> action);
67
68 abstract GeneralSpliterator<E> trySplit();
69
70 final int characteristics() {
71 return spliterator.characteristics();
72 }
73
74 final long estimateSize() {
75 return spliterator.estimateSize();
76 }
77
78 final Comparator<? super E> getComparator() {
79 return spliterator.getComparator();
80 }
81
82 final long getExactSizeIfKnown() {
83 return spliterator.getExactSizeIfKnown();
84 }
85
86 final boolean hasCharacteristics(int characteristics) {
87 return spliterator.hasCharacteristics(characteristics);
88 }
89 }
90
91 private static final class GeneralSpliteratorOfObject<E> extends GeneralSpliterator<E> {
92 GeneralSpliteratorOfObject(Spliterator<E> spliterator) {
93 super(spliterator);
94 }
95
96 @Override
97 void forEachRemaining(Consumer<? super E> action) {
98 spliterator.forEachRemaining(action);
99 }
100
101 @Override
102 boolean tryAdvance(Consumer<? super E> action) {
103 return spliterator.tryAdvance(action);
104 }
105
106 @Override
107 @Nullable GeneralSpliterator<E> trySplit() {
108 Spliterator<E> split = spliterator.trySplit();
109 return split == null ? null : new GeneralSpliteratorOfObject<>(split);
110 }
111 }
112
113 /*
114 * The AndroidJdkLibsChecker violation is informing us that this method isn't usable under
115 * Desugar. But we want to include it here for Nougat+ users -- and, mainly, for non-Android
116 * users. Fortunately, anyone who tries to use it under Desugar will presumably already see errors
117 * from creating the Spliterator.OfInt in the first place. So it's probably OK for us to suppress
118 * this particular violation.
119 */
120 @SuppressWarnings("AndroidJdkLibsChecker")
121 private static final class GeneralSpliteratorOfPrimitive<E, C> extends GeneralSpliterator<E> {
122 final Spliterator.OfPrimitive<E, C, ?> spliterator;
123 final Function<Consumer<? super E>, C> consumerizer;
124
125 GeneralSpliteratorOfPrimitive(
126 Spliterator.OfPrimitive<E, C, ?> spliterator,
127 Function<Consumer<? super E>, C> consumerizer) {
128 super(spliterator);
129 this.spliterator = spliterator;
130 this.consumerizer = consumerizer;
131 }
132
133 @Override
134 void forEachRemaining(Consumer<? super E> action) {
135 spliterator.forEachRemaining(consumerizer.apply(action));
136 }
137
138 @Override
139 boolean tryAdvance(Consumer<? super E> action) {
140 return spliterator.tryAdvance(consumerizer.apply(action));
141 }
142
143 @Override
144 @Nullable GeneralSpliterator<E> trySplit() {
145 Spliterator.OfPrimitive<E, C, ?> split = spliterator.trySplit();
146 return split == null ? null : new GeneralSpliteratorOfPrimitive<>(split, consumerizer);
147 }
148 }
149
150 /**
151 * Different ways of decomposing a Spliterator, all of which must produce the same elements (up to
152 * ordering, if Spliterator.ORDERED is not present).
153 */
154 enum SpliteratorDecompositionStrategy {
155 NO_SPLIT_FOR_EACH_REMAINING {
156 @Override
157 <E> void forEach(GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) {
158 spliterator.forEachRemaining(consumer);
159 }
160 },
161 NO_SPLIT_TRY_ADVANCE {
162 @Override
163 <E> void forEach(GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) {
164 while (spliterator.tryAdvance(consumer)) {
165 // do nothing
166 }
167 }
168 },
169 MAXIMUM_SPLIT {
170 @Override
171 <E> void forEach(GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) {
172 for (GeneralSpliterator<E> prefix = trySplitTestingSize(spliterator);
173 prefix != null;
174 prefix = trySplitTestingSize(spliterator)) {
175 forEach(prefix, consumer);
176 }
177 long size = spliterator.getExactSizeIfKnown();
178 long[] counter = {0};
179 spliterator.forEachRemaining(
180 e -> {
181 consumer.accept(e);
182 counter[0]++;
183 });
184 if (size >= 0) {
185 assertEquals(size, counter[0]);
186 }
187 }
188 },
189 ALTERNATE_ADVANCE_AND_SPLIT {
190 @Override
191 <E> void forEach(GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) {
192 while (spliterator.tryAdvance(consumer)) {
193 GeneralSpliterator<E> prefix = trySplitTestingSize(spliterator);
194 if (prefix != null) {
195 forEach(prefix, consumer);
196 }
197 }
198 }
199 };
200
201 abstract <E> void forEach(GeneralSpliterator<E> spliterator, Consumer<? super E> consumer);
202 }
203
204 private static <E> @Nullable GeneralSpliterator<E> trySplitTestingSize(
205 GeneralSpliterator<E> spliterator) {
206 boolean subsized = spliterator.hasCharacteristics(Spliterator.SUBSIZED);
207 long originalSize = spliterator.estimateSize();
208 GeneralSpliterator<E> trySplit = spliterator.trySplit();
209 if (spliterator.estimateSize() > originalSize) {
210 fail(
211 format(
212 "estimated size of spliterator after trySplit (%s) is larger than original size (%s)",
213 spliterator.estimateSize(), originalSize));
214 }
215 if (trySplit != null) {
216 if (trySplit.estimateSize() > originalSize) {
217 fail(
218 format(
219 "estimated size of trySplit result (%s) is larger than original size (%s)",
220 trySplit.estimateSize(), originalSize));
221 }
222 }
223 if (subsized) {
224 if (trySplit != null) {
225 assertEquals(
226 "sum of estimated sizes of trySplit and original spliterator after trySplit",
227 originalSize,
228 trySplit.estimateSize() + spliterator.estimateSize());
229 } else {
230 assertEquals(
231 "estimated size of spliterator after failed trySplit",
232 originalSize,
233 spliterator.estimateSize());
234 }
235 }
236 return trySplit;
237 }
238
239 public static <E> SpliteratorTester<E> of(Supplier<Spliterator<E>> spliteratorSupplier) {
240 return new SpliteratorTester<>(
241 ImmutableSet.of(() -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get())));
242 }
243
244 /** @since 28.1 */
245 @SuppressWarnings("AndroidJdkLibsChecker") // see comment on GeneralSpliteratorOfPrimitive
246 public static SpliteratorTester<Integer> ofInt(Supplier<Spliterator.OfInt> spliteratorSupplier) {
247 return new SpliteratorTester<>(
248 ImmutableSet.of(
249 () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()),
250 () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept)));
251 }
252
253 /** @since 28.1 */
254 @SuppressWarnings("AndroidJdkLibsChecker") // see comment on GeneralSpliteratorOfPrimitive
255 public static SpliteratorTester<Long> ofLong(Supplier<Spliterator.OfLong> spliteratorSupplier) {
256 return new SpliteratorTester<>(
257 ImmutableSet.of(
258 () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()),
259 () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept)));
260 }
261
262 /** @since 28.1 */
263 @SuppressWarnings("AndroidJdkLibsChecker") // see comment on GeneralSpliteratorOfPrimitive
264 public static SpliteratorTester<Double> ofDouble(
265 Supplier<Spliterator.OfDouble> spliteratorSupplier) {
266 return new SpliteratorTester<>(
267 ImmutableSet.of(
268 () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()),
269 () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept)));
270 }
271
272 private final ImmutableSet<Supplier<GeneralSpliterator<E>>> spliteratorSuppliers;
273
274 private SpliteratorTester(ImmutableSet<Supplier<GeneralSpliterator<E>>> spliteratorSuppliers) {
275 this.spliteratorSuppliers = checkNotNull(spliteratorSuppliers);
276 }
277
278 @SafeVarargs
279 @CanIgnoreReturnValue
280 public final Ordered expect(Object... elements) {
281 return expect(Arrays.asList(elements));
282 }
283
284 @CanIgnoreReturnValue
285 public final Ordered expect(Iterable<?> elements) {
286 List<List<E>> resultsForAllStrategies = new ArrayList<>();
287 for (Supplier<GeneralSpliterator<E>> spliteratorSupplier : spliteratorSuppliers) {
288 GeneralSpliterator<E> spliterator = spliteratorSupplier.get();
289 int characteristics = spliterator.characteristics();
290 long estimatedSize = spliterator.estimateSize();
291 for (SpliteratorDecompositionStrategy strategy :
292 EnumSet.allOf(SpliteratorDecompositionStrategy.class)) {
293 List<E> resultsForStrategy = new ArrayList<>();
294 strategy.forEach(spliteratorSupplier.get(), resultsForStrategy::add);
295
296 // TODO(cpovirk): better failure messages
297 if ((characteristics & Spliterator.NONNULL) != 0) {
298 assertFalse(resultsForStrategy.contains(null));
299 }
300 if ((characteristics & Spliterator.SORTED) != 0) {
301 Comparator<? super E> comparator = spliterator.getComparator();
302 if (comparator == null) {
303 comparator = (Comparator) naturalOrder();
304 }
305 assertTrue(Ordering.from(comparator).isOrdered(resultsForStrategy));
306 }
307 if ((characteristics & Spliterator.SIZED) != 0) {
308 assertEquals(Ints.checkedCast(estimatedSize), resultsForStrategy.size());
309 }
310
311 assertEqualIgnoringOrder(elements, resultsForStrategy);
312 resultsForAllStrategies.add(resultsForStrategy);
313 }
314 }
315 return new Ordered() {
316 @Override
317 public void inOrder() {
318 for (List<E> resultsForStrategy : resultsForAllStrategies) {
319 assertEqualInOrder(elements, resultsForStrategy);
320 }
321 }
322 };
323 }
324 }