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 junit.framework.*;
10 import java.util.concurrent.CancellationException;
11 import java.util.concurrent.SynchronousQueue;
12 import java.util.concurrent.ExecutionException;
13 import java.util.concurrent.ForkJoinPool;
14 import java.util.concurrent.ForkJoinTask;
15 import java.util.concurrent.ForkJoinWorkerThread;
16 import java.util.concurrent.RecursiveAction;
17 import java.util.concurrent.ThreadLocalRandom;
18 import java.util.concurrent.TimeUnit;
19 import java.util.concurrent.TimeoutException;
20 import static java.util.concurrent.TimeUnit.SECONDS;
21 import java.util.Arrays;
22 import java.util.HashSet;
23 
24 public class RecursiveActionTest extends JSR166TestCase {
25 
mainPool()26     private static ForkJoinPool mainPool() {
27         return new ForkJoinPool();
28     }
29 
singletonPool()30     private static ForkJoinPool singletonPool() {
31         return new ForkJoinPool(1);
32     }
33 
asyncSingletonPool()34     private static ForkJoinPool asyncSingletonPool() {
35         return new ForkJoinPool(1,
36                                 ForkJoinPool.defaultForkJoinWorkerThreadFactory,
37                                 null, true);
38     }
39 
testInvokeOnPool(ForkJoinPool pool, RecursiveAction a)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 
checkNotDone(RecursiveAction a)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 
checkCompletedNormally(RecursiveAction a)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 
checkCancelled(RecursiveAction a)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 
checkCompletedAbnormally(RecursiveAction a, Throwable t)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 {
FJException()161         public FJException() { super(); }
FJException(Throwable cause)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;
FibAction(int n)169         FibAction(int n) { number = n; }
realCompute()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;
FailingFibAction(int n)187         FailingFibAction(int n) { number = n; }
compute()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      */
testInvoke()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      */
testQuietlyInvoke()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      */
testForkJoin()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      */
testJoinIgnoresInterrupts()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      */
testJoinIgnoresInterruptsOutsideForkJoinPool()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      */
testForkGet()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      */
testForkTimedGet()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      */
testForkTimedGetNPE()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      */
testForkQuietlyJoin()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      */
testForkHelpQuiesce()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      */
testAbnormalInvoke()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      */
testAbnormalQuietlyInvoke()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      */
testAbnormalForkJoin()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      */
testAbnormalForkGet()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      */
testAbnormalForkTimedGet()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      */
testAbnormalForkQuietlyJoin()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      */
testCancelledInvoke()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      */
testCancelledForkJoin()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      */
testCancelledForkGet()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      */
testCancelledForkTimedGet()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      */
testCancelledForkQuietlyJoin()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      */
testGetPool()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      */
testGetPool2()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      */
testInForkJoinPool()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      */
testInForkJoinPool2()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      */
testWorkerGetPool()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      */
testWorkerGetPoolIndex()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      */
testSetRawResult()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      */
testReinitialize()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      */
testReinitializeAbnormal()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      */
testCompleteExceptionally()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      */
testComplete()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      */
testInvokeAll2()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      */
testInvokeAll1()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      */
testInvokeAll3()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      */
testInvokeAllCollection()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      */
testInvokeAllNPE()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      */
testAbnormalInvokeAll2()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      */
testAbnormalInvokeAll1()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      */
testAbnormalInvokeAll3()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      */
testAbnormalInvokeAllCollection()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      */
testTryUnfork()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      */
testGetSurplusQueuedTaskCount()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      */
testPeekNextLocalTask()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      */
testPollNextLocalTask()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      */
testPollTask()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      */
testPeekNextLocalTaskAsync()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      */
testPollNextLocalTaskAsync()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      */
testPollTaskAsync()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;
SortTask(long[] array, int lo, int hi)1197         SortTask(long[] array, int lo, int hi) {
1198             this.array = array; this.lo = lo; this.hi = hi;
1199         }
SortTask(long[] array)1200         SortTask(long[] array) { this(array, 0, array.length); }
compute()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;
sortSequentially(int lo, int hi)1213         void sortSequentially(int lo, int hi) {
1214             Arrays.sort(array, lo, hi);
1215         }
merge(int lo, int mid, int hi)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      */
testSortTaskDemo()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