Are there any static Call-Graph and/or Control-Flow-Graph API for JavaScript? [closed]

Question

Are there any Call-Graph and/or Control-Flow-Graph generators for JavaScript?

Call Graph - http://en.wikipedia.org/wiki/Call_graph

Control Flow Graph - http://en.wikipedia.org/wiki/Control_flow_graph

EDIT: I am looking specifically for a static tool that let me access the graph using some API/code

Answer 1

To do this, you need:

• parsing,
• name resolution (handling scoping)
• type analysis (while JavaScript is arguably "dynamically typed", there are all kinds of typed constants including function constants that are of specific interest here)
• control flow analysis (to build up the structure of the control flow graphs within methods)
• data flow analysis (to track where those types are generated/used)
• what amounts to global points-to analysis (to track function constants passed between functions as values to a point of application).

How to do it is pretty well documented in the compiler literature. However, implementing this matter of considerable sweat, so answers of the form of "you can use a parser result to get what you want" rather miss the point.

If you could apply all this machinery, what you'll get as a practical result is a conservative answer, e.g., "A may call B". This is all you know anyway, consider

 void A(int x,y) { if (x>y) foo.B(); }

Because a tool sometime simply can't reason about complex logic, you may get "A may call B" even when the application designer knows it isn't possible:

 void A(int x) // programmer asserts x<4
   { if (x>5) foo.B(); }

eval makes the problem worse, because you need to track string value results that arrive at eval commands and parse them to get some kind of clue as to what code is being evaled, and which functions that eval'd code might call. Things get really nasty if somebody passes "eval" in a string to eval :-{ You also likely need to model the program execution context; I suspect there are lots of browser APIs that include callbacks.

If somebody offers you tool that has all the necessary machinery completely configured to solve your problem out of the box, that would obviously be great. My suspicion is you won't get such an offer, because such a tool doesn't exist. The reason is all that infrastructure needed; its hard to build and hardly anybody can justify it for just one tool. Even an "optimizing JavaScript compiler" if you can find one likely won't have all this machinery, especially the global analysis, and what it does have is unlikely to be packaged in a form designed for easy consumption for your purpose.

I've been beating my head on this problem since I started programming in 1969 (some of my programs back then were compilers and I wanted all this stuff). The only way to get this is to amortize the cost of all this machinery across lots of tools.

My company offers the DMS Software Reengineering Toolkit, a package of generic compiler analysis and transformation machinery, with a variety of industrial strength computer langauge front-ends (including C, C++, COBOL and yes, JavaScript). DMS offers APIs to enable custom tools to be constructed on its generic foundations.

The generic machinery listed at the top of the message is all present in DMS, including control flow graph and data flow analysis available through a clean documented API. That flow analysis has to be tied to specific language front ends. That takes some work too, and so we haven't done it for all languages yet. We have done this for C [tested on systems of 18,000 compilation units as a monolith, including computing the call graph for the 250,000 functions present, including indirect function calls!], COBOL and Java and we're working on C++.

DMS has the same "JavaScript" parser answer as other answers in this thread, and viewed from just that perspective DMS isn't any better than the other answers that say "build it on top of a parser". The distinction should be clear: the machinery is already present in DMS, so the work is not one of implement the machinery and tying to the parser; it is just tying it to the parser. This is still a bit of work, but a hell of a lot less than if you just start with a parser.

Answer 2

In general it isn't possible to do this. The reason is that functions are first-class and dynamically typed, so for example:

var xs = some_function();
var each = another_function();
xs.map(each);

There are two unknowns. One is the version of 'map' that is called (since Javascript polymorphism can't be resolved statically in the general case), and the other is the value assigned to 'each', which also can't be statically resolved. The only static properties this code has are that some 'map' method is called on some function we got from 'another_function'.

If, however, that is enough information, there are two resources that might be helpful. One is a general-purpose Javascript parser, especially built using parser combinators (Chris Double's jsparse is a good one). This will let you annotate the parse tree as it is being constructed, and you can add a custom rule to invocation nodes to record graph edges.

The other tool that you might find useful (shameless plug) is a Javascript-to-Javascript compiler I wrote called Caterwaul. It lets you do pattern-matching against syntax trees and knows how to walk over them, which might be useful in your case. It could also help if you wanted to build a dynamic trace from short-term execution (probably your best bet if you want an accurate and detailed result).

Answer 3

WALA is an open-source program analysis framework that can build static call graphs and control-flow graphs for JavaScript:

http://wala.sourceforge.net/wiki/index.php/Main_Page

One caveat is that the call graphs may be missing some edges in the presence of eval, with, and other hard-to-analyze constructs. Also, we're still working on scalability; WALA can't yet analyze jquery in a reasonable amount of time, but some other frameworks can be analyzed. Also, our documentation for building JavaScript call graphs isn't great at the moment (improving it is on my TODO list).

We're actively working on this code, so if you try it and run into issues, you can email the WALA mailing list (https://lists.sourceforge.net/lists/listinfo/wala-wala) or contact me.