[keys] Simplify KeyAccumulator

src/elements.cc

 // Copyright 2012 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/elements.h"
 
 #include "src/arguments.h"
 #include "src/conversions.h"
 #include "src/factory.h"
 #include "src/isolate-inl.h"
@@ skipping 427 matching lines @@
         isolate->builtins()->builtin(Builtins::kFunctionPrototypeApply);
     if (raw_frame->unchecked_code() == apply_builtin) {
       PrintF("apply from ");
       it.Advance();
       raw_frame = it.frame();
     }
   }
   JavaScriptFrame::PrintTop(isolate, stdout, false, true);
 }
 
+static void SortIndices(
+    Handle<FixedArray> indices, uint32_t sort_size,
+    WriteBarrierMode write_barrier_mode = UPDATE_WRITE_BARRIER) {
+  struct {
+    bool operator()(Object* a, Object* b) {
+      if (!a->IsUndefined()) {
+        if (b->IsUndefined()) return true;
+        return a->Number() < b->Number();
+      }
+      return b->IsUndefined();
+    }
+  } cmp;
+  Object** start =
+      reinterpret_cast<Object**>(indices->GetFirstElementAddress());
+  std::sort(start, start + sort_size, cmp);
+  if (write_barrier_mode != SKIP_WRITE_BARRIER) {
+    FIXED_ARRAY_ELEMENTS_WRITE_BARRIER(indices->GetIsolate()->heap(), *indices,
+                                       0, sort_size);
+  }
+}
 
 // Base class for element handler implementations. Contains the
 // the common logic for objects with different ElementsKinds.
 // Subclasses must specialize method for which the element
 // implementation differs from the base class implementation.
 //
 // This class is intended to be used in the following way:
 //
 //   class SomeElementsAccessor :
 //       public ElementsAccessorBase<SomeElementsAccessor,
@@ skipping 244 matching lines @@
     } else {
       // Check whether the backing store should be expanded.
       capacity = Max(length, JSObject::NewElementsCapacity(capacity));
       Subclass::GrowCapacityAndConvertImpl(array, capacity);
     }
 
     array->set_length(Smi::FromInt(length));
     JSObject::ValidateElements(array);
   }
 
