1// Copyright 2013 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#include "src/keys.h"
6
7#include "src/api-arguments-inl.h"
8#include "src/elements-inl.h"
9#include "src/field-index-inl.h"
10#include "src/handles-inl.h"
11#include "src/heap/factory.h"
12#include "src/identity-map.h"
13#include "src/isolate-inl.h"
14#include "src/objects-inl.h"
15#include "src/objects/api-callbacks.h"
16#include "src/objects/hash-table-inl.h"
17#include "src/objects/module-inl.h"
18#include "src/objects/ordered-hash-table-inl.h"
19#include "src/property-descriptor.h"
20#include "src/prototype.h"
21
22namespace v8 {
23namespace internal {
24
25namespace {
26
27static bool ContainsOnlyValidKeys(Handle<FixedArray> array) {
28 int len = array->length();
29 for (int i = 0; i < len; i++) {
30 Object e = array->get(i);
31 if (!(e->IsName() || e->IsNumber())) return false;
32 }
33 return true;
34}
35
36} // namespace
37
38// static
39MaybeHandle<FixedArray> KeyAccumulator::GetKeys(
40 Handle<JSReceiver> object, KeyCollectionMode mode, PropertyFilter filter,
41 GetKeysConversion keys_conversion, bool is_for_in, bool skip_indices) {
42 Isolate* isolate = object->GetIsolate();
43 FastKeyAccumulator accumulator(isolate, object, mode, filter, is_for_in,
44 skip_indices);
45 return accumulator.GetKeys(keys_conversion);
46}
47
48Handle<FixedArray> KeyAccumulator::GetKeys(GetKeysConversion convert) {
49 if (keys_.is_null()) {
50 return isolate_->factory()->empty_fixed_array();
51 }
52 if (mode_ == KeyCollectionMode::kOwnOnly &&
53 keys_->map() == ReadOnlyRoots(isolate_).fixed_array_map()) {
54 return Handle<FixedArray>::cast(keys_);
55 }
56 USE(ContainsOnlyValidKeys);
57 Handle<FixedArray> result =
58 OrderedHashSet::ConvertToKeysArray(isolate(), keys(), convert);
59 DCHECK(ContainsOnlyValidKeys(result));
60 return result;
61}
62
63Handle<OrderedHashSet> KeyAccumulator::keys() {
64 return Handle<OrderedHashSet>::cast(keys_);
65}
66
67void KeyAccumulator::AddKey(Object key, AddKeyConversion convert) {
68 AddKey(handle(key, isolate_), convert);
69}
70
71void KeyAccumulator::AddKey(Handle<Object> key, AddKeyConversion convert) {
72 if (filter_ == PRIVATE_NAMES_ONLY) {
73 if (!key->IsSymbol()) return;
74 if (!Symbol::cast(*key)->is_private_name()) return;
75 } else if (key->IsSymbol()) {
76 if (filter_ & SKIP_SYMBOLS) return;
77
78 if (Symbol::cast(*key)->is_private()) return;
79 } else if (filter_ & SKIP_STRINGS) {
80 return;
81 }
82
83 if (IsShadowed(key)) return;
84 if (keys_.is_null()) {
85 keys_ = OrderedHashSet::Allocate(isolate_, 16);
86 }
87 uint32_t index;
88 if (convert == CONVERT_TO_ARRAY_INDEX && key->IsString() &&
89 Handle<String>::cast(key)->AsArrayIndex(&index)) {
90 key = isolate_->factory()->NewNumberFromUint(index);
91 }
92 Handle<OrderedHashSet> new_set = OrderedHashSet::Add(isolate(), keys(), key);
93 if (*new_set != *keys_) {
94 // The keys_ Set is converted directly to a FixedArray in GetKeys which can
95 // be left-trimmer. Hence the previous Set should not keep a pointer to the
96 // new one.
97 keys_->set(OrderedHashSet::NextTableIndex(), Smi::kZero);
98 keys_ = new_set;
99 }
100}
101
102void KeyAccumulator::AddKeys(Handle<FixedArray> array,
103 AddKeyConversion convert) {
104 int add_length = array->length();
105 for (int i = 0; i < add_length; i++) {
106 Handle<Object> current(array->get(i), isolate_);
107 AddKey(current, convert);
108 }
109}
110
111void KeyAccumulator::AddKeys(Handle<JSObject> array_like,
112 AddKeyConversion convert) {
113 DCHECK(array_like->IsJSArray() || array_like->HasSloppyArgumentsElements());
114 ElementsAccessor* accessor = array_like->GetElementsAccessor();
115 accessor->AddElementsToKeyAccumulator(array_like, this, convert);
116}
117
118MaybeHandle<FixedArray> FilterProxyKeys(KeyAccumulator* accumulator,
119 Handle<JSProxy> owner,
120 Handle<FixedArray> keys,
121 PropertyFilter filter) {
122 if (filter == ALL_PROPERTIES) {
123 // Nothing to do.
124 return keys;
125 }
126 Isolate* isolate = accumulator->isolate();
127 int store_position = 0;
128 for (int i = 0; i < keys->length(); ++i) {
129 Handle<Name> key(Name::cast(keys->get(i)), isolate);
130 if (key->FilterKey(filter)) continue; // Skip this key.
131 if (filter & ONLY_ENUMERABLE) {
132 PropertyDescriptor desc;
133 Maybe<bool> found =
134 JSProxy::GetOwnPropertyDescriptor(isolate, owner, key, &desc);
135 MAYBE_RETURN(found, MaybeHandle<FixedArray>());
136 if (!found.FromJust()) continue;
137 if (!desc.enumerable()) {
138 accumulator->AddShadowingKey(key);
139 continue;
140 }
141 }
142 // Keep this key.
143 if (store_position != i) {
144 keys->set(store_position, *key);
145 }
146 store_position++;
147 }
148 return FixedArray::ShrinkOrEmpty(isolate, keys, store_position);
149}
150
151// Returns "nothing" in case of exception, "true" on success.
152Maybe<bool> KeyAccumulator::AddKeysFromJSProxy(Handle<JSProxy> proxy,
153 Handle<FixedArray> keys) {
154 // Postpone the enumerable check for for-in to the ForInFilter step.
155 if (!is_for_in_) {
156 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
157 isolate_, keys, FilterProxyKeys(this, proxy, keys, filter_),
158 Nothing<bool>());
159 if (mode_ == KeyCollectionMode::kOwnOnly) {
160 // If we collect only the keys from a JSProxy do not sort or deduplicate.
161 keys_ = keys;
162 return Just(true);
163 }
164 }
165 AddKeys(keys, is_for_in_ ? CONVERT_TO_ARRAY_INDEX : DO_NOT_CONVERT);
166 return Just(true);
167}
168
169Maybe<bool> KeyAccumulator::CollectKeys(Handle<JSReceiver> receiver,
170 Handle<JSReceiver> object) {
171 // Proxies have no hidden prototype and we should not trigger the
172 // [[GetPrototypeOf]] trap on the last iteration when using
173 // AdvanceFollowingProxies.
174 if (mode_ == KeyCollectionMode::kOwnOnly && object->IsJSProxy()) {
175 MAYBE_RETURN(CollectOwnJSProxyKeys(receiver, Handle<JSProxy>::cast(object)),
176 Nothing<bool>());
177 return Just(true);
178 }
179
180 PrototypeIterator::WhereToEnd end = mode_ == KeyCollectionMode::kOwnOnly
181 ? PrototypeIterator::END_AT_NON_HIDDEN
182 : PrototypeIterator::END_AT_NULL;
183 for (PrototypeIterator iter(isolate_, object, kStartAtReceiver, end);
184 !iter.IsAtEnd();) {
185 // Start the shadow checks only after the first prototype has added
186 // shadowing keys.
187 if (HasShadowingKeys()) skip_shadow_check_ = false;
188 Handle<JSReceiver> current =
189 PrototypeIterator::GetCurrent<JSReceiver>(iter);
190 Maybe<bool> result = Just(false); // Dummy initialization.
191 if (current->IsJSProxy()) {
192 result = CollectOwnJSProxyKeys(receiver, Handle<JSProxy>::cast(current));
193 } else {
194 DCHECK(current->IsJSObject());
195 result = CollectOwnKeys(receiver, Handle<JSObject>::cast(current));
196 }
197 MAYBE_RETURN(result, Nothing<bool>());
198 if (!result.FromJust()) break; // |false| means "stop iterating".
199 // Iterate through proxies but ignore access checks for the ALL_CAN_READ
200 // case on API objects for OWN_ONLY keys handled in CollectOwnKeys.
201 if (!iter.AdvanceFollowingProxiesIgnoringAccessChecks()) {
202 return Nothing<bool>();
203 }
204 if (!last_non_empty_prototype_.is_null() &&
205 *last_non_empty_prototype_ == *current) {
206 break;
207 }
208 }
209 return Just(true);
210}
211
212bool KeyAccumulator::HasShadowingKeys() { return !shadowing_keys_.is_null(); }
213
214bool KeyAccumulator::IsShadowed(Handle<Object> key) {
215 if (!HasShadowingKeys() || skip_shadow_check_) return false;
216 return shadowing_keys_->Has(isolate_, key);
217}
218
219void KeyAccumulator::AddShadowingKey(Object key) {
220 if (mode_ == KeyCollectionMode::kOwnOnly) return;
221 AddShadowingKey(handle(key, isolate_));
222}
223void KeyAccumulator::AddShadowingKey(Handle<Object> key) {
224 if (mode_ == KeyCollectionMode::kOwnOnly) return;
225 if (shadowing_keys_.is_null()) {
226 shadowing_keys_ = ObjectHashSet::New(isolate_, 16);
227 }
228 shadowing_keys_ = ObjectHashSet::Add(isolate(), shadowing_keys_, key);
229}
230
231namespace {
232
233void TrySettingEmptyEnumCache(JSReceiver object) {
234 Map map = object->map();
235 DCHECK_EQ(kInvalidEnumCacheSentinel, map->EnumLength());
236 if (!map->OnlyHasSimpleProperties()) return;
237 if (map->IsJSProxyMap()) return;
238 if (map->NumberOfEnumerableProperties() > 0) return;
239 DCHECK(object->IsJSObject());
240 map->SetEnumLength(0);
241}
242
243bool CheckAndInitalizeEmptyEnumCache(JSReceiver object) {
244 if (object->map()->EnumLength() == kInvalidEnumCacheSentinel) {
245 TrySettingEmptyEnumCache(object);
246 }
247 if (object->map()->EnumLength() != 0) return false;
248 DCHECK(object->IsJSObject());
249 return !JSObject::cast(object)->HasEnumerableElements();
250}
251} // namespace
252
253void FastKeyAccumulator::Prepare() {
254 DisallowHeapAllocation no_gc;
255 // Directly go for the fast path for OWN_ONLY keys.
256 if (mode_ == KeyCollectionMode::kOwnOnly) return;
257 // Fully walk the prototype chain and find the last prototype with keys.
258 is_receiver_simple_enum_ = false;
259 has_empty_prototype_ = true;
260 JSReceiver last_prototype;
261 for (PrototypeIterator iter(isolate_, *receiver_); !iter.IsAtEnd();
262 iter.Advance()) {
263 JSReceiver current = iter.GetCurrent<JSReceiver>();
264 bool has_no_properties = CheckAndInitalizeEmptyEnumCache(current);
265 if (has_no_properties) continue;
266 last_prototype = current;
267 has_empty_prototype_ = false;
268 }
269 if (has_empty_prototype_) {
270 is_receiver_simple_enum_ =
271 receiver_->map()->EnumLength() != kInvalidEnumCacheSentinel &&
272 !JSObject::cast(*receiver_)->HasEnumerableElements();
273 } else if (!last_prototype.is_null()) {
274 last_non_empty_prototype_ = handle(last_prototype, isolate_);
275 }
276}
277
278namespace {
279
280Handle<FixedArray> ReduceFixedArrayTo(Isolate* isolate,
281 Handle<FixedArray> array, int length) {
282 DCHECK_LE(length, array->length());
283 if (array->length() == length) return array;
284 return isolate->factory()->CopyFixedArrayUpTo(array, length);
285}
286
287// Initializes and directly returns the enume cache. Users of this function
288// have to make sure to never directly leak the enum cache.
289Handle<FixedArray> GetFastEnumPropertyKeys(Isolate* isolate,
290 Handle<JSObject> object) {
291 Handle<Map> map(object->map(), isolate);
292 Handle<FixedArray> keys(map->instance_descriptors()->enum_cache()->keys(),
293 isolate);
294
295 // Check if the {map} has a valid enum length, which implies that it
296 // must have a valid enum cache as well.
297 int enum_length = map->EnumLength();
298 if (enum_length != kInvalidEnumCacheSentinel) {
299 DCHECK(map->OnlyHasSimpleProperties());
300 DCHECK_LE(enum_length, keys->length());
301 DCHECK_EQ(enum_length, map->NumberOfEnumerableProperties());
302 isolate->counters()->enum_cache_hits()->Increment();
303 return ReduceFixedArrayTo(isolate, keys, enum_length);
304 }
305
306 // Determine the actual number of enumerable properties of the {map}.
307 enum_length = map->NumberOfEnumerableProperties();
308
309 // Check if there's already a shared enum cache on the {map}s
310 // DescriptorArray with sufficient number of entries.
311 if (enum_length <= keys->length()) {
312 if (map->OnlyHasSimpleProperties()) map->SetEnumLength(enum_length);
313 isolate->counters()->enum_cache_hits()->Increment();
314 return ReduceFixedArrayTo(isolate, keys, enum_length);
315 }
316
317 Handle<DescriptorArray> descriptors =
318 Handle<DescriptorArray>(map->instance_descriptors(), isolate);
319 isolate->counters()->enum_cache_misses()->Increment();
320 int nod = map->NumberOfOwnDescriptors();
321
322 // Create the keys array.
323 int index = 0;
324 bool fields_only = true;
325 keys = isolate->factory()->NewFixedArray(enum_length);
326 for (int i = 0; i < nod; i++) {
327 DisallowHeapAllocation no_gc;
328 PropertyDetails details = descriptors->GetDetails(i);
329 if (details.IsDontEnum()) continue;
330 Object key = descriptors->GetKey(i);
331 if (key->IsSymbol()) continue;
332 keys->set(index, key);
333 if (details.location() != kField) fields_only = false;
334 index++;
335 }
336 DCHECK_EQ(index, keys->length());
337
338 // Optionally also create the indices array.
339 Handle<FixedArray> indices = isolate->factory()->empty_fixed_array();
340 if (fields_only) {
341 indices = isolate->factory()->NewFixedArray(enum_length);
342 index = 0;
343 for (int i = 0; i < nod; i++) {
344 DisallowHeapAllocation no_gc;
345 PropertyDetails details = descriptors->GetDetails(i);
346 if (details.IsDontEnum()) continue;
347 Object key = descriptors->GetKey(i);
348 if (key->IsSymbol()) continue;
349 DCHECK_EQ(kData, details.kind());
350 DCHECK_EQ(kField, details.location());
351 FieldIndex field_index = FieldIndex::ForDescriptor(*map, i);
352 indices->set(index, Smi::FromInt(field_index.GetLoadByFieldIndex()));
353 index++;
354 }
355 DCHECK_EQ(index, indices->length());
356 }
357
358 DescriptorArray::InitializeOrChangeEnumCache(descriptors, isolate, keys,
359 indices);
360 if (map->OnlyHasSimpleProperties()) map->SetEnumLength(enum_length);
361
362 return keys;
363}
364
365template <bool fast_properties>
366MaybeHandle<FixedArray> GetOwnKeysWithElements(Isolate* isolate,
367 Handle<JSObject> object,
368 GetKeysConversion convert,
369 bool skip_indices) {
370 Handle<FixedArray> keys;
371 ElementsAccessor* accessor = object->GetElementsAccessor();
372 if (fast_properties) {
373 keys = GetFastEnumPropertyKeys(isolate, object);
374 } else {
375 // TODO(cbruni): preallocate big enough array to also hold elements.
376 keys = KeyAccumulator::GetOwnEnumPropertyKeys(isolate, object);
377 }
378
379 MaybeHandle<FixedArray> result;
380 if (skip_indices) {
381 result = keys;
382 } else {
383 result =
384 accessor->PrependElementIndices(object, keys, convert, ONLY_ENUMERABLE);
385 }
386
387 if (FLAG_trace_for_in_enumerate) {
388 PrintF("| strings=%d symbols=0 elements=%u || prototypes>=1 ||\n",
389 keys->length(), result.ToHandleChecked()->length() - keys->length());
390 }
391 return result;
392}
393
394} // namespace
395
396MaybeHandle<FixedArray> FastKeyAccumulator::GetKeys(
397 GetKeysConversion keys_conversion) {
398 if (filter_ == ENUMERABLE_STRINGS) {
399 Handle<FixedArray> keys;
400 if (GetKeysFast(keys_conversion).ToHandle(&keys)) {
401 return keys;
402 }
403 if (isolate_->has_pending_exception()) return MaybeHandle<FixedArray>();
404 }
405
406 return GetKeysSlow(keys_conversion);
407}
408
409MaybeHandle<FixedArray> FastKeyAccumulator::GetKeysFast(
410 GetKeysConversion keys_conversion) {
411 bool own_only = has_empty_prototype_ || mode_ == KeyCollectionMode::kOwnOnly;
412 Map map = receiver_->map();
413 if (!own_only || map->IsCustomElementsReceiverMap()) {
414 return MaybeHandle<FixedArray>();
415 }
416
417 // From this point on we are certain to only collect own keys.
418 DCHECK(receiver_->IsJSObject());
419 Handle<JSObject> object = Handle<JSObject>::cast(receiver_);
420
421 // Do not try to use the enum-cache for dict-mode objects.
422 if (map->is_dictionary_map()) {
423 return GetOwnKeysWithElements<false>(isolate_, object, keys_conversion,
424 skip_indices_);
425 }
426 int enum_length = receiver_->map()->EnumLength();
427 if (enum_length == kInvalidEnumCacheSentinel) {
428 Handle<FixedArray> keys;
429 // Try initializing the enum cache and return own properties.
430 if (GetOwnKeysWithUninitializedEnumCache().ToHandle(&keys)) {
431 if (FLAG_trace_for_in_enumerate) {
432 PrintF("| strings=%d symbols=0 elements=0 || prototypes>=1 ||\n",
433 keys->length());
434 }
435 is_receiver_simple_enum_ =
436 object->map()->EnumLength() != kInvalidEnumCacheSentinel;
437 return keys;
438 }
439 }
440 // The properties-only case failed because there were probably elements on the
441 // receiver.
442 return GetOwnKeysWithElements<true>(isolate_, object, keys_conversion,
443 skip_indices_);
444}
445
446MaybeHandle<FixedArray>
447FastKeyAccumulator::GetOwnKeysWithUninitializedEnumCache() {
448 Handle<JSObject> object = Handle<JSObject>::cast(receiver_);
449 // Uninitalized enum cache
450 Map map = object->map();
451 if (object->elements() != ReadOnlyRoots(isolate_).empty_fixed_array() &&
452 object->elements() !=
453 ReadOnlyRoots(isolate_).empty_slow_element_dictionary()) {
454 // Assume that there are elements.
455 return MaybeHandle<FixedArray>();
456 }
457 int number_of_own_descriptors = map->NumberOfOwnDescriptors();
458 if (number_of_own_descriptors == 0) {
459 map->SetEnumLength(0);
460 return isolate_->factory()->empty_fixed_array();
461 }
462 // We have no elements but possibly enumerable property keys, hence we can
463 // directly initialize the enum cache.
464 Handle<FixedArray> keys = GetFastEnumPropertyKeys(isolate_, object);
465 if (is_for_in_) return keys;
466 // Do not leak the enum cache as it might end up as an elements backing store.
467 return isolate_->factory()->CopyFixedArray(keys);
468}
469
470MaybeHandle<FixedArray> FastKeyAccumulator::GetKeysSlow(
471 GetKeysConversion keys_conversion) {
472 KeyAccumulator accumulator(isolate_, mode_, filter_);
473 accumulator.set_is_for_in(is_for_in_);
474 accumulator.set_skip_indices(skip_indices_);
475 accumulator.set_last_non_empty_prototype(last_non_empty_prototype_);
476
477 MAYBE_RETURN(accumulator.CollectKeys(receiver_, receiver_),
478 MaybeHandle<FixedArray>());
479 return accumulator.GetKeys(keys_conversion);
480}
481
482namespace {
483
484enum IndexedOrNamed { kIndexed, kNamed };
485
486void FilterForEnumerableProperties(Handle<JSReceiver> receiver,
487 Handle<JSObject> object,
488 Handle<InterceptorInfo> interceptor,
489 KeyAccumulator* accumulator,
490 Handle<JSObject> result,
491 IndexedOrNamed type) {
492 DCHECK(result->IsJSArray() || result->HasSloppyArgumentsElements());
493 ElementsAccessor* accessor = result->GetElementsAccessor();
494
495 uint32_t length = accessor->GetCapacity(*result, result->elements());
496 for (uint32_t i = 0; i < length; i++) {
497 if (!accessor->HasEntry(*result, i)) continue;
498
499 // args are invalid after args.Call(), create a new one in every iteration.
500 PropertyCallbackArguments args(accumulator->isolate(), interceptor->data(),
501 *receiver, *object, Just(kDontThrow));
502
503 Handle<Object> element = accessor->Get(result, i);
504 Handle<Object> attributes;
505 if (type == kIndexed) {
506 uint32_t number;
507 CHECK(element->ToUint32(&number));
508 attributes = args.CallIndexedQuery(interceptor, number);
509 } else {
510 CHECK(element->IsName());
511 attributes =
512 args.CallNamedQuery(interceptor, Handle<Name>::cast(element));
513 }
514
515 if (!attributes.is_null()) {
516 int32_t value;
517 CHECK(attributes->ToInt32(&value));
518 if ((value & DONT_ENUM) == 0) {
519 accumulator->AddKey(element, DO_NOT_CONVERT);
520 }
521 }
522 }
523}
524
525// Returns |true| on success, |nothing| on exception.
526Maybe<bool> CollectInterceptorKeysInternal(Handle<JSReceiver> receiver,
527 Handle<JSObject> object,
528 Handle<InterceptorInfo> interceptor,
529 KeyAccumulator* accumulator,
530 IndexedOrNamed type) {
531 Isolate* isolate = accumulator->isolate();
532 PropertyCallbackArguments enum_args(isolate, interceptor->data(), *receiver,
533 *object, Just(kDontThrow));
534
535 Handle<JSObject> result;
536 if (!interceptor->enumerator()->IsUndefined(isolate)) {
537 if (type == kIndexed) {
538 result = enum_args.CallIndexedEnumerator(interceptor);
539 } else {
540 DCHECK_EQ(type, kNamed);
541 result = enum_args.CallNamedEnumerator(interceptor);
542 }
543 }
544 RETURN_VALUE_IF_SCHEDULED_EXCEPTION(isolate, Nothing<bool>());
545 if (result.is_null()) return Just(true);
546
547 if ((accumulator->filter() & ONLY_ENUMERABLE) &&
548 !interceptor->query()->IsUndefined(isolate)) {
549 FilterForEnumerableProperties(receiver, object, interceptor, accumulator,
550 result, type);
551 } else {
552 accumulator->AddKeys(
553 result, type == kIndexed ? CONVERT_TO_ARRAY_INDEX : DO_NOT_CONVERT);
554 }
555 return Just(true);
556}
557
558Maybe<bool> CollectInterceptorKeys(Handle<JSReceiver> receiver,
559 Handle<JSObject> object,
560 KeyAccumulator* accumulator,
561 IndexedOrNamed type) {
562 Isolate* isolate = accumulator->isolate();
563 if (type == kIndexed) {
564 if (!object->HasIndexedInterceptor()) return Just(true);
565 } else {
566 if (!object->HasNamedInterceptor()) return Just(true);
567 }
568 Handle<InterceptorInfo> interceptor(type == kIndexed
569 ? object->GetIndexedInterceptor()
570 : object->GetNamedInterceptor(),
571 isolate);
572 if ((accumulator->filter() & ONLY_ALL_CAN_READ) &&
573 !interceptor->all_can_read()) {
574 return Just(true);
575 }
576 return CollectInterceptorKeysInternal(receiver, object, interceptor,
577 accumulator, type);
578}
579
580} // namespace
581
582Maybe<bool> KeyAccumulator::CollectOwnElementIndices(
583 Handle<JSReceiver> receiver, Handle<JSObject> object) {
584 if (filter_ & SKIP_STRINGS || skip_indices_) return Just(true);
585
586 ElementsAccessor* accessor = object->GetElementsAccessor();
587 accessor->CollectElementIndices(object, this);
588
589 return CollectInterceptorKeys(receiver, object, this, kIndexed);
590}
591
592namespace {
593
594template <bool skip_symbols>
595int CollectOwnPropertyNamesInternal(Handle<JSObject> object,
596 KeyAccumulator* keys,
597 Handle<DescriptorArray> descs,
598 int start_index, int limit) {
599 int first_skipped = -1;
600 PropertyFilter filter = keys->filter();
601 KeyCollectionMode mode = keys->mode();
602 for (int i = start_index; i < limit; i++) {
603 bool is_shadowing_key = false;
604 PropertyDetails details = descs->GetDetails(i);
605
606 if ((details.attributes() & filter) != 0) {
607 if (mode == KeyCollectionMode::kIncludePrototypes) {
608 is_shadowing_key = true;
609 } else {
610 continue;
611 }
612 }
613
614 if (filter & ONLY_ALL_CAN_READ) {
615 if (details.kind() != kAccessor) continue;
616 Object accessors = descs->GetStrongValue(i);
617 if (!accessors->IsAccessorInfo()) continue;
618 if (!AccessorInfo::cast(accessors)->all_can_read()) continue;
619 }
620
621 Name key = descs->GetKey(i);
622 if (skip_symbols == key->IsSymbol()) {
623 if (first_skipped == -1) first_skipped = i;
624 continue;
625 }
626 if (key->FilterKey(keys->filter())) continue;
627
628 if (is_shadowing_key) {
629 keys->AddShadowingKey(key);
630 } else {
631 keys->AddKey(key, DO_NOT_CONVERT);
632 }
633 }
634 return first_skipped;
635}
636
637template <class T>
638Handle<FixedArray> GetOwnEnumPropertyDictionaryKeys(Isolate* isolate,
639 KeyCollectionMode mode,
640 KeyAccumulator* accumulator,
641 Handle<JSObject> object,
642 T raw_dictionary) {
643 Handle<T> dictionary(raw_dictionary, isolate);
644 if (dictionary->NumberOfElements() == 0) {
645 return isolate->factory()->empty_fixed_array();
646 }
647 int length = dictionary->NumberOfEnumerableProperties();
648 Handle<FixedArray> storage = isolate->factory()->NewFixedArray(length);
649 T::CopyEnumKeysTo(isolate, dictionary, storage, mode, accumulator);
650 return storage;
651}
652} // namespace
653
654Maybe<bool> KeyAccumulator::CollectOwnPropertyNames(Handle<JSReceiver> receiver,
655 Handle<JSObject> object) {
656 if (filter_ == ENUMERABLE_STRINGS) {
657 Handle<FixedArray> enum_keys;
658 if (object->HasFastProperties()) {
659 enum_keys = KeyAccumulator::GetOwnEnumPropertyKeys(isolate_, object);
660 // If the number of properties equals the length of enumerable properties
661 // we do not have to filter out non-enumerable ones
662 Map map = object->map();
663 int nof_descriptors = map->NumberOfOwnDescriptors();
664 if (enum_keys->length() != nof_descriptors) {
665 Handle<DescriptorArray> descs =
666 Handle<DescriptorArray>(map->instance_descriptors(), isolate_);
667 for (int i = 0; i < nof_descriptors; i++) {
668 PropertyDetails details = descs->GetDetails(i);
669 if (!details.IsDontEnum()) continue;
670 Object key = descs->GetKey(i);
671 this->AddShadowingKey(key);
672 }
673 }
674 } else if (object->IsJSGlobalObject()) {
675 enum_keys = GetOwnEnumPropertyDictionaryKeys(
676 isolate_, mode_, this, object,
677 JSGlobalObject::cast(*object)->global_dictionary());
678 } else {
679 enum_keys = GetOwnEnumPropertyDictionaryKeys(
680 isolate_, mode_, this, object, object->property_dictionary());
681 }
682 if (object->IsJSModuleNamespace()) {
683 // Simulate [[GetOwnProperty]] for establishing enumerability, which
684 // throws for uninitialized exports.
685 for (int i = 0, n = enum_keys->length(); i < n; ++i) {
686 Handle<String> key(String::cast(enum_keys->get(i)), isolate_);
687 if (Handle<JSModuleNamespace>::cast(object)
688 ->GetExport(isolate(), key)
689 .is_null()) {
690 return Nothing<bool>();
691 }
692 }
693 }
694 AddKeys(enum_keys, DO_NOT_CONVERT);
695 } else {
696 if (object->HasFastProperties()) {
697 int limit = object->map()->NumberOfOwnDescriptors();
698 Handle<DescriptorArray> descs(object->map()->instance_descriptors(),
699 isolate_);
700 // First collect the strings,
701 int first_symbol =
702 CollectOwnPropertyNamesInternal<true>(object, this, descs, 0, limit);
703 // then the symbols.
704 if (first_symbol != -1) {
705 CollectOwnPropertyNamesInternal<false>(object, this, descs,
706 first_symbol, limit);
707 }
708 } else if (object->IsJSGlobalObject()) {
709 GlobalDictionary::CollectKeysTo(
710 handle(JSGlobalObject::cast(*object)->global_dictionary(), isolate_),
711 this);
712 } else {
713 NameDictionary::CollectKeysTo(
714 handle(object->property_dictionary(), isolate_), this);
715 }
716 }
717 // Add the property keys from the interceptor.
718 return CollectInterceptorKeys(receiver, object, this, kNamed);
719}
720
721void KeyAccumulator::CollectPrivateNames(Handle<JSReceiver> receiver,
722 Handle<JSObject> object) {
723 if (object->HasFastProperties()) {
724 int limit = object->map()->NumberOfOwnDescriptors();
725 Handle<DescriptorArray> descs(object->map()->instance_descriptors(),
726 isolate_);
727 CollectOwnPropertyNamesInternal<false>(object, this, descs, 0, limit);
728 } else if (object->IsJSGlobalObject()) {
729 GlobalDictionary::CollectKeysTo(
730 handle(JSGlobalObject::cast(*object)->global_dictionary(), isolate_),
731 this);
732 } else {
733 NameDictionary::CollectKeysTo(
734 handle(object->property_dictionary(), isolate_), this);
735 }
736}
737
738Maybe<bool> KeyAccumulator::CollectAccessCheckInterceptorKeys(
739 Handle<AccessCheckInfo> access_check_info, Handle<JSReceiver> receiver,
740 Handle<JSObject> object) {
741 if (!skip_indices_) {
742 MAYBE_RETURN((CollectInterceptorKeysInternal(
743 receiver, object,
744 handle(InterceptorInfo::cast(
745 access_check_info->indexed_interceptor()),
746 isolate_),
747 this, kIndexed)),
748 Nothing<bool>());
749 }
750 MAYBE_RETURN(
751 (CollectInterceptorKeysInternal(
752 receiver, object,
753 handle(InterceptorInfo::cast(access_check_info->named_interceptor()),
754 isolate_),
755 this, kNamed)),
756 Nothing<bool>());
757 return Just(true);
758}
759
760// Returns |true| on success, |false| if prototype walking should be stopped,
761// |nothing| if an exception was thrown.
762Maybe<bool> KeyAccumulator::CollectOwnKeys(Handle<JSReceiver> receiver,
763 Handle<JSObject> object) {
764 // Check access rights if required.
765 if (object->IsAccessCheckNeeded() &&
766 !isolate_->MayAccess(handle(isolate_->context(), isolate_), object)) {
767 // The cross-origin spec says that [[Enumerate]] shall return an empty
768 // iterator when it doesn't have access...
769 if (mode_ == KeyCollectionMode::kIncludePrototypes) {
770 return Just(false);
771 }
772 // ...whereas [[OwnPropertyKeys]] shall return whitelisted properties.
773 DCHECK_EQ(KeyCollectionMode::kOwnOnly, mode_);
774 Handle<AccessCheckInfo> access_check_info;
775 {
776 DisallowHeapAllocation no_gc;
777 AccessCheckInfo maybe_info = AccessCheckInfo::Get(isolate_, object);
778 if (!maybe_info.is_null()) {
779 access_check_info = handle(maybe_info, isolate_);
780 }
781 }
782 // We always have both kinds of interceptors or none.
783 if (!access_check_info.is_null() &&
784 access_check_info->named_interceptor() != Object()) {
785 MAYBE_RETURN(CollectAccessCheckInterceptorKeys(access_check_info,
786 receiver, object),
787 Nothing<bool>());
788 return Just(false);
789 }
790 filter_ = static_cast<PropertyFilter>(filter_ | ONLY_ALL_CAN_READ);
791 }
792 if (filter_ & PRIVATE_NAMES_ONLY) {
793 CollectPrivateNames(receiver, object);
794 return Just(true);
795 }
796
797 MAYBE_RETURN(CollectOwnElementIndices(receiver, object), Nothing<bool>());
798 MAYBE_RETURN(CollectOwnPropertyNames(receiver, object), Nothing<bool>());
799 return Just(true);
800}
801
802// static
803Handle<FixedArray> KeyAccumulator::GetOwnEnumPropertyKeys(
804 Isolate* isolate, Handle<JSObject> object) {
805 if (object->HasFastProperties()) {
806 return GetFastEnumPropertyKeys(isolate, object);
807 } else if (object->IsJSGlobalObject()) {
808 return GetOwnEnumPropertyDictionaryKeys(
809 isolate, KeyCollectionMode::kOwnOnly, nullptr, object,
810 JSGlobalObject::cast(*object)->global_dictionary());
811 } else {
812 return GetOwnEnumPropertyDictionaryKeys(
813 isolate, KeyCollectionMode::kOwnOnly, nullptr, object,
814 object->property_dictionary());
815 }
816}
817
818namespace {
819
820class NameComparator {
821 public:
822 explicit NameComparator(Isolate* isolate) : isolate_(isolate) {}
823
824 bool operator()(uint32_t hash1, uint32_t hash2, const Handle<Name>& key1,
825 const Handle<Name>& key2) const {
826 return Name::Equals(isolate_, key1, key2);
827 }
828
829 private:
830 Isolate* isolate_;
831};
832
833} // namespace
834
835// ES6 #sec-proxy-object-internal-methods-and-internal-slots-ownpropertykeys
836// Returns |true| on success, |nothing| in case of exception.
837Maybe<bool> KeyAccumulator::CollectOwnJSProxyKeys(Handle<JSReceiver> receiver,
838 Handle<JSProxy> proxy) {
839 STACK_CHECK(isolate_, Nothing<bool>());
840 if (filter_ == PRIVATE_NAMES_ONLY) {
841 NameDictionary::CollectKeysTo(
842 handle(proxy->property_dictionary(), isolate_), this);
843 return Just(true);
844 }
845
846 // 1. Let handler be the value of the [[ProxyHandler]] internal slot of O.
847 Handle<Object> handler(proxy->handler(), isolate_);
848 // 2. If handler is null, throw a TypeError exception.
849 // 3. Assert: Type(handler) is Object.
850 if (proxy->IsRevoked()) {
851 isolate_->Throw(*isolate_->factory()->NewTypeError(
852 MessageTemplate::kProxyRevoked, isolate_->factory()->ownKeys_string()));
853 return Nothing<bool>();
854 }
855 // 4. Let target be the value of the [[ProxyTarget]] internal slot of O.
856 Handle<JSReceiver> target(JSReceiver::cast(proxy->target()), isolate_);
857 // 5. Let trap be ? GetMethod(handler, "ownKeys").
858 Handle<Object> trap;
859 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
860 isolate_, trap, Object::GetMethod(Handle<JSReceiver>::cast(handler),
861 isolate_->factory()->ownKeys_string()),
862 Nothing<bool>());
863 // 6. If trap is undefined, then
864 if (trap->IsUndefined(isolate_)) {
865 // 6a. Return target.[[OwnPropertyKeys]]().
866 return CollectOwnJSProxyTargetKeys(proxy, target);
867 }
868 // 7. Let trapResultArray be Call(trap, handler, «target»).
869 Handle<Object> trap_result_array;
870 Handle<Object> args[] = {target};
871 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
872 isolate_, trap_result_array,
873 Execution::Call(isolate_, trap, handler, arraysize(args), args),
874 Nothing<bool>());
875 // 8. Let trapResult be ? CreateListFromArrayLike(trapResultArray,
876 // «String, Symbol»).
877 Handle<FixedArray> trap_result;
878 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
879 isolate_, trap_result,
880 Object::CreateListFromArrayLike(isolate_, trap_result_array,
881 ElementTypes::kStringAndSymbol),
882 Nothing<bool>());
883 // 9. If trapResult contains any duplicate entries, throw a TypeError
884 // exception. Combine with step 18
885 // 18. Let uncheckedResultKeys be a new List which is a copy of trapResult.
886 Zone set_zone(isolate_->allocator(), ZONE_NAME);
887 ZoneAllocationPolicy alloc(&set_zone);
888 const int kPresent = 1;
889 const int kGone = 0;
890 base::TemplateHashMapImpl<Handle<Name>, int, NameComparator,
891 ZoneAllocationPolicy>
892 unchecked_result_keys(ZoneHashMap::kDefaultHashMapCapacity,
893 NameComparator(isolate_), alloc);
894 int unchecked_result_keys_size = 0;
895 for (int i = 0; i < trap_result->length(); ++i) {
896 Handle<Name> key(Name::cast(trap_result->get(i)), isolate_);
897 auto entry = unchecked_result_keys.LookupOrInsert(key, key->Hash(), alloc);
898 if (entry->value != kPresent) {
899 entry->value = kPresent;
900 unchecked_result_keys_size++;
901 } else {
902 // found dupes, throw exception
903 isolate_->Throw(*isolate_->factory()->NewTypeError(
904 MessageTemplate::kProxyOwnKeysDuplicateEntries));
905 return Nothing<bool>();
906 }
907 }
908 // 10. Let extensibleTarget be ? IsExtensible(target).
909 Maybe<bool> maybe_extensible = JSReceiver::IsExtensible(target);
910 MAYBE_RETURN(maybe_extensible, Nothing<bool>());
911 bool extensible_target = maybe_extensible.FromJust();
912 // 11. Let targetKeys be ? target.[[OwnPropertyKeys]]().
913 Handle<FixedArray> target_keys;
914 ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate_, target_keys,
915 JSReceiver::OwnPropertyKeys(target),
916 Nothing<bool>());
917 // 12, 13. (Assert)
918 // 14. Let targetConfigurableKeys be an empty List.
919 // To save memory, we're re-using target_keys and will modify it in-place.
920 Handle<FixedArray> target_configurable_keys = target_keys;
921 // 15. Let targetNonconfigurableKeys be an empty List.
922 Handle<FixedArray> target_nonconfigurable_keys =
923 isolate_->factory()->NewFixedArray(target_keys->length());
924 int nonconfigurable_keys_length = 0;
925 // 16. Repeat, for each element key of targetKeys:
926 for (int i = 0; i < target_keys->length(); ++i) {
927 // 16a. Let desc be ? target.[[GetOwnProperty]](key).
928 PropertyDescriptor desc;
929 Maybe<bool> found = JSReceiver::GetOwnPropertyDescriptor(
930 isolate_, target, handle(target_keys->get(i), isolate_), &desc);
931 MAYBE_RETURN(found, Nothing<bool>());
932 // 16b. If desc is not undefined and desc.[[Configurable]] is false, then
933 if (found.FromJust() && !desc.configurable()) {
934 // 16b i. Append key as an element of targetNonconfigurableKeys.
935 target_nonconfigurable_keys->set(nonconfigurable_keys_length,
936 target_keys->get(i));
937 nonconfigurable_keys_length++;
938 // The key was moved, null it out in the original list.
939 target_keys->set(i, Smi::kZero);
940 } else {
941 // 16c. Else,
942 // 16c i. Append key as an element of targetConfigurableKeys.
943 // (No-op, just keep it in |target_keys|.)
944 }
945 }
946 // 17. If extensibleTarget is true and targetNonconfigurableKeys is empty,
947 // then:
948 if (extensible_target && nonconfigurable_keys_length == 0) {
949 // 17a. Return trapResult.
950 return AddKeysFromJSProxy(proxy, trap_result);
951 }
952 // 18. (Done in step 9)
953 // 19. Repeat, for each key that is an element of targetNonconfigurableKeys:
954 for (int i = 0; i < nonconfigurable_keys_length; ++i) {
955 Object raw_key = target_nonconfigurable_keys->get(i);
956 Handle<Name> key(Name::cast(raw_key), isolate_);
957 // 19a. If key is not an element of uncheckedResultKeys, throw a
958 // TypeError exception.
959 auto found = unchecked_result_keys.Lookup(key, key->Hash());
960 if (found == nullptr || found->value == kGone) {
961 isolate_->Throw(*isolate_->factory()->NewTypeError(
962 MessageTemplate::kProxyOwnKeysMissing, key));
963 return Nothing<bool>();
964 }
965 // 19b. Remove key from uncheckedResultKeys.
966 found->value = kGone;
967 unchecked_result_keys_size--;
968 }
969 // 20. If extensibleTarget is true, return trapResult.
970 if (extensible_target) {
971 return AddKeysFromJSProxy(proxy, trap_result);
972 }
973 // 21. Repeat, for each key that is an element of targetConfigurableKeys:
974 for (int i = 0; i < target_configurable_keys->length(); ++i) {
975 Object raw_key = target_configurable_keys->get(i);
976 if (raw_key->IsSmi()) continue; // Zapped entry, was nonconfigurable.
977 Handle<Name> key(Name::cast(raw_key), isolate_);
978 // 21a. If key is not an element of uncheckedResultKeys, throw a
979 // TypeError exception.
980 auto found = unchecked_result_keys.Lookup(key, key->Hash());
981 if (found == nullptr || found->value == kGone) {
982 isolate_->Throw(*isolate_->factory()->NewTypeError(
983 MessageTemplate::kProxyOwnKeysMissing, key));
984 return Nothing<bool>();
985 }
986 // 21b. Remove key from uncheckedResultKeys.
987 found->value = kGone;
988 unchecked_result_keys_size--;
989 }
990 // 22. If uncheckedResultKeys is not empty, throw a TypeError exception.
991 if (unchecked_result_keys_size != 0) {
992 DCHECK_GT(unchecked_result_keys_size, 0);
993 isolate_->Throw(*isolate_->factory()->NewTypeError(
994 MessageTemplate::kProxyOwnKeysNonExtensible));
995 return Nothing<bool>();
996 }
997 // 23. Return trapResult.
998 return AddKeysFromJSProxy(proxy, trap_result);
999}
1000
1001Maybe<bool> KeyAccumulator::CollectOwnJSProxyTargetKeys(
1002 Handle<JSProxy> proxy, Handle<JSReceiver> target) {
1003 // TODO(cbruni): avoid creating another KeyAccumulator
1004 Handle<FixedArray> keys;
1005 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
1006 isolate_, keys,
1007 KeyAccumulator::GetKeys(
1008 target, KeyCollectionMode::kOwnOnly, ALL_PROPERTIES,
1009 GetKeysConversion::kConvertToString, is_for_in_, skip_indices_),
1010 Nothing<bool>());
1011 Maybe<bool> result = AddKeysFromJSProxy(proxy, keys);
1012 return result;
1013}
1014
1015} // namespace internal
1016} // namespace v8
1017