1 // Copyright 2017 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef V8_OBJECTS_DICTIONARY_H_
6 #define V8_OBJECTS_DICTIONARY_H_
7
8 #include "src/base/export-template.h"
9 #include "src/base/optional.h"
10 #include "src/common/globals.h"
11 #include "src/objects/hash-table.h"
12 #include "src/objects/property-array.h"
13 #include "src/objects/smi.h"
14 #include "src/roots/roots.h"
15
16 // Has to be the last include (doesn't have include guards):
17 #include "src/objects/object-macros.h"
18
19 namespace v8 {
20 namespace internal {
21
22 #ifdef V8_ENABLE_SWISS_NAME_DICTIONARY
23 class SwissNameDictionary;
24 using PropertyDictionary = SwissNameDictionary;
25 #else
26 using PropertyDictionary = NameDictionary;
27 #endif
28
29 template <typename T>
30 class Handle;
31
32 class Isolate;
33
34 template <typename Derived, typename Shape>
EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)35 class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Dictionary
36 : public HashTable<Derived, Shape> {
37 using DerivedHashTable = HashTable<Derived, Shape>;
38
39 public:
40 using Key = typename Shape::Key;
41 inline Object ValueAt(InternalIndex entry);
42 inline Object ValueAt(PtrComprCageBase cage_base, InternalIndex entry);
43 // Returns {} if we would be reading out of the bounds of the object.
44 inline base::Optional<Object> TryValueAt(InternalIndex entry);
45
46 // Set the value for entry.
47 inline void ValueAtPut(InternalIndex entry, Object value);
48
49 // Returns the property details for the property at entry.
50 inline PropertyDetails DetailsAt(InternalIndex entry);
51
52 // Set the details for entry.
53 inline void DetailsAtPut(InternalIndex entry, PropertyDetails value);
54
55 static const bool kIsOrderedDictionaryType = false;
56
57 // Delete a property from the dictionary.
58 V8_WARN_UNUSED_RESULT static Handle<Derived> DeleteEntry(
59 Isolate* isolate, Handle<Derived> dictionary, InternalIndex entry);
60
61 // Attempt to shrink the dictionary after deletion of key.
62 V8_WARN_UNUSED_RESULT static inline Handle<Derived> Shrink(
63 Isolate* isolate, Handle<Derived> dictionary) {
64 return DerivedHashTable::Shrink(isolate, dictionary);
65 }
66
67 int NumberOfEnumerableProperties();
68
69 // Returns the key (slow).
70 Object SlowReverseLookup(Object value);
71
72 inline void ClearEntry(InternalIndex entry);
73
74 // Sets the entry to (key, value) pair.
75 inline void SetEntry(InternalIndex entry, Object key, Object value,
76 PropertyDetails details);
77
78 // Garbage collection support.
79 inline ObjectSlot RawFieldOfValueAt(InternalIndex entry);
80
81 template <typename IsolateT>
82 V8_WARN_UNUSED_RESULT static Handle<Derived> Add(
83 IsolateT* isolate, Handle<Derived> dictionary, Key key,
84 Handle<Object> value, PropertyDetails details,
85 InternalIndex* entry_out = nullptr);
86
87 static Handle<Derived> ShallowCopy(Isolate* isolate,
88 Handle<Derived> dictionary);
89
90 protected:
91 // Generic at put operation.
92 V8_WARN_UNUSED_RESULT static Handle<Derived> AtPut(Isolate* isolate,
93 Handle<Derived> dictionary,
94 Key key,
95 Handle<Object> value,
96 PropertyDetails details);
97
98 OBJECT_CONSTRUCTORS(Dictionary, HashTable<Derived, Shape>);
99 };
100
101 #define EXTERN_DECLARE_DICTIONARY(DERIVED, SHAPE) \
102 EXTERN_DECLARE_HASH_TABLE(DERIVED, SHAPE) \
103 extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) \
104 Dictionary<DERIVED, SHAPE>;
105
106 template <typename Key>
107 class BaseDictionaryShape : public BaseShape<Key> {
108 public:
109 static const bool kHasDetails = true;
110 template <typename Dictionary>
111 static inline PropertyDetails DetailsAt(Dictionary dict, InternalIndex entry);
112
113 template <typename Dictionary>
114 static inline void DetailsAtPut(Dictionary dict, InternalIndex entry,
115 PropertyDetails value);
116 };
117
118 class NameDictionaryShape : public BaseDictionaryShape<Handle<Name>> {
119 public:
120 static inline bool IsMatch(Handle<Name> key, Object other);
121 static inline uint32_t Hash(ReadOnlyRoots roots, Handle<Name> key);
122 static inline uint32_t HashForObject(ReadOnlyRoots roots, Object object);
123 static inline Handle<Object> AsHandle(Isolate* isolate, Handle<Name> key);
124 static inline Handle<Object> AsHandle(LocalIsolate* isolate,
125 Handle<Name> key);
126 static const int kPrefixSize = 2;
127 static const int kEntrySize = 3;
128 static const int kEntryValueIndex = 1;
129 static const bool kMatchNeedsHoleCheck = false;
130 };
131
132 template <typename Derived, typename Shape>
EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)133 class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) BaseNameDictionary
134 : public Dictionary<Derived, Shape> {
135 using Key = typename Shape::Key;
136
137 public:
138 static const int kNextEnumerationIndexIndex =
139 HashTableBase::kPrefixStartIndex;
140 static const int kObjectHashIndex = kNextEnumerationIndexIndex + 1;
141 static const int kEntryValueIndex = 1;
142
143 inline void SetHash(int hash);
144 inline int Hash() const;
145
146 // Creates a new dictionary.
147 template <typename IsolateT>
148 V8_WARN_UNUSED_RESULT static Handle<Derived> New(
149 IsolateT* isolate, int at_least_space_for,
150 AllocationType allocation = AllocationType::kYoung,
151 MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY);
152
153 // Allocate the next enumeration index. Possibly updates all enumeration
154 // indices in the table.
155 static int NextEnumerationIndex(Isolate* isolate, Handle<Derived> dictionary);
156 // Accessors for next enumeration index.
157 inline int next_enumeration_index();
158 inline void set_next_enumeration_index(int index);
159
160 // Return the key indices sorted by its enumeration index.
161 static Handle<FixedArray> IterationIndices(Isolate* isolate,
162 Handle<Derived> dictionary);
163
164 template <typename IsolateT>
165 V8_WARN_UNUSED_RESULT static Handle<Derived> AddNoUpdateNextEnumerationIndex(
166 IsolateT* isolate, Handle<Derived> dictionary, Key key,
167 Handle<Object> value, PropertyDetails details,
168 InternalIndex* entry_out = nullptr);
169
170 V8_WARN_UNUSED_RESULT static Handle<Derived> Add(
171 Isolate* isolate, Handle<Derived> dictionary, Key key,
172 Handle<Object> value, PropertyDetails details,
173 InternalIndex* entry_out = nullptr);
174
175 OBJECT_CONSTRUCTORS(BaseNameDictionary, Dictionary<Derived, Shape>);
176 };
177
178 #define EXTERN_DECLARE_BASE_NAME_DICTIONARY(DERIVED, SHAPE) \
179 EXTERN_DECLARE_DICTIONARY(DERIVED, SHAPE) \
180 extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) \
181 BaseNameDictionary<DERIVED, SHAPE>;
182
EXTERN_DECLARE_BASE_NAME_DICTIONARY(NameDictionary,NameDictionaryShape)183 EXTERN_DECLARE_BASE_NAME_DICTIONARY(NameDictionary, NameDictionaryShape)
184
185 class V8_EXPORT_PRIVATE NameDictionary
186 : public BaseNameDictionary<NameDictionary, NameDictionaryShape> {
187 public:
188 static inline Handle<Map> GetMap(ReadOnlyRoots roots);
189
190 DECL_CAST(NameDictionary)
191 DECL_PRINTER(NameDictionary)
192
193 static const int kEntryValueIndex = 1;
194 static const int kEntryDetailsIndex = 2;
195 static const int kInitialCapacity = 2;
196
197 inline Name NameAt(InternalIndex entry);
198 inline Name NameAt(PtrComprCageBase cage_base, InternalIndex entry);
199
200 inline void set_hash(int hash);
201 inline int hash() const;
202
203 OBJECT_CONSTRUCTORS(NameDictionary,
204 BaseNameDictionary<NameDictionary, NameDictionaryShape>);
205 };
206
207 class V8_EXPORT_PRIVATE GlobalDictionaryShape : public NameDictionaryShape {
208 public:
209 static inline bool IsMatch(Handle<Name> key, Object other);
210 static inline uint32_t HashForObject(ReadOnlyRoots roots, Object object);
211
212 static const int kEntrySize = 1; // Overrides NameDictionaryShape::kEntrySize
213 static const bool kMatchNeedsHoleCheck = true;
214
215 template <typename Dictionary>
216 static inline PropertyDetails DetailsAt(Dictionary dict, InternalIndex entry);
217
218 template <typename Dictionary>
219 static inline void DetailsAtPut(Dictionary dict, InternalIndex entry,
220 PropertyDetails value);
221
222 static inline Object Unwrap(Object key);
223 };
224
EXTERN_DECLARE_BASE_NAME_DICTIONARY(GlobalDictionary,GlobalDictionaryShape)225 EXTERN_DECLARE_BASE_NAME_DICTIONARY(GlobalDictionary, GlobalDictionaryShape)
226
227 class V8_EXPORT_PRIVATE GlobalDictionary
228 : public BaseNameDictionary<GlobalDictionary, GlobalDictionaryShape> {
229 public:
230 static inline Handle<Map> GetMap(ReadOnlyRoots roots);
231
232 DECL_CAST(GlobalDictionary)
233 DECL_PRINTER(GlobalDictionary)
234
235 inline Object ValueAt(InternalIndex entry);
236 inline Object ValueAt(PtrComprCageBase cage_base, InternalIndex entry);
237 inline PropertyCell CellAt(InternalIndex entry);
238 inline PropertyCell CellAt(PtrComprCageBase cage_base, InternalIndex entry);
239 inline void SetEntry(InternalIndex entry, Object key, Object value,
240 PropertyDetails details);
241 inline void ClearEntry(InternalIndex entry);
242 inline Name NameAt(InternalIndex entry);
243 inline Name NameAt(PtrComprCageBase cage_base, InternalIndex entry);
244 inline void ValueAtPut(InternalIndex entry, Object value);
245
246 base::Optional<PropertyCell> TryFindPropertyCellForConcurrentLookupIterator(
247 Isolate* isolate, Handle<Name> name, RelaxedLoadTag tag);
248
249 OBJECT_CONSTRUCTORS(
250 GlobalDictionary,
251 BaseNameDictionary<GlobalDictionary, GlobalDictionaryShape>);
252 };
253
254 class NumberDictionaryBaseShape : public BaseDictionaryShape<uint32_t> {
255 public:
256 static inline bool IsMatch(uint32_t key, Object other);
257 static inline Handle<Object> AsHandle(Isolate* isolate, uint32_t key);
258 static inline Handle<Object> AsHandle(LocalIsolate* isolate, uint32_t key);
259
260 static inline uint32_t Hash(ReadOnlyRoots roots, uint32_t key);
261 static inline uint32_t HashForObject(ReadOnlyRoots roots, Object object);
262
263 static const bool kMatchNeedsHoleCheck = true;
264 };
265
266 class NumberDictionaryShape : public NumberDictionaryBaseShape {
267 public:
268 static const int kPrefixSize = 1;
269 static const int kEntrySize = 3;
270 };
271
272 class SimpleNumberDictionaryShape : public NumberDictionaryBaseShape {
273 public:
274 static const bool kHasDetails = false;
275 static const int kPrefixSize = 0;
276 static const int kEntrySize = 2;
277
278 template <typename Dictionary>
DetailsAt(Dictionary dict,InternalIndex entry)279 static inline PropertyDetails DetailsAt(Dictionary dict,
280 InternalIndex entry) {
281 UNREACHABLE();
282 }
283
284 template <typename Dictionary>
DetailsAtPut(Dictionary dict,InternalIndex entry,PropertyDetails value)285 static inline void DetailsAtPut(Dictionary dict, InternalIndex entry,
286 PropertyDetails value) {
287 UNREACHABLE();
288 }
289 };
290
EXTERN_DECLARE_DICTIONARY(SimpleNumberDictionary,SimpleNumberDictionaryShape)291 EXTERN_DECLARE_DICTIONARY(SimpleNumberDictionary, SimpleNumberDictionaryShape)
292
293 // SimpleNumberDictionary is used to map number to an entry.
294 class SimpleNumberDictionary
295 : public Dictionary<SimpleNumberDictionary, SimpleNumberDictionaryShape> {
296 public:
297 static inline Handle<Map> GetMap(ReadOnlyRoots roots);
298
299 DECL_CAST(SimpleNumberDictionary)
300 // Type specific at put (default NONE attributes is used when adding).
301 V8_EXPORT_PRIVATE V8_WARN_UNUSED_RESULT static Handle<SimpleNumberDictionary>
302 Set(Isolate* isolate, Handle<SimpleNumberDictionary> dictionary, uint32_t key,
303 Handle<Object> value);
304
305 static const int kEntryValueIndex = 1;
306
307 OBJECT_CONSTRUCTORS(
308 SimpleNumberDictionary,
309 Dictionary<SimpleNumberDictionary, SimpleNumberDictionaryShape>);
310 };
311
EXTERN_DECLARE_DICTIONARY(NumberDictionary,NumberDictionaryShape)312 EXTERN_DECLARE_DICTIONARY(NumberDictionary, NumberDictionaryShape)
313
314 // NumberDictionary is used as elements backing store and provides a bitfield
315 // and stores property details for every entry.
316 class NumberDictionary
317 : public Dictionary<NumberDictionary, NumberDictionaryShape> {
318 public:
319 static inline Handle<Map> GetMap(ReadOnlyRoots roots);
320
321 DECL_CAST(NumberDictionary)
322 DECL_PRINTER(NumberDictionary)
323
324 // Type specific at put (default NONE attributes is used when adding).
325 V8_WARN_UNUSED_RESULT static Handle<NumberDictionary> Set(
326 Isolate* isolate, Handle<NumberDictionary> dictionary, uint32_t key,
327 Handle<Object> value,
328 Handle<JSObject> dictionary_holder = Handle<JSObject>::null(),
329 PropertyDetails details = PropertyDetails::Empty());
330
331 static const int kMaxNumberKeyIndex = kPrefixStartIndex;
332 void UpdateMaxNumberKey(uint32_t key, Handle<JSObject> dictionary_holder);
333
334 // Sorting support
335 void CopyValuesTo(FixedArray elements);
336
337 // If slow elements are required we will never go back to fast-case
338 // for the elements kept in this dictionary. We require slow
339 // elements if an element has been added at an index larger than
340 // kRequiresSlowElementsLimit or set_requires_slow_elements() has been called
341 // when defining a getter or setter with a number key.
342 inline bool requires_slow_elements();
343 inline void set_requires_slow_elements();
344
345 // Get the value of the max number key that has been added to this
346 // dictionary. max_number_key can only be called if
347 // requires_slow_elements returns false.
348 inline uint32_t max_number_key();
349
350 static const int kEntryValueIndex = 1;
351 static const int kEntryDetailsIndex = 2;
352
353 // Bit masks.
354 static const int kRequiresSlowElementsMask = 1;
355 static const int kRequiresSlowElementsTagSize = 1;
356 static const uint32_t kRequiresSlowElementsLimit = (1 << 29) - 1;
357
358 // JSObjects prefer dictionary elements if the dictionary saves this much
359 // memory compared to a fast elements backing store.
360 static const uint32_t kPreferFastElementsSizeFactor = 3;
361
362 OBJECT_CONSTRUCTORS(NumberDictionary,
363 Dictionary<NumberDictionary, NumberDictionaryShape>);
364 };
365
366 // The comparator is passed two indices |a| and |b|, and it returns < 0 when the
367 // property at index |a| comes before the property at index |b| in the
368 // enumeration order.
369 template <typename Dictionary>
370 struct EnumIndexComparator {
EnumIndexComparatorEnumIndexComparator371 explicit EnumIndexComparator(Dictionary dict) : dict(dict) {}
operatorEnumIndexComparator372 bool operator()(Tagged_t a, Tagged_t b) {
373 PropertyDetails da(
374 dict.DetailsAt(InternalIndex(Smi(static_cast<Address>(a)).value())));
375 PropertyDetails db(
376 dict.DetailsAt(InternalIndex(Smi(static_cast<Address>(b)).value())));
377 return da.dictionary_index() < db.dictionary_index();
378 }
379 Dictionary dict;
380 };
381
382 } // namespace internal
383 } // namespace v8
384
385 #include "src/objects/object-macros-undef.h"
386
387 #endif // V8_OBJECTS_DICTIONARY_H_
388