/*

 * Copyright 1999-2006 Sun Microsystems, Inc.  All Rights Reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Sun designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Sun in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 */

//todo: one might eliminate uninits.andSets when monotonic

package com.sun.tools.javac.comp;

import com.sun.tools.javac.code.*;

import com.sun.tools.javac.tree.*;

import com.sun.tools.javac.util.*;

import com.sun.tools.javac.util.JCDiagnostic.DiagnosticPosition;

import com.sun.tools.javac.code.Symbol.*;

import com.sun.tools.javac.tree.JCTree.*;

import static com.sun.tools.javac.code.Flags.*;

import static com.sun.tools.javac.code.Kinds.*;

import static com.sun.tools.javac.code.TypeTags.*;

/** 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

 *  <pre>

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

 *  </pre>

 *  <p>In 16.2.15, the third bullet (and all of its sub-bullets) for all

 *  try blocks is changed to

 *  <pre>

 *      V is definitely unassigned before a catch block iff V is

 *      definitely unassigned everywhere in the try block.

 *  </pre>

 *  <p>The last bullet (and all of its sub-bullets) for try blocks that

 *  have a finally block is changed to

 *  <pre>

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

 *  </pre>

 *  <p>In addition,

 *  <pre>

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

 *

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

 *

 *  <p><b>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.</b>

 */

public class Flow extends TreeScanner {

    protected static final Context.Key<Flow> flowKey =

        new Context.Key<Flow>();

    private final Name.Table names;

    private final Log log;

    private final Symtab syms;

    private final Types types;

    private final Check chk;

    private       TreeMaker make;

    private       Lint lint;

    public static Flow instance(Context context) {

        Flow instance = context.get(flowKey);

        if (instance == null)

            instance = new Flow(context);

        return instance;

    }

    protected Flow(Context context) {

        context.put(flowKey, this);

        names = Name.Table.instance(context);

        log = Log.instance(context);

        syms = Symtab.instance(context);

        types = Types.instance(context);

        chk = Check.instance(context);

        lint = Lint.instance(context);

    }

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

     */

    JCClassDecl 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<Type> thrown;

    /** The list of exceptions that are either caught or declared to be

     *  thrown.

     */

    List<Type> caught;

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

    boolean loopPassTwo = false;

    /*-------------------- Environments ----------------------*/

    /** 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 {

        JCTree tree;

        Bits inits;

        Bits uninits;

        Type thrown;

        PendingExit(JCTree tree, Bits inits, Bits uninits) {

            this.tree = tree;

            this.inits = inits.dup();

            this.uninits = uninits.dup();

        }

        PendingExit(JCTree tree, Type thrown) {

            this.tree = tree;

            this.thrown = thrown;

        }

    }

    /** The currently pending exits that go from current inner blocks

     *  to an enclosing block, in source order.

     */

    ListBuffer<PendingExit> pendingExits;

    /*-------------------- Exceptions ----------------------*/

    /** Complain that pending exceptions are not caught.

     */

