soot.toolkits.graph
Class ExceptionalUnitGraph

java.lang.Object
  soot.toolkits.graph.UnitGraph
      soot.toolkits.graph.ExceptionalUnitGraph

All Implemented Interfaces:

Iterable<Unit>, DirectedGraph<Unit>, ExceptionalGraph<Unit>

Direct Known Subclasses:

CompleteUnitGraph

public class ExceptionalUnitGraph
extends UnitGraph
implements ExceptionalGraph<Unit>

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.

To describe precisely the circumstances under which exceptional edges are added to the graph, we need to distinguish the exceptions thrown explicitly by a throw instruction from the exceptions which are thrown implicitly by the VM to signal an error it encounters in the course of executing an instruction, which need not be a throw.

For every ThrowInst or ThrowStmt Unit which may explicitly throw an exception that would be caught by a Trap in the Body, there will be an edge from the throw Unit to the Trap handler's first Unit.

For every Unit which may implicitly throw an exception that could be caught by a Trap in the Body, there will be an edge from each of the excepting Unit's predecessors to the Trap handler's first Unit (since any of those predecessors may have been the last Unit to complete execution before the handler starts execution). If the excepting Unit might have the side effect of changing some field, then there will definitely be an edge from the excepting Unit itself to its handlers, since the side effect might occur before the exception is raised. If the excepting Unit has no side effects, then parameters passed to the ExceptionalUnitGraph constructor determine whether or not there is an edge from the excepting Unit itself to the handler Unit.

Nested Class Summary

static class

ExceptionalUnitGraph.ExceptionDest

Field Summary

protected ThrowAnalysis	throwAnalysis
protected Map<Unit,List<Unit>>	unitToExceptionalPreds
protected Map<Unit,List<Unit>>	unitToExceptionalSuccs
protected Map<Unit,Collection<ExceptionalUnitGraph.ExceptionDest>>	unitToExceptionDests
protected Map<Unit,List<Unit>>	unitToUnexceptionalPreds
protected Map<Unit,List<Unit>>	unitToUnexceptionalSuccs

Fields inherited from class soot.toolkits.graph.UnitGraph

body, heads, method, tails, unitChain, unitToPreds, unitToSuccs

Constructor Summary

	ExceptionalUnitGraph(Body body) Constructs the graph from a given Body instance, using the Scene's default ThrowAnalysis to estimate the set of exceptions that each Unit might throw and a default value, provided by the Options class, for the omitExceptingUnitEdges parameter.
protected	ExceptionalUnitGraph(Body body, boolean ignoredBogusParameter) Allocates an ExceptionalUnitGraph object without initializing it.
	ExceptionalUnitGraph(Body body, ThrowAnalysis throwAnalysis) Constructs the graph from a given Body instance using the passed ThrowAnalysis and a default value, provided by the Options class, for the omitExceptingUnitEdges parameter.
	ExceptionalUnitGraph(Body body, ThrowAnalysis throwAnalysis, boolean omitExceptingUnitEdges) Constructs the graph for a given Body instance, using the ThrowAnalysis and omitExceptingUnitEdges value that are passed as parameters.

Method Summary

