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/objects/hash-table.h"
9 :
10 : // Has to be the last include (doesn't have include guards):
11 : #include "src/objects/object-macros.h"
12 :
13 : namespace v8 {
14 : namespace internal {
15 :
16 : template <typename T>
17 : class Handle;
18 :
19 : class Isolate;
20 :
21 : template <typename Derived, typename Shape, typename Key>
22 : class Dictionary : public HashTable<Derived, Shape, Key> {
23 : typedef HashTable<Derived, Shape, Key> DerivedHashTable;
24 :
25 : public:
26 : // Returns the value at entry.
27 277231587 : Object* ValueAt(int entry) {
28 554463174 : return this->get(Derived::EntryToIndex(entry) + 1);
29 : }
30 :
31 : // Set the value for entry.
32 0 : void ValueAtPut(int entry, Object* value) {
33 15683565 : this->set(Derived::EntryToIndex(entry) + 1, value);
34 0 : }
35 :
36 : // Returns the property details for the property at entry.
37 0 : PropertyDetails DetailsAt(int entry) {
38 153415709 : return Shape::DetailsAt(static_cast<Derived*>(this), entry);
39 : }
40 :
41 : // Set the details for entry.
42 0 : void DetailsAtPut(int entry, PropertyDetails value) {
43 44814 : Shape::DetailsAtPut(static_cast<Derived*>(this), entry, value);
44 0 : }
45 :
46 : // Returns true if property at given entry is deleted.
47 0 : bool IsDeleted(int entry) {
48 13622742 : return Shape::IsDeleted(static_cast<Derived*>(this), entry);
49 : }
50 :
51 : // Delete a property from the dictionary.
52 : static Handle<Object> DeleteProperty(Handle<Derived> dictionary, int entry);
53 :
54 : // Attempt to shrink the dictionary after deletion of key.
55 255 : MUST_USE_RESULT static inline Handle<Derived> Shrink(
56 : Handle<Derived> dictionary, Key key) {
57 6169921 : return DerivedHashTable::Shrink(dictionary, key);
58 : }
59 :
60 : // Returns the number of elements in the dictionary filtering out properties
61 : // with the specified attributes.
62 : int NumberOfElementsFilterAttributes(PropertyFilter filter);
63 :
64 : // Returns the number of enumerable elements in the dictionary.
65 0 : int NumberOfEnumElements() {
66 98422 : return NumberOfElementsFilterAttributes(ENUMERABLE_STRINGS);
67 : }
68 :
69 : enum SortMode { UNSORTED, SORTED };
70 :
71 : // Return the key indices sorted by its enumeration index.
72 : static Handle<FixedArray> IterationIndices(
73 : Handle<Dictionary<Derived, Shape, Key>> dictionary);
74 :
75 : // Collect the keys into the given KeyAccumulator, in ascending chronological
76 : // order of property creation.
77 : static void CollectKeysTo(Handle<Dictionary<Derived, Shape, Key>> dictionary,
78 132554 : KeyAccumulator* keys);
79 :
80 : // Copies enumerable keys to preallocated fixed array.
81 : static void CopyEnumKeysTo(Handle<Dictionary<Derived, Shape, Key>> dictionary,
82 : Handle<FixedArray> storage, KeyCollectionMode mode,
83 : KeyAccumulator* accumulator);
84 :
85 : // Accessors for next enumeration index.
86 0 : void SetNextEnumerationIndex(int index) {
87 : DCHECK(index != 0);
88 : this->set(kNextEnumerationIndexIndex, Smi::FromInt(index));
89 0 : }
90 :
91 0 : int NextEnumerationIndex() {
92 0 : return Smi::cast(this->get(kNextEnumerationIndexIndex))->value();
93 : }
94 :
95 : // Creates a new dictionary.
96 : MUST_USE_RESULT static Handle<Derived> New(
97 : Isolate* isolate, int at_least_space_for,
98 : PretenureFlag pretenure = NOT_TENURED,
99 : MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY);
100 :
101 : // Creates an dictionary with minimal possible capacity.
102 : MUST_USE_RESULT static Handle<Derived> NewEmpty(
103 : Isolate* isolate, PretenureFlag pretenure = NOT_TENURED);
104 :
105 : // Ensures that a new dictionary is created when the capacity is checked.
106 : void SetRequiresCopyOnCapacityChange();
107 :
108 : // Ensure enough space for n additional elements.
109 : static Handle<Derived> EnsureCapacity(Handle<Derived> obj, int n, Key key);
110 :
111 : #ifdef OBJECT_PRINT
112 : // For our gdb macros, we should perhaps change these in the future.
113 : void Print();
114 :
115 : void Print(std::ostream& os); // NOLINT
116 : #endif
117 : // Returns the key (slow).
118 : Object* SlowReverseLookup(Object* value);
119 :
120 : // Sets the entry to (key, value) pair.
121 : inline void SetEntry(int entry, Handle<Object> key, Handle<Object> value);
122 : inline void SetEntry(int entry, Handle<Object> key, Handle<Object> value,
123 : PropertyDetails details);
124 :
125 : MUST_USE_RESULT static Handle<Derived> Add(Handle<Derived> dictionary,
126 : Key key, Handle<Object> value,
127 : PropertyDetails details,
128 : int* entry_out = nullptr);
129 :
130 : static const int kMaxNumberKeyIndex = DerivedHashTable::kPrefixStartIndex;
131 : static const int kNextEnumerationIndexIndex = kMaxNumberKeyIndex + 1;
132 :
133 : static const bool kIsEnumerable = Shape::kIsEnumerable;
134 :
135 : protected:
136 : // Generic at put operation.
137 : MUST_USE_RESULT static Handle<Derived> AtPut(Handle<Derived> dictionary,
138 : Key key, Handle<Object> value);
139 : // Add entry to dictionary. Returns entry value.
140 : static int AddEntry(Handle<Derived> dictionary, Key key, Handle<Object> value,
141 : PropertyDetails details, uint32_t hash);
142 : };
143 :
144 : template <typename Derived, typename Shape>
145 : class NameDictionaryBase : public Dictionary<Derived, Shape, Handle<Name>> {
146 : typedef Dictionary<Derived, Shape, Handle<Name>> DerivedDictionary;
147 :
148 : public:
149 : // Find entry for key, otherwise return kNotFound. Optimized version of
150 : // HashTable::FindEntry.
151 : int FindEntry(Handle<Name> key);
152 : };
153 :
154 : template <typename Key>
155 : class BaseDictionaryShape : public BaseShape<Key> {
156 : public:
157 : template <typename Dictionary>
158 153415709 : static inline PropertyDetails DetailsAt(Dictionary* dict, int entry) {
159 : STATIC_ASSERT(Dictionary::kEntrySize == 3);
160 : DCHECK(entry >= 0); // Not found is -1, which is not caught by get().
161 : return PropertyDetails(Smi::cast(dict->get(
162 306831418 : Dictionary::EntryToIndex(entry) + Dictionary::kEntryDetailsIndex)));
163 : }
164 :
165 : template <typename Dictionary>
166 44814 : static inline void DetailsAtPut(Dictionary* dict, int entry,
167 : PropertyDetails value) {
168 : STATIC_ASSERT(Dictionary::kEntrySize == 3);
169 : dict->set(Dictionary::EntryToIndex(entry) + Dictionary::kEntryDetailsIndex,
170 : value.AsSmi());
171 44814 : }
172 :
173 : template <typename Dictionary>
174 : static bool IsDeleted(Dictionary* dict, int entry) {
175 : return false;
176 : }
177 :
178 : template <typename Dictionary>
179 : static inline void SetEntry(Dictionary* dict, int entry, Handle<Object> key,
180 : Handle<Object> value, PropertyDetails details);
181 : };
182 :
183 : class NameDictionaryShape : public BaseDictionaryShape<Handle<Name>> {
184 : public:
185 : static inline bool IsMatch(Handle<Name> key, Object* other);
186 : static inline uint32_t Hash(Handle<Name> key);
187 : static inline uint32_t HashForObject(Handle<Name> key, Object* object);
188 : static inline Handle<Object> AsHandle(Isolate* isolate, Handle<Name> key);
189 : static const int kPrefixSize = 2;
190 : static const int kEntrySize = 3;
191 : static const int kEntryValueIndex = 1;
192 : static const int kEntryDetailsIndex = 2;
193 : static const bool kIsEnumerable = true;
194 : };
195 :
196 : class NameDictionary
197 : : public NameDictionaryBase<NameDictionary, NameDictionaryShape> {
198 : typedef NameDictionaryBase<NameDictionary, NameDictionaryShape>
199 : DerivedDictionary;
200 :
201 : public:
202 : DECLARE_CAST(NameDictionary)
203 :
204 : static const int kEntryValueIndex = 1;
205 : static const int kEntryDetailsIndex = 2;
206 : static const int kInitialCapacity = 2;
207 : };
208 :
209 : class GlobalDictionaryShape : public NameDictionaryShape {
210 : public:
211 : static const int kEntrySize = 2; // Overrides NameDictionaryShape::kEntrySize
212 :
213 : template <typename Dictionary>
214 : static inline PropertyDetails DetailsAt(Dictionary* dict, int entry);
215 :
216 : template <typename Dictionary>
217 : static inline void DetailsAtPut(Dictionary* dict, int entry,
218 : PropertyDetails value);
219 :
220 : template <typename Dictionary>
221 : static bool IsDeleted(Dictionary* dict, int entry);
222 :
223 : template <typename Dictionary>
224 : static inline void SetEntry(Dictionary* dict, int entry, Handle<Object> key,
225 : Handle<Object> value, PropertyDetails details);
226 : };
227 :
228 : class GlobalDictionary
229 : : public NameDictionaryBase<GlobalDictionary, GlobalDictionaryShape> {
230 : public:
231 : DECLARE_CAST(GlobalDictionary)
232 :
233 : static const int kEntryValueIndex = 1;
234 : };
235 :
236 : class NumberDictionaryShape : public BaseDictionaryShape<uint32_t> {
237 : public:
238 : static inline bool IsMatch(uint32_t key, Object* other);
239 : static inline Handle<Object> AsHandle(Isolate* isolate, uint32_t key);
240 : static const bool kIsEnumerable = false;
241 : };
242 :
243 : class SeededNumberDictionaryShape : public NumberDictionaryShape {
244 : public:
245 : static const bool UsesSeed = true;
246 : static const int kPrefixSize = 2;
247 : static const int kEntrySize = 3;
248 :
249 : static inline uint32_t SeededHash(uint32_t key, uint32_t seed);
250 : static inline uint32_t SeededHashForObject(uint32_t key, uint32_t seed,
251 : Object* object);
252 : };
253 :
254 : class UnseededNumberDictionaryShape : public NumberDictionaryShape {
255 : public:
256 : static const int kPrefixSize = 0;
257 : static const int kEntrySize = 2;
258 :
259 : static inline uint32_t Hash(uint32_t key);
260 : static inline uint32_t HashForObject(uint32_t key, Object* object);
261 :
262 : template <typename Dictionary>
263 0 : static inline PropertyDetails DetailsAt(Dictionary* dict, int entry) {
264 0 : UNREACHABLE();
265 : return PropertyDetails::Empty();
266 : }
267 :
268 : template <typename Dictionary>
269 0 : static inline void DetailsAtPut(Dictionary* dict, int entry,
270 : PropertyDetails value) {
271 0 : UNREACHABLE();
272 : }
273 :
274 : static inline Map* GetMap(Isolate* isolate);
275 : };
276 :
277 : class SeededNumberDictionary
278 : : public Dictionary<SeededNumberDictionary, SeededNumberDictionaryShape,
279 : uint32_t> {
280 : public:
281 : DECLARE_CAST(SeededNumberDictionary)
282 :
283 : // Type specific at put (default NONE attributes is used when adding).
284 : MUST_USE_RESULT static Handle<SeededNumberDictionary> AtNumberPut(
285 : Handle<SeededNumberDictionary> dictionary, uint32_t key,
286 : Handle<Object> value, Handle<JSObject> dictionary_holder);
287 : MUST_USE_RESULT static Handle<SeededNumberDictionary> AddNumberEntry(
288 : Handle<SeededNumberDictionary> dictionary, uint32_t key,
289 : Handle<Object> value, PropertyDetails details,
290 : Handle<JSObject> dictionary_holder);
291 :
292 : // Set an existing entry or add a new one if needed.
293 : // Return the updated dictionary.
294 : MUST_USE_RESULT static Handle<SeededNumberDictionary> Set(
295 : Handle<SeededNumberDictionary> dictionary, uint32_t key,
296 : Handle<Object> value, PropertyDetails details,
297 : Handle<JSObject> dictionary_holder);
298 :
299 : void UpdateMaxNumberKey(uint32_t key, Handle<JSObject> dictionary_holder);
300 :
301 : // Returns true if the dictionary contains any elements that are non-writable,
302 : // non-configurable, non-enumerable, or have getters/setters.
303 : bool HasComplexElements();
304 :
305 : // Sorting support
306 : void CopyValuesTo(FixedArray* elements);
307 :
308 : // If slow elements are required we will never go back to fast-case
309 : // for the elements kept in this dictionary. We require slow
310 : // elements if an element has been added at an index larger than
311 : // kRequiresSlowElementsLimit or set_requires_slow_elements() has been called
312 : // when defining a getter or setter with a number key.
313 : inline bool requires_slow_elements();
314 : inline void set_requires_slow_elements();
315 :
316 : // Get the value of the max number key that has been added to this
317 : // dictionary. max_number_key can only be called if
318 : // requires_slow_elements returns false.
319 : inline uint32_t max_number_key();
320 :
321 : static const int kEntryValueIndex = 1;
322 : static const int kEntryDetailsIndex = 2;
323 :
324 : // Bit masks.
325 : static const int kRequiresSlowElementsMask = 1;
326 : static const int kRequiresSlowElementsTagSize = 1;
327 : static const uint32_t kRequiresSlowElementsLimit = (1 << 29) - 1;
328 : };
329 :
330 : class UnseededNumberDictionary
331 : : public Dictionary<UnseededNumberDictionary, UnseededNumberDictionaryShape,
332 : uint32_t> {
333 : public:
334 : DECLARE_CAST(UnseededNumberDictionary)
335 :
336 : // Type specific at put (default NONE attributes is used when adding).
337 : MUST_USE_RESULT static Handle<UnseededNumberDictionary> AtNumberPut(
338 : Handle<UnseededNumberDictionary> dictionary, uint32_t key,
339 : Handle<Object> value);
340 : MUST_USE_RESULT static Handle<UnseededNumberDictionary> AddNumberEntry(
341 : Handle<UnseededNumberDictionary> dictionary, uint32_t key,
342 : Handle<Object> value);
343 : static Handle<UnseededNumberDictionary> DeleteKey(
344 : Handle<UnseededNumberDictionary> dictionary, uint32_t key);
345 :
346 : // Set an existing entry or add a new one if needed.
347 : // Return the updated dictionary.
348 : MUST_USE_RESULT static Handle<UnseededNumberDictionary> Set(
349 : Handle<UnseededNumberDictionary> dictionary, uint32_t key,
350 : Handle<Object> value);
351 :
352 : static const int kEntryValueIndex = 1;
353 : static const int kEntryDetailsIndex = 2;
354 : };
355 :
356 : } // namespace internal
357 : } // namespace v8
358 :
359 : #include "src/objects/object-macros-undef.h"
360 :
361 : #endif // V8_OBJECTS_DICTIONARY_H_
|
