[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 7484 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 (uint32_t i = 0; i < elements_.size(); i++) {

[Igor Sheludko, 2015/10/22 21:42:57]

I guess it should be size_t or you will have compilation issues on 64-bit.

[Camillo Bruni, 2015/10/23 08:56:35]

right

     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 (uint32_t level = 0; level < levelLengths_.size(); level++) {

[Igor Sheludko, 2015/10/22 21:42:57]

Ditto.

     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 (uint32_t i = 1; i < elements_.size(); i++) {

[Igor Sheludko, 2015/10/22 21:42:57]

Ditto.

+    if (AccumulatorHasKey(elements_[i - 1], key)) return false;
   }
-  elements_[lookup_limit - 1]->Add(key);
+  if (elementKeysAddCheckLimit_ == INCLUDE_CURRENT_LEVEL) {
+    // the last level may have not been sorted yet, hence we have to do
+    // a linear search here if required.
+    auto last_level = elements_.back();
+    if (std::find(last_level->begin(), last_level->end(), key) !=
+        last_level->end()) {
+      return false;
+    }
+  }
+  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::AddKeysFromInterceptor(Handle<JSObject> array_like) {
+  // The accumulator might introduce duplicates for the current level,
+  // hence we set INCLUDE_CURRENT_LEVEL

[Igor Sheludko, 2015/10/22 21:42:57]

DCHECK_EQ(EXCLUDE_CURRENT_LEVEL, elementKeysAddCheckLimit_);
or maybe save the old value to return to.

+  elementKeysAddCheckLimit_ = INCLUDE_CURRENT_LEVEL;

[Igor Sheludko, 2015/10/22 21:42:57]

WDYT about adding all the elements without checking for duplicates in the last
level, then sort the last level and erase consecutive duplicates instead of
doing linear search each time?
  std::sort(last_level.begin(), last_level.end());
  last_level.erase(std::unique(last_level.begin(), last_level.end()),
last_level.end());
  and adjust the lengths according to the number of elements deleted.

[Camillo Bruni, 2015/10/26 09:53:48]

ah right, makes sense :)

+  AddKeys(array_like, CONVERT_TO_ARRAY_INDEX);
+  elementKeysAddCheckLimit_ = EXCLUDE_CURRENT_LEVEL;
 }
 
 
-}  // namespace
-
-
 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;
+  std::vector<uint32_t>* 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();
@@ skipping 38 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.AddKeysFromInterceptor(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 10031 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