[runtime] use std::vector in 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>
 
@@ skipping 7507 matching lines @@
       return Handle<FixedArray>(isolate->heap()->empty_fixed_array());
     }
     Handle<FixedArray> storage = isolate->factory()->NewFixedArray(length);
     dictionary->CopyEnumKeysTo(*storage);
     return storage;
   }
 }
 
 
 KeyAccumulator::~KeyAccumulator() {
-  for (int i = 0; i < elements_.length(); i++) {
+  for (size_t i = 0; i < elements_.size(); i++) {
     delete elements_[i];
   }
 }
 
 
 Handle<FixedArray> KeyAccumulator::GetKeys(GetKeysConversion convert) {
   if (length_ == 0) {
     return isolate_->factory()->empty_fixed_array();
   }
   // 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_);
   int index = 0;
   int properties_index = 0;
-  for (int level = 0; level < levelLengths_.length(); level++) {
+  for (size_t level = 0; level < levelLengths_.size(); 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 proxies
       // define the complete ordering.
       num_total = -num_total;
-    } else if (level < elements_.length()) {
-      List<uint32_t>* elements = elements_[level];
-      num_elements = elements->length();
+    } else if (level < elements_.size()) {
+      std::vector<uint32_t>* elements = elements_[level];
+      num_elements = static_cast<int>(elements->size());
       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++;
     }
   }
+
   DCHECK_EQ(index, length_);
   return result;
 }
 
 
 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;
+bool AccumulatorHasKey(std::vector<uint32_t>* sub_elements, uint32_t key) {
+  return std::binary_search(sub_elements->begin(), sub_elements->end(), key);
 }
 
 }  // namespace
 
 
 bool KeyAccumulator::AddKey(uint32_t key) {
   // Make sure we do not add keys to a proxy-level (see AddKeysFromProxy).
+  // We mark proxy-levels with a negative length
   DCHECK_LE(0, levelLength_);
-  int lookup_limit = elements_.length();
-  for (int i = 0; i < lookup_limit; i++) {
-    if (AccumulatorHasKey(elements_[i], key)) return false;
+  // Binary search over all but the last level. The last one might not be
+  // sorted yet.
+  for (size_t i = 1; i < elements_.size(); i++) {
+    if (AccumulatorHasKey(elements_[i - 1], key)) return false;
   }
-  elements_[lookup_limit - 1]->Add(key);
+  elements_.back()->push_back(key);
   length_++;
   levelLength_++;
   return true;
 }
 
 
 bool KeyAccumulator::AddKey(Object* key, AddKeyConversion convert) {
   return AddKey(handle(key, isolate_), convert);
 }
 
@@ skipping 73 matching lines @@
   // 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;
+void KeyAccumulator::AddElementKeysFromInterceptor(
+    Handle<JSObject> array_like) {
+  AddKeys(array_like, CONVERT_TO_ARRAY_INDEX);
+  SortRemoveDuplicates();
 }
 
 
-}  // namespace
+void KeyAccumulator::SortRemoveDuplicates() {
+  // The accumulator might introduce duplicates for the current level, since
+  // these keys get added after the object's element keys.
+  auto last_level = elements_.back();
+  size_t nof_removed_keys = last_level->size();
+  std::sort(last_level->begin(), last_level->end());
+  last_level->erase(std::unique(last_level->begin(), last_level->end()),
+                    last_level->end());
+  // Adjust total length / level length by the number of removed duplicates
+  nof_removed_keys -= last_level->size();
+  levelLength_ -= static_cast<int>(nof_removed_keys);
+  length_ -= static_cast<int>(nof_removed_keys);
+}
 
 
 void KeyAccumulator::SortCurrentElementsList() {
-  if (elements_.length() == 0) return;
-  List<uint32_t>* element_keys = elements_[elements_.length() - 1];
-  element_keys->Sort(&compareUInt32);
+  if (elements_.empty()) return;
+  auto element_keys = elements_.back();
+  std::sort(element_keys->begin(), element_keys->end());
 }
 
 
 void KeyAccumulator::NextPrototype() {
   // Store the protoLength on the first call of this method.
-  if (!elements_.is_empty()) {
-    levelLengths_.Add(levelLength_);
+  if (!elements_.empty()) {
+    levelLengths_.push_back(levelLength_);
   }
-  elements_.Add(new List<uint32_t>());
+  elements_.push_back(new std::vector<uint32_t>());
   levelLength_ = 0;
 }
 
 
 MaybeHandle<FixedArray> JSReceiver::GetKeys(Handle<JSReceiver> object,
                                             KeyCollectionType type,
                                             KeyFilter filter,
                                             GetKeysConversion getConversion) {
   USE(ContainsOnlyValidKeys);
   Isolate* isolate = object->GetIsolate();
   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);
@@ skipping 24 matching lines @@
     }
 
     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, CONVERT_TO_ARRAY_INDEX);
+        accumulator.AddElementKeysFromInterceptor(result);
       }
     }
 
     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
@@ skipping 10043 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