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