blob: e00066ffc690ae3dc64c71008db33e79e4cc9fc5 [file] [log] [blame]
// 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.
* Instances of [Node] represent nodes in a dependency graph. The
* type parameter, [NodeType], is the derived type (this affords some
* extra type safety by making it difficult to accidentally construct
* bridges between unrelated dependency graphs).
abstract class Node<NodeType> {
* Index used by Tarjan's strongly connected components algorithm.
* Zero means the node has not been visited yet; a nonzero value
* counts the order in which the node was visited.
int _index = 0;
* Low link used by Tarjan's strongly connected components
* algorithm. This represents the smallest [_index] of all the nodes
* in the strongly connected component to which this node belongs.
int _lowLink = 0;
List<NodeType> _dependencies;
* Indicates whether this node has been evaluated yet.
bool get isEvaluated;
* Compute the dependencies of this node.
List<NodeType> computeDependencies();
* Gets the dependencies of the given node, computing them if necessary.
static List<NodeType> getDependencies<NodeType>(Node<NodeType> node) {
return node._dependencies ??= node.computeDependencies();
* An instance of [DependencyWalker] contains the core algorithms for
* walking a dependency graph and evaluating nodes in a safe order.
abstract class DependencyWalker<NodeType extends Node<NodeType>> {
* Called by [walk] to evaluate a single non-cyclical node, after
* all that node's dependencies have been evaluated.
void evaluate(NodeType v);
* Called by [walk] to evaluate a strongly connected component
* containing one or more nodes. All dependencies of the strongly
* connected component have been evaluated.
void evaluateScc(List<NodeType> scc);
* Walk the dependency graph starting at [startingPoint], finding
* strongly connected components and evaluating them in a safe order
* by calling [evaluate] and [evaluateScc].
* This is an implementation of Tarjan's strongly connected
* components algorithm
* (
void walk(NodeType startingPoint) {
// TODO(paulberry): consider rewriting in a non-recursive way so
// that long dependency chains don't cause stack overflow.
// TODO(paulberry): in the event that an exception occurs during
// the walk, restore the state of the [Node] data structures so
// that further evaluation will be safe.
// The index which will be assigned to the next node that is
// freshly visited.
int index = 1;
// Stack of nodes which have been seen so far and whose strongly
// connected component is still being determined. Nodes are only
// popped off the stack when they are evaluated, so sometimes the
// stack contains nodes that were visited after the current node.
List<NodeType> stack = <NodeType>[];
void strongConnect(NodeType node) {
bool hasTrivialCycle = false;
// Assign the current node an index and add it to the stack. We
// haven't seen any of its dependencies yet, so set its lowLink
// to its index, indicating that so far it is the only node in
// its strongly connected component.
node._index = node._lowLink = index++;
// Consider the node's dependencies one at a time.
for (NodeType dependency in Node.getDependencies(node)) {
// If the dependency has already been evaluated, it can't be
// part of this node's strongly connected component, so we can
// skip it.
if (dependency.isEvaluated) {
if (identical(node, dependency)) {
// If a node includes itself as a dependency, there is no need to
// explore the dependency further.
hasTrivialCycle = true;
} else if (dependency._index == 0) {
// The dependency hasn't been seen yet, so recurse on it.
// If the dependency's lowLink refers to a node that was
// visited before the current node, that means that the
// current node, the dependency, and the node referred to by
// the dependency's lowLink are all part of the same
// strongly connected component, so we need to update the
// current node's lowLink accordingly.
if (dependency._lowLink < node._lowLink) {
node._lowLink = dependency._lowLink;
} else {
// The dependency has already been seen, so it is part of
// the current node's strongly connected component. If it
// was visited earlier than the current node's lowLink, then
// it is a new addition to the current node's strongly
// connected component, so we need to update the current
// node's lowLink accordingly.
if (dependency._index < node._lowLink) {
node._lowLink = dependency._index;
// If the current node's lowLink is the same as its index, then
// we have finished visiting a strongly connected component, so
// pop the stack and evaluate it before moving on.
if (node._lowLink == node._index) {
// The strongly connected component has only one node. If there is a
// cycle, it's a trivial one.
if (identical(stack.last, node)) {
if (hasTrivialCycle) {
} else {
} else {
// There are multiple nodes in the strongly connected
// component.
List<NodeType> scc = <NodeType>[];
while (true) {
NodeType otherNode = stack.removeLast();
if (identical(otherNode, node)) {
// Kick off the algorithm starting with the starting point.