include fields in verify_deps, refactor graph dfs

lib/src/graph.dart

 // Copyright (c) 2015, 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.
 
 /// A library to work with graphs. It contains a couple algorithms, including
-/// Tarjan's algorithm to compute strongest connected components in a graph and
+/// Tarjan's algorithm to compute strongly connected components in a graph and
 /// Cooper et al's dominator algorithm.
 ///
 /// Portions of the code in this library was adapted from
 /// `package:analyzer/src/generated/collection_utilities.dart`.
 // TODO(sigmund): move this into a shared place, like quiver?
 library dart2js_info.src.graph;
 
 import 'dart:math' as math;
 
 abstract class Graph<N> {
@@ skipping 22 matching lines @@
     }
     return helper(source);
   }
 
   /// Returns all nodes reachable from [root] in post order.
   List<N> postOrder(N root) {
     var seen = new Set<N>();
     var result = <N>[];
     helper(n) {
       if (!seen.add(n)) return;
       targetsOf(n).forEach(helper);

[Siggi Cherem (dart-lang), 2015/10/16 23:07:41]

should we switch this implementation to avoid recursion as well?

[Harry Terkelsen, 2015/10/19 22:11:12]

I've refactored it to use yield*, what do you think?

       result.add(n);
     }
     helper(root);
     return result;
   }
 
-  /// Return a list of nodes that form a cycle containing the given node. If the
-  /// node is not part of a cycle in this graph, then a list containing only the
-  /// node itself will be returned.
+  /// Returns an iterable of all nodes reachable from [root].

[Siggi Cherem (dart-lang), 2015/10/16 23:07:41]

maybe indicate that they are in preorder?

[Harry Terkelsen, 2015/10/19 22:11:12]

Done.

+  Iterable<N> reachableFrom(N root) sync* {

[Siggi Cherem (dart-lang), 2015/10/16 23:07:41]

maybe rename this and/or `postOrder` above so we have a consistent naming
convention among the two?

[Harry Terkelsen, 2015/10/19 22:11:12]

Done.

+    var seen = new Set<N>();
+    var stack = <N>[root];
+    while (!stack.isEmpty) {
+      var next = stack.removeLast();
+      seen.add(next);
+      yield next;

[Siggi Cherem (dart-lang), 2015/10/16 23:07:41]

nice use of sync*/yield :)

[Harry Terkelsen, 2015/10/19 22:11:12]

thanks!

+      stack.addAll(targetsOf(next).where((x) => !seen.contains(x)));
+    }
+  }
+
+  /// Returns a list of nodes that form a cycle containing the given node. If
+  /// the node is not part of a cycle in this graph, then a list containing only
+  /// the node itself will be returned.
   List<N> findCycleContaining(N node) {
     assert(node != null);
     _SccFinder<N> finder = new _SccFinder<N>(this);
     return finder._componentContaining(node);
   }
 
   /// Returns a dominator tree starting from root. This is a new graph, with the
   /// same nodes as this graph, but where edges exist between a node and the
   /// nodes it immediately dominates. For example, this graph:
   ///
@@ skipping 240 matching lines @@
       while (postOrderId[finger1] < postOrderId[finger2]) {
         finger1 = immediateDominators[finger1];
       }
       while (postOrderId[finger2] < postOrderId[finger1]) {
         finger2 = immediateDominators[finger2];
       }
     }
     return finger1;
   }
 }