js/src/builtin/MapObject.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/MapObject.h"
   8
   9 #include "jsapi.h"
  10
  11 #include "ds/OrderedHashTable.h"
  12 #include "gc/GCContext.h"
  13 #include "jit/InlinableNatives.h"
  14 #include "js/MapAndSet.h"
  15 #include "js/PropertyAndElement.h"  // JS_DefineFunctions
  16 #include "js/PropertySpec.h"
  17 #include "js/Utility.h"
  18 #include "vm/BigIntType.h"
  19 #include "vm/EqualityOperations.h"  // js::SameValue
  20 #include "vm/GlobalObject.h"
  21 #include "vm/Interpreter.h"
  22 #include "vm/JSContext.h"
  23 #include "vm/JSObject.h"
  24 #include "vm/SelfHosting.h"
  25 #include "vm/SymbolType.h"
  26
  27 #ifdef ENABLE_RECORD_TUPLE
  28 #  include "vm/RecordType.h"
  29 #  include "vm/TupleType.h"
  30 #endif
  31
  32 #include "gc/GCContext-inl.h"
  33 #include "gc/Marking-inl.h"
  34 #include "vm/GeckoProfiler-inl.h"
  35 #include "vm/NativeObject-inl.h"
  36
  37 using namespace js;
  38
  39 using mozilla::NumberEqualsInt32;
  40
  41 /*** HashableValue **********************************************************/
  42
  43 static PreBarriered<Value> NormalizeDoubleValue(double d) {
  44   int32_t i;
  45   if (NumberEqualsInt32(d, &i)) {
  46     // Normalize int32_t-valued doubles to int32_t for faster hashing and
  47     // testing. Note: we use NumberEqualsInt32 here instead of NumberIsInt32
  48     // because we want -0 and 0 to be normalized to the same thing.
  49     return Int32Value(i);
  50   }
  51
  52   // Normalize the sign bit of a NaN.
  53   return JS::CanonicalizedDoubleValue(d);
  54 }
  55
  56 bool HashableValue::setValue(JSContext* cx, HandleValue v) {
  57   if (v.isString()) {
  58     // Atomize so that hash() and operator==() are fast and infallible.
  59     JSString* str = AtomizeString(cx, v.toString());
  60     if (!str) {
  61       return false;
  62     }
  63     value = StringValue(str);
  64   } else if (v.isDouble()) {
  65     value = NormalizeDoubleValue(v.toDouble());
  66 #ifdef ENABLE_RECORD_TUPLE
  67   } else if (v.isExtendedPrimitive()) {
  68     JSObject& obj = v.toExtendedPrimitive();
  69     if (obj.is<RecordType>()) {
  70       if (!obj.as<RecordType>().ensureAtomized(cx)) {
  71         return false;
  72       }
  73     } else {
  74       MOZ_ASSERT(obj.is<TupleType>());
  75       if (!obj.as<TupleType>().ensureAtomized(cx)) {
  76         return false;
  77       }
  78     }
  79     value = v;
  80 #endif
  81   } else {
  82     value = v;
  83   }
  84
  85   MOZ_ASSERT(value.isUndefined() || value.isNull() || value.isBoolean() ||
  86              value.isNumber() || value.isString() || value.isSymbol() ||
  87              value.isObject() || value.isBigInt() ||
  88              IF_RECORD_TUPLE(value.isExtendedPrimitive(), false));
  89   return true;
  90 }
  91
  92 static HashNumber HashValue(const Value& v,
  93                             const mozilla::HashCodeScrambler& hcs) {
  94   // HashableValue::setValue normalizes values so that the SameValue relation
  95   // on HashableValues is the same as the == relationship on
  96   // value.asRawBits(). So why not just return that? Security.
  97   //
  98   // To avoid revealing GC of atoms, string-based hash codes are computed
  99   // from the string contents rather than any pointer; to avoid revealing
 100   // addresses, pointer-based hash codes are computed using the
 101   // HashCodeScrambler.
 102
 103   if (v.isString()) {
 104     return v.toString()->asAtom().hash();
 105   }
 106   if (v.isSymbol()) {
 107     return v.toSymbol()->hash();
 108   }
 109   if (v.isBigInt()) {
 110     return MaybeForwarded(v.toBigInt())->hash();
 111   }
 112 #ifdef ENABLE_RECORD_TUPLE
 113   if (v.isExtendedPrimitive()) {
 114     JSObject* obj = MaybeForwarded(&v.toExtendedPrimitive());
 115     auto hasher = [&hcs](const Value& v) {
 116       return HashValue(
 117           v.isDouble() ? NormalizeDoubleValue(v.toDouble()).get() : v, hcs);
 118     };
 119
 120     if (obj->is<RecordType>()) {
 121       return obj->as<RecordType>().hash(hasher);
 122     }
 123     MOZ_ASSERT(obj->is<TupleType>());
 124     return obj->as<TupleType>().hash(hasher);
 125   }
 126 #endif
 127   if (v.isObject()) {
 128     return hcs.scramble(v.asRawBits());
 129   }
 130
 131   MOZ_ASSERT(!v.isGCThing(), "do not reveal pointers via hash codes");
 132   return mozilla::HashGeneric(v.asRawBits());
 133 }
 134
 135 HashNumber HashableValue::hash(const mozilla::HashCodeScrambler& hcs) const {
 136   return HashValue(value, hcs);
 137 }
 138
 139 #ifdef ENABLE_RECORD_TUPLE
 140 inline bool SameExtendedPrimitiveType(const PreBarriered<Value>& a,
 141                                       const PreBarriered<Value>& b) {
 142   return a.toExtendedPrimitive().getClass() ==
 143          b.toExtendedPrimitive().getClass();
 144 }
 145 #endif
 146
 147 bool HashableValue::equals(const HashableValue& other) const {
 148   // Two HashableValues are equal if they have equal bits.
 149   bool b = (value.asRawBits() == other.value.asRawBits());
 150
 151   if (!b && (value.type() == other.value.type())) {
 152     if (value.isBigInt()) {
 153       // BigInt values are considered equal if they represent the same
 154       // mathematical value.
 155       b = BigInt::equal(value.toBigInt(), other.value.toBigInt());
 156     }
 157 #ifdef ENABLE_RECORD_TUPLE
 158     else if (value.isExtendedPrimitive() &&
 159              SameExtendedPrimitiveType(value, other.value)) {
 160       b = js::SameValueZeroLinear(value, other.value);
 161     }
 162 #endif
 163   }
 164
 165 #ifdef DEBUG
 166   bool same;
 167   JSContext* cx = TlsContext.get();
 168   RootedValue valueRoot(cx, value);
 169   RootedValue otherRoot(cx, other.value);
 170   MOZ_ASSERT(SameValueZero(cx, valueRoot, otherRoot, &same));
 171   MOZ_ASSERT(same == b);
 172 #endif
 173   return b;
 174 }
 175
 176 /*** MapIterator ************************************************************/
 177
 178 namespace {} /* anonymous namespace */
 179
 180 static const JSClassOps MapIteratorObjectClassOps = {
 181     nullptr,                      // addProperty
 182     nullptr,                      // delProperty
 183     nullptr,                      // enumerate
 184     nullptr,                      // newEnumerate
 185     nullptr,                      // resolve
 186     nullptr,                      // mayResolve
 187     MapIteratorObject::finalize,  // finalize
 188     nullptr,                      // call
 189     nullptr,                      // construct
 190     nullptr,                      // trace
 191 };
 192
 193 static const ClassExtension MapIteratorObjectClassExtension = {
 194     MapIteratorObject::objectMoved,  // objectMovedOp
 195 };
 196
 197 const JSClass MapIteratorObject::class_ = {
 198     "Map Iterator",
 199     JSCLASS_HAS_RESERVED_SLOTS(MapIteratorObject::SlotCount) |
 200         JSCLASS_FOREGROUND_FINALIZE | JSCLASS_SKIP_NURSERY_FINALIZE,
 201     &MapIteratorObjectClassOps, JS_NULL_CLASS_SPEC,
 202     &MapIteratorObjectClassExtension};
 203
 204 const JSFunctionSpec MapIteratorObject::methods[] = {
 205     JS_SELF_HOSTED_FN("next", "MapIteratorNext", 0, 0), JS_FS_END};
 206
 207 static inline ValueMap::Range* MapIteratorObjectRange(NativeObject* obj) {
 208   MOZ_ASSERT(obj->is<MapIteratorObject>());
 209   return obj->maybePtrFromReservedSlot<ValueMap::Range>(
 210       MapIteratorObject::RangeSlot);
 211 }
 212
 213 inline MapObject::IteratorKind MapIteratorObject::kind() const {
 214   int32_t i = getReservedSlot(KindSlot).toInt32();
 215   MOZ_ASSERT(i == MapObject::Keys || i == MapObject::Values ||
 216              i == MapObject::Entries);
 217   return MapObject::IteratorKind(i);
 218 }
 219
 220 /* static */
 221 bool GlobalObject::initMapIteratorProto(JSContext* cx,
 222                                         Handle<GlobalObject*> global) {
 223   Rooted<JSObject*> base(
 224       cx, GlobalObject::getOrCreateIteratorPrototype(cx, global));
 225   if (!base) {
 226     return false;
 227   }
 228   Rooted<PlainObject*> proto(
 229       cx, GlobalObject::createBlankPrototypeInheriting<PlainObject>(cx, base));
 230   if (!proto) {
 231     return false;
 232   }
 233   if (!JS_DefineFunctions(cx, proto, MapIteratorObject::methods) ||
 234       !DefineToStringTag(cx, proto, cx->names().Map_Iterator_)) {
 235     return false;
 236   }
 237   global->initBuiltinProto(ProtoKind::MapIteratorProto, proto);
 238   return true;
 239 }
 240
 241 template <typename TableObject>
 242 static inline bool HasNurseryMemory(TableObject* t) {
 243   return t->getReservedSlot(TableObject::HasNurseryMemorySlot).toBoolean();
 244 }
 245
 246 template <typename TableObject>
 247 static inline void SetHasNurseryMemory(TableObject* t, bool b) {
 248   t->setReservedSlot(TableObject::HasNurseryMemorySlot, JS::BooleanValue(b));
 249 }
 250
 251 MapIteratorObject* MapIteratorObject::create(JSContext* cx, HandleObject obj,
 252                                              const ValueMap* data,
 253                                              MapObject::IteratorKind kind) {
 254   Handle<MapObject*> mapobj(obj.as<MapObject>());
 255   Rooted<GlobalObject*> global(cx, &mapobj->global());
 256   Rooted<JSObject*> proto(
 257       cx, GlobalObject::getOrCreateMapIteratorPrototype(cx, global));
 258   if (!proto) {
 259     return nullptr;
 260   }
 261
 262   MapIteratorObject* iterobj =
 263       NewObjectWithGivenProto<MapIteratorObject>(cx, proto);
 264   if (!iterobj) {
 265     return nullptr;
 266   }
 267
 268   iterobj->init(mapobj, kind);
 269
 270   constexpr size_t BufferSize =
 271       RoundUp(sizeof(ValueMap::Range), gc::CellAlignBytes);
 272
 273   Nursery& nursery = cx->nursery();
 274   void* buffer =
 275       nursery.allocateBufferSameLocation(iterobj, BufferSize, js::MallocArena);
 276   if (!buffer) {
 277     // Retry with |iterobj| and |buffer| forcibly tenured.
 278     iterobj = NewTenuredObjectWithGivenProto<MapIteratorObject>(cx, proto);
 279     if (!iterobj) {
 280       return nullptr;
 281     }
 282
 283     iterobj->init(mapobj, kind);
 284
 285     buffer = nursery.allocateBufferSameLocation(iterobj, BufferSize,
 286                                                 js::MallocArena);
 287     if (!buffer) {
 288       ReportOutOfMemory(cx);
 289       return nullptr;
 290     }
 291   }
 292
 293   bool insideNursery = IsInsideNursery(iterobj);
 294   MOZ_ASSERT(insideNursery == nursery.isInside(buffer));
 295
 296   if (insideNursery && !HasNurseryMemory(mapobj.get())) {
 297     if (!cx->nursery().addMapWithNurseryMemory(mapobj)) {
 298       ReportOutOfMemory(cx);
 299       return nullptr;
 300     }
 301     SetHasNurseryMemory(mapobj.get(), true);
 302   }
 303
 304   auto range = data->createRange(buffer, insideNursery);
 305   iterobj->setReservedSlot(RangeSlot, PrivateValue(range));
 306
 307   return iterobj;
 308 }
 309
 310 void MapIteratorObject::finalize(JS::GCContext* gcx, JSObject* obj) {
 311   MOZ_ASSERT(gcx->onMainThread());
 312   MOZ_ASSERT(!IsInsideNursery(obj));
 313
 314   auto range = MapIteratorObjectRange(&obj->as<NativeObject>());
 315   MOZ_ASSERT(!gcx->runtime()->gc.nursery().isInside(range));
 316
 317   // Bug 1560019: Malloc memory associated with MapIteratorObjects is not
 318   // currently tracked.
 319   gcx->deleteUntracked(range);
 320 }
 321
 322 size_t MapIteratorObject::objectMoved(JSObject* obj, JSObject* old) {
 323   if (!IsInsideNursery(old)) {
 324     return 0;
 325   }
 326
 327   MapIteratorObject* iter = &obj->as<MapIteratorObject>();
 328   ValueMap::Range* range = MapIteratorObjectRange(iter);
 329   if (!range) {
 330     return 0;
 331   }
 332
 333   Nursery& nursery = iter->runtimeFromMainThread()->gc.nursery();
 334   if (!nursery.isInside(range)) {
 335     nursery.removeMallocedBufferDuringMinorGC(range);
 336   }
 337
 338   size_t size = RoundUp(sizeof(ValueMap::Range), gc::CellAlignBytes);
 339   AutoEnterOOMUnsafeRegion oomUnsafe;
 340   void* buffer = nursery.allocateBufferSameLocation(obj, size, js::MallocArena);
 341   if (!buffer) {
 342     oomUnsafe.crash("MapIteratorObject::objectMoved");
 343   }
 344
 345   bool iteratorIsInNursery = IsInsideNursery(obj);
 346   MOZ_ASSERT(iteratorIsInNursery == nursery.isInside(buffer));
 347   auto* newRange = new (buffer) ValueMap::Range(*range, iteratorIsInNursery);
 348   range->~Range();
 349   iter->setReservedSlot(MapIteratorObject::RangeSlot, PrivateValue(newRange));
 350
 351   if (iteratorIsInNursery && iter->target()) {
 352     SetHasNurseryMemory(iter->target(), true);
 353   }
 354
 355   return size;
 356 }
 357
 358 MapObject* MapIteratorObject::target() const {
 359   Value value = getFixedSlot(TargetSlot);
 360   if (value.isUndefined()) {
 361     return nullptr;
 362   }
 363
 364   return &MaybeForwarded(&value.toObject())->as<MapObject>();
 365 }
 366
 367 template <typename Range>
 368 static void DestroyRange(JSObject* iterator, Range* range) {
 369   MOZ_ASSERT(IsInsideNursery(iterator) ==
 370              iterator->runtimeFromMainThread()->gc.nursery().isInside(range));
 371
 372   range->~Range();
 373   if (!IsInsideNursery(iterator)) {
 374     js_free(range);
 375   }
 376 }
 377
 378 bool MapIteratorObject::next(MapIteratorObject* mapIterator,
 379                              ArrayObject* resultPairObj) {
 380   // IC code calls this directly.
 381   AutoUnsafeCallWithABI unsafe;
 382
 383   // Check invariants for inlined GetNextMapEntryForIterator.
 384
 385   // The array should be tenured, so that post-barrier can be done simply.
 386   MOZ_ASSERT(resultPairObj->isTenured());
 387
 388   // The array elements should be fixed.
 389   MOZ_ASSERT(resultPairObj->hasFixedElements());
 390   MOZ_ASSERT(resultPairObj->getDenseInitializedLength() == 2);
 391   MOZ_ASSERT(resultPairObj->getDenseCapacity() >= 2);
 392
 393   ValueMap::Range* range = MapIteratorObjectRange(mapIterator);
 394   if (!range) {
 395     return true;
 396   }
 397
 398   if (range->empty()) {
 399     DestroyRange<ValueMap::Range>(mapIterator, range);
 400     mapIterator->setReservedSlot(RangeSlot, PrivateValue(nullptr));
 401     return true;
 402   }
 403
 404   switch (mapIterator->kind()) {
 405     case MapObject::Keys:
 406       resultPairObj->setDenseElement(0, range->front().key.get());
 407       break;
 408
 409     case MapObject::Values:
 410       resultPairObj->setDenseElement(1, range->front().value);
 411       break;
 412
 413     case MapObject::Entries: {
 414       resultPairObj->setDenseElement(0, range->front().key.get());
 415       resultPairObj->setDenseElement(1, range->front().value);
 416       break;
 417     }
 418   }
 419   range->popFront();
 420   return false;
 421 }
 422
 423 /* static */
 424 JSObject* MapIteratorObject::createResultPair(JSContext* cx) {
 425   Rooted<ArrayObject*> resultPairObj(
 426       cx, NewDenseFullyAllocatedArray(cx, 2, TenuredObject));
 427   if (!resultPairObj) {
 428     return nullptr;
 429   }
 430
 431   resultPairObj->setDenseInitializedLength(2);
 432   resultPairObj->initDenseElement(0, NullValue());
 433   resultPairObj->initDenseElement(1, NullValue());
 434
 435   return resultPairObj;
 436 }
 437
 438 /*** Map ********************************************************************/
 439
 440 struct js::UnbarrieredHashPolicy {
 441   using Lookup = Value;
 442   static HashNumber hash(const Lookup& v,
 443                          const mozilla::HashCodeScrambler& hcs) {
 444     return HashValue(v, hcs);
 445   }
 446   static bool match(const Value& k, const Lookup& l) { return k == l; }
 447   static bool isEmpty(const Value& v) { return v.isMagic(JS_HASH_KEY_EMPTY); }
 448   static void makeEmpty(Value* vp) { vp->setMagic(JS_HASH_KEY_EMPTY); }
 449 };
 450
 451 // ValueMap, MapObject::UnbarrieredTable and MapObject::PreBarrieredTable must
 452 // all have the same memory layout.
 453 static_assert(sizeof(ValueMap) == sizeof(MapObject::UnbarrieredTable));
 454 static_assert(sizeof(ValueMap::Entry) ==
 455               sizeof(MapObject::UnbarrieredTable::Entry));
 456 static_assert(sizeof(ValueMap) == sizeof(MapObject::PreBarrieredTable));
 457 static_assert(sizeof(ValueMap::Entry) ==
 458               sizeof(MapObject::PreBarrieredTable::Entry));
 459
 460 const JSClassOps MapObject::classOps_ = {
 461     nullptr,   // addProperty
 462     nullptr,   // delProperty
 463     nullptr,   // enumerate
 464     nullptr,   // newEnumerate
 465     nullptr,   // resolve
 466     nullptr,   // mayResolve
 467     finalize,  // finalize
 468     nullptr,   // call
 469     nullptr,   // construct
 470     trace,     // trace
 471 };
 472
 473 const ClassSpec MapObject::classSpec_ = {
 474     GenericCreateConstructor<MapObject::construct, 0, gc::AllocKind::FUNCTION>,
 475     GenericCreatePrototype<MapObject>,
 476     MapObject::staticMethods,
 477     MapObject::staticProperties,
 478     MapObject::methods,
 479     MapObject::properties,
 480     MapObject::finishInit,
 481 };
 482
 483 const JSClass MapObject::class_ = {
 484     "Map",
 485     JSCLASS_DELAY_METADATA_BUILDER |
 486         JSCLASS_HAS_RESERVED_SLOTS(MapObject::SlotCount) |
 487         JSCLASS_HAS_CACHED_PROTO(JSProto_Map) | JSCLASS_FOREGROUND_FINALIZE |
 488         JSCLASS_SKIP_NURSERY_FINALIZE,
 489     &MapObject::classOps_,
 490     &MapObject::classSpec_,
 491 };
 492
 493 const JSClass MapObject::protoClass_ = {
 494     "Map.prototype",
 495     JSCLASS_HAS_CACHED_PROTO(JSProto_Map),
 496     JS_NULL_CLASS_OPS,
 497     &MapObject::classSpec_,
 498 };
 499
 500 const JSPropertySpec MapObject::properties[] = {
 501     JS_PSG("size", size, 0),
 502     JS_STRING_SYM_PS(toStringTag, "Map", JSPROP_READONLY),
 503     JS_PS_END,
 504 };
 505
 506 const JSFunctionSpec MapObject::methods[] = {
 507     JS_INLINABLE_FN("get", get, 1, 0, MapGet),
 508     JS_INLINABLE_FN("has", has, 1, 0, MapHas),
 509     JS_FN("set", set, 2, 0),
 510     JS_FN("delete", delete_, 1, 0),
 511     JS_FN("keys", keys, 0, 0),
 512     JS_FN("values", values, 0, 0),
 513     JS_FN("clear", clear, 0, 0),
 514     JS_SELF_HOSTED_FN("forEach", "MapForEach", 2, 0),
 515     JS_FN("entries", entries, 0, 0),
 516     // @@iterator is re-defined in finishInit so that it has the
 517     // same identity as |entries|.
 518     JS_SYM_FN(iterator, entries, 0, 0),
 519     JS_FS_END,
 520 };
 521
 522 const JSPropertySpec MapObject::staticProperties[] = {
 523     JS_SELF_HOSTED_SYM_GET(species, "$MapSpecies", 0),
 524     JS_PS_END,
 525 };
 526
 527 const JSFunctionSpec MapObject::staticMethods[] = {
 528     JS_SELF_HOSTED_FN("groupBy", "MapGroupBy", 2, 0),
 529     JS_FS_END,
 530 };
 531
 532 /* static */ bool MapObject::finishInit(JSContext* cx, HandleObject ctor,
 533                                         HandleObject proto) {
 534   Handle<NativeObject*> nativeProto = proto.as<NativeObject>();
 535
 536   RootedValue entriesFn(cx);
 537   RootedId entriesId(cx, NameToId(cx->names().entries));
 538   if (!NativeGetProperty(cx, nativeProto, entriesId, &entriesFn)) {
 539     return false;
 540   }
 541
 542   // 23.1.3.12 Map.prototype[@@iterator]()
 543   // The initial value of the @@iterator property is the same function object
 544   // as the initial value of the "entries" property.
 545   RootedId iteratorId(cx, PropertyKey::Symbol(cx->wellKnownSymbols().iterator));
 546   return NativeDefineDataProperty(cx, nativeProto, iteratorId, entriesFn, 0);
 547 }
 548
 549 void MapObject::trace(JSTracer* trc, JSObject* obj) {
 550   if (ValueMap* map = obj->as<MapObject>().getTableUnchecked()) {
 551     map->trace(trc);
 552   }
 553 }
 554
 555 using NurseryKeysVector = GCVector<Value, 0, SystemAllocPolicy>;
 556
 557 template <typename TableObject>
 558 static NurseryKeysVector* GetNurseryKeys(TableObject* t) {
 559   Value value = t->getReservedSlot(TableObject::NurseryKeysSlot);
 560   return reinterpret_cast<NurseryKeysVector*>(value.toPrivate());
 561 }
 562
 563 template <typename TableObject>
 564 static NurseryKeysVector* AllocNurseryKeys(TableObject* t) {
 565   MOZ_ASSERT(!GetNurseryKeys(t));
 566   auto keys = js_new<NurseryKeysVector>();
 567   if (!keys) {
 568     return nullptr;
 569   }
 570
 571   t->setReservedSlot(TableObject::NurseryKeysSlot, PrivateValue(keys));
 572   return keys;
 573 }
 574
 575 template <typename TableObject>
 576 static void DeleteNurseryKeys(TableObject* t) {
 577   auto keys = GetNurseryKeys(t);
 578   MOZ_ASSERT(keys);
 579   js_delete(keys);
 580   t->setReservedSlot(TableObject::NurseryKeysSlot, PrivateValue(nullptr));
 581 }
 582
 583 // A generic store buffer entry that traces all nursery keys for an ordered hash
 584 // map or set.
 585 template <typename ObjectT>
 586 class js::OrderedHashTableRef : public gc::BufferableRef {
 587   ObjectT* object;
 588
 589  public:
 590   explicit OrderedHashTableRef(ObjectT* obj) : object(obj) {}
 591
 592   void trace(JSTracer* trc) override {
 593     MOZ_ASSERT(!IsInsideNursery(object));
 594     auto realTable = object->getTableUnchecked();
 595     auto unbarrieredTable =
 596         reinterpret_cast<typename ObjectT::UnbarrieredTable*>(realTable);
 597     NurseryKeysVector* keys = GetNurseryKeys(object);
 598     MOZ_ASSERT(keys);
 599
 600     keys->mutableEraseIf([&](Value& key) {
 601       MOZ_ASSERT(
 602           unbarrieredTable->hash(key) ==
 603           realTable->hash(*reinterpret_cast<const HashableValue*>(&key)));
 604       MOZ_ASSERT(IsInsideNursery(key.toGCThing()));
 605
 606       auto result =
 607           unbarrieredTable->rekeyOneEntry(key, [trc](const Value& prior) {
 608             Value key = prior;
 609             TraceManuallyBarrieredEdge(trc, &key, "ordered hash table key");
 610             return key;
 611           });
 612
 613       if (result.isNothing()) {
 614         return true;  // Key removed.
 615       }
 616
 617       key = result.value();
 618       return !IsInsideNursery(key.toGCThing());
 619     });
 620
 621     if (!keys->empty()) {
 622       trc->runtime()->gc.storeBuffer().putGeneric(
 623           OrderedHashTableRef<ObjectT>(object));
 624       return;
 625     }
 626
 627     DeleteNurseryKeys(object);
 628   }
 629 };
 630
 631 template <typename ObjectT>
 632 [[nodiscard]] inline static bool PostWriteBarrierImpl(ObjectT* obj,
 633                                                       const Value& keyValue) {
 634   if (MOZ_LIKELY(!keyValue.hasObjectPayload() && !keyValue.isBigInt())) {
 635     MOZ_ASSERT_IF(keyValue.isGCThing(), !IsInsideNursery(keyValue.toGCThing()));
 636     return true;
 637   }
 638
 639   if (!IsInsideNursery(keyValue.toGCThing())) {
 640     return true;
 641   }
 642
 643   NurseryKeysVector* keys = GetNurseryKeys(obj);
 644   if (!keys) {
 645     keys = AllocNurseryKeys(obj);
 646     if (!keys) {
 647       return false;
 648     }
 649
 650     keyValue.toGCThing()->storeBuffer()->putGeneric(
 651         OrderedHashTableRef<ObjectT>(obj));
 652   }
 653
 654   return keys->append(keyValue);
 655 }
 656
 657 [[nodiscard]] inline static bool PostWriteBarrier(MapObject* map,
 658                                                   const Value& key) {
 659   MOZ_ASSERT(!IsInsideNursery(map));
 660   return PostWriteBarrierImpl(map, key);
 661 }
 662
 663 [[nodiscard]] inline static bool PostWriteBarrier(SetObject* set,
 664                                                   const Value& key) {
 665   if (IsInsideNursery(set)) {
 666     return true;
 667   }
 668
 669   return PostWriteBarrierImpl(set, key);
 670 }
 671
 672 bool MapObject::getKeysAndValuesInterleaved(
 673     HandleObject obj, JS::MutableHandle<GCVector<JS::Value>> entries) {
 674   const ValueMap* map = obj->as<MapObject>().getData();
 675   if (!map) {
 676     return false;
 677   }
 678
 679   for (ValueMap::Range r = map->all(); !r.empty(); r.popFront()) {
 680     if (!entries.append(r.front().key.get()) ||
 681         !entries.append(r.front().value)) {
 682       return false;
 683     }
 684   }
 685
 686   return true;
 687 }
 688
 689 bool MapObject::set(JSContext* cx, HandleObject obj, HandleValue k,
 690                     HandleValue v) {
 691   MapObject* mapObject = &obj->as<MapObject>();
 692   Rooted<HashableValue> key(cx);
 693   if (!key.setValue(cx, k)) {
 694     return false;
 695   }
 696
 697   return setWithHashableKey(cx, mapObject, key, v);
 698 }
 699
 700 /* static */
 701 inline bool MapObject::setWithHashableKey(JSContext* cx, MapObject* obj,
 702                                           Handle<HashableValue> key,
 703                                           Handle<Value> value) {
 704   ValueMap* table = obj->getTableUnchecked();
 705   if (!table) {
 706     return false;
 707   }
 708
 709   bool needsPostBarriers = obj->isTenured();
 710   if (needsPostBarriers) {
 711     // Use the ValueMap representation which has post barriers.
 712     if (!PostWriteBarrier(obj, key.get()) || !table->put(key.get(), value)) {
 713       ReportOutOfMemory(cx);
 714       return false;
 715     }
 716   } else {
 717     // Use the PreBarrieredTable representation which does not.
 718     auto* preBarriedTable = reinterpret_cast<PreBarrieredTable*>(table);
 719     if (!preBarriedTable->put(key.get(), value.get())) {
 720       ReportOutOfMemory(cx);
 721       return false;
 722     }
 723   }
 724
 725   return true;
 726 }
 727
 728 MapObject* MapObject::create(JSContext* cx,
 729                              HandleObject proto /* = nullptr */) {
 730   auto map = cx->make_unique<ValueMap>(cx->zone(),
 731                                        cx->realm()->randomHashCodeScrambler());
 732   if (!map) {
 733     return nullptr;
 734   }
 735
 736   if (!map->init()) {
 737     ReportOutOfMemory(cx);
 738     return nullptr;
 739   }
 740
 741   AutoSetNewObjectMetadata metadata(cx);
 742   MapObject* mapObj = NewObjectWithClassProto<MapObject>(cx, proto);
 743   if (!mapObj) {
 744     return nullptr;
 745   }
 746
 747   bool insideNursery = IsInsideNursery(mapObj);
 748   if (insideNursery && !cx->nursery().addMapWithNurseryMemory(mapObj)) {
 749     ReportOutOfMemory(cx);
 750     return nullptr;
 751   }
 752
 753   InitReservedSlot(mapObj, DataSlot, map.release(), MemoryUse::MapObjectTable);
 754   mapObj->initReservedSlot(NurseryKeysSlot, PrivateValue(nullptr));
 755   mapObj->initReservedSlot(HasNurseryMemorySlot,
 756                            JS::BooleanValue(insideNursery));
 757   return mapObj;
 758 }
 759
 760 size_t MapObject::sizeOfData(mozilla::MallocSizeOf mallocSizeOf) {
 761   size_t size = 0;
 762   if (const ValueMap* map = getData()) {
 763     size += map->sizeOfIncludingThis(mallocSizeOf);
 764   }
 765   if (NurseryKeysVector* nurseryKeys = GetNurseryKeys(this)) {
 766     size += nurseryKeys->sizeOfIncludingThis(mallocSizeOf);
 767   }
 768   return size;
 769 }
 770
 771 void MapObject::finalize(JS::GCContext* gcx, JSObject* obj) {
 772   MOZ_ASSERT(gcx->onMainThread());
 773   ValueMap* table = obj->as<MapObject>().getTableUnchecked();
 774   if (!table) {
 775     return;
 776   }
 777
 778   MOZ_ASSERT_IF(obj->isTenured(), !table->hasNurseryRanges());
 779
 780   bool needsPostBarriers = obj->isTenured();
 781   if (needsPostBarriers) {
 782     // Use the ValueMap representation which has post barriers.
 783     gcx->delete_(obj, table, MemoryUse::MapObjectTable);
 784   } else {
 785     // Use the PreBarrieredTable representation which does not.
 786     auto* preBarriedTable = reinterpret_cast<PreBarrieredTable*>(table);
 787     gcx->delete_(obj, preBarriedTable, MemoryUse::MapObjectTable);
 788   }
 789 }
 790
 791 void MapObject::clearNurseryRangesBeforeMinorGC() {
 792   getTableUnchecked()->destroyNurseryRanges();
 793   SetHasNurseryMemory(this, false);
 794 }
 795
 796 /* static */
 797 MapObject* MapObject::sweepAfterMinorGC(JS::GCContext* gcx, MapObject* mapobj) {
 798   Nursery& nursery = gcx->runtime()->gc.nursery();
 799   bool wasInCollectedRegion = nursery.inCollectedRegion(mapobj);
 800   if (wasInCollectedRegion && !IsForwarded(mapobj)) {
 801     finalize(gcx, mapobj);
 802     return nullptr;
 803   }
 804
 805   mapobj = MaybeForwarded(mapobj);
 806
 807   bool insideNursery = IsInsideNursery(mapobj);
 808   if (insideNursery) {
 809     SetHasNurseryMemory(mapobj, true);
 810   }
 811
 812   if (wasInCollectedRegion && mapobj->isTenured()) {
 813     AddCellMemory(mapobj, sizeof(ValueMap), MemoryUse::MapObjectTable);
 814   }
 815
 816   if (!HasNurseryMemory(mapobj)) {
 817     return nullptr;
 818   }
 819
 820   return mapobj;
 821 }
 822
 823 bool MapObject::construct(JSContext* cx, unsigned argc, Value* vp) {
 824   AutoJSConstructorProfilerEntry pseudoFrame(cx, "Map");
 825   CallArgs args = CallArgsFromVp(argc, vp);
 826
 827   if (!ThrowIfNotConstructing(cx, args, "Map")) {
 828     return false;
 829   }
 830
 831   RootedObject proto(cx);
 832   if (!GetPrototypeFromBuiltinConstructor(cx, args, JSProto_Map, &proto)) {
 833     return false;
 834   }
 835
 836   Rooted<MapObject*> obj(cx, MapObject::create(cx, proto));
 837   if (!obj) {
 838     return false;
 839   }
 840
 841   if (!args.get(0).isNullOrUndefined()) {
 842     FixedInvokeArgs<1> args2(cx);
 843     args2[0].set(args[0]);
 844
 845     RootedValue thisv(cx, ObjectValue(*obj));
 846     if (!CallSelfHostedFunction(cx, cx->names().MapConstructorInit, thisv,
 847                                 args2, args2.rval())) {
 848       return false;
 849     }
 850   }
 851
 852   args.rval().setObject(*obj);
 853   return true;
 854 }
 855
 856 bool MapObject::is(HandleValue v) {
 857   return v.isObject() && v.toObject().hasClass(&class_) &&
 858          !v.toObject().as<MapObject>().getReservedSlot(DataSlot).isUndefined();
 859 }
 860
 861 bool MapObject::is(HandleObject o) {
 862   return o->hasClass(&class_) &&
 863          !o->as<MapObject>().getReservedSlot(DataSlot).isUndefined();
 864 }
 865
 866 #define ARG0_KEY(cx, args, key)  \
 867   Rooted<HashableValue> key(cx); \
 868   if (args.length() > 0 && !key.setValue(cx, args[0])) return false
 869
 870 const ValueMap& MapObject::extract(HandleObject o) {
 871   MOZ_ASSERT(o->hasClass(&MapObject::class_));
 872   return *o->as<MapObject>().getData();
 873 }
 874
 875 const ValueMap& MapObject::extract(const CallArgs& args) {
 876   MOZ_ASSERT(args.thisv().isObject());
 877   MOZ_ASSERT(args.thisv().toObject().hasClass(&MapObject::class_));
 878   return *args.thisv().toObject().as<MapObject>().getData();
 879 }
 880
 881 uint32_t MapObject::size(JSContext* cx, HandleObject obj) {
 882   const ValueMap& map = extract(obj);
 883   static_assert(sizeof(map.count()) <= sizeof(uint32_t),
 884                 "map count must be precisely representable as a JS number");
 885   return map.count();
 886 }
 887
 888 bool MapObject::size_impl(JSContext* cx, const CallArgs& args) {
 889   RootedObject obj(cx, &args.thisv().toObject());
 890   args.rval().setNumber(size(cx, obj));
 891   return true;
 892 }
 893
 894 bool MapObject::size(JSContext* cx, unsigned argc, Value* vp) {
 895   AutoJSMethodProfilerEntry pseudoFrame(cx, "Map.prototype", "size");
 896   CallArgs args = CallArgsFromVp(argc, vp);
 897   return CallNonGenericMethod<MapObject::is, MapObject::size_impl>(cx, args);
 898 }
 899
 900 bool MapObject::get(JSContext* cx, HandleObject obj, HandleValue key,
 901                     MutableHandleValue rval) {
 902   const ValueMap& map = extract(obj);
 903   Rooted<HashableValue> k(cx);
 904
 905   if (!k.setValue(cx, key)) {
 906     return false;
 907   }
 908
 909   if (const ValueMap::Entry* p = map.get(k)) {
 910     rval.set(p->value);
 911   } else {
 912     rval.setUndefined();
 913   }
 914
 915   return true;
 916 }
 917
 918 bool MapObject::get_impl(JSContext* cx, const CallArgs& args) {
 919   RootedObject obj(cx, &args.thisv().toObject());
 920   return get(cx, obj, args.get(0), args.rval());
 921 }
 922
 923 bool MapObject::get(JSContext* cx, unsigned argc, Value* vp) {
 924   AutoJSMethodProfilerEntry pseudoFrame(cx, "Map.prototype", "get");
 925   CallArgs args = CallArgsFromVp(argc, vp);
 926   return CallNonGenericMethod<MapObject::is, MapObject::get_impl>(cx, args);
 927 }
 928
 929 bool MapObject::has(JSContext* cx, HandleObject obj, HandleValue key,
 930                     bool* rval) {
 931   const ValueMap& map = extract(obj);
 932   Rooted<HashableValue> k(cx);
 933
 934   if (!k.setValue(cx, key)) {
 935     return false;
 936   }
 937
 938   *rval = map.has(k);
 939   return true;
 940 }
 941
 942 bool MapObject::has_impl(JSContext* cx, const CallArgs& args) {
 943   bool found;
 944   RootedObject obj(cx, &args.thisv().toObject());
 945   if (has(cx, obj, args.get(0), &found)) {
 946     args.rval().setBoolean(found);
 947     return true;
 948   }
 949   return false;
 950 }
 951
 952 bool MapObject::has(JSContext* cx, unsigned argc, Value* vp) {
 953   AutoJSMethodProfilerEntry pseudoFrame(cx, "Map.prototype", "has");
 954   CallArgs args = CallArgsFromVp(argc, vp);
 955   return CallNonGenericMethod<MapObject::is, MapObject::has_impl>(cx, args);
 956 }
 957
 958 bool MapObject::set_impl(JSContext* cx, const CallArgs& args) {
 959   MOZ_ASSERT(MapObject::is(args.thisv()));
 960
 961   MapObject* obj = &args.thisv().toObject().as<MapObject>();
 962   ARG0_KEY(cx, args, key);
 963   if (!setWithHashableKey(cx, obj, key, args.get(1))) {
 964     return false;
 965   }
 966
 967   args.rval().set(args.thisv());
 968   return true;
 969 }
 970
 971 bool MapObject::set(JSContext* cx, unsigned argc, Value* vp) {
 972   AutoJSMethodProfilerEntry pseudoFrame(cx, "Map.prototype", "set");
 973   CallArgs args = CallArgsFromVp(argc, vp);
 974   return CallNonGenericMethod<MapObject::is, MapObject::set_impl>(cx, args);
 975 }
 976
 977 bool MapObject::delete_(JSContext* cx, HandleObject obj, HandleValue key,
 978                         bool* rval) {
 979   MapObject* mapObject = &obj->as<MapObject>();
 980   Rooted<HashableValue> k(cx);
 981
 982   if (!k.setValue(cx, key)) {
 983     return false;
 984   }
 985
 986   bool ok;
 987   if (mapObject->isTenured()) {
 988     ok = mapObject->tenuredTable()->remove(k, rval);
 989   } else {
 990     ok = mapObject->nurseryTable()->remove(k, rval);
 991   }
 992
 993   if (!ok) {
 994     ReportOutOfMemory(cx);
 995     return false;
 996   }
 997
 998   return true;
 999 }
