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 Summary

Fields

Modifier and Type	Field and Description
protected IdentityHashMap<Tree,Set<Node>>	convertedTreeLookup Map from AST Trees to post-conversion sets of Nodes.
protected List<ClassTree>	declaredClasses Class declarations that have been encountered when building the control-flow graph for a method.
protected List<LambdaExpressionTree>	declaredLambdas Lambdas encountered when building the control-flow graph for a method, variable initializer, or initializer.
protected SpecialBlock	entryBlock The entry block of the control flow graph.
protected SpecialBlock	exceptionalExitBlock The exceptional exit block of the control flow graph.
protected 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.
protected SpecialBlock	regularExitBlock The regular exit block of the control flow graph.
protected List<ReturnNode>	returnNodes All return nodes (if any) encountered.
protected IdentityHashMap<Tree,Set<Node>>	treeLookup Maps from AST Trees to sets of Nodes.
UnderlyingAST	underlyingAST The AST this CFG corresponds to.

Constructor Summary

Constructors

Constructor and Description

ControlFlowGraph(SpecialBlock entryBlock, SpecialBlockImpl regularExitBlock, SpecialBlockImpl exceptionalExitBlock, UnderlyingAST underlyingAST, IdentityHashMap<Tree,Set<Node>> treeLookup, IdentityHashMap<Tree,Set<Node>> convertedTreeLookup, IdentityHashMap<UnaryTree,BinaryTree> postfixNodeLookup, List<ReturnNode> returnNodes, List<ClassTree> declaredClasses, List<LambdaExpressionTree> declaredLambdas)

Method Summary

Modifier and Type	Method and Description
Set<Block>	getAllBlocks() Returns the set of all basic blocks in this control flow graph.
List<Node>	getAllNodes() Returns all nodes in this control flow graph.
@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.
@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.
List<ClassTree>	getDeclaredClasses()
List<LambdaExpressionTree>	getDeclaredLambdas()
List<Block>	getDepthFirstOrderedBlocks() Returns all basic blocks in this control flow graph, in reversed depth-first postorder.
SpecialBlock	getEntryBlock() Returns the entry block of the control flow graph.
SpecialBlock	getExceptionalExitBlock()
@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.
UnmodifiableIdentityHashMap<UnaryTree,BinaryTree>	getPostfixNodeLookup() Returns an unmodifiable view of the lookup-map of the binary tree for a postfix expression.
SpecialBlock	getRegularExitBlock()
List<ReturnNode>	getReturnNodes()
UnmodifiableIdentityHashMap<Tree,Set<Node>>	getTreeLookup() Returns an unmodifiable view of the tree-lookup map.
long	getUid()
UnderlyingAST	getUnderlyingAST() Returns the AST this CFG corresponds to.
String	toString()
String	toStringDebug() Returns a verbose string representation of this, useful for debugging.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.plumelib.util.UniqueId

getClassAndUid

Field Detail

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 Detail

ControlFlowGraph

public ControlFlowGraph(SpecialBlock entryBlock,
                        SpecialBlockImpl regularExitBlock,
                        SpecialBlockImpl exceptionalExitBlock,
                        UnderlyingAST underlyingAST,
                        IdentityHashMap<Tree,Set<Node>> treeLookup,
                        IdentityHashMap<Tree,Set<Node>> convertedTreeLookup,
                        IdentityHashMap<UnaryTree,BinaryTree> postfixNodeLookup,
                        List<ReturnNode> returnNodes,
                        List<ClassTree> declaredClasses,
                        List<LambdaExpressionTree> declaredLambdas)

Method Detail

getUid

public long getUid(@UnknownInitialization ControlFlowGraph this)

Specified by:

getUid in interface org.plumelib.util.UniqueId

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(value=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(value=ControlFlowGraph.class) ControlFlowGraph this)

Returns all nodes in this control flow graph.

Returns:

all nodes in this control flow graph

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 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 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.

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.

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