[runtime] Fancify 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/messages.h"
@@ skipping 500 matching lines @@
                         uint32_t end) final {
     return ElementsAccessorSubclass::IsPackedImpl(holder, backing_store, start,
                                                   end);
   }
 
   static bool IsPackedImpl(Handle<JSObject> holder,
                            Handle<FixedArrayBase> backing_store, uint32_t start,
                            uint32_t end) {
     if (IsFastPackedElementsKind(kind())) return true;
     for (uint32_t i = start; i < end; i++) {
-      if (!ElementsAccessorSubclass::HasElementImpl(holder, i, backing_store)) {
+      if (!ElementsAccessorSubclass::HasElementImpl(holder, i, backing_store,
+                                                    NONE)) {
         return false;
       }
     }
     return true;
   }
 
   static void TryTransitionResultArrayToPacked(Handle<JSArray> array) {
     if (!IsHoleyElementsKind(kind())) return;
     int length = Smi::cast(array->length())->value();
     Handle<FixedArrayBase> backing_store(array->elements());
     if (!ElementsAccessorSubclass::IsPackedImpl(array, backing_store, 0,
                                                 length)) {
       return;
     }
     ElementsKind packed_kind = GetPackedElementsKind(kind());
     Handle<Map> new_map =
         JSObject::GetElementsTransitionMap(array, packed_kind);
     JSObject::MigrateToMap(array, new_map);
     if (FLAG_trace_elements_transitions) {
       JSObject::PrintElementsTransition(stdout, array, kind(), backing_store,
                                         packed_kind, backing_store);
     }
   }
 
   virtual bool HasElement(Handle<JSObject> holder, uint32_t index,
-                          Handle<FixedArrayBase> backing_store) final {
+                          Handle<FixedArrayBase> backing_store,
+                          PropertyAttributes filter) final {
     return ElementsAccessorSubclass::HasElementImpl(holder, index,
-                                                    backing_store);
+                                                    backing_store, filter);
   }
 
   static bool HasElementImpl(Handle<JSObject> holder, uint32_t index,
-                             Handle<FixedArrayBase> backing_store) {
+                             Handle<FixedArrayBase> backing_store,
+                             PropertyAttributes filter) {
     return ElementsAccessorSubclass::GetEntryForIndexImpl(
-               *holder, *backing_store, index) != kMaxUInt32;
+               *holder, *backing_store, index, filter) != kMaxUInt32;
   }
 
   virtual Handle<Object> Get(Handle<FixedArrayBase> backing_store,
                              uint32_t entry) final {
     return ElementsAccessorSubclass::GetImpl(backing_store, entry);
   }
 
   static Handle<Object> GetImpl(Handle<FixedArrayBase> backing_store,
                                 uint32_t entry) {
     uint32_t index = GetIndexForEntryImpl(*backing_store, entry);
@@ skipping 295 matching lines @@
     // intentionally to avoid ArrayConcat() builtin performance degradation.
     //
     // Details: The idea is that allocations actually happen only in case of
     // copying from object with fast double elements to object with object
     // elements. In all the other cases there are no allocations performed and
     // handle creation causes noticeable performance degradation of the builtin.
     ElementsAccessorSubclass::CopyElementsImpl(
         from, from_start, *to, from_kind, to_start, packed_size, copy_size);
   }
 
