CFGBuilder

java.lang.Object
- polyglot.visit.CFGBuilder<FlowItem>

All Implemented Interfaces:: java.lang.Cloneable, Copy<CFGBuilder<FlowItem>>

public class CFGBuilder<FlowItem extends DataFlow.Item>
extends java.lang.Object
implements Copy<CFGBuilder<FlowItem>>

Class used to construct a CFG.

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

protected static class CFGBuilder.EdgeKeyTermPair
- Nested classes/interfaces inherited from interface polyglot.util.Copy
  Copy.Util

Nested Classes
Modifier and Type	Class and Description
`protected static class`	`CFGBuilder.EdgeKeyTermPair`

Field Summary

Fields
Modifier and Type	Field and Description
`protected static int`	`counter`
`protected DataFlow<FlowItem>`	`df` The data flow analysis for which we are constructing the graph.
`protected boolean`	`errorEdgesToExitNode` True if we should add edges for uncaught Errors to the exit node of the graph.
`protected boolean`	`exceptionEdgesToFinally` Should we add exception edges into finally blocks? If true, then the edge from an AST node that throws an exception to a finally block will be labeled with the appropriate exception; if false, then the edge will be labeled OTHER.
`protected FlowGraph<FlowItem>`	`graph` The flow graph under construction.
`protected Stmt`	`innermostTarget` The innermost loop or try-block in lexical scope.
`protected CFGBuilder<FlowItem>`	`outer` The outer CFGBuilder.
`protected java.util.List<Term>`	`path_to_finally` Nodes in finally blocks need to be analyzed multiple times, once for each possible way to reach the finally block.
`protected boolean`	`skipDeadIfBranches` True if we should skip dead if branches, such as S in "if (false) { S }".
`protected boolean`	`skipDeadLoopBodies` True if we should skip dead loop bodies, such as S in "while (false) { S }".
`protected boolean`	`skipInnermostCatches` True if we should skip the catch blocks for the innermost try when building edges for an exception throw.
`protected boolean`	`trackImplicitErrors` True if we want to add implicit error edges from all statements
`protected TypeSystem`	`ts` The type system.

Constructor Summary

Constructors
Constructor and Description

CFGBuilder(JLang lang, TypeSystem ts, FlowGraph<FlowItem> graph, DataFlow<FlowItem> df)

Constructors
Constructor and Description
`CFGBuilder(JLang lang, TypeSystem ts, FlowGraph<FlowItem> graph, DataFlow<FlowItem> df)`

Method Summary

