Refactor UnionOfKeys into ElementsAccessor

src/elements.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 19 matching lines @@
 #include "objects.h"
 #include "elements.h"
 
 namespace v8 {
 namespace internal {
 
 
 ElementsAccessor** ElementsAccessor::elements_accessors_;
 
 
+bool HasKey(FixedArray* array, Object* key) {
+  int len0 = array->length();
+  for (int i = 0; i < len0; i++) {
+    Object* element = array->get(i);
+    if (element->IsSmi() && key->IsSmi() && (element == key)) return true;

[Kevin Millikin (Chromium), 2011/08/09 14:46:55]

If you feel like it, you could write

if (element->IsSmi() && (element == key)) ...

[danno, 2011/08/09 16:38:40]

Done.

+    if (element->IsString() &&
+        key->IsString() && String::cast(element)->Equals(String::cast(key))) {
+      return true;
+    }
+  }
+  return false;
+}
+
+
 // 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,
 //                                   BackingStoreClass> {
@@ skipping 16 matching lines @@
           ElementsAccessorSubclass::GetBackingStore(obj);
       return backing_store->get(index);
     }
     return obj->GetHeap()->the_hole_value();
   }
 
   virtual MaybeObject* Delete(JSObject* obj,
                               uint32_t index,
                               JSReceiver::DeleteMode mode) = 0;
 
+  virtual MaybeObject* AddJSArrayKeysToFixedArray(JSArray* other,
+                                                  FixedArray* keys) {
+    int len0 = keys->length();
+#ifdef DEBUG
+    if (FLAG_enable_slow_asserts) {
+      for (int i = 0; i < len0; i++) {
+        ASSERT(keys->get(i)->IsString() || keys->get(i)->IsNumber());
+      }
+    }
+#endif
+    int len1 = ElementsAccessorSubclass::GetCapacity(other);
+
+    // Optimize if 'other' is empty.
+    // We cannot optimize if 'this' is empty, as other may have holes
+    // or non keys.
+    if (len1 == 0) return keys;
+
+    // Compute how many elements are not in this.

[Kevin Millikin (Chromium), 2011/08/09 14:46:55]

"not in other".

[danno, 2011/08/09 16:38:40]

Done.

+    int extra = 0;
+    for (int y = 0; y < len1; y++) {
+      Object* value;
+      MaybeObject* maybe_value =
+          ElementsAccessorSubclass::GetElementAtCapacityIndex(other, y);
+      if (!maybe_value->ToObject(&value)) return maybe_value;
+      if (!value->IsTheHole() && !HasKey(keys, value)) extra++;
+    }
+
+    if (extra == 0) return keys;
+
+    // Allocate the result
+    Object* obj;

[Kevin Millikin (Chromium), 2011/08/09 14:46:55]

There's a template member function on MaybeObject that you can use here,
avoiding writing out the cast and the extra variable 'obj':

FixedArray* result;
MaybeObject* maybe_obj =
    other->GetHeap()->AllocateFixedArray(len0 + extra);
if (!maybe_obj->To<FixedArray>(&result)) return maybe_obj;

[danno, 2011/08/09 16:38:40]

Done.

+    { MaybeObject* maybe_obj =
+          other->GetHeap()->AllocateFixedArray(len0 + extra);
+      if (!maybe_obj->ToObject(&obj)) return maybe_obj;
+    }
+    // Fill in the content
+    FixedArray* result = FixedArray::cast(obj);
+    {
+      AssertNoAllocation no_gc;
+      WriteBarrierMode mode = result->GetWriteBarrierMode(no_gc);
+      for (int i = 0; i < len0; i++) {
+        Object* e = keys->get(i);
+        ASSERT(e->IsString() || e->IsNumber());
+        result->set(i, e, mode);
+      }
+    }
+    // Fill in the extra keys.
+    int index = 0;
+    for (int y = 0; y < len1; y++) {
+      MaybeObject* maybe_value =
+          ElementsAccessorSubclass::GetElementAtCapacityIndex(other, y);
+      Object* value;
+      if (!maybe_value->ToObject(&value)) return maybe_value;
+      if (!value->IsTheHole() && !HasKey(keys, value)) {
+        ASSERT(value->IsString() || value->IsNumber());
+        result->set(len0 + index, value);
+        index++;
+      }
+    }
+    ASSERT(extra == index);
+    return result;
+  }
+
+  static uint32_t GetCapacity(JSObject* obj) {
+    return ElementsAccessorSubclass::GetBackingStore(obj)->length();
+  }
+
+  static MaybeObject* GetElementAtCapacityIndex(JSObject* obj,
+                                                      int index) {

[Kevin Millikin (Chromium), 2011/08/09 14:46:55]

Indentation is off here.

[danno, 2011/08/09 16:38:40]

Done.

+    BackingStoreClass* backing_store =
+        ElementsAccessorSubclass::GetBackingStore(obj);
+    return backing_store->get(index);
+  }
+
  protected:
   static BackingStoreClass* GetBackingStore(JSObject* obj) {
     return BackingStoreClass::cast(obj->elements());
   }
 
   static uint32_t GetLength(JSObject* obj) {
     return ElementsAccessorSubclass::GetBackingStore(obj)->length();
   }
 
  private:
