Class WorklistBasedOptimisticCallgraphBuilder

java.lang.Object

com.ibm.wala.cast.js.callgraph.fieldbased.FieldBasedCallGraphBuilder

com.ibm.wala.cast.js.callgraph.fieldbased.WorklistBasedOptimisticCallgraphBuilder

public class WorklistBasedOptimisticCallgraphBuilder
extends FieldBasedCallGraphBuilder

Optimistic call graph builder that propagates inter-procedural data flow iteratively as call edges are discovered. Slower, but potentially more sound than PessimisticCallGraphBuilder.

This variant uses a worklist algorithm, generally making it scale better than OptimisticCallgraphBuilder, which repeatedly runs the pessimistic algorithm.

Author:

mschaefer

Nested Class Summary

Nested classes/interfaces inherited from class FieldBasedCallGraphBuilder

FieldBasedCallGraphBuilder.CallGraphResult

Field Summary

Fields

Modifier and Type	Field	Description
int	ITERATION_CUTOFF	The maximum number of iterations to perform.

Fields inherited from class FieldBasedCallGraphBuilder

cache, cha, constructors, options, supportFullPointerAnalysis, targetSelector

Constructor Summary

Constructors

Constructor	Description
WorklistBasedOptimisticCallgraphBuilder(IClassHierarchy cha, AnalysisOptions options, IAnalysisCacheView cache, boolean supportFullPointerAnalysis, int bound)

Method Summary

Modifier and Type	Method	Description
void	addFlowEdge(FlowGraph flowgraph, Vertex from, Vertex to, Set<Vertex> worklist)
FlowGraph	buildFlowGraph(MonitorUtil.IProgressMonitor monitor)	Build a flow graph for the program to be analysed.
Set<Pair<CallVertex, FuncVertex>>	extractCallGraphEdges(FlowGraph flowgraph, MonitorUtil.IProgressMonitor monitor)	Extract call edges from the flow graph into high-level representation.
void	processPendingCallWorklist(FlowGraph flowgraph, Map<Vertex, Set<FuncVertex>> pendingCallWorklist, VertexFactory factory, Map<Vertex, MutableIntSet> reachingFunctions, Map<VarVertex, Pair<JavaScriptInvoke, Boolean>> reflectiveCalleeVertices, Set<Vertex> worklist, OrdinalSetMapping<FuncVertex> mapping)
void	processPendingReflectiveCallWorklist(FlowGraph flowgraph, Map<Vertex, Set<FuncVertex>> pendingReflectiveCallWorklist, Map<VarVertex, Pair<JavaScriptInvoke, Boolean>> reflectiveCalleeVertices, Set<Vertex> worklist)

Methods inherited from class FieldBasedCallGraphBuilder

addEdgeToJSCallGraph, buildCallGraph, extract, extract, flowGraphFactory, handleFunctionCallOrApplyInvocation

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

ITERATION_CUTOFF

public int ITERATION_CUTOFF

The maximum number of iterations to perform.

Constructor Details

WorklistBasedOptimisticCallgraphBuilder

public WorklistBasedOptimisticCallgraphBuilder(IClassHierarchy cha,
 AnalysisOptions options,
 IAnalysisCacheView cache,
 boolean supportFullPointerAnalysis,
 int bound)

Method Details

buildFlowGraph

public FlowGraph buildFlowGraph(MonitorUtil.IProgressMonitor monitor)
                         throws CancelException

Description copied from class: FieldBasedCallGraphBuilder

Build a flow graph for the program to be analysed.

Specified by:

buildFlowGraph in class FieldBasedCallGraphBuilder

Throws:

CancelException

extractCallGraphEdges

public Set<Pair<CallVertex, FuncVertex>> extractCallGraphEdges(FlowGraph flowgraph,
 MonitorUtil.IProgressMonitor monitor)
                                                        throws CancelException

Description copied from class: FieldBasedCallGraphBuilder

Extract call edges from the flow graph into high-level representation.

Overrides:

extractCallGraphEdges in class FieldBasedCallGraphBuilder

Throws:

CancelException

processPendingCallWorklist

public void processPendingCallWorklist(FlowGraph flowgraph,
 Map<Vertex, Set<FuncVertex>> pendingCallWorklist,
 VertexFactory factory,
 Map<Vertex, MutableIntSet> reachingFunctions,
 Map<VarVertex, Pair<JavaScriptInvoke, Boolean>> reflectiveCalleeVertices,
 Set<Vertex> worklist,
 OrdinalSetMapping<FuncVertex> mapping)

processPendingReflectiveCallWorklist

public void processPendingReflectiveCallWorklist(FlowGraph flowgraph,
 Map<Vertex, Set<FuncVertex>> pendingReflectiveCallWorklist,
 Map<VarVertex, Pair<JavaScriptInvoke, Boolean>> reflectiveCalleeVertices,
 Set<Vertex> worklist)

addFlowEdge

public void addFlowEdge(FlowGraph flowgraph,
 Vertex from,
 Vertex to,
 Set<Vertex> worklist)