Methods
Modifier and Type	Method and Description
`CFGBuilder<FlowItem>`	`copy()` Copy the CFGBuilder.
`DataFlow<FlowItem>`	`dataflow()`
`void`	`edge(CFGBuilder<FlowItem> p_visitor, Term p, FlowGraph.Peer<FlowItem> pq, FlowGraph.EdgeKey edgeKey)` Add an edge to the CFG from the exit of `p` to peer pq.
`void`	`edge(CFGBuilder<FlowItem> p_visitor, Term p, int pEntry, Term q, int qEntry, FlowGraph.EdgeKey edgeKey)`
`void`	`edge(CFGBuilder<FlowItem> p_visitor, Term p, Term q, int qEntry, FlowGraph.EdgeKey edgeKey)` Add an edge to the CFG from the exit of `p` to either the entry or exit of `q`.
`protected void`	`edge(FlowGraph.Peer<FlowItem> pp, FlowGraph.Peer<FlowItem> pq, FlowGraph.EdgeKey edgeKey)`
`void`	`edge(Term p, Term q, int qEntry)` Add an edge to the CFG from the exit of `p` to either the entry or exit of `q`.
`void`	`edge(Term p, Term q, int qEntry, FlowGraph.EdgeKey edgeKey)` Add an edge to the CFG from the exit of `p` to either the entry or exit of `q`.
`protected CFGBuilder<FlowItem>`	`enterFinally(FlowGraph.Peer<FlowItem> from, boolean abruptCompletion)` Enter a finally block.
`protected FlowGraph.Peer<FlowItem>`	`entryPeer()` Utility method to get the peer for the entry of the flow graph.
`CFGBuilder<FlowItem>`	`errorEdgesToExitNode(boolean b)`
`CFGBuilder<FlowItem>`	`exceptionEdgesToFinally(boolean b)`
`protected FlowGraph.Peer<FlowItem>`	`exitPeer()` Utility method to get the peer for the exit of the flow graph.
`FlowGraph<FlowItem>`	`graph()`
`Stmt`	`innermostTarget()`
`JLang`	`lang()`
`CFGBuilder<FlowItem>`	`outer()`
`CFGBuilder<FlowItem>`	`push(Stmt n)` Construct a new CFGBuilder with the a new innermost loop or try-block `n`.
`CFGBuilder<FlowItem>`	`push(Stmt n, boolean skipInnermostCatches)` Construct a new CFGBuilder with the a new innermost loop or try-block `n`, optionally skipping innermost catch blocks.
`boolean`	`skipDeadIfBranches()` Should the CFG construction skip dead if branches? (e.g., should statement s be skipped in the following: if (false) { S } ).
`CFGBuilder<FlowItem>`	`skipDeadIfBranches(boolean b)`
`boolean`	`skipDeadLoopBodies()` Should the CFG construction skip dead loop bodies? (e.g., should statement s be skipped in the following: while (false) { S } ).
`CFGBuilder<FlowItem>`	`skipDeadLoopBodies(boolean b)`
`boolean`	`skipInnermostCatches()`
`CFGBuilder<FlowItem>`	`trackImplicitErrors(boolean b)`
`protected static <FlowItem extends DataFlow.Item> FlowGraph.Peer<FlowItem>`	`tryFinally(CFGBuilder<FlowItem> v, FlowGraph.Peer<FlowItem> last, boolean abruptCompletion, Block finallyBlock)` Create edges for the finally block of a try-finally construct.
`protected static <FlowItem extends DataFlow.Item> FlowGraph.Peer<FlowItem>`	`tryFinally(CFGBuilder<FlowItem> v, FlowGraph.Peer<FlowItem> last, boolean abruptCompletion, FlowGraph.EdgeKey edgeKeyToFinally, Block finallyBlock)` Create edges for the finally block of a try-finally construct.
`TypeSystem`	`typeSystem()` Get the type system.
`void`	`visitBranchTarget(Branch b)` Visit edges from a branch.
`void`	`visitCFG(Term a, FlowGraph.EdgeKey edgeKey, java.util.List<Term> succ, int entry)` Create edges from node `a` to all successors `succ` with the EdgeKey `edgeKey` for all edges created.
`void`	`visitCFG(Term a, FlowGraph.EdgeKey edgeKey, java.util.List<Term> succ, java.util.List<java.lang.Integer> entry)` Create edges from node `a` to all successors `succ` with the EdgeKey `edgeKey` for all edges created.
`void`	`visitCFG(Term a, FlowGraph.EdgeKey edgeKey, Term succ, int entry)` Create an edge for a node `a` with a single successor `succ`, and EdgeKey `edgeKey`.
`void`	`visitCFG(Term a, FlowGraph.EdgeKey edgeKey1, Term succ1, int entry1, FlowGraph.EdgeKey edgeKey2, Term succ2, int entry2)` Create edges from node `a` to successors `succ1` and `succ2` with EdgeKeys `edgeKey1` and `edgeKey2` respectively.
`protected void`	`visitCFG(Term a, java.util.List<CFGBuilder.EdgeKeyTermPair> succs)` Create edges for a node `a` with successors `succs`.
`void`	`visitCFG(Term a, Term succ, int entry)` Create an edge for a node `a` with a single successor `succ`.
`void`	`visitCFGList(java.util.List<? extends Term> elements, Term after, int entry)` Utility function to visit all edges in a list.
`void`	`visitGraph()` Visit the AST, constructing the CFG.
`void`	`visitReturn(Return r)` Visit edges for a return statement.
`void`	`visitThrow(Term a)`
`void`	`visitThrow(Term t, int entry, Type type)` Create edges for an exception thrown from term `t`.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - graph
```
protected FlowGraph<FlowItem extends DataFlow.Item> graph
```
    The flow graph under construction.
  - ts
```
protected TypeSystem ts
```
    The type system.
  - outer
```
protected CFGBuilder<FlowItem extends DataFlow.Item> outer
```
    The outer CFGBuilder. We create a new inner CFGBuilder when entering a loop or try-block and when entering a finally block.
  - innermostTarget
```
protected Stmt innermostTarget
```
    The innermost loop or try-block in lexical scope. We maintain a stack of loops and try-blocks in order to add edges for break and continue statements and for exception throws. When such a jump is encountered we traverse the stack, searching for the target of the jump.
  - path_to_finally
