/*

*  Copyright (C) 1999-2002 Harri Porten (porten@kde.org)

*  Copyright (C) 2001 Peter Kelly (pmk@post.com)

*  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.

*  Copyright (C) 2007 Cameron Zwarich (cwzwarich@uwaterloo.ca)

*  Copyright (C) 2007 Maks Orlovich

*  Copyright (C) 2007 Eric Seidel <eric@webkit.org>

*

*  This library is free software; you can redistribute it and/or

*  modify it under the terms of the GNU Library General Public

*  License as published by the Free Software Foundation; either

*  version 2 of the License, or (at your option) any later version.

*

*  This library 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

*  Library General Public License for more details.

*

*  You should have received a copy of the GNU Library General Public License

*  along with this library; see the file COPYING.LIB.  If not, write to

*  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

*  Boston, MA 02110-1301, USA.

*

*/

#include "config.h"

#include "Nodes.h"

#include "NodeConstructors.h"

#include "BytecodeGenerator.h"

#include "CallFrame.h"

#include "Debugger.h"

#include "JIT.h"

#include "JSFunction.h"

#include "JSGlobalObject.h"

#include "JSStaticScopeObject.h"

#include "LabelScope.h"

#include "Lexer.h"

#include "Operations.h"

#include "Parser.h"

#include "PropertyNameArray.h"

#include "RegExpCache.h"

#include "RegExpObject.h"

#include "SamplingTool.h"

#include <wtf/Assertions.h>

#include <wtf/RefCountedLeakCounter.h>

#include <wtf/Threading.h>

using namespace WTF;

namespace JSC {

/*

    Details of the emitBytecode function.

    Return value: The register holding the production's value.

             dst: An optional parameter specifying the most efficient destination at

                  which to store the production's value. The callee must honor dst.

    The dst argument provides for a crude form of copy propagation. For example,

        x = 1

    becomes

        load r[x], 1

    instead of 

        load r0, 1

        mov r[x], r0

    because the assignment node, "x =", passes r[x] as dst to the number node, "1".

*/

// ------------------------------ ThrowableExpressionData --------------------------------

static void substitute(UString& string, const UString& substring)

{

    unsigned position = string.find("%s");

    ASSERT(position != UString::NotFound);

    string = makeString(string.substr(0, position), substring, string.substr(position + 2));

}

RegisterID* ThrowableExpressionData::emitThrowError(BytecodeGenerator& generator, bool isReferenceError, const char* message)

{

    generator.emitExpressionInfo(divot(), startOffset(), endOffset());

    RegisterID* exception = generator.emitNewError(generator.newTemporary(), isReferenceError, jsString(generator.globalData(), message));

    generator.emitThrow(exception);

    return exception;

}

RegisterID* ThrowableExpressionData::emitThrowError(BytecodeGenerator& generator, bool isReferenceError, const char* messageTemplate, const UString& label)

{

    UString message = messageTemplate;

    substitute(message, label);

    generator.emitExpressionInfo(divot(), startOffset(), endOffset());

    RegisterID* exception = generator.emitNewError(generator.newTemporary(), isReferenceError, jsString(generator.globalData(), message));

    generator.emitThrow(exception);

    return exception;

}

inline RegisterID* ThrowableExpressionData::emitThrowError(BytecodeGenerator& generator, bool isReferenceError, const char* messageTemplate, const Identifier& label)

{

    return emitThrowError(generator, isReferenceError, messageTemplate, label.ustring());

}

// ------------------------------ NullNode -------------------------------------

RegisterID* NullNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    if (dst == generator.ignoredResult())

        return 0;

    return generator.emitLoad(dst, jsNull());

}

// ------------------------------ BooleanNode ----------------------------------

RegisterID* BooleanNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    if (dst == generator.ignoredResult())

        return 0;

    return generator.emitLoad(dst, m_value);

}

// ------------------------------ NumberNode -----------------------------------

RegisterID* NumberNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    if (dst == generator.ignoredResult())

        return 0;

    return generator.emitLoad(dst, m_value);

}

// ------------------------------ StringNode -----------------------------------

RegisterID* StringNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    if (dst == generator.ignoredResult())

        return 0;

    return generator.emitLoad(dst, m_value);

}

// ------------------------------ RegExpNode -----------------------------------

