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