protected Set<Unit>	buildExceptionalEdges(ThrowAnalysis throwAnalysis, Map<Unit,Collection<ExceptionalUnitGraph.ExceptionDest>> unitToExceptionDests, Map<Unit,List<Unit>> unitToSuccs, Map<Unit,List<Unit>> unitToPreds, boolean omitExceptingUnitEdges) Method to compute the edges corresponding to exceptional control flow.
protected Map<Unit,Collection<ExceptionalUnitGraph.ExceptionDest>>	buildExceptionDests(ThrowAnalysis throwAnalysis) Utility method used in the construction of UnitGraph variants which include exceptional control flow.
protected void	buildHeadsAndTails() A placeholder that overrides UnitGraph.buildHeadsAndTails() with a method which always throws an exception.
List<Unit>	getExceptionalPredsOf(Unit u) Returns a list of nodes which are predecessors of a given node when only exceptional control flow is considered.
List<Unit>	getExceptionalSuccsOf(Unit u) Returns a list of nodes which are successors of a given node when only exceptional control flow is considered.
Collection<ExceptionalUnitGraph.ExceptionDest>	getExceptionDests(Unit u) Returns a collection of ExceptionDest objects which represent how exceptions thrown by a specified unit will be handled.
List<Unit>	getUnexceptionalPredsOf(Unit u) Returns a list of nodes which are predecessors of a given node when only unexceptional control flow is considered.
List<Unit>	getUnexceptionalSuccsOf(Unit u) Returns a list of nodes which are successors of a given node when only unexceptional control flow is considered.
protected void	initialize(ThrowAnalysis throwAnalysis, boolean omitExceptingUnitEdges) Performs the real work of constructing an ExceptionalUnitGraph, factored out of the constructors so that subclasses have the option to delay creating the graph's edges until after they have performed some subclass-specific initialization.
String	toString()

Methods inherited from class soot.toolkits.graph.UnitGraph

addEdge, buildUnexceptionalEdges, combineMapValues, getBody, getExtendedBasicBlockPathBetween, getHeads, getPredsOf, getSuccsOf, getTails, iterator, makeMappedListsUnmodifiable, size

Methods inherited from class java.lang.Object

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

Methods inherited from interface soot.toolkits.graph.ExceptionalGraph

getBody

Methods inherited from interface soot.toolkits.graph.DirectedGraph

getHeads, getPredsOf, getSuccsOf, getTails, iterator, size

Field Detail

unitToUnexceptionalSuccs

protected Map<Unit,List<Unit>> unitToUnexceptionalSuccs

unitToUnexceptionalPreds

protected Map<Unit,List<Unit>> unitToUnexceptionalPreds

unitToExceptionalSuccs

protected Map<Unit,List<Unit>> unitToExceptionalSuccs

unitToExceptionalPreds

protected Map<Unit,List<Unit>> unitToExceptionalPreds

unitToExceptionDests

protected Map<Unit,Collection<ExceptionalUnitGraph.ExceptionDest>> unitToExceptionDests

throwAnalysis

protected ThrowAnalysis throwAnalysis

Constructor Detail

ExceptionalUnitGraph

public ExceptionalUnitGraph(Body body,
                            ThrowAnalysis throwAnalysis,
                            boolean omitExceptingUnitEdges)

Constructs the graph for a given Body instance, using the ThrowAnalysis and omitExceptingUnitEdges value that are passed as parameters.

Parameters:

body - the Body from which to build a graph.

throwAnalysis - the source of information about the exceptions which each Unit may throw.

omitExceptingUnitEdges - indicates whether the CFG should omit edges to a handler from trapped Units which may implicitly throw an exception which the handler catches but which have no potential side effects. The CFG will contain edges to the handler from all predecessors of Units which may implicitly throw a caught exception regardless of the setting for this parameter. If this parameter is false, there will also be edges to the handler from all the potentially excepting Units themselves. If this parameter is true, there will be edges to the handler from the excepting Units themselves only if they have potential side effects (or if they are themselves the predecessors of other potentially excepting Units). A setting of true produces CFGs which allow for more precise analyses, since a Unit without side effects has no effect on the computational state when it throws an exception. Use settings of false for compatibility with more conservative analyses, or to cater to conservative bytecode verifiers.

ExceptionalUnitGraph

public ExceptionalUnitGraph(Body body,
                            ThrowAnalysis throwAnalysis)

Constructs the graph from a given Body instance using the passed ThrowAnalysis and a default value, provided by the Options class, for the omitExceptingUnitEdges parameter.

Parameters:

body - the Body from which to build a graph.

throwAnalysis - the source of information about the exceptions which each Unit may throw.

ExceptionalUnitGraph

