public final class CallGraph extends java.lang.Object implements CompilerPass
DefinitionProvider
to compute a call graph for an
AST.
A CallGraph
connects CallGraph.Function
s to CallGraph.Callsite
s and
vice versa: each function in the graph links to the callsites it contains and
each callsite links to the functions it could call. Similarly, each callsite
links to the function that contains it and each function links to the
callsites that could call it.
The callgraph is not precise. That is, a callsite may indicate it can call a function when in fact it does not do so in the running program.
The callgraph is also not complete: in some cases it may be unable to determine some targets of a callsite. In this case, Callsite.hasUnknownTarget() will return true.
The CallGraph doesn't (currently) have functions for externally defined functions; however, callsites that target externs will have hasExternTarget() return true.
TODO(dcc): Have CallGraph (optionally?) include functions for externs.
TODO(huajiewu): Add support of tagged template in call graph.
Modifier and Type | Class and Description |
---|---|
class |
CallGraph.Callsite
An inner class that represents call sites in the call graph.
|
class |
CallGraph.Function
An inner class that represents functions in the call graph.
|
Modifier and Type | Field and Description |
---|---|
private boolean |
alreadyRun
Has the CallGraph already been constructed?
|
private java.util.Map<Node,CallGraph.Callsite> |
callsitesByNode
Maps an AST node (with type Token.CALL or Token.NEW) to a Callsite object.
|
private AbstractCompiler |
compiler |
private boolean |
computeBackwardGraph
Will the call graph support looking up the callsites that could call a
given function?
|
private boolean |
computeForwardGraph
Will the call graph support looking up the functions that a given callsite
can call?
|
private java.util.Map<Node,CallGraph.Function> |
functionsByNode
Maps an AST node (with type Token.FUNCTION) to a Function object.
|
static java.lang.String |
MAIN_FUNCTION_NAME
The name we give the main function.
|
private CallGraph.Function |
mainFunction
Represents the global function.
|
Constructor and Description |
---|
CallGraph(AbstractCompiler compiler)
Creates a call graph object support both forward and backward lookups.
|
CallGraph(AbstractCompiler compiler,
boolean computeForwardGraph,
boolean computeBackwardGraph)
Creates a call graph object supporting the specified lookups.
|
Modifier and Type | Method and Description |
---|---|
private void |
connectCallsiteToTargets(CallGraph.Callsite callsite,
DefinitionProvider definitionProvider)
Maps a Callsite to the Function(s) it could call
and each Function to the Callsite(s) that could call it.
|
private DefinitionProvider |
constructDefinitionProvider(Node externsRoot,
Node jsRoot)
Constructs a DefinitionProvider that can be used to determine the
targets of callsites.
|
private DiGraph<CallGraph.Function,CallGraph.Callsite> |
constructDirectedGraph(boolean forward)
Constructs a digraph of the call graph.
|
private CallGraph.Callsite |
createCallsite(Node callsiteNode) |
private CallGraph.Function |
createFunction(Node functionNode)
Create a Function object for given an Token.FUNCTION AST node.
|
private void |
createFunctionsAndCallsites(Node jsRoot,
DefinitionProvider provider)
Creates
CallGraph.Function s and CallGraph.Callsite s in a single
AST traversal. |
private static void |
digraphConnect(DiGraph<CallGraph.Function,CallGraph.Callsite> digraph,
CallGraph.Function caller,
CallGraph.Callsite callsite,
CallGraph.Function callee,
boolean forward) |
private void |
fillInFunctionInformation(DefinitionProvider provider)
Fills in function information (such as whether the function is ever
aliased or whether it is exposed to .call or .apply) using the
definition provider.
|
java.util.Collection<CallGraph.Callsite> |
getAllCallsites()
Returns a collection of all callsites in the call graph.
|
java.util.Collection<CallGraph.Function> |
getAllFunctions()
Returns a collection of all functions (including the main function)
in the call graph.
|
DiGraph<CallGraph.Function,CallGraph.Callsite> |
getBackwardDirectedGraph()
Constructs and returns a directed graph where the nodes are functions and
the edges are callsites connecting callees to callers.
|
CallGraph.Callsite |
getCallsiteForAstNode(Node callsiteNode)
Returns the call graph Callsite object corresponding to the provided
AST Token.CALL or Token.NEW node, or null if no such object exists.
|
DiGraph<CallGraph.Function,CallGraph.Callsite> |
getForwardDirectedGraph()
Constructs and returns a directed graph where the nodes are functions and
the edges are callsites connecting callers to callees.
|
CallGraph.Function |
getFunctionForAstNode(Node functionNode)
Returns the call graph Function object corresponding to the provided
AST Token.FUNCTION node, or null if no such object exists.
|
CallGraph.Function |
getMainFunction()
Returns a Function object representing the "main" global function.
|
CallGraph.Function |
getUniqueFunctionWithName(java.lang.String desiredName)
Finds a function with the given name.
|
private java.util.Collection<DefinitionsRemover.Definition> |
lookupDefinitionsForTargetsOfCall(Node callsite,
DefinitionProvider definitionProvider)
Queries the definition provider for the definitions that could be the
targets of the given callsite node.
|
private CallGraph.Function |
lookupFunctionForDefinition(DefinitionsRemover.Definition definition)
Returns a
CallGraph.Function for the passed in DefinitionsRemover.Definition
or null if the definition isn't for a function. |
void |
process(Node externsRoot,
Node jsRoot)
Builds a call graph for the given externsRoot and jsRoot.
|
private void |
updateFunctionForUse(CallGraph.Function function,
Node useNode)
Updates
CallGraph.Function information (such as whether is is aliased
or exposed to .apply or .call based a site where the function is used. |
private final AbstractCompiler compiler
private final java.util.Map<Node,CallGraph.Callsite> callsitesByNode
private final java.util.Map<Node,CallGraph.Function> functionsByNode
private final boolean computeBackwardGraph
private final boolean computeForwardGraph
private boolean alreadyRun
public static final java.lang.String MAIN_FUNCTION_NAME
private CallGraph.Function mainFunction
public CallGraph(AbstractCompiler compiler, boolean computeForwardGraph, boolean computeBackwardGraph)
compiler
- The compilercomputeForwardGraph
- Should the call graph allow lookup of the target
functions a given callsite could call?computeBackwardGraph
- Should the call graph allow lookup of the
callsites that could call a given function?public CallGraph(AbstractCompiler compiler)
public void process(Node externsRoot, Node jsRoot)
process
in interface CompilerPass
externsRoot
- Top of external JS treejsRoot
- Top of JS treepublic CallGraph.Function getFunctionForAstNode(Node functionNode)
public CallGraph.Function getMainFunction()
public java.util.Collection<CallGraph.Function> getAllFunctions()
public CallGraph.Function getUniqueFunctionWithName(java.lang.String desiredName)
public CallGraph.Callsite getCallsiteForAstNode(Node callsiteNode)
public java.util.Collection<CallGraph.Callsite> getAllCallsites()
private void createFunctionsAndCallsites(Node jsRoot, DefinitionProvider provider)
CallGraph.Function
s and CallGraph.Callsite
s in a single
AST traversal.private CallGraph.Function createFunction(Node functionNode)
private CallGraph.Callsite createCallsite(Node callsiteNode)
private void connectCallsiteToTargets(CallGraph.Callsite callsite, DefinitionProvider definitionProvider)
callsite
- The callsite for which target functions should be founddefinitionProvider
- The DefinitionProvider used to determine
targets of callsites.private void fillInFunctionInformation(DefinitionProvider provider)
private void updateFunctionForUse(CallGraph.Function function, Node useNode)
CallGraph.Function
information (such as whether is is aliased
or exposed to .apply or .call based a site where the function is used.
Note: this method may be called multiple times per Function, each time
with a different useNode.private CallGraph.Function lookupFunctionForDefinition(DefinitionsRemover.Definition definition)
CallGraph.Function
for the passed in DefinitionsRemover.Definition
or null if the definition isn't for a function.public DiGraph<CallGraph.Function,CallGraph.Callsite> getForwardDirectedGraph()
public DiGraph<CallGraph.Function,CallGraph.Callsite> getBackwardDirectedGraph()
private static void digraphConnect(DiGraph<CallGraph.Function,CallGraph.Callsite> digraph, CallGraph.Function caller, CallGraph.Callsite callsite, CallGraph.Function callee, boolean forward)
private DiGraph<CallGraph.Function,CallGraph.Callsite> constructDirectedGraph(boolean forward)
forward
is true, then
the edges in the digraph will go from callers to callees, if false then
the edges will go from callees to callers.
It is safe to run this method on both a forwardly constructed callgraph
and a backwardly constructed callgraph, regardless of the value of
forward
.forward
- If true then the digraph will be a forward digraph.private DefinitionProvider constructDefinitionProvider(Node externsRoot, Node jsRoot)
private java.util.Collection<DefinitionsRemover.Definition> lookupDefinitionsForTargetsOfCall(Node callsite, DefinitionProvider definitionProvider)