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