Package org.jtool.cfg

Class CFG

java.lang.Object
org.jtool.graph.Graph<CFGNode,ControlFlow>
org.jtool.cfg.CFG
public class CFG extends Graph<CFGNode,ControlFlow>
An object storing information on a control flow graph (CFG).

  • Constructor Details

    • CFG

      public CFG()
      Creates a new, empty object for storing a CFG information. This method is not intended to be invoked by clients.

  • Method Details

    • setEntryNode

      public void setEntryNode(CFGEntry node)
      Sets the entry node of this CFG. This method is not intended to be invoked by clients.
      Parameters:
      node - the entry node of this CFG

    • getEntryNode

      public CFGEntry getEntryNode()
      Returns the entry node of this CFG.
      Returns:
      the entry node of this CFG

    • setExitNode

      public void setExitNode(CFGNode node)
      Sets the exit node of this CFG. This method is not intended to be invoked by clients.
      Parameters:
      node - exit end node of this CFG

    • getExitNode

      public CFGNode getExitNode()
      Returns the exit node of this CFG.
      Returns:
      the exit node of this CFG

    • setTimeoutOccurred

      public void setTimeoutOccurred(boolean bool)
      Sets whether the timeout occurred.
      Parameters:
      bool - true if the timeout occurred, otherwise false

    • timeoutOccurred

      public boolean timeoutOccurred()
      Tests if the timeout occurred.
      Returns:
      true if the timeout occurred, otherwise false

    • getId

      public long getId()
      Returns the identification number of this CFG, which is equals to that of the entry node.
      Returns:
      the identification number of this CFG

    • getQualifiedName

      public QualifiedName getQualifiedName()
      Returns the fully-qualified name of this CFG, which is equals to the fully-qualified of a class, a method, or a field corresponding to this CFG.
      Returns:
      the CFG name.

    • add

      public void add(BasicBlock block)
      Adds a basic block to this CFG. This method is not intended to be invoked by clients.
      Parameters:
      block - the basic block to be added

    • getBasicBlocks

      public List<BasicBlock> getBasicBlocks()
      Returns all basic blocks existing in this CFG.
      Returns:
      the collection of the basic blocks

    • clearBasicBlocks

      public void clearBasicBlocks()
      Clears basic blocks existing in this CFG.

    • isMethod

      public boolean isMethod()
      Tests if this CFG is created from a method.
      Returns:
      true if this CFG is created from a method, otherwise false

    • isField

      public boolean isField()
      Tests if this CFG is created from a field.
      Returns:
      true if this CFG is created from a field, otherwise false

    • isBranch

      public boolean isBranch(CFGNode node)
      Tests if a given CFG node represents a branch in this CFG.
      Parameters:
      node - the node to be checked
      Returns:
      true if the node represents a branch, otherwise false

    • isLoop

      public boolean isLoop(CFGNode node)
      Tests if a given CFG node represents a loop in this CFG.
      Parameters:
      node - the node to be checked
      Returns:
      true if the node represents a loop, otherwise false

    • isJoinNode

      public boolean isJoinNode(CFGNode node)
      Tests if a given CFG node represents a join in this CFG.
      Parameters:
      node - the node to be checked
      Returns:
      true if the node represents a join, otherwise false

    • getNode

      public CFGNode getNode(long id)
      Returns a CFG node with a given identification number.
      Parameters:
      id - the identification number of the node to be retrieved
      Returns:
      the found node, or null if no node is found

    • getFlow

      public ControlFlow getFlow(CFGNode src, CFGNode dst)
      Finds an control flow edge specified by given source and destination CFG nodes.
      Parameters:
      src - the source CFG node for the edge to be retrieved
      dst - the destination CFG node for the edge to be retrieved
      Returns:
      the found edge, or null if no edge is found

    • getTrueFlowFrom

      public ControlFlow getTrueFlowFrom(CFGNode node)
      Finds a true control flow edge outgoing from a given node.
      Parameters:
      node - the CFG node having the outgoing edge
      Returns:
      the found true control flow edge, or null if no edge is found

    • getFalseFlowFrom

      public ControlFlow getFalseFlowFrom(CFGNode node)
      Finds a false control flow edge outgoing from a given node.
      Parameters:
      node - the CFG node having the outgoing edge
      Returns:
      the found false control flow edge, or null if no edge is found

    • getFallThroughFlowFrom

      public ControlFlow getFallThroughFlowFrom(CFGNode node)
      Finds a fall-through control flow edge outgoing from a given node.
      Parameters:
      node - the CFG node having the outgoing edge
      Returns:
      the found fall-through control flow edge, or null if no edge is found

    • getExceptionCatchFlowFrom

      public ControlFlow getExceptionCatchFlowFrom(CFGNode node)
      Finds an exception catch flow edge outgoing from a given node.
      Parameters:
      node - the CFG node having the outgoing edge
      Returns:
      the found exception catch flow edge, or null if no edge is found

    • getTrueSuccessor

      public CFGNode getTrueSuccessor(CFGNode node)
      Returns a successor node of a given CFG node with respect to the true control flow.
      Parameters:
      node - the source node
      Returns:
      the found successor, or null if no successor is found

    • getFalseSuccessor

      public CFGNode getFalseSuccessor(CFGNode node)
      Returns a successor node of a given CFG node with respect to the false control flow.
      Parameters:
      node - the source node
      Returns:
      the found successor, or null if no successor is found

    • getFallThroughSuccessor

      public CFGNode getFallThroughSuccessor(CFGNode node)
      Returns a successor node of a given CFG node with respect to the fall-through control flow.
      Parameters:
      node - the source node
      Returns:
      the found successor, or null if no successor is found

    • getExceptionCatchSuccessor

      public CFGNode getExceptionCatchSuccessor(CFGNode node)
      Returns a successor node of a given CFG node with respect to the exception catch flow.
      Parameters:
      node - the source node
      Returns:
      the found successor, or null if no successor is found

    • hasTryStatement

      public boolean hasTryStatement()
      Tests if the method of this CFG contains a try statement.
      Returns:
      true if the method contains a try statement, otherwise false

    • getMethodCallNodes

      public List<CFGMethodCall> getMethodCallNodes()
      Obtains CFG nodes for method calls.
      Returns:
      the collection of the method call nodes

    • getStatementNodes

      public List<CFGStatement> getStatementNodes()
      Obtains CFG nodes for statements having defined and used variables.
      Returns:
      the collection of the statement nodes

    • getFieldAccessNodes

      public List<CFGStatement> getFieldAccessNodes()
      Obtains CFG nodes for field accesses.
      Returns:
      the collection of the field access nodes

    • getReturnNodes

      public Set<CFGStatement> getReturnNodes()
      Obtains CFG nodes for return statements.
      Returns:
      the collection of the return statement nodes

    • forwardReachableNodes

      public List<CFGNode> forwardReachableNodes(CFGNode startnode, boolean loopbackOk, boolean fallthroughOk, StopConditionOnReachablePath condition)
      Walks forward from a given node on this CFG and collects the traversed nodes.
      Parameters:
      startnode - the starting node to be traversed
      loopbackOk - true if loop-back edges can be traversed, otherwise false
      fallthroughOk - true if fall-through edges can be traversed, otherwise false
      condition - the condition that stops traversing
      Returns:
      the collection of the forward-traversed nodes

    • forwardReachableNodes

      public List<CFGNode> forwardReachableNodes(CFGNode startnode, boolean loopbackOk, boolean fallthroughOk)
      Walks forward from a given node on this CFG and collects the traversed nodes.
      Parameters:
      startnode - the starting node to be traversed
      loopbackOk - true if loop-back edges can be traversed, otherwise false
      fallthroughOk - true if fall-through edges can be traversed, otherwise false
      Returns:
      the collection of the forward-traversed nodes

    • forwardReachableNodes

      public List<CFGNode> forwardReachableNodes(CFGNode from, CFGNode to, boolean loopbackOk, boolean fallthroughOk)
      Walks forward between two nodes on this CFG and collects the traversed nodes.
      Parameters:
      from - the source node
      to - the destination node
      loopbackOk - true if loop-back edges can be traversed, otherwise false
      fallthroughOk - true if fall-through edges can be traversed, otherwise false
      Returns:
      the collection of the forward-traversed nodes

    • backwardReachableNodes

      public List<CFGNode> backwardReachableNodes(CFGNode startnode, boolean loopbackOk, boolean fallthroughOk, StopConditionOnReachablePath condition)
      Walks backward from a given node on this CFG and collects the traversed nodes.
      Parameters:
      startnode - the starting node to be traversed
      loopbackOk - true if loop-back edges can be traversed, otherwise false
      fallthroughOk - true if fall-through edges can be traversed, otherwise false
      condition - the condition that stops traversing
      Returns:
      the collection of the backward-traversed nodes

    • backwardReachableNodes

      public List<CFGNode> backwardReachableNodes(CFGNode startnode, boolean loopbackOk, boolean fallthroughOk)
      Walks backward from a given node on this CFG and collects the traversed nodes.
      Parameters:
      startnode - the starting node to be traversed
      loopbackOk - true if loop-back edges can be traversed, otherwise false
      fallthroughOk - true if fall-through edges can be traversed, otherwise false
      Returns:
      the collection of the backward-traversed nodes

    • backwardReachableNodes

      public List<CFGNode> backwardReachableNodes(CFGNode from, CFGNode to, boolean loopbackOk, boolean fallthroughOk)
      Walks backward between two nodes on this CFG and collects the traversed nodes.
      Parameters:
      from - the source node
      to - the destination node
      loopbackOk - true if loop-back edges can be traversed, otherwise false
      fallthroughOk - true if fall-through edges can be traversed, otherwise false
      Returns:
      the collection of the backward-traversed nodes

    • reachableNodes

      public Set<CFGNode> reachableNodes(CFGNode from, CFGNode to, boolean loopbackOk, boolean fallthroughOk)
      Calculates nodes traversed between two nodes on this CFG, which are reachable from the both nodes.
      Parameters:
      from - the source node
      to - the destination node
      loopbackOk - true if loop-back edges can be traversed, otherwise false
      fallthroughOk - true if fall-through edges can be traversed, otherwise false
      Returns:
      the collection of the traversed nodes

    • constrainedReachableNodes

      public Set<CFGNode> constrainedReachableNodes(CFGNode from, CFGNode to)
      Calculates a constrained reachable nodes between two nodes.
      Parameters:
      from - the source node
      to - the destination node
      Returns:
      the collection of the reachable nodes

    • postDominator

      public Set<CFGNode> postDominator(CFGNode anchor)
      Calculates post-dominant nodes for a given CFG. This is a naive implementation. Use Lengauer-Tarjan Dominator Tree Algorithm to make the calculation efficient.
      Parameters:
      anchor - the anchor node that might dominate other nodes
      Returns:
      the collection of the dominated nodes

    • registerDominantStatement

      public void registerDominantStatement(ControlFlow flow, org.jtool.cfg.internal.DominantStatement statement)
      Registers a control flow and a dominant statement having the flow. This method is not intended to be invoked by clients.
      Parameters:
      flow - a flow that dominates nodes
      statement - a dominant statement having the flow

    • getDominantStatement

      public org.jtool.cfg.internal.DominantStatement getDominantStatement(ControlFlow flow)
      Obtains the dominant statement having a given flow. This method is not intended to be invoked by clients.
      Parameters:
      flow - the control flow
      Returns:
      the found dominant statement, null if it was found

    • findDominantStatement

      public org.jtool.cfg.internal.DominantStatement findDominantStatement(CFGNode node)
      Finds a statement that dominates a given node.
      Parameters:
      node - the node to be retrieved
      Returns:
      the found dominant statement

    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class Object

    • equals

      public boolean equals(CFG cfg)
      Tests if a given CFG is equal to this CFG.
      Parameters:
      cfg - the CFG to be checked
      Returns:
      the true if the given CFG is equal to this CFG

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • print

      public void print()
      Displays information on this graph.

    • toString

      public String toString()
      Obtains information on this CFG.
      Overrides:
      toString in class Graph<CFGNode,ControlFlow>
      Returns:
      the string representing the information

    • toStringForNodes

      protected String toStringForNodes()
      Obtains information on all nodes enclosed in this graph.
      Overrides:
      toStringForNodes in class Graph<CFGNode,ControlFlow>
      Returns:
      the string representing the information

    • toStringForEdges

      protected String toStringForEdges()
      Obtains information on all edges enclosed in this graph.
      Overrides:
      toStringForEdges in class Graph<CFGNode,ControlFlow>
      Returns:
      the string representing the information