Class BackwardsSupergraph<T,P>
java.lang.Object
com.ibm.wala.dataflow.IFDS.BackwardsSupergraph<T,P>
- All Implemented Interfaces:
ISupergraph<T,
,P> EdgeManager<T>
,Graph<T>
,NodeManager<T>
,NumberedEdgeManager<T>
,NumberedGraph<T>
,NumberedNodeManager<T>
,Iterable<T>
A "reversed" supergraph for backwards analysis.
In this view, a return is treated like a call, and vice-versa. All normal edges are reversed.
-
Field Summary
Fields inherited from interface com.ibm.wala.dataflow.IFDS.ISupergraph
CALL_EDGE, CALL_TO_RETURN_EDGE, OTHER, RETURN_EDGE
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionvoid
void
add a node to this graphbyte
classifyEdge
(T src, T dest) boolean
containsNode
(T N) getCalledNodes
(T ret) get the "called" (sic) nodes for a return site; i.e., the exit nodes that flow directly to this return site.getCallSites
(T r, P callee) T[]
getEntriesForProcedure
(P object) T[]
getExitsForProcedure
(P object) getLocalBlock
(P procedure, int i) int
int
getNode
(int number) getNormalSuccessors
(T ret) get the "normal" successors (sic) for a return site; i.e., the "normal" CFG predecessors that are not call nodes.int
int
getNumberOfBlocks
(P procedure) int
int
Return the number ofimmediate predecessor
nodes of ngetPredNodeNumbers
(Object node) getPredNodes
(T N) Return anIterator
over the immediate predecessor nodes of nTODO: for now, this is not inverted.getReturnSites
(T c, P callee) int
Return the number ofimmediate successor
nodes of this Node in the GraphgetSuccNodeNumbers
(T node) getSuccNodes
(T N) Return an Iterator over the immediate successor nodes of nboolean
boolean
boolean
boolean
boolean
iterator()
static <T,
P> BackwardsSupergraph <T, P> make
(ISupergraph<T, P> forwardGraph) void
removeAllIncidentEdges
(Object node) void
removeEdge
(Object src, Object dst) void
removeIncomingEdges
(Object node) void
removeNode
(Object n) remove a node from this graphvoid
remove a node and all its incident edgesvoid
removeOutgoingEdges
(T node) stream()
toString()
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Constructor Details
-
BackwardsSupergraph
- Parameters:
forwardGraph
- the graph to ``reverse''
-
-
Method Details
-
make
-
getProcedureGraph
TODO: for now, this is not inverted.- Specified by:
getProcedureGraph
in interfaceISupergraph<T,
P> - Returns:
- the graph of procedures (e.g. a call graph) over which this supergraph is induced.
-
isCall
- Specified by:
isCall
in interfaceISupergraph<T,
P> - Parameters:
n
- a node in this supergraph- Returns:
- true iff this node includes a call.
-
getCalledNodes
get the "called" (sic) nodes for a return site; i.e., the exit nodes that flow directly to this return site.- Specified by:
getCalledNodes
in interfaceISupergraph<T,
P> - Parameters:
ret
- a "call" node in the supergraph- Returns:
- an Iterator of nodes that are targets of this call.
-
getNormalSuccessors
get the "normal" successors (sic) for a return site; i.e., the "normal" CFG predecessors that are not call nodes.- Specified by:
getNormalSuccessors
in interfaceISupergraph<T,
P> - Parameters:
ret
- a "call" node in the supergraph- Returns:
- an Iterator of nodes that are normal (non-call) successors of this call. This should only apply to backwards problems, where we might have, say, a call and a goto flow into a return site.
- See Also:
-
getReturnSites
- Specified by:
getReturnSites
in interfaceISupergraph<T,
P> - Parameters:
c
- a "call" node in the supergraphcallee
- a "called" "procedure" in the supergraph. if callee is null, answer return sites for which no callee was found.- Returns:
- the corresponding return nodes. There may be many, because of exceptional control flow.
-
isExit
- Specified by:
isExit
in interfaceISupergraph<T,
P> - Parameters:
n
- a node in the supergraph- Returns:
- true iff this node is an exit node
-
getProcOf
-
removeNodeAndEdges
Description copied from interface:Graph
remove a node and all its incident edges- Specified by:
removeNodeAndEdges
in interfaceGraph<T>
- Throws:
UnsupportedOperationException
- if the graph implementation does not allow removal- See Also:
-
iterator
-
stream
-
getNumberOfNodes
public int getNumberOfNodes()- Specified by:
getNumberOfNodes
in interfaceNodeManager<T>
- Returns:
- the number of nodes in this graph
- See Also:
-
addNode
Description copied from interface:NodeManager
add a node to this graph- Specified by:
addNode
in interfaceNodeManager<T>
- Throws:
UnsupportedOperationException
- See Also:
-
removeNode
Description copied from interface:NodeManager
remove a node from this graph- Specified by:
removeNode
in interfaceNodeManager<T>
- Throws:
UnsupportedOperationException
- See Also:
-
containsNode
- Specified by:
containsNode
in interfaceNodeManager<T>
- Returns:
- true iff the graph contains the specified node
- See Also:
-
getPredNodes
Description copied from interface:EdgeManager
Return anIterator
over the immediate predecessor nodes of nThis method never returns
null
.- Specified by:
getPredNodes
in interfaceEdgeManager<T>
- Returns:
- an
Iterator
over the immediate predecessor nodes of this Node. - See Also:
-
getPredNodeCount
Description copied from interface:EdgeManager
Return the number ofimmediate predecessor
nodes of n- Specified by:
getPredNodeCount
in interfaceEdgeManager<T>
- Returns:
- the number of immediate predecessors of n.
- See Also:
-
getSuccNodes
Description copied from interface:EdgeManager
Return an Iterator over the immediate successor nodes of nThis method never returns
null
.- Specified by:
getSuccNodes
in interfaceEdgeManager<T>
- Returns:
- an Iterator over the immediate successor nodes of n
- See Also:
-
hasEdge
- Specified by:
hasEdge
in interfaceEdgeManager<T>
-
getSuccNodeCount
Description copied from interface:EdgeManager
Return the number ofimmediate successor
nodes of this Node in the Graph- Specified by:
getSuccNodeCount
in interfaceEdgeManager<T>
- Returns:
- the number of immediate successor Nodes of this Node in the Graph.
- See Also:
-
addEdge
- Specified by:
addEdge
in interfaceEdgeManager<T>
- Throws:
UnsupportedOperationException
- See Also:
-
removeEdge
- Specified by:
removeEdge
in interfaceEdgeManager<T>
- Throws:
UnsupportedOperationException
-
removeAllIncidentEdges
- Specified by:
removeAllIncidentEdges
in interfaceEdgeManager<T>
- Throws:
UnsupportedOperationException
- See Also:
-
getEntriesForProcedure
- Specified by:
getEntriesForProcedure
in interfaceISupergraph<T,
P> - Returns:
- the blocks in the supergraph that represents entry nodes for procedure p
-
getExitsForProcedure
- Specified by:
getExitsForProcedure
in interfaceISupergraph<T,
P> - Returns:
- the blocks in the supergraph that represents exit nodes for procedure p
- See Also:
-
isReturn
- Specified by:
isReturn
in interfaceISupergraph<T,
P> - Parameters:
n
- a node in this supergraph- Returns:
- true iff this node is a return site.
- Throws:
UnimplementedError
-
getCallSites
- Specified by:
getCallSites
in interfaceISupergraph<T,
P> - Parameters:
r
- a "return" node in the supergraphcallee
- a "called" "procedure" in the supergraph. if callee is null, answer return sites for which no callee was found.- Returns:
- the corresponding call nodes. There may be many.
-
isEntry
- Specified by:
isEntry
in interfaceISupergraph<T,
P> - Returns:
- true iff this node is an entry node s_p for a procedure
-
classifyEdge
- Specified by:
classifyEdge
in interfaceISupergraph<T,
P> - Parameters:
src
- node in the supergraphdest
- a successor of src in the supergraph- Returns:
- one of CALL_EDGE, RETURN_EDGE, CALL_TO_RETURN_EDGE, or OTHER
-
toString
-
removeIncomingEdges
- Specified by:
removeIncomingEdges
in interfaceEdgeManager<T>
- Throws:
UnsupportedOperationException
-
removeOutgoingEdges
- Specified by:
removeOutgoingEdges
in interfaceEdgeManager<T>
- Throws:
UnsupportedOperationException
-
getNumberOfBlocks
- Specified by:
getNumberOfBlocks
in interfaceISupergraph<T,
P> - Parameters:
procedure
- an object that represents a procedure- Returns:
- the number of blocks from this procedure in this supergraph
-
getLocalBlockNumber
- Specified by:
getLocalBlockNumber
in interfaceISupergraph<T,
P> - Parameters:
n
- a node in the supergraph- Returns:
- the "logical" basic block number of n in its procedure
-
getLocalBlock
- Specified by:
getLocalBlock
in interfaceISupergraph<T,
P> - Parameters:
procedure
- an object that represents a procedurei
- the "logical" basic block number of a node in the procedure- Returns:
- the corresponding node in the supergraph
-
getNumber
- Specified by:
getNumber
in interfaceNumberedNodeManager<T>
-
getNode
- Specified by:
getNode
in interfaceNumberedNodeManager<T>
-
getMaxNumber
public int getMaxNumber()- Specified by:
getMaxNumber
in interfaceNumberedNodeManager<T>
-
iterateNodes
- Specified by:
iterateNodes
in interfaceNumberedNodeManager<T>
- Returns:
- iterator of nodes with the numbers in set s
- Throws:
UnimplementedError
-
getSuccNodeNumbers
- Specified by:
getSuccNodeNumbers
in interfaceNumberedEdgeManager<T>
- Returns:
- the numbers identifying the immediate successors of node
-
getPredNodeNumbers
- Specified by:
getPredNodeNumbers
in interfaceNumberedEdgeManager<T>
- Returns:
- the numbers identifying the immediate predecessors of node
- Throws:
UnimplementedError
-