/*

 * Copyright (c) 2010, 2016, 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.ClassEmitter.Flag.PRIVATE;

import static jdk.nashorn.internal.codegen.ClassEmitter.Flag.STATIC;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

import static jdk.nashorn.internal.ir.Symbol.HAS_SLOT;

import static jdk.nashorn.internal.ir.Symbol.IS_INTERNAL;

import static jdk.nashorn.internal.runtime.UnwarrantedOptimismException.INVALID_PROGRAM_POINT;

import static jdk.nashorn.internal.runtime.UnwarrantedOptimismException.isValid;

import static jdk.nashorn.internal.runtime.linker.NashornCallSiteDescriptor.CALLSITE_APPLY_TO_CALL;

import static jdk.nashorn.internal.runtime.linker.NashornCallSiteDescriptor.CALLSITE_DECLARE;

import static jdk.nashorn.internal.runtime.linker.NashornCallSiteDescriptor.CALLSITE_FAST_SCOPE;

import static jdk.nashorn.internal.runtime.linker.NashornCallSiteDescriptor.CALLSITE_OPTIMISTIC;

import static jdk.nashorn.internal.runtime.linker.NashornCallSiteDescriptor.CALLSITE_PROGRAM_POINT_SHIFT;

import static jdk.nashorn.internal.runtime.linker.NashornCallSiteDescriptor.CALLSITE_SCOPE;

import java.io.PrintWriter;

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.BitSet;

import java.util.Collection;

import java.util.Collections;

import java.util.Deque;

import java.util.EnumSet;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Set;

import java.util.TreeMap;

import java.util.function.Supplier;

import jdk.nashorn.internal.AssertsEnabled;

import jdk.nashorn.internal.IntDeque;

import jdk.nashorn.internal.codegen.ClassEmitter.Flag;

import jdk.nashorn.internal.codegen.CompilerConstants.Call;

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

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

import jdk.nashorn.internal.ir.AccessNode;

import jdk.nashorn.internal.ir.BaseNode;

import jdk.nashorn.internal.ir.BinaryNode;

import jdk.nashorn.internal.ir.Block;

import jdk.nashorn.internal.ir.BlockStatement;

import jdk.nashorn.internal.ir.BreakNode;

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.EmptyNode;

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.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.LiteralNode.PrimitiveLiteralNode;

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.Optimistic;

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.SetSplitState;

import jdk.nashorn.internal.ir.SplitReturn;

import jdk.nashorn.internal.ir.Splittable;

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.NodeOperatorVisitor;

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

import jdk.nashorn.internal.objects.Global;

import jdk.nashorn.internal.parser.Lexer.RegexToken;

import jdk.nashorn.internal.parser.TokenType;

import jdk.nashorn.internal.runtime.Context;

import jdk.nashorn.internal.runtime.Debug;

import jdk.nashorn.internal.runtime.ECMAException;

import jdk.nashorn.internal.runtime.JSType;

import jdk.nashorn.internal.runtime.OptimisticReturnFilters;

import jdk.nashorn.internal.runtime.PropertyMap;

import jdk.nashorn.internal.runtime.RecompilableScriptFunctionData;

import jdk.nashorn.internal.runtime.RewriteException;

import jdk.nashorn.internal.runtime.Scope;

import jdk.nashorn.internal.runtime.ScriptEnvironment;

import jdk.nashorn.internal.runtime.ScriptFunction;

import jdk.nashorn.internal.runtime.ScriptObject;

import jdk.nashorn.internal.runtime.ScriptRuntime;

import jdk.nashorn.internal.runtime.Source;

import jdk.nashorn.internal.runtime.Undefined;

import jdk.nashorn.internal.runtime.UnwarrantedOptimismException;

import jdk.nashorn.internal.runtime.arrays.ArrayData;

import jdk.nashorn.internal.runtime.linker.LinkerCallSite;

import jdk.nashorn.internal.runtime.logging.DebugLogger;

import jdk.nashorn.internal.runtime.logging.Loggable;

import jdk.nashorn.internal.runtime.logging.Logger;

import jdk.nashorn.internal.runtime.options.Options;

/**

 * This is the lowest tier of the code generator. It takes lowered ASTs emitted

 * from Lower and emits Java byte code. The byte code emission logic is broken

 * out into MethodEmitter. MethodEmitter works internally with a type stack, and

 * keeps track of the contents of the byte code stack. This way we avoid a large

 * number of special cases on the form

 * <pre>

 * if (type == INT) {

 *     visitInsn(ILOAD, slot);

 * } else if (type == DOUBLE) {

 *     visitInsn(DOUBLE, slot);

 * }

 * </pre>

 * This quickly became apparent when the code generator was generalized to work

 * with all types, and not just numbers or objects.

 * <p>

 * The CodeGenerator visits nodes only once and emits bytecode for them.

 */

