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/. */
10 #include "gc/Barrier.h"
12 #include "js/TypeDecls.h"
13 #include "js/UbiNode.h"
14 #include "vm/ObjectFlags.h"
15 #include "vm/PropertyInfo.h"
16 #include "vm/PropertyKey.h"
18 // [SMDOC] Property Maps
20 // Property maps are used to store information about native object properties.
21 // Each property map represents an ordered list of (PropertyKey, PropertyInfo)
24 // Each property map can store up to 8 properties (see PropMap::Capacity). To
25 // store more than eight properties, multiple maps must be linked together with
26 // the |previous| pointer.
28 // Shapes and Property Maps
29 // ------------------------
30 // Native object shapes represent property information as a (PropMap*, length)
31 // tuple. When there are no properties yet, the shape's map will be nullptr and
32 // the length is zero.
34 // For example, consider the following objects:
37 // o2 = {x: 3, y: 4, z: 5}
39 // This is stored as follows:
41 // +-------------+ +--------------+ +-------------------+
42 // | JSObject o1 | | Shape S1 | | PropMap M1 |
43 // |-------------+ +--------------+ +-------------------+
44 // | shape: S1 -+---> | map: M1 -+--+> | key 0: x (slot 0) |
45 // | slot 0: 1 | | mapLength: 2 | | | key 1: y (slot 1) |
46 // | slot 1: 2 | +--------------+ | | key 2: z (slot 2) |
47 // +-------------+ | | ... |
48 // | +-------------------+
50 // +-------------+ +--------------+ |
51 // | JSObject o2 | | Shape S2 | |
52 // |-------------+ +--------------+ |
53 // | shape: S2 -+---> | map: M1 -+--+
54 // | slot 0: 3 | | mapLength: 3 |
55 // | slot 1: 4 | +--------------+
59 // There's a single map M1 shared by shapes S1 and S2. Shape S1 includes only
60 // the first two properties and shape S2 includes all three properties.
64 // Property maps have the following C++ class hierarchy:
68 // +-- SharedPropMap (abstract)
70 // | +-- CompactPropMap
72 // | +-- NormalPropMap
74 // +-- DictionaryPropMap
76 // * PropMap: base class. It has a flags word and an array of PropertyKeys.
78 // * SharedPropMap: base class for all shared property maps. See below for more
79 // information on shared maps.
81 // * CompactPropMap: a shared map that stores its information more compactly
82 // than the other maps. It saves four words by not storing a
83 // PropMapTable, previous pointer, and by using a more compact
84 // PropertyInfo type for slot numbers that fit in one byte.
86 // * NormalPropMap: a shared map, used when CompactPropMap can't be used.
88 // * DictionaryPropMap: an unshared map (used by a single object/shape). See
89 // below for more information on dictionary maps.
91 // Secondary hierarchy
92 // -------------------
93 // NormalPropMap and DictionaryPropMap store property information in the same
94 // way. This means property lookups don't have to distinguish between these two
95 // types. This is represented with a second class hierarchy:
101 // +-- LinkedPropMap (NormalPropMap or DictionaryPropMap)
103 // Property lookup and property iteration are very performance sensitive and use
104 // this Compact vs Linked "view" so that they don't have to handle the three map
107 // LinkedPropMap also stores the PropMapTable and a pointer to the |previous|
108 // map. Compact maps don't have these fields.
110 // To summarize these map types:
112 // +-------------------+-------------+--------+
113 // | Concrete type | Shared/tree | Linked |
114 // +-------------------+-------------+--------+
115 // | CompactPropMap | yes | no |
116 // | NormalPropMap | yes | yes |
117 // | DictionaryPropMap | no | yes |
118 // +-------------------+-------------+--------+
122 // Finding the PropertyInfo for a particular PropertyKey requires a linear
123 // search if the map is small. For larger maps we can create a PropMapTable, a
124 // hash table that maps from PropertyKey to PropMap + index, to speed up
127 // To save memory, property map tables can be discarded on GC and recreated when
128 // needed. AutoKeepPropMapTables can be used to avoid discarding tables in a
129 // particular zone. Methods to access a PropMapTable take either an
130 // AutoCheckCannotGC or AutoKeepPropMapTables argument, to help ensure tables
131 // are not purged while we're using them.
133 // Shared Property Maps
134 // --------------------
135 // Shared property maps can be shared per-Zone by objects with the same property
136 // keys, flags, and slot numbers. To make this work, shared maps form a tree:
138 // - Each Zone has a table that maps from first PropertyKey + PropertyInfo to
139 // a SharedPropMap that begins with that property. This is used to lookup the
140 // the map to use when adding the first property.
141 // See ShapeZone::initialPropMaps.
143 // - When adding a property other than the first one, the property is stored in
144 // the next entry of the same map when possible. If the map is full or the
145 // next entry already stores a different property, a child map is created and
146 // linked to the parent map.
148 // For example, imagine we want to create these objects:
150 // o1 = {x: 1, y: 2, z: 3}
151 // o2 = {x: 1, y: 2, foo: 4}
153 // This will result in the following maps being created:
155 // +---------------------+ +---------------------+
156 // | SharedPropMap M1 | | SharedPropMap M2 |
157 // +---------------------+ +---------------------+
158 // | Child M2 (index 1) -+--> | Parent M1 (index 1) |
159 // +---------------------+ +---------------------+
162 // | 2: z | | 2: foo |
164 // +---------------------+ +---------------------+
166 // M1 is the map used for initial property "x". Properties "y" and "z" can be
167 // stored inline. When later adding "foo" following "y", the map has to be
168 // forked: a child map M2 is created and M1 remembers this transition at
169 // property index 1 so that M2 will be used the next time properties "x", "y",
170 // and "foo" are added to an object.
172 // Shared maps contain a TreeData struct that stores the parent and children
173 // links for the SharedPropMap tree. The parent link is a tagged pointer that
174 // stores both the parent map and the property index of the last used property
175 // in the parent map before the branch. The children are stored similarly: the
176 // parent map can store a single child map and index, or a set of children.
177 // See SharedChildrenPtr.
179 // Looking up a child map can then be done based on the index of the last
180 // property in the parent map and the new property's key and flags. So for the
181 // example above, the lookup key for M1 => M2 is (index 1, "foo", <flags>).
183 // Note: shared maps can have both a |previous| map and a |parent| map. They are
184 // equal when the previous map was full, but can be different maps when
185 // branching in the middle of a map like in the example above: M2 has parent M1
186 // but does not have a |previous| map (because it only has three properties).
188 // Dictionary Property Maps
189 // ------------------------
190 // Certain operations can't be implemented (efficiently) for shared property
191 // maps, for example changing or deleting a property other than the last one.
192 // When this happens the map is copied as a DictionaryPropMap.
194 // Dictionary maps are unshared so can be mutated in place (after generating a
195 // new shape for the object).
197 // Unlike shared maps, dictionary maps can have holes between two property keys
198 // after removing a property. When there are more holes than properties, the
199 // map is compacted. See DictionaryPropMap::maybeCompact.
203 enum class IntegrityLevel
;
205 class DictionaryPropMap
;
208 class CompactPropMap
;
211 // Template class for storing a PropMap* and a property index as tagged pointer.
212 template <typename T
>
216 static constexpr uintptr_t IndexMask
= 0b111;
219 MapAndIndex() = default;
221 MapAndIndex(const T
* map
, uint32_t index
) : data_(uintptr_t(map
) | index
) {
222 MOZ_ASSERT((uintptr_t(map
) & IndexMask
) == 0);
223 MOZ_ASSERT(index
<= IndexMask
);
225 explicit MapAndIndex(uintptr_t data
) : data_(data
) {}
227 void setNone() { data_
= 0; }
229 bool isNone() const { return data_
== 0; }
231 uintptr_t raw() const { return data_
; }
232 T
* maybeMap() const { return reinterpret_cast<T
*>(data_
& ~IndexMask
); }
234 uint32_t index() const {
235 MOZ_ASSERT(!isNone());
236 return data_
& IndexMask
;
239 MOZ_ASSERT(!isNone());
243 inline PropertyInfo
propertyInfo() const;
245 bool operator==(const MapAndIndex
<T
>& other
) const {
246 return data_
== other
.data_
;
248 bool operator!=(const MapAndIndex
<T
>& other
) const {
249 return !operator==(other
);
252 using PropMapAndIndex
= MapAndIndex
<PropMap
>;
253 using SharedPropMapAndIndex
= MapAndIndex
<SharedPropMap
>;
255 struct SharedChildrenHasher
;
256 using SharedChildrenSet
=
257 HashSet
<SharedPropMapAndIndex
, SharedChildrenHasher
, SystemAllocPolicy
>;
259 // Children of shared maps. This is either:
261 // - None (no children)
262 // - SingleMapAndIndex (one child map, including the property index of the last
263 // property before the branch)
264 // - SharedChildrenSet (multiple children)
266 // Because SingleMapAndIndex use all bits, this relies on the HasChildrenSet
267 // flag in the map to distinguish the latter two cases.
268 class SharedChildrenPtr
{
272 bool isNone() const { return data_
== 0; }
273 void setNone() { data_
= 0; }
275 void setSingleChild(SharedPropMapAndIndex child
) { data_
= child
.raw(); }
276 void setChildrenSet(SharedChildrenSet
* set
) { data_
= uintptr_t(set
); }
278 SharedPropMapAndIndex
toSingleChild() const {
279 MOZ_ASSERT(!isNone());
280 return SharedPropMapAndIndex(data_
);
283 SharedChildrenSet
* toChildrenSet() const {
284 MOZ_ASSERT(!isNone());
285 return reinterpret_cast<SharedChildrenSet
*>(data_
);
289 // Ensures no property map tables are purged in the current zone.
290 class MOZ_RAII AutoKeepPropMapTables
{
295 void operator=(const AutoKeepPropMapTables
&) = delete;
296 AutoKeepPropMapTables(const AutoKeepPropMapTables
&) = delete;
297 explicit inline AutoKeepPropMapTables(JSContext
* cx
);
298 inline ~AutoKeepPropMapTables();
301 // Hash table to optimize property lookups on larger maps. This maps from
302 // PropertyKey to PropMapAndIndex.
305 using Key
= PropMapAndIndex
;
306 using Lookup
= PropertyKey
;
307 static MOZ_ALWAYS_INLINE HashNumber
hash(PropertyKey key
);
308 static MOZ_ALWAYS_INLINE
bool match(PropMapAndIndex
, PropertyKey key
);
311 // Small lookup cache. This has a hit rate of 30-60% on most workloads and is
312 // a lot faster than the full HashSet lookup.
315 PropMapAndIndex result
;
317 static constexpr uint32_t NumCacheEntries
= 2;
318 CacheEntry cacheEntries_
[NumCacheEntries
];
320 using Set
= HashSet
<PropMapAndIndex
, Hasher
, SystemAllocPolicy
>;
323 void setCacheEntry(PropertyKey key
, PropMapAndIndex entry
) {
324 for (uint32_t i
= 0; i
< NumCacheEntries
; i
++) {
325 if (cacheEntries_
[i
].key
== key
) {
326 cacheEntries_
[i
].result
= entry
;
331 bool lookupInCache(PropertyKey key
, PropMapAndIndex
* result
) const {
332 for (uint32_t i
= 0; i
< NumCacheEntries
; i
++) {
333 if (cacheEntries_
[i
].key
== key
) {
334 *result
= cacheEntries_
[i
].result
;
336 auto p
= lookupRaw(key
);
337 MOZ_ASSERT(*result
== (p
? *p
: PropMapAndIndex()));
344 void addToCache(PropertyKey key
, Set::Ptr p
) {
345 for (uint32_t i
= NumCacheEntries
- 1; i
> 0; i
--) {
346 cacheEntries_
[i
] = cacheEntries_
[i
- 1];
347 MOZ_ASSERT(cacheEntries_
[i
].key
!= key
);
349 cacheEntries_
[0].key
= key
;
350 cacheEntries_
[0].result
= p
? *p
: PropMapAndIndex();
354 using Ptr
= Set::Ptr
;
356 PropMapTable() = default;
357 ~PropMapTable() = default;
359 uint32_t entryCount() const { return set_
.count(); }
361 // This counts the PropMapTable object itself (which must be heap-allocated)
363 size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf
) const {
364 return mallocSizeOf(this) + set_
.shallowSizeOfExcludingThis(mallocSizeOf
);
367 // init() is fallible and reports OOM to the context.
368 bool init(JSContext
* cx
, LinkedPropMap
* map
);
370 MOZ_ALWAYS_INLINE PropMap
* lookup(PropMap
* map
, uint32_t mapLength
,
371 PropertyKey key
, uint32_t* index
);
373 Set::Ptr
lookupRaw(PropertyKey key
) const { return set_
.lookup(key
); }
375 Set::Ptr
readonlyThreadsafeLookup(PropertyKey key
) const {
376 return set_
.readonlyThreadsafeLookup(key
);
380 bool add(JSContext
* cx
, PropertyKey key
, PropMapAndIndex entry
) {
381 if (!set_
.putNew(key
, entry
)) {
382 ReportOutOfMemory(cx
);
385 setCacheEntry(key
, entry
);
390 for (uint32_t i
= 0; i
< NumCacheEntries
; i
++) {
391 cacheEntries_
[i
] = CacheEntry();
395 void remove(Ptr ptr
) {
400 void replaceEntry(Ptr ptr
, PropertyKey key
, PropMapAndIndex newEntry
) {
401 MOZ_ASSERT(*ptr
!= newEntry
);
402 set_
.replaceKey(ptr
, key
, newEntry
);
403 setCacheEntry(key
, newEntry
);
406 void trace(JSTracer
* trc
);
407 #ifdef JSGC_HASH_TABLE_CHECKS
408 void checkAfterMovingGC();
412 class PropMap
: public gc::TenuredCellWithFlags
{
414 // Number of properties that can be stored in each map. This must be small
415 // enough so that every index fits in a tagged PropMap* pointer (MapAndIndex).
416 static constexpr size_t Capacity
= 8;
419 static_assert(gc::CellFlagBitsReservedForGC
== 3,
420 "PropMap must reserve enough bits for Cell");
423 // Set if this is a CompactPropMap.
424 IsCompactFlag
= 1 << 3,
426 // Set if this map has a non-null previous map pointer. Never set for
427 // compact maps because they don't have a previous field.
428 HasPrevFlag
= 1 << 4,
430 // Set if this is a DictionaryPropMap.
431 IsDictionaryFlag
= 1 << 5,
433 // Set if this map can have a table. Never set for compact maps. Always set
434 // for dictionary maps.
435 CanHaveTableFlag
= 1 << 6,
437 // If set, this SharedPropMap has a SharedChildrenSet. Else it either has no
438 // children or a single child. See SharedChildrenPtr. Never set for
440 HasChildrenSetFlag
= 1 << 7,
442 // If set, this SharedPropMap was once converted to dictionary mode. This is
443 // only used for heuristics. Never set for dictionary maps.
444 HadDictionaryConversionFlag
= 1 << 8,
446 // For SharedPropMap this stores the number of previous maps, clamped to
447 // NumPreviousMapsMax. This is used for heuristics.
448 NumPreviousMapsMax
= 0x7f,
449 NumPreviousMapsShift
= 9,
450 NumPreviousMapsMask
= NumPreviousMapsMax
<< NumPreviousMapsShift
,
453 // Flags word, stored in the cell header. Note that this hides the
454 // Cell::flags() method.
455 uintptr_t flags() const { return headerFlagsField(); }
458 GCPtr
<PropertyKey
> keys_
[Capacity
];
463 void initKey(uint32_t index
, PropertyKey key
) {
464 MOZ_ASSERT(index
< Capacity
);
465 keys_
[index
].init(key
);
467 void setKey(uint32_t index
, PropertyKey key
) {
468 MOZ_ASSERT(index
< Capacity
);
473 bool isCompact() const { return flags() & IsCompactFlag
; }
474 bool isLinked() const { return !isCompact(); }
475 bool isDictionary() const { return flags() & IsDictionaryFlag
; }
476 bool isShared() const { return !isDictionary(); }
477 bool isNormal() const { return isShared() && !isCompact(); }
479 bool hasPrevious() const { return flags() & HasPrevFlag
; }
480 bool canHaveTable() const { return flags() & CanHaveTableFlag
; }
482 inline CompactPropMap
* asCompact();
483 inline const CompactPropMap
* asCompact() const;
485 inline LinkedPropMap
* asLinked();
486 inline const LinkedPropMap
* asLinked() const;
488 inline NormalPropMap
* asNormal();
489 inline const NormalPropMap
* asNormal() const;
491 inline SharedPropMap
* asShared();
492 inline const SharedPropMap
* asShared() const;
494 inline DictionaryPropMap
* asDictionary();
495 inline const DictionaryPropMap
* asDictionary() const;
497 bool hasKey(uint32_t index
) const {
498 MOZ_ASSERT(index
< Capacity
);
499 return !keys_
[index
].isVoid();
501 PropertyKey
getKey(uint32_t index
) const {
502 MOZ_ASSERT(index
< Capacity
);
506 uint32_t approximateEntryCount() const;
509 void dump(js::GenericPrinter
& out
) const;
511 void checkConsistency(NativeObject
* obj
) const;
514 void addSizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf
,
515 size_t* children
, size_t* tables
) const;
517 inline PropertyInfo
getPropertyInfo(uint32_t index
) const;
519 PropertyInfoWithKey
getPropertyInfoWithKey(uint32_t index
) const {
520 return PropertyInfoWithKey(getPropertyInfo(index
), getKey(index
));
523 MOZ_ALWAYS_INLINE PropMap
* lookupLinear(uint32_t mapLength
, PropertyKey key
,
526 MOZ_ALWAYS_INLINE PropMap
* lookupPure(uint32_t mapLength
, PropertyKey key
,
529 MOZ_ALWAYS_INLINE PropMap
* lookup(JSContext
* cx
, uint32_t mapLength
,
530 PropertyKey key
, uint32_t* index
);
532 static inline bool lookupForRemove(JSContext
* cx
, PropMap
* map
,
533 uint32_t mapLength
, PropertyKey key
,
534 const AutoKeepPropMapTables
& keep
,
535 PropMap
** propMap
, uint32_t* propIndex
,
536 PropMapTable
** table
,
537 PropMapTable::Ptr
* ptr
);
539 static const JS::TraceKind TraceKind
= JS::TraceKind::PropMap
;
541 void traceChildren(JSTracer
* trc
);
544 class SharedPropMap
: public PropMap
{
545 friend class PropMap
;
548 // Shared maps are stored in a tree structure. Each shared map has a TreeData
549 // struct linking the map to its parent and children. Initial maps (the ones
550 // stored in ShapeZone's initialPropMaps table) don't have a parent.
552 SharedChildrenPtr children
;
553 SharedPropMapAndIndex parent
;
555 void setParent(SharedPropMap
* map
, uint32_t index
) {
556 parent
= SharedPropMapAndIndex(map
, index
);
561 static SharedPropMap
* create(JSContext
* cx
, Handle
<SharedPropMap
*> prev
,
562 HandleId id
, PropertyInfo prop
);
563 static SharedPropMap
* createInitial(JSContext
* cx
, HandleId id
,
565 static SharedPropMap
* clone(JSContext
* cx
, Handle
<SharedPropMap
*> map
,
568 inline void initProperty(uint32_t index
, PropertyKey key
, PropertyInfo prop
);
570 static bool addPropertyInternal(JSContext
* cx
,
571 MutableHandle
<SharedPropMap
*> map
,
572 uint32_t* mapLength
, HandleId id
,
575 bool addChild(JSContext
* cx
, SharedPropMapAndIndex child
, HandleId id
,
577 SharedPropMap
* lookupChild(uint32_t length
, HandleId id
, PropertyInfo prop
);
580 void initNumPreviousMaps(uint32_t value
) {
581 MOZ_ASSERT((flags() >> NumPreviousMapsShift
) == 0);
582 // Clamp to NumPreviousMapsMax. This is okay because this value is only used
584 if (value
> NumPreviousMapsMax
) {
585 value
= NumPreviousMapsMax
;
587 setHeaderFlagBits(value
<< NumPreviousMapsShift
);
590 bool hasChildrenSet() const { return flags() & HasChildrenSetFlag
; }
591 void setHasChildrenSet() { setHeaderFlagBits(HasChildrenSetFlag
); }
592 void clearHasChildrenSet() { clearHeaderFlagBits(HasChildrenSetFlag
); }
594 void setHadDictionaryConversion() {
595 setHeaderFlagBits(HadDictionaryConversionFlag
);
599 // Heuristics used when adding a property via NativeObject::addProperty and
602 // * If numPreviousMaps >= NumPrevMapsForAddConsiderDictionary, consider
603 // converting the object to a dictionary object based on other heuristics.
605 // * If numPreviousMaps >= NumPrevMapsForAddAlwaysDictionary, always convert
606 // the object to a dictionary object.
607 static constexpr size_t NumPrevMapsConsiderDictionary
= 32;
608 static constexpr size_t NumPrevMapsAlwaysDictionary
= 100;
610 static_assert(NumPrevMapsConsiderDictionary
< NumPreviousMapsMax
);
611 static_assert(NumPrevMapsAlwaysDictionary
< NumPreviousMapsMax
);
613 // The number of properties that can definitely be added to an object without
614 // triggering dictionary mode conversion in NativeObject::addProperty.
615 static constexpr size_t MaxPropsForNonDictionary
=
616 NumPrevMapsConsiderDictionary
* Capacity
;
618 bool isDictionary() const = delete;
619 bool isShared() const = delete;
620 SharedPropMap
* asShared() = delete;
621 const SharedPropMap
* asShared() const = delete;
623 bool hadDictionaryConversion() const {
624 return flags() & HadDictionaryConversionFlag
;
627 uint32_t numPreviousMaps() const {
628 uint32_t val
= (flags() & NumPreviousMapsMask
) >> NumPreviousMapsShift
;
629 MOZ_ASSERT_IF(hasPrevious(), val
> 0);
633 MOZ_ALWAYS_INLINE
bool shouldConvertToDictionaryForAdd() const;
635 void fixupAfterMovingGC();
636 inline void sweep(JS::GCContext
* gcx
);
637 inline void finalize(JS::GCContext
* gcx
);
639 static inline void getPrevious(MutableHandle
<SharedPropMap
*> map
,
640 uint32_t* mapLength
);
642 bool matchProperty(uint32_t index
, PropertyKey key
, PropertyInfo prop
) const {
643 return getKey(index
) == key
&& getPropertyInfo(index
) == prop
;
646 inline TreeData
& treeDataRef();
647 inline const TreeData
& treeDataRef() const;
649 void removeChild(JS::GCContext
* gcx
, SharedPropMap
* child
);
651 uint32_t lastUsedSlot(uint32_t mapLength
) const {
652 return getPropertyInfo(mapLength
- 1).maybeSlot();
655 // Number of slots required for objects with this map/mapLength.
656 static uint32_t slotSpan(const JSClass
* clasp
, const SharedPropMap
* map
,
657 uint32_t mapLength
) {
658 MOZ_ASSERT(clasp
->isNativeObject());
659 uint32_t numReserved
= JSCLASS_RESERVED_SLOTS(clasp
);
661 MOZ_ASSERT(mapLength
== 0);
664 uint32_t lastSlot
= map
->lastUsedSlot(mapLength
);
665 if (lastSlot
== SHAPE_INVALID_SLOT
) {
666 // The object only has custom data properties.
669 // Some builtin objects store properties in reserved slots. Make sure the
670 // slot span >= numReserved. See addPropertyInReservedSlot.
671 return std::max(lastSlot
+ 1, numReserved
);
674 static uint32_t indexOfNextProperty(uint32_t index
) {
675 MOZ_ASSERT(index
< PropMap::Capacity
);
676 return (index
+ 1) % PropMap::Capacity
;
679 // Add a new property to this map. Returns the new map/mapLength, slot number,
681 static bool addProperty(JSContext
* cx
, const JSClass
* clasp
,
682 MutableHandle
<SharedPropMap
*> map
,
683 uint32_t* mapLength
, HandleId id
, PropertyFlags flags
,
684 ObjectFlags
* objectFlags
, uint32_t* slot
);
686 // Like addProperty, but for when the slot number is a reserved slot. A few
687 // builtin objects use this for initial properties.
688 static bool addPropertyInReservedSlot(JSContext
* cx
, const JSClass
* clasp
,
689 MutableHandle
<SharedPropMap
*> map
,
690 uint32_t* mapLength
, HandleId id
,
691 PropertyFlags flags
, uint32_t slot
,
692 ObjectFlags
* objectFlags
);
694 // Like addProperty, but for when the caller already knows the slot number to
695 // use (or wants to assert this exact slot number is used).
696 static bool addPropertyWithKnownSlot(JSContext
* cx
, const JSClass
* clasp
,
697 MutableHandle
<SharedPropMap
*> map
,
698 uint32_t* mapLength
, HandleId id
,
699 PropertyFlags flags
, uint32_t slot
,
700 ObjectFlags
* objectFlags
);
702 // Like addProperty, but for adding a custom data property.
703 static bool addCustomDataProperty(JSContext
* cx
, const JSClass
* clasp
,
704 MutableHandle
<SharedPropMap
*> map
,
705 uint32_t* mapLength
, HandleId id
,
707 ObjectFlags
* objectFlags
);
709 // Freeze or seal all properties by creating a new shared map. Returns the new
710 // map and object flags.
711 static bool freezeOrSealProperties(JSContext
* cx
, IntegrityLevel level
,
712 const JSClass
* clasp
,
713 MutableHandle
<SharedPropMap
*> map
,
715 ObjectFlags
* objectFlags
);
717 // Create a new dictionary map as copy of this map.
718 static DictionaryPropMap
* toDictionaryMap(JSContext
* cx
,
719 Handle
<SharedPropMap
*> map
,
723 class CompactPropMap final
: public SharedPropMap
{
724 CompactPropertyInfo propInfos_
[Capacity
];
727 friend class PropMap
;
728 friend class SharedPropMap
;
729 friend class DictionaryPropMap
;
730 friend class js::gc::CellAllocator
;
732 CompactPropMap(JS::Handle
<PropertyKey
> key
, PropertyInfo prop
) {
733 setHeaderFlagBits(IsCompactFlag
);
734 initProperty(0, key
, prop
);
737 CompactPropMap(JS::Handle
<CompactPropMap
*> orig
, uint32_t length
) {
738 setHeaderFlagBits(IsCompactFlag
);
739 for (uint32_t i
= 0; i
< length
; i
++) {
740 initKey(i
, orig
->getKey(i
));
741 propInfos_
[i
] = orig
->propInfos_
[i
];
745 void initProperty(uint32_t index
, PropertyKey key
, PropertyInfo prop
) {
746 MOZ_ASSERT(!hasKey(index
));
748 propInfos_
[index
] = CompactPropertyInfo(prop
);
751 TreeData
& treeDataRef() { return treeData_
; }
752 const TreeData
& treeDataRef() const { return treeData_
; }
755 bool isDictionary() const = delete;
756 bool isShared() const = delete;
757 bool isCompact() const = delete;
758 bool isNormal() const = delete;
759 bool isLinked() const = delete;
760 CompactPropMap
* asCompact() = delete;
761 const CompactPropMap
* asCompact() const = delete;
763 PropertyInfo
getPropertyInfo(uint32_t index
) const {
764 MOZ_ASSERT(hasKey(index
));
765 return PropertyInfo(propInfos_
[index
]);
769 // Layout shared by NormalPropMap and DictionaryPropMap.
770 class LinkedPropMap final
: public PropMap
{
771 friend class PropMap
;
772 friend class SharedPropMap
;
773 friend class NormalPropMap
;
774 friend class DictionaryPropMap
;
777 GCPtr
<PropMap
*> previous
;
778 PropMapTable
* table
= nullptr;
779 PropertyInfo propInfos
[Capacity
];
781 explicit Data(PropMap
* prev
) : previous(prev
) {}
785 bool createTable(JSContext
* cx
);
786 void handOffTableTo(LinkedPropMap
* next
);
789 bool isCompact() const = delete;
790 bool isLinked() const = delete;
791 LinkedPropMap
* asLinked() = delete;
792 const LinkedPropMap
* asLinked() const = delete;
794 PropMap
* previous() const { return data_
.previous
; }
796 bool hasTable() const { return data_
.table
!= nullptr; }
798 PropMapTable
* maybeTable(JS::AutoCheckCannotGC
& nogc
) const {
801 PropMapTable
* ensureTable(JSContext
* cx
, const JS::AutoCheckCannotGC
& nogc
) {
802 if (!data_
.table
&& MOZ_UNLIKELY(!createTable(cx
))) {
807 PropMapTable
* ensureTable(JSContext
* cx
, const AutoKeepPropMapTables
& keep
) {
808 if (!data_
.table
&& MOZ_UNLIKELY(!createTable(cx
))) {
814 void purgeTable(JS::GCContext
* gcx
);
816 void purgeTableCache() {
818 data_
.table
->purgeCache();
823 bool canSkipMarkingTable();
826 PropertyInfo
getPropertyInfo(uint32_t index
) const {
827 MOZ_ASSERT(hasKey(index
));
828 return data_
.propInfos
[index
];
832 class NormalPropMap final
: public SharedPropMap
{
833 friend class PropMap
;
834 friend class SharedPropMap
;
835 friend class DictionaryPropMap
;
836 friend class js::gc::CellAllocator
;
838 LinkedPropMap::Data linkedData_
;
841 NormalPropMap(JS::Handle
<SharedPropMap
*> prev
, PropertyKey key
,
843 : linkedData_(prev
) {
845 setHeaderFlagBits(HasPrevFlag
);
846 initNumPreviousMaps(prev
->numPreviousMaps() + 1);
847 if (prev
->hasPrevious()) {
848 setHeaderFlagBits(CanHaveTableFlag
);
851 initProperty(0, key
, prop
);
854 NormalPropMap(JS::Handle
<NormalPropMap
*> orig
, uint32_t length
)
855 : linkedData_(orig
->previous()) {
856 if (orig
->hasPrevious()) {
857 setHeaderFlagBits(HasPrevFlag
);
859 if (orig
->canHaveTable()) {
860 setHeaderFlagBits(CanHaveTableFlag
);
862 initNumPreviousMaps(orig
->numPreviousMaps());
863 for (uint32_t i
= 0; i
< length
; i
++) {
864 initProperty(i
, orig
->getKey(i
), orig
->getPropertyInfo(i
));
868 void initProperty(uint32_t index
, PropertyKey key
, PropertyInfo prop
) {
869 MOZ_ASSERT(!hasKey(index
));
871 linkedData_
.propInfos
[index
] = prop
;
874 bool isDictionary() const = delete;
875 bool isShared() const = delete;
876 bool isCompact() const = delete;
877 bool isNormal() const = delete;
878 bool isLinked() const = delete;
879 NormalPropMap
* asNormal() = delete;
880 const NormalPropMap
* asNormal() const = delete;
882 SharedPropMap
* previous() const {
883 return static_cast<SharedPropMap
*>(linkedData_
.previous
.get());
886 TreeData
& treeDataRef() { return treeData_
; }
887 const TreeData
& treeDataRef() const { return treeData_
; }
889 static void staticAsserts() {
890 static_assert(offsetof(NormalPropMap
, linkedData_
) ==
891 offsetof(LinkedPropMap
, data_
));
895 class DictionaryPropMap final
: public PropMap
{
896 friend class PropMap
;
897 friend class SharedPropMap
;
898 friend class js::gc::CellAllocator
;
900 LinkedPropMap::Data linkedData_
;
902 // SHAPE_INVALID_SLOT or head of slot freelist in owning dictionary-mode
904 uint32_t freeList_
= SHAPE_INVALID_SLOT
;
906 // Number of holes for removed properties in this and previous maps. Used by
907 // compacting heuristics.
908 uint32_t holeCount_
= 0;
910 DictionaryPropMap(JS::Handle
<DictionaryPropMap
*> prev
, PropertyKey key
,
912 : linkedData_(prev
) {
913 setHeaderFlagBits(IsDictionaryFlag
| CanHaveTableFlag
|
914 (prev
? HasPrevFlag
: 0));
915 initProperty(0, key
, prop
);
918 DictionaryPropMap(JS::Handle
<NormalPropMap
*> orig
, uint32_t length
)
919 : linkedData_(nullptr) {
920 setHeaderFlagBits(IsDictionaryFlag
| CanHaveTableFlag
);
921 for (uint32_t i
= 0; i
< length
; i
++) {
922 initProperty(i
, orig
->getKey(i
), orig
->getPropertyInfo(i
));
926 DictionaryPropMap(JS::Handle
<CompactPropMap
*> orig
, uint32_t length
)
927 : linkedData_(nullptr) {
928 setHeaderFlagBits(IsDictionaryFlag
| CanHaveTableFlag
);
929 for (uint32_t i
= 0; i
< length
; i
++) {
930 initProperty(i
, orig
->getKey(i
), orig
->getPropertyInfo(i
));
934 void initProperty(uint32_t index
, PropertyKey key
, PropertyInfo prop
) {
935 MOZ_ASSERT(!hasKey(index
));
937 linkedData_
.propInfos
[index
] = prop
;
940 void initPrevious(DictionaryPropMap
* prev
) {
942 linkedData_
.previous
.init(prev
);
943 setHeaderFlagBits(HasPrevFlag
);
945 void clearPrevious() {
946 linkedData_
.previous
= nullptr;
947 clearHeaderFlagBits(HasPrevFlag
);
950 void clearProperty(uint32_t index
) { setKey(index
, PropertyKey::Void()); }
952 static void skipTrailingHoles(MutableHandle
<DictionaryPropMap
*> map
,
953 uint32_t* mapLength
);
955 void handOffLastMapStateTo(DictionaryPropMap
* newLast
);
957 void incHoleCount() { holeCount_
++; }
958 void decHoleCount() {
959 MOZ_ASSERT(holeCount_
> 0);
962 static void maybeCompact(JSContext
* cx
, MutableHandle
<DictionaryPropMap
*> map
,
963 uint32_t* mapLength
);
966 bool isDictionary() const = delete;
967 bool isShared() const = delete;
968 bool isCompact() const = delete;
969 bool isNormal() const = delete;
970 bool isLinked() const = delete;
971 DictionaryPropMap
* asDictionary() = delete;
972 const DictionaryPropMap
* asDictionary() const = delete;
974 void fixupAfterMovingGC() {}
975 inline void finalize(JS::GCContext
* gcx
);
977 DictionaryPropMap
* previous() const {
978 return static_cast<DictionaryPropMap
*>(linkedData_
.previous
.get());
981 uint32_t freeList() const { return freeList_
; }
982 void setFreeList(uint32_t slot
) { freeList_
= slot
; }
984 PropertyInfo
getPropertyInfo(uint32_t index
) const {
985 MOZ_ASSERT(hasKey(index
));
986 return linkedData_
.propInfos
[index
];
989 // Add a new property to this map. Returns the new map/mapLength and object
990 // flags. The caller is responsible for generating a new dictionary shape.
991 static bool addProperty(JSContext
* cx
, const JSClass
* clasp
,
992 MutableHandle
<DictionaryPropMap
*> map
,
993 uint32_t* mapLength
, HandleId id
, PropertyFlags flags
,
994 uint32_t slot
, ObjectFlags
* objectFlags
);
996 // Remove the property referenced by the table pointer. Returns the new
997 // map/mapLength. The caller is responsible for generating a new dictionary
999 static void removeProperty(JSContext
* cx
,
1000 MutableHandle
<DictionaryPropMap
*> map
,
1001 uint32_t* mapLength
, PropMapTable
* table
,
1002 PropMapTable::Ptr
& ptr
);
1004 // Turn all sparse elements into dense elements. The caller is responsible
1005 // for checking all sparse elements are plain data properties and must
1006 // generate a new shape for the object.
1007 static void densifyElements(JSContext
* cx
,
1008 MutableHandle
<DictionaryPropMap
*> map
,
1009 uint32_t* mapLength
, NativeObject
* obj
);
1011 // Freeze or seal all properties in this map. Returns the new object flags.
1012 // The caller is responsible for generating a new shape for the object.
1013 void freezeOrSealProperties(JSContext
* cx
, IntegrityLevel level
,
1014 const JSClass
* clasp
, uint32_t mapLength
,
1015 ObjectFlags
* objectFlags
);
1017 // Change a property's slot number and/or flags and return the new object
1018 // flags. The caller is responsible for generating a new shape.
1019 void changeProperty(JSContext
* cx
, const JSClass
* clasp
, uint32_t index
,
1020 PropertyFlags flags
, uint32_t slot
,
1021 ObjectFlags
* objectFlags
);
1023 // Like changeProperty, but doesn't change the slot number.
1024 void changePropertyFlags(JSContext
* cx
, const JSClass
* clasp
, uint32_t index
,
1025 PropertyFlags flags
, ObjectFlags
* objectFlags
) {
1026 uint32_t slot
= getPropertyInfo(index
).maybeSlot();
1027 changeProperty(cx
, clasp
, index
, flags
, slot
, objectFlags
);
1030 static void staticAsserts() {
1031 static_assert(offsetof(DictionaryPropMap
, linkedData_
) ==
1032 offsetof(LinkedPropMap
, data_
));
1036 inline CompactPropMap
* PropMap::asCompact() {
1037 MOZ_ASSERT(isCompact());
1038 return static_cast<CompactPropMap
*>(this);
1040 inline const CompactPropMap
* PropMap::asCompact() const {
1041 MOZ_ASSERT(isCompact());
1042 return static_cast<const CompactPropMap
*>(this);
1044 inline LinkedPropMap
* PropMap::asLinked() {
1045 MOZ_ASSERT(isLinked());
1046 return static_cast<LinkedPropMap
*>(this);
1048 inline const LinkedPropMap
* PropMap::asLinked() const {
1049 MOZ_ASSERT(isLinked());
1050 return static_cast<const LinkedPropMap
*>(this);
1052 inline NormalPropMap
* PropMap::asNormal() {
1053 MOZ_ASSERT(isNormal());
1054 return static_cast<NormalPropMap
*>(this);
1056 inline const NormalPropMap
* PropMap::asNormal() const {
1057 MOZ_ASSERT(isNormal());
1058 return static_cast<const NormalPropMap
*>(this);
1060 inline SharedPropMap
* PropMap::asShared() {
1061 MOZ_ASSERT(isShared());
1062 return static_cast<SharedPropMap
*>(this);
1064 inline const SharedPropMap
* PropMap::asShared() const {
1065 MOZ_ASSERT(isShared());
1066 return static_cast<const SharedPropMap
*>(this);
1068 inline DictionaryPropMap
* PropMap::asDictionary() {
1069 MOZ_ASSERT(isDictionary());
1070 return static_cast<DictionaryPropMap
*>(this);
1072 inline const DictionaryPropMap
* PropMap::asDictionary() const {
1073 MOZ_ASSERT(isDictionary());
1074 return static_cast<const DictionaryPropMap
*>(this);
1077 inline PropertyInfo
PropMap::getPropertyInfo(uint32_t index
) const {
1078 return isCompact() ? asCompact()->getPropertyInfo(index
)
1079 : asLinked()->getPropertyInfo(index
);
1082 inline SharedPropMap::TreeData
& SharedPropMap::treeDataRef() {
1083 return isCompact() ? asCompact()->treeDataRef() : asNormal()->treeDataRef();
1086 inline const SharedPropMap::TreeData
& SharedPropMap::treeDataRef() const {
1087 return isCompact() ? asCompact()->treeDataRef() : asNormal()->treeDataRef();
1090 inline void SharedPropMap::initProperty(uint32_t index
, PropertyKey key
,
1091 PropertyInfo prop
) {
1093 asCompact()->initProperty(index
, key
, prop
);
1095 asNormal()->initProperty(index
, key
, prop
);
1099 template <typename T
>
1100 inline PropertyInfo MapAndIndex
<T
>::propertyInfo() const {
1101 MOZ_ASSERT(!isNone());
1102 return map()->getPropertyInfo(index());
1105 MOZ_ALWAYS_INLINE HashNumber
PropMapTable::Hasher::hash(PropertyKey key
) {
1106 return HashPropertyKey(key
);
1108 MOZ_ALWAYS_INLINE
bool PropMapTable::Hasher::match(PropMapAndIndex entry
,
1110 MOZ_ASSERT(entry
.map()->hasKey(entry
.index()));
1111 return entry
.map()->getKey(entry
.index()) == key
;
1114 // Hash policy for SharedPropMap children.
1115 struct SharedChildrenHasher
{
1116 using Key
= SharedPropMapAndIndex
;
1123 Lookup(PropertyKey key
, PropertyInfo prop
, uint8_t index
)
1124 : key(key
), prop(prop
), index(index
) {}
1125 Lookup(PropertyInfoWithKey prop
, uint8_t index
)
1126 : key(prop
.key()), prop(prop
), index(index
) {}
1129 static HashNumber
hash(const Lookup
& l
) {
1130 HashNumber hash
= HashPropertyKey(l
.key
);
1131 return mozilla::AddToHash(hash
, l
.prop
.toRaw(), l
.index
);
1133 static bool match(SharedPropMapAndIndex k
, const Lookup
& l
) {
1134 SharedPropMap
* map
= k
.map();
1135 uint32_t index
= k
.index();
1136 uint32_t newIndex
= SharedPropMap::indexOfNextProperty(index
);
1137 return index
== l
.index
&& map
->matchProperty(newIndex
, l
.key
, l
.prop
);
1143 // JS::ubi::Nodes can point to PropMaps; they're js::gc::Cell instances
1144 // with no associated compartment.
1149 class Concrete
<js::PropMap
> : TracerConcrete
<js::PropMap
> {
1151 explicit Concrete(js::PropMap
* ptr
) : TracerConcrete
<js::PropMap
>(ptr
) {}
1154 static void construct(void* storage
, js::PropMap
* ptr
) {
1155 new (storage
) Concrete(ptr
);
1158 Size
size(mozilla::MallocSizeOf mallocSizeOf
) const override
;
1160 const char16_t
* typeName() const override
{ return concreteTypeName
; }
1161 static const char16_t concreteTypeName
[];
1167 #endif // vm_PropMap_h