RegisterID* RegExpNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    RefPtr<RegExp> regExp = generator.globalData()->regExpCache()->lookupOrCreate(m_pattern.ustring(), m_flags.ustring());

    if (!regExp->isValid())

        return emitThrowError(generator, false, "Invalid regular expression: %s", regExp->errorMessage());

    if (dst == generator.ignoredResult())

        return 0;

    return generator.emitNewRegExp(generator.finalDestination(dst), regExp.get());

}

// ------------------------------ ThisNode -------------------------------------

RegisterID* ThisNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    if (dst == generator.ignoredResult())

        return 0;

    return generator.moveToDestinationIfNeeded(dst, generator.thisRegister());

}

// ------------------------------ ResolveNode ----------------------------------

bool ResolveNode::isPure(BytecodeGenerator& generator) const

{

    return generator.isLocal(m_ident);

}

RegisterID* ResolveNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    if (RegisterID* local = generator.registerFor(m_ident)) {

        if (dst == generator.ignoredResult())

            return 0;

        return generator.moveToDestinationIfNeeded(dst, local);

    }

    generator.emitExpressionInfo(m_startOffset + m_ident.size(), m_ident.size(), 0);

    return generator.emitResolve(generator.finalDestination(dst), m_ident);

}

// ------------------------------ ArrayNode ------------------------------------

RegisterID* ArrayNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    // FIXME: Should we put all of this code into emitNewArray?

    unsigned length = 0;

    ElementNode* firstPutElement;

    for (firstPutElement = m_element; firstPutElement; firstPutElement = firstPutElement->next()) {

        if (firstPutElement->elision())

            break;

        ++length;

    }

    if (!firstPutElement && !m_elision)

        return generator.emitNewArray(generator.finalDestination(dst), m_element);

    RefPtr<RegisterID> array = generator.emitNewArray(generator.tempDestination(dst), m_element);

    for (ElementNode* n = firstPutElement; n; n = n->next()) {

        RegisterID* value = generator.emitNode(n->value());

        length += n->elision();

        generator.emitPutByIndex(array.get(), length++, value);

    }

    if (m_elision) {

        RegisterID* value = generator.emitLoad(0, jsNumber(generator.globalData(), m_elision + length));

        generator.emitPutById(array.get(), generator.propertyNames().length, value);

    }

    return generator.moveToDestinationIfNeeded(dst, array.get());

}

bool ArrayNode::isSimpleArray() const

{

    if (m_elision || m_optional)

        return false;

    for (ElementNode* ptr = m_element; ptr; ptr = ptr->next()) {

        if (ptr->elision())

            return false;

    }

    return true;

}

ArgumentListNode* ArrayNode::toArgumentList(JSGlobalData* globalData) const

{

    ASSERT(!m_elision && !m_optional);

    ElementNode* ptr = m_element;

    if (!ptr)

        return 0;

    ArgumentListNode* head = new (globalData) ArgumentListNode(globalData, ptr->value());

    ArgumentListNode* tail = head;

    ptr = ptr->next();

    for (; ptr; ptr = ptr->next()) {

        ASSERT(!ptr->elision());

        tail = new (globalData) ArgumentListNode(globalData, tail, ptr->value());

    }

    return head;

}

// ------------------------------ ObjectLiteralNode ----------------------------

RegisterID* ObjectLiteralNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

     if (!m_list) {

         if (dst == generator.ignoredResult())

             return 0;

         return generator.emitNewObject(generator.finalDestination(dst));

     }

     return generator.emitNode(dst, m_list);

}

// ------------------------------ PropertyListNode -----------------------------

RegisterID* PropertyListNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    RefPtr<RegisterID> newObj = generator.tempDestination(dst);

    generator.emitNewObject(newObj.get());

    for (PropertyListNode* p = this; p; p = p->m_next) {

        RegisterID* value = generator.emitNode(p->m_node->m_assign);

        switch (p->m_node->m_type) {

            case PropertyNode::Constant: {

                generator.emitDirectPutById(newObj.get(), p->m_node->name(), value);

                break;

            }

            case PropertyNode::Getter: {

                generator.emitPutGetter(newObj.get(), p->m_node->name(), value);

                break;

            }

            case PropertyNode::Setter: {

                generator.emitPutSetter(newObj.get(), p->m_node->name(), value);

                break;

            }

            default:

                ASSERT_NOT_REACHED();

        }

    }

    return generator.moveToDestinationIfNeeded(dst, newObj.get());

}

