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