tor-browser

PropMap.h (43145B)

---

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef vm_PropMap_h
#define vm_PropMap_h

#include "gc/Barrier.h"
#include "gc/Cell.h"
#include "gc/Policy.h"
#include "js/TypeDecls.h"
#include "js/UbiNode.h"
#include "js/Utility.h"  // JS::UniqueChars
#include "vm/ObjectFlags.h"
#include "vm/PropertyInfo.h"
#include "vm/PropertyKey.h"

// [SMDOC] Property Maps
//
// Property maps are used to store information about native object properties.
// Each property map represents an ordered list of (PropertyKey, PropertyInfo)
// tuples.
//
// Each property map can store up to 8 properties (see PropMap::Capacity). To
// store more than eight properties, multiple maps must be linked together with
// the |previous| pointer.
//
// Shapes and Property Maps
// ------------------------
// Native object shapes represent property information as a (PropMap*, length)
// tuple. When there are no properties yet, the shape's map will be nullptr and
// the length is zero.
//
// For example, consider the following objects:
//
//   o1 = {x: 1, y: 2}
//   o2 = {x: 3, y: 4, z: 5}
//
// This is stored as follows:
//
//   +-------------+      +--------------+     +-------------------+
//   | JSObject o1 |      | Shape S1     |     | PropMap M1        |
//   |-------------+      +--------------+     +-------------------+
//   | shape: S1  -+--->  | map: M1     -+--+> | key 0: x (slot 0) |
//   | slot 0: 1   |      | mapLength: 2 |  |  | key 1: y (slot 1) |
//   | slot 1: 2   |      +--------------+  |  | key 2: z (slot 2) |
//   +-------------+                        |  | ...               |
//                                          |  +-------------------+
//                                          |
//   +-------------+      +--------------+  |
//   | JSObject o2 |      | Shape S2     |  |
//   |-------------+      +--------------+  |
//   | shape: S2  -+--->  | map: M1     -+--+
//   | slot 0: 3   |      | mapLength: 3 |
//   | slot 1: 4   |      +--------------+
//   | slot 2: 5   |
//   +-------------+
//
// There's a single map M1 shared by shapes S1 and S2. Shape S1 includes only
// the first two properties and shape S2 includes all three properties.
//
// Class Hierarchy
// ---------------
// Property maps have the following C++ class hierarchy:
//
//   PropMap (abstract)
//    |
//    +-- SharedPropMap (abstract)
//    |      |
//    |      +-- CompactPropMap
//    |      |
//    |      +-- NormalPropMap
//    |
//    +-- DictionaryPropMap
//
// * PropMap: base class. It has a flags word and an array of PropertyKeys.
//
// * SharedPropMap: base class for all shared property maps. See below for more
//                  information on shared maps.
//
// * CompactPropMap: a shared map that stores its information more compactly
//                   than the other maps. It saves four words by not storing a
//                   PropMapTable, previous pointer, and by using a more compact
//                   PropertyInfo type for slot numbers that fit in one byte.
//
// * NormalPropMap: a shared map, used when CompactPropMap can't be used.
//
// * DictionaryPropMap: an unshared map (used by a single object/shape). See
//                      below for more information on dictionary maps.
//
// Secondary hierarchy
// -------------------
// NormalPropMap and DictionaryPropMap store property information in the same
// way. This means property lookups don't have to distinguish between these two
// types. This is represented with a second class hierarchy:
//
//   PropMap (abstract)
//    |
//    +-- CompactPropMap
//    |
//    +-- LinkedPropMap (NormalPropMap or DictionaryPropMap)
//
// Property lookup and property iteration are very performance sensitive and use
// this Compact vs Linked "view" so that they don't have to handle the three map
// types separately.
//
// LinkedPropMap also stores the PropMapTable and a pointer to the |previous|
// map. Compact maps don't have these fields.
//
// To summarize these map types:
//
//   +-------------------+-------------+--------+
//   | Concrete type     | Shared/tree | Linked |
//   +-------------------+-------------+--------+
//   | CompactPropMap    | yes         | no     |
//   | NormalPropMap     | yes         | yes    |
//   | DictionaryPropMap | no          | yes    |
//   +-------------------+-------------+--------+
//
// PropMapTable
// ------------
// Finding the PropertyInfo for a particular PropertyKey requires a linear
// search if the map is small. For larger maps we can create a PropMapTable, a
// hash table that maps from PropertyKey to PropMap + index, to speed up
// property lookups.
//
// To save memory, property map tables can be discarded on GC and recreated when
// needed. AutoKeepPropMapTables can be used to avoid discarding tables in a
// particular zone. Methods to access a PropMapTable take either an
// AutoCheckCannotGC or AutoKeepPropMapTables argument, to help ensure tables
// are not purged while we're using them.
//
// Shared Property Maps
// --------------------
// Shared property maps can be shared per-Zone by objects with the same property
// keys, flags, and slot numbers. To make this work, shared maps form a tree:
//
// - Each Zone has a table that maps from first PropertyKey + PropertyInfo to
//   a SharedPropMap that begins with that property. This is used to lookup the
//   the map to use when adding the first property.
//   See ShapeZone::initialPropMaps.
//
// - When adding a property other than the first one, the property is stored in
//   the next entry of the same map when possible. If the map is full or the
//   next entry already stores a different property, a child map is created and
//   linked to the parent map.
//
// For example, imagine we want to create these objects:
//
//   o1 = {x: 1, y: 2, z: 3}
//   o2 = {x: 1, y: 2, foo: 4}
//
// This will result in the following maps being created:
//
//     +---------------------+    +---------------------+
//     | SharedPropMap M1    |    | SharedPropMap M2    |
//     +---------------------+    +---------------------+
//     | Child M2 (index 1) -+--> | Parent M1 (index 1) |
//     +---------------------+    +---------------------+
//     | 0: x                |    | 0: x                |
//     | 1: y                |    | 1: y                |
//     | 2: z                |    | 2: foo              |
//     | ...                 |    | ...                 |
//     +---------------------+    +---------------------+
//
// M1 is the map used for initial property "x". Properties "y" and "z" can be
// stored inline. When later adding "foo" following "y", the map has to be
// forked: a child map M2 is created and M1 remembers this transition at
// property index 1 so that M2 will be used the next time properties "x", "y",
// and "foo" are added to an object.
//
// Shared maps contain a TreeData struct that stores the parent and children
// links for the SharedPropMap tree. The parent link is a tagged pointer that
// stores both the parent map and the property index of the last used property
// in the parent map before the branch. The children are stored similarly: the
// parent map can store a single child map and index, or a set of children.
// See SharedChildrenPtr.
//
// Looking up a child map can then be done based on the index of the last
// property in the parent map and the new property's key and flags. So for the
// example above, the lookup key for M1 => M2 is (index 1, "foo", <flags>).
//
// Note: shared maps can have both a |previous| map and a |parent| map. They are
// equal when the previous map was full, but can be different maps when
// branching in the middle of a map like in the example above: M2 has parent M1
// but does not have a |previous| map (because it only has three properties).
//
// Dictionary Property Maps
// ------------------------
// Certain operations can't be implemented (efficiently) for shared property
// maps, for example changing or deleting a property other than the last one.
// When this happens the map is copied as a DictionaryPropMap.
//
// Dictionary maps are unshared so can be mutated in place (after generating a
// new shape for the object).
//
// Unlike shared maps, dictionary maps can have holes between two property keys
// after removing a property. When there are more holes than properties, the
// map is compacted. See DictionaryPropMap::maybeCompact.

