Adding ElementsAccessor::Concat

src/builtins.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/builtins.h"
 
 #include "src/api.h"
 #include "src/api-natives.h"
 #include "src/arguments.h"
 #include "src/base/once.h"
@@ skipping 586 matching lines @@
     AllowHeapAllocation allow_allocation;
     return CallJsIntrinsic(isolate, isolate->array_splice(), args);
   }
   ElementsAccessor* accessor = array->GetElementsAccessor();
   Handle<JSArray> result_array = accessor->Splice(
       array, elms_obj, actual_start, actual_delete_count, &args, add_count);
   return *result_array;
 }
 
 
-BUILTIN(ArrayConcat) {
-  HandleScope scope(isolate);
-
-  int n_arguments = args.length();
+// Array Concat -------------------------------------------------------------
+
+namespace {
+
+/**
+ * A simple visitor visits every element of Array's.
+ * The backend storage can be a fixed array for fast elements case,
+ * or a dictionary for sparse array. Since Dictionary is a subtype
+ * of FixedArray, the class can be used by both fast and slow cases.
+ * The second parameter of the constructor, fast_elements, specifies
+ * whether the storage is a FixedArray or Dictionary.
+ *
+ * An index limit is used to deal with the situation that a result array
+ * length overflows 32-bit non-negative integer.
+ */
+class ArrayConcatVisitor {

[Camillo Bruni, 2015/09/04 13:54:55]

Probably ElementsAccessor would be a better place for this?

+ public:
+  ArrayConcatVisitor(Isolate* isolate, Handle<FixedArray> storage,
+                     bool fast_elements)
+      : isolate_(isolate),
+        storage_(Handle<FixedArray>::cast(
+            isolate->global_handles()->Create(*storage))),
+        index_offset_(0u),
+        bit_field_(FastElementsField::encode(fast_elements) |
+                   ExceedsLimitField::encode(false)) {}
+
+  ~ArrayConcatVisitor() { clear_storage(); }
+
+  void visit(uint32_t i, Handle<Object> elm) {
+    if (i >= JSObject::kMaxElementCount - index_offset_) {
+      set_exceeds_array_limit(true);
+      return;
+    }
+    uint32_t index = index_offset_ + i;
+
+    if (fast_elements()) {
+      if (index < static_cast<uint32_t>(storage_->length())) {
+        storage_->set(index, *elm);
+        return;
+      }
+      // Our initial estimate of length was foiled, possibly by
+      // getters on the arrays increasing the length of later arrays
+      // during iteration.
+      // This shouldn't happen in anything but pathological cases.
+      SetDictionaryMode();
+      // Fall-through to dictionary mode.
+    }
+    DCHECK(!fast_elements());
+    Handle<SeededNumberDictionary> dict(
+        SeededNumberDictionary::cast(*storage_));
+    // The object holding this backing store has just been allocated, so
+    // it cannot yet be used as a prototype.
+    Handle<SeededNumberDictionary> result =
+        SeededNumberDictionary::AtNumberPut(dict, index, elm, false);
+    if (!result.is_identical_to(dict)) {
+      // Dictionary needed to grow.
+      clear_storage();
+      set_storage(*result);
+    }
+  }
+
+  void increase_index_offset(uint32_t delta) {
+    if (JSObject::kMaxElementCount - index_offset_ < delta) {
+      index_offset_ = JSObject::kMaxElementCount;
+    } else {
+      index_offset_ += delta;
+    }
+    // If the initial length estimate was off (see special case in visit()),
+    // but the array blowing the limit didn't contain elements beyond the
+    // provided-for index range, go to dictionary mode now.
+    if (fast_elements() &&
+        index_offset_ >
+            static_cast<uint32_t>(FixedArrayBase::cast(*storage_)->length())) {
+      SetDictionaryMode();
+    }
+  }
+
+  bool exceeds_array_limit() const {
+    return ExceedsLimitField::decode(bit_field_);
+  }
+
+  Handle<JSArray> ToArray() {
+    Handle<JSArray> array = isolate_->factory()->NewJSArray(0);
+    Handle<Object> length =
+        isolate_->factory()->NewNumber(static_cast<double>(index_offset_));
+    Handle<Map> map = JSObject::GetElementsTransitionMap(
+        array, fast_elements() ? FAST_HOLEY_ELEMENTS : DICTIONARY_ELEMENTS);
+    array->set_map(*map);
+    array->set_length(*length);
+    array->set_elements(*storage_);
+    return array;
+  }
+
+ private:
+  // Convert storage to dictionary mode.
+  void SetDictionaryMode() {
+    DCHECK(fast_elements());
+    Handle<FixedArray> current_storage(*storage_);
+    Handle<SeededNumberDictionary> slow_storage(
+        SeededNumberDictionary::New(isolate_, current_storage->length()));
+    uint32_t current_length = static_cast<uint32_t>(current_storage->length());
+    for (uint32_t i = 0; i < current_length; i++) {
+      HandleScope loop_scope(isolate_);
+      Handle<Object> element(current_storage->get(i), isolate_);
+      if (!element->IsTheHole()) {
+        // The object holding this backing store has just been allocated, so
+        // it cannot yet be used as a prototype.
+        Handle<SeededNumberDictionary> new_storage =
+            SeededNumberDictionary::AtNumberPut(slow_storage, i, element,
+                                                false);
+        if (!new_storage.is_identical_to(slow_storage)) {
+          slow_storage = loop_scope.CloseAndEscape(new_storage);
+        }
+      }
+    }
+    clear_storage();
+    set_storage(*slow_storage);
+    set_fast_elements(false);
+  }
+
+  inline void clear_storage() {
+    GlobalHandles::Destroy(Handle<Object>::cast(storage_).location());
+  }
+
+  inline void set_storage(FixedArray* storage) {
+    storage_ =
+        Handle<FixedArray>::cast(isolate_->global_handles()->Create(storage));
+  }
+
+  class FastElementsField : public BitField<bool, 0, 1> {};
+  class ExceedsLimitField : public BitField<bool, 1, 1> {};
+
+  bool fast_elements() const { return FastElementsField::decode(bit_field_); }
+  void set_fast_elements(bool fast) {
+    bit_field_ = FastElementsField::update(bit_field_, fast);
+  }
+  void set_exceeds_array_limit(bool exceeds) {
+    bit_field_ = ExceedsLimitField::update(bit_field_, exceeds);
+  }
+
+  Isolate* isolate_;
+  Handle<FixedArray> storage_;  // Always a global handle.
+  // Index after last seen index. Always less than or equal to
+  // JSObject::kMaxElementCount.
+  uint32_t index_offset_;
+  uint32_t bit_field_;
+};
+
+
+uint32_t EstimateElementCount(Handle<JSArray> array) {
+  uint32_t length = static_cast<uint32_t>(array->length()->Number());
+  int element_count = 0;
+  switch (array->GetElementsKind()) {
+    case FAST_SMI_ELEMENTS:
+    case FAST_HOLEY_SMI_ELEMENTS:
+    case FAST_ELEMENTS:
+    case FAST_HOLEY_ELEMENTS: {
+      // Fast elements can't have lengths that are not representable by
+      // a 32-bit signed integer.
+      DCHECK(static_cast<int32_t>(FixedArray::kMaxLength) >= 0);
+      int fast_length = static_cast<int>(length);
+      Handle<FixedArray> elements(FixedArray::cast(array->elements()));
+      for (int i = 0; i < fast_length; i++) {
+        if (!elements->get(i)->IsTheHole()) element_count++;
+      }
+      break;
+    }
+    case FAST_DOUBLE_ELEMENTS:
+    case FAST_HOLEY_DOUBLE_ELEMENTS: {
+      // Fast elements can't have lengths that are not representable by
+      // a 32-bit signed integer.
+      DCHECK(static_cast<int32_t>(FixedDoubleArray::kMaxLength) >= 0);
+      int fast_length = static_cast<int>(length);
+      if (array->elements()->IsFixedArray()) {
+        DCHECK(FixedArray::cast(array->elements())->length() == 0);
+        break;
+      }
+      Handle<FixedDoubleArray> elements(
+          FixedDoubleArray::cast(array->elements()));
+      for (int i = 0; i < fast_length; i++) {
+        if (!elements->is_the_hole(i)) element_count++;
+      }
+      break;
+    }
+    case DICTIONARY_ELEMENTS: {
+      Handle<SeededNumberDictionary> dictionary(
+          SeededNumberDictionary::cast(array->elements()));
+      int capacity = dictionary->Capacity();
+      for (int i = 0; i < capacity; i++) {
+        Handle<Object> key(dictionary->KeyAt(i), array->GetIsolate());
+        if (dictionary->IsKey(*key)) {
+          element_count++;
+        }
+      }
+      break;
+    }
+    case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
+    case SLOW_SLOPPY_ARGUMENTS_ELEMENTS:
+#define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) case TYPE##_ELEMENTS:
+
+      TYPED_ARRAYS(TYPED_ARRAY_CASE)
+#undef TYPED_ARRAY_CASE
+      // External arrays are always dense.
+      return length;
+  }
+  // As an estimate, we assume that the prototype doesn't contain any
+  // inherited elements.
+  return element_count;
+}
+
+
+template <class ExternalArrayClass, class ElementType>
+void IterateTypedArrayElements(Isolate* isolate, Handle<JSObject> receiver,
+                               bool elements_are_ints,
+                               bool elements_are_guaranteed_smis,
+                               ArrayConcatVisitor* visitor) {
+  Handle<ExternalArrayClass> array(
+      ExternalArrayClass::cast(receiver->elements()));
+  uint32_t len = static_cast<uint32_t>(array->length());
+
+  DCHECK(visitor != NULL);
+  if (elements_are_ints) {
+    if (elements_are_guaranteed_smis) {
+      for (uint32_t j = 0; j < len; j++) {
+        HandleScope loop_scope(isolate);
+        Handle<Smi> e(Smi::FromInt(static_cast<int>(array->get_scalar(j))),
+                      isolate);
+        visitor->visit(j, e);
+      }
+    } else {
+      for (uint32_t j = 0; j < len; j++) {
+        HandleScope loop_scope(isolate);
+        int64_t val = static_cast<int64_t>(array->get_scalar(j));
+        if (Smi::IsValid(static_cast<intptr_t>(val))) {
+          Handle<Smi> e(Smi::FromInt(static_cast<int>(val)), isolate);
+          visitor->visit(j, e);
+        } else {
+          Handle<Object> e =
+              isolate->factory()->NewNumber(static_cast<ElementType>(val));
+          visitor->visit(j, e);
+        }
+      }
+    }
+  } else {
+    for (uint32_t j = 0; j < len; j++) {
+      HandleScope loop_scope(isolate);
+      Handle<Object> e = isolate->factory()->NewNumber(array->get_scalar(j));
+      visitor->visit(j, e);
+    }
+  }
+}
+
+
+// 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 CollectElementIndices(Handle<JSObject> object, uint32_t range,
+                           List<uint32_t>* indices) {
+  Isolate* isolate = object->GetIsolate();
+  ElementsKind kind = object->GetElementsKind();
+  switch (kind) {
+    case FAST_SMI_ELEMENTS:
+    case FAST_ELEMENTS:
+    case FAST_HOLEY_SMI_ELEMENTS:
+    case FAST_HOLEY_ELEMENTS: {
+      Handle<FixedArray> elements(FixedArray::cast(object->elements()));
+      uint32_t length = static_cast<uint32_t>(elements->length());
+      if (range < length) length = range;
+      for (uint32_t i = 0; i < length; i++) {
+        if (!elements->get(i)->IsTheHole()) {
+          indices->Add(i);
+        }
+      }
+      break;
+    }
+    case FAST_HOLEY_DOUBLE_ELEMENTS:
+    case FAST_DOUBLE_ELEMENTS: {
+      if (object->elements()->IsFixedArray()) {
+        DCHECK(object->elements()->length() == 0);
+        break;
+      }
+      Handle<FixedDoubleArray> elements(
+          FixedDoubleArray::cast(object->elements()));
+      uint32_t length = static_cast<uint32_t>(elements->length());
+      if (range < length) length = range;
+      for (uint32_t i = 0; i < length; i++) {
+        if (!elements->is_the_hole(i)) {
+          indices->Add(i);
+        }
+      }
+      break;
+    }
+    case DICTIONARY_ELEMENTS: {
+      Handle<SeededNumberDictionary> dict(
+          SeededNumberDictionary::cast(object->elements()));
+      uint32_t capacity = dict->Capacity();
+      for (uint32_t j = 0; j < capacity; j++) {
+        HandleScope loop_scope(isolate);
+        Handle<Object> k(dict->KeyAt(j), isolate);
+        if (dict->IsKey(*k)) {
+          DCHECK(k->IsNumber());
+          uint32_t index = static_cast<uint32_t>(k->Number());
+          if (index < range) {
+            indices->Add(index);
+          }
+        }
+      }
+      break;
+    }
+#define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) case TYPE##_ELEMENTS:
+
+      TYPED_ARRAYS(TYPED_ARRAY_CASE)
+#undef TYPED_ARRAY_CASE
+      {
+        uint32_t length = static_cast<uint32_t>(
+            FixedArrayBase::cast(object->elements())->length());
+        if (range <= length) {
+          length = range;
+          // We will add all indices, so we might as well clear it first
+          // and avoid duplicates.
+          indices->Clear();
+        }
+        for (uint32_t i = 0; i < length; i++) {
+          indices->Add(i);
+        }
+        if (length == range) return;  // All indices accounted for already.
+        break;
+      }
+    case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
+    case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: {
+      ElementsAccessor* accessor = object->GetElementsAccessor();
+      for (uint32_t i = 0; i < range; i++) {
+        if (accessor->HasElement(object, i)) {
+          indices->Add(i);
+        }
+      }
+      break;
+    }
+  }
+
+  PrototypeIterator iter(isolate, object);
+  if (!iter.IsAtEnd()) {
+    // The prototype will usually have no inherited element indices,
+    // but we have to check.
+    CollectElementIndices(
+        Handle<JSObject>::cast(PrototypeIterator::GetCurrent(iter)), range,
+        indices);
+  }
+}
+
+
+bool IterateElementsSlow(Isolate* isolate, Handle<JSObject> receiver,
+                         uint32_t length, ArrayConcatVisitor* visitor) {
+  for (uint32_t i = 0; i < length; ++i) {
+    HandleScope loop_scope(isolate);
+    Maybe<bool> maybe = JSReceiver::HasElement(receiver, i);
+    if (!maybe.IsJust()) return false;
+    if (maybe.FromJust()) {
+      Handle<Object> element_value;
+      ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_value,
+                                       Object::GetElement(isolate, receiver, i),
+                                       false);
+      visitor->visit(i, element_value);
+    }
+  }
+  visitor->increase_index_offset(length);
+  return true;
+}
+
+
+/**
+ * A helper function that visits elements of a JSObject in numerical
+ * order.
+ *
+ * The visitor argument called for each existing element in the array
+ * with the element index and the element's value.
+ * Afterwards it increments the base-index of the visitor by the array
+ * length.
+ * Returns false if any access threw an exception, otherwise true.
+ */
+bool IterateElements(Isolate* isolate, Handle<JSObject> receiver,
+                     ArrayConcatVisitor* visitor) {
+  uint32_t length = 0;
+
+  if (receiver->IsJSArray()) {
+    Handle<JSArray> array(Handle<JSArray>::cast(receiver));
+    length = static_cast<uint32_t>(array->length()->Number());
+  } else {
+    Handle<Object> val;
+    Handle<Object> key(isolate->heap()->length_string(), isolate);
+    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
+        isolate, val, Runtime::GetObjectProperty(isolate, receiver, key),
+        false);
+    // TODO(caitp): Support larger element indexes (up to 2^53-1).
+    if (!val->ToUint32(&length)) {
+      ASSIGN_RETURN_ON_EXCEPTION_VALUE(
+          isolate, val, Execution::ToLength(isolate, val), false);
+      val->ToUint32(&length);
+    }
+  }
+
+  if (!(receiver->IsJSArray() || receiver->IsJSTypedArray())) {
+    // For classes which are not known to be safe to access via elements alone,
+    // use the slow case.
+    return IterateElementsSlow(isolate, receiver, length, visitor);
+  }
+
+  switch (receiver->GetElementsKind()) {
+    case FAST_SMI_ELEMENTS:
+    case FAST_ELEMENTS:
+    case FAST_HOLEY_SMI_ELEMENTS:
+    case FAST_HOLEY_ELEMENTS: {
+      // Run through the elements FixedArray and use HasElement and GetElement
+      // to check the prototype for missing elements.
+      Handle<FixedArray> elements(FixedArray::cast(receiver->elements()));
+      int fast_length = static_cast<int>(length);
+      DCHECK(fast_length <= elements->length());
+      for (int j = 0; j < fast_length; j++) {
+        HandleScope loop_scope(isolate);
+        Handle<Object> element_value(elements->get(j), isolate);
+        if (!element_value->IsTheHole()) {
+          visitor->visit(j, element_value);
+        } else {
+          Maybe<bool> maybe = JSReceiver::HasElement(receiver, j);
+          if (!maybe.IsJust()) return false;
+          if (maybe.FromJust()) {
+            // Call GetElement on receiver, not its prototype, or getters won't
+            // have the correct receiver.
+            ASSIGN_RETURN_ON_EXCEPTION_VALUE(
+                isolate, element_value,
+                Object::GetElement(isolate, receiver, j), false);
+            visitor->visit(j, element_value);
+          }
+        }
+      }
+      break;
+    }
+    case FAST_HOLEY_DOUBLE_ELEMENTS:
+    case FAST_DOUBLE_ELEMENTS: {
+      // Empty array is FixedArray but not FixedDoubleArray.
+      if (length == 0) break;
+      // Run through the elements FixedArray and use HasElement and GetElement
+      // to check the prototype for missing elements.
+      if (receiver->elements()->IsFixedArray()) {
+        DCHECK(receiver->elements()->length() == 0);
+        break;
+      }
+      Handle<FixedDoubleArray> elements(
+          FixedDoubleArray::cast(receiver->elements()));
+      int fast_length = static_cast<int>(length);
+      DCHECK(fast_length <= elements->length());
+      for (int j = 0; j < fast_length; j++) {
+        HandleScope loop_scope(isolate);
+        if (!elements->is_the_hole(j)) {
+          double double_value = elements->get_scalar(j);
+          Handle<Object> element_value =
+              isolate->factory()->NewNumber(double_value);
+          visitor->visit(j, element_value);
+        } else {
+          Maybe<bool> maybe = JSReceiver::HasElement(receiver, j);
+          if (!maybe.IsJust()) return false;
+          if (maybe.FromJust()) {
+            // Call GetElement on receiver, not its prototype, or getters won't
+            // have the correct receiver.
+            Handle<Object> element_value;
+            ASSIGN_RETURN_ON_EXCEPTION_VALUE(
+                isolate, element_value,
+                Object::GetElement(isolate, receiver, j), false);
+            visitor->visit(j, element_value);
+          }
+        }
+      }
+      break;
+    }
+    case DICTIONARY_ELEMENTS: {
+      Handle<SeededNumberDictionary> dict(receiver->element_dictionary());
+      List<uint32_t> indices(dict->Capacity() / 2);
+      // Collect all indices in the object and the prototypes less
+      // than length. This might introduce duplicates in the indices list.
+      CollectElementIndices(receiver, length, &indices);
+      indices.Sort(&compareUInt32);
+      int j = 0;
+      int n = indices.length();
+      while (j < n) {
+        HandleScope loop_scope(isolate);
+        uint32_t index = indices[j];
+        Handle<Object> element;
+        ASSIGN_RETURN_ON_EXCEPTION_VALUE(
+            isolate, element, Object::GetElement(isolate, receiver, index),
+            false);
+        visitor->visit(index, element);
+        // Skip to next different index (i.e., omit duplicates).
+        do {
+          j++;
+        } while (j < n && indices[j] == index);
+      }
+      break;
+    }
+    case UINT8_CLAMPED_ELEMENTS: {
+      Handle<FixedUint8ClampedArray> pixels(
+          FixedUint8ClampedArray::cast(receiver->elements()));
+      for (uint32_t j = 0; j < length; j++) {
+        Handle<Smi> e(Smi::FromInt(pixels->get_scalar(j)), isolate);
+        visitor->visit(j, e);
+      }
+      break;
+    }
+    case INT8_ELEMENTS: {
+      IterateTypedArrayElements<FixedInt8Array, int8_t>(isolate, receiver, true,
+                                                        true, visitor);
+      break;
+    }
+    case UINT8_ELEMENTS: {
+      IterateTypedArrayElements<FixedUint8Array, uint8_t>(isolate, receiver,
+                                                          true, true, visitor);
+      break;
+    }
+    case INT16_ELEMENTS: {
+      IterateTypedArrayElements<FixedInt16Array, int16_t>(isolate, receiver,
+                                                          true, true, visitor);
+      break;
+    }
+    case UINT16_ELEMENTS: {
+      IterateTypedArrayElements<FixedUint16Array, uint16_t>(
+          isolate, receiver, true, true, visitor);
+      break;
+    }
+    case INT32_ELEMENTS: {
+      IterateTypedArrayElements<FixedInt32Array, int32_t>(isolate, receiver,
+                                                          true, false, visitor);
+      break;
+    }
+    case UINT32_ELEMENTS: {
+      IterateTypedArrayElements<FixedUint32Array, uint32_t>(
+          isolate, receiver, true, false, visitor);
+      break;
+    }
+    case FLOAT32_ELEMENTS: {
+      IterateTypedArrayElements<FixedFloat32Array, float>(
+          isolate, receiver, false, false, visitor);
+      break;
+    }
+    case FLOAT64_ELEMENTS: {
+      IterateTypedArrayElements<FixedFloat64Array, double>(
+          isolate, receiver, false, false, visitor);
+      break;
+    }
+    case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
+    case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: {
+      for (uint32_t index = 0; index < length; index++) {
+        HandleScope loop_scope(isolate);
+        Handle<Object> element;
+        ASSIGN_RETURN_ON_EXCEPTION_VALUE(
+            isolate, element, Object::GetElement(isolate, receiver, index),
+            false);
+        visitor->visit(index, element);
+      }
+      break;
+    }
+  }
+  visitor->increase_index_offset(length);
+  return true;
+}
+
+
+bool HasConcatSpreadableModifier(Isolate* isolate, Handle<Object> obj) {

[Camillo Bruni, 2015/09/04 13:54:55]

At some point we need something faster here, since we have a massive penalty
with the FLAG_harmony_concat_spreadable enabled. At least we are more correct
this way (see https://codereview.chromium.org/1247243003)

+  if (!obj->IsJSReceiver()) return false;
+  if (!FLAG_harmony_concat_spreadable) return false;
+
+  Handle<Symbol> key(isolate->factory()->is_concat_spreadable_symbol());
+  Maybe<bool> maybe =
+      JSReceiver::HasProperty(Handle<JSReceiver>::cast(obj), key);
+  if (!maybe.IsJust()) return false;
+  return maybe.FromJust();
+}
+
+
+bool IsConcatSpreadable(Isolate* isolate, Handle<Object> obj) {
+  HandleScope handle_scope(isolate);
+  if (!obj->IsSpecObject()) return false;
+  if (FLAG_harmony_concat_spreadable) {
+    Handle<Symbol> key(isolate->factory()->is_concat_spreadable_symbol());
+    Handle<Object> value;
+    MaybeHandle<Object> maybeValue =
+        i::Runtime::GetObjectProperty(isolate, obj, key);
+    if (maybeValue.ToHandle(&value) && !value->IsUndefined()) {
+      return value->BooleanValue();
+    }
+  }
+  return obj->IsJSArray();
+}
+
+
+/**
+ * Array::concat implementation.
+ * See ECMAScript 262, 15.4.4.4.
+ * TODO(581): Fix non-compliance for very large concatenations and update to
+ * following the ECMAScript 5 specification.
+ */
+Object* Slow_ArrayConcat(Arguments* args, Isolate* isolate) {
+  int argument_count = args->length();
+
+  // Pass 1: estimate the length and number of elements of the result.
+  // The actual length can be larger if any of the arguments have getters
+  // that mutate other arguments (but will otherwise be precise).
+  // The number of elements is precise if there are no inherited elements.
+
+  ElementsKind kind = FAST_SMI_ELEMENTS;
+
+  uint32_t estimate_result_length = 0;
+  uint32_t estimate_nof_elements = 0;
+  for (int i = 0; i < argument_count; i++) {
+    HandleScope loop_scope(isolate);
+    Handle<Object> obj((*args)[i], isolate);
+    uint32_t length_estimate;
+    uint32_t element_estimate;
+    if (obj->IsJSArray()) {
+      Handle<JSArray> array(Handle<JSArray>::cast(obj));
+      length_estimate = static_cast<uint32_t>(array->length()->Number());
+      if (length_estimate != 0) {
+        ElementsKind array_kind =
+            GetPackedElementsKind(array->map()->elements_kind());
+        if (IsMoreGeneralElementsKindTransition(kind, array_kind)) {
+          kind = array_kind;
+        }
+      }
+      element_estimate = EstimateElementCount(array);
+    } else {
+      if (obj->IsHeapObject()) {
+        if (obj->IsNumber()) {
+          if (IsMoreGeneralElementsKindTransition(kind, FAST_DOUBLE_ELEMENTS)) {
+            kind = FAST_DOUBLE_ELEMENTS;
+          }
+        } else if (IsMoreGeneralElementsKindTransition(kind, FAST_ELEMENTS)) {
+          kind = FAST_ELEMENTS;
+        }
+      }
+      length_estimate = 1;
+      element_estimate = 1;
+    }
+    // Avoid overflows by capping at kMaxElementCount.
+    if (JSObject::kMaxElementCount - estimate_result_length < length_estimate) {
+      estimate_result_length = JSObject::kMaxElementCount;
+    } else {
+      estimate_result_length += length_estimate;
+    }
+    if (JSObject::kMaxElementCount - estimate_nof_elements < element_estimate) {
+      estimate_nof_elements = JSObject::kMaxElementCount;
+    } else {
+      estimate_nof_elements += element_estimate;
+    }
+  }
+
+  // If estimated number of elements is more than half of length, a
+  // fixed array (fast case) is more time and space-efficient than a
+  // dictionary.
+  bool fast_case = (estimate_nof_elements * 2) >= estimate_result_length;
+
+  if (fast_case && kind == FAST_DOUBLE_ELEMENTS) {
+    Handle<FixedArrayBase> storage =
+        isolate->factory()->NewFixedDoubleArray(estimate_result_length);
+    int j = 0;
+    bool failure = false;
+    if (estimate_result_length > 0) {
+      Handle<FixedDoubleArray> double_storage =
+          Handle<FixedDoubleArray>::cast(storage);
+      for (int i = 0; i < argument_count; i++) {
+        Handle<Object> obj((*args)[i], isolate);
+        if (obj->IsSmi()) {
+          double_storage->set(j, Smi::cast(*obj)->value());
+          j++;
+        } else if (obj->IsNumber()) {
+          double_storage->set(j, obj->Number());
+          j++;
+        } else {
+          JSArray* array = JSArray::cast(*obj);
+          uint32_t length = static_cast<uint32_t>(array->length()->Number());
+          switch (array->map()->elements_kind()) {
+            case FAST_HOLEY_DOUBLE_ELEMENTS:
+            case FAST_DOUBLE_ELEMENTS: {
+              // Empty array is FixedArray but not FixedDoubleArray.
+              if (length == 0) break;
+              FixedDoubleArray* elements =
+                  FixedDoubleArray::cast(array->elements());
+              for (uint32_t i = 0; i < length; i++) {
+                if (elements->is_the_hole(i)) {
+                  // TODO(jkummerow/verwaest): We could be a bit more clever
+                  // here: Check if there are no elements/getters on the
+                  // prototype chain, and if so, allow creation of a holey
+                  // result array.
+                  // Same thing below (holey smi case).
+                  failure = true;
+                  break;
+                }
+                double double_value = elements->get_scalar(i);
+                double_storage->set(j, double_value);
+                j++;
+              }
+              break;
+            }
+            case FAST_HOLEY_SMI_ELEMENTS:
+            case FAST_SMI_ELEMENTS: {
+              FixedArray* elements(FixedArray::cast(array->elements()));
+              for (uint32_t i = 0; i < length; i++) {
+                Object* element = elements->get(i);
+                if (element->IsTheHole()) {
+                  failure = true;
+                  break;
+                }
+                int32_t int_value = Smi::cast(element)->value();
+                double_storage->set(j, int_value);
+                j++;
+              }
+              break;
+            }
+            case FAST_HOLEY_ELEMENTS:
+            case FAST_ELEMENTS:
+            case DICTIONARY_ELEMENTS:
+              DCHECK_EQ(0u, length);
+              break;
+            default:
+              UNREACHABLE();
+          }
+        }
+        if (failure) break;
+      }
+    }
+    if (!failure) {
+      Handle<JSArray> array = isolate->factory()->NewJSArray(0);
+      Smi* length = Smi::FromInt(j);
+      Handle<Map> map;
+      map = JSObject::GetElementsTransitionMap(array, kind);
+      array->set_map(*map);
+      array->set_length(length);
+      array->set_elements(*storage);
+      return *array;
+    }
+    // In case of failure, fall through.
+  }
+
+  Handle<FixedArray> storage;
+  if (fast_case) {
+    // The backing storage array must have non-existing elements to preserve
+    // holes across concat operations.
+    storage =
+        isolate->factory()->NewFixedArrayWithHoles(estimate_result_length);
+  } else {
+    // TODO(126): move 25% pre-allocation logic into Dictionary::Allocate
+    uint32_t at_least_space_for =
+        estimate_nof_elements + (estimate_nof_elements >> 2);
+    storage = Handle<FixedArray>::cast(
+        SeededNumberDictionary::New(isolate, at_least_space_for));
+  }
+
+  ArrayConcatVisitor visitor(isolate, storage, fast_case);
+
+  for (int i = 0; i < argument_count; i++) {
+    Handle<Object> obj((*args)[i], isolate);
+    bool spreadable = IsConcatSpreadable(isolate, obj);
+    if (isolate->has_pending_exception()) return isolate->heap()->exception();
+    if (spreadable) {
+      Handle<JSObject> object = Handle<JSObject>::cast(obj);
+      if (!IterateElements(isolate, object, &visitor)) {
+        return isolate->heap()->exception();
+      }
+    } else {
+      visitor.visit(0, obj);
+      visitor.increase_index_offset(1);
+    }
+  }
+
+  if (visitor.exceeds_array_limit()) {
+    THROW_NEW_ERROR_RETURN_FAILURE(
+        isolate, NewRangeError(MessageTemplate::kInvalidArrayLength));
+  }
+  return *visitor.ToArray();
+}
+
+
+MaybeHandle<JSArray> Fast_ArrayConcat(Isolate* isolate, Arguments* args) {
+  if (!isolate->IsFastArrayConstructorPrototypeChainIntact()) {
+    return MaybeHandle<JSArray>();
+  }
+  int n_arguments = args->length();
   int result_len = 0;
-  ElementsKind elements_kind = GetInitialFastElementsKind();
-  bool has_double = false;
   {
     DisallowHeapAllocation no_gc;
-    Context* native_context = isolate->context()->native_context();
-    Object* array_proto = native_context->array_function()->prototype();
-    PrototypeIterator iter(isolate, array_proto,
-                           PrototypeIterator::START_AT_RECEIVER);
-    if (!PrototypeHasNoElements(&iter)) {
-      AllowHeapAllocation allow_allocation;
-      return CallJsIntrinsic(isolate, isolate->array_concat(), args);
-    }
-
+    Object* array_proto = isolate->array_function()->prototype();
     // Iterate through all the arguments performing checks
     // and calculating total length.
-    bool is_holey = false;
     for (int i = 0; i < n_arguments; i++) {
-      Object* arg = args[i];
+      Object* arg = (*args)[i];
+      if (!arg->IsJSArray()) return MaybeHandle<JSArray>();
+      Handle<JSArray> array(JSArray::cast(arg), isolate);
+      if (!array->HasFastElements()) return MaybeHandle<JSArray>();
       PrototypeIterator iter(isolate, arg);
-      if (!arg->IsJSArray() || !JSArray::cast(arg)->HasFastElements() ||
-          iter.GetCurrent() != array_proto) {
-        AllowHeapAllocation allow_allocation;
-        return CallJsIntrinsic(isolate, isolate->array_concat(), args);
-      }
-      int len = Smi::cast(JSArray::cast(arg)->length())->value();
+      if (iter.GetCurrent() != array_proto) return MaybeHandle<JSArray>();
+      if (HasConcatSpreadableModifier(isolate, array)) {

[Camillo Bruni, 2015/09/04 13:54:55]

Needed for certain cases (see https://codereview.chromium.org/1247243003)

+        return MaybeHandle<JSArray>();
+      }
+      int len = Smi::cast(array->length())->value();
 
       // We shouldn't overflow when adding another len.
       const int kHalfOfMaxInt = 1 << (kBitsPerInt - 2);
       STATIC_ASSERT(FixedArray::kMaxLength < kHalfOfMaxInt);
       USE(kHalfOfMaxInt);
       result_len += len;
       DCHECK(result_len >= 0);
 
       if (result_len > FixedDoubleArray::kMaxLength) {
-        AllowHeapAllocation allow_allocation;
-        return CallJsIntrinsic(isolate, isolate->array_concat(), args);
-      }
-
-      ElementsKind arg_kind = JSArray::cast(arg)->map()->elements_kind();
-      has_double = has_double || IsFastDoubleElementsKind(arg_kind);
-      is_holey = is_holey || IsFastHoleyElementsKind(arg_kind);
-      if (IsMoreGeneralElementsKindTransition(elements_kind, arg_kind)) {
-        elements_kind = arg_kind;
+        isolate->Throw(*isolate->factory()->NewRangeError(
+            MessageTemplate::kInvalidArrayLength));
+        return MaybeHandle<JSArray>();
       }
     }
-    if (is_holey) elements_kind = GetHoleyElementsKind(elements_kind);
   }
+  return ElementsAccessor::Concat(isolate, args, n_arguments);
+}
 
-  // If a double array is concatted into a fast elements array, the fast
-  // elements array needs to be initialized to contain proper holes, since
-  // boxing doubles may cause incremental marking.
-  ArrayStorageAllocationMode mode =
-      has_double && IsFastObjectElementsKind(elements_kind)
-      ? INITIALIZE_ARRAY_ELEMENTS_WITH_HOLE : DONT_INITIALIZE_ARRAY_ELEMENTS;
-  Handle<JSArray> result_array = isolate->factory()->NewJSArray(
-      elements_kind, result_len, result_len, Strength::WEAK, mode);
-  if (result_len == 0) return *result_array;
+}  // namespace
 
-  int j = 0;
-  Handle<FixedArrayBase> storage(result_array->elements(), isolate);
-  ElementsAccessor* accessor = ElementsAccessor::ForKind(elements_kind);
-  for (int i = 0; i < n_arguments; i++) {
-    // It is crucial to keep |array| in a raw pointer form to avoid performance
-    // degradation.
-    JSArray* array = JSArray::cast(args[i]);
-    int len = Smi::cast(array->length())->value();
-    if (len > 0) {
-      ElementsKind from_kind = array->GetElementsKind();
-      accessor->CopyElements(array, 0, from_kind, storage, j, len);
-      j += len;
-    }
+BUILTIN(ArrayConcat) {
+  HandleScope scope(isolate);
+
+  Handle<Object> receiver;
+  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
+      isolate, receiver,
+      Execution::ToObject(isolate, handle(args[0], isolate)));
+  args[0] = *receiver;
+
+  Handle<JSArray> result_array;
+  if (Fast_ArrayConcat(isolate, &args).ToHandle(&result_array)) {
+    return *result_array;
   }
-
-  DCHECK(j == result_len);
-
-  return *result_array;
+  if (isolate->has_pending_exception()) return isolate->heap()->exception();
+  return Slow_ArrayConcat(&args, isolate);
 }
 
 
 // -----------------------------------------------------------------------------
 //
 
 
 // 20.3.4.45 Date.prototype [ @@toPrimitive ] ( hint )
 BUILTIN(DateToPrimitive) {
   HandleScope scope(isolate);
@@ skipping 615 matching lines @@
 BUILTIN_LIST_C(DEFINE_BUILTIN_ACCESSOR_C)
 BUILTIN_LIST_A(DEFINE_BUILTIN_ACCESSOR_A)
 BUILTIN_LIST_H(DEFINE_BUILTIN_ACCESSOR_H)
 BUILTIN_LIST_DEBUG_A(DEFINE_BUILTIN_ACCESSOR_A)
 #undef DEFINE_BUILTIN_ACCESSOR_C
 #undef DEFINE_BUILTIN_ACCESSOR_A
 
 
 }  // namespace internal
 }  // namespace v8