// ------------------------------ BracketAccessorNode --------------------------------

RegisterID* BracketAccessorNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    RefPtr<RegisterID> base = generator.emitNodeForLeftHandSide(m_base, m_subscriptHasAssignments, m_subscript->isPure(generator));

    RegisterID* property = generator.emitNode(m_subscript);

    generator.emitExpressionInfo(divot(), startOffset(), endOffset());

    return generator.emitGetByVal(generator.finalDestination(dst), base.get(), property);

}

// ------------------------------ DotAccessorNode --------------------------------

RegisterID* DotAccessorNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    RegisterID* base = generator.emitNode(m_base);

    generator.emitExpressionInfo(divot(), startOffset(), endOffset());

    return generator.emitGetById(generator.finalDestination(dst), base, m_ident);

}

// ------------------------------ ArgumentListNode -----------------------------

RegisterID* ArgumentListNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    ASSERT(m_expr);

    return generator.emitNode(dst, m_expr);

}

// ------------------------------ NewExprNode ----------------------------------

RegisterID* NewExprNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    RefPtr<RegisterID> func = generator.emitNode(m_expr);

    CallArguments callArguments(generator, m_args);

    return generator.emitConstruct(generator.finalDestinationOrIgnored(dst), func.get(), callArguments, divot(), startOffset(), endOffset());

}

CallArguments::CallArguments(BytecodeGenerator& generator, ArgumentsNode* argumentsNode)

    : m_argumentsNode(argumentsNode)

{

    if (generator.shouldEmitProfileHooks())

        m_profileHookRegister = generator.newTemporary();

    m_argv.append(generator.newTemporary());

    if (argumentsNode) {

        for (ArgumentListNode* n = argumentsNode->m_listNode; n; n = n->m_next) {

            m_argv.append(generator.newTemporary());

            // op_call requires the arguments to be a sequential range of registers

            ASSERT(m_argv[m_argv.size() - 1]->index() == m_argv[m_argv.size() - 2]->index() + 1);

        }

    }

}

// ------------------------------ EvalFunctionCallNode ----------------------------------

RegisterID* EvalFunctionCallNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    RefPtr<RegisterID> func = generator.tempDestination(dst);

    CallArguments callArguments(generator, m_args);

    generator.emitExpressionInfo(divot() - startOffset() + 4, 4, 0);

    generator.emitResolveWithBase(callArguments.thisRegister(), func.get(), generator.propertyNames().eval);

    return generator.emitCallEval(generator.finalDestination(dst, func.get()), func.get(), callArguments, divot(), startOffset(), endOffset());

}

// ------------------------------ FunctionCallValueNode ----------------------------------

RegisterID* FunctionCallValueNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    RefPtr<RegisterID> func = generator.emitNode(m_expr);

    CallArguments callArguments(generator, m_args);

    generator.emitLoad(callArguments.thisRegister(), jsNull());

    return generator.emitCall(generator.finalDestinationOrIgnored(dst, func.get()), func.get(), callArguments, divot(), startOffset(), endOffset());

}

// ------------------------------ FunctionCallResolveNode ----------------------------------

RegisterID* FunctionCallResolveNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    if (RefPtr<RegisterID> local = generator.registerFor(m_ident)) {

        CallArguments callArguments(generator, m_args);

        generator.emitLoad(callArguments.thisRegister(), jsNull());

        return generator.emitCall(generator.finalDestinationOrIgnored(dst, callArguments.thisRegister()), local.get(), callArguments, divot(), startOffset(), endOffset());

    }

    int index = 0;

    size_t depth = 0;

    JSObject* globalObject = 0;

    bool requiresDynamicChecks = false;

    if (generator.findScopedProperty(m_ident, index, depth, false, requiresDynamicChecks, globalObject) && index != missingSymbolMarker() && !requiresDynamicChecks) {

        RefPtr<RegisterID> func = generator.emitGetScopedVar(generator.newTemporary(), depth, index, globalObject);

        CallArguments callArguments(generator, m_args);

        generator.emitLoad(callArguments.thisRegister(), jsNull());

        return generator.emitCall(generator.finalDestinationOrIgnored(dst, func.get()), func.get(), callArguments, divot(), startOffset(), endOffset());

    }

    RefPtr<RegisterID> func = generator.newTemporary();

    CallArguments callArguments(generator, m_args);

    int identifierStart = divot() - startOffset();

    generator.emitExpressionInfo(identifierStart + m_ident.size(), m_ident.size(), 0);

    generator.emitResolveWithBase(callArguments.thisRegister(), func.get(), m_ident);

    return generator.emitCall(generator.finalDestinationOrIgnored(dst, func.get()), func.get(), callArguments, divot(), startOffset(), endOffset());

}

