2010-09-15 Oliver Hunt <oliver@apple.com>
[WebKit-https.git] / 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 "JSGlobalData.h"
33 #include "NodeInfo.h"
34 #include "ASTBuilder.h"
35 #include <wtf/HashFunctions.h>
36 #include <wtf/WTFThreadData.h>
37 #include <utility>
38
39 using namespace std;
40
41 namespace JSC {
42 #define fail() do { m_error = true; return 0; } while (0)
43 #define failIfFalse(cond) do { if (!(cond)) fail(); } while (0)
44 #define failIfTrue(cond) do { if ((cond)) fail(); } while (0)
45 #define consumeOrFail(tokenType) do { if (!consume(tokenType)) fail(); } while (0)
46 #define matchOrFail(tokenType) do { if (!match(tokenType)) fail(); } while (0)
47 #define failIfStackOverflow() do { failIfFalse(canRecurse()); } while (0)
48
49 // Macros to make the more common TreeBuilder types a little less verbose
50 #define TreeStatement typename TreeBuilder::Statement
51 #define TreeExpression typename TreeBuilder::Expression
52 #define TreeFormalParameterList typename TreeBuilder::FormalParameterList
53 #define TreeSourceElements typename TreeBuilder::SourceElements
54 #define TreeClause typename TreeBuilder::Clause
55 #define TreeClauseList typename TreeBuilder::ClauseList
56 #define TreeConstDeclList typename TreeBuilder::ConstDeclList
57 #define TreeArguments typename TreeBuilder::Arguments
58 #define TreeArgumentsList typename TreeBuilder::ArgumentsList
59 #define TreeFunctionBody typename TreeBuilder::FunctionBody
60 #define TreeProperty typename TreeBuilder::Property
61 #define TreePropertyList typename TreeBuilder::PropertyList
62
63 COMPILE_ASSERT(LastUntaggedToken < 64, LessThan64UntaggedTokens);
64
65 // This matches v8
66 static const ptrdiff_t kMaxParserStackUsage = 128 * sizeof(void*) * 1024;
67
68 class JSParser {
69 public:
70     JSParser(Lexer*, JSGlobalData*, SourceProvider*);
71     bool parseProgram();
72 private:
73     struct AllowInOverride {
74         AllowInOverride(JSParser* parser)
75             : m_parser(parser)
76             , m_oldAllowsIn(parser->m_allowsIn)
77         {
78             parser->m_allowsIn = true;
79         }
80         ~AllowInOverride()
81         {
82             m_parser->m_allowsIn = m_oldAllowsIn;
83         }
84         JSParser* m_parser;
85         bool m_oldAllowsIn;
86     };
87
88     void next(Lexer::LexType lexType = Lexer::IdentifyReservedWords)
89     {
90         m_lastLine = m_token.m_info.line;
91         m_lastTokenEnd = m_token.m_info.endOffset;
92         m_lexer->setLastLineNumber(m_lastLine);
93         m_token.m_type = m_lexer->lex(&m_token.m_data, &m_token.m_info, lexType);
94         m_tokenCount++;
95     }
96
97     bool consume(JSTokenType expected)
98     {
99         bool result = m_token.m_type == expected;
100         failIfFalse(result);
101         next();
102         return result;
103     }
104
105     bool match(JSTokenType expected)
106     {
107         return m_token.m_type == expected;
108     }
109
110     int tokenStart()
111     {
112         return m_token.m_info.startOffset;
113     }
114
115     int tokenLine()
116     {
117         return m_token.m_info.line;
118     }
119
120     int tokenEnd()
121     {
122         return m_token.m_info.endOffset;
123     }
124
125     template <class TreeBuilder> TreeSourceElements parseSourceElements(TreeBuilder&);
126     template <class TreeBuilder> TreeStatement parseStatement(TreeBuilder&);
127     template <class TreeBuilder> TreeStatement parseFunctionDeclaration(TreeBuilder&);
128     template <class TreeBuilder> TreeStatement parseVarDeclaration(TreeBuilder&);
129     template <class TreeBuilder> TreeStatement parseConstDeclaration(TreeBuilder&);
130     template <class TreeBuilder> TreeStatement parseDoWhileStatement(TreeBuilder&);
131     template <class TreeBuilder> TreeStatement parseWhileStatement(TreeBuilder&);
132     template <class TreeBuilder> TreeStatement parseForStatement(TreeBuilder&);
133     template <class TreeBuilder> TreeStatement parseBreakStatement(TreeBuilder&);
134     template <class TreeBuilder> TreeStatement parseContinueStatement(TreeBuilder&);
135     template <class TreeBuilder> TreeStatement parseReturnStatement(TreeBuilder&);
136     template <class TreeBuilder> TreeStatement parseThrowStatement(TreeBuilder&);
137     template <class TreeBuilder> TreeStatement parseWithStatement(TreeBuilder&);
138     template <class TreeBuilder> TreeStatement parseSwitchStatement(TreeBuilder&);
139     template <class TreeBuilder> TreeClauseList parseSwitchClauses(TreeBuilder&);
140     template <class TreeBuilder> TreeClause parseSwitchDefaultClause(TreeBuilder&);
141     template <class TreeBuilder> TreeStatement parseTryStatement(TreeBuilder&);
142     template <class TreeBuilder> TreeStatement parseDebuggerStatement(TreeBuilder&);
143     template <class TreeBuilder> TreeStatement parseExpressionStatement(TreeBuilder&);
144     template <class TreeBuilder> TreeStatement parseExpressionOrLabelStatement(TreeBuilder&);
145     template <class TreeBuilder> TreeStatement parseIfStatement(TreeBuilder&);
146     template <class TreeBuilder> ALWAYS_INLINE TreeStatement parseBlockStatement(TreeBuilder&);
147     template <class TreeBuilder> TreeExpression parseExpression(TreeBuilder&);
148     template <class TreeBuilder> TreeExpression parseAssignmentExpression(TreeBuilder&);
149     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseConditionalExpression(TreeBuilder&);
150     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseBinaryExpression(TreeBuilder&);
151     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseUnaryExpression(TreeBuilder&);
152     template <class TreeBuilder> TreeExpression parseMemberExpression(TreeBuilder&);
153     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parsePrimaryExpression(TreeBuilder&);
154     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseArrayLiteral(TreeBuilder&);
155     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseObjectLiteral(TreeBuilder&);
156     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseStrictObjectLiteral(TreeBuilder&);
157     template <class TreeBuilder> ALWAYS_INLINE TreeArguments parseArguments(TreeBuilder&);
158     template <bool strict, class TreeBuilder> ALWAYS_INLINE TreeProperty parseProperty(TreeBuilder&);
159     template <class TreeBuilder> ALWAYS_INLINE TreeFunctionBody parseFunctionBody(TreeBuilder&);
160     template <class TreeBuilder> ALWAYS_INLINE TreeFormalParameterList parseFormalParameters(TreeBuilder&, bool& usesArguments);
161     template <class TreeBuilder> ALWAYS_INLINE TreeExpression parseVarDeclarationList(TreeBuilder&, int& declarations, const Identifier*& lastIdent, TreeExpression& lastInitializer, int& identStart, int& initStart, int& initEnd);
162     template <class TreeBuilder> ALWAYS_INLINE TreeConstDeclList parseConstDeclarationList(TreeBuilder& context);
163     enum FunctionRequirements { FunctionNoRequirements, FunctionNeedsName };
164     template <FunctionRequirements, class TreeBuilder> bool parseFunctionInfo(TreeBuilder&, const Identifier*&, TreeFormalParameterList&, TreeFunctionBody&, int& openBrace, int& closeBrace, int& bodyStartLine);
165     ALWAYS_INLINE int isBinaryOperator(JSTokenType token);
166     bool allowAutomaticSemicolon();
167
168     bool autoSemiColon()
169     {
170         if (m_token.m_type == SEMICOLON) {
171             next();
172             return true;
173         }
174         return allowAutomaticSemicolon();
175     }
176
177     bool canRecurse()
178     {
179         char sample = 0;
180         ASSERT(m_endAddress);
181         return &sample > m_endAddress;
182     }
183     
184     int lastTokenEnd() const
185     {
186         return m_lastTokenEnd;
187     }
188
189     ParserArena m_arena;
190     Lexer* m_lexer;
191     char* m_endAddress;
192     bool m_error;
193     JSGlobalData* m_globalData;
194     JSToken m_token;
195     bool m_allowsIn;
196     int m_tokenCount;
197     int m_lastLine;
198     int m_lastTokenEnd;
199     int m_assignmentCount;
200     int m_nonLHSCount;
201     bool m_syntaxAlreadyValidated;
202
203     struct Scope {
204         Scope()
205             : m_usesEval(false)
206         {
207         }
208         
209         void declareVariable(const Identifier* ident)
210         {
211             m_declaredVariables.add(ident->ustring().impl());
212         }
213         
214         void useVariable(const Identifier* ident, bool isEval)
215         {
216             m_usesEval |= isEval;
217             m_usedVariables.add(ident->ustring().impl());
218         }
219         
220         void collectFreeVariables(Scope* nestedScope, bool shouldTrackCapturedVariables)
221         {
222             if (nestedScope->m_usesEval)
223                 m_usesEval = true;
224             IdentifierSet::iterator end = nestedScope->m_usedVariables.end();
225             for (IdentifierSet::iterator ptr = nestedScope->m_usedVariables.begin(); ptr != end; ++ptr) {
226                 if (nestedScope->m_declaredVariables.contains(*ptr))
227                     continue;
228                 m_usedVariables.add(*ptr);
229                 if (shouldTrackCapturedVariables)
230                     m_capturedVariables.add(*ptr);
231             }
232         }
233
234         IdentifierSet& capturedVariables() { return m_capturedVariables; }
235     private:
236         bool m_usesEval;
237         IdentifierSet m_declaredVariables;
238         IdentifierSet m_usedVariables;
239         IdentifierSet m_capturedVariables;
240     };
241     
242     typedef Vector<Scope, 10> ScopeStack;
243
244     struct ScopeRef {
245         ScopeRef(ScopeStack* scopeStack, unsigned index)
246             : m_scopeStack(scopeStack)
247             , m_index(index)
248         {
249         }
250         Scope* operator->() { return &m_scopeStack->at(m_index); }
251         unsigned index() const { return m_index; }
252     private:
253         ScopeStack* m_scopeStack;
254         unsigned m_index;
255     };
256     
257     ScopeRef currentScope()
258     {
259         return ScopeRef(&m_scopeStack, m_scopeStack.size() - 1);
260     }
261     
262     ScopeRef pushScope()
263     {
264         m_scopeStack.append(Scope());
265         return currentScope();
266     }
267
268     void popScope(ScopeRef scope, bool shouldTrackCapturedVariables)
269     {
270         ASSERT_UNUSED(scope, scope.index() == m_scopeStack.size() - 1);
271         ASSERT(m_scopeStack.size() > 1);
272         m_scopeStack[m_scopeStack.size() - 2].collectFreeVariables(&m_scopeStack.last(), shouldTrackCapturedVariables);
273         m_scopeStack.removeLast();
274     }
275
276     ScopeStack m_scopeStack;
277 };
278
279 int jsParse(JSGlobalData* globalData, const SourceCode* source)
280 {
281     JSParser parser(globalData->lexer, globalData, source->provider());
282     return parser.parseProgram();
283 }
284
285 JSParser::JSParser(Lexer* lexer, JSGlobalData* globalData, SourceProvider* provider)
286     : m_lexer(lexer)
287     , m_endAddress(0)
288     , m_error(false)
289     , m_globalData(globalData)
290     , m_allowsIn(true)
291     , m_tokenCount(0)
292     , m_lastLine(0)
293     , m_lastTokenEnd(0)
294     , m_assignmentCount(0)
295     , m_nonLHSCount(0)
296     , m_syntaxAlreadyValidated(provider->isValid())
297 {
298     m_endAddress = wtfThreadData().approximatedStackStart() - kMaxParserStackUsage;
299     next();
300     m_lexer->setLastLineNumber(tokenLine());
301 }
302
303 bool JSParser::parseProgram()
304 {
305     ASTBuilder context(m_globalData, m_lexer);
306     ScopeRef scope = pushScope();
307     SourceElements* sourceElements = parseSourceElements<ASTBuilder>(context);
308     if (!sourceElements || !consume(EOFTOK))
309         return true;
310     m_globalData->parser->didFinishParsing(sourceElements, context.varDeclarations(), context.funcDeclarations(), context.features(),
311                                           m_lastLine, context.numConstants(), scope->capturedVariables());
312     return false;
313 }
314
315 bool JSParser::allowAutomaticSemicolon()
316 {
317     return match(CLOSEBRACE) || match(EOFTOK) || m_lexer->prevTerminator();
318 }
319
320 template <class TreeBuilder> TreeSourceElements JSParser::parseSourceElements(TreeBuilder& context)
321 {
322     TreeSourceElements sourceElements = context.createSourceElements();
323     while (TreeStatement statement = parseStatement(context))
324         context.appendStatement(sourceElements, statement);
325
326     if (m_error)
327         fail();
328     return sourceElements;
329 }
330
331 template <class TreeBuilder> TreeStatement JSParser::parseVarDeclaration(TreeBuilder& context)
332 {
333     ASSERT(match(VAR));
334     int start = tokenLine();
335     int end = 0;
336     int scratch;
337     const Identifier* scratch1 = 0;
338     TreeExpression scratch2 = 0;
339     int scratch3 = 0;
340     TreeExpression varDecls = parseVarDeclarationList(context, scratch, scratch1, scratch2, scratch3, scratch3, scratch3);
341     failIfTrue(m_error);
342     failIfFalse(autoSemiColon());
343
344     return context.createVarStatement(varDecls, start, end);
345 }
346
347 template <class TreeBuilder> TreeStatement JSParser::parseConstDeclaration(TreeBuilder& context)
348 {
349     ASSERT(match(CONSTTOKEN));
350     int start = tokenLine();
351     int end = 0;
352     TreeConstDeclList constDecls = parseConstDeclarationList(context);
353     failIfTrue(m_error);
354     failIfFalse(autoSemiColon());
355     
356     return context.createConstStatement(constDecls, start, end);
357 }
358
359 template <class TreeBuilder> TreeStatement JSParser::parseDoWhileStatement(TreeBuilder& context)
360 {
361     ASSERT(match(DO));
362     int startLine = tokenLine();
363     next();
364     TreeStatement statement = parseStatement(context);
365     failIfFalse(statement);
366     int endLine = tokenLine();
367     consumeOrFail(WHILE);
368     consumeOrFail(OPENPAREN);
369     TreeExpression expr = parseExpression(context);
370     failIfFalse(expr);
371     consumeOrFail(CLOSEPAREN);
372     if (match(SEMICOLON))
373         next(); // Always performs automatic semicolon insertion.
374     return context.createDoWhileStatement(statement, expr, startLine, endLine);
375 }
376
377 template <class TreeBuilder> TreeStatement JSParser::parseWhileStatement(TreeBuilder& context)
378 {
379     ASSERT(match(WHILE));
380     int startLine = tokenLine();
381     next();
382     consumeOrFail(OPENPAREN);
383     TreeExpression expr = parseExpression(context);
384     failIfFalse(expr);
385     int endLine = tokenLine();
386     consumeOrFail(CLOSEPAREN);
387     TreeStatement statement = parseStatement(context);
388     failIfFalse(statement);
389     return context.createWhileStatement(expr, statement, startLine, endLine);
390 }
391
392 template <class TreeBuilder> TreeExpression JSParser::parseVarDeclarationList(TreeBuilder& context, int& declarations, const Identifier*& lastIdent, TreeExpression& lastInitializer, int& identStart, int& initStart, int& initEnd)
393 {
394     TreeExpression varDecls = 0;
395     do {
396         declarations++;
397         next();
398         matchOrFail(IDENT);
399
400         int varStart = tokenStart();
401         identStart = varStart;
402         const Identifier* name = m_token.m_data.ident;
403         lastIdent = name;
404         next();
405         bool hasInitializer = match(EQUAL);
406         currentScope()->declareVariable(name);
407         context.addVar(name, (hasInitializer || (!m_allowsIn && match(INTOKEN))) ? DeclarationStacks::HasInitializer : 0);
408         if (hasInitializer) {
409             int varDivot = tokenStart() + 1;
410             initStart = tokenStart();
411             next(); // consume '='
412             int initialAssignments = m_assignmentCount;
413             TreeExpression initializer = parseAssignmentExpression(context);
414             initEnd = lastTokenEnd();
415             lastInitializer = initializer;
416             failIfFalse(initializer);
417
418             TreeExpression node = context.createAssignResolve(*name, initializer, initialAssignments != m_assignmentCount, varStart, varDivot, lastTokenEnd());
419             if (!varDecls)
420                 varDecls = node;
421             else
422                 varDecls = context.combineCommaNodes(varDecls, node);
423         }
424     } while (match(COMMA));
425     return varDecls;
426 }
427
428 template <class TreeBuilder> TreeConstDeclList JSParser::parseConstDeclarationList(TreeBuilder& context)
429 {
430     TreeConstDeclList constDecls = 0;
431     TreeConstDeclList tail = 0;
432     do {
433         next();
434         matchOrFail(IDENT);
435         const Identifier* name = m_token.m_data.ident;
436         next();
437         bool hasInitializer = match(EQUAL);
438         currentScope()->declareVariable(name);
439         context.addVar(name, DeclarationStacks::IsConstant | (hasInitializer ? DeclarationStacks::HasInitializer : 0));
440         TreeExpression initializer = 0;
441         if (hasInitializer) {
442             next(); // consume '='
443             initializer = parseAssignmentExpression(context);
444         }
445         tail = context.appendConstDecl(tail, name, initializer);
446         if (!constDecls)
447             constDecls = tail;
448     } while (match(COMMA));
449     return constDecls;
450 }
451
452 template <class TreeBuilder> TreeStatement JSParser::parseForStatement(TreeBuilder& context)
453 {
454     ASSERT(match(FOR));
455     int startLine = tokenLine();
456     next();
457     consumeOrFail(OPENPAREN);
458     int nonLHSCount = m_nonLHSCount;
459     int declarations = 0;
460     int declsStart = 0;
461     int declsEnd = 0;
462     TreeExpression decls = 0;
463     bool hasDeclaration = false;
464     if (match(VAR)) {
465         /*
466          for (var IDENT in expression) statement
467          for (var IDENT = expression in expression) statement
468          for (var varDeclarationList; expressionOpt; expressionOpt)
469          */
470         hasDeclaration = true;
471         const Identifier* forInTarget = 0;
472         TreeExpression forInInitializer = 0;
473         m_allowsIn = false;
474         int initStart = 0;
475         int initEnd = 0;
476         decls = parseVarDeclarationList(context, declarations, forInTarget, forInInitializer, declsStart, initStart, initEnd);
477         m_allowsIn = true;
478         if (m_error)
479             fail();
480
481         // Remainder of a standard for loop is handled identically
482         if (declarations > 1 || match(SEMICOLON))
483             goto standardForLoop;
484
485         // Handle for-in with var declaration
486         int inLocation = tokenStart();
487         if (!consume(INTOKEN))
488             fail();
489
490         TreeExpression expr = parseExpression(context);
491         failIfFalse(expr);
492         int exprEnd = lastTokenEnd();
493
494         int endLine = tokenLine();
495         consumeOrFail(CLOSEPAREN);
496
497         TreeStatement statement = parseStatement(context);
498         failIfFalse(statement);
499
500         return context.createForInLoop(forInTarget, forInInitializer, expr, statement, declsStart, inLocation, exprEnd, initStart, initEnd, startLine, endLine);
501     }
502
503     if (!match(SEMICOLON)) {
504         m_allowsIn = false;
505         declsStart = tokenStart();
506         decls = parseExpression(context);
507         declsEnd = lastTokenEnd();
508         m_allowsIn = true;
509         failIfFalse(decls);
510     }
511
512     if (match(SEMICOLON)) {
513     standardForLoop:
514         // Standard for loop
515         next();
516         TreeExpression condition = 0;
517
518         if (!match(SEMICOLON)) {
519             condition = parseExpression(context);
520             failIfFalse(condition);
521         }
522         consumeOrFail(SEMICOLON);
523
524         TreeExpression increment = 0;
525         if (!match(CLOSEPAREN)) {
526             increment = parseExpression(context);
527             failIfFalse(increment);
528         }
529         int endLine = tokenLine();
530         consumeOrFail(CLOSEPAREN);
531         TreeStatement statement = parseStatement(context);
532         failIfFalse(statement);
533         return context.createForLoop(decls, condition, increment, statement, hasDeclaration, startLine, endLine);
534     }
535
536     // For-in loop
537     failIfFalse(nonLHSCount == m_nonLHSCount);
538     consumeOrFail(INTOKEN);
539     TreeExpression expr = parseExpression(context);
540     failIfFalse(expr);
541     int exprEnd = lastTokenEnd();
542     int endLine = tokenLine();
543     consumeOrFail(CLOSEPAREN);
544     TreeStatement statement = parseStatement(context);
545     failIfFalse(statement);
546     
547     return context.createForInLoop(decls, expr, statement, declsStart, declsEnd, exprEnd, startLine, endLine);
548 }
549
550 template <class TreeBuilder> TreeStatement JSParser::parseBreakStatement(TreeBuilder& context)
551 {
552     ASSERT(match(BREAK));
553     int startCol = tokenStart();
554     int endCol = tokenEnd();
555     int startLine = tokenLine();
556     int endLine = tokenLine();
557     next();
558
559     if (autoSemiColon())
560         return context.createBreakStatement(startCol, endCol, startLine, endLine);
561     matchOrFail(IDENT);
562     const Identifier* ident = m_token.m_data.ident;
563     endCol = tokenEnd();
564     endLine = tokenLine();
565     next();
566     failIfFalse(autoSemiColon());
567     return context.createBreakStatement(ident, startCol, endCol, startLine, endLine);
568 }
569
570 template <class TreeBuilder> TreeStatement JSParser::parseContinueStatement(TreeBuilder& context)
571 {
572     ASSERT(match(CONTINUE));
573     int startCol = tokenStart();
574     int endCol = tokenEnd();
575     int startLine = tokenLine();
576     int endLine = tokenLine();
577     next();
578
579     if (autoSemiColon())
580         return context.createContinueStatement(startCol, endCol, startLine, endLine);
581     matchOrFail(IDENT);
582     const Identifier* ident = m_token.m_data.ident;
583     endCol = tokenEnd();
584     endLine = tokenLine();
585     next();
586     failIfFalse(autoSemiColon());
587     return context.createContinueStatement(ident, startCol, endCol, startLine, endLine);
588 }
589
590 template <class TreeBuilder> TreeStatement JSParser::parseReturnStatement(TreeBuilder& context)
591 {
592     ASSERT(match(RETURN));
593     int startLine = tokenLine();
594     int endLine = startLine;
595     int start = tokenStart();
596     int end = tokenEnd();
597     next();
598     // We do the auto semicolon check before attempting to parse an expression
599     // as we need to ensure the a line break after the return correctly terminates
600     // the statement
601     if (match(SEMICOLON))
602         endLine  = tokenLine();
603     if (autoSemiColon())
604         return context.createReturnStatement(0, start, end, startLine, endLine);
605     TreeExpression expr = parseExpression(context);
606     failIfFalse(expr);
607     end = lastTokenEnd();
608     if (match(SEMICOLON))
609         endLine  = tokenLine();
610     failIfFalse(autoSemiColon());
611     return context.createReturnStatement(expr, start, end, startLine, endLine);
612 }
613
614 template <class TreeBuilder> TreeStatement JSParser::parseThrowStatement(TreeBuilder& context)
615 {
616     ASSERT(match(THROW));
617     int eStart = tokenStart();
618     int startLine = tokenLine();
619     next();
620
621     TreeExpression expr = parseExpression(context);
622     failIfFalse(expr);
623     int eEnd = lastTokenEnd();
624     int endLine = tokenLine();
625     failIfFalse(autoSemiColon());
626
627     return context.createThrowStatement(expr, eStart, eEnd, startLine, endLine);
628 }
629
630 template <class TreeBuilder> TreeStatement JSParser::parseWithStatement(TreeBuilder& context)
631 {
632     ASSERT(match(WITH));
633     int startLine = tokenLine();
634     next();
635     consumeOrFail(OPENPAREN);
636     int start = tokenStart();
637     TreeExpression expr = parseExpression(context);
638     failIfFalse(expr);
639     int end = lastTokenEnd();
640
641     int endLine = tokenLine();
642     consumeOrFail(CLOSEPAREN);
643     
644     TreeStatement statement = parseStatement(context);
645     failIfFalse(statement);
646
647     return context.createWithStatement(expr, statement, start, end, startLine, endLine);
648 }
649
650 template <class TreeBuilder> TreeStatement JSParser::parseSwitchStatement(TreeBuilder& context)
651 {
652     ASSERT(match(SWITCH));
653     int startLine = tokenLine();
654     next();
655     consumeOrFail(OPENPAREN);
656     TreeExpression expr = parseExpression(context);
657     failIfFalse(expr);
658     int endLine = tokenLine();
659     consumeOrFail(CLOSEPAREN);
660     consumeOrFail(OPENBRACE);
661
662     TreeClauseList firstClauses = parseSwitchClauses(context);
663     failIfTrue(m_error);
664
665     TreeClause defaultClause = parseSwitchDefaultClause(context);
666     failIfTrue(m_error);
667
668     TreeClauseList secondClauses = parseSwitchClauses(context);
669     failIfTrue(m_error);
670     consumeOrFail(CLOSEBRACE);
671
672     return context.createSwitchStatement(expr, firstClauses, defaultClause, secondClauses, startLine, endLine);
673
674 }
675
676 template <class TreeBuilder> TreeClauseList JSParser::parseSwitchClauses(TreeBuilder& context)
677 {
678     if (!match(CASE))
679         return 0;
680     next();
681     TreeExpression condition = parseExpression(context);
682     failIfFalse(condition);
683     consumeOrFail(COLON);
684     TreeSourceElements statements = parseSourceElements(context);
685     failIfFalse(statements);
686     TreeClause clause = context.createClause(condition, statements);
687     TreeClauseList clauseList = context.createClauseList(clause);
688     TreeClauseList tail = clauseList;
689
690     while (match(CASE)) {
691         next();
692         TreeExpression condition = parseExpression(context);
693         failIfFalse(condition);
694         consumeOrFail(COLON);
695         TreeSourceElements statements = parseSourceElements(context);
696         failIfFalse(statements);
697         clause = context.createClause(condition, statements);
698         tail = context.createClauseList(tail, clause);
699     }
700     return clauseList;
701 }
702
703 template <class TreeBuilder> TreeClause JSParser::parseSwitchDefaultClause(TreeBuilder& context)
704 {
705     if (!match(DEFAULT))
706         return 0;
707     next();
708     consumeOrFail(COLON);
709     TreeSourceElements statements = parseSourceElements(context);
710     failIfFalse(statements);
711     return context.createClause(0, statements);
712 }
713
714 template <class TreeBuilder> TreeStatement JSParser::parseTryStatement(TreeBuilder& context)
715 {
716     ASSERT(match(TRY));
717     TreeStatement tryBlock = 0;
718     const Identifier* ident = &m_globalData->propertyNames->nullIdentifier;
719     bool catchHasEval = false;
720     TreeStatement catchBlock = 0;
721     TreeStatement finallyBlock = 0;
722     int firstLine = tokenLine();
723     next();
724     matchOrFail(OPENBRACE);
725
726     tryBlock = parseBlockStatement(context);
727     failIfFalse(tryBlock);
728     int lastLine = m_lastLine;
729
730     if (match(CATCH)) {
731         next();
732         consumeOrFail(OPENPAREN);
733         matchOrFail(IDENT);
734         ident = m_token.m_data.ident;
735         next();
736         ScopeRef catchScope = pushScope();
737         catchScope->declareVariable(ident);
738         consumeOrFail(CLOSEPAREN);
739         matchOrFail(OPENBRACE);
740         int initialEvalCount = context.evalCount();
741         catchBlock = parseBlockStatement(context);
742         failIfFalse(catchBlock);
743         catchHasEval = initialEvalCount != context.evalCount();
744         popScope(catchScope, TreeBuilder::NeedsFreeVariableInfo);
745     }
746
747     if (match(FINALLY)) {
748         next();
749         matchOrFail(OPENBRACE);
750         finallyBlock = parseBlockStatement(context);
751         failIfFalse(finallyBlock);
752     }
753     failIfFalse(catchBlock || finallyBlock);
754     return context.createTryStatement(tryBlock, ident, catchHasEval, catchBlock, finallyBlock, firstLine, lastLine);
755 }
756
757 template <class TreeBuilder> TreeStatement JSParser::parseDebuggerStatement(TreeBuilder& context)
758 {
759     ASSERT(match(DEBUGGER));
760     int startLine = tokenLine();
761     int endLine = startLine;
762     next();
763     if (match(SEMICOLON))
764         startLine = tokenLine();
765     failIfFalse(autoSemiColon());
766     return context.createDebugger(startLine, endLine);
767 }
768
769 template <class TreeBuilder> TreeStatement JSParser::parseBlockStatement(TreeBuilder& context)
770 {
771     ASSERT(match(OPENBRACE));
772     int start = tokenLine();
773     next();
774     if (match(CLOSEBRACE)) {
775         next();
776         return context.createBlockStatement(0, start, m_lastLine);
777     }
778     TreeSourceElements subtree = parseSourceElements(context);
779     failIfFalse(subtree);
780     matchOrFail(CLOSEBRACE);
781     next();
782     return context.createBlockStatement(subtree, start, m_lastLine);
783 }
784
785 template <class TreeBuilder> TreeStatement JSParser::parseStatement(TreeBuilder& context)
786 {
787     failIfStackOverflow();
788     switch (m_token.m_type) {
789     case OPENBRACE:
790         return parseBlockStatement(context);
791     case VAR:
792         return parseVarDeclaration(context);
793     case CONSTTOKEN:
794         return parseConstDeclaration(context);
795     case FUNCTION:
796         return parseFunctionDeclaration(context);
797     case SEMICOLON:
798         next();
799         return context.createEmptyStatement();
800     case IF:
801         return parseIfStatement(context);
802     case DO:
803         return parseDoWhileStatement(context);
804     case WHILE:
805         return parseWhileStatement(context);
806     case FOR:
807         return parseForStatement(context);
808     case CONTINUE:
809         return parseContinueStatement(context);
810     case BREAK:
811         return parseBreakStatement(context);
812     case RETURN:
813         return parseReturnStatement(context);
814     case WITH:
815         return parseWithStatement(context);
816     case SWITCH:
817         return parseSwitchStatement(context);
818     case THROW:
819         return parseThrowStatement(context);
820     case TRY:
821         return parseTryStatement(context);
822     case DEBUGGER:
823         return parseDebuggerStatement(context);
824     case EOFTOK:
825     case CASE:
826     case CLOSEBRACE:
827     case DEFAULT:
828         // These tokens imply the end of a set of source elements
829         return 0;
830     case IDENT:
831         return parseExpressionOrLabelStatement(context);
832     default:
833         return parseExpressionStatement(context);
834     }
835 }
836
837 template <class TreeBuilder> TreeFormalParameterList JSParser::parseFormalParameters(TreeBuilder& context, bool& usesArguments)
838 {
839     matchOrFail(IDENT);
840     usesArguments = m_globalData->propertyNames->arguments == *m_token.m_data.ident;
841     currentScope()->declareVariable(m_token.m_data.ident);
842     TreeFormalParameterList list = context.createFormalParameterList(*m_token.m_data.ident);
843     TreeFormalParameterList tail = list;
844     next();
845     while (match(COMMA)) {
846         next();
847         matchOrFail(IDENT);
848         const Identifier* ident = m_token.m_data.ident;
849         currentScope()->declareVariable(ident);
850         next();
851         usesArguments = usesArguments || m_globalData->propertyNames->arguments == *ident;
852         tail = context.createFormalParameterList(tail, *ident);
853     }
854     return list;
855 }
856
857 template <class TreeBuilder> TreeFunctionBody JSParser::parseFunctionBody(TreeBuilder& context)
858 {
859     if (match(CLOSEBRACE))
860         return context.createFunctionBody();
861     typename TreeBuilder::FunctionBodyBuilder bodyBuilder(m_globalData, m_lexer);
862     failIfFalse(parseSourceElements(bodyBuilder));
863     return context.createFunctionBody();
864 }
865
866 template <JSParser::FunctionRequirements requirements, class TreeBuilder> bool JSParser::parseFunctionInfo(TreeBuilder& context, const Identifier*& name, TreeFormalParameterList& parameters, TreeFunctionBody& body, int& openBracePos, int& closeBracePos, int& bodyStartLine)
867 {
868     ScopeRef functionScope = pushScope();
869     if (match(IDENT)) {
870         name = m_token.m_data.ident;
871         next();
872         functionScope->declareVariable(name);
873     } else if (requirements == FunctionNeedsName)
874         return false;
875     consumeOrFail(OPENPAREN);
876     bool usesArguments = false;
877     if (!match(CLOSEPAREN)) {
878         parameters = parseFormalParameters(context, usesArguments);
879         failIfFalse(parameters);
880     }
881     consumeOrFail(CLOSEPAREN);
882     matchOrFail(OPENBRACE);
883
884     openBracePos = m_token.m_data.intValue;
885     bodyStartLine = tokenLine();
886     next();
887
888     body = parseFunctionBody(context);
889     failIfFalse(body);
890     if (usesArguments)
891         context.setUsesArguments(body);
892     popScope(functionScope, TreeBuilder::NeedsFreeVariableInfo);
893     matchOrFail(CLOSEBRACE);
894     closeBracePos = m_token.m_data.intValue;
895     next();
896     return true;
897 }
898
899 template <class TreeBuilder> TreeStatement JSParser::parseFunctionDeclaration(TreeBuilder& context)
900 {
901     ASSERT(match(FUNCTION));
902     next();
903     const Identifier* name = 0;
904     TreeFormalParameterList parameters = 0;
905     TreeFunctionBody body = 0;
906     int openBracePos = 0;
907     int closeBracePos = 0;
908     int bodyStartLine = 0;
909     failIfFalse(parseFunctionInfo<FunctionNeedsName>(context, name, parameters, body, openBracePos, closeBracePos, bodyStartLine));
910     failIfFalse(name);
911     currentScope()->declareVariable(name);
912     return context.createFuncDeclStatement(name, body, parameters, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
913 }
914
915 template <class TreeBuilder> TreeStatement JSParser::parseExpressionOrLabelStatement(TreeBuilder& context)
916 {
917
918     /* Expression and Label statements are ambiguous at LL(1), to avoid
919      * the cost of having a token buffer to support LL(2) we simply assume
920      * we have an expression statement, and then only look for a label if that
921      * parse fails.
922      */
923     int start = tokenStart();
924     int startLine = tokenLine();
925     const Identifier* ident = m_token.m_data.ident;
926     int currentToken = m_tokenCount;
927     TreeExpression expression = parseExpression(context);
928     failIfFalse(expression);
929     if (autoSemiColon())
930         return context.createExprStatement(expression, startLine, m_lastLine);
931     failIfFalse(currentToken + 1 == m_tokenCount);
932     int end = tokenEnd();
933     consumeOrFail(COLON);
934     TreeStatement statement = parseStatement(context);
935     failIfFalse(statement);
936     return context.createLabelStatement(ident, statement, start, end);
937 }
938
939 template <class TreeBuilder> TreeStatement JSParser::parseExpressionStatement(TreeBuilder& context)
940 {
941     int startLine = tokenLine();
942     TreeExpression expression = parseExpression(context);
943     failIfFalse(expression);
944     failIfFalse(autoSemiColon());
945     return context.createExprStatement(expression, startLine, m_lastLine);
946 }
947
948 template <class TreeBuilder> TreeStatement JSParser::parseIfStatement(TreeBuilder& context)
949 {
950     ASSERT(match(IF));
951
952     int start = tokenLine();
953     next();
954
955     consumeOrFail(OPENPAREN);
956
957     TreeExpression condition = parseExpression(context);
958     failIfFalse(condition);
959     int end = tokenLine();
960     consumeOrFail(CLOSEPAREN);
961
962     TreeStatement trueBlock = parseStatement(context);
963     failIfFalse(trueBlock);
964
965     if (!match(ELSE))
966         return context.createIfStatement(condition, trueBlock, start, end);
967     
968     Vector<TreeExpression> exprStack;
969     Vector<pair<int, int> > posStack;
970     Vector<TreeStatement> statementStack;
971     bool trailingElse = false;
972     do {
973         next();
974         if (!match(IF)) {
975             TreeStatement block = parseStatement(context);
976             failIfFalse(block);
977             statementStack.append(block);
978             trailingElse = true;
979             break;
980         }
981         int innerStart = tokenLine();
982         next();
983         
984         consumeOrFail(OPENPAREN);
985         
986         TreeExpression innerCondition = parseExpression(context);
987         failIfFalse(innerCondition);
988         int innerEnd = tokenLine();
989         consumeOrFail(CLOSEPAREN);
990         
991         TreeStatement innerTrueBlock = parseStatement(context);
992         failIfFalse(innerTrueBlock);     
993         exprStack.append(innerCondition);
994         posStack.append(make_pair(innerStart, innerEnd));
995         statementStack.append(innerTrueBlock);
996     } while (match(ELSE));
997
998     if (!trailingElse) {
999         TreeExpression condition = exprStack.last();
1000         exprStack.removeLast();
1001         TreeStatement trueBlock = statementStack.last();
1002         statementStack.removeLast();
1003         pair<int, int> pos = posStack.last();
1004         posStack.removeLast();
1005         statementStack.append(context.createIfStatement(condition, trueBlock, pos.first, pos.second));
1006     }
1007
1008     while (!exprStack.isEmpty()) {
1009         TreeExpression condition = exprStack.last();
1010         exprStack.removeLast();
1011         TreeStatement falseBlock = statementStack.last();
1012         statementStack.removeLast();
1013         TreeStatement trueBlock = statementStack.last();
1014         statementStack.removeLast();
1015         pair<int, int> pos = posStack.last();
1016         posStack.removeLast();
1017         statementStack.append(context.createIfStatement(condition, trueBlock, falseBlock, pos.first, pos.second));
1018     }
1019     
1020     return context.createIfStatement(condition, trueBlock, statementStack.last(), start, end);
1021 }
1022
1023 template <class TreeBuilder> TreeExpression JSParser::parseExpression(TreeBuilder& context)
1024 {
1025     failIfStackOverflow();
1026     TreeExpression node = parseAssignmentExpression(context);
1027     failIfFalse(node);
1028     if (!match(COMMA))
1029         return node;
1030     next();
1031     m_nonLHSCount++;
1032     TreeExpression right = parseAssignmentExpression(context);
1033     failIfFalse(right);
1034     typename TreeBuilder::Comma commaNode = context.createCommaExpr(node, right);
1035     while (match(COMMA)) {
1036         next();
1037         right = parseAssignmentExpression(context);
1038         failIfFalse(right);
1039         context.appendToComma(commaNode, right);
1040     }
1041     return commaNode;
1042 }
1043
1044
1045 template <typename TreeBuilder> TreeExpression JSParser::parseAssignmentExpression(TreeBuilder& context)
1046 {
1047     failIfStackOverflow();
1048     int start = tokenStart();
1049     int initialAssignmentCount = m_assignmentCount;
1050     int initialNonLHSCount = m_nonLHSCount;
1051     TreeExpression lhs = parseConditionalExpression(context);
1052     failIfFalse(lhs);
1053     if (initialNonLHSCount != m_nonLHSCount)
1054         return lhs;
1055
1056     int assignmentStack = 0;
1057     Operator op;
1058     bool hadAssignment = false;
1059     while (true) {
1060         switch (m_token.m_type) {
1061         case EQUAL: op = OpEqual; break;
1062         case PLUSEQUAL: op = OpPlusEq; break;
1063         case MINUSEQUAL: op = OpMinusEq; break;
1064         case MULTEQUAL: op = OpMultEq; break;
1065         case DIVEQUAL: op = OpDivEq; break;
1066         case LSHIFTEQUAL: op = OpLShift; break;
1067         case RSHIFTEQUAL: op = OpRShift; break;
1068         case URSHIFTEQUAL: op = OpURShift; break;
1069         case ANDEQUAL: op = OpAndEq; break;
1070         case XOREQUAL: op = OpXOrEq; break;
1071         case OREQUAL: op = OpOrEq; break;
1072         case MODEQUAL: op = OpModEq; break;
1073         default:
1074             goto end;
1075         }
1076         hadAssignment = true;
1077         context.assignmentStackAppend(assignmentStack, lhs, start, tokenStart(), m_assignmentCount, op);
1078         start = tokenStart();
1079         m_assignmentCount++;
1080         next();
1081         lhs = parseConditionalExpression(context);
1082         failIfFalse(lhs);
1083         if (initialNonLHSCount != m_nonLHSCount)
1084             break;
1085     }
1086 end:
1087     if (hadAssignment)
1088         m_nonLHSCount++;
1089
1090     if (!ASTBuilder::CreatesAST)
1091         return lhs;
1092
1093     while (assignmentStack)
1094         lhs = context.createAssignment(assignmentStack, lhs, initialAssignmentCount, m_assignmentCount, lastTokenEnd());
1095
1096     return lhs;
1097 }
1098
1099 template <class TreeBuilder> TreeExpression JSParser::parseConditionalExpression(TreeBuilder& context)
1100 {
1101     TreeExpression cond = parseBinaryExpression(context);
1102     failIfFalse(cond);
1103     if (!match(QUESTION))
1104         return cond;
1105     m_nonLHSCount++;
1106     next();
1107     TreeExpression lhs = parseAssignmentExpression(context);
1108     consumeOrFail(COLON);
1109
1110     TreeExpression rhs = parseAssignmentExpression(context);
1111     failIfFalse(rhs);
1112     return context.createConditionalExpr(cond, lhs, rhs);
1113 }
1114
1115 ALWAYS_INLINE static bool isUnaryOp(JSTokenType token)
1116 {
1117     return token & UnaryOpTokenFlag;
1118 }
1119
1120 int JSParser::isBinaryOperator(JSTokenType token)
1121 {
1122     if (m_allowsIn)
1123         return token & (BinaryOpTokenPrecedenceMask << BinaryOpTokenAllowsInPrecedenceAdditionalShift);
1124     return token & BinaryOpTokenPrecedenceMask;
1125 }
1126
1127 template <class TreeBuilder> TreeExpression JSParser::parseBinaryExpression(TreeBuilder& context)
1128 {
1129
1130     int operandStackDepth = 0;
1131     int operatorStackDepth = 0;
1132     while (true) {
1133         int exprStart = tokenStart();
1134         int initialAssignments = m_assignmentCount;
1135         TreeExpression current = parseUnaryExpression(context);
1136         failIfFalse(current);
1137
1138         context.appendBinaryExpressionInfo(operandStackDepth, current, exprStart, lastTokenEnd(), lastTokenEnd(), initialAssignments != m_assignmentCount);
1139         int precedence = isBinaryOperator(m_token.m_type);
1140         if (!precedence)
1141             break;
1142         m_nonLHSCount++;
1143         int operatorToken = m_token.m_type;
1144         next();
1145
1146         while (operatorStackDepth &&  context.operatorStackHasHigherPrecedence(operatorStackDepth, precedence)) {
1147             ASSERT(operandStackDepth > 1);
1148
1149             typename TreeBuilder::BinaryOperand rhs = context.getFromOperandStack(-1);
1150             typename TreeBuilder::BinaryOperand lhs = context.getFromOperandStack(-2);
1151             context.shrinkOperandStackBy(operandStackDepth, 2);
1152             context.appendBinaryOperation(operandStackDepth, operatorStackDepth, lhs, rhs);
1153             context.operatorStackPop(operatorStackDepth);
1154         }
1155         context.operatorStackAppend(operatorStackDepth, operatorToken, precedence);
1156     }
1157
1158     while (operatorStackDepth) {
1159         ASSERT(operandStackDepth > 1);
1160
1161         typename TreeBuilder::BinaryOperand rhs = context.getFromOperandStack(-1);
1162         typename TreeBuilder::BinaryOperand lhs = context.getFromOperandStack(-2);
1163         context.shrinkOperandStackBy(operandStackDepth, 2);
1164         context.appendBinaryOperation(operandStackDepth, operatorStackDepth, lhs, rhs);
1165         context.operatorStackPop(operatorStackDepth);
1166     }
1167     return context.popOperandStack(operandStackDepth);
1168 }
1169
1170
1171 template <bool complete, class TreeBuilder> TreeProperty JSParser::parseProperty(TreeBuilder& context)
1172 {
1173     bool wasIdent = false;
1174     switch (m_token.m_type) {
1175     namedProperty:
1176     case IDENT:
1177         wasIdent = true;
1178     case STRING: {
1179         const Identifier* ident = m_token.m_data.ident;
1180         next(Lexer::IgnoreReservedWords);
1181         if (match(COLON)) {
1182             next();
1183             TreeExpression node = parseAssignmentExpression(context);
1184             failIfFalse(node);
1185             return context.template createProperty<complete>(ident, node, PropertyNode::Constant);
1186         }
1187         failIfFalse(wasIdent);
1188         matchOrFail(IDENT);
1189         const Identifier* accessorName = 0;
1190         TreeFormalParameterList parameters = 0;
1191         TreeFunctionBody body = 0;
1192         int openBracePos = 0;
1193         int closeBracePos = 0;
1194         int bodyStartLine = 0;
1195         PropertyNode::Type type;
1196         if (*ident == m_globalData->propertyNames->get)
1197             type = PropertyNode::Getter;
1198         else if (*ident == m_globalData->propertyNames->set)
1199             type = PropertyNode::Setter;
1200         else
1201             fail();
1202         failIfFalse(parseFunctionInfo<FunctionNeedsName>(context, accessorName, parameters, body, openBracePos, closeBracePos, bodyStartLine));
1203         return context.template createGetterOrSetterProperty<complete>(type, accessorName, parameters, body, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
1204     }
1205     case NUMBER: {
1206         double propertyName = m_token.m_data.doubleValue;
1207         next();
1208         consumeOrFail(COLON);
1209         TreeExpression node = parseAssignmentExpression(context);
1210         failIfFalse(node);
1211         return context.template createProperty<complete>(m_globalData, propertyName, node, PropertyNode::Constant);
1212     }
1213     default:
1214         failIfFalse(m_token.m_type & KeywordTokenFlag);
1215         goto namedProperty;
1216     }
1217 }
1218
1219 template <class TreeBuilder> TreeExpression JSParser::parseObjectLiteral(TreeBuilder& context)
1220 {
1221     int startOffset = m_token.m_data.intValue;
1222     consumeOrFail(OPENBRACE);
1223
1224     if (match(CLOSEBRACE)) {
1225         next();
1226         return context.createObjectLiteral();
1227     }
1228
1229     TreeProperty property = parseProperty<false>(context);
1230     failIfFalse(property);
1231     if (!m_syntaxAlreadyValidated && context.getType(property) != PropertyNode::Constant) {
1232         m_lexer->setOffset(startOffset);
1233         next();
1234         return parseStrictObjectLiteral(context);
1235     }
1236     TreePropertyList propertyList = context.createPropertyList(property);
1237     TreePropertyList tail = propertyList;
1238     while (match(COMMA)) {
1239         next();
1240         // allow extra comma, see http://bugs.webkit.org/show_bug.cgi?id=5939
1241         if (match(CLOSEBRACE))
1242             break;
1243         property = parseProperty<false>(context);
1244         failIfFalse(property);
1245         if (!m_syntaxAlreadyValidated && context.getType(property) != PropertyNode::Constant) {
1246             m_lexer->setOffset(startOffset);
1247             next();
1248             return parseStrictObjectLiteral(context);
1249         }
1250         tail = context.createPropertyList(property, tail);
1251     }
1252
1253     consumeOrFail(CLOSEBRACE);
1254
1255     return context.createObjectLiteral(propertyList);
1256 }
1257
1258 template <class TreeBuilder> TreeExpression JSParser::parseStrictObjectLiteral(TreeBuilder& context)
1259 {
1260     consumeOrFail(OPENBRACE);
1261     
1262     if (match(CLOSEBRACE)) {
1263         next();
1264         return context.createObjectLiteral();
1265     }
1266     
1267     TreeProperty property = parseProperty<true>(context);
1268     failIfFalse(property);
1269     
1270     typedef HashMap<RefPtr<StringImpl>, unsigned, IdentifierRepHash> ObjectValidationMap;
1271     ObjectValidationMap objectValidator;
1272     // Add the first property
1273     if (!m_syntaxAlreadyValidated)
1274         objectValidator.add(context.getName(property).impl(), context.getType(property));
1275     
1276     TreePropertyList propertyList = context.createPropertyList(property);
1277     TreePropertyList tail = propertyList;
1278     while (match(COMMA)) {
1279         next();
1280         // allow extra comma, see http://bugs.webkit.org/show_bug.cgi?id=5939
1281         if (match(CLOSEBRACE))
1282             break;
1283         property = parseProperty<true>(context);
1284         failIfFalse(property);
1285         if (!m_syntaxAlreadyValidated) {
1286             std::pair<ObjectValidationMap::iterator, bool> propertyEntryIter = objectValidator.add(context.getName(property).impl(), context.getType(property));
1287             if (!propertyEntryIter.second) {
1288                 if ((context.getType(property) & propertyEntryIter.first->second) != PropertyNode::Constant) {
1289                     // Can't have multiple getters or setters with the same name, nor can we define 
1290                     // a property as both an accessor and a constant value
1291                     failIfTrue(context.getType(property) & propertyEntryIter.first->second);
1292                     failIfTrue((context.getType(property) | propertyEntryIter.first->second) & PropertyNode::Constant);
1293                 }
1294             }
1295         }
1296         tail = context.createPropertyList(property, tail);
1297     }
1298     
1299     consumeOrFail(CLOSEBRACE);
1300     
1301     return context.createObjectLiteral(propertyList);
1302 }
1303
1304 template <class TreeBuilder> TreeExpression JSParser::parseArrayLiteral(TreeBuilder& context)
1305 {
1306     consumeOrFail(OPENBRACKET);
1307
1308     int elisions = 0;
1309     while (match(COMMA)) {
1310         next();
1311         elisions++;
1312     }
1313     if (match(CLOSEBRACKET)) {
1314         next();
1315         return context.createArray(elisions);
1316     }
1317
1318     TreeExpression elem = parseAssignmentExpression(context);
1319     failIfFalse(elem);
1320     typename TreeBuilder::ElementList elementList = context.createElementList(elisions, elem);
1321     typename TreeBuilder::ElementList tail = elementList;
1322     elisions = 0;
1323     while (match(COMMA)) {
1324         next();
1325         elisions = 0;
1326
1327         while (match(COMMA)) {
1328             next();
1329             elisions++;
1330         }
1331
1332         if (match(CLOSEBRACKET)) {
1333             next();
1334             return context.createArray(elisions, elementList);
1335         }
1336         TreeExpression elem = parseAssignmentExpression(context);
1337         failIfFalse(elem);
1338         tail = context.createElementList(tail, elisions, elem);
1339     }
1340
1341     consumeOrFail(CLOSEBRACKET);
1342
1343     return context.createArray(elementList);
1344 }
1345
1346 template <class TreeBuilder> TreeExpression JSParser::parsePrimaryExpression(TreeBuilder& context)
1347 {
1348     switch (m_token.m_type) {
1349     case OPENBRACE:
1350         return parseObjectLiteral(context);
1351     case OPENBRACKET:
1352         return parseArrayLiteral(context);
1353     case OPENPAREN: {
1354         next();
1355         int oldNonLHSCount = m_nonLHSCount;
1356         TreeExpression result = parseExpression(context);
1357         m_nonLHSCount = oldNonLHSCount;
1358         consumeOrFail(CLOSEPAREN);
1359
1360         return result;
1361     }
1362     case THISTOKEN: {
1363         next();
1364         return context.thisExpr();
1365     }
1366     case IDENT: {
1367         int start = tokenStart();
1368         const Identifier* ident = m_token.m_data.ident;
1369         next();
1370         currentScope()->useVariable(ident, m_globalData->propertyNames->eval == *ident);
1371         return context.createResolve(ident, start);
1372     }
1373     case STRING: {
1374         const Identifier* ident = m_token.m_data.ident;
1375         next();
1376         return context.createString(ident);
1377     }
1378     case NUMBER: {
1379         double d = m_token.m_data.doubleValue;
1380         next();
1381         return context.createNumberExpr(d);
1382     }
1383     case NULLTOKEN: {
1384         next();
1385         return context.createNull();
1386     }
1387     case TRUETOKEN: {
1388         next();
1389         return context.createBoolean(true);
1390     }
1391     case FALSETOKEN: {
1392         next();
1393         return context.createBoolean(false);
1394     }
1395     case DIVEQUAL:
1396     case DIVIDE: {
1397         /* regexp */
1398         const Identifier* pattern;
1399         const Identifier* flags;
1400         if (match(DIVEQUAL))
1401             failIfFalse(m_lexer->scanRegExp(pattern, flags, '='));
1402         else
1403             failIfFalse(m_lexer->scanRegExp(pattern, flags));
1404
1405         int start = tokenStart();
1406         next();
1407         return context.createRegex(*pattern, *flags, start);
1408     }
1409     default:
1410         fail();
1411     }
1412 }
1413
1414 template <class TreeBuilder> TreeArguments JSParser::parseArguments(TreeBuilder& context)
1415 {
1416     consumeOrFail(OPENPAREN);
1417     if (match(CLOSEPAREN)) {
1418         next();
1419         return context.createArguments();
1420     }
1421     TreeExpression firstArg = parseAssignmentExpression(context);
1422     failIfFalse(firstArg);
1423
1424     TreeArgumentsList argList = context.createArgumentsList(firstArg);
1425     TreeArgumentsList tail = argList;
1426     while (match(COMMA)) {
1427         next();
1428         TreeExpression arg = parseAssignmentExpression(context);
1429         failIfFalse(arg);
1430         tail = context.createArgumentsList(tail, arg);
1431     }
1432     consumeOrFail(CLOSEPAREN);
1433     return context.createArguments(argList);
1434 }
1435
1436 template <class TreeBuilder> TreeExpression JSParser::parseMemberExpression(TreeBuilder& context)
1437 {
1438     TreeExpression base = 0;
1439     int start = tokenStart();
1440     int expressionStart = start;
1441     int newCount = 0;
1442     while (match(NEW)) {
1443         next();
1444         newCount++;
1445     }
1446     if (match(FUNCTION)) {
1447         const Identifier* name = &m_globalData->propertyNames->nullIdentifier;
1448         TreeFormalParameterList parameters = 0;
1449         TreeFunctionBody body = 0;
1450         int openBracePos = 0;
1451         int closeBracePos = 0;
1452         int bodyStartLine = 0;
1453         next();
1454         failIfFalse(parseFunctionInfo<FunctionNoRequirements>(context, name, parameters, body, openBracePos, closeBracePos, bodyStartLine));
1455         base = context.createFunctionExpr(name, body, parameters, openBracePos, closeBracePos, bodyStartLine, m_lastLine);
1456     } else
1457         base = parsePrimaryExpression(context);
1458
1459     failIfFalse(base);
1460     while (true) {
1461         switch (m_token.m_type) {
1462         case OPENBRACKET: {
1463             int expressionEnd = lastTokenEnd();
1464             next();
1465             int nonLHSCount = m_nonLHSCount;
1466             int initialAssignments = m_assignmentCount;
1467             TreeExpression property = parseExpression(context);
1468             failIfFalse(property);
1469             base = context.createBracketAccess(base, property, initialAssignments != m_assignmentCount, expressionStart, expressionEnd, tokenEnd());
1470             if (!consume(CLOSEBRACKET))
1471                 fail();
1472             m_nonLHSCount = nonLHSCount;
1473             break;
1474         }
1475         case OPENPAREN: {
1476             if (newCount) {
1477                 newCount--;
1478                 if (match(OPENPAREN)) {
1479                     int exprEnd = lastTokenEnd();
1480                     TreeArguments arguments = parseArguments(context);
1481                     failIfFalse(arguments);
1482                     base = context.createNewExpr(base, arguments, start, exprEnd, lastTokenEnd());
1483                 } else
1484                     base = context.createNewExpr(base, start, lastTokenEnd());               
1485             } else {
1486                 int nonLHSCount = m_nonLHSCount;
1487                 int expressionEnd = lastTokenEnd();
1488                 TreeArguments arguments = parseArguments(context);
1489                 failIfFalse(arguments);
1490                 base = context.makeFunctionCallNode(base, arguments, expressionStart, expressionEnd, lastTokenEnd());
1491                 m_nonLHSCount = nonLHSCount;
1492             }
1493             break;
1494         }
1495         case DOT: {
1496             int expressionEnd = lastTokenEnd();
1497             next(Lexer::IgnoreReservedWords);
1498             matchOrFail(IDENT);
1499             base = context.createDotAccess(base, *m_token.m_data.ident, expressionStart, expressionEnd, tokenEnd());
1500             next();
1501             break;
1502         }
1503         default:
1504             goto endMemberExpression;
1505         }
1506     }
1507 endMemberExpression:
1508     while (newCount--)
1509         base = context.createNewExpr(base, start, lastTokenEnd());
1510     return base;
1511 }
1512
1513 template <class TreeBuilder> TreeExpression JSParser::parseUnaryExpression(TreeBuilder& context)
1514 {
1515     AllowInOverride allowInOverride(this);
1516     int tokenStackDepth = 0;
1517     while (isUnaryOp(m_token.m_type)) {
1518         m_nonLHSCount++;
1519         context.appendUnaryToken(tokenStackDepth, m_token.m_type, tokenStart());
1520         next();
1521     }
1522     int subExprStart = tokenStart();
1523     TreeExpression expr = parseMemberExpression(context);
1524     failIfFalse(expr);
1525     switch (m_token.m_type) {
1526     case PLUSPLUS:
1527         m_nonLHSCount++;
1528         expr = context.makePostfixNode(expr, OpPlusPlus, subExprStart, lastTokenEnd(), tokenEnd());
1529         m_assignmentCount++;
1530         next();
1531         break;
1532     case MINUSMINUS:
1533         m_nonLHSCount++;
1534         expr = context.makePostfixNode(expr, OpMinusMinus, subExprStart, lastTokenEnd(), tokenEnd());
1535         m_assignmentCount++;
1536         next();
1537         break;
1538     default:
1539         break;
1540     }
1541
1542     int end = lastTokenEnd();
1543
1544     if (!TreeBuilder::CreatesAST)
1545         return expr;
1546
1547     while (tokenStackDepth) {
1548         switch (context.unaryTokenStackLastType(tokenStackDepth)) {
1549         case EXCLAMATION:
1550             expr = context.createLogicalNot(expr);
1551             break;
1552         case TILDE:
1553             expr = context.makeBitwiseNotNode(expr);
1554             break;
1555         case MINUS:
1556             expr = context.makeNegateNode(expr);
1557             break;
1558         case PLUS:
1559             expr = context.createUnaryPlus(expr);
1560             break;
1561         case PLUSPLUS:
1562         case AUTOPLUSPLUS:
1563             expr = context.makePrefixNode(expr, OpPlusPlus, context.unaryTokenStackLastStart(tokenStackDepth), subExprStart + 1, end);
1564             m_assignmentCount++;
1565             break;
1566         case MINUSMINUS:
1567         case AUTOMINUSMINUS:
1568             expr = context.makePrefixNode(expr, OpMinusMinus, context.unaryTokenStackLastStart(tokenStackDepth), subExprStart + 1, end);
1569             m_assignmentCount++;
1570             break;
1571         case TYPEOF:
1572             expr = context.makeTypeOfNode(expr);
1573             break;
1574         case VOIDTOKEN:
1575             expr = context.createVoid(expr);
1576             break;
1577         case DELETETOKEN:
1578             expr = context.makeDeleteNode(expr, context.unaryTokenStackLastStart(tokenStackDepth), end, end);
1579             break;
1580         default:
1581             // If we get here something has gone horribly horribly wrong
1582             CRASH();
1583         }
1584         subExprStart = context.unaryTokenStackLastStart(tokenStackDepth);
1585         context.unaryTokenStackRemoveLast(tokenStackDepth);
1586     }
1587     return expr;
1588 }
1589
1590 }