/*

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.Deque;

import java.util.HashSet;

import java.util.Iterator;

import java.util.List;

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

import jdk.nashorn.internal.ir.CaseNode;

import jdk.nashorn.internal.ir.CatchNode;

import jdk.nashorn.internal.ir.ForNode;

import jdk.nashorn.internal.ir.FunctionNode;

import jdk.nashorn.internal.ir.FunctionNode.CompilationState;

import jdk.nashorn.internal.ir.IdentNode;

import jdk.nashorn.internal.ir.IndexNode;

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

import jdk.nashorn.internal.ir.SwitchNode;

import jdk.nashorn.internal.ir.Symbol;

import jdk.nashorn.internal.ir.TemporarySymbols;

import jdk.nashorn.internal.ir.TernaryNode;

import jdk.nashorn.internal.ir.TryNode;

import jdk.nashorn.internal.ir.UnaryNode;

import jdk.nashorn.internal.ir.VarNode;

import jdk.nashorn.internal.ir.WithNode;

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

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

import jdk.nashorn.internal.parser.TokenType;

import jdk.nashorn.internal.runtime.Context;

import jdk.nashorn.internal.runtime.Debug;

import jdk.nashorn.internal.runtime.DebugLogger;

import jdk.nashorn.internal.runtime.JSType;

import jdk.nashorn.internal.runtime.Property;

import jdk.nashorn.internal.runtime.PropertyMap;

import jdk.nashorn.internal.runtime.ScriptObject;

/**

 * This is the attribution pass of the code generator. Attr takes Lowered IR,

 * that is, IR where control flow has been computed and high level to low level

 * substitions for operations have been performed.

 *

 * After Attr, every symbol will have a conservative correct type.

 *

 * Any expression that requires temporary storage as part of computation will

 * also be detected here and give a temporary symbol

 *

 * Types can be narrowed after Attr by Access Specialization in FinalizeTypes,

 * but in general, this is where the main symbol type information is

 * computed.

 */

final class Attr extends NodeOperatorVisitor<LexicalContext> {

    /**

     * Local definitions in current block (to discriminate from function

     * declarations always defined in the function scope. This is for

     * "can be undefined" analysis.

     */

    private final Deque<Set<String>> localDefs;

    /**

     * Local definitions in current block to guard against cases like

     * NASHORN-467 when things can be undefined as they are used before

     * their local var definition. *sigh* JavaScript...

     */

    private final Deque<Set<String>> localUses;

    private final Deque<Type> returnTypes;

    private int catchNestingLevel;

    private static final DebugLogger LOG   = new DebugLogger("attr");

    private static final boolean     DEBUG = LOG.isEnabled();

    private final TemporarySymbols temporarySymbols;

    /**

     * Constructor.

     */

    Attr(final TemporarySymbols temporarySymbols) {

        super(new LexicalContext());

        this.temporarySymbols = temporarySymbols;

        this.localDefs   = new ArrayDeque<>();

        this.localUses   = new ArrayDeque<>();

        this.returnTypes = new ArrayDeque<>();

    }

    @Override

    protected boolean enterDefault(final Node node) {

        return start(node);

    }

    @Override

    protected Node leaveDefault(final Node node) {

        return end(node);

    }

    @Override

    public Node leaveAccessNode(final AccessNode accessNode) {

        //While Object type is assigned here, Access Specialization in FinalizeTypes may narrow this, that

        //is why we can't set the access node base to be an object here, that will ruin access specialization

        //for example for a.x | 17.

        return end(ensureSymbol(Type.OBJECT, accessNode));

    }

    private void initFunctionWideVariables(final FunctionNode functionNode, final Block body) {

        initCompileConstant(CALLEE, body, IS_PARAM | IS_INTERNAL, FunctionNode.FUNCTION_TYPE);

        initCompileConstant(THIS, body, IS_PARAM | IS_THIS, Type.OBJECT);

        if (functionNode.isVarArg()) {

            initCompileConstant(VARARGS, body, IS_PARAM | IS_INTERNAL, Type.OBJECT_ARRAY);

            if (functionNode.needsArguments()) {

                initCompileConstant(ARGUMENTS, body, IS_VAR | IS_INTERNAL | IS_ALWAYS_DEFINED, Type.typeFor(ScriptObject.class));

                addLocalDef(ARGUMENTS.symbolName());

            }

        }

        initParameters(functionNode, body);

        initCompileConstant(SCOPE, body, IS_VAR | IS_INTERNAL | IS_ALWAYS_DEFINED, Type.typeFor(ScriptObject.class));

        initCompileConstant(RETURN, body, IS_VAR | IS_INTERNAL | IS_ALWAYS_DEFINED, Type.OBJECT);

    }

    /**

     * This pushes all declarations (except for non-statements, i.e. for

     * node temporaries) to the top of the function scope. This way we can

     * get around problems like

     *

     * while (true) {

     *   break;

     *   if (true) {

     *     var s;

     *   }

     * }

     *

     * to an arbitrary nesting depth.

     *

     * see NASHORN-73

     *

     * @param functionNode the FunctionNode we are entering

     * @param body the body of the FunctionNode we are entering

     */