```
protected java.util.List<Term> path_to_finally
```
    Nodes in finally blocks need to be analyzed multiple times, once for each possible way to reach the finally block. The path_to_finally is used to distinguish these different "copies" of nodes in the finally block, and is a list of terms that attempted to complete normally that caused the finally block to be reached. If this CFGBuilder is for an AST that is not nested inside a finallyBlock, then path_to_finally will be empty. To explain by example, consider the following code (which is assumed to not be nested inside a finally block, and assume that S1 does not contain any try-finally block). try { S1 } finally { S2 } Assume that term t1 in S1 may complete abruptly. The code for S2 will be analyzed (at least) twice: once for normal termination of S1 (and so path_to_finally will be empty) and once for the abrupt completion of t1 (and so path_to_finally will be [t1]). Consider the following code: try { try { S1 } finally { S2 } } finally { S3 } Assume that terms t1 in S1 and t2 in S2 may complete abruptly. Nodes in S2 will be analyzed (at least) twice, with path_to_finally empty (for normal termination of S1) and with path_to_empty equals [t1] (for abrupt completion of t1). S3 will be analyzed (at least) 3 times: once with path_to_finally empty (for normal termination of S1 and S2) once with path_to_finally equals [t1] (for abrupt completion of t1 and normal termination of S2), and once with path_to_finally equals [t1, t2] (for (attempted) abrupt completion of t1 and subsequent abrupt completion of t2). Consider the following code: try { S1 } finally { try { S2 } finally { S3 } } Assume that terms t1 in S1 and t2 in S2 may complete abruptly. Nodes in S2 will be analyzed (at least) twice, with path_to_finally empty (for normal termination of S1) and with path_to_empty equals [t1] (for abrupt completion of t1). S3 will be analyzed (at least) 3 times: once with path_to_finally empty (for normal termination of S1 and S2) once with path_to_finally equals [t1] (for abrupt completion of t1 and normal termination of S2), and once with path_to_finally equals [t1, t2] (for (attempted) abrupt completion of t1 and subsequent abrupt completion of t2).
  - df
```
protected DataFlow<FlowItem extends DataFlow.Item> df
```
    The data flow analysis for which we are constructing the graph.
  - skipInnermostCatches
```
protected boolean skipInnermostCatches
```
    True if we should skip the catch blocks for the innermost try when building edges for an exception throw.
  - skipDeadIfBranches
```
protected boolean skipDeadIfBranches
```
    True if we should skip dead if branches, such as S in "if (false) { S }". Different dataflow analyses have different requirements.
  - skipDeadLoopBodies
```
protected boolean skipDeadLoopBodies
```
    True if we should skip dead loop bodies, such as S in "while (false) { S }". Different dataflow analyses have different requirements.
  - errorEdgesToExitNode
```
protected boolean errorEdgesToExitNode
```
    True if we should add edges for uncaught Errors to the exit node of the graph. By default, we do not, but subclasses can change this behavior if needed.
  - trackImplicitErrors
```
protected boolean trackImplicitErrors
```
    True if we want to add implicit error edges from all statements
  - exceptionEdgesToFinally
```
protected boolean exceptionEdgesToFinally
```
    Should we add exception edges into finally blocks? If true, then the edge from an AST node that throws an exception to a finally block will be labeled with the appropriate exception; if false, then the edge will be labeled OTHER. For backwards compatibility, the default value is false.
  - counter
```
protected static int counter
```
- Constructor Detail
  - CFGBuilder
```
public CFGBuilder(JLang lang,
          TypeSystem ts,
          FlowGraph<FlowItem> graph,
          DataFlow<FlowItem> df)
```
- Method Detail
  - lang
```
public JLang lang()
```
  - graph
```
public FlowGraph<FlowItem> graph()
```
  - dataflow
```
public DataFlow<FlowItem> dataflow()
```
  - outer
```
public CFGBuilder<FlowItem> outer()
```
  - innermostTarget
```
public Stmt innermostTarget()
```
  - skipInnermostCatches
```
public boolean skipInnermostCatches()
```
  - typeSystem
```
public TypeSystem typeSystem()
```
    Get the type system.
  - copy
```
public CFGBuilder<FlowItem> copy()
```
    Copy the CFGBuilder.
    
    Specified by:
    
    copy in interface Copy<CFGBuilder<FlowItem extends DataFlow.Item>>
  - push
```
public CFGBuilder<FlowItem> push(Stmt n)
```
    Construct a new CFGBuilder with the a new innermost loop or try-block n.
  - push
```
public CFGBuilder<FlowItem> push(Stmt n,
                        boolean skipInnermostCatches)
```
    Construct a new CFGBuilder with the a new innermost loop or try-block n, optionally skipping innermost catch blocks.
  - visitBranchTarget
```
public void visitBranchTarget(Branch b)
```
    Visit edges from a branch. Simulate breaking/continuing out of the loop, visiting any finally blocks encountered.
  - visitReturn
