edu.uci.eecs.doc.cascade.graph
Class Graph

java.lang.Object
  org.jgrapht.graph.AbstractGraph<V,E>
      org.jgrapht.graph.AbstractBaseGraph<V,E>
          org.jgrapht.graph.DefaultDirectedGraph<Vertex,Edge>
              edu.uci.eecs.doc.cascade.graph.Graph

All Implemented Interfaces:

Serializable, Cloneable, DirectedGraph<Vertex,Edge>, Graph<Vertex,Edge>

public class Graph
extends DefaultDirectedGraph<Vertex,Edge>

A control flow graph (CFG) of a Java method.

Author:

Trevor Harmon

See Also:

Tree, Serialized Form

Constructor Summary

Graph(List<String> classPath, Method method)
Creates a new control flow graph.

Graph(List<String> classPath, Method method, Tree caller, Field invokingField, boolean includeCacheMissBlocks)
Creates a new control flow graph.

Graph(Tree tree)
Creates a new control flow graph based on the given control flow tree.

Graph(Tree tree, boolean includeCacheMissBlocks)
Creates a new control flow graph based on the given control flow tree.

Method Summary

boolean	equals(Object obj) Compares this graph to the specified object.
Set<BasicBlock>	getBasicBlocks() Returns the set of vertices in this CFG, excluding the entry and exit vertices.
List<String>	getClassPath() Returns the class path that was specified when the underlying control flow tree was created.
Entry	getEntry() Returns the entry point of this CFG.
Exit	getExit() Returns the exit point of this CFG.
LoopBlock	getLoopBlock(Loop loop) Searches the graph for the loop block corresponding to the given loop node.
Method	getMethod() Returns the method from which this control flow graph was constructed.
List<Graph>	getMethodGraphs() Returns a list containing this graph and the graphs of any methods that it invokes
Set<Method>	getMethodInvocations() Returns the methods that this graph invokes.
Map<Node,Set<BasicBlock>>	getNodeBlockMap() Returns a mapping from nodes in the control flow tree to their corresponding basic blocks in the control flow graph.
Tree	getTree() Returns the control flow tree from which this control flow graph was constructed.
int	hashCode() Returns a hash code for this graph.
String	toString() Returns a simple one-line string describing the method represented by this graph.

Methods inherited from class org.jgrapht.graph.AbstractBaseGraph

addEdge, addEdge, addVertex, clone, containsEdge, containsVertex, degreeOf, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeFactory, getEdgeSource, getEdgeTarget, getEdgeWeight, incomingEdgesOf, inDegreeOf, isAllowingLoops, isAllowingMultipleEdges, outDegreeOf, outgoingEdgesOf, removeEdge, removeEdge, removeVertex, setEdgeSetFactory, setEdgeWeight, vertexSet

Methods inherited from class org.jgrapht.graph.AbstractGraph

assertVertexExist, containsEdge, removeAllEdges, removeAllEdges, removeAllEdges, removeAllVertices, toStringFromSets

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.jgrapht.DirectedGraph

incomingEdgesOf, inDegreeOf, outDegreeOf, outgoingEdgesOf

Methods inherited from interface org.jgrapht.Graph

addEdge, addEdge, addVertex, containsEdge, containsEdge, containsVertex, edgeSet, edgesOf, getAllEdges, getEdge, getEdgeFactory, getEdgeSource, getEdgeTarget, getEdgeWeight, removeAllEdges, removeAllEdges, removeAllVertices, removeEdge, removeEdge, removeVertex, vertexSet

Constructor Detail

Graph

public Graph(List<String> classPath,
             Method method)
      throws IOException,
             NoSuchMethodException,
             ClassNotFoundException

Creates a new control flow graph. A new Tree object will be created to build the graph; therefore, if a Tree object has already been created for the given method, do not use this constructor. Use the Graph(Tree) constructor instead.

Parameters:

classPath - a list of directories that will be searched when loading classes during control flow construction

method - the method whose control flow graph should be created

Throws:

IOException - if the method cannot be loaded

NoSuchMethodException - if the method cannot be found or if a method that it calls cannot be found

ClassNotFoundException - if the method calls another method and its class cannot be found

See Also:

Graph(Tree)

Graph

public Graph(List<String> classPath,
             Method method,
             Tree caller,
             Field invokingField,
             boolean includeCacheMissBlocks)
      throws IOException,
             NoSuchMethodException,
             ClassNotFoundException