namespace js {

enum class IntegrityLevel;

class DictionaryPropMap;
class SharedPropMap;
class LinkedPropMap;
class CompactPropMap;
class NormalPropMap;

class JS_PUBLIC_API GenericPrinter;
class JSONPrinter;

// Template class for storing a PropMap* and a property index as tagged pointer.
template <typename T>
class MapAndIndex {
 uintptr_t data_ = 0;

 static constexpr uintptr_t IndexMask = 0b111;

public:
 MapAndIndex() = default;

 MapAndIndex(const T* map, uint32_t index) : data_(uintptr_t(map) | index) {
   MOZ_ASSERT((uintptr_t(map) & IndexMask) == 0);
   MOZ_ASSERT(index <= IndexMask);
 }
 explicit MapAndIndex(uintptr_t data) : data_(data) {}

 void setNone() { data_ = 0; }

 bool isNone() const { return data_ == 0; }

 uintptr_t raw() const { return data_; }
 T* maybeMap() const { return reinterpret_cast<T*>(data_ & ~IndexMask); }

 uint32_t index() const {
   MOZ_ASSERT(!isNone());
   return data_ & IndexMask;
 }
 T* map() const {
   MOZ_ASSERT(!isNone());
   return maybeMap();
 }

 inline PropertyInfo propertyInfo() const;

 bool operator==(const MapAndIndex<T>& other) const {
   return data_ == other.data_;
 }
 bool operator!=(const MapAndIndex<T>& other) const {
   return !operator==(other);
 }
} JS_HAZ_GC_POINTER;
using PropMapAndIndex = MapAndIndex<PropMap>;
using SharedPropMapAndIndex = MapAndIndex<SharedPropMap>;

struct SharedChildrenHasher;
using SharedChildrenSet =
   HashSet<SharedPropMapAndIndex, SharedChildrenHasher, SystemAllocPolicy>;

// Children of shared maps. This is either:
//
// - None (no children)
// - SingleMapAndIndex (one child map, including the property index of the last
//   property before the branch)
// - SharedChildrenSet (multiple children)
//
// Because SingleMapAndIndex use all bits, this relies on the HasChildrenSet
// flag in the map to distinguish the latter two cases.
class SharedChildrenPtr {
 uintptr_t data_ = 0;

public:
 bool isNone() const { return data_ == 0; }
 void setNone() { data_ = 0; }

 void setSingleChild(SharedPropMapAndIndex child) { data_ = child.raw(); }
 void setChildrenSet(SharedChildrenSet* set) { data_ = uintptr_t(set); }

 SharedPropMapAndIndex toSingleChild() const {
   MOZ_ASSERT(!isNone());
   return SharedPropMapAndIndex(data_);
 }

 SharedChildrenSet* toChildrenSet() const {
   MOZ_ASSERT(!isNone());
   return reinterpret_cast<SharedChildrenSet*>(data_);
 }
} JS_HAZ_GC_POINTER;

// Ensures no property map tables are purged in the current zone.
class MOZ_RAII AutoKeepPropMapTables {
 JSContext* cx_;
 bool prev_;

public:
 void operator=(const AutoKeepPropMapTables&) = delete;
 AutoKeepPropMapTables(const AutoKeepPropMapTables&) = delete;
 explicit inline AutoKeepPropMapTables(JSContext* cx);
 inline ~AutoKeepPropMapTables();
};

// Hash table to optimize property lookups on larger maps. This maps from
// PropertyKey to PropMapAndIndex.
class PropMapTable {
 struct Hasher {
   using Key = PropMapAndIndex;
   using Lookup = PropertyKey;
   static MOZ_ALWAYS_INLINE HashNumber hash(PropertyKey key);
   static MOZ_ALWAYS_INLINE bool match(PropMapAndIndex, PropertyKey key);
 };

