runtime/LiteralParser.cpp

   1 /*
   2  * Copyright (C) 2009 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. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "LiteralParser.h"
  28
  29 #include "JSArray.h"
  30 #include "JSString.h"
  31 #include "Lexer.h"
  32 #include "StringBuilder.h"
  33 #include <wtf/ASCIICType.h>
  34 #include <wtf/dtoa.h>
  35
  36 namespace JSC {
  37
  38 LiteralParser::TokenType LiteralParser::Lexer::lex(LiteralParserToken& token)
  39 {
  40     while (m_ptr < m_end && isASCIISpace(*m_ptr))
  41         ++m_ptr;
  42
  43     ASSERT(m_ptr <= m_end);
  44     if (m_ptr >= m_end) {
  45         token.type = TokEnd;
  46         token.start = token.end = m_ptr;
  47         return TokEnd;
  48     }
  49     token.type = TokError;
  50     token.start = m_ptr;
  51     switch (*m_ptr) {
  52         case '[':
  53             token.type = TokLBracket;
  54             token.end = ++m_ptr;
  55             return TokLBracket;
  56         case ']':
  57             token.type = TokRBracket;
  58             token.end = ++m_ptr;
  59             return TokRBracket;
  60         case '(':
  61             token.type = TokLParen;
  62             token.end = ++m_ptr;
  63             return TokLBracket;
  64         case ')':
  65             token.type = TokRParen;
  66             token.end = ++m_ptr;
  67             return TokRBracket;
  68         case '{':
  69             token.type = TokLBrace;
  70             token.end = ++m_ptr;
  71             return TokLBrace;
  72         case '}':
  73             token.type = TokRBrace;
  74             token.end = ++m_ptr;
  75             return TokRBrace;
  76         case ',':
  77             token.type = TokComma;
  78             token.end = ++m_ptr;
  79             return TokComma;
  80         case ':':
  81             token.type = TokColon;
  82             token.end = ++m_ptr;
  83             return TokColon;
  84         case '"':
  85             if (m_mode == StrictJSON)
  86                 return lexString<StrictJSON>(token);
  87             return lexString<NonStrictJSON>(token);
  88         case 't':
  89             if (m_end - m_ptr >= 4 && m_ptr[1] == 'r' && m_ptr[2] == 'u' && m_ptr[3] == 'e') {
  90                 m_ptr += 4;
  91                 token.type = TokTrue;
  92                 token.end = m_ptr;
  93                 return TokTrue;
  94             }
  95             break;
  96         case 'f':
  97             if (m_end - m_ptr >= 5 && m_ptr[1] == 'a' && m_ptr[2] == 'l' && m_ptr[3] == 's' && m_ptr[4] == 'e') {
  98                 m_ptr += 5;
  99                 token.type = TokFalse;
 100                 token.end = m_ptr;
 101                 return TokFalse;
 102             }
 103             break;
 104         case 'n':
 105             if (m_end - m_ptr >= 4 && m_ptr[1] == 'u' && m_ptr[2] == 'l' && m_ptr[3] == 'l') {
 106                 m_ptr += 4;
 107                 token.type = TokNull;
 108                 token.end = m_ptr;
 109                 return TokNull;
 110             }
 111             break;
 112         case '-':
 113         case '0':
 114         case '1':
 115         case '2':
 116         case '3':
 117         case '4':
 118         case '5':
 119         case '6':
 120         case '7':
 121         case '8':
 122         case '9':
 123             return lexNumber(token);
 124     }
 125     return TokError;
 126 }
 127
 128 template <LiteralParser::ParserMode mode> static inline bool isSafeStringCharacter(UChar c)
 129 {
 130     return (c >= ' ' && (mode == LiteralParser::StrictJSON || c <= 0xff) && c != '\\' && c != '"') || c == '\t';
 131 }
 132
 133 // "inline" is required here to help WINSCW compiler resolve specialized argument in templated functions.
 134 template <LiteralParser::ParserMode mode> inline LiteralParser::TokenType LiteralParser::Lexer::lexString(LiteralParserToken& token)
 135 {
 136     ++m_ptr;
 137     const UChar* runStart;
 138     StringBuilder builder;
 139     do {
 140         runStart = m_ptr;
 141         while (m_ptr < m_end && isSafeStringCharacter<mode>(*m_ptr))
 142             ++m_ptr;
 143         if (runStart < m_ptr)
 144             builder.append(runStart, m_ptr - runStart);
 145         if ((mode == StrictJSON) && m_ptr < m_end && *m_ptr == '\\') {
 146             ++m_ptr;
 147             if (m_ptr >= m_end)
 148                 return TokError;
 149             switch (*m_ptr) {
 150                 case '"':
 151                     builder.append('"');
 152                     m_ptr++;
 153                     break;
 154                 case '\\':
 155                     builder.append('\\');
 156                     m_ptr++;
 157                     break;
 158                 case '/':
 159                     builder.append('/');
 160                     m_ptr++;
 161                     break;
 162                 case 'b':
 163                     builder.append('\b');
 164                     m_ptr++;
 165                     break;
 166                 case 'f':
 167                     builder.append('\f');
 168                     m_ptr++;
 169                     break;
 170                 case 'n':
 171                     builder.append('\n');
 172                     m_ptr++;
 173                     break;
 174                 case 'r':
 175                     builder.append('\r');
 176                     m_ptr++;
 177                     break;
 178                 case 't':
 179                     builder.append('\t');
 180                     m_ptr++;
 181                     break;
 182
 183                 case 'u':
 184                     if ((m_end - m_ptr) < 5) // uNNNN == 5 characters
 185                         return TokError;
 186                     for (int i = 1; i < 5; i++) {
 187                         if (!isASCIIHexDigit(m_ptr[i]))
 188                             return TokError;
 189                     }
 190                     builder.append(JSC::Lexer::convertUnicode(m_ptr[1], m_ptr[2], m_ptr[3], m_ptr[4]));
 191                     m_ptr += 5;
 192                     break;
 193
 194                 default:
 195                     return TokError;
 196             }
 197         }
 198     } while ((mode == StrictJSON) && m_ptr != runStart && (m_ptr < m_end) && *m_ptr != '"');
 199
 200     if (m_ptr >= m_end || *m_ptr != '"')
 201         return TokError;
 202
 203     token.stringToken = builder.release();
 204     token.type = TokString;
 205     token.end = ++m_ptr;
 206     return TokString;
 207 }
 208
 209 LiteralParser::TokenType LiteralParser::Lexer::lexNumber(LiteralParserToken& token)
 210 {
 211     // ES5 and json.org define numbers as
 212     // number
 213     //     int
 214     //     int frac? exp?
 215     //
 216     // int
 217     //     -? 0
 218     //     -? digit1-9 digits?
 219     //
 220     // digits
 221     //     digit digits?
 222     //
 223     // -?(0 | [1-9][0-9]*) ('.' [0-9]+)? ([eE][+-]? [0-9]+)?
 224
 225     if (m_ptr < m_end && *m_ptr == '-') // -?
 226         ++m_ptr;
 227
 228     // (0 | [1-9][0-9]*)
 229     if (m_ptr < m_end && *m_ptr == '0') // 0
 230         ++m_ptr;
 231     else if (m_ptr < m_end && *m_ptr >= '1' && *m_ptr <= '9') { // [1-9]
 232         ++m_ptr;
 233         // [0-9]*
 234         while (m_ptr < m_end && isASCIIDigit(*m_ptr))
 235             ++m_ptr;
 236     } else
 237         return TokError;
 238
 239     // ('.' [0-9]+)?
 240     if (m_ptr < m_end && *m_ptr == '.') {
 241         ++m_ptr;
 242         // [0-9]+
 243         if (m_ptr >= m_end || !isASCIIDigit(*m_ptr))
 244             return TokError;
 245
 246         ++m_ptr;
 247         while (m_ptr < m_end && isASCIIDigit(*m_ptr))
 248             ++m_ptr;
 249     }
 250
 251     //  ([eE][+-]? [0-9]+)?
 252     if (m_ptr < m_end && (*m_ptr == 'e' || *m_ptr == 'E')) { // [eE]
 253         ++m_ptr;
 254
 255         // [-+]?
 256         if (m_ptr < m_end && (*m_ptr == '-' || *m_ptr == '+'))
 257             ++m_ptr;
 258
 259         // [0-9]+
 260         if (m_ptr >= m_end || !isASCIIDigit(*m_ptr))
 261             return TokError;
 262
 263         ++m_ptr;
 264         while (m_ptr < m_end && isASCIIDigit(*m_ptr))
 265             ++m_ptr;
 266     }
 267
 268     token.type = TokNumber;
 269     token.end = m_ptr;
 270     Vector<char, 64> buffer(token.end - token.start + 1);
 271     int i;
 272     for (i = 0; i < token.end - token.start; i++) {
 273         ASSERT(static_cast<char>(token.start[i]) == token.start[i]);
 274         buffer[i] = static_cast<char>(token.start[i]);
 275     }
 276     buffer[i] = 0;
 277     char* end;
 278     token.numberToken = WTF::strtod(buffer.data(), &end);
 279     ASSERT(buffer.data() + (token.end - token.start) == end);
 280     return TokNumber;
 281 }
 282
 283 JSValue LiteralParser::parse(ParserState initialState)
 284 {
 285     ParserState state = initialState;
 286     MarkedArgumentBuffer objectStack;
 287     JSValue lastValue;
 288     Vector<ParserState, 16> stateStack;
 289     Vector<Identifier, 16> identifierStack;
 290     while (1) {
 291         switch(state) {
 292             startParseArray:
 293             case StartParseArray: {
 294                 JSArray* array = constructEmptyArray(m_exec);
 295                 objectStack.append(array);
 296                 // fallthrough
 297             }
 298             doParseArrayStartExpression:
 299             case DoParseArrayStartExpression: {
 300                 TokenType lastToken = m_lexer.currentToken().type;
 301                 if (m_lexer.next() == TokRBracket) {
 302                     if (lastToken == TokComma)
 303                         return JSValue();
 304                     m_lexer.next();
 305                     lastValue = objectStack.last();
 306                     objectStack.removeLast();
 307                     break;
 308                 }
 309
 310                 stateStack.append(DoParseArrayEndExpression);
 311                 goto startParseExpression;
 312             }
 313             case DoParseArrayEndExpression: {
 314                  asArray(objectStack.last())->push(m_exec, lastValue);
 315
 316                 if (m_lexer.currentToken().type == TokComma)
 317                     goto doParseArrayStartExpression;
 318
 319                 if (m_lexer.currentToken().type != TokRBracket)
 320                     return JSValue();
 321
 322                 m_lexer.next();
 323                 lastValue = objectStack.last();
 324                 objectStack.removeLast();
 325                 break;
 326             }
 327             startParseObject:
 328             case StartParseObject: {
 329                 JSObject* object = constructEmptyObject(m_exec);
 330                 objectStack.append(object);
 331
 332                 TokenType type = m_lexer.next();
 333                 if (type == TokString) {
 334                     Lexer::LiteralParserToken identifierToken = m_lexer.currentToken();
 335
 336                     // Check for colon
 337                     if (m_lexer.next() != TokColon)
 338                         return JSValue();
 339
 340                     m_lexer.next();
 341                     identifierStack.append(Identifier(m_exec, identifierToken.stringToken));
 342                     stateStack.append(DoParseObjectEndExpression);
 343                     goto startParseExpression;
 344                 } else if (type != TokRBrace)
 345                     return JSValue();
 346                 m_lexer.next();
 347                 lastValue = objectStack.last();
 348                 objectStack.removeLast();
 349                 break;
 350             }
 351             doParseObjectStartExpression:
 352             case DoParseObjectStartExpression: {
 353                 TokenType type = m_lexer.next();
 354                 if (type != TokString)
 355                     return JSValue();
 356                 Lexer::LiteralParserToken identifierToken = m_lexer.currentToken();
 357
 358                 // Check for colon
 359                 if (m_lexer.next() != TokColon)
 360                     return JSValue();
 361
 362                 m_lexer.next();
 363                 identifierStack.append(Identifier(m_exec, identifierToken.stringToken));
 364                 stateStack.append(DoParseObjectEndExpression);
 365                 goto startParseExpression;
 366             }
 367             case DoParseObjectEndExpression:
 368             {
 369                 asObject(objectStack.last())->putDirect(identifierStack.last(), lastValue);
 370                 identifierStack.removeLast();
 371                 if (m_lexer.currentToken().type == TokComma)
 372                     goto doParseObjectStartExpression;
 373                 if (m_lexer.currentToken().type != TokRBrace)
 374                     return JSValue();
 375                 m_lexer.next();
 376                 lastValue = objectStack.last();
 377                 objectStack.removeLast();
 378                 break;
 379             }
 380             startParseExpression:
 381             case StartParseExpression: {
 382                 switch (m_lexer.currentToken().type) {
 383                     case TokLBracket:
 384                         goto startParseArray;
 385                     case TokLBrace:
 386                         goto startParseObject;
 387                     case TokString: {
 388                         Lexer::LiteralParserToken stringToken = m_lexer.currentToken();
 389                         m_lexer.next();
 390                         lastValue = jsString(m_exec, stringToken.stringToken);
 391                         break;
 392                     }
 393                     case TokNumber: {
 394                         Lexer::LiteralParserToken numberToken = m_lexer.currentToken();
 395                         m_lexer.next();
 396                         lastValue = jsNumber(m_exec, numberToken.numberToken);
 397                         break;
 398                     }
 399                     case TokNull:
 400                         m_lexer.next();
 401                         lastValue = jsNull();
 402                         break;
 403
 404                     case TokTrue:
 405                         m_lexer.next();
 406                         lastValue = jsBoolean(true);
 407                         break;
 408
 409                     case TokFalse:
 410                         m_lexer.next();
 411                         lastValue = jsBoolean(false);
 412                         break;
 413
 414                     default:
 415                         // Error
 416                         return JSValue();
 417                 }
 418                 break;
 419             }
 420             case StartParseStatement: {
 421                 switch (m_lexer.currentToken().type) {
 422                     case TokLBracket:
 423                     case TokNumber:
 424                     case TokString:
 425                         goto startParseExpression;
 426
 427                     case TokLParen: {
 428                         m_lexer.next();
 429                         stateStack.append(StartParseStatementEndStatement);
 430                         goto startParseExpression;
 431                     }
 432                     default:
 433                         return JSValue();
 434                 }
 435             }
 436             case StartParseStatementEndStatement: {
 437                 ASSERT(stateStack.isEmpty());
 438                 if (m_lexer.currentToken().type != TokRParen)
 439                     return JSValue();
 440                 if (m_lexer.next() == TokEnd)
 441                     return lastValue;
 442                 return JSValue();
 443             }
 444             default:
 445                 ASSERT_NOT_REACHED();
 446         }
 447         if (stateStack.isEmpty())
 448             return lastValue;
 449         state = stateStack.last();
 450         stateStack.removeLast();
 451         continue;
 452     }
 453 }
 454
 455 }