```
public void visitReturn(Return r)
```
    Visit edges for a return statement. Simulate the return, visiting any finally blocks encountered.
  - visitGraph
```
public void visitGraph()
```
    Visit the AST, constructing the CFG.
  - entryPeer
```
protected FlowGraph.Peer<FlowItem> entryPeer()
```
    Utility method to get the peer for the entry of the flow graph.
  - exitPeer
```
protected FlowGraph.Peer<FlowItem> exitPeer()
```
    Utility method to get the peer for the exit of the flow graph.
  - visitCFGList
```
public void visitCFGList(java.util.List<? extends Term> elements,
                Term after,
                int entry)
```
    Utility function to visit all edges in a list. If entry is Term.ENTRY, the final successor is after's entry node; if it's Term.EXIT, it's after's exit.
  - visitCFG
```
public void visitCFG(Term a,
            Term succ,
            int entry)
```
    Create an edge for a node a with a single successor succ. The EdgeKey used for the edge from a to succ will be FlowGraph.EDGE_KEY_OTHER. If entry is Term.ENTRY, the successor is succ's entry node; if it's Term.EXIT, it's succ's exit.
  - visitCFG
```
public void visitCFG(Term a,
            FlowGraph.EdgeKey edgeKey,
            Term succ,
            int entry)
```
    Create an edge for a node a with a single successor succ, and EdgeKey edgeKey. If entry is Term.ENTRY, the successor is succ's entry node; if it's Term.EXIT, it's succ's exit.
  - visitCFG
```
public void visitCFG(Term a,
            FlowGraph.EdgeKey edgeKey1,
            Term succ1,
            int entry1,
            FlowGraph.EdgeKey edgeKey2,
            Term succ2,
            int entry2)
```
    Create edges from node a to successors succ1 and succ2 with EdgeKeys edgeKey1 and edgeKey2 respectively. entry1 and entry2 determine whether the successors are entry or exit nodes. They can be Term.ENTRY or Term.EXIT.
  - visitCFG
```
public void visitCFG(Term a,
            FlowGraph.EdgeKey edgeKey,
            java.util.List<Term> succ,
            int entry)
```
    Create edges from node a to all successors succ with the EdgeKey edgeKey for all edges created. If entry is Term.ENTRY, all terms in succ are treated as entry nodes; if it's Term.EXIT, they are treated as exit nodes.
  - visitCFG
```
public void visitCFG(Term a,
            FlowGraph.EdgeKey edgeKey,
            java.util.List<Term> succ,
            java.util.List<java.lang.Integer> entry)
```
    Create edges from node a to all successors succ with the EdgeKey edgeKey for all edges created. The entry list must have the same size as succ, and each corresponding element determines whether a successor is an entry or exit node (using Term.ENTRY or Term.EXIT).
  - visitCFG
```
protected void visitCFG(Term a,
            java.util.List<CFGBuilder.EdgeKeyTermPair> succs)
```
    Create edges for a node a with successors succs.
    
    Parameters:
    a - the source node for the edges.
    succs - a list of EdgeKeyTermPairs
  - visitThrow
```
public void visitThrow(Term a)
```
  - visitThrow
```
public void visitThrow(Term t,
              int entry,
              Type type)
```
    Create edges for an exception thrown from term t.
  - tryFinally
```
protected static <FlowItem extends DataFlow.Item> FlowGraph.Peer<FlowItem> tryFinally(CFGBuilder<FlowItem> v,
                                                                   FlowGraph.Peer<FlowItem> last,
                                                                   boolean abruptCompletion,
                                                                   FlowGraph.EdgeKey edgeKeyToFinally,
                                                                   Block finallyBlock)
```
    Create edges for the finally block of a try-finally construct.
    
    Parameters:
    v - v.innermostTarget is the Try term that the finallyBlock is associated with.
    last - is the last peer visited before the finally block is entered.
    abruptCompletion - is true if and only if the finally block is being entered due to the (attempted) abrupt completion of the term last.node.
    edgeKeyToFinally - the EdgeKey to use for the edge going to the entry of the finally block. If null, then FlowGraph.EDGE_KEY_OTHER will be used.
    finallyBlock - the finally block associated with a try finally block.
  - tryFinally
```
protected static <FlowItem extends DataFlow.Item> FlowGraph.Peer<FlowItem> tryFinally(CFGBuilder<FlowItem> v,
                                                                   FlowGraph.Peer<FlowItem> last,
                                                                   boolean abruptCompletion,
                                                                   Block finallyBlock)
```
    Create edges for the finally block of a try-finally construct.
    
    Parameters:
    v - v.innermostTarget is the Try term that the finallyBlock is associated with.
    last - is the last peer visited before the finally block is entered.
    abruptCompletion - is true if and only if the finally block is being entered due to the (attempted) abrupt completion of the term last.node.
    finallyBlock - the finally block associated with a try finally block.
  - enterFinally
