1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.  Oracle designates this
   7  * particular file as subject to the "Classpath" exception as provided
   8  * by Oracle in the LICENSE file that accompanied this code.
   9  *
  10  * This code is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * version 2 for more details (a copy is included in the LICENSE file that
  14  * accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License version
  17  * 2 along with this work; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  19  *
  20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  21  * or visit www.oracle.com if you need additional information or have any
  22  * questions.
  23  */
  24 
  25 /*
  26  * This file is available under and governed by the GNU General Public
  27  * License version 2 only, as published by the Free Software Foundation.
  28  * However, the following notice accompanied the original version of this
  29  * file:
  30  *
  31  * Written by Doug Lea with assistance from members of JCP JSR-166
  32  * Expert Group and released to the public domain, as explained at
  33  * http://creativecommons.org/publicdomain/zero/1.0/
  34  */
  35 
  36 package java.util.concurrent;
  37 
  38 import java.io.Serializable;
  39 import java.lang.invoke.MethodHandles;
  40 import java.lang.invoke.VarHandle;
  41 import java.lang.reflect.Constructor;
  42 import java.util.Collection;
  43 import java.util.List;
  44 import java.util.RandomAccess;
  45 import java.util.concurrent.locks.LockSupport;
  46 
  47 /**
  48  * Abstract base class for tasks that run within a {@link ForkJoinPool}.
  49  * A {@code ForkJoinTask} is a thread-like entity that is much
  50  * lighter weight than a normal thread.  Huge numbers of tasks and
  51  * subtasks may be hosted by a small number of actual threads in a
  52  * ForkJoinPool, at the price of some usage limitations.
  53  *
  54  * <p>A "main" {@code ForkJoinTask} begins execution when it is
  55  * explicitly submitted to a {@link ForkJoinPool}, or, if not already
  56  * engaged in a ForkJoin computation, commenced in the {@link
  57  * ForkJoinPool#commonPool()} via {@link #fork}, {@link #invoke}, or
  58  * related methods.  Once started, it will usually in turn start other
  59  * subtasks.  As indicated by the name of this class, many programs
  60  * using {@code ForkJoinTask} employ only methods {@link #fork} and
  61  * {@link #join}, or derivatives such as {@link
  62  * #invokeAll(ForkJoinTask...) invokeAll}.  However, this class also
  63  * provides a number of other methods that can come into play in
  64  * advanced usages, as well as extension mechanics that allow support
  65  * of new forms of fork/join processing.
  66  *
  67  * <p>A {@code ForkJoinTask} is a lightweight form of {@link Future}.
  68  * The efficiency of {@code ForkJoinTask}s stems from a set of
  69  * restrictions (that are only partially statically enforceable)
  70  * reflecting their main use as computational tasks calculating pure
  71  * functions or operating on purely isolated objects.  The primary
  72  * coordination mechanisms are {@link #fork}, that arranges
  73  * asynchronous execution, and {@link #join}, that doesn't proceed
  74  * until the task's result has been computed.  Computations should
  75  * ideally avoid {@code synchronized} methods or blocks, and should
  76  * minimize other blocking synchronization apart from joining other
  77  * tasks or using synchronizers such as Phasers that are advertised to
  78  * cooperate with fork/join scheduling. Subdividable tasks should also
  79  * not perform blocking I/O, and should ideally access variables that
  80  * are completely independent of those accessed by other running
  81  * tasks. These guidelines are loosely enforced by not permitting
  82  * checked exceptions such as {@code IOExceptions} to be
  83  * thrown. However, computations may still encounter unchecked
  84  * exceptions, that are rethrown to callers attempting to join
  85  * them. These exceptions may additionally include {@link
  86  * RejectedExecutionException} stemming from internal resource
  87  * exhaustion, such as failure to allocate internal task
  88  * queues. Rethrown exceptions behave in the same way as regular
  89  * exceptions, but, when possible, contain stack traces (as displayed
  90  * for example using {@code ex.printStackTrace()}) of both the thread
  91  * that initiated the computation as well as the thread actually
  92  * encountering the exception; minimally only the latter.
  93  *
  94  * <p>It is possible to define and use ForkJoinTasks that may block,
  95  * but doing so requires three further considerations: (1) Completion
  96  * of few if any <em>other</em> tasks should be dependent on a task
  97  * that blocks on external synchronization or I/O. Event-style async
  98  * tasks that are never joined (for example, those subclassing {@link
  99  * CountedCompleter}) often fall into this category.  (2) To minimize
 100  * resource impact, tasks should be small; ideally performing only the
 101  * (possibly) blocking action. (3) Unless the {@link
 102  * ForkJoinPool.ManagedBlocker} API is used, or the number of possibly
 103  * blocked tasks is known to be less than the pool's {@link
 104  * ForkJoinPool#getParallelism} level, the pool cannot guarantee that
 105  * enough threads will be available to ensure progress or good
 106  * performance.
 107  *
 108  * <p>The primary method for awaiting completion and extracting
 109  * results of a task is {@link #join}, but there are several variants:
 110  * The {@link Future#get} methods support interruptible and/or timed
 111  * waits for completion and report results using {@code Future}
 112  * conventions. Method {@link #invoke} is semantically
 113  * equivalent to {@code fork(); join()} but always attempts to begin
 114  * execution in the current thread. The "<em>quiet</em>" forms of
 115  * these methods do not extract results or report exceptions. These
 116  * may be useful when a set of tasks are being executed, and you need
 117  * to delay processing of results or exceptions until all complete.
 118  * Method {@code invokeAll} (available in multiple versions)
 119  * performs the most common form of parallel invocation: forking a set
 120  * of tasks and joining them all.
 121  *
 122  * <p>In the most typical usages, a fork-join pair act like a call
 123  * (fork) and return (join) from a parallel recursive function. As is
 124  * the case with other forms of recursive calls, returns (joins)
 125  * should be performed innermost-first. For example, {@code a.fork();
 126  * b.fork(); b.join(); a.join();} is likely to be substantially more
 127  * efficient than joining {@code a} before {@code b}.
 128  *
 129  * <p>The execution status of tasks may be queried at several levels
 130  * of detail: {@link #isDone} is true if a task completed in any way
 131  * (including the case where a task was cancelled without executing);
 132  * {@link #isCompletedNormally} is true if a task completed without
 133  * cancellation or encountering an exception; {@link #isCancelled} is
 134  * true if the task was cancelled (in which case {@link #getException}
 135  * returns a {@link CancellationException}); and
 136  * {@link #isCompletedAbnormally} is true if a task was either
 137  * cancelled or encountered an exception, in which case {@link
 138  * #getException} will return either the encountered exception or
 139  * {@link CancellationException}.
 140  *
 141  * <p>The ForkJoinTask class is not usually directly subclassed.
 142  * Instead, you subclass one of the abstract classes that support a
 143  * particular style of fork/join processing, typically {@link
 144  * RecursiveAction} for most computations that do not return results,
 145  * {@link RecursiveTask} for those that do, and {@link
 146  * CountedCompleter} for those in which completed actions trigger
 147  * other actions.  Normally, a concrete ForkJoinTask subclass declares
 148  * fields comprising its parameters, established in a constructor, and
 149  * then defines a {@code compute} method that somehow uses the control
 150  * methods supplied by this base class.
 151  *
 152  * <p>Method {@link #join} and its variants are appropriate for use
 153  * only when completion dependencies are acyclic; that is, the
 154  * parallel computation can be described as a directed acyclic graph
 155  * (DAG). Otherwise, executions may encounter a form of deadlock as
 156  * tasks cyclically wait for each other.  However, this framework
 157  * supports other methods and techniques (for example the use of
 158  * {@link Phaser}, {@link #helpQuiesce}, and {@link #complete}) that
 159  * may be of use in constructing custom subclasses for problems that
 160  * are not statically structured as DAGs. To support such usages, a
 161  * ForkJoinTask may be atomically <em>tagged</em> with a {@code short}
 162  * value using {@link #setForkJoinTaskTag} or {@link
 163  * #compareAndSetForkJoinTaskTag} and checked using {@link
 164  * #getForkJoinTaskTag}. The ForkJoinTask implementation does not use
 165  * these {@code protected} methods or tags for any purpose, but they
 166  * may be of use in the construction of specialized subclasses.  For
 167  * example, parallel graph traversals can use the supplied methods to
 168  * avoid revisiting nodes/tasks that have already been processed.
 169  * (Method names for tagging are bulky in part to encourage definition
 170  * of methods that reflect their usage patterns.)
 171  *
 172  * <p>Most base support methods are {@code final}, to prevent
 173  * overriding of implementations that are intrinsically tied to the
 174  * underlying lightweight task scheduling framework.  Developers
 175  * creating new basic styles of fork/join processing should minimally
 176  * implement {@code protected} methods {@link #exec}, {@link
 177  * #setRawResult}, and {@link #getRawResult}, while also introducing
 178  * an abstract computational method that can be implemented in its
 179  * subclasses, possibly relying on other {@code protected} methods
 180  * provided by this class.
 181  *
 182  * <p>ForkJoinTasks should perform relatively small amounts of
 183  * computation. Large tasks should be split into smaller subtasks,
 184  * usually via recursive decomposition. As a very rough rule of thumb,
 185  * a task should perform more than 100 and less than 10000 basic
 186  * computational steps, and should avoid indefinite looping. If tasks
 187  * are too big, then parallelism cannot improve throughput. If too
 188  * small, then memory and internal task maintenance overhead may
 189  * overwhelm processing.
 190  *
 191  * <p>This class provides {@code adapt} methods for {@link Runnable}
 192  * and {@link Callable}, that may be of use when mixing execution of
 193  * {@code ForkJoinTasks} with other kinds of tasks. When all tasks are
 194  * of this form, consider using a pool constructed in <em>asyncMode</em>.
 195  *
 196  * <p>ForkJoinTasks are {@code Serializable}, which enables them to be
 197  * used in extensions such as remote execution frameworks. It is
 198  * sensible to serialize tasks only before or after, but not during,
 199  * execution. Serialization is not relied on during execution itself.
 200  *
 201  * @since 1.7
 202  * @author Doug Lea
 203  */
 204 public abstract class ForkJoinTask<V> implements Future<V>, Serializable {
 205 
 206     /*
 207      * See the internal documentation of class ForkJoinPool for a
 208      * general implementation overview.  ForkJoinTasks are mainly
 209      * responsible for maintaining their "status" field amidst relays
 210      * to methods in ForkJoinWorkerThread and ForkJoinPool.
 211      *
 212      * The methods of this class are more-or-less layered into
 213      * (1) basic status maintenance
 214      * (2) execution and awaiting completion
 215      * (3) user-level methods that additionally report results.
 216      * This is sometimes hard to see because this file orders exported
 217      * methods in a way that flows well in javadocs.
 218      *
 219      * Revision notes: The use of "Aux" field replaces previous
 220      * reliance on a table to hold exceptions and synchronized blocks
 221      * and monitors to wait for completion.
 222      */
 223 
 224     /**
 225      * Nodes for threads waiting for completion, or holding a thrown
 226      * exception (never both). Waiting threads prepend nodes
 227      * Treiber-stack-style.  Signallers detach and unpark
 228      * waiters. Cancelled waiters try to unsplice.
 229      */
 230     static final class Aux {
 231         final Thread thread;
 232         final Throwable ex;  // null if a waiter
 233         Aux next;            // accessed only via memory-acquire chains
 234         Aux(Thread thread, Throwable ex) {
 235             this.thread = thread;
 236             this.ex = ex;
 237         }
 238         final boolean casNext(Aux c, Aux v) { // used only in cancellation
 239             return NEXT.compareAndSet(this, c, v);
 240         }
 241         private static final VarHandle NEXT;
 242         static {
 243             try {
 244                 NEXT = MethodHandles.lookup()
 245                     .findVarHandle(Aux.class, "next", Aux.class);
 246             } catch (ReflectiveOperationException e) {
 247                 throw new ExceptionInInitializerError(e);
 248             }
 249         }
 250     }
 251 
 252     /*
 253      * The status field holds bits packed into a single int to ensure
 254      * atomicity.  Status is initially zero, and takes on nonnegative
 255      * values until completed, upon which it holds (sign bit) DONE,
 256      * possibly with ABNORMAL (cancelled or exceptional) and THROWN
 257      * (in which case an exception has been stored). A value of
 258      * ABNORMAL without DONE signifies an interrupted wait.  These
 259      * control bits occupy only (some of) the upper half (16 bits) of
 260      * status field. The lower bits are used for user-defined tags.
 261      */
 262     private static final int DONE         = 1 << 31; // must be negative
 263     private static final int ABNORMAL     = 1 << 16;
 264     private static final int THROWN       = 1 << 17;
 265     private static final int SMASK        = 0xffff;  // short bits for tags
 266     private static final int UNCOMPENSATE = 1 << 16; // helpJoin return sentinel
 267 
 268     // Fields
 269     volatile int status;                // accessed directly by pool and workers
 270     private transient volatile Aux aux; // either waiters or thrown Exception
 271 
 272     // Support for atomic operations
 273     private static final VarHandle STATUS;
 274     private static final VarHandle AUX;
 275     private int getAndBitwiseOrStatus(int v) {
 276         return (int)STATUS.getAndBitwiseOr(this, v);
 277     }
 278     private boolean casStatus(int c, int v) {
 279         return STATUS.compareAndSet(this, c, v);
 280     }
 281     private boolean casAux(Aux c, Aux v) {
 282         return AUX.compareAndSet(this, c, v);
 283     }
 284 
 285     /** Removes and unparks waiters */
 286     private void signalWaiters() {
 287         for (Aux a; (a = aux) != null && a.ex == null; ) {
 288             if (casAux(a, null)) {             // detach entire list
 289                 for (Thread t; a != null; a = a.next) {
 290                     if ((t = a.thread) != Thread.currentThread() && t != null)
 291                         LockSupport.unpark(t); // don't self-signal
 292                 }
 293                 break;
 294             }
 295         }
 296     }
 297 
 298     /**
 299      * Sets DONE status and wakes up threads waiting to join this task.
 300      * @return status on exit
 301      */
 302     private int setDone() {
 303         int s = getAndBitwiseOrStatus(DONE) | DONE;
 304         signalWaiters();
 305         return s;
 306     }
 307 
 308     /**
 309      * Sets ABNORMAL DONE status unless already done, and wakes up threads
 310      * waiting to join this task.
 311      * @return status on exit
 312      */
 313     private int trySetCancelled() {
 314         int s;
 315         do {} while ((s = status) >= 0 && !casStatus(s, s |= (DONE | ABNORMAL)));
 316         signalWaiters();
 317         return s;
 318     }
 319 
 320     /**
 321      * Records exception and sets ABNORMAL THROWN DONE status unless
 322      * already done, and wakes up threads waiting to join this task.
 323      * If losing a race with setDone or trySetCancelled, the exception
 324      * may be recorded but not reported.
 325      *
 326      * @return status on exit
 327      */
 328     final int trySetThrown(Throwable ex) {
 329         Aux h = new Aux(Thread.currentThread(), ex), p = null;
 330         boolean installed = false;
 331         int s;
 332         while ((s = status) >= 0) {
 333             Aux a;
 334             if (!installed && ((a = aux) == null || a.ex == null) &&
 335                 (installed = casAux(a, h)))
 336                 p = a; // list of waiters replaced by h
 337             if (installed && casStatus(s, s |= (DONE | ABNORMAL | THROWN)))
 338                 break;
 339         }
 340         for (; p != null; p = p.next)
 341             LockSupport.unpark(p.thread);
 342         return s;
 343     }
 344 
 345     /**
 346      * Records exception unless already done. Overridable in subclasses.
 347      *
 348      * @return status on exit
 349      */
 350     int trySetException(Throwable ex) {
 351         return trySetThrown(ex);
 352     }
 353 
 354     /**
 355      * Constructor for subclasses to call.
 356      */
 357     public ForkJoinTask() {}
 358 
 359     static boolean isExceptionalStatus(int s) {  // needed by subclasses
 360         return (s & THROWN) != 0;
 361     }
 362 
 363     /**
 364      * Unless done, calls exec and records status if completed, but
 365      * doesn't wait for completion otherwise.
 366      *
 367      * @return status on exit from this method
 368      */
 369     final int doExec() {
 370         int s; boolean completed;
 371         if ((s = status) >= 0) {
 372             try {
 373                 completed = exec();
 374             } catch (Throwable rex) {
 375                 s = trySetException(rex);
 376                 completed = false;
 377             }
 378             if (completed)
 379                 s = setDone();
 380         }
 381         return s;
 382     }
 383 
 384     /**
 385      * Helps and/or waits for completion from join, get, or invoke;
 386      * called from either internal or external threads.
 387      *
 388      * @param pool if nonnull, known submitted pool, else assumes current pool
 389      * @param ran true if task known to have been exec'd
 390      * @param interruptible true if park interruptibly when external
 391      * @param timed true if use timed wait
 392      * @param nanos if timed, timeout value
 393      * @return ABNORMAL if interrupted, else status on exit
 394      */
 395     private int awaitDone(ForkJoinPool pool, boolean ran,
 396                           boolean interruptible, boolean timed,
 397                           long nanos) {
 398         ForkJoinPool p; boolean internal; int s; Thread t;
 399         ForkJoinPool.WorkQueue q = null;
 400         if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) {
 401             ForkJoinWorkerThread wt = (ForkJoinWorkerThread)t;
 402             p = wt.pool;
 403             if (pool == null)
 404                 pool = p;
 405             if (internal = (pool == p))
 406                 q = wt.workQueue;
 407         }
 408         else {
 409             internal = false;
 410             p = ForkJoinPool.common;
 411             if (pool == null)
 412                 pool = p;
 413             if (pool == p && p != null)
 414                 q = p.externalQueue();
 415         }
 416         if (interruptible && Thread.interrupted())
 417             return ABNORMAL;
 418         if ((s = status) < 0)
 419             return s;
 420         long deadline = 0L;
 421         if (timed) {
 422             if (nanos <= 0L)
 423                 return 0;
 424             else if ((deadline = nanos + System.nanoTime()) == 0L)
 425                 deadline = 1L;
 426         }
 427         boolean uncompensate = false;
 428         if (q != null && p != null) {  // try helping
 429             // help even in timed mode if pool has no parallelism
 430             boolean canHelp = !timed || (p.mode & SMASK) == 0;
 431             if (canHelp) {
 432                 if ((this instanceof CountedCompleter) &&
 433                     (s = p.helpComplete(this, q, internal)) < 0)
 434                     return s;
 435                 if (!ran && ((!internal && q.externalTryUnpush(this)) ||
 436                              q.tryRemove(this, internal)) && (s = doExec()) < 0)
 437                     return s;
 438             }
 439             if (internal) {
 440                 if ((s = p.helpJoin(this, q, canHelp)) < 0)
 441                     return s;
 442                 if (s == UNCOMPENSATE)
 443                     uncompensate = true;
 444             }
 445         }
 446         // block until done or cancelled wait
 447         boolean interrupted = false, queued = false;
 448         boolean parked = false, fail = false;
 449         Aux node = null;
 450         while ((s = status) >= 0) {
 451             Aux a; long ns;
 452             if (fail || (fail = (pool != null && pool.mode < 0)))
 453                 casStatus(s, s | (DONE | ABNORMAL)); // try to cancel
 454             else if (parked && Thread.interrupted()) {
 455                 if (interruptible) {
 456                     s = ABNORMAL;
 457                     break;
 458                 }
 459                 interrupted = true;
 460             }
 461             else if (queued) {
 462                 if (deadline != 0L) {
 463                     if ((ns = deadline - System.nanoTime()) <= 0L)
 464                         break;
 465                     LockSupport.parkNanos(ns);
 466                 }
 467                 else
 468                     LockSupport.park();
 469                 parked = true;
 470             }
 471             else if (node != null) {
 472                 if ((a = aux) != null && a.ex != null)
 473                     Thread.onSpinWait();     // exception in progress
 474                 else if (queued = casAux(node.next = a, node))
 475                     LockSupport.setCurrentBlocker(this);
 476             }
 477             else {
 478                 try {
 479                     node = new Aux(Thread.currentThread(), null);
 480                 } catch (Throwable ex) {     // cannot create
 481                     fail = true;
 482                 }
 483             }
 484         }
 485         if (pool != null && uncompensate)
 486             pool.uncompensate();
 487 
 488         if (queued) {
 489             LockSupport.setCurrentBlocker(null);
 490             if (s >= 0) { // cancellation similar to AbstractQueuedSynchronizer
 491                 outer: for (Aux a; (a = aux) != null && a.ex == null; ) {
 492                     for (Aux trail = null;;) {
 493                         Aux next = a.next;
 494                         if (a == node) {
 495                             if (trail != null)
 496                                 trail.casNext(trail, next);
 497                             else if (casAux(a, next))
 498                                 break outer; // cannot be re-encountered
 499                             break;           // restart
 500                         } else {
 501                             trail = a;
 502                             if ((a = next) == null)
 503                                 break outer;
 504                         }
 505                     }
 506                 }
 507             }
 508             else {
 509                 signalWaiters();             // help clean or signal
 510                 if (interrupted)
 511                     Thread.currentThread().interrupt();
 512             }
 513         }
 514         return s;
 515     }
 516 
 517     /**
 518      * Cancels, ignoring any exceptions thrown by cancel.  Cancel is
 519      * spec'ed not to throw any exceptions, but if it does anyway, we
 520      * have no recourse, so guard against this case.
 521      */
 522     static final void cancelIgnoringExceptions(Future<?> t) {
 523         if (t != null) {
 524             try {
 525                 t.cancel(true);
 526             } catch (Throwable ignore) {
 527             }
 528         }
 529     }
 530 
 531     /**
 532      * Returns a rethrowable exception for this task, if available.
 533      * To provide accurate stack traces, if the exception was not
 534      * thrown by the current thread, we try to create a new exception
 535      * of the same type as the one thrown, but with the recorded
 536      * exception as its cause. If there is no such constructor, we
 537      * instead try to use a no-arg constructor, followed by initCause,
 538      * to the same effect. If none of these apply, or any fail due to
 539      * other exceptions, we return the recorded exception, which is
 540      * still correct, although it may contain a misleading stack
 541      * trace.
 542      *
 543      * @return the exception, or null if none
 544      */
 545     private Throwable getThrowableException() {
 546         Throwable ex; Aux a;
 547         if ((a = aux) == null)
 548             ex = null;
 549         else if ((ex = a.ex) != null && a.thread != Thread.currentThread()) {
 550             try {
 551                 Constructor<?> noArgCtor = null, oneArgCtor = null;
 552                 for (Constructor<?> c : ex.getClass().getConstructors()) {
 553                     Class<?>[] ps = c.getParameterTypes();
 554                     if (ps.length == 0)
 555                         noArgCtor = c;
 556                     else if (ps.length == 1 && ps[0] == Throwable.class) {
 557                         oneArgCtor = c;
 558                         break;
 559                     }
 560                 }
 561                 if (oneArgCtor != null)
 562                     ex = (Throwable)oneArgCtor.newInstance(ex);
 563                 else if (noArgCtor != null) {
 564                     Throwable rx = (Throwable)noArgCtor.newInstance();
 565                     rx.initCause(ex);
 566                     ex = rx;
 567                 }
 568             } catch (Exception ignore) {
 569             }
 570         }
 571         return ex;
 572     }
 573 
 574     /**
 575      * Returns exception associated with the given status, or null if none.
 576      */
 577     private Throwable getException(int s) {
 578         Throwable ex = null;
 579         if ((s & ABNORMAL) != 0 &&
 580             ((s & THROWN) == 0 || (ex = getThrowableException()) == null))
 581             ex = new CancellationException();
 582         return ex;
 583     }
 584 
 585     /**
 586      * Throws exception associated with the given status, or
 587      * CancellationException if none recorded.
 588      */
 589     private void reportException(int s) {
 590         ForkJoinTask.<RuntimeException>uncheckedThrow(
 591             (s & THROWN) != 0 ? getThrowableException() : null);
 592     }
 593 
 594     /**
 595      * Throws exception for (timed or untimed) get, wrapping if
 596      * necessary in an ExecutionException.
 597      */
 598     private void reportExecutionException(int s) {
 599         Throwable ex = null;
 600         if (s == ABNORMAL)
 601             ex = new InterruptedException();
 602         else if (s >= 0)
 603             ex = new TimeoutException();
 604         else if ((s & THROWN) != 0 && (ex = getThrowableException()) != null)
 605             ex = new ExecutionException(ex);
 606         ForkJoinTask.<RuntimeException>uncheckedThrow(ex);
 607     }
 608 
 609     /**
 610      * A version of "sneaky throw" to relay exceptions in other
 611      * contexts.
 612      */
 613     static void rethrow(Throwable ex) {
 614         ForkJoinTask.<RuntimeException>uncheckedThrow(ex);
 615     }
 616 
 617     /**
 618      * The sneaky part of sneaky throw, relying on generics
 619      * limitations to evade compiler complaints about rethrowing
 620      * unchecked exceptions. If argument null, throws
 621      * CancellationException.
 622      */
 623     @SuppressWarnings("unchecked") static <T extends Throwable>
 624     void uncheckedThrow(Throwable t) throws T {
 625         if (t == null)
 626             t = new CancellationException();
 627         throw (T)t; // rely on vacuous cast
 628     }
 629 
 630     // public methods
 631 
 632     /**
 633      * Arranges to asynchronously execute this task in the pool the
 634      * current task is running in, if applicable, or using the {@link
 635      * ForkJoinPool#commonPool()} if not {@link #inForkJoinPool}.  While
 636      * it is not necessarily enforced, it is a usage error to fork a
 637      * task more than once unless it has completed and been
 638      * reinitialized.  Subsequent modifications to the state of this
 639      * task or any data it operates on are not necessarily
 640      * consistently observable by any thread other than the one
 641      * executing it unless preceded by a call to {@link #join} or
 642      * related methods, or a call to {@link #isDone} returning {@code
 643      * true}.
 644      *
 645      * @return {@code this}, to simplify usage
 646      */
 647     public final ForkJoinTask<V> fork() {
 648         Thread t; ForkJoinWorkerThread w;
 649         if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread)
 650             (w = (ForkJoinWorkerThread)t).workQueue.push(this, w.pool);
 651         else
 652             ForkJoinPool.common.externalPush(this);
 653         return this;
 654     }
 655 
 656     /**
 657      * Returns the result of the computation when it
 658      * {@linkplain #isDone is done}.
 659      * This method differs from {@link #get()} in that abnormal
 660      * completion results in {@code RuntimeException} or {@code Error},
 661      * not {@code ExecutionException}, and that interrupts of the
 662      * calling thread do <em>not</em> cause the method to abruptly
 663      * return by throwing {@code InterruptedException}.
 664      *
 665      * @return the computed result
 666      */
 667     public final V join() {
 668         int s;
 669         if ((s = status) >= 0)
 670             s = awaitDone(null, false, false, false, 0L);
 671         if ((s & ABNORMAL) != 0)
 672             reportException(s);
 673         return getRawResult();
 674     }
 675 
 676     /**
 677      * Commences performing this task, awaits its completion if
 678      * necessary, and returns its result, or throws an (unchecked)
 679      * {@code RuntimeException} or {@code Error} if the underlying
 680      * computation did so.
 681      *
 682      * @return the computed result
 683      */
 684     public final V invoke() {
 685         int s;
 686         if ((s = doExec()) >= 0)
 687             s = awaitDone(null, true, false, false, 0L);
 688         if ((s & ABNORMAL) != 0)
 689             reportException(s);
 690         return getRawResult();
 691     }
 692 
 693     /**
 694      * Forks the given tasks, returning when {@code isDone} holds for
 695      * each task or an (unchecked) exception is encountered, in which
 696      * case the exception is rethrown. If more than one task
 697      * encounters an exception, then this method throws any one of
 698      * these exceptions. If any task encounters an exception, the
 699      * other may be cancelled. However, the execution status of
 700      * individual tasks is not guaranteed upon exceptional return. The
 701      * status of each task may be obtained using {@link
 702      * #getException()} and related methods to check if they have been
 703      * cancelled, completed normally or exceptionally, or left
 704      * unprocessed.
 705      *
 706      * @param t1 the first task
 707      * @param t2 the second task
 708      * @throws NullPointerException if any task is null
 709      */
 710     public static void invokeAll(ForkJoinTask<?> t1, ForkJoinTask<?> t2) {
 711         int s1, s2;
 712         if (t1 == null || t2 == null)
 713             throw new NullPointerException();
 714         t2.fork();
 715         if ((s1 = t1.doExec()) >= 0)
 716             s1 = t1.awaitDone(null, true, false, false, 0L);
 717         if ((s1 & ABNORMAL) != 0) {
 718             cancelIgnoringExceptions(t2);
 719             t1.reportException(s1);
 720         }
 721         else if (((s2 = t2.awaitDone(null, false, false, false, 0L)) & ABNORMAL) != 0)
 722             t2.reportException(s2);
 723     }
 724 
 725     /**
 726      * Forks the given tasks, returning when {@code isDone} holds for
 727      * each task or an (unchecked) exception is encountered, in which
 728      * case the exception is rethrown. If more than one task
 729      * encounters an exception, then this method throws any one of
 730      * these exceptions. If any task encounters an exception, others
 731      * may be cancelled. However, the execution status of individual
 732      * tasks is not guaranteed upon exceptional return. The status of
 733      * each task may be obtained using {@link #getException()} and
 734      * related methods to check if they have been cancelled, completed
 735      * normally or exceptionally, or left unprocessed.
 736      *
 737      * @param tasks the tasks
 738      * @throws NullPointerException if any task is null
 739      */
 740     public static void invokeAll(ForkJoinTask<?>... tasks) {
 741         Throwable ex = null;
 742         int last = tasks.length - 1;
 743         for (int i = last; i >= 0; --i) {
 744             ForkJoinTask<?> t;
 745             if ((t = tasks[i]) == null) {
 746                 ex = new NullPointerException();
 747                 break;
 748             }
 749             if (i == 0) {
 750                 int s;
 751                 if ((s = t.doExec()) >= 0)
 752                     s = t.awaitDone(null, true, false, false, 0L);
 753                 if ((s & ABNORMAL) != 0)
 754                     ex = t.getException(s);
 755                 break;
 756             }
 757             t.fork();
 758         }
 759         if (ex == null) {
 760             for (int i = 1; i <= last; ++i) {
 761                 ForkJoinTask<?> t;
 762                 if ((t = tasks[i]) != null) {
 763                     int s;
 764                     if ((s = t.status) >= 0)
 765                         s = t.awaitDone(null, false, false, false, 0L);
 766                     if ((s & ABNORMAL) != 0 && (ex = t.getException(s)) != null)
 767                         break;
 768                 }
 769             }
 770         }
 771         if (ex != null) {
 772             for (int i = 1; i <= last; ++i)
 773                 cancelIgnoringExceptions(tasks[i]);
 774             rethrow(ex);
 775         }
 776     }
 777 
 778     /**
 779      * Forks all tasks in the specified collection, returning when
 780      * {@code isDone} holds for each task or an (unchecked) exception
 781      * is encountered, in which case the exception is rethrown. If
 782      * more than one task encounters an exception, then this method
 783      * throws any one of these exceptions. If any task encounters an
 784      * exception, others may be cancelled. However, the execution
 785      * status of individual tasks is not guaranteed upon exceptional
 786      * return. The status of each task may be obtained using {@link
 787      * #getException()} and related methods to check if they have been
 788      * cancelled, completed normally or exceptionally, or left
 789      * unprocessed.
 790      *
 791      * @param tasks the collection of tasks
 792      * @param <T> the type of the values returned from the tasks
 793      * @return the tasks argument, to simplify usage
 794      * @throws NullPointerException if tasks or any element are null
 795      */
 796     public static <T extends ForkJoinTask<?>> Collection<T> invokeAll(Collection<T> tasks) {
 797         if (!(tasks instanceof RandomAccess) || !(tasks instanceof List<?>)) {
 798             invokeAll(tasks.toArray(new ForkJoinTask<?>[0]));
 799             return tasks;
 800         }
 801         @SuppressWarnings("unchecked")
 802         List<? extends ForkJoinTask<?>> ts =
 803             (List<? extends ForkJoinTask<?>>) tasks;
 804         Throwable ex = null;
 805         int last = ts.size() - 1;  // nearly same as array version
 806         for (int i = last; i >= 0; --i) {
 807             ForkJoinTask<?> t;
 808             if ((t = ts.get(i)) == null) {
 809                 ex = new NullPointerException();
 810                 break;
 811             }
 812             if (i == 0) {
 813                 int s;
 814                 if ((s = t.doExec()) >= 0)
 815                     s = t.awaitDone(null, true, false, false, 0L);
 816                 if ((s & ABNORMAL) != 0)
 817                     ex = t.getException(s);
 818                 break;
 819             }
 820             t.fork();
 821         }
 822         if (ex == null) {
 823             for (int i = 1; i <= last; ++i) {
 824                 ForkJoinTask<?> t;
 825                 if ((t = ts.get(i)) != null) {
 826                     int s;
 827                     if ((s = t.status) >= 0)
 828                         s = t.awaitDone(null, false, false, false, 0L);
 829                     if ((s & ABNORMAL) != 0 && (ex = t.getException(s)) != null)
 830                         break;
 831                 }
 832             }
 833         }
 834         if (ex != null) {
 835             for (int i = 1; i <= last; ++i)
 836                 cancelIgnoringExceptions(ts.get(i));
 837             rethrow(ex);
 838         }
 839         return tasks;
 840     }
 841 
 842     /**
 843      * Attempts to cancel execution of this task. This attempt will
 844      * fail if the task has already completed or could not be
 845      * cancelled for some other reason. If successful, and this task
 846      * has not started when {@code cancel} is called, execution of
 847      * this task is suppressed. After this method returns
 848      * successfully, unless there is an intervening call to {@link
 849      * #reinitialize}, subsequent calls to {@link #isCancelled},
 850      * {@link #isDone}, and {@code cancel} will return {@code true}
 851      * and calls to {@link #join} and related methods will result in
 852      * {@code CancellationException}.
 853      *
 854      * <p>This method may be overridden in subclasses, but if so, must
 855      * still ensure that these properties hold. In particular, the
 856      * {@code cancel} method itself must not throw exceptions.
 857      *
 858      * <p>This method is designed to be invoked by <em>other</em>
 859      * tasks. To terminate the current task, you can just return or
 860      * throw an unchecked exception from its computation method, or
 861      * invoke {@link #completeExceptionally(Throwable)}.
 862      *
 863      * @param mayInterruptIfRunning this value has no effect in the
 864      * default implementation because interrupts are not used to
 865      * control cancellation.
 866      *
 867      * @return {@code true} if this task is now cancelled
 868      */
 869     public boolean cancel(boolean mayInterruptIfRunning) {
 870         return (trySetCancelled() & (ABNORMAL | THROWN)) == ABNORMAL;
 871     }
 872 
 873     public final boolean isDone() {
 874         return status < 0;
 875     }
 876 
 877     public final boolean isCancelled() {
 878         return (status & (ABNORMAL | THROWN)) == ABNORMAL;
 879     }
 880 
 881     /**
 882      * Returns {@code true} if this task threw an exception or was cancelled.
 883      *
 884      * @return {@code true} if this task threw an exception or was cancelled
 885      */
 886     public final boolean isCompletedAbnormally() {
 887         return (status & ABNORMAL) != 0;
 888     }
 889 
 890     /**
 891      * Returns {@code true} if this task completed without throwing an
 892      * exception and was not cancelled.
 893      *
 894      * @return {@code true} if this task completed without throwing an
 895      * exception and was not cancelled
 896      */
 897     public final boolean isCompletedNormally() {
 898         return (status & (DONE | ABNORMAL)) == DONE;
 899     }
 900 

































 901     /**
 902      * Returns the exception thrown by the base computation, or a
 903      * {@code CancellationException} if cancelled, or {@code null} if
 904      * none or if the method has not yet completed.
 905      *
 906      * @return the exception, or {@code null} if none
 907      */
 908     public final Throwable getException() {
 909         return getException(status);
 910     }
 911 
 912     /**
 913      * Completes this task abnormally, and if not already aborted or
 914      * cancelled, causes it to throw the given exception upon
 915      * {@code join} and related operations. This method may be used
 916      * to induce exceptions in asynchronous tasks, or to force
 917      * completion of tasks that would not otherwise complete.  Its use
 918      * in other situations is discouraged.  This method is
 919      * overridable, but overridden versions must invoke {@code super}
 920      * implementation to maintain guarantees.
 921      *
 922      * @param ex the exception to throw. If this exception is not a
 923      * {@code RuntimeException} or {@code Error}, the actual exception
 924      * thrown will be a {@code RuntimeException} with cause {@code ex}.
 925      */
 926     public void completeExceptionally(Throwable ex) {
 927         trySetException((ex instanceof RuntimeException) ||
 928                         (ex instanceof Error) ? ex :
 929                         new RuntimeException(ex));
 930     }
 931 
 932     /**
 933      * Completes this task, and if not already aborted or cancelled,
 934      * returning the given value as the result of subsequent
 935      * invocations of {@code join} and related operations. This method
 936      * may be used to provide results for asynchronous tasks, or to
 937      * provide alternative handling for tasks that would not otherwise
 938      * complete normally. Its use in other situations is
 939      * discouraged. This method is overridable, but overridden
 940      * versions must invoke {@code super} implementation to maintain
 941      * guarantees.
 942      *
 943      * @param value the result value for this task
 944      */
 945     public void complete(V value) {
 946         try {
 947             setRawResult(value);
 948         } catch (Throwable rex) {
 949             trySetException(rex);
 950             return;
 951         }
 952         setDone();
 953     }
 954 
 955     /**
 956      * Completes this task normally without setting a value. The most
 957      * recent value established by {@link #setRawResult} (or {@code
 958      * null} by default) will be returned as the result of subsequent
 959      * invocations of {@code join} and related operations.
 960      *
 961      * @since 1.8
 962      */
 963     public final void quietlyComplete() {
 964         setDone();
 965     }
 966 
 967     /**
 968      * Waits if necessary for the computation to complete, and then
 969      * retrieves its result.
 970      *
 971      * @return the computed result
 972      * @throws CancellationException if the computation was cancelled
 973      * @throws ExecutionException if the computation threw an
 974      * exception
 975      * @throws InterruptedException if the current thread is not a
 976      * member of a ForkJoinPool and was interrupted while waiting
 977      */
 978     public final V get() throws InterruptedException, ExecutionException {
 979         int s = awaitDone(null, false, true, false, 0L);
 980         if ((s & ABNORMAL) != 0)
 981             reportExecutionException(s);
 982         return getRawResult();
 983     }
 984 
 985     /**
 986      * Waits if necessary for at most the given time for the computation
 987      * to complete, and then retrieves its result, if available.
 988      *
 989      * @param timeout the maximum time to wait
 990      * @param unit the time unit of the timeout argument
 991      * @return the computed result
 992      * @throws CancellationException if the computation was cancelled
 993      * @throws ExecutionException if the computation threw an
 994      * exception
 995      * @throws InterruptedException if the current thread is not a
 996      * member of a ForkJoinPool and was interrupted while waiting
 997      * @throws TimeoutException if the wait timed out
 998      */
 999     public final V get(long timeout, TimeUnit unit)
