/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

/*

 * This file is available under and governed by the GNU General Public

 * License version 2 only, as published by the Free Software Foundation.

 * However, the following notice accompanied the original version of this

 * file:

 *

 * Written by Doug Lea with assistance from members of JCP JSR-166

 * Expert Group and released to the public domain, as explained at

 * http://creativecommons.org/publicdomain/zero/1.0/

 */

import static java.util.concurrent.TimeUnit.MILLISECONDS;

import java.util.Arrays;

import java.util.HashSet;

import java.util.concurrent.CancellationException;

import java.util.concurrent.ExecutionException;

import java.util.concurrent.ForkJoinPool;

import java.util.concurrent.ForkJoinTask;

import java.util.concurrent.ForkJoinWorkerThread;

import java.util.concurrent.RecursiveAction;

import java.util.concurrent.SynchronousQueue;

import java.util.concurrent.ThreadLocalRandom;

import java.util.concurrent.TimeoutException;

import junit.framework.Test;

import junit.framework.TestSuite;

public class RecursiveActionTest extends JSR166TestCase {

    public static void main(String[] args) {

        main(suite(), args);

    }

    public static Test suite() {

        return new TestSuite(RecursiveActionTest.class);

    }

    private static ForkJoinPool mainPool() {

        return new ForkJoinPool();

    }

    private static ForkJoinPool singletonPool() {

        return new ForkJoinPool(1);

    }

    private static ForkJoinPool asyncSingletonPool() {

        return new ForkJoinPool(1,

                                ForkJoinPool.defaultForkJoinWorkerThreadFactory,

                                null, true);

    }

    private void testInvokeOnPool(ForkJoinPool pool, RecursiveAction a) {

        try (PoolCleaner cleaner = cleaner(pool)) {

            checkNotDone(a);

            assertNull(pool.invoke(a));

            checkCompletedNormally(a);

        }

    }

    void checkNotDone(RecursiveAction a) {

        assertFalse(a.isDone());

        assertFalse(a.isCompletedNormally());

        assertFalse(a.isCompletedAbnormally());

        assertFalse(a.isCancelled());

        assertNull(a.getException());

        assertNull(a.getRawResult());

        if (! ForkJoinTask.inForkJoinPool()) {

            Thread.currentThread().interrupt();

            try {

                a.get();

                shouldThrow();

            } catch (InterruptedException success) {

            } catch (Throwable fail) { threadUnexpectedException(fail); }

            Thread.currentThread().interrupt();

            try {

                a.get(randomTimeout(), randomTimeUnit());

                shouldThrow();

            } catch (InterruptedException success) {

            } catch (Throwable fail) { threadUnexpectedException(fail); }

        }

        try {

            a.get(randomExpiredTimeout(), randomTimeUnit());

            shouldThrow();

        } catch (TimeoutException success) {

        } catch (Throwable fail) { threadUnexpectedException(fail); }

    }

    void checkCompletedNormally(RecursiveAction a) {

        assertTrue(a.isDone());

        assertFalse(a.isCancelled());

        assertTrue(a.isCompletedNormally());

        assertFalse(a.isCompletedAbnormally());

        assertNull(a.getException());

        assertNull(a.getRawResult());

        assertNull(a.join());

        assertFalse(a.cancel(false));

        assertFalse(a.cancel(true));

        try {

            assertNull(a.get());

            assertNull(a.get(randomTimeout(), randomTimeUnit()));

        } catch (Throwable fail) { threadUnexpectedException(fail); }

    }

    void checkCancelled(RecursiveAction a) {

        assertTrue(a.isDone());

        assertTrue(a.isCancelled());

        assertFalse(a.isCompletedNormally());

        assertTrue(a.isCompletedAbnormally());

        assertTrue(a.getException() instanceof CancellationException);

        assertNull(a.getRawResult());

        try {

            a.join();

            shouldThrow();

        } catch (CancellationException success) {

        } catch (Throwable fail) { threadUnexpectedException(fail); }

        try {

            a.get();

            shouldThrow();

        } catch (CancellationException success) {

        } catch (Throwable fail) { threadUnexpectedException(fail); }

        try {

            a.get(randomTimeout(), randomTimeUnit());

            shouldThrow();

        } catch (CancellationException success) {

        } catch (Throwable fail) { threadUnexpectedException(fail); }

    }

