1 /*

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

     3  *

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

     5  * modification, are permitted provided that the following conditions

     6  * are met:

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

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

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

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

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

    12  *

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

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

    15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

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

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

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

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

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

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

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

    23  * THE POSSIBILITY OF SUCH DAMAGE.

    24  */

    25 

    26 #include "config.h"

    27 

    28 #include "JSParser.h"

    29 

    30 using namespace JSC;

    31 

    32 #include "JSGlobalData.h"

    33 #include "NodeInfo.h"

    34 #include "ASTBuilder.h"

    35 #include <wtf/HashFunctions.h>

    36 #include <utility>

    37 

    38 using namespace std;

    39 

    40 namespace JSC {

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

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

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

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

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

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

    47 

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

    49 #define TreeStatement typename TreeBuilder::Statement

    50 #define TreeExpression typename TreeBuilder::Expression

    51 #define TreeFormalParameterList typename TreeBuilder::FormalParameterList

    52 #define TreeSourceElements typename TreeBuilder::SourceElements

    53 #define TreeClause typename TreeBuilder::Clause

    54 #define TreeClauseList typename TreeBuilder::ClauseList

    55 #define TreeConstDeclList typename TreeBuilder::ConstDeclList

    56 #define TreeArguments typename TreeBuilder::Arguments

    57 #define TreeArgumentsList typename TreeBuilder::ArgumentsList

    58 #define TreeFunctionBody typename TreeBuilder::FunctionBody

    59 #define TreeProperty typename TreeBuilder::Property

    60 #define TreePropertyList typename TreeBuilder::PropertyList

    61 

    62 COMPILE_ASSERT(LastUntaggedToken < 64, LessThan64UntaggedTokens);

    63 

    64 // This matches v8

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

    66 

    67 class JSParser {

    68 public:

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

    70     bool parseProgram();

    71 private:

    72     struct AllowInOverride {

    73         AllowInOverride(JSParser* parser)

    74             : m_parser(parser)

    75             , m_oldAllowsIn(parser->m_allowsIn)

    76         {

    77             parser->m_allowsIn = true;

    78         }

    79         ~AllowInOverride()

    80         {

    81             m_parser->m_allowsIn = m_oldAllowsIn;

    82         }

    83         JSParser* m_parser;

    84         bool m_oldAllowsIn;

    85     };

    86 

    87     const JSToken& token() { return m_token; }

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

    89     {

    90         m_lastLine = token().m_info.line;

    91         m_lastTokenEnd = token().m_info.endOffset;

    92         m_lexer->setLastLineNumber(m_lastLine);

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

    94         m_tokenCount++;

    95     }

    96 

    97     bool consume(JSTokenType expected)

    98     {

    99         bool result = m_token.m_type == expected;

   100         failIfFalse(result);

   101         next();

   102         return result;

   103     }

   104 

   105     bool match(JSTokenType expected)

   106     {

   107         return m_token.m_type == expected;

   108     }

   109 

   110     int tokenStart()

   111     {

   112         return token().m_info.startOffset;

   113     }

   114 

   115     int tokenLine()

   116     {

   117         return token().m_info.line;

   118     }

   119 

   120     int tokenEnd()

   121     {

   122         return token().m_info.endOffset;

   123     }

   124 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   158 #if COMPILER(WINSCW)

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

   160 #else

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

   162 #endif

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

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

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

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

   167     enum FunctionRequirements { FunctionNoRequirements, FunctionNeedsName };

   168 #if COMPILER(WINSCW)

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

   170 #else

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

   172 #endif

   173     ALWAYS_INLINE int isBinaryOperator(JSTokenType token);

   174     bool allowAutomaticSemicolon();

   175 

   176     bool autoSemiColon()

   177     {

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

   179             next();

   180             return true;

   181         }

   182         return allowAutomaticSemicolon();

   183     }

   184 

   185     bool canRecurse()

   186     {

   187         char sample = 0;

   188         ASSERT(m_endAddress);

   189         return &sample > m_endAddress;

   190     }

   191     

   192     int lastTokenEnd() const

   193     {

   194         return m_lastTokenEnd;

   195     }

   196 

   197     ParserArena m_arena;

   198     Lexer* m_lexer;

   199     char* m_endAddress;

   200     bool m_error;

   201     JSGlobalData* m_globalData;

   202     JSToken m_token;

   203     bool m_allowsIn;

   204     int m_tokenCount;

   205     int m_lastLine;

   206     int m_lastTokenEnd;

   207     int m_assignmentCount;

   208     int m_nonLHSCount;

   209     bool m_syntaxAlreadyValidated;

   210 };

   211 

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

   213 {

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

   215     return parser.parseProgram();

   216 }

   217 

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

   219     : m_lexer(lexer)

   220     , m_endAddress(0)

   221     , m_error(false)

   222     , m_globalData(globalData)

   223     , m_allowsIn(true)

   224     , m_tokenCount(0)

   225     , m_lastLine(0)

   226     , m_lastTokenEnd(0)

   227     , m_assignmentCount(0)

   228     , m_nonLHSCount(0)

   229     , m_syntaxAlreadyValidated(provider->isValid())

   230 {

   231     m_endAddress = *(globalData->stackGuards);

   232     if (!m_endAddress) {

   233         char sample = 0;

   234         m_endAddress = &sample - kMaxParserStackUsage;

   235         *(globalData->stackGuards) = m_endAddress;

   236     }

   237     next();

   238     m_lexer->setLastLineNumber(tokenLine());

   239 }

   240 

   241 bool JSParser::parseProgram()

   242 {

   243     ASTBuilder context(m_globalData, m_lexer);

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

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

   246         return true;

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

   248                                           m_lastLine, context.numConstants());

   249     return false;

   250 }

   251 

   252 bool JSParser::allowAutomaticSemicolon()

   253 {

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

   255 }

   256 

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

   258 {

   259     TreeSourceElements sourceElements = context.createSourceElements();

   260     while (TreeStatement statement = parseStatement(context))

   261         context.appendStatement(sourceElements, statement);

   262 

   263     if (m_error)

   264         fail();

   265     return sourceElements;

   266 }

   267 

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

   269 {

   270     ASSERT(match(VAR));

   271     int start = tokenLine();

   272     int end = 0;

   273     int scratch;

   274     const Identifier* scratch1 = 0;

   275     TreeExpression scratch2 = 0;

   276     int scratch3 = 0;

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

   278     failIfTrue(m_error);

   279     failIfFalse(autoSemiColon());

   280 

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

   282 }

   283 

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

   285 {

   286     ASSERT(match(CONSTTOKEN));

   287     int start = tokenLine();

   288     int end = 0;

   289     TreeConstDeclList constDecls = parseConstDeclarationList(context);

   290     failIfTrue(m_error);

   291     failIfFalse(autoSemiColon());

   292     

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

   294 }

   295 

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

   297 {

   298     ASSERT(match(DO));

   299     int startLine = tokenLine();

   300     next();

   301     TreeStatement statement = parseStatement(context);

   302     failIfFalse(statement);

   303     int endLine = tokenLine();

   304     consumeOrFail(WHILE);

   305     consumeOrFail(OPENPAREN);

   306     TreeExpression expr = parseExpression(context);

   307     failIfFalse(expr);

   308     consumeOrFail(CLOSEPAREN);

   309     if (match(SEMICOLON))

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

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

   312 }

   313 

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

   315 {

   316     ASSERT(match(WHILE));

   317     int startLine = tokenLine();

   318     next();

   319     consumeOrFail(OPENPAREN);

   320     TreeExpression expr = parseExpression(context);

   321     failIfFalse(expr);

   322     int endLine = tokenLine();

   323     consumeOrFail(CLOSEPAREN);

   324     TreeStatement statement = parseStatement(context);

   325     failIfFalse(statement);

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

   327 }

   328 

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

   330 {

   331     TreeExpression varDecls = 0;

   332     do {

   333         declarations++;

   334         next();

   335         matchOrFail(IDENT);

   336 

   337         int varStart = tokenStart();

   338         identStart = varStart;

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

   340         lastIdent = name;

   341         next();

   342         bool hasInitializer = match(EQUAL);

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

   344         if (hasInitializer) {

   345             int varDivot = tokenStart() + 1;

   346             initStart = tokenStart();

   347             next(); // consume '='

   348             int initialAssignments = m_assignmentCount;

   349             TreeExpression initializer = parseAssignmentExpression(context);

   350             initEnd = lastTokenEnd();

   351             lastInitializer = initializer;

   352             failIfFalse(initializer);

   353 

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

   355             if (!varDecls)

   356                 varDecls = node;

   357             else

   358                 varDecls = context.combineCommaNodes(varDecls, node);

   359         }

   360     } while (match(COMMA));

   361     return varDecls;

   362 }

   363 

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

   365 {

   366     TreeConstDeclList constDecls = 0;

   367     TreeConstDeclList tail = 0;

   368     do {

   369         next();

   370         matchOrFail(IDENT);

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

   372         next();

   373         bool hasInitializer = match(EQUAL);

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

   375         TreeExpression initializer = 0;

   376         if (hasInitializer) {

   377             next(); // consume '='

   378             initializer = parseAssignmentExpression(context);

   379         }

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

   381         if (!constDecls)

   382             constDecls = tail;

   383     } while (match(COMMA));

   384     return constDecls;

   385 }

   386 

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

   388 {

   389     ASSERT(match(FOR));

   390     int startLine = tokenLine();

   391     next();

   392     consumeOrFail(OPENPAREN);

   393     int nonLHSCount = m_nonLHSCount;

   394     int declarations = 0;

   395     int declsStart = 0;

   396     int declsEnd = 0;

   397     TreeExpression decls = 0;

   398     bool hasDeclaration = false;

   399     if (match(VAR)) {

   400         /*

   401          for (var IDENT in expression) statement

   402          for (var IDENT = expression in expression) statement

   403          for (var varDeclarationList; expressionOpt; expressionOpt)

   404          */

   405         hasDeclaration = true;

   406         const Identifier* forInTarget = 0;

   407         TreeExpression forInInitializer = 0;

   408         m_allowsIn = false;

   409         int initStart = 0;

   410         int initEnd = 0;

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

   412         m_allowsIn = true;

   413         if (m_error)

   414             fail();

   415 

   416         // Remainder of a standard for loop is handled identically

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

   418             goto standardForLoop;

   419 

   420         // Handle for-in with var declaration

   421         int inLocation = tokenStart();

   422         if (!consume(INTOKEN))

   423             fail();

   424 

   425         TreeExpression expr = parseExpression(context);

   426         failIfFalse(expr);

   427         int exprEnd = lastTokenEnd();

   428 

   429         int endLine = tokenLine();

   430         consumeOrFail(CLOSEPAREN);

   431 

   432         TreeStatement statement = parseStatement(context);

   433         failIfFalse(statement);

   434 

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

   436     }

   437 

   438     if (!match(SEMICOLON)) {

   439         m_allowsIn = false;

   440         declsStart = tokenStart();

   441         decls = parseExpression(context);

   442         declsEnd = lastTokenEnd();

   443         m_allowsIn = true;

   444         failIfFalse(decls);

   445     }

   446 

   447     if (match(SEMICOLON)) {

   448     standardForLoop:

   449         // Standard for loop

   450         next();

   451         TreeExpression condition = 0;

   452 

   453         if (!match(SEMICOLON)) {

   454             condition = parseExpression(context);

   455             failIfFalse(condition);

   456         }

   457         consumeOrFail(SEMICOLON);

   458 

   459         TreeExpression increment = 0;

   460         if (!match(CLOSEPAREN)) {

   461             increment = parseExpression(context);

   462             failIfFalse(increment);

   463         }

   464         int endLine = tokenLine();

   465         consumeOrFail(CLOSEPAREN);

   466         TreeStatement statement = parseStatement(context);

   467         failIfFalse(statement);

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

   469     }

   470 

   471     // For-in loop

   472     failIfFalse(nonLHSCount == m_nonLHSCount);

   473     consumeOrFail(INTOKEN);

   474     TreeExpression expr = parseExpression(context);

   475     failIfFalse(expr);

   476     int exprEnd = lastTokenEnd();

   477     int endLine = tokenLine();

   478     consumeOrFail(CLOSEPAREN);

   479     TreeStatement statement = parseStatement(context);

   480     failIfFalse(statement);

   481     

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

   483 }

   484 

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

   486 {

   487     ASSERT(match(BREAK));

   488     int startCol = tokenStart();

   489     int endCol = tokenEnd();

   490     int startLine = tokenLine();

   491     int endLine = tokenLine();

   492     next();

   493 

   494     if (autoSemiColon())

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

   496     matchOrFail(IDENT);

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

   498     endCol = tokenEnd();

   499     endLine = tokenLine();

   500     next();

   501     failIfFalse(autoSemiColon());

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

   503 }

   504 

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

   506 {

   507     ASSERT(match(CONTINUE));

   508     int startCol = tokenStart();

   509     int endCol = tokenEnd();

   510     int startLine = tokenLine();

   511     int endLine = tokenLine();

   512     next();

   513 

   514     if (autoSemiColon())

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

   516     matchOrFail(IDENT);

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

   518     endCol = tokenEnd();

   519     endLine = tokenLine();

   520     next();

   521     failIfFalse(autoSemiColon());

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

   523 }

   524 

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

   526 {

   527     ASSERT(match(RETURN));

   528     int startLine = tokenLine();

   529     int endLine = startLine;

   530     int start = tokenStart();

   531     int end = tokenEnd();

   532     next();

   533     // We do the auto semicolon check before attempting to parse an expression

   534     // as we need to ensure the a line break after the return correctly terminates

   535     // the statement

   536     if (match(SEMICOLON))

   537         endLine  = tokenLine();

   538     if (autoSemiColon())

   539         return context.createReturnStatement(0, start, end, startLine, endLine);

   540     TreeExpression expr = parseExpression(context);

   541     failIfFalse(expr);

   542     end = lastTokenEnd();

   543     if (match(SEMICOLON))

   544         endLine  = tokenLine();

   545     failIfFalse(autoSemiColon());

   546     return context.createReturnStatement(expr, start, end, startLine, endLine);

   547 }

   548 

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

   550 {

   551     ASSERT(match(THROW));

   552     int eStart = tokenStart();

   553     int startLine = tokenLine();

   554     next();

   555 

   556     TreeExpression expr = parseExpression(context);

   557     failIfFalse(expr);

   558     int eEnd = lastTokenEnd();

   559     int endLine = tokenLine();

   560     failIfFalse(autoSemiColon());

   561 

   562     return context.createThrowStatement(expr, eStart, eEnd, startLine, endLine);

   563 }

   564 

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

   566 {

   567     ASSERT(match(WITH));

   568     int startLine = tokenLine();

   569     next();

   570     consumeOrFail(OPENPAREN);

   571     int start = tokenStart();

   572     TreeExpression expr = parseExpression(context);

   573     failIfFalse(expr);

   574     int end = lastTokenEnd();

   575 

   576     int endLine = tokenLine();

   577     consumeOrFail(CLOSEPAREN);

   578     

   579     TreeStatement statement = parseStatement(context);

   580     failIfFalse(statement);

   581 

   582     return context.createWithStatement(expr, statement, start, end, startLine, endLine);

   583 }

   584 

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

   586 {

   587     ASSERT(match(SWITCH));

   588     int startLine = tokenLine();

   589     next();

   590     consumeOrFail(OPENPAREN);

   591     TreeExpression expr = parseExpression(context);

   592     failIfFalse(expr);

   593     int endLine = tokenLine();

   594     consumeOrFail(CLOSEPAREN);

   595     consumeOrFail(OPENBRACE);

   596 

   597     TreeClauseList firstClauses = parseSwitchClauses(context);

   598     failIfTrue(m_error);

   599 

   600     TreeClause defaultClause = parseSwitchDefaultClause(context);

   601     failIfTrue(m_error);

   602 

   603     TreeClauseList secondClauses = parseSwitchClauses(context);

   604     failIfTrue(m_error);

   605     consumeOrFail(CLOSEBRACE);

   606 

   607     return context.createSwitchStatement(expr, firstClauses, defaultClause, secondClauses, startLine, endLine);

   608 

   609 }

   610 

   611 template <class TreeBuilder> TreeClauseList JSParser::parseSwitchClauses(TreeBuilder& context)

   612 {

   613     if (!match(CASE))

   614         return 0;

   615     next();

   616     TreeExpression condition = parseExpression(context);

   617     failIfFalse(condition);

   618     consumeOrFail(COLON);

   619     TreeSourceElements statements = parseSourceElements(context);

   620     failIfFalse(statements);

   621     TreeClause clause = context.createClause(condition, statements);

   622     TreeClauseList clauseList = context.createClauseList(clause);

   623     TreeClauseList tail = clauseList;

   624 

   625     while (match(CASE)) {

   626         next();

   627         TreeExpression condition = parseExpression(context);

   628         failIfFalse(condition);

   629         consumeOrFail(COLON);

   630         TreeSourceElements statements = parseSourceElements(context);

   631         failIfFalse(statements);

   632         clause = context.createClause(condition, statements);

   633         tail = context.createClauseList(tail, clause);

   634     }

   635     return clauseList;

   636 }

   637 

   638 template <class TreeBuilder> TreeClause JSParser::parseSwitchDefaultClause(TreeBuilder& context)

   639 {

   640     if (!match(DEFAULT))

   641         return 0;

   642     next();

   643     consumeOrFail(COLON);

   644     TreeSourceElements statements = parseSourceElements(context);

   645     failIfFalse(statements);

   646     return context.createClause(0, statements);

   647 }

   648 

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

   650 {

   651     ASSERT(match(TRY));

   652     TreeStatement tryBlock = 0;

   653     const Identifier* ident = &m_globalData->propertyNames->nullIdentifier;

   654     bool catchHasEval = false;

   655     TreeStatement catchBlock = 0;

   656     TreeStatement finallyBlock = 0;

   657     int firstLine = tokenLine();

   658     next();

   659     matchOrFail(OPENBRACE);

   660 

   661     tryBlock = parseBlockStatement(context);

   662     failIfFalse(tryBlock);

   663     int lastLine = m_lastLine;

   664 

   665     if (match(CATCH)) {

   666         next();

   667         consumeOrFail(OPENPAREN);

   668         matchOrFail(IDENT);

   669         ident = token().m_data.ident;

   670         next();

   671         consumeOrFail(CLOSEPAREN);

   672         matchOrFail(OPENBRACE);

   673         int initialEvalCount = context.evalCount();

   674         catchBlock = parseBlockStatement(context);

   675         failIfFalse(catchBlock);

   676         catchHasEval = initialEvalCount != context.evalCount();

   677     }

   678 

   679     if (match(FINALLY)) {

   680         next();

   681         matchOrFail(OPENBRACE);

   682         finallyBlock = parseBlockStatement(context);

   683         failIfFalse(finallyBlock);

   684     }

   685     failIfFalse(catchBlock || finallyBlock);

   686     return context.createTryStatement(tryBlock, ident, catchHasEval, catchBlock, finallyBlock, firstLine, lastLine);

   687 }

   688 

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

   690 {

   691     ASSERT(match(DEBUGGER));

   692     int startLine = tokenLine();

   693     int endLine = startLine;

   694     next();

   695     if (match(SEMICOLON))

   696         startLine = tokenLine();

   697     failIfFalse(autoSemiColon());

   698     return context.createDebugger(startLine, endLine);

   699 }

   700 

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

   702 {

   703     ASSERT(match(OPENBRACE));

   704     int start = tokenLine();

   705     next();

   706     if (match(CLOSEBRACE)) {

   707         next();

   708         return context.createBlockStatement(0, start, m_lastLine);

   709     }

   710     TreeSourceElements subtree = parseSourceElements(context);

   711     failIfFalse(subtree);

   712     matchOrFail(CLOSEBRACE);

   713     next();

   714     return context.createBlockStatement(subtree, start, m_lastLine);

   715 }

   716 

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

   718 {

   719     failIfStackOverflow();

   720     switch (token().m_type) {

   721     case OPENBRACE:

   722         return parseBlockStatement(context);

   723     case VAR:

   724         return parseVarDeclaration(context);

   725     case CONSTTOKEN:

   726         return parseConstDeclaration(context);

   727     case FUNCTION:

   728         return parseFunctionDeclaration(context);

   729     case SEMICOLON:

   730         next();

   731         return context.createEmptyStatement();

   732     case IF:

   733         return parseIfStatement(context);

   734     case DO:

   735         return parseDoWhileStatement(context);

   736     case WHILE:

   737         return parseWhileStatement(context);

   738     case FOR:

   739         return parseForStatement(context);

   740     case CONTINUE:

   741         return parseContinueStatement(context);

   742     case BREAK:

   743         return parseBreakStatement(context);

   744     case RETURN:

   745         return parseReturnStatement(context);

   746     case WITH:

   747         return parseWithStatement(context);

   748     case SWITCH:

   749         return parseSwitchStatement(context);

   750     case THROW:

   751         return parseThrowStatement(context);

   752     case TRY:

   753         return parseTryStatement(context);

   754     case DEBUGGER:

   755         return parseDebuggerStatement(context);

   756     case EOFTOK:

   757     case CASE:

   758     case CLOSEBRACE:

   759     case DEFAULT:

   760         // These tokens imply the end of a set of source elements

   761         return 0;

   762     case IDENT:

   763         return parseExpressionOrLabelStatement(context);

   764     default:

   765         return parseExpressionStatement(context);

   766     }

   767 }

   768 

   769 template <class TreeBuilder> TreeFormalParameterList JSParser::parseFormalParameters(TreeBuilder& context, bool& usesArguments)

   770 {

   771     matchOrFail(IDENT);

   772     usesArguments = m_globalData->propertyNames->arguments == *token().m_data.ident;

   773     TreeFormalParameterList list = context.createFormalParameterList(*token().m_data.ident);

   774     TreeFormalParameterList tail = list;

   775     next();

   776     while (match(COMMA)) {

   777         next();

   778         matchOrFail(IDENT);

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

   780         next();

   781         usesArguments = usesArguments || m_globalData->propertyNames->arguments == *ident;

   782         tail = context.createFormalParameterList(tail, *ident);

   783     }

   784     return list;

   785 }

   786 

   787 template <class TreeBuilder> TreeFunctionBody JSParser::parseFunctionBody(TreeBuilder& context)

   788 {

   789     if (match(CLOSEBRACE))

   790         return context.createFunctionBody();

   791     typename TreeBuilder::FunctionBodyBuilder bodyBuilder(m_globalData, m_lexer);

   792     failIfFalse(parseSourceElements(bodyBuilder));

   793     return context.createFunctionBody();

   794 }

   795 

   796 #if COMPILER(WINSCW)

   797 template <JSParser::FunctionRequirements requirements, class TreeBuilder> bool JSParser::parseFunctionInfo(JSParser::FunctionRequirements requirements, TreeBuilder& context, const Identifier*& name, TreeFormalParameterList& parameters, TreeFunctionBody& body, int& openBracePos, int& closeBracePos, int& bodyStartLine)

   798 #else

   799 template <JSParser::FunctionRequirements requirements, class TreeBuilder> bool JSParser::parseFunctionInfo(TreeBuilder& context, const Identifier*& name, TreeFormalParameterList& parameters, TreeFunctionBody& body, int& openBracePos, int& closeBracePos, int& bodyStartLine)

   800 #endif

   801 {

   802     if (match(IDENT)) {

   803         name = token().m_data.ident;

   804         next();

   805     } else if (requirements == FunctionNeedsName)

   806         return false;

   807     consumeOrFail(OPENPAREN);

   808     bool usesArguments = false;

   809     if (!match(CLOSEPAREN)) {

   810         parameters = parseFormalParameters(context, usesArguments);

   811         failIfFalse(parameters);

   812     }

   813     consumeOrFail(CLOSEPAREN);

   814     matchOrFail(OPENBRACE);

   815 

   816     openBracePos = token().m_data.intValue;

   817     bodyStartLine = tokenLine();

   818     next();

   819 

   820     body = parseFunctionBody(context);

   821     failIfFalse(body);

   822     if (usesArguments)

   823         context.setUsesArguments(body);

   824 

   825     matchOrFail(CLOSEBRACE);

   826     closeBracePos = token().m_data.intValue;

   827     next();

   828     return true;

   829 }

   830 

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

   832 {

   833     ASSERT(match(FUNCTION));

   834     next();

   835     const Identifier* name = 0;

   836     TreeFormalParameterList parameters = 0;

   837     TreeFunctionBody body = 0;

   838     int openBracePos = 0;

   839     int closeBracePos = 0;

   840     int bodyStartLine = 0;

   841 #if COMPILER(WINSCW)

   842     failIfFalse(parseFunctionInfo<FunctionNeedsName>(FunctionNeedsName, context, name, parameters, body, openBracePos, closeBracePos, bodyStartLine));

   843 #else

   844     failIfFalse(parseFunctionInfo<FunctionNeedsName>(context, name, parameters, body, openBracePos, closeBracePos, bodyStartLine));

   845 #endif

   846     failIfFalse(name);

   847     return context.createFuncDeclStatement(name, body, parameters, openBracePos, closeBracePos, bodyStartLine, m_lastLine);

   848 }

   849 

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

   851 {

   852 

   853     /* Expression and Label statements are ambiguous at LL(1), to avoid

   854      * the cost of having a token buffer to support LL(2) we simply assume

   855      * we have an expression statement, and then only look for a label if that

   856      * parse fails.

   857      */

   858     int start = tokenStart();

   859     int startLine = tokenLine();

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

   861     int currentToken = m_tokenCount;

   862     TreeExpression expression = parseExpression(context);

   863     failIfFalse(expression);

   864     if (autoSemiColon())

   865         return context.createExprStatement(expression, startLine, m_lastLine);

   866     failIfFalse(currentToken + 1 == m_tokenCount);

   867     int end = tokenEnd();

   868     consumeOrFail(COLON);

   869     TreeStatement statement = parseStatement(context);

   870     failIfFalse(statement);

   871     return context.createLabelStatement(ident, statement, start, end);

   872 }

   873 

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

   875 {

   876     int startLine = tokenLine();

   877     TreeExpression expression = parseExpression(context);

   878     failIfFalse(expression);

   879     failIfFalse(autoSemiColon());

   880     return context.createExprStatement(expression, startLine, m_lastLine);

   881 }

   882 

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

   884 {

   885     ASSERT(match(IF));

   886 

   887     int start = tokenLine();

   888     next();

   889 

   890     consumeOrFail(OPENPAREN);

   891 

   892     TreeExpression condition = parseExpression(context);

   893     failIfFalse(condition);

   894     int end = tokenLine();

   895     consumeOrFail(CLOSEPAREN);

   896 

   897     TreeStatement trueBlock = parseStatement(context);

   898     failIfFalse(trueBlock);

   899 

   900     if (!match(ELSE))

   901         return context.createIfStatement(condition, trueBlock, start, end);

   902     

   903     Vector<TreeExpression> exprStack;

   904     Vector<pair<int, int> > posStack;

   905     Vector<TreeStatement> statementStack;

   906     bool trailingElse = false;

   907     do {

   908         next();

   909         if (!match(IF)) {

   910             TreeStatement block = parseStatement(context);

   911             failIfFalse(block);

   912             statementStack.append(block);

   913             trailingElse = true;

   914             break;

   915         }

   916         int innerStart = tokenLine();

   917         next();

   918         

   919         consumeOrFail(OPENPAREN);

   920         

   921         TreeExpression innerCondition = parseExpression(context);

   922         failIfFalse(innerCondition);

   923         int innerEnd = tokenLine();

   924         consumeOrFail(CLOSEPAREN);

   925         

   926         TreeStatement innerTrueBlock = parseStatement(context);

   927         failIfFalse(innerTrueBlock);     

   928         exprStack.append(innerCondition);

   929         posStack.append(make_pair(innerStart, innerEnd));

   930         statementStack.append(innerTrueBlock);

   931     } while (match(ELSE));

   932 

   933     if (!trailingElse) {

   934         TreeExpression condition = exprStack.last();

   935         exprStack.removeLast();

   936         TreeStatement trueBlock = statementStack.last();

   937         statementStack.removeLast();

   938         pair<int, int> pos = posStack.last();

   939         posStack.removeLast();

   940         statementStack.append(context.createIfStatement(condition, trueBlock, pos.first, pos.second));

   941     }

   942 

   943     while (!exprStack.isEmpty()) {

   944         TreeExpression condition = exprStack.last();

   945         exprStack.removeLast();

   946         TreeStatement falseBlock = statementStack.last();

   947         statementStack.removeLast();

   948         TreeStatement trueBlock = statementStack.last();

   949         statementStack.removeLast();

   950         pair<int, int> pos = posStack.last();

   951         posStack.removeLast();

   952         statementStack.append(context.createIfStatement(condition, trueBlock, falseBlock, pos.first, pos.second));

   953     }

   954     

   955     return context.createIfStatement(condition, trueBlock, statementStack.last(), start, end);

   956 }

   957 

   958 template <class TreeBuilder> TreeExpression JSParser::parseExpression(TreeBuilder& context)

   959 {

   960     failIfStackOverflow();

   961     TreeExpression node = parseAssignmentExpression(context);

   962     failIfFalse(node);

   963     if (!match(COMMA))

   964         return node;

   965     next();

   966     m_nonLHSCount++;

   967     TreeExpression right = parseAssignmentExpression(context);

   968     failIfFalse(right);

   969     typename TreeBuilder::Comma commaNode = context.createCommaExpr(node, right);

   970     while (match(COMMA)) {

   971         next();

   972         right = parseAssignmentExpression(context);

   973         failIfFalse(right);

   974         context.appendToComma(commaNode, right);

   975     }

   976     return commaNode;

   977 }

   978 

   979 

   980 template <typename TreeBuilder> TreeExpression JSParser::parseAssignmentExpression(TreeBuilder& context)

   981 {

   982     failIfStackOverflow();

   983     int start = tokenStart();

   984     int initialAssignmentCount = m_assignmentCount;

   985     int initialNonLHSCount = m_nonLHSCount;

   986     TreeExpression lhs = parseConditionalExpression(context);

   987     failIfFalse(lhs);

   988     if (initialNonLHSCount != m_nonLHSCount)

   989         return lhs;

   990 

   991     int assignmentStack = 0;

   992     Operator op;

   993     bool hadAssignment = false;

   994     while (true) {

   995         switch (token().m_type) {

   996         case EQUAL: op = OpEqual; break;

   997         case PLUSEQUAL: op = OpPlusEq; break;

   998         case MINUSEQUAL: op = OpMinusEq; break;

   999         case MULTEQUAL: op = OpMultEq; break;

  1000         case DIVEQUAL: op = OpDivEq; break;

  1001         case LSHIFTEQUAL: op = OpLShift; break;

  1002         case RSHIFTEQUAL: op = OpRShift; break;

  1003         case URSHIFTEQUAL: op = OpURShift; break;

  1004         case ANDEQUAL: op = OpAndEq; break;

  1005         case XOREQUAL: op = OpXOrEq; break;

  1006         case OREQUAL: op = OpOrEq; break;

  1007         case MODEQUAL: op = OpModEq; break;

  1008         default:

  1009             goto end;

  1010         }

  1011         hadAssignment = true;

  1012         context.assignmentStackAppend(assignmentStack, lhs, start, tokenStart(), m_assignmentCount, op);

  1013         start = tokenStart();

  1014         m_assignmentCount++;

  1015         next();

  1016         lhs = parseConditionalExpression(context);

  1017         failIfFalse(lhs);

  1018         if (initialNonLHSCount != m_nonLHSCount)

  1019             break;

  1020     }

  1021 end:

  1022     if (hadAssignment)

  1023         m_nonLHSCount++;

  1024 

  1025     if (!ASTBuilder::CreatesAST)

  1026         return lhs;

  1027 

  1028     while (assignmentStack)

  1029         lhs = context.createAssignment(assignmentStack, lhs, initialAssignmentCount, m_assignmentCount, lastTokenEnd());

  1030 

  1031     return lhs;

  1032 }

  1033 

  1034 template <class TreeBuilder> TreeExpression JSParser::parseConditionalExpression(TreeBuilder& context)

  1035 {

  1036     TreeExpression cond = parseBinaryExpression(context);

  1037     failIfFalse(cond);

  1038     if (!match(QUESTION))

  1039         return cond;

  1040     m_nonLHSCount++;

  1041     next();

  1042     TreeExpression lhs = parseAssignmentExpression(context);

  1043     consumeOrFail(COLON);

  1044 

  1045     TreeExpression rhs = parseAssignmentExpression(context);

  1046     failIfFalse(rhs);

  1047     return context.createConditionalExpr(cond, lhs, rhs);

  1048 }

  1049 

  1050 ALWAYS_INLINE static bool isUnaryOp(JSTokenType token)

  1051 {

  1052     return token & UnaryOpTokenFlag;

  1053 }

  1054 

  1055 int JSParser::isBinaryOperator(JSTokenType token)

  1056 {

  1057     if (m_allowsIn)

  1058         return token & (BinaryOpTokenPrecedenceMask << BinaryOpTokenAllowsInPrecedenceAdditionalShift);

  1059     return token & BinaryOpTokenPrecedenceMask;

  1060 }

  1061 

  1062 template <class TreeBuilder> TreeExpression JSParser::parseBinaryExpression(TreeBuilder& context)

  1063 {

  1064 

  1065     int operandStackDepth = 0;

  1066     int operatorStackDepth = 0;

  1067     while (true) {

  1068         int exprStart = tokenStart();

  1069         int initialAssignments = m_assignmentCount;

  1070         TreeExpression current = parseUnaryExpression(context);

  1071         failIfFalse(current);

  1072 

  1073         context.appendBinaryExpressionInfo(operandStackDepth, current, exprStart, lastTokenEnd(), lastTokenEnd(), initialAssignments != m_assignmentCount);

  1074         int precedence = isBinaryOperator(token().m_type);

  1075         if (!precedence)

  1076             break;

  1077         m_nonLHSCount++;

  1078         int operatorToken = token().m_type;

  1079         next();

  1080 

  1081         while (operatorStackDepth &&  context.operatorStackHasHigherPrecedence(operatorStackDepth, precedence)) {

  1082             ASSERT(operandStackDepth > 1);

  1083 

  1084             typename TreeBuilder::BinaryOperand rhs = context.getFromOperandStack(-1);

  1085             typename TreeBuilder::BinaryOperand lhs = context.getFromOperandStack(-2);

  1086             context.shrinkOperandStackBy(operandStackDepth, 2);

  1087             context.appendBinaryOperation(operandStackDepth, operatorStackDepth, lhs, rhs);

  1088             context.operatorStackPop(operatorStackDepth);

  1089         }

  1090         context.operatorStackAppend(operatorStackDepth, operatorToken, precedence);

  1091     }

  1092 

  1093     while (operatorStackDepth) {

  1094         ASSERT(operandStackDepth > 1);

  1095 

  1096         typename TreeBuilder::BinaryOperand rhs = context.getFromOperandStack(-1);

  1097         typename TreeBuilder::BinaryOperand lhs = context.getFromOperandStack(-2);

  1098         context.shrinkOperandStackBy(operandStackDepth, 2);

  1099         context.appendBinaryOperation(operandStackDepth, operatorStackDepth, lhs, rhs);

  1100         context.operatorStackPop(operatorStackDepth);

  1101     }

  1102     return context.popOperandStack(operandStackDepth);

  1103 }

  1104 

  1105 #if COMPILER(WINSCW)

  1106 template <bool complete, class TreeBuilder> TreeProperty JSParser::parseProperty(bool complete, TreeBuilder& context)

  1107 #else

  1108 template <bool complete, class TreeBuilder> TreeProperty JSParser::parseProperty(TreeBuilder& context)

  1109 #endif

  1110 {

  1111     bool wasIdent = false;

  1112     switch (token().m_type) {

  1113     namedProperty:

  1114     case IDENT:

  1115         wasIdent = true;

  1116     case STRING: {

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

  1118         next(Lexer::IgnoreReservedWords);

  1119         if (match(COLON)) {

  1120             next();

  1121             TreeExpression node = parseAssignmentExpression(context);

  1122             failIfFalse(node);

  1123             if (complete)

  1124                 return context.template createProperty<true>(ident, node, PropertyNode::Constant);

  1125             else

  1126                 return context.template createProperty<false>(ident, node, PropertyNode::Constant);

  1127         }

  1128         failIfFalse(wasIdent);

  1129         matchOrFail(IDENT);

  1130         const Identifier* accessorName = 0;

  1131         TreeFormalParameterList parameters = 0;

  1132         TreeFunctionBody body = 0;

  1133         int openBracePos = 0;

  1134         int closeBracePos = 0;

  1135         int bodyStartLine = 0;