```
protected CFGBuilder<FlowItem> enterFinally(FlowGraph.Peer<FlowItem> from,
                                boolean abruptCompletion)
```
    Enter a finally block. This method returns a new CFGBuilder with the path_to_finally set appropriately. If we are entering the finally block because peer from is (attempting to) complete abruptly, then the path_to_finally will have Term from appended to the path_to_finally list of from. Otherwise, from is not attempting to complete abruptly, and the path_to_finally will be the same as from.path_to_finally.
  - edge
```
public void edge(Term p,
        Term q,
        int qEntry)
```
    Add an edge to the CFG from the exit of p to either the entry or exit of q.
  - edge
```
public void edge(Term p,
        Term q,
        int qEntry,
        FlowGraph.EdgeKey edgeKey)
```
    Add an edge to the CFG from the exit of p to either the entry or exit of q.
  - edge
```
public void edge(CFGBuilder<FlowItem> p_visitor,
        Term p,
        Term q,
        int qEntry,
        FlowGraph.EdgeKey edgeKey)
```
    Add an edge to the CFG from the exit of p to either the entry or exit of q.
  - edge
```
public void edge(CFGBuilder<FlowItem> p_visitor,
        Term p,
        FlowGraph.Peer<FlowItem> pq,
        FlowGraph.EdgeKey edgeKey)
```
    Add an edge to the CFG from the exit of p to peer pq.
  - edge
```
public void edge(CFGBuilder<FlowItem> p_visitor,
        Term p,
        int pEntry,
        Term q,
        int qEntry,
        FlowGraph.EdgeKey edgeKey)
```
    Parameters:
    p_visitor - The visitor used to create p ("this" is the visitor that created q)
    p - The predecessor node in the forward graph
    pEntry - whether we are working with the entry or exit of p. Can be Term.ENTRY or Term.EXIT.
    q - The successor node in the forward graph
    qEntry - whether we are working with the entry or exit of q. Can be Term.ENTRY or Term.EXIT.
  - edge
```
protected void edge(FlowGraph.Peer<FlowItem> pp,
        FlowGraph.Peer<FlowItem> pq,
        FlowGraph.EdgeKey edgeKey)
```
  - skipDeadIfBranches
```
public boolean skipDeadIfBranches()
```
    Should the CFG construction skip dead if branches? (e.g., should statement s be skipped in the following: if (false) { S } ). Different dataflow analyses require different behavior.
  - skipDeadIfBranches
```
public CFGBuilder<FlowItem> skipDeadIfBranches(boolean b)
```
  - skipDeadLoopBodies
```
public boolean skipDeadLoopBodies()
```
    Should the CFG construction skip dead loop bodies? (e.g., should statement s be skipped in the following: while (false) { S } ). Different dataflow analyses require different behavior.
  - skipDeadLoopBodies
```
public CFGBuilder<FlowItem> skipDeadLoopBodies(boolean b)
```
  - errorEdgesToExitNode
```
public CFGBuilder<FlowItem> errorEdgesToExitNode(boolean b)
```
  - exceptionEdgesToFinally
```
public CFGBuilder<FlowItem> exceptionEdgesToFinally(boolean b)
```
  - trackImplicitErrors
```
public CFGBuilder<FlowItem> trackImplicitErrors(boolean b)
```

Class CFGBuilder<FlowItem extends DataFlow.Item>

Nested Class Summary

Nested classes/interfaces inherited from interface polyglot.util.Copy

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

graph

ts

outer

innermostTarget

path_to_finally

df

skipInnermostCatches

skipDeadIfBranches

skipDeadLoopBodies

errorEdgesToExitNode

trackImplicitErrors

exceptionEdgesToFinally

counter

Constructor Detail

CFGBuilder

Method Detail

lang

graph

dataflow

outer

innermostTarget

skipInnermostCatches

typeSystem

copy

push

push

visitBranchTarget

visitReturn

visitGraph

entryPeer

exitPeer

visitCFGList

visitCFG

visitCFG

visitCFG

visitCFG

visitCFG

visitCFG

visitThrow

visitThrow

tryFinally

tryFinally

enterFinally

edge

edge

edge

edge

edge

edge

skipDeadIfBranches

skipDeadIfBranches

skipDeadLoopBodies

skipDeadLoopBodies

errorEdgesToExitNode

exceptionEdgesToFinally

trackImplicitErrors