Avoid O(n^2) behavior in Barback.

pkg/barback/lib/src/phase.dart

Index: pkg/barback/lib/src/phase.dart
diff --git a/pkg/barback/lib/src/phase.dart b/pkg/barback/lib/src/phase.dart
index a240f06865f29b371ec7f3aed3393f60f9f899de..f78e0ca3b1cc959ac7d8f14630907746cbcde77c 100644
--- a/pkg/barback/lib/src/phase.dart
+++ b/pkg/barback/lib/src/phase.dart
@@ -94,13 +94,14 @@ class Phase {
   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;
@@ -109,6 +110,9 @@ class Phase {
   /// 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.
@@ -137,22 +141,21 @@ class Phase {
       : 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.
@@ -250,7 +253,7 @@ class Phase {
 
       // 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.
@@ -335,6 +338,7 @@ class Phase {
     }
     _onAssetController.close();
     _onLogPool.close();
+    _previousOnDoneSubscription.cancel();
   }
 
   /// Remove all phases after this one.