parser/Parser.h

   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, 2011, 2013 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 #ifndef Parser_h
  24 #define Parser_h
  25
  26 #include "Debugger.h"
  27 #include "ExceptionHelpers.h"
  28 #include "Executable.h"
  29 #include "JSGlobalObject.h"
  30 #include "Lexer.h"
  31 #include "Nodes.h"
  32 #include "ParserArena.h"
  33 #include "ParserError.h"
  34 #include "ParserTokens.h"
  35 #include "SourceProvider.h"
  36 #include "SourceProviderCache.h"
  37 #include "SourceProviderCacheItem.h"
  38 #include <wtf/Forward.h>
  39 #include <wtf/Noncopyable.h>
  40 #include <wtf/OwnPtr.h>
  41 #include <wtf/RefPtr.h>
  42 namespace JSC {
  43 struct Scope;
  44 }
  45
  46 namespace WTF {
  47 template <> struct VectorTraits<JSC::Scope> : SimpleClassVectorTraits {
  48     static const bool canInitializeWithMemset = false; // Not all Scope data members initialize to 0.
  49 };
  50 }
  51
  52 namespace JSC {
  53
  54 class ExecState;
  55 class FunctionBodyNode;
  56 class FunctionParameters;
  57 class Identifier;
  58 class VM;
  59 class ProgramNode;
  60 class SourceCode;
  61
  62 // Macros to make the more common TreeBuilder types a little less verbose
  63 #define TreeStatement typename TreeBuilder::Statement
  64 #define TreeExpression typename TreeBuilder::Expression
  65 #define TreeFormalParameterList typename TreeBuilder::FormalParameterList
  66 #define TreeSourceElements typename TreeBuilder::SourceElements
  67 #define TreeClause typename TreeBuilder::Clause
  68 #define TreeClauseList typename TreeBuilder::ClauseList
  69 #define TreeConstDeclList typename TreeBuilder::ConstDeclList
  70 #define TreeArguments typename TreeBuilder::Arguments
  71 #define TreeArgumentsList typename TreeBuilder::ArgumentsList
  72 #define TreeFunctionBody typename TreeBuilder::FunctionBody
  73 #define TreeProperty typename TreeBuilder::Property
  74 #define TreePropertyList typename TreeBuilder::PropertyList
  75
  76 COMPILE_ASSERT(LastUntaggedToken < 64, LessThan64UntaggedTokens);
  77
  78 enum SourceElementsMode { CheckForStrictMode, DontCheckForStrictMode };
  79 enum FunctionRequirements { FunctionNoRequirements, FunctionNeedsName };
  80
  81 template <typename T> inline bool isEvalNode() { return false; }
  82 template <> inline bool isEvalNode<EvalNode>() { return true; }
  83
  84 struct DepthManager {
  85     DepthManager(int* depth)
  86         : m_originalDepth(*depth)
  87         , m_depth(depth)
  88     {
  89     }
  90
  91     ~DepthManager()
  92     {
  93         *m_depth = m_originalDepth;
  94     }
  95
  96 private:
  97     int m_originalDepth;
  98     int* m_depth;
  99 };
 100
 101 struct ScopeLabelInfo {
 102     ScopeLabelInfo(StringImpl* ident, bool isLoop)
 103         : m_ident(ident)
 104         , m_isLoop(isLoop)
 105     {
 106     }
 107
 108     StringImpl* m_ident;
 109     bool m_isLoop;
 110 };
 111
 112 struct Scope {
 113     Scope(const VM* vm, bool isFunction, bool strictMode)
 114         : m_vm(vm)
 115         , m_shadowsArguments(false)
 116         , m_usesEval(false)
 117         , m_needsFullActivation(false)
 118         , m_allowsNewDecls(true)
 119         , m_strictMode(strictMode)
 120         , m_isFunction(isFunction)
 121         , m_isFunctionBoundary(false)
 122         , m_isValidStrictMode(true)
 123         , m_loopDepth(0)
 124         , m_switchDepth(0)
 125     {
 126     }
 127
 128     Scope(const Scope& rhs)
 129         : m_vm(rhs.m_vm)
 130         , m_shadowsArguments(rhs.m_shadowsArguments)
 131         , m_usesEval(rhs.m_usesEval)
 132         , m_needsFullActivation(rhs.m_needsFullActivation)
 133         , m_allowsNewDecls(rhs.m_allowsNewDecls)
 134         , m_strictMode(rhs.m_strictMode)
 135         , m_isFunction(rhs.m_isFunction)
 136         , m_isFunctionBoundary(rhs.m_isFunctionBoundary)
 137         , m_isValidStrictMode(rhs.m_isValidStrictMode)
 138         , m_loopDepth(rhs.m_loopDepth)
 139         , m_switchDepth(rhs.m_switchDepth)
 140     {
 141         if (rhs.m_labels) {
 142             m_labels = adoptPtr(new LabelStack);
 143
 144             typedef LabelStack::const_iterator iterator;
 145             iterator end = rhs.m_labels->end();
 146             for (iterator it = rhs.m_labels->begin(); it != end; ++it)
 147                 m_labels->append(ScopeLabelInfo(it->m_ident, it->m_isLoop));
 148         }
 149     }
 150
 151     void startSwitch() { m_switchDepth++; }
 152     void endSwitch() { m_switchDepth--; }
 153     void startLoop() { m_loopDepth++; }
 154     void endLoop() { ASSERT(m_loopDepth); m_loopDepth--; }
 155     bool inLoop() { return !!m_loopDepth; }
 156     bool breakIsValid() { return m_loopDepth || m_switchDepth; }
 157     bool continueIsValid() { return m_loopDepth; }
 158
 159     void pushLabel(const Identifier* label, bool isLoop)
 160     {
 161         if (!m_labels)
 162             m_labels = adoptPtr(new LabelStack);
 163         m_labels->append(ScopeLabelInfo(label->impl(), isLoop));
 164     }
 165
 166     void popLabel()
 167     {
 168         ASSERT(m_labels);
 169         ASSERT(m_labels->size());
 170         m_labels->removeLast();
 171     }
 172
 173     ScopeLabelInfo* getLabel(const Identifier* label)
 174     {
 175         if (!m_labels)
 176             return 0;
 177         for (int i = m_labels->size(); i > 0; i--) {
 178             if (m_labels->at(i - 1).m_ident == label->impl())
 179                 return &m_labels->at(i - 1);
 180         }
 181         return 0;
 182     }
 183
 184     void setIsFunction()
 185     {
 186         m_isFunction = true;
 187         m_isFunctionBoundary = true;
 188     }
 189     bool isFunction() { return m_isFunction; }
 190     bool isFunctionBoundary() { return m_isFunctionBoundary; }
 191
 192     void declareCallee(const Identifier* ident)
 193     {
 194         m_declaredVariables.add(ident->string().impl());
 195     }
 196
 197     bool declareVariable(const Identifier* ident)
 198     {
 199         bool isValidStrictMode = m_vm->propertyNames->eval != *ident && m_vm->propertyNames->arguments != *ident;
 200         m_isValidStrictMode = m_isValidStrictMode && isValidStrictMode;
 201         m_declaredVariables.add(ident->string().impl());
 202         return isValidStrictMode;
 203     }
 204
 205     void declareWrite(const Identifier* ident)
 206     {
 207         ASSERT(m_strictMode);
 208         m_writtenVariables.add(ident->impl());
 209     }
 210
 211     void preventNewDecls() { m_allowsNewDecls = false; }
 212     bool allowsNewDecls() const { return m_allowsNewDecls; }
 213
 214     bool declareParameter(const Identifier* ident)
 215     {
 216         bool isArguments = m_vm->propertyNames->arguments == *ident;
 217         bool isValidStrictMode = m_declaredVariables.add(ident->string().impl()).isNewEntry && m_vm->propertyNames->eval != *ident && !isArguments;
 218         m_isValidStrictMode = m_isValidStrictMode && isValidStrictMode;
 219         if (isArguments)
 220             m_shadowsArguments = true;
 221         return isValidStrictMode;
 222     }
 223
 224     void useVariable(const Identifier* ident, bool isEval)
 225     {
 226         m_usesEval |= isEval;
 227         m_usedVariables.add(ident->string().impl());
 228     }
 229
 230     void setNeedsFullActivation() { m_needsFullActivation = true; }
 231
 232     bool collectFreeVariables(Scope* nestedScope, bool shouldTrackClosedVariables)
 233     {
 234         if (nestedScope->m_usesEval)
 235             m_usesEval = true;
 236         IdentifierSet::iterator end = nestedScope->m_usedVariables.end();
 237         for (IdentifierSet::iterator ptr = nestedScope->m_usedVariables.begin(); ptr != end; ++ptr) {
 238             if (nestedScope->m_declaredVariables.contains(*ptr))
 239                 continue;
 240             m_usedVariables.add(*ptr);
 241             if (shouldTrackClosedVariables)
 242                 m_closedVariables.add(*ptr);
 243         }
 244         if (nestedScope->m_writtenVariables.size()) {
 245             IdentifierSet::iterator end = nestedScope->m_writtenVariables.end();
 246             for (IdentifierSet::iterator ptr = nestedScope->m_writtenVariables.begin(); ptr != end; ++ptr) {
 247                 if (nestedScope->m_declaredVariables.contains(*ptr))
 248                     continue;
 249                 m_writtenVariables.add(*ptr);
 250             }
 251         }
 252
 253         return true;
 254     }
 255
 256     void getUncapturedWrittenVariables(IdentifierSet& writtenVariables)
 257     {
 258         IdentifierSet::iterator end = m_writtenVariables.end();
 259         for (IdentifierSet::iterator ptr = m_writtenVariables.begin(); ptr != end; ++ptr) {
 260             if (!m_declaredVariables.contains(*ptr))
 261                 writtenVariables.add(*ptr);
 262         }
 263     }
 264
 265     void getCapturedVariables(IdentifierSet& capturedVariables)
 266     {
 267         if (m_needsFullActivation || m_usesEval) {
 268             capturedVariables.swap(m_declaredVariables);
 269             return;
 270         }
 271         for (IdentifierSet::iterator ptr = m_closedVariables.begin(); ptr != m_closedVariables.end(); ++ptr) {
 272             if (!m_declaredVariables.contains(*ptr))
 273                 continue;
 274             capturedVariables.add(*ptr);
 275         }
 276     }
 277     void setStrictMode() { m_strictMode = true; }
 278     bool strictMode() const { return m_strictMode; }
 279     bool isValidStrictMode() const { return m_isValidStrictMode; }
 280     bool shadowsArguments() const { return m_shadowsArguments; }
 281
 282     void copyCapturedVariablesToVector(const IdentifierSet& capturedVariables, Vector<RefPtr<StringImpl> >& vector)
 283     {
 284         IdentifierSet::iterator end = capturedVariables.end();
 285         for (IdentifierSet::iterator it = capturedVariables.begin(); it != end; ++it) {
 286             if (m_declaredVariables.contains(*it))
 287                 continue;
 288             vector.append(*it);
 289         }
 290     }
 291
 292     void fillParametersForSourceProviderCache(SourceProviderCacheItemCreationParameters& parameters)
 293     {
 294         ASSERT(m_isFunction);
 295         parameters.usesEval = m_usesEval;
 296         parameters.strictMode = m_strictMode;
 297         parameters.needsFullActivation = m_needsFullActivation;
 298         copyCapturedVariablesToVector(m_writtenVariables, parameters.writtenVariables);
 299         copyCapturedVariablesToVector(m_usedVariables, parameters.usedVariables);
 300     }
 301
 302     void restoreFromSourceProviderCache(const SourceProviderCacheItem* info)
 303     {
 304         ASSERT(m_isFunction);
 305         m_usesEval = info->usesEval;
 306         m_strictMode = info->strictMode;
 307         m_needsFullActivation = info->needsFullActivation;
 308         for (unsigned i = 0; i < info->usedVariablesCount; ++i)
 309             m_usedVariables.add(info->usedVariables()[i]);
 310         for (unsigned i = 0; i < info->writtenVariablesCount; ++i)
 311             m_writtenVariables.add(info->writtenVariables()[i]);
 312     }
 313
 314 private:
 315     const VM* m_vm;
 316     bool m_shadowsArguments : 1;
 317     bool m_usesEval : 1;
 318     bool m_needsFullActivation : 1;
 319     bool m_allowsNewDecls : 1;
 320     bool m_strictMode : 1;
 321     bool m_isFunction : 1;
 322     bool m_isFunctionBoundary : 1;
 323     bool m_isValidStrictMode : 1;
 324     int m_loopDepth;
 325     int m_switchDepth;
 326
 327     typedef Vector<ScopeLabelInfo, 2> LabelStack;
 328     OwnPtr<LabelStack> m_labels;
 329     IdentifierSet m_declaredVariables;
 330     IdentifierSet m_usedVariables;
 331     IdentifierSet m_closedVariables;
 332     IdentifierSet m_writtenVariables;
 333 };
 334
 335 typedef Vector<Scope, 10> ScopeStack;
 336
 337 struct ScopeRef {
 338     ScopeRef(ScopeStack* scopeStack, unsigned index)
 339         : m_scopeStack(scopeStack)
 340         , m_index(index)
 341     {
 342     }
 343     Scope* operator->() { return &m_scopeStack->at(m_index); }
 344     unsigned index() const { return m_index; }
 345
 346     bool hasContainingScope()
 347     {
 348         return m_index && !m_scopeStack->at(m_index).isFunctionBoundary();
 349     }
 350
 351     ScopeRef containingScope()
 352     {
 353         ASSERT(hasContainingScope());
 354         return ScopeRef(m_scopeStack, m_index - 1);
 355     }
 356
 357 private:
 358     ScopeStack* m_scopeStack;
 359     unsigned m_index;
 360 };
 361
 362 template <typename LexerType>
 363 class Parser {
 364     WTF_MAKE_NONCOPYABLE(Parser);
 365     WTF_MAKE_FAST_ALLOCATED;
 366
 367 public:
 368     Parser(VM*, const SourceCode&, FunctionParameters*, const Identifier&, JSParserStrictness, JSParserMode);
 369     ~Parser();
 370
 371     template <class ParsedNode>
 372     PassRefPtr<ParsedNode> parse(ParserError&);
 373
 374 private:
 375     struct AllowInOverride {
 376         AllowInOverride(Parser* parser)
 377             : m_parser(parser)
 378             , m_oldAllowsIn(parser->m_allowsIn)
 379         {
 380             parser->m_allowsIn = true;
 381         }
 382         ~AllowInOverride()
 383         {
 384             m_parser->m_allowsIn = m_oldAllowsIn;
 385         }
 386         Parser* m_parser;
 387         bool m_oldAllowsIn;
 388     };
 389
 390     struct AutoPopScopeRef : public ScopeRef {
 391         AutoPopScopeRef(Parser* parser, ScopeRef scope)
 392         : ScopeRef(scope)
 393         , m_parser(parser)
 394         {
 395         }
 396
 397         ~AutoPopScopeRef()
 398         {
 399             if (m_parser)
 400                 m_parser->popScope(*this, false);
 401         }
 402
 403         void setPopped()
 404         {
 405             m_parser = 0;
 406         }
 407
 408     private:
 409         Parser* m_parser;
 410     };
 411
 412     ScopeRef currentScope()
 413     {
 414         return ScopeRef(&m_scopeStack, m_scopeStack.size() - 1);
 415     }
 416
 417     ScopeRef pushScope()
 418     {
 419         bool isFunction = false;
 420         bool isStrict = false;
 421         if (!m_scopeStack.isEmpty()) {
 422             isStrict = m_scopeStack.last().strictMode();
 423             isFunction = m_scopeStack.last().isFunction();
 424         }
 425         m_scopeStack.append(Scope(m_vm, isFunction, isStrict));
 426         return currentScope();
 427     }
 428
 429     bool popScopeInternal(ScopeRef& scope, bool shouldTrackClosedVariables)
 430     {
 431         ASSERT_UNUSED(scope, scope.index() == m_scopeStack.size() - 1);
 432         ASSERT(m_scopeStack.size() > 1);
 433         bool result = m_scopeStack[m_scopeStack.size() - 2].collectFreeVariables(&m_scopeStack.last(), shouldTrackClosedVariables);
 434         m_scopeStack.removeLast();
 435         return result;
 436     }
 437
 438     bool popScope(ScopeRef& scope, bool shouldTrackClosedVariables)
 439     {
 440         return popScopeInternal(scope, shouldTrackClosedVariables);
 441     }
 442
 443     bool popScope(AutoPopScopeRef& scope, bool shouldTrackClosedVariables)
 444     {
 445         scope.setPopped();
 446         return popScopeInternal(scope, shouldTrackClosedVariables);
 447     }
 448
 449     bool declareVariable(const Identifier* ident)
 450     {
 451         unsigned i = m_scopeStack.size() - 1;
 452         ASSERT(i < m_scopeStack.size());
 453         while (!m_scopeStack[i].allowsNewDecls()) {
 454             i--;
 455             ASSERT(i < m_scopeStack.size());
 456         }
 457         return m_scopeStack[i].declareVariable(ident);
 458     }
 459
 460     void declareWrite(const Identifier* ident)
 461     {
 462         if (!m_syntaxAlreadyValidated)
 463             m_scopeStack.last().declareWrite(ident);
 464     }
 465
 466     ScopeStack m_scopeStack;
 467
 468     const SourceProviderCacheItem* findCachedFunctionInfo(int openBracePos)
 469     {
 470         return m_functionCache ? m_functionCache->get(openBracePos) : 0;
 471     }
 472
 473     Parser();
 474     String parseInner();
 475
 476     void didFinishParsing(SourceElements*, ParserArenaData<DeclarationStacks::VarStack>*,
 477                           ParserArenaData<DeclarationStacks::FunctionStack>*, CodeFeatures,
 478                           int, int, IdentifierSet&);
 479
 480     // Used to determine type of error to report.
 481     bool isFunctionBodyNode(ScopeNode*) { return false; }
 482     bool isFunctionBodyNode(FunctionBodyNode*) { return true; }
 483
 484     ALWAYS_INLINE void next(unsigned lexerFlags = 0)
 485     {
 486         m_lastLine = m_token.m_location.line;
 487         m_lastTokenEnd = m_token.m_location.endOffset;
 488         m_lastTokenLineStart = m_token.m_location.lineStartOffset;
 489         m_lexer->setLastLineNumber(m_lastLine);
 490         m_token.m_type = m_lexer->lex(&m_token.m_data, &m_token.m_location, lexerFlags, strictMode());
 491     }
 492
 493     ALWAYS_INLINE void nextExpectIdentifier(unsigned lexerFlags = 0)
 494     {
 495         m_lastLine = m_token.m_location.line;
 496         m_lastTokenEnd = m_token.m_location.endOffset;
 497         m_lastTokenLineStart = m_token.m_location.lineStartOffset;
 498         m_lexer->setLastLineNumber(m_lastLine);
 499         m_token.m_type = m_lexer->lexExpectIdentifier(&m_token.m_data, &m_token.m_location, lexerFlags, strictMode());
 500     }
 501
 502     ALWAYS_INLINE bool nextTokenIsColon()
 503     {
 504         return m_lexer->nextTokenIsColon();
 505     }
 506
 507     ALWAYS_INLINE bool consume(JSTokenType expected, unsigned flags = 0)
 508     {
 509         bool result = m_token.m_type == expected;
 510         if (result)
 511             next(flags);
 512         return result;
 513     }
 514
 515     ALWAYS_INLINE String getToken() {
 516         SourceProvider* sourceProvider = m_source->provider();
 517         return sourceProvider->getRange(tokenStart(), tokenEnd());
 518     }
 519
 520     ALWAYS_INLINE bool match(JSTokenType expected)
 521     {
 522         return m_token.m_type == expected;
 523     }
 524
 525     ALWAYS_INLINE unsigned tokenStart()
 526     {
 527         return m_token.m_location.startOffset;
 528     }
 529
 530     ALWAYS_INLINE int tokenLine()
 531     {
 532         return m_token.m_location.line;
 533     }
 534
 535     ALWAYS_INLINE int tokenColumn()
 536     {
 537         return tokenStart() - tokenLineStart();
 538     }
 539
 540     ALWAYS_INLINE unsigned tokenEnd()
 541     {
 542         return m_token.m_location.endOffset;
 543     }
 544
 545     ALWAYS_INLINE unsigned tokenLineStart()
 546     {
 547         return m_token.m_location.lineStartOffset;
 548     }
 549
 550     ALWAYS_INLINE const JSTokenLocation& tokenLocation()
 551     {
 552         return m_token.m_location;
 553     }
 554
 555     const char* getTokenName(JSTokenType tok)
 556     {
 557         switch (tok) {
 558         case NULLTOKEN:
 559             return "null";
 560         case TRUETOKEN:
 561             return "true";
 562         case FALSETOKEN:
 563             return "false";
 564         case BREAK:
 565             return "break";
 566         case CASE:
 567             return "case";
 568         case DEFAULT:
 569             return "default";
 570         case FOR:
 571             return "for";
 572         case NEW:
 573             return "new";
 574         case VAR:
 575             return "var";
 576         case CONSTTOKEN:
 577             return "const";
 578         case CONTINUE:
 579             return "continue";
 580         case FUNCTION:
 581             return "function";
 582         case IF:
 583             return "if";
 584         case THISTOKEN:
 585             return "this";
 586         case DO:
 587             return "do";
 588         case WHILE:
 589             return "while";
 590         case SWITCH:
 591             return "switch";
 592         case WITH:
 593             return "with";
 594         case THROW:
 595             return "throw";
 596         case TRY:
 597             return "try";
 598         case CATCH:
 599             return "catch";
 600         case FINALLY:
 601             return "finally";
 602         case DEBUGGER:
 603             return "debugger";
 604         case ELSE:
 605             return "else";
 606         case OPENBRACE:
 607             return "{";
 608         case CLOSEBRACE:
 609             return "}";
 610         case OPENPAREN:
 611             return "(";
 612         case CLOSEPAREN:
 613             return ")";
 614         case OPENBRACKET:
 615             return "[";
 616         case CLOSEBRACKET:
 617             return "]";
 618         case COMMA:
 619             return ",";
 620         case QUESTION:
 621             return "?";
 622         case SEMICOLON:
 623             return ";";
 624         case COLON:
 625             return ":";
 626         case DOT:
 627             return ".";
 628         case EQUAL:
 629             return "=";
 630         case PLUSEQUAL:
 631             return "+=";
 632         case MINUSEQUAL:
 633             return "-=";
 634         case MULTEQUAL:
 635             return "*=";
 636         case DIVEQUAL:
 637             return "/=";
 638         case LSHIFTEQUAL:
 639             return "<<=";
 640         case RSHIFTEQUAL:
 641             return ">>=";
 642         case URSHIFTEQUAL:
 643             return ">>>=";
 644         case ANDEQUAL:
 645             return "&=";
 646         case MODEQUAL:
 647             return "%=";
 648         case XOREQUAL:
 649             return "^=";
 650         case OREQUAL:
 651             return "|=";
 652         case AUTOPLUSPLUS:
 653         case PLUSPLUS:
 654             return "++";
 655         case AUTOMINUSMINUS:
 656         case MINUSMINUS:
 657             return "--";
 658         case EXCLAMATION:
 659             return "!";
 660         case TILDE:
 661             return "~";
 662         case TYPEOF:
 663             return "typeof";
 664         case VOIDTOKEN:
 665             return "void";
 666         case DELETETOKEN:
 667             return "delete";
 668         case OR:
 669             return "||";
 670         case AND:
 671             return "&&";
 672         case BITOR:
 673             return "|";
 674         case BITXOR:
 675             return "^";
 676         case BITAND:
 677             return "&";
 678         case EQEQ:
 679             return "==";
 680         case NE:
 681             return "!=";
 682         case STREQ:
 683             return "===";
 684         case STRNEQ:
 685             return "!==";
 686         case LT:
 687             return "<";
 688         case GT:
 689             return ">";
 690         case LE:
 691             return "<=";
 692         case GE:
 693             return ">=";
 694         case INSTANCEOF:
 695             return "instanceof";
 696         case INTOKEN:
 697             return "in";
 698         case LSHIFT:
 699             return "<<";
 700         case RSHIFT:
 701             return ">>";
 702         case URSHIFT:
 703             return ">>>";
 704         case PLUS:
 705             return "+";
 706         case MINUS:
 707             return "-";
 708         case TIMES:
 709             return "*";
 710         case DIVIDE:
 711             return "/";
 712         case MOD:
 713             return "%";
 714         case RETURN:
 715         case RESERVED_IF_STRICT:
 716         case RESERVED:
 717         case NUMBER:
 718         case IDENT:
 719         case STRING:
 720         case UNTERMINATED_IDENTIFIER_ESCAPE_ERRORTOK:
 721         case UNTERMINATED_IDENTIFIER_UNICODE_ESCAPE_ERRORTOK:
 722         case UNTERMINATED_MULTILINE_COMMENT_ERRORTOK:
 723         case UNTERMINATED_NUMERIC_LITERAL_ERRORTOK:
 724         case UNTERMINATED_STRING_LITERAL_ERRORTOK:
 725         case INVALID_IDENTIFIER_ESCAPE_ERRORTOK:
 726         case INVALID_IDENTIFIER_UNICODE_ESCAPE_ERRORTOK:
 727         case INVALID_NUMERIC_LITERAL_ERRORTOK:
 728         case INVALID_OCTAL_NUMBER_ERRORTOK:
 729         case INVALID_STRING_LITERAL_ERRORTOK:
 730         case ERRORTOK:
 731         case EOFTOK:
 732             return 0;
 733         case LastUntaggedToken:
 734             break;
 735         }
 736         RELEASE_ASSERT_NOT_REACHED();
 737         return "internal error";
 738     }
 739
 740     ALWAYS_INLINE void updateErrorMessageSpecialCase(JSTokenType expectedToken)
 741     {
 742         switch (expectedToken) {
 743         case RESERVED_IF_STRICT:
 744             m_errorMessage = "Use of reserved word '" + getToken() + "' in strict mode";
 745             return;
 746         case RESERVED:
 747             m_errorMessage = "Use of reserved word '" + getToken() + '\'';
 748             return;
 749         case NUMBER:
 750             m_errorMessage = "Unexpected number '" + getToken() + '\'';
 751             return;
 752         case IDENT:
 753             m_errorMessage = "Expected an identifier but found '" + getToken() + "' instead";
 754             return;
 755         case STRING:
 756             m_errorMessage = "Unexpected string " + getToken();
 757             return;
 758
 759         case UNTERMINATED_IDENTIFIER_ESCAPE_ERRORTOK:
 760         case UNTERMINATED_IDENTIFIER_UNICODE_ESCAPE_ERRORTOK:
 761             m_errorMessage = "Incomplete unicode escape in identifier: '" + getToken() + '\'';
 762             return;
 763         case UNTERMINATED_MULTILINE_COMMENT_ERRORTOK:
 764             m_errorMessage = "Unterminated multiline comment";
 765             return;
 766         case UNTERMINATED_NUMERIC_LITERAL_ERRORTOK:
 767             m_errorMessage = "Unterminated numeric literal '" + getToken() + '\'';
 768             return;
 769         case UNTERMINATED_STRING_LITERAL_ERRORTOK:
 770             m_errorMessage = "Unterminated string literal '" + getToken() + '\'';
 771             return;
 772         case INVALID_IDENTIFIER_ESCAPE_ERRORTOK:
 773             m_errorMessage = "Invalid escape in identifier: '" + getToken() + '\'';
 774             return;
 775         case INVALID_IDENTIFIER_UNICODE_ESCAPE_ERRORTOK:
 776             m_errorMessage = "Invalid unicode escape in identifier: '" + getToken() + '\'';
 777             return;
 778         case INVALID_NUMERIC_LITERAL_ERRORTOK:
 779             m_errorMessage = "Invalid numeric literal: '" + getToken() + '\'';
 780             return;
 781         case INVALID_OCTAL_NUMBER_ERRORTOK:
 782             m_errorMessage = "Invalid use of octal: '" + getToken() + '\'';
 783                 return;
 784         case INVALID_STRING_LITERAL_ERRORTOK:
 785             m_errorMessage = "Invalid string literal: '" + getToken() + '\'';
 786             return;
 787         case ERRORTOK:
 788             m_errorMessage = "Unrecognized token '" + getToken() + '\'';
 789             return;
 790         case EOFTOK:
 791             m_errorMessage = ASCIILiteral("Unexpected EOF");
 792             return;
 793         case RETURN:
 794             m_errorMessage = ASCIILiteral("Return statements are only valid inside functions");
 795             return;
 796         default:
 797             RELEASE_ASSERT_NOT_REACHED();
 798             m_errorMessage = ASCIILiteral("internal error");
 799             return;
 800         }
 801     }
 802
 803     NEVER_INLINE void updateErrorMessage()
 804     {
 805         const char* name = getTokenName(m_token.m_type);
 806         if (!name)
 807             updateErrorMessageSpecialCase(m_token.m_type);
 808         else
 809             m_errorMessage = String::format("Unexpected token '%s'", name);
 810         ASSERT(!m_errorMessage.isNull());
 811     }
 812
 813     NEVER_INLINE void updateErrorMessage(JSTokenType expectedToken)
 814     {
 815         const char* name = getTokenName(expectedToken);
 816         if (name)
 817             m_errorMessage = String::format("Expected token '%s'", name);
 818         else {
 819             if (!getTokenName(m_token.m_type))
 820                 updateErrorMessageSpecialCase(m_token.m_type);
 821             else
 822                 updateErrorMessageSpecialCase(expectedToken);
 823         }
 824         ASSERT(!m_errorMessage.isNull());
 825     }
 826
 827     NEVER_INLINE void updateErrorWithNameAndMessage(const char* beforeMsg, String name, const char* afterMsg)
 828     {
 829         m_errorMessage = makeString(beforeMsg, " '", name, "' ", afterMsg);
 830     }
 831
 832     NEVER_INLINE void updateErrorMessage(const char* msg)
 833     {
 834         ASSERT(msg);
 835         m_errorMessage = String(msg);
 836         ASSERT(!m_errorMessage.isNull());
 837     }
 838
 839     void startLoop() { currentScope()->startLoop(); }
 840     void endLoop() { currentScope()->endLoop(); }
 841     void startSwitch() { currentScope()->startSwitch(); }
 842     void endSwitch() { currentScope()->endSwitch(); }
 843     void setStrictMode() { currentScope()->setStrictMode(); }
 844     bool strictMode() { return currentScope()->strictMode(); }
 845     bool isValidStrictMode() { return currentScope()->isValidStrictMode(); }
 846     bool declareParameter(const Identifier* ident) { return currentScope()->declareParameter(ident); }
 847     bool breakIsValid()
 848     {
 849         ScopeRef current = currentScope();
 850         while (!current->breakIsValid()) {
 851             if (!current.hasContainingScope())
 852                 return false;
 853             current = current.containingScope();
 854         }
 855         return true;
 856     }
 857     bool continueIsValid()
 858     {
 859         ScopeRef current = currentScope();
 860         while (!current->continueIsValid()) {
 861             if (!current.hasContainingScope())
 862                 return false;
 863             current = current.containingScope();
 864         }
 865         return true;
 866     }
 867     void pushLabel(const Identifier* label, bool isLoop) { currentScope()->pushLabel(label, isLoop); }
 868     void popLabel() { currentScope()->popLabel(); }
 869     ScopeLabelInfo* getLabel(const Identifier* label)
 870     {
 871         ScopeRef current = currentScope();
 872         ScopeLabelInfo* result = 0;
 873         while (!(result = current->getLabel(label))) {
 874             if (!current.hasContainingScope())
 875                 return 0;
 876             current = current.containingScope();
 877         }
 878         return result;
 879     }
 880
 881     template <SourceElementsMode mode, class TreeBuilder> TreeSourceElements parseSourceElements(TreeBuilder&);
 882     template <class TreeBuilder> TreeStatement parseStatement(TreeBuilder&, const Identifier*& directive, unsigned* directiveLiteralLength = 0);
 883     template <class TreeBuilder> TreeStatement parseFunctionDeclaration(TreeBuilder&);
 884     template <class TreeBuilder> TreeStatement parseVarDeclaration(TreeBuilder&);
 885     template <class TreeBuilder> TreeStatement parseConstDeclaration(TreeBuilder&);
 886     template <class TreeBuilder> TreeStatement parseDoWhileStatement(TreeBuilder&);
 887     template <class TreeBuilder> TreeStatement parseWhileStatement(TreeBuilder&);
 888     template <class TreeBuilder> TreeStatement parseForStatement(TreeBuilder&);
 889     template <class TreeBuilder> TreeStatement parseBreakStatement(TreeBuilder&);
 890     template <class TreeBuilder> TreeStatement parseContinueStatement(TreeBuilder&);
 891     template <class TreeBuilder> TreeStatement parseReturnStatement(TreeBuilder&);
 892     template <class TreeBuilder> TreeStatement parseThrowStatement(TreeBuilder&);
 893     template <class TreeBuilder> TreeStatement parseWithStatement(TreeBuilder&);
 894     template <class TreeBuilder> TreeStatement parseSwitchStatement(TreeBuilder&);
 895     template <class TreeBuilder> TreeClauseList parseSwitchClauses(TreeBuilder&);
 896     template <class TreeBuilder> TreeClause parseSwitchDefaultClause(TreeBuilder&);
 897     template <class TreeBuilder> TreeStatement parseTryStatement(TreeBuilder&);
 898     template <class TreeBuilder> TreeStatement parseDebuggerStatement(TreeBuilder&);
 899     template <class TreeBuilder> TreeStatement parseExpressionStatement(TreeBuilder&);
 900     template <class TreeBuilder> TreeStatement parseExpressionOrLabelStatement(TreeBuilder&);
 901     template <class TreeBuilder> TreeStatement parseIfStatement(TreeBuilder&);
 902     template <class TreeBuilder> ALWAYS_INLINE TreeStatement parseBlockStatement(TreeBuilder&);
 903     template <class TreeBuilder> TreeExpression parseExpression(TreeBuilder&);
 904     template <class TreeBuilder> TreeExpression parseAssignmentExpression(TreeBuilder&);
 905     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseConditionalExpression(TreeBuilder&);
 906     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseBinaryExpression(TreeBuilder&);
 907     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseUnaryExpression(TreeBuilder&);
 908     template <class TreeBuilder> TreeExpression parseMemberExpression(TreeBuilder&);
 909     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parsePrimaryExpression(TreeBuilder&);
 910     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseArrayLiteral(TreeBuilder&);
 911     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseObjectLiteral(TreeBuilder&);
 912     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseStrictObjectLiteral(TreeBuilder&);
 913     template <class TreeBuilder> ALWAYS_INLINE TreeArguments parseArguments(TreeBuilder&);
 914     template <bool strict, class TreeBuilder> ALWAYS_INLINE TreeProperty parseProperty(TreeBuilder&);
 915     template <class TreeBuilder> ALWAYS_INLINE TreeFunctionBody parseFunctionBody(TreeBuilder&);
 916     template <class TreeBuilder> ALWAYS_INLINE TreeFormalParameterList parseFormalParameters(TreeBuilder&);
 917     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseVarDeclarationList(TreeBuilder&, int& declarations, const Identifier*& lastIdent, TreeExpression& lastInitializer, int& identStart, int& initStart, int& initEnd);
 918     template <class TreeBuilder> ALWAYS_INLINE TreeConstDeclList parseConstDeclarationList(TreeBuilder& context);
 919     template <FunctionRequirements, bool nameIsInContainingScope, class TreeBuilder> bool parseFunctionInfo(TreeBuilder&, const Identifier*&, TreeFormalParameterList&, TreeFunctionBody&, unsigned& openBraceOffset, unsigned& closeBraceOffset, int& bodyStartLine, unsigned& bodyStartColumn);
 920     ALWAYS_INLINE int isBinaryOperator(JSTokenType);
 921     bool allowAutomaticSemicolon();
 922
 923     bool autoSemiColon()
 924     {
 925         if (m_token.m_type == SEMICOLON) {
 926             next();
 927             return true;
 928         }
 929         return allowAutomaticSemicolon();
 930     }
 931
 932     bool canRecurse()
 933     {
 934         return m_stack.isSafeToRecurse();
 935     }
 936
 937     int lastTokenEnd() const
 938     {
 939         return m_lastTokenEnd;
 940     }
 941
 942     unsigned lastTokenLine() const
 943     {
 944         return m_lastLine;
 945     }
 946
 947     unsigned lastTokenLineStart() const
 948     {
 949         return m_lastTokenLineStart;
 950     }
 951
 952     bool hasError() const
 953     {
 954         return !m_errorMessage.isNull();
 955     }
 956
 957     VM* m_vm;
 958     const SourceCode* m_source;
 959     ParserArena* m_arena;
 960     OwnPtr<LexerType> m_lexer;
 961
 962     StackBounds m_stack;
 963     bool m_hasStackOverflow;
 964     String m_errorMessage;
 965     JSToken m_token;
 966     bool m_allowsIn;
 967     unsigned m_lastLine;
 968     int m_lastTokenEnd;
 969     unsigned m_lastTokenLine;
 970     unsigned m_lastTokenLineStart;
 971     int m_assignmentCount;
 972     int m_nonLHSCount;
 973     bool m_syntaxAlreadyValidated;
 974     int m_statementDepth;
 975     int m_nonTrivialExpressionCount;
 976     const Identifier* m_lastIdentifier;
 977     RefPtr<SourceProviderCache> m_functionCache;
 978     SourceElements* m_sourceElements;
 979     ParserArenaData<DeclarationStacks::VarStack>* m_varDeclarations;
 980     ParserArenaData<DeclarationStacks::FunctionStack>* m_funcDeclarations;
 981     IdentifierSet m_capturedVariables;
 982     CodeFeatures m_features;
 983     int m_numConstants;
 984
 985     struct DepthManager {
 986         DepthManager(int* depth)
 987         : m_originalDepth(*depth)
 988         , m_depth(depth)
 989         {
 990         }
 991
 992         ~DepthManager()
 993         {
 994             *m_depth = m_originalDepth;
 995         }
 996
 997     private:
 998         int m_originalDepth;
 999         int* m_depth;
1000     };
1001 };
1002
1003
1004 template <typename LexerType>
1005 template <class ParsedNode>
1006 PassRefPtr<ParsedNode> Parser<LexerType>::parse(ParserError& error)
1007 {
1008     int errLine;
1009     String errMsg;
1010
1011     if (ParsedNode::scopeIsFunction)
1012         m_lexer->setIsReparsing();
1013
1014     m_sourceElements = 0;
1015
1016     errLine = -1;
1017     errMsg = String();
1018
1019     JSTokenLocation startLocation(tokenLocation());
1020     unsigned startColumn = m_source->startColumn();
1021
1022     String parseError = parseInner();
1023
1024     int lineNumber = m_lexer->lineNumber();
1025     bool lexError = m_lexer->sawError();
1026     String lexErrorMessage = lexError ? m_lexer->getErrorMessage() : String();
1027     ASSERT(lexErrorMessage.isNull() != lexError);
1028     m_lexer->clear();
1029
1030     if (!parseError.isNull() || lexError) {
1031         errLine = lineNumber;
1032         errMsg = !lexErrorMessage.isNull() ? lexErrorMessage : parseError;
1033         m_sourceElements = 0;
1034     }
1035
1036     RefPtr<ParsedNode> result;
1037     if (m_sourceElements) {
1038         JSTokenLocation endLocation;
1039         endLocation.line = m_lexer->lastLineNumber();
1040         endLocation.lineStartOffset = m_lexer->currentLineStartOffset();
1041         endLocation.startOffset = m_lexer->currentOffset();
1042         result = ParsedNode::create(m_vm,
1043                                     startLocation,
1044                                     endLocation,
1045                                     startColumn,
1046                                     m_sourceElements,
1047                                     m_varDeclarations ? &m_varDeclarations->data : 0,
1048                                     m_funcDeclarations ? &m_funcDeclarations->data : 0,
1049                                     m_capturedVariables,
1050                                     *m_source,
1051                                     m_features,
1052                                     m_numConstants);
1053         result->setLoc(m_source->firstLine(), m_lastLine, m_lexer->currentOffset(), m_lexer->currentLineStartOffset());
1054     } else {
1055         // We can never see a syntax error when reparsing a function, since we should have
1056         // reported the error when parsing the containing program or eval code. So if we're
1057         // parsing a function body node, we assume that what actually happened here is that
1058         // we ran out of stack while parsing. If we see an error while parsing eval or program
1059         // code we assume that it was a syntax error since running out of stack is much less
1060         // likely, and we are currently unable to distinguish between the two cases.
1061         if (isFunctionBodyNode(static_cast<ParsedNode*>(0)) || m_hasStackOverflow)
1062             error = ParserError(ParserError::StackOverflow, ParserError::SyntaxErrorNone, m_token);
1063         else {
1064             ParserError::SyntaxErrorType errorType = ParserError::SyntaxErrorIrrecoverable;
1065             if (m_token.m_type == EOFTOK)
1066                 errorType = ParserError::SyntaxErrorRecoverable;
1067             else if (m_token.m_type & UnterminatedErrorTokenFlag)
1068                 errorType = ParserError::SyntaxErrorUnterminatedLiteral;
1069
1070             if (isEvalNode<ParsedNode>())
1071                 error = ParserError(ParserError::EvalError, errorType, m_token, errMsg, errLine);
1072             else
1073                 error = ParserError(ParserError::SyntaxError, errorType, m_token, errMsg, errLine);
1074         }
1075     }
1076
1077     m_arena->reset();
1078
1079     return result.release();
1080 }
1081
1082 template <class ParsedNode>
1083 PassRefPtr<ParsedNode> parse(VM* vm, const SourceCode& source, FunctionParameters* parameters, const Identifier& name, JSParserStrictness strictness, JSParserMode parserMode, ParserError& error)
1084 {
1085     SamplingRegion samplingRegion("Parsing");
1086
1087     ASSERT(!source.provider()->source().isNull());
1088     if (source.provider()->source().is8Bit()) {
1089         Parser< Lexer<LChar> > parser(vm, source, parameters, name, strictness, parserMode);
1090         return parser.parse<ParsedNode>(error);
1091     }
1092     Parser< Lexer<UChar> > parser(vm, source, parameters, name, strictness, parserMode);
1093     return parser.parse<ParsedNode>(error);
1094 }
1095
1096 } // namespace
1097 #endif