[keys] support shadowing keys in the KeyAccumulator

src/keys.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/keys.h"
 
 #include "src/api-arguments.h"
 #include "src/elements.h"
 #include "src/factory.h"
 #include "src/identity-map.h"
@@ skipping 51 matching lines @@
   AddKey(handle(key, isolate_), convert);
 }
 
 void KeyAccumulator::AddKey(Handle<Object> key, AddKeyConversion convert) {
   if (key->IsSymbol()) {
     if (filter_ & SKIP_SYMBOLS) return;
     if (Handle<Symbol>::cast(key)->is_private()) return;
   } else if (filter_ & SKIP_STRINGS) {
     return;
   }
+  if (IsShadowed(key)) return;
   if (keys_.is_null()) {
     keys_ = OrderedHashSet::Allocate(isolate_, 16);
   }
   uint32_t index;
   if (convert == CONVERT_TO_ARRAY_INDEX && key->IsString() &&
       Handle<String>::cast(key)->AsArrayIndex(&index)) {
     key = isolate_->factory()->NewNumberFromUint(index);
   }
   keys_ = OrderedHashSet::Add(keys(), key);
 }
 
 void KeyAccumulator::AddKeys(Handle<FixedArray> array,
                              AddKeyConversion convert) {
   int add_length = array->length();
   for (int i = 0; i < add_length; i++) {
     Handle<Object> current(array->get(i), isolate_);
     AddKey(current, convert);
   }
 }
 
 void KeyAccumulator::AddKeys(Handle<JSObject> array_like,
                              AddKeyConversion convert) {
   DCHECK(array_like->IsJSArray() || array_like->HasSloppyArgumentsElements());
   ElementsAccessor* accessor = array_like->GetElementsAccessor();
   accessor->AddElementsToKeyAccumulator(array_like, this, convert);
 }
 
-MaybeHandle<FixedArray> FilterProxyKeys(Isolate* isolate, Handle<JSProxy> owner,
+MaybeHandle<FixedArray> FilterProxyKeys(KeyAccumulator* accumulator,
+                                        Handle<JSProxy> owner,
                                         Handle<FixedArray> keys,
                                         PropertyFilter filter) {
   if (filter == ALL_PROPERTIES) {
     // Nothing to do.
     return keys;
   }
+  Isolate* isolate = accumulator->isolate();
   int store_position = 0;
   for (int i = 0; i < keys->length(); ++i) {
     Handle<Name> key(Name::cast(keys->get(i)), isolate);
     if (key->FilterKey(filter)) continue;  // Skip this key.
     if (filter & ONLY_ENUMERABLE) {
       PropertyDescriptor desc;
       Maybe<bool> found =
           JSProxy::GetOwnPropertyDescriptor(isolate, owner, key, &desc);
       MAYBE_RETURN(found, MaybeHandle<FixedArray>());
-      if (!found.FromJust() || !desc.enumerable()) continue;  // Skip this key.
+      if (!found.FromJust()) continue;
+      if (!desc.enumerable()) {
+        accumulator->AddShadowKey(key);
+        continue;
+      }
     }
     // Keep this key.
     if (store_position != i) {
       keys->set(store_position, *key);
     }
     store_position++;
   }
   if (store_position == 0) return isolate->factory()->empty_fixed_array();
   keys->Shrink(store_position);
   return keys;
 }
 
 // Returns "nothing" in case of exception, "true" on success.
 Maybe<bool> KeyAccumulator::AddKeysFromJSProxy(Handle<JSProxy> proxy,
                                                Handle<FixedArray> keys) {
   if (filter_proxy_keys_) {
     DCHECK(!is_for_in_);
     ASSIGN_RETURN_ON_EXCEPTION_VALUE(
-        isolate_, keys, FilterProxyKeys(isolate_, proxy, keys, filter_),
+        isolate_, keys, FilterProxyKeys(this, proxy, keys, filter_),
         Nothing<bool>());
   }
   if (mode_ == KeyCollectionMode::kOwnOnly && !is_for_in_) {
     // If we collect only the keys from a JSProxy do not sort or deduplicate it.
     keys_ = keys;
     return Just(true);
   }
   AddKeys(keys, is_for_in_ ? CONVERT_TO_ARRAY_INDEX : DO_NOT_CONVERT);
   return Just(true);
 }
@@ skipping 31 matching lines @@
       return Nothing<bool>();
     }
     if (!last_non_empty_prototype_.is_null() &&
         *last_non_empty_prototype_ == *current) {
       break;
     }
   }
   return Just(true);
 }
 
