pkg/front_end/test/src/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 '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);
  }
}