Line data Source code
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/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.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>
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 0 : Object ValueAt(int entry) {
35 5529076 : return this->get(DerivedHashTable::EntryToIndex(entry) + 1);
36 : }
37 :
38 : // Set the value for entry.
39 0 : void ValueAtPut(int entry, Object value) {
40 3150060 : this->set(DerivedHashTable::EntryToIndex(entry) + 1, value);
41 0 : }
42 :
43 : // Returns the property details for the property at entry.
44 267361102 : PropertyDetails DetailsAt(int entry) {
45 267370397 : return Shape::DetailsAt(Derived::cast(*this), entry);
46 : }
47 :
48 : // Set the details for entry.
49 12946223 : void DetailsAtPut(Isolate* isolate, int entry, PropertyDetails value) {
50 17537278 : Shape::DetailsAtPut(isolate, Derived::cast(*this), entry, value);
51 12946220 : }
52 :
53 : // Delete a property from the dictionary.
54 : V8_WARN_UNUSED_RESULT static Handle<Derived> DeleteEntry(
55 : Isolate* isolate, Handle<Derived> dictionary, int entry);
56 :
57 : // Attempt to shrink the dictionary after deletion of key.
58 261 : V8_WARN_UNUSED_RESULT static inline Handle<Derived> Shrink(
59 : Isolate* isolate, Handle<Derived> dictionary) {
60 47473 : return DerivedHashTable::Shrink(isolate, dictionary);
61 : }
62 :
63 : int NumberOfEnumerableProperties();
64 :
65 : #ifdef OBJECT_PRINT
66 : // For our gdb macros, we should perhaps change these in the future.
67 : void Print();
68 :
69 : void Print(std::ostream& os); // NOLINT
70 : #endif
71 : // Returns the key (slow).
72 : Object SlowReverseLookup(Object value);
73 :
74 : // Sets the entry to (key, value) pair.
75 : inline void ClearEntry(Isolate* isolate, int entry);
76 : inline void SetEntry(Isolate* isolate, int entry, Object key, Object value,
77 : PropertyDetails details);
78 :
79 : V8_WARN_UNUSED_RESULT static Handle<Derived> Add(
80 : Isolate* isolate, Handle<Derived> dictionary, Key key,
81 : Handle<Object> value, PropertyDetails details, int* entry_out = nullptr);
82 :
83 : protected:
84 : // Generic at put operation.
85 : V8_WARN_UNUSED_RESULT static Handle<Derived> AtPut(Isolate* isolate,
86 : Handle<Derived> dictionary,
87 : Key key,
88 : Handle<Object> value,
89 : PropertyDetails details);
90 :
91 0 : OBJECT_CONSTRUCTORS(Dictionary, HashTable<Derived, Shape>);
92 : };
93 :
94 : template <typename Key>
95 : class BaseDictionaryShape : public BaseShape<Key> {
96 : public:
97 : static const bool kHasDetails = true;
98 : template <typename Dictionary>
99 : static inline PropertyDetails DetailsAt(Dictionary dict, int entry) {
100 : STATIC_ASSERT(Dictionary::kEntrySize == 3);
101 : DCHECK_GE(entry, 0); // Not found is -1, which is not caught by get().
102 : return PropertyDetails(Smi::cast(dict->get(
103 101060594 : Dictionary::EntryToIndex(entry) + Dictionary::kEntryDetailsIndex)));
104 : }
105 :
106 : template <typename Dictionary>
107 9200405 : static inline void DetailsAtPut(Isolate* isolate, Dictionary dict, int entry,
108 : PropertyDetails value) {
109 : STATIC_ASSERT(Dictionary::kEntrySize == 3);
110 : dict->set(Dictionary::EntryToIndex(entry) + Dictionary::kEntryDetailsIndex,
111 : value.AsSmi());
112 9200405 : }
113 : };
114 :
115 : class NameDictionaryShape : public BaseDictionaryShape<Handle<Name>> {
116 : public:
117 : static inline bool IsMatch(Handle<Name> key, Object other);
118 : static inline uint32_t Hash(Isolate* isolate, Handle<Name> key);
119 : static inline uint32_t HashForObject(ReadOnlyRoots roots, Object object);
120 : static inline Handle<Object> AsHandle(Isolate* isolate, Handle<Name> key);
121 : static inline RootIndex GetMapRootIndex();
122 : static const int kPrefixSize = 2;
123 : static const int kEntrySize = 3;
124 : static const int kEntryValueIndex = 1;
125 : static const bool kNeedsHoleCheck = false;
126 : };
127 :
128 : template <typename Derived, typename Shape>
129 : class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) BaseNameDictionary
130 : : public Dictionary<Derived, Shape> {
131 : using Key = typename Shape::Key;
132 :
133 : public:
134 : static const int kNextEnumerationIndexIndex =
135 : HashTableBase::kPrefixStartIndex;
136 : static const int kObjectHashIndex = kNextEnumerationIndexIndex + 1;
137 : static const int kEntryValueIndex = 1;
138 :
139 : // Accessors for next enumeration index.
140 0 : void SetNextEnumerationIndex(int index) {
141 : DCHECK_NE(0, index);
142 : this->set(kNextEnumerationIndexIndex, Smi::FromInt(index));
143 0 : }
144 :
145 0 : int NextEnumerationIndex() {
146 0 : return Smi::ToInt(this->get(kNextEnumerationIndexIndex));
147 : }
148 :
149 0 : void SetHash(int hash) {
150 : DCHECK(PropertyArray::HashField::is_valid(hash));
151 : this->set(kObjectHashIndex, Smi::FromInt(hash));
152 0 : }
153 :
154 0 : int Hash() const {
155 : Object hash_obj = this->get(kObjectHashIndex);
156 : int hash = Smi::ToInt(hash_obj);
157 : DCHECK(PropertyArray::HashField::is_valid(hash));
158 0 : return hash;
159 : }
160 :
161 : // Creates a new dictionary.
162 : V8_WARN_UNUSED_RESULT static Handle<Derived> New(
163 : Isolate* isolate, int at_least_space_for,
164 : AllocationType allocation = AllocationType::kYoung,
165 : MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY);
166 :
167 : // Collect the keys into the given KeyAccumulator, in ascending chronological
168 : // order of property creation.
169 : static void CollectKeysTo(Handle<Derived> dictionary, KeyAccumulator* keys);
170 :
171 : // Return the key indices sorted by its enumeration index.
172 : static Handle<FixedArray> IterationIndices(Isolate* isolate,
173 : Handle<Derived> dictionary);
174 :
175 : // Copies enumerable keys to preallocated fixed array.
176 : // Does not throw for uninitialized exports in module namespace objects, so
177 : // this has to be checked separately.
178 : static void CopyEnumKeysTo(Isolate* isolate, Handle<Derived> dictionary,
179 : Handle<FixedArray> storage, KeyCollectionMode mode,
180 : KeyAccumulator* accumulator);
181 :
182 : // Ensure enough space for n additional elements.
183 : static Handle<Derived> EnsureCapacity(Isolate* isolate,
184 : Handle<Derived> dictionary, int n);
185 :
186 : V8_WARN_UNUSED_RESULT static Handle<Derived> AddNoUpdateNextEnumerationIndex(
187 : Isolate* isolate, Handle<Derived> dictionary, Key key,
188 : Handle<Object> value, PropertyDetails details, int* entry_out = nullptr);
189 :
190 : V8_WARN_UNUSED_RESULT static Handle<Derived> Add(
191 : Isolate* isolate, Handle<Derived> dictionary, Key key,
192 : Handle<Object> value, PropertyDetails details, int* entry_out = nullptr);
193 :
194 0 : OBJECT_CONSTRUCTORS(BaseNameDictionary, Dictionary<Derived, Shape>);
195 : };
196 :
197 : class NameDictionary;
198 :
199 : extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
200 : BaseNameDictionary<NameDictionary, NameDictionaryShape>;
201 :
202 : class V8_EXPORT_PRIVATE NameDictionary
203 : : public BaseNameDictionary<NameDictionary, NameDictionaryShape> {
204 : public:
205 : DECL_CAST(NameDictionary)
206 :
207 : static const int kEntryDetailsIndex = 2;
208 : static const int kInitialCapacity = 2;
209 :
210 : inline Name NameAt(int entry);
211 : inline void set_hash(int hash);
212 : inline int hash() const;
213 :
214 : OBJECT_CONSTRUCTORS(NameDictionary,
215 : BaseNameDictionary<NameDictionary, NameDictionaryShape>);
216 : };
217 :
218 : class GlobalDictionaryShape : public NameDictionaryShape {
219 : public:
220 : static inline bool IsMatch(Handle<Name> key, Object other);
221 : static inline uint32_t HashForObject(ReadOnlyRoots roots, Object object);
222 :
223 : static const int kEntrySize = 1; // Overrides NameDictionaryShape::kEntrySize
224 :
225 : template <typename Dictionary>
226 : static inline PropertyDetails DetailsAt(Dictionary dict, int entry);
227 :
228 : template <typename Dictionary>
229 : static inline void DetailsAtPut(Isolate* isolate, Dictionary dict, int entry,
230 : PropertyDetails value);
231 :
232 : static inline Object Unwrap(Object key);
233 : static inline bool IsKey(ReadOnlyRoots roots, Object k);
234 : static inline bool IsLive(ReadOnlyRoots roots, Object key);
235 : static inline RootIndex GetMapRootIndex();
236 : };
237 :
238 : class GlobalDictionary;
239 :
240 : extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
241 : BaseNameDictionary<GlobalDictionary, GlobalDictionaryShape>;
242 :
243 : class V8_EXPORT_PRIVATE GlobalDictionary
244 : : public BaseNameDictionary<GlobalDictionary, GlobalDictionaryShape> {
245 : public:
246 : DECL_CAST(GlobalDictionary)
247 :
248 : inline Object ValueAt(int entry);
249 : inline PropertyCell CellAt(int entry);
250 : inline void SetEntry(Isolate* isolate, int entry, Object key, Object value,
251 : PropertyDetails details);
252 : inline Name NameAt(int entry);
253 : inline void ValueAtPut(int entry, Object value);
254 :
255 : OBJECT_CONSTRUCTORS(
256 : GlobalDictionary,
257 : BaseNameDictionary<GlobalDictionary, GlobalDictionaryShape>);
258 : };
259 :
260 : class NumberDictionaryBaseShape : public BaseDictionaryShape<uint32_t> {
261 : public:
262 : static inline bool IsMatch(uint32_t key, Object other);
263 : static inline Handle<Object> AsHandle(Isolate* isolate, uint32_t key);
264 :
265 : static inline uint32_t Hash(Isolate* isolate, uint32_t key);
266 : static inline uint32_t HashForObject(ReadOnlyRoots roots, Object object);
267 : };
268 :
269 : class NumberDictionaryShape : public NumberDictionaryBaseShape {
270 : public:
271 : static const int kPrefixSize = 1;
272 : static const int kEntrySize = 3;
273 :
274 : static inline RootIndex GetMapRootIndex();
275 : };
276 :
277 : class SimpleNumberDictionaryShape : public NumberDictionaryBaseShape {
278 : public:
279 : static const bool kHasDetails = false;
280 : static const int kPrefixSize = 0;
281 : static const int kEntrySize = 2;
282 :
283 : template <typename Dictionary>
284 0 : static inline PropertyDetails DetailsAt(Dictionary dict, int entry) {
285 0 : UNREACHABLE();
286 : }
287 :
288 : template <typename Dictionary>
289 0 : static inline void DetailsAtPut(Isolate* isolate, Dictionary dict, int entry,
290 : PropertyDetails value) {
291 0 : UNREACHABLE();
292 : }
293 :
294 : static inline RootIndex GetMapRootIndex();
295 : };
296 :
297 : extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
298 : HashTable<SimpleNumberDictionary, SimpleNumberDictionaryShape>;
299 :
300 : extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
301 : Dictionary<SimpleNumberDictionary, SimpleNumberDictionaryShape>;
302 :
303 : // SimpleNumberDictionary is used to map number to an entry.
304 : class SimpleNumberDictionary
305 : : public Dictionary<SimpleNumberDictionary, SimpleNumberDictionaryShape> {
306 : public:
307 : DECL_CAST(SimpleNumberDictionary)
308 : // Type specific at put (default NONE attributes is used when adding).
309 : V8_WARN_UNUSED_RESULT static Handle<SimpleNumberDictionary> Set(
310 : Isolate* isolate, Handle<SimpleNumberDictionary> dictionary, uint32_t key,
311 : Handle<Object> value);
312 :
313 : static const int kEntryValueIndex = 1;
314 :
315 : OBJECT_CONSTRUCTORS(
316 : SimpleNumberDictionary,
317 : Dictionary<SimpleNumberDictionary, SimpleNumberDictionaryShape>);
318 : };
319 :
320 : extern template class EXPORT_TEMPLATE_DECLARE(
321 : V8_EXPORT_PRIVATE) HashTable<NumberDictionary, NumberDictionaryShape>;
322 :
323 : extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
324 : Dictionary<NumberDictionary, NumberDictionaryShape>;
325 :
326 : // NumberDictionary is used as elements backing store and provides a bitfield
327 : // and stores property details for every entry.
328 : class NumberDictionary
329 : : public Dictionary<NumberDictionary, NumberDictionaryShape> {
330 : public:
331 : DECL_CAST(NumberDictionary)
332 : DECL_PRINTER(NumberDictionary)
333 :
334 : // Type specific at put (default NONE attributes is used when adding).
335 : V8_WARN_UNUSED_RESULT static Handle<NumberDictionary> Set(
336 : Isolate* isolate, Handle<NumberDictionary> dictionary, uint32_t key,
337 : Handle<Object> value,
338 : Handle<JSObject> dictionary_holder = Handle<JSObject>::null(),
339 : PropertyDetails details = PropertyDetails::Empty());
340 :
341 : static const int kMaxNumberKeyIndex = kPrefixStartIndex;
342 : void UpdateMaxNumberKey(uint32_t key, Handle<JSObject> dictionary_holder);
343 :
344 : // Returns true if the dictionary contains any elements that are non-writable,
345 : // non-configurable, non-enumerable, or have getters/setters.
346 : bool HasComplexElements();
347 :
348 : // Sorting support
349 : void CopyValuesTo(FixedArray elements);
350 :
351 : // If slow elements are required we will never go back to fast-case
352 : // for the elements kept in this dictionary. We require slow
353 : // elements if an element has been added at an index larger than
354 : // kRequiresSlowElementsLimit or set_requires_slow_elements() has been called
355 : // when defining a getter or setter with a number key.
356 : inline bool requires_slow_elements();
357 : inline void set_requires_slow_elements();
358 :
359 : // Get the value of the max number key that has been added to this
360 : // dictionary. max_number_key can only be called if
361 : // requires_slow_elements returns false.
362 : inline uint32_t max_number_key();
363 :
364 : static const int kEntryValueIndex = 1;
365 : static const int kEntryDetailsIndex = 2;
366 :
367 : // Bit masks.
368 : static const int kRequiresSlowElementsMask = 1;
369 : static const int kRequiresSlowElementsTagSize = 1;
370 : static const uint32_t kRequiresSlowElementsLimit = (1 << 29) - 1;
371 :
372 : // JSObjects prefer dictionary elements if the dictionary saves this much
373 : // memory compared to a fast elements backing store.
374 : static const uint32_t kPreferFastElementsSizeFactor = 3;
375 :
376 : OBJECT_CONSTRUCTORS(NumberDictionary,
377 : Dictionary<NumberDictionary, NumberDictionaryShape>);
378 : };
379 :
380 : } // namespace internal
381 : } // namespace v8
382 :
383 : #include "src/objects/object-macros-undef.h"
384 :
385 : #endif // V8_OBJECTS_DICTIONARY_H_
|
