001/*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.util.concurrent;
016
017import static com.google.common.base.Preconditions.checkNotNull;
018import static com.google.common.base.Throwables.throwIfUnchecked;
019import static com.google.common.util.concurrent.NullnessCasts.uncheckedNull;
020import static java.lang.Integer.toHexString;
021import static java.lang.System.identityHashCode;
022import static java.util.Objects.requireNonNull;
023import static java.util.concurrent.atomic.AtomicReferenceFieldUpdater.newUpdater;
024
025import com.google.common.annotations.Beta;
026import com.google.common.annotations.GwtCompatible;
027import com.google.common.base.Strings;
028import com.google.common.util.concurrent.internal.InternalFutureFailureAccess;
029import com.google.common.util.concurrent.internal.InternalFutures;
030import com.google.errorprone.annotations.CanIgnoreReturnValue;
031import com.google.errorprone.annotations.ForOverride;
032import com.google.j2objc.annotations.ReflectionSupport;
033import java.security.AccessController;
034import java.security.PrivilegedActionException;
035import java.security.PrivilegedExceptionAction;
036import java.util.Locale;
037import java.util.concurrent.CancellationException;
038import java.util.concurrent.ExecutionException;
039import java.util.concurrent.Executor;
040import java.util.concurrent.Future;
041import java.util.concurrent.ScheduledFuture;
042import java.util.concurrent.TimeUnit;
043import java.util.concurrent.TimeoutException;
044import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
045import java.util.concurrent.locks.LockSupport;
046import java.util.logging.Level;
047import java.util.logging.Logger;
048import javax.annotation.CheckForNull;
049import org.checkerframework.checker.nullness.qual.Nullable;
050
051/**
052 * An abstract implementation of {@link ListenableFuture}, intended for advanced users only. More
053 * common ways to create a {@code ListenableFuture} include instantiating a {@link SettableFuture},
054 * submitting a task to a {@link ListeningExecutorService}, and deriving a {@code Future} from an
055 * existing one, typically using methods like {@link Futures#transform(ListenableFuture,
056 * com.google.common.base.Function, java.util.concurrent.Executor) Futures.transform} and {@link
057 * Futures#catching(ListenableFuture, Class, com.google.common.base.Function,
058 * java.util.concurrent.Executor) Futures.catching}.
059 *
060 * <p>This class implements all methods in {@code ListenableFuture}. Subclasses should provide a way
061 * to set the result of the computation through the protected methods {@link #set(Object)}, {@link
062 * #setFuture(ListenableFuture)} and {@link #setException(Throwable)}. Subclasses may also override
063 * {@link #afterDone()}, which will be invoked automatically when the future completes. Subclasses
064 * should rarely override other methods.
065 *
066 * @author Sven Mawson
067 * @author Luke Sandberg
068 * @since 1.0
069 */
070@SuppressWarnings({
071  "ShortCircuitBoolean", // we use non-short circuiting comparisons intentionally
072  "nullness", // TODO(b/147136275): Remove once our checker understands & and |.
073})
074@GwtCompatible(emulated = true)
075@ReflectionSupport(value = ReflectionSupport.Level.FULL)
076@ElementTypesAreNonnullByDefault
077public abstract class AbstractFuture<V extends @Nullable Object> extends InternalFutureFailureAccess
078    implements ListenableFuture<V> {
079  // NOTE: Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
080
081  private static final boolean GENERATE_CANCELLATION_CAUSES;
082
083  static {
084    // System.getProperty may throw if the security policy does not permit access.
085    boolean generateCancellationCauses;
086    try {
087      generateCancellationCauses =
088          Boolean.parseBoolean(
089              System.getProperty("guava.concurrent.generate_cancellation_cause", "false"));
090    } catch (SecurityException e) {
091      generateCancellationCauses = false;
092    }
093    GENERATE_CANCELLATION_CAUSES = generateCancellationCauses;
094  }
095
096  /**
097   * Tag interface marking trusted subclasses. This enables some optimizations. The implementation
098   * of this interface must also be an AbstractFuture and must not override or expose for overriding
099   * any of the public methods of ListenableFuture.
100   */
101  interface Trusted<V extends @Nullable Object> extends ListenableFuture<V> {}
102
103  /**
104   * A less abstract subclass of AbstractFuture. This can be used to optimize setFuture by ensuring
105   * that {@link #get} calls exactly the implementation of {@link AbstractFuture#get}.
106   */
107  abstract static class TrustedFuture<V extends @Nullable Object> extends AbstractFuture<V>
108      implements Trusted<V> {
109    @CanIgnoreReturnValue
110    @Override
111    @ParametricNullness
112    public final V get() throws InterruptedException, ExecutionException {
113      return super.get();
114    }
115
116    @CanIgnoreReturnValue
117    @Override
118    @ParametricNullness
119    public final V get(long timeout, TimeUnit unit)
120        throws InterruptedException, ExecutionException, TimeoutException {
121      return super.get(timeout, unit);
122    }
123
124    @Override
125    public final boolean isDone() {
126      return super.isDone();
127    }
128
129    @Override
130    public final boolean isCancelled() {
131      return super.isCancelled();
132    }
133
134    @Override
135    public final void addListener(Runnable listener, Executor executor) {
136      super.addListener(listener, executor);
137    }
138
139    @CanIgnoreReturnValue
140    @Override
141    public final boolean cancel(boolean mayInterruptIfRunning) {
142      return super.cancel(mayInterruptIfRunning);
143    }
144  }
145
146  // Logger to log exceptions caught when running listeners.
147  private static final Logger log = Logger.getLogger(AbstractFuture.class.getName());
148
149  // A heuristic for timed gets. If the remaining timeout is less than this, spin instead of
150  // blocking. This value is what AbstractQueuedSynchronizer uses.
151  private static final long SPIN_THRESHOLD_NANOS = 1000L;
152
153  private static final AtomicHelper ATOMIC_HELPER;
154
155  static {
156    AtomicHelper helper;
157    Throwable thrownUnsafeFailure = null;
158    Throwable thrownAtomicReferenceFieldUpdaterFailure = null;
159
160    try {
161      helper = new UnsafeAtomicHelper();
162    } catch (Throwable unsafeFailure) {
163      thrownUnsafeFailure = unsafeFailure;
164      // catch absolutely everything and fall through to our 'SafeAtomicHelper'
165      // The access control checks that ARFU does means the caller class has to be AbstractFuture
166      // instead of SafeAtomicHelper, so we annoyingly define these here
167      try {
168        helper =
169            new SafeAtomicHelper(
170                newUpdater(Waiter.class, Thread.class, "thread"),
171                newUpdater(Waiter.class, Waiter.class, "next"),
172                newUpdater(AbstractFuture.class, Waiter.class, "waiters"),
173                newUpdater(AbstractFuture.class, Listener.class, "listeners"),
174                newUpdater(AbstractFuture.class, Object.class, "value"));
175      } catch (Throwable atomicReferenceFieldUpdaterFailure) {
176        // Some Android 5.0.x Samsung devices have bugs in JDK reflection APIs that cause
177        // getDeclaredField to throw a NoSuchFieldException when the field is definitely there.
178        // For these users fallback to a suboptimal implementation, based on synchronized. This will
179        // be a definite performance hit to those users.
180        thrownAtomicReferenceFieldUpdaterFailure = atomicReferenceFieldUpdaterFailure;
181        helper = new SynchronizedHelper();
182      }
183    }
184    ATOMIC_HELPER = helper;
185
186    // Prevent rare disastrous classloading in first call to LockSupport.park.
187    // See: https://bugs.openjdk.java.net/browse/JDK-8074773
188    @SuppressWarnings("unused")
189    Class<?> ensureLoaded = LockSupport.class;
190
191    // Log after all static init is finished; if an installed logger uses any Futures methods, it
192    // shouldn't break in cases where reflection is missing/broken.
193    if (thrownAtomicReferenceFieldUpdaterFailure != null) {
194      log.log(Level.SEVERE, "UnsafeAtomicHelper is broken!", thrownUnsafeFailure);
195      log.log(
196          Level.SEVERE, "SafeAtomicHelper is broken!", thrownAtomicReferenceFieldUpdaterFailure);
197    }
198  }
199
200  /** Waiter links form a Treiber stack, in the {@link #waiters} field. */
201  private static final class Waiter {
202    static final Waiter TOMBSTONE = new Waiter(false /* ignored param */);
203
204    @CheckForNull volatile Thread thread;
205    @CheckForNull volatile Waiter next;
206
207    /**
208     * Constructor for the TOMBSTONE, avoids use of ATOMIC_HELPER in case this class is loaded
209     * before the ATOMIC_HELPER. Apparently this is possible on some android platforms.
210     */
211    Waiter(boolean unused) {}
212
213    Waiter() {
214      // avoid volatile write, write is made visible by subsequent CAS on waiters field
215      ATOMIC_HELPER.putThread(this, Thread.currentThread());
216    }
217
218    // non-volatile write to the next field. Should be made visible by subsequent CAS on waiters
219    // field.
220    void setNext(@CheckForNull Waiter next) {
221      ATOMIC_HELPER.putNext(this, next);
222    }
223
224    void unpark() {
225      // This is racy with removeWaiter. The consequence of the race is that we may spuriously call
226      // unpark even though the thread has already removed itself from the list. But even if we did
227      // use a CAS, that race would still exist (it would just be ever so slightly smaller).
228      Thread w = thread;
229      if (w != null) {
230        thread = null;
231        LockSupport.unpark(w);
232      }
233    }
234  }
235
236  /**
237   * Marks the given node as 'deleted' (null waiter) and then scans the list to unlink all deleted
238   * nodes. This is an O(n) operation in the common case (and O(n^2) in the worst), but we are saved
239   * by two things.
240   *
241   * <ul>
242   *   <li>This is only called when a waiting thread times out or is interrupted. Both of which
243   *       should be rare.
244   *   <li>The waiters list should be very short.
245   * </ul>
246   */
247  private void removeWaiter(Waiter node) {
248    node.thread = null; // mark as 'deleted'
249    restart:
250    while (true) {
251      Waiter pred = null;
252      Waiter curr = waiters;
253      if (curr == Waiter.TOMBSTONE) {
254        return; // give up if someone is calling complete
255      }
256      Waiter succ;
257      while (curr != null) {
258        succ = curr.next;
259        if (curr.thread != null) { // we aren't unlinking this node, update pred.
260          pred = curr;
261        } else if (pred != null) { // We are unlinking this node and it has a predecessor.
262          pred.next = succ;
263          if (pred.thread == null) { // We raced with another node that unlinked pred. Restart.
264            continue restart;
265          }
266        } else if (!ATOMIC_HELPER.casWaiters(this, curr, succ)) { // We are unlinking head
267          continue restart; // We raced with an add or complete
268        }
269        curr = succ;
270      }
271      break;
272    }
273  }
274
275  /** Listeners also form a stack through the {@link #listeners} field. */
276  private static final class Listener {
277    static final Listener TOMBSTONE = new Listener();
278    @CheckForNull // null only for TOMBSTONE
279    final Runnable task;
280    @CheckForNull // null only for TOMBSTONE
281    final Executor executor;
282
283    // writes to next are made visible by subsequent CAS's on the listeners field
284    @CheckForNull Listener next;
285
286    Listener(Runnable task, Executor executor) {
287      this.task = task;
288      this.executor = executor;
289    }
290
291    Listener() {
292      this.task = null;
293      this.executor = null;
294    }
295  }
296
297  /** A special value to represent {@code null}. */
298  private static final Object NULL = new Object();
299
300  /** A special value to represent failure, when {@link #setException} is called successfully. */
301  private static final class Failure {
302    static final Failure FALLBACK_INSTANCE =
303        new Failure(
304            new Throwable("Failure occurred while trying to finish a future.") {
305              @Override
306              public synchronized Throwable fillInStackTrace() {
307                return this; // no stack trace
308              }
309            });
310    final Throwable exception;
311
312    Failure(Throwable exception) {
313      this.exception = checkNotNull(exception);
314    }
315  }
316
317  /** A special value to represent cancellation and the 'wasInterrupted' bit. */
318  private static final class Cancellation {
319    // constants to use when GENERATE_CANCELLATION_CAUSES = false
320    @CheckForNull static final Cancellation CAUSELESS_INTERRUPTED;
321    @CheckForNull static final Cancellation CAUSELESS_CANCELLED;
322
323    static {
324      if (GENERATE_CANCELLATION_CAUSES) {
325        CAUSELESS_CANCELLED = null;
326        CAUSELESS_INTERRUPTED = null;
327      } else {
328        CAUSELESS_CANCELLED = new Cancellation(false, null);
329        CAUSELESS_INTERRUPTED = new Cancellation(true, null);
330      }
331    }
332
333    final boolean wasInterrupted;
334    @CheckForNull final Throwable cause;
335
336    Cancellation(boolean wasInterrupted, @CheckForNull Throwable cause) {
337      this.wasInterrupted = wasInterrupted;
338      this.cause = cause;
339    }
340  }
341
342  /** A special value that encodes the 'setFuture' state. */
343  private static final class SetFuture<V extends @Nullable Object> implements Runnable {
344    final AbstractFuture<V> owner;
345    final ListenableFuture<? extends V> future;
346
347    SetFuture(AbstractFuture<V> owner, ListenableFuture<? extends V> future) {
348      this.owner = owner;
349      this.future = future;
350    }
351
352    @Override
353    public void run() {
354      if (owner.value != this) {
355        // nothing to do, we must have been cancelled, don't bother inspecting the future.
356        return;
357      }
358      Object valueToSet = getFutureValue(future);
359      if (ATOMIC_HELPER.casValue(owner, this, valueToSet)) {
360        complete(owner);
361      }
362    }
363  }
364
365  // TODO(lukes): investigate using the @Contended annotation on these fields when jdk8 is
366  // available.
367  /**
368   * This field encodes the current state of the future.
369   *
370   * <p>The valid values are:
371   *
372   * <ul>
373   *   <li>{@code null} initial state, nothing has happened.
374   *   <li>{@link Cancellation} terminal state, {@code cancel} was called.
375   *   <li>{@link Failure} terminal state, {@code setException} was called.
376   *   <li>{@link SetFuture} intermediate state, {@code setFuture} was called.
377   *   <li>{@link #NULL} terminal state, {@code set(null)} was called.
378   *   <li>Any other non-null value, terminal state, {@code set} was called with a non-null
379   *       argument.
380   * </ul>
381   */
382  @CheckForNull private volatile Object value;
383
384  /** All listeners. */
385  @CheckForNull private volatile Listener listeners;
386
387  /** All waiting threads. */
388  @CheckForNull private volatile Waiter waiters;
389
390  /** Constructor for use by subclasses. */
391  protected AbstractFuture() {}
392
393  // Gets and Timed Gets
394  //
395  // * Be responsive to interruption
396  // * Don't create Waiter nodes if you aren't going to park, this helps reduce contention on the
397  //   waiters field.
398  // * Future completion is defined by when #value becomes non-null/non SetFuture
399  // * Future completion can be observed if the waiters field contains a TOMBSTONE
400
401  // Timed Get
402  // There are a few design constraints to consider
403  // * We want to be responsive to small timeouts, unpark() has non trivial latency overheads (I
404  //   have observed 12 micros on 64 bit linux systems to wake up a parked thread). So if the
405  //   timeout is small we shouldn't park(). This needs to be traded off with the cpu overhead of
406  //   spinning, so we use SPIN_THRESHOLD_NANOS which is what AbstractQueuedSynchronizer uses for
407  //   similar purposes.
408  // * We want to behave reasonably for timeouts of 0
409  // * We are more responsive to completion than timeouts. This is because parkNanos depends on
410  //   system scheduling and as such we could either miss our deadline, or unpark() could be delayed
411  //   so that it looks like we timed out even though we didn't. For comparison FutureTask respects
412  //   completion preferably and AQS is non-deterministic (depends on where in the queue the waiter
413  //   is). If we wanted to be strict about it, we could store the unpark() time in the Waiter node
414  //   and we could use that to make a decision about whether or not we timed out prior to being
415  //   unparked.
416
417  /**
418   * {@inheritDoc}
419   *
420   * <p>The default {@link AbstractFuture} implementation throws {@code InterruptedException} if the
421   * current thread is interrupted during the call, even if the value is already available.
422   *
423   * @throws CancellationException {@inheritDoc}
424   */
425  @CanIgnoreReturnValue
426  @Override
427  @ParametricNullness
428  public V get(long timeout, TimeUnit unit)
429      throws InterruptedException, TimeoutException, ExecutionException {
430    // NOTE: if timeout < 0, remainingNanos will be < 0 and we will fall into the while(true) loop
431    // at the bottom and throw a timeoutexception.
432    final long timeoutNanos = unit.toNanos(timeout); // we rely on the implicit null check on unit.
433    long remainingNanos = timeoutNanos;
434    if (Thread.interrupted()) {
435      throw new InterruptedException();
436    }
437    Object localValue = value;
438    if (localValue != null & !(localValue instanceof SetFuture)) {
439      return getDoneValue(localValue);
440    }
441    // we delay calling nanoTime until we know we will need to either park or spin
442    final long endNanos = remainingNanos > 0 ? System.nanoTime() + remainingNanos : 0;
443    long_wait_loop:
444    if (remainingNanos >= SPIN_THRESHOLD_NANOS) {
445      Waiter oldHead = waiters;
446      if (oldHead != Waiter.TOMBSTONE) {
447        Waiter node = new Waiter();
448        do {
449          node.setNext(oldHead);
450          if (ATOMIC_HELPER.casWaiters(this, oldHead, node)) {
451            while (true) {
452              OverflowAvoidingLockSupport.parkNanos(this, remainingNanos);
453              // Check interruption first, if we woke up due to interruption we need to honor that.
454              if (Thread.interrupted()) {
455                removeWaiter(node);
456                throw new InterruptedException();
457              }
458
459              // Otherwise re-read and check doneness. If we loop then it must have been a spurious
460              // wakeup
461              localValue = value;
462              if (localValue != null & !(localValue instanceof SetFuture)) {
463                return getDoneValue(localValue);
464              }
465
466              // timed out?
467              remainingNanos = endNanos - System.nanoTime();
468              if (remainingNanos < SPIN_THRESHOLD_NANOS) {
469                // Remove the waiter, one way or another we are done parking this thread.
470                removeWaiter(node);
471                break long_wait_loop; // jump down to the busy wait loop
472              }
473            }
474          }
475          oldHead = waiters; // re-read and loop.
476        } while (oldHead != Waiter.TOMBSTONE);
477      }
478      // re-read value, if we get here then we must have observed a TOMBSTONE while trying to add a
479      // waiter.
480      // requireNonNull is safe because value is always set before TOMBSTONE.
481      return getDoneValue(requireNonNull(value));
482    }
483    // If we get here then we have remainingNanos < SPIN_THRESHOLD_NANOS and there is no node on the
484    // waiters list
485    while (remainingNanos > 0) {
486      localValue = value;
487      if (localValue != null & !(localValue instanceof SetFuture)) {
488        return getDoneValue(localValue);
489      }
490      if (Thread.interrupted()) {
491        throw new InterruptedException();
492      }
493      remainingNanos = endNanos - System.nanoTime();
494    }
495
496    String futureToString = toString();
497    final String unitString = unit.toString().toLowerCase(Locale.ROOT);
498    String message = "Waited " + timeout + " " + unit.toString().toLowerCase(Locale.ROOT);
499    // Only report scheduling delay if larger than our spin threshold - otherwise it's just noise
500    if (remainingNanos + SPIN_THRESHOLD_NANOS < 0) {
501      // We over-waited for our timeout.
502      message += " (plus ";
503      long overWaitNanos = -remainingNanos;
504      long overWaitUnits = unit.convert(overWaitNanos, TimeUnit.NANOSECONDS);
505      long overWaitLeftoverNanos = overWaitNanos - unit.toNanos(overWaitUnits);
506      boolean shouldShowExtraNanos =
507          overWaitUnits == 0 || overWaitLeftoverNanos > SPIN_THRESHOLD_NANOS;
508      if (overWaitUnits > 0) {
509        message += overWaitUnits + " " + unitString;
510        if (shouldShowExtraNanos) {
511          message += ",";
512        }
513        message += " ";
514      }
515      if (shouldShowExtraNanos) {
516        message += overWaitLeftoverNanos + " nanoseconds ";
517      }
518
519      message += "delay)";
520    }
521    // It's confusing to see a completed future in a timeout message; if isDone() returns false,
522    // then we know it must have given a pending toString value earlier. If not, then the future
523    // completed after the timeout expired, and the message might be success.
524    if (isDone()) {
525      throw new TimeoutException(message + " but future completed as timeout expired");
526    }
527    throw new TimeoutException(message + " for " + futureToString);
528  }
529
530  /**
531   * {@inheritDoc}
532   *
533   * <p>The default {@link AbstractFuture} implementation throws {@code InterruptedException} if the
534   * current thread is interrupted during the call, even if the value is already available.
535   *
536   * @throws CancellationException {@inheritDoc}
537   */
538  @CanIgnoreReturnValue
539  @Override
540  @ParametricNullness
541  public V get() throws InterruptedException, ExecutionException {
542    if (Thread.interrupted()) {
543      throw new InterruptedException();
544    }
545    Object localValue = value;
546    if (localValue != null & !(localValue instanceof SetFuture)) {
547      return getDoneValue(localValue);
548    }
549    Waiter oldHead = waiters;
550    if (oldHead != Waiter.TOMBSTONE) {
551      Waiter node = new Waiter();
552      do {
553        node.setNext(oldHead);
554        if (ATOMIC_HELPER.casWaiters(this, oldHead, node)) {
555          // we are on the stack, now wait for completion.
556          while (true) {
557            LockSupport.park(this);
558            // Check interruption first, if we woke up due to interruption we need to honor that.
559            if (Thread.interrupted()) {
560              removeWaiter(node);
561              throw new InterruptedException();
562            }
563            // Otherwise re-read and check doneness. If we loop then it must have been a spurious
564            // wakeup
565            localValue = value;
566            if (localValue != null & !(localValue instanceof SetFuture)) {
567              return getDoneValue(localValue);
568            }
569          }
570        }
571        oldHead = waiters; // re-read and loop.
572      } while (oldHead != Waiter.TOMBSTONE);
573    }
574    // re-read value, if we get here then we must have observed a TOMBSTONE while trying to add a
575    // waiter.
576    // requireNonNull is safe because value is always set before TOMBSTONE.
577    return getDoneValue(requireNonNull(value));
578  }
579
580  /** Unboxes {@code obj}. Assumes that obj is not {@code null} or a {@link SetFuture}. */
581  @ParametricNullness
582  private V getDoneValue(Object obj) throws ExecutionException {
583    // While this seems like it might be too branch-y, simple benchmarking proves it to be
584    // unmeasurable (comparing done AbstractFutures with immediateFuture)
585    if (obj instanceof Cancellation) {
586      throw cancellationExceptionWithCause("Task was cancelled.", ((Cancellation) obj).cause);
587    } else if (obj instanceof Failure) {
588      throw new ExecutionException(((Failure) obj).exception);
589    } else if (obj == NULL) {
590      /*
591       * It's safe to return null because we would only have stored it in the first place if it were
592       * a valid value for V.
593       */
594      return uncheckedNull();
595    } else {
596      @SuppressWarnings("unchecked") // this is the only other option
597      V asV = (V) obj;
598      return asV;
599    }
600  }
601
602  @Override
603  public boolean isDone() {
604    final Object localValue = value;
605    return localValue != null & !(localValue instanceof SetFuture);
606  }
607
608  @Override
609  public boolean isCancelled() {
610    final Object localValue = value;
611    return localValue instanceof Cancellation;
612  }
613
614  /**
615   * {@inheritDoc}
616   *
617   * <p>If a cancellation attempt succeeds on a {@code Future} that had previously been {@linkplain
618   * #setFuture set asynchronously}, then the cancellation will also be propagated to the delegate
619   * {@code Future} that was supplied in the {@code setFuture} call.
620   *
621   * <p>Rather than override this method to perform additional cancellation work or cleanup,
622   * subclasses should override {@link #afterDone}, consulting {@link #isCancelled} and {@link
623   * #wasInterrupted} as necessary. This ensures that the work is done even if the future is
624   * cancelled without a call to {@code cancel}, such as by calling {@code
625   * setFuture(cancelledFuture)}.
626   *
627   * <p>Beware of completing a future while holding a lock. Its listeners may do slow work or
628   * acquire other locks, risking deadlocks.
629   */
630  @CanIgnoreReturnValue
631  @Override
632  public boolean cancel(boolean mayInterruptIfRunning) {
633    Object localValue = value;
634    boolean rValue = false;
635    if (localValue == null | localValue instanceof SetFuture) {
636      // Try to delay allocating the exception. At this point we may still lose the CAS, but it is
637      // certainly less likely.
638      Object valueToSet =
639          GENERATE_CANCELLATION_CAUSES
640              ? new Cancellation(
641                  mayInterruptIfRunning, new CancellationException("Future.cancel() was called."))
642              /*
643               * requireNonNull is safe because we've initialized these if
644               * !GENERATE_CANCELLATION_CAUSES.
645               *
646               * TODO(cpovirk): Maybe it would be cleaner to define a CancellationSupplier interface
647               * with two implementations, one that contains causeless Cancellation instances and
648               * the other of which creates new Cancellation instances each time it's called? Yet
649               * another alternative is to fill in a non-null value for each of the fields no matter
650               * what and to just not use it if !GENERATE_CANCELLATION_CAUSES.
651               */
652              : requireNonNull(
653                  mayInterruptIfRunning
654                      ? Cancellation.CAUSELESS_INTERRUPTED
655                      : Cancellation.CAUSELESS_CANCELLED);
656      AbstractFuture<?> abstractFuture = this;
657      while (true) {
658        if (ATOMIC_HELPER.casValue(abstractFuture, localValue, valueToSet)) {
659          rValue = true;
660          // We call interruptTask before calling complete(), which is consistent with
661          // FutureTask
662          if (mayInterruptIfRunning) {
663            abstractFuture.interruptTask();
664          }
665          complete(abstractFuture);
666          if (localValue instanceof SetFuture) {
667            // propagate cancellation to the future set in setfuture, this is racy, and we don't
668            // care if we are successful or not.
669            ListenableFuture<?> futureToPropagateTo = ((SetFuture) localValue).future;
670            if (futureToPropagateTo instanceof Trusted) {
671              // If the future is a TrustedFuture then we specifically avoid calling cancel()
672              // this has 2 benefits
673              // 1. for long chains of futures strung together with setFuture we consume less stack
674              // 2. we avoid allocating Cancellation objects at every level of the cancellation
675              //    chain
676              // We can only do this for TrustedFuture, because TrustedFuture.cancel is final and
677              // does nothing but delegate to this method.
678              AbstractFuture<?> trusted = (AbstractFuture<?>) futureToPropagateTo;
679              localValue = trusted.value;
680              if (localValue == null | localValue instanceof SetFuture) {
681                abstractFuture = trusted;
682                continue; // loop back up and try to complete the new future
683              }
684            } else {
685              // not a TrustedFuture, call cancel directly.
686              futureToPropagateTo.cancel(mayInterruptIfRunning);
687            }
688          }
689          break;
690        }
691        // obj changed, reread
692        localValue = abstractFuture.value;
693        if (!(localValue instanceof SetFuture)) {
694          // obj cannot be null at this point, because value can only change from null to non-null.
695          // So if value changed (and it did since we lost the CAS), then it cannot be null and
696          // since it isn't a SetFuture, then the future must be done and we should exit the loop
697          break;
698        }
699      }
700    }
701    return rValue;
702  }
703
704  /**
705   * Subclasses can override this method to implement interruption of the future's computation. The
706   * method is invoked automatically by a successful call to {@link #cancel(boolean) cancel(true)}.
707   *
708   * <p>The default implementation does nothing.
709   *
710   * <p>This method is likely to be deprecated. Prefer to override {@link #afterDone}, consulting
711   * {@link #wasInterrupted} to decide whether to interrupt your task.
712   *
713   * @since 10.0
714   */
715  protected void interruptTask() {}
716
717  /**
718   * Returns true if this future was cancelled with {@code mayInterruptIfRunning} set to {@code
719   * true}.
720   *
721   * @since 14.0
722   */
723  protected final boolean wasInterrupted() {
724    final Object localValue = value;
725    return (localValue instanceof Cancellation) && ((Cancellation) localValue).wasInterrupted;
726  }
727
728  /**
729   * {@inheritDoc}
730   *
731   * @since 10.0
732   */
733  @Override
734  public void addListener(Runnable listener, Executor executor) {
735    checkNotNull(listener, "Runnable was null.");
736    checkNotNull(executor, "Executor was null.");
737    // Checking isDone and listeners != TOMBSTONE may seem redundant, but our contract for
738    // addListener says that listeners execute 'immediate' if the future isDone(). However, our
739    // protocol for completing a future is to assign the value field (which sets isDone to true) and
740    // then to release waiters, followed by executing afterDone(), followed by releasing listeners.
741    // That means that it is possible to observe that the future isDone and that your listeners
742    // don't execute 'immediately'.  By checking isDone here we avoid that.
743    // A corollary to all that is that we don't need to check isDone inside the loop because if we
744    // get into the loop we know that we weren't done when we entered and therefore we aren't under
745    // an obligation to execute 'immediately'.
746    if (!isDone()) {
747      Listener oldHead = listeners;
748      if (oldHead != Listener.TOMBSTONE) {
749        Listener newNode = new Listener(listener, executor);
750        do {
751          newNode.next = oldHead;
752          if (ATOMIC_HELPER.casListeners(this, oldHead, newNode)) {
753            return;
754          }
755          oldHead = listeners; // re-read
756        } while (oldHead != Listener.TOMBSTONE);
757      }
758    }
759    // If we get here then the Listener TOMBSTONE was set, which means the future is done, call
760    // the listener.
761    executeListener(listener, executor);
762  }
763
764  /**
765   * Sets the result of this {@code Future} unless this {@code Future} has already been cancelled or
766   * set (including {@linkplain #setFuture set asynchronously}). When a call to this method returns,
767   * the {@code Future} is guaranteed to be {@linkplain #isDone done} <b>only if</b> the call was
768   * accepted (in which case it returns {@code true}). If it returns {@code false}, the {@code
769   * Future} may have previously been set asynchronously, in which case its result may not be known
770   * yet. That result, though not yet known, cannot be overridden by a call to a {@code set*}
771   * method, only by a call to {@link #cancel}.
772   *
773   * <p>Beware of completing a future while holding a lock. Its listeners may do slow work or
774   * acquire other locks, risking deadlocks.
775   *
776   * @param value the value to be used as the result
777   * @return true if the attempt was accepted, completing the {@code Future}
778   */
779  @CanIgnoreReturnValue
780  protected boolean set(@ParametricNullness V value) {
781    Object valueToSet = value == null ? NULL : value;
782    if (ATOMIC_HELPER.casValue(this, null, valueToSet)) {
783      complete(this);
784      return true;
785    }
786    return false;
787  }
788
789  /**
790   * Sets the failed result of this {@code Future} unless this {@code Future} has already been
791   * cancelled or set (including {@linkplain #setFuture set asynchronously}). When a call to this
792   * method returns, the {@code Future} is guaranteed to be {@linkplain #isDone done} <b>only if</b>
793   * the call was accepted (in which case it returns {@code true}). If it returns {@code false}, the
794   * {@code Future} may have previously been set asynchronously, in which case its result may not be
795   * known yet. That result, though not yet known, cannot be overridden by a call to a {@code set*}
796   * method, only by a call to {@link #cancel}.
797   *
798   * <p>Beware of completing a future while holding a lock. Its listeners may do slow work or
799   * acquire other locks, risking deadlocks.
800   *
801   * @param throwable the exception to be used as the failed result
802   * @return true if the attempt was accepted, completing the {@code Future}
803   */
804  @CanIgnoreReturnValue
805  protected boolean setException(Throwable throwable) {
806    Object valueToSet = new Failure(checkNotNull(throwable));
807    if (ATOMIC_HELPER.casValue(this, null, valueToSet)) {
808      complete(this);
809      return true;
810    }
811    return false;
812  }
813
814  /**
815   * Sets the result of this {@code Future} to match the supplied input {@code Future} once the
816   * supplied {@code Future} is done, unless this {@code Future} has already been cancelled or set
817   * (including "set asynchronously," defined below).
818   *
819   * <p>If the supplied future is {@linkplain #isDone done} when this method is called and the call
820   * is accepted, then this future is guaranteed to have been completed with the supplied future by
821   * the time this method returns. If the supplied future is not done and the call is accepted, then
822   * the future will be <i>set asynchronously</i>. Note that such a result, though not yet known,
823   * cannot be overridden by a call to a {@code set*} method, only by a call to {@link #cancel}.
824   *
825   * <p>If the call {@code setFuture(delegate)} is accepted and this {@code Future} is later
826   * cancelled, cancellation will be propagated to {@code delegate}. Additionally, any call to
827   * {@code setFuture} after any cancellation will propagate cancellation to the supplied {@code
828   * Future}.
829   *
830   * <p>Note that, even if the supplied future is cancelled and it causes this future to complete,
831   * it will never trigger interruption behavior. In particular, it will not cause this future to
832   * invoke the {@link #interruptTask} method, and the {@link #wasInterrupted} method will not
833   * return {@code true}.
834   *
835   * <p>Beware of completing a future while holding a lock. Its listeners may do slow work or
836   * acquire other locks, risking deadlocks.
837   *
838   * @param future the future to delegate to
839   * @return true if the attempt was accepted, indicating that the {@code Future} was not previously
840   *     cancelled or set.
841   * @since 19.0
842   */
843  @CanIgnoreReturnValue
844  protected boolean setFuture(ListenableFuture<? extends V> future) {
845    checkNotNull(future);
846    Object localValue = value;
847    if (localValue == null) {
848      if (future.isDone()) {
849        Object value = getFutureValue(future);
850        if (ATOMIC_HELPER.casValue(this, null, value)) {
851          complete(this);
852          return true;
853        }
854        return false;
855      }
856      SetFuture<V> valueToSet = new SetFuture<V>(this, future);
857      if (ATOMIC_HELPER.casValue(this, null, valueToSet)) {
858        // the listener is responsible for calling completeWithFuture, directExecutor is appropriate
859        // since all we are doing is unpacking a completed future which should be fast.
860        try {
861          future.addListener(valueToSet, DirectExecutor.INSTANCE);
862        } catch (Throwable t) {
863          // addListener has thrown an exception! SetFuture.run can't throw any exceptions so this
864          // must have been caused by addListener itself. The most likely explanation is a
865          // misconfigured mock. Try to switch to Failure.
866          Failure failure;
867          try {
868            failure = new Failure(t);
869          } catch (Throwable oomMostLikely) {
870            failure = Failure.FALLBACK_INSTANCE;
871          }
872          // Note: The only way this CAS could fail is if cancel() has raced with us. That is ok.
873          boolean unused = ATOMIC_HELPER.casValue(this, valueToSet, failure);
874        }
875        return true;
876      }
877      localValue = value; // we lost the cas, fall through and maybe cancel
878    }
879    // The future has already been set to something. If it is cancellation we should cancel the
880    // incoming future.
881    if (localValue instanceof Cancellation) {
882      // we don't care if it fails, this is best-effort.
883      future.cancel(((Cancellation) localValue).wasInterrupted);
884    }
885    return false;
886  }
887
888  /**
889   * Returns a value that satisfies the contract of the {@link #value} field based on the state of
890   * given future.
891   *
892   * <p>This is approximately the inverse of {@link #getDoneValue(Object)}
893   */
894  private static Object getFutureValue(ListenableFuture<?> future) {
895    if (future instanceof Trusted) {
896      // Break encapsulation for TrustedFuture instances since we know that subclasses cannot
897      // override .get() (since it is final) and therefore this is equivalent to calling .get()
898      // and unpacking the exceptions like we do below (just much faster because it is a single
899      // field read instead of a read, several branches and possibly creating exceptions).
900      Object v = ((AbstractFuture<?>) future).value;
901      if (v instanceof Cancellation) {
902        // If the other future was interrupted, clear the interrupted bit while preserving the cause
903        // this will make it consistent with how non-trustedfutures work which cannot propagate the
904        // wasInterrupted bit
905        Cancellation c = (Cancellation) v;
906        if (c.wasInterrupted) {
907          v =
908              c.cause != null
909                  ? new Cancellation(/* wasInterrupted= */ false, c.cause)
910                  : Cancellation.CAUSELESS_CANCELLED;
911        }
912      }
913      // requireNonNull is safe as long as we call this method only on completed futures.
914      return requireNonNull(v);
915    }
916    if (future instanceof InternalFutureFailureAccess) {
917      Throwable throwable =
918          InternalFutures.tryInternalFastPathGetFailure((InternalFutureFailureAccess) future);
919      if (throwable != null) {
920        return new Failure(throwable);
921      }
922    }
923    boolean wasCancelled = future.isCancelled();
924    // Don't allocate a CancellationException if it's not necessary
925    if (!GENERATE_CANCELLATION_CAUSES & wasCancelled) {
926      /*
927       * requireNonNull is safe because we've initialized CAUSELESS_CANCELLED if
928       * !GENERATE_CANCELLATION_CAUSES.
929       */
930      return requireNonNull(Cancellation.CAUSELESS_CANCELLED);
931    }
932    // Otherwise calculate the value by calling .get()
933    try {
934      Object v = getUninterruptibly(future);
935      if (wasCancelled) {
936        return new Cancellation(
937            false,
938            new IllegalArgumentException(
939                "get() did not throw CancellationException, despite reporting "
940                    + "isCancelled() == true: "
941                    + future));
942      }
943      return v == null ? NULL : v;
944    } catch (ExecutionException exception) {
945      if (wasCancelled) {
946        return new Cancellation(
947            false,
948            new IllegalArgumentException(
949                "get() did not throw CancellationException, despite reporting "
950                    + "isCancelled() == true: "
951                    + future,
952                exception));
953      }
954      return new Failure(exception.getCause());
955    } catch (CancellationException cancellation) {
956      if (!wasCancelled) {
957        return new Failure(
958            new IllegalArgumentException(
959                "get() threw CancellationException, despite reporting isCancelled() == false: "
960                    + future,
961                cancellation));
962      }
963      return new Cancellation(false, cancellation);
964    } catch (Throwable t) {
965      return new Failure(t);
966    }
967  }
968
969  /**
970   * An inlined private copy of {@link Uninterruptibles#getUninterruptibly} used to break an
971   * internal dependency on other /util/concurrent classes.
972   */
973  @ParametricNullness
974  private static <V extends @Nullable Object> V getUninterruptibly(Future<V> future)
975      throws ExecutionException {
976    boolean interrupted = false;
977    try {
978      while (true) {
979        try {
980          return future.get();
981        } catch (InterruptedException e) {
982          interrupted = true;
983        }
984      }
985    } finally {
986      if (interrupted) {
987        Thread.currentThread().interrupt();
988      }
989    }
990  }
991
992  /** Unblocks all threads and runs all listeners. */
993  private static void complete(AbstractFuture<?> param) {
994    // Declare a "true" local variable so that the Checker Framework will infer nullness.
995    AbstractFuture<?> future = param;
996
997    Listener next = null;
998    outer:
999    while (true) {
1000      future.releaseWaiters();
1001      // We call this before the listeners in order to avoid needing to manage a separate stack data
1002      // structure for them.  Also, some implementations rely on this running prior to listeners
1003      // so that the cleanup work is visible to listeners.
1004      // afterDone() should be generally fast and only used for cleanup work... but in theory can
1005      // also be recursive and create StackOverflowErrors
1006      future.afterDone();
1007      // push the current set of listeners onto next
1008      next = future.clearListeners(next);
1009      future = null;
1010      while (next != null) {
1011        Listener curr = next;
1012        next = next.next;
1013        /*
1014         * requireNonNull is safe because the listener stack never contains TOMBSTONE until after
1015         * clearListeners.
1016         */
1017        Runnable task = requireNonNull(curr.task);
1018        if (task instanceof SetFuture) {
1019          SetFuture<?> setFuture = (SetFuture<?>) task;
1020          // We unwind setFuture specifically to avoid StackOverflowErrors in the case of long
1021          // chains of SetFutures
1022          // Handling this special case is important because there is no way to pass an executor to
1023          // setFuture, so a user couldn't break the chain by doing this themselves.  It is also
1024          // potentially common if someone writes a recursive Futures.transformAsync transformer.
1025          future = setFuture.owner;
1026          if (future.value == setFuture) {
1027            Object valueToSet = getFutureValue(setFuture.future);
1028            if (ATOMIC_HELPER.casValue(future, setFuture, valueToSet)) {
1029              continue outer;
1030            }
1031          }
1032          // other wise the future we were trying to set is already done.
1033        } else {
1034          /*
1035           * requireNonNull is safe because the listener stack never contains TOMBSTONE until after
1036           * clearListeners.
1037           */
1038          executeListener(task, requireNonNull(curr.executor));
1039        }
1040      }
1041      break;
1042    }
1043  }
1044
1045  /**
1046   * Callback method that is called exactly once after the future is completed.
1047   *
1048   * <p>If {@link #interruptTask} is also run during completion, {@link #afterDone} runs after it.
1049   *
1050   * <p>The default implementation of this method in {@code AbstractFuture} does nothing. This is
1051   * intended for very lightweight cleanup work, for example, timing statistics or clearing fields.
1052   * If your task does anything heavier consider, just using a listener with an executor.
1053   *
1054   * @since 20.0
1055   */
1056  @Beta
1057  @ForOverride
1058  protected void afterDone() {}
1059
1060  // TODO(b/114236866): Inherit doc from InternalFutureFailureAccess. Also, -link to its URL.
1061  /**
1062   * Usually returns {@code null} but, if this {@code Future} has failed, may <i>optionally</i>
1063   * return the cause of the failure. "Failure" means specifically "completed with an exception"; it
1064   * does not include "was cancelled." To be explicit: If this method returns a non-null value,
1065   * then:
1066   *
1067   * <ul>
1068   *   <li>{@code isDone()} must return {@code true}
1069   *   <li>{@code isCancelled()} must return {@code false}
1070   *   <li>{@code get()} must not block, and it must throw an {@code ExecutionException} with the
1071   *       return value of this method as its cause
1072   * </ul>
1073   *
1074   * <p>This method is {@code protected} so that classes like {@code
1075   * com.google.common.util.concurrent.SettableFuture} do not expose it to their users as an
1076   * instance method. In the unlikely event that you need to call this method, call {@link
1077   * InternalFutures#tryInternalFastPathGetFailure(InternalFutureFailureAccess)}.
1078   *
1079   * @since 27.0
1080   */
1081  @Override
1082  /*
1083   * We should annotate the superclass, InternalFutureFailureAccess, to say that its copy of this
1084   * method returns @Nullable, too. However, we're not sure if we want to make any changes to that
1085   * class, since it's in a separate artifact that we planned to release only a single version of.
1086   */
1087  @SuppressWarnings("nullness")
1088  @CheckForNull
1089  protected final Throwable tryInternalFastPathGetFailure() {
1090    if (this instanceof Trusted) {
1091      Object obj = value;
1092      if (obj instanceof Failure) {
1093        return ((Failure) obj).exception;
1094      }
1095    }
1096    return null;
1097  }
1098
1099  /**
1100   * If this future has been cancelled (and possibly interrupted), cancels (and possibly interrupts)
1101   * the given future (if available).
1102   */
1103  final void maybePropagateCancellationTo(@CheckForNull Future<?> related) {
1104    if (related != null & isCancelled()) {
1105      related.cancel(wasInterrupted());
1106    }
1107  }
1108
1109  /** Releases all threads in the {@link #waiters} list, and clears the list. */
1110  private void releaseWaiters() {
1111    Waiter head;
1112    do {
1113      head = waiters;
1114    } while (!ATOMIC_HELPER.casWaiters(this, head, Waiter.TOMBSTONE));
1115    for (Waiter currentWaiter = head; currentWaiter != null; currentWaiter = currentWaiter.next) {
1116      currentWaiter.unpark();
1117    }
1118  }
1119
1120  /**
1121   * Clears the {@link #listeners} list and prepends its contents to {@code onto}, least recently
1122   * added first.
1123   */
1124  @CheckForNull
1125  private Listener clearListeners(@CheckForNull Listener onto) {
1126    // We need to
1127    // 1. atomically swap the listeners with TOMBSTONE, this is because addListener uses that to
1128    //    to synchronize with us
1129    // 2. reverse the linked list, because despite our rather clear contract, people depend on us
1130    //    executing listeners in the order they were added
1131    // 3. push all the items onto 'onto' and return the new head of the stack
1132    Listener head;
1133    do {
1134      head = listeners;
1135    } while (!ATOMIC_HELPER.casListeners(this, head, Listener.TOMBSTONE));
1136    Listener reversedList = onto;
1137    while (head != null) {
1138      Listener tmp = head;
1139      head = head.next;
1140      tmp.next = reversedList;
1141      reversedList = tmp;
1142    }
1143    return reversedList;
1144  }
1145
1146  // TODO(user): move parts into a default method on ListenableFuture?
1147  @Override
1148  public String toString() {
1149    // TODO(cpovirk): Presize to something plausible?
1150    StringBuilder builder = new StringBuilder();
1151    if (getClass().getName().startsWith("com.google.common.util.concurrent.")) {
1152      builder.append(getClass().getSimpleName());
1153    } else {
1154      builder.append(getClass().getName());
1155    }
1156    builder.append('@').append(toHexString(identityHashCode(this))).append("[status=");
1157    if (isCancelled()) {
1158      builder.append("CANCELLED");
1159    } else if (isDone()) {
1160      addDoneString(builder);
1161    } else {
1162      addPendingString(builder); // delegates to addDoneString if future completes mid-way
1163    }
1164    return builder.append("]").toString();
1165  }
1166
1167  /**
1168   * Provide a human-readable explanation of why this future has not yet completed.
1169   *
1170   * @return null if an explanation cannot be provided (e.g. because the future is done).
1171   * @since 23.0
1172   */
1173  @CheckForNull
1174  protected String pendingToString() {
1175    // TODO(diamondm) consider moving this into addPendingString so it's always in the output
1176    if (this instanceof ScheduledFuture) {
1177      return "remaining delay=["
1178          + ((ScheduledFuture) this).getDelay(TimeUnit.MILLISECONDS)
1179          + " ms]";
1180    }
1181    return null;
1182  }
1183
1184  private void addPendingString(StringBuilder builder) {
1185    // Capture current builder length so it can be truncated if this future ends up completing while
1186    // the toString is being calculated
1187    int truncateLength = builder.length();
1188
1189    builder.append("PENDING");
1190
1191    Object localValue = value;
1192    if (localValue instanceof SetFuture) {
1193      builder.append(", setFuture=[");
1194      appendUserObject(builder, ((SetFuture) localValue).future);
1195      builder.append("]");
1196    } else {
1197      String pendingDescription;
1198      try {
1199        pendingDescription = Strings.emptyToNull(pendingToString());
1200      } catch (RuntimeException | StackOverflowError e) {
1201        // Don't call getMessage or toString() on the exception, in case the exception thrown by the
1202        // subclass is implemented with bugs similar to the subclass.
1203        pendingDescription = "Exception thrown from implementation: " + e.getClass();
1204      }
1205      if (pendingDescription != null) {
1206        builder.append(", info=[").append(pendingDescription).append("]");
1207      }
1208    }
1209
1210    // The future may complete while calculating the toString, so we check once more to see if the
1211    // future is done
1212    if (isDone()) {
1213      // Truncate anything that was appended before realizing this future is done
1214      builder.delete(truncateLength, builder.length());
1215      addDoneString(builder);
1216    }
1217  }
1218
1219  private void addDoneString(StringBuilder builder) {
1220    try {
1221      V value = getUninterruptibly(this);
1222      builder.append("SUCCESS, result=[");
1223      appendResultObject(builder, value);
1224      builder.append("]");
1225    } catch (ExecutionException e) {
1226      builder.append("FAILURE, cause=[").append(e.getCause()).append("]");
1227    } catch (CancellationException e) {
1228      builder.append("CANCELLED"); // shouldn't be reachable
1229    } catch (RuntimeException e) {
1230      builder.append("UNKNOWN, cause=[").append(e.getClass()).append(" thrown from get()]");
1231    }
1232  }
1233
1234  /**
1235   * Any object can be the result of a Future, and not every object has a reasonable toString()
1236   * implementation. Using a reconstruction of the default Object.toString() prevents OOMs and stack
1237   * overflows, and helps avoid sensitive data inadvertently ending up in exception messages.
1238   */
1239  private void appendResultObject(StringBuilder builder, @CheckForNull Object o) {
1240    if (o == null) {
1241      builder.append("null");
1242    } else if (o == this) {
1243      builder.append("this future");
1244    } else {
1245      builder
1246          .append(o.getClass().getName())
1247          .append("@")
1248          .append(Integer.toHexString(System.identityHashCode(o)));
1249    }
1250  }
1251
1252  /** Helper for printing user supplied objects into our toString method. */
1253  private void appendUserObject(StringBuilder builder, @CheckForNull Object o) {
1254    // This is some basic recursion detection for when people create cycles via set/setFuture or
1255    // when deep chains of futures exist resulting in a StackOverflowException. We could detect
1256    // arbitrary cycles using a thread local but this should be a good enough solution (it is also
1257    // what jdk collections do in these cases)
1258    try {
1259      if (o == this) {
1260        builder.append("this future");
1261      } else {
1262        builder.append(o);
1263      }
1264    } catch (RuntimeException | StackOverflowError e) {
1265      // Don't call getMessage or toString() on the exception, in case the exception thrown by the
1266      // user object is implemented with bugs similar to the user object.
1267      builder.append("Exception thrown from implementation: ").append(e.getClass());
1268    }
1269  }
1270
1271  /**
1272   * Submits the given runnable to the given {@link Executor} catching and logging all {@linkplain
1273   * RuntimeException runtime exceptions} thrown by the executor.
1274   */
1275  private static void executeListener(Runnable runnable, Executor executor) {
1276    try {
1277      executor.execute(runnable);
1278    } catch (RuntimeException e) {
1279      // Log it and keep going -- bad runnable and/or executor. Don't punish the other runnables if
1280      // we're given a bad one. We only catch RuntimeException because we want Errors to propagate
1281      // up.
1282      log.log(
1283          Level.SEVERE,
1284          "RuntimeException while executing runnable " + runnable + " with executor " + executor,
1285          e);
1286    }
1287  }
1288
1289  private abstract static class AtomicHelper {
1290    /** Non volatile write of the thread to the {@link Waiter#thread} field. */
1291    abstract void putThread(Waiter waiter, Thread newValue);
1292
1293    /** Non volatile write of the waiter to the {@link Waiter#next} field. */
1294    abstract void putNext(Waiter waiter, @CheckForNull Waiter newValue);
1295
1296    /** Performs a CAS operation on the {@link #waiters} field. */
1297    abstract boolean casWaiters(
1298        AbstractFuture<?> future, @CheckForNull Waiter expect, @CheckForNull Waiter update);
1299
1300    /** Performs a CAS operation on the {@link #listeners} field. */
1301    abstract boolean casListeners(
1302        AbstractFuture<?> future, @CheckForNull Listener expect, Listener update);
1303
1304    /** Performs a CAS operation on the {@link #value} field. */
1305    abstract boolean casValue(AbstractFuture<?> future, @CheckForNull Object expect, Object update);
1306  }
1307
1308  /**
1309   * {@link AtomicHelper} based on {@link sun.misc.Unsafe}.
1310   *
1311   * <p>Static initialization of this class will fail if the {@link sun.misc.Unsafe} object cannot
1312   * be accessed.
1313   */
1314  @SuppressWarnings("sunapi")
1315  private static final class UnsafeAtomicHelper extends AtomicHelper {
1316    static final sun.misc.Unsafe UNSAFE;
1317    static final long LISTENERS_OFFSET;
1318    static final long WAITERS_OFFSET;
1319    static final long VALUE_OFFSET;
1320    static final long WAITER_THREAD_OFFSET;
1321    static final long WAITER_NEXT_OFFSET;
1322
1323    static {
1324      sun.misc.Unsafe unsafe = null;
1325      try {
1326        unsafe = sun.misc.Unsafe.getUnsafe();
1327      } catch (SecurityException tryReflectionInstead) {
1328        try {
1329          unsafe =
1330              AccessController.doPrivileged(
1331                  new PrivilegedExceptionAction<sun.misc.Unsafe>() {
1332                    @Override
1333                    public sun.misc.Unsafe run() throws Exception {
1334                      Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
1335                      for (java.lang.reflect.Field f : k.getDeclaredFields()) {
1336                        f.setAccessible(true);
1337                        Object x = f.get(null);
1338                        if (k.isInstance(x)) {
1339                          return k.cast(x);
1340                        }
1341                      }
1342                      throw new NoSuchFieldError("the Unsafe");
1343                    }
1344                  });
1345        } catch (PrivilegedActionException e) {
1346          throw new RuntimeException("Could not initialize intrinsics", e.getCause());
1347        }
1348      }
1349      try {
1350        Class<?> abstractFuture = AbstractFuture.class;
1351        WAITERS_OFFSET = unsafe.objectFieldOffset(abstractFuture.getDeclaredField("waiters"));
1352        LISTENERS_OFFSET = unsafe.objectFieldOffset(abstractFuture.getDeclaredField("listeners"));
1353        VALUE_OFFSET = unsafe.objectFieldOffset(abstractFuture.getDeclaredField("value"));
1354        WAITER_THREAD_OFFSET = unsafe.objectFieldOffset(Waiter.class.getDeclaredField("thread"));
1355        WAITER_NEXT_OFFSET = unsafe.objectFieldOffset(Waiter.class.getDeclaredField("next"));
1356        UNSAFE = unsafe;
1357      } catch (Exception e) {
1358        throwIfUnchecked(e);
1359        throw new RuntimeException(e);
1360      }
1361    }
1362
1363    @Override
1364    void putThread(Waiter waiter, Thread newValue) {
1365      UNSAFE.putObject(waiter, WAITER_THREAD_OFFSET, newValue);
1366    }
1367
1368    @Override
1369    void putNext(Waiter waiter, @CheckForNull Waiter newValue) {
1370      UNSAFE.putObject(waiter, WAITER_NEXT_OFFSET, newValue);
1371    }
1372
1373    /** Performs a CAS operation on the {@link #waiters} field. */
1374    @Override
1375    boolean casWaiters(
1376        AbstractFuture<?> future, @CheckForNull Waiter expect, @CheckForNull Waiter update) {
1377      return UNSAFE.compareAndSwapObject(future, WAITERS_OFFSET, expect, update);
1378    }
1379
1380    /** Performs a CAS operation on the {@link #listeners} field. */
1381    @Override
1382    boolean casListeners(AbstractFuture<?> future, @CheckForNull Listener expect, Listener update) {
1383      return UNSAFE.compareAndSwapObject(future, LISTENERS_OFFSET, expect, update);
1384    }
1385
1386    /** Performs a CAS operation on the {@link #value} field. */
1387    @Override
1388    boolean casValue(AbstractFuture<?> future, @CheckForNull Object expect, Object update) {
1389      return UNSAFE.compareAndSwapObject(future, VALUE_OFFSET, expect, update);
1390    }
1391  }
1392
1393  /** {@link AtomicHelper} based on {@link AtomicReferenceFieldUpdater}. */
1394  @SuppressWarnings("rawtypes")
1395  private static final class SafeAtomicHelper extends AtomicHelper {
1396    final AtomicReferenceFieldUpdater<Waiter, Thread> waiterThreadUpdater;
1397    final AtomicReferenceFieldUpdater<Waiter, Waiter> waiterNextUpdater;
1398    final AtomicReferenceFieldUpdater<AbstractFuture, Waiter> waitersUpdater;
1399    final AtomicReferenceFieldUpdater<AbstractFuture, Listener> listenersUpdater;
1400    final AtomicReferenceFieldUpdater<AbstractFuture, Object> valueUpdater;
1401
1402    SafeAtomicHelper(
1403        AtomicReferenceFieldUpdater<Waiter, Thread> waiterThreadUpdater,
1404        AtomicReferenceFieldUpdater<Waiter, Waiter> waiterNextUpdater,
1405        AtomicReferenceFieldUpdater<AbstractFuture, Waiter> waitersUpdater,
1406        AtomicReferenceFieldUpdater<AbstractFuture, Listener> listenersUpdater,
1407        AtomicReferenceFieldUpdater<AbstractFuture, Object> valueUpdater) {
1408      this.waiterThreadUpdater = waiterThreadUpdater;
1409      this.waiterNextUpdater = waiterNextUpdater;
1410      this.waitersUpdater = waitersUpdater;
1411      this.listenersUpdater = listenersUpdater;
1412      this.valueUpdater = valueUpdater;
1413    }
1414
1415    @Override
1416    void putThread(Waiter waiter, Thread newValue) {
1417      waiterThreadUpdater.lazySet(waiter, newValue);
1418    }
1419
1420    @Override
1421    void putNext(Waiter waiter, @CheckForNull Waiter newValue) {
1422      waiterNextUpdater.lazySet(waiter, newValue);
1423    }
1424
1425    @Override
1426    boolean casWaiters(
1427        AbstractFuture<?> future, @CheckForNull Waiter expect, @CheckForNull Waiter update) {
1428      return waitersUpdater.compareAndSet(future, expect, update);
1429    }
1430
1431    @Override
1432    boolean casListeners(AbstractFuture<?> future, @CheckForNull Listener expect, Listener update) {
1433      return listenersUpdater.compareAndSet(future, expect, update);
1434    }
1435
1436    @Override
1437    boolean casValue(AbstractFuture<?> future, @CheckForNull Object expect, Object update) {
1438      return valueUpdater.compareAndSet(future, expect, update);
1439    }
1440  }
1441
1442  /**
1443   * {@link AtomicHelper} based on {@code synchronized} and volatile writes.
1444   *
1445   * <p>This is an implementation of last resort for when certain basic VM features are broken (like
1446   * AtomicReferenceFieldUpdater).
1447   */
1448  private static final class SynchronizedHelper extends AtomicHelper {
1449    @Override
1450    void putThread(Waiter waiter, Thread newValue) {
1451      waiter.thread = newValue;
1452    }
1453
1454    @Override
1455    void putNext(Waiter waiter, @CheckForNull Waiter newValue) {
1456      waiter.next = newValue;
1457    }
1458
1459    @Override
1460    boolean casWaiters(
1461        AbstractFuture<?> future, @CheckForNull Waiter expect, @CheckForNull Waiter update) {
1462      synchronized (future) {
1463        if (future.waiters == expect) {
1464          future.waiters = update;
1465          return true;
1466        }
1467        return false;
1468      }
1469    }
1470
1471    @Override
1472    boolean casListeners(AbstractFuture<?> future, @CheckForNull Listener expect, Listener update) {
1473      synchronized (future) {
1474        if (future.listeners == expect) {
1475          future.listeners = update;
1476          return true;
1477        }
1478        return false;
1479      }
1480    }
1481
1482    @Override
1483    boolean casValue(AbstractFuture<?> future, @CheckForNull Object expect, Object update) {
1484      synchronized (future) {
1485        if (future.value == expect) {
1486          future.value = update;
1487          return true;
1488        }
1489        return false;
1490      }
1491    }
1492  }
1493
1494  private static CancellationException cancellationExceptionWithCause(
1495      String message, @CheckForNull Throwable cause) {
1496    CancellationException exception = new CancellationException(message);
1497    exception.initCause(cause);
1498    return exception;
1499  }
1500}