com.sun.tools.javac.comp
Class Flow

java.lang.Object
  com.sun.tools.javac.tree.JCTree.Visitor
      com.sun.tools.javac.tree.TreeScanner
          com.sun.tools.javac.comp.Flow

public class Flow
extends TreeScanner

This pass implements dataflow analysis for Java programs. Liveness analysis checks that every statement is reachable. Exception analysis ensures that every checked exception that is thrown is declared or caught. Definite assignment analysis ensures that each variable is assigned when used. Definite unassignment analysis ensures that no final variable is assigned more than once.

The second edition of the JLS has a number of problems in the specification of these flow analysis problems. This implementation attempts to address those issues.

First, there is no accommodation for a finally clause that cannot complete normally. For liveness analysis, an intervening finally clause can cause a break, continue, or return not to reach its target. For exception analysis, an intervening finally clause can cause any exception to be "caught". For DA/DU analysis, the finally clause can prevent a transfer of control from propagating DA/DU state to the target. In addition, code in the finally clause can affect the DA/DU status of variables.

For try statements, we introduce the idea of a variable being definitely unassigned "everywhere" in a block. A variable V is "unassigned everywhere" in a block iff it is unassigned at the beginning of the block and there is no reachable assignment to V in the block. An assignment V=e is reachable iff V is not DA after e. Then we can say that V is DU at the beginning of the catch block iff V is DU everywhere in the try block. Similarly, V is DU at the beginning of the finally block iff V is DU everywhere in the try block and in every catch block. Specifically, the following bullet is added to 16.2.2

      V is unassigned everywhere in a block if it is
      unassigned before the block and there is no reachable
      assignment to V within the block.
  

In 16.2.15, the third bullet (and all of its sub-bullets) for all try blocks is changed to

      V is definitely unassigned before a catch block iff V is
      definitely unassigned everywhere in the try block.
  

The last bullet (and all of its sub-bullets) for try blocks that have a finally block is changed to

      V is definitely unassigned before the finally block iff
      V is definitely unassigned everywhere in the try block
      and everywhere in each catch block of the try statement.
  

In addition,

      V is definitely assigned at the end of a constructor iff
      V is definitely assigned after the block that is the body
      of the constructor and V is definitely assigned at every
      return that can return from the constructor.
  

In addition, each continue statement with the loop as its target is treated as a jump to the end of the loop body, and "intervening" finally clauses are treated as follows: V is DA "due to the continue" iff V is DA before the continue statement or V is DA at the end of any intervening finally block. V is DU "due to the continue" iff any intervening finally cannot complete normally or V is DU at the end of every intervening finally block. This "due to the continue" concept is then used in the spec for the loops.

Similarly, break statements must consider intervening finally blocks. For liveness analysis, a break statement for which any intervening finally cannot complete normally is not considered to cause the target statement to be able to complete normally. Then we say V is DA "due to the break" iff V is DA before the break or V is DA at the end of any intervening finally block. V is DU "due to the break" iff any intervening finally cannot complete normally or V is DU at the break and at the end of every intervening finally block. (I suspect this latter condition can be simplified.) This "due to the break" is then used in the spec for all statements that can be "broken".

The return statement is treated similarly. V is DA "due to a return statement" iff V is DA before the return statement or V is DA at the end of any intervening finally block. Note that we don't have to worry about the return expression because this concept is only used for construcrors.

There is no spec in JLS2 for when a variable is definitely assigned at the end of a constructor, which is needed for final fields (8.3.1.2). We implement the rule that V is DA at the end of the constructor iff it is DA and the end of the body of the constructor and V is DA "due to" every return of the constructor.

Intervening finally blocks similarly affect exception analysis. An intervening finally that cannot complete normally allows us to ignore an otherwise uncaught exception.

