Package com.ibm.wala.ipa.callgraph.impl

Class BasicCallGraph<T>

java.lang.Object

com.ibm.wala.util.graph.AbstractGraph<T>

com.ibm.wala.util.graph.AbstractNumberedGraph<CGNode>

com.ibm.wala.ipa.callgraph.impl.BasicCallGraph<T>

All Implemented Interfaces:

CallGraph, EdgeManager<CGNode>, Graph<CGNode>, NodeManager<CGNode>, NumberedEdgeManager<CGNode>, NumberedGraph<CGNode>, NumberedNodeManager<CGNode>, Iterable<CGNode>

Direct Known Subclasses:

CHACallGraph, ExplicitCallGraph

public abstract class BasicCallGraph<T>
extends AbstractNumberedGraph<CGNode>
implements CallGraph

Basic data structure support for a call graph.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static final class	BasicCallGraph.Key
static class	BasicCallGraph.NodeImpl	A class that represents the a normal node in a call graph.

Field Summary

Fields

Modifier and Type	Field	Description
protected final Map<MethodReference,Set<CGNode>>	mr2Nodes	A mapping from MethodReference to Set of nodes that represent this methodReference.

Constructor Summary

Constructors

Constructor	Description
BasicCallGraph()

Method Summary

Modifier and Type	Method	Description
boolean	containsNode(CGNode N)	This implementation is necessary because the underlying SparseNumberedGraph may not support node membership tests.
abstract CGNode	findOrCreateNode(IMethod method, Context C)	Use with extreme care.
Collection<CGNode>	getEntrypointNodes()	Note: not all successors of the root node are entrypoints
CGNode	getFakeRootNode()	Return the (fake) interprocedural root node of the call graph.
CGNode	getFakeWorldClinitNode()
protected T	getInterpreter(CGNode node)
CGNode	getNode(IMethod method, Context C)	If you want to get all the nodes corresponding to a particular method, regardless of context, then use getNodes
protected CGNode	getNode(BasicCallGraph.Key K)
protected NumberedNodeManager<CGNode>	getNodeManager()
Set<CGNode>	getNodes(MethodReference m)
int	getNumberOfNodes()	We override this since this class supports remove() on nodes, but the superclass doesn't.
void	init()
Iterator<CGNode>	iterator()	We override this since this class supports remove() on nodes, but the superclass doesn't.
protected abstract CGNode	makeFakeRootNode()
protected abstract CGNode	makeFakeWorldClinitNode()
static String	nodeToString(CallGraph CG, CGNode n)
void	registerEntrypoint(CGNode node)	record that a node is an entrypoint
protected void	registerNode(BasicCallGraph.Key K, CGNode N)
void	removeNodeAndEdges(CGNode N)	remove a node and all its incident edges
void	setInterpreter(T interpreter)
void	summarizeByPackage()
String	toString()

Methods inherited from class com.ibm.wala.util.graph.AbstractNumberedGraph

getEdgeManager, getMaxNumber, getNode, getNumber, getPredNodeNumbers, getSuccNodeNumbers, iterateNodes

Methods inherited from class com.ibm.wala.util.graph.AbstractGraph

addEdge, addNode, edgeString, getPredNodeCount, getPredNodes, getSuccNodeCount, getSuccNodes, hasEdge, nodeString, removeAllIncidentEdges, removeEdge, removeIncomingEdges, removeNode, removeOutgoingEdges, stream

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.ibm.wala.ipa.callgraph.CallGraph

getClassHierarchy, getNumberOfTargets, getPossibleSites, getPossibleTargets

Methods inherited from interface com.ibm.wala.util.graph.EdgeManager

addEdge, getPredNodeCount, getPredNodes, getSuccNodeCount, getSuccNodes, hasEdge, removeAllIncidentEdges, removeEdge, removeIncomingEdges, removeOutgoingEdges

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface com.ibm.wala.util.graph.NodeManager

addNode, removeNode, stream

Methods inherited from interface com.ibm.wala.util.graph.NumberedEdgeManager

getPredNodeNumbers, getSuccNodeNumbers

Methods inherited from interface com.ibm.wala.util.graph.NumberedNodeManager

getMaxNumber, getNode, getNumber, iterateNodes

Field Details

mr2Nodes

protected final Map<MethodReference,Set<CGNode>> mr2Nodes

A mapping from MethodReference to Set of nodes that represent this methodReference.

