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-utils-inl.h"
6 : #include "src/builtins/builtins.h"
7 : #include "src/code-factory.h"
8 : #include "src/contexts.h"
9 : #include "src/counters.h"
10 : #include "src/debug/debug.h"
11 : #include "src/elements-inl.h"
12 : #include "src/global-handles.h"
13 : #include "src/isolate.h"
14 : #include "src/lookup.h"
15 : #include "src/objects-inl.h"
16 : #include "src/objects/hash-table-inl.h"
17 : #include "src/objects/js-array-inl.h"
18 : #include "src/objects/smi.h"
19 : #include "src/prototype.h"
20 :
21 : namespace v8 {
22 : namespace internal {
23 :
24 : namespace {
25 :
26 : inline bool IsJSArrayFastElementMovingAllowed(Isolate* isolate,
27 : JSArray receiver) {
28 1162305 : return JSObject::PrototypeHasNoElements(isolate, receiver);
29 : }
30 :
31 596200 : inline bool HasSimpleElements(JSObject current) {
32 1192391 : return !current->map()->IsCustomElementsReceiverMap() &&
33 1192391 : !current->GetElementsAccessor()->HasAccessors(current);
34 : }
35 :
36 575071 : inline bool HasOnlySimpleReceiverElements(Isolate* isolate, JSObject receiver) {
37 : // Check that we have no accessors on the receiver's elements.
38 575071 : if (!HasSimpleElements(receiver)) return false;
39 574891 : return JSObject::PrototypeHasNoElements(isolate, receiver);
40 : }
41 :
42 6911 : inline bool HasOnlySimpleElements(Isolate* isolate, JSReceiver receiver) {
43 : DisallowHeapAllocation no_gc;
44 : PrototypeIterator iter(isolate, receiver, kStartAtReceiver);
45 48773 : for (; !iter.IsAtEnd(); iter.Advance()) {
46 21327 : if (iter.GetCurrent()->IsJSProxy()) return false;
47 21129 : JSObject current = iter.GetCurrent<JSObject>();
48 21129 : if (!HasSimpleElements(current)) return false;
49 : }
50 : return true;
51 : }
52 :
53 : // This method may transition the elements kind of the JSArray once, to make
54 : // sure that all elements provided as arguments in the specified range can be
55 : // added without further elements kinds transitions.
56 920045 : void MatchArrayElementsKindToArguments(Isolate* isolate, Handle<JSArray> array,
57 : BuiltinArguments* args,
58 : int first_arg_index, int num_arguments) {
59 920045 : int args_length = args->length();
60 921454 : if (first_arg_index >= args_length) return;
61 :
62 : ElementsKind origin_kind = array->GetElementsKind();
63 :
64 : // We do not need to transition for PACKED/HOLEY_ELEMENTS.
65 919899 : if (IsObjectElementsKind(origin_kind)) return;
66 :
67 : ElementsKind target_kind = origin_kind;
68 : {
69 : DisallowHeapAllocation no_gc;
70 1837272 : int last_arg_index = std::min(first_arg_index + num_arguments, args_length);
71 2754784 : for (int i = first_arg_index; i < last_arg_index; i++) {
72 : Object arg = (*args)[i];
73 918700 : if (arg->IsHeapObject()) {
74 827 : if (arg->IsHeapNumber()) {
75 : target_kind = PACKED_DOUBLE_ELEMENTS;
76 : } else {
77 : target_kind = PACKED_ELEMENTS;
78 : break;
79 : }
80 : }
81 : }
82 : }
83 918636 : if (target_kind != origin_kind) {
84 : // Use a short-lived HandleScope to avoid creating several copies of the
85 : // elements handle which would cause issues when left-trimming later-on.
86 : HandleScope scope(isolate);
87 1498 : JSObject::TransitionElementsKind(array, target_kind);
88 : }
89 : }
90 :
91 : // Returns |false| if not applicable.
92 : // TODO(szuend): Refactor this function because it is getting hard to
93 : // understand what each call-site actually checks.
94 : V8_WARN_UNUSED_RESULT
95 1168043 : inline bool EnsureJSArrayWithWritableFastElements(Isolate* isolate,
96 : Handle<Object> receiver,
97 : BuiltinArguments* args,
98 : int first_arg_index,
99 : int num_arguments) {
100 1168043 : if (!receiver->IsJSArray()) return false;
101 : Handle<JSArray> array = Handle<JSArray>::cast(receiver);
102 : ElementsKind origin_kind = array->GetElementsKind();
103 1164920 : if (IsDictionaryElementsKind(origin_kind)) return false;
104 1162652 : if (!array->map()->is_extensible()) return false;
105 1162586 : if (args == nullptr) return true;
106 :
107 : // If there may be elements accessors in the prototype chain, the fast path
108 : // cannot be used if there arguments to add to the array.
109 919928 : if (!IsJSArrayFastElementMovingAllowed(isolate, *array)) return false;
110 :
111 : // Adding elements to the array prototype would break code that makes sure
112 : // it has no elements. Handle that elsewhere.
113 914459 : if (isolate->IsAnyInitialArrayPrototype(array)) return false;
114 :
115 : // Need to ensure that the arguments passed in args can be contained in
116 : // the array.
117 : MatchArrayElementsKindToArguments(isolate, array, args, first_arg_index,
118 914150 : num_arguments);
119 914150 : return true;
120 : }
121 :
122 : // If |index| is Undefined, returns init_if_undefined.
123 : // If |index| is negative, returns length + index.
124 : // If |index| is positive, returns index.
125 : // Returned value is guaranteed to be in the interval of [0, length].
126 15080 : V8_WARN_UNUSED_RESULT Maybe<double> GetRelativeIndex(Isolate* isolate,
127 : double length,
128 : Handle<Object> index,
129 : double init_if_undefined) {
130 15080 : double relative_index = init_if_undefined;
131 15080 : if (!index->IsUndefined()) {
132 : Handle<Object> relative_index_obj;
133 639 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, relative_index_obj,
134 : Object::ToInteger(isolate, index),
135 : Nothing<double>());
136 639 : relative_index = relative_index_obj->Number();
137 : }
138 :
139 15080 : if (relative_index < 0) {
140 144 : return Just(std::max(length + relative_index, 0.0));
141 : }
142 :
143 : return Just(std::min(relative_index, length));
144 : }
145 :
146 : // Returns "length", has "fast-path" for JSArrays.
147 189716 : V8_WARN_UNUSED_RESULT Maybe<double> GetLengthProperty(
148 : Isolate* isolate, Handle<JSReceiver> receiver) {
149 189716 : if (receiver->IsJSArray()) {
150 : Handle<JSArray> array = Handle<JSArray>::cast(receiver);
151 : double length = array->length()->Number();
152 : DCHECK(0 <= length && length <= kMaxSafeInteger);
153 :
154 : return Just(length);
155 : }
156 :
157 : Handle<Object> raw_length_number;
158 486 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(
159 : isolate, raw_length_number,
160 : Object::GetLengthFromArrayLike(isolate, receiver), Nothing<double>());
161 : return Just(raw_length_number->Number());
162 : }
163 :
164 : // Set "length" property, has "fast-path" for JSArrays.
165 : // Returns Nothing if something went wrong.
166 0 : V8_WARN_UNUSED_RESULT MaybeHandle<Object> SetLengthProperty(
167 : Isolate* isolate, Handle<JSReceiver> receiver, double length) {
168 0 : if (receiver->IsJSArray()) {
169 0 : Handle<JSArray> array = Handle<JSArray>::cast(receiver);
170 0 : if (!JSArray::HasReadOnlyLength(array)) {
171 : DCHECK_LE(length, kMaxUInt32);
172 0 : JSArray::SetLength(array, static_cast<uint32_t>(length));
173 0 : return receiver;
174 : }
175 : }
176 :
177 : return Object::SetProperty(
178 : isolate, receiver, isolate->factory()->length_string(),
179 : isolate->factory()->NewNumber(length), StoreOrigin::kMaybeKeyed,
180 0 : Just(ShouldThrow::kThrowOnError));
181 : }
182 :
183 377 : V8_WARN_UNUSED_RESULT Object GenericArrayFill(Isolate* isolate,
184 : Handle<JSReceiver> receiver,
185 : Handle<Object> value,
186 : double start, double end) {
187 : // 7. Repeat, while k < final.
188 2351 : while (start < end) {
189 : // a. Let Pk be ! ToString(k).
190 : Handle<String> index = isolate->factory()->NumberToString(
191 1059 : isolate->factory()->NewNumber(start));
192 :
193 : // b. Perform ? Set(O, Pk, value, true).
194 2190 : RETURN_FAILURE_ON_EXCEPTION(isolate, Object::SetPropertyOrElement(
195 : isolate, receiver, index, value,
196 : Just(ShouldThrow::kThrowOnError)));
197 :
198 : // c. Increase k by 1.
199 987 : ++start;
200 : }
201 :
202 : // 8. Return O.
203 305 : return *receiver;
204 : }
205 :
206 7478 : V8_WARN_UNUSED_RESULT bool TryFastArrayFill(
207 : Isolate* isolate, BuiltinArguments* args, Handle<JSReceiver> receiver,
208 : Handle<Object> value, double start_index, double end_index) {
209 : // If indices are too large, use generic path since they are stored as
210 : // properties, not in the element backing store.
211 7478 : if (end_index > kMaxUInt32) return false;
212 7469 : if (!receiver->IsJSObject()) return false;
213 :
214 7469 : if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, args, 1, 1)) {
215 : return false;
216 : }
217 :
218 : Handle<JSArray> array = Handle<JSArray>::cast(receiver);
219 :
220 : // If no argument was provided, we fill the array with 'undefined'.
221 : // EnsureJSArrayWith... does not handle that case so we do it here.
222 : // TODO(szuend): Pass target elements kind to EnsureJSArrayWith... when
223 : // it gets refactored.
224 7153 : if (args->length() == 1 && array->GetElementsKind() != PACKED_ELEMENTS) {
225 : // Use a short-lived HandleScope to avoid creating several copies of the
226 : // elements handle which would cause issues when left-trimming later-on.
227 : HandleScope scope(isolate);
228 25 : JSObject::TransitionElementsKind(array, PACKED_ELEMENTS);
229 : }
230 :
231 : DCHECK_LE(start_index, kMaxUInt32);
232 : DCHECK_LE(end_index, kMaxUInt32);
233 :
234 : uint32_t start, end;
235 7101 : CHECK(DoubleToUint32IfEqualToSelf(start_index, &start));
236 7101 : CHECK(DoubleToUint32IfEqualToSelf(end_index, &end));
237 :
238 7101 : ElementsAccessor* accessor = array->GetElementsAccessor();
239 14202 : accessor->Fill(array, value, start, end);
240 7101 : return true;
241 : }
242 : } // namespace
243 :
244 37880 : BUILTIN(ArrayPrototypeFill) {
245 : HandleScope scope(isolate);
246 :
247 7576 : if (isolate->debug_execution_mode() == DebugInfo::kSideEffects) {
248 27 : if (!isolate->debug()->PerformSideEffectCheckForObject(args.receiver())) {
249 18 : return ReadOnlyRoots(isolate).exception();
250 : }
251 : }
252 :
253 : // 1. Let O be ? ToObject(this value).
254 : Handle<JSReceiver> receiver;
255 15134 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
256 : isolate, receiver, Object::ToObject(isolate, args.receiver()));
257 :
258 : // 2. Let len be ? ToLength(? Get(O, "length")).
259 : double length;
260 15080 : MAYBE_ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
261 : isolate, length, GetLengthProperty(isolate, receiver));
262 :
263 : // 3. Let relativeStart be ? ToInteger(start).
264 : // 4. If relativeStart < 0, let k be max((len + relativeStart), 0);
265 : // else let k be min(relativeStart, len).
266 7540 : Handle<Object> start = args.atOrUndefined(isolate, 2);
267 :
268 : double start_index;
269 15080 : MAYBE_ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
270 : isolate, start_index, GetRelativeIndex(isolate, length, start, 0));
271 :
272 : // 5. If end is undefined, let relativeEnd be len;
273 : // else let relativeEnd be ? ToInteger(end).
274 : // 6. If relativeEnd < 0, let final be max((len + relativeEnd), 0);
275 : // else let final be min(relativeEnd, len).
276 7540 : Handle<Object> end = args.atOrUndefined(isolate, 3);
277 :
278 : double end_index;
279 15080 : MAYBE_ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
280 : isolate, end_index, GetRelativeIndex(isolate, length, end, length));
281 :
282 7602 : if (start_index >= end_index) return *receiver;
283 :
284 : // Ensure indexes are within array bounds
285 : DCHECK_LE(0, start_index);
286 : DCHECK_LE(start_index, end_index);
287 : DCHECK_LE(end_index, length);
288 :
289 7478 : Handle<Object> value = args.atOrUndefined(isolate, 1);
290 :
291 7478 : if (TryFastArrayFill(isolate, &args, receiver, value, start_index,
292 : end_index)) {
293 7101 : return *receiver;
294 : }
295 377 : return GenericArrayFill(isolate, receiver, value, start_index, end_index);
296 : }
297 :
298 : namespace {
299 7728 : V8_WARN_UNUSED_RESULT Object GenericArrayPush(Isolate* isolate,
300 : BuiltinArguments* args) {
301 : // 1. Let O be ? ToObject(this value).
302 : Handle<JSReceiver> receiver;
303 15717 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
304 : isolate, receiver, Object::ToObject(isolate, args->receiver()));
305 :
306 : // 2. Let len be ? ToLength(? Get(O, "length")).
307 : Handle<Object> raw_length_number;
308 14943 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
309 : isolate, raw_length_number,
310 : Object::GetLengthFromArrayLike(isolate, receiver));
311 :
312 : // 3. Let args be a List whose elements are, in left to right order,
313 : // the arguments that were passed to this function invocation.
314 : // 4. Let arg_count be the number of elements in args.
315 7458 : int arg_count = args->length() - 1;
316 :
317 : // 5. If len + arg_count > 2^53-1, throw a TypeError exception.
318 : double length = raw_length_number->Number();
319 7458 : if (arg_count > kMaxSafeInteger - length) {
320 18 : THROW_NEW_ERROR_RETURN_FAILURE(
321 : isolate, NewTypeError(MessageTemplate::kPushPastSafeLength,
322 : isolate->factory()->NewNumberFromInt(arg_count),
323 : raw_length_number));
324 : }
325 :
326 : // 6. Repeat, while args is not empty.
327 22749 : for (int i = 0; i < arg_count; ++i) {
328 : // a. Remove the first element from args and let E be the value of the
329 : // element.
330 15646 : Handle<Object> element = args->at(i + 1);
331 :
332 : // b. Perform ? Set(O, ! ToString(len), E, true).
333 7823 : if (length <= static_cast<double>(JSArray::kMaxArrayIndex)) {
334 23642 : RETURN_FAILURE_ON_EXCEPTION(
335 : isolate, Object::SetElement(isolate, receiver, length, element,
336 : ShouldThrow::kThrowOnError));
337 : } else {
338 : bool success;
339 : LookupIterator it = LookupIterator::PropertyOrElement(
340 0 : isolate, receiver, isolate->factory()->NewNumber(length), &success);
341 : // Must succeed since we always pass a valid key.
342 : DCHECK(success);
343 0 : MAYBE_RETURN(Object::SetProperty(&it, element, StoreOrigin::kMaybeKeyed,
344 : Just(ShouldThrow::kThrowOnError)),
345 : ReadOnlyRoots(isolate).exception());
346 : }
347 :
348 : // c. Let len be len+1.
349 7650 : ++length;
350 : }
351 :
352 : // 7. Perform ? Set(O, "length", len, true).
353 7276 : Handle<Object> final_length = isolate->factory()->NewNumber(length);
354 14588 : RETURN_FAILURE_ON_EXCEPTION(
355 : isolate, Object::SetProperty(isolate, receiver,
356 : isolate->factory()->length_string(),
357 : final_length, StoreOrigin::kMaybeKeyed,
358 : Just(ShouldThrow::kThrowOnError)));
359 :
360 : // 8. Return len.
361 : return *final_length;
362 : }
363 : } // namespace
364 :
365 4573525 : BUILTIN(ArrayPush) {
366 : HandleScope scope(isolate);
367 : Handle<Object> receiver = args.receiver();
368 914705 : if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, &args, 1,
369 : args.length() - 1)) {
370 7656 : return GenericArrayPush(isolate, &args);
371 : }
372 :
373 : // Fast Elements Path
374 907049 : int to_add = args.length() - 1;
375 : Handle<JSArray> array = Handle<JSArray>::cast(receiver);
376 907049 : uint32_t len = static_cast<uint32_t>(array->length()->Number());
377 907094 : if (to_add == 0) return *isolate->factory()->NewNumberFromUint(len);
378 :
379 : // Currently fixed arrays cannot grow too big, so we should never hit this.
380 : DCHECK_LE(to_add, Smi::kMaxValue - Smi::ToInt(array->length()));
381 :
382 907004 : if (JSArray::HasReadOnlyLength(array)) {
383 72 : return GenericArrayPush(isolate, &args);
384 : }
385 :
386 906932 : ElementsAccessor* accessor = array->GetElementsAccessor();
387 906932 : uint32_t new_length = accessor->Push(array, &args, to_add);
388 1813864 : return *isolate->factory()->NewNumberFromUint((new_length));
389 : }
390 :
391 : namespace {
392 :
393 3436 : V8_WARN_UNUSED_RESULT Object GenericArrayPop(Isolate* isolate,
394 : BuiltinArguments* args) {
395 : // 1. Let O be ? ToObject(this value).
396 : Handle<JSReceiver> receiver;
397 7043 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
398 : isolate, receiver, Object::ToObject(isolate, args->receiver()));
399 :
400 : // 2. Let len be ? ToLength(? Get(O, "length")).
401 : Handle<Object> raw_length_number;
402 6539 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
403 : isolate, raw_length_number,
404 : Object::GetLengthFromArrayLike(isolate, receiver));
405 : double length = raw_length_number->Number();
406 :
407 : // 3. If len is zero, then.
408 3256 : if (length == 0) {
409 : // a. Perform ? Set(O, "length", 0, true).
410 234 : RETURN_FAILURE_ON_EXCEPTION(
411 : isolate, Object::SetProperty(isolate, receiver,
412 : isolate->factory()->length_string(),
413 : Handle<Smi>(Smi::zero(), isolate),
414 : StoreOrigin::kMaybeKeyed,
415 : Just(ShouldThrow::kThrowOnError)));
416 :
417 : // b. Return undefined.
418 117 : return ReadOnlyRoots(isolate).undefined_value();
419 : }
420 :
421 : // 4. Else len > 0.
422 : // a. Let new_len be len-1.
423 3139 : Handle<Object> new_length = isolate->factory()->NewNumber(length - 1);
424 :
425 : // b. Let index be ! ToString(newLen).
426 3139 : Handle<String> index = isolate->factory()->NumberToString(new_length);
427 :
428 : // c. Let element be ? Get(O, index).
429 : Handle<Object> element;
430 6287 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
431 : isolate, element, Object::GetPropertyOrElement(isolate, receiver, index));
432 :
433 : // d. Perform ? DeletePropertyOrThrow(O, index).
434 6366 : MAYBE_RETURN(JSReceiver::DeletePropertyOrElement(receiver, index,
435 : LanguageMode::kStrict),
436 : ReadOnlyRoots(isolate).exception());
437 :
438 : // e. Perform ? Set(O, "length", newLen, true).
439 6273 : RETURN_FAILURE_ON_EXCEPTION(
440 : isolate, Object::SetProperty(isolate, receiver,
441 : isolate->factory()->length_string(),
442 : new_length, StoreOrigin::kMaybeKeyed,
443 : Just(ShouldThrow::kThrowOnError)));
444 :
445 : // f. Return element.
446 : return *element;
447 : }
448 :
449 : } // namespace
450 :
451 318465 : BUILTIN(ArrayPop) {
452 : HandleScope scope(isolate);
453 : Handle<Object> receiver = args.receiver();
454 63693 : if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, nullptr, 0,
455 : 0)) {
456 3211 : return GenericArrayPop(isolate, &args);
457 : }
458 : Handle<JSArray> array = Handle<JSArray>::cast(receiver);
459 :
460 60482 : uint32_t len = static_cast<uint32_t>(array->length()->Number());
461 60538 : if (len == 0) return ReadOnlyRoots(isolate).undefined_value();
462 :
463 60426 : if (JSArray::HasReadOnlyLength(array)) {
464 225 : return GenericArrayPop(isolate, &args);
465 : }
466 :
467 : Handle<Object> result;
468 60201 : if (IsJSArrayFastElementMovingAllowed(isolate, JSArray::cast(*receiver))) {
469 : // Fast Elements Path
470 58365 : result = array->GetElementsAccessor()->Pop(array);
471 : } else {
472 : // Use Slow Lookup otherwise
473 1836 : uint32_t new_length = len - 1;
474 3672 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
475 : isolate, result, JSReceiver::GetElement(isolate, array, new_length));
476 1836 : JSArray::SetLength(array, new_length);
477 : }
478 :
479 : return *result;
480 : }
481 :
482 : namespace {
483 :
484 : // Returns true, iff we can use ElementsAccessor for shifting.
485 182176 : V8_WARN_UNUSED_RESULT bool CanUseFastArrayShift(Isolate* isolate,
486 : Handle<JSReceiver> receiver) {
487 364352 : if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, nullptr, 0,
488 364352 : 0) ||
489 : !IsJSArrayFastElementMovingAllowed(isolate, JSArray::cast(*receiver))) {
490 : return false;
491 : }
492 :
493 182176 : Handle<JSArray> array = Handle<JSArray>::cast(receiver);
494 182176 : return !JSArray::HasReadOnlyLength(array);
495 : }
496 :
497 0 : V8_WARN_UNUSED_RESULT Object GenericArrayShift(Isolate* isolate,
498 : Handle<JSReceiver> receiver,
499 : double length) {
500 : // 4. Let first be ? Get(O, "0").
501 : Handle<Object> first;
502 0 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, first,
503 : Object::GetElement(isolate, receiver, 0));
504 :
505 : // 5. Let k be 1.
506 : double k = 1;
507 :
508 : // 6. Repeat, while k < len.
509 0 : while (k < length) {
510 : // a. Let from be ! ToString(k).
511 : Handle<String> from =
512 0 : isolate->factory()->NumberToString(isolate->factory()->NewNumber(k));
513 :
514 : // b. Let to be ! ToString(k-1).
515 : Handle<String> to = isolate->factory()->NumberToString(
516 0 : isolate->factory()->NewNumber(k - 1));
517 :
518 : // c. Let fromPresent be ? HasProperty(O, from).
519 : bool from_present;
520 0 : MAYBE_ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
521 : isolate, from_present, JSReceiver::HasProperty(receiver, from));
522 :
523 : // d. If fromPresent is true, then.
524 0 : if (from_present) {
525 : // i. Let fromVal be ? Get(O, from).
526 : Handle<Object> from_val;
527 0 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
528 : isolate, from_val,
529 : Object::GetPropertyOrElement(isolate, receiver, from));
530 :
531 : // ii. Perform ? Set(O, to, fromVal, true).
532 0 : RETURN_FAILURE_ON_EXCEPTION(
533 : isolate,
534 : Object::SetPropertyOrElement(isolate, receiver, to, from_val,
535 : Just(ShouldThrow::kThrowOnError)));
536 : } else { // e. Else fromPresent is false,
537 : // i. Perform ? DeletePropertyOrThrow(O, to).
538 0 : MAYBE_RETURN(JSReceiver::DeletePropertyOrElement(receiver, to,
539 : LanguageMode::kStrict),
540 : ReadOnlyRoots(isolate).exception());
541 : }
542 :
543 : // f. Increase k by 1.
544 0 : ++k;
545 : }
546 :
547 : // 7. Perform ? DeletePropertyOrThrow(O, ! ToString(len-1)).
548 : Handle<String> new_length = isolate->factory()->NumberToString(
549 0 : isolate->factory()->NewNumber(length - 1));
550 0 : MAYBE_RETURN(JSReceiver::DeletePropertyOrElement(receiver, new_length,
551 : LanguageMode::kStrict),
552 : ReadOnlyRoots(isolate).exception());
553 :
554 : // 8. Perform ? Set(O, "length", len-1, true).
555 0 : RETURN_FAILURE_ON_EXCEPTION(isolate,
556 : SetLengthProperty(isolate, receiver, length - 1));
557 :
558 : // 9. Return first.
559 : return *first;
560 : }
561 : } // namespace
562 :
563 910880 : BUILTIN(ArrayShift) {
564 : HandleScope scope(isolate);
565 :
566 : // 1. Let O be ? ToObject(this value).
567 : Handle<JSReceiver> receiver;
568 364352 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
569 : isolate, receiver, Object::ToObject(isolate, args.receiver()));
570 :
571 : // 2. Let len be ? ToLength(? Get(O, "length")).
572 : double length;
573 364352 : MAYBE_ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
574 : isolate, length, GetLengthProperty(isolate, receiver));
575 :
576 : // 3. If len is zero, then.
577 182176 : if (length == 0) {
578 : // a. Perform ? Set(O, "length", 0, true).
579 0 : RETURN_FAILURE_ON_EXCEPTION(isolate,
580 : SetLengthProperty(isolate, receiver, length));
581 :
582 : // b. Return undefined.
583 0 : return ReadOnlyRoots(isolate).undefined_value();
584 : }
585 :
586 182176 : if (CanUseFastArrayShift(isolate, receiver)) {
587 : Handle<JSArray> array = Handle<JSArray>::cast(receiver);
588 364352 : return *array->GetElementsAccessor()->Shift(array);
589 : }
590 :
591 0 : return GenericArrayShift(isolate, receiver, length);
592 : }
593 :
594 29475 : BUILTIN(ArrayUnshift) {
595 : HandleScope scope(isolate);
596 : DCHECK(args.receiver()->IsJSArray());
597 : Handle<JSArray> array = Handle<JSArray>::cast(args.receiver());
598 :
599 : // These are checked in the Torque builtin.
600 : DCHECK(array->map()->is_extensible());
601 : DCHECK(!IsDictionaryElementsKind(array->GetElementsKind()));
602 : DCHECK(IsJSArrayFastElementMovingAllowed(isolate, *array));
603 : DCHECK(!isolate->IsAnyInitialArrayPrototype(array));
604 :
605 5895 : MatchArrayElementsKindToArguments(isolate, array, &args, 1,
606 5895 : args.length() - 1);
607 :
608 5895 : int to_add = args.length() - 1;
609 5895 : if (to_add == 0) return array->length();
610 :
611 : // Currently fixed arrays cannot grow too big, so we should never hit this.
612 : DCHECK_LE(to_add, Smi::kMaxValue - Smi::ToInt(array->length()));
613 : DCHECK(!JSArray::HasReadOnlyLength(array));
614 :
615 5846 : ElementsAccessor* accessor = array->GetElementsAccessor();
616 5846 : int new_length = accessor->Unshift(array, &args, to_add);
617 5846 : return Smi::FromInt(new_length);
618 : }
619 :
620 : // Array Concat -------------------------------------------------------------
621 :
622 : namespace {
623 :
624 : /**
625 : * A simple visitor visits every element of Array's.
626 : * The backend storage can be a fixed array for fast elements case,
627 : * or a dictionary for sparse array. Since Dictionary is a subtype
628 : * of FixedArray, the class can be used by both fast and slow cases.
629 : * The second parameter of the constructor, fast_elements, specifies
630 : * whether the storage is a FixedArray or Dictionary.
631 : *
632 : * An index limit is used to deal with the situation that a result array
633 : * length overflows 32-bit non-negative integer.
634 : */
635 : class ArrayConcatVisitor {
636 : public:
637 6118 : ArrayConcatVisitor(Isolate* isolate, Handle<HeapObject> storage,
638 : bool fast_elements)
639 : : isolate_(isolate),
640 : storage_(isolate->global_handles()->Create(*storage)),
641 : index_offset_(0u),
642 : bit_field_(FastElementsField::encode(fast_elements) |
643 6118 : ExceedsLimitField::encode(false) |
644 6118 : IsFixedArrayField::encode(storage->IsFixedArray()) |
645 : HasSimpleElementsField::encode(
646 6406 : storage->IsFixedArray() ||
647 18354 : !storage->map()->IsCustomElementsReceiverMap())) {
648 : DCHECK(!(this->fast_elements() && !is_fixed_array()));
649 6118 : }
650 :
651 6118 : ~ArrayConcatVisitor() { clear_storage(); }
652 :
653 1285874 : V8_WARN_UNUSED_RESULT bool visit(uint32_t i, Handle<Object> elm) {
654 1285874 : uint32_t index = index_offset_ + i;
655 :
656 1285874 : if (i >= JSObject::kMaxElementCount - index_offset_) {
657 : set_exceeds_array_limit(true);
658 : // Exception hasn't been thrown at this point. Return true to
659 : // break out, and caller will throw. !visit would imply that
660 : // there is already a pending exception.
661 36 : return true;
662 : }
663 :
664 1285838 : if (!is_fixed_array()) {
665 324 : LookupIterator it(isolate_, storage_, index, LookupIterator::OWN);
666 648 : MAYBE_RETURN(
667 : JSReceiver::CreateDataProperty(&it, elm, Just(kThrowOnError)), false);
668 279 : return true;
669 : }
670 :
671 1285514 : if (fast_elements()) {
672 907120 : if (index < static_cast<uint32_t>(storage_fixed_array()->length())) {
673 907102 : storage_fixed_array()->set(index, *elm);
674 907102 : return true;
675 : }
676 : // Our initial estimate of length was foiled, possibly by
677 : // getters on the arrays increasing the length of later arrays
678 : // during iteration.
679 : // This shouldn't happen in anything but pathological cases.
680 18 : SetDictionaryMode();
681 : // Fall-through to dictionary mode.
682 : }
683 : DCHECK(!fast_elements());
684 378412 : Handle<NumberDictionary> dict(NumberDictionary::cast(*storage_), isolate_);
685 : // The object holding this backing store has just been allocated, so
686 : // it cannot yet be used as a prototype.
687 : Handle<JSObject> not_a_prototype_holder;
688 : Handle<NumberDictionary> result = NumberDictionary::Set(
689 378412 : isolate_, dict, index, elm, not_a_prototype_holder);
690 378412 : if (!result.is_identical_to(dict)) {
691 : // Dictionary needed to grow.
692 : clear_storage();
693 : set_storage(*result);
694 : }
695 : return true;
696 : }
697 :
698 : uint32_t index_offset() const { return index_offset_; }
699 :
700 912173 : void increase_index_offset(uint32_t delta) {
701 912173 : if (JSObject::kMaxElementCount - index_offset_ < delta) {
702 45 : index_offset_ = JSObject::kMaxElementCount;
703 : } else {
704 912128 : index_offset_ += delta;
705 : }
706 : // If the initial length estimate was off (see special case in visit()),
707 : // but the array blowing the limit didn't contain elements beyond the
708 : // provided-for index range, go to dictionary mode now.
709 1816909 : if (fast_elements() &&
710 1809472 : index_offset_ >
711 : static_cast<uint32_t>(FixedArrayBase::cast(*storage_)->length())) {
712 9 : SetDictionaryMode();
713 : }
714 912173 : }
715 :
716 : bool exceeds_array_limit() const {
717 : return ExceedsLimitField::decode(bit_field_);
718 : }
719 :
720 5632 : Handle<JSArray> ToArray() {
721 : DCHECK(is_fixed_array());
722 5632 : Handle<JSArray> array = isolate_->factory()->NewJSArray(0);
723 : Handle<Object> length =
724 5632 : isolate_->factory()->NewNumber(static_cast<double>(index_offset_));
725 : Handle<Map> map = JSObject::GetElementsTransitionMap(
726 11264 : array, fast_elements() ? HOLEY_ELEMENTS : DICTIONARY_ELEMENTS);
727 5632 : array->set_length(*length);
728 11264 : array->set_elements(*storage_fixed_array());
729 5632 : array->synchronized_set_map(*map);
730 5632 : return array;
731 : }
732 :
733 234 : V8_WARN_UNUSED_RESULT MaybeHandle<JSReceiver> ToJSReceiver() {
734 : DCHECK(!is_fixed_array());
735 : Handle<JSReceiver> result = Handle<JSReceiver>::cast(storage_);
736 : Handle<Object> length =
737 234 : isolate_->factory()->NewNumber(static_cast<double>(index_offset_));
738 702 : RETURN_ON_EXCEPTION(
739 : isolate_,
740 : Object::SetProperty(
741 : isolate_, result, isolate_->factory()->length_string(), length,
742 : StoreOrigin::kMaybeKeyed, Just(ShouldThrow::kThrowOnError)),
743 : JSReceiver);
744 225 : return result;
745 : }
746 : bool has_simple_elements() const {
747 : return HasSimpleElementsField::decode(bit_field_);
748 : }
749 :
750 : private:
751 : // Convert storage to dictionary mode.
752 27 : void SetDictionaryMode() {
753 : DCHECK(fast_elements() && is_fixed_array());
754 : Handle<FixedArray> current_storage = storage_fixed_array();
755 : Handle<NumberDictionary> slow_storage(
756 27 : NumberDictionary::New(isolate_, current_storage->length()));
757 27 : uint32_t current_length = static_cast<uint32_t>(current_storage->length());
758 486 : FOR_WITH_HANDLE_SCOPE(
759 : isolate_, uint32_t, i = 0, i, i < current_length, i++, {
760 : Handle<Object> element(current_storage->get(i), isolate_);
761 : if (!element->IsTheHole(isolate_)) {
762 : // The object holding this backing store has just been allocated, so
763 : // it cannot yet be used as a prototype.
764 : Handle<JSObject> not_a_prototype_holder;
765 : Handle<NumberDictionary> new_storage = NumberDictionary::Set(
766 : isolate_, slow_storage, i, element, not_a_prototype_holder);
767 : if (!new_storage.is_identical_to(slow_storage)) {
768 : slow_storage = loop_scope.CloseAndEscape(new_storage);
769 : }
770 : }
771 : });
772 : clear_storage();
773 : set_storage(*slow_storage);
774 : set_fast_elements(false);
775 27 : }
776 :
777 8035 : inline void clear_storage() { GlobalHandles::Destroy(storage_.location()); }
778 :
779 : inline void set_storage(FixedArray storage) {
780 : DCHECK(is_fixed_array());
781 : DCHECK(has_simple_elements());
782 3834 : storage_ = isolate_->global_handles()->Create(storage);
783 : }
784 :
785 : class FastElementsField : public BitField<bool, 0, 1> {};
786 : class ExceedsLimitField : public BitField<bool, 1, 1> {};
787 : class IsFixedArrayField : public BitField<bool, 2, 1> {};
788 : class HasSimpleElementsField : public BitField<bool, 3, 1> {};
789 :
790 : bool fast_elements() const { return FastElementsField::decode(bit_field_); }
791 : void set_fast_elements(bool fast) {
792 54 : bit_field_ = FastElementsField::update(bit_field_, fast);
793 : }
794 : void set_exceeds_array_limit(bool exceeds) {
795 72 : bit_field_ = ExceedsLimitField::update(bit_field_, exceeds);
796 : }
797 : bool is_fixed_array() const { return IsFixedArrayField::decode(bit_field_); }
798 : Handle<FixedArray> storage_fixed_array() {
799 : DCHECK(is_fixed_array());
800 : DCHECK(has_simple_elements());
801 : return Handle<FixedArray>::cast(storage_);
802 : }
803 :
804 : Isolate* isolate_;
805 : Handle<Object> storage_; // Always a global handle.
806 : // Index after last seen index. Always less than or equal to
807 : // JSObject::kMaxElementCount.
808 : uint32_t index_offset_;
809 : uint32_t bit_field_;
810 : };
811 :
812 7586 : uint32_t EstimateElementCount(Isolate* isolate, Handle<JSArray> array) {
813 : DisallowHeapAllocation no_gc;
814 7586 : uint32_t length = static_cast<uint32_t>(array->length()->Number());
815 : int element_count = 0;
816 7586 : switch (array->GetElementsKind()) {
817 : case PACKED_SMI_ELEMENTS:
818 : case HOLEY_SMI_ELEMENTS:
819 : case PACKED_ELEMENTS:
820 : case PACKED_FROZEN_ELEMENTS:
821 : case PACKED_SEALED_ELEMENTS:
822 : case HOLEY_ELEMENTS: {
823 : // Fast elements can't have lengths that are not representable by
824 : // a 32-bit signed integer.
825 : DCHECK_GE(static_cast<int32_t>(FixedArray::kMaxLength), 0);
826 6898 : int fast_length = static_cast<int>(length);
827 : FixedArray elements = FixedArray::cast(array->elements());
828 94608 : for (int i = 0; i < fast_length; i++) {
829 43855 : if (!elements->get(i)->IsTheHole(isolate)) element_count++;
830 : }
831 : break;
832 : }
833 : case PACKED_DOUBLE_ELEMENTS:
834 : case HOLEY_DOUBLE_ELEMENTS: {
835 : // Fast elements can't have lengths that are not representable by
836 : // a 32-bit signed integer.
837 : DCHECK_GE(static_cast<int32_t>(FixedDoubleArray::kMaxLength), 0);
838 72 : int fast_length = static_cast<int>(length);
839 72 : if (array->elements()->IsFixedArray()) {
840 : DCHECK_EQ(FixedArray::cast(array->elements())->length(), 0);
841 : break;
842 : }
843 : FixedDoubleArray elements = FixedDoubleArray::cast(array->elements());
844 1182735 : for (int i = 0; i < fast_length; i++) {
845 591336 : if (!elements->is_the_hole(i)) element_count++;
846 : }
847 : break;
848 : }
849 : case DICTIONARY_ELEMENTS: {
850 : NumberDictionary dictionary = NumberDictionary::cast(array->elements());
851 : int capacity = dictionary->Capacity();
852 : ReadOnlyRoots roots(isolate);
853 24012 : for (int i = 0; i < capacity; i++) {
854 11698 : Object key = dictionary->KeyAt(i);
855 11698 : if (dictionary->IsKey(roots, key)) {
856 4580 : element_count++;
857 : }
858 : }
859 : break;
860 : }
861 : #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype) case TYPE##_ELEMENTS:
862 :
863 : TYPED_ARRAYS(TYPED_ARRAY_CASE)
864 : #undef TYPED_ARRAY_CASE
865 : // External arrays are always dense.
866 0 : return length;
867 : case NO_ELEMENTS:
868 : return 0;
869 : case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
870 : case SLOW_SLOPPY_ARGUMENTS_ELEMENTS:
871 : case FAST_STRING_WRAPPER_ELEMENTS:
872 : case SLOW_STRING_WRAPPER_ELEMENTS:
873 0 : UNREACHABLE();
874 : }
875 : // As an estimate, we assume that the prototype doesn't contain any
876 : // inherited elements.
877 7586 : return element_count;
878 : }
879 :
880 1569 : void CollectElementIndices(Isolate* isolate, Handle<JSObject> object,
881 : uint32_t range, std::vector<uint32_t>* indices) {
882 : ElementsKind kind = object->GetElementsKind();
883 1569 : switch (kind) {
884 : case PACKED_SMI_ELEMENTS:
885 : case PACKED_ELEMENTS:
886 : case PACKED_FROZEN_ELEMENTS:
887 : case PACKED_SEALED_ELEMENTS:
888 : case HOLEY_SMI_ELEMENTS:
889 : case HOLEY_ELEMENTS: {
890 : DisallowHeapAllocation no_gc;
891 : FixedArray elements = FixedArray::cast(object->elements());
892 1034 : uint32_t length = static_cast<uint32_t>(elements->length());
893 1034 : if (range < length) length = range;
894 41102 : for (uint32_t i = 0; i < length; i++) {
895 80136 : if (!elements->get(i)->IsTheHole(isolate)) {
896 198 : indices->push_back(i);
897 : }
898 : }
899 : break;
900 : }
901 : case HOLEY_DOUBLE_ELEMENTS:
902 : case PACKED_DOUBLE_ELEMENTS: {
903 9 : if (object->elements()->IsFixedArray()) {
904 : DCHECK_EQ(object->elements()->length(), 0);
905 : break;
906 : }
907 : Handle<FixedDoubleArray> elements(
908 : FixedDoubleArray::cast(object->elements()), isolate);
909 9 : uint32_t length = static_cast<uint32_t>(elements->length());
910 9 : if (range < length) length = range;
911 18 : for (uint32_t i = 0; i < length; i++) {
912 18 : if (!elements->is_the_hole(i)) {
913 9 : indices->push_back(i);
914 : }
915 : }
916 9 : break;
917 : }
918 : case DICTIONARY_ELEMENTS: {
919 : DisallowHeapAllocation no_gc;
920 : NumberDictionary dict = NumberDictionary::cast(object->elements());
921 472 : uint32_t capacity = dict->Capacity();
922 : ReadOnlyRoots roots(isolate);
923 6914 : FOR_WITH_HANDLE_SCOPE(isolate, uint32_t, j = 0, j, j < capacity, j++, {
924 : Object k = dict->KeyAt(j);
925 : if (!dict->IsKey(roots, k)) continue;
926 : DCHECK(k->IsNumber());
927 : uint32_t index = static_cast<uint32_t>(k->Number());
928 : if (index < range) {
929 : indices->push_back(index);
930 : }
931 : });
932 : break;
933 : }
934 : #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype) case TYPE##_ELEMENTS:
935 :
936 : TYPED_ARRAYS(TYPED_ARRAY_CASE)
937 : #undef TYPED_ARRAY_CASE
938 : {
939 9 : uint32_t length = static_cast<uint32_t>(object->elements()->length());
940 9 : if (range <= length) {
941 : length = range;
942 : // We will add all indices, so we might as well clear it first
943 : // and avoid duplicates.
944 : indices->clear();
945 : }
946 27 : for (uint32_t i = 0; i < length; i++) {
947 18 : indices->push_back(i);
948 : }
949 9 : if (length == range) return; // All indices accounted for already.
950 : break;
951 : }
952 : case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
953 : case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: {
954 : DisallowHeapAllocation no_gc;
955 45 : FixedArrayBase elements = object->elements();
956 45 : JSObject raw_object = *object;
957 45 : ElementsAccessor* accessor = object->GetElementsAccessor();
958 270072 : for (uint32_t i = 0; i < range; i++) {
959 270027 : if (accessor->HasElement(raw_object, i, elements)) {
960 54 : indices->push_back(i);
961 : }
962 : }
963 : break;
964 : }
965 : case FAST_STRING_WRAPPER_ELEMENTS:
966 : case SLOW_STRING_WRAPPER_ELEMENTS: {
967 : DCHECK(object->IsJSValue());
968 : Handle<JSValue> js_value = Handle<JSValue>::cast(object);
969 : DCHECK(js_value->value()->IsString());
970 : Handle<String> string(String::cast(js_value->value()), isolate);
971 0 : uint32_t length = static_cast<uint32_t>(string->length());
972 0 : uint32_t i = 0;
973 : uint32_t limit = Min(length, range);
974 0 : for (; i < limit; i++) {
975 0 : indices->push_back(i);
976 : }
977 0 : ElementsAccessor* accessor = object->GetElementsAccessor();
978 0 : for (; i < range; i++) {
979 0 : if (accessor->HasElement(*object, i)) {
980 0 : indices->push_back(i);
981 : }
982 : }
983 : break;
984 : }
985 : case NO_ELEMENTS:
986 : break;
987 : }
988 :
989 1569 : PrototypeIterator iter(isolate, object);
990 1569 : if (!iter.IsAtEnd()) {
991 : // The prototype will usually have no inherited element indices,
992 : // but we have to check.
993 : CollectElementIndices(
994 1097 : isolate, PrototypeIterator::GetCurrent<JSObject>(iter), range, indices);
995 : }
996 : }
997 :
998 1144 : bool IterateElementsSlow(Isolate* isolate, Handle<JSReceiver> receiver,
999 : uint32_t length, ArrayConcatVisitor* visitor) {
1000 5861706 : FOR_WITH_HANDLE_SCOPE(isolate, uint32_t, i = 0, i, i < length, ++i, {
1001 : Maybe<bool> maybe = JSReceiver::HasElement(receiver, i);
1002 : if (maybe.IsNothing()) return false;
1003 : if (maybe.FromJust()) {
1004 : Handle<Object> element_value;
1005 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(
1006 : isolate, element_value, JSReceiver::GetElement(isolate, receiver, i),
1007 : false);
1008 : if (!visitor->visit(i, element_value)) return false;
1009 : }
1010 : });
1011 1126 : visitor->increase_index_offset(length);
1012 1126 : return true;
1013 : }
1014 : /**
1015 : * A helper function that visits "array" elements of a JSReceiver in numerical
1016 : * order.
1017 : *
1018 : * The visitor argument called for each existing element in the array
1019 : * with the element index and the element's value.
1020 : * Afterwards it increments the base-index of the visitor by the array
1021 : * length.
1022 : * Returns false if any access threw an exception, otherwise true.
1023 : */
1024 7938 : bool IterateElements(Isolate* isolate, Handle<JSReceiver> receiver,
1025 : ArrayConcatVisitor* visitor) {
1026 7938 : uint32_t length = 0;
1027 :
1028 7938 : if (receiver->IsJSArray()) {
1029 : Handle<JSArray> array = Handle<JSArray>::cast(receiver);
1030 6911 : length = static_cast<uint32_t>(array->length()->Number());
1031 : } else {
1032 : Handle<Object> val;
1033 2054 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(
1034 : isolate, val, Object::GetLengthFromArrayLike(isolate, receiver), false);
1035 1892 : if (visitor->index_offset() + val->Number() > kMaxSafeInteger) {
1036 54 : isolate->Throw(*isolate->factory()->NewTypeError(
1037 54 : MessageTemplate::kInvalidArrayLength));
1038 27 : return false;
1039 : }
1040 : // TODO(caitp): Support larger element indexes (up to 2^53-1).
1041 919 : if (!val->ToUint32(&length)) {
1042 0 : length = 0;
1043 : }
1044 : // TODO(cbruni): handle other element kind as well
1045 919 : return IterateElementsSlow(isolate, receiver, length, visitor);
1046 : }
1047 :
1048 13624 : if (!HasOnlySimpleElements(isolate, *receiver) ||
1049 : !visitor->has_simple_elements()) {
1050 225 : return IterateElementsSlow(isolate, receiver, length, visitor);
1051 : }
1052 : Handle<JSObject> array = Handle<JSObject>::cast(receiver);
1053 :
1054 6686 : switch (array->GetElementsKind()) {
1055 : case PACKED_SMI_ELEMENTS:
1056 : case PACKED_ELEMENTS:
1057 : case PACKED_FROZEN_ELEMENTS:
1058 : case PACKED_SEALED_ELEMENTS:
1059 : case HOLEY_SMI_ELEMENTS:
1060 : case HOLEY_ELEMENTS: {
1061 : // Run through the elements FixedArray and use HasElement and GetElement
1062 : // to check the prototype for missing elements.
1063 : Handle<FixedArray> elements(FixedArray::cast(array->elements()), isolate);
1064 6178 : int fast_length = static_cast<int>(length);
1065 : DCHECK(fast_length <= elements->length());
1066 214025 : FOR_WITH_HANDLE_SCOPE(isolate, int, j = 0, j, j < fast_length, j++, {
1067 : Handle<Object> element_value(elements->get(j), isolate);
1068 : if (!element_value->IsTheHole(isolate)) {
1069 : if (!visitor->visit(j, element_value)) return false;
1070 : } else {
1071 : Maybe<bool> maybe = JSReceiver::HasElement(array, j);
1072 : if (maybe.IsNothing()) return false;
1073 : if (maybe.FromJust()) {
1074 : // Call GetElement on array, not its prototype, or getters won't
1075 : // have the correct receiver.
1076 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(
1077 : isolate, element_value,
1078 : JSReceiver::GetElement(isolate, array, j), false);
1079 : if (!visitor->visit(j, element_value)) return false;
1080 : }
1081 : }
1082 : });
1083 : break;
1084 : }
1085 : case HOLEY_DOUBLE_ELEMENTS:
1086 : case PACKED_DOUBLE_ELEMENTS: {
1087 : // Empty array is FixedArray but not FixedDoubleArray.
1088 36 : if (length == 0) break;
1089 : // Run through the elements FixedArray and use HasElement and GetElement
1090 : // to check the prototype for missing elements.
1091 27 : if (array->elements()->IsFixedArray()) {
1092 : DCHECK_EQ(array->elements()->length(), 0);
1093 : break;
1094 : }
1095 : Handle<FixedDoubleArray> elements(
1096 : FixedDoubleArray::cast(array->elements()), isolate);
1097 27 : int fast_length = static_cast<int>(length);
1098 : DCHECK(fast_length <= elements->length());
1099 2736 : FOR_WITH_HANDLE_SCOPE(isolate, int, j = 0, j, j < fast_length, j++, {
1100 : if (!elements->is_the_hole(j)) {
1101 : double double_value = elements->get_scalar(j);
1102 : Handle<Object> element_value =
1103 : isolate->factory()->NewNumber(double_value);
1104 : if (!visitor->visit(j, element_value)) return false;
1105 : } else {
1106 : Maybe<bool> maybe = JSReceiver::HasElement(array, j);
1107 : if (maybe.IsNothing()) return false;
1108 : if (maybe.FromJust()) {
1109 : // Call GetElement on array, not its prototype, or getters won't
1110 : // have the correct receiver.
1111 : Handle<Object> element_value;
1112 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(
1113 : isolate, element_value,
1114 : JSReceiver::GetElement(isolate, array, j), false);
1115 : if (!visitor->visit(j, element_value)) return false;
1116 : }
1117 : }
1118 : });
1119 : break;
1120 : }
1121 :
1122 : case DICTIONARY_ELEMENTS: {
1123 : Handle<NumberDictionary> dict(array->element_dictionary(), isolate);
1124 : std::vector<uint32_t> indices;
1125 472 : indices.reserve(dict->Capacity() / 2);
1126 :
1127 : // Collect all indices in the object and the prototypes less
1128 : // than length. This might introduce duplicates in the indices list.
1129 472 : CollectElementIndices(isolate, array, length, &indices);
1130 : std::sort(indices.begin(), indices.end());
1131 : size_t n = indices.size();
1132 6141 : FOR_WITH_HANDLE_SCOPE(isolate, size_t, j = 0, j, j < n, (void)0, {
1133 : uint32_t index = indices[j];
1134 : Handle<Object> element;
1135 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(
1136 : isolate, element, JSReceiver::GetElement(isolate, array, index),
1137 : false);
1138 : if (!visitor->visit(index, element)) return false;
1139 : // Skip to next different index (i.e., omit duplicates).
1140 : do {
1141 : j++;
1142 : } while (j < n && indices[j] == index);
1143 : });
1144 : break;
1145 : }
1146 : case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
1147 : case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: {
1148 0 : FOR_WITH_HANDLE_SCOPE(
1149 : isolate, uint32_t, index = 0, index, index < length, index++, {
1150 : Handle<Object> element;
1151 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(
1152 : isolate, element, JSReceiver::GetElement(isolate, array, index),
1153 : false);
1154 : if (!visitor->visit(index, element)) return false;
1155 : });
1156 : break;
1157 : }
1158 : case NO_ELEMENTS:
1159 : break;
1160 : #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype) case TYPE##_ELEMENTS:
1161 : TYPED_ARRAYS(TYPED_ARRAY_CASE)
1162 : #undef TYPED_ARRAY_CASE
1163 0 : return IterateElementsSlow(isolate, receiver, length, visitor);
1164 : case FAST_STRING_WRAPPER_ELEMENTS:
1165 : case SLOW_STRING_WRAPPER_ELEMENTS:
1166 : // |array| is guaranteed to be an array or typed array.
1167 0 : UNREACHABLE();
1168 : break;
1169 : }
1170 6650 : visitor->increase_index_offset(length);
1171 6650 : return true;
1172 : }
1173 :
1174 912389 : static Maybe<bool> IsConcatSpreadable(Isolate* isolate, Handle<Object> obj) {
1175 : HandleScope handle_scope(isolate);
1176 912389 : if (!obj->IsJSReceiver()) return Just(false);
1177 10387 : if (!isolate->IsIsConcatSpreadableLookupChainIntact(JSReceiver::cast(*obj))) {
1178 : // Slow path if @@isConcatSpreadable has been used.
1179 : Handle<Symbol> key(isolate->factory()->is_concat_spreadable_symbol());
1180 : Handle<Object> value;
1181 : MaybeHandle<Object> maybeValue =
1182 6132 : i::Runtime::GetObjectProperty(isolate, obj, key);
1183 8545 : if (!maybeValue.ToHandle(&value)) return Nothing<bool>();
1184 8473 : if (!value->IsUndefined(isolate)) return Just(value->BooleanValue(isolate));
1185 : }
1186 : return Object::IsArray(obj);
1187 : }
1188 :
1189 6127 : Object Slow_ArrayConcat(BuiltinArguments* args, Handle<Object> species,
1190 : Isolate* isolate) {
1191 : int argument_count = args->length();
1192 :
1193 12254 : bool is_array_species = *species == isolate->context()->array_function();
1194 :
1195 : // Pass 1: estimate the length and number of elements of the result.
1196 : // The actual length can be larger if any of the arguments have getters
1197 : // that mutate other arguments (but will otherwise be precise).
1198 : // The number of elements is precise if there are no inherited elements.
1199 :
1200 : ElementsKind kind = PACKED_SMI_ELEMENTS;
1201 :
1202 : uint32_t estimate_result_length = 0;
1203 : uint32_t estimate_nof = 0;
1204 4594735 : FOR_WITH_HANDLE_SCOPE(isolate, int, i = 0, i, i < argument_count, i++, {
1205 : Handle<Object> obj = args->at(i);
1206 : uint32_t length_estimate;
1207 : uint32_t element_estimate;
1208 : if (obj->IsJSArray()) {
1209 : Handle<JSArray> array(Handle<JSArray>::cast(obj));
1210 : length_estimate = static_cast<uint32_t>(array->length()->Number());
1211 : if (length_estimate != 0) {
1212 : ElementsKind array_kind =
1213 : GetPackedElementsKind(array->GetElementsKind());
1214 : if (IsPackedFrozenOrSealedElementsKind(array_kind)) {
1215 : array_kind = PACKED_ELEMENTS;
1216 : }
1217 : kind = GetMoreGeneralElementsKind(kind, array_kind);
1218 : }
1219 : element_estimate = EstimateElementCount(isolate, array);
1220 : } else {
1221 : if (obj->IsHeapObject()) {
1222 : kind = GetMoreGeneralElementsKind(
1223 : kind, obj->IsNumber() ? PACKED_DOUBLE_ELEMENTS : PACKED_ELEMENTS);
1224 : }
1225 : length_estimate = 1;
1226 : element_estimate = 1;
1227 : }
1228 : // Avoid overflows by capping at kMaxElementCount.
1229 : if (JSObject::kMaxElementCount - estimate_result_length < length_estimate) {
1230 : estimate_result_length = JSObject::kMaxElementCount;
1231 : } else {
1232 : estimate_result_length += length_estimate;
1233 : }
1234 : if (JSObject::kMaxElementCount - estimate_nof < element_estimate) {
1235 : estimate_nof = JSObject::kMaxElementCount;
1236 : } else {
1237 : estimate_nof += element_estimate;
1238 : }
1239 : });
1240 :
1241 : // If estimated number of elements is more than half of length, a
1242 : // fixed array (fast case) is more time and space-efficient than a
1243 : // dictionary.
1244 5839 : bool fast_case = is_array_species &&
1245 11255 : (estimate_nof * 2) >= estimate_result_length &&
1246 5128 : isolate->IsIsConcatSpreadableLookupChainIntact();
1247 :
1248 6127 : if (fast_case && kind == PACKED_DOUBLE_ELEMENTS) {
1249 : Handle<FixedArrayBase> storage =
1250 18 : isolate->factory()->NewFixedDoubleArray(estimate_result_length);
1251 : int j = 0;
1252 : bool failure = false;
1253 18 : if (estimate_result_length > 0) {
1254 : Handle<FixedDoubleArray> double_storage =
1255 : Handle<FixedDoubleArray>::cast(storage);
1256 54 : for (int i = 0; i < argument_count; i++) {
1257 : Handle<Object> obj = args->at(i);
1258 27 : if (obj->IsSmi()) {
1259 0 : double_storage->set(j, Smi::ToInt(*obj));
1260 0 : j++;
1261 27 : } else if (obj->IsNumber()) {
1262 9 : double_storage->set(j, obj->Number());
1263 9 : j++;
1264 : } else {
1265 : DisallowHeapAllocation no_gc;
1266 : JSArray array = JSArray::cast(*obj);
1267 18 : uint32_t length = static_cast<uint32_t>(array->length()->Number());
1268 : switch (array->GetElementsKind()) {
1269 : case HOLEY_DOUBLE_ELEMENTS:
1270 : case PACKED_DOUBLE_ELEMENTS: {
1271 : // Empty array is FixedArray but not FixedDoubleArray.
1272 9 : if (length == 0) break;
1273 : FixedDoubleArray elements =
1274 : FixedDoubleArray::cast(array->elements());
1275 9 : for (uint32_t i = 0; i < length; i++) {
1276 18 : if (elements->is_the_hole(i)) {
1277 : // TODO(jkummerow/verwaest): We could be a bit more clever
1278 : // here: Check if there are no elements/getters on the
1279 : // prototype chain, and if so, allow creation of a holey
1280 : // result array.
1281 : // Same thing below (holey smi case).
1282 : failure = true;
1283 : break;
1284 : }
1285 : double double_value = elements->get_scalar(i);
1286 0 : double_storage->set(j, double_value);
1287 0 : j++;
1288 : }
1289 : break;
1290 : }
1291 : case HOLEY_SMI_ELEMENTS:
1292 : case PACKED_SMI_ELEMENTS: {
1293 : Object the_hole = ReadOnlyRoots(isolate).the_hole_value();
1294 : FixedArray elements(FixedArray::cast(array->elements()));
1295 0 : for (uint32_t i = 0; i < length; i++) {
1296 0 : Object element = elements->get(i);
1297 0 : if (element == the_hole) {
1298 : failure = true;
1299 : break;
1300 : }
1301 : int32_t int_value = Smi::ToInt(element);
1302 0 : double_storage->set(j, int_value);
1303 0 : j++;
1304 : }
1305 : break;
1306 : }
1307 : case HOLEY_ELEMENTS:
1308 : case PACKED_ELEMENTS:
1309 : case PACKED_FROZEN_ELEMENTS:
1310 : case PACKED_SEALED_ELEMENTS:
1311 : case DICTIONARY_ELEMENTS:
1312 : case NO_ELEMENTS:
1313 : DCHECK_EQ(0u, length);
1314 : break;
1315 : default:
1316 0 : UNREACHABLE();
1317 : }
1318 : }
1319 27 : if (failure) break;
1320 : }
1321 : }
1322 18 : if (!failure) {
1323 18 : return *isolate->factory()->NewJSArrayWithElements(storage, kind, j);
1324 : }
1325 : // In case of failure, fall through.
1326 : }
1327 :
1328 : Handle<HeapObject> storage;
1329 6118 : if (fast_case) {
1330 : // The backing storage array must have non-existing elements to preserve
1331 : // holes across concat operations.
1332 : storage =
1333 2386 : isolate->factory()->NewFixedArrayWithHoles(estimate_result_length);
1334 3732 : } else if (is_array_species) {
1335 3444 : storage = NumberDictionary::New(isolate, estimate_nof);
1336 : } else {
1337 : DCHECK(species->IsConstructor());
1338 : Handle<Object> length(Smi::kZero, isolate);
1339 : Handle<Object> storage_object;
1340 576 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1341 : isolate, storage_object,
1342 : Execution::New(isolate, species, species, 1, &length));
1343 288 : storage = Handle<HeapObject>::cast(storage_object);
1344 : }
1345 :
1346 6118 : ArrayConcatVisitor visitor(isolate, storage, fast_case);
1347 :
1348 1830464 : for (int i = 0; i < argument_count; i++) {
1349 : Handle<Object> obj = args->at(i);
1350 912389 : Maybe<bool> spreadable = IsConcatSpreadable(isolate, obj);
1351 912443 : MAYBE_RETURN(spreadable, ReadOnlyRoots(isolate).exception());
1352 912335 : if (spreadable.FromJust()) {
1353 7938 : Handle<JSReceiver> object = Handle<JSReceiver>::cast(obj);
1354 7938 : if (!IterateElements(isolate, object, &visitor)) {
1355 162 : return ReadOnlyRoots(isolate).exception();
1356 : }
1357 : } else {
1358 904397 : if (!visitor.visit(0, obj)) return ReadOnlyRoots(isolate).exception();
1359 904397 : visitor.increase_index_offset(1);
1360 : }
1361 : }
1362 :
1363 5902 : if (visitor.exceeds_array_limit()) {
1364 72 : THROW_NEW_ERROR_RETURN_FAILURE(
1365 : isolate, NewRangeError(MessageTemplate::kInvalidArrayLength));
1366 : }
1367 :
1368 5866 : if (is_array_species) {
1369 11264 : return *visitor.ToArray();
1370 : } else {
1371 477 : RETURN_RESULT_OR_FAILURE(isolate, visitor.ToJSReceiver());
1372 : }
1373 : }
1374 :
1375 573831 : bool IsSimpleArray(Isolate* isolate, Handle<JSArray> obj) {
1376 : DisallowHeapAllocation no_gc;
1377 : Map map = obj->map();
1378 : // If there is only the 'length' property we are fine.
1379 573831 : if (map->prototype() ==
1380 2295270 : isolate->native_context()->initial_array_prototype() &&
1381 : map->NumberOfOwnDescriptors() == 1) {
1382 : return true;
1383 : }
1384 : // TODO(cbruni): slower lookup for array subclasses and support slow
1385 : // @@IsConcatSpreadable lookup.
1386 54 : return false;
1387 : }
1388 :
1389 295068 : MaybeHandle<JSArray> Fast_ArrayConcat(Isolate* isolate,
1390 : BuiltinArguments* args) {
1391 295068 : if (!isolate->IsIsConcatSpreadableLookupChainIntact()) {
1392 5151 : return MaybeHandle<JSArray>();
1393 : }
1394 : // We shouldn't overflow when adding another len.
1395 : const int kHalfOfMaxInt = 1 << (kBitsPerInt - 2);
1396 : STATIC_ASSERT(FixedArray::kMaxLength < kHalfOfMaxInt);
1397 : STATIC_ASSERT(FixedDoubleArray::kMaxLength < kHalfOfMaxInt);
1398 : USE(kHalfOfMaxInt);
1399 :
1400 : int n_arguments = args->length();
1401 : int result_len = 0;
1402 : {
1403 : DisallowHeapAllocation no_gc;
1404 : // Iterate through all the arguments performing checks
1405 : // and calculating total length.
1406 1437453 : for (int i = 0; i < n_arguments; i++) {
1407 : Object arg = (*args)[i];
1408 579107 : if (!arg->IsJSArray()) return MaybeHandle<JSArray>();
1409 575071 : if (!HasOnlySimpleReceiverElements(isolate, JSObject::cast(arg))) {
1410 1046 : return MaybeHandle<JSArray>();
1411 : }
1412 : // TODO(cbruni): support fast concatenation of DICTIONARY_ELEMENTS.
1413 574025 : if (!JSObject::cast(arg)->HasFastElements()) {
1414 194 : return MaybeHandle<JSArray>();
1415 : }
1416 : Handle<JSArray> array(JSArray::cast(arg), isolate);
1417 573831 : if (!IsSimpleArray(isolate, array)) {
1418 54 : return MaybeHandle<JSArray>();
1419 : }
1420 : // The Array length is guaranted to be <= kHalfOfMaxInt thus we won't
1421 : // overflow.
1422 573777 : result_len += Smi::ToInt(array->length());
1423 : DCHECK_GE(result_len, 0);
1424 : // Throw an Error if we overflow the FixedArray limits
1425 573777 : if (FixedDoubleArray::kMaxLength < result_len ||
1426 : FixedArray::kMaxLength < result_len) {
1427 : AllowHeapAllocation gc;
1428 18 : THROW_NEW_ERROR(isolate,
1429 : NewRangeError(MessageTemplate::kInvalidArrayLength),
1430 : JSArray);
1431 : }
1432 : }
1433 : }
1434 284578 : return ElementsAccessor::Concat(isolate, args, n_arguments, result_len);
1435 : }
1436 :
1437 : } // namespace
1438 :
1439 : // ES6 22.1.3.1 Array.prototype.concat
1440 1454875 : BUILTIN(ArrayConcat) {
1441 : HandleScope scope(isolate);
1442 :
1443 : Handle<Object> receiver = args.receiver();
1444 582211 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1445 : isolate, receiver,
1446 : Object::ToObject(isolate, args.receiver(), "Array.prototype.concat"));
1447 : args.set_at(0, *receiver);
1448 :
1449 : Handle<JSArray> result_array;
1450 :
1451 : // Avoid a real species read to avoid extra lookups to the array constructor
1452 870000 : if (V8_LIKELY(receiver->IsJSArray() &&
1453 : Handle<JSArray>::cast(receiver)->HasArrayPrototype(isolate) &&
1454 : isolate->IsArraySpeciesLookupChainIntact())) {
1455 578362 : if (Fast_ArrayConcat(isolate, &args).ToHandle(&result_array)) {
1456 284530 : return *result_array;
1457 : }
1458 4651 : if (isolate->has_pending_exception())
1459 9 : return ReadOnlyRoots(isolate).exception();
1460 : }
1461 : // Reading @@species happens before anything else with a side effect, so
1462 : // we can do it here to determine whether to take the fast path.
1463 : Handle<Object> species;
1464 12350 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1465 : isolate, species, Object::ArraySpeciesConstructor(isolate, receiver));
1466 12350 : if (*species == *isolate->array_function()) {
1467 11774 : if (Fast_ArrayConcat(isolate, &args).ToHandle(&result_array)) {
1468 48 : return *result_array;
1469 : }
1470 5839 : if (isolate->has_pending_exception())
1471 0 : return ReadOnlyRoots(isolate).exception();
1472 : }
1473 6127 : return Slow_ArrayConcat(&args, species, isolate);
1474 : }
1475 :
1476 : } // namespace internal
1477 121996 : } // namespace v8
|
