001/*
002 * Copyright (C) 2015 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.testing;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.collect.testing.Helpers.assertEqualIgnoringOrder;
021import static com.google.common.collect.testing.Helpers.assertEqualInOrder;
022import static com.google.common.collect.testing.Platform.format;
023import static java.util.Arrays.asList;
024import static java.util.Collections.unmodifiableSet;
025import static junit.framework.Assert.assertEquals;
026import static junit.framework.Assert.assertFalse;
027import static junit.framework.Assert.assertTrue;
028import static junit.framework.Assert.fail;
029
030import com.google.common.annotations.GwtCompatible;
031import com.google.common.collect.ImmutableSet;
032import com.google.common.collect.Ordering;
033import com.google.common.primitives.Ints;
034import com.google.errorprone.annotations.CanIgnoreReturnValue;
035import java.util.ArrayList;
036import java.util.Arrays;
037import java.util.Comparator;
038import java.util.LinkedHashSet;
039import java.util.List;
040import java.util.Set;
041import java.util.Spliterator;
042import java.util.Spliterator.OfPrimitive;
043import java.util.function.Consumer;
044import java.util.function.Function;
045import java.util.function.Supplier;
046import org.checkerframework.checker.nullness.qual.Nullable;
047
048/**
049 * Tester for {@code Spliterator} implementations.
050 *
051 * @since 21.0
052 */
053@GwtCompatible
054@ElementTypesAreNonnullByDefault
055public final class SpliteratorTester<E extends @Nullable Object> {
056  /** Return type from "contains the following elements" assertions. */
057  public interface Ordered {
058    /**
059     * Attests that the expected values must not just be present but must be present in the order
060     * they were given.
061     */
062    void inOrder();
063  }
064
065  private abstract static class GeneralSpliterator<E extends @Nullable Object> {
066    final Spliterator<E> spliterator;
067
068    GeneralSpliterator(Spliterator<E> spliterator) {
069      this.spliterator = checkNotNull(spliterator);
070    }
071
072    abstract void forEachRemaining(Consumer<? super E> action);
073
074    abstract boolean tryAdvance(Consumer<? super E> action);
075
076    abstract @Nullable GeneralSpliterator<E> trySplit();
077
078    final int characteristics() {
079      return spliterator.characteristics();
080    }
081
082    final long estimateSize() {
083      return spliterator.estimateSize();
084    }
085
086    final Comparator<? super E> getComparator() {
087      return spliterator.getComparator();
088    }
089
090    final long getExactSizeIfKnown() {
091      return spliterator.getExactSizeIfKnown();
092    }
093
094    final boolean hasCharacteristics(int characteristics) {
095      return spliterator.hasCharacteristics(characteristics);
096    }
097  }
098
099  private static final class GeneralSpliteratorOfObject<E extends @Nullable Object>
100      extends GeneralSpliterator<E> {
101    GeneralSpliteratorOfObject(Spliterator<E> spliterator) {
102      super(spliterator);
103    }
104
105    @Override
106    void forEachRemaining(Consumer<? super E> action) {
107      spliterator.forEachRemaining(action);
108    }
109
110    @Override
111    boolean tryAdvance(Consumer<? super E> action) {
112      return spliterator.tryAdvance(action);
113    }
114
115    @Override
116    @Nullable GeneralSpliterator<E> trySplit() {
117      Spliterator<E> split = spliterator.trySplit();
118      return split == null ? null : new GeneralSpliteratorOfObject<>(split);
119    }
120  }
121
122  private static final class GeneralSpliteratorOfPrimitive<
123          E extends @Nullable Object, C, S extends Spliterator.OfPrimitive<E, C, S>>
124      extends GeneralSpliterator<E> {
125    final OfPrimitive<E, C, S> spliteratorOfPrimitive;
126    final Function<Consumer<? super E>, C> consumerizer;
127
128    GeneralSpliteratorOfPrimitive(
129        Spliterator.OfPrimitive<E, C, S> spliterator,
130        Function<Consumer<? super E>, C> consumerizer) {
131      super(spliterator);
132      this.spliteratorOfPrimitive = spliterator;
133      this.consumerizer = consumerizer;
134    }
135
136    @Override
137    void forEachRemaining(Consumer<? super E> action) {
138      spliteratorOfPrimitive.forEachRemaining(consumerizer.apply(action));
139    }
140
141    @Override
142    boolean tryAdvance(Consumer<? super E> action) {
143      return spliteratorOfPrimitive.tryAdvance(consumerizer.apply(action));
144    }
145
146    @Override
147    @Nullable GeneralSpliterator<E> trySplit() {
148      Spliterator.OfPrimitive<E, C, ?> split = spliteratorOfPrimitive.trySplit();
149      return split == null ? null : new GeneralSpliteratorOfPrimitive<>(split, consumerizer);
150    }
151  }
152
153  /**
154   * Different ways of decomposing a Spliterator, all of which must produce the same elements (up to
155   * ordering, if Spliterator.ORDERED is not present).
156   */
157  enum SpliteratorDecompositionStrategy {
158    NO_SPLIT_FOR_EACH_REMAINING {
159      @Override
160      <E extends @Nullable Object> void forEach(
161          GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) {
162        spliterator.forEachRemaining(consumer);
163      }
164    },
165    NO_SPLIT_TRY_ADVANCE {
166      @Override
167      <E extends @Nullable Object> void forEach(
168          GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) {
169        while (spliterator.tryAdvance(consumer)) {
170          // do nothing
171        }
172      }
173    },
174    MAXIMUM_SPLIT {
175      @Override
176      <E extends @Nullable Object> void forEach(
177          GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) {
178        for (GeneralSpliterator<E> prefix = trySplitTestingSize(spliterator);
179            prefix != null;
180            prefix = trySplitTestingSize(spliterator)) {
181          forEach(prefix, consumer);
182        }
183        long size = spliterator.getExactSizeIfKnown();
184        long[] counter = {0};
185        spliterator.forEachRemaining(
186            e -> {
187              consumer.accept(e);
188              counter[0]++;
189            });
190        if (size >= 0) {
191          assertEquals(size, counter[0]);
192        }
193      }
194    },
195    ALTERNATE_ADVANCE_AND_SPLIT {
196      @Override
197      <E extends @Nullable Object> void forEach(
198          GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) {
199        while (spliterator.tryAdvance(consumer)) {
200          GeneralSpliterator<E> prefix = trySplitTestingSize(spliterator);
201          if (prefix != null) {
202            forEach(prefix, consumer);
203          }
204        }
205      }
206    };
207
208    abstract <E extends @Nullable Object> void forEach(
209        GeneralSpliterator<E> spliterator, Consumer<? super E> consumer);
210
211    static final Set<SpliteratorDecompositionStrategy> ALL_STRATEGIES =
212        unmodifiableSet(new LinkedHashSet<>(asList(values())));
213  }
214
215  private static <E extends @Nullable Object> @Nullable GeneralSpliterator<E> trySplitTestingSize(
216      GeneralSpliterator<E> spliterator) {
217    boolean subsized = spliterator.hasCharacteristics(Spliterator.SUBSIZED);
218    long originalSize = spliterator.estimateSize();
219    GeneralSpliterator<E> trySplit = spliterator.trySplit();
220    if (spliterator.estimateSize() > originalSize) {
221      fail(
222          format(
223              "estimated size of spliterator after trySplit (%s) is larger than original size (%s)",
224              spliterator.estimateSize(), originalSize));
225    }
226    if (trySplit != null) {
227      if (trySplit.estimateSize() > originalSize) {
228        fail(
229            format(
230                "estimated size of trySplit result (%s) is larger than original size (%s)",
231                trySplit.estimateSize(), originalSize));
232      }
233    }
234    if (subsized) {
235      if (trySplit != null) {
236        assertEquals(
237            "sum of estimated sizes of trySplit and original spliterator after trySplit",
238            originalSize,
239            trySplit.estimateSize() + spliterator.estimateSize());
240      } else {
241        assertEquals(
242            "estimated size of spliterator after failed trySplit",
243            originalSize,
244            spliterator.estimateSize());
245      }
246    }
247    return trySplit;
248  }
249
250  public static <E extends @Nullable Object> SpliteratorTester<E> of(
251      Supplier<Spliterator<E>> spliteratorSupplier) {
252    return new SpliteratorTester<>(
253        ImmutableSet.of(() -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get())));
254  }
255
256  /**
257   * @since 28.1
258   */
259  public static SpliteratorTester<Integer> ofInt(Supplier<Spliterator.OfInt> spliteratorSupplier) {
260    return new SpliteratorTester<>(
261        ImmutableSet.of(
262            () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()),
263            () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept)));
264  }
265
266  /**
267   * @since 28.1
268   */
269  public static SpliteratorTester<Long> ofLong(Supplier<Spliterator.OfLong> spliteratorSupplier) {
270    return new SpliteratorTester<>(
271        ImmutableSet.of(
272            () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()),
273            () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept)));
274  }
275
276  /**
277   * @since 28.1
278   */
279  public static SpliteratorTester<Double> ofDouble(
280      Supplier<Spliterator.OfDouble> spliteratorSupplier) {
281    return new SpliteratorTester<>(
282        ImmutableSet.of(
283            () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()),
284            () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept)));
285  }
286
287  private final ImmutableSet<Supplier<GeneralSpliterator<E>>> spliteratorSuppliers;
288
289  private SpliteratorTester(ImmutableSet<Supplier<GeneralSpliterator<E>>> spliteratorSuppliers) {
290    this.spliteratorSuppliers = checkNotNull(spliteratorSuppliers);
291  }
292
293  @SafeVarargs
294  @CanIgnoreReturnValue
295  public final Ordered expect(Object... elements) {
296    return expect(Arrays.asList(elements));
297  }
298
299  @CanIgnoreReturnValue
300  public final Ordered expect(Iterable<?> elements) {
301    List<List<E>> resultsForAllStrategies = new ArrayList<>();
302    for (Supplier<GeneralSpliterator<E>> spliteratorSupplier : spliteratorSuppliers) {
303      GeneralSpliterator<E> spliterator = spliteratorSupplier.get();
304      int characteristics = spliterator.characteristics();
305      long estimatedSize = spliterator.estimateSize();
306      for (SpliteratorDecompositionStrategy strategy :
307          SpliteratorDecompositionStrategy.ALL_STRATEGIES) {
308        List<E> resultsForStrategy = new ArrayList<>();
309        strategy.forEach(spliteratorSupplier.get(), resultsForStrategy::add);
310
311        // TODO(cpovirk): better failure messages
312        if ((characteristics & Spliterator.NONNULL) != 0) {
313          assertFalse(resultsForStrategy.contains(null));
314        }
315        if ((characteristics & Spliterator.SORTED) != 0) {
316          Comparator<? super E> comparator = spliterator.getComparator();
317          if (comparator == null) {
318            // A sorted spliterator with no comparator is already using natural order.
319            // (We could probably find a way to avoid rawtypes here if we wanted.)
320            @SuppressWarnings({"unchecked", "rawtypes"})
321            Comparator<? super E> naturalOrder =
322                (Comparator<? super E>) Comparator.<Comparable>naturalOrder();
323            comparator = naturalOrder;
324          }
325          assertTrue(Ordering.from(comparator).isOrdered(resultsForStrategy));
326        }
327        if ((characteristics & Spliterator.SIZED) != 0) {
328          assertEquals(Ints.checkedCast(estimatedSize), resultsForStrategy.size());
329        }
330
331        assertEqualIgnoringOrder(elements, resultsForStrategy);
332        resultsForAllStrategies.add(resultsForStrategy);
333      }
334    }
335    return new Ordered() {
336      @Override
337      public void inOrder() {
338        for (List<E> resultsForStrategy : resultsForAllStrategies) {
339          assertEqualInOrder(elements, resultsForStrategy);
340        }
341      }
342    };
343  }
344}