ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/Collection8Test.java
(Generate patch)

Comparing jsr166/src/test/tck/Collection8Test.java (file contents):
Revision 1.2 by jsr166, Mon Feb 22 19:43:54 2016 UTC vs.
Revision 1.28 by jsr166, Fri Nov 18 17:23:29 2016 UTC

# Line 5 | Line 5
5   * http://creativecommons.org/publicdomain/zero/1.0/
6   */
7  
8 + import static java.util.concurrent.TimeUnit.HOURS;
9   import static java.util.concurrent.TimeUnit.MILLISECONDS;
10  
11   import java.util.ArrayList;
12 + import java.util.Arrays;
13   import java.util.Collection;
14   import java.util.Collections;
15 + import java.util.Deque;
16 + import java.util.HashSet;
17 + import java.util.Iterator;
18 + import java.util.List;
19 + import java.util.NoSuchElementException;
20 + import java.util.Queue;
21 + import java.util.Spliterator;
22 + import java.util.concurrent.BlockingDeque;
23 + import java.util.concurrent.BlockingQueue;
24   import java.util.concurrent.CountDownLatch;
25   import java.util.concurrent.Executors;
26   import java.util.concurrent.ExecutorService;
27   import java.util.concurrent.Future;
28 + import java.util.concurrent.Phaser;
29 + import java.util.concurrent.ThreadLocalRandom;
30   import java.util.concurrent.atomic.AtomicBoolean;
31   import java.util.concurrent.atomic.AtomicLong;
32 + import java.util.concurrent.atomic.AtomicReference;
33   import java.util.function.Consumer;
34 + import java.util.function.Predicate;
35 + import java.util.stream.Collectors;
36  
37   import junit.framework.Test;
38  
# Line 39 | Line 55 | public class Collection8Test extends JSR
55                                        impl);
56      }
57  
58 +    Object bomb() {
59 +        return new Object() {
60 +                public boolean equals(Object x) { throw new AssertionError(); }
61 +                public int hashCode() { throw new AssertionError(); }
62 +            };
63 +    }
64 +
65 +    /** Checks properties of empty collections. */
66 +    public void testEmptyMeansEmpty() throws Throwable {
67 +        Collection c = impl.emptyCollection();
68 +        emptyMeansEmpty(c);
69 +
70 +        if (c instanceof java.io.Serializable) {
71 +            try {
72 +                emptyMeansEmpty(serialClonePossiblyFailing(c));
73 +            } catch (java.io.NotSerializableException ex) {
74 +                // excusable when we have a serializable wrapper around
75 +                // a non-serializable collection, as can happen with:
76 +                // Vector.subList() => wrapped AbstractList$RandomAccessSubList
77 +                if (testImplementationDetails
78 +                    && (! c.getClass().getName().matches(
79 +                                "java.util.Collections.*")))
80 +                    throw ex;
81 +            }
82 +        }
83 +
84 +        Collection clone = cloneableClone(c);
85 +        if (clone != null)
86 +            emptyMeansEmpty(clone);
87 +    }
88 +
89 +    void emptyMeansEmpty(Collection c) throws InterruptedException {
90 +        assertTrue(c.isEmpty());
91 +        assertEquals(0, c.size());
92 +        assertEquals("[]", c.toString());
93 +        {
94 +            Object[] a = c.toArray();
95 +            assertEquals(0, a.length);
96 +            assertSame(Object[].class, a.getClass());
97 +        }
98 +        {
99 +            Object[] a = new Object[0];
100 +            assertSame(a, c.toArray(a));
101 +        }
102 +        {
103 +            Integer[] a = new Integer[0];
104 +            assertSame(a, c.toArray(a));
105 +        }
106 +        {
107 +            Integer[] a = { 1, 2, 3};
108 +            assertSame(a, c.toArray(a));
109 +            assertNull(a[0]);
110 +            assertSame(2, a[1]);
111 +            assertSame(3, a[2]);
112 +        }
113 +        assertIteratorExhausted(c.iterator());
114 +        Consumer alwaysThrows = e -> { throw new AssertionError(); };
115 +        c.forEach(alwaysThrows);
116 +        c.iterator().forEachRemaining(alwaysThrows);
117 +        c.spliterator().forEachRemaining(alwaysThrows);
118 +        assertFalse(c.spliterator().tryAdvance(alwaysThrows));
119 +        if (c.spliterator().hasCharacteristics(Spliterator.SIZED))
120 +            assertEquals(0, c.spliterator().estimateSize());
121 +        assertFalse(c.contains(bomb()));
122 +        assertFalse(c.remove(bomb()));
123 +        if (c instanceof Queue) {
124 +            Queue q = (Queue) c;
125 +            assertNull(q.peek());
126 +            assertNull(q.poll());
127 +        }
128 +        if (c instanceof Deque) {
129 +            Deque d = (Deque) c;
130 +            assertNull(d.peekFirst());
131 +            assertNull(d.peekLast());
132 +            assertNull(d.pollFirst());
133 +            assertNull(d.pollLast());
134 +            assertIteratorExhausted(d.descendingIterator());
135 +            d.descendingIterator().forEachRemaining(alwaysThrows);
136 +            assertFalse(d.removeFirstOccurrence(bomb()));
137 +            assertFalse(d.removeLastOccurrence(bomb()));
138 +        }
139 +        if (c instanceof BlockingQueue) {
140 +            BlockingQueue q = (BlockingQueue) c;
141 +            assertNull(q.poll(0L, MILLISECONDS));
142 +        }
143 +        if (c instanceof BlockingDeque) {
144 +            BlockingDeque q = (BlockingDeque) c;
145 +            assertNull(q.pollFirst(0L, MILLISECONDS));
146 +            assertNull(q.pollLast(0L, MILLISECONDS));
147 +        }
148 +    }
149 +
150 +    public void testNullPointerExceptions() throws InterruptedException {
151 +        Collection c = impl.emptyCollection();
152 +        assertThrows(
153 +            NullPointerException.class,
154 +            () -> c.addAll(null),
155 +            () -> c.containsAll(null),
156 +            () -> c.retainAll(null),
157 +            () -> c.removeAll(null),
158 +            () -> c.removeIf(null),
159 +            () -> c.forEach(null),
160 +            () -> c.iterator().forEachRemaining(null),
161 +            () -> c.spliterator().forEachRemaining(null),
162 +            () -> c.spliterator().tryAdvance(null),
163 +            () -> c.toArray(null));
164 +
165 +        if (!impl.permitsNulls()) {
166 +            assertThrows(
167 +                NullPointerException.class,
168 +                () -> c.add(null));
169 +        }
170 +        if (!impl.permitsNulls() && c instanceof Queue) {
171 +            Queue q = (Queue) c;
172 +            assertThrows(
173 +                NullPointerException.class,
174 +                () -> q.offer(null));
175 +        }
176 +        if (!impl.permitsNulls() && c instanceof Deque) {
177 +            Deque d = (Deque) c;
178 +            assertThrows(
179 +                NullPointerException.class,
180 +                () -> d.addFirst(null),
181 +                () -> d.addLast(null),
182 +                () -> d.offerFirst(null),
183 +                () -> d.offerLast(null),
184 +                () -> d.push(null),
185 +                () -> d.descendingIterator().forEachRemaining(null));
186 +        }
187 +        if (c instanceof BlockingQueue) {
188 +            BlockingQueue q = (BlockingQueue) c;
189 +            assertThrows(
190 +                NullPointerException.class,
191 +                () -> {
192 +                    try { q.offer(null, 1L, HOURS); }
193 +                    catch (InterruptedException ex) {
194 +                        throw new AssertionError(ex);
195 +                    }},
196 +                () -> {
197 +                    try { q.put(null); }
198 +                    catch (InterruptedException ex) {
199 +                        throw new AssertionError(ex);
200 +                    }});
201 +        }
202 +        if (c instanceof BlockingDeque) {
203 +            BlockingDeque q = (BlockingDeque) c;
204 +            assertThrows(
205 +                NullPointerException.class,
206 +                () -> {
207 +                    try { q.offerFirst(null, 1L, HOURS); }
208 +                    catch (InterruptedException ex) {
209 +                        throw new AssertionError(ex);
210 +                    }},
211 +                () -> {
212 +                    try { q.offerLast(null, 1L, HOURS); }
213 +                    catch (InterruptedException ex) {
214 +                        throw new AssertionError(ex);
215 +                    }},
216 +                () -> {
217 +                    try { q.putFirst(null); }
218 +                    catch (InterruptedException ex) {
219 +                        throw new AssertionError(ex);
220 +                    }},
221 +                () -> {
222 +                    try { q.putLast(null); }
223 +                    catch (InterruptedException ex) {
224 +                        throw new AssertionError(ex);
225 +                    }});
226 +        }
227 +    }
228 +
229 +    public void testNoSuchElementExceptions() {
230 +        Collection c = impl.emptyCollection();
231 +        assertThrows(
232 +            NoSuchElementException.class,
233 +            () -> c.iterator().next());
234 +
235 +        if (c instanceof Queue) {
236 +            Queue q = (Queue) c;
237 +            assertThrows(
238 +                NoSuchElementException.class,
239 +                () -> q.element(),
240 +                () -> q.remove());
241 +        }
242 +        if (c instanceof Deque) {
243 +            Deque d = (Deque) c;
244 +            assertThrows(
245 +                NoSuchElementException.class,
246 +                () -> d.getFirst(),
247 +                () -> d.getLast(),
248 +                () -> d.removeFirst(),
249 +                () -> d.removeLast(),
250 +                () -> d.pop(),
251 +                () -> d.descendingIterator().next());
252 +        }
253 +    }
254 +
255 +    public void testRemoveIf() {
256 +        Collection c = impl.emptyCollection();
257 +        boolean ordered =
258 +            c.spliterator().hasCharacteristics(Spliterator.ORDERED);
259 +        ThreadLocalRandom rnd = ThreadLocalRandom.current();
260 +        int n = rnd.nextInt(6);
261 +        for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
262 +        AtomicReference threwAt = new AtomicReference(null);
263 +        List orig = rnd.nextBoolean()
264 +            ? new ArrayList(c)
265 +            : Arrays.asList(c.toArray());
266 +
267 +        // Merely creating an iterator can change ArrayBlockingQueue behavior
268 +        Iterator it = rnd.nextBoolean() ? c.iterator() : null;
269 +
270 +        ArrayList survivors = new ArrayList();
271 +        ArrayList accepts = new ArrayList();
272 +        ArrayList rejects = new ArrayList();
273 +
274 +        Predicate randomPredicate = e -> {
275 +            assertNull(threwAt.get());
276 +            switch (rnd.nextInt(3)) {
277 +            case 0: accepts.add(e); return true;
278 +            case 1: rejects.add(e); return false;
279 +            case 2: threwAt.set(e); throw new ArithmeticException();
280 +            default: throw new AssertionError();
281 +            }
282 +        };
283 +        try {
284 +            try {
285 +                boolean modified = c.removeIf(randomPredicate);
286 +                assertNull(threwAt.get());
287 +                assertEquals(modified, accepts.size() > 0);
288 +                assertEquals(modified, rejects.size() != n);
289 +                assertEquals(accepts.size() + rejects.size(), n);
290 +                if (ordered) {
291 +                    assertEquals(rejects,
292 +                                 Arrays.asList(c.toArray()));
293 +                } else {
294 +                    assertEquals(new HashSet(rejects),
295 +                                 new HashSet(Arrays.asList(c.toArray())));
296 +                }
297 +            } catch (ArithmeticException ok) {
298 +                assertNotNull(threwAt.get());
299 +                assertTrue(c.contains(threwAt.get()));
300 +            }
301 +            if (it != null && impl.isConcurrent())
302 +                // check for weakly consistent iterator
303 +                while (it.hasNext()) assertTrue(orig.contains(it.next()));
304 +            switch (rnd.nextInt(4)) {
305 +            case 0: survivors.addAll(c); break;
306 +            case 1: survivors.addAll(Arrays.asList(c.toArray())); break;
307 +            case 2: c.forEach(survivors::add); break;
308 +            case 3: for (Object e : c) survivors.add(e); break;
309 +            }
310 +            assertTrue(orig.containsAll(accepts));
311 +            assertTrue(orig.containsAll(rejects));
312 +            assertTrue(orig.containsAll(survivors));
313 +            assertTrue(orig.containsAll(c));
314 +            assertTrue(c.containsAll(rejects));
315 +            assertTrue(c.containsAll(survivors));
316 +            assertTrue(survivors.containsAll(rejects));
317 +            if (threwAt.get() == null) {
318 +                assertEquals(n - accepts.size(), c.size());
319 +                for (Object x : accepts) assertFalse(c.contains(x));
320 +            } else {
321 +                // Two acceptable behaviors: entire removeIf call is one
322 +                // transaction, or each element processed is one transaction.
323 +                assertTrue(n == c.size() || n == c.size() + accepts.size());
324 +                int k = 0;
325 +                for (Object x : accepts) if (c.contains(x)) k++;
326 +                assertTrue(k == accepts.size() || k == 0);
327 +            }
328 +        } catch (Throwable ex) {
329 +            System.err.println(impl.klazz());
330 +            // c is at risk of corruption if we got here, so be lenient
331 +            try { System.err.printf("c=%s%n", c); }
332 +            catch (Throwable t) { t.printStackTrace(); }
333 +            System.err.printf("n=%d%n", n);
334 +            System.err.printf("orig=%s%n", orig);
335 +            System.err.printf("accepts=%s%n", accepts);
336 +            System.err.printf("rejects=%s%n", rejects);
337 +            System.err.printf("survivors=%s%n", survivors);
338 +            System.err.printf("threwAt=%s%n", threwAt.get());
339 +            throw ex;
340 +        }
341 +    }
342 +
343 +    /**
344 +     * Various ways of traversing a collection yield same elements
345 +     */
346 +    public void testIteratorEquivalence() {
347 +        Collection c = impl.emptyCollection();
348 +        ThreadLocalRandom rnd = ThreadLocalRandom.current();
349 +        int n = rnd.nextInt(6);
350 +        for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
351 +        ArrayList iterated = new ArrayList();
352 +        ArrayList iteratedForEachRemaining = new ArrayList();
353 +        ArrayList tryAdvanced = new ArrayList();
354 +        ArrayList spliterated = new ArrayList();
355 +        ArrayList forEached = new ArrayList();
356 +        ArrayList removeIfed = new ArrayList();
357 +        for (Object x : c) iterated.add(x);
358 +        c.iterator().forEachRemaining(iteratedForEachRemaining::add);
359 +        for (Spliterator s = c.spliterator();
360 +             s.tryAdvance(tryAdvanced::add); ) {}
361 +        c.spliterator().forEachRemaining(spliterated::add);
362 +        c.forEach(forEached::add);
363 +        c.removeIf(e -> { removeIfed.add(e); return false; });
364 +        boolean ordered =
365 +            c.spliterator().hasCharacteristics(Spliterator.ORDERED);
366 +        if (c instanceof List || c instanceof Deque)
367 +            assertTrue(ordered);
368 +        if (ordered) {
369 +            assertEquals(iterated, iteratedForEachRemaining);
370 +            assertEquals(iterated, tryAdvanced);
371 +            assertEquals(iterated, spliterated);
372 +            assertEquals(iterated, forEached);
373 +            assertEquals(iterated, removeIfed);
374 +        } else {
375 +            HashSet cset = new HashSet(c);
376 +            assertEquals(cset, new HashSet(iterated));
377 +            assertEquals(cset, new HashSet(iteratedForEachRemaining));
378 +            assertEquals(cset, new HashSet(tryAdvanced));
379 +            assertEquals(cset, new HashSet(spliterated));
380 +            assertEquals(cset, new HashSet(forEached));
381 +            assertEquals(cset, new HashSet(removeIfed));
382 +        }
383 +        if (c instanceof Deque) {
384 +            Deque d = (Deque) c;
385 +            ArrayList descending = new ArrayList();
386 +            ArrayList descendingForEachRemaining = new ArrayList();
387 +            for (Iterator it = d.descendingIterator(); it.hasNext(); )
388 +                descending.add(it.next());
389 +            d.descendingIterator().forEachRemaining(
390 +                e -> descendingForEachRemaining.add(e));
391 +            Collections.reverse(descending);
392 +            Collections.reverse(descendingForEachRemaining);
393 +            assertEquals(iterated, descending);
394 +            assertEquals(iterated, descendingForEachRemaining);
395 +        }
396 +    }
397 +
398 +    /**
399 +     * Calling Iterator#remove() after Iterator#forEachRemaining
400 +     * should (maybe) remove last element
401 +     */
402 +    public void testRemoveAfterForEachRemaining() {
403 +        Collection c = impl.emptyCollection();
404 +        ThreadLocalRandom rnd = ThreadLocalRandom.current();
405 +        testCollection: {
406 +            int n = 3 + rnd.nextInt(2);
407 +            for (int i = 0; i < n; i++) c.add(impl.makeElement(i));
408 +            Iterator it = c.iterator();
409 +            assertTrue(it.hasNext());
410 +            assertEquals(impl.makeElement(0), it.next());
411 +            assertTrue(it.hasNext());
412 +            assertEquals(impl.makeElement(1), it.next());
413 +            it.forEachRemaining(e -> assertTrue(c.contains(e)));
414 +            if (testImplementationDetails) {
415 +                if (c instanceof java.util.concurrent.ArrayBlockingQueue) {
416 +                    assertIteratorExhausted(it);
417 +                } else {
418 +                    try { it.remove(); }
419 +                    catch (UnsupportedOperationException ok) {
420 +                        break testCollection;
421 +                    }
422 +                    assertEquals(n - 1, c.size());
423 +                    for (int i = 0; i < n - 1; i++)
424 +                        assertTrue(c.contains(impl.makeElement(i)));
425 +                    assertFalse(c.contains(impl.makeElement(n - 1)));
426 +                }
427 +            }
428 +        }
429 +        if (c instanceof Deque) {
430 +            Deque d = (Deque) impl.emptyCollection();
431 +            int n = 3 + rnd.nextInt(2);
432 +            for (int i = 0; i < n; i++) d.add(impl.makeElement(i));
433 +            Iterator it = d.descendingIterator();
434 +            assertTrue(it.hasNext());
435 +            assertEquals(impl.makeElement(n - 1), it.next());
436 +            assertTrue(it.hasNext());
437 +            assertEquals(impl.makeElement(n - 2), it.next());
438 +            it.forEachRemaining(e -> assertTrue(c.contains(e)));
439 +            if (testImplementationDetails) {
440 +                it.remove();
441 +                assertEquals(n - 1, d.size());
442 +                for (int i = 1; i < n; i++)
443 +                    assertTrue(d.contains(impl.makeElement(i)));
444 +                assertFalse(d.contains(impl.makeElement(0)));
445 +            }
446 +        }
447 +    }
448 +
449      /**
450       * stream().forEach returns elements in the collection
451       */
452 <    public void testForEach() throws Throwable {
452 >    public void testStreamForEach() throws Throwable {
453          final Collection c = impl.emptyCollection();
454          final AtomicLong count = new AtomicLong(0L);
455          final Object x = impl.makeElement(1);
456          final Object y = impl.makeElement(2);
457          final ArrayList found = new ArrayList();
458 <        Consumer<Object> spy = (o) -> { found.add(o); };
458 >        Consumer<Object> spy = o -> found.add(o);
459          c.stream().forEach(spy);
460          assertTrue(found.isEmpty());
461  
# Line 69 | Line 476 | public class Collection8Test extends JSR
476          assertTrue(found.isEmpty());
477      }
478  
479 <    public void testForEachConcurrentStressTest() throws Throwable {
479 >    public void testStreamForEachConcurrentStressTest() throws Throwable {
480          if (!impl.isConcurrent()) return;
481          final Collection c = impl.emptyCollection();
482          final long testDurationMillis = timeoutMillis();
# Line 82 | Line 489 | public class Collection8Test extends JSR
489              Runnable checkElt = () -> {
490                  threadsStarted.countDown();
491                  while (!done.get())
492 <                    c.stream().forEach((x) -> { assertSame(x, elt); }); };
492 >                    c.stream().forEach(x -> assertSame(x, elt)); };
493              Runnable addRemove = () -> {
494                  threadsStarted.countDown();
495                  while (!done.get()) {
# Line 97 | Line 504 | public class Collection8Test extends JSR
504          assertNull(f2.get(0L, MILLISECONDS));
505      }
506  
507 <    // public void testCollection8DebugFail() { fail(); }
507 >    /**
508 >     * collection.forEach returns elements in the collection
509 >     */
510 >    public void testForEach() throws Throwable {
511 >        final Collection c = impl.emptyCollection();
512 >        final AtomicLong count = new AtomicLong(0L);
513 >        final Object x = impl.makeElement(1);
514 >        final Object y = impl.makeElement(2);
515 >        final ArrayList found = new ArrayList();
516 >        Consumer<Object> spy = o -> found.add(o);
517 >        c.forEach(spy);
518 >        assertTrue(found.isEmpty());
519 >
520 >        assertTrue(c.add(x));
521 >        c.forEach(spy);
522 >        assertEquals(Collections.singletonList(x), found);
523 >        found.clear();
524 >
525 >        assertTrue(c.add(y));
526 >        c.forEach(spy);
527 >        assertEquals(2, found.size());
528 >        assertTrue(found.contains(x));
529 >        assertTrue(found.contains(y));
530 >        found.clear();
531 >
532 >        c.clear();
533 >        c.forEach(spy);
534 >        assertTrue(found.isEmpty());
535 >    }
536 >
537 >    /**
538 >     * Motley crew of threads concurrently randomly hammer the collection.
539 >     */
540 >    public void testDetectRaces() throws Throwable {
541 >        if (!impl.isConcurrent()) return;
542 >        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
543 >        final Collection c = impl.emptyCollection();
544 >        final long testDurationMillis = timeoutMillis();
545 >        final AtomicBoolean done = new AtomicBoolean(false);
546 >        final Object one = impl.makeElement(1);
547 >        final Object two = impl.makeElement(2);
548 >        final List<Future<?>> futures;
549 >        final Phaser threadsStarted = new Phaser(1); // register this thread
550 >        final Runnable[] frobbers = {
551 >            () -> c.forEach(x -> assertTrue(x == one || x == two)),
552 >            () -> c.stream().forEach(x -> assertTrue(x == one || x == two)),
553 >            () -> c.spliterator().trySplit(),
554 >            () -> {
555 >                Spliterator s = c.spliterator();
556 >                s.tryAdvance(x -> assertTrue(x == one || x == two));
557 >                s.trySplit();
558 >            },
559 >            () -> {
560 >                Spliterator s = c.spliterator();
561 >                do {} while (s.tryAdvance(x -> assertTrue(x == one || x == two)));
562 >            },
563 >            () -> {
564 >                for (Object x : c) assertTrue(x == one || x == two);
565 >            },
566 >            () -> {
567 >                assertTrue(c.add(one));
568 >                assertTrue(c.contains(one));
569 >                assertTrue(c.remove(one));
570 >                assertFalse(c.contains(one));
571 >            },
572 >            () -> {
573 >                assertTrue(c.add(two));
574 >                assertTrue(c.contains(two));
575 >                assertTrue(c.remove(two));
576 >                assertFalse(c.contains(two));
577 >            },
578 >        };
579 >        final List<Runnable> tasks =
580 >            Arrays.stream(frobbers)
581 >            .filter(task -> rnd.nextBoolean()) // random subset
582 >            .map(task -> (Runnable) () -> {
583 >                     threadsStarted.arriveAndAwaitAdvance();
584 >                     while (!done.get())
585 >                         task.run();
586 >                 })
587 >            .collect(Collectors.toList());
588 >        final ExecutorService pool = Executors.newCachedThreadPool();
589 >        try (PoolCleaner cleaner = cleaner(pool, done)) {
590 >            threadsStarted.bulkRegister(tasks.size());
591 >            futures = tasks.stream()
592 >                .map(pool::submit)
593 >                .collect(Collectors.toList());
594 >            threadsStarted.arriveAndDeregister();
595 >            Thread.sleep(testDurationMillis);
596 >        }
597 >        for (Future future : futures)
598 >            assertNull(future.get(0L, MILLISECONDS));
599 >    }
600 >
601 > //     public void testCollection8DebugFail() {
602 > //         fail(impl.klazz().getSimpleName());
603 > //     }
604   }

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines