24

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

Stephan
  • 41,764
  • 65
  • 238
  • 329
DuduAlul
  • 6,313
  • 7
  • 39
  • 63
  • It doesn't look like you are going to find an off-the-shelf answer, let alone something that comes close. Are you interested in custom solution? – Ira Baxter Apr 01 '11 at 19:42
  • What do you intend to do with this call graph? Perhaps there's a way to get your answer without computing it directly. – Ira Baxter Apr 01 '11 at 19:48
  • first I had like to understand if that even possible and if not what "syntax features" make it impossible.. anyhow I wonder what would be the best approach to develop a tool that do this – DuduAlul Apr 01 '11 at 21:52
  • Yes, its possible, see my comments to Spencer Tipping's answer. – Ira Baxter Apr 01 '11 at 21:54
  • Someone interested in an updated answer here could ask this question over in https://softwarerecs.stackexchange.com - there's already a question for Ruby (https://softwarerecs.stackexchange.com/questions/19126/tools-for-creating-call-graph-for-ruby-application) – Ben Creasy Jan 19 '18 at 01:14
  • https://github.com/Persper/js-callgraph seems modern – Bergi Aug 07 '20 at 16:57

8 Answers8

11

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.

Ira Baxter
  • 93,541
  • 22
  • 172
  • 341
  • Check this out .. https://github.com/cheburakshu/Javascript-Explorer-Callgraph – Sud May 29 '17 at 18:34
  • @Sud: OK, so maybe the answer has changed a little bit in the 6 years since I wrote this. Does it handle indirect function calls? ... (dig, dig) ... oh. His procedure to compute the call graph is a grand total of 66 lines. I highly doubt this handles indirect calls. – Ira Baxter May 29 '17 at 19:39
  • @IraBaxter Does your DMS work on semi-valid JS? JS that may have syntax errors.. etc. I would need to use on JS written incorrectly but still has parts that need to be understood. Basically this problem is similar to the problem that browsers deal with when handling invalid HTML, they still try to render what they can. – CMCDragonkai Sep 11 '17 at 05:28
  • Our tools will attempt syntax repairs on broken code and often succeeds. Whether you get nonsense interpretation of the program based on the "easiest" repair is hard to say in general. If the program is syntactically well formed but the symbol usage is nonsense, you'll get some kind of semantic/type error which we don't attempt to fix. Because our front ends are customizable, you could change the default policy of "just report it" to "report it and make an assumption and proceed". Its quite the art to repair a program whose intent you don't know, and get something sensible to the author. – Ira Baxter Sep 11 '17 at 05:36
5

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).

Spencer Tipping
  • 99
  • 1
  • in that example above, can I say that I am invoking globally {x||y||Z...} .map()? – DuduAlul Mar 30 '11 at 18:51
  • 3
    In general, it isn't possible to reason about any program, whether it is JavaScript or not. The question is what can you do in practice? You *can* compute a call graph, but you might have to make conservative assumptions. For most programs, this will produce something relatively useful. For most programs, there will be some place (like the example above) where the detail is vague ("Might call anything"). No, that doesn't mean I know of a tool that attempts to compute this for JavaScript. – Ira Baxter Apr 01 '11 at 02:05
  • 1
    When I say "call graph" I mean: A graph that represents which function calls which other functions. In your example the call graph is very simple global->some_function(),global->another_function(),global->OBJ.map(each). the problem with that graph is that I must specify which object is OBJ, in our application it would be OK to have a list of possible objects instead of OBJ...moreover converting text to code(eval etc..) is not a allowed in the code we are parsing. – DuduAlul Apr 01 '11 at 07:39
  • 1
    To do this, you need: parsing, name resolution (handling scoping), type analysis, data flow analysis, and what amounts to points-to analysis (to track functions passed around as values). A mere parser is pretty far from this. *eval* makes the problem worse, because you need to track string value results and parse them to get some kind of clue as to which function they might call. You also likely need to model the program execution context; I suspect there are lots of browser APIs that include callbacks. All of this is a matter of sweat (a lot). – Ira Baxter Apr 01 '11 at 19:45
5

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.

msridhar
  • 2,846
  • 4
  • 22
  • 23
2

Here are a few solutions I can see:

  1. Use Aptana Call Graph view
    Aptana is an IDE based on Eclipse that permit you edit and debugging Javascript code.

  2. Use Dynatrace
    Dynatrace is a useful tool that let you live trace your code and see the call graph and hot spots.

  3. Use Firebug
    The famous developer addon on Firefox

Most of the call graphs generated here will be dynamic, ie you'll see the call graph for a given set of actions. If you're looking for static call graphs check Aptana first. Static call graphs may not let you see dynamic calls (code running through eval()).

Stephan
  • 41,764
  • 65
  • 238
  • 329
2

I think http://doctorjs.org/ may fit your needs. It has a nice JSON API, is available on github, backed up by mozilla. It's written in JS itself and generally does stuff pretty well (including dealing with polymorphism etc).

wildcard
  • 7,353
  • 3
  • 27
  • 25
1

For a js approach, check out arguments.callee.caller. It gives you the function that called the function you are in and you can recurse up the call stack. There is an example in this thread http://bytes.com/topic/javascript/answers/470251-recursive-functions-arguments-callee-caller.

Be aware that this may not work in all browsers and you may run in to some unexpected things when you get to the top of the "call stack" or native functions so use at your own risk.

My own example works in IE9 and Chrome 10 (didn't test any other browsers).

<html xmlns="http://www.w3.org/1999/xhtml">
<head runat="server">
<title></title>
</head>
<body onload="Function1()">
<form id="form1" runat="server">
<div>

</div>
</form>
</body>

<script type="text/javascript">

function Function1()
{
    Function2();
}

function Function2()
{
Function3();
}
function Function3()
{
Function4();
}
function Function4()
{
    var caller = arguments.callee.caller;
    var stack = [];
    while (caller != null)
    {
        stack.push(caller);//this is the text of the function.  You can probably write some code to parse out the name and parameters.
        var args = caller.arguments; //this is the arguments for that function.  You can get the actual values here and do something with them if you want.
        caller = caller.caller;
    }
    alert(stack);
}


</script>
</html>
Matthew
  • 2,210
  • 1
  • 19
  • 30
  • 1
    this is a runtime impl', I am looking for a static one(without actually executing the code..) – DuduAlul Mar 29 '11 at 17:13
  • Hmmm. You could probably use something like [Rhino](http://www.mozilla.org/rhino/) to evaluate the code. There are a few javascript minifiers that use Rhino. You could probably use them as a starting point. On the other hand, you could execute the code in a sterile test environment and use the run-time implementation to generate reports. – Matthew Mar 29 '11 at 20:41
0

Not related directly to NodeJS, but generally to JavaScript, SAP has released a Web IDE related to HANA (but also accessible freely from the HANA Cloud - see more details here http://scn.sap.com/community/developer-center/cloud-platform/blog/2014/04/15/sap-hana-web-ide-online-tutorial).

In this Web IDE, there is a REST-based service that analyzes JavaScript content with primary focus (but not only) on creating a Call Graph. There are many consumers of that service, like Code Navigation.

Some more information here (see the Function Flow part): http://scn.sap.com/community/developer-center/hana/blog/2014/12/02/sap-hana-sps-09-new-developer-features-sap-hana-web-based-development-workbench

Note: I am the main developer of this service.

Radu
  • 96
  • 2
  • 7
0

The closest thing you can get to a Call Graph is manipulating a full Javascript AST. This is possible with Rhino, take a look at this article: http://tagneto.blogspot.com/2010/03/requirejs-kicking-some-ast.html

Example from the post:

//Set up shortcut to long Java package name,
//and create a Compiler instance.
var jscomp = Packages.com.google.javascript.jscomp,
  compiler = new jscomp.Compiler(),

  //The parse method returns an AST.
  //astRoot is a kind of Node for the AST.
  //Comments are not present as nodes in the AST.
  astRoot = compiler.parse(jsSourceFile),
  node = astRoot.getChildAtIndex(0);

//Use Node methods to get child nodes, and their types.
if (node.getChildAtIndex(1).getFirstChild().getType() === CALL) {
  //Convert this call node and its children to JS source.
  //This generated source does not have comments and
  //may not be space-formatted exactly the same as the input
  //source
  var codeBuilder = new jscomp.Compiler.CodeBuilder();
  compiler.toSource(codeBuilder, 1, node);

  //Return the JavaScript source.
  //Need to use String() to convert the Java String
  //to a JavaScript String.
  return String(codeBuilder.toString());
}

In either Javascript or Java, you could walk the AST to build whatever type of call graph or dependency chain you'd like.

Shakakai
  • 3,514
  • 1
  • 16
  • 18
  • 1
    So you've exhibited the easy part: calling a parser. The harder part is producing the call graph. You need name resolution as a first step, and that isn't here, either. – Ira Baxter Apr 01 '11 at 02:07
  • I agree producing the call graph would be difficult but there isn't any open source tool that will do what he wants. Just giving the open source part that is currently available. – Shakakai Apr 02 '11 at 11:46