/*

 * 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.concurrent.CountDownLatch;

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.TimeoutException;

import junit.framework.Test;

import junit.framework.TestSuite;

public class ForkJoinTask8Test extends JSR166TestCase {

    /*

     * Testing notes: This differs from ForkJoinTaskTest mainly by

     * defining a version of BinaryAsyncAction that uses JDK8 task

     * tags for control state, thereby testing getForkJoinTaskTag,

     * setForkJoinTaskTag, and compareAndSetForkJoinTaskTag across

     * various contexts. Most of the test methods using it are

     * otherwise identical, but omitting retest of those dealing with

     * cancellation, which is not represented in this tag scheme.

     */

    static final short INITIAL_STATE = -1;

    static final short COMPLETE_STATE = 0;

    static final short EXCEPTION_STATE = 1;

    public static void main(String[] args) {

        main(suite(), args);

    }

    public static Test suite() {

        return new TestSuite(ForkJoinTask8Test.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);

    }

    // Compute fib naively and efficiently

    final int[] fib;

    {

        int[] fib = new int[10];

        fib[0] = 0;

        fib[1] = 1;

        for (int i = 2; i < fib.length; i++)

            fib[i] = fib[i - 1] + fib[i - 2];

        this.fib = fib;

    }

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

        if (a instanceof BinaryAsyncAction)

            assertEquals(INITIAL_STATE,

                         ((BinaryAsyncAction)a).getForkJoinTaskTag());

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

        if (a instanceof BinaryAsyncAction)

            assertEquals(COMPLETE_STATE,

                         ((BinaryAsyncAction)a).getForkJoinTaskTag());

        {

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

        if (a instanceof BinaryAsyncAction)

            assertTrue(((BinaryAsyncAction)a).getForkJoinTaskTag() != INITIAL_STATE);

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

    }

    public static final class FJException extends RuntimeException {

        FJException() { super(); }

    }

    abstract static class BinaryAsyncAction extends ForkJoinTask<Void> {

        private volatile BinaryAsyncAction parent;

        private volatile BinaryAsyncAction sibling;

        protected BinaryAsyncAction() {

            setForkJoinTaskTag(INITIAL_STATE);

        }

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

            if (this.getForkJoinTaskTag() != COMPLETE_STATE ||

                x.getForkJoinTaskTag() != COMPLETE_STATE ||

                y.getForkJoinTaskTag() != COMPLETE_STATE) {

                completeThisExceptionally(new FJException());

            }

        }

        protected boolean onException() {

            return true;

        }

        public void linkAndForkSubtasks(BinaryAsyncAction x, BinaryAsyncAction y) {

            linkSubtasks(x, y);

            y.fork();

            x.fork();

        }

        private void completeThis() {

            setForkJoinTaskTag(COMPLETE_STATE);

            super.complete(null);

        }

        private void completeThisExceptionally(Throwable ex) {

            setForkJoinTaskTag(EXCEPTION_STATE);

            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.compareAndSetForkJoinTaskTag(INITIAL_STATE, COMPLETE_STATE))

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

        }

    }

    final class AsyncFib extends BinaryAsyncAction {

        int number;

        int expectedResult;

        public AsyncFib(int number) {

            this.number = number;

            this.expectedResult = fib[number];

        }

        public final boolean exec() {

            try {

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

            }

            catch (Throwable ex) {

                compareAndSetForkJoinTaskTag(INITIAL_STATE, EXCEPTION_STATE);

            }

            if (getForkJoinTaskTag() == EXCEPTION_STATE)

                throw new FJException();

            return false;

        }

        protected void onComplete(BinaryAsyncAction x, BinaryAsyncAction y) {

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

            super.onComplete(x, y);

        }

        public void checkCompletedNormally() {

            assertEquals(expectedResult, number);

            ForkJoinTask8Test.this.checkCompletedNormally(this);

        }

    }

    static final class FailingAsyncFib extends BinaryAsyncAction {

        int number;

        public FailingAsyncFib(int n) {

            this.number = n;

        }

        public final boolean exec() {

            try {

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

            }

            catch (Throwable ex) {

                compareAndSetForkJoinTaskTag(INITIAL_STATE, EXCEPTION_STATE);

            }

            if (getForkJoinTaskTag() == EXCEPTION_STATE)

                throw new FJException();

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

        testInvoke(mainPool());

    }

    public void testInvoke_Singleton() {

        testInvoke(singletonPool());

    }

    public void testInvoke(ForkJoinPool pool) {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() {

                AsyncFib f = new AsyncFib(8);

                assertNull(f.invoke());

                f.checkCompletedNormally();

            }};

        testInvokeOnPool(pool, a);

    }

    /**

     * quietlyInvoke task returns when task completes normally.

     * isCompletedAbnormally and isCancelled return false for normally

     * completed tasks

     */

    public void testQuietlyInvoke() {

        testQuietlyInvoke(mainPool());

    }

    public void testQuietlyInvoke_Singleton() {

        testQuietlyInvoke(singletonPool());

    }

    public void testQuietlyInvoke(ForkJoinPool pool) {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() {

                AsyncFib f = new AsyncFib(8);

                f.quietlyInvoke();

                f.checkCompletedNormally();

            }};

        testInvokeOnPool(pool, a);

    }

    /**

     * join of a forked task returns when task completes

     */

    public void testForkJoin() {

        testForkJoin(mainPool());

    }

    public void testForkJoin_Singleton() {

        testForkJoin(singletonPool());

    }

    public void testForkJoin(ForkJoinPool pool) {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() {

                AsyncFib f = new AsyncFib(8);

                assertSame(f, f.fork());

                assertNull(f.join());

                f.checkCompletedNormally();

            }};

        testInvokeOnPool(pool, a);

    }

    /**

     * get of a forked task returns when task completes

     */

    public void testForkGet() {

        testForkGet(mainPool());

    }

    public void testForkGet_Singleton() {

        testForkGet(singletonPool());

    }

    public void testForkGet(ForkJoinPool pool) {

        RecursiveAction a = new CheckedRecursiveAction() {

            protected void realCompute() throws Exception {

                AsyncFib f = new AsyncFib(8);

                assertSame(f, f.fork());

                assertNull(f.get());

                f.checkCompletedNormally();

            }};

        testInvokeOnPool(pool, a);

    }

    /**

     * timed get of a forked task returns when task completes

     */

    public void testForkTimedGet() {

        testForkTimedGet(mainPool());

    }

    public void testForkTimedGet_Singleton() {

        testForkTimedGet(singletonPool());

    }

    public void testForkTimedGet(ForkJoinPool pool) {

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

                f.checkCompletedNormally();

            }};

        testInvokeOnPool(pool, a);

    }

    /**

     * timed get with null time unit throws NullPointerException

     */

    public void testForkTimedGetNullTimeUnit() {

        testForkTimedGetNullTimeUnit(mainPool());

    }

    public void testForkTimedGetNullTimeUnit_Singleton() {

        testForkTimedGet(singletonPool());

    }

    public void testForkTimedGetNullTimeUnit(ForkJoinPool pool) {

        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(pool, a);

    }

    /**