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