/*

 * Copyright (c) 2010, 2013, 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.

 */

package jdk.nashorn.internal.codegen;

import static jdk.nashorn.internal.codegen.CompilerConstants.RETURN;

import static jdk.nashorn.internal.ir.Expression.isAlwaysFalse;

import static jdk.nashorn.internal.ir.Expression.isAlwaysTrue;

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Deque;

import java.util.HashSet;

import java.util.IdentityHashMap;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Set;

import jdk.nashorn.internal.codegen.types.Type;

import jdk.nashorn.internal.ir.AccessNode;

import jdk.nashorn.internal.ir.BinaryNode;

import jdk.nashorn.internal.ir.Block;

import jdk.nashorn.internal.ir.BreakNode;

import jdk.nashorn.internal.ir.BreakableNode;

import jdk.nashorn.internal.ir.CallNode;

import jdk.nashorn.internal.ir.CaseNode;

import jdk.nashorn.internal.ir.CatchNode;

import jdk.nashorn.internal.ir.ContinueNode;

import jdk.nashorn.internal.ir.Expression;

import jdk.nashorn.internal.ir.ExpressionStatement;

import jdk.nashorn.internal.ir.ForNode;

import jdk.nashorn.internal.ir.FunctionNode;

import jdk.nashorn.internal.ir.GetSplitState;

import jdk.nashorn.internal.ir.IdentNode;

import jdk.nashorn.internal.ir.IfNode;

import jdk.nashorn.internal.ir.IndexNode;

import jdk.nashorn.internal.ir.JoinPredecessor;

import jdk.nashorn.internal.ir.JoinPredecessorExpression;

import jdk.nashorn.internal.ir.JumpStatement;

import jdk.nashorn.internal.ir.JumpToInlinedFinally;

import jdk.nashorn.internal.ir.LabelNode;

import jdk.nashorn.internal.ir.LexicalContext;

import jdk.nashorn.internal.ir.LexicalContextNode;

import jdk.nashorn.internal.ir.LiteralNode;

import jdk.nashorn.internal.ir.LiteralNode.ArrayLiteralNode;

import jdk.nashorn.internal.ir.LocalVariableConversion;

import jdk.nashorn.internal.ir.LoopNode;

import jdk.nashorn.internal.ir.Node;

import jdk.nashorn.internal.ir.ObjectNode;

import jdk.nashorn.internal.ir.PropertyNode;

import jdk.nashorn.internal.ir.ReturnNode;

import jdk.nashorn.internal.ir.RuntimeNode;

import jdk.nashorn.internal.ir.RuntimeNode.Request;

import jdk.nashorn.internal.ir.SplitReturn;

import jdk.nashorn.internal.ir.Statement;

import jdk.nashorn.internal.ir.SwitchNode;

import jdk.nashorn.internal.ir.Symbol;

import jdk.nashorn.internal.ir.TernaryNode;

import jdk.nashorn.internal.ir.ThrowNode;

import jdk.nashorn.internal.ir.TryNode;

import jdk.nashorn.internal.ir.UnaryNode;

import jdk.nashorn.internal.ir.VarNode;

import jdk.nashorn.internal.ir.WhileNode;

import jdk.nashorn.internal.ir.WithNode;

import jdk.nashorn.internal.ir.visitor.NodeVisitor;

import jdk.nashorn.internal.parser.TokenType;

/**

 * Calculates types for local variables. For purposes of local variable type calculation, the only types used are

 * Undefined, boolean, int, long, double, and Object. The calculation eagerly widens types of local variable to their

 * widest at control flow join points.

 * TODO: investigate a more sophisticated solution that uses use/def information to only widens the type of a local

 * variable to its widest used type after the join point. That would eliminate some widenings of undefined variables to

 * object, most notably those used only in loops. We need a full liveness analysis for that. Currently, we can establish

 * per-type liveness, which eliminates most of unwanted dead widenings.

 * NOTE: the way this class is implemented, it actually processes the AST in two passes. The first pass is top-down and

 * implemented in {@code enterXxx} methods. This pass does not mutate the AST (except for one occurrence, noted below),

 * as being able to find relevant labels for control flow joins is sensitive to their reference identity, and mutated

 * label-carrying nodes will create copies of their labels. A second bottom-up pass applying the changes is implemented

 * in the separate visitor sitting in {@link #leaveFunctionNode(FunctionNode)}. This visitor will also instantiate new

 * instances of the calculator to be run on nested functions (when not lazy compiling).

 *

 */

final class LocalVariableTypesCalculator extends NodeVisitor<LexicalContext>{

    private static class JumpOrigin {

        final JoinPredecessor node;

        final Map<Symbol, LvarType> types;

        JumpOrigin(final JoinPredecessor node, final Map<Symbol, LvarType> types) {

            this.node = node;

            this.types = types;

        }

    }

