Make chained futures point to their source instead of opposite.

sdk/lib/async/future_impl.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 part of dart.async;
 
 /** The onValue and onError handlers return either a value or a future */
 typedef dynamic _FutureOnValue<T>(T value);
 /** Test used by [Future.catchError] to handle skip some errors. */
 typedef bool _FutureErrorTest(var error);
@@ skipping 77 matching lines @@
   _FutureListener.catchError(this.result,
                              this.errorCallback, _FutureErrorTest test)
       : callback = test,
         state = (test == null) ? STATE_CATCHERROR : STATE_CATCHERROR_TEST;
 
   _FutureListener.whenComplete(this.result, _FutureAction onComplete)
       : callback = onComplete,
         errorCallback = null,
         state = STATE_WHENCOMPLETE;
 
-  _FutureListener.chain(this.result)
-      : callback = null,
-        errorCallback = null,
-        state = STATE_CHAIN;
-
   Zone get _zone => result._zone;
 
   bool get handlesValue => (state & MASK_VALUE != 0);
   bool get handlesError => (state & MASK_ERROR != 0);
   bool get hasErrorTest => (state == STATE_CATCHERROR_TEST);
   bool get handlesComplete => (state == STATE_WHENCOMPLETE);
 
   _FutureOnValue get _onValue {
     assert(handlesValue);
     return callback;
@@ skipping 13 matching lines @@
   /// Initial state, waiting for a result. In this state, the
   /// [resultOrListeners] field holds a single-linked list of
   /// [_FutureListener] listeners.
   static const int _INCOMPLETE = 0;
   /// Pending completion. Set when completed using [_asyncComplete] or
   /// [_asyncCompleteError]. It is an error to try to complete it again.
   /// [resultOrListeners] holds listeners.
   static const int _PENDING_COMPLETE = 1;
   /// The future has been chained to another future. The result of that
   /// other future becomes the result of this future as well.
-  // TODO(floitsch): we don't really need a special "_CHAINED" state. We could
-  // just use the PENDING_COMPLETE state instead.
+  /// [resultOrListeners] contains the source future.
   static const int _CHAINED = 2;
   /// The future has been completed with a value result.
   static const int _VALUE = 4;
   /// The future has been completed with an error result.
   static const int _ERROR = 8;
 
   /** Whether the future is complete, and as what. */
   int _state = _INCOMPLETE;
 
   /**
@@ skipping 12 matching lines @@
    * A result is only stored when the future has completed.
    *
    * The listeners is an internally linked list of [_FutureListener]s.
    * Listeners are only remembered while the future is not yet complete,
    * and it is not chained to another future.
    *
    * The future is another future that his future is chained to. This future
    * is waiting for the other future to complete, and when it does, this future
    * will complete with the same result.
    * All listeners are forwarded to the other future.
-   *
-   * The cases are disjoint - incomplete and unchained ([_INCOMPLETE]),
-   * incomplete and chained ([_CHAINED]), or completed with value or error
-   * ([_VALUE] or [_ERROR]) - so the field only needs to hold
-   * one value at a time.
    */
   var _resultOrListeners;
 
   // This constructor is used by async/await.
   _Future();
 
   /// Valid types for value: `T` or `Future<T>`.
   _Future.immediate(value) {
     _asyncComplete(value);
   }
 
   _Future.immediateError(var error, [StackTrace stackTrace]) {
     _asyncCompleteError(error, stackTrace);
   }
 
   bool get _mayComplete       => _state == _INCOMPLETE;
   bool get _isPendingComplete => _state == _PENDING_COMPLETE;
+  bool get _mayAddListener    => _state <= _PENDING_COMPLETE;
   bool get _isChained         => _state == _CHAINED;
   bool get _isComplete        => _state >= _VALUE;
-  bool get _hasValue          => _state == _VALUE;
   bool get _hasError          => _state == _ERROR;
 
-  void _setChained() {
-    assert(!_isComplete);
+  void _setChained(_Future source) {
+    assert(_mayAddListener);
     _state = _CHAINED;
+    _resultOrListeners = source;
   }
 
   Future then(f(T value), { Function onError }) {
     Zone currentZone = Zone.current;
     if (!identical(currentZone, _ROOT_ZONE)) {
       f = currentZone.registerUnaryCallback(f);
       if (onError != null) {
         onError = _registerErrorHandler(onError, currentZone);
       }
     }
@@ skipping 21 matching lines @@
     _Future result = new _Future<T>();
     if (!identical(result._zone, _ROOT_ZONE)) {
       action = result._zone.registerCallback(action);
     }
     _addListener(new _FutureListener.whenComplete(result, action));
     return result;
   }
 
   Stream<T> asStream() => new Stream<T>.fromFuture(this);
 
-  void _markPendingCompletion() {
-    if (!_mayComplete) throw new StateError("Future already completed");
+  void _setPendingComplete() {
+    assert(_mayComplete);
     _state = _PENDING_COMPLETE;
   }
 
-  T get _value {
-    assert(_isComplete && _hasValue);
+  AsyncError get _error {
+    assert(_hasError);
     return _resultOrListeners;
   }
 
-  AsyncError get _error {
-    assert(_isComplete && _hasError);
+  _Future get _chainSource {
+    assert(_isChained);
     return _resultOrListeners;
   }
 
   // This method is used by async/await.
   void _setValue(T value) {
     assert(!_isComplete);  // But may have a completion pending.
     _state = _VALUE;
     _resultOrListeners = value;
   }
 
   void _setErrorObject(AsyncError error) {
     assert(!_isComplete);  // But may have a completion pending.
     _state = _ERROR;
     _resultOrListeners = error;
   }
 
   void _setError(Object error, StackTrace stackTrace) {
     _setErrorObject(new AsyncError(error, stackTrace));
   }
 
+  /// Copy the completion result of [source] into this future.
+  ///
+  /// Used when a chained future notices that its source is completed.
+  void _cloneResult(_Future source) {
+    assert(!_isComplete);
+    assert(source._isComplete);
+    _state = source._state;
+    _resultOrListeners = source._resultOrListeners;
+  }
+
   void _addListener(_FutureListener listener) {
     assert(listener._nextListener == null);
-    if (_isComplete) {
+    if (_mayAddListener) {
+      listener._nextListener = _resultOrListeners;
+      _resultOrListeners = listener;
+    } else {
+      if (_isChained) {
+        // Delegate listeners to chained source future.
+        // If the source is complete, instead copy its values and
+        // drop the chaining.
+        _Future source = _chainSource;
+        if (!source._isComplete) {
+          source._addListener(listener);
+          return;
+        }
+        _cloneResult(source);
+      }
+      assert(_isComplete);
       // Handle late listeners asynchronously.
       _zone.scheduleMicrotask(() {
         _propagateToListeners(this, listener);
       });
-    } else {
-      listener._nextListener = _resultOrListeners;
-      _resultOrListeners = listener;
     }
   }
 
+  void _prependListeners(_FutureListener listeners) {
+    if (listeners == null) return;
+    if (_mayAddListener) {
+      _FutureListener existingListeners = _resultOrListeners;
+      _resultOrListeners = listeners;
+      if (existingListeners != null) {
+        _FutureListener cursor = listeners;
+        while (cursor._nextListener != null) {
+          cursor = cursor._nextListener;
+        }
+        cursor._nextListener = existingListeners;
+      }
+    } else {
+      if (_isChained) {
+        // Delegate listeners to chained source future.
+        // If the source is complete, instead copy its values and
+        // drop the chaining.
+        _Future source = _chainSource;
+        if (!source._isComplete) {
+          source._prependListeners(listeners);
+          return;
+        }
+        _cloneResult(source);
+      }
+      assert(_isComplete);
+      listeners = _reverseListeners(listeners);
+      _zone.scheduleMicrotask(() {
+        _propagateToListeners(this, listeners);
+      });
+    }
+  }
+
   _FutureListener _removeListeners() {
     // Reverse listeners before returning them, so the resulting list is in
     // subscription order.
     assert(!_isComplete);
     _FutureListener current = _resultOrListeners;
     _resultOrListeners = null;
+    return _reverseListeners(current);
+  }
+
+  _FutureListener _reverseListeners(_FutureListener listeners) {
     _FutureListener prev = null;
+    _FutureListener current = listeners;
     while (current != null) {
       _FutureListener next = current._nextListener;
       current._nextListener = prev;
       prev = current;
       current = next;
     }
     return prev;
   }
 
   // Take the value (when completed) of source and complete target with that
   // value (or error). This function could chain all Futures, but is slower
   // for _Future than _chainCoreFuture, so you must use _chainCoreFuture
   // in that case.
   static void _chainForeignFuture(Future source, _Future target) {
     assert(!target._isComplete);
     assert(source is! _Future);
 
     // Mark the target as chained (and as such half-completed).
-    target._setChained();
+    target._setPendingComplete();
     try {
       source.then((value) {
-          assert(target._isChained);
+          assert(target._isPendingComplete);
           target._completeWithValue(value);
         },
         // TODO(floitsch): eventually we would like to make this non-optional
         // and dependent on the listeners of the target future. If none of
         // the target future's listeners want to have the stack trace we don't
         // need a trace.
         onError: (error, [stackTrace]) {
-          assert(target._isChained);
+          assert(target._isPendingComplete);
           target._completeError(error, stackTrace);
         });
     } catch (e, s) {
       // This only happens if the `then` call threw synchronously when given
       // valid arguments.
       // That requires a non-conforming implementation of the Future interface,
       // which should, hopefully, never happen.
       scheduleMicrotask(() {
         target._completeError(e, s);
       });
     }
   }
 
   // Take the value (when completed) of source and complete target with that
   // value (or error). This function expects that source is a _Future.
   static void _chainCoreFuture(_Future source, _Future target) {
-    assert(!target._isComplete);
-    assert(source is _Future);
-
-    // Mark the target as chained (and as such half-completed).
-    target._setChained();
-    _FutureListener listener = new _FutureListener.chain(target);
+    assert(target._mayAddListener);  // Not completed, not already chained.
+    while (source._isChained) {
+      source = source._chainSource;
+    }
     if (source._isComplete) {
-      _propagateToListeners(source, listener);
+      _FutureListener listeners = target._removeListeners();
+      target._cloneResult(source);
+      _propagateToListeners(target, listeners);
     } else {
-      source._addListener(listener);
+      _FutureListener listeners = target._resultOrListeners;
+      target._setChained(source);
+      source._prependListeners(listeners);
     }
   }
 
   void _complete(value) {
     assert(!_isComplete);
     if (value is Future) {
       if (value is _Future) {
         _chainCoreFuture(value, this);
       } else {
         _chainForeignFuture(value, this);
@@ skipping 38 matching lines @@
     if (value == null) {
       // No checks for `null`.
     } else if (value is Future) {
       // Assign to typed variables so we get earlier checks in checked mode.
       Future<T> typedFuture = value;
       if (typedFuture is _Future) {
         _Future<T> coreFuture = typedFuture;
         if (coreFuture._hasError) {
           // Case 1 from above. Delay completion to enable the user to register
           // callbacks.
-          _markPendingCompletion();
+          _setPendingComplete();
           _zone.scheduleMicrotask(() {
             _chainCoreFuture(coreFuture, this);
           });
         } else {
           _chainCoreFuture(coreFuture, this);
         }
       } else {
         // Case 2 from above. Chain the future immidiately.
         // Note that we are still completing asynchronously (through
         // _chainForeignFuture).
         _chainForeignFuture(typedFuture, this);
       }
       return;
     } else {
       T typedValue = value;
+      assert(typedValue is T);  // Avoid warning that typedValue is unused.
     }
 
-    _markPendingCompletion();
+    _setPendingComplete();
     _zone.scheduleMicrotask(() {
       _completeWithValue(value);
     });
   }
 
   void _asyncCompleteError(error, StackTrace stackTrace) {
     assert(!_isComplete);
 
-    _markPendingCompletion();
+    _setPendingComplete();
     _zone.scheduleMicrotask(() {
       _completeError(error, stackTrace);
     });
   }
 
   /**
    * Propagates the value/error of [source] to its [listeners], executing the
    * listeners' callbacks.
    */
   static void _propagateToListeners(_Future source, _FutureListener listeners) {
@@ skipping 11 matching lines @@
       // Usually futures only have one listener. If they have several, we
       // call handle them separately in recursive calls, continuing
       // here only when there is only one listener left.
       while (listeners._nextListener != null) {
         _FutureListener listener = listeners;
         listeners = listener._nextListener;
         listener._nextListener = null;
         _propagateToListeners(source, listener);
       }
       _FutureListener listener = listeners;
+      final sourceResult = source._resultOrListeners;
       // Do the actual propagation.
       // Set initial state of listenerHasError and listenerValueOrError. These
       // variables are updated with the outcome of potential callbacks.
+      // Non-error results, including futures, are stored in
+      // listenerValueOrError and listenerHasError is set to false. Errors
+      // are stored in listenerValueOrError as an [AsyncError] and
+      // listenerHasError is set to true.
       bool listenerHasError = hasError;
-      final sourceResult = source._resultOrListeners;
       var listenerValueOrError = sourceResult;
 
       // Only if we either have an error or callbacks, go into this, somewhat
       // expensive, branch. Here we'll enter/leave the zone. Many futures
       // don't have callbacks, so this is a significant optimization.
       if (hasError || listener.handlesValue || listener.handlesComplete) {
         Zone zone = listener._zone;
         if (hasError && !source._zone.inSameErrorZone(zone)) {
           // Don't cross zone boundaries with errors.
           AsyncError asyncError = source._error;
@@ skipping 110 matching lines @@
 
         // If the listener's value is a future we need to chain it. Note that
         // this can only happen if there is a callback.
         if (listenerValueOrError is Future) {
           Future chainSource = listenerValueOrError;
           // Shortcut if the chain-source is already completed. Just continue
           // the loop.
           _Future result = listener.result;
           if (chainSource is _Future) {
             if (chainSource._isComplete) {
-              // propagate the value (simulating a tail call).
-              result._setChained();
+              listeners = result._removeListeners();
+              result._cloneResult(chainSource);
               source = chainSource;
-              listeners = new _FutureListener.chain(result);
               continue;
             } else {
               _chainCoreFuture(chainSource, result);
             }
           } else {
             _chainForeignFuture(chainSource, result);
           }
           return;
         }
       }
@@ skipping 37 matching lines @@
       }
     }, onError: (e, s) {
       if (timer.isActive) {
         timer.cancel();
         result._completeError(e, s);
       }
     });
     return result;
   }
 }