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
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 abstract class AbstractIteratorTester<E, I extends Iterator<E>> {
45 private Stimulus<E, ? super I>[] stimuli;
46 private final Iterator<E> elementsToInsert;
47 private final Set<IteratorFeature> features;
48 private final List<E> expectedElements;
49 private final int startIndex;
50 private final KnownOrder knownOrder;
51
52 /**
53 * Meta-exception thrown by {@link AbstractIteratorTester.MultiExceptionListIterator} instead of
54 * throwing any particular exception type.
55 */
56 private abstract static class PermittedMetaException extends RuntimeException {
57 static final PermittedMetaException UOE_OR_ISE =
58 new PermittedMetaException("UnsupportedOperationException or IllegalStateException") {
59 @Override
60 boolean isPermitted(RuntimeException exception) {
61 return exception instanceof UnsupportedOperationException
62 || exception instanceof IllegalStateException;
63 }
64 };
65 static final PermittedMetaException UOE =
66 new PermittedMetaException("UnsupportedOperationException") {
67 @Override
68 boolean isPermitted(RuntimeException exception) {
69 return exception instanceof UnsupportedOperationException;
70 }
71 };
72 static final PermittedMetaException ISE =
73 new PermittedMetaException("IllegalStateException") {
74 @Override
75 boolean isPermitted(RuntimeException exception) {
76 return exception instanceof IllegalStateException;
77 }
78 };
79 static final PermittedMetaException NSEE =
80 new PermittedMetaException("NoSuchElementException") {
81 @Override
82 boolean isPermitted(RuntimeException exception) {
83 return exception instanceof NoSuchElementException;
84 }
85 };
86
87 private PermittedMetaException(String message) {
88 super(message);
89 }
90
91 abstract boolean isPermitted(RuntimeException exception);
92
93 void assertPermitted(RuntimeException exception) {
94 if (!isPermitted(exception)) {
95 String message =
96 "Exception "
97 + exception.getClass().getSimpleName()
98 + " was thrown; expected "
99 + getMessage();
100 Helpers.fail(exception, message);
101 }
102 }
103
104 private static final long serialVersionUID = 0;
105 }
106
107 private static final class UnknownElementException extends RuntimeException {
108 private UnknownElementException(Collection<?> expected, Object actual) {
109 super("Returned value '" + actual + "' not found. Remaining elements: " + expected);
110 }
111
112 private static final long serialVersionUID = 0;
113 }
114
115 /**
116 * Quasi-implementation of {@link ListIterator} that works from a list of elements and a set of
117 * features to support (from the enclosing {@link AbstractIteratorTester} instance). Instead of
118 * throwing exceptions like {@link NoSuchElementException} at the appropriate times, it throws
119 * {@link PermittedMetaException} instances, which wrap a set of all exceptions that the iterator
120 * could throw during the invocation of that method. This is necessary because, e.g., a call to
121 * {@code iterator().remove()} of an unmodifiable list could throw either {@link
122 * IllegalStateException} or {@link UnsupportedOperationException}. Note that iterator
123 * implementations should always throw one of the exceptions in a {@code PermittedExceptions}
124 * instance, since {@code PermittedExceptions} is thrown only when a method call is invalid.
125 *
126 * <p>This class is accessible but not supported in GWT as it references {@link
127 * PermittedMetaException}.
128 */
129 protected final class MultiExceptionListIterator implements ListIterator<E> {
130 // TODO: track seen elements when order isn't guaranteed
131 // TODO: verify contents afterward
132 // TODO: something shiny and new instead of Stack
133 // TODO: test whether null is supported (create a Feature)
134 /**
135 * The elements to be returned by future calls to {@code next()}, with the first at the top of
136 * the stack.
137 */
138 final Stack<E> nextElements = new Stack<E>();
139 /**
140 * The elements to be returned by future calls to {@code previous()}, with the first at the top
141 * of the stack.
142 */
143 final Stack<E> previousElements = new Stack<E>();
144 /**
145 * {@link #nextElements} if {@code next()} was called more recently then {@code previous},
146 * {@link #previousElements} if the reverse is true, or -- overriding both of these -- {@code
147 * null} if {@code remove()} or {@code add()} has been called more recently than either. We use
148 * this to determine which stack to pop from on a call to {@code remove()} (or to pop from and
149 * push to on a call to {@code set()}.
150 */
151 Stack<E> stackWithLastReturnedElementAtTop = null;
152
153 MultiExceptionListIterator(List<E> expectedElements) {
154 Helpers.addAll(nextElements, Helpers.reverse(expectedElements));
155 for (int i = 0; i < startIndex; i++) {
156 previousElements.push(nextElements.pop());
157 }
158 }
159
160 @Override
161 public void add(E e) {
162 if (!features.contains(IteratorFeature.SUPPORTS_ADD)) {
163 throw PermittedMetaException.UOE;
164 }
165
166 previousElements.push(e);
167 stackWithLastReturnedElementAtTop = null;
168 }
169
170 @Override
171 public boolean hasNext() {
172 return !nextElements.isEmpty();
173 }
174
175 @Override
176 public boolean hasPrevious() {
177 return !previousElements.isEmpty();
178 }
179
180 @Override
181 public E next() {
182 return transferElement(nextElements, previousElements);
183 }
184
185 @Override
186 public int nextIndex() {
187 return previousElements.size();
188 }
189
190 @Override
191 public E previous() {
192 return transferElement(previousElements, nextElements);
193 }
194
195 @Override
196 public int previousIndex() {
197 return nextIndex() - 1;
198 }
199
200 @Override
201 public void remove() {
202 throwIfInvalid(IteratorFeature.SUPPORTS_REMOVE);
203
204 stackWithLastReturnedElementAtTop.pop();
205 stackWithLastReturnedElementAtTop = null;
206 }
207
208 @Override
209 public void set(E e) {
210 throwIfInvalid(IteratorFeature.SUPPORTS_SET);
211
212 stackWithLastReturnedElementAtTop.pop();
213 stackWithLastReturnedElementAtTop.push(e);
214 }
215
216 /**
217 * Moves the given element from its current position in {@link #nextElements} to the top of the
218 * stack so that it is returned by the next call to {@link Iterator#next()}. If the element is
219 * not in {@link #nextElements}, this method throws an {@link UnknownElementException}.
220 *
221 * <p>This method is used when testing iterators without a known ordering. We poll the target
222 * iterator's next element and pass it to the reference iterator through this method so it can
223 * return the same element. This enables the assertion to pass and the reference iterator to
224 * properly update its state.
225 */
226 void promoteToNext(E e) {
227 if (nextElements.remove(e)) {
228 nextElements.push(e);
229 } else {
230 throw new UnknownElementException(nextElements, e);
231 }
232 }
233
234 private E transferElement(Stack<E> source, Stack<E> destination) {
235 if (source.isEmpty()) {
236 throw PermittedMetaException.NSEE;
237 }
238
239 destination.push(source.pop());
240 stackWithLastReturnedElementAtTop = destination;
241 return destination.peek();
242 }
243
244 private void throwIfInvalid(IteratorFeature methodFeature) {
245 if (!features.contains(methodFeature)) {
246 if (stackWithLastReturnedElementAtTop == null) {
247 throw PermittedMetaException.UOE_OR_ISE;
248 } else {
249 throw PermittedMetaException.UOE;
250 }
251 } else if (stackWithLastReturnedElementAtTop == null) {
252 throw PermittedMetaException.ISE;
253 }
254 }
255
256 private List<E> getElements() {
257 List<E> elements = new ArrayList<E>();
258 Helpers.addAll(elements, previousElements);
259 Helpers.addAll(elements, Helpers.reverse(nextElements));
260 return elements;
261 }
262 }
263
264 public enum KnownOrder {
265 KNOWN_ORDER,
266 UNKNOWN_ORDER
267 }
268
269 @SuppressWarnings("unchecked") // creating array of generic class Stimulus
270 AbstractIteratorTester(
271 int steps,
272 Iterable<E> elementsToInsertIterable,
273 Iterable<? extends IteratorFeature> features,
274 Iterable<E> expectedElements,
275 KnownOrder knownOrder,
276 int startIndex) {
277 // periodically we should manually try (steps * 3 / 2) here; all tests but
278 // one should still pass (testVerifyGetsCalled()).
279 stimuli = new Stimulus[steps];
280 if (!elementsToInsertIterable.iterator().hasNext()) {
281 throw new IllegalArgumentException();
282 }
283 elementsToInsert = Helpers.cycle(elementsToInsertIterable);
284 this.features = Helpers.copyToSet(features);
285 this.expectedElements = Helpers.copyToList(expectedElements);
286 this.knownOrder = knownOrder;
287 this.startIndex = startIndex;
288 }
289
290 /**
291 * I'd like to make this a parameter to the constructor, but I can't because the stimulus
292 * instances refer to {@code this}.
293 */
294 protected abstract Iterable<? extends Stimulus<E, ? super I>> getStimulusValues();
295
296 /**
297 * Returns a new target iterator each time it's called. This is the iterator you are trying to
298 * test. This must return an Iterator that returns the expected elements passed to the constructor
299 * in the given order. Warning: it is not enough to simply pull multiple iterators from the same
300 * source Iterable, unless that Iterator is unmodifiable.
301 */
302 protected abstract I newTargetIterator();
303
304 /**
305 * Override this to verify anything after running a list of Stimuli.
306 *
307 * <p>For example, verify that calls to remove() actually removed the correct elements.
308 *
309 * @param elements the expected elements passed to the constructor, as mutated by {@code
310 * remove()}, {@code set()}, and {@code add()} calls
311 */
312 protected void verify(List<E> elements) {}
313
314 /** Executes the test. */
315 public final void test() {
316 try {
317 recurse(0);
318 } catch (RuntimeException e) {
319 throw new RuntimeException(Arrays.toString(stimuli), e);
320 }
321 }
322
323 public void testForEachRemaining() {
324 for (int i = 0; i < expectedElements.size() - 1; i++) {
325 List<E> targetElements = new ArrayList<E>();
326 Iterator<E> iterator = newTargetIterator();
327 for (int j = 0; j < i; j++) {
328 targetElements.add(iterator.next());
329 }
330 iterator.forEachRemaining(targetElements::add);
331 if (knownOrder == KnownOrder.KNOWN_ORDER) {
332 assertEquals(expectedElements, targetElements);
333 } else {
334 Helpers.assertEqualIgnoringOrder(expectedElements, targetElements);
335 }
336 }
337 }
338
339 private void recurse(int level) {
340 // We're going to reuse the stimuli array 3^steps times by overwriting it
341 // in a recursive loop. Sneaky.
342 if (level == stimuli.length) {
343 // We've filled the array.
344 compareResultsForThisListOfStimuli();
345 } else {
346 // Keep recursing to fill the array.
347 for (Stimulus<E, ? super I> stimulus : getStimulusValues()) {
348 stimuli[level] = stimulus;
349 recurse(level + 1);
350 }
351 }
352 }
353
354 private void compareResultsForThisListOfStimuli() {
355 int removes = Collections.frequency(Arrays.asList(stimuli), remove);
356 if ((!features.contains(IteratorFeature.SUPPORTS_REMOVE) && removes > 1)
357 || (stimuli.length >= 5 && removes > 2)) {
358 // removes are the most expensive thing to test, since they often throw exceptions with stack
359 // traces, so we test them a bit less aggressively
360 return;
361 }
362
363 MultiExceptionListIterator reference = new MultiExceptionListIterator(expectedElements);
364 I target = newTargetIterator();
365 for (int i = 0; i < stimuli.length; i++) {
366 try {
367 stimuli[i].executeAndCompare(reference, target);
368 verify(reference.getElements());
369 } catch (AssertionFailedError cause) {
370 Helpers.fail(cause, "failed with stimuli " + subListCopy(stimuli, i + 1));
371 }
372 }
373 }
374
375 private static List<Object> subListCopy(Object[] source, int size) {
376 final Object[] copy = new Object[size];
377 System.arraycopy(source, 0, copy, 0, size);
378 return Arrays.asList(copy);
379 }
380
381 private interface IteratorOperation {
382 Object execute(Iterator<?> iterator);
383 }
384
385 /**
386 * Apply this method to both iterators and return normally only if both produce the same response.
387 *
388 * @see Stimulus#executeAndCompare(ListIterator, Iterator)
389 */
390 private <T extends Iterator<E>> void internalExecuteAndCompare(
391 T reference, T target, IteratorOperation method) {
392 Object referenceReturnValue = null;
393 PermittedMetaException referenceException = null;
394 Object targetReturnValue = null;
395 RuntimeException targetException = null;
396
397 try {
398 targetReturnValue = method.execute(target);
399 } catch (RuntimeException e) {
400 targetException = e;
401 }
402
403 try {
404 if (method == NEXT_METHOD
405 && targetException == null
406 && knownOrder == KnownOrder.UNKNOWN_ORDER) {
407 /*
408 * We already know the iterator is an Iterator<E>, and now we know that
409 * we called next(), so the returned element must be of type E.
410 */
411 @SuppressWarnings("unchecked")
412 E targetReturnValueFromNext = (E) targetReturnValue;
413 /*
414 * We have an Iterator<E> and want to cast it to
415 * MultiExceptionListIterator. Because we're inside an
416 * AbstractIteratorTester<E>, that's implicitly a cast to
417 * AbstractIteratorTester<E>.MultiExceptionListIterator. The runtime
418 * won't be able to verify the AbstractIteratorTester<E> part, so it's
419 * an unchecked cast. We know, however, that the only possible value for
420 * the type parameter is <E>, since otherwise the
421 * MultiExceptionListIterator wouldn't be an Iterator<E>. The cast is
422 * safe, even though javac can't tell.
423 *
424 * Sun bug 6665356 is an additional complication. Until OpenJDK 7, javac
425 * doesn't recognize this kind of cast as unchecked cast. Neither does
426 * Eclipse 3.4. Right now, this suppression is mostly unnecessary.
427 */
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 Helpers.fail(e, e.getMessage());
438 }
439
440 if (referenceException == null) {
441 if (targetException != null) {
442 Helpers.fail(targetException, "Target threw exception when reference did not");
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 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 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 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 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 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, 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 @SuppressWarnings("unchecked")
558 List<Stimulus<E, Iterator<E>>> iteratorStimuli() {
559 return Arrays.asList(hasNext, next, remove);
560 }
561
562 Stimulus<E, ListIterator<E>> hasPrevious =
563 new Stimulus<E, ListIterator<E>>("hasPrevious") {
564 @Override
565 void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
566 assertEquals(reference.hasPrevious(), target.hasPrevious());
567 }
568 };
569 Stimulus<E, ListIterator<E>> nextIndex =
570 new Stimulus<E, ListIterator<E>>("nextIndex") {
571 @Override
572 void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
573 assertEquals(reference.nextIndex(), target.nextIndex());
574 }
575 };
576 Stimulus<E, ListIterator<E>> previousIndex =
577 new Stimulus<E, ListIterator<E>>("previousIndex") {
578 @Override
579 void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
580 assertEquals(reference.previousIndex(), target.previousIndex());
581 }
582 };
583 Stimulus<E, ListIterator<E>> previous =
584 new Stimulus<E, ListIterator<E>>("previous") {
585 @Override
586 void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
587 internalExecuteAndCompare(reference, target, PREVIOUS_METHOD);
588 }
589 };
590 Stimulus<E, ListIterator<E>> add =
591 new Stimulus<E, ListIterator<E>>("add") {
592 @Override
593 void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
594 internalExecuteAndCompare(reference, target, newAddMethod());
595 }
596 };
597 Stimulus<E, ListIterator<E>> set =
598 new Stimulus<E, ListIterator<E>>("set") {
599 @Override
600 void executeAndCompare(ListIterator<E> reference, ListIterator<E> target) {
601 internalExecuteAndCompare(reference, target, newSetMethod());
602 }
603 };
604
605 @SuppressWarnings("unchecked")
606 List<Stimulus<E, ListIterator<E>>> listIteratorStimuli() {
607 return Arrays.asList(hasPrevious, nextIndex, previousIndex, previous, add, set);
608 }
609 }