js/src/vm/Shape.h

   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 #ifndef vm_Shape_h
   8 #define vm_Shape_h
   9
  10 #include "js/shadow/Shape.h"  // JS::shadow::Shape, JS::shadow::BaseShape
  11
  12 #include "mozilla/Attributes.h"
  13 #include "mozilla/MemoryReporting.h"
  14
  15 #include "jstypes.h"
  16 #include "NamespaceImports.h"
  17
  18 #include "gc/Barrier.h"
  19 #include "gc/MaybeRooted.h"
  20 #include "js/HashTable.h"
  21 #include "js/Id.h"  // JS::PropertyKey
  22 #include "js/MemoryMetrics.h"
  23 #include "js/RootingAPI.h"
  24 #include "js/UbiNode.h"
  25 #include "util/EnumFlags.h"
  26 #include "vm/ObjectFlags.h"
  27 #include "vm/PropertyInfo.h"
  28 #include "vm/PropMap.h"
  29 #include "vm/TaggedProto.h"
  30
  31 // [SMDOC] Shapes
  32 //
  33 // A Shape represents the layout of an object. It stores and implies:
  34 //
  35 //  * The object's JSClass, Realm, prototype (see BaseShape section below).
  36 //  * The object's flags (ObjectFlags).
  37 //  * For native objects, the object's properties (PropMap and map length).
  38 //  * For native objects, the fixed slot capacity of the object (numFixedSlots).
  39 //
  40 // For native objects, the shape implies the property structure (keys,
  41 // attributes, property order for enumeration) but not the property values.
  42 // The values are stored in object slots.
  43 //
  44 // Every JSObject has a pointer, |shape_|, accessible via shape(), to the
  45 // current shape of the object. This pointer permits fast object layout tests.
  46 //
  47 // Shapes use the following C++ class hierarchy:
  48 //
  49 // C++ Type                     Used by
  50 // ============================ ====================================
  51 // Shape (abstract)             JSObject
  52 //  |
  53 //  +-- NativeShape (abstract)  NativeObject
  54 //  |    |
  55 //  |    +-- SharedShape        NativeObject with a shared shape
  56 //  |    |
  57 //  |    +-- DictionaryShape    NativeObject with a dictionary shape
  58 //  |
  59 //  +-- ProxyShape              ProxyObject
  60 //  |
  61 //  +-- WasmGCShape             WasmGCObject
  62 //
  63 // Classes marked with (abstract) above are not literally C++ Abstract Base
  64 // Classes (since there are no virtual functions, pure or not, in this
  65 // hierarchy), but have the same meaning: there are no shapes with this type as
  66 // its most-derived type.
  67 //
  68 // SharedShape
  69 // ===========
  70 // Used only for native objects. This is either an initial shape (no property
  71 // map) or SharedPropMap shape (for objects with at least one property).
  72 //
  73 // These are immutable tuples stored in a hash table, so that objects with the
  74 // same structure end up with the same shape (this both saves memory and allows
  75 // JIT optimizations based on this shape).
  76 //
  77 // To avoid hash table lookups on the hot addProperty path, shapes have a
  78 // ShapeCachePtr that's used as cache for this. This cache is purged on GC.
  79 // The shape cache is also used as cache for prototype shapes, to point to the
  80 // initial shape for objects using that shape, and for cached iterators.
  81 //
  82 // DictionaryShape
  83 // ===============
  84 // Used only for native objects. An object with a dictionary shape is "in
  85 // dictionary mode". Certain property operations are not supported for shared
  86 // maps so in these cases we need to convert the object to dictionary mode by
  87 // creating a dictionary property map and a dictionary shape. An object is
  88 // converted to dictionary mode in the following cases:
  89 //
  90 // - Changing a property's flags/attributes and the property is not the last
  91 //   property.
  92 // - Removing a property other than the object's last property.
  93 // - The object has many properties. See maybeConvertToDictionaryForAdd for the
  94 //   heuristics.
  95 //
  96 // Dictionary shapes are unshared, private to a single object, and always have a
  97 // a DictionaryPropMap that's similarly unshared. Dictionary shape mutations do
  98 // require allocating a new dictionary shape for the object, to properly
  99 // invalidate JIT inline caches and other shape guards.
 100 // See NativeObject::generateNewDictionaryShape.
 101 //
 102 // ProxyShape
 103 // ==========
 104 // Shape used for proxy objects (including wrappers). Proxies with the same
 105 // JSClass, Realm, prototype and ObjectFlags will have the same shape.
 106 //
 107 // WasmGCShape
 108 // ===========
 109 // Shape used for Wasm GC objects. Wasm GC objects with the same JSClass, Realm,
 110 // prototype and ObjectFlags will have the same shape.
 111 //
 112 // BaseShape
 113 // =========
 114 // Because many Shapes have similar data, there is actually a secondary type
 115 // called a BaseShape that holds some of a Shape's data (the JSClass, Realm,
 116 // prototype). Many shapes can share a single BaseShape.
 117
 118 MOZ_ALWAYS_INLINE size_t JSSLOT_FREE(const JSClass* clasp) {
 119   // Proxy classes have reserved slots, but proxies manage their own slot
 120   // layout.
 121   MOZ_ASSERT(!clasp->isProxyObject());
 122   return JSCLASS_RESERVED_SLOTS(clasp);
 123 }
 124
 125 namespace js {
 126
 127 class NativeShape;
 128 class Shape;
 129 class PropertyIteratorObject;
 130
 131 namespace gc {
 132 class TenuringTracer;
 133 }  // namespace gc
 134
 135 namespace wasm {
 136 class RecGroup;
 137 }  // namespace wasm
 138
 139 // Hash policy for ShapeCachePtr's ShapeSetForAdd. Maps the new property key and
 140 // flags to the new shape.
 141 struct ShapeForAddHasher : public DefaultHasher<Shape*> {
 142   using Key = SharedShape*;
 143
 144   struct Lookup {
 145     PropertyKey key;
 146     PropertyFlags flags;
 147
 148     Lookup(PropertyKey key, PropertyFlags flags) : key(key), flags(flags) {}
 149   };
 150
 151   static MOZ_ALWAYS_INLINE HashNumber hash(const Lookup& l);
 152   static MOZ_ALWAYS_INLINE bool match(SharedShape* shape, const Lookup& l);
 153 };
 154 using ShapeSetForAdd =
 155     HashSet<SharedShape*, ShapeForAddHasher, SystemAllocPolicy>;
 156
 157 // Each shape has a cache pointer that's either:
 158 //
 159 // * None
 160 // * For shared shapes, a single shape used to speed up addProperty.
 161 // * For shared shapes, a set of shapes used to speed up addProperty.
 162 // * For prototype shapes, the most recently used initial shape allocated for a
 163 //   prototype object with this shape.
 164 // * For any shape, a PropertyIteratorObject used to speed up GetIterator.
 165 //
 166 // The cache is purely an optimization and is purged on GC (all shapes with a
 167 // non-None ShapeCachePtr are added to a vector in the Zone).
 168 class ShapeCachePtr {
 169   enum {
 170     SINGLE_SHAPE_FOR_ADD = 0,
 171     SHAPE_SET_FOR_ADD = 1,
 172     SHAPE_WITH_PROTO = 2,
 173     ITERATOR = 3,
 174     MASK = 3
 175   };
 176
 177   uintptr_t bits = 0;
 178
 179  public:
 180   bool isNone() const { return !bits; }
 181   void setNone() { bits = 0; }
 182
 183   bool isSingleShapeForAdd() const {
 184     return (bits & MASK) == SINGLE_SHAPE_FOR_ADD && !isNone();
 185   }
 186   SharedShape* toSingleShapeForAdd() const {
 187     MOZ_ASSERT(isSingleShapeForAdd());
 188     return reinterpret_cast<SharedShape*>(bits & ~uintptr_t(MASK));
 189   }
 190   void setSingleShapeForAdd(SharedShape* shape) {
 191     MOZ_ASSERT(shape);
 192     MOZ_ASSERT((uintptr_t(shape) & MASK) == 0);
 193     MOZ_ASSERT(!isShapeSetForAdd());  // Don't leak the ShapeSet.
 194     bits = uintptr_t(shape) | SINGLE_SHAPE_FOR_ADD;
 195   }
 196
 197   bool isShapeSetForAdd() const { return (bits & MASK) == SHAPE_SET_FOR_ADD; }
 198   ShapeSetForAdd* toShapeSetForAdd() const {
 199     MOZ_ASSERT(isShapeSetForAdd());
 200     return reinterpret_cast<ShapeSetForAdd*>(bits & ~uintptr_t(MASK));
 201   }
 202   void setShapeSetForAdd(ShapeSetForAdd* hash) {
 203     MOZ_ASSERT(hash);
 204     MOZ_ASSERT((uintptr_t(hash) & MASK) == 0);
 205     bits = uintptr_t(hash) | SHAPE_SET_FOR_ADD;
 206   }
 207
 208   bool isForAdd() const { return isSingleShapeForAdd() || isShapeSetForAdd(); }
 209
 210   bool isShapeWithProto() const { return (bits & MASK) == SHAPE_WITH_PROTO; }
 211   SharedShape* toShapeWithProto() const {
 212     MOZ_ASSERT(isShapeWithProto());
 213     return reinterpret_cast<SharedShape*>(bits & ~uintptr_t(MASK));
 214   }
 215   void setShapeWithProto(SharedShape* shape) {
 216     MOZ_ASSERT(shape);
 217     MOZ_ASSERT((uintptr_t(shape) & MASK) == 0);
 218     MOZ_ASSERT(!isShapeSetForAdd());  // Don't leak the ShapeSet.
 219     bits = uintptr_t(shape) | SHAPE_WITH_PROTO;
 220   }
 221
 222   bool isIterator() const { return (bits & MASK) == ITERATOR; }
 223   PropertyIteratorObject* toIterator() const {
 224     MOZ_ASSERT(isIterator());
 225     return reinterpret_cast<PropertyIteratorObject*>(bits & ~uintptr_t(MASK));
 226   }
 227   void setIterator(PropertyIteratorObject* iter) {
 228     MOZ_ASSERT(iter);
 229     MOZ_ASSERT((uintptr_t(iter) & MASK) == 0);
 230     MOZ_ASSERT(!isShapeSetForAdd());  // Don't leak the ShapeSet.
 231     bits = uintptr_t(iter) | ITERATOR;
 232   }
 233   friend class js::jit::MacroAssembler;
 234 } JS_HAZ_GC_POINTER;
 235
 236 // BaseShapes store the object's class, realm and prototype. BaseShapes are
 237 // immutable tuples stored in a per-Zone hash table.
 238 class BaseShape : public gc::TenuredCellWithNonGCPointer<const JSClass> {
 239  public:
 240   /* Class of referring object, stored in the cell header */
 241   const JSClass* clasp() const { return headerPtr(); }
 242
 243  private:
 244   JS::Realm* realm_;
 245   GCPtr<TaggedProto> proto_;
 246
 247   BaseShape(const BaseShape& base) = delete;
 248   BaseShape& operator=(const BaseShape& other) = delete;
 249
 250  public:
 251   void finalize(JS::GCContext* gcx) {}
 252
 253   BaseShape(const JSClass* clasp, JS::Realm* realm, TaggedProto proto);
 254
 255   /* Not defined: BaseShapes must not be stack allocated. */
 256   ~BaseShape() = delete;
 257
 258   JS::Realm* realm() const { return realm_; }
 259   JS::Compartment* compartment() const {
 260     return JS::GetCompartmentForRealm(realm());
 261   }
 262   JS::Compartment* maybeCompartment() const { return compartment(); }
 263
 264   TaggedProto proto() const { return proto_; }
 265
 266   /*
 267    * Lookup base shapes from the zone's baseShapes table, adding if not
 268    * already found.
 269    */
 270   static BaseShape* get(JSContext* cx, const JSClass* clasp, JS::Realm* realm,
 271                         Handle<TaggedProto> proto);
 272
 273   static const JS::TraceKind TraceKind = JS::TraceKind::BaseShape;
 274
 275   void traceChildren(JSTracer* trc);
 276
 277   static constexpr size_t offsetOfClasp() { return offsetOfHeaderPtr(); }
 278
 279   static constexpr size_t offsetOfRealm() {
 280     return offsetof(BaseShape, realm_);
 281   }
 282
 283   static constexpr size_t offsetOfProto() {
 284     return offsetof(BaseShape, proto_);
 285   }
 286
 287  private:
 288   static void staticAsserts() {
 289     static_assert(offsetOfClasp() == offsetof(JS::shadow::BaseShape, clasp));
 290     static_assert(offsetOfRealm() == offsetof(JS::shadow::BaseShape, realm));
 291     static_assert(sizeof(BaseShape) % gc::CellAlignBytes == 0,
 292                   "Things inheriting from gc::Cell must have a size that's "
 293                   "a multiple of gc::CellAlignBytes");
 294     // Sanity check BaseShape size is what we expect.
 295 #ifdef JS_64BIT
 296     static_assert(sizeof(BaseShape) == 3 * sizeof(void*));
 297 #else
 298     static_assert(sizeof(BaseShape) == 4 * sizeof(void*));
 299 #endif
 300   }
 301 };
 302
 303 class Shape : public gc::CellWithTenuredGCPointer<gc::TenuredCell, BaseShape> {
 304   friend class ::JSObject;
 305   friend class ::JSFunction;
 306   friend class GCMarker;
 307   friend class NativeObject;
 308   friend class SharedShape;
 309   friend class PropertyTree;
 310   friend class gc::TenuringTracer;
 311   friend class JS::ubi::Concrete<Shape>;
 312   friend class gc::RelocationOverlay;
 313
 314  public:
 315   // Base shape, stored in the cell header.
 316   BaseShape* base() const { return headerPtr(); }
 317
 318   using Kind = JS::shadow::Shape::Kind;
 319
 320  protected:
 321   // Flags that are not modified after the Shape is created. Off-thread Ion
 322   // compilation can access the immutableFlags word, so we don't want any
 323   // mutable state here to avoid (TSan) races.
 324   enum ImmutableFlags : uint32_t {
 325     // For NativeShape: the length associated with the property map. This is a
 326     // value in the range [0, PropMap::Capacity]. A length of 0 indicates the
 327     // object is empty (has no properties).
 328     MAP_LENGTH_MASK = BitMask(4),
 329
 330     // The Shape Kind. The NativeObject kinds have the low bit set.
 331     KIND_SHIFT = 4,
 332     KIND_MASK = 0b11,
 333     IS_NATIVE_BIT = 0x1 << KIND_SHIFT,
 334
 335     // For NativeShape: the number of fixed slots in objects with this shape.
 336     // FIXED_SLOTS_MAX is the biggest count of fixed slots a Shape can store.
 337     FIXED_SLOTS_MAX = 0x1f,
 338     FIXED_SLOTS_SHIFT = 6,
 339     FIXED_SLOTS_MASK = uint32_t(FIXED_SLOTS_MAX << FIXED_SLOTS_SHIFT),
 340
 341     // For SharedShape: the slot span of the object, if it fits in a single
 342     // byte. If the value is SMALL_SLOTSPAN_MAX, the slot span has to be
 343     // computed based on the property map (which is slower).
 344     //
 345     // Note: NativeObject::addProperty will convert to dictionary mode before we
 346     // reach this limit, but there are other places where we add properties to
 347     // shapes, for example environment object shapes.
 348     SMALL_SLOTSPAN_MAX = 0x3ff,  // 10 bits.
 349     SMALL_SLOTSPAN_SHIFT = 11,
 350     SMALL_SLOTSPAN_MASK = uint32_t(SMALL_SLOTSPAN_MAX << SMALL_SLOTSPAN_SHIFT),
 351   };
 352
 353   uint32_t immutableFlags;   // Immutable flags, see above.
 354   ObjectFlags objectFlags_;  // Immutable object flags, see ObjectFlags.
 355
 356   // Cache used to speed up common operations on shapes.
 357   ShapeCachePtr cache_;
 358
 359   // Give the object a shape that's similar to its current shape, but with the
 360   // passed objectFlags, proto, and nfixed values.
 361   static bool replaceShape(JSContext* cx, HandleObject obj,
 362                            ObjectFlags objectFlags, TaggedProto proto,
 363                            uint32_t nfixed);
 364
 365  public:
 366   void addSizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf,
 367                               JS::ShapeInfo* info) const {
 368     if (cache_.isShapeSetForAdd()) {
 369       info->shapesMallocHeapCache +=
 370           cache_.toShapeSetForAdd()->shallowSizeOfIncludingThis(mallocSizeOf);
 371     }
 372   }
 373
 374   ShapeCachePtr& cacheRef() { return cache_; }
 375   ShapeCachePtr cache() const { return cache_; }
 376
 377   void maybeCacheIterator(JSContext* cx, PropertyIteratorObject* iter);
 378
 379   const JSClass* getObjectClass() const { return base()->clasp(); }
 380   JS::Realm* realm() const { return base()->realm(); }
 381
 382   JS::Compartment* compartment() const { return base()->compartment(); }
 383   JS::Compartment* maybeCompartment() const {
 384     return base()->maybeCompartment();
 385   }
 386
 387   TaggedProto proto() const { return base()->proto(); }
 388
 389   ObjectFlags objectFlags() const { return objectFlags_; }
 390   bool hasObjectFlag(ObjectFlag flag) const {
 391     return objectFlags_.hasFlag(flag);
 392   }
 393
 394  protected:
 395   Shape(Kind kind, BaseShape* base, ObjectFlags objectFlags)
 396       : CellWithTenuredGCPointer(base),
 397         immutableFlags(uint32_t(kind) << KIND_SHIFT),
 398         objectFlags_(objectFlags) {
 399     MOZ_ASSERT(base);
 400     MOZ_ASSERT(this->kind() == kind, "kind must fit in KIND_MASK");
 401     MOZ_ASSERT(isNative() == base->clasp()->isNativeObject());
 402   }
 403
 404   Shape(const Shape& other) = delete;
 405
 406  public:
 407   Kind kind() const { return Kind((immutableFlags >> KIND_SHIFT) & KIND_MASK); }
 408
 409   bool isNative() const {
 410     // Note: this is equivalent to `isShared() || isDictionary()`.
 411     return immutableFlags & IS_NATIVE_BIT;
 412   }
 413
 414   bool isShared() const { return kind() == Kind::Shared; }
 415   bool isDictionary() const { return kind() == Kind::Dictionary; }
 416   bool isProxy() const { return kind() == Kind::Proxy; }
 417   bool isWasmGC() const { return kind() == Kind::WasmGC; }
 418
 419   inline NativeShape& asNative();
 420   inline SharedShape& asShared();
 421   inline DictionaryShape& asDictionary();
 422   inline WasmGCShape& asWasmGC();
 423
 424   inline const NativeShape& asNative() const;
 425   inline const SharedShape& asShared() const;
 426   inline const DictionaryShape& asDictionary() const;
 427   inline const WasmGCShape& asWasmGC() const;
 428
 429 #ifdef DEBUG
 430   void dump(js::GenericPrinter& out) const;
 431   void dump() const;
 432 #endif
 433
 434   inline void purgeCache(JS::GCContext* gcx);
 435   inline void finalize(JS::GCContext* gcx);
 436
 437   static const JS::TraceKind TraceKind = JS::TraceKind::Shape;
 438
 439   void traceChildren(JSTracer* trc);
 440
 441   // For JIT usage.
 442   static constexpr size_t offsetOfBaseShape() { return offsetOfHeaderPtr(); }
 443
 444   static constexpr size_t offsetOfObjectFlags() {
 445     return offsetof(Shape, objectFlags_);
 446   }
 447
 448   static inline size_t offsetOfImmutableFlags() {
 449     return offsetof(Shape, immutableFlags);
 450   }
 451
 452   static constexpr uint32_t kindShift() { return KIND_SHIFT; }
 453   static constexpr uint32_t kindMask() { return KIND_MASK; }
 454   static constexpr uint32_t isNativeBit() { return IS_NATIVE_BIT; }
 455
 456   static constexpr size_t offsetOfCachePtr() { return offsetof(Shape, cache_); }
 457
 458  private:
 459   static void staticAsserts() {
 460     static_assert(offsetOfBaseShape() == offsetof(JS::shadow::Shape, base));
 461     static_assert(offsetof(Shape, immutableFlags) ==
 462                   offsetof(JS::shadow::Shape, immutableFlags));
 463     static_assert(KIND_SHIFT == JS::shadow::Shape::KIND_SHIFT);
 464     static_assert(KIND_MASK == JS::shadow::Shape::KIND_MASK);
 465     static_assert(FIXED_SLOTS_SHIFT == JS::shadow::Shape::FIXED_SLOTS_SHIFT);
 466     static_assert(FIXED_SLOTS_MASK == JS::shadow::Shape::FIXED_SLOTS_MASK);
 467   }
 468 };
 469
 470 // Shared or dictionary shape for a NativeObject.
 471 class NativeShape : public Shape {
 472  protected:
 473   // The shape's property map. This is either nullptr (for an
 474   // initial SharedShape with no properties), a SharedPropMap (for
 475   // SharedShape) or a DictionaryPropMap (for DictionaryShape).
 476   GCPtr<PropMap*> propMap_;
 477
 478   NativeShape(Kind kind, BaseShape* base, ObjectFlags objectFlags,
 479               uint32_t nfixed, PropMap* map, uint32_t mapLength)
 480       : Shape(kind, base, objectFlags), propMap_(map) {
 481     MOZ_ASSERT(base->clasp()->isNativeObject());
 482     MOZ_ASSERT(mapLength <= PropMap::Capacity);
 483     immutableFlags |= (nfixed << FIXED_SLOTS_SHIFT) | mapLength;
 484   }
 485
 486  public:
 487   void traceChildren(JSTracer* trc);
 488
 489   PropMap* propMap() const { return propMap_; }
 490   uint32_t propMapLength() const { return immutableFlags & MAP_LENGTH_MASK; }
 491
 492   PropertyInfoWithKey lastProperty() const {
 493     MOZ_ASSERT(propMapLength() > 0);
 494     size_t index = propMapLength() - 1;
 495     return propMap()->getPropertyInfoWithKey(index);
 496   }
 497
 498   MOZ_ALWAYS_INLINE PropMap* lookup(JSContext* cx, PropertyKey key,
 499                                     uint32_t* index);
 500   MOZ_ALWAYS_INLINE PropMap* lookupPure(PropertyKey key, uint32_t* index);
 501
 502   uint32_t numFixedSlots() const {
 503     return (immutableFlags & FIXED_SLOTS_MASK) >> FIXED_SLOTS_SHIFT;
 504   }
 505
 506   // For JIT usage.
 507   static constexpr uint32_t fixedSlotsMask() { return FIXED_SLOTS_MASK; }
 508   static constexpr uint32_t fixedSlotsShift() { return FIXED_SLOTS_SHIFT; }
 509 };
 510
 511 // Shared shape for a NativeObject.
 512 class SharedShape : public NativeShape {
 513   friend class js::gc::CellAllocator;
 514   SharedShape(BaseShape* base, ObjectFlags objectFlags, uint32_t nfixed,
 515               SharedPropMap* map, uint32_t mapLength)
 516       : NativeShape(Kind::Shared, base, objectFlags, nfixed, map, mapLength) {
 517     initSmallSlotSpan();
 518   }
 519
 520   static SharedShape* new_(JSContext* cx, Handle<BaseShape*> base,
 521                            ObjectFlags objectFlags, uint32_t nfixed,
 522                            Handle<SharedPropMap*> map, uint32_t mapLength);
 523
 524   void initSmallSlotSpan() {
 525     MOZ_ASSERT(isShared());
 526     uint32_t slotSpan = slotSpanSlow();
 527     if (slotSpan > SMALL_SLOTSPAN_MAX) {
 528       slotSpan = SMALL_SLOTSPAN_MAX;
 529     }
 530     MOZ_ASSERT((immutableFlags & SMALL_SLOTSPAN_MASK) == 0);
 531     immutableFlags |= (slotSpan << SMALL_SLOTSPAN_SHIFT);
 532   }
 533
 534  public:
 535   SharedPropMap* propMap() const {
 536     MOZ_ASSERT(isShared());
 537     return propMap_ ? propMap_->asShared() : nullptr;
 538   }
 539   inline SharedPropMap* propMapMaybeForwarded() const;
 540
 541   bool lastPropertyMatchesForAdd(PropertyKey key, PropertyFlags flags,
 542                                  uint32_t* slot) const {
 543     MOZ_ASSERT(isShared());
 544     MOZ_ASSERT(propMapLength() > 0);
 545     uint32_t index = propMapLength() - 1;
 546     SharedPropMap* map = propMap();
 547     if (map->getKey(index) != key) {
 548       return false;
 549     }
 550     PropertyInfo prop = map->getPropertyInfo(index);
 551     if (prop.flags() != flags) {
 552       return false;
 553     }
 554     *slot = prop.maybeSlot();
 555     return true;
 556   }
 557
 558   uint32_t slotSpanSlow() const {
 559     MOZ_ASSERT(isShared());
 560     const JSClass* clasp = getObjectClass();
 561     return SharedPropMap::slotSpan(clasp, propMap(), propMapLength());
 562   }
 563   uint32_t slotSpan() const {
 564     MOZ_ASSERT(isShared());
 565     uint32_t span =
 566         (immutableFlags & SMALL_SLOTSPAN_MASK) >> SMALL_SLOTSPAN_SHIFT;
 567     if (MOZ_LIKELY(span < SMALL_SLOTSPAN_MAX)) {
 568       MOZ_ASSERT(slotSpanSlow() == span);
 569       return span;
 570     }
 571     return slotSpanSlow();
 572   }
 573
 574   /*
 575    * Lookup an initial shape matching the given parameters, creating an empty
 576    * shape if none was found.
 577    */
 578   static SharedShape* getInitialShape(JSContext* cx, const JSClass* clasp,
 579                                       JS::Realm* realm, TaggedProto proto,
 580                                       size_t nfixed,
 581                                       ObjectFlags objectFlags = {});
 582   static SharedShape* getInitialShape(JSContext* cx, const JSClass* clasp,
 583                                       JS::Realm* realm, TaggedProto proto,
 584                                       gc::AllocKind kind,
 585                                       ObjectFlags objectFlags = {});
 586
 587   static SharedShape* getPropMapShape(JSContext* cx, BaseShape* base,
 588                                       size_t nfixed, Handle<SharedPropMap*> map,
 589                                       uint32_t mapLength,
 590                                       ObjectFlags objectFlags,
 591                                       bool* allocatedNewShape = nullptr);
 592
 593   static SharedShape* getInitialOrPropMapShape(
 594       JSContext* cx, const JSClass* clasp, JS::Realm* realm, TaggedProto proto,
 595       size_t nfixed, Handle<SharedPropMap*> map, uint32_t mapLength,
 596       ObjectFlags objectFlags);
 597
 598   /*
 599    * Reinsert an alternate initial shape, to be returned by future
 600    * getInitialShape calls, until the new shape becomes unreachable in a GC
 601    * and the table entry is purged.
 602    */
 603   static void insertInitialShape(JSContext* cx, Handle<SharedShape*> shape);
 604
 605   /*
 606    * Some object subclasses are allocated with a built-in set of properties.
 607    * The first time such an object is created, these built-in properties must
 608    * be set manually, to compute an initial shape.  Afterward, that initial
 609    * shape can be reused for newly-created objects that use the subclass's
 610    * standard prototype.  This method should be used in a post-allocation
 611    * init method, to ensure that objects of such subclasses compute and cache
 612    * the initial shape, if it hasn't already been computed.
 613    */
 614   template <class ObjectSubclass>
 615   static inline bool ensureInitialCustomShape(JSContext* cx,
 616                                               Handle<ObjectSubclass*> obj);
 617 };
 618
 619 // Dictionary shape for a NativeObject.
 620 class DictionaryShape : public NativeShape {
 621   friend class ::JSObject;
 622   friend class js::gc::CellAllocator;
 623   friend class NativeObject;
 624
 625   DictionaryShape(BaseShape* base, ObjectFlags objectFlags, uint32_t nfixed,
 626                   DictionaryPropMap* map, uint32_t mapLength)
 627       : NativeShape(Kind::Dictionary, base, objectFlags, nfixed, map,
 628                     mapLength) {
 629     MOZ_ASSERT(map);
 630   }
 631   explicit DictionaryShape(NativeObject* nobj);
 632
 633   // Methods to set fields of a new dictionary shape. Must not be used for
 634   // shapes that might have been exposed to script.
 635   void updateNewShape(ObjectFlags flags, DictionaryPropMap* map,
 636                       uint32_t mapLength) {
 637     MOZ_ASSERT(isDictionary());
 638     objectFlags_ = flags;
 639     propMap_ = map;
 640     immutableFlags = (immutableFlags & ~MAP_LENGTH_MASK) | mapLength;
 641     MOZ_ASSERT(propMapLength() == mapLength);
 642   }
 643   void setObjectFlagsOfNewShape(ObjectFlags flags) {
 644     MOZ_ASSERT(isDictionary());
 645     objectFlags_ = flags;
 646   }
 647
 648  public:
 649   static DictionaryShape* new_(JSContext* cx, Handle<BaseShape*> base,
 650                                ObjectFlags objectFlags, uint32_t nfixed,
 651                                Handle<DictionaryPropMap*> map,
 652                                uint32_t mapLength);
 653   static DictionaryShape* new_(JSContext* cx, Handle<NativeObject*> obj);
 654
 655   DictionaryPropMap* propMap() const {
 656     MOZ_ASSERT(isDictionary());
 657     MOZ_ASSERT(propMap_);
 658     return propMap_->asDictionary();
 659   }
 660 };
 661
 662 // Shape used for a ProxyObject.
 663 class ProxyShape : public Shape {
 664   // Needed to maintain the same size as other shapes.
 665   uintptr_t padding_;
 666
 667   friend class js::gc::CellAllocator;
 668   ProxyShape(BaseShape* base, ObjectFlags objectFlags)
 669       : Shape(Kind::Proxy, base, objectFlags) {
 670     MOZ_ASSERT(base->clasp()->isProxyObject());
 671   }
 672
 673   static ProxyShape* new_(JSContext* cx, Handle<BaseShape*> base,
 674                           ObjectFlags objectFlags);
 675
 676  public:
 677   static ProxyShape* getShape(JSContext* cx, const JSClass* clasp,
 678                               JS::Realm* realm, TaggedProto proto,
 679                               ObjectFlags objectFlags);
 680
 681  private:
 682   static void staticAsserts() {
 683     // Silence unused field warning.
 684     static_assert(sizeof(padding_) == sizeof(uintptr_t));
 685   }
 686 };
 687
 688 // Shape used for a WasmGCObject.
 689 class WasmGCShape : public Shape {
 690   // The shape's recursion group.
 691   const wasm::RecGroup* recGroup_;
 692
 693   friend class js::gc::CellAllocator;
 694   WasmGCShape(BaseShape* base, const wasm::RecGroup* recGroup,
 695               ObjectFlags objectFlags)
 696       : Shape(Kind::WasmGC, base, objectFlags), recGroup_(recGroup) {
 697     MOZ_ASSERT(!base->clasp()->isProxyObject());
 698     MOZ_ASSERT(!base->clasp()->isNativeObject());
 699   }
 700
 701   static WasmGCShape* new_(JSContext* cx, Handle<BaseShape*> base,
 702                            const wasm::RecGroup* recGroup,
 703                            ObjectFlags objectFlags);
 704
 705   // Take a reference to the recursion group.
 706   inline void init();
 707
 708  public:
 709   static WasmGCShape* getShape(JSContext* cx, const JSClass* clasp,
 710                                JS::Realm* realm, TaggedProto proto,
 711                                const wasm::RecGroup* recGroup,
 712                                ObjectFlags objectFlags);
 713
 714   // Release the reference to the recursion group.
 715   inline void finalize(JS::GCContext* gcx);
 716
 717   const wasm::RecGroup* recGroup() const {
 718     MOZ_ASSERT(isWasmGC());
 719     return recGroup_;
 720   }
 721 };
 722
 723 // A type that can be used to get the size of the Shape alloc kind.
 724 class SizedShape : public Shape {
 725   // The various shape kinds have an extra word that is used defined
 726   // differently depending on the type.
 727   uintptr_t padding_;
 728
 729   static void staticAsserts() {
 730     // Silence unused field warning.
 731     static_assert(sizeof(padding_) == sizeof(uintptr_t));
 732
 733     // Sanity check Shape size is what we expect.
 734 #ifdef JS_64BIT
 735     static_assert(sizeof(SizedShape) == 4 * sizeof(void*));
 736 #else
 737     static_assert(sizeof(SizedShape) == 6 * sizeof(void*));
 738 #endif
 739
 740     // All shape kinds must have the same size.
 741     static_assert(sizeof(NativeShape) == sizeof(SizedShape));
 742     static_assert(sizeof(SharedShape) == sizeof(SizedShape));
 743     static_assert(sizeof(DictionaryShape) == sizeof(SizedShape));
 744     static_assert(sizeof(ProxyShape) == sizeof(SizedShape));
 745     static_assert(sizeof(WasmGCShape) == sizeof(SizedShape));
 746   }
 747 };
 748
 749 inline NativeShape& js::Shape::asNative() {
 750   MOZ_ASSERT(isNative());
 751   return *static_cast<NativeShape*>(this);
 752 }
 753
 754 inline SharedShape& js::Shape::asShared() {
 755   MOZ_ASSERT(isShared());
 756   return *static_cast<SharedShape*>(this);
 757 }
 758
 759 inline DictionaryShape& js::Shape::asDictionary() {
 760   MOZ_ASSERT(isDictionary());
 761   return *static_cast<DictionaryShape*>(this);
 762 }
 763
 764 inline WasmGCShape& js::Shape::asWasmGC() {
 765   MOZ_ASSERT(isWasmGC());
 766   return *static_cast<WasmGCShape*>(this);
 767 }
 768
 769 inline const NativeShape& js::Shape::asNative() const {
 770   MOZ_ASSERT(isNative());
 771   return *static_cast<const NativeShape*>(this);
 772 }
 773
 774 inline const SharedShape& js::Shape::asShared() const {
 775   MOZ_ASSERT(isShared());
 776   return *static_cast<const SharedShape*>(this);
 777 }
 778
 779 inline const DictionaryShape& js::Shape::asDictionary() const {
 780   MOZ_ASSERT(isDictionary());
 781   return *static_cast<const DictionaryShape*>(this);
 782 }
 783
 784 inline const WasmGCShape& js::Shape::asWasmGC() const {
 785   MOZ_ASSERT(isWasmGC());
 786   return *static_cast<const WasmGCShape*>(this);
 787 }
 788
 789 // Iterator for iterating over a shape's properties. It can be used like this:
 790 //
 791 //   for (ShapePropertyIter<NoGC> iter(nobj->shape()); !iter.done(); iter++) {
 792 //     PropertyKey key = iter->key();
 793 //     if (iter->isDataProperty() && iter->enumerable()) { .. }
 794 //   }
 795 //
 796 // Properties are iterated in reverse order (i.e., iteration starts at the most
 797 // recently added property).
 798 template <AllowGC allowGC>
 799 class MOZ_RAII ShapePropertyIter {
 800   typename MaybeRooted<PropMap*, allowGC>::RootType map_;
 801   uint32_t mapLength_;
 802   const bool isDictionary_;
 803
 804  protected:
 805   ShapePropertyIter(JSContext* cx, NativeShape* shape, bool isDictionary)
 806       : map_(cx, shape->propMap()),
 807         mapLength_(shape->propMapLength()),
 808         isDictionary_(isDictionary) {
 809     static_assert(allowGC == CanGC);
 810     MOZ_ASSERT(shape->isDictionary() == isDictionary);
 811     MOZ_ASSERT(shape->isNative());
 812   }
 813   ShapePropertyIter(NativeShape* shape, bool isDictionary)
 814       : map_(nullptr, shape->propMap()),
 815         mapLength_(shape->propMapLength()),
 816         isDictionary_(isDictionary) {
 817     static_assert(allowGC == NoGC);
 818     MOZ_ASSERT(shape->isDictionary() == isDictionary);
 819     MOZ_ASSERT(shape->isNative());
 820   }
 821
 822  public:
 823   ShapePropertyIter(JSContext* cx, NativeShape* shape)
 824       : ShapePropertyIter(cx, shape, shape->isDictionary()) {}
 825
 826   explicit ShapePropertyIter(NativeShape* shape)
 827       : ShapePropertyIter(shape, shape->isDictionary()) {}
 828
 829   // Deleted constructors: use SharedShapePropertyIter instead.
 830   ShapePropertyIter(JSContext* cx, SharedShape* shape) = delete;
 831   explicit ShapePropertyIter(SharedShape* shape) = delete;
 832
 833   bool done() const { return mapLength_ == 0; }
 834
 835   void operator++(int) {
 836     do {
 837       MOZ_ASSERT(!done());
 838       if (mapLength_ > 1) {
 839         mapLength_--;
 840       } else if (map_->hasPrevious()) {
 841         map_ = map_->asLinked()->previous();
 842         mapLength_ = PropMap::Capacity;
 843       } else {
 844         // Done iterating.
 845         map_ = nullptr;
 846         mapLength_ = 0;
 847         return;
 848       }
 849       // Dictionary maps can have "holes" for removed properties, so keep going
 850       // until we find a non-hole slot.
 851     } while (MOZ_UNLIKELY(isDictionary_ && !map_->hasKey(mapLength_ - 1)));
 852   }
 853
 854   PropertyInfoWithKey get() const {
 855     MOZ_ASSERT(!done());
 856     return map_->getPropertyInfoWithKey(mapLength_ - 1);
 857   }
 858
 859   PropertyInfoWithKey operator*() const { return get(); }
 860
 861   // Fake pointer struct to make operator-> work.
 862   // See https://stackoverflow.com/a/52856349.
 863   struct FakePtr {
 864     PropertyInfoWithKey val_;
 865     const PropertyInfoWithKey* operator->() const { return &val_; }
 866   };
 867   FakePtr operator->() const { return {get()}; }
 868 };
 869
 870 // Optimized version of ShapePropertyIter for non-dictionary shapes. It passes
 871 // `false` for `isDictionary_`, which will let the compiler optimize away the
 872 // loop structure in ShapePropertyIter::operator++.
 873 template <AllowGC allowGC>
 874 class MOZ_RAII SharedShapePropertyIter : public ShapePropertyIter<allowGC> {
 875  public:
 876   SharedShapePropertyIter(JSContext* cx, SharedShape* shape)
 877       : ShapePropertyIter<allowGC>(cx, shape, /* isDictionary = */ false) {}
 878
 879   explicit SharedShapePropertyIter(SharedShape* shape)
 880       : ShapePropertyIter<allowGC>(shape, /* isDictionary = */ false) {}
 881 };
 882
 883 }  // namespace js
 884
 885 // JS::ubi::Nodes can point to Shapes and BaseShapes; they're js::gc::Cell
 886 // instances that occupy a compartment.
 887 namespace JS {
 888 namespace ubi {
 889
 890 template <>
 891 class Concrete<js::Shape> : TracerConcrete<js::Shape> {
 892  protected:
 893   explicit Concrete(js::Shape* ptr) : TracerConcrete<js::Shape>(ptr) {}
 894
 895  public:
 896   static void construct(void* storage, js::Shape* ptr) {
 897     new (storage) Concrete(ptr);
 898   }
 899
 900   Size size(mozilla::MallocSizeOf mallocSizeOf) const override;
 901
 902   const char16_t* typeName() const override { return concreteTypeName; }
 903   static const char16_t concreteTypeName[];
 904 };
 905
 906 template <>
 907 class Concrete<js::BaseShape> : TracerConcrete<js::BaseShape> {
 908  protected:
 909   explicit Concrete(js::BaseShape* ptr) : TracerConcrete<js::BaseShape>(ptr) {}
 910
 911  public:
 912   static void construct(void* storage, js::BaseShape* ptr) {
 913     new (storage) Concrete(ptr);
 914   }
 915
 916   Size size(mozilla::MallocSizeOf mallocSizeOf) const override;
 917
 918   const char16_t* typeName() const override { return concreteTypeName; }
 919   static const char16_t concreteTypeName[];
 920 };
 921
 922 }  // namespace ubi
 923 }  // namespace JS
 924
 925 #endif /* vm_Shape_h */