2011-04-12 Geoffrey Garen <ggaren@apple.com>
[WebKit-https.git] / Source / JavaScriptCore / parser / JSParser.cpp
1 /*
2  * Copyright (C) 2010 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27
28 #include "JSParser.h"
29
30 using namespace JSC;
31
32 #include "CodeBlock.h"
33 #include "JSGlobalData.h"
34 #include "NodeInfo.h"
35 #include "ASTBuilder.h"
36 #include "SourceProvider.h"
37 #include "SourceProviderCacheItem.h"
38 #include <wtf/HashFunctions.h>
39 #include <wtf/OwnPtr.h>
40 #include <wtf/WTFThreadData.h>
41 #include <utility>
42
43 using namespace std;
44
45 namespace JSC {
46 #define fail() do { m_error = true; return 0; } while (0)
47 #define failIfFalse(cond) do { if (!(cond)) fail(); } while (0)
48 #define failIfTrue(cond) do { if ((cond)) fail(); } while (0)
49 #define failIfTrueIfStrict(cond) do { if ((cond) && strictMode()) fail(); } while (0)
50 #define failIfFalseIfStrict(cond) do { if ((!(cond)) && strictMode()) fail(); } while (0)
51 #define consumeOrFail(tokenType) do { if (!consume(tokenType)) fail(); } while (0)
52 #define matchOrFail(tokenType) do { if (!match(tokenType)) fail(); } while (0)
53 #define failIfStackOverflow() do { failIfFalse(canRecurse()); } while (0)
54
55 // Macros to make the more common TreeBuilder types a little less verbose
56 #define TreeStatement typename TreeBuilder::Statement
57 #define TreeExpression typename TreeBuilder::Expression
58 #define TreeFormalParameterList typename TreeBuilder::FormalParameterList
59 #define TreeSourceElements typename TreeBuilder::SourceElements
60 #define TreeClause typename TreeBuilder::Clause
61 #define TreeClauseList typename TreeBuilder::ClauseList
62 #define TreeConstDeclList typename TreeBuilder::ConstDeclList
63 #define TreeArguments typename TreeBuilder::Arguments
64 #define TreeArgumentsList typename TreeBuilder::ArgumentsList
65 #define TreeFunctionBody typename TreeBuilder::FunctionBody
66 #define TreeProperty typename TreeBuilder::Property
67 #define TreePropertyList typename TreeBuilder::PropertyList
68
69 COMPILE_ASSERT(LastUntaggedToken < 64, LessThan64UntaggedTokens);
70
71 class JSParser {
72 public:
73     JSParser(Lexer*, JSGlobalData*, FunctionParameters*, bool isStrictContext, bool isFunction, SourceProvider*);
74     const char* parseProgram();
75 private:
76     struct AllowInOverride {
77         AllowInOverride(JSParser* parser)
78             : m_parser(parser)
79             , m_oldAllowsIn(parser->m_allowsIn)
80         {
81             parser->m_allowsIn = true;
82         }
83         ~AllowInOverride()
84         {
85             m_parser->m_allowsIn = m_oldAllowsIn;
86         }
87         JSParser* m_parser;
88         bool m_oldAllowsIn;
89     };
90     
91     struct ScopeLabelInfo {
92         ScopeLabelInfo(StringImpl* ident, bool isLoop)
93         : m_ident(ident)
94         , m_isLoop(isLoop)
95         {
96         }
97         StringImpl* m_ident;
98         bool m_isLoop;
99     };
100     
101     void next(Lexer::LexType lexType = Lexer::IdentifyReservedWords)
102     {
103         m_lastLine = m_token.m_info.line;
104         m_lastTokenEnd = m_token.m_info.endOffset;
105         m_lexer->setLastLineNumber(m_lastLine);
106         m_token.m_type = m_lexer->lex(&m_token.m_data, &m_token.m_info, lexType, strictMode());
107     }
108     
109     bool nextTokenIsColon()
110     {
111         return m_lexer->nextTokenIsColon();
112     }
113
114     bool consume(JSTokenType expected)
115     {
116         bool result = m_token.m_type == expected;
117         failIfFalse(result);
118         next();
119         return result;
120     }
121
122     bool match(JSTokenType expected)
123     {
124         return m_token.m_type == expected;
125     }
126
127     int tokenStart()
128     {
129         return m_token.m_info.startOffset;
130     }
131
132     int tokenLine()
133     {
134         return m_token.m_info.line;
135     }
136
137     int tokenEnd()
138     {
139         return m_token.m_info.endOffset;
140     }
141     
142     void startLoop() { currentScope()->startLoop(); }
143     void endLoop() { currentScope()->endLoop(); }
144     void startSwitch() { currentScope()->startSwitch(); }
145     void endSwitch() { currentScope()->endSwitch(); }
146     void setStrictMode() { currentScope()->setStrictMode(); }
147     bool strictMode() { return currentScope()->strictMode(); }
148     bool isValidStrictMode() { return currentScope()->isValidStrictMode(); }
149     bool declareParameter(const Identifier* ident) { return currentScope()->declareParameter(ident); }
150     bool breakIsValid()
151     {
152         ScopeRef current = currentScope();
153         while (!current->breakIsValid()) {
154             if (!current.hasContainingScope())
155                 return false;
156             current = current.containingScope();
157         }
158         return true;
159     }
160     bool continueIsValid()
161     {
162         ScopeRef current = currentScope();
163         while (!current->continueIsValid()) {
164             if (!current.hasContainingScope())
165                 return false;
166             current = current.containingScope();
167         }
168         return true;
169     }
170     void pushLabel(const Identifier* label, bool isLoop) { currentScope()->pushLabel(label, isLoop); }
171     void popLabel() { currentScope()->popLabel(); }
172     ScopeLabelInfo* getLabel(const Identifier* label)
173     {
174         ScopeRef current = currentScope();
175         ScopeLabelInfo* result = 0;
176         while (!(result = current->getLabel(label))) {
177             if (!current.hasContainingScope())
178                 return 0;
179             current = current.containingScope();
180         }
181         return result;
182     }
183
184     enum SourceElementsMode { CheckForStrictMode, DontCheckForStrictMode };
185     template <SourceElementsMode mode, class TreeBuilder> TreeSourceElements parseSourceElements(TreeBuilder&);
186     template <class TreeBuilder> TreeStatement parseStatement(TreeBuilder&, const Identifier*& directive);
187     template <class TreeBuilder> TreeStatement parseFunctionDeclaration(TreeBuilder&);
188     template <class TreeBuilder> TreeStatement parseVarDeclaration(TreeBuilder&);
189     template <class TreeBuilder> TreeStatement parseConstDeclaration(TreeBuilder&);
190     template <class TreeBuilder> TreeStatement parseDoWhileStatement(TreeBuilder&);
191     template <class TreeBuilder> TreeStatement parseWhileStatement(TreeBuilder&);
192     template <class TreeBuilder> TreeStatement parseForStatement(TreeBuilder&);
193     template <class TreeBuilder> TreeStatement parseBreakStatement(TreeBuilder&);
194     template <class TreeBuilder> TreeStatement parseContinueStatement(TreeBuilder&);
195     template <class TreeBuilder> TreeStatement parseReturnStatement(TreeBuilder&);
196     template <class TreeBuilder> TreeStatement parseThrowStatement(TreeBuilder&);
197     template <class TreeBuilder> TreeStatement parseWithStatement(TreeBuilder&);
198     template <class TreeBuilder> TreeStatement parseSwitchStatement(TreeBuilder&);
199     template <class TreeBuilder> TreeClauseList parseSwitchClauses(TreeBuilder&);
200     template <class TreeBuilder> TreeClause parseSwitchDefaultClause(TreeBuilder&);
201     template <class TreeBuilder> TreeStatement parseTryStatement(TreeBuilder&);
202     template <class TreeBuilder> TreeStatement parseDebuggerStatement(TreeBuilder&);
203     template <class TreeBuilder> TreeStatement parseExpressionStatement(TreeBuilder&);
204     template <class TreeBuilder> TreeStatement parseExpressionOrLabelStatement(TreeBuilder&);
205     template <class TreeBuilder> TreeStatement parseIfStatement(TreeBuilder&);
206     template <class TreeBuilder> ALWAYS_INLINE TreeStatement parseBlockStatement(TreeBuilder&);
207     template <class TreeBuilder> TreeExpression parseExpression(TreeBuilder&);
208     template <class TreeBuilder> TreeExpression parseAssignmentExpression(TreeBuilder&);
209     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseConditionalExpression(TreeBuilder&);
210     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseBinaryExpression(TreeBuilder&);
211     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseUnaryExpression(TreeBuilder&);
212     template <class TreeBuilder> TreeExpression parseMemberExpression(TreeBuilder&);
213     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parsePrimaryExpression(TreeBuilder&);
214     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseArrayLiteral(TreeBuilder&);
215     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseObjectLiteral(TreeBuilder&);
216     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseStrictObjectLiteral(TreeBuilder&);
217     template <class TreeBuilder> ALWAYS_INLINE TreeArguments parseArguments(TreeBuilder&);
218     template <bool strict, class TreeBuilder> ALWAYS_INLINE TreeProperty parseProperty(TreeBuilder&);
219     template <class TreeBuilder> ALWAYS_INLINE TreeFunctionBody parseFunctionBody(TreeBuilder&);
220     template <class TreeBuilder> ALWAYS_INLINE TreeFormalParameterList parseFormalParameters(TreeBuilder&);
221     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseVarDeclarationList(TreeBuilder&, int& declarations, const Identifier*& lastIdent, TreeExpression& lastInitializer, int& identStart, int& initStart, int& initEnd);
222     template <class TreeBuilder> ALWAYS_INLINE TreeConstDeclList parseConstDeclarationList(TreeBuilder& context);
223     enum FunctionRequirements { FunctionNoRequirements, FunctionNeedsName };
224     template <FunctionRequirements, bool nameIsInContainingScope, class TreeBuilder> bool parseFunctionInfo(TreeBuilder&, const Identifier*&, TreeFormalParameterList&, TreeFunctionBody&, int& openBrace, int& closeBrace, int& bodyStartLine);
225     ALWAYS_INLINE int isBinaryOperator(JSTokenType token);
226     bool allowAutomaticSemicolon();
227
228     bool autoSemiColon()
229     {
230         if (m_token.m_type == SEMICOLON) {
231             next();
232             return true;
233         }
234         return allowAutomaticSemicolon();
235     }
236
237     bool canRecurse()
238     {
239         return m_stack.recursionCheck();
240     }
241     
242     int lastTokenEnd() const
243     {
244         return m_lastTokenEnd;
245     }
246
247     ParserArena m_arena;
248     Lexer* m_lexer;
249     StackBounds m_stack;
250     bool m_error;
251     const char* m_errorMessage;
252     JSGlobalData* m_globalData;
253     JSToken m_token;
254     bool m_allowsIn;
255     int m_lastLine;
256     int m_lastTokenEnd;
257     int m_assignmentCount;
258     int m_nonLHSCount;
259     bool m_syntaxAlreadyValidated;
260     int m_statementDepth;
261     int m_nonTrivialExpressionCount;
262     const Identifier* m_lastIdentifier;
263
264     struct DepthManager {
265         DepthManager(int* depth)
266             : m_originalDepth(*depth)
267             , m_depth(depth)
268         {
269         }
270         
271         ~DepthManager()
272         {
273             *m_depth = m_originalDepth;
274         }
275         
276     private:
277         int m_originalDepth;
278         int* m_depth;
279     };
280     
281     struct Scope {
282         Scope(JSGlobalData* globalData, bool isFunction, bool strictMode)
283             : m_globalData(globalData)
284             , m_shadowsArguments(false)
285             , m_usesEval(false)
286             , m_needsFullActivation(false)
287             , m_allowsNewDecls(true)
288             , m_strictMode(strictMode)
289             , m_isFunction(isFunction)
290             , m_isFunctionBoundary(false)
291             , m_isValidStrictMode(true)
292             , m_loopDepth(0)
293             , m_switchDepth(0)
294             , m_labels(0)
295         {
296         }
297
298         Scope(const Scope& rhs)
299             : m_globalData(rhs.m_globalData)
300             , m_shadowsArguments(rhs.m_shadowsArguments)
301             , m_usesEval(rhs.m_usesEval)
302             , m_needsFullActivation(rhs.m_needsFullActivation)
303             , m_allowsNewDecls(rhs.m_allowsNewDecls)
304             , m_strictMode(rhs.m_strictMode)
305             , m_isFunction(rhs.m_isFunction)
306             , m_isFunctionBoundary(rhs.m_isFunctionBoundary)
307             , m_isValidStrictMode(rhs.m_isValidStrictMode)
308             , m_loopDepth(rhs.m_loopDepth)
309             , m_switchDepth(rhs.m_switchDepth)
310             , m_labels(0)
311         {
312             if (rhs.m_labels) {
313                 m_labels = adoptPtr(new LabelStack);
314                 
315                 typedef LabelStack::const_iterator iterator;
316                 iterator end = rhs.m_labels->end();
317                 for (iterator it = rhs.m_labels->begin(); it != end; ++it)
318                     m_labels->append(ScopeLabelInfo(it->m_ident, it->m_isLoop));
319             }
320         }
321
322         void startSwitch() { m_switchDepth++; }
323         void endSwitch() { m_switchDepth--; }
324         void startLoop() { m_loopDepth++; }
325         void endLoop() { ASSERT(m_loopDepth); m_loopDepth--; }
326         bool inLoop() { return !!m_loopDepth; }
327         bool breakIsValid() { return m_loopDepth || m_switchDepth; }
328         bool continueIsValid() { return m_loopDepth; }
329
330         void pushLabel(const Identifier* label, bool isLoop)
331         {
332             if (!m_labels)
333                 m_labels = adoptPtr(new LabelStack);
334             m_labels->append(ScopeLabelInfo(label->impl(), isLoop));
335         }
336
337         void popLabel()
338         {
339             ASSERT(m_labels);
340             ASSERT(m_labels->size());
341             m_labels->removeLast();
342         }
343
344         ScopeLabelInfo* getLabel(const Identifier* label)
345         {
346             if (!m_labels)
347                 return 0;
348             for (int i = m_labels->size(); i > 0; i--) {
349                 if (m_labels->at(i - 1).m_ident == label->impl())
350                     return &m_labels->at(i - 1);
351             }
352             return 0;
353         }
354
355         void setIsFunction()
356         {
357             m_isFunction = true;
358             m_isFunctionBoundary = true;
359         }
360         bool isFunction() { return m_isFunction; }
361         bool isFunctionBoundary() { return m_isFunctionBoundary; }
362         
363         bool declareVariable(const Identifier* ident)
364         {
365             bool isValidStrictMode = m_globalData->propertyNames->eval != *ident && m_globalData->propertyNames->arguments != *ident;
366             m_isValidStrictMode = m_isValidStrictMode && isValidStrictMode;
367             m_declaredVariables.add(ident->ustring().impl());
368             return isValidStrictMode;
369         }
370         
371         void declareWrite(const Identifier* ident)
372         {
373             ASSERT(m_strictMode);
374             m_writtenVariables.add(ident->impl());
375         }
376
377         void preventNewDecls() { m_allowsNewDecls = false; }
378         bool allowsNewDecls() const { return m_allowsNewDecls; }
379
380         bool declareParameter(const Identifier* ident)
381         {
382             bool isArguments = m_globalData->propertyNames->arguments == *ident;
383             bool isValidStrictMode = m_declaredVariables.add(ident->ustring().impl()).second && m_globalData->propertyNames->eval != *ident && !isArguments;
384             m_isValidStrictMode = m_isValidStrictMode && isValidStrictMode;
385             if (isArguments)
386                 m_shadowsArguments = true;
387             return isValidStrictMode;
388         }
389         
390         void useVariable(const Identifier* ident, bool isEval)
391         {
392             m_usesEval |= isEval;
393             m_usedVariables.add(ident->ustring().impl());
394         }
395         
396         void setNeedsFullActivation() { m_needsFullActivation = true; }
397         
398         bool collectFreeVariables(Scope* nestedScope, bool shouldTrackClosedVariables)
399         {
400             if (nestedScope->m_usesEval)
401                 m_usesEval = true;
402             IdentifierSet::iterator end = nestedScope->m_usedVariables.end();
403             for (IdentifierSet::iterator ptr = nestedScope->m_usedVariables.begin(); ptr != end; ++ptr) {
404                 if (nestedScope->m_declaredVariables.contains(*ptr))
405                     continue;
406                 m_usedVariables.add(*ptr);
407                 if (shouldTrackClosedVariables)
408                     m_closedVariables.add(*ptr);
409             }
410             if (nestedScope->m_writtenVariables.size()) {
411                 IdentifierSet::iterator end = nestedScope->m_writtenVariables.end();
412                 for (IdentifierSet::iterator ptr = nestedScope->m_writtenVariables.begin(); ptr != end; ++ptr) {
413                     if (nestedScope->m_declaredVariables.contains(*ptr))
414                         continue;
415                     m_writtenVariables.add(*ptr);
416                 }
417             }
418
419             return true;
420         }
421
422         void getUncapturedWrittenVariables(IdentifierSet& writtenVariables)
423         {
424             IdentifierSet::iterator end = m_writtenVariables.end();
425             for (IdentifierSet::iterator ptr = m_writtenVariables.begin(); ptr != end; ++ptr) {
426                 if (!m_declaredVariables.contains(*ptr))
427                     writtenVariables.add(*ptr);
428             }
429         }
430
431         void getCapturedVariables(IdentifierSet& capturedVariables)
432         {
433             if (m_needsFullActivation || m_usesEval) {
434                 capturedVariables.swap(m_declaredVariables);
435                 return;
436             }
437             for (IdentifierSet::iterator ptr = m_closedVariables.begin(); ptr != m_closedVariables.end(); ++ptr) {
438                 if (!m_declaredVariables.contains(*ptr))
439                     continue;
440                 capturedVariables.add(*ptr);
441             }
442         }
443         void setStrictMode() { m_strictMode = true; }
444         bool strictMode() const { return m_strictMode; }
445         bool isValidStrictMode() const { return m_isValidStrictMode; }
446         bool shadowsArguments() const { return m_shadowsArguments; }
447         
448         void copyCapturedVariablesToVector(const IdentifierSet& capturedVariables, Vector<RefPtr<StringImpl> >& vector)
449         {
450             IdentifierSet::iterator end = capturedVariables.end();
451             for (IdentifierSet::iterator it = capturedVariables.begin(); it != end; ++it) {
452                 if (m_declaredVariables.contains(*it))
453                     continue;
454                 vector.append(*it);
455             }
456             vector.shrinkToFit();
457         }
458
459         void saveFunctionInfo(SourceProviderCacheItem* info)
460         {
461             ASSERT(m_isFunction);
462             info->usesEval = m_usesEval;
463             copyCapturedVariablesToVector(m_writtenVariables, info->writtenVariables);
464             copyCapturedVariablesToVector(m_usedVariables, info->usedVariables);
465         }
466
467         void restoreFunctionInfo(const SourceProviderCacheItem* info)
468         {
469             ASSERT(m_isFunction);
470             m_usesEval = info->usesEval;
471             unsigned size = info->usedVariables.size();
472             for (unsigned i = 0; i < size; ++i)
473                 m_usedVariables.add(info->usedVariables[i]);
474             size = info->writtenVariables.size();
475             for (unsigned i = 0; i < size; ++i)
476                 m_writtenVariables.add(info->writtenVariables[i]);
477         }
478
479     private:
480         JSGlobalData* m_globalData;
481         bool m_shadowsArguments : 1;
482         bool m_usesEval : 1;
483         bool m_needsFullActivation : 1;
484         bool m_allowsNewDecls : 1;
485         bool m_strictMode : 1;
486         bool m_isFunction : 1;
487         bool m_isFunctionBoundary : 1;
488         bool m_isValidStrictMode : 1;
489         int m_loopDepth;
490         int m_switchDepth;
491
492         typedef Vector<ScopeLabelInfo, 2> LabelStack;
493         OwnPtr<LabelStack> m_labels;
494         IdentifierSet m_declaredVariables;
495         IdentifierSet m_usedVariables;
496         IdentifierSet m_closedVariables;
497         IdentifierSet m_writtenVariables;
498     };
499
500     typedef Vector<Scope, 10> ScopeStack;
501
502     struct ScopeRef {
503         ScopeRef(ScopeStack* scopeStack, unsigned index)
504             : m_scopeStack(scopeStack)
505             , m_index(index)
506         {
507         }
508         Scope* operator->() { return &m_scopeStack->at(m_index); }
509         unsigned index() const { return m_index; }
510
511         bool hasContainingScope()
512         {
513             return m_index && !m_scopeStack->at(m_index).isFunctionBoundary();
514         }
515
516         ScopeRef containingScope()
517         {
518             ASSERT(hasContainingScope());
519             return ScopeRef(m_scopeStack, m_index - 1);
520         }
521
522     private:
523         ScopeStack* m_scopeStack;
524         unsigned m_index;
525     };
526
527     struct AutoPopScopeRef : public ScopeRef {
528         AutoPopScopeRef(JSParser* parser, ScopeRef scope)
529             : ScopeRef(scope)
530             , m_parser(parser)
531         {
532         }
533
534         ~AutoPopScopeRef()
535         {
536             if (m_parser)
537                 m_parser->popScope(*this, false);
538         }
539
540         void setPopped()
541         {
542             m_parser = 0;
543         }
544
545     private:
546         JSParser* m_parser;
547     };
548
549     ScopeRef currentScope()
550     {
551         return ScopeRef(&m_scopeStack, m_scopeStack.size() - 1);
552     }
553     
554     ScopeRef pushScope()
555     {
556         bool isFunction = false;
557         bool isStrict = false;
558         if (!m_scopeStack.isEmpty()) {
559             isStrict = m_scopeStack.last().strictMode();
560             isFunction = m_scopeStack.last().isFunction();
561         }
562         m_scopeStack.append(Scope(m_globalData, isFunction, isStrict));
563         return currentScope();
564     }
565
566     bool popScopeInternal(ScopeRef& scope, bool shouldTrackClosedVariables)
567     {
568         ASSERT_UNUSED(scope, scope.index() == m_scopeStack.size() - 1);
569         ASSERT(m_scopeStack.size() > 1);
570         bool result = m_scopeStack[m_scopeStack.size() - 2].collectFreeVariables(&m_scopeStack.last(), shouldTrackClosedVariables);
571         m_scopeStack.removeLast();
572         return result;
573     }
574
575     bool popScope(ScopeRef& scope, bool shouldTrackClosedVariables)
576     {
577         return popScopeInternal(scope, shouldTrackClosedVariables);
578     }
579
580     bool popScope(AutoPopScopeRef& scope, bool shouldTrackClosedVariables)
581     {
582         scope.setPopped();
583         return popScopeInternal(scope, shouldTrackClosedVariables);
584     }
585
586     bool declareVariable(const Identifier* ident)
587     {
588         unsigned i = m_scopeStack.size() - 1;
589         ASSERT(i < m_scopeStack.size());
590         while (!m_scopeStack[i].allowsNewDecls()) {
591             i--;
592             ASSERT(i < m_scopeStack.size());
593         }
594         return m_scopeStack[i].declareVariable(ident);
595     }
596     
597     void declareWrite(const Identifier* ident)
598     {
599         if (!m_syntaxAlreadyValidated)
600             m_scopeStack.last().declareWrite(ident);
601     }
602
603     ScopeStack m_scopeStack;
604
605     const SourceProviderCacheItem* findCachedFunctionInfo(int openBracePos) 
606     {
607         return m_functionCache ? m_functionCache->get(openBracePos) : 0;
608     }
609
610     SourceProviderCache* m_functionCache;
611 };
612
613 const char* jsParse(JSGlobalData* globalData, FunctionParameters* parameters, JSParserStrictness strictness, JSParserMode parserMode, const SourceCode* source)
614 {
615     JSParser parser(globalData->lexer, globalData, parameters, strictness == JSParseStrict, parserMode == JSParseFunctionCode, source->provider());
616     return parser.parseProgram();
617 }
618
619 JSParser::JSParser(Lexer* lexer, JSGlobalData* globalData, FunctionParameters* parameters, bool inStrictContext, bool isFunction, SourceProvider* provider)
620     : m_lexer(lexer)
621     , m_stack(globalData->stack())
622     , m_error(false)
623     , m_errorMessage("Parse error")
624     , m_globalData(globalData)
625     , m_allowsIn(true)
626     , m_lastLine(0)
627     , m_lastTokenEnd(0)
628     , m_assignmentCount(0)
629     , m_nonLHSCount(0)
630     , m_syntaxAlreadyValidated(provider->isValid())
631     , m_statementDepth(0)
632     , m_nonTrivialExpressionCount(0)
633     , m_lastIdentifier(0)
634     , m_functionCache(m_lexer->sourceProvider()->cache())
635 {
636     ScopeRef scope = pushScope();
637     if (isFunction)
638         scope->setIsFunction();
639     if (inStrictContext)
640         scope->setStrictMode();
641     if (parameters) {
642         for (unsigned i = 0; i < parameters->size(); i++)
643             scope->declareParameter(&parameters->at(i));
644     }
645     next();
646     m_lexer->setLastLineNumber(tokenLine());
647 }
648
649 const char* JSParser::parseProgram()
650 {
651     unsigned oldFunctionCacheSize = m_functionCache ? m_functionCache->byteSize() : 0;
652     ASTBuilder context(m_globalData, m_lexer);
653     if (m_lexer->isReparsing())
654         m_statementDepth--;
655     ScopeRef scope = currentScope();
656     SourceElements* sourceElements = parseSourceElements<CheckForStrictMode>(context);
657     if (!sourceElements || !consume(EOFTOK))
658         return m_errorMessage;
659     IdentifierSet capturedVariables;
660     scope->getCapturedVariables(capturedVariables);
661     CodeFeatures features = context.features();
662     if (scope->strictMode())
663         features |= StrictModeFeature;
664     if (scope->shadowsArguments())
665         features |= ShadowsArgumentsFeature;
666     
667     unsigned functionCacheSize = m_functionCache ? m_functionCache->byteSize() : 0;
668     if (functionCacheSize != oldFunctionCacheSize)
669         m_lexer->sourceProvider()->notifyCacheSizeChanged(functionCacheSize - oldFunctionCacheSize);
670
671     m_globalData->parser->didFinishParsing(sourceElements, context.varDeclarations(), context.funcDeclarations(), features,
672                                            m_lastLine, context.numConstants(), capturedVariables);
673     return 0;
674 }
675
676 bool JSParser::allowAutomaticSemicolon()
677 {
678     return match(CLOSEBRACE) || match(EOFTOK) || m_lexer->prevTerminator();
679 }
680
681 template <JSParser::SourceElementsMode mode, class TreeBuilder> TreeSourceElements JSParser::parseSourceElements(TreeBuilder& context)
682 {
683     TreeSourceElements sourceElements = context.createSourceElements();
684     bool seenNonDirective = false;
685     const Identifier* directive = 0;
686     unsigned startOffset = m_token.m_info.startOffset;
687     bool hasSetStrict = false;
688     while (TreeStatement statement = parseStatement(context, directive)) {
689         if (mode == CheckForStrictMode && !seenNonDirective) {
690             if (directive) {
691                 if (!hasSetStrict && m_globalData->propertyNames->useStrictIdentifier == *directive) {
692                     setStrictMode();
693                     hasSetStrict = true;
694                     failIfFalse(isValidStrictMode());
695                     m_lexer->setOffset(startOffset);
696                     next();
697                     failIfTrue(m_error);
698                     continue;
699                 }
700             } else
701                 seenNonDirective = true;
702         }
703         context.appendStatement(sourceElements, statement);
704     }
705
706     if (m_error)
707         fail();
708     return sourceElements;
709 }
710
711 template <class TreeBuilder> TreeStatement JSParser::parseVarDeclaration(TreeBuilder& context)
712 {
713     ASSERT(match(VAR));
714     int start = tokenLine();
715     int end = 0;
716     int scratch;
717     const Identifier* scratch1 = 0;
718     TreeExpression scratch2 = 0;
719     int scratch3 = 0;
720     TreeExpression varDecls = parseVarDeclarationList(context, scratch, scratch1, scratch2, scratch3, scratch3, scratch3);
721     failIfTrue(m_error);
722     failIfFalse(autoSemiColon());
723
724     return context.createVarStatement(varDecls, start, end);
725 }
726
727 template <class TreeBuilder> TreeStatement JSParser::parseConstDeclaration(TreeBuilder& context)
728 {
729     ASSERT(match(CONSTTOKEN));
730     int start = tokenLine();
731     int end = 0;
732     TreeConstDeclList constDecls = parseConstDeclarationList(context);
733     failIfTrue(m_error);
734     failIfFalse(autoSemiColon());
735     
736     return context.createConstStatement(constDecls, start, end);
737 }
738
739 template <class TreeBuilder> TreeStatement JSParser::parseDoWhileStatement(TreeBuilder& context)
740 {
741     ASSERT(match(DO));
742     int startLine = tokenLine();
743     next();
744     const Identifier* unused = 0;
745     startLoop();
746     TreeStatement statement = parseStatement(context, unused);
747     endLoop();
748     failIfFalse(statement);
749     int endLine = tokenLine();
750     consumeOrFail(WHILE);
751     consumeOrFail(OPENPAREN);
752     TreeExpression expr = parseExpression(context);
753     failIfFalse(expr);
754     consumeOrFail(CLOSEPAREN);
755     if (match(SEMICOLON))
756         next(); // Always performs automatic semicolon insertion.
757     return context.createDoWhileStatement(statement, expr, startLine, endLine);
758 }
759
760 template <class TreeBuilder> TreeStatement JSParser::parseWhileStatement(TreeBuilder& context)
761 {
762     ASSERT(match(WHILE));
763     int startLine = tokenLine();
764     next();
765     consumeOrFail(OPENPAREN);
766     TreeExpression expr = parseExpression(context);
767     failIfFalse(expr);
768     int endLine = tokenLine();
769     consumeOrFail(CLOSEPAREN);
770     const Identifier* unused = 0;
771     startLoop();
772     TreeStatement statement = parseStatement(context, unused);
773     endLoop();
774     failIfFalse(statement);
775     return context.createWhileStatement(expr, statement, startLine, endLine);
776 }
777
778 template <class TreeBuilder> TreeExpression JSParser::parseVarDeclarationList(TreeBuilder& context, int& declarations, const Identifier*& lastIdent, TreeExpression& lastInitializer, int& identStart, int& initStart, int& initEnd)
779 {
780     TreeExpression varDecls = 0;
781     do {
782         declarations++;
783         next();
784         matchOrFail(IDENT);
785
786         int varStart = tokenStart();
787         identStart = varStart;
788         const Identifier* name = m_token.m_data.ident;
789         lastIdent = name;
790         next();
791         bool hasInitializer = match(EQUAL);
792         failIfFalseIfStrict(declareVariable(name));
793         context.addVar(name, (hasInitializer || (!m_allowsIn && match(INTOKEN))) ? DeclarationStacks::HasInitializer : 0);
794         if (hasInitializer) {
795             int varDivot = tokenStart() + 1;
796             initStart = tokenStart();
797             next(); // consume '='
798             int initialAssignments = m_assignmentCount;
799             TreeExpression initializer = parseAssignmentExpression(context);
800             initEnd = lastTokenEnd();
801             lastInitializer = initializer;
802             failIfFalse(initializer);
803
804             TreeExpression node = context.createAssignResolve(*name, initializer, initialAssignments != m_assignmentCount, varStart, varDivot, lastTokenEnd());
805             if (!varDecls)
806                 varDecls = node;
807             else
808                 varDecls = context.combineCommaNodes(varDecls, node);
809         }
810     } while (match(COMMA));
811     return varDecls;
812 }
813
814 template <class TreeBuilder> TreeConstDeclList JSParser::parseConstDeclarationList(TreeBuilder& context)
815 {
816     failIfTrue(strictMode());
817     TreeConstDeclList constDecls = 0;
818     TreeConstDeclList tail = 0;
819     do {
820         next();
821         matchOrFail(IDENT);
822         const Identifier* name = m_token.m_data.ident;
823         next();
824         bool hasInitializer = match(EQUAL);
825         declareVariable(name);
826         context.addVar(name, DeclarationStacks::IsConstant | (hasInitializer ? DeclarationStacks::HasInitializer : 0));
827         TreeExpression initializer = 0;
828         if (hasInitializer) {
829             next(); // consume '='
830             initializer = parseAssignmentExpression(context);
831         }
832         tail = context.appendConstDecl(tail, name, initializer);
833         if (!constDecls)
834             constDecls = tail;
835     } while (match(COMMA));
836     return constDecls;
837 }
838
839 template <class TreeBuilder> TreeStatement JSParser::parseForStatement(TreeBuilder& context)
840 {
841     ASSERT(match(FOR));
842     int startLine = tokenLine();
843     next();
844     consumeOrFail(OPENPAREN);
845     int nonLHSCount = m_nonLHSCount;
846     int declarations = 0;
847     int declsStart = 0;
848     int declsEnd = 0;
849     TreeExpression decls = 0;
850     bool hasDeclaration = false;
851     if (match(VAR)) {
852         /*
853          for (var IDENT in expression) statement
854          for (var IDENT = expression in expression) statement
855          for (var varDeclarationList; expressionOpt; expressionOpt)
856          */
857         hasDeclaration = true;
858         const Identifier* forInTarget = 0;
859         TreeExpression forInInitializer = 0;
860         m_allowsIn = false;
861         int initStart = 0;
862         int initEnd = 0;
863         decls = parseVarDeclarationList(context, declarations, forInTarget, forInInitializer, declsStart, initStart, initEnd);
864         m_allowsIn = true;
865         if (m_error)
866             fail();
867
868         // Remainder of a standard for loop is handled identically
869         if (match(SEMICOLON))
870             goto standardForLoop;
871
872         failIfFalse(declarations == 1);
873
874         // Handle for-in with var declaration
875         int inLocation = tokenStart();
876         if (!consume(INTOKEN))
877             fail();
878
879         TreeExpression expr = parseExpression(context);
880         failIfFalse(expr);
881         int exprEnd = lastTokenEnd();
882
883         int endLine = tokenLine();
884         consumeOrFail(CLOSEPAREN);
885
886         const Identifier* unused = 0;
887         startLoop();
888         TreeStatement statement = parseStatement(context, unused);
889         endLoop();
890         failIfFalse(statement);
891
892         return context.createForInLoop(forInTarget, forInInitializer, expr, statement, declsStart, inLocation, exprEnd, initStart, initEnd, startLine, endLine);
893     }
894
895     if (!match(SEMICOLON)) {
896         m_allowsIn = false;
897         declsStart = tokenStart();
898         decls = parseExpression(context);
899         declsEnd = lastTokenEnd();
900         m_allowsIn = true;
901         failIfFalse(decls);
902     }
903
904     if (match(SEMICOLON)) {
905     standardForLoop:
906         // Standard for loop
907         next();
908         TreeExpression condition = 0;
909
910         if (!match(SEMICOLON)) {
911             condition = parseExpression(context);
912             failIfFalse(condition);
913         }
914         consumeOrFail(SEMICOLON);
915
916         TreeExpression increment = 0;
917         if (!match(CLOSEPAREN)) {
918             increment = parseExpression(context);
919             failIfFalse(increment);
920         }
921         int endLine = tokenLine();
922         consumeOrFail(CLOSEPAREN);
923         const Identifier* unused = 0;
924         startLoop();
925         TreeStatement statement = parseStatement(context, unused);
926         endLoop();
927         failIfFalse(statement);
928         return context.createForLoop(decls, condition, increment, statement, hasDeclaration, startLine, endLine);
929     }
930
931     // For-in loop
932     failIfFalse(nonLHSCount == m_nonLHSCount);
933     consumeOrFail(INTOKEN);
934     TreeExpression expr = parseExpression(context);
935     failIfFalse(expr);
936     int exprEnd = lastTokenEnd();
937     int endLine = tokenLine();
938     consumeOrFail(CLOSEPAREN);
939     const Identifier* unused = 0;
940     startLoop();
941     TreeStatement statement = parseStatement(context, unused);
942     endLoop();
943     failIfFalse(statement);
944     
945     return context.createForInLoop(decls, expr, statement, declsStart, declsEnd, exprEnd, startLine, endLine);
946 }
947
948 template <class TreeBuilder> TreeStatement JSParser::parseBreakStatement(TreeBuilder& context)
949 {
950     ASSERT(match(BREAK));
951     int startCol = tokenStart();
952     int endCol = tokenEnd();
953     int startLine = tokenLine();
954     int endLine = tokenLine();
955     next();
956
957     if (autoSemiColon()) {
958         failIfFalse(breakIsValid());
959         return context.createBreakStatement(startCol, endCol, startLine, endLine);
960     }
961     matchOrFail(IDENT);
962     const Identifier* ident = m_token.m_data.ident;
963     failIfFalse(getLabel(ident));
964     endCol = tokenEnd();
965     endLine = tokenLine();
966     next();
967     failIfFalse(autoSemiColon());
968     return context.createBreakStatement(ident, startCol, endCol, startLine, endLine);
969 }
970
971 template <class TreeBuilder> TreeStatement JSParser::parseContinueStatement(TreeBuilder& context)
972 {
973     ASSERT(match(CONTINUE));
974     int startCol = tokenStart();
975     int endCol = tokenEnd();
976     int startLine = tokenLine();
977     int endLine = tokenLine();
978     next();
979
980     if (autoSemiColon()) {
981         failIfFalse(continueIsValid());
982         return context.createContinueStatement(startCol, endCol, startLine, endLine);
983     }
984     matchOrFail(IDENT);
985     const Identifier* ident = m_token.m_data.ident;
986     ScopeLabelInfo* label = getLabel(ident);
987     failIfFalse(label);
988     failIfFalse(label->m_isLoop);
989     endCol = tokenEnd();
990     endLine = tokenLine();
991     next();
992     failIfFalse(autoSemiColon());
993     return context.createContinueStatement(ident, startCol, endCol, startLine, endLine);
994 }
995
996 template <class TreeBuilder> TreeStatement JSParser::parseReturnStatement(TreeBuilder& context)
997 {
998     ASSERT(match(RETURN));
999     failIfFalse(currentScope()->isFunction());
1000     int startLine = tokenLine();
1001     int endLine = startLine;
1002     int start = tokenStart();
1003     int end = tokenEnd();
1004     next();
1005     // We do the auto semicolon check before attempting to parse an expression
1006     // as we need to ensure the a line break after the return correctly terminates
1007     // the statement
1008     if (match(SEMICOLON))
1009         endLine  = tokenLine();
1010     if (autoSemiColon())
1011         return context.createReturnStatement(0, start, end, startLine, endLine);
1012     TreeExpression expr = parseExpression(context);
1013     failIfFalse(expr);
1014     end = lastTokenEnd();
1015     if (match(SEMICOLON))
1016         endLine  = tokenLine();
1017     failIfFalse(autoSemiColon());
1018     return context.createReturnStatement(expr, start, end, startLine, endLine);
1019 }
1020
1021 template <class TreeBuilder> TreeStatement JSParser::parseThrowStatement(TreeBuilder& context)
1022 {
1023     ASSERT(match(THROW));
1024     int eStart = tokenStart();
1025     int startLine = tokenLine();
1026     next();
1027     
1028     failIfTrue(autoSemiColon());
1029
1030     TreeExpression expr = parseExpression(context);
1031     failIfFalse(expr);
1032     int eEnd = lastTokenEnd();
1033     int endLine = tokenLine();
1034     failIfFalse(autoSemiColon());
1035
1036     return context.createThrowStatement(expr, eStart, eEnd, startLine, endLine);
1037 }
1038
1039 template <class TreeBuilder> TreeStatement JSParser::parseWithStatement(TreeBuilder& context)
1040 {
1041     ASSERT(match(WITH));
1042     failIfTrue(strictMode());
1043     currentScope()->setNeedsFullActivation();
1044     int startLine = tokenLine();
1045     next();
1046     consumeOrFail(OPENPAREN);
1047     int start = tokenStart();
1048     TreeExpression expr = parseExpression(context);
1049     failIfFalse(expr);
1050     int end = lastTokenEnd();
1051
1052     int endLine = tokenLine();
1053     consumeOrFail(CLOSEPAREN);
1054     const Identifier* unused = 0;
1055     TreeStatement statement = parseStatement(context, unused);
1056     failIfFalse(statement);
1057
1058     return context.createWithStatement(expr, statement, start, end, startLine, endLine);
1059 }
1060
1061 template <class TreeBuilder> TreeStatement JSParser::parseSwitchStatement(TreeBuilder& context)
1062 {
1063     ASSERT(match(SWITCH));
1064     int startLine = tokenLine();
1065     next();
1066     consumeOrFail(OPENPAREN);
1067     TreeExpression expr = parseExpression(context);
1068     failIfFalse(expr);
1069     int endLine = tokenLine();
1070     consumeOrFail(CLOSEPAREN);
1071     consumeOrFail(OPENBRACE);
1072     startSwitch();
1073     TreeClauseList firstClauses = parseSwitchClauses(context);
1074     failIfTrue(m_error);
1075
1076     TreeClause defaultClause = parseSwitchDefaultClause(context);
1077     failIfTrue(m_error);
1078
1079     TreeClauseList secondClauses = parseSwitchClauses(context);
1080     failIfTrue(m_error);
1081     endSwitch();
1082     consumeOrFail(CLOSEBRACE);
1083
1084     return context.createSwitchStatement(expr, firstClauses, defaultClause, secondClauses, startLine, endLine);
1085
1086 }
1087
1088 template <class TreeBuilder> TreeClauseList JSParser::parseSwitchClauses(TreeBuilder& context)
1089 {
1090     if (!match(CASE))
1091         return 0;
1092     next();
1093     TreeExpression condition = parseExpression(context);
1094     failIfFalse(condition);
1095     consumeOrFail(COLON);
1096     TreeSourceElements statements = parseSourceElements<DontCheckForStrictMode>(context);
1097     failIfFalse(statements);
1098     TreeClause clause = context.createClause(condition, statements);
1099     TreeClauseList clauseList = context.createClauseList(clause);
1100     TreeClauseList tail = clauseList;
1101
1102     while (match(CASE)) {
1103         next();
1104         TreeExpression condition = parseExpression(context);
1105         failIfFalse(condition);
1106         consumeOrFail(COLON);
1107         TreeSourceElements statements = parseSourceElements<DontCheckForStrictMode>(context);
1108         failIfFalse(statements);
1109         clause = context.createClause(condition, statements);
1110         tail = context.createClauseList(tail, clause);
1111     }
1112     return clauseList;
1113 }
1114
1115 template <class TreeBuilder> TreeClause JSParser::parseSwitchDefaultClause(TreeBuilder& context)
1116 {
1117     if (!match(DEFAULT))
1118         return 0;
1119     next();
1120     consumeOrFail(COLON);
1121     TreeSourceElements statements = parseSourceElements<DontCheckForStrictMode>(context);
1122     failIfFalse(statements);
1123     return context.createClause(0, statements);
1124 }
1125
1126 template <class TreeBuilder> TreeStatement JSParser::parseTryStatement(TreeBuilder& context)
1127 {
1128     ASSERT(match(TRY));
1129     TreeStatement tryBlock = 0;
1130     const Identifier* ident = &m_globalData->propertyNames->nullIdentifier;
1131     bool catchHasEval = false;
1132     TreeStatement catchBlock = 0;
1133     TreeStatement finallyBlock = 0;
1134     int firstLine = tokenLine();
1135     next();
1136     matchOrFail(OPENBRACE);
1137
1138     tryBlock = parseBlockStatement(context);
1139     failIfFalse(tryBlock);
1140     int lastLine = m_lastLine;
1141
1142     if (match(CATCH)) {
1143         currentScope()->setNeedsFullActivation();
1144         next();
1145         consumeOrFail(OPENPAREN);
1146         matchOrFail(IDENT);
1147         ident = m_token.m_data.ident;
1148         next();
1149         AutoPopScopeRef catchScope(this, pushScope());
1150         failIfFalseIfStrict(catchScope->declareVariable(ident));
1151         catchScope->preventNewDecls();
1152         consumeOrFail(CLOSEPAREN);
1153         matchOrFail(OPENBRACE);
1154         int initialEvalCount = context.evalCount();
1155         catchBlock = parseBlockStatement(context);
1156         failIfFalse(catchBlock);
1157         catchHasEval = initialEvalCount != context.evalCount();
1158         failIfFalse(popScope(catchScope, TreeBuilder::NeedsFreeVariableInfo));
1159     }
1160
1161     if (match(FINALLY)) {
1162         next();
1163         matchOrFail(OPENBRACE);
1164         finallyBlock = parseBlockStatement(context);
1165         failIfFalse(finallyBlock);
1166     }
1167     failIfFalse(catchBlock || finallyBlock);
1168     return context.createTryStatement(tryBlock, ident, catchHasEval, catchBlock, finallyBlock, firstLine, lastLine);
1169 }
1170
1171 template <class TreeBuilder> TreeStatement JSParser::parseDebuggerStatement(TreeBuilder& context)
1172 {
1173     ASSERT(match(DEBUGGER));
1174     int startLine = tokenLine();
1175     int endLine = startLine;
1176     next();
1177     if (match(SEMICOLON))
1178         startLine = tokenLine();
1179     failIfFalse(autoSemiColon());
1180     return context.createDebugger(startLine, endLine);
1181 }
1182
1183 template <class TreeBuilder> TreeStatement JSParser::parseBlockStatement(TreeBuilder& context)
1184 {
1185     ASSERT(match(OPENBRACE));
1186     int start = tokenLine();
1187     next();
1188     if (match(CLOSEBRACE)) {
1189         next();
1190         return context.createBlockStatement(0, start, m_lastLine);
1191     }
1192     TreeSourceElements subtree = parseSourceElements<DontCheckForStrictMode>(context);
1193     failIfFalse(subtree);
1194     matchOrFail(CLOSEBRACE);
1195     next();
1196     return context.createBlockStatement(subtree, start, m_lastLine);
1197 }
1198
1199 template <class TreeBuilder> TreeStatement JSParser::parseStatement(TreeBuilder& context, const Identifier*& directive)
1200 {
1201     DepthManager statementDepth(&m_statementDepth);
1202     m_statementDepth++;
1203     directive = 0;
1204     int nonTrivialExpressionCount = 0;
1205     failIfStackOverflow();
1206     switch (m_token.m_type) {
1207     case OPENBRACE:
1208         return parseBlockStatement(context);
1209     case VAR:
1210         return parseVarDeclaration(context);
1211     case CONSTTOKEN:
1212         return parseConstDeclaration(context);
1213     case FUNCTION:
1214         failIfFalseIfStrict(m_statementDepth == 1);
1215         return parseFunctionDeclaration(context);
1216     case SEMICOLON:
1217         next();
1218         return context.createEmptyStatement();
1219     case IF:
1220         return parseIfStatement(context);
1221     case DO:
1222         return parseDoWhileStatement(context);
1223     case WHILE:
1224         return parseWhileStatement(context);
1225     case FOR:
1226         return parseForStatement(context);
1227     case CONTINUE:
1228         return parseContinueStatement(context);
1229     case BREAK:
1230         return parseBreakStatement(context);
1231     case RETURN:
1232         return parseReturnStatement(context);
1233     case WITH:
1234         return parseWithStatement(context);
1235     case SWITCH:
1236         return parseSwitchStatement(context);
1237     case THROW:
1238         return parseThrowStatement(context);
1239     case TRY:
1240         return parseTryStatement(context);
1241     case DEBUGGER:
1242         return parseDebuggerStatement(context);
1243     case EOFTOK:
1244     case CASE:
1245     case CLOSEBRACE:
1246     case DEFAULT:
1247         // These tokens imply the end of a set of source elements
1248         return 0;
1249     case IDENT:
1250         return parseExpressionOrLabelStatement(context);
1251     case STRING:
1252         directive = m_token.m_data.ident;
1253         nonTrivialExpressionCount = m_nonTrivialExpressionCount;
1254     default:
1255         TreeStatement exprStatement = parseExpressionStatement(context);
1256         if (directive && nonTrivialExpressionCount != m_nonTrivialExpressionCount)
1257             directive = 0;
1258         return exprStatement;
1259     }
1260 }
1261
1262 template <class TreeBuilder> TreeFormalParameterList JSParser::parseFormalParameters(TreeBuilder& context)
1263 {
1264     matchOrFail(IDENT);
1265     failIfFalseIfStrict(declareParameter(m_token.m_data.ident));
1266     TreeFormalParameterList list = context.createFormalParameterList(*m_token.m_data.ident);
1267     TreeFormalParameterList tail = list;
1268     next();
1269     while (match(COMMA)) {
1270         next();
1271         matchOrFail(IDENT);
1272         const Identifier* ident = m_token.m_data.ident;
1273         failIfFalseIfStrict(declareParameter(ident));
1274         next();
1275         tail = context.createFormalParameterList(tail, *ident);
1276     }
1277     return list;
1278 }
1279
1280 template <class TreeBuilder> TreeFunctionBody JSParser::parseFunctionBody(TreeBuilder& context)
1281 {
1282     if (match(CLOSEBRACE))
1283         return context.createFunctionBody(strictMode());
1284     DepthManager statementDepth(&m_statementDepth);
1285     m_statementDepth = 0;
1286     typename TreeBuilder::FunctionBodyBuilder bodyBuilder(m_globalData, m_lexer);
1287     failIfFalse(parseSourceElements<CheckForStrictMode>(bodyBuilder));
1288     return context.createFunctionBody(strictMode());
1289 }
1290
1291 template <JSParser::FunctionRequirements requirements, bool nameIsInContainingScope, class TreeBuilder> bool JSParser::parseFunctionInfo(TreeBuilder& context, const Identifier*& name, TreeFormalParameterList& parameters, TreeFunctionBody& body, int& openBracePos, int& closeBracePos, int& bodyStartLine)
1292 {
1293     AutoPopScopeRef functionScope(this, pushScope());
1294     functionScope->setIsFunction();
1295     if (match(IDENT)) {
1296         name = m_token.m_data.ident;
1297         failIfTrue(*name == m_globalData->propertyNames->underscoreProto);
1298         next();
1299         if (!nameIsInContainingScope)
1300             failIfFalseIfStrict(functionScope->declareVariable(name));
1301     } else if (requirements == FunctionNeedsName)
1302         return false;
1303     consumeOrFail(OPENPAREN);
1304     if (!match(CLOSEPAREN)) {
1305         parameters = parseFormalParameters(context);
1306         failIfFalse(parameters);
1307     }
1308     consumeOrFail(CLOSEPAREN);
1309     matchOrFail(OPENBRACE);
1310
1311     openBracePos = m_token.m_data.intValue;
1312     bodyStartLine = tokenLine();
1313
1314     if (const SourceProviderCacheItem* cachedInfo = TreeBuilder::CanUseFunctionCache ? findCachedFunctionInfo(openBracePos) : 0) {
1315         // If we know about this function already, we can use the cached info and skip the parser to the end of the function.
1316         body = context.createFunctionBody(strictMode());
1317
1318         functionScope->restoreFunctionInfo(cachedInfo);
1319         failIfFalse(popScope(functionScope, TreeBuilder::NeedsFreeVariableInfo));
1320
1321         closeBracePos = cachedInfo->closeBracePos;
1322         m_token = cachedInfo->closeBraceToken();
1323         m_lexer->setOffset(m_token.m_info.endOffset);
1324         m_lexer->setLineNumber(m_token.m_info.line);
1325
1326         next();
1327         return true;
1328     }
1329
1330     next();
1331
1332     body = parseFunctionBody(context);
1333     failIfFalse(body);
1334     if (functionScope->strictMode() && name) {
1335         failIfTrue(m_globalData->propertyNames->arguments == *name);
1336         failIfTrue(m_globalData->propertyNames->eval == *name);
1337     }
1338     closeBracePos = m_token.m_data.intValue;
1339     
1340     // Cache the tokenizer state and the function scope the first time the function is parsed.
1341     // Any future reparsing can then skip the function.
1342     static const int minimumFunctionLengthToCache = 64;
1343     OwnPtr<SourceProviderCacheItem> newInfo;
1344     int functionLength = closeBracePos - openBracePos;
1345     if (TreeBuilder::CanUseFunctionCache && m_functionCache && functionLength > minimumFunctionLengthToCache) {
1346         newInfo = adoptPtr(new SourceProviderCacheItem(m_token.m_info.line, closeBracePos));
1347         functionScope->saveFunctionInfo(newInfo.get());
1348     }
1349     
1350     failIfFalse(popScope(functionScope, TreeBuilder::NeedsFreeVariableInfo));
1351     matchOrFail(CLOSEBRACE);
1352
1353     if (newInfo) {
1354         unsigned approximateByteSize = newInfo->approximateByteSize();
1355         m_functionCache->add(openBracePos, newInfo.release(), approximateByteSize);
1356     }
1357
1358     next();
1359     return true;
1360 }
1361
1362 template <class TreeBuilder> TreeStatement JSParser::parseFunctionDeclaration(TreeBuilder& context)
1363 {
1364     ASSERT(match(FUNCTION));
1365     next();
1366     const Identifier* name = 0;
1367     TreeFormalParameterList parameters = 0;
1368     TreeFunctionBody body = 0;
1369     int openBracePos = 0;
1370     int closeBracePos = 0;
1371     int bodyStartLine = 0;
1372     failIfFalse((parseFunctionInfo<FunctionNeedsName, true>(context, name, parameters, body, openBracePos, closeBracePos, bodyStartLine)));
1373     failIfFalse(name);
1374     failIfFalseIfStrict(declareVariable(name));
1375     return context.createFuncDeclStatement(name, body, parameters, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
1376 }
1377
1378 struct LabelInfo {
1379     LabelInfo(const Identifier* ident, int start, int end)
1380         : m_ident(ident)
1381         , m_start(start)
1382         , m_end(end)
1383     {
1384     }
1385
1386     const Identifier* m_ident;
1387     int m_start;
1388     int m_end;
1389 };
1390
1391 template <class TreeBuilder> TreeStatement JSParser::parseExpressionOrLabelStatement(TreeBuilder& context)
1392 {
1393
1394     /* Expression and Label statements are ambiguous at LL(1), so we have a
1395      * special case that looks for a colon as the next character in the input.
1396      */
1397     Vector<LabelInfo> labels;
1398
1399     do {
1400         int start = tokenStart();
1401         int startLine = tokenLine();
1402         if (!nextTokenIsColon()) {
1403             // If we hit this path we're making a expression statement, which
1404             // by definition can't make use of continue/break so we can just
1405             // ignore any labels we might have accumulated.
1406             TreeExpression expression = parseExpression(context);
1407             failIfFalse(expression);
1408             failIfFalse(autoSemiColon());
1409             return context.createExprStatement(expression, startLine, m_lastLine);
1410         }
1411         const Identifier* ident = m_token.m_data.ident;
1412         int end = tokenEnd();
1413         next();
1414         consumeOrFail(COLON);
1415         if (!m_syntaxAlreadyValidated) {
1416             // This is O(N^2) over the current list of consecutive labels, but I
1417             // have never seen more than one label in a row in the real world.
1418             for (size_t i = 0; i < labels.size(); i++)
1419                 failIfTrue(ident->impl() == labels[i].m_ident->impl());
1420             failIfTrue(getLabel(ident));
1421             labels.append(LabelInfo(ident, start, end));
1422         }
1423     } while (match(IDENT));
1424     bool isLoop = false;
1425     switch (m_token.m_type) {
1426     case FOR:
1427     case WHILE:
1428     case DO:
1429         isLoop = true;
1430         break;
1431
1432     default:
1433         break;
1434     }
1435     const Identifier* unused = 0;
1436     if (!m_syntaxAlreadyValidated) {
1437         for (size_t i = 0; i < labels.size(); i++)
1438             pushLabel(labels[i].m_ident, isLoop);
1439     }
1440     TreeStatement statement = parseStatement(context, unused);
1441     if (!m_syntaxAlreadyValidated) {
1442         for (size_t i = 0; i < labels.size(); i++)
1443             popLabel();
1444     }
1445     failIfFalse(statement);
1446     for (size_t i = 0; i < labels.size(); i++) {
1447         const LabelInfo& info = labels[labels.size() - i - 1];
1448         statement = context.createLabelStatement(info.m_ident, statement, info.m_start, info.m_end);
1449     }
1450     return statement;
1451 }
1452
1453 template <class TreeBuilder> TreeStatement JSParser::parseExpressionStatement(TreeBuilder& context)
1454 {
1455     int startLine = tokenLine();
1456     TreeExpression expression = parseExpression(context);
1457     failIfFalse(expression);
1458     failIfFalse(autoSemiColon());
1459     return context.createExprStatement(expression, startLine, m_lastLine);
1460 }
1461
1462 template <class TreeBuilder> TreeStatement JSParser::parseIfStatement(TreeBuilder& context)
1463 {
1464     ASSERT(match(IF));
1465
1466     int start = tokenLine();
1467     next();
1468
1469     consumeOrFail(OPENPAREN);
1470
1471     TreeExpression condition = parseExpression(context);
1472     failIfFalse(condition);
1473     int end = tokenLine();
1474     consumeOrFail(CLOSEPAREN);
1475
1476     const Identifier* unused = 0;
1477     TreeStatement trueBlock = parseStatement(context, unused);
1478     failIfFalse(trueBlock);
1479
1480     if (!match(ELSE))
1481         return context.createIfStatement(condition, trueBlock, start, end);
1482     
1483     Vector<TreeExpression> exprStack;
1484     Vector<pair<int, int> > posStack;
1485     Vector<TreeStatement> statementStack;
1486     bool trailingElse = false;
1487     do {
1488         next();
1489         if (!match(IF)) {
1490             const Identifier* unused = 0;
1491             TreeStatement block = parseStatement(context, unused);
1492             failIfFalse(block);
1493             statementStack.append(block);
1494             trailingElse = true;
1495             break;
1496         }
1497         int innerStart = tokenLine();
1498         next();
1499         
1500         consumeOrFail(OPENPAREN);
1501         
1502         TreeExpression innerCondition = parseExpression(context);
1503         failIfFalse(innerCondition);
1504         int innerEnd = tokenLine();
1505         consumeOrFail(CLOSEPAREN);
1506         const Identifier* unused = 0;
1507         TreeStatement innerTrueBlock = parseStatement(context, unused);
1508         failIfFalse(innerTrueBlock);     
1509         exprStack.append(innerCondition);
1510         posStack.append(make_pair(innerStart, innerEnd));
1511         statementStack.append(innerTrueBlock);
1512     } while (match(ELSE));
1513
1514     if (!trailingElse) {
1515         TreeExpression condition = exprStack.last();
1516         exprStack.removeLast();
1517         TreeStatement trueBlock = statementStack.last();
1518         statementStack.removeLast();
1519         pair<int, int> pos = posStack.last();
1520         posStack.removeLast();
1521         statementStack.append(context.createIfStatement(condition, trueBlock, pos.first, pos.second));
1522     }
1523
1524     while (!exprStack.isEmpty()) {
1525         TreeExpression condition = exprStack.last();
1526         exprStack.removeLast();
1527         TreeStatement falseBlock = statementStack.last();
1528         statementStack.removeLast();
1529         TreeStatement trueBlock = statementStack.last();
1530         statementStack.removeLast();
1531         pair<int, int> pos = posStack.last();
1532         posStack.removeLast();
1533         statementStack.append(context.createIfStatement(condition, trueBlock, falseBlock, pos.first, pos.second));
1534     }
1535     
1536     return context.createIfStatement(condition, trueBlock, statementStack.last(), start, end);
1537 }
1538
1539 template <class TreeBuilder> TreeExpression JSParser::parseExpression(TreeBuilder& context)
1540 {
1541     failIfStackOverflow();
1542     TreeExpression node = parseAssignmentExpression(context);
1543     failIfFalse(node);
1544     if (!match(COMMA))
1545         return node;
1546     next();
1547     m_nonTrivialExpressionCount++;
1548     m_nonLHSCount++;
1549     TreeExpression right = parseAssignmentExpression(context);
1550     failIfFalse(right);
1551     typename TreeBuilder::Comma commaNode = context.createCommaExpr(node, right);
1552     while (match(COMMA)) {
1553         next();
1554         right = parseAssignmentExpression(context);
1555         failIfFalse(right);
1556         context.appendToComma(commaNode, right);
1557     }
1558     return commaNode;
1559 }
1560
1561
1562 template <typename TreeBuilder> TreeExpression JSParser::parseAssignmentExpression(TreeBuilder& context)
1563 {
1564     failIfStackOverflow();
1565     int start = tokenStart();
1566     int initialAssignmentCount = m_assignmentCount;
1567     int initialNonLHSCount = m_nonLHSCount;
1568     TreeExpression lhs = parseConditionalExpression(context);
1569     failIfFalse(lhs);
1570     if (initialNonLHSCount != m_nonLHSCount)
1571         return lhs;
1572
1573     int assignmentStack = 0;
1574     Operator op;
1575     bool hadAssignment = false;
1576     while (true) {
1577         switch (m_token.m_type) {
1578         case EQUAL: op = OpEqual; break;
1579         case PLUSEQUAL: op = OpPlusEq; break;
1580         case MINUSEQUAL: op = OpMinusEq; break;
1581         case MULTEQUAL: op = OpMultEq; break;
1582         case DIVEQUAL: op = OpDivEq; break;
1583         case LSHIFTEQUAL: op = OpLShift; break;
1584         case RSHIFTEQUAL: op = OpRShift; break;
1585         case URSHIFTEQUAL: op = OpURShift; break;
1586         case ANDEQUAL: op = OpAndEq; break;
1587         case XOREQUAL: op = OpXOrEq; break;
1588         case OREQUAL: op = OpOrEq; break;
1589         case MODEQUAL: op = OpModEq; break;
1590         default:
1591             goto end;
1592         }
1593         m_nonTrivialExpressionCount++;
1594         hadAssignment = true;
1595         context.assignmentStackAppend(assignmentStack, lhs, start, tokenStart(), m_assignmentCount, op);
1596         start = tokenStart();
1597         m_assignmentCount++;
1598         next();
1599         if (strictMode() && m_lastIdentifier && context.isResolve(lhs)) {
1600             failIfTrueIfStrict(m_globalData->propertyNames->eval == *m_lastIdentifier);
1601             failIfTrueIfStrict(m_globalData->propertyNames->arguments == *m_lastIdentifier);
1602             declareWrite(m_lastIdentifier);
1603             m_lastIdentifier = 0;
1604         }
1605         lhs = parseConditionalExpression(context);
1606         failIfFalse(lhs);
1607         if (initialNonLHSCount != m_nonLHSCount)
1608             break;
1609     }
1610 end:
1611     if (hadAssignment)
1612         m_nonLHSCount++;
1613
1614     if (!TreeBuilder::CreatesAST)
1615         return lhs;
1616
1617     while (assignmentStack)
1618         lhs = context.createAssignment(assignmentStack, lhs, initialAssignmentCount, m_assignmentCount, lastTokenEnd());
1619
1620     return lhs;
1621 }
1622
1623 template <class TreeBuilder> TreeExpression JSParser::parseConditionalExpression(TreeBuilder& context)
1624 {
1625     TreeExpression cond = parseBinaryExpression(context);
1626     failIfFalse(cond);
1627     if (!match(QUESTION))
1628         return cond;
1629     m_nonTrivialExpressionCount++;
1630     m_nonLHSCount++;
1631     next();
1632     TreeExpression lhs = parseAssignmentExpression(context);
1633     consumeOrFail(COLON);
1634
1635     TreeExpression rhs = parseAssignmentExpression(context);
1636     failIfFalse(rhs);
1637     return context.createConditionalExpr(cond, lhs, rhs);
1638 }
1639
1640 ALWAYS_INLINE static bool isUnaryOp(JSTokenType token)
1641 {
1642     return token & UnaryOpTokenFlag;
1643 }
1644
1645 int JSParser::isBinaryOperator(JSTokenType token)
1646 {
1647     if (m_allowsIn)
1648         return token & (BinaryOpTokenPrecedenceMask << BinaryOpTokenAllowsInPrecedenceAdditionalShift);
1649     return token & BinaryOpTokenPrecedenceMask;
1650 }
1651
1652 template <class TreeBuilder> TreeExpression JSParser::parseBinaryExpression(TreeBuilder& context)
1653 {
1654
1655     int operandStackDepth = 0;
1656     int operatorStackDepth = 0;
1657     typename TreeBuilder::BinaryExprContext binaryExprContext(context);
1658     while (true) {
1659         int exprStart = tokenStart();
1660         int initialAssignments = m_assignmentCount;
1661         TreeExpression current = parseUnaryExpression(context);
1662         failIfFalse(current);
1663
1664         context.appendBinaryExpressionInfo(operandStackDepth, current, exprStart, lastTokenEnd(), lastTokenEnd(), initialAssignments != m_assignmentCount);
1665         int precedence = isBinaryOperator(m_token.m_type);
1666         if (!precedence)
1667             break;
1668         m_nonTrivialExpressionCount++;
1669         m_nonLHSCount++;
1670         int operatorToken = m_token.m_type;
1671         next();
1672
1673         while (operatorStackDepth &&  context.operatorStackHasHigherPrecedence(operatorStackDepth, precedence)) {
1674             ASSERT(operandStackDepth > 1);
1675
1676             typename TreeBuilder::BinaryOperand rhs = context.getFromOperandStack(-1);
1677             typename TreeBuilder::BinaryOperand lhs = context.getFromOperandStack(-2);
1678             context.shrinkOperandStackBy(operandStackDepth, 2);
1679             context.appendBinaryOperation(operandStackDepth, operatorStackDepth, lhs, rhs);
1680             context.operatorStackPop(operatorStackDepth);
1681         }
1682         context.operatorStackAppend(operatorStackDepth, operatorToken, precedence);
1683     }
1684     while (operatorStackDepth) {
1685         ASSERT(operandStackDepth > 1);
1686
1687         typename TreeBuilder::BinaryOperand rhs = context.getFromOperandStack(-1);
1688         typename TreeBuilder::BinaryOperand lhs = context.getFromOperandStack(-2);
1689         context.shrinkOperandStackBy(operandStackDepth, 2);
1690         context.appendBinaryOperation(operandStackDepth, operatorStackDepth, lhs, rhs);
1691         context.operatorStackPop(operatorStackDepth);
1692     }
1693     return context.popOperandStack(operandStackDepth);
1694 }
1695
1696
1697 template <bool complete, class TreeBuilder> TreeProperty JSParser::parseProperty(TreeBuilder& context)
1698 {
1699     bool wasIdent = false;
1700     switch (m_token.m_type) {
1701     namedProperty:
1702     case IDENT:
1703         wasIdent = true;
1704     case STRING: {
1705         const Identifier* ident = m_token.m_data.ident;
1706         next(Lexer::IgnoreReservedWords);
1707         if (match(COLON)) {
1708             next();
1709             TreeExpression node = parseAssignmentExpression(context);
1710             failIfFalse(node);
1711             return context.template createProperty<complete>(ident, node, PropertyNode::Constant);
1712         }
1713         failIfFalse(wasIdent);
1714         matchOrFail(IDENT);
1715         const Identifier* accessorName = 0;
1716         TreeFormalParameterList parameters = 0;
1717         TreeFunctionBody body = 0;
1718         int openBracePos = 0;
1719         int closeBracePos = 0;
1720         int bodyStartLine = 0;
1721         PropertyNode::Type type;
1722         if (*ident == m_globalData->propertyNames->get)
1723             type = PropertyNode::Getter;
1724         else if (*ident == m_globalData->propertyNames->set)
1725             type = PropertyNode::Setter;
1726         else
1727             fail();
1728         failIfFalse((parseFunctionInfo<FunctionNeedsName, false>(context, accessorName, parameters, body, openBracePos, closeBracePos, bodyStartLine)));
1729         return context.template createGetterOrSetterProperty<complete>(type, accessorName, parameters, body, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
1730     }
1731     case NUMBER: {
1732         double propertyName = m_token.m_data.doubleValue;
1733         next();
1734         consumeOrFail(COLON);
1735         TreeExpression node = parseAssignmentExpression(context);
1736         failIfFalse(node);
1737         return context.template createProperty<complete>(m_globalData, propertyName, node, PropertyNode::Constant);
1738     }
1739     default:
1740         failIfFalse(m_token.m_type & KeywordTokenFlag);
1741         goto namedProperty;
1742     }
1743 }
1744
1745 template <class TreeBuilder> TreeExpression JSParser::parseObjectLiteral(TreeBuilder& context)
1746 {
1747     int startOffset = m_token.m_data.intValue;
1748     consumeOrFail(OPENBRACE);
1749
1750     if (match(CLOSEBRACE)) {
1751         next();
1752         return context.createObjectLiteral();
1753     }
1754
1755     TreeProperty property = parseProperty<false>(context);
1756     failIfFalse(property);
1757     if (!m_syntaxAlreadyValidated && context.getType(property) != PropertyNode::Constant) {
1758         m_lexer->setOffset(startOffset);
1759         next();
1760         return parseStrictObjectLiteral(context);
1761     }
1762     TreePropertyList propertyList = context.createPropertyList(property);
1763     TreePropertyList tail = propertyList;
1764     while (match(COMMA)) {
1765         next();
1766         // allow extra comma, see http://bugs.webkit.org/show_bug.cgi?id=5939
1767         if (match(CLOSEBRACE))
1768             break;
1769         property = parseProperty<false>(context);
1770         failIfFalse(property);
1771         if (!m_syntaxAlreadyValidated && context.getType(property) != PropertyNode::Constant) {
1772             m_lexer->setOffset(startOffset);
1773             next();
1774             return parseStrictObjectLiteral(context);
1775         }
1776         tail = context.createPropertyList(property, tail);
1777     }
1778
1779     consumeOrFail(CLOSEBRACE);
1780
1781     return context.createObjectLiteral(propertyList);
1782 }
1783
1784 template <class TreeBuilder> TreeExpression JSParser::parseStrictObjectLiteral(TreeBuilder& context)
1785 {
1786     consumeOrFail(OPENBRACE);
1787     
1788     if (match(CLOSEBRACE)) {
1789         next();
1790         return context.createObjectLiteral();
1791     }
1792     
1793     TreeProperty property = parseProperty<true>(context);
1794     failIfFalse(property);
1795     
1796     typedef HashMap<RefPtr<StringImpl>, unsigned, IdentifierRepHash> ObjectValidationMap;
1797     ObjectValidationMap objectValidator;
1798     // Add the first property
1799     if (!m_syntaxAlreadyValidated)
1800         objectValidator.add(context.getName(property).impl(), context.getType(property));
1801     
1802     TreePropertyList propertyList = context.createPropertyList(property);
1803     TreePropertyList tail = propertyList;
1804     while (match(COMMA)) {
1805         next();
1806         // allow extra comma, see http://bugs.webkit.org/show_bug.cgi?id=5939
1807         if (match(CLOSEBRACE))
1808             break;
1809         property = parseProperty<true>(context);
1810         failIfFalse(property);
1811         if (!m_syntaxAlreadyValidated) {
1812             std::pair<ObjectValidationMap::iterator, bool> propertyEntryIter = objectValidator.add(context.getName(property).impl(), context.getType(property));
1813             if (!propertyEntryIter.second) {
1814                 failIfTrue(strictMode());
1815                 if ((context.getType(property) & propertyEntryIter.first->second) != PropertyNode::Constant) {
1816                     // Can't have multiple getters or setters with the same name, nor can we define 
1817                     // a property as both an accessor and a constant value
1818                     failIfTrue(context.getType(property) & propertyEntryIter.first->second);
1819                     failIfTrue((context.getType(property) | propertyEntryIter.first->second) & PropertyNode::Constant);
1820                 }
1821             }
1822         }
1823         tail = context.createPropertyList(property, tail);
1824     }
1825     
1826     consumeOrFail(CLOSEBRACE);
1827     
1828     return context.createObjectLiteral(propertyList);
1829 }
1830
1831 template <class TreeBuilder> TreeExpression JSParser::parseArrayLiteral(TreeBuilder& context)
1832 {
1833     consumeOrFail(OPENBRACKET);
1834
1835     int elisions = 0;
1836     while (match(COMMA)) {
1837         next();
1838         elisions++;
1839     }
1840     if (match(CLOSEBRACKET)) {
1841         next();
1842         return context.createArray(elisions);
1843     }
1844
1845     TreeExpression elem = parseAssignmentExpression(context);
1846     failIfFalse(elem);
1847     typename TreeBuilder::ElementList elementList = context.createElementList(elisions, elem);
1848     typename TreeBuilder::ElementList tail = elementList;
1849     elisions = 0;
1850     while (match(COMMA)) {
1851         next();
1852         elisions = 0;
1853
1854         while (match(COMMA)) {
1855             next();
1856             elisions++;
1857         }
1858
1859         if (match(CLOSEBRACKET)) {
1860             next();
1861             return context.createArray(elisions, elementList);
1862         }
1863         TreeExpression elem = parseAssignmentExpression(context);
1864         failIfFalse(elem);
1865         tail = context.createElementList(tail, elisions, elem);
1866     }
1867
1868     consumeOrFail(CLOSEBRACKET);
1869
1870     return context.createArray(elementList);
1871 }
1872
1873 template <class TreeBuilder> TreeExpression JSParser::parsePrimaryExpression(TreeBuilder& context)
1874 {
1875     switch (m_token.m_type) {
1876     case OPENBRACE:
1877         if (strictMode())
1878             return parseStrictObjectLiteral(context);
1879         return parseObjectLiteral(context);
1880     case OPENBRACKET:
1881         return parseArrayLiteral(context);
1882     case OPENPAREN: {
1883         next();
1884         int oldNonLHSCount = m_nonLHSCount;
1885         TreeExpression result = parseExpression(context);
1886         m_nonLHSCount = oldNonLHSCount;
1887         consumeOrFail(CLOSEPAREN);
1888
1889         return result;
1890     }
1891     case THISTOKEN: {
1892         next();
1893         return context.thisExpr();
1894     }
1895     case IDENT: {
1896         int start = tokenStart();
1897         const Identifier* ident = m_token.m_data.ident;
1898         next();
1899         currentScope()->useVariable(ident, m_globalData->propertyNames->eval == *ident);
1900         m_lastIdentifier = ident;
1901         return context.createResolve(ident, start);
1902     }
1903     case STRING: {
1904         const Identifier* ident = m_token.m_data.ident;
1905         next();
1906         return context.createString(ident);
1907     }
1908     case NUMBER: {
1909         double d = m_token.m_data.doubleValue;
1910         next();
1911         return context.createNumberExpr(d);
1912     }
1913     case NULLTOKEN: {
1914         next();
1915         return context.createNull();
1916     }
1917     case TRUETOKEN: {
1918         next();
1919         return context.createBoolean(true);
1920     }
1921     case FALSETOKEN: {
1922         next();
1923         return context.createBoolean(false);
1924     }
1925     case DIVEQUAL:
1926     case DIVIDE: {
1927         /* regexp */
1928         const Identifier* pattern;
1929         const Identifier* flags;
1930         if (match(DIVEQUAL))
1931             failIfFalse(m_lexer->scanRegExp(pattern, flags, '='));
1932         else
1933             failIfFalse(m_lexer->scanRegExp(pattern, flags));
1934
1935         int start = tokenStart();
1936         next();
1937         TreeExpression re = context.createRegExp(*pattern, *flags, start);
1938         if (!re) {
1939             m_errorMessage = Yarr::checkSyntax(pattern->ustring());
1940             ASSERT(m_errorMessage);
1941             fail();
1942         }
1943         return re;
1944     }
1945     default:
1946         fail();
1947     }
1948 }
1949
1950 template <class TreeBuilder> TreeArguments JSParser::parseArguments(TreeBuilder& context)
1951 {
1952     consumeOrFail(OPENPAREN);
1953     if (match(CLOSEPAREN)) {
1954         next();
1955         return context.createArguments();
1956     }
1957     TreeExpression firstArg = parseAssignmentExpression(context);
1958     failIfFalse(firstArg);
1959
1960     TreeArgumentsList argList = context.createArgumentsList(firstArg);
1961     TreeArgumentsList tail = argList;
1962     while (match(COMMA)) {
1963         next();
1964         TreeExpression arg = parseAssignmentExpression(context);
1965         failIfFalse(arg);
1966         tail = context.createArgumentsList(tail, arg);
1967     }
1968     consumeOrFail(CLOSEPAREN);
1969     return context.createArguments(argList);
1970 }
1971
1972 template <class TreeBuilder> TreeExpression JSParser::parseMemberExpression(TreeBuilder& context)
1973 {
1974     TreeExpression base = 0;
1975     int start = tokenStart();
1976     int expressionStart = start;
1977     int newCount = 0;
1978     while (match(NEW)) {
1979         next();
1980         newCount++;
1981     }
1982
1983     if (match(FUNCTION)) {
1984         const Identifier* name = &m_globalData->propertyNames->nullIdentifier;
1985         TreeFormalParameterList parameters = 0;
1986         TreeFunctionBody body = 0;
1987         int openBracePos = 0;
1988         int closeBracePos = 0;
1989         int bodyStartLine = 0;
1990         next();
1991         failIfFalse((parseFunctionInfo<FunctionNoRequirements, false>(context, name, parameters, body, openBracePos, closeBracePos, bodyStartLine)));
1992         base = context.createFunctionExpr(name, body, parameters, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
1993     } else
1994         base = parsePrimaryExpression(context);
1995
1996     failIfFalse(base);
1997     while (true) {
1998         switch (m_token.m_type) {
1999         case OPENBRACKET: {
2000             m_nonTrivialExpressionCount++;
2001             int expressionEnd = lastTokenEnd();
2002             next();
2003             int nonLHSCount = m_nonLHSCount;
2004             int initialAssignments = m_assignmentCount;
2005             TreeExpression property = parseExpression(context);
2006             failIfFalse(property);
2007             base = context.createBracketAccess(base, property, initialAssignments != m_assignmentCount, expressionStart, expressionEnd, tokenEnd());
2008             if (!consume(CLOSEBRACKET))
2009                 fail();
2010             m_nonLHSCount = nonLHSCount;
2011             break;
2012         }
2013         case OPENPAREN: {
2014             m_nonTrivialExpressionCount++;
2015             if (newCount) {
2016                 newCount--;
2017                 if (match(OPENPAREN)) {
2018                     int exprEnd = lastTokenEnd();
2019                     TreeArguments arguments = parseArguments(context);
2020                     failIfFalse(arguments);
2021                     base = context.createNewExpr(base, arguments, start, exprEnd, lastTokenEnd());
2022                 } else
2023                     base = context.createNewExpr(base, start, lastTokenEnd());               
2024             } else {
2025                 int nonLHSCount = m_nonLHSCount;
2026                 int expressionEnd = lastTokenEnd();
2027                 TreeArguments arguments = parseArguments(context);
2028                 failIfFalse(arguments);
2029                 base = context.makeFunctionCallNode(base, arguments, expressionStart, expressionEnd, lastTokenEnd());
2030                 m_nonLHSCount = nonLHSCount;
2031             }
2032             break;
2033         }
2034         case DOT: {
2035             m_nonTrivialExpressionCount++;
2036             int expressionEnd = lastTokenEnd();
2037             next(Lexer::IgnoreReservedWords);
2038             matchOrFail(IDENT);
2039             base = context.createDotAccess(base, *m_token.m_data.ident, expressionStart, expressionEnd, tokenEnd());
2040             next();
2041             break;
2042         }
2043         default:
2044             goto endMemberExpression;
2045         }
2046     }
2047 endMemberExpression:
2048     while (newCount--)
2049         base = context.createNewExpr(base, start, lastTokenEnd());
2050     return base;
2051 }
2052
2053 template <class TreeBuilder> TreeExpression JSParser::parseUnaryExpression(TreeBuilder& context)
2054 {
2055     typename TreeBuilder::UnaryExprContext unaryExprContext(context);
2056     AllowInOverride allowInOverride(this);
2057     int tokenStackDepth = 0;
2058     bool modifiesExpr = false;
2059     bool requiresLExpr = false;
2060     while (isUnaryOp(m_token.m_type)) {
2061         if (strictMode()) {
2062             switch (m_token.m_type) {
2063             case PLUSPLUS:
2064             case MINUSMINUS:
2065             case AUTOPLUSPLUS:
2066             case AUTOMINUSMINUS:
2067                 failIfTrue(requiresLExpr);
2068                 modifiesExpr = true;
2069                 requiresLExpr = true;
2070                 break;
2071             case DELETETOKEN:
2072                 failIfTrue(requiresLExpr);
2073                 requiresLExpr = true;
2074                 break;
2075             default:
2076                 failIfTrue(requiresLExpr);
2077                 break;
2078             }
2079         }
2080         m_nonLHSCount++;
2081         context.appendUnaryToken(tokenStackDepth, m_token.m_type, tokenStart());
2082         next();
2083         m_nonTrivialExpressionCount++;
2084     }
2085     int subExprStart = tokenStart();
2086     TreeExpression expr = parseMemberExpression(context);
2087     failIfFalse(expr);
2088     bool isEvalOrArguments = false;
2089     if (strictMode() && !m_syntaxAlreadyValidated) {
2090         if (context.isResolve(expr)) {
2091             isEvalOrArguments = *m_lastIdentifier == m_globalData->propertyNames->eval || *m_lastIdentifier == m_globalData->propertyNames->arguments;
2092         }
2093     }
2094     failIfTrueIfStrict(isEvalOrArguments && modifiesExpr);
2095     switch (m_token.m_type) {
2096     case PLUSPLUS:
2097         m_nonTrivialExpressionCount++;
2098         m_nonLHSCount++;
2099         expr = context.makePostfixNode(expr, OpPlusPlus, subExprStart, lastTokenEnd(), tokenEnd());
2100         m_assignmentCount++;
2101         failIfTrueIfStrict(isEvalOrArguments);
2102         failIfTrueIfStrict(requiresLExpr);
2103         next();
2104         break;
2105     case MINUSMINUS:
2106         m_nonTrivialExpressionCount++;
2107         m_nonLHSCount++;
2108         expr = context.makePostfixNode(expr, OpMinusMinus, subExprStart, lastTokenEnd(), tokenEnd());
2109         m_assignmentCount++;
2110         failIfTrueIfStrict(isEvalOrArguments);
2111         failIfTrueIfStrict(requiresLExpr);
2112         next();
2113         break;
2114     default:
2115         break;
2116     }
2117
2118     int end = lastTokenEnd();
2119
2120     if (!TreeBuilder::CreatesAST && (m_syntaxAlreadyValidated || !strictMode()))
2121         return expr;
2122
2123     while (tokenStackDepth) {
2124         switch (context.unaryTokenStackLastType(tokenStackDepth)) {
2125         case EXCLAMATION:
2126             expr = context.createLogicalNot(expr);
2127             break;
2128         case TILDE:
2129             expr = context.makeBitwiseNotNode(expr);
2130             break;
2131         case MINUS:
2132             expr = context.makeNegateNode(expr);
2133             break;
2134         case PLUS:
2135             expr = context.createUnaryPlus(expr);
2136             break;
2137         case PLUSPLUS:
2138         case AUTOPLUSPLUS:
2139             expr = context.makePrefixNode(expr, OpPlusPlus, context.unaryTokenStackLastStart(tokenStackDepth), subExprStart + 1, end);
2140             m_assignmentCount++;
2141             break;
2142         case MINUSMINUS:
2143         case AUTOMINUSMINUS:
2144             expr = context.makePrefixNode(expr, OpMinusMinus, context.unaryTokenStackLastStart(tokenStackDepth), subExprStart + 1, end);
2145             m_assignmentCount++;
2146             break;
2147         case TYPEOF:
2148             expr = context.makeTypeOfNode(expr);
2149             break;
2150         case VOIDTOKEN:
2151             expr = context.createVoid(expr);
2152             break;
2153         case DELETETOKEN:
2154             failIfTrueIfStrict(context.isResolve(expr));
2155             expr = context.makeDeleteNode(expr, context.unaryTokenStackLastStart(tokenStackDepth), end, end);
2156             break;
2157         default:
2158             // If we get here something has gone horribly horribly wrong
2159             CRASH();
2160         }
2161         subExprStart = context.unaryTokenStackLastStart(tokenStackDepth);
2162         context.unaryTokenStackRemoveLast(tokenStackDepth);
2163     }
2164     return expr;
2165 }
2166
2167 }
2168
2169 namespace WTF
2170 {
2171     template <> struct VectorTraits<JSC::JSParser::Scope> : SimpleClassVectorTraits {
2172         static const bool canInitializeWithMemset = false; // Not all Scope data members initialize to 0.
2173     };
2174 }