com.ibm.wala.ipa.callgraph.impl
Class BasicCallGraph

java.lang.Object
  com.ibm.wala.util.graph.AbstractGraph<T>
      com.ibm.wala.util.graph.AbstractNumberedGraph<CGNode>
          com.ibm.wala.ipa.callgraph.impl.BasicCallGraph

All Implemented Interfaces:

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

Direct Known Subclasses:

ExplicitCallGraph

public abstract class BasicCallGraph
extends AbstractNumberedGraph<CGNode>
implements CallGraph

Basic data structure support for a call graph.

Nested Class Summary

protected static class	BasicCallGraph.Key
class	BasicCallGraph.NodeImpl A class that represents the a normal node in a call graph.

Constructor Summary

BasicCallGraph()

Method Summary

boolean	containsNode(CGNode N) This implementation is necessary because the underlying SparseNumberedGraph may not support node membership tests.
void	dump(java.lang.String filename) Dump this callgraph to the specified file in dotty(1) format.
abstract CGNode	findOrCreateNode(IMethod method, Context C) Method findOrCreateNode.
java.util.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()
SSAContextInterpreter	getInterpreter(CGNode node)
protected BasicCallGraph.NodeImpl	getNode(BasicCallGraph.Key K)
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 NodeManager<CGNode>	getNodeManager()
java.util.Set<CGNode>	getNodes(MethodReference m)
int	getNumberOfNodes() We override this since this class supports remove() on nodes, but the superclass doesn't.
void	init()
java.util.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()
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(SSAContextInterpreter interpreter)
java.lang.String	toString()

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

getMaxNumber, getNode, getNumber, getPredNodeNumbers, getSuccNodeNumbers, iterateNodes

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

addEdge, addNode, getEdgeManager, getPredNodeCount, getPredNodes, getSuccNodeCount, getSuccNodes, hasEdge, removeAllIncidentEdges, removeEdge, removeIncomingEdges, removeNode, removeOutgoingEdges

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

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

addNode, removeNode

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

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

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

getMaxNumber, getNode, getNumber, iterateNodes

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

addNode, removeNode

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

getPredNodeNumbers, getSuccNodeNumbers

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

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

Constructor Detail

BasicCallGraph

public BasicCallGraph()

Method Detail

init

public void init()

makeFakeRootNode

protected abstract CGNode makeFakeRootNode()

makeFakeWorldClinitNode

protected abstract CGNode makeFakeWorldClinitNode()

findOrCreateNode

public abstract CGNode findOrCreateNode(IMethod method,
                                        Context C)

Method findOrCreateNode. use with extreme care.

Parameters:

method -

Returns:

NodeImpl

registerNode

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

getNode

protected BasicCallGraph.NodeImpl 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()

registerEntrypoint

public void registerEntrypoint(CGNode node)

record that a node is an entrypoint

getEntrypointNodes

public java.util.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 java.lang.String toString()

Overrides:

toString in class AbstractGraph<CGNode>

dump

public void dump(java.lang.String filename)

Dump this callgraph to the specified file in dotty(1) format.

Specified by:

dump in interface CallGraph

Throws:

java.lang.IllegalArgumentException - if filename is null

removeNodeAndEdges

public void removeNodeAndEdges(CGNode N)

Description copied from interface: Graph

remove a node and all its incident edges

Specified by:

removeNodeAndEdges in interface Graph<CGNode>

Overrides:

removeNodeAndEdges in class AbstractGraph<CGNode>

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

Parameters:

method -

Returns:

NodeImpl, or null if none found

getNodes

public java.util.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

public SSAContextInterpreter getInterpreter(CGNode 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<CGNode>

Overrides:

getNumberOfNodes in class AbstractGraph<CGNode>

Returns:

the number of nodes in this graph

See Also:

NodeManager.getNumberOfNodes()

iterator

public java.util.Iterator<CGNode> iterator()

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

Specified by:

iterator in interface NodeManager<CGNode>

Specified by:

iterator in interface java.lang.Iterable<CGNode>

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<CGNode>

Overrides:

containsNode in class AbstractGraph<CGNode>

Returns:

true iff the graph contains the specified node

Throws:

java.lang.IllegalArgumentException - if N is null

setInterpreter

public void setInterpreter(SSAContextInterpreter interpreter)

Parameters:

interpreter -

getNodeManager

protected NodeManager<CGNode> getNodeManager()

Specified by:

getNodeManager in class AbstractGraph<CGNode>

Returns:

the object which manages nodes in the graph