@Logger(name="codegen")

final class CodeGenerator extends NodeOperatorVisitor<CodeGeneratorLexicalContext> implements Loggable {

    private static final Type SCOPE_TYPE = Type.typeFor(ScriptObject.class);

    private static final String GLOBAL_OBJECT = Type.getInternalName(Global.class);

    private static final Call CREATE_REWRITE_EXCEPTION = CompilerConstants.staticCallNoLookup(RewriteException.class,

            "create", RewriteException.class, UnwarrantedOptimismException.class, Object[].class, String[].class);

    private static final Call CREATE_REWRITE_EXCEPTION_REST_OF = CompilerConstants.staticCallNoLookup(RewriteException.class,

            "create", RewriteException.class, UnwarrantedOptimismException.class, Object[].class, String[].class, int[].class);

    private static final Call ENSURE_INT = CompilerConstants.staticCallNoLookup(OptimisticReturnFilters.class,

            "ensureInt", int.class, Object.class, int.class);

    private static final Call ENSURE_NUMBER = CompilerConstants.staticCallNoLookup(OptimisticReturnFilters.class,

            "ensureNumber", double.class, Object.class, int.class);

    private static final Call CREATE_FUNCTION_OBJECT = CompilerConstants.staticCallNoLookup(ScriptFunction.class,

            "create", ScriptFunction.class, Object[].class, int.class, ScriptObject.class);

    private static final Call CREATE_FUNCTION_OBJECT_NO_SCOPE = CompilerConstants.staticCallNoLookup(ScriptFunction.class,

            "create", ScriptFunction.class, Object[].class, int.class);

    private static final Call TO_NUMBER_FOR_EQ = CompilerConstants.staticCallNoLookup(JSType.class,

            "toNumberForEq", double.class, Object.class);

    private static final Call TO_NUMBER_FOR_STRICT_EQ = CompilerConstants.staticCallNoLookup(JSType.class,

            "toNumberForStrictEq", double.class, Object.class);

    private static final Class<?> ITERATOR_CLASS = Iterator.class;

    static {

        assert ITERATOR_CLASS == CompilerConstants.ITERATOR_PREFIX.type();

    }

    private static final Type ITERATOR_TYPE = Type.typeFor(ITERATOR_CLASS);

    private static final Type EXCEPTION_TYPE = Type.typeFor(CompilerConstants.EXCEPTION_PREFIX.type());

    private static final Integer INT_ZERO = 0;

    /** Constant data & installation. The only reason the compiler keeps this is because it is assigned

     *  by reflection in class installation */

    private final Compiler compiler;

    /** Is the current code submitted by 'eval' call? */

    private final boolean evalCode;

    /** Call site flags given to the code generator to be used for all generated call sites */

    private final int callSiteFlags;

    /** How many regexp fields have been emitted */

    private int regexFieldCount;

    /** Line number for last statement. If we encounter a new line number, line number bytecode information

     *  needs to be generated */

    private int lastLineNumber = -1;

    /** When should we stop caching regexp expressions in fields to limit bytecode size? */

    private static final int MAX_REGEX_FIELDS = 2 * 1024;

    /** Current method emitter */

    private MethodEmitter method;

    /** Current compile unit */

    private CompileUnit unit;

    private final DebugLogger log;

    /** From what size should we use spill instead of fields for JavaScript objects? */

    static final int OBJECT_SPILL_THRESHOLD = Options.getIntProperty("nashorn.spill.threshold", 256);

    private final Set<String> emittedMethods = new HashSet<>();