To implement the semantics of intervening finally clauses, all nonlocal transfers (break, continue, return, throw, method call that can throw a checked exception, and a constructor invocation that can thrown a checked exception) are recorded in a queue, and removed from the queue when we complete processing the target of the nonlocal transfer. This allows us to modify the queue in accordance with the above rules when we encounter a finally clause. The only exception to this [no pun intended] is that checked exceptions that are known to be caught or declared to be caught in the enclosing method are not recorded in the queue, but instead are recorded in a global variable "Set thrown" that records the type of all exceptions that can be thrown.

Other minor issues the treatment of members of other classes (always considered DA except that within an anonymous class constructor, where DA status from the enclosing scope is preserved), treatment of the case expression (V is DA before the case expression iff V is DA after the switch expression), treatment of variables declared in a switch block (the implied DA/DU status after the switch expression is DU and not DA for variables defined in a switch block), the treatment of boolean ?: expressions (The JLS rules only handle b and c non-boolean; the new rule is that if b and c are boolean valued, then V is (un)assigned after a?b:c when true/false iff V is (un)assigned after b when true/false and V is (un)assigned after c when true/false).

There is the remaining question of what syntactic forms constitute a reference to a variable. It is conventional to allow this.x on the left-hand-side to initialize a final instance field named x, yet this.x isn't considered a "use" when appearing on a right-hand-side in most implementations. Should parentheses affect what is considered a variable reference? The simplest rule would be to allow unqualified forms only, parentheses optional, and phase out support for assigning to a final field via this.x.

This is NOT part of any API supported by Sun Microsystems. If you write code that depends on this, you do so at your own risk. This code and its internal interfaces are subject to change or deletion without notice.

Nested Class Summary

(package private) static class

Flow.PendingExit A pending exit.

Field Summary

private boolean	alive A flag that indicates whether the last statement could complete normally.
(package private) List<Type>	caught The list of exceptions that are either caught or declared to be thrown.
private Check	chk
(package private) JCTree.JCClassDecl	classDef The current class being defined.
(package private) int	firstadr The first variable sequence number in this class definition.
protected static Context.Key<Flow>	flowKey
(package private) Bits	inits The set of definitely assigned variables.
(package private) Bits	initsWhenFalse
(package private) Bits	initsWhenTrue When analyzing a condition, inits and uninits are null.
private Lint	lint
private Log	log
(package private) boolean	loopPassTwo Set when processing a loop body the second time for DU analysis.
private TreeMaker	make
private Names	names
(package private) int	nextadr The next available variable sequence number.
(package private) ListBuffer<Flow.PendingExit>	pendingExits The currently pending exits that go from current inner blocks to an enclosing block, in source order.
private Symtab	syms
(package private) List<Type>	thrown The list of possibly thrown declarable exceptions.
private Types	types
(package private) Bits	uninits The set of definitely unassigned variables.
(package private) Bits	uninitsTry The set of variables that are definitely unassigned everywhere in current try block.
(package private) Bits	uninitsWhenFalse
(package private) Bits	uninitsWhenTrue
(package private) Symbol.VarSymbol[]	vars A mapping from addresses to variable symbols.

Constructor Summary

protected

Flow(Context context)

Method Summary

