pkg/dart2js_info/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 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;

import 'dart:math' as math;

abstract class Graph<N> {
  Iterable<N> get nodes;
  bool get isEmpty;
  int get nodeCount;
  Iterable<N> targetsOf(N source);
  Iterable<N> sourcesOf(N source);

  /// Run a topological sort of the graph. Since the graph may contain cycles,
  /// this results in a list of strongly connected components rather than a list
  /// of nodes. The nodes in each strongly connected components only have edges
  /// that point to nodes in the same component or earlier components.
  List<List<N>> computeTopologicalSort() {
    _SccFinder<N> finder = _SccFinder<N>(this);
    return finder.computeTopologicalSort();
  }

  /// Whether [source] can transitively reach [target].
  bool containsPath(N source, N target) {
    Set<N> seen = <N>{};
    bool helper(N node) {
      if (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.
  Iterable<N> postOrder(N root) sync* {
    var seen = <N>{};
    Iterable<N> helper(N n) sync* {
      if (!seen.add(n)) return;
      for (var x in targetsOf(n)) {
        yield* helper(x);
      }
      yield n;
    }

    yield* helper(root);
  }

  /// Returns an iterable of all nodes reachable from [root] in preorder.
  Iterable<N> preOrder(N root) sync* {
    var seen = <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) {
    _SccFinder<N> finder = _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:
  ///
  ///       root
  ///       /   \
  ///      a     b
  ///      |    / \
  ///      c   d   e
  ///       \ / \ /
  ///        f   g
  ///
  /// Produces this tree:
  ///
  ///       root
  ///       /|  \
  ///      a |   b
  ///      | |  /|\
  ///      c | d | e
  ///        |   |
  ///        f   g
  ///
  /// Internally we compute dominators using (Cooper, Harvey, and Kennedy's
  /// algorithm)[http://www.cs.rice.edu/~keith/EMBED/dom.pdf].
  Graph<N> dominatorTree(N root) {
    final iDom = (_DominatorFinder(this)..run(root)).immediateDominators;
    final graph = EdgeListGraph<N>();
    for (N node in iDom.keys) {
      if (node != root) graph.addEdge(iDom[node] as N, node);
    }
    return graph;
  }
}

class EdgeListGraph<N> extends Graph<N> {
  /// Edges in the graph.
  final Map<N, Set<N>> _edges = <N, Set<N>>{};

  /// The reverse of _edges.
  final Map<N, Set<N>> _revEdges = <N, Set<N>>{};

  @override
  Iterable<N> get nodes => _edges.keys;
  @override
  bool get isEmpty => _edges.isEmpty;
  @override
  int get nodeCount => _edges.length;

  @override
  Iterable<N> targetsOf(N source) => _edges[source] ?? const Iterable.empty();
  @override
  Iterable<N> sourcesOf(N source) =>
      _revEdges[source] ?? const Iterable.empty();

  void addEdge(N source, N target) {
    addNode(source);
    addNode(target);
    _edges[source]!.add(target);
    _revEdges[target]!.add(source);
  }

  void addNode(N node) {
    _edges.putIfAbsent(node, () => <N>{});
    _revEdges.putIfAbsent(node, () => <N>{});
  }

  /// Remove the edge from the given [source] node to the given [target] node.
  /// If there was no such edge then the graph will be unmodified: the number of
  /// edges will be the same and the set of nodes will be the same (neither node
  /// will either be added or removed).
  void removeEdge(N source, N target) {
    _edges[source]?.remove(target);
  }

  /// Remove the given node from this graph. As a consequence, any edges for
  /// which that node was either a head or a tail will also be removed.
  void removeNode(N node) {
    _edges.remove(node);
    var sources = _revEdges[node];
    if (sources == null) return;
    for (var source in sources) {
      _edges[source]!.remove(node);
    }
  }

  /// Remove all of the given nodes from this graph. As a consequence, any edges
  /// for which those nodes were either a head or a tail will also be removed.
  void removeAllNodes(List<N> nodes) => nodes.forEach(removeNode);
}

/// Used by the [SccFinder] to maintain information about the nodes that have
/// been examined. There is an instance of this class per node in the graph.
class _NodeInfo<N> {
  /// Depth of the node corresponding to this info.
  final int index;

  /// Depth of the first node in a cycle.
  int lowlink = 0;

  /// Whether the corresponding node is on the stack. Used to remove the need
  /// for searching a collection for the node each time the question needs to be
  /// asked.
  bool onStack = false;

  /// Component that contains the corresponding node.
  List<N>? component;

  _NodeInfo(this.index) : lowlink = index, onStack = false;
}

/// Implements Tarjan's Algorithm for finding the strongly connected components
/// in a graph.
class _SccFinder<N> {
  /// The graph to process.
  final Graph<N> _graph;

  /// The index used to uniquely identify the depth of nodes.
  int _index = 0;

  /// Nodes that are being visited in order to identify components.
  final List<N> _stack = <N>[];

  /// Information associated with each node.
  final Map<N, _NodeInfo<N>> _info = <N, _NodeInfo<N>>{};

  /// All strongly connected components found, in topological sort order (each
  /// node in a strongly connected component only has edges that point to nodes
  /// in the same component or earlier components).
  final List<List<N>> _allComponents = <List<N>>[];

  _SccFinder(this._graph);

  /// Return a list containing the nodes that are part of the strongly connected
  /// component that contains the given node.
  List<N>? _componentContaining(N node) => _strongConnect(node).component;

  /// Run Tarjan's algorithm and return the resulting list of strongly connected
  /// components. The list is in topological sort order (each node in a strongly
  /// connected component only has edges that point to nodes in the same
  /// component or earlier components).
  List<List<N>> computeTopologicalSort() {
    for (N node in _graph.nodes) {
      var nodeInfo = _info[node];
      if (nodeInfo == null) _strongConnect(node);
    }
    return _allComponents;
  }

  /// Remove and return the top-most element from the stack.
  N _pop() {
    N node = _stack.removeLast();
    _info[node]!.onStack = false;
    return node;
  }

  /// Add the given node to the stack.
  void _push(N node) {
    _info[node]!.onStack = true;
    _stack.add(node);
  }

  /// Compute the strongly connected component that contains the given node as
  /// well as any components containing nodes that are reachable from the given
  /// component.
  _NodeInfo<N> _strongConnect(N v) {
    // Set the depth index for v to the smallest unused index
    var vInfo = _NodeInfo<N>(_index++);
    _info[v] = vInfo;
    _push(v);

    for (N w in _graph.targetsOf(v)) {
      var wInfo = _info[w];
      if (wInfo == null) {
        // Successor w has not yet been visited; recurse on it
        wInfo = _strongConnect(w);
        vInfo.lowlink = math.min(vInfo.lowlink, wInfo.lowlink);
      } else if (wInfo.onStack) {
        // Successor w is in stack S and hence in the current SCC
        vInfo.lowlink = math.min(vInfo.lowlink, wInfo.index);
      }
    }

    // If v is a root node, pop the stack and generate an SCC
    if (vInfo.lowlink == vInfo.index) {
      var component = <N>[];
      N w;
      do {
        w = _pop();
        component.add(w);
        _info[w]!.component = component;
      } while (w != v);
      _allComponents.add(component);
    }
    return vInfo;
  }
}

/// Computes dominators using (Cooper, Harvey, and Kennedy's
/// algorithm)[http://www.cs.rice.edu/~keith/EMBED/dom.pdf].
class _DominatorFinder<N> {
  final Graph<N> _graph;
  Map<N, N> immediateDominators = {};
  Map<N, int> postOrderId = {};
  _DominatorFinder(this._graph);

  void run(N root) {
    immediateDominators[root] = root;
    bool changed = true;
    int i = 0;
    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;
        late N idom;
        for (var p in _graph.sourcesOf(n)) {
          if (immediateDominators[p] != null) {
            if (first) {
              idom = p;
              first = false;
            } else {
              idom = _intersect(p, idom);
            }
          }
        }
        if (immediateDominators[n] != idom) {
          immediateDominators[n] = idom;
          changed = true;
        }
      }
    }
  }

  N _intersect(N b1, N b2) {
    var finger1 = b1;
    var finger2 = b2;
    while (finger1 != finger2) {
      while (postOrderId[finger1]! < postOrderId[finger2]!) {
        finger1 = immediateDominators[finger1] as N;
      }
      while (postOrderId[finger2]! < postOrderId[finger1]!) {
        finger2 = immediateDominators[finger2] as N;
      }
    }
    return finger1;
  }
}