[runtime] Fancify KeyAccumulator

src/objects.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/objects.h"
 
 #include <cmath>
 #include <iomanip>
 #include <sstream>
 
 #include "src/accessors.h"
 #include "src/allocation-site-scopes.h"
 #include "src/api.h"
 #include "src/arguments.h"
 #include "src/base/bits.h"
 #include "src/base/utils/random-number-generator.h"
 #include "src/bootstrapper.h"
 #include "src/code-stubs.h"
 #include "src/codegen.h"
 #include "src/compilation-dependencies.h"
 #include "src/compiler.h"
 #include "src/date.h"
 #include "src/debug/debug.h"
 #include "src/deoptimizer.h"
 #include "src/elements.h"
 #include "src/execution.h"
+#include "src/field-index.h"
 #include "src/field-index-inl.h"
-#include "src/field-index.h"
 #include "src/full-codegen/full-codegen.h"
 #include "src/hydrogen.h"
 #include "src/ic/ic.h"
 #include "src/interpreter/bytecodes.h"
 #include "src/isolate-inl.h"
+#include "src/list.h"
 #include "src/log.h"
 #include "src/lookup.h"
 #include "src/macro-assembler.h"
 #include "src/messages.h"
 #include "src/objects-inl.h"
 #include "src/profiler/cpu-profiler.h"
 #include "src/prototype.h"
 #include "src/safepoint-table.h"
 #include "src/string-builder.h"
 #include "src/string-search.h"
@@ skipping 6726 matching lines @@
     if (length == 0) {
       return Handle<FixedArray>(isolate->heap()->empty_fixed_array());
     }
     Handle<FixedArray> storage = isolate->factory()->NewFixedArray(length);
     dictionary->CopyEnumKeysTo(*storage);
     return storage;
   }
 }
 
 