    private static class JumpTarget {

        private final List<JumpOrigin> origins = new LinkedList<>();

        private Map<Symbol, LvarType> types = Collections.emptyMap();

        void addOrigin(final JoinPredecessor originNode, final Map<Symbol, LvarType> originTypes) {

            origins.add(new JumpOrigin(originNode, originTypes));

            this.types = getUnionTypes(this.types, originTypes);

        }

    }

    private enum LvarType {

        UNDEFINED(Type.UNDEFINED),

        BOOLEAN(Type.BOOLEAN),

        INT(Type.INT),

        LONG(Type.LONG),

        DOUBLE(Type.NUMBER),

        OBJECT(Type.OBJECT);

        private final Type type;

        private final TypeHolderExpression typeExpression;

        private LvarType(final Type type) {

            this.type = type;

            this.typeExpression = new TypeHolderExpression(type);

        }

    }

    /**

     * A bogus Expression subclass that only reports its type. Used to interrogate BinaryNode and UnaryNode about their

     * types by creating temporary copies of them and replacing their operands with instances of these. An alternative

     * solution would be to add BinaryNode.getType(Type lhsType, Type rhsType) and UnaryNode.getType(Type exprType)

     * methods. For the time being though, this is easier to implement and is in fact fairly clean. It does result in

     * generation of higher number of temporary short lived nodes, though.

     */

    private static class TypeHolderExpression extends Expression {

        private static final long serialVersionUID = 1L;

        private final Type type;

        TypeHolderExpression(final Type type) {

            super(0L, 0, 0);

            this.type = type;

        }

        @Override

        public Node accept(final NodeVisitor<? extends LexicalContext> visitor) {

            throw new AssertionError();

        }

        @Override

        public Type getType() {

            return type;

        }

        @Override

        public void toString(final StringBuilder sb, final boolean printType) {

            throw new AssertionError();

        }

    }

    private static final Map<Type, LvarType> TO_LVAR_TYPE = new IdentityHashMap<>();

    static {

        for(final LvarType lvarType: LvarType.values()) {

            TO_LVAR_TYPE.put(lvarType.type, lvarType);

        }

    }

    @SuppressWarnings("unchecked")

    private static IdentityHashMap<Symbol, LvarType> cloneMap(final Map<Symbol, LvarType> map) {

        return (IdentityHashMap<Symbol, LvarType>)((IdentityHashMap<?,?>)map).clone();

    }

    private LocalVariableConversion createConversion(final Symbol symbol, final LvarType branchLvarType,

            final Map<Symbol, LvarType> joinLvarTypes, final LocalVariableConversion next) {

        final LvarType targetType = joinLvarTypes.get(symbol);

        assert targetType != null;

        if(targetType == branchLvarType) {

            return next;

        }

        // NOTE: we could naively just use symbolIsUsed(symbol, branchLvarType) here, but that'd be wrong. While

        // technically a conversion will read the value of the symbol with that type, but it will also write it to a new

        // type, and that type might be dead (we can't know yet). For this reason, we don't treat conversion reads as

        // real uses until we know their target type is live. If we didn't do this, and just did a symbolIsUsed here,

        // we'd introduce false live variables which could nevertheless turn into dead ones in a subsequent

        // deoptimization, causing a shift in the list of live locals that'd cause erroneous restoration of

        // continuations (since RewriteException's byteCodeSlots carries an array and not a name-value map).

        symbolIsConverted(symbol, branchLvarType, targetType);

        return new LocalVariableConversion(symbol, branchLvarType.type, targetType.type, next);

    }

    private static Map<Symbol, LvarType> getUnionTypes(final Map<Symbol, LvarType> types1, final Map<Symbol, LvarType> types2) {

        if(types1 == types2 || types1.isEmpty()) {

            return types2;

        } else if(types2.isEmpty()) {

            return types1;

        }

        final Set<Symbol> commonSymbols = new HashSet<>(types1.keySet());

        commonSymbols.retainAll(types2.keySet());

        // We have a chance of returning an unmodified set if both sets have the same keys and one is strictly wider

        // than the other.

        final int commonSize = commonSymbols.size();

        final int types1Size = types1.size();

        final int types2Size = types2.size();

        if(commonSize == types1Size && commonSize == types2Size) {

            boolean matches1 = true, matches2 = true;

            Map<Symbol, LvarType> union = null;

            for(final Symbol symbol: commonSymbols) {

                final LvarType type1 = types1.get(symbol);

                final LvarType type2 = types2.get(symbol);

                final LvarType widest = widestLvarType(type1, type2);

                if(widest != type1 && matches1) {

                    matches1 = false;

                    if(!matches2) {

                        union = cloneMap(types1);

                    }

                }

                if (widest != type2 && matches2) {

                    matches2 = false;

                    if(!matches1) {

                        union = cloneMap(types2);

                    }

                }

                if(!(matches1 || matches2)) {

                    assert union != null;

                    union.put(symbol, widest);

                }

            }

            return matches1 ? types1 : matches2 ? types2 : union;

        }

        // General case

        final Map<Symbol, LvarType> union;

        if(types1Size > types2Size) {

            union = cloneMap(types1);

            union.putAll(types2);

        } else {

            union = cloneMap(types2);

            union.putAll(types1);

        }

        for(final Symbol symbol: commonSymbols) {

            final LvarType type1 = types1.get(symbol);

            final LvarType type2 = types2.get(symbol);

            union.put(symbol, widestLvarType(type1,  type2));

        }

        return union;

    }

