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