Debian Codegraph @

guava-testlib/src/com/google/common/collect/testing/AbstractIteratorTester.java

raw
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 junit.framework.AssertionFailedError;
34 import org.checkerframework.checker.nullness.qual.Nullable;
35
36 /**
37 * Most of the logic for {@link IteratorTester} and {@link ListIteratorTester}.
38 *
39 * @param <E> the type of element returned by the iterator
40 * @param <I> the type of the iterator ({@link Iterator} or {@link ListIterator})
41 * @author Kevin Bourrillion
42 * @author Chris Povirk
43 */
44 @GwtCompatible
45 abstract class AbstractIteratorTester<E, 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(RuntimeException 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(RuntimeException exception) {
70 return exception instanceof UnsupportedOperationException;
71 }
72 };
73 static final PermittedMetaException ISE =
74 new PermittedMetaException("IllegalStateException") {
75 @Override
76 boolean isPermitted(RuntimeException exception) {
77 return exception instanceof IllegalStateException;
78 }
79 };
80 static final PermittedMetaException NSEE =
81 new PermittedMetaException("NoSuchElementException") {
82 @Override
83 boolean isPermitted(RuntimeException exception) {
84 return exception instanceof NoSuchElementException;
85 }
86 };
87
88 private PermittedMetaException(String message) {
89 super(message);
90 }
91
92 abstract boolean isPermitted(RuntimeException exception);
93
94 void assertPermitted(RuntimeException exception) {
95 if (!isPermitted(exception)) {
96 String message =
97 "Exception "
98 + exception.getClass().getSimpleName()
99 + " was thrown; expected "
100 + getMessage();
101 Helpers.fail(exception, message);
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<E>();
140 /**
141 * The elements to be returned by future calls to {@code previous()}, with the first at the top
142 * of the stack.
143 */
144 final Stack<E> previousElements = new Stack<E>();
145 /**
146 * {@link #nextElements} if {@code next()} was called more recently then {@code previous},
147 * {@link #previousElements} if the reverse is true, or -- overriding both of these -- {@code
148 * null} if {@code remove()} or {@code add()} has been called more recently than either. We use
149 * this to determine which stack to pop from on a call to {@code remove()} (or to pop from and
150 * push to on a call to {@code set()}).
151 */
152 @Nullable Stack<E> stackWithLastReturnedElementAtTop = null;
153
154 MultiExceptionListIterator(List<E> expectedElements) {
155 Helpers.addAll(nextElements, Helpers.reverse(expectedElements));
156 for (int i = 0; i < startIndex; i++) {
157 previousElements.push(nextElements.pop());
158 }
159 }
160
161 @Override
162 public void add(E e) {
163 if (!features.contains(IteratorFeature.SUPPORTS_ADD)) {
164 throw PermittedMetaException.UOE;
165 }
166
167 previousElements.push(e);
168 stackWithLastReturnedElementAtTop = null;
169 }
170
171 @Override
172 public boolean hasNext() {
173 return !nextElements.isEmpty();
174 }
175
176 @Override
177 public boolean hasPrevious() {
178 return !previousElements.isEmpty();
179 }
180
181 @Override
182 public E next() {
183 return transferElement(nextElements, previousElements);
184 }
185
186 @Override
187 public int nextIndex() {
188 return previousElements.size();
189 }
190
191 @Override
192 public E previous() {
193 return transferElement(previousElements, nextElements);
194 }
195
196 @Override
197 public int previousIndex() {
198 return nextIndex() - 1;
199 }
200
201 @Override
202 public void remove() {
203 throwIfInvalid(IteratorFeature.SUPPORTS_REMOVE);
204
205 stackWithLastReturnedElementAtTop.pop();
206 stackWithLastReturnedElementAtTop = null;
207 }
208
209 @Override
210 public void set(E e) {
211 throwIfInvalid(IteratorFeature.SUPPORTS_SET);
212
213 stackWithLastReturnedElementAtTop.pop();
214 stackWithLastReturnedElementAtTop.push(e);
215 }
216
217 /**
218 * Moves the given element from its current position in {@link #nextElements} to the top of the
219 * stack so that it is returned by the next call to {@link Iterator#next()}. If the element is
220 * not in {@link #nextElements}, this method throws an {@link UnknownElementException}.
221 *
222 * <p>This method is used when testing iterators without a known ordering. We poll the target
223 * iterator's next element and pass it to the reference iterator through this method so it can
224 * return the same element. This enables the assertion to pass and the reference iterator to
225 * properly update its state.
226 */
227 void promoteToNext(E e) {
228 if (nextElements.remove(e)) {
229 nextElements.push(e);
230 } else {
231 throw new UnknownElementException(nextElements, e);
232 }
233 }
234
235 private E transferElement(Stack<E> source, Stack<E> destination) {
236 if (source.isEmpty()) {
237 throw PermittedMetaException.NSEE;
238 }
239
240 destination.push(source.pop());
241 stackWithLastReturnedElementAtTop = destination;
242 return destination.peek();
243 }
244
245 private void throwIfInvalid(IteratorFeature methodFeature) {
246 if (!features.contains(methodFeature)) {
247 if (stackWithLastReturnedElementAtTop == null) {
248 throw PermittedMetaException.UOE_OR_ISE;
249 } else {
250 throw PermittedMetaException.UOE;
251 }
252 } else if (stackWithLastReturnedElementAtTop == null) {
253 throw PermittedMetaException.ISE;
254 }
255 }
256
257 private List<E> getElements() {
258 List<E> elements = new ArrayList<E>();
259 Helpers.addAll(elements, previousElements);
260 Helpers.addAll(elements, Helpers.reverse(nextElements));
261 return elements;
262 }
263 }
264
265 public enum KnownOrder {
266 KNOWN_ORDER,
267 UNKNOWN_ORDER
268 }
269
270 @SuppressWarnings("unchecked") // creating array of generic class Stimulus
271 AbstractIteratorTester(
272 int steps,
273 Iterable<E> elementsToInsertIterable,
274 Iterable<? extends IteratorFeature> features,
275 Iterable<E> expectedElements,
276 KnownOrder knownOrder,
277 int startIndex) {
278 // periodically we should manually try (steps * 3 / 2) here; all tests but
279 // one should still pass (testVerifyGetsCalled()).
280 stimuli = new Stimulus[steps];
281 if (!elementsToInsertIterable.iterator().hasNext()) {
282 throw new IllegalArgumentException();
283 }
284 elementsToInsert = Helpers.cycle(elementsToInsertIterable);
285 this.features = Helpers.copyToSet(features);
286 this.expectedElements = Helpers.copyToList(expectedElements);
287 this.knownOrder = knownOrder;
288 this.startIndex = startIndex;
289 }
290
291 /**
292 * I'd like to make this a parameter to the constructor, but I can't because the stimulus
293 * instances refer to {@code this}.
294 */
295 protected abstract Iterable<? extends Stimulus<E, ? super I>> getStimulusValues();
296
297 /**
298 * Returns a new target iterator each time it's called. This is the iterator you are trying to
299 * test. This must return an Iterator that returns the expected elements passed to the constructor
300 * in the given order. Warning: it is not enough to simply pull multiple iterators from the same
301 * source Iterable, unless that Iterator is unmodifiable.
302 */
303 protected abstract I newTargetIterator();
304
305 /**
306 * Override this to verify anything after running a list of Stimuli.
307 *
308 * <p>For example, verify that calls to remove() actually removed the correct elements.
309 *
310 * @param elements the expected elements passed to the constructor, as mutated by {@code
311 * remove()}, {@code set()}, and {@code add()} calls
312 */
313 protected void verify(List<E> elements) {}
314
315 /** Executes the test. */
316 public final void test() {
317 try {
318 recurse(0);
319 } catch (RuntimeException e) {
320 throw new RuntimeException(Arrays.toString(stimuli), e);
321 }
322 }
323
324 public void testForEachRemaining() {
325 for (int i = 0; i < expectedElements.size() - 1; i++) {
326 List<E> targetElements = new ArrayList<E>();
327 Iterator<E> iterator = newTargetIterator();
328 for (int j = 0; j < i; j++) {
329 targetElements.add(iterator.next());
330 }
331 iterator.forEachRemaining(targetElements::add);
332 if (knownOrder == KnownOrder.KNOWN_ORDER) {
333 assertEquals(expectedElements, targetElements);
334 } else {
335 Helpers.assertEqualIgnoringOrder(expectedElements, targetElements);
336 }
337 }
338 }
339
340 private void recurse(int level) {
341 // We're going to reuse the stimuli array 3^steps times by overwriting it
342 // in a recursive loop. Sneaky.
343 if (level == stimuli.length) {
344 // We've filled the array.
345 compareResultsForThisListOfStimuli();
346 } else {
347 // Keep recursing to fill the array.
348 for (Stimulus<E, ? super I> stimulus : getStimulusValues()) {
349 stimuli[level] = stimulus;
350 recurse(level + 1);
351 }
352 }
353 }
354
355 private void compareResultsForThisListOfStimuli() {
356 int removes = Collections.frequency(Arrays.asList(stimuli), remove);
357 if ((!features.contains(IteratorFeature.SUPPORTS_REMOVE) && removes > 1)
358 || (stimuli.length >= 5 && removes > 2)) {
359 // removes are the most expensive thing to test, since they often throw exceptions with stack
360 // traces, so we test them a bit less aggressively
361 return;
362 }
363
364 MultiExceptionListIterator reference = new MultiExceptionListIterator(expectedElements);
365 I target = newTargetIterator();
366 for (int i = 0; i < stimuli.length; i++) {
367 try {
368 stimuli[i].executeAndCompare(reference, target);
369 verify(reference.getElements());
370 } catch (AssertionFailedError cause) {
371 Helpers.fail(cause, "failed with stimuli " + subListCopy(stimuli, i + 1));
372 }
373 }
374 }
375
376 private static List<Object> subListCopy(Object[] source, int size) {
377 final Object[] copy = new Object[size];
378 System.arraycopy(source, 0, copy, 0, size);
379 return Arrays.asList(copy);
380 }
381
382 private interface IteratorOperation {
383 @Nullable Object execute(Iterator<?> iterator);
384 }
385
386 /**
387 * Apply this method to both iterators and return normally only if both produce the same response.
388 *
389 * @see Stimulus#executeAndCompare(ListIterator, Iterator)
390 */
391 private <T extends Iterator<E>> void internalExecuteAndCompare(
392 T reference, T target, IteratorOperation method) {
393 Object referenceReturnValue = null;
394 PermittedMetaException referenceException = null;
395 Object targetReturnValue = null;
396 RuntimeException targetException = null;
397
398 try {
399 targetReturnValue = method.execute(target);
400 } catch (RuntimeException e) {
401 targetException = e;
402 }
403
404 try {
405 if (method == NEXT_METHOD
406 && targetException == null
407 && knownOrder == KnownOrder.UNKNOWN_ORDER) {
408 /*
409 * We already know the iterator is an Iterator<E>, and now we know that
410 * we called next(), so the returned element must be of type E.
411 */
412 @SuppressWarnings("unchecked")
413 E targetReturnValueFromNext = (E) targetReturnValue;
414 /*
415 * We have an Iterator<E> and want to cast it to
416 * MultiExceptionListIterator. Because we're inside an
417 * AbstractIteratorTester<E>, that's implicitly a cast to
418 * AbstractIteratorTester<E>.MultiExceptionListIterator. The runtime
419 * won't be able to verify the AbstractIteratorTester<E> part, so it's
420 * an unchecked cast. We know, however, that the only possible value for
421 * the type parameter is <E>, since otherwise the
422 * MultiExceptionListIterator wouldn't be an Iterator<E>. The cast is
423 * safe, even though javac can't tell.
424 *
425 * Sun bug 6665356 is an additional complication. Until OpenJDK 7, javac
426 * doesn't recognize this kind of cast as unchecked cast. Neither does
427 * Eclipse 3.4. Right now, this suppression is mostly unnecessary.
428 */
429 MultiExceptionListIterator multiExceptionListIterator =
430 (MultiExceptionListIterator) reference;
431 multiExceptionListIterator.promoteToNext(targetReturnValueFromNext);
432 }
433
434 referenceReturnValue = method.execute(reference);
435 } catch (PermittedMetaException e) {
436 referenceException = e;
437 } catch (UnknownElementException e) {
438 Helpers.fail(e, e.getMessage());
439 }
440
441 if (referenceException == null) {
442 if (targetException != null) {
443 Helpers.fail(targetException, "Target threw exception when reference did not");
444 }
445
446 /*
447 * Reference iterator returned a value, so we should expect the
448 * same value from the target
449 */
450 assertEquals(referenceReturnValue, targetReturnValue);
451
452 return;
453 }
454
455 if (targetException == null) {
456 fail("Target failed to throw " + referenceException);
457 }
458
459 /*
460 * Reference iterator threw an exception, so we should expect an acceptable
461 * exception from the target.
462 */
463 referenceException.assertPermitted(targetException);
464 }
465
466 private static final IteratorOperation REMOVE_METHOD =
467 new IteratorOperation() {
468 @Override
469 public @Nullable Object execute(Iterator<?> iterator) {
470 iterator.remove();
471 return null;
472 }
473 };
474
475 private static final IteratorOperation NEXT_METHOD =
476 new IteratorOperation() {
477 @Override
478 public Object execute(Iterator<?> iterator) {
479 return iterator.next();
480 }
481 };
482
483 private static final IteratorOperation PREVIOUS_METHOD =
484 new IteratorOperation() {
485 @Override
486 public Object execute(Iterator<?> iterator) {
487 return ((ListIterator<?>) iterator).previous();
488 }
489 };
490
491 private final IteratorOperation newAddMethod() {
492 final Object toInsert = elementsToInsert.next();
493 return new IteratorOperation() {
494 @Override
495 public @Nullable Object execute(Iterator<?> iterator) {
496 @SuppressWarnings("unchecked")
497 ListIterator<Object> rawIterator = (ListIterator<Object>) iterator;
498 rawIterator.add(toInsert);
499 return null;
500 }
501 };
502 }
503
504 private final IteratorOperation newSetMethod() {
505 final E toInsert = elementsToInsert.next();
506 return new IteratorOperation() {
507 @Override
508 public @Nullable Object execute(Iterator<?> iterator) {
509 @SuppressWarnings("unchecked")
510 ListIterator<E> li = (ListIterator<E>) iterator;
511 li.set(toInsert);
512 return null;
513 }
514 };
515 }
516
517 abstract static class Stimulus<E, T extends Iterator<E>> {
518 private final String toString;
519
520 protected Stimulus(String toString) {
521 this.toString = toString;
522 }
523
524 /**
525 * Send this stimulus to both iterators and return normally only if both produce the same
526 * response.
527 */
528 abstract void executeAndCompare(ListIterator<E> reference, T target);
529
530 @Override
531 public String toString() {
532 return toString;
533 }
534 }
535
536 Stimulus<E, Iterator<E>> hasNext =
537 new Stimulus<E, Iterator<E>>("hasNext") {
538 @Override
539 void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
540 assertEquals(reference.hasNext(), target.hasNext());
541 }
542 };
543 Stimulus<E, Iterator<E>> next =
544 new Stimulus<E, Iterator<E>>("next") {
545 @Override
546 void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
547 internalExecuteAndCompare(reference, target, NEXT_METHOD);
548 }
549 };
550 Stimulus<E, Iterator<E>> remove =
551 new Stimulus<E, Iterator<E>>("remove") {
552 @Override
553 void executeAndCompare(ListIterator<E> reference, Iterator<E> target) {
554 internalExecuteAndCompare(reference, target, REMOVE_METHOD);
555 }
556 };
557
558 @SuppressWarnings("unchecked")
559 List<Stimulus<E, Iterator<E>>> iteratorStimuli() {
560 return Arrays.asList(hasNext, next, remove);
561 }
562
563 Stimulus<E, ListIterator<E>> hasPrevious =
564 new Stimulus<E, ListIterator<E>>("hasPrevious") {
565 @Override
566 void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
567 assertEquals(reference.hasPrevious(), target.hasPrevious());
568 }
569 };
570 Stimulus<E, ListIterator<E>> nextIndex =
571 new Stimulus<E, ListIterator<E>>("nextIndex") {
572 @Override
573 void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
574 assertEquals(reference.nextIndex(), target.nextIndex());
575 }
576 };
577 Stimulus<E, ListIterator<E>> previousIndex =
578 new Stimulus<E, ListIterator<E>>("previousIndex") {
579 @Override
580 void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
581 assertEquals(reference.previousIndex(), target.previousIndex());
582 }
583 };
584 Stimulus<E, ListIterator<E>> previous =
585 new Stimulus<E, ListIterator<E>>("previous") {
586 @Override
587 void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
588 internalExecuteAndCompare(reference, target, PREVIOUS_METHOD);
589 }
590 };
591 Stimulus<E, ListIterator<E>> add =
592 new Stimulus<E, ListIterator<E>>("add") {
593 @Override
594 void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
595 internalExecuteAndCompare(reference, target, newAddMethod());
596 }
597 };
598 Stimulus<E, ListIterator<E>> set =
599 new Stimulus<E, ListIterator<E>>("set") {
600 @Override
601 void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
602 internalExecuteAndCompare(reference, target, newSetMethod());
603 }
604 };
605
606 @SuppressWarnings("unchecked")
607 List<Stimulus<E, ListIterator<E>>> listIteratorStimuli() {
608 return Arrays.asList(hasPrevious, nextIndex, previousIndex, previous, add, set);
609 }
610 }