    void checkCompletedAbnormally(RecursiveAction a, Throwable t) {

        assertTrue(a.isDone());

        assertFalse(a.isCancelled());

        assertFalse(a.isCompletedNormally());

        assertTrue(a.isCompletedAbnormally());

        assertSame(t.getClass(), a.getException().getClass());

        assertNull(a.getRawResult());

        assertFalse(a.cancel(false));

        assertFalse(a.cancel(true));

        try {

            a.join();

            shouldThrow();

        } catch (Throwable expected) {

            assertSame(expected.getClass(), t.getClass());

        }

        try {

            a.get();

            shouldThrow();

        } catch (ExecutionException success) {

            assertSame(t.getClass(), success.getCause().getClass());

        } catch (Throwable fail) { threadUnexpectedException(fail); }

        try {

            a.get(randomTimeout(), randomTimeUnit());

            shouldThrow();

        } catch (ExecutionException success) {

            assertSame(t.getClass(), success.getCause().getClass());

        } catch (Throwable fail) { threadUnexpectedException(fail); }

    }

    public static final class FJException extends RuntimeException {

        public FJException() { super(); }

        public FJException(Throwable cause) { super(cause); }

    }

    /** A simple recursive action for testing. */

    final class FibAction extends CheckedRecursiveAction {

        final int number;

        int result;

        FibAction(int n) { number = n; }

        protected void realCompute() {

            int n = number;

            if (n <= 1)

                result = n;

            else {

                FibAction f1 = new FibAction(n - 1);

                FibAction f2 = new FibAction(n - 2);

                invokeAll(f1, f2);

                result = f1.result + f2.result;

            }

        }

    }

    /** A recursive action failing in base case. */

    static final class FailingFibAction extends RecursiveAction {

        final int number;

        int result;

        FailingFibAction(int n) { number = n; }

        public void compute() {

            int n = number;

            if (n <= 1)

                throw new FJException();

            else {

                FailingFibAction f1 = new FailingFibAction(n - 1);

                FailingFibAction f2 = new FailingFibAction(n - 2);

                invokeAll(f1, f2);

                result = f1.result + f2.result;

            }

        }

    }

    /**

     * invoke returns when task completes normally.

     * isCompletedAbnormally and isCancelled return false for normally

     * completed tasks. getRawResult of a RecursiveAction returns null;

     */

    public void testInvoke() {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() {

                FibAction f = new FibAction(8);

                assertNull(f.invoke());

                assertEquals(21, f.result);

                checkCompletedNormally(f);

            }};