private static void	addVars(List<JCTree.JCStatement> stats, Bits inits, Bits uninits) Add any variables defined in stats to inits and uninits.
void	analyzeTree(JCTree tree, TreeMaker make) Perform definite assignment/unassignment analysis on a tree.
(package private) void	checkInit(JCDiagnostic.DiagnosticPosition pos, Symbol.VarSymbol sym) Check that trackable variable is initialized.
(package private) void	errorUncaught() Complain that pending exceptions are not caught.
static Flow	instance(Context context)
(package private) void	letInit(JCDiagnostic.DiagnosticPosition pos, Symbol.VarSymbol sym) Record an initialization of a trackable variable.
(package private) void	letInit(JCTree tree) If tree is either a simple name or of the form this.name or C.this.name, and tree represents a trackable variable, record an initialization of the variable.
(package private) void	markDead() Record that statement is unreachable.
(package private) void	markThrown(JCTree tree, Type exc) Record that exception is potentially thrown and check that it is caught.
(package private) void	merge() Merge (intersect) inits/uninits from WhenTrue/WhenFalse sets.
(package private) void	newVar(Symbol.VarSymbol sym) Initialize new trackable variable by setting its address field to the next available sequence number and entering it under that index into the vars array.
(package private) void	recordExit(JCTree tree) Record an outward transfer of control.
(package private) boolean	resolveBreaks(JCTree tree, ListBuffer<Flow.PendingExit> oldPendingExits) Resolve all breaks of this statement.
(package private) boolean	resolveContinues(JCTree tree) Resolve all continues of this statement.
(package private) void	scanCond(JCTree tree) Analyze a condition.
(package private) void	scanDef(JCTree tree) Analyze a definition.
(package private) void	scanExpr(JCTree tree) Analyze an expression.
(package private) void	scanExprs(List<? extends JCTree.JCExpression> trees) Analyze a list of expressions.
(package private) void	scanStat(JCTree tree) Analyze a statement.
(package private) void	scanStats(List<? extends JCTree.JCStatement> trees) Analyze list of statements.
(package private) void	split() Split (duplicate) inits/uninits into WhenTrue/WhenFalse sets
(package private) boolean	trackable(Symbol.VarSymbol sym) Do we need to track init/uninit state of this symbol? I.e.
void	visitApply(JCTree.JCMethodInvocation tree)
void	visitAssert(JCTree.JCAssert tree)
void	visitAssign(JCTree.JCAssign tree)
void	visitAssignop(JCTree.JCAssignOp tree)
void	visitBinary(JCTree.JCBinary tree)
void	visitBlock(JCTree.JCBlock tree)
void	visitBreak(JCTree.JCBreak tree)
void	visitClassDef(JCTree.JCClassDecl tree)
void	visitConditional(JCTree.JCConditional tree)
void	visitContinue(JCTree.JCContinue tree)
void	visitDoLoop(JCTree.JCDoWhileLoop tree)
void	visitForeachLoop(JCTree.JCEnhancedForLoop tree)
void	visitForLoop(JCTree.JCForLoop tree)
void	visitIdent(JCTree.JCIdent tree)
void	visitIf(JCTree.JCIf tree)
void	visitLabelled(JCTree.JCLabeledStatement tree)
void	visitLetExpr(JCTree.LetExpr tree)
void	visitMethodDef(JCTree.JCMethodDecl tree)
void	visitNewArray(JCTree.JCNewArray tree)
void	visitNewClass(JCTree.JCNewClass tree)
void	visitReturn(JCTree.JCReturn tree)
void	visitSwitch(JCTree.JCSwitch tree)
void	visitThrow(JCTree.JCThrow tree)
void	visitTopLevel(JCTree.JCCompilationUnit tree)
void	visitTry(JCTree.JCTry tree)
void	visitTypeCast(JCTree.JCTypeCast tree)
void	visitUnary(JCTree.JCUnary tree)
void	visitVarDef(JCTree.JCVariableDecl tree)
void	visitWhileLoop(JCTree.JCWhileLoop tree)

Methods inherited from class com.sun.tools.javac.tree.TreeScanner

scan, scan, visitAnnotation, visitBracketExpr, visitCase, visitCatch, visitErroneous, visitExec, visitImport, visitIndexed, visitLiteral, visitModifiers, visitParens, visitSelect, visitSkip, visitSynchronized, visitTree, visitTypeApply, visitTypeArray, visitTypeBoundKind, visitTypeIdent, visitTypeParameter, visitTypeTest, visitWildcard

Methods inherited from class com.sun.tools.javac.tree.JCTree.Visitor

visitBracketStat, visitEscapeExpr, visitEscapeStat

Methods inherited from class java.lang.Object

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

Field Detail

flowKey

protected static final Context.Key<Flow> flowKey

names

private final Names names

log

private final Log log

syms

private final Symtab syms

types

private final Types types

chk

private final Check chk

make

private TreeMaker make

lint

private Lint lint

alive

private boolean alive