    private static void symbolIsUsed(final Symbol symbol, final LvarType type) {

        if(type != LvarType.UNDEFINED) {

            symbol.setHasSlotFor(type.type);

        }

    }

    private static class SymbolConversions {

        private static final byte I2L = 1 << 0;

        private static final byte I2D = 1 << 1;

        private static final byte I2O = 1 << 2;

        private static final byte L2D = 1 << 3;

        private static final byte L2O = 1 << 4;

        private static final byte D2O = 1 << 5;

        private byte conversions;

        void recordConversion(final LvarType from, final LvarType to) {

            switch (from) {

            case UNDEFINED:

                return;

            case INT:

            case BOOLEAN:

                switch (to) {

                case LONG:

                    recordConversion(I2L);

                    return;

                case DOUBLE:

                    recordConversion(I2D);

                    return;

                case OBJECT:

                    recordConversion(I2O);

                    return;

                default:

                    illegalConversion(from, to);

                    return;

                }

            case LONG:

                switch (to) {

                case DOUBLE:

                    recordConversion(L2D);

                    return;

                case OBJECT:

                    recordConversion(L2O);

                    return;

                default:

                    illegalConversion(from, to);

                    return;

                }

            case DOUBLE:

                if(to == LvarType.OBJECT) {

                    recordConversion(D2O);

                }

                return;

            default:

                illegalConversion(from, to);

            }

        }

        private static void illegalConversion(final LvarType from, final LvarType to) {

            throw new AssertionError("Invalid conversion from " + from + " to " + to);

        }

        void recordConversion(final byte convFlag) {

            conversions = (byte)(conversions | convFlag);

        }

        boolean hasConversion(final byte convFlag) {

            return (conversions & convFlag) != 0;

        }

        void calculateTypeLiveness(final Symbol symbol) {

            if(symbol.hasSlotFor(Type.OBJECT)) {

                if(hasConversion(D2O)) {

                    symbol.setHasSlotFor(Type.NUMBER);

                }

                if(hasConversion(L2O)) {

                    symbol.setHasSlotFor(Type.LONG);

                }

                if(hasConversion(I2O)) {

                    symbol.setHasSlotFor(Type.INT);

                }

            }

            if(symbol.hasSlotFor(Type.NUMBER)) {

                if(hasConversion(L2D)) {

                    symbol.setHasSlotFor(Type.LONG);

                }

                if(hasConversion(I2D)) {

                    symbol.setHasSlotFor(Type.INT);

                }

            }

            if(symbol.hasSlotFor(Type.LONG)) {

                if(hasConversion(I2L)) {

                    symbol.setHasSlotFor(Type.INT);

                }

            }

        }

    }

    private void symbolIsConverted(final Symbol symbol, final LvarType from, final LvarType to) {

        SymbolConversions conversions = symbolConversions.get(symbol);

        if(conversions == null) {

            conversions = new SymbolConversions();

            symbolConversions.put(symbol, conversions);

        }

        conversions.recordConversion(from, to);

    }

    private static LvarType toLvarType(final Type type) {

        assert type != null;

        final LvarType lvarType = TO_LVAR_TYPE.get(type);

        if(lvarType != null) {

            return lvarType;

        }

        assert type.isObject();

        return LvarType.OBJECT;

    }

    private static LvarType widestLvarType(final LvarType t1, final LvarType t2) {

        if(t1 == t2) {

            return t1;

        }

        // Undefined or boolean to anything always widens to object.

        if(t1.ordinal() < LvarType.INT.ordinal() || t2.ordinal() < LvarType.INT.ordinal()) {

            return LvarType.OBJECT;

        }

        // NOTE: we allow "widening" of long to double even though it can lose precision. ECMAScript doesn't have an

        // Int64 type anyway, so this loss of precision is actually more conformant to the specification...

        return LvarType.values()[Math.max(t1.ordinal(), t2.ordinal())];

    }

    private final Compiler compiler;

    private final Map<Label, JumpTarget> jumpTargets = new IdentityHashMap<>();