    // Function Id -> ContinuationInfo. Used by compilation of rest-of function only.

    private ContinuationInfo continuationInfo;

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

    private static final Label METHOD_BOUNDARY = new Label("");

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

    // Number of live locals on entry to (and thus also break from) labeled blocks.

    private final IntDeque labeledBlockBreakLiveLocals = new IntDeque();

    //is this a rest of compilation

    private final int[] continuationEntryPoints;

    // Scope object creators needed for for-of and for-in loops

    private final Deque<FieldObjectCreator<?>> scopeObjectCreators = new ArrayDeque<>();

    /**

     * Constructor.

     *

     * @param compiler

     */

    CodeGenerator(final Compiler compiler, final int[] continuationEntryPoints) {

        super(new CodeGeneratorLexicalContext());

        this.compiler                = compiler;

        this.evalCode                = compiler.getSource().isEvalCode();

        this.continuationEntryPoints = continuationEntryPoints;

        this.callSiteFlags           = compiler.getScriptEnvironment()._callsite_flags;

        this.log                     = initLogger(compiler.getContext());

    }

    @Override

    public DebugLogger getLogger() {

        return log;

    }

    @Override

    public DebugLogger initLogger(final Context context) {

        return context.getLogger(this.getClass());

    }

    /**

     * Gets the call site flags, adding the strict flag if the current function

     * being generated is in strict mode

     *

     * @return the correct flags for a call site in the current function

     */

    int getCallSiteFlags() {

        return lc.getCurrentFunction().getCallSiteFlags() | callSiteFlags;

    }

    /**

     * Gets the flags for a scope call site.

     * @param symbol a scope symbol

     * @return the correct flags for the scope call site

     */

    private int getScopeCallSiteFlags(final Symbol symbol) {

        assert symbol.isScope();

        final int flags = getCallSiteFlags() | CALLSITE_SCOPE;

        if (isEvalCode() && symbol.isGlobal()) {

            return flags; // Don't set fast-scope flag on non-declared globals in eval code - see JDK-8077955.

        }

        return isFastScope(symbol) ? flags | CALLSITE_FAST_SCOPE : flags;

    }

    /**

     * Are we generating code for 'eval' code?

     * @return true if currently compiled code is 'eval' code.

     */

    boolean isEvalCode() {

        return evalCode;

    }

    /**

     * Are we using dual primitive/object field representation?

     * @return true if using dual field representation, false for object-only fields

     */

    boolean useDualFields() {

        return compiler.getContext().useDualFields();

    }

    /**

     * Load an identity node

     *

     * @param identNode an identity node to load

     * @return the method generator used

     */

    private MethodEmitter loadIdent(final IdentNode identNode, final TypeBounds resultBounds) {

        checkTemporalDeadZone(identNode);

        final Symbol symbol = identNode.getSymbol();

        if (!symbol.isScope()) {

            final Type type = identNode.getType();

            if(type == Type.UNDEFINED) {

                return method.loadUndefined(resultBounds.widest);

            }

            assert symbol.hasSlot() || symbol.isParam();

            return method.load(identNode);

        }

        assert identNode.getSymbol().isScope() : identNode + " is not in scope!";

        final int flags = getScopeCallSiteFlags(symbol);

        if (!isFastScope(symbol)) {

            // slow scope load, prototype chain must be inspected at runtime

            new LoadScopeVar(identNode, resultBounds, flags).emit();

        } else if (identNode.isCompileTimePropertyName() || symbol.getUseCount() < SharedScopeCall.SHARED_GET_THRESHOLD) {

            // fast scope load with known prototype depth

            new LoadFastScopeVar(identNode, resultBounds, flags).emit();

        } else {

            // Only generate shared scope getter for often used fast-scope symbols.

            new OptimisticOperation(identNode, resultBounds) {

                @Override

                void loadStack() {

                    method.loadCompilerConstant(SCOPE);

                    final int depth = getScopeProtoDepth(lc.getCurrentBlock(), symbol);

                    assert depth >= 0;

                    method.load(depth);

                    method.load(getProgramPoint());

                }

                @Override

                void consumeStack() {

                    final Type resultType = isOptimistic ? getOptimisticCoercedType() : resultBounds.widest;

                    lc.getScopeGet(unit, symbol, resultType, flags, isOptimistic).generateInvoke(method);

                }

            }.emit();

        }

        return method;

    }

