Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(522)

Side by Side Diff: pkg/front_end/lib/src/dependency_walker.dart

Issue 2907023003: Change dependency walker's Node.dependencies to a static getter. (Closed)
Patch Set: Created 3 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « pkg/analyzer/lib/src/summary/link.dart ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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 }
OLDNEW
« no previous file with comments | « pkg/analyzer/lib/src/summary/link.dart ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698