Package soot.toolkits.graph

Toolkit to produce and manipulate various types of control flow graphs. While the CFG classes do not impose restrictions on the types of graph nodes, the nodes are typically instances of Unit or Block. The latter corresponds to basic blocks of Units. Some of the CFG classes include the control flow corresponding to thrown exceptions, while others abstract away exception-related edges.

Interface Summary

Interface	Description
DirectedBodyGraph<N>
DirectedGraph<N>	Defines the notion of a directed graph.
DominanceFrontier<N>	Interface to compute and/or store the dominance frontiers of nodes in a dominator tree.
DominatorsFinder<N>	General interface for a dominators analysis.
EdgeLabelledDirectedGraph<N,L>	A DirectedGraph with labels on the edges.
ExceptionalGraph<N>	Defines the interface for navigating a control flow graph which distinguishes exceptional control flow.
ExceptionalGraph.ExceptionDest<N>	Data structure to represent the fact that a given Trap will catch some subset of the exceptions which may be thrown by a given graph node.
MutableDirectedGraph<N>	Defines a DirectedGraph which is modifiable.
MutableEdgeLabelledDirectedGraph<N,L>	Defines a DirectedGraph which is modifiable and associates a label object with every edge.
Orderer<N>	An orderer builds an order on a directed, not necessarily acyclic, graph.
ReversibleGraph<N>	DirectedGraph which can be reversed and re-reversed.

Class Summary

Class	Description
ArrayRefBlockGraph	A CFG where the nodes are Block instances, and where Units which include array references start new blocks.
Block	Represents BasicBlocks that partition a method body.
BlockGraph	Represents the control flow graph of a Body at the basic block level.
BlockGraphConverter	This utility class can convert any BlockGraph to a single-headed and single-tailed graph by inserting appropriate Start or Stop nodes.
BriefBlockGraph	Represents a CFG for a Body where the nodes are Blocks and edges are derived from control flow.
BriefUnitGraph	Represents a CFG where the nodes are Unit instances, and where no edges are included to account for control flow associated with exceptions.
ClassicCompleteBlockGraph	Represents a CFG where the nodes are Blocks and the edges are derived from control flow.
ClassicCompleteUnitGraph	Represents a CFG for a Body instance where the nodes are Unit instances, and where edges are a conservative indication of unexceptional and exceptional control flow.
CompleteBlockGraph	Represents a CFG for a Body instance where the nodes are Block instances, and where control flow associated with exceptions is taken into account.
CompleteUnitGraph	Represents a CFG for a Body instance where the nodes are Unit instances, and where control flow associated with exceptions is taken into account.
CytronDominanceFrontier<N>	Class to compute the DominanceFrontier using Cytron's celebrated efficient algorithm.
DominatorAnalysis	Deprecated. use MHGDominatorsFinder instead
DominatorNode<N>	Represents a dominator node in DominatorTree.
DominatorTree<N>	Constructs a dominator tree structure from the given DominatorsFinder.
DominatorTreeAdapter<N>	This adapter provides a DirectedGraph interface to DominatorTree.
ExceptionalBlockGraph	Represents a CFG where the nodes are Blocks and the edges are derived from control flow.
ExceptionalBlockGraph.ExceptionDest
ExceptionalUnitGraph	Represents a control flow graph for a Body instance where the nodes are Unit instances, and where control flow associated with exceptions is taken into account.
ExceptionalUnitGraph.ExceptionDest
ExceptionalUnitGraphFactory
HashMutableDirectedGraph<N>	HashMap based implementation of a MutableBlockGraph.
HashMutableEdgeLabelledDirectedGraph<N,L>	HashMap based implementation of a MutableEdgeLabelledDirectedGraph.
HashMutableEdgeLabelledDirectedGraph.DGEdge<N>
HashReversibleGraph<N>	A reversible version of HashMutableDirectedGraph
InverseGraph<N>	An inverted graph of a directed graph.
LoopNestTree	A loop nesting tree, implemented as a tree-map.
MemoryEfficientGraph<N>	A memory efficient version of HashMutableDirectedGraph, in the sense that throw-away objects passed as arguments will not be kept in the process of adding edges.
MHGDominatorsFinder<N>	Calculate dominators for basic blocks.
MHGPostDominatorsFinder<N>	Post-dominators finder for multi-headed graph.
PostDominatorAnalysis	Deprecated. use MHGPostDominatorsFinder instead
PseudoTopologicalOrderer<N>	Orders in pseudo-topological order, the nodes of a DirectedGraph instance.
ReversePseudoTopologicalOrderer<N>	Deprecated. use PseudoTopologicalOrderer.newList(DirectedGraph, boolean) instead
SimpleDominatorsFinder<N>	Wrapper class for a simple dominators analysis based on a simple flow analysis algorithm.
SlowPseudoTopologicalOrderer<N>	Provide the pseudo topological order of a graph's nodes.
StronglyConnectedComponents	Deprecated. implementation is inefficient; use StronglyConnectedComponentsFast instead
StronglyConnectedComponentsFast<N>	Identifies and provides an interface to query the strongly-connected components of DirectedGraph instances.
TrapUnitGraph	Represents a CFG for a Body instance where the nodes are Unit instances, and where, in additional to unexceptional control flow edges, edges are added from every trapped Unit to the Trap's handler Unit, regardless of whether the trapped Units may actually throw the exception caught by the Trap.
UnitGraph	Represents a CFG where the nodes are Unit instances and edges represent unexceptional and (possibly) exceptional control flow between Units.
ZonedBlockGraph	A CFG where the nodes are Block instances, and where exception boundaries are taken into account when finding the Blocks for the provided Body.