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