NewGC: Merge bleeding edge up to 9009.

src/elements.cc

Index: src/elements.cc
===================================================================
--- src/elements.cc	(revision 9006)
+++ src/elements.cc	(working copy)
@@ -29,6 +29,7 @@
 
 #include "objects.h"
 #include "elements.h"
+#include "utils.h"
 
 namespace v8 {
 namespace internal {
@@ -37,6 +38,20 @@
 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() && element == key) return true;
+    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
@@ -56,32 +71,152 @@
 // specialization of SomeElementsAccessor methods).
 template <typename ElementsAccessorSubclass, typename BackingStoreClass>
 class ElementsAccessorBase : public ElementsAccessor {
- public:
+ protected:
   ElementsAccessorBase() { }
-  virtual MaybeObject* GetWithReceiver(JSObject* obj,
-                                       Object* receiver,
-                                       uint32_t index) {
-    if (index < ElementsAccessorSubclass::GetLength(obj)) {
-      BackingStoreClass* backing_store =
-          ElementsAccessorSubclass::GetBackingStore(obj);
-      return backing_store->get(index);
+  virtual MaybeObject* Get(FixedArrayBase* backing_store,
+                           uint32_t key,
+                           JSObject* obj,
+                           Object* receiver) {
+    return ElementsAccessorSubclass::Get(
+        BackingStoreClass::cast(backing_store), key, obj, receiver);
+  }
+
+  static MaybeObject* Get(BackingStoreClass* backing_store,
+                          uint32_t key,
+                          JSObject* obj,
+                          Object* receiver) {
+    if (key < ElementsAccessorSubclass::GetCapacity(backing_store)) {
+      return backing_store->get(key);
     }
-    return obj->GetHeap()->the_hole_value();
+    return backing_store->GetHeap()->the_hole_value();
   }
 
   virtual MaybeObject* Delete(JSObject* obj,
-                              uint32_t index,
+                              uint32_t key,
                               JSReceiver::DeleteMode mode) = 0;
 
+  virtual MaybeObject* AddElementsToFixedArray(FixedArrayBase* from,
+                                               FixedArray* to,
+                                               JSObject* holder,
+                                               Object* receiver) {
+    int len0 = to->length();
+#ifdef DEBUG
+    if (FLAG_enable_slow_asserts) {
+      for (int i = 0; i < len0; i++) {
+        ASSERT(!to->get(i)->IsTheHole());
+      }
+    }
+#endif
+    BackingStoreClass* backing_store = BackingStoreClass::cast(from);
+    uint32_t len1 = ElementsAccessorSubclass::GetCapacity(backing_store);
+
+    // Optimize if 'other' is empty.
+    // We cannot optimize if 'this' is empty, as other may have holes.
+    if (len1 == 0) return to;
+
+    // Compute how many elements are not in other.
+    int extra = 0;
+    for (uint32_t y = 0; y < len1; y++) {
+      if (ElementsAccessorSubclass::HasElementAtIndex(backing_store,
+                                                      y,
+                                                      holder,
+                                                      receiver)) {
+        uint32_t key =
+            ElementsAccessorSubclass::GetKeyForIndex(backing_store, y);
+        MaybeObject* maybe_value =
+            ElementsAccessorSubclass::Get(backing_store, key, holder, receiver);
+        Object* value;
+        if (!maybe_value->ToObject(&value)) return maybe_value;
+        ASSERT(!value->IsTheHole());
+        if (!HasKey(to, value)) {
+          extra++;
+        }
+      }
+    }
+
+    if (extra == 0) return to;
+
+    // Allocate the result
+    FixedArray* result;
+    MaybeObject* maybe_obj =
+        backing_store->GetHeap()->AllocateFixedArray(len0 + extra);
+    if (!maybe_obj->To<FixedArray>(&result)) return maybe_obj;
+
+    // Fill in the content
+    {
+      AssertNoAllocation no_gc;
+      WriteBarrierMode mode = result->GetWriteBarrierMode(no_gc);
+      for (int i = 0; i < len0; i++) {
+        Object* e = to->get(i);
+        ASSERT(e->IsString() || e->IsNumber());
+        result->set(i, e, mode);
+      }
+    }
+    // Fill in the extra values.
+    int index = 0;
+    for (uint32_t y = 0; y < len1; y++) {
+      if (ElementsAccessorSubclass::HasElementAtIndex(backing_store,
+                                                      y,
+                                                      holder,
+                                                      receiver)) {
+        uint32_t key =
+            ElementsAccessorSubclass::GetKeyForIndex(backing_store, y);
+        MaybeObject* maybe_value =
+            ElementsAccessorSubclass::Get(backing_store, key, holder, receiver);
+        Object* value;
+        if (!maybe_value->ToObject(&value)) return maybe_value;
+        if (!value->IsTheHole() && !HasKey(to, value)) {
+          result->set(len0 + index, value);
+          index++;
+        }
+      }
+    }
+    ASSERT(extra == index);
+    return result;
+  }
+
  protected:
-  static BackingStoreClass* GetBackingStore(JSObject* obj) {
-    return BackingStoreClass::cast(obj->elements());
+  static uint32_t GetCapacity(BackingStoreClass* backing_store) {
+    return backing_store->length();
   }
 
-  static uint32_t GetLength(JSObject* obj) {
-    return ElementsAccessorSubclass::GetBackingStore(obj)->length();
+  virtual uint32_t GetCapacity(FixedArrayBase* backing_store) {
+    return ElementsAccessorSubclass::GetCapacity(
+        BackingStoreClass::cast(backing_store));
   }
 
+  static bool HasElementAtIndex(BackingStoreClass* backing_store,
+                                uint32_t index,
+                                JSObject* holder,
+                                Object* receiver) {
+    uint32_t key =
+        ElementsAccessorSubclass::GetKeyForIndex(backing_store, index);
+    MaybeObject* element = ElementsAccessorSubclass::Get(backing_store,
+                                                         key,
+                                                         holder,
+                                                         receiver);
+    return !element->IsTheHole();
+  }
+
+  virtual bool HasElementAtIndex(FixedArrayBase* backing_store,
+                                 uint32_t index,
+                                 JSObject* holder,
+                                 Object* receiver) {
+    return ElementsAccessorSubclass::HasElementAtIndex(
+        BackingStoreClass::cast(backing_store), index, holder, receiver);
+  }
+
+  static uint32_t GetKeyForIndex(BackingStoreClass* backing_store,
+                                 uint32_t index) {
+    return index;
+  }
+
+  virtual uint32_t GetKeyForIndex(FixedArrayBase* backing_store,
+                                              uint32_t index) {
+    return ElementsAccessorSubclass::GetKeyForIndex(
+        BackingStoreClass::cast(backing_store), index);
+  }
+
  private:
   DISALLOW_COPY_AND_ASSIGN(ElementsAccessorBase);
 };
@@ -91,7 +226,7 @@
     : public ElementsAccessorBase<FastElementsAccessor, FixedArray> {
  public:
   static MaybeObject* DeleteCommon(JSObject* obj,
-                                   uint32_t index) {
+                                   uint32_t key) {
     ASSERT(obj->HasFastElements() || obj->HasFastArgumentsElements());
     Heap* heap = obj->GetHeap();
     FixedArray* backing_store = FixedArray::cast(obj->elements());
@@ -107,8 +242,8 @@
         obj->IsJSArray()
         ? Smi::cast(JSArray::cast(obj)->length())->value()
         : backing_store->length());
-    if (index < length) {
-      backing_store->set_the_hole(index);
+    if (key < length) {
+      backing_store->set_the_hole(key);
       // If an old space backing store is larger than a certain size and
       // has too few used values, normalize it.
       // To avoid doing the check on every delete we require at least
@@ -117,8 +252,8 @@
       const int kMinLengthForSparsenessCheck = 64;
       if (backing_store->length() >= kMinLengthForSparsenessCheck &&
           !heap->InNewSpace(backing_store) &&
-          ((index > 0 && backing_store->get(index - 1) == hole) ||
-           (index + 1 < length && backing_store->get(index + 1) == hole))) {
+          ((key > 0 && backing_store->get(key - 1) == hole) ||
+           (key + 1 < length && backing_store->get(key + 1) == hole))) {
         int num_used = 0;
         for (int i = 0; i < backing_store->length(); ++i) {
           if (backing_store->get(i) != hole) ++num_used;
@@ -134,10 +269,11 @@
     return heap->true_value();
   }
 
+ protected:
   virtual MaybeObject* Delete(JSObject* obj,
-                              uint32_t index,
+                              uint32_t key,
                               JSReceiver::DeleteMode mode) {
-    return DeleteCommon(obj, index);
+    return DeleteCommon(obj, key);
   }
 };
 
@@ -145,17 +281,28 @@
 class FastDoubleElementsAccessor
     : public ElementsAccessorBase<FastDoubleElementsAccessor,
                                   FixedDoubleArray> {
+ protected:
+  friend class ElementsAccessorBase<FastDoubleElementsAccessor,
+                                    FixedDoubleArray>;
+
   virtual MaybeObject* Delete(JSObject* obj,
-                              uint32_t index,
+                              uint32_t key,
                               JSReceiver::DeleteMode mode) {
     int length = obj->IsJSArray()
         ? Smi::cast(JSArray::cast(obj)->length())->value()
         : FixedDoubleArray::cast(obj->elements())->length();
-    if (index < static_cast<uint32_t>(length)) {
-      FixedDoubleArray::cast(obj->elements())->set_the_hole(index);
+    if (key < static_cast<uint32_t>(length)) {
+      FixedDoubleArray::cast(obj->elements())->set_the_hole(key);
     }
     return obj->GetHeap()->true_value();
   }
+
+  static bool HasElementAtIndex(FixedDoubleArray* backing_store,
+                                uint32_t index,
+                                JSObject* holder,
+                                Object* receiver) {
+    return !backing_store->is_the_hole(index);
+  }
 };
 
 
@@ -165,21 +312,23 @@
 class ExternalElementsAccessor
     : public ElementsAccessorBase<ExternalElementsAccessorSubclass,
                                   ExternalArray> {
- public:
-  virtual MaybeObject* GetWithReceiver(JSObject* obj,
-                                       Object* receiver,
-                                       uint32_t index) {
-    if (index < ExternalElementsAccessorSubclass::GetLength(obj)) {
-      ExternalArray* backing_store =
-          ExternalElementsAccessorSubclass::GetBackingStore(obj);
-      return backing_store->get(index);
+ protected:
+  friend class ElementsAccessorBase<ExternalElementsAccessorSubclass,
+                                    ExternalArray>;
+
+  static MaybeObject* Get(ExternalArray* backing_store,
+                          uint32_t key,
+                          JSObject* obj,
+                          Object* receiver) {
+    if (key < ExternalElementsAccessorSubclass::GetCapacity(backing_store)) {
+      return backing_store->get(key);
     } else {
-      return obj->GetHeap()->undefined_value();
+      return backing_store->GetHeap()->undefined_value();
     }
   }
 
   virtual MaybeObject* Delete(JSObject* obj,
-                              uint32_t index,
+                              uint32_t key,
                               JSReceiver::DeleteMode mode) {
     // External arrays always ignore deletes.
     return obj->GetHeap()->true_value();
@@ -245,30 +394,8 @@
     : public ElementsAccessorBase<DictionaryElementsAccessor,
                                   NumberDictionary> {
  public:
-  static MaybeObject* GetNumberDictionaryElement(
-      JSObject* obj,
-      Object* receiver,
-      NumberDictionary* backing_store,
-      uint32_t index) {
-    int entry = backing_store->FindEntry(index);
-    if (entry != NumberDictionary::kNotFound) {
-      Object* element = backing_store->ValueAt(entry);
-      PropertyDetails details = backing_store->DetailsAt(entry);
-      if (details.type() == CALLBACKS) {
-        return obj->GetElementWithCallback(receiver,
-                                           element,
-                                           index,
-                                           obj);
-      } else {
-        return element;
-      }
-    }
-    return obj->GetHeap()->the_hole_value();
-  }
-
-
   static MaybeObject* DeleteCommon(JSObject* obj,
-                                   uint32_t index,
+                                   uint32_t key,
                                    JSReceiver::DeleteMode mode) {
     Isolate* isolate = obj->GetIsolate();
     Heap* heap = isolate->heap();
@@ -279,11 +406,11 @@
       backing_store = FixedArray::cast(backing_store->get(1));
     }
     NumberDictionary* dictionary = NumberDictionary::cast(backing_store);
-    int entry = dictionary->FindEntry(index);
+    int entry = dictionary->FindEntry(key);
     if (entry != NumberDictionary::kNotFound) {
       Object* result = dictionary->DeleteProperty(entry, mode);
       if (result == heap->true_value()) {
-        MaybeObject* maybe_elements = dictionary->Shrink(index);
+        MaybeObject* maybe_elements = dictionary->Shrink(key);
         FixedArray* new_elements = NULL;
         if (!maybe_elements->To(&new_elements)) {
           return maybe_elements;
@@ -300,7 +427,7 @@
         // throws an exception.
         HandleScope scope(isolate);
         Handle<Object> holder(obj);
-        Handle<Object> name = isolate->factory()->NewNumberFromUint(index);
+        Handle<Object> name = isolate->factory()->NewNumberFromUint(key);
         Handle<Object> args[2] = { name, holder };
         Handle<Object> error =
             isolate->factory()->NewTypeError("strict_delete_property",
@@ -311,35 +438,57 @@
     return heap->true_value();
   }
 
+ protected:
+  friend class ElementsAccessorBase<DictionaryElementsAccessor,
+                                    NumberDictionary>;
+
   virtual MaybeObject* Delete(JSObject* obj,
-                              uint32_t index,
+                              uint32_t key,
                               JSReceiver::DeleteMode mode) {
-    return DeleteCommon(obj, index, mode);
+    return DeleteCommon(obj, key, mode);
   }
 
-  virtual MaybeObject* GetWithReceiver(JSObject* obj,
-                                       Object* receiver,
-                                       uint32_t index) {
-    return GetNumberDictionaryElement(obj,
-                                      receiver,
-                                      obj->element_dictionary(),
-                                      index);
+  static MaybeObject* Get(NumberDictionary* backing_store,
+                          uint32_t key,
+                          JSObject* obj,
+                          Object* receiver) {
+    int entry = backing_store->FindEntry(key);
+    if (entry != NumberDictionary::kNotFound) {
+      Object* element = backing_store->ValueAt(entry);
+      PropertyDetails details = backing_store->DetailsAt(entry);
+      if (details.type() == CALLBACKS) {
+        return obj->GetElementWithCallback(receiver,
+                                           element,
+                                           key,
+                                           obj);
+      } else {
+        return element;
+      }
+    }
+    return obj->GetHeap()->the_hole_value();
   }
+
+  static uint32_t GetKeyForIndex(NumberDictionary* dict,
+                                 uint32_t index) {
+    Object* key = dict->KeyAt(index);
+    return Smi::cast(key)->value();
+  }
 };
 
 
 class NonStrictArgumentsElementsAccessor
     : public ElementsAccessorBase<NonStrictArgumentsElementsAccessor,
                                   FixedArray> {
- public:
-  virtual MaybeObject* GetWithReceiver(JSObject* obj,
-                                       Object* receiver,
-                                       uint32_t index) {
-    FixedArray* parameter_map = GetBackingStore(obj);
-    uint32_t length = parameter_map->length();
-    Object* probe =
-        (index < length - 2) ? parameter_map->get(index + 2) : NULL;
-    if (probe != NULL && !probe->IsTheHole()) {
+ protected:
+  friend class ElementsAccessorBase<NonStrictArgumentsElementsAccessor,
+                                    FixedArray>;
+
+  static MaybeObject* Get(FixedArray* parameter_map,
+                          uint32_t key,
+                          JSObject* obj,
+                          Object* receiver) {
+    Object* probe = GetParameterMapArg(parameter_map, key);
+    if (!probe->IsTheHole()) {
       Context* context = Context::cast(parameter_map->get(0));
       int context_index = Smi::cast(probe)->value();
       ASSERT(!context->get(context_index)->IsTheHole());
@@ -347,44 +496,105 @@
     } else {
       // Object is not mapped, defer to the arguments.
       FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
-      if (arguments->IsDictionary()) {
-        return DictionaryElementsAccessor::GetNumberDictionaryElement(
-            obj,
-            receiver,
-            NumberDictionary::cast(arguments),
-            index);
-      } else if (index < static_cast<uint32_t>(arguments->length())) {
-        return arguments->get(index);
-      }
+      return ElementsAccessor::ForArray(arguments)->Get(arguments,
+                                                        key,
+                                                        obj,
+                                                        receiver);
     }
-    return obj->GetHeap()->the_hole_value();
   }
 
   virtual MaybeObject* Delete(JSObject* obj,
-                              uint32_t index,
+                              uint32_t key
+                              ,
                               JSReceiver::DeleteMode mode) {
     FixedArray* parameter_map = FixedArray::cast(obj->elements());
-    uint32_t length = parameter_map->length();
-    Object* probe =
-        index < (length - 2) ? parameter_map->get(index + 2) : NULL;
-    if (probe != NULL && !probe->IsTheHole()) {
+    Object* probe = GetParameterMapArg(parameter_map, key);
+    if (!probe->IsTheHole()) {
       // TODO(kmillikin): We could check if this was the last aliased
       // parameter, and revert to normal elements in that case.  That
       // would enable GC of the context.
-      parameter_map->set_the_hole(index + 2);
+      parameter_map->set_the_hole(key + 2);
     } else {
       FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
       if (arguments->IsDictionary()) {
-        return DictionaryElementsAccessor::DeleteCommon(obj, index, mode);
+        return DictionaryElementsAccessor::DeleteCommon(obj, key, mode);
       } else {
-        return FastElementsAccessor::DeleteCommon(obj, index);
+        return FastElementsAccessor::DeleteCommon(obj, key);
       }
     }
     return obj->GetHeap()->true_value();
   }
+
+  static uint32_t GetCapacity(FixedArray* parameter_map) {
+    FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1));
+    return Max(static_cast<uint32_t>(parameter_map->length() - 2),
+               ForArray(arguments)->GetCapacity(arguments));
+  }
+
+  static uint32_t GetKeyForIndex(FixedArray* dict,
+                                 uint32_t index) {
+    return index;
+  }
+
+  static bool HasElementAtIndex(FixedArray* parameter_map,
+                                uint32_t index,
+                                JSObject* holder,
+                                Object* receiver) {
+    Object* probe = GetParameterMapArg(parameter_map, index);
+    if (!probe->IsTheHole()) {
+      return true;
+    } else {
+      FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1));
+      ElementsAccessor* accessor = ElementsAccessor::ForArray(arguments);
+      return !accessor->Get(arguments, index, holder, receiver)->IsTheHole();
+    }
+  }
+
+ private:
+  static Object* GetParameterMapArg(FixedArray* parameter_map,
+                                    uint32_t key) {
+    uint32_t length = parameter_map->length();
+    return key < (length - 2 )
+        ? parameter_map->get(key + 2)
+        : parameter_map->GetHeap()->the_hole_value();
+  }
 };
 
 
+ElementsAccessor* ElementsAccessor::ForArray(FixedArrayBase* array) {
+  switch (array->map()->instance_type()) {
+    case FIXED_ARRAY_TYPE:
+      if (array->IsDictionary()) {
+        return elements_accessors_[JSObject::DICTIONARY_ELEMENTS];
+      } else {
+        return elements_accessors_[JSObject::FAST_ELEMENTS];
+      }
+    case EXTERNAL_BYTE_ARRAY_TYPE:
+      return elements_accessors_[JSObject::EXTERNAL_BYTE_ELEMENTS];
+    case EXTERNAL_UNSIGNED_BYTE_ARRAY_TYPE:
+      return elements_accessors_[JSObject::EXTERNAL_UNSIGNED_BYTE_ELEMENTS];
+    case EXTERNAL_SHORT_ARRAY_TYPE:
+      return elements_accessors_[JSObject::EXTERNAL_SHORT_ELEMENTS];
+    case EXTERNAL_UNSIGNED_SHORT_ARRAY_TYPE:
+      return elements_accessors_[JSObject::EXTERNAL_UNSIGNED_SHORT_ELEMENTS];
+    case EXTERNAL_INT_ARRAY_TYPE:
+      return elements_accessors_[JSObject::EXTERNAL_INT_ELEMENTS];
+    case EXTERNAL_UNSIGNED_INT_ARRAY_TYPE:
+      return elements_accessors_[JSObject::EXTERNAL_UNSIGNED_INT_ELEMENTS];
+    case EXTERNAL_FLOAT_ARRAY_TYPE:
+      return elements_accessors_[JSObject::EXTERNAL_FLOAT_ELEMENTS];
+    case EXTERNAL_DOUBLE_ARRAY_TYPE:
+      return elements_accessors_[JSObject::EXTERNAL_DOUBLE_ELEMENTS];
+    case EXTERNAL_PIXEL_ARRAY_TYPE:
+      return elements_accessors_[JSObject::EXTERNAL_PIXEL_ELEMENTS];
+    default:
+      UNREACHABLE();
+      return NULL;
+      break;
+  }
+}
+
+
 void ElementsAccessor::InitializeOncePerProcess() {
   static struct ConcreteElementsAccessors {
     FastElementsAccessor fast_elements_handler;