 // Small lookup cache. This has a hit rate of 30-60% on most workloads and is
 // a lot faster than the full HashSet lookup.
 struct CacheEntry {
   PropertyKey key;
   PropMapAndIndex result;
 };
 static constexpr uint32_t NumCacheEntries = 2;
 CacheEntry cacheEntries_[NumCacheEntries];

 using Set = HashSet<PropMapAndIndex, Hasher, SystemAllocPolicy>;
 Set set_;

 void setCacheEntry(PropertyKey key, PropMapAndIndex entry) {
   for (uint32_t i = 0; i < NumCacheEntries; i++) {
     if (cacheEntries_[i].key == key) {
       cacheEntries_[i].result = entry;
       return;
     }
   }
 }
 bool lookupInCache(PropertyKey key, PropMapAndIndex* result) const {
   for (uint32_t i = 0; i < NumCacheEntries; i++) {
     if (cacheEntries_[i].key == key) {
       *result = cacheEntries_[i].result;
#ifdef DEBUG
       auto p = lookupRaw(key);
       MOZ_ASSERT(*result == (p ? *p : PropMapAndIndex()));
#endif
       return true;
     }
   }
   return false;
 }
 void addToCache(PropertyKey key, Set::Ptr p) {
   for (uint32_t i = NumCacheEntries - 1; i > 0; i--) {
     cacheEntries_[i] = cacheEntries_[i - 1];
     MOZ_ASSERT(cacheEntries_[i].key != key);
   }
   cacheEntries_[0].key = key;
   cacheEntries_[0].result = p ? *p : PropMapAndIndex();
 }

public:
 using Ptr = Set::Ptr;

 PropMapTable() = default;
 ~PropMapTable() = default;

 uint32_t entryCount() const { return set_.count(); }

 // This counts the PropMapTable object itself (which must be heap-allocated)
 // and its HashSet.
 size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
   return mallocSizeOf(this) + set_.shallowSizeOfExcludingThis(mallocSizeOf);
 }

 // init() is fallible and reports OOM to the context.
 bool init(JSContext* cx, LinkedPropMap* map);

 MOZ_ALWAYS_INLINE PropMap* lookup(PropMap* map, uint32_t mapLength,
                                   PropertyKey key, uint32_t* index);

 Set::Ptr lookupRaw(PropertyKey key) const { return set_.lookup(key); }
#ifdef DEBUG
 Set::Ptr readonlyThreadsafeLookup(PropertyKey key) const {
   return set_.readonlyThreadsafeLookup(key);
 }
#endif

 bool add(JSContext* cx, PropertyKey key, PropMapAndIndex entry) {
   if (!set_.putNew(key, entry)) {
     ReportOutOfMemory(cx);
     return false;
   }
   setCacheEntry(key, entry);
   return true;
 }

 void purgeCache() {
   for (uint32_t i = 0; i < NumCacheEntries; i++) {
     cacheEntries_[i] = CacheEntry();
   }
 }

 void remove(Ptr ptr) {
   set_.remove(ptr);
   purgeCache();
 }

 void replaceEntry(Ptr ptr, PropertyKey key, PropMapAndIndex newEntry) {
   MOZ_ASSERT(*ptr != newEntry);
   set_.replaceKey(ptr, key, newEntry);
   setCacheEntry(key, newEntry);
 }

 void trace(JSTracer* trc);
#ifdef JSGC_HASH_TABLE_CHECKS
 void checkAfterMovingGC(JS::Zone* zone);
#endif
};

class PropMap : public gc::TenuredCellWithFlags {
public:
 // Number of properties that can be stored in each map. This must be small
 // enough so that every index fits in a tagged PropMap* pointer (MapAndIndex).
 static constexpr size_t Capacity = 8;

protected:
 static_assert(gc::CellFlagBitsReservedForGC == 3,
               "PropMap must reserve enough bits for Cell");

 enum Flags {
   // Set if this is a CompactPropMap.
   IsCompactFlag = 1 << 3,

   // Set if this map has a non-null previous map pointer. Never set for
   // compact maps because they don't have a previous field.
   HasPrevFlag = 1 << 4,

   // Set if this is a DictionaryPropMap.
   IsDictionaryFlag = 1 << 5,

   // Set if this map can have a table. Never set for compact maps. Always set
   // for dictionary maps.
   CanHaveTableFlag = 1 << 6,

   // If set, this SharedPropMap has a SharedChildrenSet. Else it either has no
   // children or a single child. See SharedChildrenPtr. Never set for
   // dictionary maps.
   HasChildrenSetFlag = 1 << 7,

   // If set, this SharedPropMap was once converted to dictionary mode. This is
   // only used for heuristics. Never set for dictionary maps.
   HadDictionaryConversionFlag = 1 << 8,

   // For SharedPropMap this stores the number of previous maps, clamped to
   // NumPreviousMapsMax. This is used for heuristics.
   NumPreviousMapsMax = 0x7f,
   NumPreviousMapsShift = 9,
   NumPreviousMapsMask = NumPreviousMapsMax << NumPreviousMapsShift,
 };

 template <typename KnownF, typename UnknownF>
 static void forEachPropMapFlag(uintptr_t flags, KnownF known,
                                UnknownF unknown);

 // Flags word, stored in the cell header. Note that this hides the
 // Cell::flags() method.
 uintptr_t flags() const { return headerFlagsField(); }

private:
 GCPtr<PropertyKey> keys_[Capacity];

protected:
 PropMap() = default;

 void initKey(uint32_t index, PropertyKey key) {
   MOZ_ASSERT(index < Capacity);
   keys_[index].init(key);
 }
 void setKey(uint32_t index, PropertyKey key) {
   MOZ_ASSERT(index < Capacity);
   keys_[index] = key;
 }

public:
 bool isCompact() const { return flags() & IsCompactFlag; }
 bool isLinked() const { return !isCompact(); }
 bool isDictionary() const { return flags() & IsDictionaryFlag; }
 bool isShared() const { return !isDictionary(); }
 bool isNormal() const { return isShared() && !isCompact(); }

