Move dependency walker logic to front end.

pkg/front_end/test/src/dependency_walker_test.dart

Index: pkg/front_end/test/src/dependency_walker_test.dart
diff --git a/pkg/front_end/test/src/dependency_walker_test.dart b/pkg/front_end/test/src/dependency_walker_test.dart
new file mode 100644
index 0000000000000000000000000000000000000000..74ed3b26a6835ec7400089709fd859bcdde71f97
--- /dev/null
+++ b/pkg/front_end/test/src/dependency_walker_test.dart
@@ -0,0 +1,215 @@
+import 'package:front_end/src/dependency_walker.dart';
+import 'package:test/test.dart';
+import 'package:test_reflective_loader/test_reflective_loader.dart';
+
+main() {
+  defineReflectiveSuite(() {
+    defineReflectiveTests(DependencyWalkerTest);
+  });
+}
+
+@reflectiveTest
+class DependencyWalkerTest {
+  final nodes = <String, TestNode>{};
+
+  void checkGraph(Map<String, List<String>> graph, String startingNodeName,
+      List<List<String>> expectedEvaluations, List<bool> expectedSccFlags) {
+    makeGraph(graph);
+    var walker = walk(startingNodeName);
+    expect(walker._evaluations, expectedEvaluations.map((x) => x.toSet()));
+    expect(walker._sccFlags, expectedSccFlags);
+  }
+
+  TestNode getNode(String name) =>
+      nodes.putIfAbsent(name, () => new TestNode(name));
+
+  void makeGraph(Map<String, List<String>> graph) {
+    graph.forEach((name, deps) {
+      var node = getNode(name);
+      for (var dep in deps) {
+        node._dependencies.add(getNode(dep));
+      }
+    });
+  }
+
+  void test_complex_graph() {
+    checkGraph(
+        {
+          'a': ['b', 'c'],
+          'b': ['c', 'd'],
+          'c': [],
+          'd': ['c', 'e'],
+          'e': ['b', 'f'],
+          'f': ['c', 'd']
+        },
+        'a',
+        [
+          ['c'],
+          ['b', 'd', 'e', 'f'],
+          ['a']
+        ],
+        [false, true, false]);
+  }
+
+  void test_diamond() {
+    checkGraph(
+        {
+          'a': ['b', 'c'],
+          'b': ['d'],
+          'c': ['d'],
+          'd': []
+        },
+        'a',
+        [
+          ['d'],
+          ['b'],
+          ['c'],
+          ['a']
+        ],
+        [false, false, false, false]);
+  }
+
+  void test_singleNode() {
+    checkGraph(
+        {'a': []},
+        'a',
+        [
+          ['a']
+        ],
+        [false]);
+  }
+
+  void test_singleNodeWithTrivialCycle() {
+    checkGraph(
+        {
+          'a': ['a']
+        },
+        'a',
+        [
+          ['a']
+        ],
+        [true]);
+  }
+
+  void test_threeNodesWithCircularDependency() {
+    checkGraph(
+        {
+          'a': ['b'],
+          'b': ['c'],
+          'c': ['a'],
+        },
+        'a',
+        [
+          ['a', 'b', 'c']
+        ],
+        [true]);
+  }
+
+  test_twoBacklinksEarlierFirst() {
+    // Test a graph A->B->C->D, where D points back to B and then C.
+    checkGraph(
+        {
+          'a': ['b'],
+          'b': ['c'],
+          'c': ['d'],
+          'd': ['b', 'c']
+        },
+        'a',
+        [
+          ['b', 'c', 'd'],
+          ['a']
+        ],
+        [true, false]);
+  }
+
+  test_twoBacklinksLaterFirst() {
+    // Test a graph A->B->C->D, where D points back to C and then B.
+    checkGraph(
+        {
+          'a': ['b'],
+          'b': ['c'],
+          'c': ['d'],
+          'd': ['c', 'b']
+        },
+        'a',
+        [
+          ['b', 'c', 'd'],
+          ['a']
+        ],
+        [true, false]);
+  }
+
+  void test_twoNodesWithCircularDependency() {
+    checkGraph(
+        {
+          'a': ['b'],
+          'b': ['a']
+        },
+        'a',
+        [
+          ['a', 'b']
+        ],
+        [true]);
+  }
+
+  void test_twoNodesWithSimpleDependency() {
+    checkGraph(
+        {
+          'a': ['b'],
+          'b': []
+        },
+        'a',
+        [
+          ['b'],
+          ['a']
+        ],
+        [false, false]);
+  }
+
+  TestWalker walk(String startingNodeName) =>
+      new TestWalker()..walk(getNode(startingNodeName));
+}
+
+class TestNode extends Node<TestNode> {
+  final String _name;
+
+  @override
+  bool isEvaluated = false;
+
+  bool _computeDependenciesCalled = false;
+
+  final _dependencies = <TestNode>[];
+
+  TestNode(this._name);
+
+  @override
+  List<TestNode> computeDependencies() {
+    expect(_computeDependenciesCalled, false);
+    _computeDependenciesCalled = true;
+    return _dependencies;
+  }
+}
+
+class TestWalker extends DependencyWalker<TestNode> {
+  final _evaluations = <Set<String>>[];
+  final _sccFlags = <bool>[];
+
+  @override
+  void evaluate(TestNode v) {
+    v.isEvaluated = true;
+    _evaluations.add([v._name].toSet());
+    _sccFlags.add(false);
+  }
+
+  @override
+  void evaluateScc(List<TestNode> scc) {
+    for (var v in scc) {
+      v.isEvaluated = true;
+    }
+    var sccNames = scc.map((node) => node._name).toSet();
+    // Make sure there were no duplicates
+    expect(sccNames.length, scc.length);
+    _evaluations.add(sccNames);
+    _sccFlags.add(true);
+  }
+}