[keys] keep track of first and last non-empty prototype

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 13 matching lines @@
 static bool ContainsOnlyValidKeys(Handle<FixedArray> array) {
   int len = array->length();
   for (int i = 0; i < len; i++) {
     Object* e = array->get(i);
     if (!(e->IsName() || e->IsNumber())) return false;
   }
   return true;
 }
 
 }  // namespace
-
 MaybeHandle<FixedArray> KeyAccumulator::GetKeys(
     Handle<JSReceiver> object, KeyCollectionMode mode, PropertyFilter filter,
     GetKeysConversion keys_conversion, bool filter_proxy_keys, bool is_for_in) {
-  USE(ContainsOnlyValidKeys);
   Isolate* isolate = object->GetIsolate();
   KeyAccumulator accumulator(isolate, mode, filter);
   accumulator.set_filter_proxy_keys(filter_proxy_keys);
   accumulator.set_is_for_in(is_for_in);
   MAYBE_RETURN(accumulator.CollectKeys(object, object),
                MaybeHandle<FixedArray>());
-  Handle<FixedArray> keys = accumulator.GetKeys(keys_conversion);
-  DCHECK(ContainsOnlyValidKeys(keys));
-  return keys;
+  return accumulator.GetKeys(keys_conversion);
 }
 
 Handle<FixedArray> KeyAccumulator::GetKeys(GetKeysConversion convert) {
   if (keys_.is_null()) {
     return isolate_->factory()->empty_fixed_array();
   }
   if (mode_ == KeyCollectionMode::kOwnOnly &&
       keys_->map() == isolate_->heap()->fixed_array_map()) {
     return Handle<FixedArray>::cast(keys_);
   }
-  return OrderedHashSet::ConvertToKeysArray(keys(), convert);
+  USE(ContainsOnlyValidKeys);
+  Handle<FixedArray> result =
+      OrderedHashSet::ConvertToKeysArray(keys(), convert);
+  DCHECK(ContainsOnlyValidKeys(result));
+  return result;
 }
 
 void KeyAccumulator::AddKey(Object* key, AddKeyConversion convert) {
   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;
@@ skipping 100 matching lines @@
       DCHECK(current->IsJSObject());
       result = CollectOwnKeys(receiver, Handle<JSObject>::cast(current));
     }
     MAYBE_RETURN(result, Nothing<bool>());
     if (!result.FromJust()) break;  // |false| means "stop iterating".
     // Iterate through proxies but ignore access checks for the ALL_CAN_READ
     // case on API objects for OWN_ONLY keys handled in CollectOwnKeys.
     if (!iter.AdvanceFollowingProxiesIgnoringAccessChecks()) {
       return Nothing<bool>();
     }
+    if (!last_non_empty_prototype_.is_null() &&
+        *last_non_empty_prototype_ == *current) {
+      break;
+    }
   }
   return Just(true);
 }
 
 namespace {
 
 void TrySettingEmptyEnumCache(JSReceiver* object) {
   Map* map = object->map();
   DCHECK_EQ(kInvalidEnumCacheSentinel, map->EnumLength());
   if (!map->OnlyHasSimpleProperties()) return;
@@ skipping 17 matching lines @@
 }
 }  // namespace
 
 void FastKeyAccumulator::Prepare() {
   DisallowHeapAllocation no_gc;
   // Directly go for the fast path for OWN_ONLY keys.
   if (mode_ == KeyCollectionMode::kOwnOnly) return;
   // Fully walk the prototype chain and find the last prototype with keys.
   is_receiver_simple_enum_ = false;
   has_empty_prototype_ = true;
-  JSReceiver* first_non_empty_prototype;
+  JSReceiver* last_prototype = nullptr;
   for (PrototypeIterator iter(isolate_, *receiver_); !iter.IsAtEnd();
        iter.Advance()) {
     JSReceiver* current = iter.GetCurrent<JSReceiver>();
-    if (CheckAndInitalizeSimpleEnumCache(current)) continue;
+    bool has_no_properties = CheckAndInitalizeSimpleEnumCache(current);
+    if (has_no_properties) continue;
+    last_prototype = current;
     has_empty_prototype_ = false;
-    first_non_empty_prototype = current;
-    // TODO(cbruni): use the first non-empty prototype.
-    USE(first_non_empty_prototype);
-    return;
   }
-  DCHECK(has_empty_prototype_);
-  is_receiver_simple_enum_ =
-      receiver_->map()->EnumLength() != kInvalidEnumCacheSentinel &&
-      !JSObject::cast(*receiver_)->HasEnumerableElements();
+  if (has_empty_prototype_) {
+    is_receiver_simple_enum_ =
+        receiver_->map()->EnumLength() != kInvalidEnumCacheSentinel &&
+        !JSObject::cast(*receiver_)->HasEnumerableElements();
+  } else if (last_prototype != nullptr) {
+    last_non_empty_prototype_ = handle(last_prototype, isolate_);
+  }
 }
 
 namespace {
 static Handle<FixedArray> ReduceFixedArrayTo(Isolate* isolate,
                                              Handle<FixedArray> array,
                                              int length) {
   DCHECK_LE(length, array->length());
   if (array->length() == length) return array;
   return isolate->factory()->CopyFixedArrayUpTo(array, length);
 }
@@ skipping 114 matching lines @@
   // directly initialize the enum cache.
   return GetFastEnumPropertyKeys(isolate, object);
 }
 
 bool OnlyHasSimpleProperties(Map* map) {
   return map->instance_type() > LAST_CUSTOM_ELEMENTS_RECEIVER;
 }
 
 }  // namespace
 