 bool hasPrevious() const { return flags() & HasPrevFlag; }
 bool canHaveTable() const { return flags() & CanHaveTableFlag; }

 inline CompactPropMap* asCompact();
 inline const CompactPropMap* asCompact() const;

 inline LinkedPropMap* asLinked();
 inline const LinkedPropMap* asLinked() const;

 inline NormalPropMap* asNormal();
 inline const NormalPropMap* asNormal() const;

 inline SharedPropMap* asShared();
 inline const SharedPropMap* asShared() const;

 inline DictionaryPropMap* asDictionary();
 inline const DictionaryPropMap* asDictionary() const;

 bool hasKey(uint32_t index) const {
   MOZ_ASSERT(index < Capacity);
   return !keys_[index].isVoid();
 }
 PropertyKey getKey(uint32_t index) const {
   MOZ_ASSERT(index < Capacity);
   return keys_[index];
 }

 uint32_t approximateEntryCount() const;

#if defined(DEBUG) || defined(JS_JITSPEW)
 void dump() const;
 void dump(js::GenericPrinter& out) const;
 void dump(js::JSONPrinter& json) const;

 void dumpFields(js::JSONPrinter& json) const;
 void dumpFieldsAt(js::JSONPrinter& json, uint32_t index) const;
 void dumpDescriptorStringContentAt(js::GenericPrinter& out,
                                    uint32_t index) const;
 JS::UniqueChars getPropertyNameAt(uint32_t index) const;
#endif

#ifdef DEBUG
 void checkConsistency(NativeObject* obj) const;
#endif

 void addSizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf,
                             size_t* children, size_t* tables) const;

 inline PropertyInfo getPropertyInfo(uint32_t index) const;

 PropertyInfoWithKey getPropertyInfoWithKey(uint32_t index) const {
   return PropertyInfoWithKey(getPropertyInfo(index), getKey(index));
 }

 MOZ_ALWAYS_INLINE PropMap* lookupLinear(uint32_t mapLength, PropertyKey key,
                                         uint32_t* index);

 MOZ_ALWAYS_INLINE PropMap* lookupPure(uint32_t mapLength, PropertyKey key,
                                       uint32_t* index);

 MOZ_ALWAYS_INLINE PropMap* lookup(JSContext* cx, uint32_t mapLength,
                                   PropertyKey key, uint32_t* index);

 static inline bool lookupForRemove(JSContext* cx, PropMap* map,
                                    uint32_t mapLength, PropertyKey key,
                                    const AutoKeepPropMapTables& keep,
                                    PropMap** propMap, uint32_t* propIndex,
                                    PropMapTable** table,
                                    PropMapTable::Ptr* ptr);

 static const JS::TraceKind TraceKind = JS::TraceKind::PropMap;

 void traceChildren(JSTracer* trc);
};

class SharedPropMap : public PropMap {
 friend class PropMap;

protected:
 // Shared maps are stored in a tree structure. Each shared map has a TreeData
 // struct linking the map to its parent and children. Initial maps (the ones
 // stored in ShapeZone's initialPropMaps table) don't have a parent.
 struct TreeData {
   SharedChildrenPtr children;
   SharedPropMapAndIndex parent;

   void setParent(SharedPropMap* map, uint32_t index) {
     parent = SharedPropMapAndIndex(map, index);
   }
 };

private:
 static SharedPropMap* create(JSContext* cx, Handle<SharedPropMap*> prev,
                              HandleId id, PropertyInfo prop);
 static SharedPropMap* createInitial(JSContext* cx, HandleId id,
                                     PropertyInfo prop);
 static SharedPropMap* clone(JSContext* cx, Handle<SharedPropMap*> map,
                             uint32_t length);

 inline void initProperty(uint32_t index, PropertyKey key, PropertyInfo prop);

 static bool addPropertyInternal(JSContext* cx,
                                 MutableHandle<SharedPropMap*> map,
                                 uint32_t* mapLength, HandleId id,
                                 PropertyInfo prop);

 bool addChild(JSContext* cx, SharedPropMapAndIndex child, HandleId id,
               PropertyInfo prop);
 SharedPropMap* lookupChild(uint32_t length, HandleId id, PropertyInfo prop);

protected:
 void initNumPreviousMaps(uint32_t value) {
   MOZ_ASSERT((flags() >> NumPreviousMapsShift) == 0);
   // Clamp to NumPreviousMapsMax. This is okay because this value is only used
   // for heuristics.
   if (value > NumPreviousMapsMax) {
     value = NumPreviousMapsMax;
   }
   setHeaderFlagBits(value << NumPreviousMapsShift);
 }

 bool hasChildrenSet() const { return flags() & HasChildrenSetFlag; }
 void setHasChildrenSet() { setHeaderFlagBits(HasChildrenSetFlag); }
 void clearHasChildrenSet() { clearHeaderFlagBits(HasChildrenSetFlag); }

 void setHadDictionaryConversion() {
   setHeaderFlagBits(HadDictionaryConversionFlag);
 }

public:
 // Heuristics used when adding a property via NativeObject::addProperty and
 // friends:
 //
 // * If numPreviousMaps >= NumPrevMapsForAddConsiderDictionary, consider
 //   converting the object to a dictionary object based on other heuristics.
 //
 // * If numPreviousMaps >= NumPrevMapsForAddAlwaysDictionary, always convert
 //   the object to a dictionary object.
 static constexpr size_t NumPrevMapsConsiderDictionary = 32;
 static constexpr size_t NumPrevMapsAlwaysDictionary = 100;

