dart2js: add simple script to compute dependency queries. Currently only

dart2js: add simple script to compute dependency queries. Currently only
one query is supported "some_path", which gives you a way to determine how a
function is included in the program. For example, running:

  dart code_deps.dart angular2_hello.js.info.json some_path main Compiler

would produce this output:

  source: examples.src.hello_world.index...main
  target: angular2.src.core.compiler.compiler...Compiler.Compiler
  result:
    0. examples.src.hello_world.index...main
    1. examples.src.gestures.index.ng_deps.dart...initReflector
    2. angular2.bootstrap_static.ng_deps.dart...initReflector
    3. angular2.application_static.ng_deps.dart...initReflector
    4. angular2.src.core.application_common.ng_deps.dart...initReflector
    5. angular2.src.core.compiler.compiler.ng_deps.dart...initReflector
    6. angular2.src.core.compiler.compiler...Compiler.Compiler

The tool accepts regular expressions to match the name of the elements.
The graph and util library will be used for other scripts as well.

R=het@google.com

Committed: https://github.com/dart-lang/sdk/commit/f95dd37d1a4845359c0df3d6820d8299619783d4

[Siggi Cherem (dart-lang), 2015-08-11 01:34:05]

Patchset #1 (id:1) has been deleted

[Siggi Cherem (dart-lang), 2015-08-11 01:34:50]

sigmund@google.com changed reviewers:
+ het@google.com, johnniwinther@google.com, sra@google.com

[Siggi Cherem (dart-lang), 2015-08-11 21:55:45]

Patchset #2 (id:40001) has been deleted

[Siggi Cherem (dart-lang), 2015-08-11 21:57:00]

(this one is now updated with all the other changes, but also includes small
changes in the structure of the graph helper code).

[Harry Terkelsen, 2015-08-11 22:57:43]

lgtm

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/code_...
File pkg/compiler/tool/code_deps.dart (right):

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/code_...
pkg/compiler/tool/code_deps.dart:5: /// Command-line tool to query for code
dependncies.
dependencies

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/code_...
pkg/compiler/tool/code_deps.dart:77: if (graph.targetsOf(n).any(helper)) return
true;
maybe more useful to do a BFS instead to find the shortest path

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/graph...
File pkg/compiler/tool/graph.dart (right):

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/graph...
pkg/compiler/tool/graph.dart:94: _edges.putIfAbsent(target, () => new Set<N>());
maybe cleaner to do addNode(source); addNode(target);?

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/graph...
pkg/compiler/tool/graph.dart:131: /// been examined. THere is an instance of
this class per node in the graph.
s/THere/There/

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/graph...
pkg/compiler/tool/graph.dart:133: /// Depth of the node correspondnig to this
info.
corresponding

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/util....
File pkg/compiler/tool/util.dart (right):

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/util....
pkg/compiler/tool/util.dart:20: if (g.target == null) print(g.toJson());
only for debugging?

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/util....
pkg/compiler/tool/util.dart:41: g3.addNode(f);
already added f to g3 above

[Siggi Cherem (dart-lang), 2015-08-12 00:05:25]

Patchset #3 (id:80001) has been deleted

[Siggi Cherem (dart-lang), 2015-08-12 00:06:01]

thanks Harry!

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/code_...
File pkg/compiler/tool/code_deps.dart (right):

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/code_...
pkg/compiler/tool/code_deps.dart:5: /// Command-line tool to query for code
dependncies.
On 2015/08/11 22:57:42, Harry Terkelsen wrote:
> dependencies

Done.

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/code_...
pkg/compiler/tool/code_deps.dart:77: if (graph.targetsOf(n).any(helper)) return
true;
On 2015/08/11 22:57:42, Harry Terkelsen wrote:
> maybe more useful to do a BFS instead to find the shortest path

Great idea! Updated. I tried it on an example in angular2 from main to
DynamicChangeDetection, and saw a change from a path of 159 steps, to a simple
path of 6 steps.

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/graph...
File pkg/compiler/tool/graph.dart (right):

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/graph...
pkg/compiler/tool/graph.dart:94: _edges.putIfAbsent(target, () => new Set<N>());
On 2015/08/11 22:57:42, Harry Terkelsen wrote:
> maybe cleaner to do addNode(source); addNode(target);?

Done.

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/graph...
pkg/compiler/tool/graph.dart:131: /// been examined. THere is an instance of
this class per node in the graph.
On 2015/08/11 22:57:42, Harry Terkelsen wrote:
> s/THere/There/

