/*

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

 *  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 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 Env<AttrContext> attrEnv;

    private       Lint lint;

    private final boolean allowImprovedRethrowAnalysis;

    private final boolean allowImprovedCatchAnalysis;

    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 FlowAnalyzer().analyzeTree(env, make);

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

    }

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

        Source source = Source.instance(context);

        allowImprovedRethrowAnalysis = source.allowImprovedRethrowAnalysis();

        allowImprovedCatchAnalysis = source.allowImprovedCatchAnalysis();

    }

    /**

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

         */

        abstract static class PendingExit {

            JCTree tree;

            PendingExit(JCTree tree) {

                this.tree = tree;

            }

            abstract void resolveJump();

        }

        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 two steps of the dataflow analysis:

     * (i) liveness analysis checks that every statement is reachable and (ii)

     *  exception analysis to ensure that every checked exception that is

     *  thrown is declared or caught.

     */

    class FlowAnalyzer extends BaseAnalyzer<FlowAnalyzer.FlowPendingExit> {

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

         *  complete normally.

         */

        private boolean alive;

        HashMap<Symbol, List<Type>> preciseRethrowTypes;

        /** The current class being defined.

         */

        JCClassDecl classDef;

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

        class FlowPendingExit extends BaseAnalyzer.PendingExit {

            Type thrown;

            FlowPendingExit(JCTree tree, Type thrown) {

                super(tree);

                this.thrown = thrown;

            }

            void resolveJump() { /*do nothing*/ }

        }

        @Override

        void markDead() {

            alive = false;

        }

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

        /** Complain that pending exceptions are not caught.

         */

        void errorUncaught() {

            for (FlowPendingExit exit = pendingExits.next();

                 exit != null;

                 exit = pendingExits.next()) {

                if (classDef != null &&

                    classDef.pos == exit.tree.pos) {

                    log.error(exit.tree.pos(),

                            "unreported.exception.default.constructor",

                            exit.thrown);

                } else if (exit.tree.hasTag(VARDEF) &&

                        ((JCVariableDecl)exit.tree).sym.isResourceVariable()) {

                    log.error(exit.tree.pos(),

                            "unreported.exception.implicit.close",

                            exit.thrown,

                            ((JCVariableDecl)exit.tree).sym.name);

                } else {

                    log.error(exit.tree.pos(),

                            "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 FlowPendingExit(tree, exc));

                    thrown = chk.incl(exc, thrown);

            }

        }

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

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

            JCClassDecl classDefPrev = classDef;

            List<Type> thrownPrev = thrown;

            List<Type> caughtPrev = caught;

            boolean alivePrev = alive;

            ListBuffer<FlowPendingExit> pendingExitsPrev = pendingExits;

            Lint lintPrev = lint;

            pendingExits = new ListBuffer<FlowPendingExit>();

            if (tree.name != names.empty) {

                caught = List.nil();

            }

            classDef = tree;

            thrown = List.nil();

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

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

                        errorUncaught();

                    }

                }

                // add intersection of all thrown clauses of initial constructors

                // to set of caught exceptions, unless class is anonymous.

                if (tree.name != names.empty) {

                    boolean firstConstructor = true;

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

                        if (TreeInfo.isInitialConstructor(l.head)) {

                            List<Type> mthrown =

                                ((JCMethodDecl) l.head).sym.type.getThrownTypes();

                            if (firstConstructor) {

                                caught = mthrown;

                                firstConstructor = false;

                            } else {

                                caught = chk.intersect(mthrown, caught);

                            }

                        }

                    }

                }

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

                        errorUncaught();

                    }

                }

                // in an anonymous class, add the set of thrown exceptions to

                // the throws clause of the synthetic constructor and propagate

                // outwards.

                // Changing the throws clause on the fly is okay here because

                // the anonymous constructor can't be invoked anywhere else,

                // and its type hasn't been cached.

                if (tree.name == names.empty) {

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

                        if (TreeInfo.isInitialConstructor(l.head)) {

                            JCMethodDecl mdef = (JCMethodDecl)l.head;

                            mdef.thrown = make.Types(thrown);

                            mdef.sym.type = types.createMethodTypeWithThrown(mdef.sym.type, thrown);

                        }

                    }

                    thrownPrev = chk.union(thrown, thrownPrev);

                }

                // process all the methods

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

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

                        scan(l.head);

                        errorUncaught();