/*

 * Copyright (c) 1999, 2012, Oracle and/or its affiliates. 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.  Oracle designates this

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

 * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.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 java.util.HashMap;

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.Flags.BLOCK;

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

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

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

/** This pass implements dataflow analysis for Java programs though

 *  different AST visitor steps. Liveness analysis (see AliveAlanyzer) checks that

 *  every statement is reachable. Exception analysis (see FlowAnalyzer) ensures that

 *  every checked exception that is thrown is declared or caught.  Definite assignment analysis

 *  (see AssignAnalyzer) ensures that each variable is assigned when used.  Definite

 *  unassignment analysis (see AssignAnalyzer) in ensures that no final variable

 *  is assigned more than once. Finally, local variable capture analysis (see CaptureAnalyzer)

 *  determines that local variables accessed within the scope of an inner class are

 *  either final or effectively-final.

 *

 *  <p>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 the JLS 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 supported API.

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

    protected static final Context.Key<Flow> flowKey =

        new Context.Key<Flow>();

    private final Names names;

    private final Log log;

    private final Symtab syms;

    private final Types types;

    private final Check chk;

    private       TreeMaker make;

    private final Resolve rs;

    private final JCDiagnostic.Factory diags;

    private Env<AttrContext> attrEnv;

    private       Lint lint;

    private final boolean allowImprovedRethrowAnalysis;

    private final boolean allowImprovedCatchAnalysis;

    private final boolean allowEffectivelyFinalInInnerClasses;

    public static Flow instance(Context context) {

        Flow instance = context.get(flowKey);

        if (instance == null)

            instance = new Flow(context);

        return instance;

    }

    public void analyzeTree(Env<AttrContext> env, TreeMaker make) {

        new AliveAnalyzer().analyzeTree(env, make);

        new AssignAnalyzer().analyzeTree(env, make);

        new FlowAnalyzer().analyzeTree(env, make);

        new CaptureAnalyzer().analyzeTree(env, make);

    }

    /**

     * Definite assignment scan mode

     */

    enum FlowKind {

        /**

         * This is the normal DA/DU analysis mode

         */

        NORMAL("var.might.already.be.assigned", false),

        /**

         * This is the speculative DA/DU analysis mode used to speculatively

         * derive assertions within loop bodies

         */

        SPECULATIVE_LOOP("var.might.be.assigned.in.loop", true);

        String errKey;

        boolean isFinal;

        FlowKind(String errKey, boolean isFinal) {

            this.errKey = errKey;

            this.isFinal = isFinal;

        }

        boolean isFinal() {

            return isFinal;

        }

    }

    protected Flow(Context context) {

        context.put(flowKey, this);

        names = Names.instance(context);

        log = Log.instance(context);

        syms = Symtab.instance(context);

        types = Types.instance(context);

        chk = Check.instance(context);

        lint = Lint.instance(context);

        rs = Resolve.instance(context);

        diags = JCDiagnostic.Factory.instance(context);

        Source source = Source.instance(context);

        allowImprovedRethrowAnalysis = source.allowImprovedRethrowAnalysis();

        allowImprovedCatchAnalysis = source.allowImprovedCatchAnalysis();

        Options options = Options.instance(context);

        allowEffectivelyFinalInInnerClasses = source.allowEffectivelyFinalInInnerClasses() &&

                options.isSet("allowEffectivelyFinalInInnerClasses"); //pre-lambda guard

    }

    /**

     * Base visitor class for all visitors implementing dataflow analysis logic.

     * This class define the shared logic for handling jumps (break/continue statements).

     */

    static abstract class BaseAnalyzer<P extends BaseAnalyzer.PendingExit> extends TreeScanner {

        enum JumpKind {

            BREAK(JCTree.Tag.BREAK) {

                @Override

                JCTree getTarget(JCTree tree) {

                    return ((JCBreak)tree).target;

                }

            },

            CONTINUE(JCTree.Tag.CONTINUE) {

                @Override

                JCTree getTarget(JCTree tree) {

                    return ((JCContinue)tree).target;

                }

            };

            JCTree.Tag treeTag;

            private JumpKind(Tag treeTag) {

                this.treeTag = treeTag;

            }

            abstract JCTree getTarget(JCTree tree);

        }

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

         *  to an enclosing block, in source order.

         */

        ListBuffer<P> pendingExits;

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

            PendingExit(JCTree tree) {

                this.tree = tree;

            }

            void resolveJump() {

                //do nothing

            }

        }

        abstract void markDead();

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

        void recordExit(JCTree tree, P pe) {

            pendingExits.append(pe);

            markDead();

        }

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

        private boolean resolveJump(JCTree tree,

                        ListBuffer<P> oldPendingExits,

                        JumpKind jk) {

            boolean resolved = false;

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

            pendingExits = oldPendingExits;

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

                P exit = exits.head;

                if (exit.tree.hasTag(jk.treeTag) &&

                        jk.getTarget(exit.tree) == tree) {

                    exit.resolveJump();

                    resolved = true;

                } else {

                    pendingExits.append(exit);

                }

            }

            return resolved;

        }

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

        boolean resolveContinues(JCTree tree) {

            return resolveJump(tree, new ListBuffer<P>(), JumpKind.CONTINUE);

        }

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

        boolean resolveBreaks(JCTree tree, ListBuffer<P> oldPendingExits) {

            return resolveJump(tree, oldPendingExits, JumpKind.BREAK);

        }

    }

    /**

     * This pass implements the first step of the dataflow analysis, namely

     * the liveness analysis check. This checks that every statement is reachable.

     * The output of this analysis pass are used by other analyzers. This analyzer

     * sets the 'finallyCanCompleteNormally' field in the JCTry class.

     */

    class AliveAnalyzer extends BaseAnalyzer<BaseAnalyzer.PendingExit> {

        /** A flag that indicates whether the last statement could

         *  complete normally.

         */

        private boolean alive;

        @Override

        void markDead() {

            alive = false;

        }

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

     * Visitor methods for statements and definitions

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

        /** Analyze a definition.

         */

        void scanDef(JCTree tree) {

            scanStat(tree);

            if (tree != null && tree.hasTag(JCTree.Tag.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.hasTag(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);

        }

        /* ------------ Visitor methods for various sorts of trees -------------*/

        public void visitClassDef(JCClassDecl tree) {

            if (tree.sym == null) return;

            boolean alivePrev = alive;

            ListBuffer<PendingExit> pendingExitsPrev = pendingExits;

            Lint lintPrev = lint;

            pendingExits = new ListBuffer<PendingExit>();

            lint = lint.augment(tree.sym.annotations);

            try {

                // process all the static initializers

                for (List<JCTree> l = tree.defs; l.nonEmpty(); l = l.tail) {

                    if (!l.head.hasTag(METHODDEF) &&

                        (TreeInfo.flags(l.head) & STATIC) != 0) {

                        scanDef(l.head);

                    }

                }

                // process all the instance initializers

                for (List<JCTree> l = tree.defs; l.nonEmpty(); l = l.tail) {

                    if (!l.head.hasTag(METHODDEF) &&

                        (TreeInfo.flags(l.head) & STATIC) == 0) {

                        scanDef(l.head);

                    }

                }

                // process all the methods

                for (List<JCTree> l = tree.defs; l.nonEmpty(); l = l.tail) {

                    if (l.head.hasTag(METHODDEF)) {

                        scan(l.head);

                    }

                }

            } finally {

                pendingExits = pendingExitsPrev;

                alive = alivePrev;

                lint = lintPrev;

            }

        }

        public void visitMethodDef(JCMethodDecl tree) {

            if (tree.body == null) return;

            Lint lintPrev = lint;

            lint = lint.augment(tree.sym.annotations);

            Assert.check(pendingExits.isEmpty());

            try {

                alive = true;

                scanStat(tree.body);

                if (alive && tree.sym.type.getReturnType().tag != VOID)

                    log.error(TreeInfo.diagEndPos(tree.body), "missing.ret.stmt");

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

                pendingExits = new ListBuffer<PendingExit>();

                while (exits.nonEmpty()) {

                    PendingExit exit = exits.head;

                    exits = exits.tail;

                    Assert.check(exit.tree.hasTag(RETURN));

                }

            } finally {

                lint = lintPrev;

            }

        }

        public void visitVarDef(JCVariableDecl tree) {

            if (tree.init != null) {

                Lint lintPrev = lint;

                lint = lint.augment(tree.sym.annotations);

                try{

                    scan(tree.init);

                } finally {

                    lint = lintPrev;

                }

            }

        }

        public void visitBlock(JCBlock tree) {

            scanStats(tree.stats);

        }

        public void visitDoLoop(JCDoWhileLoop tree) {

            ListBuffer<PendingExit> prevPendingExits = pendingExits;

            pendingExits = new ListBuffer<PendingExit>();

            scanStat(tree.body);

            alive |= resolveContinues(tree);

            scan(tree.cond);

            alive = alive && !tree.cond.type.isTrue();

            alive |= resolveBreaks(tree, prevPendingExits);

        }

        public void visitWhileLoop(JCWhileLoop tree) {

            ListBuffer<PendingExit> prevPendingExits = pendingExits;

            pendingExits = new ListBuffer<PendingExit>();

            scan(tree.cond);

            alive = !tree.cond.type.isFalse();

            scanStat(tree.body);

            alive |= resolveContinues(tree);

            alive = resolveBreaks(tree, prevPendingExits) ||

                !tree.cond.type.isTrue();

        }