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
|