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