+bool KeyAccumulator::IsShadowed(Handle<Object> key) {
+  if (shadowed_keys_.is_null()) return false;
+  return shadowed_keys_->Has(isolate_, key);
+}
+
+void KeyAccumulator::AddShadowKey(Object* key) {
+  if (mode_ == KeyCollectionMode::kOwnOnly) return;
+  AddShadowKey(handle(key, isolate_));
+}
+void KeyAccumulator::AddShadowKey(Handle<Object> key) {
+  if (mode_ == KeyCollectionMode::kOwnOnly) return;
+  if (shadowed_keys_.is_null()) {
+    shadowed_keys_ = ObjectHashSet::New(isolate_, 16);
+  }
+  shadowed_keys_ = ObjectHashSet::Add(shadowed_keys_, key);
+}
+
 namespace {
 
 void TrySettingEmptyEnumCache(JSReceiver* object) {
   Map* map = object->map();
   DCHECK_EQ(kInvalidEnumCacheSentinel, map->EnumLength());
   if (!map->OnlyHasSimpleProperties()) return;
   if (map->IsJSProxyMap()) return;
   if (map->NumberOfOwnDescriptors() > 0) {
     int number_of_enumerable_own_properties =
         map->NumberOfDescribedProperties(OWN_DESCRIPTORS, ENUMERABLE_STRINGS);
@@ skipping 126 matching lines @@
 template <bool fast_properties>
 Handle<FixedArray> GetOwnKeysWithElements(Isolate* isolate,
                                           Handle<JSObject> object,
                                           GetKeysConversion convert) {
   Handle<FixedArray> keys;
   ElementsAccessor* accessor = object->GetElementsAccessor();
   if (fast_properties) {
     keys = GetFastEnumPropertyKeys(isolate, object);
   } else {
     // TODO(cbruni): preallocate big enough array to also hold elements.
-    keys = KeyAccumulator::GetEnumPropertyKeys(isolate, object);
+    keys = KeyAccumulator::GetOwnEnumPropertyKeys(isolate, object);
   }
   Handle<FixedArray> result =
       accessor->PrependElementIndices(object, keys, convert, ONLY_ENUMERABLE);
 
   if (FLAG_trace_for_in_enumerate) {
     PrintF("| strings=%d symbols=0 elements=%u || prototypes>=1 ||\n",
            keys->length(), result->length() - keys->length());
   }
   return result;
 }
@@ skipping 135 matching lines @@
 }
 
 namespace {
 
 template <bool skip_symbols>
 int CollectOwnPropertyNamesInternal(Handle<JSObject> object,
                                     KeyAccumulator* keys,
                                     Handle<DescriptorArray> descs,
                                     int start_index, int limit) {
   int first_skipped = -1;
+  PropertyFilter filter = keys->filter();
+  KeyCollectionMode mode = keys->mode();
+  bool is_shadowing_key = false;

[adamk, 2016/06/27 19:19:33]

This declaration seems like it'd be clearer inside the loop. Is it out here for
some reason I'm missing?

[Camillo Bruni, 2016/06/29 17:27:56]

pushing it into the loop

   for (int i = start_index; i < limit; i++) {
+    is_shadowing_key = false;
     PropertyDetails details = descs->GetDetails(i);
-    if ((details.attributes() & keys->filter()) != 0) continue;
-    if (keys->filter() & ONLY_ALL_CAN_READ) {
+
+    if ((details.attributes() & filter) != 0) {
+      if (mode == KeyCollectionMode::kIncludePrototypes) {
+        is_shadowing_key = true;
+      } else {
+        continue;
+      }
+    }
+
+    if (filter & ONLY_ALL_CAN_READ) {
       if (details.kind() != kAccessor) continue;
       Object* accessors = descs->GetValue(i);
       if (!accessors->IsAccessorInfo()) continue;
       if (!AccessorInfo::cast(accessors)->all_can_read()) continue;
     }
+
     Name* key = descs->GetKey(i);
     if (skip_symbols == key->IsSymbol()) {
       if (first_skipped == -1) first_skipped = i;
       continue;
     }
     if (key->FilterKey(keys->filter())) continue;
-    keys->AddKey(key, DO_NOT_CONVERT);
+
+    if (is_shadowing_key) {
+      keys->AddShadowKey(key);
+    } else {
+      keys->AddKey(key, DO_NOT_CONVERT);
+    }
   }
   return first_skipped;
 }
 
+template <class T>
+Handle<FixedArray> GetOwnEnumPropertyDictionaryKeys(Isolate* isolate,
+                                                    KeyCollectionMode mode,
+                                                    KeyAccumulator* accumulator,
+                                                    Handle<JSObject> object,
+                                                    T* raw_dictionary) {
+  Handle<T> dictionary(raw_dictionary, isolate);
+  int length = dictionary->NumberOfEnumElements();
+  if (length == 0) {
+    return isolate->factory()->empty_fixed_array();
+  }
+  Handle<FixedArray> storage = isolate->factory()->NewFixedArray(length);
+  T::CopyEnumKeysTo(dictionary, storage, mode, accumulator);
+  return storage;
+}
 }  // namespace
 
 Maybe<bool> KeyAccumulator::CollectOwnPropertyNames(Handle<JSReceiver> receiver,
                                                     Handle<JSObject> object) {
   if (filter_ == ENUMERABLE_STRINGS) {
-    Handle<FixedArray> enum_keys =
-        KeyAccumulator::GetEnumPropertyKeys(isolate_, object);
+    Handle<FixedArray> enum_keys;
+    if (object->HasFastProperties()) {
+      enum_keys = KeyAccumulator::GetOwnEnumPropertyKeys(isolate_, object);
+      // If the number of properties equals the length of enumerable properties
+      // we do not have to filter out non-enumerable ones
+      Map* map = object->map();
+      int nof_descriptors = map->NumberOfOwnDescriptors();
+      if (enum_keys->length() != nof_descriptors) {
+        Handle<DescriptorArray> descs =
+            Handle<DescriptorArray>(map->instance_descriptors(), isolate_);
+        for (int i = 0; i < nof_descriptors; i++) {
+          PropertyDetails details = descs->GetDetails(i);
+          if (!details.IsDontEnum()) continue;
+          Object* key = descs->GetKey(i);
+          this->AddShadowKey(key);
+        }
+      }
+    } else if (object->IsJSGlobalObject()) {
+      enum_keys = GetOwnEnumPropertyDictionaryKeys(
+          isolate_, mode_, this, object, object->global_dictionary());
+    } else {
+      enum_keys = GetOwnEnumPropertyDictionaryKeys(
+          isolate_, mode_, this, object, object->property_dictionary());
+    }
     AddKeys(enum_keys, DO_NOT_CONVERT);
   } else {
     if (object->HasFastProperties()) {
       int limit = object->map()->NumberOfOwnDescriptors();
       Handle<DescriptorArray> descs(object->map()->instance_descriptors(),
                                     isolate_);
       // First collect the strings,
       int first_symbol =
           CollectOwnPropertyNamesInternal<true>(object, this, descs, 0, limit);
       // then the symbols.
       if (first_symbol != -1) {
         CollectOwnPropertyNamesInternal<false>(object, this, descs,
                                                first_symbol, limit);
       }
     } else if (object->IsJSGlobalObject()) {
       GlobalDictionary::CollectKeysTo(
-          handle(object->global_dictionary(), isolate_), this, filter_);
+          handle(object->global_dictionary(), isolate_), this);
     } else {
       NameDictionary::CollectKeysTo(
-          handle(object->property_dictionary(), isolate_), this, filter_);
+          handle(object->property_dictionary(), isolate_), this);
     }
   }
   // Add the property keys from the interceptor.
   return CollectInterceptorKeys<v8::GenericNamedPropertyEnumeratorCallback,
                                 kNamed>(receiver, object, this);
 }
 
 // Returns |true| on success, |false| if prototype walking should be stopped,
 // |nothing| if an exception was thrown.
 Maybe<bool> KeyAccumulator::CollectOwnKeys(Handle<JSReceiver> receiver,
                                            Handle<JSObject> object) {
   // Check access rights if required.
   if (object->IsAccessCheckNeeded() &&
       !isolate_->MayAccess(handle(isolate_->context()), object)) {
     // The cross-origin spec says that [[Enumerate]] shall return an empty
     // iterator when it doesn't have access...
     if (mode_ == KeyCollectionMode::kIncludePrototypes) {
       return Just(false);
     }
     // ...whereas [[OwnPropertyKeys]] shall return whitelisted properties.
     DCHECK(KeyCollectionMode::kOwnOnly == mode_);
     filter_ = static_cast<PropertyFilter>(filter_ | ONLY_ALL_CAN_READ);
   }
   MAYBE_RETURN(CollectOwnElementIndices(receiver, object), Nothing<bool>());
   MAYBE_RETURN(CollectOwnPropertyNames(receiver, object), Nothing<bool>());
   return Just(true);
 }
 
 // static
-Handle<FixedArray> KeyAccumulator::GetEnumPropertyKeys(
+Handle<FixedArray> KeyAccumulator::GetOwnEnumPropertyKeys(
     Isolate* isolate, Handle<JSObject> object) {
   if (object->HasFastProperties()) {
     return GetFastEnumPropertyKeys(isolate, object);
   } else if (object->IsJSGlobalObject()) {
-    Handle<GlobalDictionary> dictionary(object->global_dictionary(), isolate);
-    int length = dictionary->NumberOfEnumElements();
-    if (length == 0) {
-      return isolate->factory()->empty_fixed_array();
-    }
-    Handle<FixedArray> storage = isolate->factory()->NewFixedArray(length);
-    dictionary->CopyEnumKeysTo(*storage);
-    return storage;
+    return GetOwnEnumPropertyDictionaryKeys(
+        isolate, KeyCollectionMode::kOwnOnly, nullptr, object,
+        object->global_dictionary());
   } else {
-    Handle<NameDictionary> dictionary(object->property_dictionary(), isolate);
-    int length = dictionary->NumberOfEnumElements();
-    if (length == 0) {
-      return isolate->factory()->empty_fixed_array();
-    }
-    Handle<FixedArray> storage = isolate->factory()->NewFixedArray(length);
-    dictionary->CopyEnumKeysTo(*storage);
-    return storage;
+    return GetOwnEnumPropertyDictionaryKeys(
+        isolate, KeyCollectionMode::kOwnOnly, nullptr, object,
+        object->property_dictionary());
   }
 }
 
 // ES6 9.5.12
 // Returns |true| on success, |nothing| in case of exception.
 Maybe<bool> KeyAccumulator::CollectOwnJSProxyKeys(Handle<JSReceiver> receiver,
                                                   Handle<JSProxy> proxy) {
   STACK_CHECK(isolate_, Nothing<bool>());
   // 1. Let handler be the value of the [[ProxyHandler]] internal slot of O.
   Handle<Object> handler(proxy->handler(), isolate_);
@@ skipping 145 matching lines @@
       isolate_, keys, JSReceiver::OwnPropertyKeys(target), Nothing<bool>());
   bool prev_filter_proxy_keys_ = filter_proxy_keys_;
   filter_proxy_keys_ = false;
   Maybe<bool> result = AddKeysFromJSProxy(proxy, keys);
   filter_proxy_keys_ = prev_filter_proxy_keys_;
   return result;
 }
 
 }  // namespace internal
 }  // namespace v8