    // Local variable type mapping at the currently evaluated point. No map instance is ever modified; setLvarType() always

    // allocates a new map. Immutability of maps allows for cheap snapshots by just keeping the reference to the current

    // value.

    private Map<Symbol, LvarType> localVariableTypes = new IdentityHashMap<>();

    // Stack for evaluated expression types.

    private final Deque<LvarType> typeStack = new ArrayDeque<>();

    // Whether the current point in the AST is reachable code

    private boolean reachable = true;

    // Return type of the function

    private Type returnType = Type.UNKNOWN;

    // Synthetic return node that we must insert at the end of the function if it's end is reachable.

    private ReturnNode syntheticReturn;

    private boolean alreadyEnteredTopLevelFunction;

    // LvarType and conversion information gathered during the top-down pass; applied to nodes in the bottom-up pass.

    private final Map<JoinPredecessor, LocalVariableConversion> localVariableConversions = new IdentityHashMap<>();

    private final Map<IdentNode, LvarType> identifierLvarTypes = new IdentityHashMap<>();

    private final Map<Symbol, SymbolConversions> symbolConversions = new IdentityHashMap<>();

    // Stack of open labels for starts of catch blocks, one for every currently traversed try block; for inserting

    // control flow edges to them. Note that we currently don't insert actual control flow edges, but instead edges that

    // help us with type calculations. This means that some operations that can result in an exception being thrown

    // aren't considered (function calls, side effecting property getters and setters etc.), while some operations that

    // don't result in control flow transfers do originate an edge to the catch blocks (namely, assignments to local

    // variables).

    private final Deque<Label> catchLabels = new ArrayDeque<>();

    LocalVariableTypesCalculator(final Compiler compiler) {

        super(new LexicalContext());

        this.compiler = compiler;

    }

    private JumpTarget createJumpTarget(final Label label) {

        assert !jumpTargets.containsKey(label);

        final JumpTarget jumpTarget = new JumpTarget();

        jumpTargets.put(label, jumpTarget);

        return jumpTarget;

    }

    private void doesNotContinueSequentially() {

        reachable = false;

        localVariableTypes = Collections.emptyMap();

        assertTypeStackIsEmpty();

    }

    private boolean pushExpressionType(final Expression expr) {

        typeStack.push(toLvarType(expr.getType()));

        return false;

    }

    @Override

    public boolean enterAccessNode(final AccessNode accessNode) {

        visitExpression(accessNode.getBase());

        return pushExpressionType(accessNode);

    }

    @Override

    public boolean enterBinaryNode(final BinaryNode binaryNode) {

        // NOTE: regardless of operator's lexical associativity, lhs is always evaluated first.

        final Expression lhs = binaryNode.lhs();

        final LvarType lhsType;

        if (!(lhs instanceof IdentNode && binaryNode.isTokenType(TokenType.ASSIGN))) {

            lhsType = visitExpression(lhs);

        } else {

            // Can't visit IdentNode on LHS of a simple assignment, as visits imply use, and this is def.

            // The type is irrelevant, as only RHS is used to determine the type anyway.

            lhsType = LvarType.UNDEFINED;

        }

        final boolean isLogical = binaryNode.isLogical();

        final Label joinLabel = isLogical ? new Label("") : null;

        if(isLogical) {

            jumpToLabel((JoinPredecessor)lhs, joinLabel);

        }

        final Expression rhs = binaryNode.rhs();

        final LvarType rhsType = visitExpression(rhs);

        if(isLogical) {

            jumpToLabel((JoinPredecessor)rhs, joinLabel);

        }

        joinOnLabel(joinLabel);

        final LvarType type = toLvarType(binaryNode.setOperands(lhsType.typeExpression, rhsType.typeExpression).getType());

        if(binaryNode.isAssignment() && lhs instanceof IdentNode) {

            if(binaryNode.isSelfModifying()) {

                onSelfAssignment((IdentNode)lhs, type);

            } else {

                onAssignment((IdentNode)lhs, type);

            }

        }

        typeStack.push(type);

        return false;

    }

    @Override

    public boolean enterBlock(final Block block) {

        for(final Symbol symbol: block.getSymbols()) {

            if(symbol.isBytecodeLocal() && getLocalVariableTypeOrNull(symbol) == null) {

                setType(symbol, LvarType.UNDEFINED);

            }

        }

        return true;

    }

    @Override

    public boolean enterBreakNode(final BreakNode breakNode) {

        return enterJumpStatement(breakNode);

    }

    @Override

    public boolean enterCallNode(final CallNode callNode) {

        visitExpression(callNode.getFunction());

        visitExpressions(callNode.getArgs());

        final CallNode.EvalArgs evalArgs = callNode.getEvalArgs();

        if (evalArgs != null) {