--- jsr166/src/test/tck/Collection8Test.java 2016/11/28 17:53:59 1.35 +++ jsr166/src/test/tck/Collection8Test.java 2019/02/22 19:27:47 1.58 @@ -8,16 +8,19 @@ import static java.util.concurrent.TimeUnit.HOURS; import static java.util.concurrent.TimeUnit.MILLISECONDS; +import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Collections; +import java.util.ConcurrentModificationException; import java.util.Deque; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.NoSuchElementException; import java.util.Queue; +import java.util.Set; import java.util.Spliterator; import java.util.concurrent.BlockingDeque; import java.util.concurrent.BlockingQueue; @@ -58,9 +61,10 @@ public class Collection8Test extends JSR Object bomb() { return new Object() { - public boolean equals(Object x) { throw new AssertionError(); } - public int hashCode() { throw new AssertionError(); } - }; + @Override public boolean equals(Object x) { throw new AssertionError(); } + @Override public int hashCode() { throw new AssertionError(); } + @Override public String toString() { throw new AssertionError(); } + }; } /** Checks properties of empty collections. */ @@ -91,6 +95,23 @@ public class Collection8Test extends JSR assertTrue(c.isEmpty()); assertEquals(0, c.size()); assertEquals("[]", c.toString()); + if (c instanceof List) { + List x = (List) c; + assertEquals(1, x.hashCode()); + assertEquals(x, Collections.emptyList()); + assertEquals(Collections.emptyList(), x); + assertEquals(-1, x.indexOf(impl.makeElement(86))); + assertEquals(-1, x.lastIndexOf(impl.makeElement(99))); + assertThrows( + IndexOutOfBoundsException.class, + () -> x.get(0), + () -> x.set(0, impl.makeElement(42))); + } + else if (c instanceof Set) { + assertEquals(0, c.hashCode()); + assertEquals(c, Collections.emptySet()); + assertEquals(Collections.emptySet(), c); + } { Object[] a = c.toArray(); assertEquals(0, a.length); @@ -139,12 +160,12 @@ public class Collection8Test extends JSR } if (c instanceof BlockingQueue) { BlockingQueue q = (BlockingQueue) c; - assertNull(q.poll(0L, MILLISECONDS)); + assertNull(q.poll(randomExpiredTimeout(), randomTimeUnit())); } if (c instanceof BlockingDeque) { BlockingDeque q = (BlockingDeque) c; - assertNull(q.pollFirst(0L, MILLISECONDS)); - assertNull(q.pollLast(0L, MILLISECONDS)); + assertNull(q.pollFirst(randomExpiredTimeout(), randomTimeUnit())); + assertNull(q.pollLast(randomExpiredTimeout(), randomTimeUnit())); } } @@ -161,7 +182,7 @@ public class Collection8Test extends JSR () -> c.iterator().forEachRemaining(null), () -> c.spliterator().forEachRemaining(null), () -> c.spliterator().tryAdvance(null), - () -> c.toArray(null)); + () -> c.toArray((Object[])null)); if (!impl.permitsNulls()) { assertThrows( @@ -189,41 +210,17 @@ public class Collection8Test extends JSR BlockingQueue q = (BlockingQueue) c; assertThrows( NullPointerException.class, - () -> { - try { q.offer(null, 1L, HOURS); } - catch (InterruptedException ex) { - throw new AssertionError(ex); - }}, - () -> { - try { q.put(null); } - catch (InterruptedException ex) { - throw new AssertionError(ex); - }}); + () -> q.offer(null, 1L, HOURS), + () -> q.put(null)); } if (c instanceof BlockingDeque) { BlockingDeque q = (BlockingDeque) c; assertThrows( NullPointerException.class, - () -> { - try { q.offerFirst(null, 1L, HOURS); } - catch (InterruptedException ex) { - throw new AssertionError(ex); - }}, - () -> { - try { q.offerLast(null, 1L, HOURS); } - catch (InterruptedException ex) { - throw new AssertionError(ex); - }}, - () -> { - try { q.putFirst(null); } - catch (InterruptedException ex) { - throw new AssertionError(ex); - }}, - () -> { - try { q.putLast(null); } - catch (InterruptedException ex) { - throw new AssertionError(ex); - }}); + () -> q.offerFirst(null, 1L, HOURS), + () -> q.offerLast(null, 1L, HOURS), + () -> q.putFirst(null), + () -> q.putLast(null)); } } @@ -251,6 +248,16 @@ public class Collection8Test extends JSR () -> d.pop(), () -> d.descendingIterator().next()); } + if (c instanceof List) { + List x = (List) c; + assertThrows( + NoSuchElementException.class, + () -> x.iterator().next(), + () -> x.listIterator().next(), + () -> x.listIterator(0).next(), + () -> x.listIterator().previous(), + () -> x.listIterator(0).previous()); + } } public void testRemoveIf() { @@ -342,9 +349,112 @@ public class Collection8Test extends JSR } /** + * All elements removed in the middle of CONCURRENT traversal. + */ + public void testElementRemovalDuringTraversal() { + Collection c = impl.emptyCollection(); + ThreadLocalRandom rnd = ThreadLocalRandom.current(); + int n = rnd.nextInt(6); + ArrayList copy = new ArrayList(); + for (int i = 0; i < n; i++) { + Object x = impl.makeElement(i); + copy.add(x); + c.add(x); + } + ArrayList iterated = new ArrayList(); + ArrayList spliterated = new ArrayList(); + Spliterator s = c.spliterator(); + Iterator it = c.iterator(); + for (int i = rnd.nextInt(n + 1); --i >= 0; ) { + assertTrue(s.tryAdvance(spliterated::add)); + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + iterated.add(it.next()); + } + Consumer alwaysThrows = e -> { throw new AssertionError(); }; + if (s.hasCharacteristics(Spliterator.CONCURRENT)) { + c.clear(); // TODO: many more removal methods + if (testImplementationDetails + && !(c instanceof java.util.concurrent.ArrayBlockingQueue)) { + if (rnd.nextBoolean()) + assertFalse(s.tryAdvance(alwaysThrows)); + else + s.forEachRemaining(alwaysThrows); + } + if (it.hasNext()) iterated.add(it.next()); + if (rnd.nextBoolean()) assertIteratorExhausted(it); + } + assertTrue(copy.containsAll(iterated)); + assertTrue(copy.containsAll(spliterated)); + } + + /** + * Some elements randomly disappear in the middle of traversal. + */ + public void testRandomElementRemovalDuringTraversal() { + Collection c = impl.emptyCollection(); + ThreadLocalRandom rnd = ThreadLocalRandom.current(); + int n = rnd.nextInt(6); + ArrayList copy = new ArrayList(); + for (int i = 0; i < n; i++) { + Object x = impl.makeElement(i); + copy.add(x); + c.add(x); + } + ArrayList iterated = new ArrayList(); + ArrayList spliterated = new ArrayList(); + ArrayList removed = new ArrayList(); + Spliterator s = c.spliterator(); + Iterator it = c.iterator(); + if (! (s.hasCharacteristics(Spliterator.CONCURRENT) || + s.hasCharacteristics(Spliterator.IMMUTABLE))) + return; + for (int i = rnd.nextInt(n + 1); --i >= 0; ) { + assertTrue(s.tryAdvance(e -> {})); + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + it.next(); + } + Consumer alwaysThrows = e -> { throw new AssertionError(); }; + // TODO: many more removal methods + if (rnd.nextBoolean()) { + for (Iterator z = c.iterator(); z.hasNext(); ) { + Object e = z.next(); + if (rnd.nextBoolean()) { + try { + z.remove(); + } catch (UnsupportedOperationException ok) { return; } + removed.add(e); + } + } + } else { + Predicate randomlyRemove = e -> { + if (rnd.nextBoolean()) { removed.add(e); return true; } + else return false; + }; + c.removeIf(randomlyRemove); + } + s.forEachRemaining(spliterated::add); + while (it.hasNext()) + iterated.add(it.next()); + assertTrue(copy.containsAll(iterated)); + assertTrue(copy.containsAll(spliterated)); + assertTrue(copy.containsAll(removed)); + if (s.hasCharacteristics(Spliterator.CONCURRENT)) { + ArrayList iteratedAndRemoved = new ArrayList(iterated); + ArrayList spliteratedAndRemoved = new ArrayList(spliterated); + iteratedAndRemoved.retainAll(removed); + spliteratedAndRemoved.retainAll(removed); + assertTrue(iteratedAndRemoved.size() <= 1); + assertTrue(spliteratedAndRemoved.size() <= 1); + if (testImplementationDetails + && !(c instanceof java.util.concurrent.ArrayBlockingQueue)) + assertTrue(spliteratedAndRemoved.isEmpty()); + } + } + + /** * Various ways of traversing a collection yield same elements */ - public void testIteratorEquivalence() { + public void testTraversalEquivalence() { Collection c = impl.emptyCollection(); ThreadLocalRandom rnd = ThreadLocalRandom.current(); int n = rnd.nextInt(6); @@ -412,21 +522,75 @@ public class Collection8Test extends JSR } /** + * Iterator.forEachRemaining has same behavior as Iterator's + * default implementation. + */ + public void testForEachRemainingConsistentWithDefaultImplementation() { + Collection c = impl.emptyCollection(); + if (!testImplementationDetails + || c.getClass() == java.util.LinkedList.class) + return; + ThreadLocalRandom rnd = ThreadLocalRandom.current(); + int n = 1 + rnd.nextInt(3); + for (int i = 0; i < n; i++) c.add(impl.makeElement(i)); + ArrayList iterated = new ArrayList(); + ArrayList iteratedForEachRemaining = new ArrayList(); + Iterator it1 = c.iterator(); + Iterator it2 = c.iterator(); + assertTrue(it1.hasNext()); + assertTrue(it2.hasNext()); + c.clear(); + Object r1, r2; + try { + while (it1.hasNext()) iterated.add(it1.next()); + r1 = iterated; + } catch (ConcurrentModificationException ex) { + r1 = ConcurrentModificationException.class; + assertFalse(impl.isConcurrent()); + } + try { + it2.forEachRemaining(iteratedForEachRemaining::add); + r2 = iteratedForEachRemaining; + } catch (ConcurrentModificationException ex) { + r2 = ConcurrentModificationException.class; + assertFalse(impl.isConcurrent()); + } + assertEquals(r1, r2); + } + + /** * Calling Iterator#remove() after Iterator#forEachRemaining * should (maybe) remove last element */ public void testRemoveAfterForEachRemaining() { Collection c = impl.emptyCollection(); ThreadLocalRandom rnd = ThreadLocalRandom.current(); + ArrayList copy = new ArrayList(); + boolean ordered = c.spliterator().hasCharacteristics(Spliterator.ORDERED); testCollection: { int n = 3 + rnd.nextInt(2); - for (int i = 0; i < n; i++) c.add(impl.makeElement(i)); + for (int i = 0; i < n; i++) { + Object x = impl.makeElement(i); + c.add(x); + copy.add(x); + } Iterator it = c.iterator(); - assertTrue(it.hasNext()); - assertEquals(impl.makeElement(0), it.next()); - assertTrue(it.hasNext()); - assertEquals(impl.makeElement(1), it.next()); - it.forEachRemaining(e -> assertTrue(c.contains(e))); + if (ordered) { + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + assertEquals(impl.makeElement(0), it.next()); + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + assertEquals(impl.makeElement(1), it.next()); + } else { + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + assertTrue(copy.contains(it.next())); + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + assertTrue(copy.contains(it.next())); + } + if (rnd.nextBoolean()) assertTrue(it.hasNext()); + it.forEachRemaining( + e -> { + assertTrue(c.contains(e)); + assertTrue(copy.contains(e));}); if (testImplementationDetails) { if (c instanceof java.util.concurrent.ArrayBlockingQueue) { assertIteratorExhausted(it); @@ -436,14 +600,17 @@ public class Collection8Test extends JSR break testCollection; } assertEquals(n - 1, c.size()); - for (int i = 0; i < n - 1; i++) - assertTrue(c.contains(impl.makeElement(i))); - assertFalse(c.contains(impl.makeElement(n - 1))); + if (ordered) { + for (int i = 0; i < n - 1; i++) + assertTrue(c.contains(impl.makeElement(i))); + assertFalse(c.contains(impl.makeElement(n - 1))); + } } } } if (c instanceof Deque) { Deque d = (Deque) impl.emptyCollection(); + assertTrue(ordered); int n = 3 + rnd.nextInt(2); for (int i = 0; i < n; i++) d.add(impl.makeElement(i)); Iterator it = d.descendingIterator(); @@ -550,6 +717,66 @@ public class Collection8Test extends JSR assertTrue(found.isEmpty()); } + /** TODO: promote to a common utility */ + static T chooseOne(T ... ts) { + return ts[ThreadLocalRandom.current().nextInt(ts.length)]; + } + + /** TODO: more random adders and removers */ + static Runnable adderRemover(Collection c, E e) { + return chooseOne( + () -> { + assertTrue(c.add(e)); + assertTrue(c.contains(e)); + assertTrue(c.remove(e)); + assertFalse(c.contains(e)); + }, + () -> { + assertTrue(c.add(e)); + assertTrue(c.contains(e)); + assertTrue(c.removeIf(x -> x == e)); + assertFalse(c.contains(e)); + }, + () -> { + assertTrue(c.add(e)); + assertTrue(c.contains(e)); + for (Iterator it = c.iterator();; ) + if (it.next() == e) { + try { it.remove(); } + catch (UnsupportedOperationException ok) { + c.remove(e); + } + break; + } + assertFalse(c.contains(e)); + }); + } + + /** + * Concurrent Spliterators, once exhausted, stay exhausted. + */ + public void testStickySpliteratorExhaustion() throws Throwable { + if (!impl.isConcurrent()) return; + if (!testImplementationDetails) return; + final ThreadLocalRandom rnd = ThreadLocalRandom.current(); + final Consumer alwaysThrows = e -> { throw new AssertionError(); }; + final Collection c = impl.emptyCollection(); + final Spliterator s = c.spliterator(); + if (rnd.nextBoolean()) { + assertFalse(s.tryAdvance(alwaysThrows)); + } else { + s.forEachRemaining(alwaysThrows); + } + final Object one = impl.makeElement(1); + // Spliterator should not notice added element + c.add(one); + if (rnd.nextBoolean()) { + assertFalse(s.tryAdvance(alwaysThrows)); + } else { + s.forEachRemaining(alwaysThrows); + } + } + /** * Motley crew of threads concurrently randomly hammer the collection. */ @@ -563,6 +790,10 @@ public class Collection8Test extends JSR final Object one = impl.makeElement(1); final Object two = impl.makeElement(2); final Consumer checkSanity = x -> assertTrue(x == one || x == two); + final Consumer checkArraySanity = array -> { + // assertTrue(array.length <= 2); // duplicates are permitted + for (Object x : array) assertTrue(x == one || x == two); + }; final Object[] emptyArray = (Object[]) java.lang.reflect.Array.newInstance(one.getClass(), 0); final List> futures; @@ -582,20 +813,23 @@ public class Collection8Test extends JSR do {} while (s.tryAdvance(checkSanity)); }, () -> { for (Object x : c) checkSanity.accept(x); }, - () -> { for (Object x : c.toArray()) checkSanity.accept(x); }, - () -> { for (Object x : c.toArray(emptyArray)) checkSanity.accept(x); }, + () -> checkArraySanity.accept(c.toArray()), + () -> checkArraySanity.accept(c.toArray(emptyArray)), () -> { - assertTrue(c.add(one)); - assertTrue(c.contains(one)); - assertTrue(c.remove(one)); - assertFalse(c.contains(one)); - }, - () -> { - assertTrue(c.add(two)); - assertTrue(c.contains(two)); - assertTrue(c.remove(two)); - assertFalse(c.contains(two)); - }, + Object[] a = new Object[5]; + Object three = impl.makeElement(3); + Arrays.fill(a, 0, a.length, three); + Object[] x = c.toArray(a); + if (x == a) + for (int i = 0; i < a.length && a[i] != null; i++) + checkSanity.accept(a[i]); + // A careful reading of the spec does not support: + // for (i++; i < a.length; i++) assertSame(three, a[i]); + else + checkArraySanity.accept(x); + }, + adderRemover(c, one), + adderRemover(c, two), }; final List tasks = Arrays.stream(frobbers) @@ -653,6 +887,66 @@ public class Collection8Test extends JSR } } + /** + * Spliterator.getComparator throws IllegalStateException iff the + * spliterator does not report SORTED. + */ + public void testGetComparator_IllegalStateException() { + Collection c = impl.emptyCollection(); + Spliterator s = c.spliterator(); + boolean reportsSorted = s.hasCharacteristics(Spliterator.SORTED); + try { + s.getComparator(); + assertTrue(reportsSorted); + } catch (IllegalStateException ex) { + assertFalse(reportsSorted); + } + } + + public void testCollectionCopies() throws Exception { + ThreadLocalRandom rnd = ThreadLocalRandom.current(); + Collection c = impl.emptyCollection(); + for (int n = rnd.nextInt(4); n--> 0; ) + c.add(impl.makeElement(rnd.nextInt())); + assertEquals(c, c); + if (c instanceof List) + assertCollectionsEquals(c, new ArrayList(c)); + else if (c instanceof Set) + assertCollectionsEquals(c, new HashSet(c)); + else if (c instanceof Deque) + assertCollectionsEquivalent(c, new ArrayDeque(c)); + + Collection clone = cloneableClone(c); + if (clone != null) { + assertSame(c.getClass(), clone.getClass()); + assertCollectionsEquivalent(c, clone); + } + try { + Collection serialClone = serialClonePossiblyFailing(c); + assertSame(c.getClass(), serialClone.getClass()); + assertCollectionsEquivalent(c, serialClone); + } catch (java.io.NotSerializableException acceptable) {} + } + + public void testReplaceAllIsNotStructuralModification() { + Collection c = impl.emptyCollection(); + if (!(c instanceof List)) + return; + List list = (List) c; + ThreadLocalRandom rnd = ThreadLocalRandom.current(); + for (int n = rnd.nextInt(2, 10); n--> 0; ) + list.add(impl.makeElement(rnd.nextInt())); + ArrayList copy = new ArrayList(list); + int size = list.size(), half = size / 2; + Iterator it = list.iterator(); + for (int i = 0; i < half; i++) + assertEquals(it.next(), copy.get(i)); + list.replaceAll(n -> n); + // ConcurrentModificationException must not be thrown here. + for (int i = half; i < size; i++) + assertEquals(it.next(), copy.get(i)); + } + // public void testCollection8DebugFail() { // fail(impl.klazz().getSimpleName()); // }