pkg/_fe_analyzer_shared/test/util/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:_fe_analyzer_shared/src/util/dependency_walker.dart';
import 'package:test/test.dart';

main() {
  late Map<String, TestNode> nodes;
  setUp(() {
    nodes = {};
  });

  TestNode getNode(String name) =>
      nodes.putIfAbsent(name, () => 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));
      }
    });
  }

  TestWalker walk(String startingNodeName) =>
      TestWalker()..walk(getNode(startingNodeName));

  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);
  }

  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],
    );
  });

  test('Diamond', () {
    checkGraph(
      {
        'a': ['b', 'c'],
        'b': ['d'],
        'c': ['d'],
        'd': [],
      },
      'a',
      [
        ['d'],
        ['b'],
        ['c'],
        ['a'],
      ],
      [false, false, false, false],
    );
  });

  test('Single node', () {
    checkGraph(
      {'a': []},
      'a',
      [
        ['a'],
      ],
      [false],
    );
  });

  test('Single node with trivial cycle', () {
    checkGraph(
      {
        'a': ['a'],
      },
      'a',
      [
        ['a'],
      ],
      [true],
    );
  });

  test('Three nodes with circular dependency', () {
    checkGraph(
      {
        'a': ['b'],
        'b': ['c'],
        'c': ['a'],
      },
      'a',
      [
        ['a', 'b', 'c'],
      ],
      [true],
    );
  });

  group('Two backlinks:', () {
    test('earlier first', () {
      // 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('later first', () {
      // 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],
      );
    });
  });

  test('Two nodes with circular dependency', () {
    checkGraph(
      {
        'a': ['b'],
        'b': ['a'],
      },
      'a',
      [
        ['a', 'b'],
      ],
      [true],
    );
  });

  test('Two nodes with simple dependency', () {
    checkGraph(
      {
        'a': ['b'],
        'b': [],
      },
      'a',
      [
        ['b'],
        ['a'],
      ],
      [false, false],
    );
  });

  test('Do not revisit already-evaluated nodes', () {
    makeGraph({
      'a': ['b'],
      'b': [],
    });
    var walker = TestWalker();
    var a = getNode('a');
    walker.walk(a);
    expect(walker._evaluations, hasLength(2));
    walker.walk(a);
    expect(walker._evaluations, hasLength(2));
  });
}

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});
    _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);
  }
}