/*

 * 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.Callable;

import java.util.concurrent.CancellationException;

import java.util.concurrent.ExecutionException;

import java.util.concurrent.ForkJoinPool;

import java.util.concurrent.ForkJoinTask;

import java.util.concurrent.RecursiveAction;

import java.util.concurrent.TimeoutException;

import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;

import junit.framework.Test;

import junit.framework.TestSuite;

public class ForkJoinTaskTest extends JSR166TestCase {

    public static void main(String[] args) {

        main(suite(), args);

    }

    public static Test suite() {

        return new TestSuite(ForkJoinTaskTest.class);

    }

    // Runs with "mainPool" use > 1 thread. singletonPool tests use 1

    static final int mainPoolSize =

        Math.max(2, Runtime.getRuntime().availableProcessors());

    private static ForkJoinPool mainPool() {

        return new ForkJoinPool(mainPoolSize);

    }

    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)) {

            assertFalse(a.isDone());

            assertFalse(a.isCompletedNormally());

            assertFalse(a.isCompletedAbnormally());

            assertFalse(a.isCancelled());

            assertNull(a.getException());

            assertNull(a.getRawResult());

            assertNull(pool.invoke(a));

            assertTrue(a.isDone());

            assertTrue(a.isCompletedNormally());

            assertFalse(a.isCompletedAbnormally());

            assertFalse(a.isCancelled());

            assertNull(a.getException());

            assertNull(a.getRawResult());

        }

    }

    void checkNotDone(ForkJoinTask a) {

        assertFalse(a.isDone());

        assertFalse(a.isCompletedNormally());

        assertFalse(a.isCompletedAbnormally());

        assertFalse(a.isCancelled());

        assertNull(a.getException());

        assertNull(a.getRawResult());

        try {

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

            shouldThrow();

        } catch (TimeoutException success) {

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

    }

    <T> void checkCompletedNormally(ForkJoinTask<T> a) {

        checkCompletedNormally(a, null);

    }

    <T> void checkCompletedNormally(ForkJoinTask<T> a, T expectedValue) {

        assertTrue(a.isDone());

        assertFalse(a.isCancelled());

        assertTrue(a.isCompletedNormally());

        assertFalse(a.isCompletedAbnormally());

        assertNull(a.getException());

        assertSame(expectedValue, a.getRawResult());

        {

            Thread.currentThread().interrupt();

            long startTime = System.nanoTime();

            assertSame(expectedValue, a.join());

            assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);

            Thread.interrupted();

        }

        {

            Thread.currentThread().interrupt();

            long startTime = System.nanoTime();

            a.quietlyJoin();        // should be no-op

            assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);

            Thread.interrupted();

        }

        assertFalse(a.cancel(false));

        assertFalse(a.cancel(true));

        T v1 = null, v2 = null;

        try {

            v1 = a.get();

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

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

        assertSame(expectedValue, v1);

        assertSame(expectedValue, v2);

    }

    void checkCancelled(ForkJoinTask a) {

        assertTrue(a.isDone());

        assertTrue(a.isCancelled());

        assertFalse(a.isCompletedNormally());

        assertTrue(a.isCompletedAbnormally());

        assertTrue(a.getException() instanceof CancellationException);

        assertNull(a.getRawResult());

        assertTrue(a.cancel(false));

        assertTrue(a.cancel(true));

        try {

            Thread.currentThread().interrupt();

            a.join();

            shouldThrow();

        } catch (CancellationException success) {

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

        Thread.interrupted();

        {

            long startTime = System.nanoTime();

            a.quietlyJoin();        // should be no-op

            assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);

        }

        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(ForkJoinTask 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 {

            Thread.currentThread().interrupt();

            a.join();

            shouldThrow();

        } catch (Throwable expected) {

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

        }

        Thread.interrupted();

        {

            long startTime = System.nanoTime();

            a.quietlyJoin();        // should be no-op

            assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);

        }

        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); }

    }

    /*

     * Testing coverage notes:

     *

     * To test extension methods and overrides, most tests use

     * BinaryAsyncAction extension class that processes joins

     * differently than supplied Recursive forms.

     */

    public static final class FJException extends RuntimeException {

        FJException() { super(); }

    }

    abstract static class BinaryAsyncAction extends ForkJoinTask<Void> {

        private volatile int controlState;

        static final AtomicIntegerFieldUpdater<BinaryAsyncAction> controlStateUpdater =

            AtomicIntegerFieldUpdater.newUpdater(BinaryAsyncAction.class,

                                                 "controlState");

        private volatile BinaryAsyncAction parent;

        private volatile BinaryAsyncAction sibling;

        protected BinaryAsyncAction() {

        }

        public final Void getRawResult() { return null; }

        protected final void setRawResult(Void mustBeNull) { }

        public final void linkSubtasks(BinaryAsyncAction x, BinaryAsyncAction y) {

            x.parent = y.parent = this;

            x.sibling = y;

            y.sibling = x;

        }

        protected void onComplete(BinaryAsyncAction x, BinaryAsyncAction y) {

        }

        protected boolean onException() {

            return true;

        }

        public void linkAndForkSubtasks(BinaryAsyncAction x, BinaryAsyncAction y) {

            linkSubtasks(x, y);

            y.fork();

            x.fork();

        }

        private void completeThis() {

            super.complete(null);

        }

        private void completeThisExceptionally(Throwable ex) {

            super.completeExceptionally(ex);

        }

        public boolean cancel(boolean mayInterruptIfRunning) {

            if (super.cancel(mayInterruptIfRunning)) {

                completeExceptionally(new FJException());

                return true;

            }

            return false;

        }

        public final void complete() {

            BinaryAsyncAction a = this;

            for (;;) {

                BinaryAsyncAction s = a.sibling;

                BinaryAsyncAction p = a.parent;

                a.sibling = null;

                a.parent = null;

                a.completeThis();

                if (p == null || p.compareAndSetControlState(0, 1))

                    break;

                try {

                    p.onComplete(a, s);

                } catch (Throwable rex) {

                    p.completeExceptionally(rex);

                    return;

                }

                a = p;

            }

        }

        public final void completeExceptionally(Throwable ex) {

            for (BinaryAsyncAction a = this;;) {

                a.completeThisExceptionally(ex);

                BinaryAsyncAction s = a.sibling;

                if (s != null && !s.isDone())

                    s.completeExceptionally(ex);

                if ((a = a.parent) == null)

                    break;

            }

        }

        public final BinaryAsyncAction getParent() {

            return parent;

        }

        public BinaryAsyncAction getSibling() {

            return sibling;

        }

        public void reinitialize() {

            parent = sibling = null;

            super.reinitialize();

        }

        protected final int getControlState() {

            return controlState;

        }

        protected final boolean compareAndSetControlState(int expect,

                                                          int update) {

            return controlStateUpdater.compareAndSet(this, expect, update);

        }

        protected final void setControlState(int value) {

            controlState = value;

        }

        protected final void incrementControlState() {

            controlStateUpdater.incrementAndGet(this);

        }

        protected final void decrementControlState() {

            controlStateUpdater.decrementAndGet(this);

        }

    }

    static final class AsyncFib extends BinaryAsyncAction {

        int number;

        public AsyncFib(int n) {

            this.number = n;

        }

        public final boolean exec() {

            AsyncFib f = this;

            int n = f.number;

            while (n > 1) {

                AsyncFib p = f;

                AsyncFib r = new AsyncFib(n - 2);

                f = new AsyncFib(--n);

                p.linkSubtasks(r, f);

                r.fork();

            }

            f.complete();

            return false;

        }

        protected void onComplete(BinaryAsyncAction x, BinaryAsyncAction y) {

            number = ((AsyncFib)x).number + ((AsyncFib)y).number;

        }

    }

    static final class FailingAsyncFib extends BinaryAsyncAction {

        int number;

        public FailingAsyncFib(int n) {

            this.number = n;

        }

        public final boolean exec() {

            FailingAsyncFib f = this;

            int n = f.number;

            while (n > 1) {

                FailingAsyncFib p = f;

                FailingAsyncFib r = new FailingAsyncFib(n - 2);

                f = new FailingAsyncFib(--n);

                p.linkSubtasks(r, f);

                r.fork();

            }

            f.complete();

            return false;

        }

        protected void onComplete(BinaryAsyncAction x, BinaryAsyncAction y) {

            completeExceptionally(new FJException());

        }

    }

    /**

     * invoke returns when task completes normally.

     * isCompletedAbnormally and isCancelled return false for normally

     * completed tasks; getRawResult returns null.

     */

    public void testInvoke() {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() {

                AsyncFib f = new AsyncFib(8);

                assertNull(f.invoke());

                assertEquals(21, f.number);

                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() {

                AsyncFib f = new AsyncFib(8);

                f.quietlyInvoke();

                assertEquals(21, f.number);

                checkCompletedNormally(f);

            }};

        testInvokeOnPool(mainPool(), a);

    }

    /**

     * join of a forked task returns when task completes

     */

    public void testForkJoin() {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() {

                AsyncFib f = new AsyncFib(8);

                assertSame(f, f.fork());

                assertNull(f.join());

                assertEquals(21, f.number);

                checkCompletedNormally(f);

            }};

        testInvokeOnPool(mainPool(), a);

    }

    /**

     * get of a forked task returns when task completes

     */

    public void testForkGet() {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() throws Exception {

                AsyncFib f = new AsyncFib(8);

                assertSame(f, f.fork());

                assertNull(f.get());

                assertEquals(21, f.number);

                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 {

                AsyncFib f = new AsyncFib(8);

                assertSame(f, f.fork());

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

                assertEquals(21, f.number);

                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 {

                AsyncFib f = new AsyncFib(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() {

                AsyncFib f = new AsyncFib(8);

                assertSame(f, f.fork());

                f.quietlyJoin();

                assertEquals(21, f.number);

                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() {

                AsyncFib f = new AsyncFib(8);