Class SDG<T extends InstanceKey>

java.lang.Object

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

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

com.ibm.wala.ipa.slicer.SDG<T>

All Implemented Interfaces:

IClassHierarchyDweller, ISDG, EdgeManager<Statement>, Graph<Statement>, NodeManager<Statement>, NumberedEdgeManager<Statement>, NumberedGraph<Statement>, NumberedNodeManager<Statement>, Iterable<Statement>

public class SDG<T extends InstanceKey>
extends AbstractNumberedGraph<Statement>
implements ISDG

System dependence graph.

An SDG comprises a set of PDGs, one for each method. We compute these lazily.

Prototype implementation. Not efficient.

Constructor Summary

Constructors

Constructor	Description
SDG(CallGraph cg, PointerAnalysis<T> pa, ModRef<T> modRef, Slicer.DataDependenceOptions dOptions, Slicer.ControlDependenceOptions cOptions)
SDG(CallGraph cg, PointerAnalysis<T> pa, ModRef<T> modRef, Slicer.DataDependenceOptions dOptions, Slicer.ControlDependenceOptions cOptions, HeapExclusions heapExclude)
SDG(CallGraph cg, PointerAnalysis<T> pa, Slicer.DataDependenceOptions dOptions, Slicer.ControlDependenceOptions cOptions)

Method Summary

Modifier and Type	Method	Description
CallGraph	getCallGraph()
IClassHierarchy	getClassHierarchy()
Slicer.ControlDependenceOptions	getCOptions()	Slicer.ControlDependenceOptions used to construct this graph.
Slicer.DataDependenceOptions	getDOptions()
Set<? extends Dependency>	getEdgeLabels(Statement src, Statement dst)
protected NumberedEdgeManager<Statement>	getEdgeManager()
NumberedNodeManager<Statement>	getNodeManager()
PDG<T>	getPDG(CGNode node)	Get the program dependence graph constructed for a particular node.
PointerAnalysis<T>	getPointerAnalysis()
Iterator<? extends Statement>	iterateLazyNodes()	iterate over the nodes without constructing any new ones.
String	toString()	Use this with care.

Methods inherited from class AbstractNumberedGraph

getMaxNumber, getNode, getNumber, getPredNodeNumbers, getSuccNodeNumbers, iterateNodes

Modifier and Type	Method	Description
int	getMaxNumber()
Statement	getNode(int number)
int	getNumber(Statement N)
IntSet	getPredNodeNumbers(Statement node)
IntSet	getSuccNodeNumbers(Statement node)
Iterator<Statement>	iterateNodes(IntSet s)

Methods inherited from class AbstractGraph

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

Modifier and Type	Method	Description
void	addEdge(Statement src, Statement dst)
void	addNode(Statement n)	add a node to this graph
boolean	containsNode(Statement n)
protected String	edgeString(Statement from, Statement to)
int	getNumberOfNodes()
int	getPredNodeCount(Statement n)	Return the number of immediate predecessor nodes of n
Iterator<Statement>	getPredNodes(Statement n)	Return an Iterator over the immediate predecessor nodes of n
int	getSuccNodeCount(Statement n)	Return the number of immediate successor nodes of this Node in the Graph
Iterator<Statement>	getSuccNodes(Statement n)	Return an Iterator over the immediate successor nodes of n
boolean	hasEdge(Statement src, Statement dst)
Iterator<Statement>	iterator()
protected String	nodeString(Statement n, boolean forEdge)
void	removeAllIncidentEdges(Statement node)
void	removeEdge(Statement src, Statement dst)
void	removeIncomingEdges(Statement node)
void	removeNode(Statement n)	remove a node from this graph
void	removeNodeAndEdges(Statement N)	remove a node and all its incident edges
void	removeOutgoingEdges(Statement node)
Stream<Statement>	stream()

Methods inherited from class Object

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

Methods inherited from interface Iterable

forEach, spliterator

Constructor Details

SDG

public SDG(CallGraph cg,
 PointerAnalysis<T> pa,
 Slicer.DataDependenceOptions dOptions,
 Slicer.ControlDependenceOptions cOptions)

SDG

public SDG(CallGraph cg,
 PointerAnalysis<T> pa,
 ModRef<T> modRef,
 Slicer.DataDependenceOptions dOptions,
 Slicer.ControlDependenceOptions cOptions)

SDG

public SDG(CallGraph cg,
 PointerAnalysis<T> pa,
 ModRef<T> modRef,
 Slicer.DataDependenceOptions dOptions,
 Slicer.ControlDependenceOptions cOptions,
 HeapExclusions heapExclude)
    throws IllegalArgumentException

Throws:

IllegalArgumentException

Method Details

toString

public String toString()

Use this with care. This forces eager construction of the SDG, and SDGs can be big.

Overrides:

toString in class AbstractGraph<Statement>

See Also:

• AbstractGraph.toString()

iterateLazyNodes

public Iterator<? extends Statement> iterateLazyNodes()

iterate over the nodes without constructing any new ones. Use with extreme care. May break graph traversals that lazily add more nodes.

Specified by:

iterateLazyNodes in interface ISDG

getEdgeManager

protected NumberedEdgeManager<Statement> getEdgeManager()

Specified by:

getEdgeManager in class AbstractNumberedGraph<Statement>

Returns:

the object which manages edges in the graph

getNodeManager

public NumberedNodeManager<Statement> getNodeManager()

Specified by:

getNodeManager in class AbstractNumberedGraph<Statement>

Returns:

the object which manages nodes in the graph

getPDG

public PDG<T> getPDG(CGNode node)

Description copied from interface: ISDG

Get the program dependence graph constructed for a particular node.

Specified by:

getPDG in interface ISDG

getCOptions

public Slicer.ControlDependenceOptions getCOptions()

Description copied from interface: ISDG

Slicer.ControlDependenceOptions used to construct this graph.

Specified by:

getCOptions in interface ISDG

getDOptions

public Slicer.DataDependenceOptions getDOptions()

getCallGraph

public CallGraph getCallGraph()

getClassHierarchy

public IClassHierarchy getClassHierarchy()

Specified by:

getClassHierarchy in interface IClassHierarchyDweller

getPointerAnalysis

public PointerAnalysis<T> getPointerAnalysis()

getEdgeLabels

public Set<? extends Dependency> getEdgeLabels(Statement src,
 Statement dst)