Add an async version of dependency_walker.dart.

pkg/front_end/test/src/async_dependency_walker_test.dart

+// Copyright (c) 2016, 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.
+
+import 'dart:async';
+
+import 'package:front_end/src/async_dependency_walker.dart';
+import 'package:test/test.dart';
+import 'package:test_reflective_loader/test_reflective_loader.dart';
+
+main() {
+  defineReflectiveSuite(() {
+    defineReflectiveTests(AsyncDependencyWalkerTest);
+  });
+}
+
+@reflectiveTest
+class AsyncDependencyWalkerTest {
+  final nodes = <String, TestNode>{};
+
+  Future checkGraph(
+      Map<String, List<String>> graph,
+      String startingNodeName,
+      List<List<String>> expectedEvaluations,
+      List<bool> expectedSccFlags) async {
+    makeGraph(graph);
+    var walker = await 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));
+      }
+    });
+  }
+
+  Future test_complex_graph() async {

[scheglov, 2016/12/06 19:24:14]

For tests I usually don't specify the Future return type.
It's OK it keep it too thought.
Just curious if there is a benefit.

[Paul Berry, 2016/12/06 20:28:45]

No benefit I'm aware of.  I went ahead and removed them.

+    await 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]);
+  }
+
+  Future test_diamond() async {
+    await checkGraph(
+        {
+          'a': ['b', 'c'],
+          'b': ['d'],
+          'c': ['d'],
+          'd': []
+        },
+        'a',
+        [
+          ['d'],
+          ['b'],
+          ['c'],
+          ['a']
+        ],
+        [false, false, false, false]);
+  }
+
+  Future test_singleNode() async {
+    await checkGraph(
+        {'a': []},
+        'a',
+        [
+          ['a']
+        ],
+        [false]);
+  }
+
+  Future test_singleNodeWithTrivialCycle() async {
+    await checkGraph(
+        {
+          'a': ['a']
+        },
+        'a',
+        [
+          ['a']
+        ],
+        [true]);
+  }
+
+  Future test_threeNodesWithCircularDependency() async {
+    await checkGraph(
+        {
+          'a': ['b'],
+          'b': ['c'],
+          'c': ['a'],
+        },
+        'a',
+        [
+          ['a', 'b', 'c']
+        ],
+        [true]);
+  }
+
+  Future test_twoBacklinksEarlierFirst() async {
+    // Test a graph A->B->C->D, where D points back to B and then C.
+    await checkGraph(
+        {
+          'a': ['b'],
+          'b': ['c'],
+          'c': ['d'],
+          'd': ['b', 'c']
+        },
+        'a',
+        [
+          ['b', 'c', 'd'],
+          ['a']
+        ],
+        [true, false]);
+  }
+
+  Future test_twoBacklinksLaterFirst() async {
+    // Test a graph A->B->C->D, where D points back to C and then B.
+    await checkGraph(
+        {
+          'a': ['b'],
+          'b': ['c'],
+          'c': ['d'],
+          'd': ['c', 'b']
+        },
+        'a',
+        [
+          ['b', 'c', 'd'],
+          ['a']
+        ],
+        [true, false]);
+  }
+
+  Future test_twoNodesWithCircularDependency() async {
+    await checkGraph(
+        {
+          'a': ['b'],
+          'b': ['a']
+        },
+        'a',
+        [
+          ['a', 'b']
+        ],
+        [true]);
+  }
+
+  Future test_twoNodesWithSimpleDependency() async {
+    await checkGraph(
+        {
+          'a': ['b'],
+          'b': []
+        },
+        'a',
+        [
+          ['b'],
+          ['a']
+        ],
+        [false, false]);
+  }
+
+  Future<TestWalker> walk(String startingNodeName) async {
+    var testWalker = new TestWalker();
+    await testWalker.walk(getNode(startingNodeName));
+    return testWalker;
+  }
+}
+
+class TestNode extends Node<TestNode> {
+  final String _name;
+
+  bool _computeDependenciesCalled = false;
+
+  final _dependencies = <TestNode>[];
+
+  TestNode(this._name);
+
+  @override
+  Future<List<TestNode>> computeDependencies() async {
+    expect(_computeDependenciesCalled, false);
+    _computeDependenciesCalled = true;
+    return _dependencies;
+  }
+}
+
+class TestWalker extends AsyncDependencyWalker<TestNode> {
+  final _evaluations = <Set<String>>[];
+  final _sccFlags = <bool>[];
+
+  @override
+  Future evaluate(TestNode v) async {
+    _evaluations.add([v._name].toSet());
+    _sccFlags.add(false);
+  }
+
+  @override
+  Future evaluateScc(List<TestNode> scc) async {
+    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);
+  }
+}