Creates a new control flow graph. A new Tree object will be created to build the graph; therefore, if a Tree object has already been created for the given method, do not use this constructor. Use the Graph(Tree) constructor instead.

Parameters:

classPath - a list of directories that will be searched when loading classes during control flow construction

method - the method whose control flow graph should be created

includeCacheMissBlocks - if true, every method invocation is preceded by an InvokeMiss block and every return instruction by a ReturnMiss block; if false, no such blocks appear in the graph

Throws:

IOException - if the method cannot be loaded

NoSuchMethodException - if the method cannot be found or if a method that it calls cannot be found

ClassNotFoundException - if the method calls another method and its class cannot be found

See Also:

Graph(Tree)

Graph

public Graph(Tree tree)
      throws NoSuchMethodException,
             ClassNotFoundException,
             IOException

Creates a new control flow graph based on the given control flow tree.

Parameters:

tree - a control flow tree to be used as the basis of the CFG

Throws:

NoSuchMethodException - if the method calls another method and it cannot be found

ClassNotFoundException - if the method calls another method and its class cannot be found

IOException - if the method calls another method and it cannot be loaded

Graph

public Graph(Tree tree,
             boolean includeCacheMissBlocks)
      throws NoSuchMethodException,
             ClassNotFoundException,
             IOException

Creates a new control flow graph based on the given control flow tree.

Parameters:

tree - a control flow tree to be used as the basis of the CFG

includeCacheMissBlocks - if true, every method invocation is preceded by an InvokeMiss block and every return instruction by a ReturnMiss block; if false, no such blocks appear in the graph

Throws:

NoSuchMethodException - if the method calls another method and it cannot be found

ClassNotFoundException - if the method calls another method and its class cannot be found

IOException - if the method calls another method and it cannot be loaded

Method Detail

getTree

public Tree getTree()

Returns the control flow tree from which this control flow graph was constructed.

Returns:

the control flow tree used as the basis for this CFG

getMethod

public Method getMethod()

Returns the method from which this control flow graph was constructed.

Returns:

the Java method that this graph represents

getClassPath

public List<String> getClassPath()

Returns the class path that was specified when the underlying control flow tree was created.

Returns:

a list of directories

getMethodInvocations

public Set<Method> getMethodInvocations()

Returns the methods that this graph invokes.

Returns:

a set of Java method handles, or an empty set if this graph does not invoke any methods

getEntry

public Entry getEntry()

Returns the entry point of this CFG.

Returns:

an entry vertex

getExit

public Exit getExit()

Returns the exit point of this CFG.

Returns:

an exit vertex

getBasicBlocks

public Set<BasicBlock> getBasicBlocks()

Returns the set of vertices in this CFG, excluding the entry and exit vertices. The set also includes the basic blocks of methods that are invoked by this method.

Returns:

a set of CFG basic blocks

getNodeBlockMap

public Map<Node,Set<BasicBlock>> getNodeBlockMap()

Returns a mapping from nodes in the control flow tree to their corresponding basic blocks in the control flow graph. The mapping does not include the nodes in any invoked methods.

Returns:

a mapping of nodes to basic blocks

getMethodGraphs

public List<Graph> getMethodGraphs()

Returns a list containing this graph and the graphs of any methods that it invokes

Returns:

a list of control flow graphs

getLoopBlock

public LoopBlock getLoopBlock(Loop loop)

Searches the graph for the loop block corresponding to the given loop node.

Parameters:

loop - a loop node

Returns:

the corresponding loop block for the node, or null if it cannot be found

equals

public boolean equals(Object obj)

Compares this graph to the specified object. The result is true if and only if the argument is a Graph object whose underlying tree is equivalent to this graph's underlying tree.

Overrides:

equals in class Object

Parameters:

obj - the object to compare this graph against

Returns:

true if the given object represents a graph equivalent to this graph; false otherwise

hashCode

public int hashCode()

Returns a hash code for this graph. The hash code is identical to the hash code of the graph's underlying tree.

Overrides:

hashCode in class Object

Returns:

a hash code for this graph

toString

public String toString()

Returns a simple one-line string describing the method represented by this graph.

Overrides:

toString in class AbstractGraph<Vertex,Edge>

Returns:

a string representation of this graph