/** * @(#)Flow.java	1.64 03/04/16 * * Copyright 2003 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */package com.sun.tools.javac.v8.comp;import com.sun.tools.javac.v8.util.*;import com.sun.tools.javac.v8.code.*;import com.sun.tools.javac.v8.tree.*;import com.sun.tools.javac.v8.code.Symbol.*;import com.sun.tools.javac.v8.tree.Tree.*;import com.sun.tools.javac.v8.code.Type.*;/** * 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. * *  <p>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. * *  <p>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. * *  <p>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 <em>unassigned everywhere</em> 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. *  </pre> * *  <p>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. * *  <p>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". * *  <p>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. * *  <p>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. * *  <p>Intervening finally blocks similarly affect exception analysis.	An *  intervening finally that cannot complete normally allows us to ignore *  an otherwise uncaught exception. * *  <p>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<Type> thrown" that records the type of all *  exceptions that can be thrown. * *  <p>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. */public class Flow extends TreeScanner implements Flags, Kinds, TypeTags {    private static final Context.Key flowKey = new Context.Key();    private Name.Table names;    private Log log;    private Symtab syms;    private Check chk;    private TreeMaker make;    private boolean switchCheck;    public static Flow instance(Context context) {        Flow instance = (Flow) context.get(flowKey);        if (instance == null)            instance = new Flow(context);        return instance;    }    private Flow(Context context) {        super();        context.put(flowKey, this);        names = Name.Table.instance(context);        log = Log.instance(context);        syms = Symtab.instance(context);        chk = Check.instance(context);        Options options = Options.instance(context);        switchCheck = options.get("-Xswitchcheck") != null;    }    /**      * A flag that indicates whether the last statement could      *	complete normally.      */    private boolean alive;    /**     * The set of definitely assigned variables.     */    Bits inits;    /**     * The set of definitely unassigned variables.     */    Bits uninits;    /**     * 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.     */    Bits uninitsTry;    /**     * When analyzing a condition, inits and uninits are null.     *	Instead we have:     */    Bits initsWhenTrue;    Bits initsWhenFalse;    Bits uninitsWhenTrue;    Bits uninitsWhenFalse;    /**     * A mapping from addresses to variable symbols.     */    VarSymbol[] vars;    /**     * The current class being defined.     */    ClassDef classDef;    /**     * The first variable sequence number in this class definition.     */    int firstadr;    /**     * The next available variable sequence number.     */    int nextadr;    /**     * The list of possibly thrown declarable exceptions.     */    List thrown;    /**     * The list of exceptions that are either caught or declared to be     *	thrown.     */    List caught;    /**     * Set when processing a loop body the second time for DU analysis.     */    boolean loopPassTwo = false;    /**     * A pending exit.	 These are the statements return, break, and     *	continue.  In addition, exception-throwing expressions or     *	statements are put here when not known to be caught.  This     *	will typically result in an error unless it is within a     *	try-finally whose finally block cannot complete normally.     */    static class PendingExit {        Tree tree;        Bits inits;        Bits uninits;        Type thrown;        PendingExit(Tree tree, Bits inits, Bits uninits) {            super();            this.tree = tree;            this.inits = inits.dup();            this.uninits = uninits.dup();        }        PendingExit(Tree tree, Type thrown) {            super();            this.tree = tree;            this.thrown = thrown;        }    }    /**      * The currently pending exits that go from current inner blocks      *	to an enclosing block, in source order.      */    ListBuffer pendingExits;    /**     * Complain that pending exceptions are not caught.     */    void errorUncaught() {        for (PendingExit exit = (Flow.PendingExit) pendingExits.next();                exit != null; exit = (Flow.PendingExit) pendingExits.next()) {            boolean synthetic = classDef != null && classDef.pos == exit.tree.pos;            log.error(exit.tree.pos,                    synthetic ? "unreported.exception.default.constructor" : "unreported.exception.need.to.catch.or.throw",                    exit.thrown.toJava());        }    }    /**      * Record that exception is potentially thrown and check that it      *	is caught.      */    void markThrown(Tree tree, Type exc) {        if (!chk.isUnchecked(tree.pos, exc)) {            if (!chk.isHandled(exc, caught))                pendingExits.append(new PendingExit(tree, exc));            thrown = chk.incl(exc, thrown);        }    }    /**      * Do we need to track init/uninit state of this symbol?      *	I.e. is symbol either a local or a blank final variable?      */    boolean trackable(VarSymbol sym) {        return (sym.owner.kind == MTH ||                ((sym.flags() & (FINAL | HASINIT | PARAMETER)) == FINAL &&                classDef.sym.isEnclosedBy((ClassSymbol) sym.owner)));    }    /**      * 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.      */    void newVar(VarSymbol sym) {        if (nextadr == vars.length) {            VarSymbol[] newvars = new VarSymbol[nextadr * 2];            System.arraycopy(vars, 0, newvars, 0, nextadr);            vars = newvars;        }        sym.adr = nextadr;        vars[nextadr] = sym;        inits.excl(nextadr);        uninits.incl(nextadr);        nextadr++;    }    /**      * Record an initialization of a trackable variable.      */    void letInit(int pos, VarSymbol sym) {        if (sym.adr >= firstadr && trackable(sym)) {            if ((sym.flags() & FINAL) != 0) {                if ((sym.flags() & PARAMETER) != 0) {                    log.error(pos, "final.parameter.may.not.be.assigned",                            sym.toJava());                } else if (!uninits.isMember(sym.adr)) {                    log.error(pos,                            loopPassTwo ? "var.might.be.assigned.in.loop" : "var.might.already.be.assigned",                            sym.toJava());                } else if (!inits.isMember(sym.adr)) {                    uninits.excl(sym.adr);                    uninitsTry.excl(sym.adr);                } else {                    uninits.excl(sym.adr);                }            }            inits.incl(sym.adr);        } else if ((sym.flags() & FINAL) != 0) {            log.error(pos, "var.might.already.be.assigned", sym.toJava());        }    }    /**      * 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.      */    void letInit(Tree tree) {        tree = TreeInfo.skipParens(tree);        if (tree.tag == Tree.IDENT || tree.tag == Tree.SELECT) {            Symbol sym = TreeInfo.symbol(tree);            letInit(tree.pos, (VarSymbol) sym);        }    }    /**      * Check that trackable variable is initialized.      */    void checkInit(int pos, VarSymbol sym) {        if ((sym.adr >= firstadr || sym.owner.kind != TYP) && trackable(sym) &&                !inits.isMember(sym.adr)) {            log.error(pos, "var.might.not.have.been.initialized", sym.toJava());            inits.incl(sym.adr);        }    }    /**      * Record an outward transfer of control.      */    void recordExit(Tree tree) {        pendingExits.append(new PendingExit(tree, inits, uninits));        markDead();    }