    // Any access to LET and CONST variables before their declaration must throw ReferenceError.

    // This is called the temporal dead zone (TDZ). See https://gist.github.com/rwaldron/f0807a758aa03bcdd58a

    private void checkTemporalDeadZone(final IdentNode identNode) {

        if (identNode.isDead()) {

            method.load(identNode.getSymbol().getName()).invoke(ScriptRuntime.THROW_REFERENCE_ERROR);

        }

    }

    // Runtime check for assignment to ES6 const

    private void checkAssignTarget(final Expression expression) {

        if (expression instanceof IdentNode && ((IdentNode)expression).getSymbol().isConst()) {

            method.load(((IdentNode)expression).getSymbol().getName()).invoke(ScriptRuntime.THROW_CONST_TYPE_ERROR);

        }

    }

    private boolean isRestOf() {

        return continuationEntryPoints != null;

    }

    private boolean isCurrentContinuationEntryPoint(final int programPoint) {

        return isRestOf() && getCurrentContinuationEntryPoint() == programPoint;

    }

    private int[] getContinuationEntryPoints() {

        return isRestOf() ? continuationEntryPoints : null;

    }

    private int getCurrentContinuationEntryPoint() {

        return isRestOf() ? continuationEntryPoints[0] : INVALID_PROGRAM_POINT;

    }

    private boolean isContinuationEntryPoint(final int programPoint) {

        if (isRestOf()) {

            assert continuationEntryPoints != null;

            for (final int cep : continuationEntryPoints) {

                if (cep == programPoint) {

                    return true;

                }

            }

        }

        return false;

    }

    /**

     * Check if this symbol can be accessed directly with a putfield or getfield or dynamic load

     *

     * @param symbol symbol to check for fast scope

     * @return true if fast scope

     */

    private boolean isFastScope(final Symbol symbol) {

        if (!symbol.isScope()) {

            return false;

        }

        if (!lc.inDynamicScope()) {

            // If there's no with or eval in context, and the symbol is marked as scoped, it is fast scoped. Such a

            // symbol must either be global, or its defining block must need scope.

            assert symbol.isGlobal() || lc.getDefiningBlock(symbol).needsScope() : symbol.getName();

            return true;

        }

        if (symbol.isGlobal()) {

            // Shortcut: if there's a with or eval in context, globals can't be fast scoped

            return false;

        }

        // Otherwise, check if there's a dynamic scope between use of the symbol and its definition

        final String name = symbol.getName();

        boolean previousWasBlock = false;

        for (final Iterator<LexicalContextNode> it = lc.getAllNodes(); it.hasNext();) {

            final LexicalContextNode node = it.next();

            if (node instanceof Block) {

                // If this block defines the symbol, then we can fast scope the symbol.

                final Block block = (Block)node;

                if (block.getExistingSymbol(name) == symbol) {

                    assert block.needsScope();

                    return true;

                }

                previousWasBlock = true;

            } else {

                if (node instanceof WithNode && previousWasBlock || node instanceof FunctionNode && ((FunctionNode)node).needsDynamicScope()) {

                    // If we hit a scope that can have symbols introduced into it at run time before finding the defining

                    // block, the symbol can't be fast scoped. A WithNode only counts if we've immediately seen a block

                    // before - its block. Otherwise, we are currently processing the WithNode's expression, and that's

                    // obviously not subjected to introducing new symbols.

                    return false;

                }

                previousWasBlock = false;

            }

        }

        // Should've found the symbol defined in a block

        throw new AssertionError();

    }

    private class LoadScopeVar extends OptimisticOperation {

        final IdentNode identNode;

        private final int flags;

        LoadScopeVar(final IdentNode identNode, final TypeBounds resultBounds, final int flags) {

            super(identNode, resultBounds);

            this.identNode = identNode;

            this.flags = flags;

        }

        @Override

        void loadStack() {

            method.loadCompilerConstant(SCOPE);

            getProto();

        }

        void getProto() {

            //empty

        }

        @Override

        void consumeStack() {