1000         throws InterruptedException, ExecutionException, TimeoutException {
1001         long nanos = unit.toNanos(timeout);
1002         int s = awaitDone(null, false, true, true, nanos);
1003         if (s >= 0 || (s & ABNORMAL) != 0)
1004             reportExecutionException(s);
1005         return getRawResult();
1006     }
1007 
1008     /**
1009      * Joins this task, without returning its result or throwing its
1010      * exception. This method may be useful when processing
1011      * collections of tasks when some have been cancelled or otherwise
1012      * known to have aborted.
1013      */
1014     public final void quietlyJoin() {
1015         if (status >= 0)
1016             awaitDone(null, false, false, false, 0L);
1017     }
1018 
1019 
1020     /**
1021      * Commences performing this task and awaits its completion if
1022      * necessary, without returning its result or throwing its
1023      * exception.
1024      */
1025     public final void quietlyInvoke() {
1026         if (doExec() >= 0)
1027             awaitDone(null, true, false, false, 0L);
1028     }
1029 
1030     // Versions of join/get for pool.invoke* methods that use external,
1031     // possibly-non-commonPool submits
1032 
1033     final void awaitPoolInvoke(ForkJoinPool pool) {
1034         awaitDone(pool, false, false, false, 0L);
1035     }
1036     final void awaitPoolInvoke(ForkJoinPool pool, long nanos) {
1037         awaitDone(pool, false, true, true, nanos);
1038     }
1039     final V joinForPoolInvoke(ForkJoinPool pool) {
1040         int s = awaitDone(pool, false, false, false, 0L);
1041         if ((s & ABNORMAL) != 0)
1042             reportException(s);
1043         return getRawResult();
1044     }
1045     final V getForPoolInvoke(ForkJoinPool pool)
1046         throws InterruptedException, ExecutionException {
1047         int s = awaitDone(pool, false, true, false, 0L);
1048         if ((s & ABNORMAL) != 0)
1049             reportExecutionException(s);
1050         return getRawResult();
1051     }
1052     final V getForPoolInvoke(ForkJoinPool pool, long nanos)
1053         throws InterruptedException, ExecutionException, TimeoutException {
1054         int s = awaitDone(pool, false, true, true, nanos);
1055         if (s >= 0 || (s & ABNORMAL) != 0)
1056             reportExecutionException(s);
1057         return getRawResult();
1058     }
1059 
1060     /**
1061      * Possibly executes tasks until the pool hosting the current task
1062      * {@linkplain ForkJoinPool#isQuiescent is quiescent}.  This
1063      * method may be of use in designs in which many tasks are forked,
1064      * but none are explicitly joined, instead executing them until
1065      * all are processed.
1066      */
1067     public static void helpQuiesce() {
1068         Thread t; ForkJoinWorkerThread w; ForkJoinPool p;
1069         if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread &&
1070             (p = (w = (ForkJoinWorkerThread)t).pool) != null)
1071             p.helpQuiescePool(w.workQueue, Long.MAX_VALUE, false);
1072         else
1073             ForkJoinPool.common.externalHelpQuiescePool(Long.MAX_VALUE, false);
1074     }
1075 
1076     /**
1077      * Resets the internal bookkeeping state of this task, allowing a
1078      * subsequent {@code fork}. This method allows repeated reuse of
1079      * this task, but only if reuse occurs when this task has either
1080      * never been forked, or has been forked, then completed and all
1081      * outstanding joins of this task have also completed. Effects
1082      * under any other usage conditions are not guaranteed.
1083      * This method may be useful when executing
1084      * pre-constructed trees of subtasks in loops.
1085      *
1086      * <p>Upon completion of this method, {@code isDone()} reports
1087      * {@code false}, and {@code getException()} reports {@code
1088      * null}. However, the value returned by {@code getRawResult} is
1089      * unaffected. To clear this value, you can invoke {@code
1090      * setRawResult(null)}.
1091      */
1092     public void reinitialize() {
1093         aux = null;
1094         status = 0;
1095     }
1096 
1097     /**
1098      * Returns the pool hosting the current thread, or {@code null}
1099      * if the current thread is executing outside of any ForkJoinPool.
1100      *
1101      * <p>This method returns {@code null} if and only if {@link
1102      * #inForkJoinPool} returns {@code false}.
1103      *
1104      * @return the pool, or {@code null} if none
1105      */
1106     public static ForkJoinPool getPool() {
1107         Thread t;
1108         return (((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) ?
1109                 ((ForkJoinWorkerThread) t).pool : null);
1110     }
1111 
1112     /**
1113      * Returns {@code true} if the current thread is a {@link
1114      * ForkJoinWorkerThread} executing as a ForkJoinPool computation.
1115      *
1116      * @return {@code true} if the current thread is a {@link
1117      * ForkJoinWorkerThread} executing as a ForkJoinPool computation,
1118      * or {@code false} otherwise
1119      */
1120     public static boolean inForkJoinPool() {
1121         return Thread.currentThread() instanceof ForkJoinWorkerThread;
1122     }
1123 
1124     /**
1125      * Tries to unschedule this task for execution. This method will
1126      * typically (but is not guaranteed to) succeed if this task is
1127      * the most recently forked task by the current thread, and has
1128      * not commenced executing in another thread.  This method may be
1129      * useful when arranging alternative local processing of tasks
1130      * that could have been, but were not, stolen.
1131      *
1132      * @return {@code true} if unforked
1133      */
1134     public boolean tryUnfork() {
1135         Thread t; ForkJoinPool.WorkQueue q;
1136         return ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread)
1137             ? (q = ((ForkJoinWorkerThread)t).workQueue) != null
1138                && q.tryUnpush(this)
1139             : (q = ForkJoinPool.commonQueue()) != null
1140                && q.externalTryUnpush(this);
1141     }
1142 
1143     /**
1144      * Returns an estimate of the number of tasks that have been
1145      * forked by the current worker thread but not yet executed. This
1146      * value may be useful for heuristic decisions about whether to
1147      * fork other tasks.
1148      *
1149      * @return the number of tasks
1150      */
1151     public static int getQueuedTaskCount() {
1152         Thread t; ForkJoinPool.WorkQueue q;
1153         if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread)
1154             q = ((ForkJoinWorkerThread)t).workQueue;
1155         else
1156             q = ForkJoinPool.commonQueue();
1157         return (q == null) ? 0 : q.queueSize();
1158     }
1159 
1160     /**
1161      * Returns an estimate of how many more locally queued tasks are
1162      * held by the current worker thread than there are other worker
1163      * threads that might steal them, or zero if this thread is not
1164      * operating in a ForkJoinPool. This value may be useful for
1165      * heuristic decisions about whether to fork other tasks. In many
1166      * usages of ForkJoinTasks, at steady state, each worker should
1167      * aim to maintain a small constant surplus (for example, 3) of
1168      * tasks, and to process computations locally if this threshold is
1169      * exceeded.
1170      *
1171      * @return the surplus number of tasks, which may be negative
1172      */
1173     public static int getSurplusQueuedTaskCount() {
1174         return ForkJoinPool.getSurplusQueuedTaskCount();
1175     }
1176 
1177     // Extension methods
1178 
1179     /**
1180      * Returns the result that would be returned by {@link #join}, even
1181      * if this task completed abnormally, or {@code null} if this task
1182      * is not known to have been completed.  This method is designed
1183      * to aid debugging, as well as to support extensions. Its use in
1184      * any other context is discouraged.
1185      *
1186      * @return the result, or {@code null} if not completed
1187      */
1188     public abstract V getRawResult();
1189 
1190     /**
1191      * Forces the given value to be returned as a result.  This method
1192      * is designed to support extensions, and should not in general be
1193      * called otherwise.
1194      *
1195      * @param value the value
1196      */
1197     protected abstract void setRawResult(V value);
1198 
1199     /**
1200      * Immediately performs the base action of this task and returns
1201      * true if, upon return from this method, this task is guaranteed
1202      * to have completed. This method may return false otherwise, to
1203      * indicate that this task is not necessarily complete (or is not
1204      * known to be complete), for example in asynchronous actions that
1205      * require explicit invocations of completion methods. This method
1206      * may also throw an (unchecked) exception to indicate abnormal
1207      * exit. This method is designed to support extensions, and should
1208      * not in general be called otherwise.
1209      *
1210      * @return {@code true} if this task is known to have completed normally
1211      */
1212     protected abstract boolean exec();
1213 
1214     /**
1215      * Returns, but does not unschedule or execute, a task queued by
1216      * the current thread but not yet executed, if one is immediately
1217      * available. There is no guarantee that this task will actually
1218      * be polled or executed next. Conversely, this method may return
1219      * null even if a task exists but cannot be accessed without
1220      * contention with other threads.  This method is designed
1221      * primarily to support extensions, and is unlikely to be useful
1222      * otherwise.
1223      *
1224      * @return the next task, or {@code null} if none are available
1225      */
1226     protected static ForkJoinTask<?> peekNextLocalTask() {
1227         Thread t; ForkJoinPool.WorkQueue q;
1228         if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread)
1229             q = ((ForkJoinWorkerThread)t).workQueue;
1230         else
1231             q = ForkJoinPool.commonQueue();
1232         return (q == null) ? null : q.peek();
1233     }
1234 
1235     /**
1236      * Unschedules and returns, without executing, the next task
1237      * queued by the current thread but not yet executed, if the
1238      * current thread is operating in a ForkJoinPool.  This method is
1239      * designed primarily to support extensions, and is unlikely to be
1240      * useful otherwise.
1241      *
1242      * @return the next task, or {@code null} if none are available
1243      */
1244     protected static ForkJoinTask<?> pollNextLocalTask() {
1245         Thread t;
1246         return (((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) ?
1247                 ((ForkJoinWorkerThread)t).workQueue.nextLocalTask() : null);
1248     }
1249 
1250     /**
1251      * If the current thread is operating in a ForkJoinPool,
1252      * unschedules and returns, without executing, the next task
1253      * queued by the current thread but not yet executed, if one is
1254      * available, or if not available, a task that was forked by some
1255      * other thread, if available. Availability may be transient, so a
1256      * {@code null} result does not necessarily imply quiescence of
1257      * the pool this task is operating in.  This method is designed
1258      * primarily to support extensions, and is unlikely to be useful
1259      * otherwise.
1260      *
1261      * @return a task, or {@code null} if none are available
1262      */
1263     protected static ForkJoinTask<?> pollTask() {
1264         Thread t; ForkJoinWorkerThread w;
1265         return (((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) ?
1266                 (w = (ForkJoinWorkerThread)t).pool.nextTaskFor(w.workQueue) :
1267                 null);
1268     }
1269 
1270     /**
1271      * If the current thread is operating in a ForkJoinPool,
1272      * unschedules and returns, without executing, a task externally
1273      * submitted to the pool, if one is available. Availability may be
1274      * transient, so a {@code null} result does not necessarily imply
1275      * quiescence of the pool.  This method is designed primarily to
1276      * support extensions, and is unlikely to be useful otherwise.
1277      *
1278      * @return a task, or {@code null} if none are available
1279      * @since 9
1280      */
1281     protected static ForkJoinTask<?> pollSubmission() {
1282         Thread t;
1283         return (((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) ?
1284                 ((ForkJoinWorkerThread)t).pool.pollSubmission() : null);
1285     }
1286 
1287     // tag operations
1288 
1289     /**
1290      * Returns the tag for this task.
1291      *
1292      * @return the tag for this task
1293      * @since 1.8
1294      */
1295     public final short getForkJoinTaskTag() {
1296         return (short)status;
1297     }
1298 
1299     /**
1300      * Atomically sets the tag value for this task and returns the old value.
1301      *
1302      * @param newValue the new tag value
1303      * @return the previous value of the tag
1304      * @since 1.8
1305      */
1306     public final short setForkJoinTaskTag(short newValue) {
1307         for (int s;;) {
1308             if (casStatus(s = status, (s & ~SMASK) | (newValue & SMASK)))
1309                 return (short)s;
1310         }
1311     }
1312 
1313     /**
1314      * Atomically conditionally sets the tag value for this task.
1315      * Among other applications, tags can be used as visit markers
1316      * in tasks operating on graphs, as in methods that check: {@code
1317      * if (task.compareAndSetForkJoinTaskTag((short)0, (short)1))}
1318      * before processing, otherwise exiting because the node has
1319      * already been visited.
1320      *
1321      * @param expect the expected tag value
1322      * @param update the new tag value
1323      * @return {@code true} if successful; i.e., the current value was
1324      * equal to {@code expect} and was changed to {@code update}.
1325      * @since 1.8
1326      */
1327     public final boolean compareAndSetForkJoinTaskTag(short expect, short update) {
1328         for (int s;;) {
1329             if ((short)(s = status) != expect)
1330                 return false;
1331             if (casStatus(s, (s & ~SMASK) | (update & SMASK)))
1332                 return true;
1333         }
1334     }
1335 
1336     /**
1337      * Adapter for Runnables. This implements RunnableFuture
1338      * to be compliant with AbstractExecutorService constraints
1339      * when used in ForkJoinPool.
1340      */
1341     static final class AdaptedRunnable<T> extends ForkJoinTask<T>
1342         implements RunnableFuture<T> {
1343         @SuppressWarnings("serial") // Conditionally serializable
1344         final Runnable runnable;
1345         @SuppressWarnings("serial") // Conditionally serializable
1346         T result;
1347         AdaptedRunnable(Runnable runnable, T result) {
1348             if (runnable == null) throw new NullPointerException();
1349             this.runnable = runnable;
1350             this.result = result; // OK to set this even before completion
1351         }
1352         public final T getRawResult() { return result; }
1353         public final void setRawResult(T v) { result = v; }
1354         public final boolean exec() { runnable.run(); return true; }
1355         public final void run() { invoke(); }
1356         public String toString() {
1357             return super.toString() + "[Wrapped task = " + runnable + "]";
1358         }
1359         private static final long serialVersionUID = 5232453952276885070L;
1360     }
1361 
1362     /**
1363      * Adapter for Runnables without results.
1364      */
1365     static final class AdaptedRunnableAction extends ForkJoinTask<Void>
1366         implements RunnableFuture<Void> {
1367         @SuppressWarnings("serial") // Conditionally serializable
1368         final Runnable runnable;
1369         AdaptedRunnableAction(Runnable runnable) {
1370             if (runnable == null) throw new NullPointerException();
1371             this.runnable = runnable;
1372         }
1373         public final Void getRawResult() { return null; }
1374         public final void setRawResult(Void v) { }
1375         public final boolean exec() { runnable.run(); return true; }
1376         public final void run() { invoke(); }
1377         public String toString() {
1378             return super.toString() + "[Wrapped task = " + runnable + "]";
1379         }
1380         private static final long serialVersionUID = 5232453952276885070L;
1381     }
1382 
1383     /**
1384      * Adapter for Runnables in which failure forces worker exception.
1385      */
1386     static final class RunnableExecuteAction extends ForkJoinTask<Void> {
1387         @SuppressWarnings("serial") // Conditionally serializable
1388         final Runnable runnable;
1389         RunnableExecuteAction(Runnable runnable) {
1390             if (runnable == null) throw new NullPointerException();
1391             this.runnable = runnable;
1392         }
1393         public final Void getRawResult() { return null; }
1394         public final void setRawResult(Void v) { }
1395         public final boolean exec() { runnable.run(); return true; }
1396         int trySetException(Throwable ex) { // if a handler, invoke it
1397             int s; Thread t; java.lang.Thread.UncaughtExceptionHandler h;
1398             if (isExceptionalStatus(s = trySetThrown(ex)) &&
1399                 (h = ((t = Thread.currentThread()).
1400                       getUncaughtExceptionHandler())) != null) {
1401                 try {
1402                     h.uncaughtException(t, ex);
1403                 } catch (Throwable ignore) {
1404                 }
1405             }
1406             return s;
1407         }
1408         private static final long serialVersionUID = 5232453952276885070L;
1409     }
1410 
1411     /**
1412      * Adapter for Callables.
1413      */
1414     static final class AdaptedCallable<T> extends ForkJoinTask<T>
1415         implements RunnableFuture<T> {
1416         @SuppressWarnings("serial") // Conditionally serializable
1417         final Callable<? extends T> callable;
1418         @SuppressWarnings("serial") // Conditionally serializable
1419         T result;
1420         AdaptedCallable(Callable<? extends T> callable) {
1421             if (callable == null) throw new NullPointerException();
1422             this.callable = callable;
1423         }
1424         public final T getRawResult() { return result; }
1425         public final void setRawResult(T v) { result = v; }
1426         public final boolean exec() {
1427             try {
1428                 result = callable.call();
1429                 return true;
1430             } catch (RuntimeException rex) {
1431                 throw rex;
1432             } catch (Exception ex) {
1433                 throw new RuntimeException(ex);
1434             }
1435         }
1436         public final void run() { invoke(); }
1437         public String toString() {
1438             return super.toString() + "[Wrapped task = " + callable + "]";
1439         }
1440         private static final long serialVersionUID = 2838392045355241008L;
1441     }
1442 
1443     static final class AdaptedInterruptibleCallable<T> extends ForkJoinTask<T>
1444         implements RunnableFuture<T> {
1445         @SuppressWarnings("serial") // Conditionally serializable
1446         final Callable<? extends T> callable;
1447         transient volatile Thread runner;
1448         @SuppressWarnings("serial") // Conditionally serializable
1449         T result;
1450         AdaptedInterruptibleCallable(Callable<? extends T> callable) {
1451             if (callable == null) throw new NullPointerException();
1452             this.callable = callable;
1453         }
1454         public final T getRawResult() { return result; }
1455         public final void setRawResult(T v) { result = v; }
1456         public final boolean exec() {
1457             Thread.interrupted();
1458             runner = Thread.currentThread();
1459             try {
1460                 if (!isDone()) // recheck
1461                     result = callable.call();
1462                 return true;
1463             } catch (RuntimeException rex) {
1464                 throw rex;
1465             } catch (Exception ex) {
1466                 throw new RuntimeException(ex);
1467             } finally {
1468                 runner = null;
1469                 Thread.interrupted();
1470             }
1471         }
1472         public final void run() { invoke(); }
1473         public final boolean cancel(boolean mayInterruptIfRunning) {
1474             Thread t;
1475             boolean stat = super.cancel(false);
1476             if (mayInterruptIfRunning && (t = runner) != null) {
1477                 try {
1478                     t.interrupt();
1479                 } catch (Throwable ignore) {
1480                 }
1481             }
1482             return stat;
1483         }
1484         public String toString() {
1485             return super.toString() + "[Wrapped task = " + callable + "]";
1486         }
1487         private static final long serialVersionUID = 2838392045355241008L;
1488     }
1489 
1490     /**
1491      * Returns a new {@code ForkJoinTask} that performs the {@code run}
1492      * method of the given {@code Runnable} as its action, and returns
1493      * a null result upon {@link #join}.
1494      *
1495      * @param runnable the runnable action
1496      * @return the task
1497      */
1498     public static ForkJoinTask<?> adapt(Runnable runnable) {
1499         return new AdaptedRunnableAction(runnable);
1500     }
1501 
1502     /**
1503      * Returns a new {@code ForkJoinTask} that performs the {@code run}
1504      * method of the given {@code Runnable} as its action, and returns
1505      * the given result upon {@link #join}.
1506      *
1507      * @param runnable the runnable action
1508      * @param result the result upon completion
1509      * @param <T> the type of the result
1510      * @return the task
1511      */
1512     public static <T> ForkJoinTask<T> adapt(Runnable runnable, T result) {
1513         return new AdaptedRunnable<T>(runnable, result);
1514     }
1515 
1516     /**
1517      * Returns a new {@code ForkJoinTask} that performs the {@code call}
1518      * method of the given {@code Callable} as its action, and returns
1519      * its result upon {@link #join}, translating any checked exceptions
1520      * encountered into {@code RuntimeException}.
1521      *
1522      * @param callable the callable action
1523      * @param <T> the type of the callable's result
1524      * @return the task
1525      */
1526     public static <T> ForkJoinTask<T> adapt(Callable<? extends T> callable) {
1527         return new AdaptedCallable<T>(callable);
1528     }
1529 
1530     /**
1531      * Returns a new {@code ForkJoinTask} that performs the {@code call}
1532      * method of the given {@code Callable} as its action, and returns
1533      * its result upon {@link #join}, translating any checked exceptions
1534      * encountered into {@code RuntimeException}.  Additionally,
1535      * invocations of {@code cancel} with {@code mayInterruptIfRunning
1536      * true} will attempt to interrupt the thread performing the task.
1537      *
1538      * @param callable the callable action
1539      * @param <T> the type of the callable's result
1540      * @return the task
1541      *
1542      * @since 17
1543      */
1544     // adaptInterruptible deferred to its own independent change
1545     // https://bugs.openjdk.java.net/browse/JDK-8246587
1546     /* TODO: public */ private static <T> ForkJoinTask<T> adaptInterruptible(Callable<? extends T> callable) {
1547         return new AdaptedInterruptibleCallable<T>(callable);
1548     }
1549 
1550     // Serialization support
1551 
1552     private static final long serialVersionUID = -7721805057305804111L;
1553 
1554     /**
1555      * Saves this task to a stream (that is, serializes it).
1556      *
1557      * @param s the stream
1558      * @throws java.io.IOException if an I/O error occurs
1559      * @serialData the current run status and the exception thrown
1560      * during execution, or {@code null} if none
1561      */
1562     private void writeObject(java.io.ObjectOutputStream s)
1563         throws java.io.IOException {
1564         Aux a;
1565         s.defaultWriteObject();
1566         s.writeObject((a = aux) == null ? null : a.ex);
1567     }
1568 
1569     /**
1570      * Reconstitutes this task from a stream (that is, deserializes it).
1571      * @param s the stream
1572      * @throws ClassNotFoundException if the class of a serialized object
1573      *         could not be found
1574      * @throws java.io.IOException if an I/O error occurs
1575      */
1576     private void readObject(java.io.ObjectInputStream s)
1577         throws java.io.IOException, ClassNotFoundException {
1578         s.defaultReadObject();
1579         Object ex = s.readObject();
1580         if (ex != null)
1581             trySetThrown((Throwable)ex);
1582     }
1583 
1584     static {
1585         try {
1586             MethodHandles.Lookup l = MethodHandles.lookup();
1587             STATUS = l.findVarHandle(ForkJoinTask.class, "status", int.class);
1588             AUX = l.findVarHandle(ForkJoinTask.class, "aux", Aux.class);
1589         } catch (ReflectiveOperationException e) {
1590             throw new ExceptionInInitializerError(e);
1591         }
1592     }
1593 
1594 }
--- EOF ---