-MaybeHandle<FixedArray> FastKeyAccumulator::GetKeys(GetKeysConversion convert) {
+MaybeHandle<FixedArray> FastKeyAccumulator::GetKeys(
+    GetKeysConversion keys_conversion) {
   Handle<FixedArray> keys;
-  if (GetKeysFast(convert).ToHandle(&keys)) {
+  if (filter_ == ENUMERABLE_STRINGS &&
+      GetKeysFast(keys_conversion).ToHandle(&keys)) {
     return keys;
   }
-  return GetKeysSlow(convert);
+  return GetKeysSlow(keys_conversion);
 }
 
 MaybeHandle<FixedArray> FastKeyAccumulator::GetKeysFast(
-    GetKeysConversion convert) {
+    GetKeysConversion keys_conversion) {
   bool own_only = has_empty_prototype_ || mode_ == KeyCollectionMode::kOwnOnly;
   Map* map = receiver_->map();
   if (!own_only || !OnlyHasSimpleProperties(map)) {
     return MaybeHandle<FixedArray>();
   }
 
   // From this point on we are certiain to only collect own keys.
   DCHECK(receiver_->IsJSObject());
   Handle<JSObject> object = Handle<JSObject>::cast(receiver_);
 
   // Do not try to use the enum-cache for dict-mode objects.
   if (map->is_dictionary_map()) {
-    return GetOwnKeysWithElements<false>(isolate_, object, convert);
+    return GetOwnKeysWithElements<false>(isolate_, object, keys_conversion);
   }
   int enum_length = receiver_->map()->EnumLength();
   if (enum_length == kInvalidEnumCacheSentinel) {
     Handle<FixedArray> keys;
     // Try initializing the enum cache and return own properties.
     if (GetOwnKeysWithUninitializedEnumCache(isolate_, object)
             .ToHandle(&keys)) {
       if (FLAG_trace_for_in_enumerate) {
         PrintF("| strings=%d symbols=0 elements=0 || prototypes>=1 ||\n",
                keys->length());
       }
       is_receiver_simple_enum_ =
           object->map()->EnumLength() != kInvalidEnumCacheSentinel;
       return keys;
     }
   }
   // The properties-only case failed because there were probably elements on the
   // receiver.
-  return GetOwnKeysWithElements<true>(isolate_, object, convert);
+  return GetOwnKeysWithElements<true>(isolate_, object, keys_conversion);
 }
 
 MaybeHandle<FixedArray> FastKeyAccumulator::GetKeysSlow(
-    GetKeysConversion convert) {
-  return KeyAccumulator::GetKeys(receiver_, mode_, filter_,
-                                 GetKeysConversion::kKeepNumbers,
-                                 filter_proxy_keys_, is_for_in_);
+    GetKeysConversion keys_conversion) {
+  KeyAccumulator accumulator(isolate_, mode_, filter_);
+  accumulator.set_filter_proxy_keys(filter_proxy_keys_);
+  accumulator.set_is_for_in(is_for_in_);
+  accumulator.set_last_non_empty_prototype(last_non_empty_prototype_);
+
+  MAYBE_RETURN(accumulator.CollectKeys(receiver_, receiver_),
+               MaybeHandle<FixedArray>());
+  return accumulator.GetKeys(keys_conversion);
 }
 
 namespace {
 
 enum IndexedOrNamed { kIndexed, kNamed };
 
 // Returns |true| on success, |nothing| on exception.
 template <class Callback, IndexedOrNamed type>
-Maybe<bool> GetKeysFromInterceptor(Handle<JSReceiver> receiver,
+Maybe<bool> CollectInterceptorKeys(Handle<JSReceiver> receiver,
                                    Handle<JSObject> object,
                                    KeyAccumulator* accumulator) {
   Isolate* isolate = accumulator->isolate();
   if (type == kIndexed) {
     if (!object->HasIndexedInterceptor()) return Just(true);
   } else {
     if (!object->HasNamedInterceptor()) return Just(true);
   }
   Handle<InterceptorInfo> interceptor(type == kIndexed
                                           ? object->GetIndexedInterceptor()
@@ skipping 22 matching lines @@
 
 }  // namespace
 
 Maybe<bool> KeyAccumulator::CollectOwnElementIndices(
     Handle<JSReceiver> receiver, Handle<JSObject> object) {
   if (filter_ & SKIP_STRINGS || skip_indices_) return Just(true);
 
   ElementsAccessor* accessor = object->GetElementsAccessor();
   accessor->CollectElementIndices(object, this);
 
-  return GetKeysFromInterceptor<v8::IndexedPropertyEnumeratorCallback,
+  return CollectInterceptorKeys<v8::IndexedPropertyEnumeratorCallback,
                                 kIndexed>(receiver, object, this);
 }
 
 namespace {
 
 template <bool skip_symbols>
 int CollectOwnPropertyNamesInternal(Handle<JSObject> object,
                                     KeyAccumulator* keys,
                                     Handle<DescriptorArray> descs,
                                     int start_index, int limit) {
@@ skipping 41 matching lines @@
       }
     } else if (object->IsJSGlobalObject()) {
       GlobalDictionary::CollectKeysTo(
           handle(object->global_dictionary(), isolate_), this, filter_);
     } else {
       NameDictionary::CollectKeysTo(
           handle(object->property_dictionary(), isolate_), this, filter_);
     }
   }
   // Add the property keys from the interceptor.
-  return GetKeysFromInterceptor<v8::GenericNamedPropertyEnumeratorCallback,
+  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)) {
@@ skipping 192 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