A flag that indicates whether the last statement could complete normally.

inits

Bits inits

The set of definitely assigned variables.

uninits

Bits uninits

The set of definitely unassigned variables.

uninitsTry

Bits uninitsTry

The set of variables that are definitely unassigned everywhere in current try block. This variable is maintained lazily; it is updated only when something gets removed from uninits, typically by being assigned in reachable code. To obtain the correct set of variables which are definitely unassigned anywhere in current try block, intersect uninitsTry and uninits.

initsWhenTrue

Bits initsWhenTrue

When analyzing a condition, inits and uninits are null. Instead we have:

initsWhenFalse

Bits initsWhenFalse

uninitsWhenTrue

Bits uninitsWhenTrue

uninitsWhenFalse

Bits uninitsWhenFalse

vars

Symbol.VarSymbol[] vars

A mapping from addresses to variable symbols.

classDef

JCTree.JCClassDecl classDef

The current class being defined.

firstadr

int firstadr

The first variable sequence number in this class definition.

nextadr

int nextadr

The next available variable sequence number.

thrown

List<Type> thrown

The list of possibly thrown declarable exceptions.

caught

List<Type> caught

The list of exceptions that are either caught or declared to be thrown.

loopPassTwo

boolean loopPassTwo

Set when processing a loop body the second time for DU analysis.

pendingExits

ListBuffer<Flow.PendingExit> pendingExits

The currently pending exits that go from current inner blocks to an enclosing block, in source order.

Constructor Detail

Flow

protected Flow(Context context)

Method Detail

instance

public static Flow instance(Context context)

errorUncaught

void errorUncaught()

Complain that pending exceptions are not caught.

markThrown

void markThrown(JCTree tree,
                Type exc)

Record that exception is potentially thrown and check that it is caught.

trackable

boolean trackable(Symbol.VarSymbol sym)

Do we need to track init/uninit state of this symbol? I.e. is symbol either a local or a blank final variable?

newVar

void newVar(Symbol.VarSymbol sym)

Initialize new trackable variable by setting its address field to the next available sequence number and entering it under that index into the vars array.

letInit

void letInit(JCDiagnostic.DiagnosticPosition pos,
             Symbol.VarSymbol sym)

Record an initialization of a trackable variable.

letInit

void letInit(JCTree tree)

If tree is either a simple name or of the form this.name or C.this.name, and tree represents a trackable variable, record an initialization of the variable.

checkInit

void checkInit(JCDiagnostic.DiagnosticPosition pos,
               Symbol.VarSymbol sym)

Check that trackable variable is initialized.

recordExit

void recordExit(JCTree tree)

Record an outward transfer of control.

resolveBreaks

boolean resolveBreaks(JCTree tree,
                      ListBuffer<Flow.PendingExit> oldPendingExits)

Resolve all breaks of this statement.

resolveContinues

boolean resolveContinues(JCTree tree)

Resolve all continues of this statement.

markDead

void markDead()

Record that statement is unreachable.

split

void split()

Split (duplicate) inits/uninits into WhenTrue/WhenFalse sets

merge

void merge()

Merge (intersect) inits/uninits from WhenTrue/WhenFalse sets.

scanDef

void scanDef(JCTree tree)

Analyze a definition.

scanStat

void scanStat(JCTree tree)

Analyze a statement. Check that statement is reachable.

scanStats

void scanStats(List<? extends JCTree.JCStatement> trees)

Analyze list of statements.

scanExpr

void scanExpr(JCTree tree)

Analyze an expression. Make sure to set (un)inits rather than (un)initsWhenTrue(WhenFalse) on exit.

scanExprs

void scanExprs(List<? extends JCTree.JCExpression> trees)

Analyze a list of expressions.

scanCond

void scanCond(JCTree tree)

Analyze a condition. Make sure to set (un)initsWhenTrue(WhenFalse) rather than (un)inits on exit.

visitClassDef

public void visitClassDef(JCTree.JCClassDecl tree)

Overrides:

visitClassDef in class TreeScanner

visitMethodDef

public void visitMethodDef(JCTree.JCMethodDecl tree)

Overrides:

visitMethodDef in class TreeScanner

visitVarDef

public void visitVarDef(JCTree.JCVariableDecl tree)

Overrides:

visitVarDef in class TreeScanner

visitBlock

public void visitBlock(JCTree.JCBlock tree)

Overrides:

visitBlock in class TreeScanner

visitDoLoop

public void visitDoLoop(JCTree.JCDoWhileLoop tree)

Overrides:

visitDoLoop in class TreeScanner

visitWhileLoop

public void visitWhileLoop(JCTree.JCWhileLoop tree)

Overrides:

visitWhileLoop in class TreeScanner

visitForLoop

public void visitForLoop(JCTree.JCForLoop tree)

Overrides:

visitForLoop in class TreeScanner

visitForeachLoop

public void visitForeachLoop(JCTree.JCEnhancedForLoop tree)

Overrides:

visitForeachLoop in class TreeScanner

visitLabelled

public void visitLabelled(JCTree.JCLabeledStatement tree)

Overrides:

visitLabelled in class TreeScanner

visitSwitch

public void visitSwitch(JCTree.JCSwitch tree)

Overrides:

visitSwitch in class TreeScanner

addVars

private static void addVars(List<JCTree.JCStatement> stats,
                            Bits inits,
                            Bits uninits)

Add any variables defined in stats to inits and uninits.

visitTry

public void visitTry(JCTree.JCTry tree)

Overrides:

visitTry in class TreeScanner

visitConditional

public void visitConditional(JCTree.JCConditional tree)

Overrides:

visitConditional in class TreeScanner

visitIf

public void visitIf(JCTree.JCIf tree)

Overrides:

visitIf in class TreeScanner

visitBreak

public void visitBreak(JCTree.JCBreak tree)

Overrides:

visitBreak in class TreeScanner

visitContinue

public void visitContinue(JCTree.JCContinue tree)

Overrides:

visitContinue in class TreeScanner

visitReturn

public void visitReturn(JCTree.JCReturn tree)

Overrides:

visitReturn in class TreeScanner

visitThrow

public void visitThrow(JCTree.JCThrow tree)

Overrides:

visitThrow in class TreeScanner

visitApply

public void visitApply(JCTree.JCMethodInvocation tree)

Overrides:

visitApply in class TreeScanner

visitNewClass

public void visitNewClass(JCTree.JCNewClass tree)

Overrides:

visitNewClass in class TreeScanner

visitNewArray

public void visitNewArray(JCTree.JCNewArray tree)

Overrides:

visitNewArray in class TreeScanner

visitAssert

public void visitAssert(JCTree.JCAssert tree)

Overrides:

visitAssert in class TreeScanner

visitAssign

public void visitAssign(JCTree.JCAssign tree)

Overrides:

visitAssign in class TreeScanner

visitAssignop

public void visitAssignop(JCTree.JCAssignOp tree)

Overrides:

visitAssignop in class TreeScanner

visitUnary

public void visitUnary(JCTree.JCUnary tree)

Overrides:

visitUnary in class TreeScanner

visitBinary

public void visitBinary(JCTree.JCBinary tree)

Overrides:

visitBinary in class TreeScanner

visitIdent

public void visitIdent(JCTree.JCIdent tree)

Overrides:

visitIdent in class TreeScanner

visitTypeCast

public void visitTypeCast(JCTree.JCTypeCast tree)

Overrides:

visitTypeCast in class TreeScanner

visitLetExpr

public void visitLetExpr(JCTree.LetExpr tree)

Overrides:

visitLetExpr in class TreeScanner

visitTopLevel

public void visitTopLevel(JCTree.JCCompilationUnit tree)

Overrides:

visitTopLevel in class TreeScanner

analyzeTree

public void analyzeTree(JCTree tree,
                        TreeMaker make)

Perform definite assignment/unassignment analysis on a tree.