LCOV - code coverage report
Current view: top level - src/builtins - builtins-array.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 351 378 92.9 %
Date: 2017-04-26 Functions: 35 42 83.3 %

          Line data    Source code
       1             : // Copyright 2016 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/builtins/builtins.h"
       6             : #include "src/builtins/builtins-utils.h"
       7             : 
       8             : #include "src/code-factory.h"
       9             : #include "src/code-stub-assembler.h"
      10             : #include "src/contexts.h"
      11             : #include "src/counters.h"
      12             : #include "src/elements.h"
      13             : #include "src/isolate.h"
      14             : #include "src/lookup.h"
      15             : #include "src/objects-inl.h"
      16             : #include "src/prototype.h"
      17             : 
      18             : namespace v8 {
      19             : namespace internal {
      20             : 
      21             : namespace {
      22             : 
      23     1062838 : inline bool ClampedToInteger(Isolate* isolate, Object* object, int* out) {
      24             :   // This is an extended version of ECMA-262 7.1.11 handling signed values
      25             :   // Try to convert object to a number and clamp values to [kMinInt, kMaxInt]
      26     1062838 :   if (object->IsSmi()) {
      27     1059262 :     *out = Smi::cast(object)->value();
      28     1059262 :     return true;
      29        3576 :   } else if (object->IsHeapNumber()) {
      30             :     double value = HeapNumber::cast(object)->value();
      31        1450 :     if (std::isnan(value)) {
      32           0 :       *out = 0;
      33        1450 :     } else if (value > kMaxInt) {
      34         210 :       *out = kMaxInt;
      35        1240 :     } else if (value < kMinInt) {
      36         210 :       *out = kMinInt;
      37             :     } else {
      38        1030 :       *out = static_cast<int>(value);
      39             :     }
      40             :     return true;
      41        2126 :   } else if (object->IsNullOrUndefined(isolate)) {
      42         686 :     *out = 0;
      43         686 :     return true;
      44        1440 :   } else if (object->IsBoolean()) {
      45           0 :     *out = object->IsTrue(isolate);
      46           0 :     return true;
      47             :   }
      48             :   return false;
      49             : }
      50             : 
      51      420640 : inline bool GetSloppyArgumentsLength(Isolate* isolate, Handle<JSObject> object,
      52             :                                      int* out) {
      53      841280 :   Context* context = *isolate->native_context();
      54             :   Map* map = object->map();
      55      421251 :   if (map != context->sloppy_arguments_map() &&
      56      421153 :       map != context->strict_arguments_map() &&
      57             :       map != context->fast_aliased_arguments_map()) {
      58             :     return false;
      59             :   }
      60             :   DCHECK(object->HasFastElements() || object->HasFastArgumentsElements());
      61             :   Object* len_obj = object->InObjectPropertyAt(JSArgumentsObject::kLengthIndex);
      62      420363 :   if (!len_obj->IsSmi()) return false;
      63      420348 :   *out = Max(0, Smi::cast(len_obj)->value());
      64             : 
      65             :   FixedArray* parameters = FixedArray::cast(object->elements());
      66      420348 :   if (object->HasSloppyArgumentsElements()) {
      67             :     FixedArray* arguments = FixedArray::cast(parameters->get(1));
      68         442 :     return *out <= arguments->length();
      69             :   }
      70      840254 :   return *out <= parameters->length();
      71             : }
      72             : 
      73             : inline bool IsJSArrayFastElementMovingAllowed(Isolate* isolate,
      74             :                                               JSArray* receiver) {
      75     1450506 :   return JSObject::PrototypeHasNoElements(isolate, receiver);
      76             : }
      77             : 
      78      925634 : inline bool HasSimpleElements(JSObject* current) {
      79     1851253 :   return current->map()->instance_type() > LAST_CUSTOM_ELEMENTS_RECEIVER &&
      80     1851253 :          !current->GetElementsAccessor()->HasAccessors(current);
      81             : }
      82             : 
      83      893760 : inline bool HasOnlySimpleReceiverElements(Isolate* isolate,
      84             :                                           JSObject* receiver) {
      85             :   // Check that we have no accessors on the receiver's elements.
      86      893760 :   if (!HasSimpleElements(receiver)) return false;
      87      893550 :   return JSObject::PrototypeHasNoElements(isolate, receiver);
      88             : }
      89             : 
      90       10440 : inline bool HasOnlySimpleElements(Isolate* isolate, JSReceiver* receiver) {
      91             :   DisallowHeapAllocation no_gc;
      92             :   PrototypeIterator iter(isolate, receiver, kStartAtReceiver);
      93       31593 :   for (; !iter.IsAtEnd(); iter.Advance()) {
      94       63748 :     if (iter.GetCurrent()->IsJSProxy()) return false;
      95       31874 :     JSObject* current = iter.GetCurrent<JSObject>();
      96       31874 :     if (!HasSimpleElements(current)) return false;
      97             :   }
      98             :   return true;
      99             : }
     100             : 
     101             : // Returns |false| if not applicable.
     102             : MUST_USE_RESULT
     103     1110947 : inline bool EnsureJSArrayWithWritableFastElements(Isolate* isolate,
     104             :                                                   Handle<Object> receiver,
     105             :                                                   BuiltinArguments* args,
     106             :                                                   int first_added_arg) {
     107     1110947 :   if (!receiver->IsJSArray()) return false;
     108             :   Handle<JSArray> array = Handle<JSArray>::cast(receiver);
     109             :   ElementsKind origin_kind = array->GetElementsKind();
     110     1104280 :   if (IsDictionaryElementsKind(origin_kind)) return false;
     111     1101074 :   if (!array->map()->is_extensible()) return false;
     112     1101074 :   if (args == nullptr) return true;
     113             : 
     114             :   // If there may be elements accessors in the prototype chain, the fast path
     115             :   // cannot be used if there arguments to add to the array.
     116       28196 :   if (!IsJSArrayFastElementMovingAllowed(isolate, *array)) return false;
     117             : 
     118             :   // Adding elements to the array prototype would break code that makes sure
     119             :   // it has no elements. Handle that elsewhere.
     120       17859 :   if (isolate->IsAnyInitialArrayPrototype(array)) return false;
     121             : 
     122             :   // Need to ensure that the arguments passed in args can be contained in
     123             :   // the array.
     124             :   int args_length = args->length();
     125       17791 :   if (first_added_arg >= args_length) return true;
     126             : 
     127       10712 :   if (IsFastObjectElementsKind(origin_kind)) return true;
     128             :   ElementsKind target_kind = origin_kind;
     129             :   {
     130             :     DisallowHeapAllocation no_gc;
     131        9596 :     for (int i = first_added_arg; i < args_length; i++) {
     132       10229 :       Object* arg = (*args)[i];
     133       10229 :       if (arg->IsHeapObject()) {
     134         893 :         if (arg->IsHeapNumber()) {
     135             :           target_kind = FAST_DOUBLE_ELEMENTS;
     136             :         } else {
     137             :           target_kind = FAST_ELEMENTS;
     138             :           break;
     139             :         }
     140             :       }
     141             :     }
     142             :   }
     143        9660 :   if (target_kind != origin_kind) {
     144             :     // Use a short-lived HandleScope to avoid creating several copies of the
     145             :     // elements handle which would cause issues when left-trimming later-on.
     146             :     HandleScope scope(isolate);
     147         672 :     JSObject::TransitionElementsKind(array, target_kind);
     148             :   }
     149             :   return true;
     150             : }
     151             : 
     152       25021 : MUST_USE_RESULT static Object* CallJsIntrinsic(Isolate* isolate,
     153             :                                                Handle<JSFunction> function,
     154             :                                                BuiltinArguments args) {
     155             :   HandleScope handleScope(isolate);
     156       25021 :   int argc = args.length() - 1;
     157             :   ScopedVector<Handle<Object>> argv(argc);
     158       78849 :   for (int i = 0; i < argc; ++i) {
     159       57614 :     argv[i] = args.at(i + 1);
     160             :   }
     161       70236 :   RETURN_RESULT_OR_FAILURE(
     162             :       isolate,
     163             :       Execution::Call(isolate, function, args.receiver(), argc, argv.start()));
     164             : }
     165             : }  // namespace
     166             : 
     167       38154 : BUILTIN(ArrayPush) {
     168             :   HandleScope scope(isolate);
     169             :   Handle<Object> receiver = args.receiver();
     170       12718 :   if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, &args, 1)) {
     171       12523 :     return CallJsIntrinsic(isolate, isolate->array_push(), args);
     172             :   }
     173             :   // Fast Elements Path
     174         195 :   int to_add = args.length() - 1;
     175             :   Handle<JSArray> array = Handle<JSArray>::cast(receiver);
     176             :   int len = Smi::cast(array->length())->value();
     177         240 :   if (to_add == 0) return Smi::FromInt(len);
     178             : 
     179             :   // Currently fixed arrays cannot grow too big, so we should never hit this.
     180             :   DCHECK_LE(to_add, Smi::kMaxValue - Smi::cast(array->length())->value());
     181             : 
     182         150 :   if (JSArray::HasReadOnlyLength(array)) {
     183         120 :     return CallJsIntrinsic(isolate, isolate->array_push(), args);
     184             :   }
     185             : 
     186          30 :   ElementsAccessor* accessor = array->GetElementsAccessor();
     187          30 :   int new_length = accessor->Push(array, &args, to_add);
     188          30 :   return Smi::FromInt(new_length);
     189             : }
     190             : 
     191     2276991 : BUILTIN(ArrayPop) {
     192             :   HandleScope scope(isolate);
     193             :   Handle<Object> receiver = args.receiver();
     194      758997 :   if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, nullptr, 0)) {
     195        2966 :     return CallJsIntrinsic(isolate, isolate->array_pop(), args);
     196             :   }
     197             : 
     198             :   Handle<JSArray> array = Handle<JSArray>::cast(receiver);
     199             : 
     200      756031 :   uint32_t len = static_cast<uint32_t>(Smi::cast(array->length())->value());
     201      756031 :   if (len == 0) return isolate->heap()->undefined_value();
     202             : 
     203      755815 :   if (JSArray::HasReadOnlyLength(array)) {
     204         360 :     return CallJsIntrinsic(isolate, isolate->array_pop(), args);
     205             :   }
     206             : 
     207             :   Handle<Object> result;
     208      755455 :   if (IsJSArrayFastElementMovingAllowed(isolate, JSArray::cast(*receiver))) {
     209             :     // Fast Elements Path
     210      750387 :     result = array->GetElementsAccessor()->Pop(array);
     211             :   } else {
     212             :     // Use Slow Lookup otherwise
     213        5068 :     uint32_t new_length = len - 1;
     214       10136 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
     215             :         isolate, result, JSReceiver::GetElement(isolate, array, new_length));
     216        5068 :     JSArray::SetLength(array, new_length);
     217             :   }
     218      755455 :   return *result;
     219             : }
     220             : 
     221      956358 : BUILTIN(ArrayShift) {
     222             :   HandleScope scope(isolate);
     223         283 :   Heap* heap = isolate->heap();
     224             :   Handle<Object> receiver = args.receiver();
     225      635633 :   if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, nullptr, 0) ||
     226             :       !IsJSArrayFastElementMovingAllowed(isolate, JSArray::cast(*receiver))) {
     227        2280 :     return CallJsIntrinsic(isolate, isolate->array_shift(), args);
     228             :   }
     229             :   Handle<JSArray> array = Handle<JSArray>::cast(receiver);
     230             : 
     231             :   int len = Smi::cast(array->length())->value();
     232      316789 :   if (len == 0) return heap->undefined_value();
     233             : 
     234      316223 :   if (JSArray::HasReadOnlyLength(array)) {
     235         360 :     return CallJsIntrinsic(isolate, isolate->array_shift(), args);
     236             :   }
     237             : 
     238      315863 :   Handle<Object> first = array->GetElementsAccessor()->Shift(array);
     239      315863 :   return *first;
     240             : }
     241             : 
     242       32100 : BUILTIN(ArrayUnshift) {
     243             :   HandleScope scope(isolate);
     244             :   Handle<Object> receiver = args.receiver();
     245       10700 :   if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, &args, 1)) {
     246        1394 :     return CallJsIntrinsic(isolate, isolate->array_unshift(), args);
     247             :   }
     248             :   Handle<JSArray> array = Handle<JSArray>::cast(receiver);
     249        9306 :   int to_add = args.length() - 1;
     250        9341 :   if (to_add == 0) return array->length();
     251             : 
     252             :   // Currently fixed arrays cannot grow too big, so we should never hit this.
     253             :   DCHECK_LE(to_add, Smi::kMaxValue - Smi::cast(array->length())->value());
     254             : 
     255        9271 :   if (JSArray::HasReadOnlyLength(array)) {
     256         120 :     return CallJsIntrinsic(isolate, isolate->array_unshift(), args);
     257             :   }
     258             : 
     259        9151 :   ElementsAccessor* accessor = array->GetElementsAccessor();
     260        9151 :   int new_length = accessor->Unshift(array, &args, to_add);
     261        9151 :   return Smi::FromInt(new_length);
     262             : }
     263             : 
     264     2313288 : BUILTIN(ArraySlice) {
     265             :   HandleScope scope(isolate);
     266             :   Handle<Object> receiver = args.receiver();
     267      771096 :   int len = -1;
     268      771096 :   int relative_start = 0;
     269      771096 :   int relative_end = 0;
     270             : 
     271      771096 :   if (receiver->IsJSArray()) {
     272             :     DisallowHeapAllocation no_gc;
     273             :     JSArray* array = JSArray::cast(*receiver);
     274     1049965 :     if (V8_UNLIKELY(!array->HasFastElements() ||
     275             :                     !IsJSArrayFastElementMovingAllowed(isolate, array) ||
     276             :                     !isolate->IsArraySpeciesLookupChainIntact() ||
     277             :                     // If this is a subclass of Array, then call out to JS
     278             :                     !array->HasArrayPrototype(isolate))) {
     279             :       AllowHeapAllocation allow_allocation;
     280         517 :       return CallJsIntrinsic(isolate, isolate->array_slice(), args);
     281             :     }
     282      349565 :     len = Smi::cast(array->length())->value();
     283      841654 :   } else if (receiver->IsJSObject() &&
     284             :              GetSloppyArgumentsLength(isolate, Handle<JSObject>::cast(receiver),
     285      420640 :                                       &len)) {
     286             :     // Array.prototype.slice.call(arguments, ...) is quite a common idiom
     287             :     // (notably more than 50% of invocations in Web apps).
     288             :     // Treat it in C++ as well.
     289             :     DCHECK(JSObject::cast(*receiver)->HasFastElements() ||
     290             :            JSObject::cast(*receiver)->HasFastArgumentsElements());
     291             :   } else {
     292             :     AllowHeapAllocation allow_allocation;
     293         681 :     return CallJsIntrinsic(isolate, isolate->array_slice(), args);
     294             :   }
     295             :   DCHECK_LE(0, len);
     296      769898 :   int argument_count = args.length() - 1;
     297             :   // Note carefully chosen defaults---if argument is missing,
     298             :   // it's undefined which gets converted to 0 for relative_start
     299             :   // and to len for relative_end.
     300      769898 :   relative_start = 0;
     301      769898 :   relative_end = len;
     302      769898 :   if (argument_count > 0) {
     303             :     DisallowHeapAllocation no_gc;
     304      737090 :     if (!ClampedToInteger(isolate, args[1], &relative_start)) {
     305             :       AllowHeapAllocation allow_allocation;
     306         405 :       return CallJsIntrinsic(isolate, isolate->array_slice(), args);
     307             :     }
     308      736685 :     if (argument_count > 1) {
     309      312644 :       Object* end_arg = args[2];
     310             :       // slice handles the end_arg specially
     311      312644 :       if (end_arg->IsUndefined(isolate)) {
     312         105 :         relative_end = len;
     313      312539 :       } else if (!ClampedToInteger(isolate, end_arg, &relative_end)) {
     314             :         AllowHeapAllocation allow_allocation;
     315         105 :         return CallJsIntrinsic(isolate, isolate->array_slice(), args);
     316             :       }
     317             :     }
     318             :   }
     319             : 
     320             :   // ECMAScript 232, 3rd Edition, Section 15.4.4.10, step 6.
     321      769731 :   uint32_t actual_start = (relative_start < 0) ? Max(len + relative_start, 0)
     322     1538776 :                                                : Min(relative_start, len);
     323             : 
     324             :   // ECMAScript 232, 3rd Edition, Section 15.4.4.10, step 8.
     325             :   uint32_t actual_end =
     326     1538776 :       (relative_end < 0) ? Max(len + relative_end, 0) : Min(relative_end, len);
     327             : 
     328             :   Handle<JSObject> object = Handle<JSObject>::cast(receiver);
     329      769388 :   ElementsAccessor* accessor = object->GetElementsAccessor();
     330     1538776 :   return *accessor->Slice(object, actual_start, actual_end);
     331             : }
     332             : 
     333       29238 : BUILTIN(ArraySplice) {
     334             :   HandleScope scope(isolate);
     335             :   Handle<Object> receiver = args.receiver();
     336       26163 :   if (V8_UNLIKELY(
     337             :           !EnsureJSArrayWithWritableFastElements(isolate, receiver, &args, 3) ||
     338             :           // If this is a subclass of Array, then call out to JS.
     339             :           !Handle<JSArray>::cast(receiver)->HasArrayPrototype(isolate) ||
     340             :           // If anything with @@species has been messed with, call out to JS.
     341             :           !isolate->IsArraySpeciesLookupChainIntact())) {
     342        1780 :     return CallJsIntrinsic(isolate, isolate->array_splice(), args);
     343             :   }
     344             :   Handle<JSArray> array = Handle<JSArray>::cast(receiver);
     345             : 
     346        7966 :   int argument_count = args.length() - 1;
     347        7966 :   int relative_start = 0;
     348        7966 :   if (argument_count > 0) {
     349             :     DisallowHeapAllocation no_gc;
     350        7797 :     if (!ClampedToInteger(isolate, args[1], &relative_start)) {
     351             :       AllowHeapAllocation allow_allocation;
     352         720 :       return CallJsIntrinsic(isolate, isolate->array_splice(), args);
     353             :     }
     354             :   }
     355             :   int len = Smi::cast(array->length())->value();
     356             :   // clip relative start to [0, len]
     357        7890 :   int actual_start = (relative_start < 0) ? Max(len + relative_start, 0)
     358        7246 :                                           : Min(relative_start, len);
     359             : 
     360             :   int actual_delete_count;
     361        7246 :   if (argument_count == 1) {
     362             :     // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is
     363             :     // given as a request to delete all the elements from the start.
     364             :     // And it differs from the case of undefined delete count.
     365             :     // This does not follow ECMA-262, but we do the same for compatibility.
     366             :     DCHECK(len - actual_start >= 0);
     367        1665 :     actual_delete_count = len - actual_start;
     368             :   } else {
     369        5581 :     int delete_count = 0;
     370             :     DisallowHeapAllocation no_gc;
     371        5581 :     if (argument_count > 1) {
     372        5412 :       if (!ClampedToInteger(isolate, args[2], &delete_count)) {
     373             :         AllowHeapAllocation allow_allocation;
     374         210 :         return CallJsIntrinsic(isolate, isolate->array_splice(), args);
     375             :       }
     376             :     }
     377        5371 :     actual_delete_count = Min(Max(delete_count, 0), len - actual_start);
     378             :   }
     379             : 
     380        7036 :   int add_count = (argument_count > 1) ? (argument_count - 2) : 0;
     381        7036 :   int new_length = len - actual_delete_count + add_count;
     382             : 
     383        7036 :   if (new_length != len && JSArray::HasReadOnlyLength(array)) {
     384             :     AllowHeapAllocation allow_allocation;
     385         480 :     return CallJsIntrinsic(isolate, isolate->array_splice(), args);
     386             :   }
     387        6556 :   ElementsAccessor* accessor = array->GetElementsAccessor();
     388             :   Handle<JSArray> result_array = accessor->Splice(
     389        6556 :       array, actual_start, actual_delete_count, &args, add_count);
     390        6556 :   return *result_array;
     391             : }
     392             : 
     393             : // Array Concat -------------------------------------------------------------
     394             : 
     395             : namespace {
     396             : 
     397             : /**
     398             :  * A simple visitor visits every element of Array's.
     399             :  * The backend storage can be a fixed array for fast elements case,
     400             :  * or a dictionary for sparse array. Since Dictionary is a subtype
     401             :  * of FixedArray, the class can be used by both fast and slow cases.
     402             :  * The second parameter of the constructor, fast_elements, specifies
     403             :  * whether the storage is a FixedArray or Dictionary.
     404             :  *
     405             :  * An index limit is used to deal with the situation that a result array
     406             :  * length overflows 32-bit non-negative integer.
     407             :  */
     408             : class ArrayConcatVisitor {
     409             :  public:
     410       18520 :   ArrayConcatVisitor(Isolate* isolate, Handle<HeapObject> storage,
     411             :                      bool fast_elements)
     412             :       : isolate_(isolate),
     413             :         storage_(isolate->global_handles()->Create(*storage)),
     414             :         index_offset_(0u),
     415             :         bit_field_(
     416             :             FastElementsField::encode(fast_elements) |
     417        9260 :             ExceedsLimitField::encode(false) |
     418        9260 :             IsFixedArrayField::encode(storage->IsFixedArray()) |
     419        9673 :             HasSimpleElementsField::encode(storage->IsFixedArray() ||
     420         413 :                                            storage->map()->instance_type() >
     421       27780 :                                                LAST_CUSTOM_ELEMENTS_RECEIVER)) {
     422             :     DCHECK(!(this->fast_elements() && !is_fixed_array()));
     423        9260 :   }
     424             : 
     425             :   ~ArrayConcatVisitor() { clear_storage(); }
     426             : 
     427     4193650 :   MUST_USE_RESULT bool visit(uint32_t i, Handle<Object> elm) {
     428     2096855 :     uint32_t index = index_offset_ + i;
     429             : 
     430     2096855 :     if (i >= JSObject::kMaxElementCount - index_offset_) {
     431             :       set_exceeds_array_limit(true);
     432             :       // Exception hasn't been thrown at this point. Return true to
     433             :       // break out, and caller will throw. !visit would imply that
     434             :       // there is already a pending exception.
     435          60 :       return true;
     436             :     }
     437             : 
     438     2096795 :     if (!is_fixed_array()) {
     439         441 :       LookupIterator it(isolate_, storage_, index, LookupIterator::OWN);
     440         441 :       MAYBE_RETURN(
     441             :           JSReceiver::CreateDataProperty(&it, elm, Object::THROW_ON_ERROR),
     442             :           false);
     443         367 :       return true;
     444             :     }
     445             : 
     446     2096354 :     if (fast_elements()) {
     447     1510336 :       if (index < static_cast<uint32_t>(storage_fixed_array()->length())) {
     448     1510306 :         storage_fixed_array()->set(index, *elm);
     449     1510306 :         return true;
     450             :       }
     451             :       // Our initial estimate of length was foiled, possibly by
     452             :       // getters on the arrays increasing the length of later arrays
     453             :       // during iteration.
     454             :       // This shouldn't happen in anything but pathological cases.
     455          30 :       SetDictionaryMode();
     456             :       // Fall-through to dictionary mode.
     457             :     }
     458             :     DCHECK(!fast_elements());
     459             :     Handle<SeededNumberDictionary> dict(
     460             :         SeededNumberDictionary::cast(*storage_));
     461             :     // The object holding this backing store has just been allocated, so
     462             :     // it cannot yet be used as a prototype.
     463             :     Handle<JSObject> not_a_prototype_holder;
     464             :     Handle<SeededNumberDictionary> result = SeededNumberDictionary::AtNumberPut(
     465      586048 :         dict, index, elm, not_a_prototype_holder);
     466      586048 :     if (!result.is_identical_to(dict)) {
     467             :       // Dictionary needed to grow.
     468             :       clear_storage();
     469             :       set_storage(*result);
     470             :     }
     471             :     return true;
     472             :   }
     473             : 
     474     3036970 :   void increase_index_offset(uint32_t delta) {
     475     1518485 :     if (JSObject::kMaxElementCount - index_offset_ < delta) {
     476          75 :       index_offset_ = JSObject::kMaxElementCount;
     477             :     } else {
     478     1518410 :       index_offset_ += delta;
     479             :     }
     480             :     // If the initial length estimate was off (see special case in visit()),
     481             :     // but the array blowing the limit didn't contain elements beyond the
     482             :     // provided-for index range, go to dictionary mode now.
     483     3025407 :     if (fast_elements() &&
     484     3013844 :         index_offset_ >
     485             :             static_cast<uint32_t>(FixedArrayBase::cast(*storage_)->length())) {
     486          15 :       SetDictionaryMode();
     487             :     }
     488     1518485 :   }
     489             : 
     490             :   bool exceeds_array_limit() const {
     491             :     return ExceedsLimitField::decode(bit_field_);
     492             :   }
     493             : 
     494       17152 :   Handle<JSArray> ToArray() {
     495             :     DCHECK(is_fixed_array());
     496        8576 :     Handle<JSArray> array = isolate_->factory()->NewJSArray(0);
     497             :     Handle<Object> length =
     498        8576 :         isolate_->factory()->NewNumber(static_cast<double>(index_offset_));
     499             :     Handle<Map> map = JSObject::GetElementsTransitionMap(
     500       17152 :         array, fast_elements() ? FAST_HOLEY_ELEMENTS : DICTIONARY_ELEMENTS);
     501        8576 :     array->set_map(*map);
     502        8576 :     array->set_length(*length);
     503        8576 :     array->set_elements(*storage_fixed_array());
     504        8576 :     return array;
     505             :   }
     506             : 
     507             :   // Storage is either a FixedArray (if is_fixed_array()) or a JSReciever
     508             :   // (otherwise)
     509             :   Handle<FixedArray> storage_fixed_array() {
     510             :     DCHECK(is_fixed_array());
     511             :     DCHECK(has_simple_elements());
     512             :     return Handle<FixedArray>::cast(storage_);
     513             :   }
     514             :   Handle<JSReceiver> storage_jsreceiver() {
     515             :     DCHECK(!is_fixed_array());
     516             :     return Handle<JSReceiver>::cast(storage_);
     517             :   }
     518             :   bool has_simple_elements() const {
     519             :     return HasSimpleElementsField::decode(bit_field_);
     520             :   }
     521             : 
     522             :  private:
     523             :   // Convert storage to dictionary mode.
     524          45 :   void SetDictionaryMode() {
     525             :     DCHECK(fast_elements() && is_fixed_array());
     526             :     Handle<FixedArray> current_storage = storage_fixed_array();
     527             :     Handle<SeededNumberDictionary> slow_storage(
     528          45 :         SeededNumberDictionary::New(isolate_, current_storage->length()));
     529          45 :     uint32_t current_length = static_cast<uint32_t>(current_storage->length());
     530         810 :     FOR_WITH_HANDLE_SCOPE(
     531             :         isolate_, uint32_t, i = 0, i, i < current_length, i++, {
     532             :           Handle<Object> element(current_storage->get(i), isolate_);
     533             :           if (!element->IsTheHole(isolate_)) {
     534             :             // The object holding this backing store has just been allocated, so
     535             :             // it cannot yet be used as a prototype.
     536             :             Handle<JSObject> not_a_prototype_holder;
     537             :             Handle<SeededNumberDictionary> new_storage =
     538             :                 SeededNumberDictionary::AtNumberPut(slow_storage, i, element,
     539             :                                                     not_a_prototype_holder);
     540             :             if (!new_storage.is_identical_to(slow_storage)) {
     541             :               slow_storage = loop_scope.CloseAndEscape(new_storage);
     542             :             }
     543             :           }
     544             :         });
     545             :     clear_storage();
     546             :     set_storage(*slow_storage);
     547             :     set_fast_elements(false);
     548          45 :   }
     549             : 
     550       11915 :   inline void clear_storage() { GlobalHandles::Destroy(storage_.location()); }
     551             : 
     552             :   inline void set_storage(FixedArray* storage) {
     553             :     DCHECK(is_fixed_array());
     554             :     DCHECK(has_simple_elements());
     555        5310 :     storage_ = isolate_->global_handles()->Create(storage);
     556             :   }
     557             : 
     558             :   class FastElementsField : public BitField<bool, 0, 1> {};
     559             :   class ExceedsLimitField : public BitField<bool, 1, 1> {};
     560             :   class IsFixedArrayField : public BitField<bool, 2, 1> {};
     561             :   class HasSimpleElementsField : public BitField<bool, 3, 1> {};
     562             : 
     563             :   bool fast_elements() const { return FastElementsField::decode(bit_field_); }
     564             :   void set_fast_elements(bool fast) {
     565          90 :     bit_field_ = FastElementsField::update(bit_field_, fast);
     566             :   }
     567             :   void set_exceeds_array_limit(bool exceeds) {
     568         120 :     bit_field_ = ExceedsLimitField::update(bit_field_, exceeds);
     569             :   }
     570             :   bool is_fixed_array() const { return IsFixedArrayField::decode(bit_field_); }
     571             : 
     572             :   Isolate* isolate_;
     573             :   Handle<Object> storage_;  // Always a global handle.
     574             :   // Index after last seen index. Always less than or equal to
     575             :   // JSObject::kMaxElementCount.
     576             :   uint32_t index_offset_;
     577             :   uint32_t bit_field_;
     578             : };
     579             : 
     580       11498 : uint32_t EstimateElementCount(Handle<JSArray> array) {
     581             :   DisallowHeapAllocation no_gc;
     582       11498 :   uint32_t length = static_cast<uint32_t>(array->length()->Number());
     583             :   int element_count = 0;
     584       11498 :   switch (array->GetElementsKind()) {
     585             :     case FAST_SMI_ELEMENTS:
     586             :     case FAST_HOLEY_SMI_ELEMENTS:
     587             :     case FAST_ELEMENTS:
     588             :     case FAST_HOLEY_ELEMENTS: {
     589             :       // Fast elements can't have lengths that are not representable by
     590             :       // a 32-bit signed integer.
     591             :       DCHECK(static_cast<int32_t>(FixedArray::kMaxLength) >= 0);
     592       10510 :       int fast_length = static_cast<int>(length);
     593             :       Isolate* isolate = array->GetIsolate();
     594             :       FixedArray* elements = FixedArray::cast(array->elements());
     595       77400 :       for (int i = 0; i < fast_length; i++) {
     596       66890 :         if (!elements->get(i)->IsTheHole(isolate)) element_count++;
     597             :       }
     598             :       break;
     599             :     }
     600             :     case FAST_DOUBLE_ELEMENTS:
     601             :     case FAST_HOLEY_DOUBLE_ELEMENTS: {
     602             :       // Fast elements can't have lengths that are not representable by
     603             :       // a 32-bit signed integer.
     604             :       DCHECK(static_cast<int32_t>(FixedDoubleArray::kMaxLength) >= 0);
     605          90 :       int fast_length = static_cast<int>(length);
     606          90 :       if (array->elements()->IsFixedArray()) {
     607             :         DCHECK(FixedArray::cast(array->elements())->length() == 0);
     608             :         break;
     609             :       }
     610             :       FixedDoubleArray* elements = FixedDoubleArray::cast(array->elements());
     611        2040 :       for (int i = 0; i < fast_length; i++) {
     612        1965 :         if (!elements->is_the_hole(i)) element_count++;
     613             :       }
     614             :       break;
     615             :     }
     616             :     case DICTIONARY_ELEMENTS: {
     617             :       SeededNumberDictionary* dictionary =
     618             :           SeededNumberDictionary::cast(array->elements());
     619             :       Isolate* isolate = dictionary->GetIsolate();
     620             :       int capacity = dictionary->Capacity();
     621       19016 :       for (int i = 0; i < capacity; i++) {
     622             :         Object* key = dictionary->KeyAt(i);
     623       18118 :         if (dictionary->IsKey(isolate, key)) {
     624        7102 :           element_count++;
     625             :         }
     626             :       }
     627             :       break;
     628             :     }
     629             : #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) case TYPE##_ELEMENTS:
     630             : 
     631             :       TYPED_ARRAYS(TYPED_ARRAY_CASE)
     632             : #undef TYPED_ARRAY_CASE
     633             :       // External arrays are always dense.
     634           0 :       return length;
     635             :     case NO_ELEMENTS:
     636             :       return 0;
     637             :     case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
     638             :     case SLOW_SLOPPY_ARGUMENTS_ELEMENTS:
     639             :     case FAST_STRING_WRAPPER_ELEMENTS:
     640             :     case SLOW_STRING_WRAPPER_ELEMENTS:
     641           0 :       UNREACHABLE();
     642             :       return 0;
     643             :   }
     644             :   // As an estimate, we assume that the prototype doesn't contain any
     645             :   // inherited elements.
     646       11498 :   return element_count;
     647             : }
     648             : 
     649             : // Used for sorting indices in a List<uint32_t>.
     650        2111 : int compareUInt32(const uint32_t* ap, const uint32_t* bp) {
     651        2111 :   uint32_t a = *ap;
     652        2111 :   uint32_t b = *bp;
     653        2111 :   return (a == b) ? 0 : (a < b) ? -1 : 1;
     654             : }
     655             : 
     656        2381 : void CollectElementIndices(Handle<JSObject> object, uint32_t range,
     657             :                            List<uint32_t>* indices) {
     658             :   Isolate* isolate = object->GetIsolate();
     659             :   ElementsKind kind = object->GetElementsKind();
     660        2381 :   switch (kind) {
     661             :     case FAST_SMI_ELEMENTS:
     662             :     case FAST_ELEMENTS:
     663             :     case FAST_HOLEY_SMI_ELEMENTS:
     664             :     case FAST_HOLEY_ELEMENTS: {
     665             :       DisallowHeapAllocation no_gc;
     666             :       FixedArray* elements = FixedArray::cast(object->elements());
     667        1570 :       uint32_t length = static_cast<uint32_t>(elements->length());
     668        1570 :       if (range < length) length = range;
     669       66008 :       for (uint32_t i = 0; i < length; i++) {
     670      128876 :         if (!elements->get(i)->IsTheHole(isolate)) {
     671         290 :           indices->Add(i);
     672             :         }
     673             :       }
     674             :       break;
     675             :     }
     676             :     case FAST_HOLEY_DOUBLE_ELEMENTS:
     677             :     case FAST_DOUBLE_ELEMENTS: {
     678          15 :       if (object->elements()->IsFixedArray()) {
     679             :         DCHECK(object->elements()->length() == 0);
     680             :         break;
     681             :       }
     682             :       Handle<FixedDoubleArray> elements(
     683             :           FixedDoubleArray::cast(object->elements()));
     684          15 :       uint32_t length = static_cast<uint32_t>(elements->length());
     685          15 :       if (range < length) length = range;
     686          30 :       for (uint32_t i = 0; i < length; i++) {
     687          30 :         if (!elements->is_the_hole(i)) {
     688          15 :           indices->Add(i);
     689             :         }
     690             :       }
     691          15 :       break;
     692             :     }
     693             :     case DICTIONARY_ELEMENTS: {
     694             :       DisallowHeapAllocation no_gc;
     695             :       SeededNumberDictionary* dict =
     696             :           SeededNumberDictionary::cast(object->elements());
     697         706 :       uint32_t capacity = dict->Capacity();
     698        8844 :       FOR_WITH_HANDLE_SCOPE(isolate, uint32_t, j = 0, j, j < capacity, j++, {
     699             :         Object* k = dict->KeyAt(j);
     700             :         if (!dict->IsKey(isolate, k)) continue;
     701             :         DCHECK(k->IsNumber());
     702             :         uint32_t index = static_cast<uint32_t>(k->Number());
     703             :         if (index < range) {
     704             :           indices->Add(index);
     705             :         }
     706             :       });
     707             :       break;
     708             :     }
     709             : #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) case TYPE##_ELEMENTS:
     710             : 
     711             :       TYPED_ARRAYS(TYPED_ARRAY_CASE)
     712             : #undef TYPED_ARRAY_CASE
     713             :       {
     714             :         uint32_t length = static_cast<uint32_t>(
     715          15 :             FixedArrayBase::cast(object->elements())->length());
     716          15 :         if (range <= length) {
     717             :           length = range;
     718             :           // We will add all indices, so we might as well clear it first
     719             :           // and avoid duplicates.
     720             :           indices->Clear();
     721             :         }
     722          45 :         for (uint32_t i = 0; i < length; i++) {
     723          30 :           indices->Add(i);
     724             :         }
     725          15 :         if (length == range) return;  // All indices accounted for already.
     726             :         break;
     727             :       }
     728             :     case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
     729             :     case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: {
     730             :       DisallowHeapAllocation no_gc;
     731             :       FixedArrayBase* elements = object->elements();
     732             :       JSObject* raw_object = *object;
     733          75 :       ElementsAccessor* accessor = object->GetElementsAccessor();
     734      450120 :       for (uint32_t i = 0; i < range; i++) {
     735      450045 :         if (accessor->HasElement(raw_object, i, elements)) {
     736          90 :           indices->Add(i);
     737             :         }
     738             :       }
     739             :       break;
     740             :     }
     741             :     case FAST_STRING_WRAPPER_ELEMENTS:
     742             :     case SLOW_STRING_WRAPPER_ELEMENTS: {
     743             :       DCHECK(object->IsJSValue());
     744             :       Handle<JSValue> js_value = Handle<JSValue>::cast(object);
     745             :       DCHECK(js_value->value()->IsString());
     746             :       Handle<String> string(String::cast(js_value->value()), isolate);
     747           0 :       uint32_t length = static_cast<uint32_t>(string->length());
     748           0 :       uint32_t i = 0;
     749             :       uint32_t limit = Min(length, range);
     750           0 :       for (; i < limit; i++) {
     751           0 :         indices->Add(i);
     752             :       }
     753           0 :       ElementsAccessor* accessor = object->GetElementsAccessor();
     754           0 :       for (; i < range; i++) {
     755           0 :         if (accessor->HasElement(*object, i)) {
     756           0 :           indices->Add(i);
     757             :         }
     758             :       }
     759             :       break;
     760             :     }
     761             :     case NO_ELEMENTS:
     762             :       break;
     763             :   }
     764             : 
     765        2381 :   PrototypeIterator iter(isolate, object);
     766        2381 :   if (!iter.IsAtEnd()) {
     767             :     // The prototype will usually have no inherited element indices,
     768             :     // but we have to check.
     769             :     CollectElementIndices(PrototypeIterator::GetCurrent<JSObject>(iter), range,
     770        1675 :                           indices);
     771             :   }
     772             : }
     773             : 
     774        1727 : bool IterateElementsSlow(Isolate* isolate, Handle<JSReceiver> receiver,
     775             :                          uint32_t length, ArrayConcatVisitor* visitor) {
     776     5858053 :   FOR_WITH_HANDLE_SCOPE(isolate, uint32_t, i = 0, i, i < length, ++i, {
     777             :     Maybe<bool> maybe = JSReceiver::HasElement(receiver, i);
     778             :     if (!maybe.IsJust()) return false;
     779             :     if (maybe.FromJust()) {
     780             :       Handle<Object> element_value;
     781             :       ASSIGN_RETURN_ON_EXCEPTION_VALUE(
     782             :           isolate, element_value, JSReceiver::GetElement(isolate, receiver, i),
     783             :           false);
     784             :       if (!visitor->visit(i, element_value)) return false;
     785             :     }
     786             :   });
     787        1698 :   visitor->increase_index_offset(length);
     788        1698 :   return true;
     789             : }
     790             : /**
     791             :  * A helper function that visits "array" elements of a JSReceiver in numerical
     792             :  * order.
     793             :  *
     794             :  * The visitor argument called for each existing element in the array
     795             :  * with the element index and the element's value.
     796             :  * Afterwards it increments the base-index of the visitor by the array
     797             :  * length.
     798             :  * Returns false if any access threw an exception, otherwise true.
     799             :  */
     800       11984 : bool IterateElements(Isolate* isolate, Handle<JSReceiver> receiver,
     801       10159 :                      ArrayConcatVisitor* visitor) {
     802       11984 :   uint32_t length = 0;
     803             : 
     804       11984 :   if (receiver->IsJSArray()) {
     805             :     Handle<JSArray> array = Handle<JSArray>::cast(receiver);
     806       10440 :     length = static_cast<uint32_t>(array->length()->Number());
     807             :   } else {
     808             :     Handle<Object> val;
     809        3088 :     ASSIGN_RETURN_ON_EXCEPTION_VALUE(
     810             :         isolate, val, Object::GetLengthFromArrayLike(isolate, receiver), false);
     811             :     // TODO(caitp): Support larger element indexes (up to 2^53-1).
     812        1416 :     if (!val->ToUint32(&length)) {
     813           0 :       length = 0;
     814             :     }
     815             :     // TODO(cbruni): handle other element kind as well
     816        1416 :     return IterateElementsSlow(isolate, receiver, length, visitor);
     817             :   }
     818             : 
     819       20599 :   if (!HasOnlySimpleElements(isolate, *receiver) ||
     820             :       !visitor->has_simple_elements()) {
     821         311 :     return IterateElementsSlow(isolate, receiver, length, visitor);
     822             :   }
     823             :   Handle<JSObject> array = Handle<JSObject>::cast(receiver);
     824             : 
     825       10129 :   switch (array->GetElementsKind()) {
     826             :     case FAST_SMI_ELEMENTS:
     827             :     case FAST_ELEMENTS:
     828             :     case FAST_HOLEY_SMI_ELEMENTS:
     829             :     case FAST_HOLEY_ELEMENTS: {
     830             :       // Run through the elements FixedArray and use HasElement and GetElement
     831             :       // to check the prototype for missing elements.
     832             :       Handle<FixedArray> elements(FixedArray::cast(array->elements()));
     833        9378 :       int fast_length = static_cast<int>(length);
     834             :       DCHECK(fast_length <= elements->length());
     835      279232 :       FOR_WITH_HANDLE_SCOPE(isolate, int, j = 0, j, j < fast_length, j++, {
     836             :         Handle<Object> element_value(elements->get(j), isolate);
     837             :         if (!element_value->IsTheHole(isolate)) {
     838             :           if (!visitor->visit(j, element_value)) return false;
     839             :         } else {
     840             :           Maybe<bool> maybe = JSReceiver::HasElement(array, j);
     841             :           if (!maybe.IsJust()) return false;
     842             :           if (maybe.FromJust()) {
     843             :             // Call GetElement on array, not its prototype, or getters won't
     844             :             // have the correct receiver.
     845             :             ASSIGN_RETURN_ON_EXCEPTION_VALUE(
     846             :                 isolate, element_value,
     847             :                 JSReceiver::GetElement(isolate, array, j), false);
     848             :             if (!visitor->visit(j, element_value)) return false;
     849             :           }
     850             :         }
     851             :       });
     852             :       break;
     853             :     }
     854             :     case FAST_HOLEY_DOUBLE_ELEMENTS:
     855             :     case FAST_DOUBLE_ELEMENTS: {
     856             :       // Empty array is FixedArray but not FixedDoubleArray.
     857          45 :       if (length == 0) break;
     858             :       // Run through the elements FixedArray and use HasElement and GetElement
     859             :       // to check the prototype for missing elements.
     860          30 :       if (array->elements()->IsFixedArray()) {
     861             :         DCHECK(array->elements()->length() == 0);
     862             :         break;
     863             :       }
     864             :       Handle<FixedDoubleArray> elements(
     865             :           FixedDoubleArray::cast(array->elements()));
     866          30 :       int fast_length = static_cast<int>(length);
     867             :       DCHECK(fast_length <= elements->length());
     868         465 :       FOR_WITH_HANDLE_SCOPE(isolate, int, j = 0, j, j < fast_length, j++, {
     869             :         if (!elements->is_the_hole(j)) {
     870             :           double double_value = elements->get_scalar(j);
     871             :           Handle<Object> element_value =
     872             :               isolate->factory()->NewNumber(double_value);
     873             :           if (!visitor->visit(j, element_value)) return false;
     874             :         } else {
     875             :           Maybe<bool> maybe = JSReceiver::HasElement(array, j);
     876             :           if (!maybe.IsJust()) return false;
     877             :           if (maybe.FromJust()) {
     878             :             // Call GetElement on array, not its prototype, or getters won't
     879             :             // have the correct receiver.
     880             :             Handle<Object> element_value;
     881             :             ASSIGN_RETURN_ON_EXCEPTION_VALUE(
     882             :                 isolate, element_value,
     883             :                 JSReceiver::GetElement(isolate, array, j), false);
     884             :             if (!visitor->visit(j, element_value)) return false;
     885             :           }
     886             :         }
     887             :       });
     888             :       break;
     889             :     }
     890             : 
     891             :     case DICTIONARY_ELEMENTS: {
     892             :       Handle<SeededNumberDictionary> dict(array->element_dictionary());
     893         706 :       List<uint32_t> indices(dict->Capacity() / 2);
     894             :       // Collect all indices in the object and the prototypes less
     895             :       // than length. This might introduce duplicates in the indices list.
     896         706 :       CollectElementIndices(array, length, &indices);
     897             :       indices.Sort(&compareUInt32);
     898         706 :       int n = indices.length();
     899       10688 :       FOR_WITH_HANDLE_SCOPE(isolate, int, j = 0, j, j < n, (void)0, {
     900             :         uint32_t index = indices[j];
     901             :         Handle<Object> element;
     902             :         ASSIGN_RETURN_ON_EXCEPTION_VALUE(
     903             :             isolate, element, JSReceiver::GetElement(isolate, array, index),
     904             :             false);
     905             :         if (!visitor->visit(index, element)) return false;
     906             :         // Skip to next different index (i.e., omit duplicates).
     907             :         do {
     908             :           j++;
     909             :         } while (j < n && indices[j] == index);
     910             :       });
     911             :       break;
     912             :     }
     913             :     case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
     914             :     case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: {
     915           0 :       FOR_WITH_HANDLE_SCOPE(
     916             :           isolate, uint32_t, index = 0, index, index < length, index++, {
     917             :             Handle<Object> element;
     918             :             ASSIGN_RETURN_ON_EXCEPTION_VALUE(
     919             :                 isolate, element, JSReceiver::GetElement(isolate, array, index),
     920             :                 false);
     921             :             if (!visitor->visit(index, element)) return false;
     922             :           });
     923             :       break;
     924             :     }
     925             :     case NO_ELEMENTS:
     926             :       break;
     927             : #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) case TYPE##_ELEMENTS:
     928             :       TYPED_ARRAYS(TYPED_ARRAY_CASE)
     929             : #undef TYPED_ARRAY_CASE
     930           0 :       return IterateElementsSlow(isolate, receiver, length, visitor);
     931             :     case FAST_STRING_WRAPPER_ELEMENTS:
     932             :     case SLOW_STRING_WRAPPER_ELEMENTS:
     933             :       // |array| is guaranteed to be an array or typed array.
     934           0 :       UNREACHABLE();
     935             :       break;
     936             :   }
     937       10070 :   visitor->increase_index_offset(length);
     938       10070 :   return true;
     939             : }
     940             : 
     941     1518785 : static Maybe<bool> IsConcatSpreadable(Isolate* isolate, Handle<Object> obj) {
     942             :   HandleScope handle_scope(isolate);
     943     1518785 :   if (!obj->IsJSReceiver()) return Just(false);
     944       15729 :   if (!isolate->IsIsConcatSpreadableLookupChainIntact(JSReceiver::cast(*obj))) {
     945             :     // Slow path if @@isConcatSpreadable has been used.
     946             :     Handle<Symbol> key(isolate->factory()->is_concat_spreadable_symbol());
     947             :     Handle<Object> value;
     948             :     MaybeHandle<Object> maybeValue =
     949        9627 :         i::Runtime::GetObjectProperty(isolate, obj, key);
     950        9627 :     if (!maybeValue.ToHandle(&value)) return Nothing<bool>();
     951       13220 :     if (!value->IsUndefined(isolate)) return Just(value->BooleanValue());
     952             :   }
     953       12024 :   return Object::IsArray(obj);
     954             : }
     955             : 
     956        9275 : Object* Slow_ArrayConcat(BuiltinArguments* args, Handle<Object> species,
     957        9275 :                          Isolate* isolate) {
     958             :   int argument_count = args->length();
     959             : 
     960        9275 :   bool is_array_species = *species == isolate->context()->array_function();
     961             : 
     962             :   // Pass 1: estimate the length and number of elements of the result.
     963             :   // The actual length can be larger if any of the arguments have getters
     964             :   // that mutate other arguments (but will otherwise be precise).
     965             :   // The number of elements is precise if there are no inherited elements.
     966             : 
     967             :   ElementsKind kind = FAST_SMI_ELEMENTS;
     968             : 
     969             :   uint32_t estimate_result_length = 0;
     970             :   uint32_t estimate_nof_elements = 0;
     971     7623919 :   FOR_WITH_HANDLE_SCOPE(isolate, int, i = 0, i, i < argument_count, i++, {
     972             :     Handle<Object> obj((*args)[i], isolate);
     973             :     uint32_t length_estimate;
     974             :     uint32_t element_estimate;
     975             :     if (obj->IsJSArray()) {
     976             :       Handle<JSArray> array(Handle<JSArray>::cast(obj));
     977             :       length_estimate = static_cast<uint32_t>(array->length()->Number());
     978             :       if (length_estimate != 0) {
     979             :         ElementsKind array_kind =
     980             :             GetPackedElementsKind(array->GetElementsKind());
     981             :         kind = GetMoreGeneralElementsKind(kind, array_kind);
     982             :       }
     983             :       element_estimate = EstimateElementCount(array);
     984             :     } else {
     985             :       if (obj->IsHeapObject()) {
     986             :         kind = GetMoreGeneralElementsKind(
     987             :             kind, obj->IsNumber() ? FAST_DOUBLE_ELEMENTS : FAST_ELEMENTS);
     988             :       }
     989             :       length_estimate = 1;
     990             :       element_estimate = 1;
     991             :     }
     992             :     // Avoid overflows by capping at kMaxElementCount.
     993             :     if (JSObject::kMaxElementCount - estimate_result_length < length_estimate) {
     994             :       estimate_result_length = JSObject::kMaxElementCount;
     995             :     } else {
     996             :       estimate_result_length += length_estimate;
     997             :     }
     998             :     if (JSObject::kMaxElementCount - estimate_nof_elements < element_estimate) {
     999             :       estimate_nof_elements = JSObject::kMaxElementCount;
    1000             :     } else {
    1001             :       estimate_nof_elements += element_estimate;
    1002             :     }
    1003             :   });
    1004             : 
    1005             :   // If estimated number of elements is more than half of length, a
    1006             :   // fixed array (fast case) is more time and space-efficient than a
    1007             :   // dictionary.
    1008        8862 :   bool fast_case = is_array_species &&
    1009       17074 :                    (estimate_nof_elements * 2) >= estimate_result_length &&
    1010        7799 :                    isolate->IsIsConcatSpreadableLookupChainIntact();
    1011             : 
    1012        9275 :   if (fast_case && kind == FAST_DOUBLE_ELEMENTS) {
    1013             :     Handle<FixedArrayBase> storage =
    1014          30 :         isolate->factory()->NewFixedDoubleArray(estimate_result_length);
    1015             :     int j = 0;
    1016             :     bool failure = false;
    1017          30 :     if (estimate_result_length > 0) {
    1018             :       Handle<FixedDoubleArray> double_storage =
    1019             :           Handle<FixedDoubleArray>::cast(storage);
    1020          60 :       for (int i = 0; i < argument_count; i++) {
    1021          45 :         Handle<Object> obj((*args)[i], isolate);
    1022          45 :         if (obj->IsSmi()) {
    1023           0 :           double_storage->set(j, Smi::cast(*obj)->value());
    1024           0 :           j++;
    1025          45 :         } else if (obj->IsNumber()) {
    1026             :           double_storage->set(j, obj->Number());
    1027          15 :           j++;
    1028             :         } else {
    1029             :           DisallowHeapAllocation no_gc;
    1030             :           JSArray* array = JSArray::cast(*obj);
    1031          30 :           uint32_t length = static_cast<uint32_t>(array->length()->Number());
    1032          30 :           switch (array->GetElementsKind()) {
    1033             :             case FAST_HOLEY_DOUBLE_ELEMENTS:
    1034             :             case FAST_DOUBLE_ELEMENTS: {
    1035             :               // Empty array is FixedArray but not FixedDoubleArray.
    1036          15 :               if (length == 0) break;
    1037             :               FixedDoubleArray* elements =
    1038             :                   FixedDoubleArray::cast(array->elements());
    1039          15 :               for (uint32_t i = 0; i < length; i++) {
    1040          30 :                 if (elements->is_the_hole(i)) {
    1041             :                   // TODO(jkummerow/verwaest): We could be a bit more clever
    1042             :                   // here: Check if there are no elements/getters on the
    1043             :                   // prototype chain, and if so, allow creation of a holey
    1044             :                   // result array.
    1045             :                   // Same thing below (holey smi case).
    1046             :                   failure = true;
    1047             :                   break;
    1048             :                 }
    1049             :                 double double_value = elements->get_scalar(i);
    1050             :                 double_storage->set(j, double_value);
    1051           0 :                 j++;
    1052             :               }
    1053             :               break;
    1054             :             }
    1055             :             case FAST_HOLEY_SMI_ELEMENTS:
    1056             :             case FAST_SMI_ELEMENTS: {
    1057           0 :               Object* the_hole = isolate->heap()->the_hole_value();
    1058             :               FixedArray* elements(FixedArray::cast(array->elements()));
    1059           0 :               for (uint32_t i = 0; i < length; i++) {
    1060           0 :                 Object* element = elements->get(i);
    1061           0 :                 if (element == the_hole) {
    1062             :                   failure = true;
    1063             :                   break;
    1064             :                 }
    1065             :                 int32_t int_value = Smi::cast(element)->value();
    1066           0 :                 double_storage->set(j, int_value);
    1067           0 :                 j++;
    1068             :               }
    1069             :               break;
    1070             :             }
    1071             :             case FAST_HOLEY_ELEMENTS:
    1072             :             case FAST_ELEMENTS:
    1073             :             case DICTIONARY_ELEMENTS:
    1074             :             case NO_ELEMENTS:
    1075             :               DCHECK_EQ(0u, length);
    1076             :               break;
    1077             :             default:
    1078           0 :               UNREACHABLE();
    1079             :           }
    1080             :         }
    1081          45 :         if (failure) break;
    1082             :       }
    1083             :     }
    1084          30 :     if (!failure) {
    1085          30 :       return *isolate->factory()->NewJSArrayWithElements(storage, kind, j);
    1086             :     }
    1087             :     // In case of failure, fall through.
    1088             :   }
    1089             : 
    1090             :   Handle<HeapObject> storage;
    1091        9260 :   if (fast_case) {
    1092             :     // The backing storage array must have non-existing elements to preserve
    1093             :     // holes across concat operations.
    1094             :     storage =
    1095        3489 :         isolate->factory()->NewFixedArrayWithHoles(estimate_result_length);
    1096        5771 :   } else if (is_array_species) {
    1097             :     // TODO(126): move 25% pre-allocation logic into Dictionary::Allocate
    1098             :     uint32_t at_least_space_for =
    1099        5358 :         estimate_nof_elements + (estimate_nof_elements >> 2);
    1100        5358 :     storage = SeededNumberDictionary::New(isolate, at_least_space_for);
    1101             :   } else {
    1102             :     DCHECK(species->IsConstructor());
    1103             :     Handle<Object> length(Smi::kZero, isolate);
    1104             :     Handle<Object> storage_object;
    1105         826 :     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1106             :         isolate, storage_object,
    1107             :         Execution::New(isolate, species, species, 1, &length));
    1108         413 :     storage = Handle<HeapObject>::cast(storage_object);
    1109             :   }
    1110             : 
    1111        9260 :   ArrayConcatVisitor visitor(isolate, storage, fast_case);
    1112             : 
    1113     1527745 :   for (int i = 0; i < argument_count; i++) {
    1114     1518785 :     Handle<Object> obj((*args)[i], isolate);
    1115     1518785 :     Maybe<bool> spreadable = IsConcatSpreadable(isolate, obj);
    1116     1519085 :     MAYBE_RETURN(spreadable, isolate->heap()->exception());
    1117     1518701 :     if (spreadable.FromJust()) {
    1118       11984 :       Handle<JSReceiver> object = Handle<JSReceiver>::cast(obj);
    1119       11984 :       if (!IterateElements(isolate, object, &visitor)) {
    1120         216 :         return isolate->heap()->exception();
    1121             :       }
    1122             :     } else {
    1123     1506717 :       if (!visitor.visit(0, obj)) return isolate->heap()->exception();
    1124     1506717 :       visitor.increase_index_offset(1);
    1125             :     }
    1126             :   }
    1127             : 
    1128       17920 :   if (visitor.exceeds_array_limit()) {
    1129         120 :     THROW_NEW_ERROR_RETURN_FAILURE(
    1130             :         isolate, NewRangeError(MessageTemplate::kInvalidArrayLength));
    1131             :   }
    1132             : 
    1133        8900 :   if (is_array_species) {
    1134       17152 :     return *visitor.ToArray();
    1135             :   } else {
    1136             :     return *visitor.storage_jsreceiver();
    1137             :   }
    1138             : }
    1139             : 
    1140      892199 : bool IsSimpleArray(Isolate* isolate, Handle<JSArray> obj) {
    1141             :   DisallowHeapAllocation no_gc;
    1142             :   Map* map = obj->map();
    1143             :   // If there is only the 'length' property we are fine.
    1144      892199 :   if (map->prototype() ==
    1145     2676511 :           isolate->native_context()->initial_array_prototype() &&
    1146             :       map->NumberOfOwnDescriptors() == 1) {
    1147             :     return true;
    1148             :   }
    1149             :   // TODO(cbruni): slower lookup for array subclasses and support slow
    1150             :   // @@IsConcatSpreadable lookup.
    1151          86 :   return false;
    1152             : }
    1153             : 
    1154      458382 : MaybeHandle<JSArray> Fast_ArrayConcat(Isolate* isolate,
    1155             :                                       BuiltinArguments* args) {
    1156      458382 :   if (!isolate->IsIsConcatSpreadableLookupChainIntact()) {
    1157             :     return MaybeHandle<JSArray>();
    1158             :   }
    1159             :   // We shouldn't overflow when adding another len.
    1160             :   const int kHalfOfMaxInt = 1 << (kBitsPerInt - 2);
    1161             :   STATIC_ASSERT(FixedArray::kMaxLength < kHalfOfMaxInt);
    1162             :   STATIC_ASSERT(FixedDoubleArray::kMaxLength < kHalfOfMaxInt);
    1163             :   USE(kHalfOfMaxInt);
    1164             : 
    1165             :   int n_arguments = args->length();
    1166             :   int result_len = 0;
    1167             :   {
    1168             :     DisallowHeapAllocation no_gc;
    1169             :     // Iterate through all the arguments performing checks
    1170             :     // and calculating total length.
    1171     1342412 :     for (int i = 0; i < n_arguments; i++) {
    1172      899955 :       Object* arg = (*args)[i];
    1173      899955 :       if (!arg->IsJSArray()) return MaybeHandle<JSArray>();
    1174      893760 :       if (!HasOnlySimpleReceiverElements(isolate, JSObject::cast(arg))) {
    1175             :         return MaybeHandle<JSArray>();
    1176             :       }
    1177             :       // TODO(cbruni): support fast concatenation of DICTIONARY_ELEMENTS.
    1178      892379 :       if (!JSObject::cast(arg)->HasFastElements()) {
    1179             :         return MaybeHandle<JSArray>();
    1180             :       }
    1181             :       Handle<JSArray> array(JSArray::cast(arg), isolate);
    1182      892199 :       if (!IsSimpleArray(isolate, array)) {
    1183             :         return MaybeHandle<JSArray>();
    1184             :       }
    1185             :       // The Array length is guaranted to be <= kHalfOfMaxInt thus we won't
    1186             :       // overflow.
    1187      892113 :       result_len += Smi::cast(array->length())->value();
    1188             :       DCHECK(result_len >= 0);
    1189             :       // Throw an Error if we overflow the FixedArray limits
    1190      892113 :       if (FixedDoubleArray::kMaxLength < result_len ||
    1191             :           FixedArray::kMaxLength < result_len) {
    1192             :         AllowHeapAllocation gc;
    1193          30 :         THROW_NEW_ERROR(isolate,
    1194             :                         NewRangeError(MessageTemplate::kInvalidArrayLength),
    1195             :                         JSArray);
    1196             :       }
    1197             :     }
    1198             :   }
    1199      442457 :   return ElementsAccessor::Concat(isolate, args, n_arguments, result_len);
    1200             : }
    1201             : 
    1202             : }  // namespace
    1203             : 
    1204             : // ES6 22.1.3.1 Array.prototype.concat
    1205     1356543 : BUILTIN(ArrayConcat) {
    1206             :   HandleScope scope(isolate);
    1207             : 
    1208             :   Handle<Object> receiver = args.receiver();
    1209      904362 :   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1210             :       isolate, receiver,
    1211             :       Object::ToObject(isolate, args.receiver(), "Array.prototype.concat"));
    1212      451747 :   args[0] = *receiver;
    1213             : 
    1214             :   Handle<JSArray> result_array;
    1215             : 
    1216             :   // Avoid a real species read to avoid extra lookups to the array constructor
    1217     1351963 :   if (V8_LIKELY(receiver->IsJSArray() &&
    1218             :                 Handle<JSArray>::cast(receiver)->HasArrayPrototype(isolate) &&
    1219             :                 isolate->IsArraySpeciesLookupChainIntact())) {
    1220      898848 :     if (Fast_ArrayConcat(isolate, &args).ToHandle(&result_array)) {
    1221      442361 :       return *result_array;
    1222             :     }
    1223        7063 :     if (isolate->has_pending_exception()) return isolate->heap()->exception();
    1224             :   }
    1225             :   // Reading @@species happens before anything else with a side effect, so
    1226             :   // we can do it here to determine whether to take the fast path.
    1227             :   Handle<Object> species;
    1228       18742 :   ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
    1229             :       isolate, species, Object::ArraySpeciesConstructor(isolate, receiver));
    1230       18742 :   if (*species == *isolate->array_function()) {
    1231       17916 :     if (Fast_ArrayConcat(isolate, &args).ToHandle(&result_array)) {
    1232          96 :       return *result_array;
    1233             :     }
    1234        8862 :     if (isolate->has_pending_exception()) return isolate->heap()->exception();
    1235             :   }
    1236        9275 :   return Slow_ArrayConcat(&args, species, isolate);
    1237             : }
    1238             : 
    1239             : }  // namespace internal
    1240             : }  // namespace v8

Generated by: LCOV version 1.10