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