js/src/jsonparser.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  * vim: set ts=8 sw=4 et tw=99:
   3  *
   4  * ***** BEGIN LICENSE BLOCK *****
   5  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   6  *
   7  * The contents of this file are subject to the Mozilla Public License Version
   8  * 1.1 (the "License"); you may not use this file except in compliance with
   9  * the License. You may obtain a copy of the License at
  10  * http://www.mozilla.org/MPL/
  11  *
  12  * Software distributed under the License is distributed on an "AS IS" basis,
  13  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  14  * for the specific language governing rights and limitations under the
  15  * License.
  16  *
  17  * The Original Code is SpiderMonkey JSON.
  18  *
  19  * The Initial Developer of the Original Code is
  20  * the Mozilla Foundation.
  21  * Portions created by the Initial Developer are Copyright (C) 2011
  22  * the Initial Developer. All Rights Reserved.
  23  *
  24  * Contributor(s):
  25  *   Jeff Walden <jwalden+code@mit.edu> (original author)
  26  *
  27  * Alternatively, the contents of this file may be used under the terms of
  28  * either of the GNU General Public License Version 2 or later (the "GPL"),
  29  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  30  * in which case the provisions of the GPL or the LGPL are applicable instead
  31  * of those above. If you wish to allow use of your version of this file only
  32  * under the terms of either the GPL or the LGPL, and not to allow others to
  33  * use your version of this file under the terms of the MPL, indicate your
  34  * decision by deleting the provisions above and replace them with the notice
  35  * and other provisions required by the GPL or the LGPL. If you do not delete
  36  * the provisions above, a recipient may use your version of this file under
  37  * the terms of any one of the MPL, the GPL or the LGPL.
  38  *
  39  * ***** END LICENSE BLOCK ***** */
  40
  41 #include "jsarray.h"
  42 #include "jsnum.h"
  43 #include "jsonparser.h"
  44
  45 #include "vm/StringBuffer.h"
  46
  47 #include "jsobjinlines.h"
  48
  49 using namespace js;
  50
  51 void
  52 JSONParser::error(const char *msg)
  53 {
  54     if (errorHandling == RaiseError)
  55         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_JSON_BAD_PARSE, msg);
  56 }
  57
  58 bool
  59 JSONParser::errorReturn()
  60 {
  61     return errorHandling == NoError;
  62 }
  63
  64 template<JSONParser::StringType ST>
  65 JSONParser::Token
  66 JSONParser::readString()
  67 {
  68     JS_ASSERT(current < end);
  69     JS_ASSERT(*current == '"');
  70
  71     /*
  72      * JSONString:
  73      *   /^"([^\u0000-\u001F"\\]|\\(["/\\bfnrt]|u[0-9a-fA-F]{4}))*"$/
  74      */
  75
  76     if (++current == end) {
  77         error("unterminated string literal");
  78         return token(Error);
  79     }
  80
  81     /*
  82      * Optimization: if the source contains no escaped characters, create the
  83      * string directly from the source text.
  84      */
  85     RangedPtr<const jschar> start = current;
  86     for (; current < end; current++) {
  87         if (*current == '"') {
  88             size_t length = current - start;
  89             current++;
  90             JSFlatString *str = (ST == JSONParser::PropertyName)
  91                                 ? js_AtomizeChars(cx, start.get(), length)
  92                                 : js_NewStringCopyN(cx, start.get(), length);
  93             if (!str)
  94                 return token(OOM);
  95             return stringToken(str);
  96         }
  97
  98         if (*current == '\\')
  99             break;
 100
 101         if (*current <= 0x001F) {
 102             error("bad control character in string literal");
 103             return token(Error);
 104         }
 105     }
 106
 107     /*
 108      * Slow case: string contains escaped characters.  Copy a maximal sequence
 109      * of unescaped characters into a temporary buffer, then an escaped
 110      * character, and repeat until the entire string is consumed.
 111      */
 112     StringBuffer buffer(cx);
 113     do {
 114         if (start < current && !buffer.append(start.get(), current.get()))
 115             return token(OOM);
 116
 117         if (current >= end)
 118             break;
 119
 120         jschar c = *current++;
 121         if (c == '"') {
 122             JSFlatString *str = (ST == JSONParser::PropertyName)
 123                                 ? buffer.finishAtom()
 124                                 : buffer.finishString();
 125             if (!str)
 126                 return token(OOM);
 127             return stringToken(str);
 128         }
 129
 130         if (c != '\\') {
 131             error("bad character in string literal");
 132             return token(Error);
 133         }
 134
 135         if (current >= end)
 136             break;
 137
 138         switch (*current++) {
 139           case '"':  c = '"';  break;
 140           case '/':  c = '/';  break;
 141           case '\\': c = '\\'; break;
 142           case 'b':  c = '\b'; break;
 143           case 'f':  c = '\f'; break;
 144           case 'n':  c = '\n'; break;
 145           case 'r':  c = '\r'; break;
 146           case 't':  c = '\t'; break;
 147
 148           case 'u':
 149             if (end - current < 4) {
 150                 error("bad Unicode escape");
 151                 return token(Error);
 152             }
 153             if (JS7_ISHEX(current[0]) &&
 154                 JS7_ISHEX(current[1]) &&
 155                 JS7_ISHEX(current[2]) &&
 156                 JS7_ISHEX(current[3]))
 157             {
 158                 c = (JS7_UNHEX(current[0]) << 12)
 159                   | (JS7_UNHEX(current[1]) << 8)
 160                   | (JS7_UNHEX(current[2]) << 4)
 161                   | (JS7_UNHEX(current[3]));
 162                 current += 4;
 163                 break;
 164             }
 165             /* FALL THROUGH */
 166
 167           default:
 168             error("bad escaped character");
 169             return token(Error);
 170         }
 171         if (!buffer.append(c))
 172             return token(OOM);
 173
 174         start = current;
 175         for (; current < end; current++) {
 176             if (*current == '"' || *current == '\\' || *current <= 0x001F)
 177                 break;
 178         }
 179     } while (current < end);
 180
 181     error("unterminated string");
 182     return token(Error);
 183 }
 184
 185 JSONParser::Token
 186 JSONParser::readNumber()
 187 {
 188     JS_ASSERT(current < end);
 189     JS_ASSERT(JS7_ISDEC(*current) || *current == '-');
 190
 191     /*
 192      * JSONNumber:
 193      *   /^-?(0|[1-9][0-9]+)(\.[0-9]+)?([eE][\+\-]?[0-9]+)?$/
 194      */
 195
 196     bool negative = *current == '-';
 197
 198     /* -? */
 199     if (negative && ++current == end) {
 200         error("no number after minus sign");
 201         return token(Error);
 202     }
 203
 204     const RangedPtr<const jschar> digitStart = current;
 205
 206     /* 0|[1-9][0-9]+ */
 207     if (!JS7_ISDEC(*current)) {
 208         error("unexpected non-digit");
 209         return token(Error);
 210     }
 211     if (*current++ != '0') {
 212         for (; current < end; current++) {
 213             if (!JS7_ISDEC(*current))
 214                 break;
 215         }
 216     }
 217
 218     /* Fast path: no fractional or exponent part. */
 219     if (current == end || (*current != '.' && *current != 'e' && *current != 'E')) {
 220         const jschar *dummy;
 221         double d;
 222         if (!GetPrefixInteger(cx, digitStart.get(), current.get(), 10, &dummy, &d))
 223             return token(OOM);
 224         JS_ASSERT(current == dummy);
 225         return numberToken(negative ? -d : d);
 226     }
 227
 228     /* (\.[0-9]+)? */
 229     if (current < end && *current == '.') {
 230         if (++current == end) {
 231             error("missing digits after decimal point");
 232             return token(Error);
 233         }
 234         if (!JS7_ISDEC(*current)) {
 235             error("unterminated fractional number");
 236             return token(Error);
 237         }
 238         while (++current < end) {
 239             if (!JS7_ISDEC(*current))
 240                 break;
 241         }
 242     }
 243
 244     /* ([eE][\+\-]?[0-9]+)? */
 245     if (current < end && (*current == 'e' || *current == 'E')) {
 246         if (++current == end) {
 247             error("missing digits after exponent indicator");
 248             return token(Error);
 249         }
 250         if (*current == '+' || *current == '-') {
 251             if (++current == end) {
 252                 error("missing digits after exponent sign");
 253                 return token(Error);
 254             }
 255         }
 256         if (!JS7_ISDEC(*current)) {
 257             error("exponent part is missing a number");
 258             return token(Error);
 259         }
 260         while (++current < end) {
 261             if (!JS7_ISDEC(*current))
 262                 break;
 263         }
 264     }
 265
 266     double d;
 267     const jschar *finish;
 268     if (!js_strtod(cx, digitStart.get(), current.get(), &finish, &d))
 269         return token(OOM);
 270     JS_ASSERT(current == finish);
 271     return numberToken(negative ? -d : d);
 272 }
 273
 274 static inline bool
 275 IsJSONWhitespace(jschar c)
 276 {
 277     return c == '\t' || c == '\r' || c == '\n' || c == ' ';
 278 }
 279
 280 JSONParser::Token
 281 JSONParser::advance()
 282 {
 283     while (current < end && IsJSONWhitespace(*current))
 284         current++;
 285     if (current >= end) {
 286         error("unexpected end of data");
 287         return token(Error);
 288     }
 289
 290     switch (*current) {
 291       case '"':
 292         return readString<LiteralValue>();
 293
 294       case '-':
 295       case '0':
 296       case '1':
 297       case '2':
 298       case '3':
 299       case '4':
 300       case '5':
 301       case '6':
 302       case '7':
 303       case '8':
 304       case '9':
 305         return readNumber();
 306
 307       case 't':
 308         if (end - current < 4 || current[1] != 'r' || current[2] != 'u' || current[3] != 'e') {
 309             error("unexpected keyword");
 310             return token(Error);
 311         }
 312         current += 4;
 313         return token(True);
 314
 315       case 'f':
 316         if (end - current < 5 ||
 317             current[1] != 'a' || current[2] != 'l' || current[3] != 's' || current[4] != 'e')
 318         {
 319             error("unexpected keyword");
 320             return token(Error);
 321         }
 322         current += 5;
 323         return token(False);
 324
 325       case 'n':
 326         if (end - current < 4 || current[1] != 'u' || current[2] != 'l' || current[3] != 'l') {
 327             error("unexpected keyword");
 328             return token(Error);
 329         }
 330         current += 4;
 331         return token(Null);
 332
 333       case '[':
 334         current++;
 335         return token(ArrayOpen);
 336       case ']':
 337         current++;
 338         return token(ArrayClose);
 339
 340       case '{':
 341         current++;
 342         return token(ObjectOpen);
 343       case '}':
 344         current++;
 345         return token(ObjectClose);
 346
 347       case ',':
 348         current++;
 349         return token(Comma);
 350
 351       case ':':
 352         current++;
 353         return token(Colon);
 354
 355       default:
 356         error("unexpected character");
 357         return token(Error);
 358     }
 359 }
 360
 361 JSONParser::Token
 362 JSONParser::advanceAfterObjectOpen()
 363 {
 364     JS_ASSERT(current[-1] == '{');
 365
 366     while (current < end && IsJSONWhitespace(*current))
 367         current++;
 368     if (current >= end) {
 369         error("end of data while reading object contents");
 370         return token(Error);
 371     }
 372
 373     if (*current == '"')
 374         return readString<PropertyName>();
 375
 376     if (*current == '}') {
 377         current++;
 378         return token(ObjectClose);
 379     }
 380
 381     error("expected property name or '}'");
 382     return token(Error);
 383 }
 384
 385 static inline void
 386 AssertPastValue(const RangedPtr<const jschar> current)
 387 {
 388     /*
 389      * We're past an arbitrary JSON value, so the previous character is
 390      * *somewhat* constrained, even if this assertion is pretty broad.  Don't
 391      * knock it till you tried it: this assertion *did* catch a bug once.
 392      */
 393     JS_ASSERT((current[-1] == 'l' &&
 394                current[-2] == 'l' &&
 395                current[-3] == 'u' &&
 396                current[-4] == 'n') ||
 397               (current[-1] == 'e' &&
 398                current[-2] == 'u' &&
 399                current[-3] == 'r' &&
 400                current[-4] == 't') ||
 401               (current[-1] == 'e' &&
 402                current[-2] == 's' &&
 403                current[-3] == 'l' &&
 404                current[-4] == 'a' &&
 405                current[-5] == 'f') ||
 406               current[-1] == '}' ||
 407               current[-1] == ']' ||
 408               current[-1] == '"' ||
 409               JS7_ISDEC(current[-1]));
 410 }
 411
 412 JSONParser::Token
 413 JSONParser::advanceAfterArrayElement()
 414 {
 415     AssertPastValue(current);
 416
 417     while (current < end && IsJSONWhitespace(*current))
 418         current++;
 419     if (current >= end) {
 420         error("end of data when ',' or ']' was expected");
 421         return token(Error);
 422     }
 423
 424     if (*current == ',') {
 425         current++;
 426         return token(Comma);
 427     }
 428
 429     if (*current == ']') {
 430         current++;
 431         return token(ArrayClose);
 432     }
 433
 434     error("expected ',' or ']' after array element");
 435     return token(Error);
 436 }
 437
 438 JSONParser::Token
 439 JSONParser::advancePropertyName()
 440 {
 441     JS_ASSERT(current[-1] == ',');
 442
 443     while (current < end && IsJSONWhitespace(*current))
 444         current++;
 445     if (current >= end) {
 446         error("end of data when property name was expected");
 447         return token(Error);
 448     }
 449
 450     if (*current == '"')
 451         return readString<PropertyName>();
 452
 453     if (parsingMode == LegacyJSON && *current == '}') {
 454         /*
 455          * Previous JSON parsing accepted trailing commas in non-empty object
 456          * syntax, and some users depend on this.  (Specifically, Places data
 457          * serialization in versions of Firefox before 4.0.  We can remove this
 458          * mode when profile upgrades from 3.6 become unsupported.)  Permit
 459          * such trailing commas only when legacy parsing is specifically
 460          * requested.
 461          */
 462         current++;
 463         return token(ObjectClose);
 464     }
 465
 466     error("expected double-quoted property name");
 467     return token(Error);
 468 }
 469
 470 JSONParser::Token
 471 JSONParser::advancePropertyColon()
 472 {
 473     JS_ASSERT(current[-1] == '"');
 474
 475     while (current < end && IsJSONWhitespace(*current))
 476         current++;
 477     if (current >= end) {
 478         error("end of data after property name when ':' was expected");
 479         return token(Error);
 480     }
 481
 482     if (*current == ':') {
 483         current++;
 484         return token(Colon);
 485     }
 486
 487     error("expected ':' after property name in object");
 488     return token(Error);
 489 }
 490
 491 JSONParser::Token
 492 JSONParser::advanceAfterProperty()
 493 {
 494     AssertPastValue(current);
 495
 496     while (current < end && IsJSONWhitespace(*current))
 497         current++;
 498     if (current >= end) {
 499         error("end of data after property value in object");
 500         return token(Error);
 501     }
 502
 503     if (*current == ',') {
 504         current++;
 505         return token(Comma);
 506     }
 507
 508     if (*current == '}') {
 509         current++;
 510         return token(ObjectClose);
 511     }
 512
 513     error("expected ',' or '}' after property value in object");
 514     return token(Error);
 515 }
 516
 517 /*
 518  * This enum is local to JSONParser::parse, below, but ISO C++98 doesn't allow
 519  * templates to depend on local types.  Boo-urns!
 520  */
 521 enum ParserState { FinishArrayElement, FinishObjectMember, JSONValue };
 522
 523 bool
 524 JSONParser::parse(Value *vp)
 525 {
 526     Vector<ParserState> stateStack(cx);
 527     AutoValueVector valueStack(cx);
 528
 529     *vp = UndefinedValue();
 530
 531     Token token;
 532     ParserState state = JSONValue;
 533     while (true) {
 534         switch (state) {
 535           case FinishObjectMember: {
 536             Value v = valueStack.popCopy();
 537             jsid propid = AtomToId(&valueStack.popCopy().toString()->asAtom());
 538             RootedVarObject obj(cx, &valueStack.back().toObject());
 539             if (!DefineNativeProperty(cx, obj, propid, v,
 540                                       JS_PropertyStub, JS_StrictPropertyStub, JSPROP_ENUMERATE,
 541                                       0, 0))
 542             {
 543                 return false;
 544             }
 545             token = advanceAfterProperty();
 546             if (token == ObjectClose)
 547                 break;
 548             if (token != Comma) {
 549                 if (token == OOM)
 550                     return false;
 551                 if (token != Error)
 552                     error("expected ',' or '}' after property-value pair in object literal");
 553                 return errorReturn();
 554             }
 555             token = advancePropertyName();
 556             /* FALL THROUGH */
 557           }
 558
 559           JSONMember:
 560             if (token == String) {
 561                 if (!valueStack.append(atomValue()))
 562                     return false;
 563                 token = advancePropertyColon();
 564                 if (token != Colon) {
 565                     JS_ASSERT(token == Error);
 566                     return errorReturn();
 567                 }
 568                 if (!stateStack.append(FinishObjectMember))
 569                     return false;
 570                 goto JSONValue;
 571             }
 572             if (token == ObjectClose) {
 573                 JS_ASSERT(state == FinishObjectMember);
 574                 JS_ASSERT(parsingMode == LegacyJSON);
 575                 break;
 576             }
 577             if (token == OOM)
 578                 return false;
 579             if (token != Error)
 580                 error("property names must be double-quoted strings");
 581             return errorReturn();
 582
 583           case FinishArrayElement: {
 584             Value v = valueStack.popCopy();
 585             if (!js_NewbornArrayPush(cx, &valueStack.back().toObject(), v))
 586                 return false;
 587             token = advanceAfterArrayElement();
 588             if (token == Comma) {
 589                 if (!stateStack.append(FinishArrayElement))
 590                     return false;
 591                 goto JSONValue;
 592             }
 593             if (token == ArrayClose)
 594                 break;
 595             JS_ASSERT(token == Error);
 596             return errorReturn();
 597           }
 598
 599           JSONValue:
 600           case JSONValue:
 601             token = advance();
 602           JSONValueSwitch:
 603             switch (token) {
 604               case String:
 605               case Number:
 606                 if (!valueStack.append(token == String ? stringValue() : numberValue()))
 607                     return false;
 608                 break;
 609               case True:
 610                 if (!valueStack.append(BooleanValue(true)))
 611                     return false;
 612                 break;
 613               case False:
 614                 if (!valueStack.append(BooleanValue(false)))
 615                     return false;
 616                 break;
 617               case Null:
 618                 if (!valueStack.append(NullValue()))
 619                     return false;
 620                 break;
 621
 622               case ArrayOpen: {
 623                 JSObject *obj = NewDenseEmptyArray(cx);
 624                 if (!obj || !valueStack.append(ObjectValue(*obj)))
 625                     return false;
 626                 token = advance();
 627                 if (token == ArrayClose)
 628                     break;
 629                 if (!stateStack.append(FinishArrayElement))
 630                     return false;
 631                 goto JSONValueSwitch;
 632               }
 633
 634               case ObjectOpen: {
 635                 JSObject *obj = NewBuiltinClassInstance(cx, &ObjectClass);
 636                 if (!obj || !valueStack.append(ObjectValue(*obj)))
 637                     return false;
 638                 token = advanceAfterObjectOpen();
 639                 if (token == ObjectClose)
 640                     break;
 641                 goto JSONMember;
 642               }
 643
 644               case ArrayClose:
 645                 if (parsingMode == LegacyJSON &&
 646                     !stateStack.empty() &&
 647                     stateStack.back() == FinishArrayElement) {
 648                     /*
 649                      * Previous JSON parsing accepted trailing commas in
 650                      * non-empty array syntax, and some users depend on this.
 651                      * (Specifically, Places data serialization in versions of
 652                      * Firefox prior to 4.0.  We can remove this mode when
 653                      * profile upgrades from 3.6 become unsupported.)  Permit
 654                      * such trailing commas only when specifically
 655                      * instructed to do so.
 656                      */
 657                     stateStack.popBack();
 658                     break;
 659                 }
 660                 /* FALL THROUGH */
 661
 662               case ObjectClose:
 663               case Colon:
 664               case Comma:
 665                 error("unexpected character");
 666                 return errorReturn();
 667
 668               case OOM:
 669                 return false;
 670
 671               case Error:
 672                 return errorReturn();
 673             }
 674             break;
 675         }
 676
 677         if (stateStack.empty())
 678             break;
 679         state = stateStack.popCopy();
 680     }
 681
 682     for (; current < end; current++) {
 683         if (!IsJSONWhitespace(*current)) {
 684             error("unexpected non-whitespace character after JSON data");
 685             return errorReturn();
 686         }
 687     }
 688
 689     JS_ASSERT(end == current);
 690     JS_ASSERT(valueStack.length() == 1);
 691     *vp = valueStack[0];
 692     return true;
 693 }