 static_assert(NumPrevMapsConsiderDictionary < NumPreviousMapsMax);
 static_assert(NumPrevMapsAlwaysDictionary < NumPreviousMapsMax);

 // The number of properties that can definitely be added to an object without
 // triggering dictionary mode conversion in NativeObject::addProperty.
 static constexpr size_t MaxPropsForNonDictionary =
     NumPrevMapsConsiderDictionary * Capacity;

 bool isDictionary() const = delete;
 bool isShared() const = delete;
 SharedPropMap* asShared() = delete;
 const SharedPropMap* asShared() const = delete;

 bool hadDictionaryConversion() const {
   return flags() & HadDictionaryConversionFlag;
 }

 uint32_t numPreviousMaps() const {
   uint32_t val = (flags() & NumPreviousMapsMask) >> NumPreviousMapsShift;
   MOZ_ASSERT_IF(hasPrevious(), val > 0);
   return val;
 }

 MOZ_ALWAYS_INLINE bool shouldConvertToDictionaryForAdd() const;

 void fixupAfterMovingGC();
 inline void sweep(JS::GCContext* gcx);
 inline void finalize(JS::GCContext* gcx);

 static inline void getPrevious(MutableHandle<SharedPropMap*> map,
                                uint32_t* mapLength);

 bool matchProperty(uint32_t index, PropertyKey key, PropertyInfo prop) const {
   return getKey(index) == key && getPropertyInfo(index) == prop;
 }

 inline TreeData& treeDataRef();
 inline const TreeData& treeDataRef() const;

 void removeChild(JS::GCContext* gcx, SharedPropMap* child);

 uint32_t lastUsedSlot(uint32_t mapLength) const {
   return getPropertyInfo(mapLength - 1).maybeSlot();
 }

 // Number of slots required for objects with this map/mapLength.
 static uint32_t slotSpan(const JSClass* clasp, const SharedPropMap* map,
                          uint32_t mapLength) {
   MOZ_ASSERT(clasp->isNativeObject());
   uint32_t numReserved = JSCLASS_RESERVED_SLOTS(clasp);
   if (!map) {
     MOZ_ASSERT(mapLength == 0);
     return numReserved;
   }
   uint32_t lastSlot = map->lastUsedSlot(mapLength);
   if (lastSlot == SHAPE_INVALID_SLOT) {
     // The object only has custom data properties.
     return numReserved;
   }
   // Some builtin objects store properties in reserved slots. Make sure the
   // slot span >= numReserved. See addPropertyInReservedSlot.
   return std::max(lastSlot + 1, numReserved);
 }

 static uint32_t indexOfNextProperty(uint32_t index) {
   MOZ_ASSERT(index < PropMap::Capacity);
   return (index + 1) % PropMap::Capacity;
 }

 // Add a new property to this map. Returns the new map/mapLength, slot number,
 // and object flags.
 static bool addProperty(JSContext* cx, const JSClass* clasp,
                         MutableHandle<SharedPropMap*> map,
                         uint32_t* mapLength, HandleId id, PropertyFlags flags,
                         ObjectFlags* objectFlags, uint32_t* slot);

 // Like addProperty, but for when the slot number is a reserved slot. A few
 // builtin objects use this for initial properties.
 static bool addPropertyInReservedSlot(JSContext* cx, const JSClass* clasp,
                                       MutableHandle<SharedPropMap*> map,
                                       uint32_t* mapLength, HandleId id,
                                       PropertyFlags flags, uint32_t slot,
                                       ObjectFlags* objectFlags);

 // Like addProperty, but for when the caller already knows the slot number to
 // use (or wants to assert this exact slot number is used).
 static bool addPropertyWithKnownSlot(JSContext* cx, const JSClass* clasp,
                                      MutableHandle<SharedPropMap*> map,
                                      uint32_t* mapLength, HandleId id,
                                      PropertyFlags flags, uint32_t slot,
                                      ObjectFlags* objectFlags);

 // Like addProperty, but for adding a custom data property.
 static bool addCustomDataProperty(JSContext* cx, const JSClass* clasp,
                                   MutableHandle<SharedPropMap*> map,
                                   uint32_t* mapLength, HandleId id,
                                   PropertyFlags flags,
                                   ObjectFlags* objectFlags);

 // Freeze or seal all properties by creating a new shared map. Returns the new
 // map and object flags.
 static bool freezeOrSealProperties(JSContext* cx, IntegrityLevel level,
                                    const JSClass* clasp,
                                    MutableHandle<SharedPropMap*> map,
                                    uint32_t mapLength,
                                    ObjectFlags* objectFlags);

 // Create a new dictionary map as copy of this map.
 static DictionaryPropMap* toDictionaryMap(JSContext* cx,
                                           Handle<SharedPropMap*> map,
                                           uint32_t length);

#if defined(DEBUG) || defined(JS_JITSPEW)
 void dumpOwnFields(js::JSONPrinter& json) const;
#endif
};

class CompactPropMap final : public SharedPropMap {
 CompactPropertyInfo propInfos_[Capacity];
 TreeData treeData_;

 friend class PropMap;
 friend class SharedPropMap;
 friend class DictionaryPropMap;
 friend class js::gc::CellAllocator;

 CompactPropMap(JS::Handle<PropertyKey> key, PropertyInfo prop) {
   setHeaderFlagBits(IsCompactFlag);
   initProperty(0, key, prop);
 }

 CompactPropMap(JS::Handle<CompactPropMap*> orig, uint32_t length) {
   setHeaderFlagBits(IsCompactFlag);
   for (uint32_t i = 0; i < length; i++) {
     initKey(i, orig->getKey(i));
     propInfos_[i] = orig->propInfos_[i];
   }
 }