        testInvokeOnPool(mainPool(), a);

    }

    /**

     * quietlyInvoke task returns when task completes normally.

     * isCompletedAbnormally and isCancelled return false for normally

     * completed tasks

     */

    public void testQuietlyInvoke() {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() {

                FibAction f = new FibAction(8);

                f.quietlyInvoke();

                assertEquals(21, f.result);

                checkCompletedNormally(f);

            }};

        testInvokeOnPool(mainPool(), a);

    }

    /**

     * join of a forked task returns when task completes

     */

    public void testForkJoin() {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() {

                FibAction f = new FibAction(8);

                assertSame(f, f.fork());

                assertNull(f.join());

                assertEquals(21, f.result);

                checkCompletedNormally(f);

            }};

        testInvokeOnPool(mainPool(), a);

    }

    /**

     * join/quietlyJoin of a forked task succeeds in the presence of interrupts

     */

    public void testJoinIgnoresInterrupts() {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() {

                FibAction f = new FibAction(8);

                final Thread currentThread = Thread.currentThread();

                // test join()

                assertSame(f, f.fork());

                currentThread.interrupt();

                assertNull(f.join());

                Thread.interrupted();

                assertEquals(21, f.result);

                checkCompletedNormally(f);

                f = new FibAction(8);

                f.cancel(true);

                assertSame(f, f.fork());

                currentThread.interrupt();

                try {

                    f.join();

                    shouldThrow();

                } catch (CancellationException success) {

                    Thread.interrupted();

                    checkCancelled(f);

                }

                f = new FibAction(8);

                f.completeExceptionally(new FJException());

                assertSame(f, f.fork());

                currentThread.interrupt();

                try {

                    f.join();

                    shouldThrow();

                } catch (FJException success) {

                    Thread.interrupted();

                    checkCompletedAbnormally(f, success);

                }

                // test quietlyJoin()

                f = new FibAction(8);

                assertSame(f, f.fork());

                currentThread.interrupt();

                f.quietlyJoin();

                Thread.interrupted();

                assertEquals(21, f.result);

                checkCompletedNormally(f);

                f = new FibAction(8);

                f.cancel(true);

                assertSame(f, f.fork());

                currentThread.interrupt();

                f.quietlyJoin();

                Thread.interrupted();

                checkCancelled(f);

                f = new FibAction(8);

                f.completeExceptionally(new FJException());

                assertSame(f, f.fork());

                currentThread.interrupt();

                f.quietlyJoin();

                Thread.interrupted();

                checkCompletedAbnormally(f, f.getException());

            }};

        testInvokeOnPool(mainPool(), a);

        a.reinitialize();

        testInvokeOnPool(singletonPool(), a);

    }

    /**

     * join/quietlyJoin of a forked task when not in ForkJoinPool

     * succeeds in the presence of interrupts

     */

    public void testJoinIgnoresInterruptsOutsideForkJoinPool() {

        final SynchronousQueue<FibAction[]> sq =

            new SynchronousQueue<FibAction[]>();

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() throws InterruptedException {

                FibAction[] fibActions = new FibAction[6];

                for (int i = 0; i < fibActions.length; i++)

                    fibActions[i] = new FibAction(8);

                fibActions[1].cancel(false);

                fibActions[2].completeExceptionally(new FJException());

                fibActions[4].cancel(true);

                fibActions[5].completeExceptionally(new FJException());

                for (int i = 0; i < fibActions.length; i++)

                    fibActions[i].fork();

                sq.put(fibActions);

                helpQuiesce();

            }};

        Runnable r = new CheckedRunnable() {

            public void realRun() throws InterruptedException {

                FibAction[] fibActions = sq.take();

                FibAction f;

                final Thread currentThread = Thread.currentThread();

                // test join() ------------

                f = fibActions[0];

                assertFalse(ForkJoinTask.inForkJoinPool());

                currentThread.interrupt();

                assertNull(f.join());

                assertTrue(Thread.interrupted());

                assertEquals(21, f.result);

                checkCompletedNormally(f);

                f = fibActions[1];

                currentThread.interrupt();

                try {

                    f.join();

                    shouldThrow();

                } catch (CancellationException success) {

                    assertTrue(Thread.interrupted());

                    checkCancelled(f);

                }

                f = fibActions[2];

                currentThread.interrupt();

                try {

                    f.join();

                    shouldThrow();

                } catch (FJException success) {

                    assertTrue(Thread.interrupted());

                    checkCompletedAbnormally(f, success);

                }

                // test quietlyJoin() ---------

                f = fibActions[3];

                currentThread.interrupt();

                f.quietlyJoin();

                assertTrue(Thread.interrupted());

                assertEquals(21, f.result);

                checkCompletedNormally(f);

                f = fibActions[4];

                currentThread.interrupt();

                f.quietlyJoin();

                assertTrue(Thread.interrupted());

                checkCancelled(f);

                f = fibActions[5];

                currentThread.interrupt();

                f.quietlyJoin();

                assertTrue(Thread.interrupted());

                assertTrue(f.getException() instanceof FJException);

                checkCompletedAbnormally(f, f.getException());

            }};

        Thread t;

        t = newStartedThread(r);

        testInvokeOnPool(mainPool(), a);

        awaitTermination(t);

        a.reinitialize();

        t = newStartedThread(r);

        testInvokeOnPool(singletonPool(), a);

        awaitTermination(t);

    }

    /**

     * get of a forked task returns when task completes

     */

    public void testForkGet() {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() throws Exception {

                FibAction f = new FibAction(8);

                assertSame(f, f.fork());

                assertNull(f.get());

                assertEquals(21, f.result);

                checkCompletedNormally(f);

            }};

        testInvokeOnPool(mainPool(), a);

    }

    /**

     * timed get of a forked task returns when task completes

     */

    public void testForkTimedGet() {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() throws Exception {

                FibAction f = new FibAction(8);

                assertSame(f, f.fork());

                assertNull(f.get(LONG_DELAY_MS, MILLISECONDS));

                assertEquals(21, f.result);

                checkCompletedNormally(f);

            }};

        testInvokeOnPool(mainPool(), a);

    }

    /**

     * timed get with null time unit throws NPE

     */

    public void testForkTimedGetNPE() {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() throws Exception {

                FibAction f = new FibAction(8);

                assertSame(f, f.fork());

                try {

                    f.get(randomTimeout(), null);

                    shouldThrow();

                } catch (NullPointerException success) {}

            }};

        testInvokeOnPool(mainPool(), a);

    }

    /**

     * quietlyJoin of a forked task returns when task completes

     */

    public void testForkQuietlyJoin() {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() {

                FibAction f = new FibAction(8);

                assertSame(f, f.fork());

                f.quietlyJoin();

                assertEquals(21, f.result);

                checkCompletedNormally(f);

            }};

        testInvokeOnPool(mainPool(), a);

    }

    /**

     * helpQuiesce returns when tasks are complete.

     * getQueuedTaskCount returns 0 when quiescent

     */

    public void testForkHelpQuiesce() {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() {

                FibAction f = new FibAction(8);

                assertSame(f, f.fork());

                helpQuiesce();

                while (!f.isDone()) // wait out race

                    ;

                assertEquals(21, f.result);

                assertEquals(0, getQueuedTaskCount());

                checkCompletedNormally(f);

            }};

        testInvokeOnPool(mainPool(), a);