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.13 by jsr166, Sat Nov 5 19:56:46 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;
# Line 17 | Line 19 | 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 57 | Line 63 | public class Collection8Test extends JSR
63      }
64  
65      /** Checks properties of empty collections. */
66 <    public void testEmptyMeansEmpty() {
66 >    public void testEmptyMeansEmpty() throws Throwable {
67          Collection c = impl.emptyCollection();
68          emptyMeansEmpty(c);
69  
70 <        if (c instanceof java.io.Serializable)
71 <            emptyMeansEmpty(serialClone(c));
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) {
89 >    void emptyMeansEmpty(Collection c) throws InterruptedException {
90          assertTrue(c.isEmpty());
91          assertEquals(0, c.size());
92          assertEquals("[]", c.toString());
# Line 94 | Line 111 | public class Collection8Test extends JSR
111              assertSame(3, a[2]);
112          }
113          assertIteratorExhausted(c.iterator());
114 <        Consumer alwaysThrows = (e) -> { throw new AssertionError(); };
114 >        Consumer alwaysThrows = e -> { throw new AssertionError(); };
115          c.forEach(alwaysThrows);
116          c.iterator().forEachRemaining(alwaysThrows);
117          c.spliterator().forEachRemaining(alwaysThrows);
# Line 119 | Line 136 | public class Collection8Test extends JSR
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() {
150 >    public void testNullPointerExceptions() throws InterruptedException {
151          Collection c = impl.emptyCollection();
152          assertThrows(
153              NullPointerException.class,
# Line 141 | Line 167 | public class Collection8Test extends JSR
167                  NullPointerException.class,
168                  () -> c.add(null));
169          }
170 <        if (!impl.permitsNulls()
145 <            && Queue.class.isAssignableFrom(impl.klazz())) {
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()
152 <            && Deque.class.isAssignableFrom(impl.klazz())) {
176 >        if (!impl.permitsNulls() && c instanceof Deque) {
177              Deque d = (Deque) c;
178              assertThrows(
179                  NullPointerException.class,
# Line 160 | Line 184 | public class Collection8Test extends JSR
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() {
# Line 168 | Line 232 | public class Collection8Test extends JSR
232              NoSuchElementException.class,
233              () -> c.iterator().next());
234  
235 <        if (Queue.class.isAssignableFrom(impl.klazz())) {
235 >        if (c instanceof Queue) {
236              Queue q = (Queue) c;
237              assertThrows(
238                  NoSuchElementException.class,
239                  () -> q.element(),
240                  () -> q.remove());
241          }
242 <        if (Deque.class.isAssignableFrom(impl.klazz())) {
242 >        if (c instanceof Deque) {
243              Deque d = (Deque) c;
244              assertThrows(
245                  NoSuchElementException.class,
# Line 190 | Line 254 | public class Collection8Test extends JSR
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 <        ArrayList survivors = new ArrayList(c);
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 <        Predicate randomPredicate = (e) -> {
273 >
274 >        Predicate randomPredicate = e -> {
275              assertNull(threwAt.get());
276              switch (rnd.nextInt(3)) {
277              case 0: accepts.add(e); return true;
# Line 207 | Line 281 | public class Collection8Test extends JSR
281              }
282          };
283          try {
210            assertFalse(survivors.contains(null));
284              try {
285                  boolean modified = c.removeIf(randomPredicate);
286 <                if (!modified) {
287 <                    assertNull(threwAt.get());
288 <                    assertEquals(n, rejects.size());
289 <                    assertEquals(0, accepts.size());
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 <            survivors.removeAll(accepts);
299 <            assertEquals(n - accepts.size(), c.size());
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 <            for (Object x : accepts) assertFalse(c.contains(x));
318 <            if (threwAt.get() == null)
319 <                assertEquals(accepts.size() + rejects.size(), n);
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 <            System.err.printf("c=%s%n", c);
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("threw=%s%n", threwAt.get());
338 >            System.err.printf("threwAt=%s%n", threwAt.get());
339              throw ex;
340          }
341      }
# Line 250 | Line 355 | public class Collection8Test extends JSR
355          ArrayList forEached = new ArrayList();
356          ArrayList removeIfed = new ArrayList();
357          for (Object x : c) iterated.add(x);
358 <        c.iterator().forEachRemaining(e -> iteratedForEachRemaining.add(e));
358 >        c.iterator().forEachRemaining(iteratedForEachRemaining::add);
359          for (Spliterator s = c.spliterator();
360 <             s.tryAdvance(e -> tryAdvanced.add(e)); ) {}
361 <        c.spliterator().forEachRemaining(e -> spliterated.add(e));
362 <        c.forEach(e -> forEached.add(e));
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);
# Line 292 | Line 397 | public class Collection8Test extends JSR
397  
398      /**
399       * Calling Iterator#remove() after Iterator#forEachRemaining
400 <     * should remove last element
400 >     * should (maybe) remove last element
401       */
402      public void testRemoveAfterForEachRemaining() {
403          Collection c = impl.emptyCollection();
404          ThreadLocalRandom rnd = ThreadLocalRandom.current();
405 <        {
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();
# Line 305 | Line 410 | public class Collection8Test extends JSR
410              assertEquals(impl.makeElement(0), it.next());
411              assertTrue(it.hasNext());
412              assertEquals(impl.makeElement(1), it.next());
413 <            it.forEachRemaining((e) -> {});
414 <            it.remove();
415 <            assertEquals(n - 1, c.size());
416 <            for (int i = 0; i < n - 1; i++)
417 <                assertTrue(c.contains(impl.makeElement(i)));
418 <            assertFalse(c.contains(impl.makeElement(n - 1)));
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();
# Line 321 | Line 435 | public class Collection8Test extends JSR
435              assertEquals(impl.makeElement(n - 1), it.next());
436              assertTrue(it.hasNext());
437              assertEquals(impl.makeElement(n - 2), it.next());
438 <            it.forEachRemaining((e) -> {});
439 <            it.remove();
440 <            assertEquals(n - 1, d.size());
441 <            for (int i = 1; i < n; i++)
442 <                assertTrue(d.contains(impl.makeElement(i)));
443 <            assertFalse(d.contains(impl.makeElement(0)));
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  
# Line 339 | Line 455 | public class Collection8Test extends JSR
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 373 | 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 397 | Line 513 | public class Collection8Test extends JSR
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); };
516 >        Consumer<Object> spy = o -> found.add(o);
517          c.forEach(spy);
518          assertTrue(found.isEmpty());
519  
# Line 418 | Line 534 | public class Collection8Test extends JSR
534          assertTrue(found.isEmpty());
535      }
536  
537 <    public void testForEachConcurrentStressTest() throws Throwable {
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 elt = impl.makeElement(1);
547 <        final Future<?> f1, f2;
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 <            final CountDownLatch threadsStarted = new CountDownLatch(2);
591 <            Runnable checkElt = () -> {
592 <                threadsStarted.countDown();
593 <                while (!done.get())
594 <                    c.forEach((x) -> { assertSame(x, elt); }); };
435 <            Runnable addRemove = () -> {
436 <                threadsStarted.countDown();
437 <                while (!done.get()) {
438 <                    assertTrue(c.add(elt));
439 <                    assertTrue(c.remove(elt));
440 <                }};
441 <            f1 = pool.submit(checkElt);
442 <            f2 = pool.submit(addRemove);
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 <        assertNull(f1.get(0L, MILLISECONDS));
598 <        assertNull(f2.get(0L, MILLISECONDS));
597 >        for (Future future : futures)
598 >            assertNull(future.get(0L, MILLISECONDS));
599      }
600  
601   //     public void testCollection8DebugFail() {

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines