Adding ElementsAccessor::Splice

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 92 matching lines @@
   int len0 = array->length();
   for (int i = 0; i < len0; i++) {
     Object* element = array->get(i);
     if (index->KeyEquals(element)) return true;
   }
   return false;
 }
 
 
 MUST_USE_RESULT
-static MaybeHandle<Object> ThrowArrayLengthRangeError(Isolate* isolate) {
+MaybeHandle<Object> ThrowArrayLengthRangeError(Isolate* isolate) {
   THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kInvalidArrayLength),
                   Object);
 }
 
 
-static void CopyObjectToObjectElements(FixedArrayBase* from_base,
-                                       ElementsKind from_kind,
-                                       uint32_t from_start,
-                                       FixedArrayBase* to_base,
-                                       ElementsKind to_kind, uint32_t to_start,
-                                       int raw_copy_size) {
+void CopyObjectToObjectElements(FixedArrayBase* from_base,
+                                ElementsKind from_kind, uint32_t from_start,
+                                FixedArrayBase* to_base, ElementsKind to_kind,
+                                uint32_t to_start, int raw_copy_size) {
   DCHECK(to_base->map() !=
       from_base->GetIsolate()->heap()->fixed_cow_array_map());
   DisallowHeapAllocation no_allocation;
   int copy_size = raw_copy_size;
   if (raw_copy_size < 0) {
     DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
            raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
     copy_size = Min(from_base->length() - from_start,
                     to_base->length() - to_start);
     if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
@@ skipping 444 matching lines @@
                                               push_size, direction);
   }
 
   static uint32_t PushImpl(Handle<JSArray> receiver,
                            Handle<FixedArrayBase> elms_obj, Object** objects,
                            uint32_t push_size, int direction) {
     UNREACHABLE();
     return 0;
   }
 
+  virtual Handle<JSArray> Splice(Handle<JSArray> receiver,
+                                 Handle<FixedArrayBase> backing_store,
+                                 uint32_t start, uint32_t delete_count,
+                                 Arguments args, uint32_t add_count) {
+    return ElementsAccessorSubclass::SpliceImpl(receiver, backing_store, start,
+                                                delete_count, args, add_count);
+  }
+
+  static Handle<JSArray> SpliceImpl(Handle<JSArray> receiver,
+                                    Handle<FixedArrayBase> backing_store,
+                                    uint32_t start, uint32_t delete_count,
+                                    Arguments args, uint32_t add_count) {
+    UNREACHABLE();
+    return Handle<JSArray>();
+  }
+
+
   virtual void SetLength(Handle<JSArray> array, uint32_t length) final {
     ElementsAccessorSubclass::SetLengthImpl(array, length,
                                             handle(array->elements()));
   }
 
   static void SetLengthImpl(Handle<JSArray> array, uint32_t length,
                             Handle<FixedArrayBase> backing_store);
 
   static Handle<FixedArrayBase> ConvertElementsWithCapacity(
       Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
       ElementsKind from_kind, uint32_t capacity) {
+    return ConvertElementsWithCapacity(
+        object, old_elements, from_kind, capacity,
+        ElementsAccessor::kCopyToEndAndInitializeToHole);
+  }
+
+  static Handle<FixedArrayBase> ConvertElementsWithCapacity(
+      Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
+      ElementsKind from_kind, uint32_t capacity, int copy_size) {
     Isolate* isolate = object->GetIsolate();
-    Handle<FixedArrayBase> elements;
+    Handle<FixedArrayBase> new_elements;
     if (IsFastDoubleElementsKind(kind())) {
-      elements = isolate->factory()->NewFixedDoubleArray(capacity);
+      new_elements = isolate->factory()->NewFixedDoubleArray(capacity);
     } else {
-      elements = isolate->factory()->NewUninitializedFixedArray(capacity);
+      new_elements = isolate->factory()->NewUninitializedFixedArray(capacity);
     }
 
-    int packed = kPackedSizeNotKnown;
+    int packed_size = kPackedSizeNotKnown;
     if (IsFastPackedElementsKind(from_kind) && object->IsJSArray()) {
-      packed = Smi::cast(JSArray::cast(*object)->length())->value();
+      packed_size = Smi::cast(JSArray::cast(*object)->length())->value();
     }
 
     ElementsAccessorSubclass::CopyElementsImpl(
-        *old_elements, 0, *elements, from_kind, 0, packed,
-        ElementsAccessor::kCopyToEndAndInitializeToHole);
-    return elements;
+        *old_elements, 0, *new_elements, from_kind, 0, packed_size, copy_size);
+
+    return new_elements;
   }
 
   static void GrowCapacityAndConvertImpl(Handle<JSObject> object,
                                          uint32_t capacity) {
     ElementsKind from_kind = object->GetElementsKind();
     if (IsFastSmiOrObjectElementsKind(from_kind)) {
       // Array optimizations rely on the prototype lookups of Array objects
       // always returning undefined. If there is a store to the initial
       // prototype object, make sure all of these optimizations are invalidated.
       object->GetIsolate()->UpdateArrayProtectorOnSetLength(object);
@@ skipping 545 matching lines @@
     uint32_t new_length = len + push_size;
     Handle<FixedArrayBase> new_elms;
 
     if (new_length > elms_len) {
       // New backing storage is needed.
       uint32_t capacity = new_length + (new_length >> 1) + 16;
       new_elms = FastElementsAccessorSubclass::ConvertElementsWithCapacity(
           receiver, backing_store, KindTraits::Kind, capacity);
     } else {
       // push_size is > 0 and new_length <= elms_len, so backing_store cannot be
-      // the
-      // empty_fixed_array.
+      // the empty_fixed_array.
       new_elms = backing_store;
     }
 
     // Add the provided values.
     DisallowHeapAllocation no_gc;
     DCHECK(direction == ElementsAccessor::kDirectionForward ||
            direction == ElementsAccessor::kDirectionReverse);
     STATIC_ASSERT(ElementsAccessor::kDirectionForward == 1);
     STATIC_ASSERT(ElementsAccessor::kDirectionReverse == -1);
     for (uint32_t index = 0; index < push_size; index++) {
       int offset = direction * index;
       Object* object = objects[offset];
       FastElementsAccessorSubclass::SetImpl(*new_elms, index + len, object);
     }
     if (!new_elms.is_identical_to(backing_store)) {
       receiver->set_elements(*new_elms);
     }
     DCHECK(*new_elms == receiver->elements());
     // Set the length.
     receiver->set_length(Smi::FromInt(new_length));
     return new_length;
   }
+
+  static void MoveElements(Heap* heap, Handle<FixedArrayBase> backing_store,
+                           int dst_index, int src_index, int len,
+                           int hole_start, int hole_end) {
+    UNREACHABLE();
+  }
+
+  static Handle<JSArray> SpliceImpl(Handle<JSArray> receiver,
+                                    Handle<FixedArrayBase> backing_store,
+                                    uint32_t start, uint32_t delete_count,
+                                    Arguments args, uint32_t add_count) {
+    Isolate* isolate = receiver->GetIsolate();
+    Heap* heap = isolate->heap();
+    const uint32_t len = Smi::cast(receiver->length())->value();
+    const uint32_t new_length = len - delete_count + add_count;
+
+    if (new_length == 0) {
+      receiver->set_elements(heap->empty_fixed_array());
+      receiver->set_length(Smi::FromInt(0));
+      return isolate->factory()->NewJSArrayWithElements(
+          backing_store, KindTraits::Kind, delete_count);
+    }
+
+    // construct the result array which holds the deleted elements
+    Handle<JSArray> deleted_elements = isolate->factory()->NewJSArray(
+        KindTraits::Kind, delete_count, delete_count);
+    if (delete_count > 0) {
+      DisallowHeapAllocation no_gc;
+      FastElementsAccessorSubclass::CopyElementsImpl(
+          *backing_store, start, deleted_elements->elements(), KindTraits::Kind,
+          0, kPackedSizeNotKnown, delete_count);
+    }
+
+    // delete and move elements to make space for add_count new elements
+    bool elms_changed = false;
+    if (add_count < delete_count) {
+      elms_changed = SpliceShrinkStep(backing_store, heap, start, delete_count,
+                                      add_count, len, new_length);
+    } else if (add_count > delete_count) {
+      elms_changed =
+          SpliceGrowStep(receiver, backing_store, isolate, heap, start,
+                         delete_count, add_count, len, new_length);
+    }
+
+    // Copy new Elements from args
+    DisallowHeapAllocation no_gc;
+    for (uint32_t index = start; index < start + add_count; index++) {
+      Object* arg = args[3 + index - start];
+      FastElementsAccessorSubclass::SetImpl(*backing_store, index, arg);
+    }
+
+    if (elms_changed) {
+      receiver->set_elements(*backing_store);
+    }
+    receiver->set_length(Smi::FromInt(new_length));
+    return deleted_elements;
+  }
+
+ private:
+  static bool SpliceShrinkStep(Handle<FixedArrayBase>& backing_store,
+                               Heap* heap, uint32_t start,
+                               uint32_t delete_count, uint32_t add_count,
+                               uint32_t len, uint32_t new_length) {
+    const int move_left_count = len - delete_count - start;
+    const int move_left_dst_index = start + add_count;
+    const bool left_trim_array = heap->CanMoveObjectStart(*backing_store) &&
+                                 (move_left_dst_index < move_left_count);
+    if (left_trim_array) {
+      const int delta = delete_count - add_count;
+      // shift from before the insertion point to the right
+      FastElementsAccessorSubclass::MoveElements(heap, backing_store, delta, 0,
+                                                 start, 0, 0);
+      backing_store = handle(heap->LeftTrimFixedArray(*backing_store, delta));
+      return true;
+    } else {
+      // No left-trim needed or possible (in this case we left-move and store
+      // the hole)
+      FastElementsAccessorSubclass::MoveElements(
+          heap, backing_store, move_left_dst_index, start + delete_count,
+          move_left_count, new_length, len);
+    }
+    return false;
+  }
+
+
+  static bool SpliceGrowStep(Handle<JSArray> receiver,
+                             Handle<FixedArrayBase>& backing_store,
+                             Isolate* isolate, Heap* heap, uint32_t start,
+                             uint32_t delete_count, uint32_t add_count,
+                             uint32_t len, uint32_t new_length) {
+    // Currently fixed arrays cannot grow too big, so
+    // we should never hit this case.
+    DCHECK((add_count - delete_count) <= (Smi::kMaxValue - len));
+    // Check if backing_store needs to grow.
+    if (new_length > static_cast<uint32_t>(backing_store->length())) {
+      // New backing storage is needed.
+      int capacity = new_length + (new_length >> 1) + 16;
+      // partially copy all elements up to start
+      Handle<FixedArrayBase> new_elms =
+          FastElementsAccessorSubclass::ConvertElementsWithCapacity(
+              receiver, backing_store, KindTraits::Kind, capacity, start);
+      // Copy the trailing elements after start + delete_count
+      FastElementsAccessorSubclass::CopyElementsImpl(
+          *backing_store, start + delete_count, *new_elms, KindTraits::Kind,
+          start + add_count, kPackedSizeNotKnown,
+          ElementsAccessor::kCopyToEndAndInitializeToHole);
+
+      backing_store = new_elms;
+      return true;
+    } else {
+      DisallowHeapAllocation no_gc;
+      FastElementsAccessorSubclass::MoveElements(
+          heap, backing_store, start + add_count, start + delete_count,
+          (len - delete_count - start), 0, 0);
+    }
+    return false;
+  }
 };
 
 
 template<typename FastElementsAccessorSubclass,
          typename KindTraits>
 class FastSmiOrObjectElementsAccessor
     : public FastElementsAccessor<FastElementsAccessorSubclass, KindTraits> {
  public:
   explicit FastSmiOrObjectElementsAccessor(const char* name)
       : FastElementsAccessor<FastElementsAccessorSubclass,
                              KindTraits>(name) {}
 
   static Object* GetRaw(FixedArray* backing_store, uint32_t entry) {
     uint32_t index = FastElementsAccessorSubclass::GetIndexForEntryImpl(
         backing_store, entry);
     return backing_store->get(index);
   }
 
+  static void MoveElements(Heap* heap, Handle<FixedArrayBase> backing_store,
+                           int dst_index, int src_index, int len,
+                           int hole_start, int hole_end) {
+    Handle<FixedArray> dst_elms = Handle<FixedArray>::cast(backing_store);
+    if (len != 0) {
+      DisallowHeapAllocation no_gc;
+      heap->MoveElements(*dst_elms, dst_index, src_index, len);
+    }
+    if (hole_start != hole_end) {
+      dst_elms->FillWithHoles(hole_start, hole_end);
+    }
+  }
+
   // NOTE: this method violates the handlified function signature convention:
   // raw pointer parameters in the function that allocates.
   // See ElementsAccessor::CopyElements() for details.
   // This method could actually allocate if copying from double elements to
   // object elements.
   static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start,
                                FixedArrayBase* to, ElementsKind from_kind,
                                uint32_t to_start, int packed_size,
                                int copy_size) {
     DisallowHeapAllocation no_gc;
@@ skipping 80 matching lines @@
 
 template<typename FastElementsAccessorSubclass,
          typename KindTraits>
 class FastDoubleElementsAccessor
     : public FastElementsAccessor<FastElementsAccessorSubclass, KindTraits> {
  public:
   explicit FastDoubleElementsAccessor(const char* name)
       : FastElementsAccessor<FastElementsAccessorSubclass,
                              KindTraits>(name) {}
 
+  static void MoveElements(Heap* heap, Handle<FixedArrayBase> backing_store,
+                           int dst_index, int src_index, int len,
+                           int hole_start, int hole_end) {
+    Handle<FixedDoubleArray> dst_elms =
+        Handle<FixedDoubleArray>::cast(backing_store);
+    if (len != 0) {
+      MemMove(dst_elms->data_start() + dst_index,
+              dst_elms->data_start() + src_index, len * kDoubleSize);
+    }
+    if (hole_start != hole_end) {
+      dst_elms->FillWithHoles(hole_start, hole_end);
+    }
+  }
+
   static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start,
                                FixedArrayBase* to, ElementsKind from_kind,
                                uint32_t to_start, int packed_size,
                                int copy_size) {
     DisallowHeapAllocation no_allocation;
     switch (from_kind) {
       case FAST_SMI_ELEMENTS:
         CopyPackedSmiToDoubleElements(from, from_start, to, to_start,
                                       packed_size, copy_size);
         break;
@@ skipping 640 matching lines @@
 #define ACCESSOR_DELETE(Class, Kind, Store) delete elements_accessors_[Kind];
   ELEMENTS_LIST(ACCESSOR_DELETE)
 #undef ACCESSOR_DELETE
   elements_accessors_ = NULL;
 }
 
 
 ElementsAccessor** ElementsAccessor::elements_accessors_ = NULL;
 }  // namespace internal
 }  // namespace v8