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 class
BasicCallGraph.Key
class
BasicCallGraph.NodeImpl
A class that represents the a normal node in a call graph.
-
Field Summary
Fields Modifier and Type Field Description protected 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
All Methods Instance Methods Abstract Methods Concrete Methods 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 entrypointsCGNode
getFakeRootNode()
Return the (fake) interproceduralroot 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 usegetNodes
protected BasicCallGraph.NodeImpl
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()
void
registerEntrypoint(CGNode node)
record that a node is an entrypointprotected void
registerNode(BasicCallGraph.Key K, CGNode N)
void
removeNodeAndEdges(CGNode N)
remove a node and all its incident edgesvoid
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, 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, 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
-
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 Detail
-
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.
-
-
Method Detail
-
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 BasicCallGraph.NodeImpl getNode(BasicCallGraph.Key K)
-
getFakeRootNode
public CGNode getFakeRootNode()
Description copied from interface:CallGraph
Return the (fake) interproceduralroot node
of the call graph.- Specified by:
getFakeRootNode
in interfaceCallGraph
- Returns:
- the "fake" root node the call graph
-
getFakeWorldClinitNode
public CGNode getFakeWorldClinitNode()
- Specified by:
getFakeWorldClinitNode
in interfaceCallGraph
-
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 interfaceCallGraph
- Returns:
- an Iterator of the nodes designated as "root nodes"
-
toString
public String toString()
- Overrides:
toString
in classAbstractGraph<CGNode>
-
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 interfaceGraph<T>
- Overrides:
removeNodeAndEdges
in classAbstractGraph<CGNode>
- Throws:
UnimplementedError
-
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 usegetNodes
-
getNodes
public Set<CGNode> getNodes(MethodReference m)
-
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 interfaceNodeManager<T>
- Overrides:
getNumberOfNodes
in classAbstractGraph<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 interfaceIterable<T>
- Specified by:
iterator
in interfaceNodeManager<T>
- Overrides:
iterator
in classAbstractGraph<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 interfaceNodeManager<T>
- Overrides:
containsNode
in classAbstractGraph<CGNode>
- Returns:
- true iff the graph contains the specified node
- Throws:
IllegalArgumentException
- if N is null
-
setInterpreter
public void setInterpreter(T interpreter)
-
getNodeManager
protected NumberedNodeManager<CGNode> getNodeManager()
- Specified by:
getNodeManager
in classAbstractNumberedGraph<CGNode>
- Returns:
- the object which manages nodes in the graph
-
summarizeByPackage
public void summarizeByPackage()
-
-