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