    void errorUncaught() {

        for (PendingExit exit = pendingExits.next();

             exit != null;

             exit = 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);

        }

    }

    /** Record that exception is potentially thrown and check that it

     *  is caught.

     */

    void markThrown(JCTree 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);

        }

    }

    /*-------------- Processing variables ----------------------*/

    /** 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(DiagnosticPosition 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);

                } else if (!uninits.isMember(sym.adr)) {

                    log.error(pos,

                              loopPassTwo

                              ? "var.might.be.assigned.in.loop"

                              : "var.might.already.be.assigned",

                              sym);

                } else if (!inits.isMember(sym.adr)) {

                    // reachable assignment

                    uninits.excl(sym.adr);

                    uninitsTry.excl(sym.adr);

                } else {

                    //log.rawWarning(pos, "unreachable assignment");//DEBUG

                    uninits.excl(sym.adr);

                }

            }

            inits.incl(sym.adr);

        } else if ((sym.flags() & FINAL) != 0) {

            log.error(pos, "var.might.already.be.assigned", sym);

        }

    }

    /** 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(JCTree tree) {

        tree = TreeInfo.skipParens(tree);

        if (tree.getTag() == JCTree.IDENT || tree.getTag() == JCTree.SELECT) {

            Symbol sym = TreeInfo.symbol(tree);

            letInit(tree.pos(), (VarSymbol)sym);

        }

    }

    /** Check that trackable variable is initialized.

     */

    void checkInit(DiagnosticPosition 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);

            inits.incl(sym.adr);

        }

    }

    /*-------------------- Handling jumps ----------------------*/

    /** Record an outward transfer of control. */

    void recordExit(JCTree tree) {

        pendingExits.append(new PendingExit(tree, inits, uninits));

        markDead();

    }

    /** Resolve all breaks of this statement. */

    boolean resolveBreaks(JCTree tree,

                          ListBuffer<PendingExit> oldPendingExits) {

        boolean result = false;

        List<PendingExit> exits = pendingExits.toList();

        pendingExits = oldPendingExits;

        for (; exits.nonEmpty(); exits = exits.tail) {

            PendingExit exit = exits.head;

            if (exit.tree.getTag() == JCTree.BREAK &&

                ((JCBreak) exit.tree).target == tree) {

                inits.andSet(exit.inits);

                uninits.andSet(exit.uninits);

                result = true;

            } else {

                pendingExits.append(exit);

            }

        }

        return result;

    }

    /** Resolve all continues of this statement. */

    boolean resolveContinues(JCTree tree) {

        boolean result = false;

        List<PendingExit> exits = pendingExits.toList();

        pendingExits = new ListBuffer<PendingExit>();

        for (; exits.nonEmpty(); exits = exits.tail) {

            PendingExit exit = exits.head;

            if (exit.tree.getTag() == JCTree.CONTINUE &&

                ((JCContinue) exit.tree).target == tree) {

                inits.andSet(exit.inits);

                uninits.andSet(exit.uninits);

                result = true;

            } else {

                pendingExits.append(exit);

            }

        }

        return result;

    }

    /** Record that statement is unreachable.

     */

    void markDead() {

        inits.inclRange(firstadr, nextadr);

        uninits.inclRange(firstadr, nextadr);

        alive = false;

    }

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

     */

    void split() {

        initsWhenFalse = inits.dup();

        uninitsWhenFalse = uninits.dup();

        initsWhenTrue = inits;

        uninitsWhenTrue = uninits;

        inits = uninits = null;

    }

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

     */

    void merge() {

        inits = initsWhenFalse.andSet(initsWhenTrue);

        uninits = uninitsWhenFalse.andSet(uninitsWhenTrue);

    }

/* ************************************************************************

 * Visitor methods for statements and definitions

 *************************************************************************/

    /** Analyze a definition.

     */

    void scanDef(JCTree tree) {

        scanStat(tree);

        if (tree != null && tree.getTag() == JCTree.BLOCK && !alive) {

            log.error(tree.pos(),

                      "initializer.must.be.able.to.complete.normally");

        }

    }

    /** Analyze a statement. Check that statement is reachable.

     */

    void scanStat(JCTree tree) {

        if (!alive && tree != null) {

            log.error(tree.pos(), "unreachable.stmt");

            if (tree.getTag() != JCTree.SKIP) alive = true;

        }

        scan(tree);

    }

    /** Analyze list of statements.

     */

    void scanStats(List<? extends JCStatement> trees) {

        if (trees != null)

            for (List<? extends JCStatement> l = trees; l.nonEmpty(); l = l.tail)

                scanStat(l.head);

    }

    /** Analyze an expression. Make sure to set (un)inits rather than

     *  (un)initsWhenTrue(WhenFalse) on exit.

     */

    void scanExpr(JCTree tree) {

        if (tree != null) {

            scan(tree);

            if (inits == null) merge();

        }

    }

    /** Analyze a list of expressions.

     */

    void scanExprs(List<? extends JCExpression> trees) {

        if (trees != null)

            for (List<? extends JCExpression> l = trees; l.nonEmpty(); l = l.tail)

                scanExpr(l.head);

    }

    /** Analyze a condition. Make sure to set (un)initsWhenTrue(WhenFalse)

     *  rather than (un)inits on exit.

     */