guava

1
/*
2
 * Copyright (C) 2008 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 junit.framework.Assert.assertEquals;
20
import static junit.framework.Assert.fail;
21

22
import com.google.common.annotations.GwtCompatible;
23
import java.util.ArrayList;
24
import java.util.Arrays;
25
import java.util.Collection;
26
import java.util.Collections;
27
import java.util.Iterator;
28
import java.util.List;
29
import java.util.ListIterator;
30
import java.util.NoSuchElementException;
31
import java.util.Set;
32
import java.util.Stack;
33
import org.checkerframework.checker.nullness.qual.Nullable;
34

35
/**
36
 * Most of the logic for {@link IteratorTester} and {@link ListIteratorTester}.
37
 *
38
 * @param <E> the type of element returned by the iterator
39
 * @param <I> the type of the iterator ({@link Iterator} or {@link ListIterator})
40
 * @author Kevin Bourrillion
41
 * @author Chris Povirk
42
 */
43
@GwtCompatible
44
@ElementTypesAreNonnullByDefault
45
abstract class AbstractIteratorTester<E extends @Nullable Object, I extends Iterator<E>> {
46
  private Stimulus<E, ? super I>[] stimuli;
47
  private final Iterator<E> elementsToInsert;
48
  private final Set<IteratorFeature> features;
49
  private final List<E> expectedElements;
50
  private final int startIndex;
51
  private final KnownOrder knownOrder;
52

53
  /**
54
   * Meta-exception thrown by {@link AbstractIteratorTester.MultiExceptionListIterator} instead of
55
   * throwing any particular exception type.
56
   */
57
  private abstract static class PermittedMetaException extends RuntimeException {
58
    static final PermittedMetaException UOE_OR_ISE =
59
        new PermittedMetaException("UnsupportedOperationException or IllegalStateException") {
60
          @Override
61
          boolean isPermitted(Exception exception) {
62
            return exception instanceof UnsupportedOperationException
63
                || exception instanceof IllegalStateException;
64
          }
65
        };
66
    static final PermittedMetaException UOE =
67
        new PermittedMetaException("UnsupportedOperationException") {
68
          @Override
69
          boolean isPermitted(Exception exception) {
70
            return exception instanceof UnsupportedOperationException;
71
          }
72
        };
73
    static final PermittedMetaException ISE =
74
        new PermittedMetaException("IllegalStateException") {
75
          @Override
76
          boolean isPermitted(Exception exception) {
77
            return exception instanceof IllegalStateException;
78
          }
79
        };
80
    static final PermittedMetaException NSEE =
81
        new PermittedMetaException("NoSuchElementException") {
82
          @Override
83
          boolean isPermitted(Exception exception) {
84
            return exception instanceof NoSuchElementException;
85
          }
86
        };
87

88
    private PermittedMetaException(String message) {
89
      super(message);
90
    }
91

92
    abstract boolean isPermitted(Exception exception);
93

94
    void assertPermitted(Exception exception) {
95
      if (!isPermitted(exception)) {
96
        String message =
97
            "Exception "
98
                + exception.getClass().getSimpleName()
99
                + " was thrown; expected "
100
                + getMessage();
101
        throw new AssertionError(message, exception);
102
      }
103
    }
104

105
    private static final long serialVersionUID = 0;
106
  }
107

108
  private static final class UnknownElementException extends RuntimeException {
109
    private UnknownElementException(Collection<?> expected, Object actual) {
110
      super("Returned value '" + actual + "' not found. Remaining elements: " + expected);
111
    }
112

113
    private static final long serialVersionUID = 0;
114
  }
115

116
  /**
117
   * Quasi-implementation of {@link ListIterator} that works from a list of elements and a set of
118
   * features to support (from the enclosing {@link AbstractIteratorTester} instance). Instead of
119
   * throwing exceptions like {@link NoSuchElementException} at the appropriate times, it throws
120
   * {@link PermittedMetaException} instances, which wrap a set of all exceptions that the iterator
121
   * could throw during the invocation of that method. This is necessary because, e.g., a call to
122
   * {@code iterator().remove()} of an unmodifiable list could throw either {@link
123
   * IllegalStateException} or {@link UnsupportedOperationException}. Note that iterator
124
   * implementations should always throw one of the exceptions in a {@code PermittedExceptions}
125
   * instance, since {@code PermittedExceptions} is thrown only when a method call is invalid.
126
   *
127
   * <p>This class is accessible but not supported in GWT as it references {@link
128
   * PermittedMetaException}.
129
   */
130
  protected final class MultiExceptionListIterator implements ListIterator<E> {
131
    // TODO: track seen elements when order isn't guaranteed
132
    // TODO: verify contents afterward
133
    // TODO: something shiny and new instead of Stack
134
    // TODO: test whether null is supported (create a Feature)
135
    /**
136
     * The elements to be returned by future calls to {@code next()}, with the first at the top of
137
     * the stack.
138
     */
139
    final Stack<E> nextElements = new Stack<>();
140

141
    /**
142
     * The elements to be returned by future calls to {@code previous()}, with the first at the top
143
     * of the stack.
144
     */
145
    final Stack<E> previousElements = new Stack<>();
146

147
    /**
148
     * {@link #nextElements} if {@code next()} was called more recently then {@code previous},
149
     * {@link #previousElements} if the reverse is true, or -- overriding both of these -- {@code
150
     * null} if {@code remove()} or {@code add()} has been called more recently than either. We use
151
     * this to determine which stack to pop from on a call to {@code remove()} (or to pop from and
152
     * push to on a call to {@code set()}).
153
     */
154
    @Nullable Stack<E> stackWithLastReturnedElementAtTop = null;
155

156
    MultiExceptionListIterator(List<E> expectedElements) {
157
      Helpers.addAll(nextElements, Helpers.reverse(expectedElements));
158
      for (int i = 0; i < startIndex; i++) {
159
        previousElements.push(nextElements.pop());
160
      }
161
    }
162

163
    @Override
164
    public void add(E e) {
165
      if (!features.contains(IteratorFeature.SUPPORTS_ADD)) {
166
        throw PermittedMetaException.UOE;
167
      }
168

169
      previousElements.push(e);
170
      stackWithLastReturnedElementAtTop = null;
171
    }
172

173
    @Override
174
    public boolean hasNext() {
175
      return !nextElements.isEmpty();
176
    }
177

178
    @Override
179
    public boolean hasPrevious() {
180
      return !previousElements.isEmpty();
181
    }
182

183
    @Override
184
    public E next() {
185
      return transferElement(nextElements, previousElements);
186
    }
187

188
    @Override
189
    public int nextIndex() {
190
      return previousElements.size();
191
    }
192

193
    @Override
194
    public E previous() {
195
      return transferElement(previousElements, nextElements);
196
    }
197

198
    @Override
199
    public int previousIndex() {
200
      return nextIndex() - 1;
201
    }
202

203
    @Override
204
    public void remove() {
205
      throwIfInvalid(IteratorFeature.SUPPORTS_REMOVE);
206

207
      stackWithLastReturnedElementAtTop.pop();
208
      stackWithLastReturnedElementAtTop = null;
209
    }
210

211
    @Override
212
    public void set(E e) {
213
      throwIfInvalid(IteratorFeature.SUPPORTS_SET);
214

215
      stackWithLastReturnedElementAtTop.pop();
216
      stackWithLastReturnedElementAtTop.push(e);
217
    }
218

219
    /**
220
     * Moves the given element from its current position in {@link #nextElements} to the top of the
221
     * stack so that it is returned by the next call to {@link Iterator#next()}. If the element is
222
     * not in {@link #nextElements}, this method throws an {@link UnknownElementException}.
223
     *
224
     * <p>This method is used when testing iterators without a known ordering. We poll the target
225
     * iterator's next element and pass it to the reference iterator through this method so it can
226
     * return the same element. This enables the assertion to pass and the reference iterator to
227
     * properly update its state.
228
     */
229
    void promoteToNext(E e) {
230
      if (nextElements.remove(e)) {
231
        nextElements.push(e);
232
      } else {
233
        throw new UnknownElementException(nextElements, e);
234
      }
235
    }
236

237
    private E transferElement(Stack<E> source, Stack<E> destination) {
238
      if (source.isEmpty()) {
239
        throw PermittedMetaException.NSEE;
240
      }
241

242
      destination.push(source.pop());
243
      stackWithLastReturnedElementAtTop = destination;
244
      return destination.peek();
245
    }
246

247
    private void throwIfInvalid(IteratorFeature methodFeature) {
248
      if (!features.contains(methodFeature)) {
249
        if (stackWithLastReturnedElementAtTop == null) {
250
          throw PermittedMetaException.UOE_OR_ISE;
251
        } else {
252
          throw PermittedMetaException.UOE;
253
        }
254
      } else if (stackWithLastReturnedElementAtTop == null) {
255
        throw PermittedMetaException.ISE;
256
      }
257
    }
258

259
    private List<E> getElements() {
260
      List<E> elements = new ArrayList<>();
261
      Helpers.addAll(elements, previousElements);
262
      Helpers.addAll(elements, Helpers.reverse(nextElements));
263
      return elements;
264
    }
265
  }
266

267
  public enum KnownOrder {
268
    KNOWN_ORDER,
269
    UNKNOWN_ORDER
270
  }
271

272
  @SuppressWarnings("unchecked") // TODO(cpovirk): Stop using arrays.
273
  AbstractIteratorTester(
274
      int steps,
275
      Iterable<E> elementsToInsertIterable,
276
      Iterable<? extends IteratorFeature> features,
277
      Iterable<E> expectedElements,
278
      KnownOrder knownOrder,
279
      int startIndex) {
280
    // periodically we should manually try (steps * 3 / 2) here; all tests but
281
    // one should still pass (testVerifyGetsCalled()).
282
    stimuli = (Stimulus<E, ? super I>[]) new Stimulus<?, ?>[steps];
283
    if (!elementsToInsertIterable.iterator().hasNext()) {
284
      throw new IllegalArgumentException();
285
    }
286
    elementsToInsert = Helpers.cycle(elementsToInsertIterable);
287
    this.features = Helpers.copyToSet(features);
288
    this.expectedElements = Helpers.copyToList(expectedElements);
289
    this.knownOrder = knownOrder;
290
    this.startIndex = startIndex;
291
  }
292

293
  /**
294
   * I'd like to make this a parameter to the constructor, but I can't because the stimulus
295
   * instances refer to {@code this}.
296
   */
297
  protected abstract Iterable<? extends Stimulus<E, ? super I>> getStimulusValues();
298

299
  /**
300
   * Returns a new target iterator each time it's called. This is the iterator you are trying to
301
   * test. This must return an Iterator that returns the expected elements passed to the constructor
302
   * in the given order. Warning: it is not enough to simply pull multiple iterators from the same
303
   * source Iterable, unless that Iterator is unmodifiable.
304
   */
305
  protected abstract I newTargetIterator();
306

307
  /**
308
   * Override this to verify anything after running a list of Stimuli.
309
   *
310
   * <p>For example, verify that calls to remove() actually removed the correct elements.
311
   *
312
   * @param elements the expected elements passed to the constructor, as mutated by {@code
313
   *     remove()}, {@code set()}, and {@code add()} calls
314
   */
315
  protected void verify(List<E> elements) {}
316

317
  /** Executes the test. */
318
  @SuppressWarnings("CatchingUnchecked") // sneaky checked exception
319
  public final void test() {
320
    try {
321
      recurse(0);
322
    } catch (Exception e) { // sneaky checked exception
323
      throw new RuntimeException(Arrays.toString(stimuli), e);
324
    }
325
  }
326

327
  public void testForEachRemaining() {
328
    for (int i = 0; i < expectedElements.size() - 1; i++) {
329
      List<E> targetElements = new ArrayList<>();
330
      Iterator<E> iterator = newTargetIterator();
331
      for (int j = 0; j < i; j++) {
332
        targetElements.add(iterator.next());
333
      }
334
      iterator.forEachRemaining(targetElements::add);
335
      if (knownOrder == KnownOrder.KNOWN_ORDER) {
336
        assertEquals(expectedElements, targetElements);
337
      } else {
338
        Helpers.assertEqualIgnoringOrder(expectedElements, targetElements);
339
      }
340
    }
341
  }
342

343
  private void recurse(int level) {
344
    // We're going to reuse the stimuli array 3^steps times by overwriting it
345
    // in a recursive loop.  Sneaky.
346
    if (level == stimuli.length) {
347
      // We've filled the array.
348
      compareResultsForThisListOfStimuli();
349
    } else {
350
      // Keep recursing to fill the array.
351
      for (Stimulus<E, ? super I> stimulus : getStimulusValues()) {
352
        stimuli[level] = stimulus;
353
        recurse(level + 1);
354
      }
355
    }
356
  }
357

358
  private void compareResultsForThisListOfStimuli() {
359
    int removes = Collections.frequency(Arrays.asList(stimuli), remove);
360
    if ((!features.contains(IteratorFeature.SUPPORTS_REMOVE) && removes > 1)
361
        || (stimuli.length >= 5 && removes > 2)) {
362
      // removes are the most expensive thing to test, since they often throw exceptions with stack
363
      // traces, so we test them a bit less aggressively
364
      return;
365
    }
366

367
    MultiExceptionListIterator reference = new MultiExceptionListIterator(expectedElements);
368
    I target = newTargetIterator();
369
    for (int i = 0; i < stimuli.length; i++) {
370
      try {
371
        stimuli[i].executeAndCompare(reference, target);
372
        verify(reference.getElements());
373
      } catch (AssertionError cause) {
374
        throw new AssertionError("failed with stimuli " + subListCopy(stimuli, i + 1), cause);
375
      }
376
    }
377
  }
378

379
  private static List<Object> subListCopy(Object[] source, int size) {
380
    final Object[] copy = new Object[size];
381
    System.arraycopy(source, 0, copy, 0, size);
382
    return Arrays.asList(copy);
383
  }
384

385
  private interface IteratorOperation {
386
    @Nullable Object execute(Iterator<?> iterator);
387
  }
388

389
  /**
390
   * Apply this method to both iterators and return normally only if both produce the same response.
391
   *
392
   * @see Stimulus#executeAndCompare(ListIterator, Iterator)
393
   */
394
  @SuppressWarnings("CatchingUnchecked") // sneaky checked exception
395
  private <T extends Iterator<E>> void internalExecuteAndCompare(
396
      T reference, T target, IteratorOperation method) {
397
    Object referenceReturnValue = null;
398
    PermittedMetaException referenceException = null;
399
    Object targetReturnValue = null;
400
    Exception targetException = null;
401

402
    try {
403
      targetReturnValue = method.execute(target);
404
    } catch (Exception e) { // sneaky checked exception
405
      targetException = e;
406
    }
407

408
    try {
409
      if (method == NEXT_METHOD
410
          && targetException == null
411
          && knownOrder == KnownOrder.UNKNOWN_ORDER) {
412
        /*
413
         * We already know the iterator is an Iterator<E>, and now we know that
414
         * we called next(), so the returned element must be of type E.
415
         */
416
        @SuppressWarnings("unchecked")
417
        E targetReturnValueFromNext = (E) targetReturnValue;
418
        /*
419
         * We have an Iterator<E> and want to cast it to
420
         * MultiExceptionListIterator. Because we're inside an
421
         * AbstractIteratorTester<E>, that's implicitly a cast to
422
         * AbstractIteratorTester<E>.MultiExceptionListIterator. The runtime
423
         * won't be able to verify the AbstractIteratorTester<E> part, so it's
424
         * an unchecked cast. We know, however, that the only possible value for
425
         * the type parameter is <E>, since otherwise the
426
         * MultiExceptionListIterator wouldn't be an Iterator<E>. The cast is
427
         * safe, even though javac can't tell.
428
         *
429
         * Sun bug 6665356 is an additional complication. Until OpenJDK 7, javac
430
         * doesn't recognize this kind of cast as unchecked cast. Neither does
431
         * Eclipse 3.4. Right now, this suppression is mostly unnecessary.
432
         */
433
        @SuppressWarnings("unchecked")
434
        MultiExceptionListIterator multiExceptionListIterator =
435
            (MultiExceptionListIterator) reference;
436
        multiExceptionListIterator.promoteToNext(targetReturnValueFromNext);
437
      }
438

439
      referenceReturnValue = method.execute(reference);
440
    } catch (PermittedMetaException e) {
441
      referenceException = e;
442
    } catch (UnknownElementException e) {
443
      throw new AssertionError(e);
444
    }
445

446
    if (referenceException == null) {
447
      if (targetException != null) {
448
        throw new AssertionError("Target threw exception when reference did not", targetException);
449
      }
450

451
      /*
452
       * Reference iterator returned a value, so we should expect the
453
       * same value from the target
454
       */
455
      assertEquals(referenceReturnValue, targetReturnValue);
456

457
      return;
458
    }
459

460
    if (targetException == null) {
461
      fail("Target failed to throw " + referenceException);
462
    }
463

464
    /*
465
     * Reference iterator threw an exception, so we should expect an acceptable
466
     * exception from the target.
467
     */
468
    referenceException.assertPermitted(targetException);
469
  }
470

471
  private static final IteratorOperation REMOVE_METHOD =
472
      new IteratorOperation() {
473
        @Override
474
        public @Nullable Object execute(Iterator<?> iterator) {
475
          iterator.remove();
476
          return null;
477
        }
478
      };
479

480
  private static final IteratorOperation NEXT_METHOD =
481
      new IteratorOperation() {
482
        @Override
483
        public @Nullable Object execute(Iterator<?> iterator) {
484
          return iterator.next();
485
        }
486
      };
487

488
  private static final IteratorOperation PREVIOUS_METHOD =
489
      new IteratorOperation() {
490
        @Override
491
        public @Nullable Object execute(Iterator<?> iterator) {
492
          return ((ListIterator<?>) iterator).previous();
493
        }
494
      };
495

496
  private final IteratorOperation newAddMethod() {
497
    final Object toInsert = elementsToInsert.next();
498
    return new IteratorOperation() {
499
      @Override
500
      public @Nullable Object execute(Iterator<?> iterator) {
501
        @SuppressWarnings("unchecked")
502
        ListIterator<Object> rawIterator = (ListIterator<Object>) iterator;
503
        rawIterator.add(toInsert);
504
        return null;
505
      }
506
    };
507
  }
508

509
  private final IteratorOperation newSetMethod() {
510
    final E toInsert = elementsToInsert.next();
511
    return new IteratorOperation() {
512
      @Override
513
      public @Nullable Object execute(Iterator<?> iterator) {
514
        @SuppressWarnings("unchecked")
515
        ListIterator<E> li = (ListIterator<E>) iterator;
516
        li.set(toInsert);
517
        return null;
518
      }
519
    };
520
  }
521

522
  abstract static class Stimulus<E extends @Nullable Object, T extends Iterator<E>> {
523
    private final String toString;
524

525
    protected Stimulus(String toString) {
526
      this.toString = toString;
527
    }
528

529
    /**
530
     * Send this stimulus to both iterators and return normally only if both produce the same
531
     * response.
532
     */
533
    abstract void executeAndCompare(ListIterator<E> reference, T target);
534

535
    @Override
536
    public String toString() {
537
      return toString;
538
    }
539
  }
540

541
  Stimulus<E, Iterator<E>> hasNext =
542
      new Stimulus<E, Iterator<E>>("hasNext") {
543
        @Override
544
        void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
545
          assertEquals(reference.hasNext(), target.hasNext());
546
        }
547
      };