-Handle<FixedArray> KeyAccumulator::GetKeys() {
+KeyAccumulator::~KeyAccumulator() {
+  for (int i = 0; i < elements_.length(); i++) {
+    delete elements_[i];
+  }
+}
+
+
+Handle<FixedArray> KeyAccumulator::GetKeys(GetKeysConversion convert) {
   if (length_ == 0) {
     return isolate_->factory()->empty_fixed_array();
   }
-  if (set_.is_null()) {
-    keys_->Shrink(length_);
-    return keys_;
-  }
-  // copy over results from set_
+  // make sure we have all the lengths collected
+  NextPrototype();
+
+  // Assemble the result array by first adding the element keys and then
+  // the property keys. We use the total number of keys per level in
+  // |protoLengths_| and the available element keys in the corresponding bucket
+  // in |elements_| to deduce the number of keys to take from the |properties_|
+  // set.
   Handle<FixedArray> result = isolate_->factory()->NewFixedArray(length_);
-  for (int i = 0; i < length_; i++) {
-    result->set(i, set_->KeyAt(i));
+  int index = 0;
+  int properties_index = 0;
+  for (int level = 0; level < levelLengths_.length(); level++) {
+    int num_total = levelLengths_[level];
+    int num_elements = 0;
+    if (num_total < 0) {
+      // If the total is negative, the current level contains properties from a
+      // proxy, hence we skip the integer keys in |elements_| since procies

[Igor Sheludko, 2015/10/15 09:51:44]

s/procies/proxies/

+      // define the complete ordering.
+      num_total = -num_total;
+    } else if (level < elements_.length()) {
+      List<uint32_t>* elements = elements_[level];
+      num_elements = elements->length();
+      for (int i = 0; i < num_elements; i++) {
+        Handle<Object> key;
+        if (convert == KEEP_NUMBERS) {
+          key = isolate_->factory()->NewNumberFromUint(elements->at(i));
+        } else {
+          key = isolate_->factory()->Uint32ToString(elements->at(i));
+        }
+        result->set(index, *key);
+        index++;
+      }
+    }
+    // Add the property keys for this prototype level.
+    int num_properties = num_total - num_elements;
+    for (int i = 0; i < num_properties; i++) {
+      Object* key = properties_->KeyAt(properties_index);
+      result->set(index, key);
+      index++;
+      properties_index++;
+    }
   }

[Igor Sheludko, 2015/10/15 09:51:44]

DCHECK_EQ(index, length_);

   return result;
 }
 
 
-void KeyAccumulator::AddKey(Handle<Object> key, int check_limit) {
-#ifdef ENABLE_SLOW_DCHECKS
-  if (FLAG_enable_slow_asserts) {
-    DCHECK(key->IsNumber() || key->IsName());
-  }
-#endif
-  if (!set_.is_null()) {
-    set_ = OrderedHashSet::Add(set_, key);
-    length_ = set_->NumberOfElements();
-    return;
-  }
-  // check if we already have the key in the case we are still using
-  // the keys_ FixedArray
-  check_limit = Min(check_limit, length_);
-  for (int i = 0; i < check_limit; i++) {
-    Object* current = keys_->get(i);
-    if (current->KeyEquals(*key)) return;
-  }
-  EnsureCapacity(length_);
-  keys_->set(length_, *key);
+namespace {
+
+class FindKey {
+ public:
+  explicit FindKey(uint32_t key) : key_(key) {}
+  int operator()(uint32_t* entry) {
+    if (*entry == key_) return 0;
+    return *entry < key_ ? -1 : 1;
+  }
+
+ private:
+  uint32_t key_;
+};
+
+
+bool AccumulatorHasKey(List<uint32_t>* sub_elements, uint32_t key) {
+  int index = SortedListBSearch(*sub_elements, FindKey(key));
+  return index != -1;
+}
+
+}  // namespace
+
+
+bool KeyAccumulator::AddKey(uint32_t key) {
+  int lookup_limit = elements_.length();
+  for (int i = 0; i < lookup_limit; i++) {
+    if (AccumulatorHasKey(elements_[i], key)) return false;
+  }
+  elements_[lookup_limit - 1]->Add(key);
   length_++;
-}
-
-
-void KeyAccumulator::AddKeys(Handle<FixedArray> array, KeyFilter filter) {
+  levelLength_++;
+  return true;
+}
+
+
+bool KeyAccumulator::AddKey(Object* key, AddKeyConversion convert) {
+  return AddKey(handle(key, isolate_), convert);
+}
+
+
+bool KeyAccumulator::AddKey(Handle<Object> key, AddKeyConversion convert) {
+  if (filter_ == SKIP_SYMBOLS && key->IsSymbol()) {
+    return false;
+  }

[Igor Sheludko, 2015/10/15 09:51:43]

Just to be sure we are not trying to add to the proxy-level:
DCHECK_LE(0, levelLength_);

+  // In some cases (e.g. proxies) we might get in String-converted ints which
+  // should be added to the elements list instead of the properties. For
+  // proxies we have to convert as well but also respect the original order.
+  // Therefore we add a converted key to both sides
+  if (convert == CONVERT_TO_ARRAY_INDEX || convert == PROXY_MAGIC) {
+    uint32_t index = 0;
+    int prev_length = length_;
+    int prev_proto = levelLength_;
+    bool was_array_index = false;
+    bool key_was_added = false;
+    if ((key->IsString() && Handle<String>::cast(key)->AsArrayIndex(&index)) ||
+        key->ToArrayIndex(&index)) {
+      key_was_added = AddKey(index);
+      was_array_index = true;
+      if (convert == CONVERT_TO_ARRAY_INDEX) return key_was_added;
+    }
+    if (was_array_index && convert == PROXY_MAGIC) {
+      // If we had an array index (number) and it wasn't added, the key
+      // already existed before, hence we cannot add it to the properties
+      // keys as it would lead to duplicate entries.
+      if (!key_was_added) {
+        return false;
+      }
+      length_ = prev_length;
+      levelLength_ = prev_proto;
+    }
+  }
+  if (properties_.is_null()) {
+    properties_ = OrderedHashSet::Allocate(isolate_, 16);
+  }
+  // TODO(cbruni): remove this conversion once we throw the correct TypeError
+  // for non-string/symbol elements returned by proxies
+  if (convert == PROXY_MAGIC && key->IsNumber()) {
+    key = isolate_->factory()->NumberToString(key);
+  }
+  int prev_size = properties_->NumberOfElements();
+  properties_ = OrderedHashSet::Add(properties_, key);
+  if (prev_size < properties_->NumberOfElements()) {
+    length_++;
+    levelLength_++;
+  }
+  return true;
+}
+
+
+void KeyAccumulator::AddKeys(Handle<FixedArray> array,
+                             AddKeyConversion convert) {
   int add_length = array->length();
   if (add_length == 0) return;
-  if (keys_.is_null() && filter == INCLUDE_SYMBOLS) {
-    keys_ = array;
-    length_ = keys_->length();
-    return;
-  }
-  PrepareForComparisons(add_length);
-  int previous_key_count = length_;
   for (int i = 0; i < add_length; i++) {
     Handle<Object> current(array->get(i), isolate_);
-    if (filter == SKIP_SYMBOLS && current->IsSymbol()) continue;
-    AddKey(current, previous_key_count);
-  }
-}
-
-
-void KeyAccumulator::AddKeys(Handle<JSObject> array_like, KeyFilter filter) {
+    AddKey(current);
+  }
+}
+
+
+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, filter);
-}
-
-
-void KeyAccumulator::PrepareForComparisons(int count) {
-  // Depending on how many comparisons we do we should switch to the
-  // hash-table-based checks which have a one-time overhead for
-  // initializing but O(1) for HasKey checks.
-  if (!set_.is_null()) return;
-  // These limits were obtained through evaluation of several microbenchmarks.
-  if (length_ * count < 100) return;
-  // Don't use a set for few elements
-  if (length_ < 100 && count < 20) return;
-  set_ = OrderedHashSet::Allocate(isolate_, length_);
-  for (int i = 0; i < length_; i++) {
-    Handle<Object> value(keys_->get(i), isolate_);
-    set_ = OrderedHashSet::Add(set_, value);
-  }
-}
-
-
-void KeyAccumulator::EnsureCapacity(int capacity) {
-  if (keys_.is_null() || keys_->length() <= capacity) {
-    Grow();
-  }
-}
-
-
-void KeyAccumulator::Grow() {
-  // The OrderedHashSet handles growing by itself.
-  if (!set_.is_null()) return;
-  // Otherwise, grow the internal keys_ FixedArray
-  int capacity = keys_.is_null() ? 16 : keys_->length() * 2 + 16;
-  Handle<FixedArray> new_keys = isolate_->factory()->NewFixedArray(capacity);
-  if (keys_.is_null()) {
-    keys_ = new_keys;
-    return;
-  }
-  int buffer_length = keys_->length();
-  {
-    DisallowHeapAllocation no_gc;
-    WriteBarrierMode mode = new_keys->GetWriteBarrierMode(no_gc);
-    for (int i = 0; i < buffer_length; i++) {
-      new_keys->set(i, keys_->get(i), mode);
-    }
-  }
-  keys_ = new_keys;
-}
-
-
+  accessor->AddElementsToKeyAccumulator(array_like, this, convert);
+}
+
+
+void KeyAccumulator::AddKeysFromProxy(Handle<JSObject> array_like) {
+  // Proxies define a complete list of keys with no distinction of
+  // elements and properties, which breaks the normal assumption for the
+  // KeyAccumulator.
+  AddKeys(array_like, PROXY_MAGIC);
+  // Invert the current length to indicate a present proxy, so we can ignore
+  // element keys for this level. Otherwise we would not fully respect the order
+  // given by the proxy.
+  levelLength_ = -levelLength_;
+}
+
+
+namespace {
+
+// Used for sorting indices in a List<uint32_t>.
+int compareUInt32(const uint32_t* ap, const uint32_t* bp) {
+  uint32_t a = *ap;
+  uint32_t b = *bp;
+  return (a == b) ? 0 : (a < b) ? -1 : 1;
+}
+
+
+}  // namespace
+
+
+void KeyAccumulator::SortCurrentElementsList() {
+  if (elements_.length() == 0) return;
+  List<uint32_t>* element_keys = elements_[elements_.length() - 1];
+  element_keys->Sort(&compareUInt32);
+}
+
+
+void KeyAccumulator::NextPrototype() {
+  // Store the protoLength on the first call of this method.
+  if (!elements_.is_empty()) {
+    levelLengths_.Add(levelLength_);
+  }
+  elements_.Add(new List<uint32_t>());
+  levelLength_ = 0;
+}
+
+
 MaybeHandle<FixedArray> JSReceiver::GetKeys(Handle<JSReceiver> object,
                                             KeyCollectionType type,
                                             KeyFilter filter) {
   USE(ContainsOnlyValidKeys);
   Isolate* isolate = object->GetIsolate();
-  KeyAccumulator accumulator(isolate);
+  KeyAccumulator accumulator(isolate, filter);
   Handle<JSFunction> arguments_function(
       JSFunction::cast(isolate->sloppy_arguments_map()->GetConstructor()));
 
   PrototypeIterator::WhereToEnd end = type == OWN_ONLY
                                           ? PrototypeIterator::END_AT_NON_HIDDEN
                                           : PrototypeIterator::END_AT_NULL;
   // Only collect keys if access is permitted.
   for (PrototypeIterator iter(isolate, object,
                               PrototypeIterator::START_AT_RECEIVER);
        !iter.IsAtEnd(end); iter.Advance()) {
+    accumulator.NextPrototype();
     if (PrototypeIterator::GetCurrent(iter)->IsJSProxy()) {
       Handle<JSProxy> proxy = PrototypeIterator::GetCurrent<JSProxy>(iter);
       Handle<Object> args[] = { proxy };
       Handle<Object> names;
       ASSIGN_RETURN_ON_EXCEPTION(
           isolate, names,
           Execution::Call(isolate,
                           isolate->proxy_enumerate(),
                           object,
                           arraysize(args),
                           args),
           FixedArray);
-      accumulator.AddKeys(Handle<JSObject>::cast(names), filter);
+      accumulator.AddKeysFromProxy(Handle<JSObject>::cast(names));
       break;
     }
 
     Handle<JSObject> current = PrototypeIterator::GetCurrent<JSObject>(iter);
 
     // Check access rights if required.
     if (current->IsAccessCheckNeeded() &&
         !isolate->MayAccess(handle(isolate->context()), current)) {
       if (iter.IsAtEnd(PrototypeIterator::END_AT_NON_HIDDEN)) {
         isolate->ReportFailedAccessCheck(current);
         RETURN_EXCEPTION_IF_SCHEDULED_EXCEPTION(isolate, FixedArray);
       }
       break;
     }
 
-    // Compute the element keys.
-    Handle<FixedArray> element_keys =
-        isolate->factory()->NewFixedArray(current->NumberOfEnumElements());
-    current->GetEnumElementKeys(*element_keys);
-    accumulator.AddKeys(element_keys, filter);
-    DCHECK(ContainsOnlyValidKeys(accumulator.GetKeys()));
+    JSObject::CollectOwnElementKeys(current, &accumulator,
+                                    static_cast<PropertyAttributes>(DONT_ENUM));
 
     // Add the element keys from the interceptor.
     if (current->HasIndexedInterceptor()) {
       Handle<JSObject> result;
-      if (JSObject::GetKeysForIndexedInterceptor(
-              current, object).ToHandle(&result)) {
-        accumulator.AddKeys(result, filter);
+      if (JSObject::GetKeysForIndexedInterceptor(current, object)
+              .ToHandle(&result)) {
+        accumulator.AddKeys(result, CONVERT_TO_ARRAY_INDEX);
       }
-      DCHECK(ContainsOnlyValidKeys(accumulator.GetKeys()));
     }
 
     if (filter == SKIP_SYMBOLS) {
       // We can cache the computed property keys if access checks are
       // not needed and no interceptors are involved.
       //
       // We do not use the cache if the object has elements and
       // therefore it does not make sense to cache the property names
       // for arguments objects.  Arguments objects will always have
       // elements.
       // Wrapped strings have elements, but don't have an elements
       // array or dictionary.  So the fast inline test for whether to
       // use the cache says yes, so we should not create a cache.
       bool cache_enum_length =
           ((current->map()->GetConstructor() != *arguments_function) &&
            !current->IsJSValue() && !current->IsAccessCheckNeeded() &&
            !current->HasNamedInterceptor() &&
            !current->HasIndexedInterceptor());
       // Compute the property keys and cache them if possible.
-
       Handle<FixedArray> enum_keys =
           JSObject::GetEnumPropertyKeys(current, cache_enum_length);
-      accumulator.AddKeys(enum_keys, filter);
+      accumulator.AddKeys(enum_keys);
     } else {
       DCHECK(filter == INCLUDE_SYMBOLS);
       PropertyAttributes attr_filter =
           static_cast<PropertyAttributes>(DONT_ENUM | PRIVATE_SYMBOL);
-      Handle<FixedArray> property_keys = isolate->factory()->NewFixedArray(
-          current->NumberOfOwnProperties(attr_filter));
-      current->GetOwnPropertyNames(*property_keys, 0, attr_filter);
-      accumulator.AddKeys(property_keys, filter);
+      JSObject::CollectOwnElementKeys(current, &accumulator, attr_filter);
     }
-    DCHECK(ContainsOnlyValidKeys(accumulator.GetKeys()));
 
     // Add the property keys from the interceptor.
     if (current->HasNamedInterceptor()) {
       Handle<JSObject> result;
-      if (JSObject::GetKeysForNamedInterceptor(
-              current, object).ToHandle(&result)) {
-        accumulator.AddKeys(result, filter);
+      if (JSObject::GetKeysForNamedInterceptor(current, object)
+              .ToHandle(&result)) {
+        accumulator.AddKeys(result);
       }
-      DCHECK(ContainsOnlyValidKeys(accumulator.GetKeys()));
     }
   }
 
   Handle<FixedArray> keys = accumulator.GetKeys();
   DCHECK(ContainsOnlyValidKeys(keys));
   return keys;
 }
 
 
 bool Map::DictionaryElementsInPrototypeChainOnly() {
@@ skipping 6964 matching lines @@
   // Compute the number of enumerable elements.
   return GetOwnElementKeys(NULL, filter);
 }
 
 
 int JSObject::NumberOfEnumElements() {
   return NumberOfOwnElements(static_cast<PropertyAttributes>(DONT_ENUM));
 }
 
 
+namespace {
+
+// TODO(cbruni): unify with the version in builtins.cc
+void CollectElementIndices(Handle<JSObject> object, uint32_t range,
+                           KeyAccumulator* keys, PropertyAttributes filter,
+                           uint32_t offset) {
+  ElementsKind kind = object->GetElementsKind();
+  switch (kind) {
+    case FAST_SMI_ELEMENTS:
+    case FAST_ELEMENTS:
+    case FAST_HOLEY_SMI_ELEMENTS:
+    case FAST_HOLEY_ELEMENTS: {
+      Handle<FixedArray> elements(FixedArray::cast(object->elements()));
+      uint32_t length = static_cast<uint32_t>(elements->length());
+      if (range < length) length = range;
+      for (uint32_t i = offset; i < length; i++) {
+        if (!elements->get(i)->IsTheHole()) {
+          keys->AddKey(i);
+        }
+      }
+      break;
+    }
+    case FAST_HOLEY_DOUBLE_ELEMENTS:
+    case FAST_DOUBLE_ELEMENTS: {
+      if (object->elements()->IsFixedArray()) {
+        DCHECK(object->elements()->length() == 0);
+        return;
+      }
+      Handle<FixedDoubleArray> elements(
+          FixedDoubleArray::cast(object->elements()));
+      uint32_t length = static_cast<uint32_t>(elements->length());
+      if (range < length) length = range;
+      for (uint32_t i = offset; i < length; i++) {
+        if (!elements->is_the_hole(i)) {
+          keys->AddKey(i);
+        }
+      }
+      break;
+    }
+    case DICTIONARY_ELEMENTS: {
+      Handle<SeededNumberDictionary> dict(object->element_dictionary());
+      SeededNumberDictionary::CopyElementKeysTo(dict, keys, filter, offset);
+      keys->SortCurrentElementsList();
+      break;
+    }
+#define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) case TYPE##_ELEMENTS:
+
+      TYPED_ARRAYS(TYPED_ARRAY_CASE)
+#undef TYPED_ARRAY_CASE
+      {
+        uint32_t length = static_cast<uint32_t>(
+            FixedArrayBase::cast(object->elements())->length());
+        for (uint32_t i = offset; i < length; i++) {
+          keys->AddKey(i);
+        }
+        break;
+      }
+    case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
+    case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: {
+      ElementsAccessor* accessor = object->GetElementsAccessor();
+      uint32_t length = accessor->GetCapacity(*object, object->elements());

[Igor Sheludko, 2015/10/15 09:51:43]

I don't like exposing ElementsAccessor::GetCapacity(). It looks like the whole
CollectElementIndices() function should be another virtual method of 
ElementsAccessor's. WDYT?

[Camillo Bruni, 2015/10/16 09:38:02]

Indeed, I postponed it since I had so many other bugs to figure out ;). I'll
move it.

+      range = Min(range, length);
+      for (uint32_t i = offset; i < range; i++) {
+        // Check for filter
+        if (accessor->HasElement(object, i, filter)) {
+          keys->AddKey(i);
+        }
+      }
+      break;
+    }
+  }
+}
+
+}  // namespace
+
+void JSObject::CollectOwnElementKeys(Handle<JSObject> object,
+                                     KeyAccumulator* keys,
+                                     PropertyAttributes filter) {
+  uint32_t string_keys = 0;
+
+  // If this is a String wrapper, add the string indices first,
+  // as they're guaranteed to precede the elements in numerical order
+  // and ascending order is required by ECMA-262, 6th, 9.1.12.
+  if (object->IsJSValue()) {
+    Object* val = JSValue::cast(*object)->value();
+    if (val->IsString()) {
+      String* str = String::cast(val);
+      string_keys = str->length();
+      for (uint32_t i = 0; i < string_keys; i++) {
+        keys->AddKey(i);
+      }
+    }
+  }
+  CollectElementIndices(object, kMaxUInt32, keys, filter, string_keys);
+}
+
+
 int JSObject::GetOwnElementKeys(FixedArray* storage,
                                 PropertyAttributes filter) {
   int counter = 0;
 
   // If this is a String wrapper, add the string indices first,
-  // as they're guaranteed to preced the elements in numerical order
+  // as they're guaranteed to precede the elements in numerical order
   // and ascending order is required by ECMA-262, 6th, 9.1.12.
   if (IsJSValue()) {
     Object* val = JSValue::cast(this)->value();
     if (val->IsString()) {
       String* str = String::cast(val);
       if (storage) {
         for (int i = 0; i < str->length(); i++) {
           storage->set(counter + i, Smi::FromInt(i));
         }
       }
@@ skipping 104 matching lines @@
       }
       break;
     }
   }
 
   DCHECK(!storage || storage->length() == counter);
   return counter;
 }
 
 
