Avoid O(n^2) behavior in Barback.

pkg/barback/lib/src/phase.dart

 // Copyright (c) 2013, 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.
 
 library barback.phase;
 
 import 'dart:async';
 
 import 'asset_cascade.dart';
 import 'asset_id.dart';
@@ skipping 76 matching lines @@
 
   /// A stream that emits any new assets emitted by [this].
   ///
   /// Assets are emitted synchronously to ensure that any changes are thoroughly
   /// propagated as soon as they occur. Only a phase with no [next] phase will
   /// emit assets.
   Stream<AssetNode> get onAsset => _onAssetController.stream;
   final _onAssetController = new StreamController<AssetNode>(sync: true);
 
   /// Whether [this] is dirty and still has more processing to do.
-  bool get isDirty => _inputs.values.any((input) => input.isDirty) ||
+  ///
+  /// A phase is considered dirty if any of the previous phases in the same
+  /// cascade are dirty, since those phases could emit an asset that this phase
+  /// will then need to process.
+  bool get isDirty => (_previous != null && _previous.isDirty) ||
+      _inputs.values.any((input) => input.isDirty) ||
       _groups.values.any((group) => group.isDirty);
 
-  /// Whether [this] or any previous phase is dirty.
-  bool get _isTransitivelyDirty => isDirty ||
-      (_previous != null && _previous._isTransitivelyDirty);
-
   /// A stream that emits an event whenever any transforms in this phase logs
   /// an entry.
   Stream<LogEntry> get onLog => _onLogPool.stream;
   final _onLogPool = new StreamPool<LogEntry>.broadcast();
 
   /// The previous phase in the cascade, or null if this is the first phase.
   final Phase _previous;
 
+  /// The subscription to [_previous]'s [onDone] stream.
+  StreamSubscription _previousOnDoneSubscription;
+
   /// The phase after this one.
   ///
   /// Outputs from this phase will be passed to it.
   Phase get next => _next;
   Phase _next;
 
   /// A map of asset ids to completers for [getInput] requests.
   ///
   /// If an asset node is requested before it's available, we put a completer in
   /// this map to wait for the asset to be generated. If it's not generated, the
   /// completer should complete to `null`.
   final _pendingOutputRequests = new Map<AssetId, Completer<AssetNode>>();
 
   /// Returns all currently-available output assets for this phase.
   Set<AssetNode> get availableOutputs {
     return _outputs.values
         .map((output) => output.output)
         .where((node) => node.state.isAvailable)
         .toSet();
   }
 
   // TODO(nweiz): Rather than passing the cascade and the phase everywhere,
   // create an interface that just exposes [getInput]. Emit errors via
   // [AssetNode]s.
   Phase(AssetCascade cascade, String location)
       : this._(cascade, location, 0);
 
   Phase._(this.cascade, this._location, this._index, [this._previous]) {
-    // TODO(nweiz): This does O(n^2) work whenever a phase emits an [onDone]
-    // event, since each phase after it has to check each phase before. Find a
-    // better way to do this.
-    for (var phase = this; phase != null; phase = phase._previous) {
-      phase.onDone.listen((_) {
-        if (_isTransitivelyDirty) return;
-
-        // All the previous phases have finished building. If anyone's still
-        // waiting for outputs, cut off the wait; we won't be generating them,
-        // at least until a source asset changes.
-        for (var completer in _pendingOutputRequests.values) {
-          completer.complete(null);
-        }
-        _pendingOutputRequests.clear();
+    if (_previous != null) {
+      _previousOnDoneSubscription = _previous.onDone.listen((_) {
+        if (!isDirty) _onDoneController.add(null);
       });
     }
+
+    onDone.listen((_) {
+      // All the previous phases have finished building. If anyone's still
+      // waiting for outputs, cut off the wait; we won't be generating them,
+      // at least until a source asset changes.
+      for (var completer in _pendingOutputRequests.values) {
+        completer.complete(null);
+      }
+      _pendingOutputRequests.clear();
+    });
   }
 
   /// Adds a new asset as an input for this phase.
   ///
   /// [node] doesn't have to be [AssetState.AVAILABLE]. Once it is, the phase
   /// will automatically begin determining which transforms can consume it as a
   /// primary input. The transforms themselves won't be applied until [process]
   /// is called, however.
   ///
   /// This should only be used for brand-new assets or assets that have been
@@ skipping 77 matching lines @@
         // try again, since it could be generated again.
         output.force();
         return output.whenAvailable((_) => output).catchError((error) {
           if (error is! AssetNotFoundException) throw error;
           return getOutput(id);
         });
       }
 
       // If neither this phase nor the previous phases are dirty, the requested
       // output won't be generated and we can safely return null.
-      if (!_isTransitivelyDirty) return null;
+      if (!isDirty) return null;
 
       // Otherwise, store a completer for the asset node. If it's generated in
       // the future, we'll complete this completer.
       var completer = _pendingOutputRequests.putIfAbsent(id,
           () => new Completer.sync());
       return completer.future;
     });
   }
 
   /// Set this phase's transformers to [transformers].
@@ skipping 64 matching lines @@
     if (_previous != null) _previous._next = null;
     removeFollowing();
     for (var input in _inputs.values.toList()) {
       input.remove();
     }
     for (var group in _groups.values) {
       group.remove();
     }
     _onAssetController.close();
     _onLogPool.close();
+    _previousOnDoneSubscription.cancel();
   }
 
   /// Remove all phases after this one.
   void removeFollowing() {
     if (_next == null) return;
     _next.remove();
     _next = null;
   }
 
   /// Add [asset] as an output of this phase.
@@ skipping 50 matching lines @@
     assert(asset.state.isDirty);
     asset.force();
     asset.whenStateChanges().then((state) {
       if (state.isRemoved) return getOutput(asset.id);
       return asset;
     }).then(request.complete).catchError(request.completeError);
   }
 
   String toString() => "phase $_location.$_index";
 }