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