parser/Parser.cpp

   1 /*
   2  *  Copyright (C) 1999-2001 Harri Porten (porten@kde.org)
   3  *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
   4  *  Copyright (C) 2003, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved.
   5  *
   6  *  This library is free software; you can redistribute it and/or
   7  *  modify it under the terms of the GNU Library General Public
   8  *  License as published by the Free Software Foundation; either
   9  *  version 2 of the License, or (at your option) any later version.
  10  *
  11  *  This library is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  *  Library General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU Library General Public License
  17  *  along with this library; see the file COPYING.LIB.  If not, write to
  18  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  19  *  Boston, MA 02110-1301, USA.
  20  *
  21  */
  22
  23 #include "config.h"
  24 #include "Parser.h"
  25
  26 #include "ASTBuilder.h"
  27 #include "CodeBlock.h"
  28 #include "Debugger.h"
  29 #include "JSGlobalData.h"
  30 #include "Lexer.h"
  31 #include "NodeInfo.h"
  32 #include "SourceProvider.h"
  33 #include <utility>
  34 #include <wtf/HashFunctions.h>
  35 #include <wtf/OwnPtr.h>
  36 #include <wtf/WTFThreadData.h>
  37
  38 using namespace std;
  39
  40 namespace JSC {
  41
  42 template <typename LexerType>
  43 Parser<LexerType>::Parser(JSGlobalData* globalData, const SourceCode& source, FunctionParameters* parameters, JSParserStrictness strictness, JSParserMode parserMode)
  44     : m_globalData(globalData)
  45     , m_source(&source)
  46     , m_stack(wtfThreadData().stack())
  47     , m_error(false)
  48     , m_errorMessage("Parse error")
  49     , m_allowsIn(true)
  50     , m_lastLine(0)
  51     , m_lastTokenEnd(0)
  52     , m_assignmentCount(0)
  53     , m_nonLHSCount(0)
  54     , m_syntaxAlreadyValidated(source.provider()->isValid())
  55     , m_statementDepth(0)
  56     , m_nonTrivialExpressionCount(0)
  57     , m_lastIdentifier(0)
  58     , m_sourceElements(0)
  59 {
  60     m_lexer = adoptPtr(new LexerType(globalData));
  61     m_arena = m_globalData->parserArena.get();
  62     m_lexer->setCode(source, m_arena);
  63
  64     m_functionCache = source.provider()->cache();
  65     ScopeRef scope = pushScope();
  66     if (parserMode == JSParseFunctionCode)
  67         scope->setIsFunction();
  68     if (strictness == JSParseStrict)
  69         scope->setStrictMode();
  70     if (parameters) {
  71         for (unsigned i = 0; i < parameters->size(); i++)
  72             scope->declareParameter(&parameters->at(i));
  73     }
  74     next();
  75     m_lexer->setLastLineNumber(tokenLine());
  76 }
  77
  78 template <typename LexerType>
  79 Parser<LexerType>::~Parser()
  80 {
  81 }
  82
  83 template <typename LexerType>
  84 UString Parser<LexerType>::parseInner()
  85 {
  86     UString parseError = UString();
  87
  88     unsigned oldFunctionCacheSize = m_functionCache ? m_functionCache->byteSize() : 0;
  89     ASTBuilder context(const_cast<JSGlobalData*>(m_globalData), const_cast<SourceCode*>(m_source));
  90     if (m_lexer->isReparsing())
  91         m_statementDepth--;
  92     ScopeRef scope = currentScope();
  93     SourceElements* sourceElements = parseSourceElements<CheckForStrictMode>(context);
  94     if (!sourceElements || !consume(EOFTOK))
  95         parseError = m_errorMessage;
  96
  97     IdentifierSet capturedVariables;
  98     scope->getCapturedVariables(capturedVariables);
  99     CodeFeatures features = context.features();
 100     if (scope->strictMode())
 101         features |= StrictModeFeature;
 102     if (scope->shadowsArguments())
 103         features |= ShadowsArgumentsFeature;
 104     unsigned functionCacheSize = m_functionCache ? m_functionCache->byteSize() : 0;
 105     if (functionCacheSize != oldFunctionCacheSize)
 106         m_lexer->sourceProvider()->notifyCacheSizeChanged(functionCacheSize - oldFunctionCacheSize);
 107
 108     didFinishParsing(sourceElements, context.varDeclarations(), context.funcDeclarations(), features,
 109                      m_lastLine, context.numConstants(), capturedVariables);
 110
 111     return parseError;
 112 }
 113
 114 template <typename LexerType>
 115 void Parser<LexerType>::didFinishParsing(SourceElements* sourceElements, ParserArenaData<DeclarationStacks::VarStack>* varStack,
 116                               ParserArenaData<DeclarationStacks::FunctionStack>* funcStack, CodeFeatures features, int lastLine, int numConstants, IdentifierSet& capturedVars)
 117 {
 118     m_sourceElements = sourceElements;
 119     m_varDeclarations = varStack;
 120     m_funcDeclarations = funcStack;
 121     m_capturedVariables.swap(capturedVars);
 122     m_features = features;
 123     m_lastLine = lastLine;
 124     m_numConstants = numConstants;
 125 }
 126
 127 template <typename LexerType>
 128 bool Parser<LexerType>::allowAutomaticSemicolon()
 129 {
 130     return match(CLOSEBRACE) || match(EOFTOK) || m_lexer->prevTerminator();
 131 }
 132
 133 template <typename LexerType>
 134 template <SourceElementsMode mode, class TreeBuilder> TreeSourceElements Parser<LexerType>::parseSourceElements(TreeBuilder& context)
 135 {
 136     const unsigned lengthOfUseStrictLiteral = 12; // "use strict".length
 137     TreeSourceElements sourceElements = context.createSourceElements();
 138     bool seenNonDirective = false;
 139     const Identifier* directive = 0;
 140     unsigned directiveLiteralLength = 0;
 141     unsigned startOffset = m_token.m_info.startOffset;
 142     unsigned oldLastLineNumber = m_lexer->lastLineNumber();
 143     unsigned oldLineNumber = m_lexer->lineNumber();
 144     bool hasSetStrict = false;
 145     while (TreeStatement statement = parseStatement(context, directive, &directiveLiteralLength)) {
 146         if (mode == CheckForStrictMode && !seenNonDirective) {
 147             if (directive) {
 148                 // "use strict" must be the exact literal without escape sequences or line continuation.
 149                 if (!hasSetStrict && directiveLiteralLength == lengthOfUseStrictLiteral && m_globalData->propertyNames->useStrictIdentifier == *directive) {
 150                     setStrictMode();
 151                     hasSetStrict = true;
 152                     failIfFalse(isValidStrictMode());
 153                     m_lexer->setOffset(startOffset);
 154                     next();
 155                     m_lexer->setLastLineNumber(oldLastLineNumber);
 156                     m_lexer->setLineNumber(oldLineNumber);
 157                     failIfTrue(m_error);
 158                     continue;
 159                 }
 160             } else
 161                 seenNonDirective = true;
 162         }
 163         context.appendStatement(sourceElements, statement);
 164     }
 165
 166     if (m_error)
 167         fail();
 168     return sourceElements;
 169 }
 170
 171 template <typename LexerType>
 172 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseVarDeclaration(TreeBuilder& context)
 173 {
 174     ASSERT(match(VAR));
 175     int start = tokenLine();
 176     int end = 0;
 177     int scratch;
 178     const Identifier* scratch1 = 0;
 179     TreeExpression scratch2 = 0;
 180     int scratch3 = 0;
 181     TreeExpression varDecls = parseVarDeclarationList(context, scratch, scratch1, scratch2, scratch3, scratch3, scratch3);
 182     failIfTrue(m_error);
 183     failIfFalse(autoSemiColon());
 184
 185     return context.createVarStatement(m_lexer->lastLineNumber(), varDecls, start, end);
 186 }
 187
 188 template <typename LexerType>
 189 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseConstDeclaration(TreeBuilder& context)
 190 {
 191     ASSERT(match(CONSTTOKEN));
 192     int start = tokenLine();
 193     int end = 0;
 194     TreeConstDeclList constDecls = parseConstDeclarationList(context);
 195     failIfTrue(m_error);
 196     failIfFalse(autoSemiColon());
 197
 198     return context.createConstStatement(m_lexer->lastLineNumber(), constDecls, start, end);
 199 }
 200
 201 template <typename LexerType>
 202 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseDoWhileStatement(TreeBuilder& context)
 203 {
 204     ASSERT(match(DO));
 205     int startLine = tokenLine();
 206     next();
 207     const Identifier* unused = 0;
 208     startLoop();
 209     TreeStatement statement = parseStatement(context, unused);
 210     endLoop();
 211     failIfFalse(statement);
 212     int endLine = tokenLine();
 213     consumeOrFail(WHILE);
 214     consumeOrFail(OPENPAREN);
 215     TreeExpression expr = parseExpression(context);
 216     failIfFalse(expr);
 217     consumeOrFail(CLOSEPAREN);
 218     if (match(SEMICOLON))
 219         next(); // Always performs automatic semicolon insertion.
 220     return context.createDoWhileStatement(m_lexer->lastLineNumber(), statement, expr, startLine, endLine);
 221 }
 222
 223 template <typename LexerType>
 224 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseWhileStatement(TreeBuilder& context)
 225 {
 226     ASSERT(match(WHILE));
 227     int startLine = tokenLine();
 228     next();
 229     consumeOrFail(OPENPAREN);
 230     TreeExpression expr = parseExpression(context);
 231     failIfFalse(expr);
 232     int endLine = tokenLine();
 233     consumeOrFail(CLOSEPAREN);
 234     const Identifier* unused = 0;
 235     startLoop();
 236     TreeStatement statement = parseStatement(context, unused);
 237     endLoop();
 238     failIfFalse(statement);
 239     return context.createWhileStatement(m_lexer->lastLineNumber(), expr, statement, startLine, endLine);
 240 }
 241
 242 template <typename LexerType>
 243 template <class TreeBuilder> TreeExpression Parser<LexerType>::parseVarDeclarationList(TreeBuilder& context, int& declarations, const Identifier*& lastIdent, TreeExpression& lastInitializer, int& identStart, int& initStart, int& initEnd)
 244 {
 245     TreeExpression varDecls = 0;
 246     do {
 247         declarations++;
 248         next();
 249         matchOrFail(IDENT);
 250
 251         int varStart = tokenStart();
 252         identStart = varStart;
 253         const Identifier* name = m_token.m_data.ident;
 254         lastIdent = name;
 255         next();
 256         bool hasInitializer = match(EQUAL);
 257         failIfFalseIfStrictWithNameAndMessage(declareVariable(name), "Cannot declare a variable named", name->impl(), "in strict mode.");
 258         context.addVar(name, (hasInitializer || (!m_allowsIn && match(INTOKEN))) ? DeclarationStacks::HasInitializer : 0);
 259         if (hasInitializer) {
 260             int varDivot = tokenStart() + 1;
 261             initStart = tokenStart();
 262             next(TreeBuilder::DontBuildStrings); // consume '='
 263             int initialAssignments = m_assignmentCount;
 264             TreeExpression initializer = parseAssignmentExpression(context);
 265             initEnd = lastTokenEnd();
 266             lastInitializer = initializer;
 267             failIfFalse(initializer);
 268
 269             TreeExpression node = context.createAssignResolve(m_lexer->lastLineNumber(), *name, initializer, initialAssignments != m_assignmentCount, varStart, varDivot, lastTokenEnd());
 270             if (!varDecls)
 271                 varDecls = node;
 272             else
 273                 varDecls = context.combineCommaNodes(m_lexer->lastLineNumber(), varDecls, node);
 274         }
 275     } while (match(COMMA));
 276     return varDecls;
 277 }
 278
 279 template <typename LexerType>
 280 template <class TreeBuilder> TreeConstDeclList Parser<LexerType>::parseConstDeclarationList(TreeBuilder& context)
 281 {
 282     failIfTrue(strictMode());
 283     TreeConstDeclList constDecls = 0;
 284     TreeConstDeclList tail = 0;
 285     do {
 286         next();
 287         matchOrFail(IDENT);
 288         const Identifier* name = m_token.m_data.ident;
 289         next();
 290         bool hasInitializer = match(EQUAL);
 291         declareVariable(name);
 292         context.addVar(name, DeclarationStacks::IsConstant | (hasInitializer ? DeclarationStacks::HasInitializer : 0));
 293         TreeExpression initializer = 0;
 294         if (hasInitializer) {
 295             next(TreeBuilder::DontBuildStrings); // consume '='
 296             initializer = parseAssignmentExpression(context);
 297         }
 298         tail = context.appendConstDecl(m_lexer->lastLineNumber(), tail, name, initializer);
 299         if (!constDecls)
 300             constDecls = tail;
 301     } while (match(COMMA));
 302     return constDecls;
 303 }
 304
 305 template <typename LexerType>
 306 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseForStatement(TreeBuilder& context)
 307 {
 308     ASSERT(match(FOR));
 309     int startLine = tokenLine();
 310     next();
 311     consumeOrFail(OPENPAREN);
 312     int nonLHSCount = m_nonLHSCount;
 313     int declarations = 0;
 314     int declsStart = 0;
 315     int declsEnd = 0;
 316     TreeExpression decls = 0;
 317     bool hasDeclaration = false;
 318     if (match(VAR)) {
 319         /*
 320          for (var IDENT in expression) statement
 321          for (var IDENT = expression in expression) statement
 322          for (var varDeclarationList; expressionOpt; expressionOpt)
 323          */
 324         hasDeclaration = true;
 325         const Identifier* forInTarget = 0;
 326         TreeExpression forInInitializer = 0;
 327         m_allowsIn = false;
 328         int initStart = 0;
 329         int initEnd = 0;
 330         decls = parseVarDeclarationList(context, declarations, forInTarget, forInInitializer, declsStart, initStart, initEnd);
 331         m_allowsIn = true;
 332         if (m_error)
 333             fail();
 334
 335         // Remainder of a standard for loop is handled identically
 336         if (match(SEMICOLON))
 337             goto standardForLoop;
 338
 339         failIfFalse(declarations == 1);
 340
 341         // Handle for-in with var declaration
 342         int inLocation = tokenStart();
 343         consumeOrFail(INTOKEN);
 344
 345         TreeExpression expr = parseExpression(context);
 346         failIfFalse(expr);
 347         int exprEnd = lastTokenEnd();
 348
 349         int endLine = tokenLine();
 350         consumeOrFail(CLOSEPAREN);
 351
 352         const Identifier* unused = 0;
 353         startLoop();
 354         TreeStatement statement = parseStatement(context, unused);
 355         endLoop();
 356         failIfFalse(statement);
 357
 358         return context.createForInLoop(m_lexer->lastLineNumber(), forInTarget, forInInitializer, expr, statement, declsStart, inLocation, exprEnd, initStart, initEnd, startLine, endLine);
 359     }
 360
 361     if (!match(SEMICOLON)) {
 362         m_allowsIn = false;
 363         declsStart = tokenStart();
 364         decls = parseExpression(context);
 365         declsEnd = lastTokenEnd();
 366         m_allowsIn = true;
 367         failIfFalse(decls);
 368     }
 369
 370     if (match(SEMICOLON)) {
 371     standardForLoop:
 372         // Standard for loop
 373         next();
 374         TreeExpression condition = 0;
 375
 376         if (!match(SEMICOLON)) {
 377             condition = parseExpression(context);
 378             failIfFalse(condition);
 379         }
 380         consumeOrFail(SEMICOLON);
 381
 382         TreeExpression increment = 0;
 383         if (!match(CLOSEPAREN)) {
 384             increment = parseExpression(context);
 385             failIfFalse(increment);
 386         }
 387         int endLine = tokenLine();
 388         consumeOrFail(CLOSEPAREN);
 389         const Identifier* unused = 0;
 390         startLoop();
 391         TreeStatement statement = parseStatement(context, unused);
 392         endLoop();
 393         failIfFalse(statement);
 394         return context.createForLoop(m_lexer->lastLineNumber(), decls, condition, increment, statement, hasDeclaration, startLine, endLine);
 395     }
 396
 397     // For-in loop
 398     failIfFalse(nonLHSCount == m_nonLHSCount);
 399     consumeOrFail(INTOKEN);
 400     TreeExpression expr = parseExpression(context);
 401     failIfFalse(expr);
 402     int exprEnd = lastTokenEnd();
 403     int endLine = tokenLine();
 404     consumeOrFail(CLOSEPAREN);
 405     const Identifier* unused = 0;
 406     startLoop();
 407     TreeStatement statement = parseStatement(context, unused);
 408     endLoop();
 409     failIfFalse(statement);
 410
 411     return context.createForInLoop(m_lexer->lastLineNumber(), decls, expr, statement, declsStart, declsEnd, exprEnd, startLine, endLine);
 412 }
 413
 414 template <typename LexerType>
 415 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseBreakStatement(TreeBuilder& context)
 416 {
 417     ASSERT(match(BREAK));
 418     int startCol = tokenStart();
 419     int endCol = tokenEnd();
 420     int startLine = tokenLine();
 421     int endLine = tokenLine();
 422     next();
 423
 424     if (autoSemiColon()) {
 425         failIfFalseWithMessage(breakIsValid(), "'break' is only valid inside a switch or loop statement");
 426         return context.createBreakStatement(m_lexer->lastLineNumber(), startCol, endCol, startLine, endLine);
 427     }
 428     matchOrFail(IDENT);
 429     const Identifier* ident = m_token.m_data.ident;
 430     failIfFalseWithNameAndMessage(getLabel(ident), "Label", ident->impl(), "is not defined");
 431     endCol = tokenEnd();
 432     endLine = tokenLine();
 433     next();
 434     failIfFalse(autoSemiColon());
 435     return context.createBreakStatement(m_lexer->lastLineNumber(), ident, startCol, endCol, startLine, endLine);
 436 }
 437
 438 template <typename LexerType>
 439 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseContinueStatement(TreeBuilder& context)
 440 {
 441     ASSERT(match(CONTINUE));
 442     int startCol = tokenStart();
 443     int endCol = tokenEnd();
 444     int startLine = tokenLine();
 445     int endLine = tokenLine();
 446     next();
 447
 448     if (autoSemiColon()) {
 449         failIfFalseWithMessage(continueIsValid(), "'continue' is only valid inside a loop statement");
 450         return context.createContinueStatement(m_lexer->lastLineNumber(), startCol, endCol, startLine, endLine);
 451     }
 452     matchOrFail(IDENT);
 453     const Identifier* ident = m_token.m_data.ident;
 454     ScopeLabelInfo* label = getLabel(ident);
 455     failIfFalseWithNameAndMessage(label, "Label", ident->impl(), "is not defined");
 456     failIfFalseWithMessage(label->m_isLoop, "'continue' is only valid inside a loop statement");
 457     endCol = tokenEnd();
 458     endLine = tokenLine();
 459     next();
 460     failIfFalse(autoSemiColon());
 461     return context.createContinueStatement(m_lexer->lastLineNumber(), ident, startCol, endCol, startLine, endLine);
 462 }
 463
 464 template <typename LexerType>
 465 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseReturnStatement(TreeBuilder& context)
 466 {
 467     ASSERT(match(RETURN));
 468     failIfFalse(currentScope()->isFunction());
 469     int startLine = tokenLine();
 470     int endLine = startLine;
 471     int start = tokenStart();
 472     int end = tokenEnd();
 473     next();
 474     // We do the auto semicolon check before attempting to parse an expression
 475     // as we need to ensure the a line break after the return correctly terminates
 476     // the statement
 477     if (match(SEMICOLON))
 478         endLine  = tokenLine();
 479     if (autoSemiColon())
 480         return context.createReturnStatement(m_lexer->lastLineNumber(), 0, start, end, startLine, endLine);
 481     TreeExpression expr = parseExpression(context);
 482     failIfFalse(expr);
 483     end = lastTokenEnd();
 484     if (match(SEMICOLON))
 485         endLine  = tokenLine();
 486     failIfFalse(autoSemiColon());
 487     return context.createReturnStatement(m_lexer->lastLineNumber(), expr, start, end, startLine, endLine);
 488 }
 489
 490 template <typename LexerType>
 491 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseThrowStatement(TreeBuilder& context)
 492 {
 493     ASSERT(match(THROW));
 494     int eStart = tokenStart();
 495     int startLine = tokenLine();
 496     next();
 497
 498     failIfTrue(autoSemiColon());
 499
 500     TreeExpression expr = parseExpression(context);
 501     failIfFalse(expr);
 502     int eEnd = lastTokenEnd();
 503     int endLine = tokenLine();
 504     failIfFalse(autoSemiColon());
 505
 506     return context.createThrowStatement(m_lexer->lastLineNumber(), expr, eStart, eEnd, startLine, endLine);
 507 }
 508
 509 template <typename LexerType>
 510 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseWithStatement(TreeBuilder& context)
 511 {
 512     ASSERT(match(WITH));
 513     failIfTrueWithMessage(strictMode(), "'with' statements are not valid in strict mode");
 514     currentScope()->setNeedsFullActivation();
 515     int startLine = tokenLine();
 516     next();
 517     consumeOrFail(OPENPAREN);
 518     int start = tokenStart();
 519     TreeExpression expr = parseExpression(context);
 520     failIfFalse(expr);
 521     int end = lastTokenEnd();
 522
 523     int endLine = tokenLine();
 524     consumeOrFail(CLOSEPAREN);
 525     const Identifier* unused = 0;
 526     TreeStatement statement = parseStatement(context, unused);
 527     failIfFalse(statement);
 528
 529     return context.createWithStatement(m_lexer->lastLineNumber(), expr, statement, start, end, startLine, endLine);
 530 }
 531
 532 template <typename LexerType>
 533 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseSwitchStatement(TreeBuilder& context)
 534 {
 535     ASSERT(match(SWITCH));
 536     int startLine = tokenLine();
 537     next();
 538     consumeOrFail(OPENPAREN);
 539     TreeExpression expr = parseExpression(context);
 540     failIfFalse(expr);
 541     int endLine = tokenLine();
 542     consumeOrFail(CLOSEPAREN);
 543     consumeOrFail(OPENBRACE);
 544     startSwitch();
 545     TreeClauseList firstClauses = parseSwitchClauses(context);
 546     failIfTrue(m_error);
 547
 548     TreeClause defaultClause = parseSwitchDefaultClause(context);
 549     failIfTrue(m_error);
 550
 551     TreeClauseList secondClauses = parseSwitchClauses(context);
 552     failIfTrue(m_error);
 553     endSwitch();
 554     consumeOrFail(CLOSEBRACE);
 555
 556     return context.createSwitchStatement(m_lexer->lastLineNumber(), expr, firstClauses, defaultClause, secondClauses, startLine, endLine);
 557
 558 }
 559
 560 template <typename LexerType>
 561 template <class TreeBuilder> TreeClauseList Parser<LexerType>::parseSwitchClauses(TreeBuilder& context)
 562 {
 563     if (!match(CASE))
 564         return 0;
 565     next();
 566     TreeExpression condition = parseExpression(context);
 567     failIfFalse(condition);
 568     consumeOrFail(COLON);
 569     TreeSourceElements statements = parseSourceElements<DontCheckForStrictMode>(context);
 570     failIfFalse(statements);
 571     TreeClause clause = context.createClause(condition, statements);
 572     TreeClauseList clauseList = context.createClauseList(clause);
 573     TreeClauseList tail = clauseList;
 574
 575     while (match(CASE)) {
 576         next();
 577         TreeExpression condition = parseExpression(context);
 578         failIfFalse(condition);
 579         consumeOrFail(COLON);
 580         TreeSourceElements statements = parseSourceElements<DontCheckForStrictMode>(context);
 581         failIfFalse(statements);
 582         clause = context.createClause(condition, statements);
 583         tail = context.createClauseList(tail, clause);
 584     }
 585     return clauseList;
 586 }
 587
 588 template <typename LexerType>
 589 template <class TreeBuilder> TreeClause Parser<LexerType>::parseSwitchDefaultClause(TreeBuilder& context)
 590 {
 591     if (!match(DEFAULT))
 592         return 0;
 593     next();
 594     consumeOrFail(COLON);
 595     TreeSourceElements statements = parseSourceElements<DontCheckForStrictMode>(context);
 596     failIfFalse(statements);
 597     return context.createClause(0, statements);
 598 }
 599
 600 template <typename LexerType>
 601 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseTryStatement(TreeBuilder& context)
 602 {
 603     ASSERT(match(TRY));
 604     TreeStatement tryBlock = 0;
 605     const Identifier* ident = &m_globalData->propertyNames->nullIdentifier;
 606     TreeStatement catchBlock = 0;
 607     TreeStatement finallyBlock = 0;
 608     int firstLine = tokenLine();
 609     next();
 610     matchOrFail(OPENBRACE);
 611
 612     tryBlock = parseBlockStatement(context);
 613     failIfFalse(tryBlock);
 614     int lastLine = m_lastLine;
 615
 616     if (match(CATCH)) {
 617         currentScope()->setNeedsFullActivation();
 618         next();
 619         consumeOrFail(OPENPAREN);
 620         matchOrFail(IDENT);
 621         ident = m_token.m_data.ident;
 622         next();
 623         AutoPopScopeRef catchScope(this, pushScope());
 624         failIfFalseIfStrictWithNameAndMessage(declareVariable(ident), "Cannot declare a variable named", ident->impl(), "in strict mode");
 625         catchScope->preventNewDecls();
 626         consumeOrFail(CLOSEPAREN);
 627         matchOrFail(OPENBRACE);
 628         catchBlock = parseBlockStatement(context);
 629         failIfFalseWithMessage(catchBlock, "'try' must have a catch or finally block");
 630         failIfFalse(popScope(catchScope, TreeBuilder::NeedsFreeVariableInfo));
 631     }
 632
 633     if (match(FINALLY)) {
 634         next();
 635         matchOrFail(OPENBRACE);
 636         finallyBlock = parseBlockStatement(context);
 637         failIfFalse(finallyBlock);
 638     }
 639     failIfFalse(catchBlock || finallyBlock);
 640     return context.createTryStatement(m_lexer->lastLineNumber(), tryBlock, ident, catchBlock, finallyBlock, firstLine, lastLine);
 641 }
 642
 643 template <typename LexerType>
 644 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseDebuggerStatement(TreeBuilder& context)
 645 {
 646     ASSERT(match(DEBUGGER));
 647     int startLine = tokenLine();
 648     int endLine = startLine;
 649     next();
 650     if (match(SEMICOLON))
 651         startLine = tokenLine();
 652     failIfFalse(autoSemiColon());
 653     return context.createDebugger(m_lexer->lastLineNumber(), startLine, endLine);
 654 }
 655
 656 template <typename LexerType>
 657 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseBlockStatement(TreeBuilder& context)
 658 {
 659     ASSERT(match(OPENBRACE));
 660     int start = tokenLine();
 661     next();
 662     if (match(CLOSEBRACE)) {
 663         next();
 664         return context.createBlockStatement(m_lexer->lastLineNumber(), 0, start, m_lastLine);
 665     }
 666     TreeSourceElements subtree = parseSourceElements<DontCheckForStrictMode>(context);
 667     failIfFalse(subtree);
 668     matchOrFail(CLOSEBRACE);
 669     next();
 670     return context.createBlockStatement(m_lexer->lastLineNumber(), subtree, start, m_lastLine);
 671 }
 672
 673 template <typename LexerType>
 674 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseStatement(TreeBuilder& context, const Identifier*& directive, unsigned* directiveLiteralLength)
 675 {
 676     DepthManager statementDepth(&m_statementDepth);
 677     m_statementDepth++;
 678     directive = 0;
 679     int nonTrivialExpressionCount = 0;
 680     failIfStackOverflow();
 681     switch (m_token.m_type) {
 682     case OPENBRACE:
 683         return parseBlockStatement(context);
 684     case VAR:
 685         return parseVarDeclaration(context);
 686     case CONSTTOKEN:
 687         return parseConstDeclaration(context);
 688     case FUNCTION:
 689         failIfFalseIfStrictWithMessage(m_statementDepth == 1, "Functions cannot be declared in a nested block in strict mode");
 690         return parseFunctionDeclaration(context);
 691     case SEMICOLON:
 692         next();
 693         return context.createEmptyStatement(m_lexer->lastLineNumber());
 694     case IF:
 695         return parseIfStatement(context);
 696     case DO:
 697         return parseDoWhileStatement(context);
 698     case WHILE:
 699         return parseWhileStatement(context);
 700     case FOR:
 701         return parseForStatement(context);
 702     case CONTINUE:
 703         return parseContinueStatement(context);
 704     case BREAK:
 705         return parseBreakStatement(context);
 706     case RETURN:
 707         return parseReturnStatement(context);
 708     case WITH:
 709         return parseWithStatement(context);
 710     case SWITCH:
 711         return parseSwitchStatement(context);
 712     case THROW:
 713         return parseThrowStatement(context);
 714     case TRY:
 715         return parseTryStatement(context);
 716     case DEBUGGER:
 717         return parseDebuggerStatement(context);
 718     case EOFTOK:
 719     case CASE:
 720     case CLOSEBRACE:
 721     case DEFAULT:
 722         // These tokens imply the end of a set of source elements
 723         return 0;
 724     case IDENT:
 725         return parseExpressionOrLabelStatement(context);
 726     case STRING:
 727         directive = m_token.m_data.ident;
 728         if (directiveLiteralLength)
 729             *directiveLiteralLength = m_token.m_info.endOffset - m_token.m_info.startOffset;
 730         nonTrivialExpressionCount = m_nonTrivialExpressionCount;
 731     default:
 732         TreeStatement exprStatement = parseExpressionStatement(context);
 733         if (directive && nonTrivialExpressionCount != m_nonTrivialExpressionCount)
 734             directive = 0;
 735         return exprStatement;
 736     }
 737 }
 738
 739 template <typename LexerType>
 740 template <class TreeBuilder> TreeFormalParameterList Parser<LexerType>::parseFormalParameters(TreeBuilder& context)
 741 {
 742     matchOrFail(IDENT);
 743     failIfFalseIfStrictWithNameAndMessage(declareParameter(m_token.m_data.ident), "Cannot declare a parameter named", m_token.m_data.ident->impl(), " in strict mode");
 744     TreeFormalParameterList list = context.createFormalParameterList(*m_token.m_data.ident);
 745     TreeFormalParameterList tail = list;
 746     next();
 747     while (match(COMMA)) {
 748         next();
 749         matchOrFail(IDENT);
 750         const Identifier* ident = m_token.m_data.ident;
 751         failIfFalseIfStrictWithNameAndMessage(declareParameter(ident), "Cannot declare a parameter named", ident->impl(), "in strict mode");
 752         next();
 753         tail = context.createFormalParameterList(tail, *ident);
 754     }
 755     return list;
 756 }
 757
 758 template <typename LexerType>
 759 template <class TreeBuilder> TreeFunctionBody Parser<LexerType>::parseFunctionBody(TreeBuilder& context)
 760 {
 761     if (match(CLOSEBRACE))
 762         return context.createFunctionBody(m_lexer->lastLineNumber(), strictMode());
 763     DepthManager statementDepth(&m_statementDepth);
 764     m_statementDepth = 0;
 765     typename TreeBuilder::FunctionBodyBuilder bodyBuilder(const_cast<JSGlobalData*>(m_globalData), m_lexer.get());
 766     failIfFalse(parseSourceElements<CheckForStrictMode>(bodyBuilder));
 767     return context.createFunctionBody(m_lexer->lastLineNumber(), strictMode());
 768 }
 769
 770 template <typename LexerType>
 771 template <FunctionRequirements requirements, bool nameIsInContainingScope, class TreeBuilder> bool Parser<LexerType>::parseFunctionInfo(TreeBuilder& context, const Identifier*& name, TreeFormalParameterList& parameters, TreeFunctionBody& body, int& openBracePos, int& closeBracePos, int& bodyStartLine)
 772 {
 773     AutoPopScopeRef functionScope(this, pushScope());
 774     functionScope->setIsFunction();
 775     if (match(IDENT)) {
 776         name = m_token.m_data.ident;
 777         next();
 778         if (!nameIsInContainingScope)
 779             failIfFalseIfStrict(functionScope->declareVariable(name));
 780     } else if (requirements == FunctionNeedsName)
 781         return false;
 782     consumeOrFail(OPENPAREN);
 783     if (!match(CLOSEPAREN)) {
 784         parameters = parseFormalParameters(context);
 785         failIfFalse(parameters);
 786     }
 787     consumeOrFail(CLOSEPAREN);
 788     matchOrFail(OPENBRACE);
 789
 790     openBracePos = m_token.m_data.intValue;
 791     bodyStartLine = tokenLine();
 792
 793     // If we know about this function already, we can use the cached info and skip the parser to the end of the function.
 794     if (const SourceProviderCacheItem* cachedInfo = TreeBuilder::CanUseFunctionCache ? findCachedFunctionInfo(openBracePos) : 0) {
 795         // If we're in a strict context, the cached function info must say it was strict too.
 796         ASSERT(!strictMode() || cachedInfo->strictMode);
 797         body = context.createFunctionBody(m_lexer->lastLineNumber(), cachedInfo->strictMode);
 798
 799         functionScope->restoreFunctionInfo(cachedInfo);
 800         failIfFalse(popScope(functionScope, TreeBuilder::NeedsFreeVariableInfo));
 801
 802         closeBracePos = cachedInfo->closeBracePos;
 803         m_token = cachedInfo->closeBraceToken();
 804         m_lexer->setOffset(m_token.m_info.endOffset);
 805         m_lexer->setLineNumber(m_token.m_info.line);
 806
 807         next();
 808         return true;
 809     }
 810
 811     next();
 812
 813     body = parseFunctionBody(context);
 814     failIfFalse(body);
 815     if (functionScope->strictMode() && name) {
 816         failIfTrueWithNameAndMessage(m_globalData->propertyNames->arguments == *name, "Function name", name->impl(), "is not valid in strict mode");
 817         failIfTrueWithNameAndMessage(m_globalData->propertyNames->eval == *name, "Function name", name->impl(), "is not valid in strict mode");
 818     }
 819     closeBracePos = m_token.m_data.intValue;
 820
 821     // Cache the tokenizer state and the function scope the first time the function is parsed.
 822     // Any future reparsing can then skip the function.
 823     static const int minimumFunctionLengthToCache = 64;
 824     OwnPtr<SourceProviderCacheItem> newInfo;
 825     int functionLength = closeBracePos - openBracePos;
 826     if (TreeBuilder::CanUseFunctionCache && m_functionCache && functionLength > minimumFunctionLengthToCache) {
 827         newInfo = adoptPtr(new SourceProviderCacheItem(m_token.m_info.line, closeBracePos));
 828         functionScope->saveFunctionInfo(newInfo.get());
 829     }
 830
 831     failIfFalse(popScope(functionScope, TreeBuilder::NeedsFreeVariableInfo));
 832     matchOrFail(CLOSEBRACE);
 833
 834     if (newInfo) {
 835         unsigned approximateByteSize = newInfo->approximateByteSize();
 836         m_functionCache->add(openBracePos, newInfo.release(), approximateByteSize);
 837     }
 838
 839     next();
 840     return true;
 841 }
 842
 843 template <typename LexerType>
 844 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseFunctionDeclaration(TreeBuilder& context)
 845 {
 846     ASSERT(match(FUNCTION));
 847     next();
 848     const Identifier* name = 0;
 849     TreeFormalParameterList parameters = 0;
 850     TreeFunctionBody body = 0;
 851     int openBracePos = 0;
 852     int closeBracePos = 0;
 853     int bodyStartLine = 0;
 854     failIfFalse((parseFunctionInfo<FunctionNeedsName, true>(context, name, parameters, body, openBracePos, closeBracePos, bodyStartLine)));
 855     failIfFalse(name);
 856     failIfFalseIfStrict(declareVariable(name));
 857     return context.createFuncDeclStatement(m_lexer->lastLineNumber(), name, body, parameters, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
 858 }
 859
 860 struct LabelInfo {
 861     LabelInfo(const Identifier* ident, int start, int end)
 862     : m_ident(ident)
 863     , m_start(start)
 864     , m_end(end)
 865     {
 866     }
 867
 868     const Identifier* m_ident;
 869     int m_start;
 870     int m_end;
 871 };
 872
 873 template <typename LexerType>
 874 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseExpressionOrLabelStatement(TreeBuilder& context)
 875 {
 876
 877     /* Expression and Label statements are ambiguous at LL(1), so we have a
 878      * special case that looks for a colon as the next character in the input.
 879      */
 880     Vector<LabelInfo> labels;
 881
 882     do {
 883         int start = tokenStart();
 884         int startLine = tokenLine();
 885         if (!nextTokenIsColon()) {
 886             // If we hit this path we're making a expression statement, which
 887             // by definition can't make use of continue/break so we can just
 888             // ignore any labels we might have accumulated.
 889             TreeExpression expression = parseExpression(context);
 890             failIfFalse(expression);
 891             failIfFalse(autoSemiColon());
 892             return context.createExprStatement(m_lexer->lastLineNumber(), expression, startLine, m_lastLine);
 893         }
 894         const Identifier* ident = m_token.m_data.ident;
 895         int end = tokenEnd();
 896         next();
 897         consumeOrFail(COLON);
 898         if (!m_syntaxAlreadyValidated) {
 899             // This is O(N^2) over the current list of consecutive labels, but I
 900             // have never seen more than one label in a row in the real world.
 901             for (size_t i = 0; i < labels.size(); i++)
 902                 failIfTrue(ident->impl() == labels[i].m_ident->impl());
 903             failIfTrue(getLabel(ident));
 904             labels.append(LabelInfo(ident, start, end));
 905         }
 906     } while (match(IDENT));
 907     bool isLoop = false;
 908     switch (m_token.m_type) {
 909     case FOR:
 910     case WHILE:
 911     case DO:
 912         isLoop = true;
 913         break;
 914
 915     default:
 916         break;
 917     }
 918     const Identifier* unused = 0;
 919     if (!m_syntaxAlreadyValidated) {
 920         for (size_t i = 0; i < labels.size(); i++)
 921             pushLabel(labels[i].m_ident, isLoop);
 922     }
 923     TreeStatement statement = parseStatement(context, unused);
 924     if (!m_syntaxAlreadyValidated) {
 925         for (size_t i = 0; i < labels.size(); i++)
 926             popLabel();
 927     }
 928     failIfFalse(statement);
 929     for (size_t i = 0; i < labels.size(); i++) {
 930         const LabelInfo& info = labels[labels.size() - i - 1];
 931         statement = context.createLabelStatement(m_lexer->lastLineNumber(), info.m_ident, statement, info.m_start, info.m_end);
 932     }
 933     return statement;
 934 }
 935
 936 template <typename LexerType>
 937 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseExpressionStatement(TreeBuilder& context)
 938 {
 939     int startLine = tokenLine();
 940     TreeExpression expression = parseExpression(context);
 941     failIfFalse(expression);
 942     failIfFalse(autoSemiColon());
 943     return context.createExprStatement(m_lexer->lastLineNumber(), expression, startLine, m_lastLine);
 944 }
 945
 946 template <typename LexerType>
 947 template <class TreeBuilder> TreeStatement Parser<LexerType>::parseIfStatement(TreeBuilder& context)
 948 {
 949     ASSERT(match(IF));
 950
 951     int start = tokenLine();
 952     next();
 953
 954     consumeOrFail(OPENPAREN);
 955
 956     TreeExpression condition = parseExpression(context);
 957     failIfFalse(condition);
 958     int end = tokenLine();
 959     consumeOrFail(CLOSEPAREN);
 960
 961     const Identifier* unused = 0;
 962     TreeStatement trueBlock = parseStatement(context, unused);
 963     failIfFalse(trueBlock);
 964
 965     if (!match(ELSE))
 966         return context.createIfStatement(m_lexer->lastLineNumber(), condition, trueBlock, start, end);
 967
 968     Vector<TreeExpression> exprStack;
 969     Vector<pair<int, int> > posStack;
 970     Vector<TreeStatement> statementStack;
 971     bool trailingElse = false;
 972     do {
 973         next();
 974         if (!match(IF)) {
 975             const Identifier* unused = 0;
 976             TreeStatement block = parseStatement(context, unused);
 977             failIfFalse(block);
 978             statementStack.append(block);
 979             trailingElse = true;
 980             break;
 981         }
 982         int innerStart = tokenLine();
 983         next();
 984
 985         consumeOrFail(OPENPAREN);
 986
 987         TreeExpression innerCondition = parseExpression(context);
 988         failIfFalse(innerCondition);
 989         int innerEnd = tokenLine();
 990         consumeOrFail(CLOSEPAREN);
 991         const Identifier* unused = 0;
 992         TreeStatement innerTrueBlock = parseStatement(context, unused);
 993         failIfFalse(innerTrueBlock);
 994         exprStack.append(innerCondition);
 995         posStack.append(make_pair(innerStart, innerEnd));
 996         statementStack.append(innerTrueBlock);
 997     } while (match(ELSE));
 998
 999     if (!trailingElse) {
1000         TreeExpression condition = exprStack.last();
1001         exprStack.removeLast();
1002         TreeStatement trueBlock = statementStack.last();
1003         statementStack.removeLast();
1004         pair<int, int> pos = posStack.last();
1005         posStack.removeLast();
1006         statementStack.append(context.createIfStatement(m_lexer->lastLineNumber(), condition, trueBlock, pos.first, pos.second));
1007     }
1008
1009     while (!exprStack.isEmpty()) {
1010         TreeExpression condition = exprStack.last();
1011         exprStack.removeLast();
1012         TreeStatement falseBlock = statementStack.last();
1013         statementStack.removeLast();
1014         TreeStatement trueBlock = statementStack.last();
1015         statementStack.removeLast();
1016         pair<int, int> pos = posStack.last();
1017         posStack.removeLast();
1018         statementStack.append(context.createIfStatement(m_lexer->lastLineNumber(), condition, trueBlock, falseBlock, pos.first, pos.second));
1019     }
1020
1021     return context.createIfStatement(m_lexer->lastLineNumber(), condition, trueBlock, statementStack.last(), start, end);
1022 }
1023
1024 template <typename LexerType>
1025 template <class TreeBuilder> TreeExpression Parser<LexerType>::parseExpression(TreeBuilder& context)
1026 {
1027     failIfStackOverflow();
1028     TreeExpression node = parseAssignmentExpression(context);
1029     failIfFalse(node);
1030     if (!match(COMMA))
1031         return node;
1032     next();
1033     m_nonTrivialExpressionCount++;
1034     m_nonLHSCount++;
1035     TreeExpression right = parseAssignmentExpression(context);
1036     failIfFalse(right);
1037     typename TreeBuilder::Comma commaNode = context.createCommaExpr(m_lexer->lastLineNumber(), node, right);
1038     while (match(COMMA)) {
1039         next(TreeBuilder::DontBuildStrings);
1040         right = parseAssignmentExpression(context);
1041         failIfFalse(right);
1042         context.appendToComma(commaNode, right);
1043     }
1044     return commaNode;
1045 }
1046
1047 template <typename LexerType>
1048 template <typename TreeBuilder> TreeExpression Parser<LexerType>::parseAssignmentExpression(TreeBuilder& context)
1049 {
1050     failIfStackOverflow();
1051     int start = tokenStart();
1052     int initialAssignmentCount = m_assignmentCount;
1053     int initialNonLHSCount = m_nonLHSCount;
1054     TreeExpression lhs = parseConditionalExpression(context);
1055     failIfFalse(lhs);
1056     if (initialNonLHSCount != m_nonLHSCount)
1057         return lhs;
1058
1059     int assignmentStack = 0;
1060     Operator op;
1061     bool hadAssignment = false;
1062     while (true) {
1063         switch (m_token.m_type) {
1064         case EQUAL: op = OpEqual; break;
1065         case PLUSEQUAL: op = OpPlusEq; break;
1066         case MINUSEQUAL: op = OpMinusEq; break;
1067         case MULTEQUAL: op = OpMultEq; break;
1068         case DIVEQUAL: op = OpDivEq; break;
1069         case LSHIFTEQUAL: op = OpLShift; break;
1070         case RSHIFTEQUAL: op = OpRShift; break;
1071         case URSHIFTEQUAL: op = OpURShift; break;
1072         case ANDEQUAL: op = OpAndEq; break;
1073         case XOREQUAL: op = OpXOrEq; break;
1074         case OREQUAL: op = OpOrEq; break;
1075         case MODEQUAL: op = OpModEq; break;
1076         default:
1077             goto end;
1078         }
1079         m_nonTrivialExpressionCount++;
1080         hadAssignment = true;
1081         context.assignmentStackAppend(assignmentStack, lhs, start, tokenStart(), m_assignmentCount, op);
1082         start = tokenStart();
1083         m_assignmentCount++;
1084         next(TreeBuilder::DontBuildStrings);
1085         if (strictMode() && m_lastIdentifier && context.isResolve(lhs)) {
1086             failIfTrueIfStrictWithMessage(m_globalData->propertyNames->eval == *m_lastIdentifier, "'eval' cannot be modified in strict mode");
1087             failIfTrueIfStrictWithMessage(m_globalData->propertyNames->arguments == *m_lastIdentifier, "'arguments' cannot be modified in strict mode");
1088             declareWrite(m_lastIdentifier);
1089             m_lastIdentifier = 0;
1090         }
1091         lhs = parseConditionalExpression(context);
1092         failIfFalse(lhs);
1093         if (initialNonLHSCount != m_nonLHSCount)
1094             break;
1095     }
1096 end:
1097     if (hadAssignment)
1098         m_nonLHSCount++;
1099
1100     if (!TreeBuilder::CreatesAST)
1101         return lhs;
1102
1103     while (assignmentStack)
1104         lhs = context.createAssignment(m_lexer->lastLineNumber(), assignmentStack, lhs, initialAssignmentCount, m_assignmentCount, lastTokenEnd());
1105
1106     return lhs;
1107 }
1108
1109 template <typename LexerType>
1110 template <class TreeBuilder> TreeExpression Parser<LexerType>::parseConditionalExpression(TreeBuilder& context)
1111 {
1112     TreeExpression cond = parseBinaryExpression(context);
1113     failIfFalse(cond);
1114     if (!match(QUESTION))
1115         return cond;
1116     m_nonTrivialExpressionCount++;
1117     m_nonLHSCount++;
1118     next(TreeBuilder::DontBuildStrings);
1119     TreeExpression lhs = parseAssignmentExpression(context);
1120     consumeOrFailWithFlags(COLON, TreeBuilder::DontBuildStrings);
1121
1122     TreeExpression rhs = parseAssignmentExpression(context);
1123     failIfFalse(rhs);
1124     return context.createConditionalExpr(m_lexer->lastLineNumber(), cond, lhs, rhs);
1125 }
1126
1127 ALWAYS_INLINE static bool isUnaryOp(JSTokenType token)
1128 {
1129     return token & UnaryOpTokenFlag;
1130 }
1131
1132 template <typename LexerType>
1133 int Parser<LexerType>::isBinaryOperator(JSTokenType token)
1134 {
1135     if (m_allowsIn)
1136         return token & (BinaryOpTokenPrecedenceMask << BinaryOpTokenAllowsInPrecedenceAdditionalShift);
1137     return token & BinaryOpTokenPrecedenceMask;
1138 }
1139
1140 template <typename LexerType>
1141 template <class TreeBuilder> TreeExpression Parser<LexerType>::parseBinaryExpression(TreeBuilder& context)
1142 {
1143
1144     int operandStackDepth = 0;
1145     int operatorStackDepth = 0;
1146     typename TreeBuilder::BinaryExprContext binaryExprContext(context);
1147     while (true) {
1148         int exprStart = tokenStart();
1149         int initialAssignments = m_assignmentCount;
1150         TreeExpression current = parseUnaryExpression(context);
1151         failIfFalse(current);
1152
1153         context.appendBinaryExpressionInfo(operandStackDepth, current, exprStart, lastTokenEnd(), lastTokenEnd(), initialAssignments != m_assignmentCount);
1154         int precedence = isBinaryOperator(m_token.m_type);
1155         if (!precedence)
1156             break;
1157         m_nonTrivialExpressionCount++;
1158         m_nonLHSCount++;
1159         int operatorToken = m_token.m_type;
1160         next(TreeBuilder::DontBuildStrings);
1161
1162         while (operatorStackDepth &&  context.operatorStackHasHigherPrecedence(operatorStackDepth, precedence)) {
1163             ASSERT(operandStackDepth > 1);
1164
1165             typename TreeBuilder::BinaryOperand rhs = context.getFromOperandStack(-1);
1166             typename TreeBuilder::BinaryOperand lhs = context.getFromOperandStack(-2);
1167             context.shrinkOperandStackBy(operandStackDepth, 2);
1168             context.appendBinaryOperation(m_lexer->lastLineNumber(), operandStackDepth, operatorStackDepth, lhs, rhs);
1169             context.operatorStackPop(operatorStackDepth);
1170         }
1171         context.operatorStackAppend(operatorStackDepth, operatorToken, precedence);
1172     }
1173     while (operatorStackDepth) {
1174         ASSERT(operandStackDepth > 1);
1175
1176         typename TreeBuilder::BinaryOperand rhs = context.getFromOperandStack(-1);
1177         typename TreeBuilder::BinaryOperand lhs = context.getFromOperandStack(-2);
1178         context.shrinkOperandStackBy(operandStackDepth, 2);
1179         context.appendBinaryOperation(m_lexer->lastLineNumber(), operandStackDepth, operatorStackDepth, lhs, rhs);
1180         context.operatorStackPop(operatorStackDepth);
1181     }
1182     return context.popOperandStack(operandStackDepth);
1183 }
1184
1185 template <typename LexerType>
1186 template <bool complete, class TreeBuilder> TreeProperty Parser<LexerType>::parseProperty(TreeBuilder& context)
1187 {
1188     bool wasIdent = false;
1189     switch (m_token.m_type) {
1190     namedProperty:
1191     case IDENT:
1192         wasIdent = true;
1193     case STRING: {
1194         const Identifier* ident = m_token.m_data.ident;
1195         if (complete || (wasIdent && (*ident == m_globalData->propertyNames->get || *ident == m_globalData->propertyNames->set)))
1196             nextExpectIdentifier(LexerFlagsIgnoreReservedWords);
1197         else
1198             nextExpectIdentifier(LexerFlagsIgnoreReservedWords | TreeBuilder::DontBuildKeywords);
1199
1200         if (match(COLON)) {
1201             next();
1202             TreeExpression node = parseAssignmentExpression(context);
1203             failIfFalse(node);
1204             return context.template createProperty<complete>(ident, node, PropertyNode::Constant);
1205         }
1206         failIfFalse(wasIdent);
1207         const Identifier* accessorName = 0;
1208         TreeFormalParameterList parameters = 0;
1209         TreeFunctionBody body = 0;
1210         int openBracePos = 0;
1211         int closeBracePos = 0;
1212         int bodyStartLine = 0;
1213         PropertyNode::Type type;
1214         if (*ident == m_globalData->propertyNames->get)
1215             type = PropertyNode::Getter;
1216         else if (*ident == m_globalData->propertyNames->set)
1217             type = PropertyNode::Setter;
1218         else
1219             fail();
1220         const Identifier* stringPropertyName = 0;
1221         double numericPropertyName = 0;
1222         if (m_token.m_type == IDENT || m_token.m_type == STRING)
1223             stringPropertyName = m_token.m_data.ident;
1224         else if (m_token.m_type == NUMBER)
1225             numericPropertyName = m_token.m_data.doubleValue;
1226         else
1227             fail();
1228         next();
1229         failIfFalse((parseFunctionInfo<FunctionNoRequirements, false>(context, accessorName, parameters, body, openBracePos, closeBracePos, bodyStartLine)));
1230         if (stringPropertyName)
1231             return context.template createGetterOrSetterProperty<complete>(m_lexer->lastLineNumber(), type, stringPropertyName, parameters, body, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
1232         return context.template createGetterOrSetterProperty<complete>(const_cast<JSGlobalData*>(m_globalData), m_lexer->lastLineNumber(), type, numericPropertyName, parameters, body, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
1233     }
1234     case NUMBER: {
1235         double propertyName = m_token.m_data.doubleValue;
1236         next();
1237         consumeOrFail(COLON);
1238         TreeExpression node = parseAssignmentExpression(context);
1239         failIfFalse(node);
1240         return context.template createProperty<complete>(const_cast<JSGlobalData*>(m_globalData), propertyName, node, PropertyNode::Constant);
1241     }
1242     default:
1243         failIfFalse(m_token.m_type & KeywordTokenFlag);
1244         goto namedProperty;
1245     }
1246 }
1247
1248 template <typename LexerType>
1249 template <class TreeBuilder> TreeExpression Parser<LexerType>::parseObjectLiteral(TreeBuilder& context)
1250 {
1251     int startOffset = m_token.m_data.intValue;
1252     unsigned oldLastLineNumber = m_lexer->lastLineNumber();
1253     unsigned oldLineNumber = m_lexer->lineNumber();
1254     consumeOrFailWithFlags(OPENBRACE, TreeBuilder::DontBuildStrings);
1255
1256     int oldNonLHSCount = m_nonLHSCount;
1257
1258     if (match(CLOSEBRACE)) {
1259         next();
1260         return context.createObjectLiteral(m_lexer->lastLineNumber());
1261     }
1262
1263     TreeProperty property = parseProperty<false>(context);
1264     failIfFalse(property);
1265     if (!m_syntaxAlreadyValidated && context.getType(property) != PropertyNode::Constant) {
1266         m_lexer->setOffset(startOffset);
1267         next();
1268         m_lexer->setLastLineNumber(oldLastLineNumber);
1269         m_lexer->setLineNumber(oldLineNumber);
1270         return parseStrictObjectLiteral(context);
1271     }
1272     TreePropertyList propertyList = context.createPropertyList(m_lexer->lastLineNumber(), property);
1273     TreePropertyList tail = propertyList;
1274     while (match(COMMA)) {
1275         next(TreeBuilder::DontBuildStrings);
1276         // allow extra comma, see http://bugs.webkit.org/show_bug.cgi?id=5939
1277         if (match(CLOSEBRACE))
1278             break;
1279         property = parseProperty<false>(context);
1280         failIfFalse(property);
1281         if (!m_syntaxAlreadyValidated && context.getType(property) != PropertyNode::Constant) {
1282             m_lexer->setOffset(startOffset);
1283             next();
1284             m_lexer->setLastLineNumber(oldLastLineNumber);
1285             m_lexer->setLineNumber(oldLineNumber);
1286             return parseStrictObjectLiteral(context);
1287         }
1288         tail = context.createPropertyList(m_lexer->lastLineNumber(), property, tail);
1289     }
1290
1291     consumeOrFail(CLOSEBRACE);
1292
1293     m_nonLHSCount = oldNonLHSCount;
1294
1295     return context.createObjectLiteral(m_lexer->lastLineNumber(), propertyList);
1296 }
1297
1298 template <typename LexerType>
1299 template <class TreeBuilder> TreeExpression Parser<LexerType>::parseStrictObjectLiteral(TreeBuilder& context)
1300 {
1301     consumeOrFail(OPENBRACE);
1302
1303     int oldNonLHSCount = m_nonLHSCount;
1304
1305     if (match(CLOSEBRACE)) {
1306         next();
1307         return context.createObjectLiteral(m_lexer->lastLineNumber());
1308     }
1309
1310     TreeProperty property = parseProperty<true>(context);
1311     failIfFalse(property);
1312
1313     typedef HashMap<RefPtr<StringImpl>, unsigned, IdentifierRepHash> ObjectValidationMap;
1314     ObjectValidationMap objectValidator;
1315     // Add the first property
1316     if (!m_syntaxAlreadyValidated)
1317         objectValidator.add(context.getName(property).impl(), context.getType(property));
1318
1319     TreePropertyList propertyList = context.createPropertyList(m_lexer->lastLineNumber(), property);
1320     TreePropertyList tail = propertyList;
1321     while (match(COMMA)) {
1322         next();
1323         // allow extra comma, see http://bugs.webkit.org/show_bug.cgi?id=5939
1324         if (match(CLOSEBRACE))
1325             break;
1326         property = parseProperty<true>(context);
1327         failIfFalse(property);
1328         if (!m_syntaxAlreadyValidated) {
1329             ObjectValidationMap::AddResult propertyEntry = objectValidator.add(context.getName(property).impl(), context.getType(property));
1330             if (!propertyEntry.isNewEntry) {
1331                 failIfTrue(propertyEntry.iterator->second == PropertyNode::Constant);
1332                 failIfTrue(context.getType(property) == PropertyNode::Constant);
1333                 failIfTrue(context.getType(property) & propertyEntry.iterator->second);
1334                 propertyEntry.iterator->second |= context.getType(property);
1335             }
1336         }
1337         tail = context.createPropertyList(m_lexer->lastLineNumber(), property, tail);
1338     }
1339
1340     consumeOrFail(CLOSEBRACE);
1341
1342     m_nonLHSCount = oldNonLHSCount;
1343
1344     return context.createObjectLiteral(m_lexer->lastLineNumber(), propertyList);
1345 }
1346
1347 template <typename LexerType>
1348 template <class TreeBuilder> TreeExpression Parser<LexerType>::parseArrayLiteral(TreeBuilder& context)
1349 {
1350     consumeOrFailWithFlags(OPENBRACKET, TreeBuilder::DontBuildStrings);
1351
1352     int oldNonLHSCount = m_nonLHSCount;
1353
1354     int elisions = 0;
1355     while (match(COMMA)) {
1356         next(TreeBuilder::DontBuildStrings);
1357         elisions++;
1358     }
1359     if (match(CLOSEBRACKET)) {
1360         next(TreeBuilder::DontBuildStrings);
1361         return context.createArray(m_lexer->lastLineNumber(), elisions);
1362     }
1363
1364     TreeExpression elem = parseAssignmentExpression(context);
1365     failIfFalse(elem);
1366     typename TreeBuilder::ElementList elementList = context.createElementList(elisions, elem);
1367     typename TreeBuilder::ElementList tail = elementList;
1368     elisions = 0;
1369     while (match(COMMA)) {
1370         next(TreeBuilder::DontBuildStrings);
1371         elisions = 0;
1372
1373         while (match(COMMA)) {
1374             next();
1375             elisions++;
1376         }
1377
1378         if (match(CLOSEBRACKET)) {
1379             next(TreeBuilder::DontBuildStrings);
1380             return context.createArray(m_lexer->lastLineNumber(), elisions, elementList);
1381         }
1382         TreeExpression elem = parseAssignmentExpression(context);
1383         failIfFalse(elem);
1384         tail = context.createElementList(tail, elisions, elem);
1385     }
1386
1387     consumeOrFail(CLOSEBRACKET);
1388
1389     m_nonLHSCount = oldNonLHSCount;
1390
1391     return context.createArray(m_lexer->lastLineNumber(), elementList);
1392 }
1393
1394 template <typename LexerType>
1395 template <class TreeBuilder> TreeExpression Parser<LexerType>::parsePrimaryExpression(TreeBuilder& context)
1396 {
1397     failIfStackOverflow();
1398     switch (m_token.m_type) {
1399     case OPENBRACE:
1400         if (strictMode())
1401             return parseStrictObjectLiteral(context);
1402         return parseObjectLiteral(context);
1403     case OPENBRACKET:
1404         return parseArrayLiteral(context);
1405     case OPENPAREN: {
1406         next();
1407         int oldNonLHSCount = m_nonLHSCount;
1408         TreeExpression result = parseExpression(context);
1409         m_nonLHSCount = oldNonLHSCount;
1410         consumeOrFail(CLOSEPAREN);
1411
1412         return result;
1413     }
1414     case THISTOKEN: {
1415         next();
1416         return context.thisExpr(m_lexer->lastLineNumber());
1417     }
1418     case IDENT: {
1419         int start = tokenStart();
1420         const Identifier* ident = m_token.m_data.ident;
1421         next();
1422         currentScope()->useVariable(ident, m_globalData->propertyNames->eval == *ident);
1423         m_lastIdentifier = ident;
1424         return context.createResolve(m_lexer->lastLineNumber(), ident, start);
1425     }
1426     case STRING: {
1427         const Identifier* ident = m_token.m_data.ident;
1428         next();
1429         return context.createString(m_lexer->lastLineNumber(), ident);
1430     }
1431     case NUMBER: {
1432         double d = m_token.m_data.doubleValue;
1433         next();
1434         return context.createNumberExpr(m_lexer->lastLineNumber(), d);
1435     }
1436     case NULLTOKEN: {
1437         next();
1438         return context.createNull(m_lexer->lastLineNumber());
1439     }
1440     case TRUETOKEN: {
1441         next();
1442         return context.createBoolean(m_lexer->lastLineNumber(), true);
1443     }
1444     case FALSETOKEN: {
1445         next();
1446         return context.createBoolean(m_lexer->lastLineNumber(), false);
1447     }
1448     case DIVEQUAL:
1449     case DIVIDE: {
1450         /* regexp */
1451         const Identifier* pattern;
1452         const Identifier* flags;
1453         if (match(DIVEQUAL))
1454             failIfFalse(m_lexer->scanRegExp(pattern, flags, '='));
1455         else
1456             failIfFalse(m_lexer->scanRegExp(pattern, flags));
1457
1458         int start = tokenStart();
1459         next();
1460         TreeExpression re = context.createRegExp(m_lexer->lastLineNumber(), *pattern, *flags, start);
1461         if (!re) {
1462             const char* yarrErrorMsg = Yarr::checkSyntax(pattern->ustring());
1463             ASSERT(!m_errorMessage.isNull());
1464             failWithMessage(yarrErrorMsg);
1465         }
1466         return re;
1467     }
1468     default:
1469         fail();
1470     }
1471 }
1472
1473 template <typename LexerType>
1474 template <class TreeBuilder> TreeArguments Parser<LexerType>::parseArguments(TreeBuilder& context)
1475 {
1476     consumeOrFailWithFlags(OPENPAREN, TreeBuilder::DontBuildStrings);
1477     if (match(CLOSEPAREN)) {
1478         next(TreeBuilder::DontBuildStrings);
1479         return context.createArguments();
1480     }
1481     TreeExpression firstArg = parseAssignmentExpression(context);
1482     failIfFalse(firstArg);
1483
1484     TreeArgumentsList argList = context.createArgumentsList(m_lexer->lastLineNumber(), firstArg);
1485     TreeArgumentsList tail = argList;
1486     while (match(COMMA)) {
1487         next(TreeBuilder::DontBuildStrings);
1488         TreeExpression arg = parseAssignmentExpression(context);
1489         failIfFalse(arg);
1490         tail = context.createArgumentsList(m_lexer->lastLineNumber(), tail, arg);
1491     }
1492     consumeOrFail(CLOSEPAREN);
1493     return context.createArguments(argList);
1494 }
1495
1496 template <typename LexerType>
1497 template <class TreeBuilder> TreeExpression Parser<LexerType>::parseMemberExpression(TreeBuilder& context)
1498 {
1499     TreeExpression base = 0;
1500     int start = tokenStart();
1501     int expressionStart = start;
1502     int newCount = 0;
1503     while (match(NEW)) {
1504         next();
1505         newCount++;
1506     }
1507
1508     if (match(FUNCTION)) {
1509         const Identifier* name = &m_globalData->propertyNames->nullIdentifier;
1510         TreeFormalParameterList parameters = 0;
1511         TreeFunctionBody body = 0;
1512         int openBracePos = 0;
1513         int closeBracePos = 0;
1514         int bodyStartLine = 0;
1515         next();
1516         failIfFalse((parseFunctionInfo<FunctionNoRequirements, false>(context, name, parameters, body, openBracePos, closeBracePos, bodyStartLine)));
1517         base = context.createFunctionExpr(m_lexer->lastLineNumber(), name, body, parameters, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
1518     } else
1519         base = parsePrimaryExpression(context);
1520
1521     failIfFalse(base);
1522     while (true) {
1523         switch (m_token.m_type) {
1524         case OPENBRACKET: {
1525             m_nonTrivialExpressionCount++;
1526             int expressionEnd = lastTokenEnd();
1527             next();
1528             int nonLHSCount = m_nonLHSCount;
1529             int initialAssignments = m_assignmentCount;
1530             TreeExpression property = parseExpression(context);
1531             failIfFalse(property);
1532             base = context.createBracketAccess(m_lexer->lastLineNumber(), base, property, initialAssignments != m_assignmentCount, expressionStart, expressionEnd, tokenEnd());
1533             consumeOrFail(CLOSEBRACKET);
1534             m_nonLHSCount = nonLHSCount;
1535             break;
1536         }
1537         case OPENPAREN: {
1538             m_nonTrivialExpressionCount++;
1539             int nonLHSCount = m_nonLHSCount;
1540             if (newCount) {
1541                 newCount--;
1542                 int exprEnd = lastTokenEnd();
1543                 TreeArguments arguments = parseArguments(context);
1544                 failIfFalse(arguments);
1545                 base = context.createNewExpr(m_lexer->lastLineNumber(), base, arguments, start, exprEnd, lastTokenEnd());
1546             } else {
1547                 int expressionEnd = lastTokenEnd();
1548                 TreeArguments arguments = parseArguments(context);
1549                 failIfFalse(arguments);
1550                 base = context.makeFunctionCallNode(m_lexer->lastLineNumber(), base, arguments, expressionStart, expressionEnd, lastTokenEnd());
1551             }
1552             m_nonLHSCount = nonLHSCount;
1553             break;
1554         }
1555         case DOT: {
1556             m_nonTrivialExpressionCount++;
1557             int expressionEnd = lastTokenEnd();
1558             nextExpectIdentifier(LexerFlagsIgnoreReservedWords | TreeBuilder::DontBuildKeywords);
1559             matchOrFail(IDENT);
1560             base = context.createDotAccess(m_lexer->lastLineNumber(), base, m_token.m_data.ident, expressionStart, expressionEnd, tokenEnd());
1561             next();
1562             break;
1563         }
1564         default:
1565             goto endMemberExpression;
1566         }
1567     }
1568 endMemberExpression:
1569     while (newCount--)
1570         base = context.createNewExpr(m_lexer->lastLineNumber(), base, start, lastTokenEnd());
1571     return base;
1572 }
1573
1574 template <typename LexerType>
1575 template <class TreeBuilder> TreeExpression Parser<LexerType>::parseUnaryExpression(TreeBuilder& context)
1576 {
1577     typename TreeBuilder::UnaryExprContext unaryExprContext(context);
1578     AllowInOverride allowInOverride(this);
1579     int tokenStackDepth = 0;
1580     bool modifiesExpr = false;
1581     bool requiresLExpr = false;
1582     while (isUnaryOp(m_token.m_type)) {
1583         if (strictMode()) {
1584             switch (m_token.m_type) {
1585             case PLUSPLUS:
1586             case MINUSMINUS:
1587             case AUTOPLUSPLUS:
1588             case AUTOMINUSMINUS:
1589                 failIfTrue(requiresLExpr);
1590                 modifiesExpr = true;
1591                 requiresLExpr = true;
1592                 break;
1593             case DELETETOKEN:
1594                 failIfTrue(requiresLExpr);
1595                 requiresLExpr = true;
1596                 break;
1597             default:
1598                 failIfTrue(requiresLExpr);
1599                 break;
1600             }
1601         }
1602         m_nonLHSCount++;
1603         context.appendUnaryToken(tokenStackDepth, m_token.m_type, tokenStart());
1604         next();
1605         m_nonTrivialExpressionCount++;
1606     }
1607     int subExprStart = tokenStart();
1608     TreeExpression expr = parseMemberExpression(context);
1609     failIfFalse(expr);
1610     bool isEvalOrArguments = false;
1611     if (strictMode() && !m_syntaxAlreadyValidated) {
1612         if (context.isResolve(expr))
1613             isEvalOrArguments = *m_lastIdentifier == m_globalData->propertyNames->eval || *m_lastIdentifier == m_globalData->propertyNames->arguments;
1614     }
1615     failIfTrueIfStrictWithNameAndMessage(isEvalOrArguments && modifiesExpr, "'", m_lastIdentifier->impl(), "' cannot be modified in strict mode");
1616     switch (m_token.m_type) {
1617     case PLUSPLUS:
1618         m_nonTrivialExpressionCount++;
1619         m_nonLHSCount++;
1620         expr = context.makePostfixNode(m_lexer->lastLineNumber(), expr, OpPlusPlus, subExprStart, lastTokenEnd(), tokenEnd());
1621         m_assignmentCount++;
1622         failIfTrueIfStrictWithNameAndMessage(isEvalOrArguments, "'", m_lastIdentifier->impl(), "' cannot be modified in strict mode");
1623         failIfTrueIfStrict(requiresLExpr);
1624         next();
1625         break;
1626     case MINUSMINUS:
1627         m_nonTrivialExpressionCount++;
1628         m_nonLHSCount++;
1629         expr = context.makePostfixNode(m_lexer->lastLineNumber(), expr, OpMinusMinus, subExprStart, lastTokenEnd(), tokenEnd());
1630         m_assignmentCount++;
1631         failIfTrueIfStrictWithNameAndMessage(isEvalOrArguments, "'", m_lastIdentifier->impl(), "' cannot be modified in strict mode");
1632         failIfTrueIfStrict(requiresLExpr);
1633         next();
1634         break;
1635     default:
1636         break;
1637     }
1638
1639     int end = lastTokenEnd();
1640
1641     if (!TreeBuilder::CreatesAST && (m_syntaxAlreadyValidated || !strictMode()))
1642         return expr;
1643
1644     while (tokenStackDepth) {
1645         switch (context.unaryTokenStackLastType(tokenStackDepth)) {
1646         case EXCLAMATION:
1647             expr = context.createLogicalNot(m_lexer->lastLineNumber(), expr);
1648             break;
1649         case TILDE:
1650             expr = context.makeBitwiseNotNode(m_lexer->lastLineNumber(), expr);
1651             break;
1652         case MINUS:
1653             expr = context.makeNegateNode(m_lexer->lastLineNumber(), expr);
1654             break;
1655         case PLUS:
1656             expr = context.createUnaryPlus(m_lexer->lastLineNumber(), expr);
1657             break;
1658         case PLUSPLUS:
1659         case AUTOPLUSPLUS:
1660             expr = context.makePrefixNode(m_lexer->lastLineNumber(), expr, OpPlusPlus, context.unaryTokenStackLastStart(tokenStackDepth), subExprStart + 1, end);
1661             m_assignmentCount++;
1662             break;
1663         case MINUSMINUS:
1664         case AUTOMINUSMINUS:
1665             expr = context.makePrefixNode(m_lexer->lastLineNumber(), expr, OpMinusMinus, context.unaryTokenStackLastStart(tokenStackDepth), subExprStart + 1, end);
1666             m_assignmentCount++;
1667             break;
1668         case TYPEOF:
1669             expr = context.makeTypeOfNode(m_lexer->lastLineNumber(), expr);
1670             break;
1671         case VOIDTOKEN:
1672             expr = context.createVoid(m_lexer->lastLineNumber(), expr);
1673             break;
1674         case DELETETOKEN:
1675             failIfTrueIfStrictWithNameAndMessage(context.isResolve(expr), "Cannot delete unqualified property", m_lastIdentifier->impl(), "in strict mode");
1676             expr = context.makeDeleteNode(m_lexer->lastLineNumber(), expr, context.unaryTokenStackLastStart(tokenStackDepth), end, end);
1677             break;
1678         default:
1679             // If we get here something has gone horribly horribly wrong
1680             CRASH();
1681         }
1682         subExprStart = context.unaryTokenStackLastStart(tokenStackDepth);
1683         context.unaryTokenStackRemoveLast(tokenStackDepth);
1684     }
1685     return expr;
1686 }
1687
1688 // Instantiate the two flavors of Parser we need instead of putting most of this file in Parser.h
1689 template class Parser< Lexer<LChar> >;
1690 template class Parser< Lexer<UChar> >;
1691
1692 } // namespace JSC