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

Side by Side Diff: lib/src/graph.dart

Issue 2233093003: make dart2js_info strong-mode clean (Closed) Base URL: git@github.com:dart-lang/dart2js_info.git@master
Patch Set: update version Created 4 years, 4 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 | « lib/json_info_codec.dart ('k') | lib/src/measurements.dart » ('j') | 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) 2015, the Dart project authors. Please see the AUTHORS file 1 // Copyright (c) 2015, 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 /// A library to work with graphs. It contains a couple algorithms, including 5 /// A library to work with graphs. It contains a couple algorithms, including
6 /// Tarjan's algorithm to compute strongly connected components in a graph and 6 /// Tarjan's algorithm to compute strongly connected components in a graph and
7 /// Cooper et al's dominator algorithm. 7 /// Cooper et al's dominator algorithm.
8 /// 8 ///
9 /// Portions of the code in this library was adapted from 9 /// Portions of the code in this library was adapted from
10 /// `package:analyzer/src/generated/collection_utilities.dart`. 10 /// `package:analyzer/src/generated/collection_utilities.dart`.
(...skipping 25 matching lines...) Expand all
36 if (identical(node, target)) return true; 36 if (identical(node, target)) return true;
37 if (!seen.add(node)) return false; 37 if (!seen.add(node)) return false;
38 return targetsOf(node).any(helper); 38 return targetsOf(node).any(helper);
39 } 39 }
40 return helper(source); 40 return helper(source);
41 } 41 }
42 42
43 /// Returns all nodes reachable from [root] in post order. 43 /// Returns all nodes reachable from [root] in post order.
44 Iterable<N> postOrder(N root) sync* { 44 Iterable<N> postOrder(N root) sync* {
45 var seen = new Set<N>(); 45 var seen = new Set<N>();
46 Iterable<N> helper(n) sync* { 46 Iterable<N> helper(N n) sync* {
47 if (!seen.add(n)) return; 47 if (!seen.add(n)) return;
48 for (var x in targetsOf(n)) { 48 for (var x in targetsOf(n)) {
49 yield* helper(x); 49 yield* helper(x);
50 } 50 }
51 yield n; 51 yield n;
52 } 52 }
53 yield* helper(root); 53 yield* helper(root);
54 } 54 }
55 55
56 /// Returns an iterable of all nodes reachable from [root] in preorder. 56 /// Returns an iterable of all nodes reachable from [root] in preorder.
(...skipping 233 matching lines...) Expand 10 before | Expand all | Expand 10 after
290 var nodesInPostOrder = _graph.postOrder(root).toList(); 290 var nodesInPostOrder = _graph.postOrder(root).toList();
291 for (var n in nodesInPostOrder) { 291 for (var n in nodesInPostOrder) {
292 postOrderId[n] = i++; 292 postOrderId[n] = i++;
293 } 293 }
294 var nodesInReversedPostOrder = nodesInPostOrder.reversed; 294 var nodesInReversedPostOrder = nodesInPostOrder.reversed;
295 while (changed) { 295 while (changed) {
296 changed = false; 296 changed = false;
297 for (var n in nodesInReversedPostOrder) { 297 for (var n in nodesInReversedPostOrder) {
298 if (n == root) continue; 298 if (n == root) continue;
299 bool first = true; 299 bool first = true;
300 var idom = null; 300 N idom;
301 for (var p in _graph.sourcesOf(n)) { 301 for (var p in _graph.sourcesOf(n)) {
302 if (immediateDominators[p] != null) { 302 if (immediateDominators[p] != null) {
303 if (first) { 303 if (first) {
304 idom = p; 304 idom = p;
305 first = false; 305 first = false;
306 } else { 306 } else {
307 idom = _intersect(p, idom); 307 idom = _intersect(p, idom);
308 } 308 }
309 } 309 }
310 } 310 }
(...skipping 12 matching lines...) Expand all
323 while (postOrderId[finger1] < postOrderId[finger2]) { 323 while (postOrderId[finger1] < postOrderId[finger2]) {
324 finger1 = immediateDominators[finger1]; 324 finger1 = immediateDominators[finger1];
325 } 325 }
326 while (postOrderId[finger2] < postOrderId[finger1]) { 326 while (postOrderId[finger2] < postOrderId[finger1]) {
327 finger2 = immediateDominators[finger2]; 327 finger2 = immediateDominators[finger2];
328 } 328 }
329 } 329 }
330 return finger1; 330 return finger1;
331 } 331 }
332 } 332 }
OLDNEW
« no previous file with comments | « lib/json_info_codec.dart ('k') | lib/src/measurements.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698