Package org.checkerframework.dataflow.cfg

Class ControlFlowGraph

java.lang.Object
org.checkerframework.dataflow.cfg.ControlFlowGraph
All Implemented Interfaces:
org.plumelib.util.UniqueId
public class ControlFlowGraph extends Object implements org.plumelib.util.UniqueId
A control flow graph (CFG for short) of a single method.

The graph is represented by the successors (methods SingleSuccessorBlock.getSuccessor(), ConditionalBlock.getThenSuccessor(), ConditionalBlock.getElseSuccessor(), ExceptionBlock.getExceptionalSuccessors(), RegularBlock.getRegularSuccessor()) and predecessors (method Block.getPredecessors()) of the entry and exit blocks.

  • Field Details

    • entryBlock

      protected final SpecialBlock entryBlock
      The entry block of the control flow graph.

    • regularExitBlock

      protected final SpecialBlock regularExitBlock
      The regular exit block of the control flow graph.

    • exceptionalExitBlock

      protected final SpecialBlock exceptionalExitBlock
      The exceptional exit block of the control flow graph.

    • underlyingAST

      public final UnderlyingAST underlyingAST
      The AST this CFG corresponds to.

    • treeLookup

      protected final IdentityHashMap<Tree,Set<Node>> treeLookup
      Maps from AST Trees to sets of Nodes.
      • Most Trees that produce a value will have at least one corresponding Node.
      • Trees that undergo conversions, such as boxing or unboxing, can map to two distinct Nodes. The Node for the pre-conversion value is stored in treeLookup, while the Node for the post-conversion value is stored in convertedTreeLookup.
      Some of the mapped-to nodes (in both treeLookup and convertedTreeLookup) do not appear in getAllNodes() because their blocks are not reachable in the control flow graph. Dataflow will not compute abstract values for these nodes.

    • convertedTreeLookup

      protected final IdentityHashMap<Tree,Set<Node>> convertedTreeLookup
      Map from AST Trees to post-conversion sets of Nodes.

    • postfixNodeLookup

      protected final IdentityHashMap<UnaryTree,BinaryTree> postfixNodeLookup
      Map from postfix increment or decrement trees that are AST UnaryTrees to the synthetic tree that is v + 1 or v - 1.

    • returnNodes

      protected final List<ReturnNode> returnNodes
      All return nodes (if any) encountered. Only includes return statements that actually return something

    • declaredClasses

      protected final List<ClassTree> declaredClasses
      Class declarations that have been encountered when building the control-flow graph for a method.

    • declaredLambdas

      protected final List<LambdaExpressionTree> declaredLambdas
      Lambdas encountered when building the control-flow graph for a method, variable initializer, or initializer.

  • Constructor Details

  • Method Details

    • getUid

      public long getUid(@UnknownInitialization ControlFlowGraph this)
      Specified by:
      getUid in interface org.plumelib.util.UniqueId

    • checkInvariants

      public void checkInvariants()
      Verify that this is a complete and well-formed CFG, i.e. that all internal invariants hold.
      Throws:
      IllegalStateException - if some internal invariant is violated

    • getNodesCorrespondingToTree

      public @Nullable Set<Node> getNodesCorrespondingToTree(Tree t)
      Returns the set of Nodes to which the Tree t corresponds, or null for trees that don't produce a value.
      Parameters:
      t - a tree
      Returns:
      the set of Nodes to which the Tree t corresponds, or null for trees that don't produce a value

    • getEntryBlock

      public SpecialBlock getEntryBlock()
      Returns the entry block of the control flow graph.
      Returns:
      the entry block of the control flow graph

    • getReturnNodes

      public List<ReturnNode> getReturnNodes()

    • getRegularExitBlock

      public SpecialBlock getRegularExitBlock()

    • getExceptionalExitBlock

      public SpecialBlock getExceptionalExitBlock()

    • getUnderlyingAST

      public UnderlyingAST getUnderlyingAST()
      Returns the AST this CFG corresponds to.
      Returns:
      the AST this CFG corresponds to

    • getAllBlocks

      public Set<Block> getAllBlocks(@UnknownInitialization(ControlFlowGraph.class) ControlFlowGraph this)
      Returns the set of all basic blocks in this control flow graph.
      Returns:
      the set of all basic blocks in this control flow graph

    • getAllNodes

      public List<Node> getAllNodes(@UnknownInitialization(ControlFlowGraph.class) ControlFlowGraph this)
      Returns all nodes in this control flow graph.
      Returns:
      all nodes in this control flow graph

    • getAllBlocks

      public Set<Block> getAllBlocks(@UnknownInitialization(ControlFlowGraph.class) ControlFlowGraph this, Function<TypeMirror,Boolean> shouldIgnoreException)
      Returns the set of all basic blocks in this control flow graph, except those that are only reachable via an exception whose type is ignored by parameter shouldIgnoreException.
      Parameters:
      shouldIgnoreException - returns true if it is passed a TypeMirror that should be ignored
      Returns:
      the set of all basic blocks in this control flow graph, except those that are only reachable via an exception whose type is ignored by shouldIgnoreException

    • getAllNodes

      public List<Node> getAllNodes(@UnknownInitialization(ControlFlowGraph.class) ControlFlowGraph this, Function<TypeMirror,Boolean> shouldIgnoreException)
      Returns the list of all nodes in this control flow graph, except those that are only reachable via an exception whose type is ignored by parameter shouldIgnoreException.
      Parameters:
      shouldIgnoreException - returns true if it is passed a TypeMirror that should be ignored
      Returns:
      the list of all nodes in this control flow graph, except those that are only reachable via an exception whose type is ignored by shouldIgnoreException

    • getDepthFirstOrderedBlocks

      public List<Block> getDepthFirstOrderedBlocks()
      Returns all basic blocks in this control flow graph, in reversed depth-first postorder. Blocks may appear more than once in the sequence.
      Returns:
      the list of all basic block in this control flow graph in reversed depth-first postorder sequence

    • getTreeLookup

      public org.plumelib.util.UnmodifiableIdentityHashMap<Tree,Set<Node>> getTreeLookup()
      Returns an unmodifiable view of the tree-lookup map. Ignores convertedTreeLookup, though getNodesCorrespondingToTree(com.sun.source.tree.Tree) uses that field.
      Returns:
      the unmodifiable tree-lookup map

    • getPostfixNodeLookup

      public org.plumelib.util.UnmodifiableIdentityHashMap<UnaryTree,BinaryTree> getPostfixNodeLookup()
      Returns an unmodifiable view of the lookup-map of the binary tree for a postfix expression.
      Returns:
      the unmodifiable lookup-map of the binary tree for a postfix expression

    • getContainingMethod

      public @Nullable MethodTree getContainingMethod(Tree t)
      Get the MethodTree of the CFG if the argument Tree maps to a Node in the CFG, or null otherwise.
      Parameters:
      t - a tree that might correspond to a node in the CFG
      Returns:
      the method that contains t's Node, or null

    • getContainingClass

      public @Nullable ClassTree getContainingClass(Tree t)
      Get the ClassTree of the CFG if the argument Tree maps to a Node in the CFG, or null otherwise.
      Parameters:
      t - a tree that might be within a class
      Returns:
      the class that contains the given tree, or null

    • getDeclaredClasses

      public List<ClassTree> getDeclaredClasses()

    • getDeclaredLambdas

      public List<LambdaExpressionTree> getDeclaredLambdas()

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • toStringDebug

      public String toStringDebug()
      Returns a verbose string representation of this, useful for debugging.
      Returns:
      a string representation of this