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 17 matching lines @@
     Set<N> seen = new Set<N>();
     bool helper(N node) {
       if (identical(node, target)) return true;
       if (!seen.add(node)) return false;
       return targetsOf(node).any(helper);
     }
     return helper(source);
   }
 
   /// Returns all nodes reachable from [root] in post order.
-  List<N> postOrder(N root) {
+  Iterable<N> postOrder(N root) sync* {
     var seen = new Set<N>();
-    var result = <N>[];
-    helper(n) {
+    Iterable<N> helper(n) sync* {
       if (!seen.add(n)) return;
-      targetsOf(n).forEach(helper);
-      result.add(n);
+      for (var x in targetsOf(n)) {
+        yield* helper(x);
+      }
+      yield n;
     }
-    helper(root);
-    return result;
+    yield* helper(root);
   }
 
-  /// 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] in preorder.
+  Iterable<N> preOrder(N root) sync* {
+    var seen = new Set<N>();
+    var stack = <N>[root];
+    while (stack.isNotEmpty) {
+      var next = stack.removeLast();
+      if (!seen.contains(next)) {
+        seen.add(next);
+        yield next;
+        stack.addAll(targetsOf(next));
+      }
+    }
+  }
+
+  /// 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 197 matching lines @@
 class _DominatorFinder<N> {
   final Graph<N> _graph;
   Map<N, N> immediateDominators = {};
   Map<N, int> postOrderId = {};
   _DominatorFinder(this._graph);
 
   run(N root) {
     immediateDominators[root] = root;
     bool changed = true;
     int i = 0;
-    var nodesInPostOrder = _graph.postOrder(root);
+    var nodesInPostOrder = _graph.postOrder(root).toList();
     for (var n in nodesInPostOrder) {
       postOrderId[n] = i++;
     }
     var nodesInReversedPostOrder = nodesInPostOrder.reversed;
     while (changed) {
       changed = false;
       for (var n in nodesInReversedPostOrder) {
         if (n == root) continue;
         bool first = true;
         var idom = null;
@@ skipping 22 matching lines @@
       while (postOrderId[finger1] < postOrderId[finger2]) {
         finger1 = immediateDominators[finger1];
       }
       while (postOrderId[finger2] < postOrderId[finger1]) {
         finger2 = immediateDominators[finger2];
       }
     }
     return finger1;
   }
 }