| OLD | NEW |
| 1 // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 /** | 5 /** |
| 6 * Instances of [Node] represent nodes in a dependency graph. The | 6 * Instances of [Node] represent nodes in a dependency graph. The |
| 7 * type parameter, [NodeType], is the derived type (this affords some | 7 * type parameter, [NodeType], is the derived type (this affords some |
| 8 * extra type safety by making it difficult to accidentally construct | 8 * extra type safety by making it difficult to accidentally construct |
| 9 * bridges between unrelated dependency graphs). | 9 * bridges between unrelated dependency graphs). |
| 10 */ | 10 */ |
| 11 abstract class Node<NodeType> { | 11 abstract class Node<NodeType> { |
| 12 /** | 12 /** |
| 13 * Index used by Tarjan's strongly connected components algorithm. | 13 * Index used by Tarjan's strongly connected components algorithm. |
| 14 * Zero means the node has not been visited yet; a nonzero value | 14 * Zero means the node has not been visited yet; a nonzero value |
| 15 * counts the order in which the node was visited. | 15 * counts the order in which the node was visited. |
| 16 */ | 16 */ |
| 17 int _index = 0; | 17 int _index = 0; |
| 18 | 18 |
| 19 /** | 19 /** |
| 20 * Low link used by Tarjan's strongly connected components | 20 * Low link used by Tarjan's strongly connected components |
| 21 * algorithm. This represents the smallest [_index] of all the nodes | 21 * algorithm. This represents the smallest [_index] of all the nodes |
| 22 * in the strongly connected component to which this node belongs. | 22 * in the strongly connected component to which this node belongs. |
| 23 */ | 23 */ |
| 24 int _lowLink = 0; | 24 int _lowLink = 0; |
| 25 | 25 |
| 26 List<NodeType> _dependencies; | 26 List<NodeType> _dependencies; |
| 27 | 27 |
| 28 /** | 28 /** |
| 29 * Retrieve the dependencies of this node. | |
| 30 */ | |
| 31 List<NodeType> get dependencies => _dependencies ??= computeDependencies(); | |
| 32 | |
| 33 /** | |
| 34 * Indicates whether this node has been evaluated yet. | 29 * Indicates whether this node has been evaluated yet. |
| 35 */ | 30 */ |
| 36 bool get isEvaluated; | 31 bool get isEvaluated; |
| 37 | 32 |
| 38 /** | 33 /** |
| 39 * Compute the dependencies of this node. | 34 * Compute the dependencies of this node. |
| 40 */ | 35 */ |
| 41 List<NodeType> computeDependencies(); | 36 List<NodeType> computeDependencies(); |
| 37 |
| 38 /** |
| 39 * Gets the dependencies of the given node, computing them if necessary. |
| 40 */ |
| 41 static List<NodeType> getDependencies<NodeType>(Node<NodeType> node) { |
| 42 return node._dependencies ??= node.computeDependencies(); |
| 43 } |
| 42 } | 44 } |
| 43 | 45 |
| 44 /** | 46 /** |
| 45 * An instance of [DependencyWalker] contains the core algorithms for | 47 * An instance of [DependencyWalker] contains the core algorithms for |
| 46 * walking a dependency graph and evaluating nodes in a safe order. | 48 * walking a dependency graph and evaluating nodes in a safe order. |
| 47 */ | 49 */ |
| 48 abstract class DependencyWalker<NodeType extends Node<NodeType>> { | 50 abstract class DependencyWalker<NodeType extends Node<NodeType>> { |
| 49 /** | 51 /** |
| 50 * Called by [walk] to evaluate a single non-cyclical node, after | 52 * Called by [walk] to evaluate a single non-cyclical node, after |
| 51 * all that node's dependencies have been evaluated. | 53 * all that node's dependencies have been evaluated. |
| (...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 90 bool hasTrivialCycle = false; | 92 bool hasTrivialCycle = false; |
| 91 | 93 |
| 92 // Assign the current node an index and add it to the stack. We | 94 // Assign the current node an index and add it to the stack. We |
| 93 // haven't seen any of its dependencies yet, so set its lowLink | 95 // haven't seen any of its dependencies yet, so set its lowLink |
| 94 // to its index, indicating that so far it is the only node in | 96 // to its index, indicating that so far it is the only node in |
| 95 // its strongly connected component. | 97 // its strongly connected component. |
| 96 node._index = node._lowLink = index++; | 98 node._index = node._lowLink = index++; |
| 97 stack.add(node); | 99 stack.add(node); |
| 98 | 100 |
| 99 // Consider the node's dependencies one at a time. | 101 // Consider the node's dependencies one at a time. |
| 100 for (NodeType dependency in node.dependencies) { | 102 for (NodeType dependency in Node.getDependencies(node)) { |
| 101 // If the dependency has already been evaluated, it can't be | 103 // If the dependency has already been evaluated, it can't be |
| 102 // part of this node's strongly connected component, so we can | 104 // part of this node's strongly connected component, so we can |
| 103 // skip it. | 105 // skip it. |
| 104 if (dependency.isEvaluated) { | 106 if (dependency.isEvaluated) { |
| 105 continue; | 107 continue; |
| 106 } | 108 } |
| 107 if (identical(node, dependency)) { | 109 if (identical(node, dependency)) { |
| 108 // If a node includes itself as a dependency, there is no need to | 110 // If a node includes itself as a dependency, there is no need to |
| 109 // explore the dependency further. | 111 // explore the dependency further. |
| 110 hasTrivialCycle = true; | 112 hasTrivialCycle = true; |
| (...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 159 } | 161 } |
| 160 evaluateScc(scc); | 162 evaluateScc(scc); |
| 161 } | 163 } |
| 162 } | 164 } |
| 163 } | 165 } |
| 164 | 166 |
| 165 // Kick off the algorithm starting with the starting point. | 167 // Kick off the algorithm starting with the starting point. |
| 166 strongConnect(startingPoint); | 168 strongConnect(startingPoint); |
| 167 } | 169 } |
| 168 } | 170 } |
| OLD | NEW |