Changeset 44644 in webkit for trunk/JavaScriptCore


Ignore:
Timestamp:
Jun 12, 2009, 6:18:57 PM (16 years ago)
Author:
[email protected]
Message:

Make LiteralParser non-recursive

Reviewed by Geoff Garen.

Convert LiteralParser from using a simple recursive descent parser
to a hand rolled PDA. Relatively simple conversion, but required
modifications to MarkedArgumentBuffer to make it more suitable as
a generic marked vector. I'll refactor and rename MarkedArgumentBuffer
in future as there are many other cases where it will be useful to
have such a class.

Location:
trunk/JavaScriptCore
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r44642 r44644  
     12009-06-12  Oliver Hunt  <[email protected]>
     2
     3        Reviewed by Geoff Garen.
     4
     5        Make LiteralParser non-recursive
     6
     7        Convert LiteralParser from using a simple recursive descent parser
     8        to a hand rolled PDA.  Relatively simple conversion, but required
     9        modifications to MarkedArgumentBuffer to make it more suitable as
     10        a generic marked vector.   I'll refactor and rename MarkedArgumentBuffer
     11        in future as there are many other cases where it will be useful to
     12        have such a class.
     13
     14        * runtime/ArgList.h:
     15        (JSC::MarkedArgumentBuffer::MarkedArgumentBuffer):
     16        (JSC::MarkedArgumentBuffer::append):
     17        (JSC::MarkedArgumentBuffer::removeLast):
     18        (JSC::MarkedArgumentBuffer::last):
     19        * runtime/LiteralParser.cpp:
     20        (JSC::LiteralParser::parse):
     21        * runtime/LiteralParser.h:
     22        (JSC::LiteralParser::LiteralParser):
     23        (JSC::LiteralParser::tryLiteralParse):
     24        (JSC::LiteralParser::):
     25
    1262009-06-12  David Levin  <[email protected]>
    227

  • trunk/JavaScriptCore/runtime/ArgList.h

    r44224 r44644  
    4545        // FIXME: Remove all clients of this API, then remove this API.
    4646        MarkedArgumentBuffer()
    47             : m_markSet(0)
     47            : m_isUsingInlineBuffer(true)
     48            , m_markSet(0)
    4849#ifndef NDEBUG
    4950            , m_isReadOnly(false)
    … …  
    5859            : m_buffer(buffer)
    5960            , m_size(size)
     61            , m_isUsingInlineBuffer(true)
    6062            , m_markSet(0)
    6163#ifndef NDEBUG
    … …  
    104106            ASSERT(!m_isReadOnly);
    105107           
    106             if (m_size < inlineCapacity) {
     108            if (m_isUsingInlineBuffer && m_size < inlineCapacity) {
    107109                m_vector.uncheckedAppend(v);
    108110                ++m_size;
    … …  
    112114                slowAppend(v);
    113115                ++m_size;
     116                m_isUsingInlineBuffer = false;
    114117            }
    115118        }
    116119
     120        void removeLast()
     121        {
     122            ASSERT(m_size);
     123            m_size--;
     124            m_vector.removeLast();
     125        }
     126
     127        JSValue last()
     128        {
     129            ASSERT(m_size);
     130            return m_buffer[m_size - 1].jsValue();
     131        }
     132       
    117133        iterator begin() { return m_buffer; }
    118134        iterator end() { return m_buffer + m_size; }
    … …  
    128144        Register* m_buffer;
    129145        size_t m_size;
     146        bool m_isUsingInlineBuffer;
    130147
    131148        VectorType m_vector;

  • trunk/JavaScriptCore/runtime/LiteralParser.cpp

    r44343 r44644  
    3333namespace JSC {
    3434
    35 class LiteralParser::StackGuard {
    36 public:
    37     StackGuard(LiteralParser* parser)
    38         : m_parser(parser)
    39     {
    40         m_parser->m_depth++;
    41     }
    42     ~StackGuard()
    43     {
    44         m_parser->m_depth--;
    45     }
    46     bool isSafe() { return m_parser->m_depth < 10; }
    47 private:
    48     LiteralParser* m_parser;
    49 };
    50 
    5135static bool isSafeStringCharacter(UChar c)
    5236{
    … …  
    198182}
    199183
    200 JSValue LiteralParser::parseStatement()
    201 {
    202     StackGuard guard(this);
    203     if (!guard.isSafe())
    204         return abortParse();
    205 
    206     switch (m_lexer.currentToken().type) {
    207         case TokLBracket:
    208         case TokNumber:
    209         case TokString:
    210             return parseExpression();
    211         case TokLParen: {
    212             m_lexer.next();
    213             JSValue result = parseExpression();
    214             if (m_aborted || m_lexer.currentToken().type != TokRParen)
    215                 return abortParse();
    216             m_lexer.next();
    217             return result;
     184JSValue LiteralParser::parse(ParserState initialState)
     185{
     186    ParserState state = initialState;
     187    MarkedArgumentBuffer objectStack;
     188    JSValue lastValue;
     189    Vector<ParserState, 16> stateStack;
     190    Vector<Identifier, 16> identifierStack;
     191    while (1) {
     192        switch(state) {
     193            startParseArray:
     194            case StartParseArray: {
     195                JSArray* array = constructEmptyArray(m_exec);
     196                objectStack.append(array);
     197                // fallthrough
     198            }
     199            doParseArrayStartExpression:
     200            case DoParseArrayStartExpression: {
     201                if (m_lexer.next() == TokRBracket) {
     202                    m_lexer.next();
     203                    lastValue = objectStack.last();
     204                    objectStack.removeLast();
     205                    break;
     206                }
     207
     208                stateStack.append(DoParseArrayEndExpression);
     209                goto startParseExpression;
     210            }
     211            case DoParseArrayEndExpression: {
     212                 asArray(objectStack.last())->push(m_exec, lastValue);
     213               
     214                if (m_lexer.currentToken().type == TokComma)
     215                    goto doParseArrayStartExpression;
     216
     217                if (m_lexer.currentToken().type != TokRBracket)
     218                    return JSValue();
     219               
     220                m_lexer.next();
     221                lastValue = objectStack.last();
     222                objectStack.removeLast();
     223                break;
     224            }
     225            startParseObject:
     226            case StartParseObject: {
     227                JSObject* object = constructEmptyObject(m_exec);
     228                objectStack.append(object);
     229                // fallthrough
     230            }
     231            doParseObjectStartExpression:
     232            case DoParseObjectStartExpression: {
     233                TokenType type = m_lexer.next();
     234                if (type == TokString) {
     235                    Lexer::LiteralParserToken identifierToken = m_lexer.currentToken();
     236
     237                    // Check for colon
     238                    if (m_lexer.next() != TokColon)
     239                        return JSValue();
     240
     241                    m_lexer.next();
     242                    identifierStack.append(Identifier(m_exec, identifierToken.start + 1, identifierToken.end - identifierToken.start - 2));
     243                    stateStack.append(DoParseObjectEndExpression);
     244                    goto startParseExpression;
     245                } else if (type != TokRBrace)
     246                    return JSValue();
     247                m_lexer.next();
     248                lastValue = objectStack.last();
     249                objectStack.removeLast();
     250                break;
     251            }
     252            case DoParseObjectEndExpression:
     253            {
     254                asObject(objectStack.last())->putDirect(identifierStack.last(), lastValue);
     255                identifierStack.removeLast();
     256                if (m_lexer.currentToken().type == TokComma)
     257                    goto doParseObjectStartExpression;
     258                if (m_lexer.currentToken().type != TokRBrace)
     259                    return JSValue();
     260                m_lexer.next();
     261                lastValue = objectStack.last();
     262                objectStack.removeLast();
     263                break;
     264            }
     265            startParseExpression:
     266            case StartParseExpression: {
     267                switch (m_lexer.currentToken().type) {
     268                    case TokLBracket:
     269                        goto startParseArray;
     270                    case TokLBrace:
     271                        goto startParseObject;
     272                    case TokString: {
     273                        Lexer::LiteralParserToken stringToken = m_lexer.currentToken();
     274                        m_lexer.next();
     275                        lastValue = jsString(m_exec, UString(stringToken.start + 1, stringToken.end - stringToken.start - 2));
     276                        break;
     277                    }
     278                    case TokNumber: {
     279                        Lexer::LiteralParserToken numberToken = m_lexer.currentToken();
     280                        m_lexer.next();
     281                        lastValue = jsNumber(m_exec, UString(numberToken.start, numberToken.end - numberToken.start).toDouble());
     282                        break;
     283                    }
     284                    default:
     285                        // Error
     286                        return JSValue();
     287                }
     288                break;
     289            }
     290            case StartParseStatement: {
     291                switch (m_lexer.currentToken().type) {
     292                    case TokLBracket:
     293                    case TokNumber:
     294                    case TokString:
     295                        goto startParseExpression;
     296
     297                    case TokLParen: {
     298                        m_lexer.next();
     299                        stateStack.append(StartParseStatementEndStatement);
     300                        goto startParseExpression;
     301                    }
     302                    default:
     303                        return JSValue();
     304                }
     305            }
     306            case StartParseStatementEndStatement: {
     307                ASSERT(stateStack.isEmpty());
     308                if (m_lexer.currentToken().type != TokRParen)
     309                    return JSValue();
     310                if (m_lexer.next() == TokEnd)
     311                    return lastValue;
     312                return JSValue();
     313            }
     314            default:
     315                ASSERT_NOT_REACHED();
    218316        }
    219         default:
    220             return abortParse();
    221     }
    222 }
    223 
    224 JSValue LiteralParser::parseExpression()
    225 {
    226     StackGuard guard(this);
    227     if (!guard.isSafe())
    228         return abortParse();
    229     switch (m_lexer.currentToken().type) {
    230         case TokLBracket:
    231             return parseArray();
    232         case TokLBrace:
    233             return parseObject();
    234         case TokString: {
    235             Lexer::LiteralParserToken stringToken = m_lexer.currentToken();
    236             m_lexer.next();
    237             return jsString(m_exec, UString(stringToken.start + 1, stringToken.end - stringToken.start - 2));
    238         }
    239         case TokNumber: {
    240             Lexer::LiteralParserToken numberToken = m_lexer.currentToken();
    241             m_lexer.next();
    242             return jsNumber(m_exec, UString(numberToken.start, numberToken.end - numberToken.start).toDouble());
    243         }
    244         default:
    245             return JSValue();
    246     }
    247 }
    248 
    249 JSValue LiteralParser::parseArray()
    250 {
    251     StackGuard guard(this);
    252     if (!guard.isSafe())
    253         return abortParse();
    254     JSArray* array = constructEmptyArray(m_exec);
    255     while (true) {
    256         m_lexer.next();
    257         JSValue value = parseExpression();
    258         if (m_aborted)
    259             return JSValue();
    260         if (!value)
    261             break;
    262         array->push(m_exec, value);
    263 
    264         if (m_lexer.currentToken().type != TokComma)
    265             break;
    266     }
    267     if (m_lexer.currentToken().type != TokRBracket)
    268         return abortParse();
    269 
    270     m_lexer.next();
    271     return array;
    272 }
    273 
    274 JSValue LiteralParser::parseObject()
    275 {
    276     StackGuard guard(this);
    277     if (!guard.isSafe())
    278         return abortParse();
    279     JSObject* object = constructEmptyObject(m_exec);
    280    
    281     while (m_lexer.next() == TokString) {
    282         Lexer::LiteralParserToken identifierToken = m_lexer.currentToken();
    283        
    284         // Check for colon
    285         if (m_lexer.next() != TokColon)
    286             return abortParse();
    287         m_lexer.next();
    288        
    289         JSValue value = parseExpression();
    290         if (!value || m_aborted)
    291             return abortParse();
    292        
    293         Identifier ident(m_exec, identifierToken.start + 1, identifierToken.end - identifierToken.start - 2);
    294         object->putDirect(ident, value);
    295        
    296         if (m_lexer.currentToken().type != TokComma)
    297             break;
    298     }
    299    
    300     if (m_lexer.currentToken().type != TokRBrace)
    301         return abortParse();
    302     m_lexer.next();
    303     return object;
    304 }
    305 
    306 }
     317        if (stateStack.isEmpty())
     318            return lastValue;
     319        state = stateStack.last();
     320        stateStack.removeLast();
     321        continue;
     322    }
     323}
     324
     325}

  • trunk/JavaScriptCore/runtime/LiteralParser.h

    r43424 r44644  
    3838            : m_exec(exec)
    3939            , m_lexer(s)
    40             , m_depth(0)
    41             , m_aborted(false)
    4240        {
    4341        }
    … …  
    4644        {
    4745            m_lexer.next();
    48             JSValue result = parseStatement();
    49             if (m_aborted || m_lexer.currentToken().type != TokEnd)
     46            JSValue result = parse(StartParseStatement);
     47            if (m_lexer.currentToken().type != TokEnd)
    5048                return JSValue();
    5149            return result;
    5250        }
    5351    private:
    54        
     52        enum ParserState { StartParseObject, StartParseArray, StartParseExpression,
     53                           StartParseStatement, StartParseStatementEndStatement,
     54                           DoParseObjectStartExpression, DoParseObjectEndExpression,
     55                           DoParseArrayStartExpression, DoParseArrayEndExpression };
    5556        enum TokenType { TokLBracket, TokRBracket, TokLBrace, TokRBrace,
    5657                         TokString, TokIdentifier, TokNumber, TokColon,
    … …  
    9293       
    9394        class StackGuard;
    94         JSValue parseStatement();
    95         JSValue parseExpression();
    96         JSValue parseArray();
    97         JSValue parseObject();
    98 
    99         JSValue abortParse()
    100         {
    101             m_aborted = true;
    102             return JSValue();
    103         }
     95        JSValue parse(ParserState);
    10496
    10597        ExecState* m_exec;
    10698        LiteralParser::Lexer m_lexer;
    107         int m_depth;
    108         bool m_aborted;
    10999    };
    110100}
Note: See TracChangeset for help on using the changeset viewer.