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