 void initProperty(uint32_t index, PropertyKey key, PropertyInfo prop) {
   MOZ_ASSERT(!hasKey(index));
   initKey(index, key);
   propInfos_[index] = CompactPropertyInfo(prop);
 }

 TreeData& treeDataRef() { return treeData_; }
 const TreeData& treeDataRef() const { return treeData_; }

public:
 bool isDictionary() const = delete;
 bool isShared() const = delete;
 bool isCompact() const = delete;
 bool isNormal() const = delete;
 bool isLinked() const = delete;
 CompactPropMap* asCompact() = delete;
 const CompactPropMap* asCompact() const = delete;

 PropertyInfo getPropertyInfo(uint32_t index) const {
   MOZ_ASSERT(hasKey(index));
   return PropertyInfo(propInfos_[index]);
 }
};

// Layout shared by NormalPropMap and DictionaryPropMap.
class LinkedPropMap final : public PropMap {
 friend class PropMap;
 friend class SharedPropMap;
 friend class NormalPropMap;
 friend class DictionaryPropMap;

 struct Data {
   GCPtr<PropMap*> previous;
   PropMapTable* table = nullptr;
   PropertyInfo propInfos[Capacity];

   explicit Data(PropMap* prev) : previous(prev) {}
 };
 Data data_;

 bool createTable(JSContext* cx);
 void handOffTableTo(LinkedPropMap* next);

public:
 bool isCompact() const = delete;
 bool isLinked() const = delete;
 LinkedPropMap* asLinked() = delete;
 const LinkedPropMap* asLinked() const = delete;

 PropMap* previous() const { return data_.previous; }

 bool hasTable() const { return data_.table != nullptr; }

 PropMapTable* maybeTable(JS::AutoCheckCannotGC& nogc) const {
   return data_.table;
 }
 PropMapTable* ensureTable(JSContext* cx, const JS::AutoCheckCannotGC& nogc) {
   if (!data_.table && MOZ_UNLIKELY(!createTable(cx))) {
     return nullptr;
   }
   return data_.table;
 }
 PropMapTable* ensureTable(JSContext* cx, const AutoKeepPropMapTables& keep) {
   if (!data_.table && MOZ_UNLIKELY(!createTable(cx))) {
     return nullptr;
   }
   return data_.table;
 }

 void purgeTable(JS::GCContext* gcx);

 void purgeTableCache() {
   if (data_.table) {
     data_.table->purgeCache();
   }
 }

#ifdef DEBUG
 bool canSkipMarkingTable();
#endif

 PropertyInfo getPropertyInfo(uint32_t index) const {
   MOZ_ASSERT(hasKey(index));
   return data_.propInfos[index];
 }

#if defined(DEBUG) || defined(JS_JITSPEW)
 void dumpOwnFields(js::JSONPrinter& json) const;
#endif
};

class NormalPropMap final : public SharedPropMap {
 friend class PropMap;
 friend class SharedPropMap;
 friend class DictionaryPropMap;
 friend class js::gc::CellAllocator;

 LinkedPropMap::Data linkedData_;
 TreeData treeData_;

 NormalPropMap(JS::Handle<SharedPropMap*> prev, PropertyKey key,
               PropertyInfo prop)
     : linkedData_(prev) {
   if (prev) {
     setHeaderFlagBits(HasPrevFlag);
     initNumPreviousMaps(prev->numPreviousMaps() + 1);
     if (prev->hasPrevious()) {
       setHeaderFlagBits(CanHaveTableFlag);
     }
   }
   initProperty(0, key, prop);
 }

 NormalPropMap(JS::Handle<NormalPropMap*> orig, uint32_t length)
     : linkedData_(orig->previous()) {
   if (orig->hasPrevious()) {
     setHeaderFlagBits(HasPrevFlag);
   }
   if (orig->canHaveTable()) {
     setHeaderFlagBits(CanHaveTableFlag);
   }
   initNumPreviousMaps(orig->numPreviousMaps());
   for (uint32_t i = 0; i < length; i++) {
     initProperty(i, orig->getKey(i), orig->getPropertyInfo(i));
   }
 }

 void initProperty(uint32_t index, PropertyKey key, PropertyInfo prop) {
   MOZ_ASSERT(!hasKey(index));
   initKey(index, key);
   linkedData_.propInfos[index] = prop;
 }

 bool isDictionary() const = delete;
 bool isShared() const = delete;
 bool isCompact() const = delete;
 bool isNormal() const = delete;
 bool isLinked() const = delete;
 NormalPropMap* asNormal() = delete;
 const NormalPropMap* asNormal() const = delete;

 SharedPropMap* previous() const {
   return static_cast<SharedPropMap*>(linkedData_.previous.get());
 }

 TreeData& treeDataRef() { return treeData_; }
 const TreeData& treeDataRef() const { return treeData_; }

 static void staticAsserts() {
   static_assert(offsetof(NormalPropMap, linkedData_) ==
                 offsetof(LinkedPropMap, data_));
 }
};

class DictionaryPropMap final : public PropMap {
 friend class PropMap;
 friend class SharedPropMap;
 friend class js::gc::CellAllocator;

 LinkedPropMap::Data linkedData_;

 // SHAPE_INVALID_SLOT or head of slot freelist in owning dictionary-mode
 // object.
 uint32_t freeList_ = SHAPE_INVALID_SLOT;

 // Number of holes for removed properties in this and previous maps. Used by
 // compacting heuristics.
 uint32_t holeCount_ = 0;

 // Empty Dictionary prop map used during reshape.
 explicit DictionaryPropMap(std::nullptr_t) : linkedData_(nullptr) {
   setHeaderFlagBits(IsDictionaryFlag | CanHaveTableFlag);
 }

 DictionaryPropMap(JS::Handle<DictionaryPropMap*> prev, PropertyKey key,
                   PropertyInfo prop)
     : linkedData_(prev) {
   setHeaderFlagBits(IsDictionaryFlag | CanHaveTableFlag |
                     (prev ? HasPrevFlag : 0));
   initProperty(0, key, prop);
 }

 DictionaryPropMap(JS::Handle<NormalPropMap*> orig, uint32_t length)
     : linkedData_(nullptr) {
   setHeaderFlagBits(IsDictionaryFlag | CanHaveTableFlag);
   for (uint32_t i = 0; i < length; i++) {
     initProperty(i, orig->getKey(i), orig->getPropertyInfo(i));
   }
 }

 DictionaryPropMap(JS::Handle<CompactPropMap*> orig, uint32_t length)
     : linkedData_(nullptr) {
   setHeaderFlagBits(IsDictionaryFlag | CanHaveTableFlag);
   for (uint32_t i = 0; i < length; i++) {
     initProperty(i, orig->getKey(i), orig->getPropertyInfo(i));
   }
 }

 void initProperty(uint32_t index, PropertyKey key, PropertyInfo prop) {
   MOZ_ASSERT(!hasKey(index));
   initKey(index, key);
   linkedData_.propInfos[index] = prop;
 }

 void initPrevious(DictionaryPropMap* prev) {
   MOZ_ASSERT(prev);
   linkedData_.previous.init(prev);
   setHeaderFlagBits(HasPrevFlag);
 }
 void clearPrevious() {
   linkedData_.previous = nullptr;
   clearHeaderFlagBits(HasPrevFlag);
 }

 void clearProperty(uint32_t index) { setKey(index, PropertyKey::Void()); }

 static void skipTrailingHoles(MutableHandle<DictionaryPropMap*> map,
                               uint32_t* mapLength);

 void handOffLastMapStateTo(DictionaryPropMap* newLast);

 void incHoleCount() { holeCount_++; }
 void decHoleCount() {
   MOZ_ASSERT(holeCount_ > 0);
   holeCount_--;
 }
 static void maybeCompact(JSContext* cx, MutableHandle<DictionaryPropMap*> map,
                          uint32_t* mapLength);

public:
 bool isDictionary() const = delete;
 bool isShared() const = delete;
 bool isCompact() const = delete;
 bool isNormal() const = delete;
 bool isLinked() const = delete;
 DictionaryPropMap* asDictionary() = delete;
 const DictionaryPropMap* asDictionary() const = delete;

 void fixupAfterMovingGC() {}
 inline void finalize(JS::GCContext* gcx);

 DictionaryPropMap* previous() const {
   return static_cast<DictionaryPropMap*>(linkedData_.previous.get());
 }

 uint32_t freeList() const { return freeList_; }
 void setFreeList(uint32_t slot) { freeList_ = slot; }

 PropertyInfo getPropertyInfo(uint32_t index) const {
   MOZ_ASSERT(hasKey(index));
   return linkedData_.propInfos[index];
 }

 // Create an empty prop map for dictionary mode teleporting
 static DictionaryPropMap* createEmpty(JSContext* cx);

 // Add a new property to this map. Returns the new map/mapLength and object
 // flags. The caller is responsible for generating a new dictionary shape.
 static bool addProperty(JSContext* cx, const JSClass* clasp,
                         MutableHandle<DictionaryPropMap*> map,
                         uint32_t* mapLength, HandleId id, PropertyFlags flags,
                         uint32_t slot, ObjectFlags* objectFlags);

 // Remove the property referenced by the table pointer. Returns the new
 // map/mapLength. The caller is responsible for generating a new dictionary
 // shape.
 static void removeProperty(JSContext* cx,
                            MutableHandle<DictionaryPropMap*> map,
                            uint32_t* mapLength, PropMapTable* table,
                            PropMapTable::Ptr& ptr);

 // Turn all sparse elements into dense elements. The caller is responsible
 // for checking all sparse elements are plain data properties and must
 // generate a new shape for the object.
 static void densifyElements(JSContext* cx,
                             MutableHandle<DictionaryPropMap*> map,
                             uint32_t* mapLength, NativeObject* obj);

 // Freeze or seal all properties in this map. Returns the new object flags.
 // The caller is responsible for generating a new shape for the object.
 void freezeOrSealProperties(JSContext* cx, IntegrityLevel level,
                             const JSClass* clasp, uint32_t mapLength,
                             ObjectFlags* objectFlags);

 // Change a property's slot number and/or flags and return the new object
 // flags. The caller is responsible for generating a new shape.
 void changeProperty(JSContext* cx, const JSClass* clasp, uint32_t index,
                     PropertyFlags flags, uint32_t slot,
                     ObjectFlags* objectFlags);

 // Like changeProperty, but doesn't change the slot number.
 void changePropertyFlags(JSContext* cx, const JSClass* clasp, uint32_t index,
                          PropertyFlags flags, ObjectFlags* objectFlags) {
   uint32_t slot = getPropertyInfo(index).maybeSlot();
   changeProperty(cx, clasp, index, flags, slot, objectFlags);
 }

 static void staticAsserts() {
   static_assert(offsetof(DictionaryPropMap, linkedData_) ==
                 offsetof(LinkedPropMap, data_));
 }

#if defined(DEBUG) || defined(JS_JITSPEW)
 void dumpOwnFields(js::JSONPrinter& json) const;
#endif
};

