AbstractIteratorTester.java revision 7dd252788645e940eada959bdde927426e2531c9
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 17package com.google.common.collect.testing; 18 19import static junit.framework.Assert.assertEquals; 20import static junit.framework.Assert.fail; 21 22import com.google.common.annotations.GwtCompatible; 23 24import junit.framework.AssertionFailedError; 25 26import java.util.ArrayList; 27import java.util.Arrays; 28import java.util.Collection; 29import java.util.Collections; 30import java.util.HashSet; 31import java.util.Iterator; 32import java.util.List; 33import java.util.ListIterator; 34import java.util.NoSuchElementException; 35import java.util.Set; 36import java.util.Stack; 37 38/** 39 * Most of the logic for {@link IteratorTester} and {@link ListIteratorTester}. 40 * 41 * <p>This class is GWT compatible. 42 * 43 * @param <E> the type of element returned by the iterator 44 * @param <I> the type of the iterator ({@link Iterator} or 45 * {@link ListIterator}) 46 * 47 * @author Kevin Bourrillion 48 * @author Chris Povirk 49 */ 50@GwtCompatible 51abstract class AbstractIteratorTester<E, I extends Iterator<E>> { 52 private boolean whenNextThrowsExceptionStopTestingCallsToRemove; 53 private boolean whenAddThrowsExceptionStopTesting; 54 55 /** 56 * Don't verify iterator behavior on remove() after a call to next() 57 * throws an exception. 58 * 59 * <p>JDK 6 currently has a bug where some iterators get into a undefined 60 * state when next() throws a NoSuchElementException. The correct 61 * behavior is for remove() to remove the last element returned by 62 * next, even if a subsequent next() call threw an exception; however 63 * JDK 6's HashMap and related classes throw an IllegalStateException 64 * in this case. 65 * 66 * <p>Calling this method causes the iterator tester to skip testing 67 * any remove() in a stimulus sequence after the reference iterator 68 * throws an exception in next(). 69 * 70 * <p>TODO: remove this once we're on 6u5, which has the fix. 71 * 72 * @see <a href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6529795"> 73 * Sun Java Bug 6529795</a> 74 */ 75 public void ignoreSunJavaBug6529795() { 76 whenNextThrowsExceptionStopTestingCallsToRemove = true; 77 } 78 79 /** 80 * Don't verify iterator behavior after a call to add() throws an exception. 81 * 82 * <p>AbstractList's ListIterator implementation gets into a undefined state 83 * when add() throws an UnsupportedOperationException. Instead of leaving the 84 * iterator's position unmodified, it increments it, skipping an element or 85 * even moving past the end of the list. 86 * 87 * <p>Calling this method causes the iterator tester to skip testing in a 88 * stimulus sequence after the iterator under test throws an exception in 89 * add(). 90 * 91 * <p>TODO: remove this once the behavior is fixed. 92 * 93 * @see <a href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6533203"> 94 * Sun Java Bug 6533203</a> 95 */ 96 public void stopTestingWhenAddThrowsException() { 97 whenAddThrowsExceptionStopTesting = true; 98 } 99 100 private Stimulus<E, ? super I>[] stimuli; 101 private final Iterator<E> elementsToInsert; 102 private final Set<IteratorFeature> features; 103 private final List<E> expectedElements; 104 private final int startIndex; 105 private final KnownOrder knownOrder; 106 107 /** 108 * Meta-exception thrown by 109 * {@link AbstractIteratorTester.MultiExceptionListIterator} instead of 110 * throwing any particular exception type. 111 */ 112 // This class is accessible but not supported in GWT. 113 private static final class PermittedMetaException extends RuntimeException { 114 final Set<? extends Class<? extends RuntimeException>> exceptionClasses; 115 116 PermittedMetaException( 117 Set<? extends Class<? extends RuntimeException>> exceptionClasses) { 118 super("one of " + exceptionClasses); 119 this.exceptionClasses = exceptionClasses; 120 } 121 122 PermittedMetaException(Class<? extends RuntimeException> exceptionClass) { 123 this(Collections.singleton(exceptionClass)); 124 } 125 126 // It's not supported In GWT, it always returns true. 127 boolean isPermitted(RuntimeException exception) { 128 for (Class<? extends RuntimeException> clazz : exceptionClasses) { 129 if (Platform.checkIsInstance(clazz, exception)) { 130 return true; 131 } 132 } 133 return false; 134 } 135 136 // It's not supported in GWT, it always passes. 137 void assertPermitted(RuntimeException exception) { 138 if (!isPermitted(exception)) { 139 // TODO: use simple class names 140 String message = "Exception " + exception.getClass() 141 + " was thrown; expected " + this; 142 Helpers.fail(exception, message); 143 } 144 } 145 146 @Override public String toString() { 147 return getMessage(); 148 } 149 150 private static final long serialVersionUID = 0; 151 } 152 153 private static final class UnknownElementException extends RuntimeException { 154 private UnknownElementException(Collection<?> expected, Object actual) { 155 super("Returned value '" 156 + actual + "' not found. Remaining elements: " + expected); 157 } 158 159 private static final long serialVersionUID = 0; 160 } 161 162 /** 163 * Quasi-implementation of {@link ListIterator} that works from a list of 164 * elements and a set of features to support (from the enclosing 165 * {@link AbstractIteratorTester} instance). Instead of throwing exceptions 166 * like {@link NoSuchElementException} at the appropriate times, it throws 167 * {@link PermittedMetaException} instances, which wrap a set of all 168 * exceptions that the iterator could throw during the invocation of that 169 * method. This is necessary because, e.g., a call to 170 * {@code iterator().remove()} of an unmodifiable list could throw either 171 * {@link IllegalStateException} or {@link UnsupportedOperationException}. 172 * Note that iterator implementations should always throw one of the 173 * exceptions in a {@code PermittedExceptions} instance, since 174 * {@code PermittedExceptions} is thrown only when a method call is invalid. 175 * 176 * <p>This class is accessible but not supported in GWT as it references 177 * {@link PermittedMetaException}. 178 */ 179 protected final class MultiExceptionListIterator implements ListIterator<E> { 180 // TODO: track seen elements when order isn't guaranteed 181 // TODO: verify contents afterward 182 // TODO: something shiny and new instead of Stack 183 // TODO: test whether null is supported (create a Feature) 184 /** 185 * The elements to be returned by future calls to {@code next()}, with the 186 * first at the top of the stack. 187 */ 188 final Stack<E> nextElements = new Stack<E>(); 189 /** 190 * The elements to be returned by future calls to {@code previous()}, with 191 * the first at the top of the stack. 192 */ 193 final Stack<E> previousElements = new Stack<E>(); 194 /** 195 * {@link #nextElements} if {@code next()} was called more recently then 196 * {@code previous}, {@link #previousElements} if the reverse is true, or -- 197 * overriding both of these -- {@code null} if {@code remove()} or 198 * {@code add()} has been called more recently than either. We use this to 199 * determine which stack to pop from on a call to {@code remove()} (or to 200 * pop from and push to on a call to {@code set()}. 201 */ 202 Stack<E> stackWithLastReturnedElementAtTop = null; 203 204 MultiExceptionListIterator(List<E> expectedElements) { 205 Helpers.addAll(nextElements, Helpers.reverse(expectedElements)); 206 for (int i = 0; i < startIndex; i++) { 207 previousElements.push(nextElements.pop()); 208 } 209 } 210 211 @Override 212 public void add(E e) { 213 if (!features.contains(IteratorFeature.SUPPORTS_ADD)) { 214 throw new PermittedMetaException(UnsupportedOperationException.class); 215 } 216 217 previousElements.push(e); 218 stackWithLastReturnedElementAtTop = null; 219 } 220 221 @Override 222 public boolean hasNext() { 223 return !nextElements.isEmpty(); 224 } 225 226 @Override 227 public boolean hasPrevious() { 228 return !previousElements.isEmpty(); 229 } 230 231 @Override 232 public E next() { 233 return transferElement(nextElements, previousElements); 234 } 235 236 @Override 237 public int nextIndex() { 238 return previousElements.size(); 239 } 240 241 @Override 242 public E previous() { 243 return transferElement(previousElements, nextElements); 244 } 245 246 @Override 247 public int previousIndex() { 248 return nextIndex() - 1; 249 } 250 251 @Override 252 public void remove() { 253 throwIfInvalid(IteratorFeature.SUPPORTS_REMOVE); 254 255 stackWithLastReturnedElementAtTop.pop(); 256 stackWithLastReturnedElementAtTop = null; 257 } 258 259 @Override 260 public void set(E e) { 261 throwIfInvalid(IteratorFeature.SUPPORTS_SET); 262 263 stackWithLastReturnedElementAtTop.pop(); 264 stackWithLastReturnedElementAtTop.push(e); 265 } 266 267 /** 268 * Moves the given element from its current position in 269 * {@link #nextElements} to the top of the stack so that it is returned by 270 * the next call to {@link Iterator#next()}. If the element is not in 271 * {@link #nextElements}, this method throws an 272 * {@link UnknownElementException}. 273 * 274 * <p>This method is used when testing iterators without a known ordering. 275 * We poll the target iterator's next element and pass it to the reference 276 * iterator through this method so it can return the same element. This 277 * enables the assertion to pass and the reference iterator to properly 278 * update its state. 279 */ 280 void promoteToNext(E e) { 281 if (nextElements.remove(e)) { 282 nextElements.push(e); 283 } else { 284 throw new UnknownElementException(nextElements, e); 285 } 286 } 287 288 private E transferElement(Stack<E> source, Stack<E> destination) { 289 if (source.isEmpty()) { 290 throw new PermittedMetaException(NoSuchElementException.class); 291 } 292 293 destination.push(source.pop()); 294 stackWithLastReturnedElementAtTop = destination; 295 return destination.peek(); 296 } 297 298 private void throwIfInvalid(IteratorFeature methodFeature) { 299 Set<Class<? extends RuntimeException>> exceptions 300 = new HashSet<Class<? extends RuntimeException>>(); 301 302 if (!features.contains(methodFeature)) { 303 exceptions.add(UnsupportedOperationException.class); 304 } 305 306 if (stackWithLastReturnedElementAtTop == null) { 307 exceptions.add(IllegalStateException.class); 308 } 309 310 if (!exceptions.isEmpty()) { 311 throw new PermittedMetaException(exceptions); 312 } 313 } 314 315 private List<E> getElements() { 316 List<E> elements = new ArrayList<E>(); 317 Helpers.addAll(elements, previousElements); 318 Helpers.addAll(elements, Helpers.reverse(nextElements)); 319 return elements; 320 } 321 } 322 323 public enum KnownOrder { KNOWN_ORDER, UNKNOWN_ORDER } 324 325 @SuppressWarnings("unchecked") // creating array of generic class Stimulus 326 AbstractIteratorTester(int steps, Iterable<E> elementsToInsertIterable, 327 Iterable<? extends IteratorFeature> features, 328 Iterable<E> expectedElements, KnownOrder knownOrder, int startIndex) { 329 // periodically we should manually try (steps * 3 / 2) here; all tests but 330 // one should still pass (testVerifyGetsCalled()). 331 stimuli = new Stimulus[steps]; 332 if (!elementsToInsertIterable.iterator().hasNext()) { 333 throw new IllegalArgumentException(); 334 } 335 elementsToInsert = Helpers.cycle(elementsToInsertIterable); 336 this.features = Helpers.copyToSet(features); 337 this.expectedElements = Helpers.copyToList(expectedElements); 338 this.knownOrder = knownOrder; 339 this.startIndex = startIndex; 340 } 341 342 /** 343 * I'd like to make this a parameter to the constructor, but I can't because 344 * the stimulus instances refer to {@code this}. 345 */ 346 protected abstract Iterable<? extends Stimulus<E, ? super I>> 347 getStimulusValues(); 348 349 /** 350 * Returns a new target iterator each time it's called. This is the iterator 351 * you are trying to test. This must return an Iterator that returns the 352 * expected elements passed to the constructor in the given order. Warning: it 353 * is not enough to simply pull multiple iterators from the same source 354 * Iterable, unless that Iterator is unmodifiable. 355 */ 356 protected abstract I newTargetIterator(); 357 358 /** 359 * Override this to verify anything after running a list of Stimuli. 360 * 361 * <p>For example, verify that calls to remove() actually removed 362 * the correct elements. 363 * 364 * @param elements the expected elements passed to the constructor, as mutated 365 * by {@code remove()}, {@code set()}, and {@code add()} calls 366 */ 367 protected void verify(List<E> elements) {} 368 369 /** 370 * Executes the test. 371 */ 372 public final void test() { 373 try { 374 recurse(0); 375 } catch (RuntimeException e) { 376 throw new RuntimeException(Arrays.toString(stimuli), e); 377 } 378 } 379 380 private void recurse(int level) { 381 // We're going to reuse the stimuli array 3^steps times by overwriting it 382 // in a recursive loop. Sneaky. 383 if (level == stimuli.length) { 384 // We've filled the array. 385 compareResultsForThisListOfStimuli(); 386 } else { 387 // Keep recursing to fill the array. 388 for (Stimulus<E, ? super I> stimulus : getStimulusValues()) { 389 stimuli[level] = stimulus; 390 recurse(level + 1); 391 } 392 } 393 } 394 395 private void compareResultsForThisListOfStimuli() { 396 MultiExceptionListIterator reference = 397 new MultiExceptionListIterator(expectedElements); 398 I target = newTargetIterator(); 399 boolean shouldStopTestingCallsToRemove = false; 400 for (int i = 0; i < stimuli.length; i++) { 401 Stimulus<E, ? super I> stimulus = stimuli[i]; 402 if (stimulus.equals(remove) && shouldStopTestingCallsToRemove) { 403 break; 404 } 405 try { 406 boolean threwException = stimulus.executeAndCompare(reference, target); 407 if (threwException 408 && stimulus.equals(next) 409 && whenNextThrowsExceptionStopTestingCallsToRemove) { 410 shouldStopTestingCallsToRemove = true; 411 } 412 if (threwException 413 && stimulus.equals(add) 414 && whenAddThrowsExceptionStopTesting) { 415 break; 416 } 417 List<E> elements = reference.getElements(); 418 verify(elements); 419 } catch (AssertionFailedError cause) { 420 Helpers.fail(cause, 421 "failed with stimuli " + subListCopy(stimuli, i + 1)); 422 } 423 } 424 } 425 426 private static List<Object> subListCopy(Object[] source, int size) { 427 final Object[] copy = new Object[size]; 428 System.arraycopy(source, 0, copy, 0, size); 429 return Arrays.asList(copy); 430 } 431 432 private interface IteratorOperation { 433 Object execute(Iterator<?> iterator); 434 } 435 436 /** 437 * Apply this method to both iterators and return normally only if both 438 * produce the same response. 439 * 440 * @return {@code true} if an exception was thrown by the iterators. 441 * 442 * @see Stimulus#executeAndCompare(ListIterator, Iterator) 443 */ 444 private <T extends Iterator<E>> boolean internalExecuteAndCompare( 445 T reference, T target, IteratorOperation method) 446 throws AssertionFailedError { 447 448 Object referenceReturnValue = null; 449 PermittedMetaException referenceException = null; 450 Object targetReturnValue = null; 451 RuntimeException targetException = null; 452 453 try { 454 targetReturnValue = method.execute(target); 455 } catch (RuntimeException e) { 456 targetException = e; 457 } 458 459 try { 460 if (method == NEXT_METHOD && targetException == null 461 && knownOrder == KnownOrder.UNKNOWN_ORDER) { 462 /* 463 * We already know the iterator is an Iterator<E>, and now we know that 464 * we called next(), so the returned element must be of type E. 465 */ 466 @SuppressWarnings("unchecked") 467 E targetReturnValueFromNext = (E) targetReturnValue; 468 /* 469 * We have an Iterator<E> and want to cast it to 470 * MultiExceptionListIterator. Because we're inside an 471 * AbstractIteratorTester<E>, that's implicitly a cast to 472 * AbstractIteratorTester<E>.MultiExceptionListIterator. The runtime 473 * won't be able to verify the AbstractIteratorTester<E> part, so it's 474 * an unchecked cast. We know, however, that the only possible value for 475 * the type parameter is <E>, since otherwise the 476 * MultiExceptionListIterator wouldn't be an Iterator<E>. The cast is 477 * safe, even though javac can't tell. 478 * 479 * Sun bug 6665356 is an additional complication. Until OpenJDK 7, javac 480 * doesn't recognize this kind of cast as unchecked cast. Neither does 481 * Eclipse 3.4. Right now, this suppression is mostly unecessary. 482 */ 483 MultiExceptionListIterator multiExceptionListIterator = 484 (MultiExceptionListIterator) reference; 485 multiExceptionListIterator.promoteToNext(targetReturnValueFromNext); 486 } 487 488 referenceReturnValue = method.execute(reference); 489 } catch (PermittedMetaException e) { 490 referenceException = e; 491 } catch (UnknownElementException e) { 492 Helpers.fail(e, e.getMessage()); 493 } 494 495 if (referenceException == null) { 496 if (targetException != null) { 497 Helpers.fail(targetException, 498 "Target threw exception when reference did not"); 499 } 500 501 /* 502 * Reference iterator returned a value, so we should expect the 503 * same value from the target 504 */ 505 assertEquals(referenceReturnValue, targetReturnValue); 506 507 return false; 508 } 509 510 if (targetException == null) { 511 fail("Target failed to throw " + referenceException); 512 } 513 514 /* 515 * Reference iterator threw an exception, so we should expect an acceptable 516 * exception from the target. 517 */ 518 referenceException.assertPermitted(targetException); 519 520 return true; 521 } 522 523 private static final IteratorOperation REMOVE_METHOD = 524 new IteratorOperation() { 525 @Override 526 public Object execute(Iterator<?> iterator) { 527 iterator.remove(); 528 return null; 529 } 530 }; 531 532 private static final IteratorOperation NEXT_METHOD = 533 new IteratorOperation() { 534 @Override 535 public Object execute(Iterator<?> iterator) { 536 return iterator.next(); 537 } 538 }; 539 540 private static final IteratorOperation PREVIOUS_METHOD = 541 new IteratorOperation() { 542 @Override 543 public Object execute(Iterator<?> iterator) { 544 return ((ListIterator<?>) iterator).previous(); 545 } 546 }; 547 548 private final IteratorOperation newAddMethod() { 549 final Object toInsert = elementsToInsert.next(); 550 return new IteratorOperation() { 551 @Override 552 public Object execute(Iterator<?> iterator) { 553 @SuppressWarnings("unchecked") 554 ListIterator<Object> rawIterator = (ListIterator<Object>) iterator; 555 rawIterator.add(toInsert); 556 return null; 557 } 558 }; 559 } 560 561 private final IteratorOperation newSetMethod() { 562 final E toInsert = elementsToInsert.next(); 563 return new IteratorOperation() { 564 @Override 565 public Object execute(Iterator<?> iterator) { 566 @SuppressWarnings("unchecked") 567 ListIterator<E> li = (ListIterator<E>) iterator; 568 li.set(toInsert); 569 return null; 570 } 571 }; 572 } 573 574 abstract static class Stimulus<E, T extends Iterator<E>> { 575 private final String toString; 576 577 protected Stimulus(String toString) { 578 this.toString = toString; 579 } 580 581 /** 582 * Send this stimulus to both iterators and return normally only if both 583 * produce the same response. 584 * 585 * @return {@code true} if an exception was thrown by the iterators. 586 */ 587 abstract boolean executeAndCompare(ListIterator<E> reference, T target); 588 589 @Override public String toString() { 590 return toString; 591 } 592 } 593 594 Stimulus<E, Iterator<E>> hasNext = new Stimulus<E, Iterator<E>>("hasNext") { 595 @Override boolean 596 executeAndCompare(ListIterator<E> reference, Iterator<E> target) { 597 // return only if both are true or both are false 598 assertEquals(reference.hasNext(), target.hasNext()); 599 return false; 600 } 601 }; 602 Stimulus<E, Iterator<E>> next = new Stimulus<E, Iterator<E>>("next") { 603 @Override boolean 604 executeAndCompare(ListIterator<E> reference, Iterator<E> target) { 605 return internalExecuteAndCompare(reference, target, NEXT_METHOD); 606 } 607 }; 608 Stimulus<E, Iterator<E>> remove = new Stimulus<E, Iterator<E>>("remove") { 609 @Override boolean 610 executeAndCompare(ListIterator<E> reference, Iterator<E> target) { 611 return internalExecuteAndCompare(reference, target, REMOVE_METHOD); 612 } 613 }; 614 615 @SuppressWarnings("unchecked") 616 List<Stimulus<E, Iterator<E>>> iteratorStimuli() { 617 return Arrays.asList(hasNext, next, remove); 618 } 619 620 Stimulus<E, ListIterator<E>> hasPrevious = 621 new Stimulus<E, ListIterator<E>>("hasPrevious") { 622 @Override boolean executeAndCompare( 623 ListIterator<E> reference, ListIterator<E> target) { 624 // return only if both are true or both are false 625 assertEquals(reference.hasPrevious(), target.hasPrevious()); 626 return false; 627 } 628 }; 629 Stimulus<E, ListIterator<E>> nextIndex = 630 new Stimulus<E, ListIterator<E>>("nextIndex") { 631 @Override boolean executeAndCompare( 632 ListIterator<E> reference, ListIterator<E> target) { 633 assertEquals(reference.nextIndex(), target.nextIndex()); 634 return false; 635 } 636 }; 637 Stimulus<E, ListIterator<E>> previousIndex = 638 new Stimulus<E, ListIterator<E>>("previousIndex") { 639 @Override boolean executeAndCompare( 640 ListIterator<E> reference, ListIterator<E> target) { 641 assertEquals(reference.previousIndex(), target.previousIndex()); 642 return false; 643 } 644 }; 645 Stimulus<E, ListIterator<E>> previous = 646 new Stimulus<E, ListIterator<E>>("previous") { 647 @Override boolean executeAndCompare( 648 ListIterator<E> reference, ListIterator<E> target) { 649 return internalExecuteAndCompare(reference, target, PREVIOUS_METHOD); 650 } 651 }; 652 Stimulus<E, ListIterator<E>> add = new Stimulus<E, ListIterator<E>>("add") { 653 @Override boolean executeAndCompare( 654 ListIterator<E> reference, ListIterator<E> target) { 655 return internalExecuteAndCompare(reference, target, newAddMethod()); 656 } 657 }; 658 Stimulus<E, ListIterator<E>> set = new Stimulus<E, ListIterator<E>>("set") { 659 @Override boolean executeAndCompare( 660 ListIterator<E> reference, ListIterator<E> target) { 661 return internalExecuteAndCompare(reference, target, newSetMethod()); 662 } 663 }; 664 665 @SuppressWarnings("unchecked") 666 List<Stimulus<E, ListIterator<E>>> listIteratorStimuli() { 667 return Arrays.asList( 668 hasPrevious, nextIndex, previousIndex, previous, add, set); 669 } 670} 671