Java

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 MultiExceptionListIterator. Because we're
420
         * inside an AbstractIteratorTester<E>, that's implicitly a cast to
421
         * AbstractIteratorTester<E>.MultiExceptionListIterator. The runtime won't be able to verify
422
         * the AbstractIteratorTester<E> part, so it's an unchecked cast. We know, however, that the
423
         * only possible value for the type parameter is <E>, since otherwise the
424
         * MultiExceptionListIterator wouldn't be an Iterator<E>. The cast is safe, even though
425
         * javac can't tell.
426
         */
427
        @SuppressWarnings("unchecked")
428
        MultiExceptionListIterator multiExceptionListIterator =
429
            (MultiExceptionListIterator) reference;
430
        multiExceptionListIterator.promoteToNext(targetReturnValueFromNext);
431
      }
432

433
      referenceReturnValue = method.execute(reference);
434
    } catch (PermittedMetaException e) {
435
      referenceException = e;
436
    } catch (UnknownElementException e) {
437
      throw new AssertionError(e);
438
    }
439

440
    if (referenceException == null) {
441
      if (targetException != null) {
442
        throw new AssertionError("Target threw exception when reference did not", targetException);
443
      }
444

445
      /*
446
       * Reference iterator returned a value, so we should expect the
447
       * same value from the target
448
       */
449
      assertEquals(referenceReturnValue, targetReturnValue);
450

451
      return;
452
    }
453

454
    if (targetException == null) {
455
      fail("Target failed to throw " + referenceException);
456
    }
457

458
    /*
459
     * Reference iterator threw an exception, so we should expect an acceptable
460
     * exception from the target.
461
     */
462
    referenceException.assertPermitted(targetException);
463
  }
464

465
  private static final IteratorOperation REMOVE_METHOD =
466
      new IteratorOperation() {
467
        @Override
468
        public @Nullable Object execute(Iterator<?> iterator) {
469
          iterator.remove();
470
          return null;
471
        }
472
      };
473

474
  private static final IteratorOperation NEXT_METHOD =
475
      new IteratorOperation() {
476
        @Override
477
        public @Nullable Object execute(Iterator<?> iterator) {
478
          return iterator.next();
479
        }
480
      };
481

482
  private static final IteratorOperation PREVIOUS_METHOD =
483
      new IteratorOperation() {
484
        @Override
485
        public @Nullable Object execute(Iterator<?> iterator) {
486
          return ((ListIterator<?>) iterator).previous();
487
        }
488
      };
489

490
  private final IteratorOperation newAddMethod() {
491
    final Object toInsert = elementsToInsert.next();
492
    return new IteratorOperation() {
493
      @Override
494
      public @Nullable Object execute(Iterator<?> iterator) {
495
        @SuppressWarnings("unchecked")
496
        ListIterator<Object> rawIterator = (ListIterator<Object>) iterator;
497
        rawIterator.add(toInsert);
498
        return null;
499
      }
500
    };
501
  }
502

503
  private final IteratorOperation newSetMethod() {
504
    final E toInsert = elementsToInsert.next();
505
    return new IteratorOperation() {
506
      @Override
507
      public @Nullable Object execute(Iterator<?> iterator) {
508
        @SuppressWarnings("unchecked")
509
        ListIterator<E> li = (ListIterator<E>) iterator;
510
        li.set(toInsert);
511
        return null;
512
      }
513
    };
514
  }
515

516
  abstract static class Stimulus<E extends @Nullable Object, T extends Iterator<E>> {
517
    private final String toString;
518

519
    protected Stimulus(String toString) {
520
      this.toString = toString;
521
    }
522

523
    /**
524
     * Send this stimulus to both iterators and return normally only if both produce the same
525
     * response.
526
     */
527
    abstract void executeAndCompare(ListIterator<E> reference, T target);
528

529
    @Override
530
    public String toString() {
531
      return toString;
532
    }
533
  }
534

535
  Stimulus<E, Iterator<E>> hasNext =
536
      new Stimulus<E, Iterator<E>>("hasNext") {
537
        @Override
538
        void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
539
          assertEquals(reference.hasNext(), target.hasNext());
540
        }
541
      };
542
  Stimulus<E, Iterator<E>> next =
543
      new Stimulus<E, Iterator<E>>("next") {
544
        @Override
545
        void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
546
          internalExecuteAndCompare(reference, target, NEXT_METHOD);
547
        }
548
      };
549
  Stimulus<E, Iterator<E>> remove =
550
      new Stimulus<E, Iterator<E>>("remove") {
551
        @Override
552
        void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
553
          internalExecuteAndCompare(reference, target, REMOVE_METHOD);
554
        }
555
      };
556

557
  List<Stimulus<E, Iterator<E>>> iteratorStimuli() {
558
    return Arrays.asList(hasNext, next, remove);
559
  }
560

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

604
  List<Stimulus<E, ListIterator<E>>> listIteratorStimuli() {
605
    return Arrays.asList(hasPrevious, nextIndex, previousIndex, previous, add, set);
606
  }
607
}
608