inline CompactPropMap* PropMap::asCompact() {
 MOZ_ASSERT(isCompact());
 return static_cast<CompactPropMap*>(this);
}
inline const CompactPropMap* PropMap::asCompact() const {
 MOZ_ASSERT(isCompact());
 return static_cast<const CompactPropMap*>(this);
}
inline LinkedPropMap* PropMap::asLinked() {
 MOZ_ASSERT(isLinked());
 return static_cast<LinkedPropMap*>(this);
}
inline const LinkedPropMap* PropMap::asLinked() const {
 MOZ_ASSERT(isLinked());
 return static_cast<const LinkedPropMap*>(this);
}
inline NormalPropMap* PropMap::asNormal() {
 MOZ_ASSERT(isNormal());
 return static_cast<NormalPropMap*>(this);
}
inline const NormalPropMap* PropMap::asNormal() const {
 MOZ_ASSERT(isNormal());
 return static_cast<const NormalPropMap*>(this);
}
inline SharedPropMap* PropMap::asShared() {
 MOZ_ASSERT(isShared());
 return static_cast<SharedPropMap*>(this);
}
inline const SharedPropMap* PropMap::asShared() const {
 MOZ_ASSERT(isShared());
 return static_cast<const SharedPropMap*>(this);
}
inline DictionaryPropMap* PropMap::asDictionary() {
 MOZ_ASSERT(isDictionary());
 return static_cast<DictionaryPropMap*>(this);
}
inline const DictionaryPropMap* PropMap::asDictionary() const {
 MOZ_ASSERT(isDictionary());
 return static_cast<const DictionaryPropMap*>(this);
}

inline PropertyInfo PropMap::getPropertyInfo(uint32_t index) const {
 return isCompact() ? asCompact()->getPropertyInfo(index)
                    : asLinked()->getPropertyInfo(index);
}

inline SharedPropMap::TreeData& SharedPropMap::treeDataRef() {
 return isCompact() ? asCompact()->treeDataRef() : asNormal()->treeDataRef();
}

inline const SharedPropMap::TreeData& SharedPropMap::treeDataRef() const {
 return isCompact() ? asCompact()->treeDataRef() : asNormal()->treeDataRef();
}

inline void SharedPropMap::initProperty(uint32_t index, PropertyKey key,
                                       PropertyInfo prop) {
 if (isCompact()) {
   asCompact()->initProperty(index, key, prop);
 } else {
   asNormal()->initProperty(index, key, prop);
 }
}

template <typename T>
inline PropertyInfo MapAndIndex<T>::propertyInfo() const {
 MOZ_ASSERT(!isNone());
 return map()->getPropertyInfo(index());
}

MOZ_ALWAYS_INLINE HashNumber PropMapTable::Hasher::hash(PropertyKey key) {
 return HashPropertyKey(key);
}
MOZ_ALWAYS_INLINE bool PropMapTable::Hasher::match(PropMapAndIndex entry,
                                                  PropertyKey key) {
 MOZ_ASSERT(entry.map()->hasKey(entry.index()));
 return entry.map()->getKey(entry.index()) == key;
}

// Hash policy for SharedPropMap children.
struct SharedChildrenHasher {
 using Key = SharedPropMapAndIndex;

 struct Lookup {
   PropertyKey key;
   PropertyInfo prop;
   uint8_t index;

   Lookup(PropertyKey key, PropertyInfo prop, uint8_t index)
       : key(key), prop(prop), index(index) {}
   Lookup(PropertyInfoWithKey prop, uint8_t index)
       : key(prop.key()), prop(prop), index(index) {}
 };

 static HashNumber hash(const Lookup& l) {
   HashNumber hash = HashPropertyKey(l.key);
   return mozilla::AddToHash(hash, l.prop.toRaw(), l.index);
 }
 static bool match(SharedPropMapAndIndex k, const Lookup& l) {
   SharedPropMap* map = k.map();
   uint32_t index = k.index();
   uint32_t newIndex = SharedPropMap::indexOfNextProperty(index);
   return index == l.index && map->matchProperty(newIndex, l.key, l.prop);
 }
};

// An iterator that walks a shared prop map in property definition order
class MOZ_RAII SharedPropMapIter {
public:
 // Iterate over all properties of propMap.
 SharedPropMapIter(JSContext* cx, SharedPropMapAndIndex propMap);

 // Iterate over all properties after (but not including) startAfter.
 SharedPropMapIter(JSContext* cx, SharedPropMapAndIndex startAfter,
                   SharedPropMapAndIndex end);

 PropertyKey key() const {
   MOZ_ASSERT(!done());
   return maps_[mapIdx_]->getKey(propIdx_);
 }
 PropertyInfo prop() const {
   MOZ_ASSERT(!done());
   return maps_[mapIdx_]->getPropertyInfo(propIdx_);
 }

 bool done() const { return mapIdx_ == 0 && propIdx_ > endIdx_; }
 void next() {
   MOZ_ASSERT(!done());
   if (++propIdx_ == PropMap::Capacity && mapIdx_ > 0) {
     propIdx_ = 0;
     mapIdx_--;
   }
 }

private:
 SharedPropMapIter(JSContext* cx, mozilla::Maybe<SharedPropMapAndIndex> start,
                   SharedPropMapAndIndex end);

 JS::RootedVector<SharedPropMap*> maps_;
 uint32_t mapIdx_;
 uint32_t propIdx_;
 uint32_t endIdx_;
};

}  // namespace js

// JS::ubi::Nodes can point to PropMaps; they're js::gc::Cell instances
// with no associated compartment.
namespace JS {
namespace ubi {

template <>
class Concrete<js::PropMap> : TracerConcrete<js::PropMap> {
protected:
 explicit Concrete(js::PropMap* ptr) : TracerConcrete<js::PropMap>(ptr) {}

public:
 static void construct(void* storage, js::PropMap* ptr) {
   new (storage) Concrete(ptr);
 }

 Size size(mozilla::MallocSizeOf mallocSizeOf) const override;

 const char16_t* typeName() const override { return concreteTypeName; }
 static const char16_t concreteTypeName[];
};

}  // namespace ubi
}  // namespace JS

#endif  // vm_PropMap_h