/*

 * Copyright (C) 2010 Apple Inc. All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 *

 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''

 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,

 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS

 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF

 * THE POSSIBILITY OF SUCH DAMAGE.

 */

#include "config.h"

#include "JSParser.h"

using namespace JSC;

#include "JSGlobalData.h"

#include "NodeInfo.h"

#include "ASTBuilder.h"

#include <wtf/HashFunctions.h>

#include <utility>

using namespace std;

namespace JSC {

#define fail() do { m_error = true; return 0; } while (0)

#define failIfFalse(cond) do { if (!(cond)) fail(); } while (0)

#define failIfTrue(cond) do { if ((cond)) fail(); } while (0)

#define consumeOrFail(tokenType) do { if (!consume(tokenType)) fail(); } while (0)

#define matchOrFail(tokenType) do { if (!match(tokenType)) fail(); } while (0)

#define failIfStackOverflow() do { failIfFalse(canRecurse()); } while (0)

// Macros to make the more common TreeBuilder types a little less verbose

#define TreeStatement typename TreeBuilder::Statement

#define TreeExpression typename TreeBuilder::Expression

#define TreeFormalParameterList typename TreeBuilder::FormalParameterList

#define TreeSourceElements typename TreeBuilder::SourceElements

#define TreeClause typename TreeBuilder::Clause

#define TreeClauseList typename TreeBuilder::ClauseList

#define TreeConstDeclList typename TreeBuilder::ConstDeclList

#define TreeArguments typename TreeBuilder::Arguments

#define TreeArgumentsList typename TreeBuilder::ArgumentsList

#define TreeFunctionBody typename TreeBuilder::FunctionBody

#define TreeProperty typename TreeBuilder::Property

#define TreePropertyList typename TreeBuilder::PropertyList

COMPILE_ASSERT(LastUntaggedToken < 64, LessThan64UntaggedTokens);

// This matches v8

static const ptrdiff_t kMaxParserStackUsage = 128 * sizeof(void*) * 1024;

class JSParser {

public:

    JSParser(Lexer*, JSGlobalData*, SourceProvider*);

    bool parseProgram();

private:

    struct AllowInOverride {

        AllowInOverride(JSParser* parser)

            : m_parser(parser)

            , m_oldAllowsIn(parser->m_allowsIn)

        {

            parser->m_allowsIn = true;

        }

        ~AllowInOverride()

        {

            m_parser->m_allowsIn = m_oldAllowsIn;

        }

        JSParser* m_parser;

        bool m_oldAllowsIn;

    };

    const JSToken& token() { return m_token; }

    void next(Lexer::LexType lexType = Lexer::IdentifyReservedWords)

    {

        m_lastLine = token().m_info.line;

        m_lastTokenEnd = token().m_info.endOffset;

        m_lexer->setLastLineNumber(m_lastLine);

        m_token.m_type = m_lexer->lex(&m_token.m_data, &m_token.m_info, lexType);

        m_tokenCount++;

    }

    bool consume(JSTokenType expected)

    {

        bool result = m_token.m_type == expected;

        failIfFalse(result);

        next();

        return result;

    }

    bool match(JSTokenType expected)

    {

        return m_token.m_type == expected;

    }

    int tokenStart()

    {

        return token().m_info.startOffset;

    }

    int tokenLine()

    {

        return token().m_info.line;

    }

    int tokenEnd()

    {

        return token().m_info.endOffset;

    }