@@ skipping 232 matching lines @@
   }
 
   virtual MaybeObject* GetWithReceiver(JSObject* obj,
                                        Object* receiver,
                                        uint32_t index) {
     return GetNumberDictionaryElement(obj,
                                       receiver,
                                       obj->element_dictionary(),
                                       index);
   }
+
+  static uint32_t GetCapacity(JSObject* obj) {
+    return obj->element_dictionary()->Capacity();
+  }
+
+  static MaybeObject* GetElementAtCapacityIndex(JSObject* obj,
+                                                      int index) {

[Kevin Millikin (Chromium), 2011/08/09 14:46:55]

Indentation is off here.

[danno, 2011/08/09 16:38:40]

Done.

+    NumberDictionary* dict = obj->element_dictionary();
+    if (dict->IsKey(dict->KeyAt(index))) {
+      return dict->ValueAt(index);
+    } else {
+      return obj->GetHeap()->the_hole_value();
+    }
+  }
 };
 
 
 class NonStrictArgumentsElementsAccessor
     : public ElementsAccessorBase<NonStrictArgumentsElementsAccessor,
                                   FixedArray> {
  public:
   virtual MaybeObject* GetWithReceiver(JSObject* obj,
                                        Object* receiver,
                                        uint32_t index) {
@@ skipping 37 matching lines @@
     } else {
       FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
       if (arguments->IsDictionary()) {
         return DictionaryElementsAccessor::DeleteCommon(obj, index, mode);
       } else {
         return FastElementsAccessor::DeleteCommon(obj, index);
       }
     }
     return obj->GetHeap()->true_value();
   }
+
+  static uint32_t GetCapacity(JSObject* obj) {
+    // TODO(danno): Return max of parameter map length or backing store
+    // capacity.
+    return 0;
+  }
+
+  static MaybeObject* GetElementAtCapacityIndex(JSObject* obj, int index) {
+    // TODO(danno): Return either value from parameter map of backing
+    // store value at index.
+    return obj->GetHeap()->the_hole_value();
+  }
 };
 
 
 void ElementsAccessor::InitializeOncePerProcess() {
   static struct ConcreteElementsAccessors {
     FastElementsAccessor fast_elements_handler;
     FastDoubleElementsAccessor fast_double_elements_handler;
     DictionaryElementsAccessor dictionary_elements_handler;
     NonStrictArgumentsElementsAccessor non_strict_arguments_elements_handler;
     ExternalByteElementsAccessor byte_elements_handler;
@@ skipping 21 matching lines @@
     &element_accessors.float_elements_handler,
     &element_accessors.double_elements_handler,
     &element_accessors.pixel_elements_handler
   };
 
   elements_accessors_ = accessor_array;
 }
 
 
 } }  // namespace v8::internal