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