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