Done.

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/graph...
pkg/compiler/tool/graph.dart:133: /// Depth of the node correspondnig to this
info.
On 2015/08/11 22:57:42, Harry Terkelsen wrote:
> corresponding

Done.

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/util....
File pkg/compiler/tool/util.dart (right):

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/util....
pkg/compiler/tool/util.dart:20: if (g.target == null) print(g.toJson());
On 2015/08/11 22:57:42, Harry Terkelsen wrote:
> only for debugging?

True. removed

https://codereview.chromium.org/1284843002/diff/60001/pkg/compiler/tool/util....
pkg/compiler/tool/util.dart:41: g3.addNode(f);
On 2015/08/11 22:57:42, Harry Terkelsen wrote:
> already added f to g3 above

Good catch. Done

[Siggi Cherem (dart-lang), 2015-08-12 00:12:50]

Committed patchset #3 (id:100001) manually as
f95dd37d1a4845359c0df3d6820d8299619783d4 (presubmit successful).

[Johnni Winther, 2015-08-18 13:17:11]

lgtm

https://codereview.chromium.org/1284843002/diff/100001/pkg/compiler/tool/grap...
File pkg/compiler/tool/graph.dart (right):

https://codereview.chromium.org/1284843002/diff/100001/pkg/compiler/tool/grap...
pkg/compiler/tool/graph.dart:57: /// node is not part of this graph, then a list
containing only the node
Shouldn't it be `is not a part of a cycle in this graph` ?

https://codereview.chromium.org/1284843002/diff/100001/pkg/compiler/tool/grap...
pkg/compiler/tool/graph.dart:65: Graph<N> dominatorTree(N root) {
Add documentation.

https://codereview.chromium.org/1284843002/diff/100001/pkg/compiler/tool/grap...
pkg/compiler/tool/graph.dart:171: _SccFinder(this._graph) : super();
Why the explicit super call?

https://codereview.chromium.org/1284843002/diff/100001/pkg/compiler/tool/util...
File pkg/compiler/tool/util.dart (right):

https://codereview.chromium.org/1284843002/diff/100001/pkg/compiler/tool/util...
pkg/compiler/tool/util.dart:8: // Note: currently we build two graphs to debug
the differences between to
'between to' -> 'between two' ?

[Siggi Cherem (dart-lang), 2015-08-18 19:13:18]

Thanks Johnni, I submitted a separate change with the fixes.

Here:
https://github.com/dart-lang/dart2js_info/commit/f952bbd8ff334c1446c70781aee1...

and here:
https://github.com/dart-lang/dart2js_info/commit/bfb46714c5a292f0c43e1164cd69...

https://codereview.chromium.org/1284843002/diff/100001/pkg/compiler/tool/grap...
File pkg/compiler/tool/graph.dart (right):

https://codereview.chromium.org/1284843002/diff/100001/pkg/compiler/tool/grap...
pkg/compiler/tool/graph.dart:57: /// node is not part of this graph, then a list
containing only the node
On 2015/08/18 13:17:11, Johnni Winther wrote:
> Shouldn't it be `is not a part of a cycle in this graph` ?

Good point yes

https://codereview.chromium.org/1284843002/diff/100001/pkg/compiler/tool/grap...
pkg/compiler/tool/graph.dart:65: Graph<N> dominatorTree(N root) {
On 2015/08/18 13:17:11, Johnni Winther wrote:
> Add documentation.

Done.

https://codereview.chromium.org/1284843002/diff/100001/pkg/compiler/tool/grap...
pkg/compiler/tool/graph.dart:171: _SccFinder(this._graph) : super();
On 2015/08/18 13:17:11, Johnni Winther wrote:
> Why the explicit super call?

removed, good catch!

(Except for the dominance code, the rest of this code and comments were
copied/adapted from an internal copy in package:analyzer, which was
autogenerated from Java. I tried to clean up some things, but I missed a couple
cases like this one :))

https://codereview.chromium.org/1284843002/diff/100001/pkg/compiler/tool/util...
File pkg/compiler/tool/util.dart (right):

https://codereview.chromium.org/1284843002/diff/100001/pkg/compiler/tool/util...
pkg/compiler/tool/util.dart:8: // Note: currently we build two graphs to debug
the differences between to
On 2015/08/18 13:17:11, Johnni Winther wrote:
> 'between to' -> 'between two' ?

Done.