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