org.evosuite.graphs.ccfg

Class ClassControlFlowGraph

java.lang.Object

org.evosuite.graphs.EvoSuiteGraph<CCFGNode,CCFGEdge>

org.evosuite.graphs.ccfg.ClassControlFlowGraph

public class ClassControlFlowGraph
extends EvoSuiteGraph<CCFGNode,CCFGEdge>

This class computes the Class Control Flow Graph (CCFG) of a CUT. Given the ClassCallGraph the CCFG is generated as follows: The RawControlFlowGraph (CFG) of each method in the target class is retrieved from the GraphPool and imported into this CCFG. BytecodeInstructions are imported as CCFGCodeNodes and ControlFlowEdges as CCFGCodeEdges. Additionally each CFG is enclosed by a CCFGMethodEntryNode and CCFGMethodExitNode with an edge from the entry node to the first instruction in the CFG and an edge from each exit instruction in the CFG to the exit node. After that each method call instruction as defined in BytecodeInstruction.isMethodCall() is replaced by two new nodes CCFGMethodCallNode and CCFGMethodReturnNode that are labeled with that call instruction. Each incoming edge to the previous CCFGCodeNode is redirected to the CCFGMethodCallNode and each outgoing edge from the previous node is redirected to the CCFGMethodReturnNode. Then two CCFGMethodCallEdges are added. One from the CCFGMethodCallNode to the CCFGMethodEntryNode of the called method and one from that methods CCFGMethodExitNode to the CCFGMethodReturnNode. NOTE: Not every method call is replaced like this. Only calls to methods of the class this CCFG is created for that are either static methods - as defined by BytecodeInstruction.isStaticMethodCall() - or calls to methods on the same object (this) as defined by BytecodeInstruction.isMethodCallOnSameObject(). All this is enclosed by a frame consisting of five CCFGFrameNodes of different types. This frame has two dedicated ENTRY and EXIT nodes connected via a third node LOOP. The LOOP node has an outgoing edge to CALL which in turn has an outgoing edge to each CCFGMethodEntryNode of each public method in this graph. Analogously the CCFGMethodExitNode of each public method has an outgoing edge to the CCFGFrameNode RETURN which in turn has an outgoing edge back to LOOP. All these edges are CCFGFrameEdges. The frame simulates the possible calls to the CUT a test can potentially make. After starting (ENTRY->LOOP) a test can make arbitrary calls to public methods (LOOP->CALL) that can in turn call other methods of the class (CCFGMethodCallEdges). After returning from a public method call (RETURN->LOOP) the test can either make more calls to the class (LOOP->CALL) or stop (LOOP->EXIT). The construction of the CCFG is inspired by: Proc. of the Second ACM SIGSOFT Symp. on the Foundations of Softw. Eng., December 1994, pages 154-164 "Performing Data Flow Testing on Classes" Mary Jean Harrold and Gregg Rothermel, Section 5. The resulting CCFG should be as described in the paper but our construction differs a little (we don't import the CCG and then replace method nodes with CFGs but rather import CFGs and connect them directly).

Author:

Andre Mis

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	ClassControlFlowGraph.FrameNodeType

Field Summary

Fields

Modifier and Type	Field and Description
Set<CCFGMethodEntryNode>	publicMethods

Fields inherited from class org.evosuite.graphs.EvoSuiteGraph

edgeClass, graph, graphId

Constructor Summary

Constructors

Constructor and Description
ClassControlFlowGraph(ClassCallGraph ccg) Given the ClassCallGraph of a class this constructor will build up the corresponding CCFG using the RCFGs from the GraphPool.

Method Summary

Modifier and Type	Method and Description
protected String	dotSubFolder() Subclasses can overwrite this method in order to separate their .dot and .png export to a special folder.
ClassCallGraph	getCcg()
CCFGFrameNode	getFrameNode(ClassControlFlowGraph.FrameNodeType type) getFrameNode
CCFGMethodEntryNode	getMethodEntryNodeForClassCallNode(ClassCallNode ccgNode)
CCFGMethodEntryNode	getMethodEntryOf(CCFGMethodExitNode methodExit) getMethodEntryOf
CCFGMethodExitNode	getMethodExitOf(CCFGMethodEntryNode methodEntry) getMethodExitOf
String	getName() getName
boolean	isPublicMethod(CCFGMethodEntryNode node)
boolean	isPublicMethod(String method)
boolean	isPure(String methodName)

Methods inherited from class org.evosuite.graphs.EvoSuiteGraph

addEdge, addEdge, addVertex, addVertices, addVertices, computeReverseJGraph, containsEdge, containsEdge, containsVertex, determineBranches, determineConnectedVertices, determineEntryPoints, determineExitPoints, determineJoins, edgeCount, edgeSet, getChildren, getDistance, getEdge, getEdgeSource, getEdgeTarget, getIsolatedNodes, getNodesWithoutChildren, getParents, getRandomVertex, getSingleChild, hasNPartentsMChildren, incomingEdgesOf, inDegreeOf, isConnected, isDirectSuccessor, isEmpty, outDegreeOf, outgoingEdgesOf, redirectEdges, redirectEdgeSource, redirectEdgeTarget, redirectIncomingEdges, redirectOutgoingEdges, registerEdgeAttributeProvider, registerVertexAttributeProvider, toDot, toFileString, vertexCount, vertexSet

Methods inherited from class java.lang.Object

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

Field Detail

publicMethods

public Set<CCFGMethodEntryNode> publicMethods

Constructor Detail

ClassControlFlowGraph

public ClassControlFlowGraph(ClassCallGraph ccg)

Given the ClassCallGraph of a class this constructor will build up the corresponding CCFG using the RCFGs from the GraphPool.

Parameters:

ccg - a ClassCallGraph object.

Method Detail

isPure

public boolean isPure(String methodName)

isPublicMethod

public boolean isPublicMethod(String method)

isPublicMethod

public boolean isPublicMethod(CCFGMethodEntryNode node)

getMethodEntryNodeForClassCallNode

public CCFGMethodEntryNode getMethodEntryNodeForClassCallNode(ClassCallNode ccgNode)

getMethodExitOf

public CCFGMethodExitNode getMethodExitOf(CCFGMethodEntryNode methodEntry)

getMethodExitOf

Parameters:

methodEntry - a CCFGMethodEntryNode object.

Returns:

a CCFGMethodExitNode object.

getMethodEntryOf

public CCFGMethodEntryNode getMethodEntryOf(CCFGMethodExitNode methodExit)

getMethodEntryOf

Parameters:

methodExit - a CCFGMethodExitNode object.

Returns:

a CCFGMethodEntryNode object.

getFrameNode

public CCFGFrameNode getFrameNode(ClassControlFlowGraph.FrameNodeType type)

getFrameNode

Parameters:

type - a ClassControlFlowGraph.FrameNodeType object.

Returns:

a CCFGFrameNode object.

getName

public String getName()

getName

Overrides:

getName in class EvoSuiteGraph<CCFGNode,CCFGEdge>

Returns:

a String object.

dotSubFolder

protected String dotSubFolder()

Subclasses can overwrite this method in order to separate their .dot and .png export to a special folder.

Overrides:

dotSubFolder in class EvoSuiteGraph<CCFGNode,CCFGEdge>

Returns:

a String object.

getCcg

public ClassCallGraph getCcg()

Returns:

the ccg