-  static uint32_t GetIterationLength(JSObject* receiver,
-                                     FixedArrayBase* elements) {
+  static uint32_t GetMaxIndex(JSObject* receiver, FixedArrayBase* elements) {
     if (receiver->IsJSArray()) {
       DCHECK(JSArray::cast(receiver)->length()->IsSmi());
       return static_cast<uint32_t>(
           Smi::cast(JSArray::cast(receiver)->length())->value());
     }
     return Subclass::GetCapacityImpl(receiver, elements);
   }
 
+  static uint32_t GetMaxNumberOfEntries(JSObject* receiver,
+                                        FixedArrayBase* elements) {
+    return Subclass::GetMaxIndex(receiver, elements);
+  }
+
   static Handle<FixedArrayBase> ConvertElementsWithCapacity(
       Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
       ElementsKind from_kind, uint32_t capacity) {
     return ConvertElementsWithCapacity(
         object, old_elements, from_kind, capacity, 0, 0,
         ElementsAccessor::kCopyToEndAndInitializeToHole);
   }
 
   static Handle<FixedArrayBase> ConvertElementsWithCapacity(
       Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
@@ skipping 124 matching lines @@
     return Subclass::CollectValuesOrEntriesImpl(
         isolate, object, values_or_entries, get_entries, nof_items, filter);
   }
 
   static Maybe<bool> CollectValuesOrEntriesImpl(
       Isolate* isolate, Handle<JSObject> object,
       Handle<FixedArray> values_or_entries, bool get_entries, int* nof_items,
       PropertyFilter filter) {
     int count = 0;
     KeyAccumulator accumulator(isolate, OWN_ONLY, ALL_PROPERTIES);
-    accumulator.NextPrototype();
     Subclass::CollectElementIndicesImpl(
         object, handle(object->elements(), isolate), &accumulator);
     Handle<FixedArray> keys = accumulator.GetKeys();
 
     for (int i = 0; i < keys->length(); ++i) {
       Handle<Object> key(keys->get(i), isolate);
       Handle<Object> value;
       uint32_t index;
       if (!key->ToUint32(&index)) continue;
 
@@ skipping 25 matching lines @@
                              KeyAccumulator* keys) final {
     if (keys->filter() & ONLY_ALL_CAN_READ) return;
     Subclass::CollectElementIndicesImpl(object, backing_store, keys);
   }
 
   static void CollectElementIndicesImpl(Handle<JSObject> object,
                                         Handle<FixedArrayBase> backing_store,
                                         KeyAccumulator* keys) {
     DCHECK_NE(DICTIONARY_ELEMENTS, kind());
     // Non-dictionary elements can't have all-can-read accessors.
-    uint32_t length = GetIterationLength(*object, *backing_store);
+    uint32_t length = Subclass::GetMaxIndex(*object, *backing_store);
     PropertyFilter filter = keys->filter();
+    Factory* factory = keys->isolate()->factory();
     for (uint32_t i = 0; i < length; i++) {
       if (Subclass::HasElementImpl(object, i, backing_store, filter)) {
-        keys->AddKey(i);
+        keys->AddKey(factory->NewNumberFromUint(i));
       }
     }
   }
 
   static Handle<FixedArray> DirectCollectElementIndicesImpl(
       Isolate* isolate, Handle<JSObject> object,
       Handle<FixedArrayBase> backing_store, GetKeysConversion convert,
       PropertyFilter filter, Handle<FixedArray> list, uint32_t* nof_indices,
       uint32_t insertion_index = 0) {
-    uint32_t length = Subclass::GetIterationLength(*object, *backing_store);
+    uint32_t length = Subclass::GetMaxIndex(*object, *backing_store);
     for (uint32_t i = 0; i < length; i++) {
       if (Subclass::HasElementImpl(object, i, backing_store, filter)) {
         if (convert == CONVERT_TO_STRING) {
           Handle<String> index_string = isolate->factory()->Uint32ToString(i);
           list->set(insertion_index, *index_string);
         } else {
           list->set(insertion_index, Smi::FromInt(i), SKIP_WRITE_BARRIER);
         }
         insertion_index++;
       }
@@ skipping 24 matching lines @@
     // Collect the element indices into a new list.
     uint32_t nof_indices = 0;
     Handle<FixedArray> combined_keys =
         isolate->factory()->NewFixedArray(initial_list_length);
     combined_keys = Subclass::DirectCollectElementIndicesImpl(
         isolate, object, backing_store, convert, filter, combined_keys,
         &nof_indices);
 
     // Sort the indices list if necessary.
     if (IsDictionaryElementsKind(kind()) || IsSloppyArgumentsElements(kind())) {
-      struct {
-        bool operator()(Object* a, Object* b) {
-          if (!a->IsUndefined()) {
-            if (b->IsUndefined()) return true;
-            return a->Number() < b->Number();
-          }
-          return !b->IsUndefined();
-        }
-      } cmp;
-      Object** start =
-          reinterpret_cast<Object**>(combined_keys->GetFirstElementAddress());
-      std::sort(start, start + nof_indices, cmp);
+      SortIndices(combined_keys, nof_indices, SKIP_WRITE_BARRIER);
       uint32_t array_length = 0;
       // Indices from dictionary elements should only be converted after
       // sorting.
       if (convert == CONVERT_TO_STRING) {
         for (uint32_t i = 0; i < nof_indices; i++) {
           Handle<Object> index_string = isolate->factory()->Uint32ToString(
                   combined_keys->get(i)->Number());
           combined_keys->set(i, *index_string);
         }
       } else if (!(object->IsJSArray() &&
@@ skipping 44 matching lines @@
 
   static uint32_t GetEntryForIndexImpl(JSObject* holder,
                                        FixedArrayBase* backing_store,
                                        uint32_t index, PropertyFilter filter) {
     if (IsHoleyElementsKind(kind())) {
       return index < Subclass::GetCapacityImpl(holder, backing_store) &&
                      !BackingStore::cast(backing_store)->is_the_hole(index)
                  ? index
                  : kMaxUInt32;
     } else {
-      uint32_t length = GetIterationLength(holder, backing_store);
+      uint32_t length = Subclass::GetMaxIndex(holder, backing_store);
       return index < length ? index : kMaxUInt32;
     }
   }
 
   uint32_t GetEntryForIndex(JSObject* holder, FixedArrayBase* backing_store,
                             uint32_t index) final {
     return Subclass::GetEntryForIndexImpl(holder, backing_store, index,
                                           ALL_PROPERTIES);
   }
 
@@ skipping 16 matching lines @@
 
 
 class DictionaryElementsAccessor
     : public ElementsAccessorBase<DictionaryElementsAccessor,
                                   ElementsKindTraits<DICTIONARY_ELEMENTS> > {
  public:
   explicit DictionaryElementsAccessor(const char* name)
       : ElementsAccessorBase<DictionaryElementsAccessor,
                              ElementsKindTraits<DICTIONARY_ELEMENTS> >(name) {}
 
-  static uint32_t GetIterationLength(JSObject* receiver,
-                                     FixedArrayBase* elements) {
-    uint32_t length;
+  static uint32_t GetMaxIndex(JSObject* receiver, FixedArrayBase* elements) {
     if (receiver->IsJSArray()) {
-      // Special-case GetIterationLength for dictionary elements since the
-      // length of the array might be a HeapNumber.
-      JSArray::cast(receiver)->length()->ToArrayLength(&length);
-    } else {
-      length = GetCapacityImpl(receiver, elements);
+      DCHECK(JSArray::cast(receiver)->length()->IsSmi());

[Jakob Kummerow, 2016/05/24 13:19:58]

Nope! Dictionary arrays can have heap number lengths (see original
implementation of this function that you've ripped out).

+      return static_cast<uint32_t>(
+          Smi::cast(JSArray::cast(receiver)->length())->value());
     }
-    return length;
+    // We don't properly estimate the MaxIndex for dictionaries.
+    return kMaxUInt32;
+  }
+
+  static uint32_t GetMaxNumberOfEntries(JSObject* receiver,
+                                        FixedArrayBase* backing_store) {
+    SeededNumberDictionary* dict = SeededNumberDictionary::cast(backing_store);
+    return dict->NumberOfElements();
   }
 
   static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array,
                             uint32_t length,
                             Handle<FixedArrayBase> backing_store) {
     Handle<SeededNumberDictionary> dict =
         Handle<SeededNumberDictionary>::cast(backing_store);
     int capacity = dict->Capacity();
     uint32_t old_length = 0;
     CHECK(array->length()->ToArrayLength(&old_length));
@@ skipping 201 matching lines @@
     if (raw_key == undefined || raw_key == the_hole) {
       return kMaxUInt32;
     }
     return FilterKey(dictionary, entry, raw_key, filter);
   }
 
   static void CollectElementIndicesImpl(Handle<JSObject> object,
                                         Handle<FixedArrayBase> backing_store,
                                         KeyAccumulator* keys) {
     if (keys->filter() & SKIP_STRINGS) return;
-    Isolate* isolate = keys->isolate();
-    Handle<Object> undefined = isolate->factory()->undefined_value();
-    Handle<Object> the_hole = isolate->factory()->the_hole_value();
+    Factory* factory = keys->isolate()->factory();
+    Handle<Object> undefined = factory->undefined_value();
+    Handle<Object> the_hole = factory->the_hole_value();
     Handle<SeededNumberDictionary> dictionary =
         Handle<SeededNumberDictionary>::cast(backing_store);
     int capacity = dictionary->Capacity();
+    Handle<FixedArray> elements =
+        factory->NewFixedArray(GetMaxNumberOfEntries(*object, *backing_store));
+    int insertion_index = 0;
     PropertyFilter filter = keys->filter();
     for (int i = 0; i < capacity; i++) {
       uint32_t key =
           GetKeyForEntryImpl(dictionary, i, filter, *undefined, *the_hole);
       if (key == kMaxUInt32) continue;
-      keys->AddKey(key);
+      elements->set(insertion_index, *factory->NewNumberFromUint(key));
+      insertion_index++;
     }
-
-    keys->SortCurrentElementsList();
+    SortIndices(elements, insertion_index);
+    for (int i = 0; i < insertion_index; i++) {
+      keys->AddKey(elements->get(i));
+    }
   }
 
   static Handle<FixedArray> DirectCollectElementIndicesImpl(
       Isolate* isolate, Handle<JSObject> object,
       Handle<FixedArrayBase> backing_store, GetKeysConversion convert,
       PropertyFilter filter, Handle<FixedArray> list, uint32_t* nof_indices,
       uint32_t insertion_index = 0) {
     if (filter & SKIP_STRINGS) return list;
     if (filter & ONLY_ALL_CAN_READ) return list;
 
@@ skipping 204 matching lines @@
   }
 
   static bool HasEntryImpl(FixedArrayBase* backing_store, uint32_t entry) {
     return !BackingStore::cast(backing_store)->is_the_hole(entry);
   }
 
   static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver,
                                               KeyAccumulator* accumulator,
                                               AddKeyConversion convert) {
     Handle<FixedArrayBase> elements(receiver->elements(),
-                                    receiver->GetIsolate());
-    uint32_t length = Subclass::GetIterationLength(*receiver, *elements);
+                                    accumulator->isolate());
+    uint32_t length = Subclass::GetMaxNumberOfEntries(*receiver, *elements);
     for (uint32_t i = 0; i < length; i++) {
       if (IsFastPackedElementsKind(KindTraits::Kind) ||
           HasEntryImpl(*elements, i)) {
         accumulator->AddKey(Subclass::GetImpl(*elements, i), convert);
       }
     }
   }
 
   static void ValidateContents(Handle<JSObject> holder, int length) {
 #if DEBUG
@@ skipping 812 matching lines @@
       // would enable GC of the context.
       parameter_map->set_the_hole(entry + 2);
     } else {
       Subclass::DeleteFromArguments(obj, entry - length);
     }
   }
 
   static void CollectElementIndicesImpl(Handle<JSObject> object,
                                         Handle<FixedArrayBase> backing_store,
                                         KeyAccumulator* keys) {
-    FixedArray* parameter_map = FixedArray::cast(*backing_store);
-    uint32_t length = parameter_map->length() - 2;
-    for (uint32_t i = 0; i < length; ++i) {
-      if (!parameter_map->get(i + 2)->IsTheHole()) {
-        keys->AddKey(i);
-      }
-    }
-
-    Handle<FixedArrayBase> store(FixedArrayBase::cast(parameter_map->get(1)));
-    ArgumentsAccessor::CollectElementIndicesImpl(object, store, keys);
-    if (Subclass::kind() == FAST_SLOPPY_ARGUMENTS_ELEMENTS) {
-      keys->SortCurrentElementsList();
+    Isolate* isolate = keys->isolate();
+    uint32_t nof_indices = 0;
+    Handle<FixedArray> indices = isolate->factory()->NewFixedArray(
+        GetCapacityImpl(*object, *backing_store));
+    DirectCollectElementIndicesImpl(isolate, object, backing_store,
+                                    KEEP_NUMBERS, ENUMERABLE_STRINGS, indices,
+                                    &nof_indices);
+    SortIndices(indices, nof_indices);
+    for (uint32_t i = 0; i < nof_indices; i++) {
+      keys->AddKey(indices->get(i));
     }
   }
 
   static Handle<FixedArray> DirectCollectElementIndicesImpl(
       Isolate* isolate, Handle<JSObject> object,
       Handle<FixedArrayBase> backing_store, GetKeysConversion convert,
       PropertyFilter filter, Handle<FixedArray> list, uint32_t* nof_indices,
       uint32_t insertion_index = 0) {
     FixedArray* parameter_map = FixedArray::cast(*backing_store);
     uint32_t length = parameter_map->length() - 2;
@@ skipping 327 matching lines @@
           convert);
     }
     BackingStoreAccessor::AddElementsToKeyAccumulatorImpl(receiver, accumulator,
                                                           convert);
   }
 
   static void CollectElementIndicesImpl(Handle<JSObject> object,
                                         Handle<FixedArrayBase> backing_store,
                                         KeyAccumulator* keys) {
     uint32_t length = GetString(*object)->length();
+    Factory* factory = keys->isolate()->factory();
     for (uint32_t i = 0; i < length; i++) {
-      keys->AddKey(i);
+      keys->AddKey(factory->NewNumberFromUint(i));
     }
     BackingStoreAccessor::CollectElementIndicesImpl(object, backing_store,
                                                     keys);
   }
 
   static void GrowCapacityAndConvertImpl(Handle<JSObject> object,
                                          uint32_t capacity) {
     Handle<FixedArrayBase> old_elements(object->elements());
     ElementsKind from_kind = object->GetElementsKind();
     // This method should only be called if there's a reason to update the
@@ skipping 264 matching lines @@
     insertion_index += len;
   }
 
   DCHECK_EQ(insertion_index, result_len);
   return result_array;
 }
 
 ElementsAccessor** ElementsAccessor::elements_accessors_ = NULL;
 }  // namespace internal
 }  // namespace v8