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_OBJECTS_KEYS_H_ 6 #define V8_OBJECTS_KEYS_H_ 7 8 #include "include/v8-object.h" 9 #include "src/objects/hash-table.h" 10 #include "src/objects/js-objects.h" 11 #include "src/objects/objects.h" 12 13 namespace v8 { 14 namespace internal { 15 16 class JSProxy; 17 class FastKeyAccumulator; 18 19 enum AddKeyConversion { DO_NOT_CONVERT, CONVERT_TO_ARRAY_INDEX }; 20 21 enum class GetKeysConversion { 22 kKeepNumbers = static_cast<int>(v8::KeyConversionMode::kKeepNumbers), 23 kConvertToString = static_cast<int>(v8::KeyConversionMode::kConvertToString), 24 kNoNumbers = static_cast<int>(v8::KeyConversionMode::kNoNumbers) 25 }; 26 27 enum class KeyCollectionMode { 28 kOwnOnly = static_cast<int>(v8::KeyCollectionMode::kOwnOnly), 29 kIncludePrototypes = 30 static_cast<int>(v8::KeyCollectionMode::kIncludePrototypes) 31 }; 32 33 // This is a helper class for JSReceiver::GetKeys which collects and sorts keys. 34 // GetKeys needs to sort keys per prototype level, first showing the integer 35 // indices from elements then the strings from the properties. However, this 36 // does not apply to proxies which are in full control of how the keys are 37 // sorted. 38 // 39 // For performance reasons the KeyAccumulator internally separates integer keys 40 // in |elements_| into sorted lists per prototype level. String keys are 41 // collected in |string_properties_|, a single OrderedHashSet (similar for 42 // Symbols in |symbol_properties_|. To separate the keys per level later when 43 // assembling the final list, |levelLengths_| keeps track of the number of 44 // String and Symbol keys per level. 45 // 46 // Only unique keys are kept by the KeyAccumulator, strings are stored in a 47 // HashSet for inexpensive lookups. Integer keys are kept in sorted lists which 48 // are more compact and allow for reasonably fast includes check. 49 class KeyAccumulator final { 50 public: KeyAccumulator(Isolate * isolate,KeyCollectionMode mode,PropertyFilter filter)51 KeyAccumulator(Isolate* isolate, KeyCollectionMode mode, 52 PropertyFilter filter) 53 : isolate_(isolate), mode_(mode), filter_(filter) {} 54 ~KeyAccumulator() = default; 55 KeyAccumulator(const KeyAccumulator&) = delete; 56 KeyAccumulator& operator=(const KeyAccumulator&) = delete; 57 58 static MaybeHandle<FixedArray> GetKeys( 59 Handle<JSReceiver> object, KeyCollectionMode mode, PropertyFilter filter, 60 GetKeysConversion keys_conversion = GetKeysConversion::kKeepNumbers, 61 bool is_for_in = false, bool skip_indices = false); 62 63 Handle<FixedArray> GetKeys( 64 GetKeysConversion convert = GetKeysConversion::kKeepNumbers); 65 Maybe<bool> CollectKeys(Handle<JSReceiver> receiver, 66 Handle<JSReceiver> object); 67 68 // Might return directly the object's enum_cache, copy the result before using 69 // as an elements backing store for a JSObject. 70 // Does not throw for uninitialized exports in module namespace objects, so 71 // this has to be checked separately. 72 static Handle<FixedArray> GetOwnEnumPropertyKeys(Isolate* isolate, 73 Handle<JSObject> object); 74 75 V8_WARN_UNUSED_RESULT ExceptionStatus 76 AddKey(Object key, AddKeyConversion convert = DO_NOT_CONVERT); 77 V8_WARN_UNUSED_RESULT ExceptionStatus 78 AddKey(Handle<Object> key, AddKeyConversion convert = DO_NOT_CONVERT); 79 80 // Jump to the next level, pushing the current |levelLength_| to 81 // |levelLengths_| and adding a new list to |elements_|. isolate()82 Isolate* isolate() { return isolate_; } 83 // Filter keys based on their property descriptors. filter()84 PropertyFilter filter() { return filter_; } 85 // The collection mode defines whether we collect the keys from the prototype 86 // chain or only look at the receiver. mode()87 KeyCollectionMode mode() { return mode_; } set_skip_indices(bool value)88 void set_skip_indices(bool value) { skip_indices_ = value; } 89 // Shadowing keys are used to filter keys. This happens when non-enumerable 90 // keys appear again on the prototype chain. 91 void AddShadowingKey(Object key, AllowGarbageCollection* allow_gc); 92 void AddShadowingKey(Handle<Object> key); 93 94 private: 95 enum IndexedOrNamed { kIndexed, kNamed }; 96 97 V8_WARN_UNUSED_RESULT ExceptionStatus 98 CollectPrivateNames(Handle<JSReceiver> receiver, Handle<JSObject> object); 99 Maybe<bool> CollectAccessCheckInterceptorKeys( 100 Handle<AccessCheckInfo> access_check_info, Handle<JSReceiver> receiver, 101 Handle<JSObject> object); 102 103 Maybe<bool> CollectInterceptorKeysInternal( 104 Handle<JSReceiver> receiver, Handle<JSObject> object, 105 Handle<InterceptorInfo> interceptor, IndexedOrNamed type); 106 Maybe<bool> CollectInterceptorKeys(Handle<JSReceiver> receiver, 107 Handle<JSObject> object, 108 IndexedOrNamed type); 109 110 Maybe<bool> CollectOwnElementIndices(Handle<JSReceiver> receiver, 111 Handle<JSObject> object); 112 Maybe<bool> CollectOwnPropertyNames(Handle<JSReceiver> receiver, 113 Handle<JSObject> object); 114 Maybe<bool> CollectOwnKeys(Handle<JSReceiver> receiver, 115 Handle<JSObject> object); 116 Maybe<bool> CollectOwnJSProxyKeys(Handle<JSReceiver> receiver, 117 Handle<JSProxy> proxy); 118 Maybe<bool> CollectOwnJSProxyTargetKeys(Handle<JSProxy> proxy, 119 Handle<JSReceiver> target); 120 121 V8_WARN_UNUSED_RESULT ExceptionStatus FilterForEnumerableProperties( 122 Handle<JSReceiver> receiver, Handle<JSObject> object, 123 Handle<InterceptorInfo> interceptor, Handle<JSObject> result, 124 IndexedOrNamed type); 125 126 Maybe<bool> AddKeysFromJSProxy(Handle<JSProxy> proxy, 127 Handle<FixedArray> keys); 128 V8_WARN_UNUSED_RESULT ExceptionStatus AddKeys(Handle<FixedArray> array, 129 AddKeyConversion convert); 130 V8_WARN_UNUSED_RESULT ExceptionStatus AddKeys(Handle<JSObject> array_like, 131 AddKeyConversion convert); 132 133 bool IsShadowed(Handle<Object> key); 134 bool HasShadowingKeys(); 135 Handle<OrderedHashSet> keys(); 136 137 // In case of for-in loops we have to treat JSProxy keys differently and 138 // deduplicate them. Additionally we convert JSProxy keys back to array 139 // indices. set_is_for_in(bool value)140 void set_is_for_in(bool value) { is_for_in_ = value; } set_first_prototype_map(Handle<Map> value)141 void set_first_prototype_map(Handle<Map> value) { 142 first_prototype_map_ = value; 143 } set_try_prototype_info_cache(bool value)144 void set_try_prototype_info_cache(bool value) { 145 try_prototype_info_cache_ = value; 146 } set_receiver(Handle<JSReceiver> object)147 void set_receiver(Handle<JSReceiver> object) { receiver_ = object; } 148 // The last_non_empty_prototype is used to limit the prototypes for which 149 // we have to keep track of non-enumerable keys that can shadow keys 150 // repeated on the prototype chain. set_last_non_empty_prototype(Handle<JSReceiver> object)151 void set_last_non_empty_prototype(Handle<JSReceiver> object) { 152 last_non_empty_prototype_ = object; 153 } set_may_have_elements(bool value)154 void set_may_have_elements(bool value) { may_have_elements_ = value; } 155 156 Isolate* isolate_; 157 Handle<OrderedHashSet> keys_; 158 Handle<Map> first_prototype_map_; 159 Handle<JSReceiver> receiver_; 160 Handle<JSReceiver> last_non_empty_prototype_; 161 Handle<ObjectHashSet> shadowing_keys_; 162 KeyCollectionMode mode_; 163 PropertyFilter filter_; 164 bool is_for_in_ = false; 165 bool skip_indices_ = false; 166 // For all the keys on the first receiver adding a shadowing key we can skip 167 // the shadow check. 168 bool skip_shadow_check_ = true; 169 bool may_have_elements_ = true; 170 bool try_prototype_info_cache_ = false; 171 172 friend FastKeyAccumulator; 173 }; 174 175 // The FastKeyAccumulator handles the cases where there are no elements on the 176 // prototype chain and forwords the complex/slow cases to the normal 177 // KeyAccumulator. This significantly speeds up the cases where the OWN_ONLY 178 // case where we do not have to walk the prototype chain. 179 class FastKeyAccumulator { 180 public: 181 FastKeyAccumulator(Isolate* isolate, Handle<JSReceiver> receiver, 182 KeyCollectionMode mode, PropertyFilter filter, 183 bool is_for_in = false, bool skip_indices = false) isolate_(isolate)184 : isolate_(isolate), 185 receiver_(receiver), 186 mode_(mode), 187 filter_(filter), 188 is_for_in_(is_for_in), 189 skip_indices_(skip_indices) { 190 Prepare(); 191 } 192 FastKeyAccumulator(const FastKeyAccumulator&) = delete; 193 FastKeyAccumulator& operator=(const FastKeyAccumulator&) = delete; 194 is_receiver_simple_enum()195 bool is_receiver_simple_enum() { return is_receiver_simple_enum_; } has_empty_prototype()196 bool has_empty_prototype() { return has_empty_prototype_; } may_have_elements()197 bool may_have_elements() { return may_have_elements_; } 198 199 MaybeHandle<FixedArray> GetKeys( 200 GetKeysConversion convert = GetKeysConversion::kKeepNumbers); 201 202 private: 203 void Prepare(); 204 MaybeHandle<FixedArray> GetKeysFast(GetKeysConversion convert); 205 MaybeHandle<FixedArray> GetKeysSlow(GetKeysConversion convert); 206 MaybeHandle<FixedArray> GetKeysWithPrototypeInfoCache( 207 GetKeysConversion convert); 208 209 MaybeHandle<FixedArray> GetOwnKeysWithUninitializedEnumCache(); 210 211 bool MayHaveElements(JSReceiver receiver); 212 bool TryPrototypeInfoCache(Handle<JSReceiver> receiver); 213 214 Isolate* isolate_; 215 Handle<JSReceiver> receiver_; 216 Handle<Map> first_prototype_map_; 217 Handle<JSReceiver> first_prototype_; 218 Handle<JSReceiver> last_non_empty_prototype_; 219 KeyCollectionMode mode_; 220 PropertyFilter filter_; 221 bool is_for_in_ = false; 222 bool skip_indices_ = false; 223 bool is_receiver_simple_enum_ = false; 224 bool has_empty_prototype_ = false; 225 bool may_have_elements_ = true; 226 bool has_prototype_info_cache_ = false; 227 bool try_prototype_info_cache_ = false; 228 bool only_own_has_simple_elements_ = false; 229 }; 230 231 } // namespace internal 232 } // namespace v8 233 234 #endif // V8_OBJECTS_KEYS_H_ 235