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 a106441e327e19734a5f5c17c60d8b4912d25bac..6c20801c3ef0e399da921e82cb6557fab1d5997a 100644
--- a/pkg/barback/lib/src/phase.dart
+++ b/pkg/barback/lib/src/phase.dart
@@ -94,13 +94,10 @@ class Phase {
   final _onAssetController = new StreamController<AssetNode>(sync: true);
 
   /// Whether [this] is dirty and still has more processing to do.

[Bob Nystrom, 2014/03/07 17:05:58]

Add a bit here explaining that a phase is if it's doing work or its previous
phase is dirty.

[nweiz, 2014/03/07 19:39:58]

Done.

-  bool get isDirty => _inputs.values.any((input) => input.isDirty) ||
+  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 +106,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 _previousSubscription;

[Bob Nystrom, 2014/03/07 17:05:58]

_previousOnDoneSubscription?

[nweiz, 2014/03/07 19:39:58]

Done.

+
   /// The phase after this one.
   ///
   /// Outputs from this phase will be passed to it.
@@ -137,22 +137,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) {
+      _previousSubscription = _previous.onDone.listen((_) {
+        if (!isDirty) _onDoneController.add(null);
       });
     }
+
+    this.onDone.listen((_) {

[Bob Nystrom, 2014/03/07 17:05:58]

Remove "this.".

[nweiz, 2014/03/07 19:39:58]

Done.

+      // 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 +249,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 +334,7 @@ class Phase {
     }
     _onAssetController.close();
     _onLogPool.close();
+    _previousSubscription.cancel();
   }
 
   /// Remove all phases after this one.