Index: pkg/compiler/tool/graph.dart |
diff --git a/pkg/compiler/tool/graph.dart b/pkg/compiler/tool/graph.dart |
new file mode 100644 |
index 0000000000000000000000000000000000000000..1ef8d9e12d4a50b015bbd3a42071e5f544c88e4c |
--- /dev/null |
+++ b/pkg/compiler/tool/graph.dart |
@@ -0,0 +1,292 @@ |
+// 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 strongest 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? |
+library compiler.tool.graph; |
+ |
+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 = new _SccFinder<N>(this); |
+ return finder.computeTopologicalSort(); |
+ } |
+ |
+ /// Whether [source] can transitively reach [target]. |
+ bool containsPath(N source, N target) { |
+ Set<N> seen = new Set<N>(); |
+ bool helper(N node) { |
+ if (identical(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. |
+ List<N> postOrder(N root) { |
+ var seen = new Set<N>(); |
+ var result = <N>[]; |
+ helper(n) { |
+ if (!seen.add(n)) return; |
+ targetsOf(n).forEach(helper); |
+ result.add(n); |
+ } |
+ helper(root); |
+ return result; |
+ } |
+ |
+ /// Return a list of nodes that form a cycle containing the given node. If the |
+ /// node is not part of this graph, then a list containing only the node |
Johnni Winther
2015/08/18 13:17:11
Shouldn't it be `is not a part of a cycle in this
Siggi Cherem (dart-lang)
2015/08/18 19:13:18
Good point yes
|
+ /// itself will be returned. |
+ List<N> findCycleContaining(N node) { |
+ assert(node != null); |
+ _SccFinder<N> finder = new _SccFinder<N>(this); |
+ return finder._componentContaining(node); |
+ } |
+ |
+ Graph<N> dominatorTree(N root) { |
Johnni Winther
2015/08/18 13:17:11
Add documentation.
Siggi Cherem (dart-lang)
2015/08/18 19:13:17
Done.
|
+ var iDom = (new _DominatorFinder(this)..run(root)).immediateDominators; |
+ var graph = new EdgeListGraph<N>(); |
+ for (N node in iDom.keys) { |
+ if (node != root) graph.addEdge(iDom[node], node); |
+ } |
+ return graph; |
+ } |
+} |
+ |
+class EdgeListGraph<N> extends Graph<N> { |
+ /// Edges in the graph. |
+ Map<N, Set<N>> _edges = new Map<N, Set<N>>(); |
+ |
+ /// The reverse of _edges. |
+ Map<N, Set<N>> _revEdges = new Map<N, Set<N>>(); |
+ |
+ Iterable<N> get nodes => _edges.keys; |
+ bool get isEmpty => _edges.isEmpty; |
+ int get nodeCount => _edges.length; |
+ |
+ final _empty = new Set<N>(); |
+ |
+ Iterable<N> targetsOf(N source) => _edges[source] ?? _empty; |
+ Iterable<N> sourcesOf(N source) => _revEdges[source] ?? _empty; |
+ |
+ void addEdge(N source, N target) { |
+ assert(source != null); |
+ assert(target != null); |
+ addNode(source); |
+ addNode(target); |
+ _edges[source].add(target); |
+ _revEdges[target].add(source); |
+ } |
+ |
+ void addNode(N node) { |
+ assert(node != null); |
+ _edges.putIfAbsent(node, () => new Set<N>()); |
+ _revEdges.putIfAbsent(node, () => new Set<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. |
+ int index = 0; |
+ |
+ /// 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(int depth) |
+ : index = depth, lowlink = depth, 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. |
+ List<N> _stack = new List<N>(); |
+ |
+ /// Information associated with each node. |
+ 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). |
+ List<List<N>> _allComponents = new List<List<N>>(); |
+ |
+ _SccFinder(this._graph) : super(); |
Johnni Winther
2015/08/18 13:17:11
Why the explicit super call?
Siggi Cherem (dart-lang)
2015/08/18 19:13:17
removed, good catch!
(Except for the dominance co
|
+ |
+ /// 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.removeAt(_stack.length - 1); |
+ _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 = new _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 = new List<N>(); |
+ N w; |
+ do { |
+ w = _pop(); |
+ component.add(w); |
+ _info[w].component = component; |
+ } while (!identical(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); |
+ |
+ run(N root) { |
+ immediateDominators[root] = root; |
+ bool changed = true; |
+ int i = 0; |
+ var nodesInPostOrder = _graph.postOrder(root); |
+ 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; |
+ var idom = null; |
+ 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]; |
+ } |
+ while (postOrderId[finger2] < postOrderId[finger1]) { |
+ finger2 = immediateDominators[finger2]; |
+ } |
+ } |
+ return finger1; |
+ } |
+} |