[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,
+                        bool emit_write_barrier = true) {

[Jakob Kummerow, 2016/05/23 16:25:21]

Consider using the existing enum WriteBarrierMode instead of a bool.

[Camillo Bruni, 2016/05/23 19:10:13]

updated.

+  struct {
+    bool operator()(Object* a, Object* b) {
+      if (!a->IsUndefined()) {
+        if (b->IsUndefined()) return true;
+        return a->Number() < b->Number();
+      }
+      return !b->IsUndefined();

[Jakob Kummerow, 2016/05/23 16:25:21]

I'm pretty sure this condition is inverted, i.e. you want s/!//.

[Camillo Bruni, 2016/05/23 19:10:13]

good catch!
you're right, if b is smaller than a return false.

+    }
+  } cmp;
+  Object** start =
+      reinterpret_cast<Object**>(indices->GetFirstElementAddress());
+  std::sort(start, start + sort_size, cmp);
+  if (emit_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 398 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 27 matching lines @@
     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);
     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);
@@ skipping 34 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, false);
       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 82 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;
-    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);
-    }
-    return length;
+                                     FixedArrayBase* backing_store) {
+    SeededNumberDictionary* dict = SeededNumberDictionary::cast(backing_store);
+    return dict->NumberOfElements();

[Jakob Kummerow, 2016/05/23 16:25:21]

In existing code, GetIterationLength is clearly expected to return the array
length, not the number of actually existing elements, and in the superclass
implementation in line 731ff this is still the case. Having an identically named
overridden method with different semantics seems dangerous.
Maybe "GetIterationLength" is just a too ambiguous name, and we should have
"GetArrayLength" and "GetCapacity"/"GetNumberOfElements" instead?
Or just inline it?

[Camillo Bruni, 2016/05/23 19:10:13]

Renamed to GetMaxNumberOfElements, though the rest of the code stays the same.
In all the cases where we could get a dictionary we do the indirection via
Get/HasEntry which makes this method work in both cases.

   }
 
   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(GetIterationLength(*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 1038 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