[key-accumulator] Starting to reimplement the key-accumulator

src/elements.cc

Index: src/elements.cc
diff --git a/src/elements.cc b/src/elements.cc
index e6d3f84f9ce8eec80bec76695220f6ff392c2787..409fc9cf9194a57c41b32b3aef474c3ea4b2d735 100644
--- a/src/elements.cc
+++ b/src/elements.cc
@@ -428,6 +428,14 @@ static void CopyDictionaryToDoubleElements(FixedArrayBase* from_base,
   }
 }
 
+Handle<FixedArray> EnsureSize(Isolate* isolate, Handle<FixedArray> array,
+                              int size) {
+  int length = array->length();
+  if (size < length) return array;
+  int new_capacity = length + length / 2;
+  int grow_by = new_capacity - length;
+  return isolate->factory()->CopyFixedArrayAndGrow(array, grow_by);
+}
 
 static void TraceTopFrame(Isolate* isolate) {
   StackFrameIterator it(isolate);
@@ -727,6 +735,16 @@ class ElementsAccessorBase : public ElementsAccessor {
     JSObject::ValidateElements(array);
   }
 
+  static uint32_t GetIterationLength(JSObject* receiver,
+                                     FixedArrayBase* elements) {
+    if (receiver->IsJSArray()) {
+      return static_cast<uint32_t>(
+          Smi::cast(JSArray::cast(receiver)->length())->value());
+    } else {
+      return ElementsAccessorSubclass::GetCapacityImpl(receiver, elements);
+    }
+  }
+
   static Handle<FixedArrayBase> ConvertElementsWithCapacity(
       Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
       ElementsKind from_kind, uint32_t capacity) {
@@ -843,6 +861,14 @@ class ElementsAccessorBase : public ElementsAccessor {
         from, from_start, *to, from_kind, to_start, packed_size, copy_size);
   }
 
+  void CollectElementIndices(Handle<JSObject> object,
+                             Handle<FixedArrayBase> backing_store,
+                             KeyAccumulator* keys, uint32_t range,
+                             PropertyFilter filter, uint32_t offset) final {
+    ElementsAccessorSubclass::CollectElementIndicesImpl(
+        object, backing_store, keys, range, filter, offset);
+  }
+
   static void CollectElementIndicesImpl(Handle<JSObject> object,
                                         Handle<FixedArrayBase> backing_store,
                                         KeyAccumulator* keys, uint32_t range,
@@ -853,30 +879,115 @@ class ElementsAccessorBase : public ElementsAccessor {
       // Non-dictionary elements can't have all-can-read accessors.
       return;
     }
-    uint32_t length = 0;
-    if (object->IsJSArray()) {
-      length = Smi::cast(JSArray::cast(*object)->length())->value();
-    } else {
-      length =
-          ElementsAccessorSubclass::GetCapacityImpl(*object, *backing_store);
-    }
+    uint32_t length = GetIterationLength(*object, *backing_store);
     if (range < length) length = range;
     for (uint32_t i = offset; i < length; i++) {
-      if (!ElementsAccessorSubclass::HasElementImpl(object, i, backing_store,
-                                                    filter)) {
-        continue;
+      if (ElementsAccessorSubclass::HasElementImpl(object, i, backing_store,
+                                                   filter)) {
+        keys->AddKey(i);
       }
-      keys->AddKey(i);
     }
   }
 
-  void CollectElementIndices(Handle<JSObject> object,
-                             Handle<FixedArrayBase> backing_store,
-                             KeyAccumulator* keys, uint32_t range,
-                             PropertyFilter filter, uint32_t offset) final {
-    ElementsAccessorSubclass::CollectElementIndicesImpl(
-        object, backing_store, keys, range, filter, offset);
-  };
+  static Handle<FixedArray> FastCollectElementIndicesImpl(
+      Isolate* isolate, Handle<JSObject> object,
+      Handle<FixedArrayBase> backing_store, GetKeysConversion convert,
+      PropertyFilter filter, Handle<FixedArray> list, int* nof_indices) {
+    uint32_t length =
+        ElementsAccessorSubclass::GetIterationLength(*object, *backing_store);
+    int insertion_index = 0;
+    for (uint32_t i = 0; i < length; i++) {
+      if (IsFastPackedElementsKind(kind())) {

[Toon Verwaest, 2016/02/24 15:07:06]

HasElementImpl should just return true for packed kind(). Similarly, EnsureSize
should be a noop for packed kind(). In that case you don't need to duplicate the
branches.

+        if (convert == CONVERT_TO_STRING) {
+          list->set(insertion_index++, *isolate->factory()->Uint32ToString(i));
+        } else {
+          list->set(insertion_index++, Smi::FromInt(i), SKIP_WRITE_BARRIER);
+        }
+      } else {
+        if (ElementsAccessorSubclass::HasElementImpl(object, i, backing_store,
+                                                     filter)) {
+          list = EnsureSize(isolate, list, insertion_index);
+          if (convert == CONVERT_TO_STRING) {
+            list->set(insertion_index++,
+                      *isolate->factory()->Uint32ToString(i));
+          } else {
+            list->set(insertion_index++, Smi::FromInt(i), SKIP_WRITE_BARRIER);
+          }
+        }
+      }
+    }
+    *nof_indices = insertion_index;
+    return list;
+  }
+
+  Handle<FixedArray> PrependElementIndices(Handle<JSObject> object,
+                                           Handle<FixedArrayBase> backing_store,
+                                           Handle<FixedArray> keys,
+                                           GetKeysConversion convert,
+                                           PropertyFilter filter) final {
+    return ElementsAccessorSubclass::PrependElementIndicesImpl(
+        object, backing_store, keys, convert, filter);
+  }
+
+  Handle<FixedArray> PrependElementIndicesImpl(
+      Handle<JSObject> object, Handle<FixedArrayBase> backing_store,
+      Handle<FixedArray> keys, GetKeysConversion convert,
+      PropertyFilter filter) {
+    if (!IsDictionaryElementsKind(kind()) && filter & ONLY_ALL_CAN_READ) {

[Toon Verwaest, 2016/02/24 15:07:06]

There are no ALL_CAN_READ indexed properties that aren't handled by an
all-can-read indexed interceptor. We should probably add a (D)CHECK to the API
that this never happens, rather than implement support here. Those properties
are only relevant for browsers and browser-like settings; and in chrome we don't
use it.

+      // Non-dictionary elements can't have all-can-read accessors.
+      return keys;
+    }
+
+    Isolate* isolate = object->GetIsolate();
+    int nof_property_keys = keys->length();
+
+    // Calculate the initial list size depending on the object at hand.
+    int initial_list_length = 10;

[Toon Verwaest, 2016/02/24 15:07:06]

Why not immediately use Capacity + nof_property_keys, and then always trim
later? I doubt you'll be able to avoid much memory allocation in practice; you
probably just make it worse by using a list + expanding.

+    if (IsFastPackedElementsKind(kind())) {
+      initial_list_length =
+          ElementsAccessorSubclass::GetCapacityImpl(*object, *backing_store);
+      initial_list_length += nof_property_keys;
+    }
+
+    // Collect the element indices into a new list.
+    int nof_indices = 0;
+    Handle<FixedArray> combined_keys =
+        isolate->factory()->NewFixedArray(initial_list_length);
+    combined_keys = ElementsAccessorSubclass::FastCollectElementIndicesImpl(
+        isolate, object, backing_store, convert, filter, combined_keys,
+        &nof_indices);
+
+    // Sort the indices list if necessary.
+    if (kind() == DICTIONARY_ELEMENTS) {
+      struct {
+        bool operator()(Object* a, Object* b) {

[Toon Verwaest, 2016/02/24 15:07:06]

return a->Number()  < b->Number()? Seems like double-encoded indices aren't
going to be sorted otherwise ...

+          if (a->IsSmi()) {
+            if (!b->IsSmi()) return true;
+            return Smi::cast(a)->value() < Smi::cast(b)->value();
+          }
+          return !b->IsSmi();
+        }
+      } cmp;
+      Object** start =
+          reinterpret_cast<Object**>(combined_keys->GetFirstElementAddress());
+      std::sort(start, start + nof_indices, cmp);
+    }
+
+    // Shrink/Grow the combined_keys to the final size.
+    int final_size = nof_indices + nof_property_keys;
+    if (combined_keys->length() < final_size) {
+      combined_keys = isolate->factory()->CopyFixedArrayAndGrow(
+          combined_keys, final_size - combined_keys->length());
+    } else {
+      combined_keys->Shrink(final_size);
+    }
+
+    // Copy over the property keys.
+    ElementsKind kind = FAST_HOLEY_ELEMENTS;

[Toon Verwaest, 2016/02/24 15:07:06]

I guess it doesn't change anything, but this should be FAST_ELEMENTS right?

+    CopyObjectToObjectElements(*keys, kind, 0, *combined_keys, kind,
+                               nof_indices, nof_property_keys);
+    return combined_keys;
+  }
 
   void AddElementsToKeyAccumulator(Handle<JSObject> receiver,
                                    KeyAccumulator* accumulator,
@@ -909,12 +1020,7 @@ class ElementsAccessorBase : public ElementsAccessor {
                  ? index
                  : kMaxUInt32;
     } else {
-      uint32_t length =
-          holder->IsJSArray()
-              ? static_cast<uint32_t>(
-                    Smi::cast(JSArray::cast(holder)->length())->value())
-              : ElementsAccessorSubclass::GetCapacityImpl(holder,
-                                                          backing_store);
+      uint32_t length = GetIterationLength(holder, backing_store);
       return index < length ? index : kMaxUInt32;
     }
   }
@@ -1116,6 +1222,27 @@ class DictionaryElementsAccessor
     return SeededNumberDictionary::cast(backing_store)->DetailsAt(entry);
   }
 
+  static uint32_t GetKeyForEntryImpl(Handle<SeededNumberDictionary> dictionary,
+                                     int entry, PropertyFilter filter) {
+    Object* raw_key = dictionary->KeyAt(entry);
+    if (!dictionary->IsKey(raw_key)) return kMaxUInt32;
+    if (raw_key->FilterKey(filter)) return kMaxUInt32;
+    if (dictionary->IsDeleted(entry)) return kMaxUInt32;
+    DCHECK(raw_key->IsNumber());
+    DCHECK_LE(raw_key->Number(), kMaxUInt32);
+    uint32_t key = static_cast<uint32_t>(raw_key->Number());
+    PropertyDetails details = dictionary->DetailsAt(entry);
+    if (filter & ONLY_ALL_CAN_READ) {
+      if (details.kind() != kAccessor) return kMaxUInt32;
+      Object* accessors = dictionary->ValueAt(entry);
+      if (!accessors->IsAccessorInfo()) return kMaxUInt32;
+      if (!AccessorInfo::cast(accessors)->all_can_read()) return kMaxUInt32;
+    }
+    PropertyAttributes attr = details.attributes();
+    if ((attr & filter) != 0) return kMaxUInt32;
+    return key;
+  }
+
   static void CollectElementIndicesImpl(Handle<JSObject> object,
                                         Handle<FixedArrayBase> backing_store,
                                         KeyAccumulator* keys, uint32_t range,
@@ -1125,29 +1252,37 @@ class DictionaryElementsAccessor
         Handle<SeededNumberDictionary>::cast(backing_store);
     int capacity = dictionary->Capacity();
     for (int i = 0; i < capacity; i++) {
-      Object* k = dictionary->KeyAt(i);
-      if (!dictionary->IsKey(k)) continue;
-      if (k->FilterKey(filter)) continue;
-      if (dictionary->IsDeleted(i)) continue;
-      DCHECK(k->IsNumber());
-      DCHECK_LE(k->Number(), kMaxUInt32);
-      uint32_t index = static_cast<uint32_t>(k->Number());
-      if (index < offset) continue;
-      PropertyDetails details = dictionary->DetailsAt(i);
-      if (filter & ONLY_ALL_CAN_READ) {
-        if (details.kind() != kAccessor) continue;
-        Object* accessors = dictionary->ValueAt(i);
-        if (!accessors->IsAccessorInfo()) continue;
-        if (!AccessorInfo::cast(accessors)->all_can_read()) continue;
-      }
-      PropertyAttributes attr = details.attributes();
-      if ((attr & filter) != 0) continue;
-      keys->AddKey(index);
+      uint32_t key = GetKeyForEntryImpl(dictionary, i, filter);
+      if (key == kMaxUInt32) continue;
+      keys->AddKey(key);
     }
 
     keys->SortCurrentElementsList();
   }
 
+  static Handle<FixedArray> FastCollectElementIndicesImpl(
+      Isolate* isolate, Handle<JSObject> object,
+      Handle<FixedArrayBase> backing_store, GetKeysConversion convert,
+      PropertyFilter filter, Handle<FixedArray> list, int* nof_indices) {
+    Handle<SeededNumberDictionary> dictionary =
+        Handle<SeededNumberDictionary>::cast(backing_store);
+
+    int capacity = dictionary->Capacity();
+    int insertion_index = 0;
+    for (uint32_t i = 0; i < capacity; i++) {
+      uint32_t key = GetKeyForEntryImpl(dictionary, i, filter);
+      if (key == kMaxUInt32) continue;
+      list = EnsureSize(isolate, list, insertion_index);
+      if (convert == CONVERT_TO_STRING) {
+        list->set(insertion_index++, *isolate->factory()->Uint32ToString(key));
+      } else {
+        list->set(insertion_index++, Smi::FromInt(key), SKIP_WRITE_BARRIER);
+      }
+    }
+    *nof_indices = insertion_index;
+    return list;
+  }
+
   static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver,
                                               KeyAccumulator* accumulator,
                                               AddKeyConversion convert) {
@@ -1312,15 +1447,10 @@ class FastElementsAccessor
   static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver,
                                               KeyAccumulator* accumulator,
                                               AddKeyConversion convert) {
-    uint32_t length = 0;
     Handle<FixedArrayBase> elements(receiver->elements(),
                                     receiver->GetIsolate());
-    if (receiver->IsJSArray()) {
-      length = Smi::cast(JSArray::cast(*receiver)->length())->value();
-    } else {
-      length =
-          FastElementsAccessorSubclass::GetCapacityImpl(*receiver, *elements);
-    }
+    uint32_t length =
+        FastElementsAccessorSubclass::GetIterationLength(*receiver, *elements);
     for (uint32_t i = 0; i < length; i++) {
       if (IsFastPackedElementsKind(KindTraits::Kind) ||
           HasEntryImpl(*elements, i)) {