// ------------------------------ FunctionCallBracketNode ----------------------------------

RegisterID* FunctionCallBracketNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    RefPtr<RegisterID> base = generator.emitNode(m_base);

    RegisterID* property = generator.emitNode(m_subscript);

    generator.emitExpressionInfo(divot() - m_subexpressionDivotOffset, startOffset() - m_subexpressionDivotOffset, m_subexpressionEndOffset);

    RefPtr<RegisterID> function = generator.emitGetByVal(generator.tempDestination(dst), base.get(), property);

    CallArguments callArguments(generator, m_args);

    generator.emitMove(callArguments.thisRegister(), base.get());

    return generator.emitCall(generator.finalDestinationOrIgnored(dst, function.get()), function.get(), callArguments, divot(), startOffset(), endOffset());

}

// ------------------------------ FunctionCallDotNode ----------------------------------

RegisterID* FunctionCallDotNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    RefPtr<RegisterID> function = generator.tempDestination(dst);

    CallArguments callArguments(generator, m_args);

    generator.emitNode(callArguments.thisRegister(), m_base);

    generator.emitExpressionInfo(divot() - m_subexpressionDivotOffset, startOffset() - m_subexpressionDivotOffset, m_subexpressionEndOffset);

    generator.emitMethodCheck();

    generator.emitGetById(function.get(), callArguments.thisRegister(), m_ident);

    return generator.emitCall(generator.finalDestinationOrIgnored(dst, function.get()), function.get(), callArguments, divot(), startOffset(), endOffset());

}

RegisterID* CallFunctionCallDotNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    RefPtr<Label> realCall = generator.newLabel();

    RefPtr<Label> end = generator.newLabel();

    RefPtr<RegisterID> base = generator.emitNode(m_base);

    generator.emitExpressionInfo(divot() - m_subexpressionDivotOffset, startOffset() - m_subexpressionDivotOffset, m_subexpressionEndOffset);

    RefPtr<RegisterID> function = generator.emitGetById(generator.tempDestination(dst), base.get(), m_ident);

    RefPtr<RegisterID> finalDestinationOrIgnored = generator.finalDestinationOrIgnored(dst, function.get());

    generator.emitJumpIfNotFunctionCall(function.get(), realCall.get());

    {

        if (m_args->m_listNode && m_args->m_listNode->m_expr) {

            ArgumentListNode* oldList = m_args->m_listNode;

            m_args->m_listNode = m_args->m_listNode->m_next;

            RefPtr<RegisterID> realFunction = generator.emitMove(generator.tempDestination(dst), base.get());

            CallArguments callArguments(generator, m_args);

            generator.emitNode(callArguments.thisRegister(), oldList->m_expr);

            generator.emitCall(finalDestinationOrIgnored.get(), realFunction.get(), callArguments, divot(), startOffset(), endOffset());

            generator.emitJump(end.get());

            m_args->m_listNode = oldList;

        } else {

            RefPtr<RegisterID> realFunction = generator.emitMove(generator.tempDestination(dst), base.get());

            CallArguments callArguments(generator, m_args);

            generator.emitLoad(callArguments.thisRegister(), jsNull());

            generator.emitCall(finalDestinationOrIgnored.get(), realFunction.get(), callArguments, divot(), startOffset(), endOffset());

            generator.emitJump(end.get());

        }

    }

    generator.emitLabel(realCall.get());

    {

        CallArguments callArguments(generator, m_args);

        generator.emitMove(callArguments.thisRegister(), base.get());

        generator.emitCall(finalDestinationOrIgnored.get(), function.get(), callArguments, divot(), startOffset(), endOffset());

    }

    generator.emitLabel(end.get());

    return finalDestinationOrIgnored.get();

}

static bool areTrivialApplyArguments(ArgumentsNode* args)

{

    return !args->m_listNode || !args->m_listNode->m_expr || !args->m_listNode->m_next

        || (!args->m_listNode->m_next->m_next && args->m_listNode->m_next->m_expr->isSimpleArray());

}

RegisterID* ApplyFunctionCallDotNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)

