parser/JSParser.cpp

   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 "CodeBlock.h"
  33 #include "JSGlobalData.h"
  34 #include "NodeInfo.h"
  35 #include "ASTBuilder.h"
  36 #include "SourceProvider.h"
  37 #include "SourceProviderCacheItem.h"
  38 #include <wtf/HashFunctions.h>
  39 #include <wtf/OwnPtr.h>
  40 #include <wtf/WTFThreadData.h>
  41 #include <utility>
  42
  43 using namespace std;
  44
  45 namespace JSC {
  46 #define fail() do { m_error = true; return 0; } while (0)
  47 #define failIfFalse(cond) do { if (!(cond)) fail(); } while (0)
  48 #define failIfTrue(cond) do { if ((cond)) fail(); } while (0)
  49 #define failIfTrueIfStrict(cond) do { if ((cond) && strictMode()) fail(); } while (0)
  50 #define failIfFalseIfStrict(cond) do { if ((!(cond)) && strictMode()) fail(); } while (0)
  51 #define consumeOrFail(tokenType) do { if (!consume(tokenType)) fail(); } while (0)
  52 #define consumeOrFailWithFlags(tokenType, flags) do { if (!consume(tokenType, flags)) fail(); } while (0)
  53 #define matchOrFail(tokenType) do { if (!match(tokenType)) fail(); } while (0)
  54 #define failIfStackOverflow() do { failIfFalse(canRecurse()); } while (0)
  55
  56 // Macros to make the more common TreeBuilder types a little less verbose
  57 #define TreeStatement typename TreeBuilder::Statement
  58 #define TreeExpression typename TreeBuilder::Expression
  59 #define TreeFormalParameterList typename TreeBuilder::FormalParameterList
  60 #define TreeSourceElements typename TreeBuilder::SourceElements
  61 #define TreeClause typename TreeBuilder::Clause
  62 #define TreeClauseList typename TreeBuilder::ClauseList
  63 #define TreeConstDeclList typename TreeBuilder::ConstDeclList
  64 #define TreeArguments typename TreeBuilder::Arguments
  65 #define TreeArgumentsList typename TreeBuilder::ArgumentsList
  66 #define TreeFunctionBody typename TreeBuilder::FunctionBody
  67 #define TreeProperty typename TreeBuilder::Property
  68 #define TreePropertyList typename TreeBuilder::PropertyList
  69
  70 COMPILE_ASSERT(LastUntaggedToken < 64, LessThan64UntaggedTokens);
  71
  72 class JSParser {
  73 public:
  74     JSParser(Lexer*, JSGlobalData*, FunctionParameters*, bool isStrictContext, bool isFunction, SourceProvider*);
  75     const char* parseProgram();
  76 private:
  77     struct AllowInOverride {
  78         AllowInOverride(JSParser* parser)
  79             : m_parser(parser)
  80             , m_oldAllowsIn(parser->m_allowsIn)
  81         {
  82             parser->m_allowsIn = true;
  83         }
  84         ~AllowInOverride()
  85         {
  86             m_parser->m_allowsIn = m_oldAllowsIn;
  87         }
  88         JSParser* m_parser;
  89         bool m_oldAllowsIn;
  90     };
  91
  92     struct ScopeLabelInfo {
  93         ScopeLabelInfo(StringImpl* ident, bool isLoop)
  94         : m_ident(ident)
  95         , m_isLoop(isLoop)
  96         {
  97         }
  98         StringImpl* m_ident;
  99         bool m_isLoop;
 100     };
 101
 102     ALWAYS_INLINE void next(unsigned lexType = 0)
 103     {
 104         m_lastLine = m_token.m_info.line;
 105         m_lastTokenEnd = m_token.m_info.endOffset;
 106         m_lexer->setLastLineNumber(m_lastLine);
 107         m_token.m_type = m_lexer->lex(&m_token.m_data, &m_token.m_info, lexType, strictMode());
 108     }
 109
 110     ALWAYS_INLINE void nextExpectIdentifier(unsigned lexType = 0)
 111     {
 112         m_lastLine = m_token.m_info.line;
 113         m_lastTokenEnd = m_token.m_info.endOffset;
 114         m_lexer->setLastLineNumber(m_lastLine);
 115         m_token.m_type = m_lexer->lexExpectIdentifier(&m_token.m_data, &m_token.m_info, lexType, strictMode());
 116     }
 117
 118     ALWAYS_INLINE bool nextTokenIsColon()
 119     {
 120         return m_lexer->nextTokenIsColon();
 121     }
 122
 123     ALWAYS_INLINE bool consume(JSTokenType expected, unsigned flags = 0)
 124     {
 125         bool result = m_token.m_type == expected;
 126         failIfFalse(result);
 127         next(flags);
 128         return result;
 129     }
 130
 131     ALWAYS_INLINE bool match(JSTokenType expected)
 132     {
 133         return m_token.m_type == expected;
 134     }
 135
 136     ALWAYS_INLINE int tokenStart()
 137     {
 138         return m_token.m_info.startOffset;
 139     }
 140
 141     ALWAYS_INLINE int tokenLine()
 142     {
 143         return m_token.m_info.line;
 144     }
 145
 146     ALWAYS_INLINE int tokenEnd()
 147     {
 148         return m_token.m_info.endOffset;
 149     }
 150
 151     void startLoop() { currentScope()->startLoop(); }
 152     void endLoop() { currentScope()->endLoop(); }
 153     void startSwitch() { currentScope()->startSwitch(); }
 154     void endSwitch() { currentScope()->endSwitch(); }
 155     void setStrictMode() { currentScope()->setStrictMode(); }
 156     bool strictMode() { return currentScope()->strictMode(); }
 157     bool isValidStrictMode() { return currentScope()->isValidStrictMode(); }
 158     bool declareParameter(const Identifier* ident) { return currentScope()->declareParameter(ident); }
 159     bool breakIsValid()
 160     {
 161         ScopeRef current = currentScope();
 162         while (!current->breakIsValid()) {
 163             if (!current.hasContainingScope())
 164                 return false;
 165             current = current.containingScope();
 166         }
 167         return true;
 168     }
 169     bool continueIsValid()
 170     {
 171         ScopeRef current = currentScope();
 172         while (!current->continueIsValid()) {
 173             if (!current.hasContainingScope())
 174                 return false;
 175             current = current.containingScope();
 176         }
 177         return true;
 178     }
 179     void pushLabel(const Identifier* label, bool isLoop) { currentScope()->pushLabel(label, isLoop); }
 180     void popLabel() { currentScope()->popLabel(); }
 181     ScopeLabelInfo* getLabel(const Identifier* label)
 182     {
 183         ScopeRef current = currentScope();
 184         ScopeLabelInfo* result = 0;
 185         while (!(result = current->getLabel(label))) {
 186             if (!current.hasContainingScope())
 187                 return 0;
 188             current = current.containingScope();
 189         }
 190         return result;
 191     }
 192
 193     enum SourceElementsMode { CheckForStrictMode, DontCheckForStrictMode };
 194     template <SourceElementsMode mode, class TreeBuilder> TreeSourceElements parseSourceElements(TreeBuilder&);
 195     template <class TreeBuilder> TreeStatement parseStatement(TreeBuilder&, const Identifier*& directive);
 196     template <class TreeBuilder> TreeStatement parseFunctionDeclaration(TreeBuilder&);
 197     template <class TreeBuilder> TreeStatement parseVarDeclaration(TreeBuilder&);
 198     template <class TreeBuilder> TreeStatement parseConstDeclaration(TreeBuilder&);
 199     template <class TreeBuilder> TreeStatement parseDoWhileStatement(TreeBuilder&);
 200     template <class TreeBuilder> TreeStatement parseWhileStatement(TreeBuilder&);
 201     template <class TreeBuilder> TreeStatement parseForStatement(TreeBuilder&);
 202     template <class TreeBuilder> TreeStatement parseBreakStatement(TreeBuilder&);
 203     template <class TreeBuilder> TreeStatement parseContinueStatement(TreeBuilder&);
 204     template <class TreeBuilder> TreeStatement parseReturnStatement(TreeBuilder&);
 205     template <class TreeBuilder> TreeStatement parseThrowStatement(TreeBuilder&);
 206     template <class TreeBuilder> TreeStatement parseWithStatement(TreeBuilder&);
 207     template <class TreeBuilder> TreeStatement parseSwitchStatement(TreeBuilder&);
 208     template <class TreeBuilder> TreeClauseList parseSwitchClauses(TreeBuilder&);
 209     template <class TreeBuilder> TreeClause parseSwitchDefaultClause(TreeBuilder&);
 210     template <class TreeBuilder> TreeStatement parseTryStatement(TreeBuilder&);
 211     template <class TreeBuilder> TreeStatement parseDebuggerStatement(TreeBuilder&);
 212     template <class TreeBuilder> TreeStatement parseExpressionStatement(TreeBuilder&);
 213     template <class TreeBuilder> TreeStatement parseExpressionOrLabelStatement(TreeBuilder&);
 214     template <class TreeBuilder> TreeStatement parseIfStatement(TreeBuilder&);
 215     template <class TreeBuilder> ALWAYS_INLINE TreeStatement parseBlockStatement(TreeBuilder&);
 216     template <class TreeBuilder> TreeExpression parseExpression(TreeBuilder&);
 217     template <class TreeBuilder> TreeExpression parseAssignmentExpression(TreeBuilder&);
 218     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseConditionalExpression(TreeBuilder&);
 219     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseBinaryExpression(TreeBuilder&);
 220     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseUnaryExpression(TreeBuilder&);
 221     template <class TreeBuilder> TreeExpression parseMemberExpression(TreeBuilder&);
 222     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parsePrimaryExpression(TreeBuilder&);
 223     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseArrayLiteral(TreeBuilder&);
 224     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseObjectLiteral(TreeBuilder&);
 225     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseStrictObjectLiteral(TreeBuilder&);
 226     template <class TreeBuilder> ALWAYS_INLINE TreeArguments parseArguments(TreeBuilder&);
 227     template <bool strict, class TreeBuilder> ALWAYS_INLINE TreeProperty parseProperty(TreeBuilder&);
 228     template <class TreeBuilder> ALWAYS_INLINE TreeFunctionBody parseFunctionBody(TreeBuilder&);
 229     template <class TreeBuilder> ALWAYS_INLINE TreeFormalParameterList parseFormalParameters(TreeBuilder&);
 230     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseVarDeclarationList(TreeBuilder&, int& declarations, const Identifier*& lastIdent, TreeExpression& lastInitializer, int& identStart, int& initStart, int& initEnd);
 231     template <class TreeBuilder> ALWAYS_INLINE TreeConstDeclList parseConstDeclarationList(TreeBuilder& context);
 232     enum FunctionRequirements { FunctionNoRequirements, FunctionNeedsName };
 233     template <FunctionRequirements, bool nameIsInContainingScope, class TreeBuilder> bool parseFunctionInfo(TreeBuilder&, const Identifier*&, TreeFormalParameterList&, TreeFunctionBody&, int& openBrace, int& closeBrace, int& bodyStartLine);
 234     ALWAYS_INLINE int isBinaryOperator(JSTokenType token);
 235     bool allowAutomaticSemicolon();
 236
 237     bool autoSemiColon()
 238     {
 239         if (m_token.m_type == SEMICOLON) {
 240             next();
 241             return true;
 242         }
 243         return allowAutomaticSemicolon();
 244     }
 245
 246     bool canRecurse()
 247     {
 248         return m_stack.recursionCheck();
 249     }
 250
 251     int lastTokenEnd() const
 252     {
 253         return m_lastTokenEnd;
 254     }
 255
 256     ParserArena m_arena;
 257     Lexer* m_lexer;
 258     StackBounds m_stack;
 259     bool m_error;
 260     const char* m_errorMessage;
 261     JSGlobalData* m_globalData;
 262     JSToken m_token;
 263     bool m_allowsIn;
 264     int m_lastLine;
 265     int m_lastTokenEnd;
 266     int m_assignmentCount;
 267     int m_nonLHSCount;
 268     bool m_syntaxAlreadyValidated;
 269     int m_statementDepth;
 270     int m_nonTrivialExpressionCount;
 271     const Identifier* m_lastIdentifier;
 272
 273     struct DepthManager {
 274         DepthManager(int* depth)
 275             : m_originalDepth(*depth)
 276             , m_depth(depth)
 277         {
 278         }
 279
 280         ~DepthManager()
 281         {
 282             *m_depth = m_originalDepth;
 283         }
 284
 285     private:
 286         int m_originalDepth;
 287         int* m_depth;
 288     };
 289
 290     struct Scope {
 291         Scope(JSGlobalData* globalData, bool isFunction, bool strictMode)
 292             : m_globalData(globalData)
 293             , m_shadowsArguments(false)
 294             , m_usesEval(false)
 295             , m_needsFullActivation(false)
 296             , m_allowsNewDecls(true)
 297             , m_strictMode(strictMode)
 298             , m_isFunction(isFunction)
 299             , m_isFunctionBoundary(false)
 300             , m_isValidStrictMode(true)
 301             , m_loopDepth(0)
 302             , m_switchDepth(0)
 303         {
 304         }
 305
 306         Scope(const Scope& rhs)
 307             : m_globalData(rhs.m_globalData)
 308             , m_shadowsArguments(rhs.m_shadowsArguments)
 309             , m_usesEval(rhs.m_usesEval)
 310             , m_needsFullActivation(rhs.m_needsFullActivation)
 311             , m_allowsNewDecls(rhs.m_allowsNewDecls)
 312             , m_strictMode(rhs.m_strictMode)
 313             , m_isFunction(rhs.m_isFunction)
 314             , m_isFunctionBoundary(rhs.m_isFunctionBoundary)
 315             , m_isValidStrictMode(rhs.m_isValidStrictMode)
 316             , m_loopDepth(rhs.m_loopDepth)
 317             , m_switchDepth(rhs.m_switchDepth)
 318         {
 319             if (rhs.m_labels) {
 320                 m_labels = adoptPtr(new LabelStack);
 321
 322                 typedef LabelStack::const_iterator iterator;
 323                 iterator end = rhs.m_labels->end();
 324                 for (iterator it = rhs.m_labels->begin(); it != end; ++it)
 325                     m_labels->append(ScopeLabelInfo(it->m_ident, it->m_isLoop));
 326             }
 327         }
 328
 329         void startSwitch() { m_switchDepth++; }
 330         void endSwitch() { m_switchDepth--; }
 331         void startLoop() { m_loopDepth++; }
 332         void endLoop() { ASSERT(m_loopDepth); m_loopDepth--; }
 333         bool inLoop() { return !!m_loopDepth; }
 334         bool breakIsValid() { return m_loopDepth || m_switchDepth; }
 335         bool continueIsValid() { return m_loopDepth; }
 336
 337         void pushLabel(const Identifier* label, bool isLoop)
 338         {
 339             if (!m_labels)
 340                 m_labels = adoptPtr(new LabelStack);
 341             m_labels->append(ScopeLabelInfo(label->impl(), isLoop));
 342         }
 343
 344         void popLabel()
 345         {
 346             ASSERT(m_labels);
 347             ASSERT(m_labels->size());
 348             m_labels->removeLast();
 349         }
 350
 351         ScopeLabelInfo* getLabel(const Identifier* label)
 352         {
 353             if (!m_labels)
 354                 return 0;
 355             for (int i = m_labels->size(); i > 0; i--) {
 356                 if (m_labels->at(i - 1).m_ident == label->impl())
 357                     return &m_labels->at(i - 1);
 358             }
 359             return 0;
 360         }
 361
 362         void setIsFunction()
 363         {
 364             m_isFunction = true;
 365             m_isFunctionBoundary = true;
 366         }
 367         bool isFunction() { return m_isFunction; }
 368         bool isFunctionBoundary() { return m_isFunctionBoundary; }
 369
 370         bool declareVariable(const Identifier* ident)
 371         {
 372             bool isValidStrictMode = m_globalData->propertyNames->eval != *ident && m_globalData->propertyNames->arguments != *ident;
 373             m_isValidStrictMode = m_isValidStrictMode && isValidStrictMode;
 374             m_declaredVariables.add(ident->ustring().impl());
 375             return isValidStrictMode;
 376         }
 377
 378         void declareWrite(const Identifier* ident)
 379         {
 380             ASSERT(m_strictMode);
 381             m_writtenVariables.add(ident->impl());
 382         }
 383
 384         void preventNewDecls() { m_allowsNewDecls = false; }
 385         bool allowsNewDecls() const { return m_allowsNewDecls; }
 386
 387         bool declareParameter(const Identifier* ident)
 388         {
 389             bool isArguments = m_globalData->propertyNames->arguments == *ident;
 390             bool isValidStrictMode = m_declaredVariables.add(ident->ustring().impl()).second && m_globalData->propertyNames->eval != *ident && !isArguments;
 391             m_isValidStrictMode = m_isValidStrictMode && isValidStrictMode;
 392             if (isArguments)
 393                 m_shadowsArguments = true;
 394             return isValidStrictMode;
 395         }
 396
 397         void useVariable(const Identifier* ident, bool isEval)
 398         {
 399             m_usesEval |= isEval;
 400             m_usedVariables.add(ident->ustring().impl());
 401         }
 402
 403         void setNeedsFullActivation() { m_needsFullActivation = true; }
 404
 405         bool collectFreeVariables(Scope* nestedScope, bool shouldTrackClosedVariables)
 406         {
 407             if (nestedScope->m_usesEval)
 408                 m_usesEval = true;
 409             IdentifierSet::iterator end = nestedScope->m_usedVariables.end();
 410             for (IdentifierSet::iterator ptr = nestedScope->m_usedVariables.begin(); ptr != end; ++ptr) {
 411                 if (nestedScope->m_declaredVariables.contains(*ptr))
 412                     continue;
 413                 m_usedVariables.add(*ptr);
 414                 if (shouldTrackClosedVariables)
 415                     m_closedVariables.add(*ptr);
 416             }
 417             if (nestedScope->m_writtenVariables.size()) {
 418                 IdentifierSet::iterator end = nestedScope->m_writtenVariables.end();
 419                 for (IdentifierSet::iterator ptr = nestedScope->m_writtenVariables.begin(); ptr != end; ++ptr) {
 420                     if (nestedScope->m_declaredVariables.contains(*ptr))
 421                         continue;
 422                     m_writtenVariables.add(*ptr);
 423                 }
 424             }
 425
 426             return true;
 427         }
 428
 429         void getUncapturedWrittenVariables(IdentifierSet& writtenVariables)
 430         {
 431             IdentifierSet::iterator end = m_writtenVariables.end();
 432             for (IdentifierSet::iterator ptr = m_writtenVariables.begin(); ptr != end; ++ptr) {
 433                 if (!m_declaredVariables.contains(*ptr))
 434                     writtenVariables.add(*ptr);
 435             }
 436         }
 437
 438         void getCapturedVariables(IdentifierSet& capturedVariables)
 439         {
 440             if (m_needsFullActivation || m_usesEval) {
 441                 capturedVariables.swap(m_declaredVariables);
 442                 return;
 443             }
 444             for (IdentifierSet::iterator ptr = m_closedVariables.begin(); ptr != m_closedVariables.end(); ++ptr) {
 445                 if (!m_declaredVariables.contains(*ptr))
 446                     continue;
 447                 capturedVariables.add(*ptr);
 448             }
 449         }
 450         void setStrictMode() { m_strictMode = true; }
 451         bool strictMode() const { return m_strictMode; }
 452         bool isValidStrictMode() const { return m_isValidStrictMode; }
 453         bool shadowsArguments() const { return m_shadowsArguments; }
 454
 455         void copyCapturedVariablesToVector(const IdentifierSet& capturedVariables, Vector<RefPtr<StringImpl> >& vector)
 456         {
 457             IdentifierSet::iterator end = capturedVariables.end();
 458             for (IdentifierSet::iterator it = capturedVariables.begin(); it != end; ++it) {
 459                 if (m_declaredVariables.contains(*it))
 460                     continue;
 461                 vector.append(*it);
 462             }
 463             vector.shrinkToFit();
 464         }
 465
 466         void saveFunctionInfo(SourceProviderCacheItem* info)
 467         {
 468             ASSERT(m_isFunction);
 469             info->usesEval = m_usesEval;
 470             copyCapturedVariablesToVector(m_writtenVariables, info->writtenVariables);
 471             copyCapturedVariablesToVector(m_usedVariables, info->usedVariables);
 472         }
 473
 474         void restoreFunctionInfo(const SourceProviderCacheItem* info)
 475         {
 476             ASSERT(m_isFunction);
 477             m_usesEval = info->usesEval;
 478             unsigned size = info->usedVariables.size();
 479             for (unsigned i = 0; i < size; ++i)
 480                 m_usedVariables.add(info->usedVariables[i]);
 481             size = info->writtenVariables.size();
 482             for (unsigned i = 0; i < size; ++i)
 483                 m_writtenVariables.add(info->writtenVariables[i]);
 484         }
 485
 486     private:
 487         JSGlobalData* m_globalData;
 488         bool m_shadowsArguments : 1;
 489         bool m_usesEval : 1;
 490         bool m_needsFullActivation : 1;
 491         bool m_allowsNewDecls : 1;
 492         bool m_strictMode : 1;
 493         bool m_isFunction : 1;
 494         bool m_isFunctionBoundary : 1;
 495         bool m_isValidStrictMode : 1;
 496         int m_loopDepth;
 497         int m_switchDepth;
 498
 499         typedef Vector<ScopeLabelInfo, 2> LabelStack;
 500         OwnPtr<LabelStack> m_labels;
 501         IdentifierSet m_declaredVariables;
 502         IdentifierSet m_usedVariables;
 503         IdentifierSet m_closedVariables;
 504         IdentifierSet m_writtenVariables;
 505     };
 506
 507     typedef Vector<Scope, 10> ScopeStack;
 508
 509     struct ScopeRef {
 510         ScopeRef(ScopeStack* scopeStack, unsigned index)
 511             : m_scopeStack(scopeStack)
 512             , m_index(index)
 513         {
 514         }
 515         Scope* operator->() { return &m_scopeStack->at(m_index); }
 516         unsigned index() const { return m_index; }
 517
 518         bool hasContainingScope()
 519         {
 520             return m_index && !m_scopeStack->at(m_index).isFunctionBoundary();
 521         }
 522
 523         ScopeRef containingScope()
 524         {
 525             ASSERT(hasContainingScope());
 526             return ScopeRef(m_scopeStack, m_index - 1);
 527         }
 528
 529     private:
 530         ScopeStack* m_scopeStack;
 531         unsigned m_index;
 532     };
 533
 534     struct AutoPopScopeRef : public ScopeRef {
 535         AutoPopScopeRef(JSParser* parser, ScopeRef scope)
 536             : ScopeRef(scope)
 537             , m_parser(parser)
 538         {
 539         }
 540
 541         ~AutoPopScopeRef()
 542         {
 543             if (m_parser)
 544                 m_parser->popScope(*this, false);
 545         }
 546
 547         void setPopped()
 548         {
 549             m_parser = 0;
 550         }
 551
 552     private:
 553         JSParser* m_parser;
 554     };
 555
 556     ScopeRef currentScope()
 557     {
 558         return ScopeRef(&m_scopeStack, m_scopeStack.size() - 1);
 559     }
 560
 561     ScopeRef pushScope()
 562     {
 563         bool isFunction = false;
 564         bool isStrict = false;
 565         if (!m_scopeStack.isEmpty()) {
 566             isStrict = m_scopeStack.last().strictMode();
 567             isFunction = m_scopeStack.last().isFunction();
 568         }
 569         m_scopeStack.append(Scope(m_globalData, isFunction, isStrict));
 570         return currentScope();
 571     }
 572
 573     bool popScopeInternal(ScopeRef& scope, bool shouldTrackClosedVariables)
 574     {
 575         ASSERT_UNUSED(scope, scope.index() == m_scopeStack.size() - 1);
 576         ASSERT(m_scopeStack.size() > 1);
 577         bool result = m_scopeStack[m_scopeStack.size() - 2].collectFreeVariables(&m_scopeStack.last(), shouldTrackClosedVariables);
 578         m_scopeStack.removeLast();
 579         return result;
 580     }
 581
 582     bool popScope(ScopeRef& scope, bool shouldTrackClosedVariables)
 583     {
 584         return popScopeInternal(scope, shouldTrackClosedVariables);
 585     }
 586
 587     bool popScope(AutoPopScopeRef& scope, bool shouldTrackClosedVariables)
 588     {
 589         scope.setPopped();
 590         return popScopeInternal(scope, shouldTrackClosedVariables);
 591     }
 592
 593     bool declareVariable(const Identifier* ident)
 594     {
 595         unsigned i = m_scopeStack.size() - 1;
 596         ASSERT(i < m_scopeStack.size());
 597         while (!m_scopeStack[i].allowsNewDecls()) {
 598             i--;
 599             ASSERT(i < m_scopeStack.size());
 600         }
 601         return m_scopeStack[i].declareVariable(ident);
 602     }
 603
 604     void declareWrite(const Identifier* ident)
 605     {
 606         if (!m_syntaxAlreadyValidated)
 607             m_scopeStack.last().declareWrite(ident);
 608     }
 609
 610     ScopeStack m_scopeStack;
 611
 612     const SourceProviderCacheItem* findCachedFunctionInfo(int openBracePos)
 613     {
 614         return m_functionCache ? m_functionCache->get(openBracePos) : 0;
 615     }
 616
 617     SourceProviderCache* m_functionCache;
 618 };
 619
 620 const char* jsParse(JSGlobalData* globalData, FunctionParameters* parameters, JSParserStrictness strictness, JSParserMode parserMode, const SourceCode* source)
 621 {
 622     JSParser parser(globalData->lexer, globalData, parameters, strictness == JSParseStrict, parserMode == JSParseFunctionCode, source->provider());
 623     return parser.parseProgram();
 624 }
 625
 626 JSParser::JSParser(Lexer* lexer, JSGlobalData* globalData, FunctionParameters* parameters, bool inStrictContext, bool isFunction, SourceProvider* provider)
 627     : m_lexer(lexer)
 628     , m_stack(globalData->stack())
 629     , m_error(false)
 630     , m_errorMessage("Parse error")
 631     , m_globalData(globalData)
 632     , m_allowsIn(true)
 633     , m_lastLine(0)
 634     , m_lastTokenEnd(0)
 635     , m_assignmentCount(0)
 636     , m_nonLHSCount(0)
 637     , m_syntaxAlreadyValidated(provider->isValid())
 638     , m_statementDepth(0)
 639     , m_nonTrivialExpressionCount(0)
 640     , m_lastIdentifier(0)
 641     , m_functionCache(m_lexer->sourceProvider()->cache())
 642 {
 643     ScopeRef scope = pushScope();
 644     if (isFunction)
 645         scope->setIsFunction();
 646     if (inStrictContext)
 647         scope->setStrictMode();
 648     if (parameters) {
 649         for (unsigned i = 0; i < parameters->size(); i++)
 650             scope->declareParameter(&parameters->at(i));
 651     }
 652     next();
 653     m_lexer->setLastLineNumber(tokenLine());
 654 }
 655
 656 const char* JSParser::parseProgram()
 657 {
 658     unsigned oldFunctionCacheSize = m_functionCache ? m_functionCache->byteSize() : 0;
 659     ASTBuilder context(m_globalData, m_lexer);
 660     if (m_lexer->isReparsing())
 661         m_statementDepth--;
 662     ScopeRef scope = currentScope();
 663     SourceElements* sourceElements = parseSourceElements<CheckForStrictMode>(context);
 664     if (!sourceElements || !consume(EOFTOK))
 665         return m_errorMessage;
 666     IdentifierSet capturedVariables;
 667     scope->getCapturedVariables(capturedVariables);
 668     CodeFeatures features = context.features();
 669     if (scope->strictMode())
 670         features |= StrictModeFeature;
 671     if (scope->shadowsArguments())
 672         features |= ShadowsArgumentsFeature;
 673
 674     unsigned functionCacheSize = m_functionCache ? m_functionCache->byteSize() : 0;
 675     if (functionCacheSize != oldFunctionCacheSize)
 676         m_lexer->sourceProvider()->notifyCacheSizeChanged(functionCacheSize - oldFunctionCacheSize);
 677
 678     m_globalData->parser->didFinishParsing(sourceElements, context.varDeclarations(), context.funcDeclarations(), features,
 679                                            m_lastLine, context.numConstants(), capturedVariables);
 680     return 0;
 681 }
 682
 683 bool JSParser::allowAutomaticSemicolon()
 684 {
 685     return match(CLOSEBRACE) || match(EOFTOK) || m_lexer->prevTerminator();
 686 }
 687
 688 template <JSParser::SourceElementsMode mode, class TreeBuilder> TreeSourceElements JSParser::parseSourceElements(TreeBuilder& context)
 689 {
 690     TreeSourceElements sourceElements = context.createSourceElements();
 691     bool seenNonDirective = false;
 692     const Identifier* directive = 0;
 693     unsigned startOffset = m_token.m_info.startOffset;
 694     unsigned oldLastLineNumber = m_lexer->lastLineNumber();
 695     unsigned oldLineNumber = m_lexer->lineNumber();
 696     bool hasSetStrict = false;
 697     while (TreeStatement statement = parseStatement(context, directive)) {
 698         if (mode == CheckForStrictMode && !seenNonDirective) {
 699             if (directive) {
 700                 if (!hasSetStrict && m_globalData->propertyNames->useStrictIdentifier == *directive) {
 701                     setStrictMode();
 702                     hasSetStrict = true;
 703                     failIfFalse(isValidStrictMode());
 704                     m_lexer->setOffset(startOffset);
 705                     next();
 706                     m_lexer->setLastLineNumber(oldLastLineNumber);
 707                     m_lexer->setLineNumber(oldLineNumber);
 708                     failIfTrue(m_error);
 709                     continue;
 710                 }
 711             } else
 712                 seenNonDirective = true;
 713         }
 714         context.appendStatement(sourceElements, statement);
 715     }
 716
 717     if (m_error)
 718         fail();
 719     return sourceElements;
 720 }
 721
 722 template <class TreeBuilder> TreeStatement JSParser::parseVarDeclaration(TreeBuilder& context)
 723 {
 724     ASSERT(match(VAR));
 725     int start = tokenLine();
 726     int end = 0;
 727     int scratch;
 728     const Identifier* scratch1 = 0;
 729     TreeExpression scratch2 = 0;
 730     int scratch3 = 0;
 731     TreeExpression varDecls = parseVarDeclarationList(context, scratch, scratch1, scratch2, scratch3, scratch3, scratch3);
 732     failIfTrue(m_error);
 733     failIfFalse(autoSemiColon());
 734
 735     return context.createVarStatement(varDecls, start, end);
 736 }
 737
 738 template <class TreeBuilder> TreeStatement JSParser::parseConstDeclaration(TreeBuilder& context)
 739 {
 740     ASSERT(match(CONSTTOKEN));
 741     int start = tokenLine();
 742     int end = 0;
 743     TreeConstDeclList constDecls = parseConstDeclarationList(context);
 744     failIfTrue(m_error);
 745     failIfFalse(autoSemiColon());
 746
 747     return context.createConstStatement(constDecls, start, end);
 748 }
 749
 750 template <class TreeBuilder> TreeStatement JSParser::parseDoWhileStatement(TreeBuilder& context)
 751 {
 752     ASSERT(match(DO));
 753     int startLine = tokenLine();
 754     next();
 755     const Identifier* unused = 0;
 756     startLoop();
 757     TreeStatement statement = parseStatement(context, unused);
 758     endLoop();
 759     failIfFalse(statement);
 760     int endLine = tokenLine();
 761     consumeOrFail(WHILE);
 762     consumeOrFail(OPENPAREN);
 763     TreeExpression expr = parseExpression(context);
 764     failIfFalse(expr);
 765     consumeOrFail(CLOSEPAREN);
 766     if (match(SEMICOLON))
 767         next(); // Always performs automatic semicolon insertion.
 768     return context.createDoWhileStatement(statement, expr, startLine, endLine);
 769 }
 770
 771 template <class TreeBuilder> TreeStatement JSParser::parseWhileStatement(TreeBuilder& context)
 772 {
 773     ASSERT(match(WHILE));
 774     int startLine = tokenLine();
 775     next();
 776     consumeOrFail(OPENPAREN);
 777     TreeExpression expr = parseExpression(context);
 778     failIfFalse(expr);
 779     int endLine = tokenLine();
 780     consumeOrFail(CLOSEPAREN);
 781     const Identifier* unused = 0;
 782     startLoop();
 783     TreeStatement statement = parseStatement(context, unused);
 784     endLoop();
 785     failIfFalse(statement);
 786     return context.createWhileStatement(expr, statement, startLine, endLine);
 787 }
 788
 789 template <class TreeBuilder> TreeExpression JSParser::parseVarDeclarationList(TreeBuilder& context, int& declarations, const Identifier*& lastIdent, TreeExpression& lastInitializer, int& identStart, int& initStart, int& initEnd)
 790 {
 791     TreeExpression varDecls = 0;
 792     do {
 793         declarations++;
 794         next();
 795         matchOrFail(IDENT);
 796
 797         int varStart = tokenStart();
 798         identStart = varStart;
 799         const Identifier* name = m_token.m_data.ident;
 800         lastIdent = name;
 801         next();
 802         bool hasInitializer = match(EQUAL);
 803         failIfFalseIfStrict(declareVariable(name));
 804         context.addVar(name, (hasInitializer || (!m_allowsIn && match(INTOKEN))) ? DeclarationStacks::HasInitializer : 0);
 805         if (hasInitializer) {
 806             int varDivot = tokenStart() + 1;
 807             initStart = tokenStart();
 808             next(TreeBuilder::DontBuildStrings); // consume '='
 809             int initialAssignments = m_assignmentCount;
 810             TreeExpression initializer = parseAssignmentExpression(context);
 811             initEnd = lastTokenEnd();
 812             lastInitializer = initializer;
 813             failIfFalse(initializer);
 814
 815             TreeExpression node = context.createAssignResolve(*name, initializer, initialAssignments != m_assignmentCount, varStart, varDivot, lastTokenEnd());
 816             if (!varDecls)
 817                 varDecls = node;
 818             else
 819                 varDecls = context.combineCommaNodes(varDecls, node);
 820         }
 821     } while (match(COMMA));
 822     return varDecls;
 823 }
 824
 825 template <class TreeBuilder> TreeConstDeclList JSParser::parseConstDeclarationList(TreeBuilder& context)
 826 {
 827     failIfTrue(strictMode());
 828     TreeConstDeclList constDecls = 0;
 829     TreeConstDeclList tail = 0;
 830     do {
 831         next();
 832         matchOrFail(IDENT);
 833         const Identifier* name = m_token.m_data.ident;
 834         next();
 835         bool hasInitializer = match(EQUAL);
 836         declareVariable(name);
 837         context.addVar(name, DeclarationStacks::IsConstant | (hasInitializer ? DeclarationStacks::HasInitializer : 0));
 838         TreeExpression initializer = 0;
 839         if (hasInitializer) {
 840             next(TreeBuilder::DontBuildStrings); // consume '='
 841             initializer = parseAssignmentExpression(context);
 842         }
 843         tail = context.appendConstDecl(tail, name, initializer);
 844         if (!constDecls)
 845             constDecls = tail;
 846     } while (match(COMMA));
 847     return constDecls;
 848 }
 849
 850 template <class TreeBuilder> TreeStatement JSParser::parseForStatement(TreeBuilder& context)
 851 {
 852     ASSERT(match(FOR));
 853     int startLine = tokenLine();
 854     next();
 855     consumeOrFail(OPENPAREN);
 856     int nonLHSCount = m_nonLHSCount;
 857     int declarations = 0;
 858     int declsStart = 0;
 859     int declsEnd = 0;
 860     TreeExpression decls = 0;
 861     bool hasDeclaration = false;
 862     if (match(VAR)) {
 863         /*
 864          for (var IDENT in expression) statement
 865          for (var IDENT = expression in expression) statement
 866          for (var varDeclarationList; expressionOpt; expressionOpt)
 867          */
 868         hasDeclaration = true;
 869         const Identifier* forInTarget = 0;
 870         TreeExpression forInInitializer = 0;
 871         m_allowsIn = false;
 872         int initStart = 0;
 873         int initEnd = 0;
 874         decls = parseVarDeclarationList(context, declarations, forInTarget, forInInitializer, declsStart, initStart, initEnd);
 875         m_allowsIn = true;
 876         if (m_error)
 877             fail();
 878
 879         // Remainder of a standard for loop is handled identically
 880         if (match(SEMICOLON))
 881             goto standardForLoop;
 882
 883         failIfFalse(declarations == 1);
 884
 885         // Handle for-in with var declaration
 886         int inLocation = tokenStart();
 887         if (!consume(INTOKEN))
 888             fail();
 889
 890         TreeExpression expr = parseExpression(context);
 891         failIfFalse(expr);
 892         int exprEnd = lastTokenEnd();
 893
 894         int endLine = tokenLine();
 895         consumeOrFail(CLOSEPAREN);
 896
 897         const Identifier* unused = 0;
 898         startLoop();
 899         TreeStatement statement = parseStatement(context, unused);
 900         endLoop();
 901         failIfFalse(statement);
 902
 903         return context.createForInLoop(forInTarget, forInInitializer, expr, statement, declsStart, inLocation, exprEnd, initStart, initEnd, startLine, endLine);
 904     }
 905
 906     if (!match(SEMICOLON)) {
 907         m_allowsIn = false;
 908         declsStart = tokenStart();
 909         decls = parseExpression(context);
 910         declsEnd = lastTokenEnd();
 911         m_allowsIn = true;
 912         failIfFalse(decls);
 913     }
 914
 915     if (match(SEMICOLON)) {
 916     standardForLoop:
 917         // Standard for loop
 918         next();
 919         TreeExpression condition = 0;
 920
 921         if (!match(SEMICOLON)) {
 922             condition = parseExpression(context);
 923             failIfFalse(condition);
 924         }
 925         consumeOrFail(SEMICOLON);
 926
 927         TreeExpression increment = 0;
 928         if (!match(CLOSEPAREN)) {
 929             increment = parseExpression(context);
 930             failIfFalse(increment);
 931         }
 932         int endLine = tokenLine();
 933         consumeOrFail(CLOSEPAREN);
 934         const Identifier* unused = 0;
 935         startLoop();
 936         TreeStatement statement = parseStatement(context, unused);
 937         endLoop();
 938         failIfFalse(statement);
 939         return context.createForLoop(decls, condition, increment, statement, hasDeclaration, startLine, endLine);
 940     }
 941
 942     // For-in loop
 943     failIfFalse(nonLHSCount == m_nonLHSCount);
 944     consumeOrFail(INTOKEN);
 945     TreeExpression expr = parseExpression(context);
 946     failIfFalse(expr);
 947     int exprEnd = lastTokenEnd();
 948     int endLine = tokenLine();
 949     consumeOrFail(CLOSEPAREN);
 950     const Identifier* unused = 0;
 951     startLoop();
 952     TreeStatement statement = parseStatement(context, unused);
 953     endLoop();
 954     failIfFalse(statement);
 955
 956     return context.createForInLoop(decls, expr, statement, declsStart, declsEnd, exprEnd, startLine, endLine);
 957 }
 958
 959 template <class TreeBuilder> TreeStatement JSParser::parseBreakStatement(TreeBuilder& context)
 960 {
 961     ASSERT(match(BREAK));
 962     int startCol = tokenStart();
 963     int endCol = tokenEnd();
 964     int startLine = tokenLine();
 965     int endLine = tokenLine();
 966     next();
 967
 968     if (autoSemiColon()) {
 969         failIfFalse(breakIsValid());
 970         return context.createBreakStatement(startCol, endCol, startLine, endLine);
 971     }
 972     matchOrFail(IDENT);
 973     const Identifier* ident = m_token.m_data.ident;
 974     failIfFalse(getLabel(ident));
 975     endCol = tokenEnd();
 976     endLine = tokenLine();
 977     next();
 978     failIfFalse(autoSemiColon());
 979     return context.createBreakStatement(ident, startCol, endCol, startLine, endLine);
 980 }
 981
 982 template <class TreeBuilder> TreeStatement JSParser::parseContinueStatement(TreeBuilder& context)
 983 {
 984     ASSERT(match(CONTINUE));
 985     int startCol = tokenStart();
 986     int endCol = tokenEnd();
 987     int startLine = tokenLine();
 988     int endLine = tokenLine();
 989     next();
 990
 991     if (autoSemiColon()) {
 992         failIfFalse(continueIsValid());
 993         return context.createContinueStatement(startCol, endCol, startLine, endLine);
 994     }
 995     matchOrFail(IDENT);
 996     const Identifier* ident = m_token.m_data.ident;
 997     ScopeLabelInfo* label = getLabel(ident);
 998     failIfFalse(label);
 999     failIfFalse(label->m_isLoop);
1000     endCol = tokenEnd();
1001     endLine = tokenLine();
1002     next();
1003     failIfFalse(autoSemiColon());
1004     return context.createContinueStatement(ident, startCol, endCol, startLine, endLine);
1005 }
1006
1007 template <class TreeBuilder> TreeStatement JSParser::parseReturnStatement(TreeBuilder& context)
1008 {
1009     ASSERT(match(RETURN));
1010     failIfFalse(currentScope()->isFunction());
1011     int startLine = tokenLine();
1012     int endLine = startLine;
1013     int start = tokenStart();
1014     int end = tokenEnd();
1015     next();
1016     // We do the auto semicolon check before attempting to parse an expression
1017     // as we need to ensure the a line break after the return correctly terminates
1018     // the statement
1019     if (match(SEMICOLON))
1020         endLine  = tokenLine();
1021     if (autoSemiColon())
1022         return context.createReturnStatement(0, start, end, startLine, endLine);
1023     TreeExpression expr = parseExpression(context);
1024     failIfFalse(expr);
1025     end = lastTokenEnd();
1026     if (match(SEMICOLON))
1027         endLine  = tokenLine();
1028     failIfFalse(autoSemiColon());
1029     return context.createReturnStatement(expr, start, end, startLine, endLine);
1030 }
1031
1032 template <class TreeBuilder> TreeStatement JSParser::parseThrowStatement(TreeBuilder& context)
1033 {
1034     ASSERT(match(THROW));
1035     int eStart = tokenStart();
1036     int startLine = tokenLine();
1037     next();
1038
1039     failIfTrue(autoSemiColon());
1040
1041     TreeExpression expr = parseExpression(context);
1042     failIfFalse(expr);
1043     int eEnd = lastTokenEnd();
1044     int endLine = tokenLine();
1045     failIfFalse(autoSemiColon());
1046
1047     return context.createThrowStatement(expr, eStart, eEnd, startLine, endLine);
1048 }
1049
1050 template <class TreeBuilder> TreeStatement JSParser::parseWithStatement(TreeBuilder& context)
1051 {
1052     ASSERT(match(WITH));
1053     failIfTrue(strictMode());
1054     currentScope()->setNeedsFullActivation();
1055     int startLine = tokenLine();
1056     next();
1057     consumeOrFail(OPENPAREN);
1058     int start = tokenStart();
1059     TreeExpression expr = parseExpression(context);
1060     failIfFalse(expr);
1061     int end = lastTokenEnd();
1062
1063     int endLine = tokenLine();
1064     consumeOrFail(CLOSEPAREN);
1065     const Identifier* unused = 0;
1066     TreeStatement statement = parseStatement(context, unused);
1067     failIfFalse(statement);
1068
1069     return context.createWithStatement(expr, statement, start, end, startLine, endLine);
1070 }
1071
1072 template <class TreeBuilder> TreeStatement JSParser::parseSwitchStatement(TreeBuilder& context)
1073 {
1074     ASSERT(match(SWITCH));
1075     int startLine = tokenLine();
1076     next();
1077     consumeOrFail(OPENPAREN);
1078     TreeExpression expr = parseExpression(context);
1079     failIfFalse(expr);
1080     int endLine = tokenLine();
1081     consumeOrFail(CLOSEPAREN);
1082     consumeOrFail(OPENBRACE);
1083     startSwitch();
1084     TreeClauseList firstClauses = parseSwitchClauses(context);
1085     failIfTrue(m_error);
1086
1087     TreeClause defaultClause = parseSwitchDefaultClause(context);
1088     failIfTrue(m_error);
1089
1090     TreeClauseList secondClauses = parseSwitchClauses(context);
1091     failIfTrue(m_error);
1092     endSwitch();
1093     consumeOrFail(CLOSEBRACE);
1094
1095     return context.createSwitchStatement(expr, firstClauses, defaultClause, secondClauses, startLine, endLine);
1096
1097 }
1098
1099 template <class TreeBuilder> TreeClauseList JSParser::parseSwitchClauses(TreeBuilder& context)
1100 {
1101     if (!match(CASE))
1102         return 0;
1103     next();
1104     TreeExpression condition = parseExpression(context);
1105     failIfFalse(condition);
1106     consumeOrFail(COLON);
1107     TreeSourceElements statements = parseSourceElements<DontCheckForStrictMode>(context);
1108     failIfFalse(statements);
1109     TreeClause clause = context.createClause(condition, statements);
1110     TreeClauseList clauseList = context.createClauseList(clause);
1111     TreeClauseList tail = clauseList;
1112
1113     while (match(CASE)) {
1114         next();
1115         TreeExpression condition = parseExpression(context);
1116         failIfFalse(condition);
1117         consumeOrFail(COLON);
1118         TreeSourceElements statements = parseSourceElements<DontCheckForStrictMode>(context);
1119         failIfFalse(statements);
1120         clause = context.createClause(condition, statements);
1121         tail = context.createClauseList(tail, clause);
1122     }
1123     return clauseList;
1124 }
1125
1126 template <class TreeBuilder> TreeClause JSParser::parseSwitchDefaultClause(TreeBuilder& context)
1127 {
1128     if (!match(DEFAULT))
1129         return 0;
1130     next();
1131     consumeOrFail(COLON);
1132     TreeSourceElements statements = parseSourceElements<DontCheckForStrictMode>(context);
1133     failIfFalse(statements);
1134     return context.createClause(0, statements);
1135 }
1136
1137 template <class TreeBuilder> TreeStatement JSParser::parseTryStatement(TreeBuilder& context)
1138 {
1139     ASSERT(match(TRY));
1140     TreeStatement tryBlock = 0;
1141     const Identifier* ident = &m_globalData->propertyNames->nullIdentifier;
1142     bool catchHasEval = false;
1143     TreeStatement catchBlock = 0;
1144     TreeStatement finallyBlock = 0;
1145     int firstLine = tokenLine();
1146     next();
1147     matchOrFail(OPENBRACE);
1148
1149     tryBlock = parseBlockStatement(context);
1150     failIfFalse(tryBlock);
1151     int lastLine = m_lastLine;
1152
1153     if (match(CATCH)) {
1154         currentScope()->setNeedsFullActivation();
1155         next();
1156         consumeOrFail(OPENPAREN);
1157         matchOrFail(IDENT);
1158         ident = m_token.m_data.ident;
1159         next();
1160         AutoPopScopeRef catchScope(this, pushScope());
1161         failIfFalseIfStrict(catchScope->declareVariable(ident));
1162         catchScope->preventNewDecls();
1163         consumeOrFail(CLOSEPAREN);
1164         matchOrFail(OPENBRACE);
1165         int initialEvalCount = context.evalCount();
1166         catchBlock = parseBlockStatement(context);
1167         failIfFalse(catchBlock);
1168         catchHasEval = initialEvalCount != context.evalCount();
1169         failIfFalse(popScope(catchScope, TreeBuilder::NeedsFreeVariableInfo));
1170     }
1171
1172     if (match(FINALLY)) {
1173         next();
1174         matchOrFail(OPENBRACE);
1175         finallyBlock = parseBlockStatement(context);
1176         failIfFalse(finallyBlock);
1177     }
1178     failIfFalse(catchBlock || finallyBlock);
1179     return context.createTryStatement(tryBlock, ident, catchHasEval, catchBlock, finallyBlock, firstLine, lastLine);
1180 }
1181
1182 template <class TreeBuilder> TreeStatement JSParser::parseDebuggerStatement(TreeBuilder& context)
1183 {
1184     ASSERT(match(DEBUGGER));
1185     int startLine = tokenLine();
1186     int endLine = startLine;
1187     next();
1188     if (match(SEMICOLON))
1189         startLine = tokenLine();
1190     failIfFalse(autoSemiColon());
1191     return context.createDebugger(startLine, endLine);
1192 }
1193
1194 template <class TreeBuilder> TreeStatement JSParser::parseBlockStatement(TreeBuilder& context)
1195 {
1196     ASSERT(match(OPENBRACE));
1197     int start = tokenLine();
1198     next();
1199     if (match(CLOSEBRACE)) {
1200         next();
1201         return context.createBlockStatement(0, start, m_lastLine);
1202     }
1203     TreeSourceElements subtree = parseSourceElements<DontCheckForStrictMode>(context);
1204     failIfFalse(subtree);
1205     matchOrFail(CLOSEBRACE);
1206     next();
1207     return context.createBlockStatement(subtree, start, m_lastLine);
1208 }
1209
1210 template <class TreeBuilder> TreeStatement JSParser::parseStatement(TreeBuilder& context, const Identifier*& directive)
1211 {
1212     DepthManager statementDepth(&m_statementDepth);
1213     m_statementDepth++;
1214     directive = 0;
1215     int nonTrivialExpressionCount = 0;
1216     failIfStackOverflow();
1217     switch (m_token.m_type) {
1218     case OPENBRACE:
1219         return parseBlockStatement(context);
1220     case VAR:
1221         return parseVarDeclaration(context);
1222     case CONSTTOKEN:
1223         return parseConstDeclaration(context);
1224     case FUNCTION:
1225         failIfFalseIfStrict(m_statementDepth == 1);
1226         return parseFunctionDeclaration(context);
1227     case SEMICOLON:
1228         next();
1229         return context.createEmptyStatement();
1230     case IF:
1231         return parseIfStatement(context);
1232     case DO:
1233         return parseDoWhileStatement(context);
1234     case WHILE:
1235         return parseWhileStatement(context);
1236     case FOR:
1237         return parseForStatement(context);
1238     case CONTINUE:
1239         return parseContinueStatement(context);
1240     case BREAK:
1241         return parseBreakStatement(context);
1242     case RETURN:
1243         return parseReturnStatement(context);
1244     case WITH:
1245         return parseWithStatement(context);
1246     case SWITCH:
1247         return parseSwitchStatement(context);
1248     case THROW:
1249         return parseThrowStatement(context);
1250     case TRY:
1251         return parseTryStatement(context);
1252     case DEBUGGER:
1253         return parseDebuggerStatement(context);
1254     case EOFTOK:
1255     case CASE:
1256     case CLOSEBRACE:
1257     case DEFAULT:
1258         // These tokens imply the end of a set of source elements
1259         return 0;
1260     case IDENT:
1261         return parseExpressionOrLabelStatement(context);
1262     case STRING:
1263         directive = m_token.m_data.ident;
1264         nonTrivialExpressionCount = m_nonTrivialExpressionCount;
1265     default:
1266         TreeStatement exprStatement = parseExpressionStatement(context);
1267         if (directive && nonTrivialExpressionCount != m_nonTrivialExpressionCount)
1268             directive = 0;
1269         return exprStatement;
1270     }
1271 }
1272
1273 template <class TreeBuilder> TreeFormalParameterList JSParser::parseFormalParameters(TreeBuilder& context)
1274 {
1275     matchOrFail(IDENT);
1276     failIfFalseIfStrict(declareParameter(m_token.m_data.ident));
1277     TreeFormalParameterList list = context.createFormalParameterList(*m_token.m_data.ident);
1278     TreeFormalParameterList tail = list;
1279     next();
1280     while (match(COMMA)) {
1281         next();
1282         matchOrFail(IDENT);
1283         const Identifier* ident = m_token.m_data.ident;
1284         failIfFalseIfStrict(declareParameter(ident));
1285         next();
1286         tail = context.createFormalParameterList(tail, *ident);
1287     }
1288     return list;
1289 }
1290
1291 template <class TreeBuilder> TreeFunctionBody JSParser::parseFunctionBody(TreeBuilder& context)
1292 {
1293     if (match(CLOSEBRACE))
1294         return context.createFunctionBody(strictMode());
1295     DepthManager statementDepth(&m_statementDepth);
1296     m_statementDepth = 0;
1297     typename TreeBuilder::FunctionBodyBuilder bodyBuilder(m_globalData, m_lexer);
1298     failIfFalse(parseSourceElements<CheckForStrictMode>(bodyBuilder));
1299     return context.createFunctionBody(strictMode());
1300 }
1301
1302 template <JSParser::FunctionRequirements requirements, bool nameIsInContainingScope, class TreeBuilder> bool JSParser::parseFunctionInfo(TreeBuilder& context, const Identifier*& name, TreeFormalParameterList& parameters, TreeFunctionBody& body, int& openBracePos, int& closeBracePos, int& bodyStartLine)
1303 {
1304     AutoPopScopeRef functionScope(this, pushScope());
1305     functionScope->setIsFunction();
1306     if (match(IDENT)) {
1307         name = m_token.m_data.ident;
1308         failIfTrue(*name == m_globalData->propertyNames->underscoreProto);
1309         next();
1310         if (!nameIsInContainingScope)
1311             failIfFalseIfStrict(functionScope->declareVariable(name));
1312     } else if (requirements == FunctionNeedsName)
1313         return false;
1314     consumeOrFail(OPENPAREN);
1315     if (!match(CLOSEPAREN)) {
1316         parameters = parseFormalParameters(context);
1317         failIfFalse(parameters);
1318     }
1319     consumeOrFail(CLOSEPAREN);
1320     matchOrFail(OPENBRACE);
1321
1322     openBracePos = m_token.m_data.intValue;
1323     bodyStartLine = tokenLine();
1324
1325     if (const SourceProviderCacheItem* cachedInfo = TreeBuilder::CanUseFunctionCache ? findCachedFunctionInfo(openBracePos) : 0) {
1326         // If we know about this function already, we can use the cached info and skip the parser to the end of the function.
1327         body = context.createFunctionBody(strictMode());
1328
1329         functionScope->restoreFunctionInfo(cachedInfo);
1330         failIfFalse(popScope(functionScope, TreeBuilder::NeedsFreeVariableInfo));
1331
1332         closeBracePos = cachedInfo->closeBracePos;
1333         m_token = cachedInfo->closeBraceToken();
1334         m_lexer->setOffset(m_token.m_info.endOffset);
1335         m_lexer->setLineNumber(m_token.m_info.line);
1336
1337         next();
1338         return true;
1339     }
1340
1341     next();
1342
1343     body = parseFunctionBody(context);
1344     failIfFalse(body);
1345     if (functionScope->strictMode() && name) {
1346         failIfTrue(m_globalData->propertyNames->arguments == *name);
1347         failIfTrue(m_globalData->propertyNames->eval == *name);
1348     }
1349     closeBracePos = m_token.m_data.intValue;
1350
1351     // Cache the tokenizer state and the function scope the first time the function is parsed.
1352     // Any future reparsing can then skip the function.
1353     static const int minimumFunctionLengthToCache = 64;
1354     OwnPtr<SourceProviderCacheItem> newInfo;
1355     int functionLength = closeBracePos - openBracePos;
1356     if (TreeBuilder::CanUseFunctionCache && m_functionCache && functionLength > minimumFunctionLengthToCache) {
1357         newInfo = adoptPtr(new SourceProviderCacheItem(m_token.m_info.line, closeBracePos));
1358         functionScope->saveFunctionInfo(newInfo.get());
1359     }
1360
1361     failIfFalse(popScope(functionScope, TreeBuilder::NeedsFreeVariableInfo));
1362     matchOrFail(CLOSEBRACE);
1363
1364     if (newInfo) {
1365         unsigned approximateByteSize = newInfo->approximateByteSize();
1366         m_functionCache->add(openBracePos, newInfo.release(), approximateByteSize);
1367     }
1368
1369     next();
1370     return true;
1371 }
1372
1373 template <class TreeBuilder> TreeStatement JSParser::parseFunctionDeclaration(TreeBuilder& context)
1374 {
1375     ASSERT(match(FUNCTION));
1376     next();
1377     const Identifier* name = 0;
1378     TreeFormalParameterList parameters = 0;
1379     TreeFunctionBody body = 0;
1380     int openBracePos = 0;
1381     int closeBracePos = 0;
1382     int bodyStartLine = 0;
1383     failIfFalse((parseFunctionInfo<FunctionNeedsName, true>(context, name, parameters, body, openBracePos, closeBracePos, bodyStartLine)));
1384     failIfFalse(name);
1385     failIfFalseIfStrict(declareVariable(name));
1386     return context.createFuncDeclStatement(name, body, parameters, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
1387 }
1388
1389 struct LabelInfo {
1390     LabelInfo(const Identifier* ident, int start, int end)
1391         : m_ident(ident)
1392         , m_start(start)
1393         , m_end(end)
1394     {
1395     }
1396
1397     const Identifier* m_ident;
1398     int m_start;
1399     int m_end;
1400 };
1401
1402 template <class TreeBuilder> TreeStatement JSParser::parseExpressionOrLabelStatement(TreeBuilder& context)
1403 {
1404
1405     /* Expression and Label statements are ambiguous at LL(1), so we have a
1406      * special case that looks for a colon as the next character in the input.
1407      */
1408     Vector<LabelInfo> labels;
1409
1410     do {
1411         int start = tokenStart();
1412         int startLine = tokenLine();
1413         if (!nextTokenIsColon()) {
1414             // If we hit this path we're making a expression statement, which
1415             // by definition can't make use of continue/break so we can just
1416             // ignore any labels we might have accumulated.
1417             TreeExpression expression = parseExpression(context);
1418             failIfFalse(expression);
1419             failIfFalse(autoSemiColon());
1420             return context.createExprStatement(expression, startLine, m_lastLine);
1421         }
1422         const Identifier* ident = m_token.m_data.ident;
1423         int end = tokenEnd();
1424         next();
1425         consumeOrFail(COLON);
1426         if (!m_syntaxAlreadyValidated) {
1427             // This is O(N^2) over the current list of consecutive labels, but I
1428             // have never seen more than one label in a row in the real world.
1429             for (size_t i = 0; i < labels.size(); i++)
1430                 failIfTrue(ident->impl() == labels[i].m_ident->impl());
1431             failIfTrue(getLabel(ident));
1432             labels.append(LabelInfo(ident, start, end));
1433         }
1434     } while (match(IDENT));
1435     bool isLoop = false;
1436     switch (m_token.m_type) {
1437     case FOR:
1438     case WHILE:
1439     case DO:
1440         isLoop = true;
1441         break;
1442
1443     default:
1444         break;
1445     }
1446     const Identifier* unused = 0;
1447     if (!m_syntaxAlreadyValidated) {
1448         for (size_t i = 0; i < labels.size(); i++)
1449             pushLabel(labels[i].m_ident, isLoop);
1450     }
1451     TreeStatement statement = parseStatement(context, unused);
1452     if (!m_syntaxAlreadyValidated) {
1453         for (size_t i = 0; i < labels.size(); i++)
1454             popLabel();
1455     }
1456     failIfFalse(statement);
1457     for (size_t i = 0; i < labels.size(); i++) {
1458         const LabelInfo& info = labels[labels.size() - i - 1];
1459         statement = context.createLabelStatement(info.m_ident, statement, info.m_start, info.m_end);
1460     }
1461     return statement;
1462 }
1463
1464 template <class TreeBuilder> TreeStatement JSParser::parseExpressionStatement(TreeBuilder& context)
1465 {
1466     int startLine = tokenLine();
1467     TreeExpression expression = parseExpression(context);
1468     failIfFalse(expression);
1469     failIfFalse(autoSemiColon());
1470     return context.createExprStatement(expression, startLine, m_lastLine);
1471 }
1472
1473 template <class TreeBuilder> TreeStatement JSParser::parseIfStatement(TreeBuilder& context)
1474 {
1475     ASSERT(match(IF));
1476
1477     int start = tokenLine();
1478     next();
1479
1480     consumeOrFail(OPENPAREN);
1481
1482     TreeExpression condition = parseExpression(context);
1483     failIfFalse(condition);
1484     int end = tokenLine();
1485     consumeOrFail(CLOSEPAREN);
1486
1487     const Identifier* unused = 0;
1488     TreeStatement trueBlock = parseStatement(context, unused);
1489     failIfFalse(trueBlock);
1490
1491     if (!match(ELSE))
1492         return context.createIfStatement(condition, trueBlock, start, end);
1493
1494     Vector<TreeExpression> exprStack;
1495     Vector<pair<int, int> > posStack;
1496     Vector<TreeStatement> statementStack;
1497     bool trailingElse = false;
1498     do {
1499         next();
1500         if (!match(IF)) {
1501             const Identifier* unused = 0;
1502             TreeStatement block = parseStatement(context, unused);
1503             failIfFalse(block);
1504             statementStack.append(block);
1505             trailingElse = true;
1506             break;
1507         }
1508         int innerStart = tokenLine();
1509         next();
1510
1511         consumeOrFail(OPENPAREN);
1512
1513         TreeExpression innerCondition = parseExpression(context);
1514         failIfFalse(innerCondition);
1515         int innerEnd = tokenLine();
1516         consumeOrFail(CLOSEPAREN);
1517         const Identifier* unused = 0;
1518         TreeStatement innerTrueBlock = parseStatement(context, unused);
1519         failIfFalse(innerTrueBlock);
1520         exprStack.append(innerCondition);
1521         posStack.append(make_pair(innerStart, innerEnd));
1522         statementStack.append(innerTrueBlock);
1523     } while (match(ELSE));
1524
1525     if (!trailingElse) {
1526         TreeExpression condition = exprStack.last();
1527         exprStack.removeLast();
1528         TreeStatement trueBlock = statementStack.last();
1529         statementStack.removeLast();
1530         pair<int, int> pos = posStack.last();
1531         posStack.removeLast();
1532         statementStack.append(context.createIfStatement(condition, trueBlock, pos.first, pos.second));
1533     }
1534
1535     while (!exprStack.isEmpty()) {
1536         TreeExpression condition = exprStack.last();
1537         exprStack.removeLast();
1538         TreeStatement falseBlock = statementStack.last();
1539         statementStack.removeLast();
1540         TreeStatement trueBlock = statementStack.last();
1541         statementStack.removeLast();
1542         pair<int, int> pos = posStack.last();
1543         posStack.removeLast();
1544         statementStack.append(context.createIfStatement(condition, trueBlock, falseBlock, pos.first, pos.second));
1545     }
1546
1547     return context.createIfStatement(condition, trueBlock, statementStack.last(), start, end);
1548 }
1549
1550 template <class TreeBuilder> TreeExpression JSParser::parseExpression(TreeBuilder& context)
1551 {
1552     failIfStackOverflow();
1553     TreeExpression node = parseAssignmentExpression(context);
1554     failIfFalse(node);
1555     if (!match(COMMA))
1556         return node;
1557     next();
1558     m_nonTrivialExpressionCount++;
1559     m_nonLHSCount++;
1560     TreeExpression right = parseAssignmentExpression(context);
1561     failIfFalse(right);
1562     typename TreeBuilder::Comma commaNode = context.createCommaExpr(node, right);
1563     while (match(COMMA)) {
1564         next(TreeBuilder::DontBuildStrings);
1565         right = parseAssignmentExpression(context);
1566         failIfFalse(right);
1567         context.appendToComma(commaNode, right);
1568     }
1569     return commaNode;
1570 }
1571
1572
1573 template <typename TreeBuilder> TreeExpression JSParser::parseAssignmentExpression(TreeBuilder& context)
1574 {
1575     failIfStackOverflow();
1576     int start = tokenStart();
1577     int initialAssignmentCount = m_assignmentCount;
1578     int initialNonLHSCount = m_nonLHSCount;
1579     TreeExpression lhs = parseConditionalExpression(context);
1580     failIfFalse(lhs);
1581     if (initialNonLHSCount != m_nonLHSCount)
1582         return lhs;
1583
1584     int assignmentStack = 0;
1585     Operator op;
1586     bool hadAssignment = false;
1587     while (true) {
1588         switch (m_token.m_type) {
1589         case EQUAL: op = OpEqual; break;
1590         case PLUSEQUAL: op = OpPlusEq; break;
1591         case MINUSEQUAL: op = OpMinusEq; break;
1592         case MULTEQUAL: op = OpMultEq; break;
1593         case DIVEQUAL: op = OpDivEq; break;
1594         case LSHIFTEQUAL: op = OpLShift; break;
1595         case RSHIFTEQUAL: op = OpRShift; break;
1596         case URSHIFTEQUAL: op = OpURShift; break;
1597         case ANDEQUAL: op = OpAndEq; break;
1598         case XOREQUAL: op = OpXOrEq; break;
1599         case OREQUAL: op = OpOrEq; break;
1600         case MODEQUAL: op = OpModEq; break;
1601         default:
1602             goto end;
1603         }
1604         m_nonTrivialExpressionCount++;
1605         hadAssignment = true;
1606         context.assignmentStackAppend(assignmentStack, lhs, start, tokenStart(), m_assignmentCount, op);
1607         start = tokenStart();
1608         m_assignmentCount++;
1609         next(TreeBuilder::DontBuildStrings);
1610         if (strictMode() && m_lastIdentifier && context.isResolve(lhs)) {
1611             failIfTrueIfStrict(m_globalData->propertyNames->eval == *m_lastIdentifier);
1612             failIfTrueIfStrict(m_globalData->propertyNames->arguments == *m_lastIdentifier);
1613             declareWrite(m_lastIdentifier);
1614             m_lastIdentifier = 0;
1615         }
1616         lhs = parseConditionalExpression(context);
1617         failIfFalse(lhs);
1618         if (initialNonLHSCount != m_nonLHSCount)
1619             break;
1620     }
1621 end:
1622     if (hadAssignment)
1623         m_nonLHSCount++;
1624
1625     if (!TreeBuilder::CreatesAST)
1626         return lhs;
1627
1628     while (assignmentStack)
1629         lhs = context.createAssignment(assignmentStack, lhs, initialAssignmentCount, m_assignmentCount, lastTokenEnd());
1630
1631     return lhs;
1632 }
1633
1634 template <class TreeBuilder> TreeExpression JSParser::parseConditionalExpression(TreeBuilder& context)
1635 {
1636     TreeExpression cond = parseBinaryExpression(context);
1637     failIfFalse(cond);
1638     if (!match(QUESTION))
1639         return cond;
1640     m_nonTrivialExpressionCount++;
1641     m_nonLHSCount++;
1642     next(TreeBuilder::DontBuildStrings);
1643     TreeExpression lhs = parseAssignmentExpression(context);
1644     consumeOrFailWithFlags(COLON, TreeBuilder::DontBuildStrings);
1645
1646     TreeExpression rhs = parseAssignmentExpression(context);
1647     failIfFalse(rhs);
1648     return context.createConditionalExpr(cond, lhs, rhs);
1649 }
1650
1651 ALWAYS_INLINE static bool isUnaryOp(JSTokenType token)
1652 {
1653     return token & UnaryOpTokenFlag;
1654 }
1655
1656 int JSParser::isBinaryOperator(JSTokenType token)
1657 {
1658     if (m_allowsIn)
1659         return token & (BinaryOpTokenPrecedenceMask << BinaryOpTokenAllowsInPrecedenceAdditionalShift);
1660     return token & BinaryOpTokenPrecedenceMask;
1661 }
1662
1663 template <class TreeBuilder> TreeExpression JSParser::parseBinaryExpression(TreeBuilder& context)
1664 {
1665
1666     int operandStackDepth = 0;
1667     int operatorStackDepth = 0;
1668     typename TreeBuilder::BinaryExprContext binaryExprContext(context);
1669     while (true) {
1670         int exprStart = tokenStart();
1671         int initialAssignments = m_assignmentCount;
1672         TreeExpression current = parseUnaryExpression(context);
1673         failIfFalse(current);
1674
1675         context.appendBinaryExpressionInfo(operandStackDepth, current, exprStart, lastTokenEnd(), lastTokenEnd(), initialAssignments != m_assignmentCount);
1676         int precedence = isBinaryOperator(m_token.m_type);
1677         if (!precedence)
1678             break;
1679         m_nonTrivialExpressionCount++;
1680         m_nonLHSCount++;
1681         int operatorToken = m_token.m_type;
1682         next(TreeBuilder::DontBuildStrings);
1683
1684         while (operatorStackDepth &&  context.operatorStackHasHigherPrecedence(operatorStackDepth, precedence)) {
1685             ASSERT(operandStackDepth > 1);
1686
1687             typename TreeBuilder::BinaryOperand rhs = context.getFromOperandStack(-1);
1688             typename TreeBuilder::BinaryOperand lhs = context.getFromOperandStack(-2);
1689             context.shrinkOperandStackBy(operandStackDepth, 2);
1690             context.appendBinaryOperation(operandStackDepth, operatorStackDepth, lhs, rhs);
1691             context.operatorStackPop(operatorStackDepth);
1692         }
1693         context.operatorStackAppend(operatorStackDepth, operatorToken, precedence);
1694     }
1695     while (operatorStackDepth) {
1696         ASSERT(operandStackDepth > 1);
1697
1698         typename TreeBuilder::BinaryOperand rhs = context.getFromOperandStack(-1);
1699         typename TreeBuilder::BinaryOperand lhs = context.getFromOperandStack(-2);
1700         context.shrinkOperandStackBy(operandStackDepth, 2);
1701         context.appendBinaryOperation(operandStackDepth, operatorStackDepth, lhs, rhs);
1702         context.operatorStackPop(operatorStackDepth);
1703     }
1704     return context.popOperandStack(operandStackDepth);
1705 }
1706
1707
1708 template <bool complete, class TreeBuilder> TreeProperty JSParser::parseProperty(TreeBuilder& context)
1709 {
1710     bool wasIdent = false;
1711     switch (m_token.m_type) {
1712     namedProperty:
1713     case IDENT:
1714         wasIdent = true;
1715     case STRING: {
1716         const Identifier* ident = m_token.m_data.ident;
1717         if (complete || (wasIdent && (*ident == m_globalData->propertyNames->get || *ident == m_globalData->propertyNames->set)))
1718             nextExpectIdentifier(Lexer::IgnoreReservedWords);
1719         else
1720             nextExpectIdentifier(Lexer::IgnoreReservedWords | TreeBuilder::DontBuildKeywords);
1721
1722         if (match(COLON)) {
1723             next();
1724             TreeExpression node = parseAssignmentExpression(context);
1725             failIfFalse(node);
1726             return context.template createProperty<complete>(ident, node, PropertyNode::Constant);
1727         }
1728         failIfFalse(wasIdent);
1729         matchOrFail(IDENT);
1730         const Identifier* accessorName = 0;
1731         TreeFormalParameterList parameters = 0;
1732         TreeFunctionBody body = 0;
1733         int openBracePos = 0;
1734         int closeBracePos = 0;
1735         int bodyStartLine = 0;
1736         PropertyNode::Type type;
1737         if (*ident == m_globalData->propertyNames->get)
1738             type = PropertyNode::Getter;
1739         else if (*ident == m_globalData->propertyNames->set)
1740             type = PropertyNode::Setter;
1741         else
1742             fail();
1743         failIfFalse((parseFunctionInfo<FunctionNeedsName, false>(context, accessorName, parameters, body, openBracePos, closeBracePos, bodyStartLine)));
1744         return context.template createGetterOrSetterProperty<complete>(type, accessorName, parameters, body, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
1745     }
1746     case NUMBER: {
1747         double propertyName = m_token.m_data.doubleValue;
1748         next();
1749         consumeOrFail(COLON);
1750         TreeExpression node = parseAssignmentExpression(context);
1751         failIfFalse(node);
1752         return context.template createProperty<complete>(m_globalData, propertyName, node, PropertyNode::Constant);
1753     }
1754     default:
1755         failIfFalse(m_token.m_type & KeywordTokenFlag);
1756         goto namedProperty;
1757     }
1758 }
1759
1760 template <class TreeBuilder> TreeExpression JSParser::parseObjectLiteral(TreeBuilder& context)
1761 {
1762     int startOffset = m_token.m_data.intValue;
1763     consumeOrFailWithFlags(OPENBRACE, TreeBuilder::DontBuildStrings);
1764
1765     if (match(CLOSEBRACE)) {
1766         next();
1767         return context.createObjectLiteral();
1768     }
1769
1770     TreeProperty property = parseProperty<false>(context);
1771     failIfFalse(property);
1772     if (!m_syntaxAlreadyValidated && context.getType(property) != PropertyNode::Constant) {
1773         m_lexer->setOffset(startOffset);
1774         next();
1775         return parseStrictObjectLiteral(context);
1776     }
1777     TreePropertyList propertyList = context.createPropertyList(property);
1778     TreePropertyList tail = propertyList;
1779     while (match(COMMA)) {
1780         next(TreeBuilder::DontBuildStrings);
1781         // allow extra comma, see http://bugs.webkit.org/show_bug.cgi?id=5939
1782         if (match(CLOSEBRACE))
1783             break;
1784         property = parseProperty<false>(context);
1785         failIfFalse(property);
1786         if (!m_syntaxAlreadyValidated && context.getType(property) != PropertyNode::Constant) {
1787             m_lexer->setOffset(startOffset);
1788             next();
1789             return parseStrictObjectLiteral(context);
1790         }
1791         tail = context.createPropertyList(property, tail);
1792     }
1793
1794     consumeOrFail(CLOSEBRACE);
1795
1796     return context.createObjectLiteral(propertyList);
1797 }
1798
1799 template <class TreeBuilder> TreeExpression JSParser::parseStrictObjectLiteral(TreeBuilder& context)
1800 {
1801     consumeOrFail(OPENBRACE);
1802
1803     if (match(CLOSEBRACE)) {
1804         next();
1805         return context.createObjectLiteral();
1806     }
1807
1808     TreeProperty property = parseProperty<true>(context);
1809     failIfFalse(property);
1810
1811     typedef HashMap<RefPtr<StringImpl>, unsigned, IdentifierRepHash> ObjectValidationMap;
1812     ObjectValidationMap objectValidator;
1813     // Add the first property
1814     if (!m_syntaxAlreadyValidated)
1815         objectValidator.add(context.getName(property).impl(), context.getType(property));
1816
1817     TreePropertyList propertyList = context.createPropertyList(property);
1818     TreePropertyList tail = propertyList;
1819     while (match(COMMA)) {
1820         next();
1821         // allow extra comma, see http://bugs.webkit.org/show_bug.cgi?id=5939
1822         if (match(CLOSEBRACE))
1823             break;
1824         property = parseProperty<true>(context);
1825         failIfFalse(property);
1826         if (!m_syntaxAlreadyValidated) {
1827             std::pair<ObjectValidationMap::iterator, bool> propertyEntryIter = objectValidator.add(context.getName(property).impl(), context.getType(property));
1828             if (!propertyEntryIter.second) {
1829                 failIfTrue(propertyEntryIter.first->second == PropertyNode::Constant);
1830                 failIfTrue(context.getType(property) == PropertyNode::Constant);
1831                 failIfTrue(context.getType(property) & propertyEntryIter.first->second);
1832                 propertyEntryIter.first->second |= context.getType(property);
1833             }
1834         }
1835         tail = context.createPropertyList(property, tail);
1836     }
1837
1838     consumeOrFail(CLOSEBRACE);
1839
1840     return context.createObjectLiteral(propertyList);
1841 }
1842
1843 template <class TreeBuilder> TreeExpression JSParser::parseArrayLiteral(TreeBuilder& context)
1844 {
1845     consumeOrFailWithFlags(OPENBRACKET, TreeBuilder::DontBuildStrings);
1846
1847     int elisions = 0;
1848     while (match(COMMA)) {
1849         next(TreeBuilder::DontBuildStrings);
1850         elisions++;
1851     }
1852     if (match(CLOSEBRACKET)) {
1853         next(TreeBuilder::DontBuildStrings);
1854         return context.createArray(elisions);
1855     }
1856
1857     TreeExpression elem = parseAssignmentExpression(context);
1858     failIfFalse(elem);
1859     typename TreeBuilder::ElementList elementList = context.createElementList(elisions, elem);
1860     typename TreeBuilder::ElementList tail = elementList;
1861     elisions = 0;
1862     while (match(COMMA)) {
1863         next(TreeBuilder::DontBuildStrings);
1864         elisions = 0;
1865
1866         while (match(COMMA)) {
1867             next();
1868             elisions++;
1869         }
1870
1871         if (match(CLOSEBRACKET)) {
1872             next(TreeBuilder::DontBuildStrings);
1873             return context.createArray(elisions, elementList);
1874         }
1875         TreeExpression elem = parseAssignmentExpression(context);
1876         failIfFalse(elem);
1877         tail = context.createElementList(tail, elisions, elem);
1878     }
1879
1880     consumeOrFail(CLOSEBRACKET);
1881
1882     return context.createArray(elementList);
1883 }
1884
1885 template <class TreeBuilder> TreeExpression JSParser::parsePrimaryExpression(TreeBuilder& context)
1886 {
1887     switch (m_token.m_type) {
1888     case OPENBRACE:
1889         if (strictMode())
1890             return parseStrictObjectLiteral(context);
1891         return parseObjectLiteral(context);
1892     case OPENBRACKET:
1893         return parseArrayLiteral(context);
1894     case OPENPAREN: {
1895         next();
1896         int oldNonLHSCount = m_nonLHSCount;
1897         TreeExpression result = parseExpression(context);
1898         m_nonLHSCount = oldNonLHSCount;
1899         consumeOrFail(CLOSEPAREN);
1900
1901         return result;
1902     }
1903     case THISTOKEN: {
1904         next();
1905         return context.thisExpr();
1906     }
1907     case IDENT: {
1908         int start = tokenStart();
1909         const Identifier* ident = m_token.m_data.ident;
1910         next();
1911         currentScope()->useVariable(ident, m_globalData->propertyNames->eval == *ident);
1912         m_lastIdentifier = ident;
1913         return context.createResolve(ident, start);
1914     }
1915     case STRING: {
1916         const Identifier* ident = m_token.m_data.ident;
1917         next();
1918         return context.createString(ident);
1919     }
1920     case NUMBER: {
1921         double d = m_token.m_data.doubleValue;
1922         next();
1923         return context.createNumberExpr(d);
1924     }
1925     case NULLTOKEN: {
1926         next();
1927         return context.createNull();
1928     }
1929     case TRUETOKEN: {
1930         next();
1931         return context.createBoolean(true);
1932     }
1933     case FALSETOKEN: {
1934         next();
1935         return context.createBoolean(false);
1936     }
1937     case DIVEQUAL:
1938     case DIVIDE: {
1939         /* regexp */
1940         const Identifier* pattern;
1941         const Identifier* flags;
1942         if (match(DIVEQUAL))
1943             failIfFalse(m_lexer->scanRegExp(pattern, flags, '='));
1944         else
1945             failIfFalse(m_lexer->scanRegExp(pattern, flags));
1946
1947         int start = tokenStart();
1948         next();
1949         TreeExpression re = context.createRegExp(*pattern, *flags, start);
1950         if (!re) {
1951             m_errorMessage = Yarr::checkSyntax(pattern->ustring());
1952             ASSERT(m_errorMessage);
1953             fail();
1954         }
1955         return re;
1956     }
1957     default:
1958         fail();
1959     }
1960 }
1961
1962 template <class TreeBuilder> TreeArguments JSParser::parseArguments(TreeBuilder& context)
1963 {
1964     consumeOrFailWithFlags(OPENPAREN, TreeBuilder::DontBuildStrings);
1965     if (match(CLOSEPAREN)) {
1966         next(TreeBuilder::DontBuildStrings);
1967         return context.createArguments();
1968     }
1969     TreeExpression firstArg = parseAssignmentExpression(context);
1970     failIfFalse(firstArg);
1971
1972     TreeArgumentsList argList = context.createArgumentsList(firstArg);
1973     TreeArgumentsList tail = argList;
1974     while (match(COMMA)) {
1975         next(TreeBuilder::DontBuildStrings);
1976         TreeExpression arg = parseAssignmentExpression(context);
1977         failIfFalse(arg);
1978         tail = context.createArgumentsList(tail, arg);
1979     }
1980     consumeOrFail(CLOSEPAREN);
1981     return context.createArguments(argList);
1982 }
1983
1984 template <class TreeBuilder> TreeExpression JSParser::parseMemberExpression(TreeBuilder& context)
1985 {
1986     TreeExpression base = 0;
1987     int start = tokenStart();
1988     int expressionStart = start;
1989     int newCount = 0;
1990     while (match(NEW)) {
1991         next();
1992         newCount++;
1993     }
1994
1995     if (match(FUNCTION)) {
1996         const Identifier* name = &m_globalData->propertyNames->nullIdentifier;
1997         TreeFormalParameterList parameters = 0;
1998         TreeFunctionBody body = 0;
1999         int openBracePos = 0;
2000         int closeBracePos = 0;
2001         int bodyStartLine = 0;
2002         next();
2003         failIfFalse((parseFunctionInfo<FunctionNoRequirements, false>(context, name, parameters, body, openBracePos, closeBracePos, bodyStartLine)));
2004         base = context.createFunctionExpr(name, body, parameters, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
2005     } else
2006         base = parsePrimaryExpression(context);
2007
2008     failIfFalse(base);
2009     while (true) {
2010         switch (m_token.m_type) {
2011         case OPENBRACKET: {
2012             m_nonTrivialExpressionCount++;
2013             int expressionEnd = lastTokenEnd();
2014             next();
2015             int nonLHSCount = m_nonLHSCount;
2016             int initialAssignments = m_assignmentCount;
2017             TreeExpression property = parseExpression(context);
2018             failIfFalse(property);
2019             base = context.createBracketAccess(base, property, initialAssignments != m_assignmentCount, expressionStart, expressionEnd, tokenEnd());
2020             if (!consume(CLOSEBRACKET))
2021                 fail();
2022             m_nonLHSCount = nonLHSCount;
2023             break;
2024         }
2025         case OPENPAREN: {
2026             m_nonTrivialExpressionCount++;
2027             if (newCount) {
2028                 newCount--;
2029                 if (match(OPENPAREN)) {
2030                     int exprEnd = lastTokenEnd();
2031                     TreeArguments arguments = parseArguments(context);
2032                     failIfFalse(arguments);
2033                     base = context.createNewExpr(base, arguments, start, exprEnd, lastTokenEnd());
2034                 } else
2035                     base = context.createNewExpr(base, start, lastTokenEnd());
2036             } else {
2037                 int nonLHSCount = m_nonLHSCount;
2038                 int expressionEnd = lastTokenEnd();
2039                 TreeArguments arguments = parseArguments(context);
2040                 failIfFalse(arguments);
2041                 base = context.makeFunctionCallNode(base, arguments, expressionStart, expressionEnd, lastTokenEnd());
2042                 m_nonLHSCount = nonLHSCount;
2043             }
2044             break;
2045         }
2046         case DOT: {
2047             m_nonTrivialExpressionCount++;
2048             int expressionEnd = lastTokenEnd();
2049             nextExpectIdentifier(Lexer::IgnoreReservedWords | TreeBuilder::DontBuildKeywords);
2050             matchOrFail(IDENT);
2051             base = context.createDotAccess(base, m_token.m_data.ident, expressionStart, expressionEnd, tokenEnd());
2052             next();
2053             break;
2054         }
2055         default:
2056             goto endMemberExpression;
2057         }
2058     }
2059 endMemberExpression:
2060     while (newCount--)
2061         base = context.createNewExpr(base, start, lastTokenEnd());
2062     return base;
2063 }
2064
2065 template <class TreeBuilder> TreeExpression JSParser::parseUnaryExpression(TreeBuilder& context)
2066 {
2067     typename TreeBuilder::UnaryExprContext unaryExprContext(context);
2068     AllowInOverride allowInOverride(this);
2069     int tokenStackDepth = 0;
2070     bool modifiesExpr = false;
2071     bool requiresLExpr = false;
2072     while (isUnaryOp(m_token.m_type)) {
2073         if (strictMode()) {
2074             switch (m_token.m_type) {
2075             case PLUSPLUS:
2076             case MINUSMINUS:
2077             case AUTOPLUSPLUS:
2078             case AUTOMINUSMINUS:
2079                 failIfTrue(requiresLExpr);
2080                 modifiesExpr = true;
2081                 requiresLExpr = true;
2082                 break;
2083             case DELETETOKEN:
2084                 failIfTrue(requiresLExpr);
2085                 requiresLExpr = true;
2086                 break;
2087             default:
2088                 failIfTrue(requiresLExpr);
2089                 break;
2090             }
2091         }
2092         m_nonLHSCount++;
2093         context.appendUnaryToken(tokenStackDepth, m_token.m_type, tokenStart());
2094         next();
2095         m_nonTrivialExpressionCount++;
2096     }
2097     int subExprStart = tokenStart();
2098     TreeExpression expr = parseMemberExpression(context);
2099     failIfFalse(expr);
2100     bool isEvalOrArguments = false;
2101     if (strictMode() && !m_syntaxAlreadyValidated) {
2102         if (context.isResolve(expr)) {
2103             isEvalOrArguments = *m_lastIdentifier == m_globalData->propertyNames->eval || *m_lastIdentifier == m_globalData->propertyNames->arguments;
2104         }
2105     }
2106     failIfTrueIfStrict(isEvalOrArguments && modifiesExpr);
2107     switch (m_token.m_type) {
2108     case PLUSPLUS:
2109         m_nonTrivialExpressionCount++;
2110         m_nonLHSCount++;
2111         expr = context.makePostfixNode(expr, OpPlusPlus, subExprStart, lastTokenEnd(), tokenEnd());
2112         m_assignmentCount++;
2113         failIfTrueIfStrict(isEvalOrArguments);
2114         failIfTrueIfStrict(requiresLExpr);
2115         next();
2116         break;
2117     case MINUSMINUS:
2118         m_nonTrivialExpressionCount++;
2119         m_nonLHSCount++;
2120         expr = context.makePostfixNode(expr, OpMinusMinus, subExprStart, lastTokenEnd(), tokenEnd());
2121         m_assignmentCount++;
2122         failIfTrueIfStrict(isEvalOrArguments);
2123         failIfTrueIfStrict(requiresLExpr);
2124         next();
2125         break;
2126     default:
2127         break;
2128     }
2129
2130     int end = lastTokenEnd();
2131
2132     if (!TreeBuilder::CreatesAST && (m_syntaxAlreadyValidated || !strictMode()))
2133         return expr;
2134
2135     while (tokenStackDepth) {
2136         switch (context.unaryTokenStackLastType(tokenStackDepth)) {
2137         case EXCLAMATION:
2138             expr = context.createLogicalNot(expr);
2139             break;
2140         case TILDE:
2141             expr = context.makeBitwiseNotNode(expr);
2142             break;
2143         case MINUS:
2144             expr = context.makeNegateNode(expr);
2145             break;
2146         case PLUS:
2147             expr = context.createUnaryPlus(expr);
2148             break;
2149         case PLUSPLUS:
2150         case AUTOPLUSPLUS:
2151             expr = context.makePrefixNode(expr, OpPlusPlus, context.unaryTokenStackLastStart(tokenStackDepth), subExprStart + 1, end);
2152             m_assignmentCount++;
2153             break;
2154         case MINUSMINUS:
2155         case AUTOMINUSMINUS:
2156             expr = context.makePrefixNode(expr, OpMinusMinus, context.unaryTokenStackLastStart(tokenStackDepth), subExprStart + 1, end);
2157             m_assignmentCount++;
2158             break;
2159         case TYPEOF:
2160             expr = context.makeTypeOfNode(expr);
2161             break;
2162         case VOIDTOKEN:
2163             expr = context.createVoid(expr);
2164             break;
2165         case DELETETOKEN:
2166             failIfTrueIfStrict(context.isResolve(expr));
2167             expr = context.makeDeleteNode(expr, context.unaryTokenStackLastStart(tokenStackDepth), end, end);
2168             break;
2169         default:
2170             // If we get here something has gone horribly horribly wrong
2171             CRASH();
2172         }
2173         subExprStart = context.unaryTokenStackLastStart(tokenStackDepth);
2174         context.unaryTokenStackRemoveLast(tokenStackDepth);
2175     }
2176     return expr;
2177 }
2178
2179 }
2180
2181 namespace WTF
2182 {
2183     template <> struct VectorTraits<JSC::JSParser::Scope> : SimpleClassVectorTraits {
2184         static const bool canInitializeWithMemset = false; // Not all Scope data members initialize to 0.
2185     };
2186 }