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         size_t length = s->length();
 410         const jschar *chars = s->getChars(cx);
 411         if (!chars)
 412             return JS_FALSE;
 413
 414         if (!write_string(cx, scx->sb, chars, length) ||
 415             !scx->sb.append(':') ||
 416             !(scx->gap.empty() || scx->sb.append(' ')) ||
 417             !Str(cx, id, obj, scx, &outputValue, true)) {
 418             return JS_FALSE;
 419         }
 420     }
 421
 422     if (memberWritten && !WriteIndent(cx, scx, scx->depth - 1))
 423         return JS_FALSE;
 424
 425     return scx->sb.append('}');
 426 }
 427
 428 static JSBool
 429 JA(JSContext *cx, Value *vp, StringifyContext *scx)
 430 {
 431     JSObject *obj = &vp->toObject();
 432
 433     CycleDetector detect(scx, obj);
 434     if (!detect.init(cx))
 435         return JS_FALSE;
 436
 437     if (!scx->sb.append('['))
 438         return JS_FALSE;
 439
 440     jsuint length;
 441     if (!js_GetLengthProperty(cx, obj, &length))
 442         return JS_FALSE;
 443
 444     if (length != 0 && !WriteIndent(cx, scx, scx->depth))
 445         return JS_FALSE;
 446
 447     AutoValueRooter outputValue(cx);
 448
 449     jsid id;
 450     jsuint i;
 451     for (i = 0; i < length; i++) {
 452         id = INT_TO_JSID(i);
 453
 454         if (!obj->getProperty(cx, id, outputValue.addr()))
 455             return JS_FALSE;
 456
 457         if (!Str(cx, id, obj, scx, outputValue.addr()))
 458             return JS_FALSE;
 459
 460         if (outputValue.value().isUndefined()) {
 461             if (!scx->sb.append("null"))
 462                 return JS_FALSE;
 463         }
 464
 465         if (i < length - 1) {
 466             if (!scx->sb.append(','))
 467                 return JS_FALSE;
 468             if (!WriteIndent(cx, scx, scx->depth))
 469                 return JS_FALSE;
 470         }
 471     }
 472
 473     if (length != 0 && !WriteIndent(cx, scx, scx->depth - 1))
 474         return JS_FALSE;
 475
 476     return scx->sb.append(']');
 477 }
 478
 479 static JSBool
 480 CallReplacerFunction(JSContext *cx, jsid id, JSObject *holder, StringifyContext *scx, Value *vp)
 481 {
 482     if (scx->replacer && scx->replacer->isCallable()) {
 483         Value vec[2] = { IdToValue(id), *vp};
 484         if (!JS_CallFunctionValue(cx, holder, OBJECT_TO_JSVAL(scx->replacer),
 485                                   2, Jsvalify(vec), Jsvalify(vp))) {
 486             return JS_FALSE;
 487         }
 488     }
 489
 490     return JS_TRUE;
 491 }
 492
 493 static JSBool
 494 Str(JSContext *cx, jsid id, JSObject *holder, StringifyContext *scx, Value *vp, bool callReplacer)
 495 {
 496     JS_CHECK_RECURSION(cx, return JS_FALSE);
 497
 498     if (vp->isObject() && !js_TryJSON(cx, vp))
 499         return JS_FALSE;
 500
 501     if (callReplacer && !CallReplacerFunction(cx, id, holder, scx, vp))
 502         return JS_FALSE;
 503
 504     // catches string and number objects with no toJSON
 505     if (vp->isObject()) {
 506         JSObject *obj = &vp->toObject();
 507         Class *clasp = obj->getClass();
 508         if (clasp == &js_StringClass || clasp == &js_NumberClass)
 509             *vp = obj->getPrimitiveThis();
 510     }
 511
 512     if (vp->isString()) {
 513         JSString *str = vp->toString();
 514         size_t length = str->length();
 515         const jschar *chars = str->getChars(cx);
 516         if (!chars)
 517             return JS_FALSE;
 518         return write_string(cx, scx->sb, chars, length);
 519     }
 520
 521     if (vp->isNull())
 522         return scx->sb.append("null");
 523
 524     if (vp->isBoolean())
 525         return vp->toBoolean() ? scx->sb.append("true") : scx->sb.append("false");
 526
 527     if (vp->isNumber()) {
 528         if (vp->isDouble()) {
 529             jsdouble d = vp->toDouble();
 530             if (!JSDOUBLE_IS_FINITE(d))
 531                 return scx->sb.append("null");
 532         }
 533
 534         StringBuffer sb(cx);
 535         if (!NumberValueToStringBuffer(cx, *vp, sb))
 536             return JS_FALSE;
 537
 538         return scx->sb.append(sb.begin(), sb.length());
 539     }
 540
 541     if (vp->isObject() && !IsFunctionObject(*vp) && !IsXML(*vp)) {
 542         JSBool ok;
 543
 544         scx->depth++;
 545         ok = (JS_IsArrayObject(cx, &vp->toObject()) ? JA : JO)(cx, vp, scx);
 546         scx->depth--;
 547
 548         return ok;
 549     }
 550
 551     vp->setUndefined();
 552     return JS_TRUE;
 553 }
 554
 555 JSBool
 556 js_Stringify(JSContext *cx, Value *vp, JSObject *replacer, const Value &space,
 557              StringBuffer &sb)
 558 {
 559     StringifyContext scx(cx, sb, replacer);
 560     if (!scx.initializeGap(cx, space) || !scx.initializeStack())
 561         return JS_FALSE;
 562
 563     JSObject *obj = NewBuiltinClassInstance(cx, &js_ObjectClass);
 564     if (!obj)
 565         return JS_FALSE;
 566
 567     AutoObjectRooter tvr(cx, obj);
 568     if (!obj->defineProperty(cx, ATOM_TO_JSID(cx->runtime->atomState.emptyAtom),
 569                              *vp, NULL, NULL, JSPROP_ENUMERATE)) {
 570         return JS_FALSE;
 571     }
 572
 573     return Str(cx, ATOM_TO_JSID(cx->runtime->atomState.emptyAtom), obj, &scx, vp);
 574 }
 575
 576 // helper to determine whether a character could be part of a number
 577 static JSBool IsNumChar(jschar c)
 578 {
 579     return ((c <= '9' && c >= '0') || c == '.' || c == '-' || c == '+' || c == 'e' || c == 'E');
 580 }
 581
 582 static JSBool HandleDataString(JSContext *cx, JSONParser *jp);
 583 static JSBool HandleDataKeyString(JSContext *cx, JSONParser *jp);
 584 static JSBool HandleDataNumber(JSContext *cx, JSONParser *jp);
 585 static JSBool HandleDataKeyword(JSContext *cx, JSONParser *jp);
 586 static JSBool PopState(JSContext *cx, JSONParser *jp);
 587
 588 static bool
 589 Walk(JSContext *cx, jsid id, JSObject *holder, const Value &reviver, Value *vp)
 590 {
 591     JS_CHECK_RECURSION(cx, return false);
 592
 593     if (!holder->getProperty(cx, id, vp))
 594         return false;
 595
 596     JSObject *obj;
 597
 598     if (vp->isObject() && !(obj = &vp->toObject())->isCallable()) {
 599         AutoValueRooter propValue(cx);
 600
 601         if(obj->isArray()) {
 602             jsuint length = 0;
 603             if (!js_GetLengthProperty(cx, obj, &length))
 604                 return false;
 605
 606             for (jsuint i = 0; i < length; i++) {
 607                 jsid index;
 608                 if (!js_IndexToId(cx, i, &index))
 609                     return false;
 610
 611                 if (!Walk(cx, index, obj, reviver, propValue.addr()))
 612                     return false;
 613
 614                 if (!obj->defineProperty(cx, index, propValue.value(), NULL, NULL, JSPROP_ENUMERATE))
 615                     return false;
 616             }
 617         } else {
 618             AutoIdVector props(cx);
 619             if (!GetPropertyNames(cx, obj, JSITER_OWNONLY, &props))
 620                 return false;
 621
 622             for (size_t i = 0, len = props.length(); i < len; i++) {
 623                 jsid idName = props[i];
 624                 if (!Walk(cx, idName, obj, reviver, propValue.addr()))
 625                     return false;
 626                 if (propValue.value().isUndefined()) {
 627                     if (!js_DeleteProperty(cx, obj, idName, propValue.addr(), false))
 628                         return false;
 629                 } else {
 630                     if (!obj->defineProperty(cx, idName, propValue.value(), NULL, NULL,
 631                                              JSPROP_ENUMERATE)) {
 632                         return false;
 633                     }
 634                 }
 635             }
 636         }
 637     }
 638
 639     // return reviver.call(holder, key, value);
 640     const Value &value = *vp;
 641     JSString *key = js_ValueToString(cx, IdToValue(id));
 642     if (!key)
 643         return false;
 644
 645     Value vec[2] = { StringValue(key), value };
 646     Value reviverResult;
 647     if (!JS_CallFunctionValue(cx, holder, Jsvalify(reviver),
 648                               2, Jsvalify(vec), Jsvalify(&reviverResult))) {
 649         return false;
 650     }
 651
 652     *vp = reviverResult;
 653     return true;
 654 }
 655
 656 static JSBool
 657 JSONParseError(JSONParser *jp, JSContext *cx)
 658 {
 659     if (!jp->suppressErrors)
 660         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_JSON_BAD_PARSE);
 661     return JS_FALSE;
 662 }
 663
 664 static bool
 665 Revive(JSContext *cx, const Value &reviver, Value *vp)
 666 {
 667
 668     JSObject *obj = NewBuiltinClassInstance(cx, &js_ObjectClass);
 669     if (!obj)
 670         return false;
 671
 672     AutoObjectRooter tvr(cx, obj);
 673     if (!obj->defineProperty(cx, ATOM_TO_JSID(cx->runtime->atomState.emptyAtom),
 674                              *vp, NULL, NULL, JSPROP_ENUMERATE)) {
 675         return false;
 676     }
 677
 678     return Walk(cx, ATOM_TO_JSID(cx->runtime->atomState.emptyAtom), obj, reviver, vp);
 679 }
 680
 681 JSONParser *
 682 js_BeginJSONParse(JSContext *cx, Value *rootVal, bool suppressErrors /*= false*/)
 683 {
 684     if (!cx)
 685         return NULL;
 686
 687     JSObject *arr = NewDenseEmptyArray(cx);
 688     if (!arr)
 689         return NULL;
 690
 691     JSONParser *jp = cx->create<JSONParser>(cx);
 692     if (!jp)
 693         return NULL;
 694
 695     jp->objectStack = arr;
 696     if (!JS_AddNamedObjectRoot(cx, &jp->objectStack, "JSON parse stack"))
 697         goto bad;
 698
 699     jp->statep = jp->stateStack;
 700     *jp->statep = JSON_PARSE_STATE_INIT;
 701     jp->rootVal = rootVal;
 702     jp->suppressErrors = suppressErrors;
 703
 704     return jp;
 705
 706 bad:
 707     js_FinishJSONParse(cx, jp, NullValue());
 708     return NULL;
 709 }
 710
 711 bool
 712 js_FinishJSONParse(JSContext *cx, JSONParser *jp, const Value &reviver)
 713 {
 714     if (!jp)
 715         return true;
 716
 717     JSBool early_ok = JS_TRUE;
 718
 719     // Check for unprocessed primitives at the root. This doesn't happen for
 720     // strings because a closing quote triggers value processing.
 721     if ((jp->statep - jp->stateStack) == 1) {
 722         if (*jp->statep == JSON_PARSE_STATE_KEYWORD) {
 723             early_ok = HandleDataKeyword(cx, jp);
 724             if (early_ok)
 725                 PopState(cx, jp);
 726         } else if (*jp->statep == JSON_PARSE_STATE_NUMBER) {
 727             early_ok = HandleDataNumber(cx, jp);
 728             if (early_ok)
 729                 PopState(cx, jp);
 730         }
 731     }
 732
 733     // This internal API is infallible, in spite of its JSBool return type.
 734     js_RemoveRoot(cx->runtime, &jp->objectStack);
 735
 736     bool ok = *jp->statep == JSON_PARSE_STATE_FINISHED;
 737     Value *vp = jp->rootVal;
 738
 739     if (!early_ok) {
 740         ok = false;
 741     } else if (!ok) {
 742         JSONParseError(jp, cx);
 743     } else if (reviver.isObject() && reviver.toObject().isCallable()) {
 744         ok = Revive(cx, reviver, vp);
 745     }
 746
 747     cx->destroy(jp);
 748
 749     return ok;
 750 }
 751
 752 static JSBool
 753 PushState(JSContext *cx, JSONParser *jp, JSONParserState state)
 754 {
 755     if (*jp->statep == JSON_PARSE_STATE_FINISHED) {
 756         // extra input
 757         return JSONParseError(jp, cx);
 758     }
 759
 760     jp->statep++;
 761     if ((uint32)(jp->statep - jp->stateStack) >= JS_ARRAY_LENGTH(jp->stateStack)) {
 762         // too deep
 763         return JSONParseError(jp, cx);
 764     }
 765
 766     *jp->statep = state;
 767
 768     return JS_TRUE;
 769 }
 770
 771 static JSBool
 772 PopState(JSContext *cx, JSONParser *jp)
 773 {
 774     jp->statep--;
 775     if (jp->statep < jp->stateStack) {
 776         jp->statep = jp->stateStack;
 777         return JSONParseError(jp, cx);
 778     }
 779
 780     if (*jp->statep == JSON_PARSE_STATE_INIT)
 781         *jp->statep = JSON_PARSE_STATE_FINISHED;
 782
 783     return JS_TRUE;
 784 }
 785
 786 static JSBool
 787 PushValue(JSContext *cx, JSONParser *jp, JSObject *parent, const Value &value)
 788 {
 789     JSBool ok;
 790     if (parent->isArray()) {
 791         jsuint len;
 792         ok = js_GetLengthProperty(cx, parent, &len);
 793         if (ok) {
 794             jsid index;
 795             if (!js_IndexToId(cx, len, &index))
 796                 return JS_FALSE;
 797             ok = parent->defineProperty(cx, index, value, NULL, NULL, JSPROP_ENUMERATE);
 798         }
 799     } else {
 800         ok = JS_DefineUCProperty(cx, parent, jp->objectKey.begin(),
 801                                  jp->objectKey.length(), Jsvalify(value),
 802                                  NULL, NULL, JSPROP_ENUMERATE);
 803         jp->objectKey.clear();
 804     }
 805
 806     return ok;
 807 }
 808
 809 static JSBool
 810 PushObject(JSContext *cx, JSONParser *jp, JSObject *obj)
 811 {
 812     jsuint len;
 813     if (!js_GetLengthProperty(cx, jp->objectStack, &len))
 814         return JS_FALSE;
 815     if (len >= JSON_MAX_DEPTH)
 816         return JSONParseError(jp, cx);
 817
 818     AutoObjectRooter tvr(cx, obj);
 819     Value v = ObjectOrNullValue(obj);
 820
 821     // Check if this is the root object
 822     if (len == 0) {
 823         *jp->rootVal = v;
 824         // This property must be enumerable to keep the array dense
 825         if (!jp->objectStack->defineProperty(cx, INT_TO_JSID(0), *jp->rootVal,
 826                                              NULL, NULL, JSPROP_ENUMERATE)) {
 827             return JS_FALSE;
 828         }
 829         return JS_TRUE;
 830     }
 831
 832     Value p;
 833     if (!jp->objectStack->getProperty(cx, INT_TO_JSID(len - 1), &p))
 834         return JS_FALSE;
 835
 836     JSObject *parent = &p.toObject();
 837     if (!PushValue(cx, jp, parent, v))
 838         return JS_FALSE;
 839
 840     // This property must be enumerable to keep the array dense
 841     if (!jp->objectStack->defineProperty(cx, INT_TO_JSID(len), v,
 842                                          NULL, NULL, JSPROP_ENUMERATE)) {
 843         return JS_FALSE;
 844     }
 845
 846     return JS_TRUE;
 847 }
 848
 849 static JSBool
 850 OpenObject(JSContext *cx, JSONParser *jp)
 851 {
 852     JSObject *obj = NewBuiltinClassInstance(cx, &js_ObjectClass);
 853     if (!obj)
 854         return JS_FALSE;
 855
 856     return PushObject(cx, jp, obj);
 857 }
 858
 859 static JSBool
 860 OpenArray(JSContext *cx, JSONParser *jp)
 861 {
 862     // Add an array to an existing array or object
 863     JSObject *arr = NewDenseEmptyArray(cx);
 864     if (!arr)
 865         return JS_FALSE;
 866
 867     return PushObject(cx, jp, arr);
 868 }
 869
 870 static JSBool
 871 CloseObject(JSContext *cx, JSONParser *jp)
 872 {
 873     jsuint len;
 874     if (!js_GetLengthProperty(cx, jp->objectStack, &len))
 875         return JS_FALSE;
 876     if (!js_SetLengthProperty(cx, jp->objectStack, len - 1))
 877         return JS_FALSE;
 878
 879     return JS_TRUE;
 880 }
 881
 882 static JSBool
 883 CloseArray(JSContext *cx, JSONParser *jp)
 884 {
 885     return CloseObject(cx, jp);
 886 }
 887
 888 static JSBool
 889 PushPrimitive(JSContext *cx, JSONParser *jp, const Value &value)
 890 {
 891     AutoValueRooter tvr(cx, value);
 892
 893     jsuint len;
 894     if (!js_GetLengthProperty(cx, jp->objectStack, &len))
 895         return JS_FALSE;
 896
 897     if (len > 0) {
 898         Value o;
 899         if (!jp->objectStack->getProperty(cx, INT_TO_JSID(len - 1), &o))
 900             return JS_FALSE;
 901
 902         return PushValue(cx, jp, &o.toObject(), value);
 903     }
 904
 905     // root value must be primitive
 906     *jp->rootVal = value;
 907     return JS_TRUE;
 908 }
 909
 910 static JSBool
 911 HandleNumber(JSContext *cx, JSONParser *jp, const jschar *buf, uint32 len)
 912 {
 913     const jschar *ep;
 914     double val;
 915     if (!js_strtod(cx, buf, buf + len, &ep, &val))
 916         return JS_FALSE;
 917     if (ep != buf + len) {
 918         // bad number input
 919         return JSONParseError(jp, cx);
 920     }
 921
 922     return PushPrimitive(cx, jp, NumberValue(val));
 923 }
 924
 925 static JSBool
 926 HandleString(JSContext *cx, JSONParser *jp, const jschar *buf, uint32 len)
 927 {
 928     JSString *str = js_NewStringCopyN(cx, buf, len);
 929     if (!str)
 930         return JS_FALSE;
 931
 932     return PushPrimitive(cx, jp, StringValue(str));
 933 }
 934
 935 static JSBool
 936 HandleKeyword(JSContext *cx, JSONParser *jp, const jschar *buf, uint32 len)
 937 {
 938     const KeywordInfo *ki = FindKeyword(buf, len);
 939     if (!ki || ki->tokentype != TOK_PRIMARY) {
 940         // bad keyword
 941         return JSONParseError(jp, cx);
 942     }
 943
 944     Value keyword;
 945     if (buf[0] == 'n') {
 946         keyword.setNull();
 947     } else if (buf[0] == 't') {
 948         keyword.setBoolean(true);
 949     } else if (buf[0] == 'f') {
 950         keyword.setBoolean(false);
 951     } else {
 952         return JSONParseError(jp, cx);
 953     }
 954
 955     return PushPrimitive(cx, jp, keyword);
 956 }
 957
 958 static JSBool
 959 HandleDataString(JSContext *cx, JSONParser *jp)
 960 {
 961     JSBool ok = HandleString(cx, jp, jp->buffer.begin(), jp->buffer.length());
 962     if (ok)
 963         jp->buffer.clear();
 964     return ok;
 965 }
 966
 967 static JSBool
 968 HandleDataKeyString(JSContext *cx, JSONParser *jp)
 969 {
 970     JSBool ok = jp->objectKey.append(jp->buffer.begin(), jp->buffer.end());
 971     if (ok)
 972         jp->buffer.clear();
 973     return ok;
 974 }
 975
 976 static JSBool
 977 HandleDataNumber(JSContext *cx, JSONParser *jp)
 978 {
 979     JSBool ok = HandleNumber(cx, jp, jp->buffer.begin(), jp->buffer.length());
 980     if (ok)
 981         jp->buffer.clear();
 982     return ok;
 983 }
 984
 985 static JSBool
 986 HandleDataKeyword(JSContext *cx, JSONParser *jp)
 987 {
 988     JSBool ok = HandleKeyword(cx, jp, jp->buffer.begin(), jp->buffer.length());
 989     if (ok)
 990         jp->buffer.clear();
 991     return ok;
 992 }
 993
 994 JSBool
 995 js_ConsumeJSONText(JSContext *cx, JSONParser *jp, const jschar *data, uint32 len,
 996                    DecodingMode decodingMode)
 997 {
 998     CHECK_REQUEST(cx);
 999
1000     if (*jp->statep == JSON_PARSE_STATE_INIT) {
1001         PushState(cx, jp, JSON_PARSE_STATE_VALUE);
1002     }
1003
1004     for (uint32 i = 0; i < len; i++) {
1005         jschar c = data[i];
1006         switch (*jp->statep) {
1007           case JSON_PARSE_STATE_ARRAY_INITIAL_VALUE:
1008             if (c == ']') {
1009                 if (!PopState(cx, jp))
1010                     return JS_FALSE;
1011                 JS_ASSERT(*jp->statep == JSON_PARSE_STATE_ARRAY_AFTER_ELEMENT);
1012                 if (!CloseArray(cx, jp) || !PopState(cx, jp))
1013                     return JS_FALSE;
1014                 break;
1015             }
1016             // fall through if non-empty array or whitespace
1017
1018           case JSON_PARSE_STATE_VALUE:
1019             if (c == '"') {
1020                 *jp->statep = JSON_PARSE_STATE_STRING;
1021                 break;
1022             }
1023
1024             if (IsNumChar(c)) {
1025                 *jp->statep = JSON_PARSE_STATE_NUMBER;
1026                 if (!jp->buffer.append(c))
1027                     return JS_FALSE;
1028                 break;
1029             }
1030
1031             if (JS7_ISLET(c)) {
1032                 *jp->statep = JSON_PARSE_STATE_KEYWORD;
1033                 if (!jp->buffer.append(c))
1034                     return JS_FALSE;
1035                 break;
1036             }
1037
1038             if (c == '{') {
1039                 *jp->statep = JSON_PARSE_STATE_OBJECT_AFTER_PAIR;
1040                 if (!OpenObject(cx, jp) || !PushState(cx, jp, JSON_PARSE_STATE_OBJECT_INITIAL_PAIR))
1041                     return JS_FALSE;
1042             } else if (c == '[') {
1043                 *jp->statep = JSON_PARSE_STATE_ARRAY_AFTER_ELEMENT;
1044                 if (!OpenArray(cx, jp) || !PushState(cx, jp, JSON_PARSE_STATE_ARRAY_INITIAL_VALUE))
1045                     return JS_FALSE;
1046             } else if (JS_ISXMLSPACE(c)) {
1047                 // nothing to do
1048             } else if (decodingMode == LEGACY && c == ']') {
1049                 if (!PopState(cx, jp))
1050                     return JS_FALSE;
1051                 JS_ASSERT(*jp->statep == JSON_PARSE_STATE_ARRAY_AFTER_ELEMENT);
1052                 if (!CloseArray(cx, jp) || !PopState(cx, jp))
1053                     return JS_FALSE;
1054             } else {
1055                 return JSONParseError(jp, cx);
1056             }
1057             break;
1058
1059           case JSON_PARSE_STATE_ARRAY_AFTER_ELEMENT:
1060             if (c == ',') {
1061                 if (!PushState(cx, jp, JSON_PARSE_STATE_VALUE))
1062                     return JS_FALSE;
1063             } else if (c == ']') {
1064                 if (!CloseArray(cx, jp) || !PopState(cx, jp))
1065                     return JS_FALSE;
1066             } else if (!JS_ISXMLSPACE(c)) {
1067                 return JSONParseError(jp, cx);
1068             }
1069             break;
1070
1071           case JSON_PARSE_STATE_OBJECT_AFTER_PAIR:
1072             if (c == ',') {
1073                 if (!PushState(cx, jp, JSON_PARSE_STATE_OBJECT_PAIR))
1074                     return JS_FALSE;
1075             } else if (c == '}') {
1076                 if (!CloseObject(cx, jp) || !PopState(cx, jp))
1077                     return JS_FALSE;
1078             } else if (!JS_ISXMLSPACE(c)) {
1079                 return JSONParseError(jp, cx);
1080             }
1081             break;
1082
1083           case JSON_PARSE_STATE_OBJECT_INITIAL_PAIR:
1084             if (c == '}') {
1085                 if (!PopState(cx, jp))
1086                     return JS_FALSE;
1087                 JS_ASSERT(*jp->statep == JSON_PARSE_STATE_OBJECT_AFTER_PAIR);
1088                 if (!CloseObject(cx, jp) || !PopState(cx, jp))
1089                     return JS_FALSE;
1090                 break;
1091             }
1092             // fall through if non-empty object or whitespace
1093
1094           case JSON_PARSE_STATE_OBJECT_PAIR:
1095             if (c == '"') {
1096                 // we want to be waiting for a : when the string has been read
1097                 *jp->statep = JSON_PARSE_STATE_OBJECT_IN_PAIR;
1098                 if (!PushState(cx, jp, JSON_PARSE_STATE_STRING))
1099                     return JS_FALSE;
1100             } else if (JS_ISXMLSPACE(c)) {
1101                 // nothing to do
1102             } else if (decodingMode == LEGACY && c == '}') {
1103                 if (!PopState(cx, jp))
1104                     return JS_FALSE;
1105                 JS_ASSERT(*jp->statep == JSON_PARSE_STATE_OBJECT_AFTER_PAIR);
1106                 if (!CloseObject(cx, jp) || !PopState(cx, jp))
1107                     return JS_FALSE;
1108             } else {
1109                 return JSONParseError(jp, cx);
1110             }
1111             break;
1112
1113           case JSON_PARSE_STATE_OBJECT_IN_PAIR:
1114             if (c == ':') {
1115                 *jp->statep = JSON_PARSE_STATE_VALUE;
1116             } else if (!JS_ISXMLSPACE(c)) {
1117                 return JSONParseError(jp, cx);
1118             }
1119             break;
1120
1121           case JSON_PARSE_STATE_STRING:
1122             if (c == '"') {
1123                 if (!PopState(cx, jp))
1124                     return JS_FALSE;
1125                 if (*jp->statep == JSON_PARSE_STATE_OBJECT_IN_PAIR) {
1126                     if (!HandleDataKeyString(cx, jp))
1127                         return JS_FALSE;
1128                 } else {
1129                     if (!HandleDataString(cx, jp))
1130                         return JS_FALSE;
1131                 }
1132             } else if (c == '\\') {
1133                 *jp->statep = JSON_PARSE_STATE_STRING_ESCAPE;
1134             } else if (c <= 0x1F) {
1135                 // The JSON lexical grammer does not allow a JSONStringCharacter to be
1136                 // any of the Unicode characters U+0000 thru U+001F (control characters).
1137                 return JSONParseError(jp, cx);
1138             } else {
1139                 if (!jp->buffer.append(c))
1140                     return JS_FALSE;
1141             }
1142             break;
1143
1144           case JSON_PARSE_STATE_STRING_ESCAPE:
1145             switch (c) {
1146               case '"':
1147               case '\\':
1148               case '/':
1149                 break;
1150               case 'b' : c = '\b'; break;
1151               case 'f' : c = '\f'; break;
1152               case 'n' : c = '\n'; break;
1153               case 'r' : c = '\r'; break;
1154               case 't' : c = '\t'; break;
1155               default :
1156                 if (c == 'u') {
1157                     jp->numHex = 0;
1158                     jp->hexChar = 0;
1159                     *jp->statep = JSON_PARSE_STATE_STRING_HEX;
1160                     continue;
1161                 } else {
1162                     return JSONParseError(jp, cx);
1163                 }
1164             }
1165
1166             if (!jp->buffer.append(c))
1167                 return JS_FALSE;
1168             *jp->statep = JSON_PARSE_STATE_STRING;
1169             break;
1170
1171           case JSON_PARSE_STATE_STRING_HEX:
1172             if (('0' <= c) && (c <= '9')) {
1173                 jp->hexChar = (jp->hexChar << 4) | (c - '0');
1174             } else if (('a' <= c) && (c <= 'f')) {
1175                 jp->hexChar = (jp->hexChar << 4) | (c - 'a' + 0x0a);
1176             } else if (('A' <= c) && (c <= 'F')) {
1177                 jp->hexChar = (jp->hexChar << 4) | (c - 'A' + 0x0a);
1178             } else {
1179                 return JSONParseError(jp, cx);
1180             }
1181
1182             if (++(jp->numHex) == 4) {
1183                 if (!jp->buffer.append(jp->hexChar))
1184                     return JS_FALSE;
1185                 jp->hexChar = 0;
1186                 jp->numHex = 0;
1187                 *jp->statep = JSON_PARSE_STATE_STRING;
1188             }
1189             break;
1190
1191           case JSON_PARSE_STATE_KEYWORD:
1192             if (JS7_ISLET(c)) {
1193                 if (!jp->buffer.append(c))
1194                     return JS_FALSE;
1195             } else {
1196                 // this character isn't part of the keyword, process it again
1197                 i--;
1198                 if (!PopState(cx, jp))
1199                     return JS_FALSE;
1200
1201                 if (!HandleDataKeyword(cx, jp))
1202                     return JS_FALSE;
1203             }
1204             break;
1205
1206           case JSON_PARSE_STATE_NUMBER:
1207             if (IsNumChar(c)) {
1208                 if (!jp->buffer.append(c))
1209                     return JS_FALSE;
1210             } else {
1211                 // this character isn't part of the number, process it again
1212                 i--;
1213                 if (!PopState(cx, jp))
1214                     return JS_FALSE;
1215                 if (!HandleDataNumber(cx, jp))
1216                     return JS_FALSE;
1217             }
1218             break;
1219
1220           case JSON_PARSE_STATE_FINISHED:
1221             if (!JS_ISXMLSPACE(c)) {
1222                 // extra input
1223                 return JSONParseError(jp, cx);
1224             }
1225             break;
1226
1227           default:
1228             JS_NOT_REACHED("Invalid JSON parser state");
1229         }
1230     }
1231
1232     return JS_TRUE;
1233 }
1234
1235 #if JS_HAS_TOSOURCE
1236 static JSBool
1237 json_toSource(JSContext *cx, uintN argc, Value *vp)
1238 {
1239     vp->setString(ATOM_TO_STRING(CLASS_ATOM(cx, JSON)));
1240     return JS_TRUE;
1241 }
1242 #endif
1243
1244 static JSFunctionSpec json_static_methods[] = {
1245 #if JS_HAS_TOSOURCE
1246     JS_FN(js_toSource_str,  json_toSource,      0, 0),
1247 #endif
1248     JS_FN("parse",          js_json_parse,      2, 0),
1249     JS_FN("stringify",      js_json_stringify,  3, 0),
1250     JS_FS_END
1251 };
1252
1253 JSObject *
1254 js_InitJSONClass(JSContext *cx, JSObject *obj)
1255 {
1256     JSObject *JSON;
1257
1258     JSON = NewNonFunction<WithProto::Class>(cx, &js_JSONClass, NULL, obj);
1259     if (!JSON)
1260         return NULL;
1261     if (!JS_DefineProperty(cx, obj, js_JSON_str, OBJECT_TO_JSVAL(JSON),
1262                            JS_PropertyStub, JS_StrictPropertyStub, 0))
1263         return NULL;
1264
1265     if (!JS_DefineFunctions(cx, JSON, json_static_methods))
1266         return NULL;
1267
1268     return JSON;
1269 }