guava

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.Arrays.asList;
24
import static java.util.Collections.unmodifiableSet;
25
import static junit.framework.Assert.assertEquals;
26
import static junit.framework.Assert.assertFalse;
27
import static junit.framework.Assert.assertTrue;
28
import static junit.framework.Assert.fail;
29

30
import com.google.common.annotations.GwtCompatible;
31
import com.google.common.collect.ImmutableSet;
32
import com.google.common.collect.Ordering;
33
import com.google.common.primitives.Ints;
34
import com.google.errorprone.annotations.CanIgnoreReturnValue;
35
import java.util.ArrayList;
36
import java.util.Arrays;
37
import java.util.Comparator;
38
import java.util.LinkedHashSet;
39
import java.util.List;
40
import java.util.Set;
41
import java.util.Spliterator;
42
import java.util.Spliterator.OfPrimitive;
43
import java.util.function.Consumer;
44
import java.util.function.Function;
45
import java.util.function.Supplier;
46
import org.checkerframework.checker.nullness.qual.Nullable;
47

48
/**
49
 * Tester for {@code Spliterator} implementations.
50
 *
51
 * @since 21.0
52
 */
53
@GwtCompatible
54
@ElementTypesAreNonnullByDefault
55
public final class SpliteratorTester<E extends @Nullable Object> {
56
  /** Return type from "contains the following elements" assertions. */
57
  public interface Ordered {
58
    /**
59
     * Attests that the expected values must not just be present but must be present in the order
60
     * they were given.
61
     */
62
    void inOrder();
63
  }
64

65
  private abstract static class GeneralSpliterator<E extends @Nullable Object> {
66
    final Spliterator<E> spliterator;
67

68
    GeneralSpliterator(Spliterator<E> spliterator) {
69
      this.spliterator = checkNotNull(spliterator);
70
    }
71

72
    abstract void forEachRemaining(Consumer<? super E> action);
73

74
    abstract boolean tryAdvance(Consumer<? super E> action);
75

76
    abstract @Nullable GeneralSpliterator<E> trySplit();
77

78
    final int characteristics() {
79
      return spliterator.characteristics();
80
    }
81

82
    final long estimateSize() {
83
      return spliterator.estimateSize();
84
    }
85

86
    final Comparator<? super E> getComparator() {
87
      return spliterator.getComparator();
88
    }
89

90
    final long getExactSizeIfKnown() {
91
      return spliterator.getExactSizeIfKnown();
92
    }
93

94
    final boolean hasCharacteristics(int characteristics) {
95
      return spliterator.hasCharacteristics(characteristics);
96
    }
97
  }
98

99
  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
}
345