+  static void CollectElementIndicesImpl(Handle<JSObject> object,
+                                        Handle<FixedArrayBase> backing_store,
+                                        KeyAccumulator* keys, uint32_t range,
+                                        PropertyAttributes filter,
+                                        uint32_t offset) {
+    uint32_t length = 0;
+    if (object->IsJSArray()) {
+      length = Smi::cast(JSArray::cast(*object)->length())->value();
+    } else {
+      length =
+          ElementsAccessorSubclass::GetCapacityImpl(*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;
+      keys->AddKey(i);
+    }
+  }
+
+  virtual void CollectElementIndices(Handle<JSObject> object,
+                                     Handle<FixedArrayBase> backing_store,
+                                     KeyAccumulator* keys, uint32_t range,
+                                     PropertyAttributes filter,
+                                     uint32_t offset) final {
+    ElementsAccessorSubclass::CollectElementIndicesImpl(
+        object, backing_store, keys, range, filter, offset);
+  };
+
   virtual void AddElementsToKeyAccumulator(Handle<JSObject> receiver,
                                            KeyAccumulator* accumulator,
-                                           KeyFilter filter) final {
+                                           AddKeyConversion convert) final {
     Handle<FixedArrayBase> from(receiver->elements());
     uint32_t add_length =
         ElementsAccessorSubclass::GetCapacityImpl(*receiver, *from);
     if (add_length == 0) return;
-    accumulator->PrepareForComparisons(add_length);
-    int prev_key_count = accumulator->GetLength();
+
     for (uint32_t i = 0; i < add_length; i++) {
       if (!ElementsAccessorSubclass::HasEntryImpl(*from, i)) continue;
       Handle<Object> value = ElementsAccessorSubclass::GetImpl(from, i);
       DCHECK(!value->IsTheHole());
       DCHECK(!value->IsAccessorPair());
       DCHECK(!value->IsExecutableAccessorInfo());
-      if (filter == SKIP_SYMBOLS && value->IsSymbol()) {
-        continue;
-      }
-      accumulator->AddKey(value, prev_key_count);
+      accumulator->AddKey(value, convert);
     }
   }
 
   static uint32_t GetCapacityImpl(JSObject* holder,
                                   FixedArrayBase* backing_store) {
     return backing_store->length();
   }
 
-  uint32_t GetCapacity(JSObject* holder, FixedArrayBase* backing_store) final {
+  virtual uint32_t GetCapacity(JSObject* holder,
+                               FixedArrayBase* backing_store) final {
     return ElementsAccessorSubclass::GetCapacityImpl(holder, backing_store);
   }
 
   static bool HasEntryImpl(FixedArrayBase* backing_store, uint32_t entry) {
     return true;
   }
 
   static uint32_t GetIndexForEntryImpl(FixedArrayBase* backing_store,
                                        uint32_t entry) {
     return entry;
   }
 
   static uint32_t GetEntryForIndexImpl(JSObject* holder,
                                        FixedArrayBase* backing_store,
-                                       uint32_t index) {
+                                       uint32_t index,
+                                       PropertyAttributes filter) {
     if (IsHoleyElementsKind(kind())) {
       return index < ElementsAccessorSubclass::GetCapacityImpl(holder,
                                                                backing_store) &&
                      !BackingStore::cast(backing_store)->is_the_hole(index)
                  ? index
                  : kMaxUInt32;
     } else {
       Smi* smi_length = Smi::cast(JSArray::cast(holder)->length());
       uint32_t length = static_cast<uint32_t>(smi_length->value());
       return index < length ? index : kMaxUInt32;
     }
   }
 
   virtual uint32_t GetEntryForIndex(JSObject* holder,
                                     FixedArrayBase* backing_store,
                                     uint32_t index) final {
     return ElementsAccessorSubclass::GetEntryForIndexImpl(holder, backing_store,
-                                                          index);
+                                                          index, NONE);
   }
 
   static PropertyDetails GetDetailsImpl(FixedArrayBase* backing_store,
                                         uint32_t entry) {
     return PropertyDetails(NONE, DATA, 0, PropertyCellType::kNoCell);
   }
 
   virtual PropertyDetails GetDetails(FixedArrayBase* backing_store,
                                      uint32_t entry) final {
     return ElementsAccessorSubclass::GetDetailsImpl(backing_store, entry);
@@ skipping 141 matching lines @@
 
   static uint32_t GetIndexForEntryImpl(FixedArrayBase* store, uint32_t entry) {
     DisallowHeapAllocation no_gc;
     SeededNumberDictionary* dict = SeededNumberDictionary::cast(store);
     uint32_t result = 0;
     CHECK(dict->KeyAt(entry)->ToArrayIndex(&result));
     return result;
   }
 
   static uint32_t GetEntryForIndexImpl(JSObject* holder, FixedArrayBase* store,
-                                       uint32_t index) {
+                                       uint32_t index,
+                                       PropertyAttributes filter) {
     DisallowHeapAllocation no_gc;
-    SeededNumberDictionary* dict = SeededNumberDictionary::cast(store);
-    int entry = dict->FindEntry(index);
-    return entry == SeededNumberDictionary::kNotFound
-               ? kMaxUInt32
-               : static_cast<uint32_t>(entry);
+    SeededNumberDictionary* dictionary = SeededNumberDictionary::cast(store);
+    int entry = dictionary->FindEntry(index);
+    if (entry == SeededNumberDictionary::kNotFound) return kMaxUInt32;
+    if (filter != NONE) {
+      PropertyDetails details = dictionary->DetailsAt(entry);
+      PropertyAttributes attr = details.attributes();
+      if ((attr & filter) != 0) return kMaxUInt32;
+    }
+    return static_cast<uint32_t>(entry);
   }
 
   static PropertyDetails GetDetailsImpl(FixedArrayBase* backing_store,
                                         uint32_t entry) {
     return SeededNumberDictionary::cast(backing_store)->DetailsAt(entry);
   }
+
+  static void CollectElementIndicesImpl(Handle<JSObject> object,
+                                        Handle<FixedArrayBase> backing_store,
+                                        KeyAccumulator* keys, uint32_t range,
+                                        PropertyAttributes filter,
+                                        uint32_t offset) {
+    Handle<SeededNumberDictionary> dictionary =
+        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);
+      PropertyAttributes attr = details.attributes();
+      if ((attr & filter) != 0) continue;
+      keys->AddKey(index);
+    }
+
+    keys->SortCurrentElementsList();
+  }
 };
 
 
 // Super class for all fast element arrays.
 template<typename FastElementsAccessorSubclass,
          typename KindTraits>
 class FastElementsAccessor
     : public ElementsAccessorBase<FastElementsAccessorSubclass, KindTraits> {
  public:
   explicit FastElementsAccessor(const char* name)
@@ skipping 636 matching lines @@
     UNREACHABLE();
   }
 
   static uint32_t GetIndexForEntryImpl(FixedArrayBase* backing_store,
                                        uint32_t entry) {
     return entry;
   }
 
   static uint32_t GetEntryForIndexImpl(JSObject* holder,
                                        FixedArrayBase* backing_store,
-                                       uint32_t index) {
+                                       uint32_t index,
+                                       PropertyAttributes filter) {
     return index < AccessorClass::GetCapacityImpl(holder, backing_store)
                ? index
                : kMaxUInt32;
   }
 
   static uint32_t GetCapacityImpl(JSObject* holder,
                                   FixedArrayBase* backing_store) {
     JSArrayBufferView* view = JSArrayBufferView::cast(holder);
     if (view->WasNeutered()) return 0;
     return backing_store->length();
@@ skipping 113 matching lines @@
     FixedArray* parameter_map = FixedArray::cast(parameters);
     uint32_t length = parameter_map->length() - 2;
     if (entry < length) return entry;
 
     FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
     return ArgumentsAccessor::GetIndexForEntryImpl(arguments, entry - length);
   }
 
   static uint32_t GetEntryForIndexImpl(JSObject* holder,
                                        FixedArrayBase* parameters,
-                                       uint32_t index) {
+                                       uint32_t index,
+                                       PropertyAttributes filter) {
     FixedArray* parameter_map = FixedArray::cast(parameters);
     Object* probe = GetParameterMapArg(parameter_map, index);
     if (!probe->IsTheHole()) return index;
 
     FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
-    uint32_t entry =
-        ArgumentsAccessor::GetEntryForIndexImpl(holder, arguments, index);
+    uint32_t entry = ArgumentsAccessor::GetEntryForIndexImpl(holder, arguments,
+                                                             index, filter);
     if (entry == kMaxUInt32) return entry;
     return (parameter_map->length() - 2) + entry;
   }
 
   static PropertyDetails GetDetailsImpl(FixedArrayBase* parameters,
                                         uint32_t entry) {
     FixedArray* parameter_map = FixedArray::cast(parameters);
     uint32_t length = parameter_map->length() - 2;
     if (entry < length) {
       return PropertyDetails(NONE, DATA, 0, PropertyCellType::kNoCell);
@@ skipping 412 matching lines @@
     }
   }
 
   DCHECK(j == result_len);
   return result_array;
 }
 
 ElementsAccessor** ElementsAccessor::elements_accessors_ = NULL;
 }  // namespace internal
 }  // namespace v8