js/src/json.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  * Mozilla Corporation.
  21  * Portions created by the Initial Developer are Copyright (C) 1998-1999
  22  * the Initial Developer. All Rights Reserved.
  23  *
  24  * Contributor(s):
  25  *   Robert Sayre <sayrer@gmail.com>
  26  *   Dave Camp <dcamp@mozilla.com>
  27  *
  28  * Alternatively, the contents of this file may be used under the terms of
  29  * either of the GNU General Public License Version 2 or later (the "GPL"),
  30  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  31  * in which case the provisions of the GPL or the LGPL are applicable instead
  32  * of those above. If you wish to allow use of your version of this file only
  33  * under the terms of either the GPL or the LGPL, and not to allow others to
  34  * use your version of this file under the terms of the MPL, indicate your
  35  * decision by deleting the provisions above and replace them with the notice
  36  * and other provisions required by the GPL or the LGPL. If you do not delete
  37  * the provisions above, a recipient may use your version of this file under
  38  * the terms of any one of the MPL, the GPL or the LGPL.
  39  *
  40  * ***** END LICENSE BLOCK ***** */
  41
  42 #include <string.h>
  43 #include "jsapi.h"
  44 #include "jsarena.h"
  45 #include "jsarray.h"
  46 #include "jsatom.h"
  47 #include "jsbool.h"
  48 #include "jscntxt.h"
  49 #include "jsdtoa.h"
  50 #include "jsfun.h"
  51 #include "jsinterp.h"
  52 #include "jsiter.h"
  53 #include "jsnum.h"
  54 #include "jsobj.h"
  55 #include "jsprf.h"
  56 #include "jsscan.h"
  57 #include "jsstr.h"
  58 #include "jstypes.h"
  59 #include "jsstdint.h"
  60 #include "jsutil.h"
  61 #include "jsxml.h"
  62 #include "jsvector.h"
  63
  64 #include "json.h"
  65
  66 #include "jsatominlines.h"
  67 #include "jsobjinlines.h"
  68
  69 using namespace js;
  70
  71 #ifdef _MSC_VER
  72 #pragma warning(push)
  73 #pragma warning(disable:4351)
  74 #endif
  75
  76 struct JSONParser
  77 {
  78     JSONParser(JSContext *cx)
  79      : hexChar(), numHex(), statep(), stateStack(), rootVal(), objectStack(),
  80        objectKey(cx), buffer(cx), suppressErrors(false)
  81     {}
  82
  83     /* Used while handling \uNNNN in strings */
  84     jschar hexChar;
  85     uint8 numHex;
  86
  87     JSONParserState *statep;
  88     JSONParserState stateStack[JSON_MAX_DEPTH];
  89     Value *rootVal;
  90     JSObject *objectStack;
  91     js::Vector<jschar, 8> objectKey;
  92     js::Vector<jschar, 8> buffer;
  93     bool suppressErrors;
  94 };
  95
  96 #ifdef _MSC_VER
  97 #pragma warning(pop)
  98 #endif
  99
 100 Class js_JSONClass = {
 101     js_JSON_str,
 102     JSCLASS_HAS_CACHED_PROTO(JSProto_JSON),
 103     PropertyStub,   /* addProperty */
 104     PropertyStub,   /* delProperty */
 105     PropertyStub,   /* getProperty */
 106     PropertyStub,   /* setProperty */
 107     EnumerateStub,
 108     ResolveStub,
 109     ConvertStub
 110 };
 111
 112 JSBool
 113 js_json_parse(JSContext *cx, uintN argc, Value *vp)
 114 {
 115     JSString *s = NULL;
 116     Value *argv = vp + 2;
 117     AutoValueRooter reviver(cx);
 118
 119     if (!JS_ConvertArguments(cx, argc, Jsvalify(argv), "S / v", &s, reviver.addr()))
 120         return JS_FALSE;
 121
 122     JSONParser *jp = js_BeginJSONParse(cx, vp);
 123     JSBool ok = jp != NULL;
 124     if (ok) {
 125         const jschar *chars;
 126         size_t length;
 127         s->getCharsAndLength(chars, length);
 128         ok = js_ConsumeJSONText(cx, jp, chars, length);
 129         ok &= !!js_FinishJSONParse(cx, jp, reviver.value());
 130     }
 131
 132     return ok;
 133 }
 134
 135 JSBool
 136 js_json_stringify(JSContext *cx, uintN argc, Value *vp)
 137 {
 138     Value *argv = vp + 2;
 139     AutoValueRooter space(cx);
 140     AutoObjectRooter replacer(cx);
 141
 142     // Must throw an Error if there isn't a first arg
 143     if (!JS_ConvertArguments(cx, argc, Jsvalify(argv), "v / o v", vp, replacer.addr(), space.addr()))
 144         return JS_FALSE;
 145
 146     JSCharBuffer cb(cx);
 147
 148     if (!js_Stringify(cx, vp, replacer.object(), space.value(), cb))
 149         return JS_FALSE;
 150
 151     // XXX This can never happen to nsJSON.cpp, but the JSON object
 152     // needs to support returning undefined. So this is a little awkward
 153     // for the API, because we want to support streaming writers.
 154     if (!cb.empty()) {
 155         JSString *str = js_NewStringFromCharBuffer(cx, cb);
 156         if (!str)
 157             return JS_FALSE;
 158         vp->setString(str);
 159     } else {
 160         vp->setUndefined();
 161     }
 162
 163     return JS_TRUE;
 164 }
 165
 166 JSBool
 167 js_TryJSON(JSContext *cx, Value *vp)
 168 {
 169     // Checks whether the return value implements toJSON()
 170     JSBool ok = JS_TRUE;
 171
 172     if (vp->isObject()) {
 173         JSObject *obj = &vp->toObject();
 174         ok = js_TryMethod(cx, obj, cx->runtime->atomState.toJSONAtom, 0, NULL, vp);
 175     }
 176
 177     return ok;
 178 }
 179
 180
 181 static const char quote = '\"';
 182 static const char backslash = '\\';
 183 static const char unicodeEscape[] = "\\u00";
 184
 185 static JSBool
 186 write_string(JSContext *cx, JSCharBuffer &cb, const jschar *buf, uint32 len)
 187 {
 188     if (!cb.append(quote))
 189         return JS_FALSE;
 190
 191     uint32 mark = 0;
 192     uint32 i;
 193     for (i = 0; i < len; ++i) {
 194         if (buf[i] == quote || buf[i] == backslash) {
 195             if (!cb.append(&buf[mark], i - mark) || !cb.append(backslash) ||
 196                 !cb.append(buf[i])) {
 197                 return JS_FALSE;
 198             }
 199             mark = i + 1;
 200         } else if (buf[i] <= 31 || buf[i] == 127) {
 201             if (!cb.append(&buf[mark], i - mark) ||
 202                 !js_AppendLiteral(cb, unicodeEscape)) {
 203                 return JS_FALSE;
 204             }
 205             char ubuf[3];
 206             size_t len = JS_snprintf(ubuf, sizeof(ubuf), "%.2x", buf[i]);
 207             JS_ASSERT(len == 2);
 208             jschar wbuf[3];
 209             size_t wbufSize = JS_ARRAY_LENGTH(wbuf);
 210             if (!js_InflateStringToBuffer(cx, ubuf, len, wbuf, &wbufSize) ||
 211                 !cb.append(wbuf, wbufSize)) {
 212                 return JS_FALSE;
 213             }
 214             mark = i + 1;
 215         }
 216     }
 217
 218     if (mark < len && !cb.append(&buf[mark], len - mark))
 219         return JS_FALSE;
 220
 221     return cb.append(quote);
 222 }
 223
 224 class StringifyContext
 225 {
 226 public:
 227     StringifyContext(JSContext *cx, JSCharBuffer &cb, JSObject *replacer)
 228     : cb(cb), gap(cx), replacer(replacer), depth(0), objectStack(cx)
 229     {}
 230
 231     bool initializeGap(JSContext *cx, const Value &space) {
 232         AutoValueRooter gapValue(cx, space);
 233
 234         if (space.isObject()) {
 235             JSObject &obj = space.toObject();
 236             Class *clasp = obj.getClass();
 237             if (clasp == &js_NumberClass || clasp == &js_StringClass)
 238                 *gapValue.addr() = obj.getPrimitiveThis();
 239         }
 240
 241         if (gapValue.value().isString()) {
 242             if (!js_ValueToCharBuffer(cx, gapValue.value(), gap))
 243                 return false;
 244             if (gap.length() > 10)
 245                 gap.resize(10);
 246         } else if (gapValue.value().isNumber()) {
 247             jsdouble d = gapValue.value().isInt32()
 248                          ? gapValue.value().toInt32()
 249                          : js_DoubleToInteger(gapValue.value().toDouble());
 250             d = JS_MIN(10, d);
 251             if (d >= 1 && !gap.appendN(' ', uint32(d)))
 252                 return false;
 253         }
 254
 255         return true;
 256     }
 257
 258     bool initializeStack() {
 259         return objectStack.init(16);
 260     }
 261
 262 #ifdef DEBUG
 263     ~StringifyContext() { JS_ASSERT(objectStack.empty()); }
 264 #endif
 265
 266     JSCharBuffer &cb;
 267     JSCharBuffer gap;
 268     JSObject *replacer;
 269     uint32 depth;
 270     HashSet<JSObject *> objectStack;
 271 };
 272
 273 static JSBool CallReplacerFunction(JSContext *cx, jsid id, JSObject *holder,
 274                                    StringifyContext *scx, Value *vp);
 275 static JSBool Str(JSContext *cx, jsid id, JSObject *holder,
 276                   StringifyContext *scx, Value *vp, bool callReplacer = true);
 277
 278 static JSBool
 279 WriteIndent(JSContext *cx, StringifyContext *scx, uint32 limit)
 280 {
 281     if (!scx->gap.empty()) {
 282         if (!scx->cb.append('\n'))
 283             return JS_FALSE;
 284         for (uint32 i = 0; i < limit; i++) {
 285             if (!scx->cb.append(scx->gap.begin(), scx->gap.end()))
 286                 return JS_FALSE;
 287         }
 288     }
 289
 290     return JS_TRUE;
 291 }
 292
 293 class CycleDetector
 294 {
 295   public:
 296     CycleDetector(StringifyContext *scx, JSObject *obj)
 297       : objectStack(scx->objectStack), obj(obj) {
 298     }
 299
 300     bool init(JSContext *cx) {
 301         HashSet<JSObject *>::AddPtr ptr = objectStack.lookupForAdd(obj);
 302         if (ptr) {
 303             JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_CYCLIC_VALUE, js_object_str);
 304             return false;
 305         }
 306         return objectStack.add(ptr, obj);
 307     }
 308
 309     ~CycleDetector() {
 310         objectStack.remove(obj);
 311     }
 312
 313   private:
 314     HashSet<JSObject *> &objectStack;
 315     JSObject *const obj;
 316 };
 317
 318 static JSBool
 319 JO(JSContext *cx, Value *vp, StringifyContext *scx)
 320 {
 321     JSObject *obj = &vp->toObject();
 322
 323     CycleDetector detect(scx, obj);
 324     if (!detect.init(cx))
 325         return JS_FALSE;
 326
 327     if (!scx->cb.append('{'))
 328         return JS_FALSE;
 329
 330     Value vec[3] = { NullValue(), NullValue(), NullValue() };
 331     AutoArrayRooter tvr(cx, JS_ARRAY_LENGTH(vec), vec);
 332     Value& outputValue = vec[0];
 333     Value& whitelistElement = vec[1];
 334     AutoIdRooter idr(cx);
 335     jsid& id = *idr.addr();
 336
 337     Value *keySource = vp;
 338     bool usingWhitelist = false;
 339
 340     // if the replacer is an array, we use the keys from it
 341     if (scx->replacer && JS_IsArrayObject(cx, scx->replacer)) {
 342         usingWhitelist = true;
 343         vec[2].setObject(*scx->replacer);
 344         keySource = &vec[2];
 345     }
 346
 347     JSBool memberWritten = JS_FALSE;
 348     AutoIdVector props(cx);
 349     if (!GetPropertyNames(cx, &keySource->toObject(), JSITER_OWNONLY, props))
 350         return JS_FALSE;
 351
 352     for (size_t i = 0, len = props.length(); i < len; i++) {
 353         outputValue.setUndefined();
 354
 355         if (!usingWhitelist) {
 356             if (!js_ValueToStringId(cx, IdToValue(props[i]), &id))
 357                 return JS_FALSE;
 358         } else {
 359             // skip non-index properties
 360             jsuint index = 0;
 361             if (!js_IdIsIndex(props[i], &index))
 362                 continue;
 363
 364             if (!scx->replacer->getProperty(cx, props[i], &whitelistElement))
 365                 return JS_FALSE;
 366
 367             if (!js_ValueToStringId(cx, whitelistElement, &id))
 368                 return JS_FALSE;
 369         }
 370
 371         // We should have a string id by this point. Either from
 372         // JS_Enumerate's id array, or by converting an element
 373         // of the whitelist.
 374         JS_ASSERT(JSID_IS_ATOM(id));
 375
 376         if (!JS_GetPropertyById(cx, obj, id, Jsvalify(&outputValue)))
 377             return JS_FALSE;
 378
 379         if (outputValue.isObjectOrNull() && !js_TryJSON(cx, &outputValue))
 380             return JS_FALSE;
 381
 382         // call this here, so we don't write out keys if the replacer function
 383         // wants to elide the value.
 384         if (!CallReplacerFunction(cx, id, obj, scx, &outputValue))
 385             return JS_FALSE;
 386
 387         JSType type = JS_TypeOfValue(cx, Jsvalify(outputValue));
 388
 389         // elide undefined values and functions and XML
 390         if (outputValue.isUndefined() || type == JSTYPE_FUNCTION || type == JSTYPE_XML)
 391             continue;
 392
 393         // output a comma unless this is the first member to write
 394         if (memberWritten && !scx->cb.append(','))
 395             return JS_FALSE;
 396         memberWritten = JS_TRUE;
 397
 398         if (!WriteIndent(cx, scx, scx->depth))
 399             return JS_FALSE;
 400
 401         // Be careful below, this string is weakly rooted
 402         JSString *s = js_ValueToString(cx, IdToValue(id));
 403         if (!s)
 404             return JS_FALSE;
 405
 406         const jschar *chars;
 407         size_t length;
 408         s->getCharsAndLength(chars, length);
 409         if (!write_string(cx, scx->cb, chars, length) ||
 410             !scx->cb.append(':') ||
 411             !(scx->gap.empty() || scx->cb.append(' ')) ||
 412             !Str(cx, id, obj, scx, &outputValue, true)) {
 413             return JS_FALSE;
 414         }
 415     }
 416
 417     if (memberWritten && !WriteIndent(cx, scx, scx->depth - 1))
 418         return JS_FALSE;
 419
 420     return scx->cb.append('}');
 421 }
 422
 423 static JSBool
 424 JA(JSContext *cx, Value *vp, StringifyContext *scx)
 425 {
 426     JSObject *obj = &vp->toObject();
 427
 428     CycleDetector detect(scx, obj);
 429     if (!detect.init(cx))
 430         return JS_FALSE;
 431
 432     if (!scx->cb.append('['))
 433         return JS_FALSE;
 434
 435     jsuint length;
 436     if (!js_GetLengthProperty(cx, obj, &length))
 437         return JS_FALSE;
 438
 439     if (length != 0 && !WriteIndent(cx, scx, scx->depth))
 440         return JS_FALSE;
 441
 442     AutoValueRooter outputValue(cx);
 443
 444     jsid id;
 445     jsuint i;
 446     for (i = 0; i < length; i++) {
 447         id = INT_TO_JSID(i);
 448
 449         if (!obj->getProperty(cx, id, outputValue.addr()))
 450             return JS_FALSE;
 451
 452         if (!Str(cx, id, obj, scx, outputValue.addr()))
 453             return JS_FALSE;
 454
 455         if (outputValue.value().isUndefined()) {
 456             if (!js_AppendLiteral(scx->cb, "null"))
 457                 return JS_FALSE;
 458         }
 459
 460         if (i < length - 1) {
 461             if (!scx->cb.append(','))
 462                 return JS_FALSE;
 463             if (!WriteIndent(cx, scx, scx->depth))
 464                 return JS_FALSE;
 465         }
 466     }
 467
 468     if (length != 0 && !WriteIndent(cx, scx, scx->depth - 1))
 469         return JS_FALSE;
 470
 471     return scx->cb.append(']');
 472 }
 473
 474 static JSBool
 475 CallReplacerFunction(JSContext *cx, jsid id, JSObject *holder, StringifyContext *scx, Value *vp)
 476 {
 477     if (scx->replacer && scx->replacer->isCallable()) {
 478         Value vec[2] = { IdToValue(id), *vp};
 479         if (!JS_CallFunctionValue(cx, holder, OBJECT_TO_JSVAL(scx->replacer),
 480                                   2, Jsvalify(vec), Jsvalify(vp))) {
 481             return JS_FALSE;
 482         }
 483     }
 484
 485     return JS_TRUE;
 486 }
 487
 488 static JSBool
 489 Str(JSContext *cx, jsid id, JSObject *holder, StringifyContext *scx, Value *vp, bool callReplacer)
 490 {
 491     JS_CHECK_RECURSION(cx, return JS_FALSE);
 492
 493     if (vp->isObject() && !js_TryJSON(cx, vp))
 494         return JS_FALSE;
 495
 496     if (callReplacer && !CallReplacerFunction(cx, id, holder, scx, vp))
 497         return JS_FALSE;
 498
 499     // catches string and number objects with no toJSON
 500     if (vp->isObject()) {
 501         JSObject *obj = &vp->toObject();
 502         Class *clasp = obj->getClass();
 503         if (clasp == &js_StringClass || clasp == &js_NumberClass)
 504             *vp = obj->getPrimitiveThis();
 505     }
 506
 507     if (vp->isString()) {
 508         const jschar *chars;
 509         size_t length;
 510         vp->toString()->getCharsAndLength(chars, length);
 511         return write_string(cx, scx->cb, chars, length);
 512     }
 513
 514     if (vp->isNull()) {
 515         return js_AppendLiteral(scx->cb, "null");
 516     }
 517
 518     if (vp->isBoolean()) {
 519         return vp->toBoolean() ? js_AppendLiteral(scx->cb, "true")
 520                                : js_AppendLiteral(scx->cb, "false");
 521     }
 522
 523     if (vp->isNumber()) {
 524         if (vp->isDouble()) {
 525             jsdouble d = vp->toDouble();
 526             if (!JSDOUBLE_IS_FINITE(d))
 527                 return js_AppendLiteral(scx->cb, "null");
 528         }
 529
 530         char numBuf[DTOSTR_STANDARD_BUFFER_SIZE], *numStr;
 531         jsdouble d = vp->isInt32() ? jsdouble(vp->toInt32()) : vp->toDouble();
 532         numStr = js_dtostr(JS_THREAD_DATA(cx)->dtoaState, numBuf, sizeof numBuf,
 533                            DTOSTR_STANDARD, 0, d);
 534         if (!numStr) {
 535             JS_ReportOutOfMemory(cx);
 536             return JS_FALSE;
 537         }
 538
 539         jschar dstr[DTOSTR_STANDARD_BUFFER_SIZE];
 540         size_t dbufSize = DTOSTR_STANDARD_BUFFER_SIZE;
 541         if (!js_InflateStringToBuffer(cx, numStr, strlen(numStr), dstr, &dbufSize))
 542             return JS_FALSE;
 543
 544         return scx->cb.append(dstr, dbufSize);
 545     }
 546
 547     if (vp->isObject() && !IsFunctionObject(*vp) && !IsXML(*vp)) {
 548         JSBool ok;
 549
 550         scx->depth++;
 551         ok = (JS_IsArrayObject(cx, &vp->toObject()) ? JA : JO)(cx, vp, scx);
 552         scx->depth--;
 553
 554         return ok;
 555     }
 556
 557     vp->setUndefined();
 558     return JS_TRUE;
 559 }
 560
 561 JSBool
 562 js_Stringify(JSContext *cx, Value *vp, JSObject *replacer, const Value &space,
 563              JSCharBuffer &cb)
 564 {
 565     StringifyContext scx(cx, cb, replacer);
 566     if (!scx.initializeGap(cx, space) || !scx.initializeStack())
 567         return JS_FALSE;
 568
 569     JSObject *obj = NewBuiltinClassInstance(cx, &js_ObjectClass);
 570     if (!obj)
 571         return JS_FALSE;
 572
 573     AutoObjectRooter tvr(cx, obj);
 574     if (!obj->defineProperty(cx, ATOM_TO_JSID(cx->runtime->atomState.emptyAtom),
 575                              *vp, NULL, NULL, JSPROP_ENUMERATE)) {
 576         return JS_FALSE;
 577     }
 578
 579     return Str(cx, ATOM_TO_JSID(cx->runtime->atomState.emptyAtom), obj, &scx, vp);
 580 }
 581
 582 // helper to determine whether a character could be part of a number
 583 static JSBool IsNumChar(jschar c)
 584 {
 585     return ((c <= '9' && c >= '0') || c == '.' || c == '-' || c == '+' || c == 'e' || c == 'E');
 586 }
 587
 588 static JSBool HandleData(JSContext *cx, JSONParser *jp, JSONDataType type);
 589 static JSBool PopState(JSContext *cx, JSONParser *jp);
 590
 591 static bool
 592 Walk(JSContext *cx, jsid id, JSObject *holder, const Value &reviver, Value *vp)
 593 {
 594     JS_CHECK_RECURSION(cx, return false);
 595
 596     if (!holder->getProperty(cx, id, vp))
 597         return false;
 598
 599     JSObject *obj;
 600
 601     if (vp->isObject() && !(obj = &vp->toObject())->isCallable()) {
 602         AutoValueRooter propValue(cx);
 603
 604         if(obj->isArray()) {
 605             jsuint length = 0;
 606             if (!js_GetLengthProperty(cx, obj, &length))
 607                 return false;
 608
 609             for (jsuint i = 0; i < length; i++) {
 610                 jsid index;
 611                 if (!js_IndexToId(cx, i, &index))
 612                     return false;
 613
 614                 if (!Walk(cx, index, obj, reviver, propValue.addr()))
 615                     return false;
 616
 617                 if (!obj->defineProperty(cx, index, propValue.value(), NULL, NULL, JSPROP_ENUMERATE))
 618                     return false;
 619             }
 620         } else {
 621             AutoIdVector props(cx);
 622             if (!GetPropertyNames(cx, obj, JSITER_OWNONLY, props))
 623                 return false;
 624
 625             for (size_t i = 0, len = props.length(); i < len; i++) {
 626                 jsid idName = props[i];
 627                 if (!Walk(cx, idName, obj, reviver, propValue.addr()))
 628                     return false;
 629                 if (propValue.value().isUndefined()) {
 630                     if (!js_DeleteProperty(cx, obj, idName, propValue.addr()))
 631                         return false;
 632                 } else {
 633                     if (!obj->defineProperty(cx, idName, propValue.value(), NULL, NULL,
 634                                              JSPROP_ENUMERATE)) {
 635                         return false;
 636                     }
 637                 }
 638             }
 639         }
 640     }
 641
 642     // return reviver.call(holder, key, value);
 643     const Value &value = *vp;
 644     JSString *key = js_ValueToString(cx, IdToValue(id));
 645     if (!key)
 646         return false;
 647
 648     Value vec[2] = { StringValue(key), value };
 649     Value reviverResult;
 650     if (!JS_CallFunctionValue(cx, holder, Jsvalify(reviver),
 651                               2, Jsvalify(vec), Jsvalify(&reviverResult))) {
 652         return false;
 653     }
 654
 655     *vp = reviverResult;
 656     return true;
 657 }
 658
 659 static JSBool
 660 JSONParseError(JSONParser *jp, JSContext *cx)
 661 {
 662     if (!jp->suppressErrors)
 663         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_JSON_BAD_PARSE);
 664     return JS_FALSE;
 665 }
 666
 667 static bool
 668 Revive(JSContext *cx, const Value &reviver, Value *vp)
 669 {
 670
 671     JSObject *obj = NewBuiltinClassInstance(cx, &js_ObjectClass);
 672     if (!obj)
 673         return false;
 674
 675     AutoObjectRooter tvr(cx, obj);
 676     if (!obj->defineProperty(cx, ATOM_TO_JSID(cx->runtime->atomState.emptyAtom),
 677                              *vp, NULL, NULL, JSPROP_ENUMERATE)) {
 678         return false;
 679     }
 680
 681     return Walk(cx, ATOM_TO_JSID(cx->runtime->atomState.emptyAtom), obj, reviver, vp);
 682 }
 683
 684 JSONParser *
 685 js_BeginJSONParse(JSContext *cx, Value *rootVal, bool suppressErrors /*= false*/)
 686 {
 687     if (!cx)
 688         return NULL;
 689
 690     JSObject *arr = js_NewArrayObject(cx, 0, NULL);
 691     if (!arr)
 692         return NULL;
 693
 694     JSONParser *jp = cx->create<JSONParser>(cx);
 695     if (!jp)
 696         return NULL;
 697
 698     jp->objectStack = arr;
 699     if (!JS_AddNamedObjectRoot(cx, &jp->objectStack, "JSON parse stack"))
 700         goto bad;
 701
 702     jp->statep = jp->stateStack;
 703     *jp->statep = JSON_PARSE_STATE_INIT;
 704     jp->rootVal = rootVal;
 705     jp->suppressErrors = suppressErrors;
 706
 707     return jp;
 708
 709 bad:
 710     js_FinishJSONParse(cx, jp, NullValue());
 711     return NULL;
 712 }
 713
 714 bool
 715 js_FinishJSONParse(JSContext *cx, JSONParser *jp, const Value &reviver)
 716 {
 717     if (!jp)
 718         return true;
 719
 720     JSBool early_ok = JS_TRUE;
 721
 722     // Check for unprocessed primitives at the root. This doesn't happen for
 723     // strings because a closing quote triggers value processing.
 724     if ((jp->statep - jp->stateStack) == 1) {
 725         if (*jp->statep == JSON_PARSE_STATE_KEYWORD) {
 726             early_ok = HandleData(cx, jp, JSON_DATA_KEYWORD);
 727             if (early_ok)
 728                 PopState(cx, jp);
 729         } else if (*jp->statep == JSON_PARSE_STATE_NUMBER) {
 730             early_ok = HandleData(cx, jp, JSON_DATA_NUMBER);
 731             if (early_ok)
 732                 PopState(cx, jp);
 733         }
 734     }
 735
 736     // This internal API is infallible, in spite of its JSBool return type.
 737     js_RemoveRoot(cx->runtime, &jp->objectStack);
 738
 739     bool ok = *jp->statep == JSON_PARSE_STATE_FINISHED;
 740     Value *vp = jp->rootVal;
 741
 742     if (!early_ok) {
 743         ok = false;
 744     } else if (!ok) {
 745         JSONParseError(jp, cx);
 746     } else if (reviver.isObject() && reviver.toObject().isCallable()) {
 747         ok = Revive(cx, reviver, vp);
 748     }
 749
 750     cx->destroy(jp);
 751
 752     return ok;
 753 }
 754
 755 static JSBool
 756 PushState(JSContext *cx, JSONParser *jp, JSONParserState state)
 757 {
 758     if (*jp->statep == JSON_PARSE_STATE_FINISHED) {
 759         // extra input
 760         return JSONParseError(jp, cx);
 761     }
 762
 763     jp->statep++;
 764     if ((uint32)(jp->statep - jp->stateStack) >= JS_ARRAY_LENGTH(jp->stateStack)) {
 765         // too deep
 766         return JSONParseError(jp, cx);
 767     }
 768
 769     *jp->statep = state;
 770
 771     return JS_TRUE;
 772 }
 773
 774 static JSBool
 775 PopState(JSContext *cx, JSONParser *jp)
 776 {
 777     jp->statep--;
 778     if (jp->statep < jp->stateStack) {
 779         jp->statep = jp->stateStack;
 780         return JSONParseError(jp, cx);
 781     }
 782
 783     if (*jp->statep == JSON_PARSE_STATE_INIT)
 784         *jp->statep = JSON_PARSE_STATE_FINISHED;
 785
 786     return JS_TRUE;
 787 }
 788
 789 static JSBool
 790 PushValue(JSContext *cx, JSONParser *jp, JSObject *parent, const Value &value)
 791 {
 792     JSBool ok;
 793     if (parent->isArray()) {
 794         jsuint len;
 795         ok = js_GetLengthProperty(cx, parent, &len);
 796         if (ok) {
 797             jsid index;
 798             if (!js_IndexToId(cx, len, &index))
 799                 return JS_FALSE;
 800             ok = parent->defineProperty(cx, index, value, NULL, NULL, JSPROP_ENUMERATE);
 801         }
 802     } else {
 803         ok = JS_DefineUCProperty(cx, parent, jp->objectKey.begin(),
 804                                  jp->objectKey.length(), Jsvalify(value),
 805                                  NULL, NULL, JSPROP_ENUMERATE);
 806         jp->objectKey.clear();
 807     }
 808
 809     return ok;
 810 }
 811
 812 static JSBool
 813 PushObject(JSContext *cx, JSONParser *jp, JSObject *obj)
 814 {
 815     jsuint len;
 816     if (!js_GetLengthProperty(cx, jp->objectStack, &len))
 817         return JS_FALSE;
 818     if (len >= JSON_MAX_DEPTH)
 819         return JSONParseError(jp, cx);
 820
 821     AutoObjectRooter tvr(cx, obj);
 822     Value v = ObjectOrNullValue(obj);
 823
 824     // Check if this is the root object
 825     if (len == 0) {
 826         *jp->rootVal = v;
 827         // This property must be enumerable to keep the array dense
 828         if (!jp->objectStack->defineProperty(cx, INT_TO_JSID(0), *jp->rootVal,
 829                                              NULL, NULL, JSPROP_ENUMERATE)) {
 830             return JS_FALSE;
 831         }
 832         return JS_TRUE;
 833     }
 834
 835     Value p;
 836     if (!jp->objectStack->getProperty(cx, INT_TO_JSID(len - 1), &p))
 837         return JS_FALSE;
 838
 839     JSObject *parent = &p.toObject();
 840     if (!PushValue(cx, jp, parent, v))
 841         return JS_FALSE;
 842
 843     // This property must be enumerable to keep the array dense
 844     if (!jp->objectStack->defineProperty(cx, INT_TO_JSID(len), v,
 845                                          NULL, NULL, JSPROP_ENUMERATE)) {
 846         return JS_FALSE;
 847     }
 848
 849     return JS_TRUE;
 850 }
 851
 852 static JSBool
 853 OpenObject(JSContext *cx, JSONParser *jp)
 854 {
 855     JSObject *obj = NewBuiltinClassInstance(cx, &js_ObjectClass);
 856     if (!obj)
 857         return JS_FALSE;
 858
 859     return PushObject(cx, jp, obj);
 860 }
 861
 862 static JSBool
 863 OpenArray(JSContext *cx, JSONParser *jp)
 864 {
 865     // Add an array to an existing array or object
 866     JSObject *arr = js_NewArrayObject(cx, 0, NULL);
 867     if (!arr)
 868         return JS_FALSE;
 869
 870     return PushObject(cx, jp, arr);
 871 }
 872
 873 static JSBool
 874 CloseObject(JSContext *cx, JSONParser *jp)
 875 {
 876     jsuint len;
 877     if (!js_GetLengthProperty(cx, jp->objectStack, &len))
 878         return JS_FALSE;
 879     if (!js_SetLengthProperty(cx, jp->objectStack, len - 1))
 880         return JS_FALSE;
 881
 882     return JS_TRUE;
 883 }
 884
 885 static JSBool
 886 CloseArray(JSContext *cx, JSONParser *jp)
 887 {
 888     return CloseObject(cx, jp);
 889 }
 890
 891 static JSBool
 892 PushPrimitive(JSContext *cx, JSONParser *jp, const Value &value)
 893 {
 894     AutoValueRooter tvr(cx, value);
 895
 896     jsuint len;
 897     if (!js_GetLengthProperty(cx, jp->objectStack, &len))
 898         return JS_FALSE;
 899
 900     if (len > 0) {
 901         Value o;
 902         if (!jp->objectStack->getProperty(cx, INT_TO_JSID(len - 1), &o))
 903             return JS_FALSE;
 904
 905         return PushValue(cx, jp, &o.toObject(), value);
 906     }
 907
 908     // root value must be primitive
 909     *jp->rootVal = value;
 910     return JS_TRUE;
 911 }
 912
 913 static JSBool
 914 HandleNumber(JSContext *cx, JSONParser *jp, const jschar *buf, uint32 len)
 915 {
 916     const jschar *ep;
 917     double val;
 918     if (!js_strtod(cx, buf, buf + len, &ep, &val))
 919         return JS_FALSE;
 920     if (ep != buf + len) {
 921         // bad number input
 922         return JSONParseError(jp, cx);
 923     }
 924
 925     return PushPrimitive(cx, jp, DoubleValue(val));
 926 }
 927
 928 static JSBool
 929 HandleString(JSContext *cx, JSONParser *jp, const jschar *buf, uint32 len)
 930 {
 931     JSString *str = js_NewStringCopyN(cx, buf, len);
 932     if (!str)
 933         return JS_FALSE;
 934
 935     return PushPrimitive(cx, jp, StringValue(str));
 936 }
 937
 938 static JSBool
 939 HandleKeyword(JSContext *cx, JSONParser *jp, const jschar *buf, uint32 len)
 940 {
 941     Value keyword;
 942     TokenKind tt = js_CheckKeyword(buf, len);
 943     if (tt != TOK_PRIMARY) {
 944         // bad keyword
 945         return JSONParseError(jp, cx);
 946     }
 947
 948     if (buf[0] == 'n') {
 949         keyword.setNull();
 950     } else if (buf[0] == 't') {
 951         keyword.setBoolean(true);
 952     } else if (buf[0] == 'f') {
 953         keyword.setBoolean(false);
 954     } else {
 955         return JSONParseError(jp, cx);
 956     }
 957
 958     return PushPrimitive(cx, jp, keyword);
 959 }
 960
 961 static JSBool
 962 HandleData(JSContext *cx, JSONParser *jp, JSONDataType type)
 963 {
 964     JSBool ok;
 965
 966     switch (type) {
 967       case JSON_DATA_STRING:
 968         ok = HandleString(cx, jp, jp->buffer.begin(), jp->buffer.length());
 969         break;
 970
 971       case JSON_DATA_KEYSTRING:
 972         ok = jp->objectKey.append(jp->buffer.begin(), jp->buffer.end());
 973         break;
 974
 975       case JSON_DATA_NUMBER:
 976         ok = HandleNumber(cx, jp, jp->buffer.begin(), jp->buffer.length());
 977         break;
 978
 979       default:
 980         JS_ASSERT(type == JSON_DATA_KEYWORD);
 981         ok = HandleKeyword(cx, jp, jp->buffer.begin(), jp->buffer.length());
 982         break;
 983     }
 984
 985     if (ok)
 986         jp->buffer.clear();
 987     return ok;
 988 }
 989
 990 JSBool
 991 js_ConsumeJSONText(JSContext *cx, JSONParser *jp, const jschar *data, uint32 len)
 992 {
 993     uint32 i;
 994
 995     if (*jp->statep == JSON_PARSE_STATE_INIT) {
 996         PushState(cx, jp, JSON_PARSE_STATE_VALUE);
 997     }
 998
 999     for (i = 0; i < len; i++) {
1000         jschar c = data[i];
1001         switch (*jp->statep) {
1002           case JSON_PARSE_STATE_VALUE:
1003             if (c == ']') {
1004                 // empty array
1005                 if (!PopState(cx, jp))
1006                     return JS_FALSE;
1007
1008                 if (*jp->statep != JSON_PARSE_STATE_ARRAY)
1009                     return JSONParseError(jp, cx);
1010
1011                 if (!CloseArray(cx, jp) || !PopState(cx, jp))
1012                     return JS_FALSE;
1013
1014                 break;
1015             }
1016
1017             if (c == '}') {
1018                 // we should only find these in OBJECT_KEY state
1019                 return JSONParseError(jp, cx);
1020             }
1021
1022             if (c == '"') {
1023                 *jp->statep = JSON_PARSE_STATE_STRING;
1024                 break;
1025             }
1026
1027             if (IsNumChar(c)) {
1028                 *jp->statep = JSON_PARSE_STATE_NUMBER;
1029                 if (!jp->buffer.append(c))
1030                     return JS_FALSE;
1031                 break;
1032             }
1033
1034             if (JS7_ISLET(c)) {
1035                 *jp->statep = JSON_PARSE_STATE_KEYWORD;
1036                 if (!jp->buffer.append(c))
1037                     return JS_FALSE;
1038                 break;
1039             }
1040
1041           // fall through in case the value is an object or array
1042           case JSON_PARSE_STATE_OBJECT_VALUE:
1043             if (c == '{') {
1044                 *jp->statep = JSON_PARSE_STATE_OBJECT;
1045                 if (!OpenObject(cx, jp) || !PushState(cx, jp, JSON_PARSE_STATE_OBJECT_PAIR))
1046                     return JS_FALSE;
1047             } else if (c == '[') {
1048                 *jp->statep = JSON_PARSE_STATE_ARRAY;
1049                 if (!OpenArray(cx, jp) || !PushState(cx, jp, JSON_PARSE_STATE_VALUE))
1050                     return JS_FALSE;
1051             } else if (!JS_ISXMLSPACE(c)) {
1052                 return JSONParseError(jp, cx);
1053             }
1054             break;
1055
1056           case JSON_PARSE_STATE_OBJECT:
1057             if (c == '}') {
1058                 if (!CloseObject(cx, jp) || !PopState(cx, jp))
1059                     return JS_FALSE;
1060             } else if (c == ',') {
1061                 if (!PushState(cx, jp, JSON_PARSE_STATE_OBJECT_PAIR))
1062                     return JS_FALSE;
1063             } else if (c == ']' || !JS_ISXMLSPACE(c)) {
1064                 return JSONParseError(jp, cx);
1065             }
1066             break;
1067
1068           case JSON_PARSE_STATE_ARRAY:
1069             if (c == ']') {
1070                 if (!CloseArray(cx, jp) || !PopState(cx, jp))
1071                     return JS_FALSE;
1072             } else if (c == ',') {
1073                 if (!PushState(cx, jp, JSON_PARSE_STATE_VALUE))
1074                     return JS_FALSE;
1075             } else if (!JS_ISXMLSPACE(c)) {
1076                 return JSONParseError(jp, cx);
1077             }
1078             break;
1079
1080           case JSON_PARSE_STATE_OBJECT_PAIR:
1081             if (c == '"') {
1082                 // we want to be waiting for a : when the string has been read
1083                 *jp->statep = JSON_PARSE_STATE_OBJECT_IN_PAIR;
1084                 if (!PushState(cx, jp, JSON_PARSE_STATE_STRING))
1085                     return JS_FALSE;
1086             } else if (c == '}') {
1087                 // pop off the object pair state and the object state
1088                 if (!CloseObject(cx, jp) || !PopState(cx, jp) || !PopState(cx, jp))
1089                     return JS_FALSE;
1090             } else if (c == ']' || !JS_ISXMLSPACE(c)) {
1091                 return JSONParseError(jp, cx);
1092             }
1093             break;
1094
1095           case JSON_PARSE_STATE_OBJECT_IN_PAIR:
1096             if (c == ':') {
1097                 *jp->statep = JSON_PARSE_STATE_VALUE;
1098             } else if (!JS_ISXMLSPACE(c)) {
1099                 return JSONParseError(jp, cx);
1100             }
1101             break;
1102
1103           case JSON_PARSE_STATE_STRING:
1104             if (c == '"') {
1105                 if (!PopState(cx, jp))
1106                     return JS_FALSE;
1107                 JSONDataType jdt;
1108                 if (*jp->statep == JSON_PARSE_STATE_OBJECT_IN_PAIR) {
1109                     jdt = JSON_DATA_KEYSTRING;
1110                 } else {
1111                     jdt = JSON_DATA_STRING;
1112                 }
1113                 if (!HandleData(cx, jp, jdt))
1114                     return JS_FALSE;
1115             } else if (c == '\\') {
1116                 *jp->statep = JSON_PARSE_STATE_STRING_ESCAPE;
1117             } else if (c < 31) {
1118                 // The JSON lexical grammer does not allow a JSONStringCharacter to be
1119                 // any of the Unicode characters U+0000 thru U+001F (control characters).
1120                 return JSONParseError(jp, cx);
1121             } else {
1122                 if (!jp->buffer.append(c))
1123                     return JS_FALSE;
1124             }
1125             break;
1126
1127           case JSON_PARSE_STATE_STRING_ESCAPE:
1128             switch (c) {
1129               case '"':
1130               case '\\':
1131               case '/':
1132                 break;
1133               case 'b' : c = '\b'; break;
1134               case 'f' : c = '\f'; break;
1135               case 'n' : c = '\n'; break;
1136               case 'r' : c = '\r'; break;
1137               case 't' : c = '\t'; break;
1138               default :
1139                 if (c == 'u') {
1140                     jp->numHex = 0;
1141                     jp->hexChar = 0;
1142                     *jp->statep = JSON_PARSE_STATE_STRING_HEX;
1143                     continue;
1144                 } else {
1145                     return JSONParseError(jp, cx);
1146                 }
1147             }
1148
1149             if (!jp->buffer.append(c))
1150                 return JS_FALSE;
1151             *jp->statep = JSON_PARSE_STATE_STRING;
1152             break;
1153
1154           case JSON_PARSE_STATE_STRING_HEX:
1155             if (('0' <= c) && (c <= '9')) {
1156                 jp->hexChar = (jp->hexChar << 4) | (c - '0');
1157             } else if (('a' <= c) && (c <= 'f')) {
1158                 jp->hexChar = (jp->hexChar << 4) | (c - 'a' + 0x0a);
1159             } else if (('A' <= c) && (c <= 'F')) {
1160                 jp->hexChar = (jp->hexChar << 4) | (c - 'A' + 0x0a);
1161             } else {
1162                 return JSONParseError(jp, cx);
1163             }
1164
1165             if (++(jp->numHex) == 4) {
1166                 if (!jp->buffer.append(jp->hexChar))
1167                     return JS_FALSE;
1168                 jp->hexChar = 0;
1169                 jp->numHex = 0;
1170                 *jp->statep = JSON_PARSE_STATE_STRING;
1171             }
1172             break;
1173
1174           case JSON_PARSE_STATE_KEYWORD:
1175             if (JS7_ISLET(c)) {
1176                 if (!jp->buffer.append(c))
1177                     return JS_FALSE;
1178             } else {
1179                 // this character isn't part of the keyword, process it again
1180                 i--;
1181                 if (!PopState(cx, jp))
1182                     return JS_FALSE;
1183
1184                 if (!HandleData(cx, jp, JSON_DATA_KEYWORD))
1185                     return JS_FALSE;
1186             }
1187             break;
1188
1189           case JSON_PARSE_STATE_NUMBER:
1190             if (IsNumChar(c)) {
1191                 if (!jp->buffer.append(c))
1192                     return JS_FALSE;
1193             } else {
1194                 // this character isn't part of the number, process it again
1195                 i--;
1196                 if (!PopState(cx, jp))
1197                     return JS_FALSE;
1198                 if (!HandleData(cx, jp, JSON_DATA_NUMBER))
1199                     return JS_FALSE;
1200             }
1201             break;
1202
1203           case JSON_PARSE_STATE_FINISHED:
1204             if (!JS_ISXMLSPACE(c)) {
1205                 // extra input
1206                 return JSONParseError(jp, cx);
1207             }
1208             break;
1209
1210           default:
1211             JS_NOT_REACHED("Invalid JSON parser state");
1212         }
1213     }
1214
1215     return JS_TRUE;
1216 }
1217
1218 #if JS_HAS_TOSOURCE
1219 static JSBool
1220 json_toSource(JSContext *cx, uintN argc, Value *vp)
1221 {
1222     vp->setString(ATOM_TO_STRING(CLASS_ATOM(cx, JSON)));
1223     return JS_TRUE;
1224 }
1225 #endif
1226
1227 static JSFunctionSpec json_static_methods[] = {
1228 #if JS_HAS_TOSOURCE
1229     JS_FN(js_toSource_str,  json_toSource,      0, 0),
1230 #endif
1231     JS_FN("parse",          js_json_parse,      2, 0),
1232     JS_FN("stringify",      js_json_stringify,  3, 0),
1233     JS_FS_END
1234 };
1235
1236 JSObject *
1237 js_InitJSONClass(JSContext *cx, JSObject *obj)
1238 {
1239     JSObject *JSON;
1240
1241     JSON = NewNonFunction<WithProto::Class>(cx, &js_JSONClass, NULL, obj);
1242     if (!JSON)
1243         return NULL;
1244     if (!JS_DefineProperty(cx, obj, js_JSON_str, OBJECT_TO_JSVAL(JSON),
1245                            JS_PropertyStub, JS_PropertyStub, 0))
1246         return NULL;
1247
1248     if (!JS_DefineFunctions(cx, JSON, json_static_methods))
1249         return NULL;
1250
1251     return JSON;
1252 }