sofya.apps.dejavu
Class GraphTraverser

java.lang.Object
  extended by sofya.apps.dejavu.GraphTraverser
All Implemented Interfaces:
SConstants

public class GraphTraverser
extends java.lang.Object
implements SConstants

This class traverses two graphs using a node comparer to build a list of dangerous edges.

A dangerous edge is one which:

  1. Has successor nodes which differ between the two graphs.
  2. Is present in the first graph but not the second.
  3. Is an edge in the first graph that would be traversed instead of a new edge found in the second graph.

The traverser is designed to be completely polymorphic, in that it operates on any Graph or subclass, and uses an externally specified node comparer which presumably is appropriate for the type of graph being traversed. Generally it is expected that nodes encode type information consistent with the types defined in SConstants, which is to say node type information that should be relevant to any type of graph constructed from Java code. In the absence of certain expected but optional type information, the traverser will emit appropriate warnings but will not terminate.

Version:
05/13/2005
Author:
Rogan Creswick, Sharat Narayan, Sriraam Natarajan, Alex Kinneer

Nested Class Summary
 
Nested classes/interfaces inherited from interface sofya.base.SConstants
SConstants.BlockLabel, SConstants.BlockObjectType, SConstants.BlockSubType, SConstants.BlockType, SConstants.BranchObjectType, SConstants.BranchType, SConstants.EDObjectType, SConstants.TraceObjectType
 
Field Summary
 
Fields inherited from interface sofya.base.SConstants
DEFAULT_PORT, INST_COMPATIBLE, INST_OLD_UNSUPPORTED, INST_OPT_NORMAL, INST_OPT_SEQUENCE, SIG_CHKALIVE, SIG_ECHO
 
Constructor Summary
protected GraphTraverser()
          Protected constructor for subclasses only.
  GraphTraverser(NodeComparer nc, EdgeSelector es)
          Standard constructor, initializes the traverser with the given node comparer.
 
Method Summary
 Edge[] getDangerousEdges(MethodPair method)
          Gets the list of dangerous edges by invoking the traverser to walk the graphs.
 NodeComparer getNodeComparer()
          Returns the node comparer which the traverser is currently set to use to test node equivalence.
 void setNodeComparer(NodeComparer nc)
          Sets the node comparer which the traverser should use to test node equivalence.
protected  void traverseGraph(Node oldNode, Node newNode)
          Recursively traverses two graphs from the given start nodes in each graph respectively.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

GraphTraverser

protected GraphTraverser()
Protected constructor for subclasses only.


GraphTraverser

public GraphTraverser(NodeComparer nc,
                      EdgeSelector es)
Standard constructor, initializes the traverser with the given node comparer.

Parameters:
nc - Node comparer which will be used to test nodes in the graph for equivalence.
Method Detail

getNodeComparer

public NodeComparer getNodeComparer()
Returns the node comparer which the traverser is currently set to use to test node equivalence.

Returns:
The node comparer currently in use by the traverser.

setNodeComparer

public void setNodeComparer(NodeComparer nc)
Sets the node comparer which the traverser should use to test node equivalence.

Note: If the node comparer does not handle the type of node contained in the supplied graphs, the traverser will fail.

Parameters:
nc - New node comparer to be used by the traverser when checking nodes for equivalence.

getDangerousEdges

public Edge[] getDangerousEdges(MethodPair method)
                         throws MethodNotFoundException,
                                java.io.IOException
Gets the list of dangerous edges by invoking the traverser to walk the graphs.

Parameters:
method - Method pair that supplies the names and control flow graphs for the two methods to be compared.
Returns:
The list of dangerous edges selected by the graph traversal.
Throws:
MethodNotFoundException - If a method specified in method cannot be found in a class file loaded by the traverser.
java.io.IOException - For any IO error that prevents the traverser from successfully reading a required input file.

traverseGraph

protected void traverseGraph(Node oldNode,
                             Node newNode)
                      throws MethodNotFoundException
Recursively traverses two graphs from the given start nodes in each graph respectively.

The graph is traversed until all paths have reached an exit node or a changed node. There is no guarantee that the graph is traversed completely or that every node is visited.

Parameters:
oldNode - Node in the old graph from which to start the traversal.
newNode - Node in the new graph from which to start the traversal.
Throws:
MethodNotFoundException - If the method currently being traversed cannot be found in the classfile currently loaded by the node comparer.