public ExceptionalUnitGraph(Body body)

Constructs the graph from a given Body instance, using the Scene's default ThrowAnalysis to estimate the set of exceptions that each Unit might throw and a default value, provided by the Options class, for the omitExceptingUnitEdges parameter.

Parameters:

body - the Body from which to build a graph.

ExceptionalUnitGraph

protected ExceptionalUnitGraph(Body body,
                               boolean ignoredBogusParameter)

Allocates an ExceptionalUnitGraph object without initializing it. This “partial constructor” is provided for the benefit of subclasses whose constructors need to perform some subclass-specific processing before actually creating the graph edges (because, for example, the subclass overrides a utility method like buildExceptionDests(ThrowAnalysis) or buildExceptionalEdges(ThrowAnalysis, Map, Map, Map, boolean) with a replacement method that depends on additional parameters passed to the subclass's constructor). The subclass constructor is responsible for calling initialize(ThrowAnalysis, boolean), or otherwise performing the initialization required to implement ExceptionalUnitGraph's interface.

Clients who opt to extend ExceptionalUnitGraph should be warned that the class has not been carefully designed for inheritance; code that uses the protected members of this class may need to be rewritten for each new Soot release.

Parameters:

body - the Body from which to build a graph.

ignoredBogusParameter - a meaningless placeholder, which exists solely to distinguish this constructor from the public ExceptionalUnitGraph(Body) constructor.

Method Detail

initialize

protected void initialize(ThrowAnalysis throwAnalysis,
                          boolean omitExceptingUnitEdges)

Performs the real work of constructing an ExceptionalUnitGraph, factored out of the constructors so that subclasses have the option to delay creating the graph's edges until after they have performed some subclass-specific initialization.

Parameters:

throwAnalysis - the source of information about the exceptions which each Unit may throw.

omitExceptingUnitEdges - indicates whether the CFG should omit edges to a handler from trapped Units which may throw an exception which the handler catches but which have no potential side effects.

buildExceptionDests

protected Map<Unit,Collection<ExceptionalUnitGraph.ExceptionDest>> buildExceptionDests(ThrowAnalysis throwAnalysis)

Utility method used in the construction of UnitGraph variants which include exceptional control flow. It determines which Units may throw exceptions that would be caught by Traps within the method.

Parameters:

throwAnalysis - The source of information about which exceptions each Unit may throw.

Returns:

null if no Units in the method throw any exceptions caught within the method. Otherwise, a Map from Units to Collections of ExceptionalUnitGraph.ExceptionDests.

The returned map has an idiosyncracy which is hidden from most client code, but which is exposed to subclasses extending ExceptionalUnitGraph. If a Unit throws one or more exceptions which are caught within the method, it will be mapped to a Collection of ExceptionDests describing the sets of exceptions that the Unit might throw to each Trap. But if all of a Unit's exceptions escape the method, it will be mapped to nullCollection containing a single ExceptionDest with a null trap. (The special case for Units with no caught exceptions allows buildExceptionDests() to ignore completely Units which are outside the scope of all Traps.)

buildExceptionalEdges

protected Set<Unit> buildExceptionalEdges(ThrowAnalysis throwAnalysis,
                                          Map<Unit,Collection<ExceptionalUnitGraph.ExceptionDest>> unitToExceptionDests,
                                          Map<Unit,List<Unit>> unitToSuccs,
                                          Map<Unit,List<Unit>> unitToPreds,
                                          boolean omitExceptingUnitEdges)

Method to compute the edges corresponding to exceptional control flow.

Parameters:

throwAnalysis - the source of information about the exceptions which each Unit may throw.

unitToExceptionDests2 - A Map from Units to Collections of ExceptionDests which represent the handlers that might catch exceptions thrown by the Unit. This is an ``in parameter''.

unitToSuccs - A Map from Units to Lists of Units. This is an ``out parameter''; buildExceptionalEdges will add a mapping from every Unit in the body that may throw an exception that could be caught by a Trap in the body to a list of its exceptional successors.

unitToPreds - A Map from Units to Lists of Units. This is an ``out parameter''; buildExceptionalEdges will add a mapping from each handler unit that may catch an exception to the list of Units whose exceptions it may catch.

omitExceptingUnitEdges - Indicates whether to omit exceptional edges from excepting units which lack side effects

Returns:

a Set of trap Units that might catch exceptions thrown by the first Unit in the Body associated with the graph being constructed. Such trap Units may need to be added to the list of heads (depending on your definition of heads), since they can be the first Unit in the Body which actually completes execution.

buildHeadsAndTails

protected void buildHeadsAndTails()
                           throws IllegalStateException

A placeholder that overrides UnitGraph.buildHeadsAndTails() with a method which always throws an exception. The placeholder serves to indicate that ExceptionalUnitGraph does not use buildHeadsAndTails(), and to document the conditions under which ExceptionalUnitGraph considers a node to be a head or tail.

ExceptionalUnitGraph defines the graph's set of heads to include the first Unit in the graph's body, together with the first Unit in any exception handler which might catch an exception thrown by the first Unit in the body (because any of those Units might be the first to successfully complete execution). ExceptionalUnitGraph defines the graph's set of tails to include all Units which represent some variety of return bytecode or an athrow bytecode whose argument might escape the method.

Overrides:

buildHeadsAndTails in class UnitGraph

Throws:

IllegalStateException

getExceptionDests

public Collection<ExceptionalUnitGraph.ExceptionDest> getExceptionDests(Unit u)

Returns a collection of ExceptionDest objects which represent how exceptions thrown by a specified unit will be handled.

Specified by:

getExceptionDests in interface ExceptionalGraph<Unit>

Parameters:

u - The unit for which to provide exception information. (u must be a Unit, though the parameter is declared as an Object to satisfy the interface of ExceptionalGraph.

Returns:

a collection of ExceptionDest objects describing the traps, if any, which catch the exceptions which may be thrown by u.

getUnexceptionalPredsOf

public List<Unit> getUnexceptionalPredsOf(Unit u)

Description copied from interface: ExceptionalGraph

Returns a list of nodes which are predecessors of a given node when only unexceptional control flow is considered.

Specified by:

getUnexceptionalPredsOf in interface ExceptionalGraph<Unit>

Parameters:

u - The node whose predecessors are to be returned.

Returns:

a List of the nodes in this graph from which there is an unexceptional edge to n.

getUnexceptionalSuccsOf

public List<Unit> getUnexceptionalSuccsOf(Unit u)

Description copied from interface: ExceptionalGraph

Returns a list of nodes which are successors of a given node when only unexceptional control flow is considered.

Specified by:

getUnexceptionalSuccsOf in interface ExceptionalGraph<Unit>

Parameters:

u - The node whose successors are to be returned.

Returns:

a List of nodes in this graph to which there is an unexceptional edge from n.

getExceptionalPredsOf

public List<Unit> getExceptionalPredsOf(Unit u)

Description copied from interface: ExceptionalGraph

Returns a list of nodes which are predecessors of a given node when only exceptional control flow is considered.

Specified by:

getExceptionalPredsOf in interface ExceptionalGraph<Unit>

Parameters:

u - The node whose predecessors are to be returned.

Returns:

a List of nodes in this graph from which there is an exceptional edge to n.

getExceptionalSuccsOf

public List<Unit> getExceptionalSuccsOf(Unit u)

Description copied from interface: ExceptionalGraph

Returns a list of nodes which are successors of a given node when only exceptional control flow is considered.

Specified by:

getExceptionalSuccsOf in interface ExceptionalGraph<Unit>

Parameters:

u - The node whose successors are to be returned.

Returns:

a List of nodes in this graph to which there is an exceptional edge from n.

toString

public String toString()

Overrides:

toString in class UnitGraph