Line data Source code
1 : // Copyright 2012 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_KEYS_H_
6 : #define V8_KEYS_H_
7 :
8 : #include "src/isolate.h"
9 : #include "src/objects.h"
10 :
11 : namespace v8 {
12 : namespace internal {
13 :
14 : enum AddKeyConversion { DO_NOT_CONVERT, CONVERT_TO_ARRAY_INDEX };
15 :
16 : // This is a helper class for JSReceiver::GetKeys which collects and sorts keys.
17 : // GetKeys needs to sort keys per prototype level, first showing the integer
18 : // indices from elements then the strings from the properties. However, this
19 : // does not apply to proxies which are in full control of how the keys are
20 : // sorted.
21 : //
22 : // For performance reasons the KeyAccumulator internally separates integer keys
23 : // in |elements_| into sorted lists per prototype level. String keys are
24 : // collected in |string_properties_|, a single OrderedHashSet (similar for
25 : // Symbols in |symbol_properties_|. To separate the keys per level later when
26 : // assembling the final list, |levelLengths_| keeps track of the number of
27 : // String and Symbol keys per level.
28 : //
29 : // Only unique keys are kept by the KeyAccumulator, strings are stored in a
30 : // HashSet for inexpensive lookups. Integer keys are kept in sorted lists which
31 : // are more compact and allow for reasonably fast includes check.
32 : class KeyAccumulator final BASE_EMBEDDED {
33 : public:
34 3702 : KeyAccumulator(Isolate* isolate, KeyCollectionMode mode,
35 : PropertyFilter filter)
36 19316426 : : isolate_(isolate), mode_(mode), filter_(filter) {}
37 : ~KeyAccumulator();
38 :
39 : static MaybeHandle<FixedArray> GetKeys(
40 : Handle<JSReceiver> object, KeyCollectionMode mode, PropertyFilter filter,
41 : GetKeysConversion keys_conversion = GetKeysConversion::kKeepNumbers,
42 : bool is_for_in = false);
43 :
44 : Handle<FixedArray> GetKeys(
45 : GetKeysConversion convert = GetKeysConversion::kKeepNumbers);
46 : Maybe<bool> CollectKeys(Handle<JSReceiver> receiver,
47 : Handle<JSReceiver> object);
48 : Maybe<bool> CollectOwnElementIndices(Handle<JSReceiver> receiver,
49 : Handle<JSObject> object);
50 : Maybe<bool> CollectOwnPropertyNames(Handle<JSReceiver> receiver,
51 : Handle<JSObject> object);
52 : Maybe<bool> CollectAccessCheckInterceptorKeys(
53 : Handle<AccessCheckInfo> access_check_info, Handle<JSReceiver> receiver,
54 : Handle<JSObject> object);
55 :
56 : // Might return directly the object's enum_cache, copy the result before using
57 : // as an elements backing store for a JSObject.
58 : static Handle<FixedArray> GetOwnEnumPropertyKeys(Isolate* isolate,
59 : Handle<JSObject> object);
60 : void AddKey(Object* key, AddKeyConversion convert = DO_NOT_CONVERT);
61 : void AddKey(Handle<Object> key, AddKeyConversion convert = DO_NOT_CONVERT);
62 : void AddKeys(Handle<FixedArray> array, AddKeyConversion convert);
63 : void AddKeys(Handle<JSObject> array_like, AddKeyConversion convert);
64 :
65 : // Jump to the next level, pushing the current |levelLength_| to
66 : // |levelLengths_| and adding a new list to |elements_|.
67 : Isolate* isolate() { return isolate_; }
68 : // Filter keys based on their property descriptors.
69 : PropertyFilter filter() { return filter_; }
70 : // The collection mode defines whether we collect the keys from the prototype
71 : // chain or only look at the receiver.
72 : KeyCollectionMode mode() { return mode_; }
73 : // In case of for-in loops we have to treat JSProxy keys differently and
74 : // deduplicate them. Additionally we convert JSProxy keys back to array
75 : // indices.
76 628059 : void set_is_for_in(bool value) { is_for_in_ = value; }
77 9026129 : void set_skip_indices(bool value) { skip_indices_ = value; }
78 : // The last_non_empty_prototype is used to limit the prototypes for which
79 : // we have to keep track of non-enumerable keys that can shadow keys
80 : // repeated on the prototype chain.
81 : void set_last_non_empty_prototype(Handle<JSReceiver> object) {
82 628059 : last_non_empty_prototype_ = object;
83 : }
84 : // Shadowing keys are used to filter keys. This happens when non-enumerable
85 : // keys appear again on the prototype chain.
86 : void AddShadowingKey(Object* key);
87 : void AddShadowingKey(Handle<Object> key);
88 :
89 : private:
90 : Maybe<bool> CollectOwnKeys(Handle<JSReceiver> receiver,
91 : Handle<JSObject> object);
92 : Maybe<bool> CollectOwnJSProxyKeys(Handle<JSReceiver> receiver,
93 : Handle<JSProxy> proxy);
94 : Maybe<bool> CollectOwnJSProxyTargetKeys(Handle<JSProxy> proxy,
95 : Handle<JSReceiver> target);
96 : Maybe<bool> AddKeysFromJSProxy(Handle<JSProxy> proxy,
97 : Handle<FixedArray> keys);
98 : bool IsShadowed(Handle<Object> key);
99 : bool HasShadowingKeys();
100 : Handle<OrderedHashSet> keys() { return Handle<OrderedHashSet>::cast(keys_); }
101 :
102 : Isolate* isolate_;
103 : // keys_ is either an Handle<OrderedHashSet> or in the case of own JSProxy
104 : // keys a Handle<FixedArray>. The OrderedHashSet is in-place converted to the
105 : // result list, a FixedArray containing all collected keys.
106 : Handle<FixedArray> keys_;
107 : Handle<JSReceiver> last_non_empty_prototype_;
108 : Handle<ObjectHashSet> shadowing_keys_;
109 : KeyCollectionMode mode_;
110 : PropertyFilter filter_;
111 : bool is_for_in_ = false;
112 : bool skip_indices_ = false;
113 : // For all the keys on the first receiver adding a shadowing key we can skip
114 : // the shadow check.
115 : bool skip_shadow_check_ = true;
116 :
117 : DISALLOW_COPY_AND_ASSIGN(KeyAccumulator);
118 : };
119 :
120 : // The FastKeyAccumulator handles the cases where there are no elements on the
121 : // prototype chain and forwords the complex/slow cases to the normal
122 : // KeyAccumulator. This significantly speeds up the cases where the OWN_ONLY
123 : // case where we do not have to walk the prototype chain.
124 : class FastKeyAccumulator {
125 : public:
126 : FastKeyAccumulator(Isolate* isolate, Handle<JSReceiver> receiver,
127 : KeyCollectionMode mode, PropertyFilter filter)
128 4299764 : : isolate_(isolate), receiver_(receiver), mode_(mode), filter_(filter) {
129 2149882 : Prepare();
130 : }
131 :
132 : bool is_receiver_simple_enum() { return is_receiver_simple_enum_; }
133 : bool has_empty_prototype() { return has_empty_prototype_; }
134 2149882 : void set_is_for_in(bool value) { is_for_in_ = value; }
135 :
136 : MaybeHandle<FixedArray> GetKeys(
137 : GetKeysConversion convert = GetKeysConversion::kKeepNumbers);
138 :
139 : private:
140 : void Prepare();
141 : MaybeHandle<FixedArray> GetKeysFast(GetKeysConversion convert);
142 : MaybeHandle<FixedArray> GetKeysSlow(GetKeysConversion convert);
143 :
144 : MaybeHandle<FixedArray> GetOwnKeysWithUninitializedEnumCache();
145 :
146 : Isolate* isolate_;
147 : Handle<JSReceiver> receiver_;
148 : Handle<JSReceiver> last_non_empty_prototype_;
149 : KeyCollectionMode mode_;
150 : PropertyFilter filter_;
151 : bool is_for_in_ = false;
152 : bool is_receiver_simple_enum_ = false;
153 : bool has_empty_prototype_ = false;
154 :
155 : DISALLOW_COPY_AND_ASSIGN(FastKeyAccumulator);
156 : };
157 :
158 : } // namespace internal
159 : } // namespace v8
160 :
161 : #endif // V8_KEYS_H_
|