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