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