js/src/vm/Shape.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 "vm/Shape-inl.h"
   8
   9 #include "mozilla/MathAlgorithms.h"
  10 #include "mozilla/PodOperations.h"
  11
  12 #include "gc/HashUtil.h"
  13 #include "js/friend/WindowProxy.h"  // js::IsWindow
  14 #include "js/HashTable.h"
  15 #include "js/Printer.h"  // js::GenericPrinter, js::Fprinter
  16 #include "js/UniquePtr.h"
  17 #include "vm/JSObject.h"
  18 #include "vm/JSONPrinter.h"  // js::JSONPrinter
  19 #include "vm/ShapeZone.h"
  20 #include "vm/Watchtower.h"
  21
  22 #include "gc/StableCellHasher-inl.h"
  23 #include "vm/JSContext-inl.h"
  24 #include "vm/JSObject-inl.h"
  25 #include "vm/NativeObject-inl.h"
  26
  27 using namespace js;
  28
  29 using mozilla::CeilingLog2Size;
  30 using mozilla::PodZero;
  31
  32 using JS::AutoCheckCannotGC;
  33
  34 /* static */
  35 bool Shape::replaceShape(JSContext* cx, HandleObject obj,
  36                          ObjectFlags objectFlags, TaggedProto proto,
  37                          uint32_t nfixed) {
  38   Shape* newShape;
  39   switch (obj->shape()->kind()) {
  40     case Kind::Shared: {
  41       Handle<NativeObject*> nobj = obj.as<NativeObject>();
  42       if (nobj->shape()->propMap()) {
  43         Rooted<BaseShape*> base(cx, obj->shape()->base());
  44         if (proto != base->proto()) {
  45           Rooted<TaggedProto> protoRoot(cx, proto);
  46           base = BaseShape::get(cx, base->clasp(), base->realm(), protoRoot);
  47           if (!base) {
  48             return false;
  49           }
  50         }
  51         Rooted<SharedPropMap*> map(cx, nobj->sharedShape()->propMap());
  52         uint32_t mapLength = nobj->shape()->propMapLength();
  53         newShape = SharedShape::getPropMapShape(cx, base, nfixed, map,
  54                                                 mapLength, objectFlags);
  55       } else {
  56         newShape = SharedShape::getInitialShape(
  57             cx, obj->shape()->getObjectClass(), obj->shape()->realm(), proto,
  58             nfixed, objectFlags);
  59       }
  60       break;
  61     }
  62     case Kind::Dictionary: {
  63       Handle<NativeObject*> nobj = obj.as<NativeObject>();
  64
  65       Rooted<BaseShape*> base(cx, nobj->shape()->base());
  66       if (proto != base->proto()) {
  67         Rooted<TaggedProto> protoRoot(cx, proto);
  68         base = BaseShape::get(cx, nobj->getClass(), nobj->realm(), protoRoot);
  69         if (!base) {
  70           return false;
  71         }
  72       }
  73
  74       Rooted<DictionaryPropMap*> map(cx, nobj->dictionaryShape()->propMap());
  75       uint32_t mapLength = nobj->shape()->propMapLength();
  76       newShape =
  77           DictionaryShape::new_(cx, base, objectFlags, nfixed, map, mapLength);
  78       break;
  79     }
  80     case Kind::Proxy:
  81       MOZ_ASSERT(nfixed == 0);
  82       newShape =
  83           ProxyShape::getShape(cx, obj->shape()->getObjectClass(),
  84                                obj->shape()->realm(), proto, objectFlags);
  85       break;
  86     case Kind::WasmGC:
  87       MOZ_ASSERT(nfixed == 0);
  88       const wasm::RecGroup* recGroup = obj->shape()->asWasmGC().recGroup();
  89       newShape = WasmGCShape::getShape(cx, obj->shape()->getObjectClass(),
  90                                        obj->shape()->realm(), proto, recGroup,
  91                                        objectFlags);
  92       break;
  93   }
  94   if (!newShape) {
  95     return false;
  96   }
  97
  98   obj->setShape(newShape);
  99   return true;
 100 }
 101
 102 /* static */
 103 bool js::NativeObject::toDictionaryMode(JSContext* cx,
 104                                         Handle<NativeObject*> obj) {
 105   MOZ_ASSERT(!obj->inDictionaryMode());
 106   MOZ_ASSERT(cx->isInsideCurrentCompartment(obj));
 107
 108   Rooted<NativeShape*> shape(cx, obj->shape());
 109   uint32_t span = obj->slotSpan();
 110
 111   uint32_t mapLength = shape->propMapLength();
 112   MOZ_ASSERT(mapLength > 0, "shouldn't convert empty object to dictionary");
 113
 114   // Clone the shared property map to an unshared dictionary map.
 115   Rooted<SharedPropMap*> map(cx, shape->propMap()->asShared());
 116   Rooted<DictionaryPropMap*> dictMap(
 117       cx, SharedPropMap::toDictionaryMap(cx, map, mapLength));
 118   if (!dictMap) {
 119     return false;
 120   }
 121
 122   // Allocate and use a new dictionary shape.
 123   Rooted<BaseShape*> base(cx, shape->base());
 124   shape = DictionaryShape::new_(cx, base, shape->objectFlags(),
 125                                 shape->numFixedSlots(), dictMap, mapLength);
 126   if (!shape) {
 127     return false;
 128   }
 129   obj->setShape(shape);
 130
 131   MOZ_ASSERT(obj->inDictionaryMode());
 132   obj->setDictionaryModeSlotSpan(span);
 133
 134   return true;
 135 }
 136
 137 namespace js {
 138
 139 class MOZ_RAII AutoCheckShapeConsistency {
 140 #ifdef DEBUG
 141   Handle<NativeObject*> obj_;
 142 #endif
 143
 144  public:
 145   explicit AutoCheckShapeConsistency(Handle<NativeObject*> obj)
 146 #ifdef DEBUG
 147       : obj_(obj)
 148 #endif
 149   {
 150   }
 151
 152 #ifdef DEBUG
 153   ~AutoCheckShapeConsistency() { obj_->checkShapeConsistency(); }
 154 #endif
 155 };
 156
 157 }  // namespace js
 158
 159 /* static */ MOZ_ALWAYS_INLINE bool
 160 NativeObject::maybeConvertToDictionaryForAdd(JSContext* cx,
 161                                              Handle<NativeObject*> obj) {
 162   if (obj->inDictionaryMode()) {
 163     return true;
 164   }
 165   SharedPropMap* map = obj->sharedShape()->propMap();
 166   if (!map) {
 167     return true;
 168   }
 169   if (MOZ_LIKELY(!map->shouldConvertToDictionaryForAdd())) {
 170     return true;
 171   }
 172   return toDictionaryMode(cx, obj);
 173 }
 174
 175 static void AssertValidCustomDataProp(NativeObject* obj, PropertyFlags flags) {
 176   // We only support custom data properties on ArrayObject and ArgumentsObject.
 177   // The mechanism is deprecated so we don't want to add new uses.
 178   MOZ_ASSERT(flags.isCustomDataProperty());
 179   MOZ_ASSERT(!flags.isAccessorProperty());
 180   MOZ_ASSERT(obj->is<ArrayObject>() || obj->is<ArgumentsObject>());
 181 }
 182
 183 /* static */
 184 bool NativeObject::addCustomDataProperty(JSContext* cx,
 185                                          Handle<NativeObject*> obj, HandleId id,
 186                                          PropertyFlags flags) {
 187   MOZ_ASSERT(!id.isVoid());
 188   MOZ_ASSERT(!id.isPrivateName());
 189   MOZ_ASSERT(!obj->containsPure(id));
 190
 191   AutoCheckShapeConsistency check(obj);
 192   AssertValidCustomDataProp(obj, flags);
 193
 194   if (!Watchtower::watchPropertyAdd(cx, obj, id)) {
 195     return false;
 196   }
 197
 198   if (!maybeConvertToDictionaryForAdd(cx, obj)) {
 199     return false;
 200   }
 201
 202   ObjectFlags objectFlags = obj->shape()->objectFlags();
 203   const JSClass* clasp = obj->shape()->getObjectClass();
 204
 205   if (obj->inDictionaryMode()) {
 206     // First generate a new dictionary shape so that the map can be mutated
 207     // without having to worry about OOM conditions.
 208     if (!NativeObject::generateNewDictionaryShape(cx, obj)) {
 209       return false;
 210     }
 211
 212     Rooted<DictionaryPropMap*> map(cx, obj->dictionaryShape()->propMap());
 213     uint32_t mapLength = obj->shape()->propMapLength();
 214     if (!DictionaryPropMap::addProperty(cx, clasp, &map, &mapLength, id, flags,
 215                                         SHAPE_INVALID_SLOT, &objectFlags)) {
 216       return false;
 217     }
 218
 219     obj->dictionaryShape()->updateNewShape(objectFlags, map, mapLength);
 220     return true;
 221   }
 222
 223   Rooted<SharedPropMap*> map(cx, obj->sharedShape()->propMap());
 224   uint32_t mapLength = obj->shape()->propMapLength();
 225   if (!SharedPropMap::addCustomDataProperty(cx, clasp, &map, &mapLength, id,
 226                                             flags, &objectFlags)) {
 227     return false;
 228   }
 229
 230   Shape* shape = SharedShape::getPropMapShape(cx, obj->shape()->base(),
 231                                               obj->shape()->numFixedSlots(),
 232                                               map, mapLength, objectFlags);
 233   if (!shape) {
 234     return false;
 235   }
 236
 237   obj->setShape(shape);
 238   return true;
 239 }
 240
 241 static ShapeSetForAdd* MakeShapeSetForAdd(SharedShape* shape1,
 242                                           SharedShape* shape2) {
 243   MOZ_ASSERT(shape1 != shape2);
 244   MOZ_ASSERT(shape1->propMapLength() == shape2->propMapLength());
 245
 246   auto hash = MakeUnique<ShapeSetForAdd>();
 247   if (!hash || !hash->reserve(2)) {
 248     return nullptr;
 249   }
 250
 251   PropertyInfoWithKey prop = shape1->lastProperty();
 252   hash->putNewInfallible(ShapeForAddHasher::Lookup(prop.key(), prop.flags()),
 253                          shape1);
 254
 255   prop = shape2->lastProperty();
 256   hash->putNewInfallible(ShapeForAddHasher::Lookup(prop.key(), prop.flags()),
 257                          shape2);
 258
 259   return hash.release();
 260 }
 261
 262 static MOZ_ALWAYS_INLINE SharedShape* LookupShapeForAdd(Shape* shape,
 263                                                         PropertyKey key,
 264                                                         PropertyFlags flags,
 265                                                         uint32_t* slot) {
 266   ShapeCachePtr cache = shape->cache();
 267
 268   if (cache.isSingleShapeForAdd()) {
 269     SharedShape* newShape = cache.toSingleShapeForAdd();
 270     if (newShape->lastPropertyMatchesForAdd(key, flags, slot)) {
 271       return newShape;
 272     }
 273     return nullptr;
 274   }
 275
 276   if (cache.isShapeSetForAdd()) {
 277     ShapeSetForAdd* set = cache.toShapeSetForAdd();
 278     ShapeForAddHasher::Lookup lookup(key, flags);
 279     if (auto p = set->lookup(lookup)) {
 280       SharedShape* newShape = *p;
 281       *slot = newShape->lastProperty().slot();
 282       return newShape;
 283     }
 284     return nullptr;
 285   }
 286
 287   MOZ_ASSERT(!cache.isForAdd());
 288   return nullptr;
 289 }
 290
 291 // Add shapes with a non-None ShapeCachePtr to the shapesWithCache list so that
 292 // these caches can be discarded on GC.
 293 static bool RegisterShapeCache(JSContext* cx, Shape* shape) {
 294   ShapeCachePtr cache = shape->cache();
 295   if (!cache.isNone()) {
 296     // Already registered this shape.
 297     return true;
 298   }
 299   return cx->zone()->shapeZone().shapesWithCache.append(shape);
 300 }
 301
 302 /* static */
 303 bool NativeObject::addProperty(JSContext* cx, Handle<NativeObject*> obj,
 304                                HandleId id, PropertyFlags flags,
 305                                uint32_t* slot) {
 306   AutoCheckShapeConsistency check(obj);
 307   MOZ_ASSERT(!flags.isCustomDataProperty(),
 308              "Use addCustomDataProperty for custom data properties");
 309
 310   // The object must not contain a property named |id|. The object must be
 311   // extensible, but allow private fields and sparsifying dense elements.
 312   MOZ_ASSERT(!id.isVoid());
 313   MOZ_ASSERT(!obj->containsPure(id));
 314   MOZ_ASSERT_IF(!id.isPrivateName(),
 315                 obj->isExtensible() ||
 316                     (id.isInt() && obj->containsDenseElement(id.toInt())) ||
 317                     // R&T wrappers are non-extensible, but we still want to be
 318                     // able to lazily resolve their properties. We can
 319                     // special-case them to allow doing so.
 320                     IF_RECORD_TUPLE(IsExtendedPrimitiveWrapper(*obj), false));
 321
 322   if (!Watchtower::watchPropertyAdd(cx, obj, id)) {
 323     return false;
 324   }
 325
 326   if (!maybeConvertToDictionaryForAdd(cx, obj)) {
 327     return false;
 328   }
 329
 330   if (auto* shape = LookupShapeForAdd(obj->shape(), id, flags, slot)) {
 331     return obj->setShapeAndAddNewSlot(cx, shape, *slot);
 332   }
 333
 334   if (obj->inDictionaryMode()) {
 335     // First generate a new dictionary shape so that the map and shape can be
 336     // mutated without having to worry about OOM conditions.
 337     if (!NativeObject::generateNewDictionaryShape(cx, obj)) {
 338       return false;
 339     }
 340     if (!allocDictionarySlot(cx, obj, slot)) {
 341       return false;
 342     }
 343
 344     ObjectFlags objectFlags = obj->shape()->objectFlags();
 345     const JSClass* clasp = obj->shape()->getObjectClass();
 346
 347     Rooted<DictionaryPropMap*> map(cx, obj->shape()->propMap()->asDictionary());
 348     uint32_t mapLength = obj->shape()->propMapLength();
 349     if (!DictionaryPropMap::addProperty(cx, clasp, &map, &mapLength, id, flags,
 350                                         *slot, &objectFlags)) {
 351       return false;
 352     }
 353
 354     obj->dictionaryShape()->updateNewShape(objectFlags, map, mapLength);
 355     return true;
 356   }
 357
 358   ObjectFlags objectFlags = obj->shape()->objectFlags();
 359   const JSClass* clasp = obj->shape()->getObjectClass();
 360
 361   Rooted<SharedPropMap*> map(cx, obj->sharedShape()->propMap());
 362   uint32_t mapLength = obj->shape()->propMapLength();
 363
 364   if (!SharedPropMap::addProperty(cx, clasp, &map, &mapLength, id, flags,
 365                                   &objectFlags, slot)) {
 366     return false;
 367   }
 368
 369   bool allocatedNewShape;
 370   SharedShape* newShape = SharedShape::getPropMapShape(
 371       cx, obj->shape()->base(), obj->shape()->numFixedSlots(), map, mapLength,
 372       objectFlags, &allocatedNewShape);
 373   if (!newShape) {
 374     return false;
 375   }
 376
 377   Shape* oldShape = obj->shape();
 378   if (!obj->setShapeAndAddNewSlot(cx, newShape, *slot)) {
 379     return false;
 380   }
 381
 382   // Add the new shape to the old shape's shape cache, to optimize this shape
 383   // transition. Don't do this if we just allocated a new shape, because that
 384   // suggests this may not be a hot transition that would benefit from the
 385   // cache.
 386
 387   if (allocatedNewShape) {
 388     return true;
 389   }
 390
 391   if (!RegisterShapeCache(cx, oldShape)) {
 392     // Ignore OOM, the cache is just an optimization.
 393     return true;
 394   }
 395
 396   ShapeCachePtr& cache = oldShape->cacheRef();
 397   if (!cache.isForAdd()) {
 398     cache.setSingleShapeForAdd(newShape);
 399   } else if (cache.isSingleShapeForAdd()) {
 400     SharedShape* prevShape = cache.toSingleShapeForAdd();
 401     if (ShapeSetForAdd* set = MakeShapeSetForAdd(prevShape, newShape)) {
 402       cache.setShapeSetForAdd(set);
 403       AddCellMemory(oldShape, sizeof(ShapeSetForAdd),
 404                     MemoryUse::ShapeSetForAdd);
 405     }
 406   } else {
 407     ShapeForAddHasher::Lookup lookup(id, flags);
 408     (void)cache.toShapeSetForAdd()->putNew(lookup, newShape);
 409   }
 410
 411   return true;
 412 }
 413
 414 void Shape::maybeCacheIterator(JSContext* cx, PropertyIteratorObject* iter) {
 415   if (!cache().isNone() && !cache().isIterator()) {
 416     // If we're already caching other shape data, skip caching the iterator.
 417     return;
 418   }
 419   if (MOZ_UNLIKELY(!RegisterShapeCache(cx, this))) {
 420     // Ignore OOM. The cache is just an optimization.
 421     return;
 422   }
 423   cacheRef().setIterator(iter);
 424 }
 425
 426 /* static */
 427 bool NativeObject::addPropertyInReservedSlot(JSContext* cx,
 428                                              Handle<NativeObject*> obj,
 429                                              HandleId id, uint32_t slot,
 430                                              PropertyFlags flags) {
 431   AutoCheckShapeConsistency check(obj);
 432   MOZ_ASSERT(!flags.isCustomDataProperty(),
 433              "Use addCustomDataProperty for custom data properties");
 434
 435   // The slot must be a reserved slot.
 436   MOZ_ASSERT(slot < JSCLASS_RESERVED_SLOTS(obj->getClass()));
 437
 438   // The object must not contain a property named |id| and must be extensible.
 439   MOZ_ASSERT(!id.isVoid());
 440   MOZ_ASSERT(!obj->containsPure(id));
 441   MOZ_ASSERT(!id.isPrivateName());
 442   MOZ_ASSERT(obj->isExtensible());
 443
 444   // The object must not be in dictionary mode. This simplifies the code below.
 445   MOZ_ASSERT(!obj->inDictionaryMode());
 446
 447   // We don't need to call Watchtower::watchPropertyAdd here because this isn't
 448   // used for any watched objects.
 449   MOZ_ASSERT(!Watchtower::watchesPropertyAdd(obj));
 450
 451   ObjectFlags objectFlags = obj->shape()->objectFlags();
 452   const JSClass* clasp = obj->shape()->getObjectClass();
 453
 454   Rooted<SharedPropMap*> map(cx, obj->sharedShape()->propMap());
 455   uint32_t mapLength = obj->shape()->propMapLength();
 456   if (!SharedPropMap::addPropertyInReservedSlot(cx, clasp, &map, &mapLength, id,
 457                                                 flags, slot, &objectFlags)) {
 458     return false;
 459   }
 460
 461   Shape* shape = SharedShape::getPropMapShape(cx, obj->shape()->base(),
 462                                               obj->shape()->numFixedSlots(),
 463                                               map, mapLength, objectFlags);
 464   if (!shape) {
 465     return false;
 466   }
 467   obj->setShape(shape);
 468
 469   MOZ_ASSERT(obj->getLastProperty().slot() == slot);
 470   return true;
 471 }
 472
 473 /*
 474  * Assert some invariants that should hold when changing properties. It's the
 475  * responsibility of the callers to ensure these hold.
 476  */
 477 static void AssertCanChangeFlags(PropertyInfo prop, PropertyFlags flags) {
 478 #ifdef DEBUG
 479   if (prop.configurable()) {
 480     return;
 481   }
 482
 483   // A non-configurable property must stay non-configurable.
 484   MOZ_ASSERT(!flags.configurable());
 485
 486   // Reject attempts to turn a non-configurable data property into an accessor
 487   // or custom data property.
 488   MOZ_ASSERT_IF(prop.isDataProperty(), flags.isDataProperty());
 489
 490   // Reject attempts to turn a non-configurable accessor property into a data
 491   // property or custom data property.
 492   MOZ_ASSERT_IF(prop.isAccessorProperty(), flags.isAccessorProperty());
 493 #endif
 494 }
 495
 496 static void AssertValidArrayIndex(NativeObject* obj, jsid id) {
 497 #ifdef DEBUG
 498   if (obj->is<ArrayObject>()) {
 499     ArrayObject* arr = &obj->as<ArrayObject>();
 500     uint32_t index;
 501     if (IdIsIndex(id, &index)) {
 502       MOZ_ASSERT(index < arr->length() || arr->lengthIsWritable());
 503     }
 504   }
 505 #endif
 506 }
 507
 508 /* static */
 509 bool NativeObject::changeProperty(JSContext* cx, Handle<NativeObject*> obj,
 510                                   HandleId id, PropertyFlags flags,
 511                                   uint32_t* slotOut) {
 512   MOZ_ASSERT(!id.isVoid());
 513
 514   AutoCheckShapeConsistency check(obj);
 515   AssertValidArrayIndex(obj, id);
 516   MOZ_ASSERT(!flags.isCustomDataProperty(),
 517              "Use changeCustomDataPropAttributes for custom data properties");
 518
 519   if (!Watchtower::watchPropertyChange(cx, obj, id, flags)) {
 520     return false;
 521   }
 522
 523   Rooted<PropMap*> map(cx, obj->shape()->propMap());
 524   uint32_t mapLength = obj->shape()->propMapLength();
 525
 526   uint32_t propIndex;
 527   Rooted<PropMap*> propMap(cx, map->lookup(cx, mapLength, id, &propIndex));
 528   MOZ_ASSERT(propMap);
 529
 530   ObjectFlags objectFlags = obj->shape()->objectFlags();
 531
 532   PropertyInfo oldProp = propMap->getPropertyInfo(propIndex);
 533   AssertCanChangeFlags(oldProp, flags);
 534
 535   if (oldProp.isAccessorProperty()) {
 536     objectFlags.setFlag(ObjectFlag::HadGetterSetterChange);
 537   }
 538
 539   // If the property flags are not changing, the only thing we have to do is
 540   // update the object flags. This prevents a dictionary mode conversion below.
 541   if (oldProp.flags() == flags) {
 542     *slotOut = oldProp.slot();
 543     if (objectFlags == obj->shape()->objectFlags()) {
 544       return true;
 545     }
 546     return Shape::replaceShape(cx, obj, objectFlags, obj->shape()->proto(),
 547                                obj->shape()->numFixedSlots());
 548   }
 549
 550   const JSClass* clasp = obj->shape()->getObjectClass();
 551
 552   if (map->isShared()) {
 553     // Fast path for changing the last property in a SharedPropMap. Call
 554     // getPrevious to "remove" the last property and then call addProperty
 555     // to re-add the last property with the new flags.
 556     if (propMap == map && propIndex == mapLength - 1) {
 557       MOZ_ASSERT(obj->getLastProperty().key() == id);
 558
 559       Rooted<SharedPropMap*> sharedMap(cx, map->asShared());
 560       SharedPropMap::getPrevious(&sharedMap, &mapLength);
 561
 562       if (MOZ_LIKELY(oldProp.hasSlot())) {
 563         *slotOut = oldProp.slot();
 564         if (!SharedPropMap::addPropertyWithKnownSlot(cx, clasp, &sharedMap,
 565                                                      &mapLength, id, flags,
 566                                                      *slotOut, &objectFlags)) {
 567           return false;
 568         }
 569       } else {
 570         if (!SharedPropMap::addProperty(cx, clasp, &sharedMap, &mapLength, id,
 571                                         flags, &objectFlags, slotOut)) {
 572           return false;
 573         }
 574       }
 575
 576       SharedShape* newShape = SharedShape::getPropMapShape(
 577           cx, obj->shape()->base(), obj->shape()->numFixedSlots(), sharedMap,
 578           mapLength, objectFlags);
 579       if (!newShape) {
 580         return false;
 581       }
 582
 583       if (MOZ_LIKELY(oldProp.hasSlot())) {
 584         MOZ_ASSERT(obj->sharedShape()->slotSpan() == newShape->slotSpan());
 585         obj->setShape(newShape);
 586         return true;
 587       }
 588       return obj->setShapeAndAddNewSlot(cx, newShape, *slotOut);
 589     }
 590
 591     // Changing a non-last property. Switch to dictionary mode and relookup
 592     // pointers for the new dictionary map.
 593     if (!NativeObject::toDictionaryMode(cx, obj)) {
 594       return false;
 595     }
 596     map = obj->shape()->propMap();
 597     propMap = map->lookup(cx, mapLength, id, &propIndex);
 598     MOZ_ASSERT(propMap);
 599   } else {
 600     if (!NativeObject::generateNewDictionaryShape(cx, obj)) {
 601       return false;
 602     }
 603   }
 604
 605   // The object has a new dictionary shape (see toDictionaryMode and
 606   // generateNewDictionaryShape calls above), so we can mutate the map and shape
 607   // in place.
 608
 609   MOZ_ASSERT(map->isDictionary());
 610   MOZ_ASSERT(propMap->isDictionary());
 611
 612   uint32_t slot = oldProp.hasSlot() ? oldProp.slot() : SHAPE_INVALID_SLOT;
 613   if (slot == SHAPE_INVALID_SLOT) {
 614     if (!allocDictionarySlot(cx, obj, &slot)) {
 615       return false;
 616     }
 617   }
 618
 619   propMap->asDictionary()->changeProperty(cx, clasp, propIndex, flags, slot,
 620                                           &objectFlags);
 621   obj->dictionaryShape()->setObjectFlagsOfNewShape(objectFlags);
 622
 623   *slotOut = slot;
 624   return true;
 625 }
 626
 627 /* static */
 628 bool NativeObject::changeCustomDataPropAttributes(JSContext* cx,
 629                                                   Handle<NativeObject*> obj,
 630                                                   HandleId id,
 631                                                   PropertyFlags flags) {
 632   MOZ_ASSERT(!id.isVoid());
 633
 634   AutoCheckShapeConsistency check(obj);
 635   AssertValidArrayIndex(obj, id);
 636   AssertValidCustomDataProp(obj, flags);
 637
 638   if (!Watchtower::watchPropertyChange(cx, obj, id, flags)) {
 639     return false;
 640   }
 641
 642   Rooted<PropMap*> map(cx, obj->shape()->propMap());
 643   uint32_t mapLength = obj->shape()->propMapLength();
 644
 645   uint32_t propIndex;
 646   Rooted<PropMap*> propMap(cx, map->lookup(cx, mapLength, id, &propIndex));
 647   MOZ_ASSERT(propMap);
 648
 649   PropertyInfo oldProp = propMap->getPropertyInfo(propIndex);
 650   MOZ_ASSERT(oldProp.isCustomDataProperty());
 651   AssertCanChangeFlags(oldProp, flags);
 652
 653   // If the property flags are not changing, we're done.
 654   if (oldProp.flags() == flags) {
 655     return true;
 656   }
 657
 658   const JSClass* clasp = obj->shape()->getObjectClass();
 659   ObjectFlags objectFlags = obj->shape()->objectFlags();
 660
 661   if (map->isShared()) {
 662     // Fast path for changing the last property in a SharedPropMap. Call
 663     // getPrevious to "remove" the last property and then call
 664     // addCustomDataProperty to re-add the last property with the new flags.
 665     if (propMap == map && propIndex == mapLength - 1) {
 666       MOZ_ASSERT(obj->getLastProperty().key() == id);
 667
 668       Rooted<SharedPropMap*> sharedMap(cx, map->asShared());
 669       SharedPropMap::getPrevious(&sharedMap, &mapLength);
 670
 671       if (!SharedPropMap::addCustomDataProperty(
 672               cx, clasp, &sharedMap, &mapLength, id, flags, &objectFlags)) {
 673         return false;
 674       }
 675
 676       Shape* newShape = SharedShape::getPropMapShape(
 677           cx, obj->shape()->base(), obj->shape()->numFixedSlots(), sharedMap,
 678           mapLength, objectFlags);
 679       if (!newShape) {
 680         return false;
 681       }
 682       obj->setShape(newShape);
 683       return true;
 684     }
 685
 686     // Changing a non-last property. Switch to dictionary mode and relookup
 687     // pointers for the new dictionary map.
 688     if (!NativeObject::toDictionaryMode(cx, obj)) {
 689       return false;
 690     }
 691     map = obj->shape()->propMap();
 692     propMap = map->lookup(cx, mapLength, id, &propIndex);
 693     MOZ_ASSERT(propMap);
 694   } else {
 695     if (!NativeObject::generateNewDictionaryShape(cx, obj)) {
 696       return false;
 697     }
 698   }
 699
 700   // The object has a new dictionary shape (see toDictionaryMode and
 701   // generateNewDictionaryShape calls above), so we can mutate the map and shape
 702   // in place.
 703
 704   MOZ_ASSERT(map->isDictionary());
 705   MOZ_ASSERT(propMap->isDictionary());
 706
 707   propMap->asDictionary()->changePropertyFlags(cx, clasp, propIndex, flags,
 708                                                &objectFlags);
 709   obj->dictionaryShape()->setObjectFlagsOfNewShape(objectFlags);
 710   return true;
 711 }
 712
 713 void NativeObject::maybeFreeDictionaryPropSlots(JSContext* cx,
 714                                                 DictionaryPropMap* map,
 715                                                 uint32_t mapLength) {
 716   // We can free all non-reserved slots if there are no properties left. We also
 717   // handle the case where there's a single slotless property, to support arrays
 718   // (array.length is a custom data property).
 719
 720   MOZ_ASSERT(dictionaryShape()->propMap() == map);
 721   MOZ_ASSERT(shape()->propMapLength() == mapLength);
 722
 723   if (mapLength > 1 || map->previous()) {
 724     return;
 725   }
 726   if (mapLength == 1 && map->getPropertyInfo(0).hasSlot()) {
 727     return;
 728   }
 729
 730   uint32_t oldSpan = dictionaryModeSlotSpan();
 731   uint32_t newSpan = JSCLASS_RESERVED_SLOTS(getClass());
 732   if (oldSpan == newSpan) {
 733     return;
 734   }
 735
 736   MOZ_ASSERT(newSpan < oldSpan);
 737
 738   // Trigger write barriers on the old slots before reallocating.
 739   prepareSlotRangeForOverwrite(newSpan, oldSpan);
 740   invalidateSlotRange(newSpan, oldSpan);
 741
 742   uint32_t oldCapacity = numDynamicSlots();
 743   uint32_t newCapacity =
 744       calculateDynamicSlots(numFixedSlots(), newSpan, getClass());
 745   if (newCapacity < oldCapacity) {
 746     shrinkSlots(cx, oldCapacity, newCapacity);
 747   }
 748
 749   setDictionaryModeSlotSpan(newSpan);
 750   map->setFreeList(SHAPE_INVALID_SLOT);
 751 }
 752
 753 void NativeObject::setShapeAndRemoveLastSlot(JSContext* cx,
 754                                              SharedShape* newShape,
 755                                              uint32_t slot) {
 756   MOZ_ASSERT(!inDictionaryMode());
 757   MOZ_ASSERT(newShape->isShared());
 758   MOZ_ASSERT(newShape->slotSpan() == slot);
 759
 760   uint32_t numFixed = newShape->numFixedSlots();
 761   if (slot < numFixed) {
 762     setFixedSlot(slot, UndefinedValue());
 763   } else {
 764     setDynamicSlot(numFixed, slot, UndefinedValue());
 765     uint32_t oldCapacity = numDynamicSlots();
 766     uint32_t newCapacity = calculateDynamicSlots(numFixed, slot, getClass());
 767     MOZ_ASSERT(newCapacity <= oldCapacity);
 768     if (newCapacity < oldCapacity) {
 769       shrinkSlots(cx, oldCapacity, newCapacity);
 770     }
 771   }
 772
 773   setShape(newShape);
 774 }
 775
 776 /* static */
 777 bool NativeObject::removeProperty(JSContext* cx, Handle<NativeObject*> obj,
 778                                   HandleId id) {
 779   AutoCheckShapeConsistency check(obj);
 780
 781   Rooted<PropMap*> map(cx, obj->shape()->propMap());
 782   uint32_t mapLength = obj->shape()->propMapLength();
 783
 784   AutoKeepPropMapTables keep(cx);
 785   PropMapTable* table;
 786   PropMapTable::Ptr ptr;
 787   Rooted<PropMap*> propMap(cx);
 788   uint32_t propIndex;
 789   if (!PropMap::lookupForRemove(cx, map, mapLength, id, keep, propMap.address(),
 790                                 &propIndex, &table, &ptr)) {
 791     return false;
 792   }
 793
 794   if (!propMap) {
 795     return true;
 796   }
 797
 798   if (!Watchtower::watchPropertyRemove(cx, obj, id)) {
 799     return false;
 800   }
 801
 802   PropertyInfo prop = propMap->getPropertyInfo(propIndex);
 803
 804   // If we're removing an accessor property, ensure the HadGetterSetterChange
 805   // object flag is set. This is necessary because the slot holding the
 806   // GetterSetter can be changed indirectly by removing the property and then
 807   // adding it back with a different GetterSetter value but the same shape.
 808   if (prop.isAccessorProperty() && !obj->hadGetterSetterChange()) {
 809     if (!NativeObject::setHadGetterSetterChange(cx, obj)) {
 810       return false;
 811     }
 812   }
 813
 814   if (map->isShared()) {
 815     // Fast path for removing the last property from a SharedPropMap. In this
 816     // case we can just call getPrevious and then look up a shape for the
 817     // resulting map/mapLength.
 818     if (propMap == map && propIndex == mapLength - 1) {
 819       MOZ_ASSERT(obj->getLastProperty().key() == id);
 820
 821       Rooted<SharedPropMap*> sharedMap(cx, map->asShared());
 822       SharedPropMap::getPrevious(&sharedMap, &mapLength);
 823
 824       SharedShape* shape = obj->sharedShape();
 825       SharedShape* newShape;
 826       if (sharedMap) {
 827         newShape = SharedShape::getPropMapShape(
 828             cx, shape->base(), shape->numFixedSlots(), sharedMap, mapLength,
 829             shape->objectFlags());
 830       } else {
 831         newShape = SharedShape::getInitialShape(
 832             cx, shape->getObjectClass(), shape->realm(), shape->proto(),
 833             shape->numFixedSlots(), shape->objectFlags());
 834       }
 835       if (!newShape) {
 836         return false;
 837       }
 838
 839       if (MOZ_LIKELY(prop.hasSlot())) {
 840         if (MOZ_LIKELY(prop.slot() == newShape->slotSpan())) {
 841           obj->setShapeAndRemoveLastSlot(cx, newShape, prop.slot());
 842           return true;
 843         }
 844         // Uncommon case: the property is stored in a reserved slot.
 845         // See NativeObject::addPropertyInReservedSlot.
 846         MOZ_ASSERT(prop.slot() < JSCLASS_RESERVED_SLOTS(obj->getClass()));
 847         obj->setSlot(prop.slot(), UndefinedValue());
 848       }
 849       obj->setShape(newShape);
 850       return true;
 851     }
 852
 853     // Removing a non-last property. Switch to dictionary mode and relookup
 854     // pointers for the new dictionary map.
 855     if (!NativeObject::toDictionaryMode(cx, obj)) {
 856       return false;
 857     }
 858     map = obj->shape()->propMap();
 859     if (!PropMap::lookupForRemove(cx, map, mapLength, id, keep,
 860                                   propMap.address(), &propIndex, &table,
 861                                   &ptr)) {
 862       return false;
 863     }
 864   } else {
 865     if (!NativeObject::generateNewDictionaryShape(cx, obj)) {
 866       return false;
 867     }
 868   }
 869
 870   // The object has a new dictionary shape (see toDictionaryMode and
 871   // generateNewDictionaryShape calls above), so we can mutate the map and shape
 872   // in place.
 873
 874   MOZ_ASSERT(map->isDictionary());
 875   MOZ_ASSERT(table);
 876   MOZ_ASSERT(prop == ptr->propertyInfo());
 877
 878   Rooted<DictionaryPropMap*> dictMap(cx, map->asDictionary());
 879
 880   // If the property has a slot, free its slot number.
 881   if (prop.hasSlot()) {
 882     obj->freeDictionarySlot(prop.slot());
 883   }
 884
 885   DictionaryPropMap::removeProperty(cx, &dictMap, &mapLength, table, ptr);
 886
 887   obj->dictionaryShape()->updateNewShape(obj->shape()->objectFlags(), dictMap,
 888                                          mapLength);
 889
 890   // If we just deleted the last property, consider shrinking the slots. We only
 891   // do this if there are a lot of slots, to avoid allocating/freeing dynamic
 892   // slots repeatedly.
 893   static constexpr size_t MinSlotSpanForFree = 64;
 894   if (obj->dictionaryModeSlotSpan() >= MinSlotSpanForFree) {
 895     obj->maybeFreeDictionaryPropSlots(cx, dictMap, mapLength);
 896   }
 897
 898   return true;
 899 }
 900
 901 /* static */
 902 bool NativeObject::densifySparseElements(JSContext* cx,
 903                                          Handle<NativeObject*> obj) {
 904   AutoCheckShapeConsistency check(obj);
 905   MOZ_ASSERT(obj->inDictionaryMode());
 906
 907   // First generate a new dictionary shape so that the shape and map can then
 908   // be updated infallibly.
 909   if (!NativeObject::generateNewDictionaryShape(cx, obj)) {
 910     return false;
 911   }
 912
 913   Rooted<DictionaryPropMap*> map(cx, obj->shape()->propMap()->asDictionary());
 914   uint32_t mapLength = obj->shape()->propMapLength();
 915
 916   DictionaryPropMap::densifyElements(cx, &map, &mapLength, obj);
 917
 918   // All indexed properties on the object are now dense. Clear the indexed
 919   // flag so that we will not start using sparse indexes again if we need
 920   // to grow the object.
 921   ObjectFlags objectFlags = obj->shape()->objectFlags();
 922   objectFlags.clearFlag(ObjectFlag::Indexed);
 923
 924   obj->dictionaryShape()->updateNewShape(objectFlags, map, mapLength);
 925
 926   obj->maybeFreeDictionaryPropSlots(cx, map, mapLength);
 927
 928   return true;
 929 }
 930
 931 // static
 932 bool NativeObject::freezeOrSealProperties(JSContext* cx,
 933                                           Handle<NativeObject*> obj,
 934                                           IntegrityLevel level) {
 935   AutoCheckShapeConsistency check(obj);
 936
 937   if (!Watchtower::watchFreezeOrSeal(cx, obj)) {
 938     return false;
 939   }
 940
 941   uint32_t mapLength = obj->shape()->propMapLength();
 942   MOZ_ASSERT(mapLength > 0);
 943
 944   const JSClass* clasp = obj->shape()->getObjectClass();
 945   ObjectFlags objectFlags = obj->shape()->objectFlags();
 946
 947   if (obj->inDictionaryMode()) {
 948     // First generate a new dictionary shape so that the map and shape can be
 949     // updated infallibly.
 950     if (!generateNewDictionaryShape(cx, obj)) {
 951       return false;
 952     }
 953     DictionaryPropMap* map = obj->dictionaryShape()->propMap();
 954     map->freezeOrSealProperties(cx, level, clasp, mapLength, &objectFlags);
 955     obj->dictionaryShape()->updateNewShape(objectFlags, map, mapLength);
 956     return true;
 957   }
 958
 959   Rooted<SharedPropMap*> map(cx, obj->sharedShape()->propMap());
 960   if (!SharedPropMap::freezeOrSealProperties(cx, level, clasp, &map, mapLength,
 961                                              &objectFlags)) {
 962     return false;
 963   }
 964
 965   SharedShape* newShape = SharedShape::getPropMapShape(
 966       cx, obj->shape()->base(), obj->numFixedSlots(), map, mapLength,
 967       objectFlags);
 968   if (!newShape) {
 969     return false;
 970   }
 971   MOZ_ASSERT(obj->sharedShape()->slotSpan() == newShape->slotSpan());
 972
 973   obj->setShape(newShape);
 974   return true;
 975 }
 976
 977 /* static */
 978 bool NativeObject::generateNewDictionaryShape(JSContext* cx,
 979                                               Handle<NativeObject*> obj) {
 980   // Clone the current dictionary shape to a new shape. This ensures ICs and
 981   // other shape guards are properly invalidated before we start mutating the
 982   // map or new shape.
 983
 984   MOZ_ASSERT(obj->inDictionaryMode());
 985
 986   Shape* shape = DictionaryShape::new_(cx, obj);
 987   if (!shape) {
 988     return false;
 989   }
 990
 991   obj->setShape(shape);
 992   return true;
 993 }
 994
 995 /* static */
 996 bool JSObject::setFlag(JSContext* cx, HandleObject obj, ObjectFlag flag) {
 997   MOZ_ASSERT(cx->compartment() == obj->compartment());
 998
 999   if (obj->hasFlag(flag)) {
1000     return true;
1001   }
1002
1003   ObjectFlags objectFlags = obj->shape()->objectFlags();
1004   objectFlags.setFlag(flag);
1005
1006   uint32_t numFixed =
1007       obj->is<NativeObject>() ? obj->as<NativeObject>().numFixedSlots() : 0;
1008   return Shape::replaceShape(cx, obj, objectFlags, obj->shape()->proto(),
1009                              numFixed);
1010 }
1011
1012 static bool SetObjectIsUsedAsPrototype(JSContext* cx, Handle<JSObject*> proto) {
1013   MOZ_ASSERT(!proto->isUsedAsPrototype());
1014
1015   // Ensure the proto object has a unique id to prevent OOM crashes below.
1016   uint64_t unused;
1017   if (!gc::GetOrCreateUniqueId(proto, &unused)) {
1018     ReportOutOfMemory(cx);
1019     return false;
1020   }
1021
1022   return JSObject::setIsUsedAsPrototype(cx, proto);
1023 }
1024
1025 /* static */
1026 bool JSObject::setProtoUnchecked(JSContext* cx, HandleObject obj,
1027                                  Handle<TaggedProto> proto) {
1028   MOZ_ASSERT(cx->compartment() == obj->compartment());
1029   MOZ_ASSERT(!obj->staticPrototypeIsImmutable());
1030   MOZ_ASSERT_IF(!obj->is<ProxyObject>(), obj->nonProxyIsExtensible());
1031   MOZ_ASSERT(obj->shape()->proto() != proto);
1032
1033   // Notify Watchtower of this proto change, so it can properly invalidate shape
1034   // teleporting and other optimizations.
1035   if (!Watchtower::watchProtoChange(cx, obj)) {
1036     return false;
1037   }
1038
1039   if (proto.isObject() && !proto.toObject()->isUsedAsPrototype()) {
1040     RootedObject protoObj(cx, proto.toObject());
1041     if (!SetObjectIsUsedAsPrototype(cx, protoObj)) {
1042       return false;
1043     }
1044   }
1045
1046   uint32_t numFixed =
1047       obj->is<NativeObject>() ? obj->as<NativeObject>().numFixedSlots() : 0;
1048   return Shape::replaceShape(cx, obj, obj->shape()->objectFlags(), proto,
1049                              numFixed);
1050 }
1051
1052 /* static */
1053 bool NativeObject::changeNumFixedSlotsAfterSwap(JSContext* cx,
1054                                                 Handle<NativeObject*> obj,
1055                                                 uint32_t nfixed) {
1056   MOZ_ASSERT(nfixed != obj->shape()->numFixedSlots());
1057
1058   return Shape::replaceShape(cx, obj, obj->shape()->objectFlags(),
1059                              obj->shape()->proto(), nfixed);
1060 }
1061
1062 BaseShape::BaseShape(JSContext* cx, const JSClass* clasp, JS::Realm* realm,
1063                      TaggedProto proto)
1064     : TenuredCellWithNonGCPointer(clasp), realm_(realm), proto_(proto) {
1065 #ifdef DEBUG
1066   AssertJSClassInvariants(clasp);
1067 #endif
1068
1069   MOZ_ASSERT_IF(proto.isObject(),
1070                 compartment() == proto.toObject()->compartment());
1071   MOZ_ASSERT_IF(proto.isObject(), proto.toObject()->isUsedAsPrototype());
1072
1073   // Windows may not appear on prototype chains.
1074   MOZ_ASSERT_IF(proto.isObject(), !IsWindow(proto.toObject()));
1075
1076   if (MOZ_UNLIKELY(clasp->emulatesUndefined())) {
1077     cx->runtime()->hasSeenObjectEmulateUndefinedFuse.ref().popFuse(cx);
1078   }
1079
1080 #ifdef DEBUG
1081   if (GlobalObject* global = realm->unsafeUnbarrieredMaybeGlobal()) {
1082     AssertTargetIsNotGray(global);
1083   }
1084 #endif
1085 }
1086
1087 /* static */
1088 BaseShape* BaseShape::get(JSContext* cx, const JSClass* clasp, JS::Realm* realm,
1089                           Handle<TaggedProto> proto) {
1090   auto& table = cx->zone()->shapeZone().baseShapes;
1091
1092   using Lookup = BaseShapeHasher::Lookup;
1093
1094   auto p = MakeDependentAddPtr(cx, table, Lookup(clasp, realm, proto));
1095   if (p) {
1096     return *p;
1097   }
1098
1099   BaseShape* nbase = cx->newCell<BaseShape>(cx, clasp, realm, proto);
1100   if (!nbase) {
1101     return nullptr;
1102   }
1103
1104   if (!p.add(cx, table, Lookup(clasp, realm, proto), nbase)) {
1105     return nullptr;
1106   }
1107
1108   return nbase;
1109 }
1110
1111 // static
1112 SharedShape* SharedShape::new_(JSContext* cx, Handle<BaseShape*> base,
1113                                ObjectFlags objectFlags, uint32_t nfixed,
1114                                Handle<SharedPropMap*> map, uint32_t mapLength) {
1115   return cx->newCell<SharedShape>(base, objectFlags, nfixed, map, mapLength);
1116 }
1117
1118 // static
1119 DictionaryShape* DictionaryShape::new_(JSContext* cx, Handle<BaseShape*> base,
1120                                        ObjectFlags objectFlags, uint32_t nfixed,
1121                                        Handle<DictionaryPropMap*> map,
1122                                        uint32_t mapLength) {
1123   return cx->newCell<DictionaryShape>(base, objectFlags, nfixed, map,
1124                                       mapLength);
1125 }
1126
1127 DictionaryShape::DictionaryShape(NativeObject* nobj)
1128     : DictionaryShape(nobj->shape()->base(), nobj->shape()->objectFlags(),
1129                       nobj->shape()->numFixedSlots(),
1130                       nobj->dictionaryShape()->propMap(),
1131                       nobj->shape()->propMapLength()) {}
1132
1133 // static
1134 DictionaryShape* DictionaryShape::new_(JSContext* cx,
1135                                        Handle<NativeObject*> obj) {
1136   return cx->newCell<DictionaryShape>(obj);
1137 }
1138
1139 // static
1140 ProxyShape* ProxyShape::new_(JSContext* cx, Handle<BaseShape*> base,
1141                              ObjectFlags objectFlags) {
1142   return cx->newCell<ProxyShape>(base, objectFlags);
1143 }
1144
1145 // static
1146 WasmGCShape* WasmGCShape::new_(JSContext* cx, Handle<BaseShape*> base,
1147                                const wasm::RecGroup* recGroup,
1148                                ObjectFlags objectFlags) {
1149   WasmGCShape* shape = cx->newCell<WasmGCShape>(base, recGroup, objectFlags);
1150   if (shape) {
1151     shape->init();
1152   }
1153   return shape;
1154 }
1155
1156 MOZ_ALWAYS_INLINE HashNumber ShapeForAddHasher::hash(const Lookup& l) {
1157   HashNumber hash = HashPropertyKey(l.key);
1158   return mozilla::AddToHash(hash, l.flags.toRaw());
1159 }
1160
1161 MOZ_ALWAYS_INLINE bool ShapeForAddHasher::match(SharedShape* shape,
1162                                                 const Lookup& l) {
1163   uint32_t slot;
1164   return shape->lastPropertyMatchesForAdd(l.key, l.flags, &slot);
1165 }
1166
1167 #if defined(DEBUG) || defined(JS_JITSPEW)
1168 void BaseShape::dump() const {
1169   Fprinter out(stderr);
1170   dump(out);
1171 }
1172
1173 void BaseShape::dump(js::GenericPrinter& out) const {
1174   js::JSONPrinter json(out);
1175   dump(json);
1176   out.put("\n");
1177 }
1178
1179 void BaseShape::dump(js::JSONPrinter& json) const {
1180   json.beginObject();
1181   dumpFields(json);
1182   json.endObject();
1183 }
1184
1185 void BaseShape::dumpFields(js::JSONPrinter& json) const {
1186   json.formatProperty("address", "(js::BaseShape*)0x%p", this);
1187
1188   json.formatProperty("realm", "(JS::Realm*)0x%p", realm());
1189
1190   if (proto().isDynamic()) {
1191     json.property("proto", "<dynamic>");
1192   } else {
1193     JSObject* protoObj = proto().toObjectOrNull();
1194     if (protoObj) {
1195       json.formatProperty("proto", "(JSObject*)0x%p", protoObj);
1196     } else {
1197       json.nullProperty("proto");
1198     }
1199   }
1200 }
1201
1202 void Shape::dump() const {
1203   Fprinter out(stderr);
1204   dump(out);
1205 }
1206
1207 void Shape::dump(js::GenericPrinter& out) const {
1208   js::JSONPrinter json(out);
1209   dump(json);
1210   out.put("\n");
1211 }
1212
1213 void Shape::dump(js::JSONPrinter& json) const {
1214   json.beginObject();
1215   dumpFields(json);
1216   json.endObject();
1217 }
1218
1219 template <typename KnownF, typename UnknownF>
1220 void ForEachObjectFlag(ObjectFlags flags, KnownF known, UnknownF unknown) {
1221   uint16_t raw = flags.toRaw();
1222   for (uint16_t i = 1; i; i = i << 1) {
1223     if (!(raw & i)) {
1224       continue;
1225     }
1226     switch (ObjectFlag(raw & i)) {
1227       case ObjectFlag::IsUsedAsPrototype:
1228         known("IsUsedAsPrototype");
1229         break;
1230       case ObjectFlag::NotExtensible:
1231         known("NotExtensible");
1232         break;
1233       case ObjectFlag::Indexed:
1234         known("Indexed");
1235         break;
1236       case ObjectFlag::HasInterestingSymbol:
1237         known("HasInterestingSymbol");
1238         break;
1239       case ObjectFlag::HasEnumerable:
1240         known("HasEnumerable");
1241         break;
1242       case ObjectFlag::FrozenElements:
1243         known("FrozenElements");
1244         break;
1245       case ObjectFlag::InvalidatedTeleporting:
1246         known("InvalidatedTeleporting");
1247         break;
1248       case ObjectFlag::ImmutablePrototype:
1249         known("ImmutablePrototype");
1250         break;
1251       case ObjectFlag::QualifiedVarObj:
1252         known("QualifiedVarObj");
1253         break;
1254       case ObjectFlag::HasNonWritableOrAccessorPropExclProto:
1255         known("HasNonWritableOrAccessorPropExclProto");
1256         break;
1257       case ObjectFlag::HadGetterSetterChange:
1258         known("HadGetterSetterChange");
1259         break;
1260       case ObjectFlag::UseWatchtowerTestingLog:
1261         known("UseWatchtowerTestingLog");
1262         break;
1263       case ObjectFlag::GenerationCountedGlobal:
1264         known("GenerationCountedGlobal");
1265         break;
1266       case ObjectFlag::NeedsProxyGetSetResultValidation:
1267         known("NeedsProxyGetSetResultValidation");
1268         break;
1269       case ObjectFlag::HasFuseProperty:
1270         known("HasFuseProperty");
1271         break;
1272       default:
1273         unknown(i);
1274         break;
1275     }
1276   }
1277 }
1278
1279 void Shape::dumpFields(js::JSONPrinter& json) const {
1280   json.formatProperty("address", "(js::Shape*)0x%p", this);
1281
1282   json.beginObjectProperty("base");
1283   base()->dumpFields(json);
1284   json.endObject();
1285
1286   switch (kind()) {
1287     case Kind::Shared:
1288       json.property("kind", "Shared");
1289       break;
1290     case Kind::Dictionary:
1291       json.property("kind", "Dictionary");
1292       break;
1293     case Kind::Proxy:
1294       json.property("kind", "Proxy");
1295       break;
1296     case Kind::WasmGC:
1297       json.property("kind", "WasmGC");
1298       break;
1299   }
1300
1301   json.beginInlineListProperty("objectFlags");
1302   ForEachObjectFlag(
1303       objectFlags(), [&](const char* name) { json.value("%s", name); },
1304       [&](uint16_t value) { json.value("Unknown(%04x)", value); });
1305   json.endInlineList();
1306
1307   if (isNative()) {
1308     json.property("numFixedSlots", asNative().numFixedSlots());
1309     json.property("propMapLength", asNative().propMapLength());
1310
1311     if (asNative().propMap()) {
1312       json.beginObjectProperty("propMap");
1313       asNative().propMap()->dumpFields(json);
1314       json.endObject();
1315     } else {
1316       json.nullProperty("propMap");
1317     }
1318   }
1319
1320   if (isShared()) {
1321     if (getObjectClass()->isNativeObject()) {
1322       json.property("slotSpan", asShared().slotSpan());
1323     }
1324   }
1325
1326   if (isWasmGC()) {
1327     json.formatProperty("recGroup", "(js::wasm::RecGroup*)0x%p",
1328                         asWasmGC().recGroup());
1329   }
1330 }
1331
1332 void Shape::dumpStringContent(js::GenericPrinter& out) const {
1333   out.printf("<(js::Shape*)0x%p", this);
1334
1335   if (isDictionary()) {
1336     out.put(", dictionary");
1337   }
1338
1339   out.put(", objectFlags=[");
1340   bool first = true;
1341   ForEachObjectFlag(
1342       objectFlags(),
1343       [&](const char* name) {
1344         if (!first) {
1345           out.put(", ");
1346         }
1347         first = false;
1348
1349         out.put(name);
1350       },
1351       [&](uint16_t value) {
1352         if (!first) {
1353           out.put(", ");
1354         }
1355         first = false;
1356
1357         out.printf("Unknown(%04x)", value);
1358       });
1359   out.put("]>");
1360 }
1361 #endif  // defined(DEBUG) || defined(JS_JITSPEW)
1362
1363 /* static */
1364 SharedShape* SharedShape::getInitialShape(JSContext* cx, const JSClass* clasp,
1365                                           JS::Realm* realm, TaggedProto proto,
1366                                           size_t nfixed,
1367                                           ObjectFlags objectFlags) {
1368   MOZ_ASSERT(cx->compartment() == realm->compartment());
1369   MOZ_ASSERT_IF(proto.isObject(),
1370                 cx->isInsideCurrentCompartment(proto.toObject()));
1371
1372   if (proto.isObject()) {
1373     if (proto.toObject()->isUsedAsPrototype()) {
1374       // Use the cache on the prototype's shape to get to the initial shape.
1375       // This cache has a hit rate of 80-90% on typical workloads and is faster
1376       // than the HashSet lookup below.
1377       JSObject* protoObj = proto.toObject();
1378       Shape* protoObjShape = protoObj->shape();
1379       if (protoObjShape->cache().isShapeWithProto()) {
1380         SharedShape* shape = protoObjShape->cache().toShapeWithProto();
1381         if (shape->numFixedSlots() == nfixed &&
1382             shape->objectFlags() == objectFlags &&
1383             shape->getObjectClass() == clasp && shape->realm() == realm &&
1384             shape->proto() == proto) {
1385 #ifdef DEBUG
1386           // Verify the table lookup below would have resulted in the same
1387           // shape.
1388           using Lookup = InitialShapeHasher::Lookup;
1389           Lookup lookup(clasp, realm, proto, nfixed, objectFlags);
1390           auto p = realm->zone()->shapeZone().initialShapes.lookup(lookup);
1391           MOZ_ASSERT(*p == shape);
1392 #endif
1393           return shape;
1394         }
1395       }
1396     } else {
1397       RootedObject protoObj(cx, proto.toObject());
1398       if (!SetObjectIsUsedAsPrototype(cx, protoObj)) {
1399         return nullptr;
1400       }
1401       proto = TaggedProto(protoObj);
1402     }
1403   }
1404
1405   auto& table = realm->zone()->shapeZone().initialShapes;
1406
1407   using Lookup = InitialShapeHasher::Lookup;
1408   auto ptr = MakeDependentAddPtr(
1409       cx, table, Lookup(clasp, realm, proto, nfixed, objectFlags));
1410   if (ptr) {
1411     // Cache the result of this lookup on the prototype's shape.
1412     if (proto.isObject()) {
1413       JSObject* protoObj = proto.toObject();
1414       Shape* protoShape = protoObj->shape();
1415       if (!protoShape->cache().isForAdd() &&
1416           RegisterShapeCache(cx, protoShape)) {
1417         protoShape->cacheRef().setShapeWithProto(*ptr);
1418       }
1419     }
1420     return *ptr;
1421   }
1422
1423   Rooted<TaggedProto> protoRoot(cx, proto);
1424   Rooted<BaseShape*> nbase(cx, BaseShape::get(cx, clasp, realm, protoRoot));
1425   if (!nbase) {
1426     return nullptr;
1427   }
1428
1429   Rooted<SharedShape*> shape(
1430       cx, SharedShape::new_(cx, nbase, objectFlags, nfixed, nullptr, 0));
1431   if (!shape) {
1432     return nullptr;
1433   }
1434
1435   Lookup lookup(clasp, realm, protoRoot, nfixed, objectFlags);
1436   if (!ptr.add(cx, table, lookup, shape)) {
1437     return nullptr;
1438   }
1439
1440   return shape;
1441 }
1442
1443 /* static */
1444 SharedShape* SharedShape::getInitialShape(JSContext* cx, const JSClass* clasp,
1445                                           JS::Realm* realm, TaggedProto proto,
1446                                           gc::AllocKind kind,
1447                                           ObjectFlags objectFlags) {
1448   return getInitialShape(cx, clasp, realm, proto, GetGCKindSlots(kind),
1449                          objectFlags);
1450 }
1451
1452 /* static */
1453 SharedShape* SharedShape::getPropMapShape(
1454     JSContext* cx, BaseShape* base, size_t nfixed, Handle<SharedPropMap*> map,
1455     uint32_t mapLength, ObjectFlags objectFlags, bool* allocatedNewShape) {
1456   MOZ_ASSERT(cx->compartment() == base->compartment());
1457   MOZ_ASSERT_IF(base->proto().isObject(),
1458                 cx->isInsideCurrentCompartment(base->proto().toObject()));
1459   MOZ_ASSERT_IF(base->proto().isObject(),
1460                 base->proto().toObject()->isUsedAsPrototype());
1461   MOZ_ASSERT(map);
1462   MOZ_ASSERT(mapLength > 0);
1463
1464   auto& table = cx->zone()->shapeZone().propMapShapes;
1465
1466   using Lookup = PropMapShapeHasher::Lookup;
1467   auto ptr = MakeDependentAddPtr(
1468       cx, table, Lookup(base, nfixed, map, mapLength, objectFlags));
1469   if (ptr) {
1470     if (allocatedNewShape) {
1471       *allocatedNewShape = false;
1472     }
1473     return *ptr;
1474   }
1475
1476   Rooted<BaseShape*> baseRoot(cx, base);
1477   Rooted<SharedShape*> shape(
1478       cx, SharedShape::new_(cx, baseRoot, objectFlags, nfixed, map, mapLength));
1479   if (!shape) {
1480     return nullptr;
1481   }
1482
1483   Lookup lookup(baseRoot, nfixed, map, mapLength, objectFlags);
1484   if (!ptr.add(cx, table, lookup, shape)) {
1485     return nullptr;
1486   }
1487
1488   if (allocatedNewShape) {
1489     *allocatedNewShape = true;
1490   }
1491
1492   return shape;
1493 }
1494
1495 /* static */
1496 SharedShape* SharedShape::getInitialOrPropMapShape(
1497     JSContext* cx, const JSClass* clasp, JS::Realm* realm, TaggedProto proto,
1498     size_t nfixed, Handle<SharedPropMap*> map, uint32_t mapLength,
1499     ObjectFlags objectFlags) {
1500   if (!map) {
1501     MOZ_ASSERT(mapLength == 0);
1502     return getInitialShape(cx, clasp, realm, proto, nfixed, objectFlags);
1503   }
1504
1505   Rooted<TaggedProto> protoRoot(cx, proto);
1506   BaseShape* nbase = BaseShape::get(cx, clasp, realm, protoRoot);
1507   if (!nbase) {
1508     return nullptr;
1509   }
1510
1511   return getPropMapShape(cx, nbase, nfixed, map, mapLength, objectFlags);
1512 }
1513
1514 /* static */
1515 void SharedShape::insertInitialShape(JSContext* cx,
1516                                      Handle<SharedShape*> shape) {
1517   using Lookup = InitialShapeHasher::Lookup;
1518   Lookup lookup(shape->getObjectClass(), shape->realm(), shape->proto(),
1519                 shape->numFixedSlots(), shape->objectFlags());
1520
1521   auto& table = cx->zone()->shapeZone().initialShapes;
1522   InitialShapeSet::Ptr p = table.lookup(lookup);
1523   MOZ_ASSERT(p);
1524
1525   // The metadata callback can end up causing redundant changes of the initial
1526   // shape.
1527   SharedShape* initialShape = *p;
1528   if (initialShape == shape) {
1529     return;
1530   }
1531
1532   MOZ_ASSERT(initialShape->numFixedSlots() == shape->numFixedSlots());
1533   MOZ_ASSERT(initialShape->base() == shape->base());
1534   MOZ_ASSERT(initialShape->objectFlags() == shape->objectFlags());
1535
1536   table.replaceKey(p, lookup, shape.get());
1537
1538   // Purge the prototype's shape cache entry.
1539   if (shape->proto().isObject()) {
1540     JSObject* protoObj = shape->proto().toObject();
1541     if (protoObj->shape()->cache().isShapeWithProto()) {
1542       protoObj->shape()->cacheRef().setNone();
1543     }
1544   }
1545 }
1546
1547 /* static */
1548 ProxyShape* ProxyShape::getShape(JSContext* cx, const JSClass* clasp,
1549                                  JS::Realm* realm, TaggedProto proto,
1550                                  ObjectFlags objectFlags) {
1551   MOZ_ASSERT(cx->compartment() == realm->compartment());
1552   MOZ_ASSERT_IF(proto.isObject(),
1553                 cx->isInsideCurrentCompartment(proto.toObject()));
1554
1555   if (proto.isObject() && !proto.toObject()->isUsedAsPrototype()) {
1556     RootedObject protoObj(cx, proto.toObject());
1557     if (!SetObjectIsUsedAsPrototype(cx, protoObj)) {
1558       return nullptr;
1559     }
1560     proto = TaggedProto(protoObj);
1561   }
1562
1563   auto& table = realm->zone()->shapeZone().proxyShapes;
1564
1565   using Lookup = ProxyShapeHasher::Lookup;
1566   auto ptr =
1567       MakeDependentAddPtr(cx, table, Lookup(clasp, realm, proto, objectFlags));
1568   if (ptr) {
1569     return *ptr;
1570   }
1571
1572   Rooted<TaggedProto> protoRoot(cx, proto);
1573   Rooted<BaseShape*> nbase(cx, BaseShape::get(cx, clasp, realm, protoRoot));
1574   if (!nbase) {
1575     return nullptr;
1576   }
1577
1578   Rooted<ProxyShape*> shape(cx, ProxyShape::new_(cx, nbase, objectFlags));
1579   if (!shape) {
1580     return nullptr;
1581   }
1582
1583   Lookup lookup(clasp, realm, protoRoot, objectFlags);
1584   if (!ptr.add(cx, table, lookup, shape)) {
1585     return nullptr;
1586   }
1587
1588   return shape;
1589 }
1590
1591 /* static */
1592 WasmGCShape* WasmGCShape::getShape(JSContext* cx, const JSClass* clasp,
1593                                    JS::Realm* realm, TaggedProto proto,
1594                                    const wasm::RecGroup* recGroup,
1595                                    ObjectFlags objectFlags) {
1596   MOZ_ASSERT(cx->compartment() == realm->compartment());
1597   MOZ_ASSERT_IF(proto.isObject(),
1598                 cx->isInsideCurrentCompartment(proto.toObject()));
1599
1600   if (proto.isObject() && !proto.toObject()->isUsedAsPrototype()) {
1601     RootedObject protoObj(cx, proto.toObject());
1602     if (!SetObjectIsUsedAsPrototype(cx, protoObj)) {
1603       return nullptr;
1604     }
1605     proto = TaggedProto(protoObj);
1606   }
1607
1608   auto& table = realm->zone()->shapeZone().wasmGCShapes;
1609
1610   using Lookup = WasmGCShapeHasher::Lookup;
1611   auto ptr = MakeDependentAddPtr(
1612       cx, table, Lookup(clasp, realm, proto, recGroup, objectFlags));
1613   if (ptr) {
1614     return *ptr;
1615   }
1616
1617   Rooted<TaggedProto> protoRoot(cx, proto);
1618   Rooted<BaseShape*> nbase(cx, BaseShape::get(cx, clasp, realm, protoRoot));
1619   if (!nbase) {
1620     return nullptr;
1621   }
1622
1623   Rooted<WasmGCShape*> shape(
1624       cx, WasmGCShape::new_(cx, nbase, recGroup, objectFlags));
1625   if (!shape) {
1626     return nullptr;
1627   }
1628
1629   Lookup lookup(clasp, realm, protoRoot, recGroup, objectFlags);
1630   if (!ptr.add(cx, table, lookup, shape)) {
1631     return nullptr;
1632   }
1633
1634   return shape;
1635 }
1636
1637 JS::ubi::Node::Size JS::ubi::Concrete<js::Shape>::size(
1638     mozilla::MallocSizeOf mallocSizeOf) const {
1639   Size size = js::gc::Arena::thingSize(get().asTenured().getAllocKind());
1640
1641   if (get().cache().isShapeSetForAdd()) {
1642     ShapeSetForAdd* set = get().cache().toShapeSetForAdd();
1643     size += set->shallowSizeOfIncludingThis(mallocSizeOf);
1644   }
1645
1646   return size;
1647 }
1648
1649 JS::ubi::Node::Size JS::ubi::Concrete<js::BaseShape>::size(
1650     mozilla::MallocSizeOf mallocSizeOf) const {
1651   return js::gc::Arena::thingSize(get().asTenured().getAllocKind());
1652 }