-int JSObject::GetEnumElementKeys(FixedArray* storage) {
-  return GetOwnElementKeys(storage, static_cast<PropertyAttributes>(DONT_ENUM));
-}
-
-
 const char* Symbol::PrivateSymbolToName() const {
   Heap* heap = GetIsolate()->heap();
 #define SYMBOL_CHECK_AND_PRINT(name) \
   if (this == heap->name()) return #name;
   PRIVATE_SYMBOL_LIST(SYMBOL_CHECK_AND_PRINT)
 #undef SYMBOL_CHECK_AND_PRINT
   return "UNKNOWN";
 }
 
 
@@ skipping 1593 matching lines @@
     }
   }
   if (sort_mode == Dictionary::SORTED) {
     storage->SortPairs(storage, index);
   }
   DCHECK(storage->length() >= index);
   return index - start_index;
 }
 
 
+template <typename Derived, typename Shape, typename Key>
+void Dictionary<Derived, Shape, Key>::CopyElementKeysTo(
+    Handle<Derived> dictionary, KeyAccumulator* keys, PropertyAttributes filter,
+    uint32_t start) {
+  int capacity = dictionary->Capacity();
+  for (int i = 0; i < capacity; i++) {
+    Object* k = dictionary->KeyAt(i);
+    if (!dictionary->IsKey(k) || FilterKey(k, filter)) continue;
+    if (dictionary->IsDeleted(i)) continue;
+    DCHECK(k->IsNumber());
+    PropertyDetails details = dictionary->DetailsAt(i);
+    PropertyAttributes attr = details.attributes();
+    if ((attr & filter) != 0) continue;
+    uint32_t index = static_cast<uint32_t>(k->Number());
+    if (start <= index) {
+      keys->AddKey(index);
+    }
+  }
+}
+
+
 // Backwards lookup (slow).
 template<typename Derived, typename Shape, typename Key>
 Object* Dictionary<Derived, Shape, Key>::SlowReverseLookup(Object* value) {
   int capacity = this->Capacity();
   for (int i = 0; i < capacity; i++) {
     Object* k = this->KeyAt(i);
     if (this->IsKey(k)) {
       Object* e = this->ValueAt(i);
       // TODO(dcarney): this should be templatized.
       if (e->IsPropertyCell()) {
@@ skipping 1190 matching lines @@
   if (cell->value() != *new_value) {
     cell->set_value(*new_value);
     Isolate* isolate = cell->GetIsolate();
     cell->dependent_code()->DeoptimizeDependentCodeGroup(
         isolate, DependentCode::kPropertyCellChangedGroup);
   }
 }
 
 }  // namespace internal
 }  // namespace v8