1000
1001 bool MapObject::delete_impl(JSContext* cx, const CallArgs& args) {
1002   // MapObject::trace does not trace deleted entries. Incremental GC therefore
1003   // requires that no HeapPtr<Value> objects pointing to heap values be left
1004   // alive in the ValueMap.
1005   //
1006   // OrderedHashMap::remove() doesn't destroy the removed entry. It merely
1007   // calls OrderedHashMap::MapOps::makeEmpty. But that is sufficient, because
1008   // makeEmpty clears the value by doing e->value = Value(), and in the case
1009   // of a ValueMap, Value() means HeapPtr<Value>(), which is the same as
1010   // HeapPtr<Value>(UndefinedValue()).
1011   MOZ_ASSERT(MapObject::is(args.thisv()));
1012   RootedObject obj(cx, &args.thisv().toObject());
1013
1014   bool found;
1015   if (!delete_(cx, obj, args.get(0), &found)) {
1016     return false;
1017   }
1018
1019   args.rval().setBoolean(found);
1020   return true;
1021 }
1022
1023 bool MapObject::delete_(JSContext* cx, unsigned argc, Value* vp) {
1024   AutoJSMethodProfilerEntry pseudoFrame(cx, "Map.prototype", "delete");
1025   CallArgs args = CallArgsFromVp(argc, vp);
1026   return CallNonGenericMethod<MapObject::is, MapObject::delete_impl>(cx, args);
1027 }
1028
1029 bool MapObject::iterator(JSContext* cx, IteratorKind kind, HandleObject obj,
1030                          MutableHandleValue iter) {
1031   const ValueMap& map = extract(obj);
1032   Rooted<JSObject*> iterobj(cx, MapIteratorObject::create(cx, obj, &map, kind));
1033   if (!iterobj) {
1034     return false;
1035   }
1036   iter.setObject(*iterobj);
1037   return true;
1038 }
1039
1040 bool MapObject::iterator_impl(JSContext* cx, const CallArgs& args,
1041                               IteratorKind kind) {
1042   RootedObject obj(cx, &args.thisv().toObject());
1043   return iterator(cx, kind, obj, args.rval());
1044 }
1045
1046 bool MapObject::keys_impl(JSContext* cx, const CallArgs& args) {
1047   return iterator_impl(cx, args, Keys);
1048 }
1049
1050 bool MapObject::keys(JSContext* cx, unsigned argc, Value* vp) {
1051   AutoJSMethodProfilerEntry pseudoFrame(cx, "Map.prototype", "keys");
1052   CallArgs args = CallArgsFromVp(argc, vp);
1053   return CallNonGenericMethod(cx, is, keys_impl, args);
1054 }
1055
1056 bool MapObject::values_impl(JSContext* cx, const CallArgs& args) {
1057   return iterator_impl(cx, args, Values);
1058 }
1059
1060 bool MapObject::values(JSContext* cx, unsigned argc, Value* vp) {
1061   AutoJSMethodProfilerEntry pseudoFrame(cx, "Map.prototype", "values");
1062   CallArgs args = CallArgsFromVp(argc, vp);
1063   return CallNonGenericMethod(cx, is, values_impl, args);
1064 }
1065
1066 bool MapObject::entries_impl(JSContext* cx, const CallArgs& args) {
1067   return iterator_impl(cx, args, Entries);
1068 }
1069
1070 bool MapObject::entries(JSContext* cx, unsigned argc, Value* vp) {
1071   AutoJSMethodProfilerEntry pseudoFrame(cx, "Map.prototype", "entries");
1072   CallArgs args = CallArgsFromVp(argc, vp);
1073   return CallNonGenericMethod(cx, is, entries_impl, args);
1074 }
1075
1076 bool MapObject::clear_impl(JSContext* cx, const CallArgs& args) {
1077   RootedObject obj(cx, &args.thisv().toObject());
1078   args.rval().setUndefined();
1079   return clear(cx, obj);
1080 }
1081
1082 bool MapObject::clear(JSContext* cx, unsigned argc, Value* vp) {
1083   AutoJSMethodProfilerEntry pseudoFrame(cx, "Map.prototype", "clear");
1084   CallArgs args = CallArgsFromVp(argc, vp);
1085   return CallNonGenericMethod(cx, is, clear_impl, args);
1086 }
1087
1088 bool MapObject::clear(JSContext* cx, HandleObject obj) {
1089   MapObject* mapObject = &obj->as<MapObject>();
1090
1091   bool ok;
1092   if (mapObject->isTenured()) {
1093     ok = mapObject->tenuredTable()->clear();
1094   } else {
1095     ok = mapObject->nurseryTable()->clear();
1096   }
1097
1098   if (!ok) {
1099     ReportOutOfMemory(cx);
1100     return false;
1101   }
1102
1103   return true;
1104 }
1105
1106 /*** SetIterator ************************************************************/
1107
1108 static const JSClassOps SetIteratorObjectClassOps = {
1109     nullptr,                      // addProperty
1110     nullptr,                      // delProperty
1111     nullptr,                      // enumerate
1112     nullptr,                      // newEnumerate
1113     nullptr,                      // resolve
1114     nullptr,                      // mayResolve
1115     SetIteratorObject::finalize,  // finalize
1116     nullptr,                      // call
1117     nullptr,                      // construct
1118     nullptr,                      // trace
1119 };
1120
1121 static const ClassExtension SetIteratorObjectClassExtension = {
1122     SetIteratorObject::objectMoved,  // objectMovedOp
1123 };
1124
1125 const JSClass SetIteratorObject::class_ = {
1126     "Set Iterator",
1127     JSCLASS_HAS_RESERVED_SLOTS(SetIteratorObject::SlotCount) |
1128         JSCLASS_FOREGROUND_FINALIZE | JSCLASS_SKIP_NURSERY_FINALIZE,
1129     &SetIteratorObjectClassOps, JS_NULL_CLASS_SPEC,
1130     &SetIteratorObjectClassExtension};
1131
1132 const JSFunctionSpec SetIteratorObject::methods[] = {
1133     JS_SELF_HOSTED_FN("next", "SetIteratorNext", 0, 0), JS_FS_END};
1134
1135 static inline ValueSet::Range* SetIteratorObjectRange(NativeObject* obj) {
1136   MOZ_ASSERT(obj->is<SetIteratorObject>());
1137   return obj->maybePtrFromReservedSlot<ValueSet::Range>(
1138       SetIteratorObject::RangeSlot);
1139 }
1140
1141 inline SetObject::IteratorKind SetIteratorObject::kind() const {
1142   int32_t i = getReservedSlot(KindSlot).toInt32();
1143   MOZ_ASSERT(i == SetObject::Values || i == SetObject::Entries);
1144   return SetObject::IteratorKind(i);
1145 }
1146
1147 /* static */
1148 bool GlobalObject::initSetIteratorProto(JSContext* cx,
1149                                         Handle<GlobalObject*> global) {
1150   Rooted<JSObject*> base(
1151       cx, GlobalObject::getOrCreateIteratorPrototype(cx, global));
1152   if (!base) {
1153     return false;
1154   }
1155   Rooted<PlainObject*> proto(
1156       cx, GlobalObject::createBlankPrototypeInheriting<PlainObject>(cx, base));
1157   if (!proto) {
1158     return false;
1159   }
1160   if (!JS_DefineFunctions(cx, proto, SetIteratorObject::methods) ||
1161       !DefineToStringTag(cx, proto, cx->names().Set_Iterator_)) {
1162     return false;
1163   }
1164   global->initBuiltinProto(ProtoKind::SetIteratorProto, proto);
1165   return true;
1166 }
1167
1168 SetIteratorObject* SetIteratorObject::create(JSContext* cx, HandleObject obj,
1169                                              ValueSet* data,
1170                                              SetObject::IteratorKind kind) {
1171   MOZ_ASSERT(kind != SetObject::Keys);
1172
1173   Handle<SetObject*> setobj(obj.as<SetObject>());
1174   Rooted<GlobalObject*> global(cx, &setobj->global());
1175   Rooted<JSObject*> proto(
1176       cx, GlobalObject::getOrCreateSetIteratorPrototype(cx, global));
1177   if (!proto) {
1178     return nullptr;
1179   }
1180
1181   SetIteratorObject* iterobj =
1182       NewObjectWithGivenProto<SetIteratorObject>(cx, proto);
1183   if (!iterobj) {
1184     return nullptr;
1185   }
1186
1187   iterobj->init(setobj, kind);
1188
1189   constexpr size_t BufferSize =
1190       RoundUp(sizeof(ValueSet::Range), gc::CellAlignBytes);
1191
1192   Nursery& nursery = cx->nursery();
1193   void* buffer =
1194       nursery.allocateBufferSameLocation(iterobj, BufferSize, js::MallocArena);
1195   if (!buffer) {
1196     // Retry with |iterobj| and |buffer| forcibly tenured.
1197     iterobj = NewTenuredObjectWithGivenProto<SetIteratorObject>(cx, proto);
1198     if (!iterobj) {
1199       return nullptr;
1200     }
1201
1202     iterobj->init(setobj, kind);
1203
1204     buffer = nursery.allocateBufferSameLocation(iterobj, BufferSize,
1205                                                 js::MallocArena);
1206     if (!buffer) {
1207       ReportOutOfMemory(cx);
1208       return nullptr;
1209     }
1210   }
1211
1212   bool insideNursery = IsInsideNursery(iterobj);
1213   MOZ_ASSERT(insideNursery == nursery.isInside(buffer));
1214
1215   if (insideNursery && !HasNurseryMemory(setobj.get())) {
1216     if (!cx->nursery().addSetWithNurseryMemory(setobj)) {
1217       ReportOutOfMemory(cx);
1218       return nullptr;
1219     }
1220     SetHasNurseryMemory(setobj.get(), true);
1221   }
1222
1223   auto range = data->createRange(buffer, insideNursery);
1224   iterobj->setReservedSlot(RangeSlot, PrivateValue(range));
1225
1226   return iterobj;
1227 }
1228
1229 void SetIteratorObject::finalize(JS::GCContext* gcx, JSObject* obj) {
1230   MOZ_ASSERT(gcx->onMainThread());
1231   MOZ_ASSERT(!IsInsideNursery(obj));
1232
1233   auto range = SetIteratorObjectRange(&obj->as<NativeObject>());
1234   MOZ_ASSERT(!gcx->runtime()->gc.nursery().isInside(range));
1235
1236   // Bug 1560019: Malloc memory associated with SetIteratorObjects is not
1237   // currently tracked.
1238   gcx->deleteUntracked(range);
1239 }
1240
1241 size_t SetIteratorObject::objectMoved(JSObject* obj, JSObject* old) {
1242   if (!IsInsideNursery(old)) {
1243     return 0;
1244   }
1245
1246   SetIteratorObject* iter = &obj->as<SetIteratorObject>();
1247   ValueSet::Range* range = SetIteratorObjectRange(iter);
1248   if (!range) {
1249     return 0;
1250   }
1251
1252   Nursery& nursery = iter->runtimeFromMainThread()->gc.nursery();
1253   if (!nursery.isInside(range)) {
1254     nursery.removeMallocedBufferDuringMinorGC(range);
1255   }
1256
1257   size_t size = RoundUp(sizeof(ValueSet::Range), gc::CellAlignBytes);
1258   ;
1259   AutoEnterOOMUnsafeRegion oomUnsafe;
1260   void* buffer = nursery.allocateBufferSameLocation(obj, size, js::MallocArena);
1261   if (!buffer) {
1262     oomUnsafe.crash("SetIteratorObject::objectMoved");
1263   }
1264
1265   bool iteratorIsInNursery = IsInsideNursery(obj);
1266   MOZ_ASSERT(iteratorIsInNursery == nursery.isInside(buffer));
1267   auto* newRange = new (buffer) ValueSet::Range(*range, iteratorIsInNursery);
1268   range->~Range();
1269   iter->setReservedSlot(SetIteratorObject::RangeSlot, PrivateValue(newRange));
1270
1271   if (iteratorIsInNursery && iter->target()) {
1272     SetHasNurseryMemory(iter->target(), true);
1273   }
1274
1275   return size;
1276 }
1277
1278 SetObject* SetIteratorObject::target() const {
1279   Value value = getFixedSlot(TargetSlot);
1280   if (value.isUndefined()) {
1281     return nullptr;
1282   }
1283
1284   return &MaybeForwarded(&value.toObject())->as<SetObject>();
1285 }
1286
1287 bool SetIteratorObject::next(SetIteratorObject* setIterator,
1288                              ArrayObject* resultObj) {
1289   // IC code calls this directly.
1290   AutoUnsafeCallWithABI unsafe;
1291
1292   // Check invariants for inlined _GetNextSetEntryForIterator.
1293
1294   // The array should be tenured, so that post-barrier can be done simply.
1295   MOZ_ASSERT(resultObj->isTenured());
1296
1297   // The array elements should be fixed.
1298   MOZ_ASSERT(resultObj->hasFixedElements());
1299   MOZ_ASSERT(resultObj->getDenseInitializedLength() == 1);
1300   MOZ_ASSERT(resultObj->getDenseCapacity() >= 1);
1301
1302   ValueSet::Range* range = SetIteratorObjectRange(setIterator);
1303   if (!range) {
1304     return true;
1305   }
1306
1307   if (range->empty()) {
1308     DestroyRange<ValueSet::Range>(setIterator, range);
1309     setIterator->setReservedSlot(RangeSlot, PrivateValue(nullptr));
1310     return true;
1311   }
1312
1313   resultObj->setDenseElement(0, range->front().get());
1314   range->popFront();
1315   return false;
1316 }
1317
1318 /* static */
1319 JSObject* SetIteratorObject::createResult(JSContext* cx) {
1320   Rooted<ArrayObject*> resultObj(
1321       cx, NewDenseFullyAllocatedArray(cx, 1, TenuredObject));
1322   if (!resultObj) {
1323     return nullptr;
1324   }
1325
1326   resultObj->setDenseInitializedLength(1);
1327   resultObj->initDenseElement(0, NullValue());
1328
1329   return resultObj;
1330 }
1331
1332 /*** Set ********************************************************************/
1333
1334 const JSClassOps SetObject::classOps_ = {
1335     nullptr,   // addProperty
1336     nullptr,   // delProperty
1337     nullptr,   // enumerate
1338     nullptr,   // newEnumerate
1339     nullptr,   // resolve
1340     nullptr,   // mayResolve
1341     finalize,  // finalize
1342     nullptr,   // call
1343     nullptr,   // construct
1344     trace,     // trace
1345 };
1346
1347 const ClassSpec SetObject::classSpec_ = {
1348     GenericCreateConstructor<SetObject::construct, 0, gc::AllocKind::FUNCTION>,
1349     GenericCreatePrototype<SetObject>,
1350     nullptr,
1351     SetObject::staticProperties,
1352     SetObject::methods,
1353     SetObject::properties,
1354     SetObject::finishInit,
1355 };
1356
1357 const JSClass SetObject::class_ = {
1358     "Set",
1359     JSCLASS_DELAY_METADATA_BUILDER |
1360         JSCLASS_HAS_RESERVED_SLOTS(SetObject::SlotCount) |
1361         JSCLASS_HAS_CACHED_PROTO(JSProto_Set) | JSCLASS_FOREGROUND_FINALIZE |
1362         JSCLASS_SKIP_NURSERY_FINALIZE,
1363     &SetObject::classOps_,
1364     &SetObject::classSpec_,
1365 };
1366
1367 const JSClass SetObject::protoClass_ = {
1368     "Set.prototype",
1369     JSCLASS_HAS_CACHED_PROTO(JSProto_Set),
1370     JS_NULL_CLASS_OPS,
1371     &SetObject::classSpec_,
1372 };
1373
1374 const JSPropertySpec SetObject::properties[] = {
1375     JS_PSG("size", size, 0),
1376     JS_STRING_SYM_PS(toStringTag, "Set", JSPROP_READONLY),
1377     JS_PS_END,
1378 };
1379
1380 const JSFunctionSpec SetObject::methods[] = {
1381     JS_INLINABLE_FN("has", has, 1, 0, SetHas),
1382     JS_FN("add", add, 1, 0),
1383     JS_FN("delete", delete_, 1, 0),
1384     JS_FN("entries", entries, 0, 0),
1385     JS_FN("clear", clear, 0, 0),
1386     JS_SELF_HOSTED_FN("forEach", "SetForEach", 2, 0),
1387 #ifdef NIGHTLY_BUILD
1388     JS_SELF_HOSTED_FN("union", "SetUnion", 1, 0),
1389     JS_SELF_HOSTED_FN("difference", "SetDifference", 1, 0),
1390     JS_SELF_HOSTED_FN("intersection", "SetIntersection", 1, 0),
1391     JS_SELF_HOSTED_FN("symmetricDifference", "SetSymmetricDifference", 1, 0),
1392     JS_SELF_HOSTED_FN("isSubsetOf", "SetIsSubsetOf", 1, 0),
1393     JS_SELF_HOSTED_FN("isSupersetOf", "SetIsSupersetOf", 1, 0),
1394     JS_SELF_HOSTED_FN("isDisjointFrom", "SetIsDisjointFrom", 1, 0),
1395 #endif
1396     JS_FN("values", values, 0, 0),
1397     // @@iterator and |keys| re-defined in finishInit so that they have the
1398     // same identity as |values|.
1399     JS_FN("keys", values, 0, 0),
1400     JS_SYM_FN(iterator, values, 0, 0),
1401     JS_FS_END,
1402 };
1403 // clang-format on
1404
1405 const JSPropertySpec SetObject::staticProperties[] = {
1406     JS_SELF_HOSTED_SYM_GET(species, "$SetSpecies", 0),
1407     JS_PS_END,
1408 };
1409
1410 /* static */ bool SetObject::finishInit(JSContext* cx, HandleObject ctor,
1411                                         HandleObject proto) {
1412   Handle<NativeObject*> nativeProto = proto.as<NativeObject>();
1413
1414   RootedValue valuesFn(cx);
1415   RootedId valuesId(cx, NameToId(cx->names().values));
1416   if (!NativeGetProperty(cx, nativeProto, valuesId, &valuesFn)) {
1417     return false;
1418   }
1419
1420   // 23.2.3.8 Set.prototype.keys()
1421   // The initial value of the "keys" property is the same function object
1422   // as the initial value of the "values" property.
1423   RootedId keysId(cx, NameToId(cx->names().keys));
1424   if (!NativeDefineDataProperty(cx, nativeProto, keysId, valuesFn, 0)) {
1425     return false;
1426   }
1427
1428   // 23.2.3.11 Set.prototype[@@iterator]()
1429   // See above.
1430   RootedId iteratorId(cx, PropertyKey::Symbol(cx->wellKnownSymbols().iterator));
1431   return NativeDefineDataProperty(cx, nativeProto, iteratorId, valuesFn, 0);
1432 }
1433
1434 bool SetObject::keys(JSContext* cx, HandleObject obj,
1435                      JS::MutableHandle<GCVector<JS::Value>> keys) {
1436   ValueSet* set = obj->as<SetObject>().getData();
1437   if (!set) {
1438     return false;
1439   }
1440
1441   for (ValueSet::Range r = set->all(); !r.empty(); r.popFront()) {
1442     if (!keys.append(r.front().get())) {
1443       return false;
1444     }
1445   }
1446
1447   return true;
1448 }
1449
1450 bool SetObject::add(JSContext* cx, HandleObject obj, HandleValue k) {
1451   ValueSet* set = obj->as<SetObject>().getData();
1452   if (!set) {
1453     return false;
1454   }
1455
1456   Rooted<HashableValue> key(cx);
1457   if (!key.setValue(cx, k)) {
1458     return false;
1459   }
1460
1461   if (!PostWriteBarrier(&obj->as<SetObject>(), key.get()) ||
1462       !set->put(key.get())) {
1463     ReportOutOfMemory(cx);
1464     return false;
1465   }
1466   return true;
1467 }
1468
1469 SetObject* SetObject::create(JSContext* cx,
1470                              HandleObject proto /* = nullptr */) {
1471   auto set = cx->make_unique<ValueSet>(cx->zone(),
1472                                        cx->realm()->randomHashCodeScrambler());
1473   if (!set) {
1474     return nullptr;
1475   }
1476
1477   if (!set->init()) {
1478     ReportOutOfMemory(cx);
1479     return nullptr;
1480   }
1481
1482   AutoSetNewObjectMetadata metadata(cx);
1483   SetObject* obj = NewObjectWithClassProto<SetObject>(cx, proto);
1484   if (!obj) {
1485     return nullptr;
1486   }
1487
1488   bool insideNursery = IsInsideNursery(obj);
1489   if (insideNursery && !cx->nursery().addSetWithNurseryMemory(obj)) {
1490     ReportOutOfMemory(cx);
1491     return nullptr;
1492   }
1493
1494   InitReservedSlot(obj, DataSlot, set.release(), MemoryUse::MapObjectTable);
1495   obj->initReservedSlot(NurseryKeysSlot, PrivateValue(nullptr));
1496   obj->initReservedSlot(HasNurseryMemorySlot, JS::BooleanValue(insideNursery));
1497   return obj;
1498 }
1499
1500 void SetObject::trace(JSTracer* trc, JSObject* obj) {
1501   SetObject* setobj = static_cast<SetObject*>(obj);
1502   if (ValueSet* set = setobj->getData()) {
1503     set->trace(trc);
1504   }
1505 }
1506
1507 size_t SetObject::sizeOfData(mozilla::MallocSizeOf mallocSizeOf) {
1508   size_t size = 0;
1509   if (ValueSet* set = getData()) {
1510     size += set->sizeOfIncludingThis(mallocSizeOf);
1511   }
1512   if (NurseryKeysVector* nurseryKeys = GetNurseryKeys(this)) {
1513     size += nurseryKeys->sizeOfIncludingThis(mallocSizeOf);
1514   }
1515   return size;
1516 }
1517
1518 void SetObject::finalize(JS::GCContext* gcx, JSObject* obj) {
1519   MOZ_ASSERT(gcx->onMainThread());
1520   SetObject* setobj = static_cast<SetObject*>(obj);
1521   if (ValueSet* set = setobj->getData()) {
1522     MOZ_ASSERT_IF(obj->isTenured(), !set->hasNurseryRanges());
1523     gcx->delete_(obj, set, MemoryUse::MapObjectTable);
1524   }
1525 }
1526
1527 void SetObject::clearNurseryRangesBeforeMinorGC() {
1528   getTableUnchecked()->destroyNurseryRanges();
1529   SetHasNurseryMemory(this, false);
1530 }
1531
1532 /* static */
1533 SetObject* SetObject::sweepAfterMinorGC(JS::GCContext* gcx, SetObject* setobj) {
1534   Nursery& nursery = gcx->runtime()->gc.nursery();
1535   bool wasInCollectedRegion = nursery.inCollectedRegion(setobj);
1536   if (wasInCollectedRegion && !IsForwarded(setobj)) {
1537     finalize(gcx, setobj);
1538     return nullptr;
1539   }
1540
1541   setobj = MaybeForwarded(setobj);
1542
1543   bool insideNursery = IsInsideNursery(setobj);
1544   if (insideNursery) {
1545     SetHasNurseryMemory(setobj, true);
1546   }
1547
1548   if (wasInCollectedRegion && setobj->isTenured()) {
1549     AddCellMemory(setobj, sizeof(ValueSet), MemoryUse::MapObjectTable);
1550   }
1551
1552   if (!HasNurseryMemory(setobj)) {
1553     return nullptr;
1554   }
1555
1556   return setobj;
1557 }
1558
1559 bool SetObject::isBuiltinAdd(HandleValue add) {
1560   return IsNativeFunction(add, SetObject::add);
1561 }
1562
1563 bool SetObject::construct(JSContext* cx, unsigned argc, Value* vp) {
1564   AutoJSConstructorProfilerEntry pseudoFrame(cx, "Set");
1565   CallArgs args = CallArgsFromVp(argc, vp);
1566
1567   if (!ThrowIfNotConstructing(cx, args, "Set")) {
1568     return false;
1569   }
1570
1571   RootedObject proto(cx);
1572   if (!GetPrototypeFromBuiltinConstructor(cx, args, JSProto_Set, &proto)) {
1573     return false;
1574   }
1575
1576   Rooted<SetObject*> obj(cx, SetObject::create(cx, proto));
1577   if (!obj) {
1578     return false;
1579   }
1580
1581   if (!args.get(0).isNullOrUndefined()) {
1582     RootedValue iterable(cx, args[0]);
1583     bool optimized = false;
1584     if (!IsOptimizableInitForSet<GlobalObject::getOrCreateSetPrototype,
1585                                  isBuiltinAdd>(cx, obj, iterable, &optimized)) {
1586       return false;
1587     }
1588
1589     if (optimized) {
1590       RootedValue keyVal(cx);
1591       Rooted<HashableValue> key(cx);
1592       ValueSet* set = obj->getData();
1593       Rooted<ArrayObject*> array(cx, &iterable.toObject().as<ArrayObject>());
1594       for (uint32_t index = 0; index < array->getDenseInitializedLength();
1595            ++index) {
1596         keyVal.set(array->getDenseElement(index));
1597         MOZ_ASSERT(!keyVal.isMagic(JS_ELEMENTS_HOLE));
1598
1599         if (!key.setValue(cx, keyVal)) {
1600           return false;
1601         }
1602         if (!PostWriteBarrier(obj, key.get()) || !set->put(key.get())) {
1603           ReportOutOfMemory(cx);
1604           return false;
1605         }
1606       }
1607     } else {
1608       FixedInvokeArgs<1> args2(cx);
1609       args2[0].set(args[0]);
1610
1611       RootedValue thisv(cx, ObjectValue(*obj));
1612       if (!CallSelfHostedFunction(cx, cx->names().SetConstructorInit, thisv,
1613                                   args2, args2.rval())) {
1614         return false;
1615       }
1616     }
1617   }
1618
1619   args.rval().setObject(*obj);
1620   return true;
1621 }
1622
1623 bool SetObject::is(HandleValue v) {
1624   return v.isObject() && v.toObject().hasClass(&class_) &&
1625          !v.toObject().as<SetObject>().getReservedSlot(DataSlot).isUndefined();
1626 }
1627
1628 bool SetObject::is(HandleObject o) {
1629   return o->hasClass(&class_) &&
1630          !o->as<SetObject>().getReservedSlot(DataSlot).isUndefined();
1631 }
1632
1633 ValueSet& SetObject::extract(HandleObject o) {
1634   MOZ_ASSERT(o->hasClass(&SetObject::class_));
1635   return *o->as<SetObject>().getData();
1636 }
1637
1638 ValueSet& SetObject::extract(const CallArgs& args) {
1639   MOZ_ASSERT(args.thisv().isObject());
1640   MOZ_ASSERT(args.thisv().toObject().hasClass(&SetObject::class_));
1641   return *static_cast<SetObject&>(args.thisv().toObject()).getData();
1642 }
1643
1644 uint32_t SetObject::size(JSContext* cx, HandleObject obj) {
1645   MOZ_ASSERT(SetObject::is(obj));
1646   ValueSet& set = extract(obj);
1647   static_assert(sizeof(set.count()) <= sizeof(uint32_t),
1648                 "set count must be precisely representable as a JS number");
1649   return set.count();
1650 }
1651
1652 bool SetObject::size_impl(JSContext* cx, const CallArgs& args) {
1653   MOZ_ASSERT(is(args.thisv()));
1654
1655   ValueSet& set = extract(args);
1656   static_assert(sizeof(set.count()) <= sizeof(uint32_t),
1657                 "set count must be precisely representable as a JS number");
1658   args.rval().setNumber(set.count());
1659   return true;
1660 }
1661
1662 bool SetObject::size(JSContext* cx, unsigned argc, Value* vp) {
1663   AutoJSMethodProfilerEntry pseudoFrame(cx, "Set.prototype", "size");
1664   CallArgs args = CallArgsFromVp(argc, vp);
1665   return CallNonGenericMethod<SetObject::is, SetObject::size_impl>(cx, args);
1666 }
1667
1668 bool SetObject::has_impl(JSContext* cx, const CallArgs& args) {
1669   MOZ_ASSERT(is(args.thisv()));
1670
1671   ValueSet& set = extract(args);
1672   ARG0_KEY(cx, args, key);
1673   args.rval().setBoolean(set.has(key));
1674   return true;
1675 }
1676
1677 bool SetObject::has(JSContext* cx, HandleObject obj, HandleValue key,
1678                     bool* rval) {
1679   MOZ_ASSERT(SetObject::is(obj));
1680
1681   ValueSet& set = extract(obj);
1682   Rooted<HashableValue> k(cx);
1683
1684   if (!k.setValue(cx, key)) {
1685     return false;
1686   }
1687
1688   *rval = set.has(k);
1689   return true;
1690 }
1691
1692 bool SetObject::has(JSContext* cx, unsigned argc, Value* vp) {
1693   AutoJSMethodProfilerEntry pseudoFrame(cx, "Set.prototype", "has");
1694   CallArgs args = CallArgsFromVp(argc, vp);
1695   return CallNonGenericMethod<SetObject::is, SetObject::has_impl>(cx, args);
1696 }
1697
1698 bool SetObject::add_impl(JSContext* cx, const CallArgs& args) {
1699   MOZ_ASSERT(is(args.thisv()));
1700
1701   ValueSet& set = extract(args);
1702   ARG0_KEY(cx, args, key);
1703   if (!PostWriteBarrier(&args.thisv().toObject().as<SetObject>(), key.get()) ||
1704       !set.put(key.get())) {
1705     ReportOutOfMemory(cx);
1706     return false;
1707   }
1708   args.rval().set(args.thisv());
1709   return true;
1710 }
1711
1712 bool SetObject::add(JSContext* cx, unsigned argc, Value* vp) {
1713   AutoJSMethodProfilerEntry pseudoFrame(cx, "Set.prototype", "add");
1714   CallArgs args = CallArgsFromVp(argc, vp);
1715   return CallNonGenericMethod<SetObject::is, SetObject::add_impl>(cx, args);
1716 }
1717
1718 bool SetObject::delete_(JSContext* cx, HandleObject obj, HandleValue key,
1719                         bool* rval) {
1720   MOZ_ASSERT(SetObject::is(obj));
1721
1722   ValueSet& set = extract(obj);
1723   Rooted<HashableValue> k(cx);
1724
1725   if (!k.setValue(cx, key)) {
1726     return false;
1727   }
1728
1729   if (!set.remove(k, rval)) {
1730     ReportOutOfMemory(cx);
1731     return false;
1732   }
1733   return true;
1734 }
1735
1736 bool SetObject::delete_impl(JSContext* cx, const CallArgs& args) {
1737   MOZ_ASSERT(is(args.thisv()));
1738
1739   ValueSet& set = extract(args);
1740   ARG0_KEY(cx, args, key);
1741   bool found;
1742   if (!set.remove(key, &found)) {
1743     ReportOutOfMemory(cx);
1744     return false;
1745   }
1746   args.rval().setBoolean(found);
1747   return true;
1748 }
1749
1750 bool SetObject::delete_(JSContext* cx, unsigned argc, Value* vp) {
1751   AutoJSMethodProfilerEntry pseudoFrame(cx, "Set.prototype", "delete");
1752   CallArgs args = CallArgsFromVp(argc, vp);
1753   return CallNonGenericMethod<SetObject::is, SetObject::delete_impl>(cx, args);
1754 }
1755
1756 bool SetObject::iterator(JSContext* cx, IteratorKind kind, HandleObject obj,
1757                          MutableHandleValue iter) {
1758   MOZ_ASSERT(SetObject::is(obj));
1759   ValueSet& set = extract(obj);
1760   Rooted<JSObject*> iterobj(cx, SetIteratorObject::create(cx, obj, &set, kind));
1761   if (!iterobj) {
1762     return false;
1763   }
1764   iter.setObject(*iterobj);
1765   return true;
1766 }
1767
1768 bool SetObject::iterator_impl(JSContext* cx, const CallArgs& args,
1769                               IteratorKind kind) {
1770   Rooted<SetObject*> setobj(cx, &args.thisv().toObject().as<SetObject>());
1771   ValueSet& set = *setobj->getData();
1772   Rooted<JSObject*> iterobj(cx,
1773                             SetIteratorObject::create(cx, setobj, &set, kind));
1774   if (!iterobj) {
1775     return false;
1776   }
1777   args.rval().setObject(*iterobj);
1778   return true;
1779 }
1780
1781 bool SetObject::values_impl(JSContext* cx, const CallArgs& args) {
1782   return iterator_impl(cx, args, Values);
1783 }
1784
1785 bool SetObject::values(JSContext* cx, unsigned argc, Value* vp) {
1786   AutoJSMethodProfilerEntry pseudoFrame(cx, "Set.prototype", "values");
1787   CallArgs args = CallArgsFromVp(argc, vp);
1788   return CallNonGenericMethod(cx, is, values_impl, args);
1789 }
1790
1791 bool SetObject::entries_impl(JSContext* cx, const CallArgs& args) {
1792   return iterator_impl(cx, args, Entries);
1793 }
1794
1795 bool SetObject::entries(JSContext* cx, unsigned argc, Value* vp) {
1796   AutoJSMethodProfilerEntry pseudoFrame(cx, "Set.prototype", "entries");
1797   CallArgs args = CallArgsFromVp(argc, vp);
1798   return CallNonGenericMethod(cx, is, entries_impl, args);
1799 }
1800
1801 bool SetObject::clear(JSContext* cx, HandleObject obj) {
1802   MOZ_ASSERT(SetObject::is(obj));
1803   ValueSet& set = extract(obj);
1804   if (!set.clear()) {
1805     ReportOutOfMemory(cx);
1806     return false;
1807   }
1808   return true;
1809 }
1810
1811 bool SetObject::clear_impl(JSContext* cx, const CallArgs& args) {
1812   Rooted<SetObject*> setobj(cx, &args.thisv().toObject().as<SetObject>());
1813   if (!setobj->getData()->clear()) {
1814     ReportOutOfMemory(cx);
1815     return false;
1816   }
1817   args.rval().setUndefined();
1818   return true;
1819 }
1820
1821 bool SetObject::clear(JSContext* cx, unsigned argc, Value* vp) {
1822   AutoJSMethodProfilerEntry pseudoFrame(cx, "Set.prototype", "clear");
1823   CallArgs args = CallArgsFromVp(argc, vp);
1824   return CallNonGenericMethod(cx, is, clear_impl, args);
1825 }
1826
1827 bool SetObject::copy(JSContext* cx, unsigned argc, Value* vp) {
1828   CallArgs args = CallArgsFromVp(argc, vp);
1829   MOZ_ASSERT(args.length() == 1);
1830   MOZ_ASSERT(SetObject::is(args[0]));
1831
1832   auto* result = SetObject::create(cx);
1833   if (!result) {
1834     return false;
1835   }
1836
1837   ValueSet* set = result->getData();
1838   MOZ_ASSERT(set);
1839
1840   auto* from = &args[0].toObject().as<SetObject>();
1841   for (auto range = from->getData()->all(); !range.empty(); range.popFront()) {
1842     HashableValue value = range.front().get();
1843
1844     if (!PostWriteBarrier(result, value) || !set->put(value)) {
1845       ReportOutOfMemory(cx);
1846       return false;
1847     }
1848   }
1849
1850   args.rval().setObject(*result);
1851   return true;
1852 }
1853
1854 /*** JS static utility functions ********************************************/
1855
1856 static bool forEach(const char* funcName, JSContext* cx, HandleObject obj,
1857                     HandleValue callbackFn, HandleValue thisArg) {
1858   CHECK_THREAD(cx);
1859
1860   RootedId forEachId(cx, NameToId(cx->names().forEach));
1861   RootedFunction forEachFunc(
1862       cx, JS::GetSelfHostedFunction(cx, funcName, forEachId, 2));
1863   if (!forEachFunc) {
1864     return false;
1865   }
1866
1867   RootedValue fval(cx, ObjectValue(*forEachFunc));
1868   return Call(cx, fval, obj, callbackFn, thisArg, &fval);
1869 }
1870
1871 // Handles Clear/Size for public jsapi map/set access
1872 template <typename RetT>
1873 RetT CallObjFunc(RetT (*ObjFunc)(JSContext*, HandleObject), JSContext* cx,
1874                  HandleObject obj) {
1875   CHECK_THREAD(cx);
1876   cx->check(obj);
1877
1878   // Always unwrap, in case this is an xray or cross-compartment wrapper.
1879   RootedObject unwrappedObj(cx);
1880   unwrappedObj = UncheckedUnwrap(obj);
1881
1882   // Enter the realm of the backing object before calling functions on
1883   // it.
1884   JSAutoRealm ar(cx, unwrappedObj);
1885   return ObjFunc(cx, unwrappedObj);
1886 }
1887
1888 // Handles Has/Delete for public jsapi map/set access
1889 bool CallObjFunc(bool (*ObjFunc)(JSContext* cx, HandleObject obj,
1890                                  HandleValue key, bool* rval),
1891                  JSContext* cx, HandleObject obj, HandleValue key, bool* rval) {
1892   CHECK_THREAD(cx);
1893   cx->check(obj, key);
1894
1895   // Always unwrap, in case this is an xray or cross-compartment wrapper.
1896   RootedObject unwrappedObj(cx);
1897   unwrappedObj = UncheckedUnwrap(obj);
1898   JSAutoRealm ar(cx, unwrappedObj);
1899
1900   // If we're working with a wrapped map/set, rewrap the key into the
1901   // compartment of the unwrapped map/set.
1902   RootedValue wrappedKey(cx, key);
1903   if (obj != unwrappedObj) {
1904     if (!JS_WrapValue(cx, &wrappedKey)) {
1905       return false;
1906     }
1907   }
1908   return ObjFunc(cx, unwrappedObj, wrappedKey, rval);
1909 }
1910
1911 // Handles iterator generation for public jsapi map/set access
1912 template <typename Iter>
1913 bool CallObjFunc(bool (*ObjFunc)(JSContext* cx, Iter kind, HandleObject obj,
1914                                  MutableHandleValue iter),
1915                  JSContext* cx, Iter iterType, HandleObject obj,
1916                  MutableHandleValue rval) {
1917   CHECK_THREAD(cx);
1918   cx->check(obj);
1919
1920   // Always unwrap, in case this is an xray or cross-compartment wrapper.
1921   RootedObject unwrappedObj(cx);
1922   unwrappedObj = UncheckedUnwrap(obj);
1923   {
1924     // Retrieve the iterator while in the unwrapped map/set's compartment,
1925     // otherwise we'll crash on a compartment assert.
1926     JSAutoRealm ar(cx, unwrappedObj);
1927     if (!ObjFunc(cx, iterType, unwrappedObj, rval)) {
1928       return false;
1929     }
1930   }
1931
1932   // If the caller is in a different compartment than the map/set, rewrap the
1933   // iterator object into the caller's compartment.
1934   if (obj != unwrappedObj) {
1935     if (!JS_WrapValue(cx, rval)) {
1936       return false;
1937     }
1938   }
1939   return true;
1940 }
1941
1942 /*** JS public APIs *********************************************************/
1943
1944 JS_PUBLIC_API JSObject* JS::NewMapObject(JSContext* cx) {
1945   return MapObject::create(cx);
1946 }
1947
1948 JS_PUBLIC_API uint32_t JS::MapSize(JSContext* cx, HandleObject obj) {
1949   return CallObjFunc<uint32_t>(&MapObject::size, cx, obj);
1950 }
1951
1952 JS_PUBLIC_API bool JS::MapGet(JSContext* cx, HandleObject obj, HandleValue key,
1953                               MutableHandleValue rval) {
1954   CHECK_THREAD(cx);
1955   cx->check(obj, key, rval);
1956
1957   // Unwrap the object, and enter its realm. If object isn't wrapped,
1958   // this is essentially a noop.
1959   RootedObject unwrappedObj(cx);
1960   unwrappedObj = UncheckedUnwrap(obj);
1961   {
1962     JSAutoRealm ar(cx, unwrappedObj);
1963     RootedValue wrappedKey(cx, key);
1964
1965     // If we passed in a wrapper, wrap our key into its compartment now.
1966     if (obj != unwrappedObj) {
1967       if (!JS_WrapValue(cx, &wrappedKey)) {
1968         return false;
1969       }
1970     }
1971     if (!MapObject::get(cx, unwrappedObj, wrappedKey, rval)) {
1972       return false;
1973     }
1974   }
1975
1976   // If we passed in a wrapper, wrap our return value on the way out.
1977   if (obj != unwrappedObj) {
1978     if (!JS_WrapValue(cx, rval)) {
1979       return false;
1980     }
1981   }
1982   return true;
1983 }
1984
1985 JS_PUBLIC_API bool JS::MapSet(JSContext* cx, HandleObject obj, HandleValue key,
1986                               HandleValue val) {
1987   CHECK_THREAD(cx);
1988   cx->check(obj, key, val);
1989
1990   // Unwrap the object, and enter its compartment. If object isn't wrapped,
1991   // this is essentially a noop.
1992   RootedObject unwrappedObj(cx);
1993   unwrappedObj = UncheckedUnwrap(obj);
1994   {
1995     JSAutoRealm ar(cx, unwrappedObj);
1996
1997     // If we passed in a wrapper, wrap both key and value before adding to
1998     // the map
1999     RootedValue wrappedKey(cx, key);
2000     RootedValue wrappedValue(cx, val);
2001     if (obj != unwrappedObj) {
2002       if (!JS_WrapValue(cx, &wrappedKey) || !JS_WrapValue(cx, &wrappedValue)) {
2003         return false;
2004       }
2005     }
2006     return MapObject::set(cx, unwrappedObj, wrappedKey, wrappedValue);
2007   }
2008 }
2009
2010 JS_PUBLIC_API bool JS::MapHas(JSContext* cx, HandleObject obj, HandleValue key,
2011                               bool* rval) {
2012   return CallObjFunc(MapObject::has, cx, obj, key, rval);
2013 }
2014
2015 JS_PUBLIC_API bool JS::MapDelete(JSContext* cx, HandleObject obj,
2016                                  HandleValue key, bool* rval) {
2017   return CallObjFunc(MapObject::delete_, cx, obj, key, rval);
2018 }
2019
2020 JS_PUBLIC_API bool JS::MapClear(JSContext* cx, HandleObject obj) {
2021   return CallObjFunc(&MapObject::clear, cx, obj);
2022 }
2023
2024 JS_PUBLIC_API bool JS::MapKeys(JSContext* cx, HandleObject obj,
2025                                MutableHandleValue rval) {
2026   return CallObjFunc(&MapObject::iterator, cx, MapObject::Keys, obj, rval);
2027 }
2028
2029 JS_PUBLIC_API bool JS::MapValues(JSContext* cx, HandleObject obj,
2030                                  MutableHandleValue rval) {
2031   return CallObjFunc(&MapObject::iterator, cx, MapObject::Values, obj, rval);
2032 }
2033
2034 JS_PUBLIC_API bool JS::MapEntries(JSContext* cx, HandleObject obj,
2035                                   MutableHandleValue rval) {
2036   return CallObjFunc(&MapObject::iterator, cx, MapObject::Entries, obj, rval);
2037 }
2038
2039 JS_PUBLIC_API bool JS::MapForEach(JSContext* cx, HandleObject obj,
2040                                   HandleValue callbackFn, HandleValue thisVal) {
2041   return forEach("MapForEach", cx, obj, callbackFn, thisVal);
2042 }
2043
2044 JS_PUBLIC_API JSObject* JS::NewSetObject(JSContext* cx) {
2045   return SetObject::create(cx);
2046 }
2047
2048 JS_PUBLIC_API uint32_t JS::SetSize(JSContext* cx, HandleObject obj) {
2049   return CallObjFunc<uint32_t>(&SetObject::size, cx, obj);
2050 }
2051
2052 JS_PUBLIC_API bool JS::SetAdd(JSContext* cx, HandleObject obj,
2053                               HandleValue key) {
2054   CHECK_THREAD(cx);
2055   cx->check(obj, key);
2056
2057   // Unwrap the object, and enter its compartment. If object isn't wrapped,
2058   // this is essentially a noop.
2059   RootedObject unwrappedObj(cx);
2060   unwrappedObj = UncheckedUnwrap(obj);
2061   {
2062     JSAutoRealm ar(cx, unwrappedObj);
2063
2064     // If we passed in a wrapper, wrap key before adding to the set
2065     RootedValue wrappedKey(cx, key);
2066     if (obj != unwrappedObj) {
2067       if (!JS_WrapValue(cx, &wrappedKey)) {
2068         return false;
2069       }
2070     }
2071     return SetObject::add(cx, unwrappedObj, wrappedKey);
2072   }
2073 }
2074
2075 JS_PUBLIC_API bool JS::SetHas(JSContext* cx, HandleObject obj, HandleValue key,
2076                               bool* rval) {
2077   return CallObjFunc(SetObject::has, cx, obj, key, rval);
2078 }
2079
2080 JS_PUBLIC_API bool JS::SetDelete(JSContext* cx, HandleObject obj,
2081                                  HandleValue key, bool* rval) {
2082   return CallObjFunc(SetObject::delete_, cx, obj, key, rval);
2083 }
2084
2085 JS_PUBLIC_API bool JS::SetClear(JSContext* cx, HandleObject obj) {
2086   return CallObjFunc(&SetObject::clear, cx, obj);
2087 }
2088
2089 JS_PUBLIC_API bool JS::SetKeys(JSContext* cx, HandleObject obj,
2090                                MutableHandleValue rval) {
2091   return SetValues(cx, obj, rval);
2092 }
2093
2094 JS_PUBLIC_API bool JS::SetValues(JSContext* cx, HandleObject obj,
2095                                  MutableHandleValue rval) {
2096   return CallObjFunc(&SetObject::iterator, cx, SetObject::Values, obj, rval);
2097 }
2098
2099 JS_PUBLIC_API bool JS::SetEntries(JSContext* cx, HandleObject obj,
2100                                   MutableHandleValue rval) {
2101   return CallObjFunc(&SetObject::iterator, cx, SetObject::Entries, obj, rval);
2102 }
2103
2104 JS_PUBLIC_API bool JS::SetForEach(JSContext* cx, HandleObject obj,
2105                                   HandleValue callbackFn, HandleValue thisVal) {
2106   return forEach("SetForEach", cx, obj, callbackFn, thisVal);
2107 }