TODO: rhs of mapping doesn't have to be a set if it's a singleton; could be a node instead.

TODO: this is a bit redundant with the nodes Map. Restructure these data structures for space efficiency.

Constructor Details

BasicCallGraph

public BasicCallGraph()

Method Details

init

public void init()
          throws CancelException

Throws:

CancelException

makeFakeRootNode

protected abstract CGNode makeFakeRootNode()
                                    throws CancelException

Throws:

CancelException

makeFakeWorldClinitNode

protected abstract CGNode makeFakeWorldClinitNode()
                                           throws CancelException

Throws:

CancelException

findOrCreateNode

public abstract CGNode findOrCreateNode(IMethod method,
 Context C)
                                 throws CancelException

Use with extreme care.

Throws:

CancelException - TODO

registerNode

protected void registerNode(BasicCallGraph.Key K,
 CGNode N)

getNode

protected CGNode getNode(BasicCallGraph.Key K)

getFakeRootNode

public CGNode getFakeRootNode()

Description copied from interface: CallGraph

Return the (fake) interprocedural root node of the call graph.

Specified by:

getFakeRootNode in interface CallGraph

Returns:

the "fake" root node the call graph

getFakeWorldClinitNode

public CGNode getFakeWorldClinitNode()

Specified by:

getFakeWorldClinitNode in interface CallGraph

registerEntrypoint

public void registerEntrypoint(CGNode node)

record that a node is an entrypoint

getEntrypointNodes

public Collection<CGNode> getEntrypointNodes()

Note: not all successors of the root node are entrypoints

Specified by:

getEntrypointNodes in interface CallGraph

Returns:

an Iterator of the nodes designated as "root nodes"

toString

public String toString()

Overrides:

toString in class AbstractGraph<CGNode>

nodeToString

public static String nodeToString(CallGraph CG,
 CGNode n)

removeNodeAndEdges

public void removeNodeAndEdges(CGNode N)
                        throws UnimplementedError

Description copied from interface: Graph

remove a node and all its incident edges

Specified by:

removeNodeAndEdges in interface Graph<T>

Overrides:

removeNodeAndEdges in class AbstractGraph<CGNode>

Throws:

UnimplementedError

See Also:

• NodeManager.removeNode(Object)

getNode

public CGNode getNode(IMethod method,
 Context C)

Description copied from interface: CallGraph

If you want to get all the nodes corresponding to a particular method, regardless of context, then use getNodes

Specified by:

getNode in interface CallGraph

Returns:

NodeImpl, or null if none found

getNodes

public Set<CGNode> getNodes(MethodReference m)

Specified by:

getNodes in interface CallGraph

Parameters:

m - a method reference

Returns:

the set of all nodes in the call graph that represent this method.

getInterpreter

protected T getInterpreter(CGNode node)

Parameters:

node - a call graph node we want information about

Returns:

an object that knows how to interpret information about the node

getNumberOfNodes

public int getNumberOfNodes()

We override this since this class supports remove() on nodes, but the superclass doesn't.

Specified by:

getNumberOfNodes in interface NodeManager<T>

Overrides:

getNumberOfNodes in class AbstractGraph<CGNode>

Returns:

the number of nodes in this graph

See Also:

• NodeManager.getNumberOfNodes()

iterator

public Iterator<CGNode> iterator()

We override this since this class supports remove() on nodes, but the superclass doesn't.

Specified by:

iterator in interface Iterable<T>

Specified by:

iterator in interface NodeManager<T>

Overrides:

iterator in class AbstractGraph<CGNode>

Returns:

an Iterator of the nodes in this graph

See Also:

• NodeManager.iterator()

containsNode

public boolean containsNode(CGNode N)

This implementation is necessary because the underlying SparseNumberedGraph may not support node membership tests.

Specified by:

containsNode in interface NodeManager<T>

Overrides:

containsNode in class AbstractGraph<CGNode>

Returns:

true iff the graph contains the specified node

Throws:

IllegalArgumentException - if N is null

See Also:

• NodeManager.containsNode(Object)

setInterpreter

public void setInterpreter(T interpreter)

getNodeManager

protected NumberedNodeManager<CGNode> getNodeManager()

Specified by:

getNodeManager in class AbstractNumberedGraph<CGNode>

Returns:

the object which manages nodes in the graph

summarizeByPackage

public void summarizeByPackage()