{

    // A few simple cases can be trivially handled as ordinary function calls.

    // function.apply(), function.apply(arg) -> identical to function.call

    // function.apply(thisArg, [arg0, arg1, ...]) -> can be trivially coerced into function.call(thisArg, arg0, arg1, ...) and saves object allocation

    bool mayBeCall = areTrivialApplyArguments(m_args);

    RefPtr<Label> realCall = generator.newLabel();

    RefPtr<Label> end = generator.newLabel();

    RefPtr<RegisterID> base = generator.emitNode(m_base);

    generator.emitExpressionInfo(divot() - m_subexpressionDivotOffset, startOffset() - m_subexpressionDivotOffset, m_subexpressionEndOffset);

    RefPtr<RegisterID> function = generator.emitGetById(generator.tempDestination(dst), base.get(), m_ident);

    RefPtr<RegisterID> finalDestinationOrIgnored = generator.finalDestinationOrIgnored(dst, function.get());

    generator.emitJumpIfNotFunctionApply(function.get(), realCall.get());

    {

        if (mayBeCall) {

            if (m_args->m_listNode && m_args->m_listNode->m_expr) {

                ArgumentListNode* oldList = m_args->m_listNode;

                if (m_args->m_listNode->m_next) {

                    ASSERT(m_args->m_listNode->m_next->m_expr->isSimpleArray());

                    ASSERT(!m_args->m_listNode->m_next->m_next);

                    m_args->m_listNode = static_cast<ArrayNode*>(m_args->m_listNode->m_next->m_expr)->toArgumentList(generator.globalData());

                    RefPtr<RegisterID> realFunction = generator.emitMove(generator.tempDestination(dst), base.get());

                    CallArguments callArguments(generator, m_args);

                    generator.emitNode(callArguments.thisRegister(), oldList->m_expr);

                    generator.emitCall(finalDestinationOrIgnored.get(), realFunction.get(), callArguments, divot(), startOffset(), endOffset());

                } else {

                    m_args->m_listNode = m_args->m_listNode->m_next;

                    RefPtr<RegisterID> realFunction = generator.emitMove(generator.tempDestination(dst), base.get());

                    CallArguments callArguments(generator, m_args);

                    generator.emitNode(callArguments.thisRegister(), oldList->m_expr);

                    generator.emitCall(finalDestinationOrIgnored.get(), realFunction.get(), callArguments, divot(), startOffset(), endOffset());

                }

                m_args->m_listNode = oldList;

            } else {

                RefPtr<RegisterID> realFunction = generator.emitMove(generator.tempDestination(dst), base.get());

                CallArguments callArguments(generator, m_args);

                generator.emitLoad(callArguments.thisRegister(), jsNull());

                generator.emitCall(finalDestinationOrIgnored.get(), realFunction.get(), callArguments, divot(), startOffset(), endOffset());

            }

        } else {

            ASSERT(m_args->m_listNode && m_args->m_listNode->m_next);

            RefPtr<RegisterID> realFunction = generator.emitMove(generator.newTemporary(), base.get());

            RefPtr<RegisterID> argsCountRegister = generator.newTemporary();

            RefPtr<RegisterID> thisRegister = generator.newTemporary();

            RefPtr<RegisterID> argsRegister = generator.newTemporary();

            generator.emitNode(thisRegister.get(), m_args->m_listNode->m_expr);

            ArgumentListNode* args = m_args->m_listNode->m_next;

            bool isArgumentsApply = false;

            if (args->m_expr->isResolveNode()) {

                ResolveNode* resolveNode = static_cast<ResolveNode*>(args->m_expr);

                isArgumentsApply = generator.willResolveToArguments(resolveNode->identifier());

                if (isArgumentsApply)

                    generator.emitMove(argsRegister.get(), generator.uncheckedRegisterForArguments());

            }

            if (!isArgumentsApply)

                generator.emitNode(argsRegister.get(), args->m_expr);

            while ((args = args->m_next))

                generator.emitNode(args->m_expr);

            generator.emitLoadVarargs(argsCountRegister.get(), argsRegister.get());

            generator.emitCallVarargs(finalDestinationOrIgnored.get(), realFunction.get(), thisRegister.get(), argsCountRegister.get(), divot(), startOffset(), endOffset());

        }

        generator.emitJump(end.get());

    }

    generator.emitLabel(realCall.get());

    {

        CallArguments callArguments(generator, m_args);