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