    private void acceptDeclarations(final FunctionNode functionNode, final Block body) {

        // This visitor will assign symbol to all declared variables, except function declarations (which are taken care

        // in a separate step above) and "var" declarations in for loop initializers.

        //

        // It also handles the case that a variable can be undefined, e.g

        // if (cond) {

        //    x = x.y;

        // }

        // var x = 17;

        //

        // by making sure that no identifier has been found earlier in the body than the

        // declaration - if such is the case the identifier is flagged as caBeUndefined to

        // be safe if it turns into a local var. Otherwise corrupt bytecode results

        body.accept(new NodeVisitor<LexicalContext>(new LexicalContext()) {

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

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

            @Override

            public boolean enterFunctionNode(final FunctionNode nestedFn) {

                return false;

            }

            @Override

            public Node leaveIdentNode(final IdentNode identNode) {

                uses.add(identNode.getName());

                return identNode;

            }

            @Override

            public boolean enterVarNode(final VarNode varNode) {

                final String name = varNode.getName().getName();

                //if this is used before the var node, the var node symbol needs to be tagged as can be undefined

                if (uses.contains(name)) {

                    canBeUndefined.add(name);

                }

                // all uses of the declared varnode inside the var node are potentially undefined

                // however this is a bit conservative as e.g. var x = 17; var x = 1 + x; does work

                if (!varNode.isFunctionDeclaration() && varNode.getInit() != null) {

                    varNode.getInit().accept(new NodeVisitor<LexicalContext>(new LexicalContext()) {

                       @Override

                       public boolean enterIdentNode(final IdentNode identNode) {

                           if (name.equals(identNode.getName())) {

                              canBeUndefined.add(name);

                           }

                           return false;

                       }

                    });

                }

                return true;

            }

            @Override

            public Node leaveVarNode(final VarNode varNode) {

                // any declared symbols that aren't visited need to be typed as well, hence the list

                if (varNode.isStatement()) {

                    final IdentNode ident  = varNode.getName();

                    final Symbol    symbol = defineSymbol(body, ident.getName(), IS_VAR);

                    if (canBeUndefined.contains(ident.getName())) {

                        symbol.setType(Type.OBJECT);

                        symbol.setCanBeUndefined();

                    }

                    functionNode.addDeclaredSymbol(symbol);

                    if (varNode.isFunctionDeclaration()) {

                        newType(symbol, FunctionNode.FUNCTION_TYPE);

                    }

                    return varNode.setName((IdentNode)ident.setSymbol(lc, symbol));

                }

                return varNode;

            }

        });

    }

    private void enterFunctionBody() {

        final FunctionNode functionNode = lc.getCurrentFunction();

        final Block body = lc.getCurrentBlock();

        initFunctionWideVariables(functionNode, body);

        if (functionNode.isProgram()) {

            initFromPropertyMap(body);

        } else if (!functionNode.isDeclared()) {

            // It's neither declared nor program - it's a function expression then; assign it a self-symbol.

            assert functionNode.getSymbol() == null;

            final boolean anonymous = functionNode.isAnonymous();

            final String  name      = anonymous ? null : functionNode.getIdent().getName();

            if (!(anonymous || body.getExistingSymbol(name) != null)) {

                assert !anonymous && name != null;

                newType(defineSymbol(body, name, IS_VAR | IS_FUNCTION_SELF), Type.OBJECT);

            }

        }

        acceptDeclarations(functionNode, body);

    }

    @Override

    public boolean enterBlock(final Block block) {

        start(block);

        //ensure that we don't use information from a previous compile. This is very ugly TODO

        //the symbols in the block should really be stateless

        block.clearSymbols();

        if (lc.isFunctionBody()) {

            enterFunctionBody();

        }

        pushLocalsBlock();

        return true;

    }

    @Override

    public Node leaveBlock(final Block block) {

        popLocals();

        return end(block);

    }

    @Override

    public boolean enterCallNode(final CallNode callNode) {

        return start(callNode);

    }

    @Override

    public Node leaveCallNode(final CallNode callNode) {

        return end(ensureSymbol(callNode.getType(), callNode));

    }

    @Override

    public boolean enterCatchNode(final CatchNode catchNode) {

        final IdentNode exception = catchNode.getException();

        final Block     block     = lc.getCurrentBlock();

        start(catchNode);

        catchNestingLevel++;

        // define block-local exception variable

        final String exname = exception.getName();

        final Symbol def = defineSymbol(block, exname, IS_VAR | IS_LET | IS_ALWAYS_DEFINED);

        newType(def, Type.OBJECT); //we can catch anything, not just ecma exceptions

        addLocalDef(exname);

        return true;

    }

    @Override