    template <class TreeBuilder> TreeSourceElements parseSourceElements(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseStatement(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseFunctionDeclaration(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseVarDeclaration(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseConstDeclaration(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseDoWhileStatement(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseWhileStatement(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseForStatement(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseBreakStatement(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseContinueStatement(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseReturnStatement(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseThrowStatement(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseWithStatement(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseSwitchStatement(TreeBuilder&);

    template <class TreeBuilder> TreeClauseList parseSwitchClauses(TreeBuilder&);

    template <class TreeBuilder> TreeClause parseSwitchDefaultClause(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseTryStatement(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseDebuggerStatement(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseExpressionStatement(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseExpressionOrLabelStatement(TreeBuilder&);

    template <class TreeBuilder> TreeStatement parseIfStatement(TreeBuilder&);

    template <class TreeBuilder> ALWAYS_INLINE TreeStatement parseBlockStatement(TreeBuilder&);

    template <class TreeBuilder> TreeExpression parseExpression(TreeBuilder&);

    template <class TreeBuilder> TreeExpression parseAssignmentExpression(TreeBuilder&);

    template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseConditionalExpression(TreeBuilder&);

    template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseBinaryExpression(TreeBuilder&);

    template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseUnaryExpression(TreeBuilder&);

    template <class TreeBuilder> TreeExpression parseMemberExpression(TreeBuilder&);

    template <class TreeBuilder> ALWAYS_INLINE TreeExpression parsePrimaryExpression(TreeBuilder&);

    template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseArrayLiteral(TreeBuilder&);

    template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseObjectLiteral(TreeBuilder&);

    template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseStrictObjectLiteral(TreeBuilder&);

    template <class TreeBuilder> ALWAYS_INLINE TreeArguments parseArguments(TreeBuilder&);

#if COMPILER(WINSCW)

    template <bool strict, class TreeBuilder> ALWAYS_INLINE TreeProperty parseProperty(bool, TreeBuilder&);

#else

    template <bool strict, class TreeBuilder> ALWAYS_INLINE TreeProperty parseProperty(TreeBuilder&);

#endif

    template <class TreeBuilder> ALWAYS_INLINE TreeFunctionBody parseFunctionBody(TreeBuilder&);

    template <class TreeBuilder> ALWAYS_INLINE TreeFormalParameterList parseFormalParameters(TreeBuilder&, bool& usesArguments);

    template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseVarDeclarationList(TreeBuilder&, int& declarations, const Identifier*& lastIdent, TreeExpression& lastInitializer, int& identStart, int& initStart, int& initEnd);

    template <class TreeBuilder> ALWAYS_INLINE TreeConstDeclList parseConstDeclarationList(TreeBuilder& context);

    enum FunctionRequirements { FunctionNoRequirements, FunctionNeedsName };

#if COMPILER(WINSCW)

    template <FunctionRequirements, class TreeBuilder> bool parseFunctionInfo(FunctionRequirements, TreeBuilder&, const Identifier*&, TreeFormalParameterList&, TreeFunctionBody&, int& openBrace, int& closeBrace, int& bodyStartLine);

#else

    template <FunctionRequirements, class TreeBuilder> bool parseFunctionInfo(TreeBuilder&, const Identifier*&, TreeFormalParameterList&, TreeFunctionBody&, int& openBrace, int& closeBrace, int& bodyStartLine);

#endif

    ALWAYS_INLINE int isBinaryOperator(JSTokenType token);

    bool allowAutomaticSemicolon();

    bool autoSemiColon()

    {

        if (token().m_type == SEMICOLON) {

            next();

            return true;

        }

        return allowAutomaticSemicolon();

    }

    bool canRecurse()

    {

        char sample = 0;

        ASSERT(m_endAddress);

        return &sample > m_endAddress;

    }

    int lastTokenEnd() const

    {

        return m_lastTokenEnd;

    }

    ParserArena m_arena;

    Lexer* m_lexer;

    char* m_endAddress;

    bool m_error;

    JSGlobalData* m_globalData;

    JSToken m_token;

    bool m_allowsIn;

    int m_tokenCount;

    int m_lastLine;

    int m_lastTokenEnd;

    int m_assignmentCount;

    int m_nonLHSCount;

    bool m_syntaxAlreadyValidated;

};

int jsParse(JSGlobalData* globalData, const SourceCode* source)

{

    JSParser parser(globalData->lexer, globalData, source->provider());

    return parser.parseProgram();

}

JSParser::JSParser(Lexer* lexer, JSGlobalData* globalData, SourceProvider* provider)

    : m_lexer(lexer)

    , m_endAddress(0)

    , m_error(false)

    , m_globalData(globalData)

    , m_allowsIn(true)

    , m_tokenCount(0)

    , m_lastLine(0)

    , m_lastTokenEnd(0)

    , m_assignmentCount(0)

    , m_nonLHSCount(0)

    , m_syntaxAlreadyValidated(provider->isValid())

{

    m_endAddress = *(globalData->stackGuards);

    if (!m_endAddress) {

        char sample = 0;

        m_endAddress = &sample - kMaxParserStackUsage;

        *(globalData->stackGuards) = m_endAddress;

    }

    next();

    m_lexer->setLastLineNumber(tokenLine());

}

bool JSParser::parseProgram()

{

    ASTBuilder context(m_globalData, m_lexer);

    SourceElements* sourceElements = parseSourceElements<ASTBuilder>(context);

    if (!sourceElements || !consume(EOFTOK))

        return true;

    m_globalData->parser->didFinishParsing(sourceElements, context.varDeclarations(), context.funcDeclarations(), context.features(),

                                          m_lastLine, context.numConstants());

    return false;

}

bool JSParser::allowAutomaticSemicolon()

{

    return match(CLOSEBRACE) || match(EOFTOK) || m_lexer->prevTerminator();

}

template <class TreeBuilder> TreeSourceElements JSParser::parseSourceElements(TreeBuilder& context)

{

    TreeSourceElements sourceElements = context.createSourceElements();

    while (TreeStatement statement = parseStatement(context))

        context.appendStatement(sourceElements, statement);

    if (m_error)

        fail();

    return sourceElements;

}

template <class TreeBuilder> TreeStatement JSParser::parseVarDeclaration(TreeBuilder& context)

{

    ASSERT(match(VAR));

    int start = tokenLine();

    int end = 0;

    int scratch;

    const Identifier* scratch1 = 0;

    TreeExpression scratch2 = 0;

    int scratch3 = 0;

    TreeExpression varDecls = parseVarDeclarationList(context, scratch, scratch1, scratch2, scratch3, scratch3, scratch3);

    failIfTrue(m_error);

    failIfFalse(autoSemiColon());

    return context.createVarStatement(varDecls, start, end);

}

template <class TreeBuilder> TreeStatement JSParser::parseConstDeclaration(TreeBuilder& context)

{

    ASSERT(match(CONSTTOKEN));

    int start = tokenLine();

    int end = 0;

    TreeConstDeclList constDecls = parseConstDeclarationList(context);

    failIfTrue(m_error);

    failIfFalse(autoSemiColon());

    return context.createConstStatement(constDecls, start, end);

}

template <class TreeBuilder> TreeStatement JSParser::parseDoWhileStatement(TreeBuilder& context)

{

    ASSERT(match(DO));

    int startLine = tokenLine();

    next();

    TreeStatement statement = parseStatement(context);

    failIfFalse(statement);

    int endLine = tokenLine();

    consumeOrFail(WHILE);

    consumeOrFail(OPENPAREN);

    TreeExpression expr = parseExpression(context);

    failIfFalse(expr);

    consumeOrFail(CLOSEPAREN);

    if (match(SEMICOLON))

        next(); // Always performs automatic semicolon insertion.

    return context.createDoWhileStatement(statement, expr, startLine, endLine);

}

template <class TreeBuilder> TreeStatement JSParser::parseWhileStatement(TreeBuilder& context)

{

    ASSERT(match(WHILE));

    int startLine = tokenLine();

    next();

    consumeOrFail(OPENPAREN);

    TreeExpression expr = parseExpression(context);

    failIfFalse(expr);

    int endLine = tokenLine();

    consumeOrFail(CLOSEPAREN);

    TreeStatement statement = parseStatement(context);

    failIfFalse(statement);

    return context.createWhileStatement(expr, statement, startLine, endLine);

}

template <class TreeBuilder> TreeExpression JSParser::parseVarDeclarationList(TreeBuilder& context, int& declarations, const Identifier*& lastIdent, TreeExpression& lastInitializer, int& identStart, int& initStart, int& initEnd)

{

    TreeExpression varDecls = 0;

    do {

        declarations++;

        next();

        matchOrFail(IDENT);

        int varStart = tokenStart();

        identStart = varStart;

        const Identifier* name = token().m_data.ident;

        lastIdent = name;

        next();

        bool hasInitializer = match(EQUAL);

        context.addVar(name, (hasInitializer || (!m_allowsIn && match(INTOKEN))) ? DeclarationStacks::HasInitializer : 0);

        if (hasInitializer) {

            int varDivot = tokenStart() + 1;

            initStart = tokenStart();

            next(); // consume '='

            int initialAssignments = m_assignmentCount;

            TreeExpression initializer = parseAssignmentExpression(context);

            initEnd = lastTokenEnd();

            lastInitializer = initializer;

            failIfFalse(initializer);

            TreeExpression node = context.createAssignResolve(*name, initializer, initialAssignments != m_assignmentCount, varStart, varDivot, lastTokenEnd());

            if (!varDecls)

                varDecls = node;

            else

                varDecls = context.combineCommaNodes(varDecls, node);

        }

    } while (match(COMMA));

    return varDecls;

}

template <class TreeBuilder> TreeConstDeclList JSParser::parseConstDeclarationList(TreeBuilder& context)

{

    TreeConstDeclList constDecls = 0;

    TreeConstDeclList tail = 0;

    do {

        next();

        matchOrFail(IDENT);

        const Identifier* name = token().m_data.ident;

        next();

        bool hasInitializer = match(EQUAL);

        context.addVar(name, DeclarationStacks::IsConstant | (hasInitializer ? DeclarationStacks::HasInitializer : 0));

        TreeExpression initializer = 0;

        if (hasInitializer) {

            next(); // consume '='

            initializer = parseAssignmentExpression(context);

        }

        tail = context.appendConstDecl(tail, name, initializer);

        if (!constDecls)

            constDecls = tail;

    } while (match(COMMA));

    return constDecls;

}

template <class TreeBuilder> TreeStatement JSParser::parseForStatement(TreeBuilder& context)

{

    ASSERT(match(FOR));

    int startLine = tokenLine();

    next();

    consumeOrFail(OPENPAREN);

    int nonLHSCount = m_nonLHSCount;

    int declarations = 0;

    int declsStart = 0;

    int declsEnd = 0;

    TreeExpression decls = 0;

    bool hasDeclaration = false;

    if (match(VAR)) {

        /*

         for (var IDENT in expression) statement

         for (var IDENT = expression in expression) statement

         for (var varDeclarationList; expressionOpt; expressionOpt)

         */

        hasDeclaration = true;

        const Identifier* forInTarget = 0;

        TreeExpression forInInitializer = 0;

        m_allowsIn = false;

        int initStart = 0;

        int initEnd = 0;

        decls = parseVarDeclarationList(context, declarations, forInTarget, forInInitializer, declsStart, initStart, initEnd);

        m_allowsIn = true;

        if (m_error)

            fail();

        // Remainder of a standard for loop is handled identically

        if (declarations > 1 || match(SEMICOLON))

            goto standardForLoop;

        // Handle for-in with var declaration

        int inLocation = tokenStart();

        if (!consume(INTOKEN))

            fail();

        TreeExpression expr = parseExpression(context);

        failIfFalse(expr);

        int exprEnd = lastTokenEnd();

        int endLine = tokenLine();

        consumeOrFail(CLOSEPAREN);

        TreeStatement statement = parseStatement(context);

        failIfFalse(statement);

        return context.createForInLoop(forInTarget, forInInitializer, expr, statement, declsStart, inLocation, exprEnd, initStart, initEnd, startLine, endLine);

    }

    if (!match(SEMICOLON)) {

        m_allowsIn = false;

        declsStart = tokenStart();

        decls = parseExpression(context);

        declsEnd = lastTokenEnd();

        m_allowsIn = true;

        failIfFalse(decls);

    }

    if (match(SEMICOLON)) {

    standardForLoop:

        // Standard for loop

        next();

        TreeExpression condition = 0;

        if (!match(SEMICOLON)) {

            condition = parseExpression(context);

            failIfFalse(condition);

        }

        consumeOrFail(SEMICOLON);

        TreeExpression increment = 0;

        if (!match(CLOSEPAREN)) {

            increment = parseExpression(context);

            failIfFalse(increment);

        }

        int endLine = tokenLine();

        consumeOrFail(CLOSEPAREN);

        TreeStatement statement = parseStatement(context);

        failIfFalse(statement);

        return context.createForLoop(decls, condition, increment, statement, hasDeclaration, startLine, endLine);

    }

    // For-in loop

    failIfFalse(nonLHSCount == m_nonLHSCount);

    consumeOrFail(INTOKEN);

    TreeExpression expr = parseExpression(context);

    failIfFalse(expr);

    int exprEnd = lastTokenEnd();

    int endLine = tokenLine();

    consumeOrFail(CLOSEPAREN);

    TreeStatement statement = parseStatement(context);

    failIfFalse(statement);

    return context.createForInLoop(decls, expr, statement, declsStart, declsEnd, exprEnd, startLine, endLine);

}

template <class TreeBuilder> TreeStatement JSParser::parseBreakStatement(TreeBuilder& context)

{

    ASSERT(match(BREAK));

    int startCol = tokenStart();

    int endCol = tokenEnd();

    int startLine = tokenLine();

    int endLine = tokenLine();

    next();

    if (autoSemiColon())

        return context.createBreakStatement(startCol, endCol, startLine, endLine);

    matchOrFail(IDENT);

    const Identifier* ident = token().m_data.ident;

    endCol = tokenEnd();

    endLine = tokenLine();

    next();

    failIfFalse(autoSemiColon());

    return context.createBreakStatement(ident, startCol, endCol, startLine, endLine);

}

template <class TreeBuilder> TreeStatement JSParser::parseContinueStatement(TreeBuilder& context)

{

    ASSERT(match(CONTINUE));

    int startCol = tokenStart();

    int endCol = tokenEnd();

    int startLine = tokenLine();

    int endLine = tokenLine();

    next();

    if (autoSemiColon())

        return context.createContinueStatement(startCol, endCol, startLine, endLine);

    matchOrFail(IDENT);

    const Identifier* ident = token().m_data.ident;

    endCol = tokenEnd();

    endLine = tokenLine();

    next();

    failIfFalse(autoSemiColon());

    return context.createContinueStatement(ident, startCol, endCol, startLine, endLine);

}

template <class TreeBuilder> TreeStatement JSParser::parseReturnStatement(TreeBuilder& context)

{

    ASSERT(match(RETURN));

    int startLine = tokenLine();