/* -*- 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 "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;
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];
}
// 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);
}
};
}
// 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
