js/src/builtin/JSON.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "builtin/JSON.h"
   8
   9 #include "mozilla/CheckedInt.h"
  10 #include "mozilla/FloatingPoint.h"
  11 #include "mozilla/Range.h"
  12 #include "mozilla/ScopeExit.h"
  13 #include "mozilla/Variant.h"
  14
  15 #include <algorithm>
  16
  17 #include "jsnum.h"
  18 #include "jstypes.h"
  19
  20 #include "builtin/Array.h"
  21 #include "builtin/BigInt.h"
  22 #include "builtin/ParseRecordObject.h"
  23 #include "builtin/RawJSONObject.h"
  24 #include "js/friend/ErrorMessages.h"  // js::GetErrorMessage, JSMSG_*
  25 #include "js/friend/StackLimits.h"    // js::AutoCheckRecursionLimit
  26 #include "js/Object.h"                // JS::GetBuiltinClass
  27 #include "js/Prefs.h"                 // JS::Prefs
  28 #include "js/PropertySpec.h"
  29 #include "js/StableStringChars.h"
  30 #include "js/TypeDecls.h"
  31 #include "js/Value.h"
  32 #include "util/StringBuffer.h"
  33 #include "vm/BooleanObject.h"       // js::BooleanObject
  34 #include "vm/EqualityOperations.h"  // js::SameValue
  35 #include "vm/Interpreter.h"
  36 #include "vm/Iteration.h"
  37 #include "vm/JSAtomUtils.h"  // ToAtom
  38 #include "vm/JSContext.h"
  39 #include "vm/JSObject.h"
  40 #include "vm/JSONParser.h"
  41 #include "vm/NativeObject.h"
  42 #include "vm/NumberObject.h"  // js::NumberObject
  43 #include "vm/PlainObject.h"   // js::PlainObject
  44 #include "vm/StringObject.h"  // js::StringObject
  45 #ifdef ENABLE_RECORD_TUPLE
  46 #  include "builtin/RecordObject.h"
  47 #  include "builtin/TupleObject.h"
  48 #  include "vm/RecordType.h"
  49 #endif
  50
  51 #include "builtin/Array-inl.h"
  52 #include "vm/GeckoProfiler-inl.h"
  53 #include "vm/JSAtomUtils-inl.h"  // AtomToId, PrimitiveValueToId, IndexToId, IdToString,
  54 #include "vm/NativeObject-inl.h"
  55
  56 using namespace js;
  57
  58 using mozilla::AsVariant;
  59 using mozilla::CheckedInt;
  60 using mozilla::Maybe;
  61 using mozilla::RangedPtr;
  62 using mozilla::Variant;
  63
  64 using JS::AutoStableStringChars;
  65
  66 /* https://262.ecma-international.org/14.0/#sec-quotejsonstring
  67  * Requires that the destination has enough space allocated for src after
  68  * escaping (that is, `2 + 6 * (srcEnd - srcBegin)` characters).
  69  */
  70 template <typename SrcCharT, typename DstCharT>
  71 static MOZ_ALWAYS_INLINE RangedPtr<DstCharT> InfallibleQuoteJSONString(
  72     RangedPtr<const SrcCharT> srcBegin, RangedPtr<const SrcCharT> srcEnd,
  73     RangedPtr<DstCharT> dstPtr) {
  74   // Maps characters < 256 to the value that must follow the '\\' in the quoted
  75   // string. Entries with 'u' are handled as \\u00xy, and entries with 0 are not
  76   // escaped in any way. Characters >= 256 are all assumed to be unescaped.
  77   static const Latin1Char escapeLookup[256] = {
  78       // clang-format off
  79         'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'b', 't',
  80         'n', 'u', 'f', 'r', 'u', 'u', 'u', 'u', 'u', 'u',
  81         'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u',
  82         'u', 'u', 0,   0,  '\"', 0,   0,   0,   0,   0,
  83         0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  84         0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  85         0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  86         0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  87         0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
  88         0,   0,  '\\', // rest are all zeros
  89       // clang-format on
  90   };
  91
  92   /* Step 1. */
  93   *dstPtr++ = '"';
  94
  95   auto ToLowerHex = [](uint8_t u) {
  96     MOZ_ASSERT(u <= 0xF);
  97     return "0123456789abcdef"[u];
  98   };
  99
 100   /* Step 2. */
 101   while (srcBegin != srcEnd) {
 102     const SrcCharT c = *srcBegin++;
 103
 104     // Handle the Latin-1 cases.
 105     if (MOZ_LIKELY(c < sizeof(escapeLookup))) {
 106       Latin1Char escaped = escapeLookup[c];
 107
 108       // Directly copy non-escaped code points.
 109       if (escaped == 0) {
 110         *dstPtr++ = c;
 111         continue;
 112       }
 113
 114       // Escape the rest, elaborating Unicode escapes when needed.
 115       *dstPtr++ = '\\';
 116       *dstPtr++ = escaped;
 117       if (escaped == 'u') {
 118         *dstPtr++ = '0';
 119         *dstPtr++ = '0';
 120
 121         uint8_t x = c >> 4;
 122         MOZ_ASSERT(x < 10);
 123         *dstPtr++ = '0' + x;
 124
 125         *dstPtr++ = ToLowerHex(c & 0xF);
 126       }
 127
 128       continue;
 129     }
 130
 131     // Non-ASCII non-surrogates are directly copied.
 132     if (!unicode::IsSurrogate(c)) {
 133       *dstPtr++ = c;
 134       continue;
 135     }
 136
 137     // So too for complete surrogate pairs.
 138     if (MOZ_LIKELY(unicode::IsLeadSurrogate(c) && srcBegin < srcEnd &&
 139                    unicode::IsTrailSurrogate(*srcBegin))) {
 140       *dstPtr++ = c;
 141       *dstPtr++ = *srcBegin++;
 142       continue;
 143     }
 144
 145     // But lone surrogates are Unicode-escaped.
 146     char32_t as32 = char32_t(c);
 147     *dstPtr++ = '\\';
 148     *dstPtr++ = 'u';
 149     *dstPtr++ = ToLowerHex(as32 >> 12);
 150     *dstPtr++ = ToLowerHex((as32 >> 8) & 0xF);
 151     *dstPtr++ = ToLowerHex((as32 >> 4) & 0xF);
 152     *dstPtr++ = ToLowerHex(as32 & 0xF);
 153   }
 154
 155   /* Steps 3-4. */
 156   *dstPtr++ = '"';
 157   return dstPtr;
 158 }
 159
 160 template <typename SrcCharT, typename DstCharT>
 161 static size_t QuoteJSONStringHelper(const JSLinearString& linear,
 162                                     StringBuffer& sb, size_t sbOffset) {
 163   size_t len = linear.length();
 164
 165   JS::AutoCheckCannotGC nogc;
 166   RangedPtr<const SrcCharT> srcBegin{linear.chars<SrcCharT>(nogc), len};
 167   RangedPtr<DstCharT> dstBegin{sb.begin<DstCharT>(), sb.begin<DstCharT>(),
 168                                sb.end<DstCharT>()};
 169   RangedPtr<DstCharT> dstEnd =
 170       InfallibleQuoteJSONString(srcBegin, srcBegin + len, dstBegin + sbOffset);
 171
 172   return dstEnd - dstBegin;
 173 }
 174
 175 static bool QuoteJSONString(JSContext* cx, StringBuffer& sb, JSString* str) {
 176   JSLinearString* linear = str->ensureLinear(cx);
 177   if (!linear) {
 178     return false;
 179   }
 180
 181   if (linear->hasTwoByteChars() && !sb.ensureTwoByteChars()) {
 182     return false;
 183   }
 184
 185   // We resize the backing buffer to the maximum size we could possibly need,
 186   // write the escaped string into it, and shrink it back to the size we ended
 187   // up needing.
 188
 189   size_t len = linear->length();
 190   size_t sbInitialLen = sb.length();
 191
 192   CheckedInt<size_t> reservedLen = CheckedInt<size_t>(len) * 6 + 2;
 193   if (MOZ_UNLIKELY(!reservedLen.isValid())) {
 194     ReportAllocationOverflow(cx);
 195     return false;
 196   }
 197
 198   if (!sb.growByUninitialized(reservedLen.value())) {
 199     return false;
 200   }
 201
 202   size_t newSize;
 203
 204   if (linear->hasTwoByteChars()) {
 205     newSize =
 206         QuoteJSONStringHelper<char16_t, char16_t>(*linear, sb, sbInitialLen);
 207   } else if (sb.isUnderlyingBufferLatin1()) {
 208     newSize = QuoteJSONStringHelper<Latin1Char, Latin1Char>(*linear, sb,
 209                                                             sbInitialLen);
 210   } else {
 211     newSize =
 212         QuoteJSONStringHelper<Latin1Char, char16_t>(*linear, sb, sbInitialLen);
 213   }
 214
 215   sb.shrinkTo(newSize);
 216
 217   return true;
 218 }
 219
 220 namespace {
 221
 222 using ObjectVector = GCVector<JSObject*, 8>;
 223
 224 class StringifyContext {
 225  public:
 226   StringifyContext(JSContext* cx, StringBuffer& sb, const StringBuffer& gap,
 227                    HandleObject replacer, const RootedIdVector& propertyList,
 228                    bool maybeSafely)
 229       : sb(sb),
 230         gap(gap),
 231         replacer(cx, replacer),
 232         stack(cx, ObjectVector(cx)),
 233         propertyList(propertyList),
 234         depth(0),
 235         maybeSafely(maybeSafely) {
 236     MOZ_ASSERT_IF(maybeSafely, !replacer);
 237     MOZ_ASSERT_IF(maybeSafely, gap.empty());
 238   }
 239
 240   StringBuffer& sb;
 241   const StringBuffer& gap;
 242   RootedObject replacer;
 243   Rooted<ObjectVector> stack;
 244   const RootedIdVector& propertyList;
 245   uint32_t depth;
 246   bool maybeSafely;
 247 };
 248
 249 } /* anonymous namespace */
 250
 251 static bool SerializeJSONProperty(JSContext* cx, const Value& v,
 252                                   StringifyContext* scx);
 253
 254 static bool WriteIndent(StringifyContext* scx, uint32_t limit) {
 255   if (!scx->gap.empty()) {
 256     if (!scx->sb.append('\n')) {
 257       return false;
 258     }
 259
 260     if (scx->gap.isUnderlyingBufferLatin1()) {
 261       for (uint32_t i = 0; i < limit; i++) {
 262         if (!scx->sb.append(scx->gap.rawLatin1Begin(),
 263                             scx->gap.rawLatin1End())) {
 264           return false;
 265         }
 266       }
 267     } else {
 268       for (uint32_t i = 0; i < limit; i++) {
 269         if (!scx->sb.append(scx->gap.rawTwoByteBegin(),
 270                             scx->gap.rawTwoByteEnd())) {
 271           return false;
 272         }
 273       }
 274     }
 275   }
 276
 277   return true;
 278 }
 279
 280 namespace {
 281
 282 template <typename KeyType>
 283 class KeyStringifier {};
 284
 285 template <>
 286 class KeyStringifier<uint32_t> {
 287  public:
 288   static JSString* toString(JSContext* cx, uint32_t index) {
 289     return IndexToString(cx, index);
 290   }
 291 };
 292
 293 template <>
 294 class KeyStringifier<HandleId> {
 295  public:
 296   static JSString* toString(JSContext* cx, HandleId id) {
 297     return IdToString(cx, id);
 298   }
 299 };
 300
 301 } /* anonymous namespace */
 302
 303 /*
 304  * https://262.ecma-international.org/14.0/#sec-serializejsonproperty, steps
 305  * 2-4, extracted to enable preprocessing of property values when stringifying
 306  * objects in SerializeJSONObject.
 307  */
 308 template <typename KeyType>
 309 static bool PreprocessValue(JSContext* cx, HandleObject holder, KeyType key,
 310                             MutableHandleValue vp, StringifyContext* scx) {
 311   // We don't want to do any preprocessing here if scx->maybeSafely,
 312   // since the stuff we do here can have side-effects.
 313   if (scx->maybeSafely) {
 314     return true;
 315   }
 316
 317   RootedString keyStr(cx);
 318
 319   // Step 2. Modified by BigInt spec 6.1 to check for a toJSON method on the
 320   // BigInt prototype when the value is a BigInt, and to pass the BigInt
 321   // primitive value as receiver.
 322   if (vp.isObject() || vp.isBigInt()) {
 323     RootedValue toJSON(cx);
 324     RootedObject obj(cx, JS::ToObject(cx, vp));
 325     if (!obj) {
 326       return false;
 327     }
 328
 329     if (!GetProperty(cx, obj, vp, cx->names().toJSON, &toJSON)) {
 330       return false;
 331     }
 332
 333     if (IsCallable(toJSON)) {
 334       keyStr = KeyStringifier<KeyType>::toString(cx, key);
 335       if (!keyStr) {
 336         return false;
 337       }
 338
 339       RootedValue arg0(cx, StringValue(keyStr));
 340       if (!js::Call(cx, toJSON, vp, arg0, vp)) {
 341         return false;
 342       }
 343     }
 344   }
 345
 346   /* Step 3. */
 347   if (scx->replacer && scx->replacer->isCallable()) {
 348     MOZ_ASSERT(holder != nullptr,
 349                "holder object must be present when replacer is callable");
 350
 351     if (!keyStr) {
 352       keyStr = KeyStringifier<KeyType>::toString(cx, key);
 353       if (!keyStr) {
 354         return false;
 355       }
 356     }
 357
 358     RootedValue arg0(cx, StringValue(keyStr));
 359     RootedValue replacerVal(cx, ObjectValue(*scx->replacer));
 360     if (!js::Call(cx, replacerVal, holder, arg0, vp, vp)) {
 361       return false;
 362     }
 363   }
 364
 365   /* Step 4. */
 366   if (vp.get().isObject()) {
 367     RootedObject obj(cx, &vp.get().toObject());
 368
 369     ESClass cls;
 370     if (!JS::GetBuiltinClass(cx, obj, &cls)) {
 371       return false;
 372     }
 373
 374     if (cls == ESClass::Number) {
 375       double d;
 376       if (!ToNumber(cx, vp, &d)) {
 377         return false;
 378       }
 379       vp.setNumber(d);
 380     } else if (cls == ESClass::String) {
 381       JSString* str = ToStringSlow<CanGC>(cx, vp);
 382       if (!str) {
 383         return false;
 384       }
 385       vp.setString(str);
 386     } else if (cls == ESClass::Boolean || cls == ESClass::BigInt ||
 387                IF_RECORD_TUPLE(
 388                    obj->is<RecordObject>() || obj->is<TupleObject>(), false)) {
 389       if (!Unbox(cx, obj, vp)) {
 390         return false;
 391       }
 392     }
 393   }
 394
 395   return true;
 396 }
 397
 398 /*
 399  * Determines whether a value which has passed by
 400  * https://262.ecma-international.org/14.0/#sec-serializejsonproperty steps
 401  * 1-4's gauntlet will result in SerializeJSONProperty returning |undefined|.
 402  * This function is used to properly omit properties resulting in such values
 403  * when stringifying objects, while properly stringifying such properties as
 404  * null when they're encountered in arrays.
 405  */
 406 static inline bool IsFilteredValue(const Value& v) {
 407   MOZ_ASSERT_IF(v.isMagic(), v.isMagic(JS_ELEMENTS_HOLE));
 408   return v.isUndefined() || v.isSymbol() || v.isMagic() || IsCallable(v);
 409 }
 410
 411 class CycleDetector {
 412  public:
 413   CycleDetector(StringifyContext* scx, HandleObject obj)
 414       : stack_(&scx->stack), obj_(obj), appended_(false) {}
 415
 416   MOZ_ALWAYS_INLINE bool foundCycle(JSContext* cx) {
 417     JSObject* obj = obj_;
 418     for (JSObject* obj2 : stack_) {
 419       if (MOZ_UNLIKELY(obj == obj2)) {
 420         JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
 421                                   JSMSG_JSON_CYCLIC_VALUE);
 422         return false;
 423       }
 424     }
 425     appended_ = stack_.append(obj);
 426     return appended_;
 427   }
 428
 429   ~CycleDetector() {
 430     if (MOZ_LIKELY(appended_)) {
 431       MOZ_ASSERT(stack_.back() == obj_);
 432       stack_.popBack();
 433     }
 434   }
 435
 436  private:
 437   MutableHandle<ObjectVector> stack_;
 438   HandleObject obj_;
 439   bool appended_;
 440 };
 441
 442 static inline JSString* MaybeGetRawJSON(JSContext* cx, JSObject* obj) {
 443   if (!obj->is<RawJSONObject>()) {
 444     return nullptr;
 445   }
 446
 447   JSString* rawJSON = obj->as<js::RawJSONObject>().rawJSON(cx);
 448   MOZ_ASSERT(rawJSON);
 449   return rawJSON;
 450 }
 451
 452 #ifdef ENABLE_RECORD_TUPLE
 453 enum class JOType { Record, Object };
 454 template <JOType type = JOType::Object>
 455 #endif
 456 /* https://262.ecma-international.org/14.0/#sec-serializejsonobject */
 457 static bool SerializeJSONObject(JSContext* cx, HandleObject obj,
 458                                 StringifyContext* scx) {
 459   /*
 460    * This method implements the SerializeJSONObject algorithm, but:
 461    *
 462    *   * The algorithm is somewhat reformulated to allow the final string to
 463    *     be streamed into a single buffer, rather than be created and copied
 464    *     into place incrementally as the algorithm specifies it.  This
 465    *     requires moving portions of the SerializeJSONProperty call in 8a into
 466    *     this algorithm (and in SerializeJSONArray as well).
 467    */
 468
 469 #ifdef ENABLE_RECORD_TUPLE
 470   RecordType* rec;
 471
 472   if constexpr (type == JOType::Record) {
 473     MOZ_ASSERT(obj->is<RecordType>());
 474     rec = &obj->as<RecordType>();
 475   } else {
 476     MOZ_ASSERT(!IsExtendedPrimitive(*obj));
 477   }
 478 #endif
 479   MOZ_ASSERT_IF(scx->maybeSafely, obj->is<PlainObject>());
 480
 481   /* Steps 1-2, 11. */
 482   CycleDetector detect(scx, obj);
 483   if (!detect.foundCycle(cx)) {
 484     return false;
 485   }
 486
 487   if (!scx->sb.append('{')) {
 488     return false;
 489   }
 490
 491   /* Steps 5-7. */
 492   Maybe<RootedIdVector> ids;
 493   const RootedIdVector* props;
 494   if (scx->replacer && !scx->replacer->isCallable()) {
 495     // NOTE: We can't assert |IsArray(scx->replacer)| because the replacer
 496     //       might have been a revocable proxy to an array.  Such a proxy
 497     //       satisfies |IsArray|, but any side effect of JSON.stringify
 498     //       could revoke the proxy so that |!IsArray(scx->replacer)|.  See
 499     //       bug 1196497.
 500     props = &scx->propertyList;
 501   } else {
 502     MOZ_ASSERT_IF(scx->replacer, scx->propertyList.length() == 0);
 503     ids.emplace(cx);
 504     if (!GetPropertyKeys(cx, obj, JSITER_OWNONLY, ids.ptr())) {
 505       return false;
 506     }
 507     props = ids.ptr();
 508   }
 509
 510   /* My kingdom for not-quite-initialized-from-the-start references. */
 511   const RootedIdVector& propertyList = *props;
 512
 513   /* Steps 8-10, 13. */
 514   bool wroteMember = false;
 515   RootedId id(cx);
 516   for (size_t i = 0, len = propertyList.length(); i < len; i++) {
 517     if (!CheckForInterrupt(cx)) {
 518       return false;
 519     }
 520
 521     /*
 522      * Steps 8a-8b.  Note that the call to SerializeJSONProperty is broken up
 523      * into 1) getting the property; 2) processing for toJSON, calling the
 524      * replacer, and handling boxed Number/String/Boolean objects; 3) filtering
 525      * out values which process to |undefined|, and 4) stringifying all values
 526      * which pass the filter.
 527      */
 528     id = propertyList[i];
 529     RootedValue outputValue(cx);
 530 #ifdef DEBUG
 531     if (scx->maybeSafely) {
 532       PropertyResult prop;
 533       if (!NativeLookupOwnPropertyNoResolve(cx, &obj->as<NativeObject>(), id,
 534                                             &prop)) {
 535         return false;
 536       }
 537       MOZ_ASSERT(prop.isNativeProperty() &&
 538                  prop.propertyInfo().isDataDescriptor());
 539     }
 540 #endif  // DEBUG
 541
 542 #ifdef ENABLE_RECORD_TUPLE
 543     if constexpr (type == JOType::Record) {
 544       MOZ_ALWAYS_TRUE(rec->getOwnProperty(cx, id, &outputValue));
 545     } else
 546 #endif
 547     {
 548       RootedValue objValue(cx, ObjectValue(*obj));
 549       if (!GetProperty(cx, obj, objValue, id, &outputValue)) {
 550         return false;
 551       }
 552     }
 553     if (!PreprocessValue(cx, obj, HandleId(id), &outputValue, scx)) {
 554       return false;
 555     }
 556     if (IsFilteredValue(outputValue)) {
 557       continue;
 558     }
 559
 560     /* Output a comma unless this is the first member to write. */
 561     if (wroteMember && !scx->sb.append(',')) {
 562       return false;
 563     }
 564     wroteMember = true;
 565
 566     if (!WriteIndent(scx, scx->depth)) {
 567       return false;
 568     }
 569
 570     JSString* s = IdToString(cx, id);
 571     if (!s) {
 572       return false;
 573     }
 574
 575     if (!QuoteJSONString(cx, scx->sb, s) || !scx->sb.append(':') ||
 576         !(scx->gap.empty() || scx->sb.append(' ')) ||
 577         !SerializeJSONProperty(cx, outputValue, scx)) {
 578       return false;
 579     }
 580   }
 581
 582   if (wroteMember && !WriteIndent(scx, scx->depth - 1)) {
 583     return false;
 584   }
 585
 586   return scx->sb.append('}');
 587 }
 588
 589 // For JSON.stringify and JSON.parse with a reviver function, we need to know
 590 // the length of an object for which JS::IsArray returned true. This must be
 591 // either an ArrayObject or a proxy wrapping one.
 592 static MOZ_ALWAYS_INLINE bool GetLengthPropertyForArrayLike(JSContext* cx,
 593                                                             HandleObject obj,
 594                                                             uint32_t* lengthp) {
 595   if (MOZ_LIKELY(obj->is<ArrayObject>())) {
 596     *lengthp = obj->as<ArrayObject>().length();
 597     return true;
 598   }
 599 #ifdef ENABLE_RECORD_TUPLE
 600   if (obj->is<TupleType>()) {
 601     *lengthp = obj->as<TupleType>().length();
 602     return true;
 603   }
 604 #endif
 605
 606   MOZ_ASSERT(obj->is<ProxyObject>());
 607
 608   uint64_t len = 0;
 609   if (!GetLengthProperty(cx, obj, &len)) {
 610     return false;
 611   }
 612
 613   // A scripted proxy wrapping an array can return a length value larger than
 614   // UINT32_MAX. Stringification will likely report an OOM in this case. Match
 615   // other JS engines and report an early error in this case, although
 616   // technically this is observable, for example when stringifying with a
 617   // replacer function.
 618   if (len > UINT32_MAX) {
 619     ReportAllocationOverflow(cx);
 620     return false;
 621   }
 622
 623   *lengthp = uint32_t(len);
 624   return true;
 625 }
 626
 627 /* https://262.ecma-international.org/14.0/#sec-serializejsonarray */
 628 static bool SerializeJSONArray(JSContext* cx, HandleObject obj,
 629                                StringifyContext* scx) {
 630   /*
 631    * This method implements the SerializeJSONArray algorithm, but:
 632    *
 633    *   * The algorithm is somewhat reformulated to allow the final string to
 634    *     be streamed into a single buffer, rather than be created and copied
 635    *     into place incrementally as the algorithm specifies it.  This
 636    *     requires moving portions of the SerializeJSONProperty call in 8a into
 637    *     this algorithm (and in SerializeJSONObject as well).
 638    */
 639
 640   /* Steps 1-2, 11. */
 641   CycleDetector detect(scx, obj);
 642   if (!detect.foundCycle(cx)) {
 643     return false;
 644   }
 645
 646   if (!scx->sb.append('[')) {
 647     return false;
 648   }
 649
 650   /* Step 6. */
 651   uint32_t length;
 652   if (!GetLengthPropertyForArrayLike(cx, obj, &length)) {
 653     return false;
 654   }
 655
 656   /* Steps 7-10. */
 657   if (length != 0) {
 658     /* Steps 4, 10b(i). */
 659     if (!WriteIndent(scx, scx->depth)) {
 660       return false;
 661     }
 662
 663     /* Steps 7-10. */
 664     RootedValue outputValue(cx);
 665     for (uint32_t i = 0; i < length; i++) {
 666       if (!CheckForInterrupt(cx)) {
 667         return false;
 668       }
 669
 670       /*
 671        * Steps 8a-8c.  Again note how the call to the spec's
 672        * SerializeJSONProperty method is broken up into getting the property,
 673        * running it past toJSON and the replacer and maybe unboxing, and
 674        * interpreting some values as |null| in separate steps.
 675        */
 676 #ifdef DEBUG
 677       if (scx->maybeSafely) {
 678         /*
 679          * Trying to do a JS_AlreadyHasOwnElement runs the risk of
 680          * hitting OOM on jsid creation.  Let's just assert sanity for
 681          * small enough indices.
 682          */
 683         MOZ_ASSERT(obj->is<ArrayObject>());
 684         MOZ_ASSERT(obj->is<NativeObject>());
 685         Rooted<NativeObject*> nativeObj(cx, &obj->as<NativeObject>());
 686         if (i <= PropertyKey::IntMax) {
 687           MOZ_ASSERT(
 688               nativeObj->containsDenseElement(i) != nativeObj->isIndexed(),
 689               "the array must either be small enough to remain "
 690               "fully dense (and otherwise un-indexed), *or* "
 691               "all its initially-dense elements were sparsified "
 692               "and the object is indexed");
 693         } else {
 694           MOZ_ASSERT(nativeObj->isIndexed());
 695         }
 696       }
 697 #endif
 698       if (!GetElement(cx, obj, i, &outputValue)) {
 699         return false;
 700       }
 701       if (!PreprocessValue(cx, obj, i, &outputValue, scx)) {
 702         return false;
 703       }
 704       if (IsFilteredValue(outputValue)) {
 705         if (!scx->sb.append("null")) {
 706           return false;
 707         }
 708       } else {
 709         if (!SerializeJSONProperty(cx, outputValue, scx)) {
 710           return false;
 711         }
 712       }
 713
 714       /* Steps 3, 4, 10b(i). */
 715       if (i < length - 1) {
 716         if (!scx->sb.append(',')) {
 717           return false;
 718         }
 719         if (!WriteIndent(scx, scx->depth)) {
 720           return false;
 721         }
 722       }
 723     }
 724
 725     /* Step 10(b)(iii). */
 726     if (!WriteIndent(scx, scx->depth - 1)) {
 727       return false;
 728     }
 729   }
 730
 731   return scx->sb.append(']');
 732 }
 733
 734 /* https://262.ecma-international.org/14.0/#sec-serializejsonproperty */
 735 static bool SerializeJSONProperty(JSContext* cx, const Value& v,
 736                                   StringifyContext* scx) {
 737   /* Step 12 must be handled by the caller. */
 738   MOZ_ASSERT(!IsFilteredValue(v));
 739
 740   /*
 741    * This method implements the SerializeJSONProperty algorithm, but:
 742    *
 743    *   * We move property retrieval (step 1) into callers to stream the
 744    *     stringification process and avoid constantly copying strings.
 745    *   * We move the preprocessing in steps 2-4 into a helper function to
 746    *     allow both SerializeJSONObject and SerializeJSONArray to use this
 747    * method.  While SerializeJSONArray could use it without this move,
 748    * SerializeJSONObject must omit any |undefined|-valued property per so it
 749    * can't stream out a value using the SerializeJSONProperty method exactly as
 750    * defined by the spec.
 751    *   * We move step 12 into callers, again to ease streaming.
 752    */
 753
 754   /* Step 8. */
 755   if (v.isString()) {
 756     return QuoteJSONString(cx, scx->sb, v.toString());
 757   }
 758
 759   /* Step 5. */
 760   if (v.isNull()) {
 761     return scx->sb.append("null");
 762   }
 763
 764   /* Steps 6-7. */
 765   if (v.isBoolean()) {
 766     return v.toBoolean() ? scx->sb.append("true") : scx->sb.append("false");
 767   }
 768
 769   /* Step 9. */
 770   if (v.isNumber()) {
 771     if (v.isDouble()) {
 772       if (!std::isfinite(v.toDouble())) {
 773         MOZ_ASSERT(!scx->maybeSafely,
 774                    "input JS::ToJSONMaybeSafely must not include "
 775                    "reachable non-finite numbers");
 776         return scx->sb.append("null");
 777       }
 778     }
 779
 780     return NumberValueToStringBuffer(v, scx->sb);
 781   }
 782
 783   /* Step 10. */
 784   if (v.isBigInt()) {
 785     JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
 786                               JSMSG_BIGINT_NOT_SERIALIZABLE);
 787     return false;
 788   }
 789
 790   AutoCheckRecursionLimit recursion(cx);
 791   if (!recursion.check(cx)) {
 792     return false;
 793   }
 794
 795   /* Step 11. */
 796   MOZ_ASSERT(v.hasObjectPayload());
 797   RootedObject obj(cx, &v.getObjectPayload());
 798
 799   /* https://tc39.es/proposal-json-parse-with-source/#sec-serializejsonproperty
 800    * Step 4a.*/
 801   if (JSString* rawJSON = MaybeGetRawJSON(cx, obj)) {
 802     return scx->sb.append(rawJSON);
 803   }
 804
 805   MOZ_ASSERT(
 806       !scx->maybeSafely || obj->is<PlainObject>() || obj->is<ArrayObject>(),
 807       "input to JS::ToJSONMaybeSafely must not include reachable "
 808       "objects that are neither arrays nor plain objects");
 809
 810   scx->depth++;
 811   auto dec = mozilla::MakeScopeExit([&] { scx->depth--; });
 812
 813 #ifdef ENABLE_RECORD_TUPLE
 814   if (v.isExtendedPrimitive()) {
 815     if (obj->is<RecordType>()) {
 816       return SerializeJSONObject<JOType::Record>(cx, obj, scx);
 817     }
 818     if (obj->is<TupleType>()) {
 819       return SerializeJSONArray(cx, obj, scx);
 820     }
 821     MOZ_CRASH("Unexpected extended primitive - boxes cannot be stringified.");
 822   }
 823 #endif
 824
 825   bool isArray;
 826   if (!IsArray(cx, obj, &isArray)) {
 827     return false;
 828   }
 829
 830   return isArray ? SerializeJSONArray(cx, obj, scx)
 831                  : SerializeJSONObject(cx, obj, scx);
 832 }
 833
 834 static bool CanFastStringifyObject(NativeObject* obj) {
 835   if (ClassCanHaveExtraEnumeratedProperties(obj->getClass())) {
 836     return false;
 837   }
 838
 839   if (obj->is<ArrayObject>()) {
 840     // Arrays will look up all keys [0..length) so disallow anything that could
 841     // find those keys anywhere but in the dense elements.
 842     if (!IsPackedArray(obj) && ObjectMayHaveExtraIndexedProperties(obj)) {
 843       return false;
 844     }
 845   } else {
 846     // Non-Arrays will only look at own properties, but still disallow any
 847     // indexed properties other than in the dense elements because they would
 848     // require sorting.
 849     if (ObjectMayHaveExtraIndexedOwnProperties(obj)) {
 850       return false;
 851     }
 852   }
 853
 854   // Only used for internal environment objects that should never be passed to
 855   // JSON.stringify.
 856   MOZ_ASSERT(!obj->getOpsLookupProperty());
 857
 858 #ifdef ENABLE_RECORD_TUPLE
 859   if (ObjectValue(*obj).isExtendedPrimitive()) {
 860     return false;
 861   }
 862 #endif
 863
 864   return true;
 865 }
 866
 867 #define FOR_EACH_STRINGIFY_BAIL_REASON(MACRO) \
 868   MACRO(NO_REASON)                            \
 869   MACRO(INELIGIBLE_OBJECT)                    \
 870   MACRO(DEEP_RECURSION)                       \
 871   MACRO(NON_DATA_PROPERTY)                    \
 872   MACRO(TOO_MANY_PROPERTIES)                  \
 873   MACRO(BIGINT)                               \
 874   MACRO(API)                                  \
 875   MACRO(HAVE_REPLACER)                        \
 876   MACRO(HAVE_SPACE)                           \
 877   MACRO(PRIMITIVE)                            \
 878   MACRO(HAVE_TOJSON)                          \
 879   MACRO(IMPURE_LOOKUP)                        \
 880   MACRO(INTERRUPT)
 881
 882 enum class BailReason : uint8_t {
 883 #define DECLARE_ENUM(name) name,
 884   FOR_EACH_STRINGIFY_BAIL_REASON(DECLARE_ENUM)
 885 #undef DECLARE_ENUM
 886 };
 887
 888 static const char* DescribeStringifyBailReason(BailReason whySlow) {
 889   switch (whySlow) {
 890 #define ENUM_NAME(name)  \
 891   case BailReason::name: \
 892     return #name;
 893     FOR_EACH_STRINGIFY_BAIL_REASON(ENUM_NAME)
 894 #undef ENUM_NAME
 895     default:
 896       return "Unknown";
 897   }
 898 }
 899
 900 // Iterator over all the dense elements of an object. Used
 901 // for both Arrays and non-Arrays.
 902 class DenseElementsIteratorForJSON {
 903   HeapSlotArray elements;
 904   uint32_t element;
 905
 906   // Arrays can have a length less than getDenseInitializedLength(), in which
 907   // case the remaining Array elements are treated as UndefinedValue.
 908   uint32_t numElements;
 909   uint32_t length;
 910
 911  public:
 912   explicit DenseElementsIteratorForJSON(NativeObject* nobj)
 913       : elements(nobj->getDenseElements()),
 914         element(0),
 915         numElements(nobj->getDenseInitializedLength()) {
 916     length = nobj->is<ArrayObject>() ? nobj->as<ArrayObject>().length()
 917                                      : numElements;
 918   }
 919
 920   bool done() const { return element == length; }
 921
 922   Value next() {
 923     // For Arrays, steps 6-8 of
 924     // https://262.ecma-international.org/14.0/#sec-serializejsonarray. For
 925     // non-Arrays, step 6a of
 926     // https://262.ecma-international.org/14.0/#sec-serializejsonobject
 927     // following the order from
 928     // https://262.ecma-international.org/14.0/#sec-ordinaryownpropertykeys
 929
 930     MOZ_ASSERT(!done());
 931     auto i = element++;
 932     // Consider specializing the iterator for Arrays vs non-Arrays to avoid this
 933     // branch.
 934     return i < numElements ? elements.begin()[i] : UndefinedValue();
 935   }
 936
 937   uint32_t getIndex() const { return element; }
 938 };
 939
 940 // An iterator over the non-element properties of a Shape, returned in forward
 941 // (creation) order. Note that it is fallible, so after iteration is complete
 942 // isOverflowed() should be called to verify that the results are actually
 943 // complete.
 944
 945 class ShapePropertyForwardIterNoGC {
 946   // Pointer to the current PropMap with length and an index within it.
 947   PropMap* map_;
 948   uint32_t mapLength_;
 949   uint32_t i_ = 0;
 950
 951   // Stack of PropMaps to iterate through, oldest properties on top. The current
 952   // map (map_, above) is never on this stack.
 953   mozilla::Vector<PropMap*> stack_;
 954
 955   const NativeShape* shape_;
 956
 957   MOZ_ALWAYS_INLINE void settle() {
 958     while (true) {
 959       if (MOZ_UNLIKELY(i_ == mapLength_)) {
 960         i_ = 0;
 961         if (stack_.empty()) {
 962           mapLength_ = 0;  // Done
 963           return;
 964         }
 965         map_ = stack_.back();
 966         stack_.popBack();
 967         mapLength_ =
 968             stack_.empty() ? shape_->propMapLength() : PropMap::Capacity;
 969       } else if (MOZ_UNLIKELY(shape_->isDictionary() && !map_->hasKey(i_))) {
 970         // Dictionary maps can have "holes" for removed properties, so keep
 971         // going until we find a non-hole slot.
 972         i_++;
 973       } else {
 974         return;
 975       }
 976     }
 977   }
 978
 979  public:
 980   explicit ShapePropertyForwardIterNoGC(NativeShape* shape) : shape_(shape) {
 981     // Set map_ to the PropMap containing the first property (the deepest map in
 982     // the previous() chain). Push pointers to all other PropMaps onto stack_.
 983     map_ = shape->propMap();
 984     if (!map_) {
 985       // No properties.
 986       i_ = mapLength_ = 0;
 987       return;
 988     }
 989     while (map_->hasPrevious()) {
 990       if (!stack_.append(map_)) {
 991         // Overflowed.
 992         i_ = mapLength_ = UINT32_MAX;
 993         return;
 994       }
 995       map_ = map_->asLinked()->previous();
 996     }
 997
 998     // Set mapLength_ to the number of properties in map_ (including dictionary
 999     // holes, if any.)
1000     mapLength_ = stack_.empty() ? shape_->propMapLength() : PropMap::Capacity;
1001
1002     settle();
1003   }
1004
1005   bool done() const { return i_ == mapLength_; }
1006   bool isOverflowed() const { return i_ == UINT32_MAX; }
1007
1008   void operator++(int) {
1009     MOZ_ASSERT(!done());
1010     i_++;
1011     settle();
1012   }
1013
1014   PropertyInfoWithKey get() const {
1015     MOZ_ASSERT(!done());
1016     return map_->getPropertyInfoWithKey(i_);
1017   }
1018
1019   PropertyInfoWithKey operator*() const { return get(); }
1020
1021   // Fake pointer struct to make operator-> work.
1022   // See https://stackoverflow.com/a/52856349.
1023   struct FakePtr {
1024     PropertyInfoWithKey val_;
1025     const PropertyInfoWithKey* operator->() const { return &val_; }
1026   };
1027   FakePtr operator->() const { return {get()}; }
1028 };
1029
1030 // Iterator over EnumerableOwnProperties
1031 // https://262.ecma-international.org/14.0/#sec-enumerableownproperties
1032 // that fails if it encounters any accessor properties, as they are not handled
1033 // by JSON FastSerializeJSONProperty, or if it sees too many properties on one
1034 // object.
1035 class OwnNonIndexKeysIterForJSON {
1036   ShapePropertyForwardIterNoGC shapeIter;
1037   bool done_ = false;
1038   BailReason fastFailed_ = BailReason::NO_REASON;
1039
1040   void settle() {
1041     // Skip over any non-enumerable or Symbol properties, and permanently fail
1042     // if any enumerable non-data properties are encountered.
1043     for (; !shapeIter.done(); shapeIter++) {
1044       if (!shapeIter->enumerable()) {
1045         continue;
1046       }
1047       if (!shapeIter->isDataProperty()) {
1048         fastFailed_ = BailReason::NON_DATA_PROPERTY;
1049         done_ = true;
1050         return;
1051       }
1052       PropertyKey id = shapeIter->key();
1053       if (!id.isSymbol()) {
1054         return;
1055       }
1056     }
1057     done_ = true;
1058   }
1059
1060  public:
1061   explicit OwnNonIndexKeysIterForJSON(const NativeObject* nobj)
1062       : shapeIter(nobj->shape()) {
1063     if (MOZ_UNLIKELY(shapeIter.isOverflowed())) {
1064       fastFailed_ = BailReason::TOO_MANY_PROPERTIES;
1065       done_ = true;
1066       return;
1067     }
1068     if (!nobj->hasEnumerableProperty()) {
1069       // Non-Arrays with no enumerable properties can just be skipped.
1070       MOZ_ASSERT(!nobj->is<ArrayObject>());
1071       done_ = true;
1072       return;
1073     }
1074     settle();
1075   }
1076
1077   bool done() const { return done_ || shapeIter.done(); }
1078   BailReason cannotFastStringify() const { return fastFailed_; }
1079
1080   PropertyInfoWithKey next() {
1081     MOZ_ASSERT(!done());
1082     PropertyInfoWithKey prop = shapeIter.get();
1083     shapeIter++;
1084     settle();
1085     return prop;
1086   }
1087 };
1088
1089 // Steps from https://262.ecma-international.org/14.0/#sec-serializejsonproperty
1090 static bool EmitSimpleValue(JSContext* cx, StringBuffer& sb, const Value& v) {
1091   /* Step 8. */
1092   if (v.isString()) {
1093     return QuoteJSONString(cx, sb, v.toString());
1094   }
1095
1096   /* Step 5. */
1097   if (v.isNull()) {
1098     return sb.append("null");
1099   }
1100
1101   /* Steps 6-7. */
1102   if (v.isBoolean()) {
1103     return v.toBoolean() ? sb.append("true") : sb.append("false");
1104   }
1105
1106   /* Step 9. */
1107   if (v.isNumber()) {
1108     if (v.isDouble()) {
1109       if (!std::isfinite(v.toDouble())) {
1110         return sb.append("null");
1111       }
1112     }
1113
1114     return NumberValueToStringBuffer(v, sb);
1115   }
1116
1117   // Unrepresentable values.
1118   if (v.isUndefined() || v.isMagic()) {
1119     MOZ_ASSERT_IF(v.isMagic(), v.isMagic(JS_ELEMENTS_HOLE));
1120     return sb.append("null");
1121   }
1122
1123   /* Step 10. */
1124   MOZ_CRASH("should have validated printable simple value already");
1125 }
1126
1127 // https://262.ecma-international.org/14.0/#sec-serializejsonproperty step 8b
1128 // where K is an integer index.
1129 static bool EmitQuotedIndexColon(StringBuffer& sb, uint32_t index) {
1130   Int32ToCStringBuf cbuf;
1131   size_t cstrlen;
1132   const char* cstr = ::Int32ToCString(&cbuf, index, &cstrlen);
1133   if (!sb.reserve(sb.length() + 1 + cstrlen + 1 + 1)) {
1134     return false;
1135   }
1136   sb.infallibleAppend('"');
1137   sb.infallibleAppend(cstr, cstrlen);
1138   sb.infallibleAppend('"');
1139   sb.infallibleAppend(':');
1140   return true;
1141 }
1142
1143 // Similar to PreprocessValue: replace the value with a simpler one to
1144 // stringify, but also detect whether the value is compatible with the fast
1145 // path. If not, bail out by setting *whySlow and returning true.
1146 static bool PreprocessFastValue(JSContext* cx, Value* vp, StringifyContext* scx,
1147                                 BailReason* whySlow) {
1148   MOZ_ASSERT(!scx->maybeSafely);
1149
1150   // Steps are from
1151   // https://262.ecma-international.org/14.0/#sec-serializejsonproperty
1152
1153   // Disallow BigInts to avoid caring about BigInt.prototype.toJSON.
1154   if (vp->isBigInt()) {
1155     *whySlow = BailReason::BIGINT;
1156     return true;
1157   }
1158
1159   if (!vp->isObject()) {
1160     return true;
1161   }
1162
1163   if (!vp->toObject().is<NativeObject>()) {
1164     *whySlow = BailReason::INELIGIBLE_OBJECT;
1165     return true;
1166   }
1167
1168   // Step 2: lookup a .toJSON property (and bail if found).
1169   NativeObject* obj = &vp->toObject().as<NativeObject>();
1170   PropertyResult toJSON;
1171   NativeObject* holder;
1172   PropertyKey id = NameToId(cx->names().toJSON);
1173   if (!NativeLookupPropertyInline<NoGC, LookupResolveMode::CheckMayResolve>(
1174           cx, obj, id, &holder, &toJSON)) {
1175     // Looking up this property would require a side effect.
1176     *whySlow = BailReason::IMPURE_LOOKUP;
1177     return true;
1178   }
1179   if (toJSON.isFound()) {
1180     *whySlow = BailReason::HAVE_TOJSON;
1181     return true;
1182   }
1183
1184   // Step 4: convert primitive wrapper objects to primitives. Disallowed for
1185   // fast path.
1186   if (obj->is<NumberObject>() || obj->is<StringObject>() ||
1187       obj->is<BooleanObject>() || obj->is<BigIntObject>() ||
1188       IF_RECORD_TUPLE(obj->is<RecordObject>() || obj->is<TupleObject>(),
1189                       false)) {
1190     // Primitive wrapper objects can invoke arbitrary code when being coerced to
1191     // their primitive values (eg via @@toStringTag).
1192     *whySlow = BailReason::INELIGIBLE_OBJECT;
1193     return true;
1194   }
1195
1196   if (obj->isCallable()) {
1197     // Steps 11,12: Callable objects are treated as undefined.
1198     vp->setUndefined();
1199     return true;
1200   }
1201
1202   if (!CanFastStringifyObject(obj)) {
1203     *whySlow = BailReason::INELIGIBLE_OBJECT;
1204     return true;
1205   }
1206
1207   return true;
1208 }
1209
1210 // FastSerializeJSONProperty maintains an explicit stack to handle nested
1211 // objects. For each object, first the dense elements are iterated, then the
1212 // named properties (included sparse indexes, which will cause
1213 // FastSerializeJSONProperty to bail out.)
1214 //
1215 // The iterators for each of those parts are not merged into a single common
1216 // iterator because the interface is different for the two parts, and they are
1217 // handled separately in the FastSerializeJSONProperty code.
1218 struct FastStackEntry {
1219   NativeObject* nobj;
1220   Variant<DenseElementsIteratorForJSON, OwnNonIndexKeysIterForJSON> iter;
1221   bool isArray;  // Cached nobj->is<ArrayObject>()
1222
1223   // Given an object, a FastStackEntry starts with the dense elements. The
1224   // caller is expected to inspect the variant to use it differently based on
1225   // which iterator is active.
1226   explicit FastStackEntry(NativeObject* obj)
1227       : nobj(obj),
1228         iter(AsVariant(DenseElementsIteratorForJSON(obj))),
1229         isArray(obj->is<ArrayObject>()) {}
1230
1231   // Called by Vector when moving data around.
1232   FastStackEntry(FastStackEntry&& other) noexcept
1233       : nobj(other.nobj), iter(std::move(other.iter)), isArray(other.isArray) {}
1234
1235   // Move assignment, called when updating the `top` entry.
1236   void operator=(FastStackEntry&& other) noexcept {
1237     nobj = other.nobj;
1238     iter = std::move(other.iter);
1239     isArray = other.isArray;
1240   }
1241
1242   // Advance from dense elements to the named properties.
1243   void advanceToProperties() {
1244     iter = AsVariant(OwnNonIndexKeysIterForJSON(nobj));
1245   }
1246 };
1247
1248 /* https://262.ecma-international.org/14.0/#sec-serializejsonproperty */
1249 static bool FastSerializeJSONProperty(JSContext* cx, Handle<Value> v,
1250                                       StringifyContext* scx,
1251                                       BailReason* whySlow) {
1252   MOZ_ASSERT(*whySlow == BailReason::NO_REASON);
1253   MOZ_ASSERT(v.isObject());
1254
1255   if (JSString* rawJSON = MaybeGetRawJSON(cx, &v.toObject())) {
1256     return scx->sb.append(rawJSON);
1257   }
1258
1259   /*
1260    * FastSerializeJSONProperty is an optimistic fast path for the
1261    * SerializeJSONProperty algorithm that applies in limited situations. It
1262    * falls back to SerializeJSONProperty() if:
1263    *
1264    *   * Any externally visible code attempts to run: getter, enumerate
1265    *     hook, toJSON property.
1266    *   * Sparse index found (this would require accumulating props and sorting.)
1267    *   * Max stack depth is reached. (This will also detect self-referential
1268    *     input.)
1269    *
1270    *  Algorithm:
1271    *
1272    *    stack = []
1273    *    top = iter(obj)
1274    *    wroteMember = false
1275    *    OUTER: while true:
1276    *      if !wroteMember:
1277    *        emit("[" or "{")
1278    *      while !top.done():
1279    *        key, value = top.next()
1280    *        if top is a non-Array and value is skippable:
1281    *          continue
1282    *        if wroteMember:
1283    *          emit(",")
1284    *        wroteMember = true
1285    *        if value is object:
1286    *          emit(key + ":") if top is iterating a non-Array
1287    *          stack.push(top)
1288    *          top <- value
1289    *          wroteMember = false
1290    *          continue OUTER
1291    *        else:
1292    *          emit(value) or emit(key + ":" + value)
1293    *      emit("]" or "}")
1294    *      if stack is empty: done!
1295    *      top <- stack.pop()
1296    *      wroteMember = true
1297    *
1298    * except:
1299    *
1300    *   * The `while !top.done()` loop is split into the dense element portion
1301    *     and the slot portion. Each is iterated to completion before advancing
1302    *     or finishing.
1303    *
1304    *   * For Arrays, the named properties are not output, but they are still
1305    *     scanned to bail if any numeric keys are found that could be indexes.
1306    */
1307
1308   // FastSerializeJSONProperty will bail if an interrupt is requested in the
1309   // middle of an operation, so handle any interrupts now before starting. Note:
1310   // this can GC, but after this point nothing should be able to GC unless
1311   // something fails, so rooting is unnecessary.
1312   if (!CheckForInterrupt(cx)) {
1313     return false;
1314   }
1315
1316   constexpr size_t MAX_STACK_DEPTH = 20;
1317   Vector<FastStackEntry> stack(cx);
1318   if (!stack.reserve(MAX_STACK_DEPTH - 1)) {
1319     return false;
1320   }
1321   // Construct an iterator for the object,
1322   // https://262.ecma-international.org/14.0/#sec-serializejsonobject step 6:
1323   // EnumerableOwnPropertyNames or
1324   // https://262.ecma-international.org/14.0/#sec-serializejsonarray step 7-8.
1325   FastStackEntry top(&v.toObject().as<NativeObject>());
1326   bool wroteMember = false;
1327
1328   if (!CanFastStringifyObject(top.nobj)) {
1329     *whySlow = BailReason::INELIGIBLE_OBJECT;
1330     return true;
1331   }
1332
1333   while (true) {
1334     if (!wroteMember) {
1335       if (!scx->sb.append(top.isArray ? '[' : '{')) {
1336         return false;
1337       }
1338     }
1339
1340     if (top.iter.is<DenseElementsIteratorForJSON>()) {
1341       auto& iter = top.iter.as<DenseElementsIteratorForJSON>();
1342       bool nestedObject = false;
1343       while (!iter.done()) {
1344         // Interrupts can GC and we are working with unrooted pointers.
1345         if (cx->hasPendingInterrupt(InterruptReason::CallbackUrgent) ||
1346             cx->hasPendingInterrupt(InterruptReason::CallbackCanWait)) {
1347           *whySlow = BailReason::INTERRUPT;
1348           return true;
1349         }
1350
1351         uint32_t index = iter.getIndex();
1352         Value val = iter.next();
1353
1354         if (!PreprocessFastValue(cx, &val, scx, whySlow)) {
1355           return false;
1356         }
1357         if (*whySlow != BailReason::NO_REASON) {
1358           return true;
1359         }
1360         if (IsFilteredValue(val)) {
1361           if (top.isArray) {
1362             // Arrays convert unrepresentable values to "null".
1363             val = UndefinedValue();
1364           } else {
1365             // Objects skip unrepresentable values.
1366             continue;
1367           }
1368         }
1369
1370         if (wroteMember && !scx->sb.append(',')) {
1371           return false;
1372         }
1373         wroteMember = true;
1374
1375         if (!top.isArray) {
1376           if (!EmitQuotedIndexColon(scx->sb, index)) {
1377             return false;
1378           }
1379         }
1380
1381         if (val.isObject()) {
1382           if (JSString* rawJSON = MaybeGetRawJSON(cx, &val.toObject())) {
1383             if (!scx->sb.append(rawJSON)) {
1384               return false;
1385             }
1386           } else {
1387             if (stack.length() >= MAX_STACK_DEPTH - 1) {
1388               *whySlow = BailReason::DEEP_RECURSION;
1389               return true;
1390             }
1391             // Save the current iterator position on the stack and
1392             // switch to processing the nested value.
1393             stack.infallibleAppend(std::move(top));
1394             top = FastStackEntry(&val.toObject().as<NativeObject>());
1395             wroteMember = false;
1396             nestedObject = true;  // Break out to the outer loop.
1397             break;
1398           }
1399         } else if (!EmitSimpleValue(cx, scx->sb, val)) {
1400           return false;
1401         }
1402       }
1403
1404       if (nestedObject) {
1405         continue;  // Break out to outer loop.
1406       }
1407
1408       MOZ_ASSERT(iter.done());
1409       if (top.isArray) {
1410         MOZ_ASSERT(!top.nobj->isIndexed() || IsPackedArray(top.nobj));
1411       } else {
1412         top.advanceToProperties();
1413       }
1414     }
1415
1416     if (top.iter.is<OwnNonIndexKeysIterForJSON>()) {
1417       auto& iter = top.iter.as<OwnNonIndexKeysIterForJSON>();
1418       bool nesting = false;
1419       while (!iter.done()) {
1420         // Interrupts can GC and we are working with unrooted pointers.
1421         if (cx->hasPendingInterrupt(InterruptReason::CallbackUrgent) ||
1422             cx->hasPendingInterrupt(InterruptReason::CallbackCanWait)) {
1423           *whySlow = BailReason::INTERRUPT;
1424           return true;
1425         }
1426
1427         PropertyInfoWithKey prop = iter.next();
1428
1429         // A non-Array with indexed elements would need to sort the indexes
1430         // numerically, which this code does not support. These objects are
1431         // skipped when obj->isIndexed(), so no index properties should be found
1432         // here.
1433         mozilla::DebugOnly<uint32_t> index = -1;
1434         MOZ_ASSERT(!IdIsIndex(prop.key(), &index));
1435
1436         Value val = top.nobj->getSlot(prop.slot());
1437         if (!PreprocessFastValue(cx, &val, scx, whySlow)) {
1438           return false;
1439         }
1440         if (*whySlow != BailReason::NO_REASON) {
1441           return true;
1442         }
1443         if (IsFilteredValue(val)) {
1444           // Undefined check in
1445           // https://262.ecma-international.org/14.0/#sec-serializejsonobject
1446           // step 8b, covering undefined, symbol
1447           continue;
1448         }
1449
1450         if (wroteMember && !scx->sb.append(",")) {
1451           return false;
1452         }
1453         wroteMember = true;
1454
1455         MOZ_ASSERT(prop.key().isString());
1456         if (!QuoteJSONString(cx, scx->sb, prop.key().toString())) {
1457           return false;
1458         }
1459
1460         if (!scx->sb.append(':')) {
1461           return false;
1462         }
1463         if (val.isObject()) {
1464           if (JSString* rawJSON = MaybeGetRawJSON(cx, &val.toObject())) {
1465             if (!scx->sb.append(rawJSON)) {
1466               return false;
1467             }
1468           } else {
1469             if (stack.length() >= MAX_STACK_DEPTH - 1) {
1470               *whySlow = BailReason::DEEP_RECURSION;
1471               return true;
1472             }
1473             // Save the current iterator position on the stack and
1474             // switch to processing the nested value.
1475             stack.infallibleAppend(std::move(top));
1476             top = FastStackEntry(&val.toObject().as<NativeObject>());
1477             wroteMember = false;
1478             nesting = true;  // Break out to the outer loop.
1479             break;
1480           }
1481         } else if (!EmitSimpleValue(cx, scx->sb, val)) {
1482           return false;
1483         }
1484       }
1485       *whySlow = iter.cannotFastStringify();
1486       if (*whySlow != BailReason::NO_REASON) {
1487         return true;
1488       }
1489       if (nesting) {
1490         continue;  // Break out to outer loop.
1491       }
1492       MOZ_ASSERT(iter.done());
1493     }
1494
1495     if (!scx->sb.append(top.isArray ? ']' : '}')) {
1496       return false;
1497     }
1498     if (stack.empty()) {
1499       return true;  // Success!
1500     }
1501     top = std::move(stack.back());
1502
1503     stack.popBack();
1504     wroteMember = true;
1505   }
1506 }
1507
1508 /* https://262.ecma-international.org/14.0/#sec-json.stringify */
1509 bool js::Stringify(JSContext* cx, MutableHandleValue vp, JSObject* replacer_,
1510                    const Value& space_, StringBuffer& sb,
1511                    StringifyBehavior stringifyBehavior) {
1512   RootedObject replacer(cx, replacer_);
1513   RootedValue space(cx, space_);
1514
1515   MOZ_ASSERT_IF(stringifyBehavior == StringifyBehavior::RestrictedSafe,
1516                 space.isNull());
1517   MOZ_ASSERT_IF(stringifyBehavior == StringifyBehavior::RestrictedSafe,
1518                 vp.isObject());
1519   /**
1520    * This uses MOZ_ASSERT, since it's actually asserting something jsapi
1521    * consumers could get wrong, so needs a better error message.
1522    */
1523   MOZ_ASSERT(stringifyBehavior != StringifyBehavior::RestrictedSafe ||
1524                  vp.toObject().is<PlainObject>() ||
1525                  vp.toObject().is<ArrayObject>(),
1526              "input to JS::ToJSONMaybeSafely must be a plain object or array");
1527
1528   /* Step 5. */
1529   RootedIdVector propertyList(cx);
1530   BailReason whySlow = BailReason::NO_REASON;
1531   if (stringifyBehavior == StringifyBehavior::SlowOnly ||
1532       stringifyBehavior == StringifyBehavior::RestrictedSafe) {
1533     whySlow = BailReason::API;
1534   }
1535   if (replacer) {
1536     whySlow = BailReason::HAVE_REPLACER;
1537     bool isArray;
1538     if (replacer->isCallable()) {
1539       /* Step 5a(i): use replacer to transform values.  */
1540     } else if (!IsArray(cx, replacer, &isArray)) {
1541       return false;
1542     } else if (isArray) {
1543       /* Step 5b(ii). */
1544
1545       /* Step 5b(ii)(2). */
1546       uint32_t len;
1547       if (!GetLengthPropertyForArrayLike(cx, replacer, &len)) {
1548         return false;
1549       }
1550
1551       // Cap the initial size to a moderately small value.  This avoids
1552       // ridiculous over-allocation if an array with bogusly-huge length
1553       // is passed in.  If we end up having to add elements past this
1554       // size, the set will naturally resize to accommodate them.
1555       const uint32_t MaxInitialSize = 32;
1556       Rooted<GCHashSet<jsid>> idSet(
1557           cx, GCHashSet<jsid>(cx, std::min(len, MaxInitialSize)));
1558
1559       /* Step 5b(ii)(3). */
1560       uint32_t k = 0;
1561
1562       /* Step 5b(ii)(4). */
1563       RootedValue item(cx);
1564       for (; k < len; k++) {
1565         if (!CheckForInterrupt(cx)) {
1566           return false;
1567         }
1568
1569         /* Step 5b(ii)(4)(a-b). */
1570         if (!GetElement(cx, replacer, k, &item)) {
1571           return false;
1572         }
1573
1574         /* Step 5b(ii)(4)(c-g). */
1575         RootedId id(cx);
1576         if (item.isNumber() || item.isString()) {
1577           if (!PrimitiveValueToId<CanGC>(cx, item, &id)) {
1578             return false;
1579           }
1580         } else {
1581           ESClass cls;
1582           if (!GetClassOfValue(cx, item, &cls)) {
1583             return false;
1584           }
1585
1586           if (cls != ESClass::String && cls != ESClass::Number) {
1587             continue;
1588           }
1589
1590           JSAtom* atom = ToAtom<CanGC>(cx, item);
1591           if (!atom) {
1592             return false;
1593           }
1594
1595           id.set(AtomToId(atom));
1596         }
1597
1598         /* Step 5b(ii)(4)(g). */
1599         auto p = idSet.lookupForAdd(id);
1600         if (!p) {
1601           /* Step 5b(ii)(4)(g)(i). */
1602           if (!idSet.add(p, id) || !propertyList.append(id)) {
1603             return false;
1604           }
1605         }
1606       }
1607     } else {
1608       replacer = nullptr;
1609     }
1610   }
1611
1612   /* Step 6. */
1613   if (space.isObject()) {
1614     RootedObject spaceObj(cx, &space.toObject());
1615
1616     ESClass cls;
1617     if (!JS::GetBuiltinClass(cx, spaceObj, &cls)) {
1618       return false;
1619     }
1620
1621     if (cls == ESClass::Number) {
1622       double d;
1623       if (!ToNumber(cx, space, &d)) {
1624         return false;
1625       }
1626       space = NumberValue(d);
1627     } else if (cls == ESClass::String) {
1628       JSString* str = ToStringSlow<CanGC>(cx, space);
1629       if (!str) {
1630         return false;
1631       }
1632       space = StringValue(str);
1633     }
1634   }
1635
1636   StringBuffer gap(cx);
1637
1638   if (space.isNumber()) {
1639     /* Step 7. */
1640     double d;
1641     MOZ_ALWAYS_TRUE(ToInteger(cx, space, &d));
1642     d = std::min(10.0, d);
1643     if (d >= 1 && !gap.appendN(' ', uint32_t(d))) {
1644       return false;
1645     }
1646   } else if (space.isString()) {
1647     /* Step 8. */
1648     JSLinearString* str = space.toString()->ensureLinear(cx);
1649     if (!str) {
1650       return false;
1651     }
1652     size_t len = std::min(size_t(10), str->length());
1653     if (!gap.appendSubstring(str, 0, len)) {
1654       return false;
1655     }
1656   } else {
1657     /* Step 9. */
1658     MOZ_ASSERT(gap.empty());
1659   }
1660   if (!gap.empty()) {
1661     whySlow = BailReason::HAVE_SPACE;
1662   }
1663
1664   Rooted<PlainObject*> wrapper(cx);
1665   RootedId emptyId(cx, NameToId(cx->names().empty_));
1666   if (replacer && replacer->isCallable()) {
1667     // We can skip creating the initial wrapper object if no replacer
1668     // function is present.
1669
1670     /* Step 10. */
1671     wrapper = NewPlainObject(cx);
1672     if (!wrapper) {
1673       return false;
1674     }
1675
1676     /* Step 11. */
1677     if (!NativeDefineDataProperty(cx, wrapper, emptyId, vp, JSPROP_ENUMERATE)) {
1678       return false;
1679     }
1680   }
1681
1682   /* Step 13. */
1683   Rooted<JSAtom*> fastJSON(cx);
1684   if (whySlow == BailReason::NO_REASON) {
1685     MOZ_ASSERT(propertyList.empty());
1686     MOZ_ASSERT(stringifyBehavior != StringifyBehavior::RestrictedSafe);
1687     StringifyContext scx(cx, sb, gap, nullptr, propertyList, false);
1688     if (!PreprocessFastValue(cx, vp.address(), &scx, &whySlow)) {
1689       return false;
1690     }
1691     if (!vp.isObject()) {
1692       // "Fast" stringify of primitives would create a wrapper object and thus
1693       // be slower than regular stringify.
1694       whySlow = BailReason::PRIMITIVE;
1695     }
1696     if (whySlow == BailReason::NO_REASON) {
1697       if (!FastSerializeJSONProperty(cx, vp, &scx, &whySlow)) {
1698         return false;
1699       }
1700       if (whySlow == BailReason::NO_REASON) {
1701         // Fast stringify succeeded!
1702         if (stringifyBehavior != StringifyBehavior::Compare) {
1703           return true;
1704         }
1705         fastJSON = scx.sb.finishAtom();
1706         if (!fastJSON) {
1707           return false;
1708         }
1709       }
1710       scx.sb.clear();  // Preserves allocated space.
1711     }
1712   }
1713
1714   if (MOZ_UNLIKELY((stringifyBehavior == StringifyBehavior::FastOnly) &&
1715                    (whySlow != BailReason::NO_REASON))) {
1716     JS_ReportErrorASCII(cx, "JSON stringify failed mandatory fast path: %s",
1717                         DescribeStringifyBailReason(whySlow));
1718     return false;
1719   }
1720
1721   // Slow, general path.
1722
1723   StringifyContext scx(cx, sb, gap, replacer, propertyList,
1724                        stringifyBehavior == StringifyBehavior::RestrictedSafe);
1725   if (!PreprocessValue(cx, wrapper, HandleId(emptyId), vp, &scx)) {
1726     return false;
1727   }
1728   if (IsFilteredValue(vp)) {
1729     return true;
1730   }
1731
1732   if (!SerializeJSONProperty(cx, vp, &scx)) {
1733     return false;
1734   }
1735
1736   // For StringBehavior::Compare, when the fast path succeeded.
1737   if (MOZ_UNLIKELY(fastJSON)) {
1738     JSAtom* slowJSON = scx.sb.finishAtom();
1739     if (!slowJSON) {
1740       return false;
1741     }
1742     if (fastJSON != slowJSON) {
1743       MOZ_CRASH("JSON.stringify mismatch between fast and slow paths");
1744     }
1745     // Put the JSON back into the StringBuffer for returning.
1746     if (!sb.append(slowJSON)) {
1747       return false;
1748     }
1749   }
1750
1751   return true;
1752 }
1753
1754 /* https://262.ecma-international.org/14.0/#sec-internalizejsonproperty */
1755 static bool InternalizeJSONProperty(
1756     JSContext* cx, HandleObject holder, HandleId name, HandleValue reviver,
1757     MutableHandle<ParseRecordObject> parseRecord, MutableHandleValue vp) {
1758   AutoCheckRecursionLimit recursion(cx);
1759   if (!recursion.check(cx)) {
1760     return false;
1761   }
1762
1763   /* Step 1. */
1764   RootedValue val(cx);
1765   if (!GetProperty(cx, holder, holder, name, &val)) {
1766     return false;
1767   }
1768
1769 #ifdef ENABLE_JSON_PARSE_WITH_SOURCE
1770   RootedObject context(cx);
1771   Rooted<UniquePtr<ParseRecordObject::EntryMap>> entries(cx);
1772   if (JS::Prefs::experimental_json_parse_with_source()) {
1773     // https://tc39.es/proposal-json-parse-with-source/#sec-internalizejsonproperty
1774     bool sameVal = false;
1775     Rooted<Value> parsedValue(cx, parseRecord.get().value);
1776     if (!SameValue(cx, parsedValue, val, &sameVal)) {
1777       return false;
1778     }
1779     if (!parseRecord.get().isEmpty() && sameVal) {
1780       if (parseRecord.get().parseNode) {
1781         MOZ_ASSERT(!val.isObject());
1782         Rooted<IdValueVector> props(cx, cx);
1783         if (!props.emplaceBack(
1784                 IdValuePair(NameToId(cx->names().source),
1785                             StringValue(parseRecord.get().parseNode)))) {
1786           return false;
1787         }
1788         context = NewPlainObjectWithUniqueNames(cx, props);
1789         if (!context) {
1790           return false;
1791         }
1792       }
1793       entries = std::move(parseRecord.get().entries);
1794     }
1795     if (!context) {
1796       context = NewPlainObject(cx);
1797       if (!context) {
1798         return false;
1799       }
1800     }
1801   }
1802 #endif
1803
1804   /* Step 2. */
1805   if (val.isObject()) {
1806     RootedObject obj(cx, &val.toObject());
1807
1808     bool isArray;
1809     if (!IsArray(cx, obj, &isArray)) {
1810       return false;
1811     }
1812
1813     if (isArray) {
1814       /* Step 2b(i). */
1815       uint32_t length;
1816       if (!GetLengthPropertyForArrayLike(cx, obj, &length)) {
1817         return false;
1818       }
1819
1820       /* Steps 2b(ii-iii). */
1821       RootedId id(cx);
1822       RootedValue newElement(cx);
1823       for (uint32_t i = 0; i < length; i++) {
1824         if (!CheckForInterrupt(cx)) {
1825           return false;
1826         }
1827
1828         if (!IndexToId(cx, i, &id)) {
1829           return false;
1830         }
1831
1832         /* Step 2a(iii)(1). */
1833         Rooted<ParseRecordObject> elementRecord(cx);
1834 #ifdef ENABLE_JSON_PARSE_WITH_SOURCE
1835         if (entries) {
1836           if (auto entry = entries->lookup(id)) {
1837             elementRecord = std::move(entry->value());
1838           }
1839         }
1840 #endif
1841         if (!InternalizeJSONProperty(cx, obj, id, reviver, &elementRecord,
1842                                      &newElement)) {
1843           return false;
1844         }
1845
1846         ObjectOpResult ignored;
1847         if (newElement.isUndefined()) {
1848           /* Step 2b(iii)(3). The spec deliberately ignores strict failure. */
1849           if (!DeleteProperty(cx, obj, id, ignored)) {
1850             return false;
1851           }
1852         } else {
1853           /* Step 2b(iii)(4). The spec deliberately ignores strict failure. */
1854           Rooted<PropertyDescriptor> desc(
1855               cx, PropertyDescriptor::Data(newElement,
1856                                            {JS::PropertyAttribute::Configurable,
1857                                             JS::PropertyAttribute::Enumerable,
1858                                             JS::PropertyAttribute::Writable}));
1859           if (!DefineProperty(cx, obj, id, desc, ignored)) {
1860             return false;
1861           }
1862         }
1863       }
1864     } else {
1865       /* Step 2c(i). */
1866       RootedIdVector keys(cx);
1867       if (!GetPropertyKeys(cx, obj, JSITER_OWNONLY, &keys)) {
1868         return false;
1869       }
1870
1871       /* Step 2c(ii). */
1872       RootedId id(cx);
1873       RootedValue newElement(cx);
1874       for (size_t i = 0, len = keys.length(); i < len; i++) {
1875         if (!CheckForInterrupt(cx)) {
1876           return false;
1877         }
1878
1879         /* Step 2c(ii)(1). */
1880         id = keys[i];
1881         Rooted<ParseRecordObject> entryRecord(cx);
1882 #ifdef ENABLE_JSON_PARSE_WITH_SOURCE
1883         if (entries) {
1884           if (auto entry = entries->lookup(id)) {
1885             entryRecord = std::move(entry->value());
1886           }
1887         }
1888 #endif
1889         if (!InternalizeJSONProperty(cx, obj, id, reviver, &entryRecord,
1890                                      &newElement)) {
1891           return false;
1892         }
1893
1894         ObjectOpResult ignored;
1895         if (newElement.isUndefined()) {
1896           /* Step 2c(ii)(2). The spec deliberately ignores strict failure. */
1897           if (!DeleteProperty(cx, obj, id, ignored)) {
1898             return false;
1899           }
1900         } else {
1901           /* Step 2c(ii)(3). The spec deliberately ignores strict failure. */
1902           Rooted<PropertyDescriptor> desc(
1903               cx, PropertyDescriptor::Data(newElement,
1904                                            {JS::PropertyAttribute::Configurable,
1905                                             JS::PropertyAttribute::Enumerable,
1906                                             JS::PropertyAttribute::Writable}));
1907           if (!DefineProperty(cx, obj, id, desc, ignored)) {
1908             return false;
1909           }
1910         }
1911       }
1912     }
1913   }
1914
1915   /* Step 3. */
1916   RootedString key(cx, IdToString(cx, name));
1917   if (!key) {
1918     return false;
1919   }
1920
1921   RootedValue keyVal(cx, StringValue(key));
1922 #ifdef ENABLE_JSON_PARSE_WITH_SOURCE
1923   if (JS::Prefs::experimental_json_parse_with_source()) {
1924     RootedValue contextVal(cx, ObjectValue(*context));
1925     return js::Call(cx, reviver, holder, keyVal, val, contextVal, vp);
1926   }
1927 #endif
1928   return js::Call(cx, reviver, holder, keyVal, val, vp);
1929 }
1930
1931 static bool Revive(JSContext* cx, HandleValue reviver,
1932                    MutableHandle<ParseRecordObject> pro,
1933                    MutableHandleValue vp) {
1934   Rooted<PlainObject*> obj(cx, NewPlainObject(cx));
1935   if (!obj) {
1936     return false;
1937   }
1938
1939   if (!DefineDataProperty(cx, obj, cx->names().empty_, vp)) {
1940     return false;
1941   }
1942
1943 #ifdef ENABLE_JSON_PARSE_WITH_SOURCE
1944   MOZ_ASSERT_IF(JS::Prefs::experimental_json_parse_with_source(),
1945                 pro.get().value == vp.get());
1946 #endif
1947   Rooted<jsid> id(cx, NameToId(cx->names().empty_));
1948   return InternalizeJSONProperty(cx, obj, id, reviver, pro, vp);
1949 }
1950
1951 template <typename CharT>
1952 bool ParseJSON(JSContext* cx, const mozilla::Range<const CharT> chars,
1953                MutableHandleValue vp) {
1954   Rooted<JSONParser<CharT>> parser(cx, cx, chars,
1955                                    JSONParser<CharT>::ParseType::JSONParse);
1956   return parser.parse(vp);
1957 }
1958
1959 template <typename CharT>
1960 bool js::ParseJSONWithReviver(JSContext* cx,
1961                               const mozilla::Range<const CharT> chars,
1962                               HandleValue reviver, MutableHandleValue vp) {
1963   /* https://262.ecma-international.org/14.0/#sec-json.parse steps 2-10. */
1964   Rooted<ParseRecordObject> pro(cx);
1965 #ifdef ENABLE_JSON_PARSE_WITH_SOURCE
1966   if (JS::Prefs::experimental_json_parse_with_source() && IsCallable(reviver)) {
1967     Rooted<JSONReviveParser<CharT>> parser(cx, cx, chars);
1968     if (!parser.get().parse(vp, &pro)) {
1969       return false;
1970     }
1971   } else
1972 #endif
1973       if (!ParseJSON(cx, chars, vp)) {
1974     return false;
1975   }
1976
1977   /* Steps 11-12. */
1978   if (IsCallable(reviver)) {
1979     return Revive(cx, reviver, &pro, vp);
1980   }
1981   return true;
1982 }
1983
1984 template bool js::ParseJSONWithReviver(
1985     JSContext* cx, const mozilla::Range<const Latin1Char> chars,
1986     HandleValue reviver, MutableHandleValue vp);
1987
1988 template bool js::ParseJSONWithReviver(
1989     JSContext* cx, const mozilla::Range<const char16_t> chars,
1990     HandleValue reviver, MutableHandleValue vp);
1991
1992 static bool json_toSource(JSContext* cx, unsigned argc, Value* vp) {
1993   CallArgs args = CallArgsFromVp(argc, vp);
1994   args.rval().setString(cx->names().JSON);
1995   return true;
1996 }
1997
1998 /* https://262.ecma-international.org/14.0/#sec-json.parse */
1999 static bool json_parse(JSContext* cx, unsigned argc, Value* vp) {
2000   AutoJSMethodProfilerEntry pseudoFrame(cx, "JSON", "parse");
2001   CallArgs args = CallArgsFromVp(argc, vp);
2002
2003   /* Step 1. */
2004   JSString* str = (args.length() >= 1) ? ToString<CanGC>(cx, args[0])
2005                                        : cx->names().undefined;
2006   if (!str) {
2007     return false;
2008   }
2009
2010   JSLinearString* linear = str->ensureLinear(cx);
2011   if (!linear) {
2012     return false;
2013   }
2014
2015   AutoStableStringChars linearChars(cx);
2016   if (!linearChars.init(cx, linear)) {
2017     return false;
2018   }
2019
2020   HandleValue reviver = args.get(1);
2021
2022   /* Steps 2-12. */
2023   return linearChars.isLatin1()
2024              ? ParseJSONWithReviver(cx, linearChars.latin1Range(), reviver,
2025                                     args.rval())
2026              : ParseJSONWithReviver(cx, linearChars.twoByteRange(), reviver,
2027                                     args.rval());
2028 }
2029
2030 #ifdef ENABLE_RECORD_TUPLE
2031 bool BuildImmutableProperty(JSContext* cx, HandleValue value, HandleId name,
2032                             HandleValue reviver,
2033                             MutableHandleValue immutableRes) {
2034   MOZ_ASSERT(!name.isSymbol());
2035
2036   // Step 1
2037   if (value.isObject()) {
2038     RootedValue childValue(cx), newElement(cx);
2039     RootedId childName(cx);
2040
2041     // Step 1.a-1.b
2042     if (value.toObject().is<ArrayObject>()) {
2043       Rooted<ArrayObject*> arr(cx, &value.toObject().as<ArrayObject>());
2044
2045       // Step 1.b.iii
2046       uint32_t len = arr->length();
2047
2048       TupleType* tup = TupleType::createUninitialized(cx, len);
2049       if (!tup) {
2050         return false;
2051       }
2052       immutableRes.setExtendedPrimitive(*tup);
2053
2054       // Step 1.b.iv
2055       for (uint32_t i = 0; i < len; i++) {
2056         // Step 1.b.iv.1
2057         childName.set(PropertyKey::Int(i));
2058
2059         // Step 1.b.iv.2
2060         if (!GetProperty(cx, arr, value, childName, &childValue)) {
2061           return false;
2062         }
2063
2064         // Step 1.b.iv.3
2065         if (!BuildImmutableProperty(cx, childValue, childName, reviver,
2066                                     &newElement)) {
2067           return false;
2068         }
2069         MOZ_ASSERT(newElement.isPrimitive());
2070
2071         // Step 1.b.iv.5
2072         if (!tup->initializeNextElement(cx, newElement)) {
2073           return false;
2074         }
2075       }
2076
2077       // Step 1.b.v
2078       tup->finishInitialization(cx);
2079     } else {
2080       RootedObject obj(cx, &value.toObject());
2081
2082       // Step 1.c.i - We only get the property keys rather than the
2083       // entries, but the difference is not observable from user code
2084       // because `obj` is a plan object not exposed externally
2085       RootedIdVector props(cx);
2086       if (!GetPropertyKeys(cx, obj, JSITER_OWNONLY, &props)) {
2087         return false;
2088       }
2089
2090       RecordType* rec = RecordType::createUninitialized(cx, props.length());
2091       if (!rec) {
2092         return false;
2093       }
2094       immutableRes.setExtendedPrimitive(*rec);
2095
2096       for (uint32_t i = 0; i < props.length(); i++) {
2097         // Step 1.c.iii.1
2098         childName.set(props[i]);
2099
2100         // Step 1.c.iii.2
2101         if (!GetProperty(cx, obj, value, childName, &childValue)) {
2102           return false;
2103         }
2104
2105         // Step 1.c.iii.3
2106         if (!BuildImmutableProperty(cx, childValue, childName, reviver,
2107                                     &newElement)) {
2108           return false;
2109         }
2110         MOZ_ASSERT(newElement.isPrimitive());
2111
2112         // Step 1.c.iii.5
2113         if (!newElement.isUndefined()) {
2114           // Step 1.c.iii.5.a-b
2115           rec->initializeNextProperty(cx, childName, newElement);
2116         }
2117       }
2118
2119       // Step 1.c.iv
2120       rec->finishInitialization(cx);
2121     }
2122   } else {
2123     // Step 2.a
2124     immutableRes.set(value);
2125   }
2126
2127   // Step 3
2128   if (IsCallable(reviver)) {
2129     RootedValue keyVal(cx, StringValue(IdToString(cx, name)));
2130
2131     // Step 3.a
2132     if (!Call(cx, reviver, UndefinedHandleValue, keyVal, immutableRes,
2133               immutableRes)) {
2134       return false;
2135     }
2136
2137     // Step 3.b
2138     if (!immutableRes.isPrimitive()) {
2139       JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
2140                                 JSMSG_RECORD_TUPLE_NO_OBJECT);
2141       return false;
2142     }
2143   }
2144
2145   return true;
2146 }
2147
2148 static bool json_parseImmutable(JSContext* cx, unsigned argc, Value* vp) {
2149   AutoJSMethodProfilerEntry pseudoFrame(cx, "JSON", "parseImmutable");
2150   CallArgs args = CallArgsFromVp(argc, vp);
2151
2152   /* Step 1. */
2153   JSString* str = (args.length() >= 1) ? ToString<CanGC>(cx, args[0])
2154                                        : cx->names().undefined;
2155   if (!str) {
2156     return false;
2157   }
2158
2159   JSLinearString* linear = str->ensureLinear(cx);
2160   if (!linear) {
2161     return false;
2162   }
2163
2164   AutoStableStringChars linearChars(cx);
2165   if (!linearChars.init(cx, linear)) {
2166     return false;
2167   }
2168
2169   HandleValue reviver = args.get(1);
2170   RootedValue unfiltered(cx);
2171
2172   if (linearChars.isLatin1()) {
2173     if (!ParseJSON(cx, linearChars.latin1Range(), &unfiltered)) {
2174       return false;
2175     }
2176   } else {
2177     if (!ParseJSON(cx, linearChars.twoByteRange(), &unfiltered)) {
2178       return false;
2179     }
2180   }
2181
2182   RootedId id(cx, NameToId(cx->names().empty_));
2183   return BuildImmutableProperty(cx, unfiltered, id, reviver, args.rval());
2184 }
2185 #endif
2186
2187 #ifdef ENABLE_JSON_PARSE_WITH_SOURCE
2188 /* https://tc39.es/proposal-json-parse-with-source/#sec-json.israwjson */
2189 static bool json_isRawJSON(JSContext* cx, unsigned argc, Value* vp) {
2190   AutoJSMethodProfilerEntry pseudoFrame(cx, "JSON", "isRawJSON");
2191   CallArgs args = CallArgsFromVp(argc, vp);
2192
2193   /* Step 1. */
2194   if (args.get(0).isObject()) {
2195     Rooted<JSObject*> obj(cx, &args[0].toObject());
2196 #  ifdef DEBUG
2197     if (obj->is<RawJSONObject>()) {
2198       bool objIsFrozen = false;
2199       MOZ_ASSERT(js::TestIntegrityLevel(cx, obj, IntegrityLevel::Frozen,
2200                                         &objIsFrozen));
2201       MOZ_ASSERT(objIsFrozen);
2202     }
2203 #  endif  // DEBUG
2204     args.rval().setBoolean(obj->is<RawJSONObject>());
2205     return true;
2206   }
2207
2208   /* Step 2. */
2209   args.rval().setBoolean(false);
2210   return true;
2211 }
2212
2213 static inline bool IsJSONWhitespace(char16_t ch) {
2214   return ch == '\t' || ch == '\n' || ch == '\r' || ch == ' ';
2215 }
2216
2217 /* https://tc39.es/proposal-json-parse-with-source/#sec-json.rawjson */
2218 static bool json_rawJSON(JSContext* cx, unsigned argc, Value* vp) {
2219   AutoJSMethodProfilerEntry pseudoFrame(cx, "JSON", "rawJSON");
2220   CallArgs args = CallArgsFromVp(argc, vp);
2221
2222   /* Step 1. */
2223   JSString* jsonString = ToString<CanGC>(cx, args.get(0));
2224   if (!jsonString) {
2225     return false;
2226   }
2227
2228   Rooted<JSLinearString*> linear(cx, jsonString->ensureLinear(cx));
2229   if (!linear) {
2230     return false;
2231   }
2232
2233   AutoStableStringChars linearChars(cx);
2234   if (!linearChars.init(cx, linear)) {
2235     return false;
2236   }
2237
2238   /* Step 2. */
2239   if (linear->empty()) {
2240     JS_ReportErrorNumberASCII(cx, js::GetErrorMessage, nullptr,
2241                               JSMSG_JSON_RAW_EMPTY);
2242     return false;
2243   }
2244   if (IsJSONWhitespace(linear->latin1OrTwoByteChar(0)) ||
2245       IsJSONWhitespace(linear->latin1OrTwoByteChar(linear->length() - 1))) {
2246     JS_ReportErrorNumberASCII(cx, js::GetErrorMessage, nullptr,
2247                               JSMSG_JSON_RAW_WHITESPACE);
2248     return false;
2249   }
2250
2251   /* Step 3. */
2252   RootedValue parsedValue(cx);
2253   if (linearChars.isLatin1()) {
2254     if (!ParseJSON(cx, linearChars.latin1Range(), &parsedValue)) {
2255       return false;
2256     }
2257   } else {
2258     if (!ParseJSON(cx, linearChars.twoByteRange(), &parsedValue)) {
2259       return false;
2260     }
2261   }
2262
2263   if (parsedValue.isObject()) {
2264     JS_ReportErrorNumberASCII(cx, js::GetErrorMessage, nullptr,
2265                               JSMSG_JSON_RAW_ARRAY_OR_OBJECT);
2266     return false;
2267   }
2268
2269   /* Steps 4-6. */
2270   Rooted<RawJSONObject*> obj(cx, RawJSONObject::create(cx, linear));
2271   if (!obj) {
2272     return false;
2273   }
2274
2275   /* Step 7. */
2276   if (!js::FreezeObject(cx, obj)) {
2277     return false;
2278   }
2279
2280   args.rval().setObject(*obj);
2281   return true;
2282 }
2283 #endif  // ENABLE_JSON_PARSE_WITH_SOURCE
2284
2285 /* https://262.ecma-international.org/14.0/#sec-json.stringify */
2286 bool json_stringify(JSContext* cx, unsigned argc, Value* vp) {
2287   AutoJSMethodProfilerEntry pseudoFrame(cx, "JSON", "stringify");
2288   CallArgs args = CallArgsFromVp(argc, vp);
2289
2290   RootedObject replacer(cx,
2291                         args.get(1).isObject() ? &args[1].toObject() : nullptr);
2292   RootedValue value(cx, args.get(0));
2293   RootedValue space(cx, args.get(2));
2294
2295 #ifdef DEBUG
2296   StringifyBehavior behavior = StringifyBehavior::Compare;
2297 #else
2298   StringifyBehavior behavior = StringifyBehavior::Normal;
2299 #endif
2300
2301   JSStringBuilder sb(cx);
2302   if (!Stringify(cx, &value, replacer, space, sb, behavior)) {
2303     return false;
2304   }
2305
2306   // XXX This can never happen to nsJSON.cpp, but the JSON object
2307   // needs to support returning undefined. So this is a little awkward
2308   // for the API, because we want to support streaming writers.
2309   if (!sb.empty()) {
2310     JSString* str = sb.finishString();
2311     if (!str) {
2312       return false;
2313     }
2314     args.rval().setString(str);
2315   } else {
2316     args.rval().setUndefined();
2317   }
2318
2319   return true;
2320 }
2321
2322 static const JSFunctionSpec json_static_methods[] = {
2323     JS_FN("toSource", json_toSource, 0, 0),
2324     JS_FN("parse", json_parse, 2, 0),
2325     JS_FN("stringify", json_stringify, 3, 0),
2326 #ifdef ENABLE_RECORD_TUPLE
2327     JS_FN("parseImmutable", json_parseImmutable, 2, 0),
2328 #endif
2329 #ifdef ENABLE_JSON_PARSE_WITH_SOURCE
2330     JS_FN("isRawJSON", json_isRawJSON, 1, 0),
2331     JS_FN("rawJSON", json_rawJSON, 1, 0),
2332 #endif
2333     JS_FS_END};
2334
2335 static const JSPropertySpec json_static_properties[] = {
2336     JS_STRING_SYM_PS(toStringTag, "JSON", JSPROP_READONLY), JS_PS_END};
2337
2338 static JSObject* CreateJSONObject(JSContext* cx, JSProtoKey key) {
2339   RootedObject proto(cx, &cx->global()->getObjectPrototype());
2340   return NewTenuredObjectWithGivenProto(cx, &JSONClass, proto);
2341 }
2342
2343 static const ClassSpec JSONClassSpec = {
2344     CreateJSONObject, nullptr, json_static_methods, json_static_properties};
2345
2346 const JSClass js::JSONClass = {"JSON", JSCLASS_HAS_CACHED_PROTO(JSProto_JSON),
2347                                JS_NULL_CLASS_OPS, &JSONClassSpec};