1/*
2 * Written by Doug Lea with assistance from members of JCP JSR-166
3 * Expert Group and released to the public domain, as explained at
4 * http://creativecommons.org/publicdomain/zero/1.0/
5 */
6
7package jsr166;
8
9import junit.framework.*;
10import java.util.concurrent.CancellationException;
11import java.util.concurrent.SynchronousQueue;
12import java.util.concurrent.ExecutionException;
13import java.util.concurrent.ForkJoinPool;
14import java.util.concurrent.ForkJoinTask;
15import java.util.concurrent.ForkJoinWorkerThread;
16import java.util.concurrent.RecursiveAction;
17import java.util.concurrent.ThreadLocalRandom;
18import java.util.concurrent.TimeUnit;
19import java.util.concurrent.TimeoutException;
20import static java.util.concurrent.TimeUnit.SECONDS;
21import java.util.Arrays;
22import java.util.HashSet;
23
24public class RecursiveActionTest extends JSR166TestCase {
25
26    private static ForkJoinPool mainPool() {
27        return new ForkJoinPool();
28    }
29
30    private static ForkJoinPool singletonPool() {
31        return new ForkJoinPool(1);
32    }
33
34    private static ForkJoinPool asyncSingletonPool() {
35        return new ForkJoinPool(1,
36                                ForkJoinPool.defaultForkJoinWorkerThreadFactory,
37                                null, true);
38    }
39
40    private void testInvokeOnPool(ForkJoinPool pool, RecursiveAction a) {
41        try {
42            checkNotDone(a);
43
44            assertNull(pool.invoke(a));
45
46            checkCompletedNormally(a);
47        } finally {
48            joinPool(pool);
49        }
50    }
51
52    void checkNotDone(RecursiveAction a) {
53        assertFalse(a.isDone());
54        assertFalse(a.isCompletedNormally());
55        assertFalse(a.isCompletedAbnormally());
56        assertFalse(a.isCancelled());
57        assertNull(a.getException());
58        assertNull(a.getRawResult());
59
60        if (! ForkJoinTask.inForkJoinPool()) {
61            Thread.currentThread().interrupt();
62            try {
63                a.get();
64                shouldThrow();
65            } catch (InterruptedException success) {
66            } catch (Throwable fail) { threadUnexpectedException(fail); }
67
68            Thread.currentThread().interrupt();
69            try {
70                a.get(5L, SECONDS);
71                shouldThrow();
72            } catch (InterruptedException success) {
73            } catch (Throwable fail) { threadUnexpectedException(fail); }
74        }
75
76        try {
77            a.get(0L, SECONDS);
78            shouldThrow();
79        } catch (TimeoutException success) {
80        } catch (Throwable fail) { threadUnexpectedException(fail); }
81    }
82
83    void checkCompletedNormally(RecursiveAction a) {
84        assertTrue(a.isDone());
85        assertFalse(a.isCancelled());
86        assertTrue(a.isCompletedNormally());
87        assertFalse(a.isCompletedAbnormally());
88        assertNull(a.getException());
89        assertNull(a.getRawResult());
90        assertNull(a.join());
91        assertFalse(a.cancel(false));
92        assertFalse(a.cancel(true));
93        try {
94            assertNull(a.get());
95        } catch (Throwable fail) { threadUnexpectedException(fail); }
96        try {
97            assertNull(a.get(5L, SECONDS));
98        } catch (Throwable fail) { threadUnexpectedException(fail); }
99    }
100
101    void checkCancelled(RecursiveAction a) {
102        assertTrue(a.isDone());
103        assertTrue(a.isCancelled());
104        assertFalse(a.isCompletedNormally());
105        assertTrue(a.isCompletedAbnormally());
106        assertTrue(a.getException() instanceof CancellationException);
107        assertNull(a.getRawResult());
108
109        try {
110            a.join();
111            shouldThrow();
112        } catch (CancellationException success) {
113        } catch (Throwable fail) { threadUnexpectedException(fail); }
114
115        try {
116            a.get();
117            shouldThrow();
118        } catch (CancellationException success) {
119        } catch (Throwable fail) { threadUnexpectedException(fail); }
120
121        try {
122            a.get(5L, SECONDS);
123            shouldThrow();
124        } catch (CancellationException success) {
125        } catch (Throwable fail) { threadUnexpectedException(fail); }
126    }
127
128    void checkCompletedAbnormally(RecursiveAction a, Throwable t) {
129        assertTrue(a.isDone());
130        assertFalse(a.isCancelled());
131        assertFalse(a.isCompletedNormally());
132        assertTrue(a.isCompletedAbnormally());
133        assertSame(t.getClass(), a.getException().getClass());
134        assertNull(a.getRawResult());
135        assertFalse(a.cancel(false));
136        assertFalse(a.cancel(true));
137
138        try {
139            a.join();
140            shouldThrow();
141        } catch (Throwable expected) {
142            assertSame(expected.getClass(), t.getClass());
143        }
144
145        try {
146            a.get();
147            shouldThrow();
148        } catch (ExecutionException success) {
149            assertSame(t.getClass(), success.getCause().getClass());
150        } catch (Throwable fail) { threadUnexpectedException(fail); }
151
152        try {
153            a.get(5L, SECONDS);
154            shouldThrow();
155        } catch (ExecutionException success) {
156            assertSame(t.getClass(), success.getCause().getClass());
157        } catch (Throwable fail) { threadUnexpectedException(fail); }
158    }
159
160    public static final class FJException extends RuntimeException {
161        public FJException() { super(); }
162        public FJException(Throwable cause) { super(cause); }
163    }
164
165    // A simple recursive action for testing
166    final class FibAction extends CheckedRecursiveAction {
167        final int number;
168        int result;
169        FibAction(int n) { number = n; }
170        protected void realCompute() {
171            int n = number;
172            if (n <= 1)
173                result = n;
174            else {
175                FibAction f1 = new FibAction(n - 1);
176                FibAction f2 = new FibAction(n - 2);
177                invokeAll(f1, f2);
178                result = f1.result + f2.result;
179            }
180        }
181    }
182
183    // A recursive action failing in base case
184    static final class FailingFibAction extends RecursiveAction {
185        final int number;
186        int result;
187        FailingFibAction(int n) { number = n; }
188        public void compute() {
189            int n = number;
190            if (n <= 1)
191                throw new FJException();
192            else {
193                FailingFibAction f1 = new FailingFibAction(n - 1);
194                FailingFibAction f2 = new FailingFibAction(n - 2);
195                invokeAll(f1, f2);
196                result = f1.result + f2.result;
197            }
198        }
199    }
200
201    /**
202     * invoke returns when task completes normally.
203     * isCompletedAbnormally and isCancelled return false for normally
204     * completed tasks. getRawResult of a RecursiveAction returns null;
205     */
206    public void testInvoke() {
207        RecursiveAction a = new CheckedRecursiveAction() {
208            protected void realCompute() {
209                FibAction f = new FibAction(8);
210                assertNull(f.invoke());
211                assertEquals(21, f.result);
212                checkCompletedNormally(f);
213            }};
214        testInvokeOnPool(mainPool(), a);
215    }
216
217    /**
218     * quietlyInvoke task returns when task completes normally.
219     * isCompletedAbnormally and isCancelled return false for normally
220     * completed tasks
221     */
222    public void testQuietlyInvoke() {
223        RecursiveAction a = new CheckedRecursiveAction() {
224            protected void realCompute() {
225                FibAction f = new FibAction(8);
226                f.quietlyInvoke();
227                assertEquals(21, f.result);
228                checkCompletedNormally(f);
229            }};
230        testInvokeOnPool(mainPool(), a);
231    }
232
233    /**
234     * join of a forked task returns when task completes
235     */
236    public void testForkJoin() {
237        RecursiveAction a = new CheckedRecursiveAction() {
238            protected void realCompute() {
239                FibAction f = new FibAction(8);
240                assertSame(f, f.fork());
241                assertNull(f.join());
242                assertEquals(21, f.result);
243                checkCompletedNormally(f);
244            }};
245        testInvokeOnPool(mainPool(), a);
246    }
247
248    /**
249     * join/quietlyJoin of a forked task succeeds in the presence of interrupts
250     */
251    public void testJoinIgnoresInterrupts() {
252        RecursiveAction a = new CheckedRecursiveAction() {
253            protected void realCompute() {
254                FibAction f = new FibAction(8);
255                final Thread myself = Thread.currentThread();
256
257                // test join()
258                assertSame(f, f.fork());
259                myself.interrupt();
260                assertTrue(myself.isInterrupted());
261                assertNull(f.join());
262                Thread.interrupted();
263                assertEquals(21, f.result);
264                checkCompletedNormally(f);
265
266                f = new FibAction(8);
267                f.cancel(true);
268                assertSame(f, f.fork());
269                myself.interrupt();
270                assertTrue(myself.isInterrupted());
271                try {
272                    f.join();
273                    shouldThrow();
274                } catch (CancellationException success) {
275                    Thread.interrupted();
276                    checkCancelled(f);
277                }
278
279                f = new FibAction(8);
280                f.completeExceptionally(new FJException());
281                assertSame(f, f.fork());
282                myself.interrupt();
283                assertTrue(myself.isInterrupted());
284                try {
285                    f.join();
286                    shouldThrow();
287                } catch (FJException success) {
288                    Thread.interrupted();
289                    checkCompletedAbnormally(f, success);
290                }
291
292                // test quietlyJoin()
293                f = new FibAction(8);
294                assertSame(f, f.fork());
295                myself.interrupt();
296                assertTrue(myself.isInterrupted());
297                f.quietlyJoin();
298                Thread.interrupted();
299                assertEquals(21, f.result);
300                checkCompletedNormally(f);
301
302                f = new FibAction(8);
303                f.cancel(true);
304                assertSame(f, f.fork());
305                myself.interrupt();
306                assertTrue(myself.isInterrupted());
307                f.quietlyJoin();
308                Thread.interrupted();
309                checkCancelled(f);
310
311                f = new FibAction(8);
312                f.completeExceptionally(new FJException());
313                assertSame(f, f.fork());
314                myself.interrupt();
315                assertTrue(myself.isInterrupted());
316                f.quietlyJoin();
317                Thread.interrupted();
318                checkCompletedAbnormally(f, f.getException());
319            }};
320        testInvokeOnPool(mainPool(), a);
321        a.reinitialize();
322        testInvokeOnPool(singletonPool(), a);
323    }
324
325    /**
326     * join/quietlyJoin of a forked task when not in ForkJoinPool
327     * succeeds in the presence of interrupts
328     */
329    public void testJoinIgnoresInterruptsOutsideForkJoinPool() {
330        final SynchronousQueue<FibAction[]> sq =
331            new SynchronousQueue<FibAction[]>();
332        RecursiveAction a = new CheckedRecursiveAction() {
333            protected void realCompute() throws InterruptedException {
334                FibAction[] fibActions = new FibAction[6];
335                for (int i = 0; i < fibActions.length; i++)
336                    fibActions[i] = new FibAction(8);
337
338                fibActions[1].cancel(false);
339                fibActions[2].completeExceptionally(new FJException());
340                fibActions[4].cancel(true);
341                fibActions[5].completeExceptionally(new FJException());
342
343                for (int i = 0; i < fibActions.length; i++)
344                    fibActions[i].fork();
345
346                sq.put(fibActions);
347
348                helpQuiesce();
349            }};
350
351        Runnable r = new CheckedRunnable() {
352            public void realRun() throws InterruptedException {
353                FibAction[] fibActions = sq.take();
354                FibAction f;
355                final Thread myself = Thread.currentThread();
356
357                // test join() ------------
358
359                f = fibActions[0];
360                assertFalse(ForkJoinTask.inForkJoinPool());
361                myself.interrupt();
362                assertTrue(myself.isInterrupted());
363                assertNull(f.join());
364                assertTrue(Thread.interrupted());
365                assertEquals(21, f.result);
366                checkCompletedNormally(f);
367
368                f = fibActions[1];
369                myself.interrupt();
370                assertTrue(myself.isInterrupted());
371                try {
372                    f.join();
373                    shouldThrow();
374                } catch (CancellationException success) {
375                    assertTrue(Thread.interrupted());
376                    checkCancelled(f);
377                }
378
379                f = fibActions[2];
380                myself.interrupt();
381                assertTrue(myself.isInterrupted());
382                try {
383                    f.join();
384                    shouldThrow();
385                } catch (FJException success) {
386                    assertTrue(Thread.interrupted());
387                    checkCompletedAbnormally(f, success);
388                }
389
390                // test quietlyJoin() ---------
391
392                f = fibActions[3];
393                myself.interrupt();
394                assertTrue(myself.isInterrupted());
395                f.quietlyJoin();
396                assertTrue(Thread.interrupted());
397                assertEquals(21, f.result);
398                checkCompletedNormally(f);
399
400                f = fibActions[4];
401                myself.interrupt();
402                assertTrue(myself.isInterrupted());
403                f.quietlyJoin();
404                assertTrue(Thread.interrupted());
405                checkCancelled(f);
406
407                f = fibActions[5];
408                myself.interrupt();
409                assertTrue(myself.isInterrupted());
410                f.quietlyJoin();
411                assertTrue(Thread.interrupted());
412                assertTrue(f.getException() instanceof FJException);
413                checkCompletedAbnormally(f, f.getException());
414            }};
415
416        Thread t;
417
418        t = newStartedThread(r);
419        testInvokeOnPool(mainPool(), a);
420        awaitTermination(t, LONG_DELAY_MS);
421
422        a.reinitialize();
423        t = newStartedThread(r);
424        testInvokeOnPool(singletonPool(), a);
425        awaitTermination(t, LONG_DELAY_MS);
426    }
427
428    /**
429     * get of a forked task returns when task completes
430     */
431    public void testForkGet() {
432        RecursiveAction a = new CheckedRecursiveAction() {
433            protected void realCompute() throws Exception {
434                FibAction f = new FibAction(8);
435                assertSame(f, f.fork());
436                assertNull(f.get());
437                assertEquals(21, f.result);
438                checkCompletedNormally(f);
439            }};
440        testInvokeOnPool(mainPool(), a);
441    }
442
443    /**
444     * timed get of a forked task returns when task completes
445     */
446    public void testForkTimedGet() {
447        RecursiveAction a = new CheckedRecursiveAction() {
448            protected void realCompute() throws Exception {
449                FibAction f = new FibAction(8);
450                assertSame(f, f.fork());
451                assertNull(f.get(5L, SECONDS));
452                assertEquals(21, f.result);
453                checkCompletedNormally(f);
454            }};
455        testInvokeOnPool(mainPool(), a);
456    }
457
458    /**
459     * timed get with null time unit throws NPE
460     */
461    public void testForkTimedGetNPE() {
462        RecursiveAction a = new CheckedRecursiveAction() {
463            protected void realCompute() throws Exception {
464                FibAction f = new FibAction(8);
465                assertSame(f, f.fork());
466                try {
467                    f.get(5L, null);
468                    shouldThrow();
469                } catch (NullPointerException success) {}
470            }};
471        testInvokeOnPool(mainPool(), a);
472    }
473
474    /**
475     * quietlyJoin of a forked task returns when task completes
476     */
477    public void testForkQuietlyJoin() {
478        RecursiveAction a = new CheckedRecursiveAction() {
479            protected void realCompute() {
480                FibAction f = new FibAction(8);
481                assertSame(f, f.fork());
482                f.quietlyJoin();
483                assertEquals(21, f.result);
484                checkCompletedNormally(f);
485            }};
486        testInvokeOnPool(mainPool(), a);
487    }
488
489    /**
490     * helpQuiesce returns when tasks are complete.
491     * getQueuedTaskCount returns 0 when quiescent
492     */
493    public void testForkHelpQuiesce() {
494        RecursiveAction a = new CheckedRecursiveAction() {
495            protected void realCompute() {
496                FibAction f = new FibAction(8);
497                assertSame(f, f.fork());
498                helpQuiesce();
499                assertEquals(21, f.result);
500                assertEquals(0, getQueuedTaskCount());
501                checkCompletedNormally(f);
502            }};
503        testInvokeOnPool(mainPool(), a);
504    }
505
506    /**
507     * invoke task throws exception when task completes abnormally
508     */
509    public void testAbnormalInvoke() {
510        RecursiveAction a = new CheckedRecursiveAction() {
511            protected void realCompute() {
512                FailingFibAction f = new FailingFibAction(8);
513                try {
514                    f.invoke();
515                    shouldThrow();
516                } catch (FJException success) {
517                    checkCompletedAbnormally(f, success);
518                }
519            }};
520        testInvokeOnPool(mainPool(), a);
521    }
522
523    /**
524     * quietlyInvoke task returns when task completes abnormally
525     */
526    public void testAbnormalQuietlyInvoke() {
527        RecursiveAction a = new CheckedRecursiveAction() {
528            protected void realCompute() {
529                FailingFibAction f = new FailingFibAction(8);
530                f.quietlyInvoke();
531                assertTrue(f.getException() instanceof FJException);
532                checkCompletedAbnormally(f, f.getException());
533            }};
534        testInvokeOnPool(mainPool(), a);
535    }
536
537    /**
538     * join of a forked task throws exception when task completes abnormally
539     */
540    public void testAbnormalForkJoin() {
541        RecursiveAction a = new CheckedRecursiveAction() {
542            protected void realCompute() {
543                FailingFibAction f = new FailingFibAction(8);
544                assertSame(f, f.fork());
545                try {
546                    f.join();
547                    shouldThrow();
548                } catch (FJException success) {
549                    checkCompletedAbnormally(f, success);
550                }
551            }};
552        testInvokeOnPool(mainPool(), a);
553    }
554
555    /**
556     * get of a forked task throws exception when task completes abnormally
557     */
558    public void testAbnormalForkGet() {
559        RecursiveAction a = new CheckedRecursiveAction() {
560            protected void realCompute() throws Exception {
561                FailingFibAction f = new FailingFibAction(8);
562                assertSame(f, f.fork());
563                try {
564                    f.get();
565                    shouldThrow();
566                } catch (ExecutionException success) {
567                    Throwable cause = success.getCause();
568                    assertTrue(cause instanceof FJException);
569                    checkCompletedAbnormally(f, cause);
570                }
571            }};
572        testInvokeOnPool(mainPool(), a);
573    }
574
575    /**
576     * timed get of a forked task throws exception when task completes abnormally
577     */
578    public void testAbnormalForkTimedGet() {
579        RecursiveAction a = new CheckedRecursiveAction() {
580            protected void realCompute() throws Exception {
581                FailingFibAction f = new FailingFibAction(8);
582                assertSame(f, f.fork());
583                try {
584                    f.get(5L, TimeUnit.SECONDS);
585                    shouldThrow();
586                } catch (ExecutionException success) {
587                    Throwable cause = success.getCause();
588                    assertTrue(cause instanceof FJException);
589                    checkCompletedAbnormally(f, cause);
590                }
591            }};
592        testInvokeOnPool(mainPool(), a);
593    }
594
595    /**
596     * quietlyJoin of a forked task returns when task completes abnormally
597     */
598    public void testAbnormalForkQuietlyJoin() {
599        RecursiveAction a = new CheckedRecursiveAction() {
600            protected void realCompute() {
601                FailingFibAction f = new FailingFibAction(8);
602                assertSame(f, f.fork());
603                f.quietlyJoin();
604                assertTrue(f.getException() instanceof FJException);
605                checkCompletedAbnormally(f, f.getException());
606            }};
607        testInvokeOnPool(mainPool(), a);
608    }
609
610    /**
611     * invoke task throws exception when task cancelled
612     */
613    public void testCancelledInvoke() {
614        RecursiveAction a = new CheckedRecursiveAction() {
615            protected void realCompute() {
616                FibAction f = new FibAction(8);
617                assertTrue(f.cancel(true));
618                try {
619                    f.invoke();
620                    shouldThrow();
621                } catch (CancellationException success) {
622                    checkCancelled(f);
623                }
624            }};
625        testInvokeOnPool(mainPool(), a);
626    }
627
628    /**
629     * join of a forked task throws exception when task cancelled
630     */
631    public void testCancelledForkJoin() {
632        RecursiveAction a = new CheckedRecursiveAction() {
633            protected void realCompute() {
634                FibAction f = new FibAction(8);
635                assertTrue(f.cancel(true));
636                assertSame(f, f.fork());
637                try {
638                    f.join();
639                    shouldThrow();
640                } catch (CancellationException success) {
641                    checkCancelled(f);
642                }
643            }};
644        testInvokeOnPool(mainPool(), a);
645    }
646
647    /**
648     * get of a forked task throws exception when task cancelled
649     */
650    public void testCancelledForkGet() {
651        RecursiveAction a = new CheckedRecursiveAction() {
652            protected void realCompute() throws Exception {
653                FibAction f = new FibAction(8);
654                assertTrue(f.cancel(true));
655                assertSame(f, f.fork());
656                try {
657                    f.get();
658                    shouldThrow();
659                } catch (CancellationException success) {
660                    checkCancelled(f);
661                }
662            }};
663        testInvokeOnPool(mainPool(), a);
664    }
665
666    /**
667     * timed get of a forked task throws exception when task cancelled
668     */
669    public void testCancelledForkTimedGet() {
670        RecursiveAction a = new CheckedRecursiveAction() {
671            protected void realCompute() throws Exception {
672                FibAction f = new FibAction(8);
673                assertTrue(f.cancel(true));
674                assertSame(f, f.fork());
675                try {
676                    f.get(5L, SECONDS);
677                    shouldThrow();
678                } catch (CancellationException success) {
679                    checkCancelled(f);
680                }
681            }};
682        testInvokeOnPool(mainPool(), a);
683    }
684
685    /**
686     * quietlyJoin of a forked task returns when task cancelled
687     */
688    public void testCancelledForkQuietlyJoin() {
689        RecursiveAction a = new CheckedRecursiveAction() {
690            protected void realCompute() {
691                FibAction f = new FibAction(8);
692                assertTrue(f.cancel(true));
693                assertSame(f, f.fork());
694                f.quietlyJoin();
695                checkCancelled(f);
696            }};
697        testInvokeOnPool(mainPool(), a);
698    }
699
700    /**
701     * getPool of executing task returns its pool
702     */
703    public void testGetPool() {
704        final ForkJoinPool mainPool = mainPool();
705        RecursiveAction a = new CheckedRecursiveAction() {
706            protected void realCompute() {
707                assertSame(mainPool, getPool());
708            }};
709        testInvokeOnPool(mainPool, a);
710    }
711
712    /**
713     * getPool of non-FJ task returns null
714     */
715    public void testGetPool2() {
716        RecursiveAction a = new CheckedRecursiveAction() {
717            protected void realCompute() {
718                assertNull(getPool());
719            }};
720        assertNull(a.invoke());
721    }
722
723    /**
724     * inForkJoinPool of executing task returns true
725     */
726    public void testInForkJoinPool() {
727        RecursiveAction a = new CheckedRecursiveAction() {
728            protected void realCompute() {
729                assertTrue(inForkJoinPool());
730            }};
731        testInvokeOnPool(mainPool(), a);
732    }
733
734    /**
735     * inForkJoinPool of non-FJ task returns false
736     */
737    public void testInForkJoinPool2() {
738        RecursiveAction a = new CheckedRecursiveAction() {
739            protected void realCompute() {
740                assertFalse(inForkJoinPool());
741            }};
742        assertNull(a.invoke());
743    }
744
745    /**
746     * getPool of current thread in pool returns its pool
747     */
748    public void testWorkerGetPool() {
749        final ForkJoinPool mainPool = mainPool();
750        RecursiveAction a = new CheckedRecursiveAction() {
751            protected void realCompute() {
752                ForkJoinWorkerThread w =
753                    (ForkJoinWorkerThread) Thread.currentThread();
754                assertSame(mainPool, w.getPool());
755            }};
756        testInvokeOnPool(mainPool, a);
757    }
758
759    /**
760     * getPoolIndex of current thread in pool returns 0 <= value < poolSize
761     */
762    public void testWorkerGetPoolIndex() {
763        final ForkJoinPool mainPool = mainPool();
764        RecursiveAction a = new CheckedRecursiveAction() {
765            protected void realCompute() {
766                ForkJoinWorkerThread w =
767                    (ForkJoinWorkerThread) Thread.currentThread();
768                assertTrue(w.getPoolIndex() >= 0);
769                // pool size can shrink after assigning index, so cannot check
770                // assertTrue(w.getPoolIndex() < mainPool.getPoolSize());
771            }};
772        testInvokeOnPool(mainPool, a);
773    }
774
775    /**
776     * setRawResult(null) succeeds
777     */
778    public void testSetRawResult() {
779        RecursiveAction a = new CheckedRecursiveAction() {
780            protected void realCompute() {
781                setRawResult(null);
782                assertNull(getRawResult());
783            }};
784        assertNull(a.invoke());
785    }
786
787    /**
788     * A reinitialized normally completed task may be re-invoked
789     */
790    public void testReinitialize() {
791        RecursiveAction a = new CheckedRecursiveAction() {
792            protected void realCompute() {
793                FibAction f = new FibAction(8);
794                checkNotDone(f);
795
796                for (int i = 0; i < 3; i++) {
797                    assertNull(f.invoke());
798                    assertEquals(21, f.result);
799                    checkCompletedNormally(f);
800                    f.reinitialize();
801                    checkNotDone(f);
802                }
803            }};
804        testInvokeOnPool(mainPool(), a);
805    }
806
807    /**
808     * A reinitialized abnormally completed task may be re-invoked
809     */
810    public void testReinitializeAbnormal() {
811        RecursiveAction a = new CheckedRecursiveAction() {
812            protected void realCompute() {
813                FailingFibAction f = new FailingFibAction(8);
814                checkNotDone(f);
815
816                for (int i = 0; i < 3; i++) {
817                    try {
818                        f.invoke();
819                        shouldThrow();
820                    } catch (FJException success) {
821                        checkCompletedAbnormally(f, success);
822                    }
823                    f.reinitialize();
824                    checkNotDone(f);
825                }
826            }};
827        testInvokeOnPool(mainPool(), a);
828    }
829
830    /**
831     * invoke task throws exception after invoking completeExceptionally
832     */
833    public void testCompleteExceptionally() {
834        RecursiveAction a = new CheckedRecursiveAction() {
835            protected void realCompute() {
836                FibAction f = new FibAction(8);
837                f.completeExceptionally(new FJException());
838                try {
839                    f.invoke();
840                    shouldThrow();
841                } catch (FJException success) {
842                    checkCompletedAbnormally(f, success);
843                }
844            }};
845        testInvokeOnPool(mainPool(), a);
846    }
847
848    /**
849     * invoke task suppresses execution invoking complete
850     */
851    public void testComplete() {
852        RecursiveAction a = new CheckedRecursiveAction() {
853            protected void realCompute() {
854                FibAction f = new FibAction(8);
855                f.complete(null);
856                assertNull(f.invoke());
857                assertEquals(0, f.result);
858                checkCompletedNormally(f);
859            }};
860        testInvokeOnPool(mainPool(), a);
861    }
862
863    /**
864     * invokeAll(t1, t2) invokes all task arguments
865     */
866    public void testInvokeAll2() {
867        RecursiveAction a = new CheckedRecursiveAction() {
868            protected void realCompute() {
869                FibAction f = new FibAction(8);
870                FibAction g = new FibAction(9);
871                invokeAll(f, g);
872                checkCompletedNormally(f);
873                assertEquals(21, f.result);
874                checkCompletedNormally(g);
875                assertEquals(34, g.result);
876            }};
877        testInvokeOnPool(mainPool(), a);
878    }
879
880    /**
881     * invokeAll(tasks) with 1 argument invokes task
882     */
883    public void testInvokeAll1() {
884        RecursiveAction a = new CheckedRecursiveAction() {
885            protected void realCompute() {
886                FibAction f = new FibAction(8);
887                invokeAll(f);
888                checkCompletedNormally(f);
889                assertEquals(21, f.result);
890            }};
891        testInvokeOnPool(mainPool(), a);
892    }
893
894    /**
895     * invokeAll(tasks) with > 2 argument invokes tasks
896     */
897    public void testInvokeAll3() {
898        RecursiveAction a = new CheckedRecursiveAction() {
899            protected void realCompute() {
900                FibAction f = new FibAction(8);
901                FibAction g = new FibAction(9);
902                FibAction h = new FibAction(7);
903                invokeAll(f, g, h);
904                assertTrue(f.isDone());
905                assertTrue(g.isDone());
906                assertTrue(h.isDone());
907                checkCompletedNormally(f);
908                assertEquals(21, f.result);
909                checkCompletedNormally(g);
910                assertEquals(34, g.result);
911                checkCompletedNormally(g);
912                assertEquals(13, h.result);
913            }};
914        testInvokeOnPool(mainPool(), a);
915    }
916
917    /**
918     * invokeAll(collection) invokes all tasks in the collection
919     */
920    public void testInvokeAllCollection() {
921        RecursiveAction a = new CheckedRecursiveAction() {
922            protected void realCompute() {
923                FibAction f = new FibAction(8);
924                FibAction g = new FibAction(9);
925                FibAction h = new FibAction(7);
926                HashSet set = new HashSet();
927                set.add(f);
928                set.add(g);
929                set.add(h);
930                invokeAll(set);
931                assertTrue(f.isDone());
932                assertTrue(g.isDone());
933                assertTrue(h.isDone());
934                checkCompletedNormally(f);
935                assertEquals(21, f.result);
936                checkCompletedNormally(g);
937                assertEquals(34, g.result);
938                checkCompletedNormally(g);
939                assertEquals(13, h.result);
940            }};
941        testInvokeOnPool(mainPool(), a);
942    }
943
944    /**
945     * invokeAll(tasks) with any null task throws NPE
946     */
947    public void testInvokeAllNPE() {
948        RecursiveAction a = new CheckedRecursiveAction() {
949            protected void realCompute() {
950                FibAction f = new FibAction(8);
951                FibAction g = new FibAction(9);
952                FibAction h = null;
953                try {
954                    invokeAll(f, g, h);
955                    shouldThrow();
956                } catch (NullPointerException success) {}
957            }};
958        testInvokeOnPool(mainPool(), a);
959    }
960
961    /**
962     * invokeAll(t1, t2) throw exception if any task does
963     */
964    public void testAbnormalInvokeAll2() {
965        RecursiveAction a = new CheckedRecursiveAction() {
966            protected void realCompute() {
967                FibAction f = new FibAction(8);
968                FailingFibAction g = new FailingFibAction(9);
969                try {
970                    invokeAll(f, g);
971                    shouldThrow();
972                } catch (FJException success) {
973                    checkCompletedAbnormally(g, success);
974                }
975            }};
976        testInvokeOnPool(mainPool(), a);
977    }
978
979    /**
980     * invokeAll(tasks) with 1 argument throws exception if task does
981     */
982    public void testAbnormalInvokeAll1() {
983        RecursiveAction a = new CheckedRecursiveAction() {
984            protected void realCompute() {
985                FailingFibAction g = new FailingFibAction(9);
986                try {
987                    invokeAll(g);
988                    shouldThrow();
989                } catch (FJException success) {
990                    checkCompletedAbnormally(g, success);
991                }
992            }};
993        testInvokeOnPool(mainPool(), a);
994    }
995
996    /**
997     * invokeAll(tasks) with > 2 argument throws exception if any task does
998     */
999    public void testAbnormalInvokeAll3() {
1000        RecursiveAction a = new CheckedRecursiveAction() {
1001            protected void realCompute() {
1002                FibAction f = new FibAction(8);
1003                FailingFibAction g = new FailingFibAction(9);
1004                FibAction h = new FibAction(7);
1005                try {
1006                    invokeAll(f, g, h);
1007                    shouldThrow();
1008                } catch (FJException success) {
1009                    checkCompletedAbnormally(g, success);
1010                }
1011            }};
1012        testInvokeOnPool(mainPool(), a);
1013    }
1014
1015    /**
1016     * invokeAll(collection) throws exception if any task does
1017     */
1018    public void testAbnormalInvokeAllCollection() {
1019        RecursiveAction a = new CheckedRecursiveAction() {
1020            protected void realCompute() {
1021                FailingFibAction f = new FailingFibAction(8);
1022                FibAction g = new FibAction(9);
1023                FibAction h = new FibAction(7);
1024                HashSet set = new HashSet();
1025                set.add(f);
1026                set.add(g);
1027                set.add(h);
1028                try {
1029                    invokeAll(set);
1030                    shouldThrow();
1031                } catch (FJException success) {
1032                    checkCompletedAbnormally(f, success);
1033                }
1034            }};
1035        testInvokeOnPool(mainPool(), a);
1036    }
1037
1038    /**
1039     * tryUnfork returns true for most recent unexecuted task,
1040     * and suppresses execution
1041     */
1042    public void testTryUnfork() {
1043        RecursiveAction a = new CheckedRecursiveAction() {
1044            protected void realCompute() {
1045                FibAction g = new FibAction(9);
1046                assertSame(g, g.fork());
1047                FibAction f = new FibAction(8);
1048                assertSame(f, f.fork());
1049                assertTrue(f.tryUnfork());
1050                helpQuiesce();
1051                checkNotDone(f);
1052                checkCompletedNormally(g);
1053            }};
1054        testInvokeOnPool(singletonPool(), a);
1055    }
1056
1057    /**
1058     * getSurplusQueuedTaskCount returns > 0 when
1059     * there are more tasks than threads
1060     */
1061    public void testGetSurplusQueuedTaskCount() {
1062        RecursiveAction a = new CheckedRecursiveAction() {
1063            protected void realCompute() {
1064                FibAction h = new FibAction(7);
1065                assertSame(h, h.fork());
1066                FibAction g = new FibAction(9);
1067                assertSame(g, g.fork());
1068                FibAction f = new FibAction(8);
1069                assertSame(f, f.fork());
1070                assertTrue(getSurplusQueuedTaskCount() > 0);
1071                helpQuiesce();
1072                assertEquals(0, getSurplusQueuedTaskCount());
1073                checkCompletedNormally(f);
1074                checkCompletedNormally(g);
1075                checkCompletedNormally(h);
1076            }};
1077        testInvokeOnPool(singletonPool(), a);
1078    }
1079
1080    /**
1081     * peekNextLocalTask returns most recent unexecuted task.
1082     */
1083    public void testPeekNextLocalTask() {
1084        RecursiveAction a = new CheckedRecursiveAction() {
1085            protected void realCompute() {
1086                FibAction g = new FibAction(9);
1087                assertSame(g, g.fork());
1088                FibAction f = new FibAction(8);
1089                assertSame(f, f.fork());
1090                assertSame(f, peekNextLocalTask());
1091                assertNull(f.join());
1092                checkCompletedNormally(f);
1093                helpQuiesce();
1094                checkCompletedNormally(f);
1095                checkCompletedNormally(g);
1096            }};
1097        testInvokeOnPool(singletonPool(), a);
1098    }
1099
1100    /**
1101     * pollNextLocalTask returns most recent unexecuted task
1102     * without executing it
1103     */
1104    public void testPollNextLocalTask() {
1105        RecursiveAction a = new CheckedRecursiveAction() {
1106            protected void realCompute() {
1107                FibAction g = new FibAction(9);
1108                assertSame(g, g.fork());
1109                FibAction f = new FibAction(8);
1110                assertSame(f, f.fork());
1111                assertSame(f, pollNextLocalTask());
1112                helpQuiesce();
1113                checkNotDone(f);
1114                checkCompletedNormally(g);
1115            }};
1116        testInvokeOnPool(singletonPool(), a);
1117    }
1118
1119    /**
1120     * pollTask returns an unexecuted task without executing it
1121     */
1122    public void testPollTask() {
1123        RecursiveAction a = new CheckedRecursiveAction() {
1124            protected void realCompute() {
1125                FibAction g = new FibAction(9);
1126                assertSame(g, g.fork());
1127                FibAction f = new FibAction(8);
1128                assertSame(f, f.fork());
1129                assertSame(f, pollTask());
1130                helpQuiesce();
1131                checkNotDone(f);
1132                checkCompletedNormally(g);
1133            }};
1134        testInvokeOnPool(singletonPool(), a);
1135    }
1136
1137    /**
1138     * peekNextLocalTask returns least recent unexecuted task in async mode
1139     */
1140    public void testPeekNextLocalTaskAsync() {
1141        RecursiveAction a = new CheckedRecursiveAction() {
1142            protected void realCompute() {
1143                FibAction g = new FibAction(9);
1144                assertSame(g, g.fork());
1145                FibAction f = new FibAction(8);
1146                assertSame(f, f.fork());
1147                assertSame(g, peekNextLocalTask());
1148                assertNull(f.join());
1149                helpQuiesce();
1150                checkCompletedNormally(f);
1151                checkCompletedNormally(g);
1152            }};
1153        testInvokeOnPool(asyncSingletonPool(), a);
1154    }
1155
1156    /**
1157     * pollNextLocalTask returns least recent unexecuted task without
1158     * executing it, in async mode
1159     */
1160    public void testPollNextLocalTaskAsync() {
1161        RecursiveAction a = new CheckedRecursiveAction() {
1162            protected void realCompute() {
1163                FibAction g = new FibAction(9);
1164                assertSame(g, g.fork());
1165                FibAction f = new FibAction(8);
1166                assertSame(f, f.fork());
1167                assertSame(g, pollNextLocalTask());
1168                helpQuiesce();
1169                checkCompletedNormally(f);
1170                checkNotDone(g);
1171            }};
1172        testInvokeOnPool(asyncSingletonPool(), a);
1173    }
1174
1175    /**
1176     * pollTask returns an unexecuted task without executing it, in
1177     * async mode
1178     */
1179    public void testPollTaskAsync() {
1180        RecursiveAction a = new CheckedRecursiveAction() {
1181            protected void realCompute() {
1182                FibAction g = new FibAction(9);
1183                assertSame(g, g.fork());
1184                FibAction f = new FibAction(8);
1185                assertSame(f, f.fork());
1186                assertSame(g, pollTask());
1187                helpQuiesce();
1188                checkCompletedNormally(f);
1189                checkNotDone(g);
1190            }};
1191        testInvokeOnPool(asyncSingletonPool(), a);
1192    }
1193
1194    /** Demo from RecursiveAction javadoc */
1195    static class SortTask extends RecursiveAction {
1196        final long[] array; final int lo, hi;
1197        SortTask(long[] array, int lo, int hi) {
1198            this.array = array; this.lo = lo; this.hi = hi;
1199        }
1200        SortTask(long[] array) { this(array, 0, array.length); }
1201        protected void compute() {
1202            if (hi - lo < THRESHOLD)
1203                sortSequentially(lo, hi);
1204            else {
1205                int mid = (lo + hi) >>> 1;
1206                invokeAll(new SortTask(array, lo, mid),
1207                          new SortTask(array, mid, hi));
1208                merge(lo, mid, hi);
1209            }
1210        }
1211        // implementation details follow:
1212        static final int THRESHOLD = 100;
1213        void sortSequentially(int lo, int hi) {
1214            Arrays.sort(array, lo, hi);
1215        }
1216        void merge(int lo, int mid, int hi) {
1217            long[] buf = Arrays.copyOfRange(array, lo, mid);
1218            for (int i = 0, j = lo, k = mid; i < buf.length; j++)
1219                array[j] = (k == hi || buf[i] < array[k]) ?
1220                    buf[i++] : array[k++];
1221        }
1222    }
1223
1224    /**
1225     * SortTask demo works as advertised
1226     */
1227    public void testSortTaskDemo() {
1228        ThreadLocalRandom rnd = ThreadLocalRandom.current();
1229        long[] array = new long[1007];
1230        for (int i = 0; i < array.length; i++)
1231            array[i] = rnd.nextLong();
1232        long[] arrayClone = array.clone();
1233        testInvokeOnPool(mainPool(), new SortTask(array));
1234        Arrays.sort(arrayClone);
1235        assertTrue(Arrays.equals(array, arrayClone));
1236    }
1237}
1238