soot.toolkits.graph
Class UnitGraph

java.lang.Object
  extended bysoot.toolkits.graph.UnitGraph
All Implemented Interfaces:
DirectedGraph
Direct Known Subclasses:
BriefUnitGraph, ExceptionalUnitGraph, TrapUnitGraph

public abstract class UnitGraph
extends Object
implements DirectedGraph

Represents a CFG where the nodes are Unit instances and edges represent unexceptional and (possibly) exceptional control flow between Units.

This is an abstract class, providing the facilities used to build CFGs for specific purposes.


Field Summary
protected  Body body
           
protected  SootMethod method
           
protected  Chain unitChain
           
protected  Map unitToPreds
           
protected  Map unitToSuccs
           
 
Constructor Summary
protected UnitGraph(Body body)
          Performs the work that is required to construct any sort of UnitGraph.
 
Method Summary
protected  void addEdge(Map unitToSuccs, Map unitToPreds, Unit head, Unit tail)
          Utility method for adding an edge to maps representing the CFG.
protected  void buildHeadsAndTails()
          Utility method used in the construction of UnitGraphs, to be called only after the unitToPreds and unitToSuccs maps have been built.
protected  void buildUnexceptionalEdges(Map unitToSuccs, Map unitToPreds)
          Utility method for UnitGraph constructors.
protected  Map combineMapValues(Map mapA, Map mapB)
          Utility method that produces a new map from the Units of this graph's body to the union of the values stored in the two argument Maps, used to combine the maps of exceptional and unexceptional predecessors and successors into maps of all predecessors and successors.
 Body getBody()
           
 List getExtendedBasicBlockPathBetween(Unit from, Unit to)
          Look for a path in graph, from def to use.
 List getHeads()
          Returns a list of entry points for this graph.
 List getPredsOf(Object u)
          Returns a list of predecessors for the given node in the graph.
 List getSuccsOf(Object u)
          Returns a list of successors for the given node in the graph.
 List getTails()
          Returns a list of exit points for this graph.
 Iterator iterator()
          Returns an iterator for the nodes in this graph.
protected static void makeMappedListsUnmodifiable(Map map)
          Utility method that replaces the values of a Map, which must be instances of List, with unmodifiable equivalents.
 int size()
          Returns the node count for this graph.
 String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

unitToSuccs

protected Map unitToSuccs

unitToPreds

protected Map unitToPreds

method

protected SootMethod method

body

protected Body body

unitChain

protected Chain unitChain
Constructor Detail

UnitGraph

protected UnitGraph(Body body)
Performs the work that is required to construct any sort of UnitGraph.

Parameters:
body - The body of the method for which to construct a control flow graph.
Method Detail

buildUnexceptionalEdges

protected void buildUnexceptionalEdges(Map unitToSuccs,
                                       Map unitToPreds)
Utility method for UnitGraph constructors. It computes the edges corresponding to unexceptional control flow.

Parameters:
unitToSuccs - A Map from Units to Lists of Units. This is an ``out parameter''; callers must pass an empty Map. buildUnexceptionalEdges will add a mapping for every Unit in the body to a list of its unexceptional successors.
unitToPreds - A Map from Units to Lists of Units. This is an ``out parameter''; callers must pass an empty Map. buildUnexceptionalEdges will add a mapping for every Unit in the body to a list of its unexceptional predecessors.

buildHeadsAndTails

protected void buildHeadsAndTails()

Utility method used in the construction of UnitGraphs, to be called only after the unitToPreds and unitToSuccs maps have been built.

UnitGraph provides an implementation of buildHeadsAndTails() which defines the graph's set of heads to include the first Unit in the graph's body, together with any other Unit which has no predecessors. It defines the graph's set of tails to include all Units with no successors. Subclasses of UnitGraph may override this method to change the criteria for classifying a node as a head or tail.


makeMappedListsUnmodifiable

protected static void makeMappedListsUnmodifiable(Map map)
Utility method that replaces the values of a Map, which must be instances of List, with unmodifiable equivalents.

Parameters:
map - The map whose values are to be made unmodifiable.

combineMapValues

protected Map combineMapValues(Map mapA,
                               Map mapB)
Utility method that produces a new map from the Units of this graph's body to the union of the values stored in the two argument Maps, used to combine the maps of exceptional and unexceptional predecessors and successors into maps of all predecessors and successors. The values stored in both argument maps must be Lists of Units, which are assumed not to contain any duplicate Units.

Parameters:
mapA - The first map to be combined.
mapB - The second map to be combined.

addEdge

protected void addEdge(Map unitToSuccs,
                       Map unitToPreds,
                       Unit head,
                       Unit tail)
Utility method for adding an edge to maps representing the CFG.

Parameters:
unitToSuccs - The Map from Units to Lists of their successors.
unitToPreds - The Map from Units to Lists of their successors.
head - The Unit from which the edge starts.
tail - The Unit to which the edge flows.

getBody

public Body getBody()
Returns:
The body from which this UnitGraph was built.
See Also:
Body

getExtendedBasicBlockPathBetween

public List getExtendedBasicBlockPathBetween(Unit from,
                                             Unit to)
Look for a path in graph, from def to use. This path has to lie inside an extended basic block (and this property implies uniqueness.). The path returned includes from and to.

Parameters:
from - start point for the path.
to - end point for the path.
Returns:
null if there is no such path.

getHeads

public List getHeads()
Description copied from interface: DirectedGraph
Returns a list of entry points for this graph.

Specified by:
getHeads in interface DirectedGraph

getTails

public List getTails()
Description copied from interface: DirectedGraph
Returns a list of exit points for this graph.

Specified by:
getTails in interface DirectedGraph

getPredsOf

public List getPredsOf(Object u)
Description copied from interface: DirectedGraph
Returns a list of predecessors for the given node in the graph.

Specified by:
getPredsOf in interface DirectedGraph

getSuccsOf

public List getSuccsOf(Object u)
Description copied from interface: DirectedGraph
Returns a list of successors for the given node in the graph.

Specified by:
getSuccsOf in interface DirectedGraph

size

public int size()
Description copied from interface: DirectedGraph
Returns the node count for this graph.

Specified by:
size in interface DirectedGraph

iterator

public Iterator iterator()
Description copied from interface: DirectedGraph
Returns an iterator for the nodes in this graph. No specific ordering of the nodes is guaranteed.

Specified by:
iterator in interface DirectedGraph

toString

public String toString()