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