    public Node leaveCatchNode(final CatchNode catchNode) {

        final IdentNode exception = catchNode.getException();

        final Block  block        = lc.getCurrentBlock();

        final Symbol symbol       = findSymbol(block, exception.getName());

        catchNestingLevel--;

        assert symbol != null;

        return end(catchNode.setException((IdentNode)exception.setSymbol(lc, symbol)));

    }

    /**

     * Declare the definition of a new symbol.

     *

     * @param name         Name of symbol.

     * @param symbolFlags  Symbol flags.

     *

     * @return Symbol for given name or null for redefinition.

     */

    private Symbol defineSymbol(final Block block, final String name, final int symbolFlags) {

        int    flags  = symbolFlags;

        Symbol symbol = findSymbol(block, name); // Locate symbol.

        if ((flags & KINDMASK) == IS_GLOBAL) {

            flags |= IS_SCOPE;

        }

        final FunctionNode function = lc.getFunction(block);

        if (symbol != null) {

            // Symbol was already defined. Check if it needs to be redefined.

            if ((flags & KINDMASK) == IS_PARAM) {

                if (!isLocal(function, symbol)) {

                    // Not defined in this function. Create a new definition.

                    symbol = null;

                } else if (symbol.isParam()) {

                    // Duplicate parameter. Null return will force an error.

                    assert false : "duplicate parameter";

                    return null;

                }

            } else if ((flags & KINDMASK) == IS_VAR) {

                if ((flags & IS_INTERNAL) == IS_INTERNAL || (flags & IS_LET) == IS_LET) {

                    // Always create a new definition.

                    symbol = null;

                } else {

                    // Not defined in this function. Create a new definition.

                    if (!isLocal(function, symbol) || symbol.less(IS_VAR)) {

                        symbol = null;

                    }

                }

            }

        }

        if (symbol == null) {

            // If not found, then create a new one.

            Block symbolBlock;

            // Determine where to create it.

            if ((flags & Symbol.KINDMASK) == IS_VAR && ((flags & IS_INTERNAL) == IS_INTERNAL || (flags & IS_LET) == IS_LET)) {

                symbolBlock = block; //internal vars are always defined in the block closest to them

            } else {

                symbolBlock = lc.getFunctionBody(function);

            }

            // Create and add to appropriate block.

            symbol = new Symbol(name, flags);

            symbolBlock.putSymbol(lc, symbol);

            if ((flags & Symbol.KINDMASK) != IS_GLOBAL) {

                symbol.setNeedsSlot(true);

            }

        } else if (symbol.less(flags)) {

            symbol.setFlags(flags);

        }

        return symbol;

    }

    @Override

    public boolean enterFunctionNode(final FunctionNode functionNode) {

        start(functionNode, false);

        if (functionNode.isLazy()) {

            return false;

        }

        //an outermost function in our lexical context that is not a program (runScript)

        //is possible - it is a function being compiled lazily

        if (functionNode.isDeclared()) {

            final Iterator<Block> blocks = lc.getBlocks();

            if (blocks.hasNext()) {

                defineSymbol(blocks.next(), functionNode.getIdent().getName(), IS_VAR);

            }

        }

        returnTypes.push(functionNode.getReturnType());

        pushLocalsFunction();

        return true;

    }

    @Override

    public Node leaveFunctionNode(final FunctionNode functionNode) {

        FunctionNode newFunctionNode = functionNode;

        final Block body = newFunctionNode.getBody();

        //look for this function in the parent block

        if (functionNode.isDeclared()) {

            final Iterator<Block> blocks = lc.getBlocks();

            if (blocks.hasNext()) {

                newFunctionNode = (FunctionNode)newFunctionNode.setSymbol(lc, findSymbol(blocks.next(), functionNode.getIdent().getName()));

            }

        } else if (!functionNode.isProgram()) {

            final boolean anonymous = functionNode.isAnonymous();

            final String  name      = anonymous ? null : functionNode.getIdent().getName();

            if (anonymous || body.getExistingSymbol(name) != null) {

                newFunctionNode = (FunctionNode)ensureSymbol(FunctionNode.FUNCTION_TYPE, newFunctionNode);

            } else {

                assert name != null;

                final Symbol self = body.getExistingSymbol(name);

                assert self != null && self.isFunctionSelf();

                newFunctionNode = (FunctionNode)newFunctionNode.setSymbol(lc, body.getExistingSymbol(name));

            }

        }

        //unknown parameters are promoted to object type.

        newFunctionNode = finalizeParameters(newFunctionNode);

        newFunctionNode = finalizeTypes(newFunctionNode);

        for (final Symbol symbol : newFunctionNode.getDeclaredSymbols()) {

            if (symbol.getSymbolType().isUnknown()) {

                symbol.setType(Type.OBJECT);

                symbol.setCanBeUndefined();

            }

        }

        if (newFunctionNode.hasLazyChildren()) {

            //the final body has already been assigned as we have left the function node block body by now

            objectifySymbols(body);

        }

        if (body.getFlag(Block.NEEDS_SELF_SYMBOL)) {