548
  Stimulus<E, Iterator<E>> next =
549
      new Stimulus<E, Iterator<E>>("next") {
550
        @Override
551
        void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
552
          internalExecuteAndCompare(reference, target, NEXT_METHOD);
553
        }
554
      };
555
  Stimulus<E, Iterator<E>> remove =
556
      new Stimulus<E, Iterator<E>>("remove") {
557
        @Override
558
        void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
559
          internalExecuteAndCompare(reference, target, REMOVE_METHOD);
560
        }
561
      };
562

563
  List<Stimulus<E, Iterator<E>>> iteratorStimuli() {
564
    return Arrays.asList(hasNext, next, remove);
565
  }
566

567
  Stimulus<E, ListIterator<E>> hasPrevious =
568
      new Stimulus<E, ListIterator<E>>("hasPrevious") {
569
        @Override
570
        void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
571
          assertEquals(reference.hasPrevious(), target.hasPrevious());
572
        }
573
      };
574
  Stimulus<E, ListIterator<E>> nextIndex =
575
      new Stimulus<E, ListIterator<E>>("nextIndex") {
576
        @Override
577
        void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
578
          assertEquals(reference.nextIndex(), target.nextIndex());
579
        }
580
      };
581
  Stimulus<E, ListIterator<E>> previousIndex =
582
      new Stimulus<E, ListIterator<E>>("previousIndex") {
583
        @Override
584
        void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
585
          assertEquals(reference.previousIndex(), target.previousIndex());
586
        }
587
      };
588
  Stimulus<E, ListIterator<E>> previous =
589
      new Stimulus<E, ListIterator<E>>("previous") {
590
        @Override
591
        void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
592
          internalExecuteAndCompare(reference, target, PREVIOUS_METHOD);
593
        }
594
      };
595
  Stimulus<E, ListIterator<E>> add =
596
      new Stimulus<E, ListIterator<E>>("add") {
597
        @Override
598
        void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
599
          internalExecuteAndCompare(reference, target, newAddMethod());
600
        }
601
      };
602
  Stimulus<E, ListIterator<E>> set =
603
      new Stimulus<E, ListIterator<E>>("set") {
604
        @Override
605
        void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
606
          internalExecuteAndCompare(reference, target, newSetMethod());
607
        }
608
      };
609

610
  List<Stimulus<E, ListIterator<E>>> listIteratorStimuli() {
611
    return Arrays.asList(hasPrevious, nextIndex, previousIndex, previous, add, set);
612
  }
613
}
614