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 1156991 : return JSObject::PrototypeHasNoElements(isolate, receiver);
29 : }
30 :
31 595887 : inline bool HasSimpleElements(JSObject current) {
32 1191765 : return !current->map()->IsCustomElementsReceiverMap() &&
33 1191765 : !current->GetElementsAccessor()->HasAccessors(current);
34 : }
35 :
36 574956 : inline bool HasOnlySimpleReceiverElements(Isolate* isolate, JSObject receiver) {
37 : // Check that we have no accessors on the receiver's elements.
38 574956 : if (!HasSimpleElements(receiver)) return false;
39 574776 : return JSObject::PrototypeHasNoElements(isolate, receiver);
40 : }
41 :
42 6845 : inline bool HasOnlySimpleElements(Isolate* isolate, JSReceiver receiver) {
43 : DisallowHeapAllocation no_gc;
44 : PrototypeIterator iter(isolate, receiver, kStartAtReceiver);
45 48311 : for (; !iter.IsAtEnd(); iter.Advance()) {
46 21129 : if (iter.GetCurrent()->IsJSProxy()) return false;
47 20931 : JSObject current = iter.GetCurrent<JSObject>();
48 20931 : 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 919862 : void MatchArrayElementsKindToArguments(Isolate* isolate, Handle<JSArray> array,
57 : BuiltinArguments* args,
58 : int first_arg_index, int num_arguments) {
59 919862 : int args_length = args->length();
60 921217 : if (first_arg_index >= args_length) return;
61 :
62 919770 : ElementsKind origin_kind = array->GetElementsKind();
63 :
64 : // We do not need to transition for PACKED/HOLEY_ELEMENTS.
65 919770 : if (IsObjectElementsKind(origin_kind)) return;
66 :
67 : ElementsKind target_kind = origin_kind;
68 : {
69 : DisallowHeapAllocation no_gc;
70 1837014 : int last_arg_index = std::min(first_arg_index + num_arguments, args_length);
71 2754415 : for (int i = first_arg_index; i < last_arg_index; i++) {
72 : Object arg = (*args)[i];
73 918571 : if (arg->IsHeapObject()) {
74 818 : if (arg->IsHeapNumber()) {
75 : target_kind = PACKED_DOUBLE_ELEMENTS;
76 : } else {
77 : target_kind = PACKED_ELEMENTS;
78 : break;
79 : }
80 : }
81 : }
82 : }
83 918507 : 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 1480 : 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 1162729 : inline bool EnsureJSArrayWithWritableFastElements(Isolate* isolate,
96 : Handle<Object> receiver,
97 : BuiltinArguments* args,
98 : int first_arg_index,
99 : int num_arguments) {
100 1162729 : if (!receiver->IsJSArray()) return false;
101 : Handle<JSArray> array = Handle<JSArray>::cast(receiver);
102 1159606 : ElementsKind origin_kind = array->GetElementsKind();
103 1159606 : if (IsDictionaryElementsKind(origin_kind)) return false;
104 1157272 : if (!array->map()->is_extensible()) return false;
105 1157272 : 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 919763 : 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 914294 : 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 913994 : num_arguments);
119 913994 : 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 14768 : V8_WARN_UNUSED_RESULT Maybe<double> GetRelativeIndex(Isolate* isolate,
127 : double length,
128 : Handle<Object> index,
129 : double init_if_undefined) {
130 14768 : double relative_index = init_if_undefined;
131 14768 : 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 14768 : 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 189558 : V8_WARN_UNUSED_RESULT Maybe<double> GetLengthProperty(
148 : Isolate* isolate, Handle<JSReceiver> receiver) {
149 189558 : 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 7322 : 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 7322 : if (end_index > kMaxUInt32) return false;
212 7313 : if (!receiver->IsJSObject()) return false;
213 :
214 7313 : 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 6970 : 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 6945 : CHECK(DoubleToUint32IfEqualToSelf(start_index, &start));
236 6945 : CHECK(DoubleToUint32IfEqualToSelf(end_index, &end));
237 :
238 6945 : ElementsAccessor* accessor = array->GetElementsAccessor();
239 13890 : accessor->Fill(array, value, start, end);
240 6945 : return true;
241 : }
242 : } // namespace
243 :
244 37100 : BUILTIN(ArrayPrototypeFill) {
245 : HandleScope scope(isolate);
246 :
247 7420 : 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 14822 : 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 14768 : 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 7384 : Handle<Object> start = args.atOrUndefined(isolate, 2);
267 :
268 : double start_index;
269 14768 : 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 7384 : Handle<Object> end = args.atOrUndefined(isolate, 3);
277 :
278 : double end_index;
279 14768 : MAYBE_ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
280 : isolate, end_index, GetRelativeIndex(isolate, length, end, length));
281 :
282 7446 : 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 7322 : Handle<Object> value = args.atOrUndefined(isolate, 1);
290 :
291 7322 : if (TryFastArrayFill(isolate, &args, receiver, value, start_index,
292 : end_index)) {
293 6945 : return *receiver;
294 : }
295 377 : return GenericArrayFill(isolate, receiver, value, start_index, end_index);
296 : }
297 :
298 : namespace {
299 7719 : V8_WARN_UNUSED_RESULT Object GenericArrayPush(Isolate* isolate,
300 : BuiltinArguments* args) {
301 : // 1. Let O be ? ToObject(this value).
302 : Handle<JSReceiver> receiver;
303 15699 : 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 14925 : 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 7449 : 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 7449 : 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 22722 : 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 15628 : Handle<Object> element = args->at(i + 1);
331 :
332 : // b. Perform ? Set(O, ! ToString(len), E, true).
333 7814 : if (length <= static_cast<double>(JSArray::kMaxArrayIndex)) {
334 23615 : 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 7641 : ++length;
350 : }
351 :
352 : // 7. Perform ? Set(O, "length", len, true).
353 7267 : Handle<Object> final_length = isolate->factory()->NewNumber(length);
354 14570 : 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 4573480 : BUILTIN(ArrayPush) {
366 : HandleScope scope(isolate);
367 : Handle<Object> receiver = args.receiver();
368 914696 : if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, &args, 1,
369 : args.length() - 1)) {
370 7647 : 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 292730 : BUILTIN(ArrayPop) {
452 : HandleScope scope(isolate);
453 : Handle<Object> receiver = args.receiver();
454 58546 : 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 55335 : uint32_t len = static_cast<uint32_t>(array->length()->Number());
461 55391 : if (len == 0) return ReadOnlyRoots(isolate).undefined_value();
462 :
463 55279 : if (JSArray::HasReadOnlyLength(array)) {
464 225 : return GenericArrayPop(isolate, &args);
465 : }
466 :
467 : Handle<Object> result;
468 55054 : if (IsJSArrayFastElementMovingAllowed(isolate, JSArray::cast(*receiver))) {
469 : // Fast Elements Path
470 53218 : 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 182174 : V8_WARN_UNUSED_RESULT bool CanUseFastArrayShift(Isolate* isolate,
486 : Handle<JSReceiver> receiver) {
487 364348 : if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, nullptr, 0,
488 364348 : 0) ||
489 : !IsJSArrayFastElementMovingAllowed(isolate, JSArray::cast(*receiver))) {
490 : return false;
491 : }
492 :
493 182174 : Handle<JSArray> array = Handle<JSArray>::cast(receiver);
494 182174 : 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 910870 : BUILTIN(ArrayShift) {
564 : HandleScope scope(isolate);
565 :
566 : // 1. Let O be ? ToObject(this value).
567 : Handle<JSReceiver> receiver;
568 364348 : 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 364348 : MAYBE_ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
574 : isolate, length, GetLengthProperty(isolate, receiver));
575 :
576 : // 3. If len is zero, then.
577 182174 : 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 182174 : if (CanUseFastArrayShift(isolate, receiver)) {
587 : Handle<JSArray> array = Handle<JSArray>::cast(receiver);
588 364348 : return *array->GetElementsAccessor()->Shift(array);
589 : }
590 :
591 0 : return GenericArrayShift(isolate, receiver, length);
592 : }
593 :
594 29340 : 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 5868 : MatchArrayElementsKindToArguments(isolate, array, &args, 1,
606 5868 : args.length() - 1);
607 :
608 5868 : int to_add = args.length() - 1;
609 5868 : 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 6074 : 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 6074 : ExceedsLimitField::encode(false) |
644 6074 : IsFixedArrayField::encode(storage->IsFixedArray()) |
645 : HasSimpleElementsField::encode(
646 6362 : storage->IsFixedArray() ||
647 18222 : !storage->map()->IsCustomElementsReceiverMap())) {
648 : DCHECK(!(this->fast_elements() && !is_fixed_array()));
649 6074 : }
650 :
651 6074 : ~ArrayConcatVisitor() { clear_storage(); }
652 :
653 1285742 : V8_WARN_UNUSED_RESULT bool visit(uint32_t i, Handle<Object> elm) {
654 1285742 : uint32_t index = index_offset_ + i;
655 :
656 1285742 : 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 1285706 : 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 1285382 : if (fast_elements()) {
672 906988 : if (index < static_cast<uint32_t>(storage_fixed_array()->length())) {
673 906970 : storage_fixed_array()->set(index, *elm);
674 906970 : 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 912085 : void increase_index_offset(uint32_t delta) {
701 912085 : if (JSObject::kMaxElementCount - index_offset_ < delta) {
702 45 : index_offset_ = JSObject::kMaxElementCount;
703 : } else {
704 912040 : 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 1816733 : if (fast_elements() &&
710 1809296 : index_offset_ >
711 : static_cast<uint32_t>(FixedArrayBase::cast(*storage_)->length())) {
712 9 : SetDictionaryMode();
713 : }
714 912085 : }
715 :
716 : bool exceeds_array_limit() const {
717 : return ExceedsLimitField::decode(bit_field_);
718 : }
719 :
720 5588 : Handle<JSArray> ToArray() {
721 : DCHECK(is_fixed_array());
722 5588 : Handle<JSArray> array = isolate_->factory()->NewJSArray(0);
723 : Handle<Object> length =
724 5588 : isolate_->factory()->NewNumber(static_cast<double>(index_offset_));
725 : Handle<Map> map = JSObject::GetElementsTransitionMap(
726 11176 : array, fast_elements() ? HOLEY_ELEMENTS : DICTIONARY_ELEMENTS);
727 5588 : array->set_length(*length);
728 11176 : array->set_elements(*storage_fixed_array());
729 5588 : array->synchronized_set_map(*map);
730 5588 : 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 7991 : 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 7520 : uint32_t EstimateElementCount(Isolate* isolate, Handle<JSArray> array) {
813 : DisallowHeapAllocation no_gc;
814 7520 : uint32_t length = static_cast<uint32_t>(array->length()->Number());
815 : int element_count = 0;
816 7520 : switch (array->GetElementsKind()) {
817 : case PACKED_SMI_ELEMENTS:
818 : case HOLEY_SMI_ELEMENTS:
819 : case PACKED_ELEMENTS:
820 : case HOLEY_ELEMENTS: {
821 : // Fast elements can't have lengths that are not representable by
822 : // a 32-bit signed integer.
823 : DCHECK_GE(static_cast<int32_t>(FixedArray::kMaxLength), 0);
824 6806 : int fast_length = static_cast<int>(length);
825 : FixedArray elements = FixedArray::cast(array->elements());
826 94028 : for (int i = 0; i < fast_length; i++) {
827 43611 : if (!elements->get(i)->IsTheHole(isolate)) element_count++;
828 : }
829 : break;
830 : }
831 : case PACKED_DOUBLE_ELEMENTS:
832 : case HOLEY_DOUBLE_ELEMENTS: {
833 : // Fast elements can't have lengths that are not representable by
834 : // a 32-bit signed integer.
835 : DCHECK_GE(static_cast<int32_t>(FixedDoubleArray::kMaxLength), 0);
836 94 : int fast_length = static_cast<int>(length);
837 94 : if (array->elements()->IsFixedArray()) {
838 : DCHECK_EQ(FixedArray::cast(array->elements())->length(), 0);
839 : break;
840 : }
841 : FixedDoubleArray elements = FixedDoubleArray::cast(array->elements());
842 591443 : for (int i = 0; i < fast_length; i++) {
843 591358 : if (!elements->is_the_hole(i)) element_count++;
844 : }
845 : break;
846 : }
847 : case DICTIONARY_ELEMENTS: {
848 620 : NumberDictionary dictionary = NumberDictionary::cast(array->elements());
849 : int capacity = dictionary->Capacity();
850 : ReadOnlyRoots roots(isolate);
851 24672 : for (int i = 0; i < capacity; i++) {
852 12026 : Object key = dictionary->KeyAt(i);
853 12026 : if (dictionary->IsKey(roots, key)) {
854 4692 : element_count++;
855 : }
856 : }
857 : break;
858 : }
859 : #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype) case TYPE##_ELEMENTS:
860 :
861 : TYPED_ARRAYS(TYPED_ARRAY_CASE)
862 : #undef TYPED_ARRAY_CASE
863 : // External arrays are always dense.
864 0 : return length;
865 : case NO_ELEMENTS:
866 : return 0;
867 : case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
868 : case SLOW_SLOPPY_ARGUMENTS_ELEMENTS:
869 : case FAST_STRING_WRAPPER_ELEMENTS:
870 : case SLOW_STRING_WRAPPER_ELEMENTS:
871 0 : UNREACHABLE();
872 : }
873 : // As an estimate, we assume that the prototype doesn't contain any
874 : // inherited elements.
875 7520 : return element_count;
876 : }
877 :
878 1590 : void CollectElementIndices(Isolate* isolate, Handle<JSObject> object,
879 : uint32_t range, std::vector<uint32_t>* indices) {
880 1590 : ElementsKind kind = object->GetElementsKind();
881 1590 : switch (kind) {
882 : case PACKED_SMI_ELEMENTS:
883 : case PACKED_ELEMENTS:
884 : case HOLEY_SMI_ELEMENTS:
885 : case HOLEY_ELEMENTS: {
886 : DisallowHeapAllocation no_gc;
887 : FixedArray elements = FixedArray::cast(object->elements());
888 1051 : uint32_t length = static_cast<uint32_t>(elements->length());
889 1051 : if (range < length) length = range;
890 41209 : for (uint32_t i = 0; i < length; i++) {
891 80316 : if (!elements->get(i)->IsTheHole(isolate)) {
892 207 : indices->push_back(i);
893 : }
894 : }
895 : break;
896 : }
897 : case HOLEY_DOUBLE_ELEMENTS:
898 : case PACKED_DOUBLE_ELEMENTS: {
899 9 : if (object->elements()->IsFixedArray()) {
900 : DCHECK_EQ(object->elements()->length(), 0);
901 : break;
902 : }
903 : Handle<FixedDoubleArray> elements(
904 : FixedDoubleArray::cast(object->elements()), isolate);
905 9 : uint32_t length = static_cast<uint32_t>(elements->length());
906 9 : if (range < length) length = range;
907 18 : for (uint32_t i = 0; i < length; i++) {
908 18 : if (!elements->is_the_hole(i)) {
909 9 : indices->push_back(i);
910 : }
911 : }
912 9 : break;
913 : }
914 : case DICTIONARY_ELEMENTS: {
915 : DisallowHeapAllocation no_gc;
916 476 : NumberDictionary dict = NumberDictionary::cast(object->elements());
917 476 : uint32_t capacity = dict->Capacity();
918 : ReadOnlyRoots roots(isolate);
919 5293 : FOR_WITH_HANDLE_SCOPE(isolate, uint32_t, j = 0, j, j < capacity, j++, {
920 : Object k = dict->KeyAt(j);
921 : if (!dict->IsKey(roots, k)) continue;
922 : DCHECK(k->IsNumber());
923 : uint32_t index = static_cast<uint32_t>(k->Number());
924 : if (index < range) {
925 : indices->push_back(index);
926 : }
927 : });
928 : break;
929 : }
930 : #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype) case TYPE##_ELEMENTS:
931 :
932 : TYPED_ARRAYS(TYPED_ARRAY_CASE)
933 : #undef TYPED_ARRAY_CASE
934 : {
935 9 : uint32_t length = static_cast<uint32_t>(object->elements()->length());
936 9 : if (range <= length) {
937 : length = range;
938 : // We will add all indices, so we might as well clear it first
939 : // and avoid duplicates.
940 : indices->clear();
941 : }
942 27 : for (uint32_t i = 0; i < length; i++) {
943 18 : indices->push_back(i);
944 : }
945 9 : if (length == range) return; // All indices accounted for already.
946 : break;
947 : }
948 : case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
949 : case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: {
950 : DisallowHeapAllocation no_gc;
951 45 : FixedArrayBase elements = object->elements();
952 45 : JSObject raw_object = *object;
953 45 : ElementsAccessor* accessor = object->GetElementsAccessor();
954 270072 : for (uint32_t i = 0; i < range; i++) {
955 270027 : if (accessor->HasElement(raw_object, i, elements)) {
956 54 : indices->push_back(i);
957 : }
958 : }
959 : break;
960 : }
961 : case FAST_STRING_WRAPPER_ELEMENTS:
962 : case SLOW_STRING_WRAPPER_ELEMENTS: {
963 : DCHECK(object->IsJSValue());
964 : Handle<JSValue> js_value = Handle<JSValue>::cast(object);
965 : DCHECK(js_value->value()->IsString());
966 : Handle<String> string(String::cast(js_value->value()), isolate);
967 0 : uint32_t length = static_cast<uint32_t>(string->length());
968 0 : uint32_t i = 0;
969 : uint32_t limit = Min(length, range);
970 0 : for (; i < limit; i++) {
971 0 : indices->push_back(i);
972 : }
973 0 : ElementsAccessor* accessor = object->GetElementsAccessor();
974 0 : for (; i < range; i++) {
975 0 : if (accessor->HasElement(*object, i)) {
976 0 : indices->push_back(i);
977 : }
978 : }
979 : break;
980 : }
981 : case NO_ELEMENTS:
982 : break;
983 : }
984 :
985 1590 : PrototypeIterator iter(isolate, object);
986 1590 : if (!iter.IsAtEnd()) {
987 : // The prototype will usually have no inherited element indices,
988 : // but we have to check.
989 : CollectElementIndices(
990 1114 : isolate, PrototypeIterator::GetCurrent<JSObject>(iter), range, indices);
991 : }
992 : }
993 :
994 1144 : bool IterateElementsSlow(Isolate* isolate, Handle<JSReceiver> receiver,
995 : uint32_t length, ArrayConcatVisitor* visitor) {
996 5861706 : FOR_WITH_HANDLE_SCOPE(isolate, uint32_t, i = 0, i, i < length, ++i, {
997 : Maybe<bool> maybe = JSReceiver::HasElement(receiver, i);
998 : if (maybe.IsNothing()) return false;
999 : if (maybe.FromJust()) {
1000 : Handle<Object> element_value;
1001 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(
1002 : isolate, element_value, JSReceiver::GetElement(isolate, receiver, i),
1003 : false);
1004 : if (!visitor->visit(i, element_value)) return false;
1005 : }
1006 : });
1007 1126 : visitor->increase_index_offset(length);
1008 1126 : return true;
1009 : }
1010 : /**
1011 : * A helper function that visits "array" elements of a JSReceiver in numerical
1012 : * order.
1013 : *
1014 : * The visitor argument called for each existing element in the array
1015 : * with the element index and the element's value.
1016 : * Afterwards it increments the base-index of the visitor by the array
1017 : * length.
1018 : * Returns false if any access threw an exception, otherwise true.
1019 : */
1020 7872 : bool IterateElements(Isolate* isolate, Handle<JSReceiver> receiver,
1021 : ArrayConcatVisitor* visitor) {
1022 7872 : uint32_t length = 0;
1023 :
1024 7872 : if (receiver->IsJSArray()) {
1025 : Handle<JSArray> array = Handle<JSArray>::cast(receiver);
1026 6845 : length = static_cast<uint32_t>(array->length()->Number());
1027 : } else {
1028 : Handle<Object> val;
1029 2054 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(
1030 : isolate, val, Object::GetLengthFromArrayLike(isolate, receiver), false);
1031 1892 : if (visitor->index_offset() + val->Number() > kMaxSafeInteger) {
1032 54 : isolate->Throw(*isolate->factory()->NewTypeError(
1033 54 : MessageTemplate::kInvalidArrayLength));
1034 27 : return false;
1035 : }
1036 : // TODO(caitp): Support larger element indexes (up to 2^53-1).
1037 919 : if (!val->ToUint32(&length)) {
1038 0 : length = 0;
1039 : }
1040 : // TODO(cbruni): handle other element kind as well
1041 919 : return IterateElementsSlow(isolate, receiver, length, visitor);
1042 : }
1043 :
1044 13492 : if (!HasOnlySimpleElements(isolate, *receiver) ||
1045 : !visitor->has_simple_elements()) {
1046 225 : return IterateElementsSlow(isolate, receiver, length, visitor);
1047 : }
1048 : Handle<JSObject> array = Handle<JSObject>::cast(receiver);
1049 :
1050 6620 : switch (array->GetElementsKind()) {
1051 : case PACKED_SMI_ELEMENTS:
1052 : case PACKED_ELEMENTS:
1053 : case HOLEY_SMI_ELEMENTS:
1054 : case HOLEY_ELEMENTS: {
1055 : // Run through the elements FixedArray and use HasElement and GetElement
1056 : // to check the prototype for missing elements.
1057 : Handle<FixedArray> elements(FixedArray::cast(array->elements()), isolate);
1058 6104 : int fast_length = static_cast<int>(length);
1059 : DCHECK(fast_length <= elements->length());
1060 213369 : FOR_WITH_HANDLE_SCOPE(isolate, int, j = 0, j, j < fast_length, j++, {
1061 : Handle<Object> element_value(elements->get(j), isolate);
1062 : if (!element_value->IsTheHole(isolate)) {
1063 : if (!visitor->visit(j, element_value)) return false;
1064 : } else {
1065 : Maybe<bool> maybe = JSReceiver::HasElement(array, j);
1066 : if (maybe.IsNothing()) return false;
1067 : if (maybe.FromJust()) {
1068 : // Call GetElement on array, not its prototype, or getters won't
1069 : // have the correct receiver.
1070 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(
1071 : isolate, element_value,
1072 : JSReceiver::GetElement(isolate, array, j), false);
1073 : if (!visitor->visit(j, element_value)) return false;
1074 : }
1075 : }
1076 : });
1077 : break;
1078 : }
1079 : case HOLEY_DOUBLE_ELEMENTS:
1080 : case PACKED_DOUBLE_ELEMENTS: {
1081 : // Empty array is FixedArray but not FixedDoubleArray.
1082 40 : if (length == 0) break;
1083 : // Run through the elements FixedArray and use HasElement and GetElement
1084 : // to check the prototype for missing elements.
1085 31 : if (array->elements()->IsFixedArray()) {
1086 : DCHECK_EQ(array->elements()->length(), 0);
1087 : break;
1088 : }
1089 : Handle<FixedDoubleArray> elements(
1090 : FixedDoubleArray::cast(array->elements()), isolate);
1091 31 : int fast_length = static_cast<int>(length);
1092 : DCHECK(fast_length <= elements->length());
1093 2760 : FOR_WITH_HANDLE_SCOPE(isolate, int, j = 0, j, j < fast_length, j++, {
1094 : if (!elements->is_the_hole(j)) {
1095 : double double_value = elements->get_scalar(j);
1096 : Handle<Object> element_value =
1097 : isolate->factory()->NewNumber(double_value);
1098 : if (!visitor->visit(j, element_value)) return false;
1099 : } else {
1100 : Maybe<bool> maybe = JSReceiver::HasElement(array, j);
1101 : if (maybe.IsNothing()) return false;
1102 : if (maybe.FromJust()) {
1103 : // Call GetElement on array, not its prototype, or getters won't
1104 : // have the correct receiver.
1105 : Handle<Object> element_value;
1106 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(
1107 : isolate, element_value,
1108 : JSReceiver::GetElement(isolate, array, j), false);
1109 : if (!visitor->visit(j, element_value)) return false;
1110 : }
1111 : }
1112 : });
1113 : break;
1114 : }
1115 :
1116 : case DICTIONARY_ELEMENTS: {
1117 : Handle<NumberDictionary> dict(array->element_dictionary(), isolate);
1118 : std::vector<uint32_t> indices;
1119 476 : indices.reserve(dict->Capacity() / 2);
1120 :
1121 : // Collect all indices in the object and the prototypes less
1122 : // than length. This might introduce duplicates in the indices list.
1123 476 : CollectElementIndices(isolate, array, length, &indices);
1124 : std::sort(indices.begin(), indices.end());
1125 : size_t n = indices.size();
1126 6700 : FOR_WITH_HANDLE_SCOPE(isolate, size_t, j = 0, j, j < n, (void)0, {
1127 : uint32_t index = indices[j];
1128 : Handle<Object> element;
1129 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(
1130 : isolate, element, JSReceiver::GetElement(isolate, array, index),
1131 : false);
1132 : if (!visitor->visit(index, element)) return false;
1133 : // Skip to next different index (i.e., omit duplicates).
1134 : do {
1135 : j++;
1136 : } while (j < n && indices[j] == index);
1137 : });
1138 : break;
1139 : }
1140 : case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
1141 : case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: {
1142 0 : FOR_WITH_HANDLE_SCOPE(
1143 : isolate, uint32_t, index = 0, index, index < length, index++, {
1144 : Handle<Object> element;
1145 : ASSIGN_RETURN_ON_EXCEPTION_VALUE(
1146 : isolate, element, JSReceiver::GetElement(isolate, array, index),
1147 : false);
1148 : if (!visitor->visit(index, element)) return false;
1149 : });
1150 : break;
1151 : }
1152 : case NO_ELEMENTS:
1153 : break;
1154 : #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype) case TYPE##_ELEMENTS:
1155 : TYPED_ARRAYS(TYPED_ARRAY_CASE)
1156 : #undef TYPED_ARRAY_CASE
1157 0 : return IterateElementsSlow(isolate, receiver, length, visitor);
1158 : case FAST_STRING_WRAPPER_ELEMENTS:
1159 : case SLOW_STRING_WRAPPER_ELEMENTS:
1160 : // |array| is guaranteed to be an array or typed array.
1161 0 : UNREACHABLE();
1162 : break;
1163 : }
1164 6584 : visitor->increase_index_offset(length);
1165 6584 : return true;
1166 : }
1167 :
1168 912301 : static Maybe<bool> IsConcatSpreadable(Isolate* isolate, Handle<Object> obj) {
1169 : HandleScope handle_scope(isolate);
1170 912301 : if (!obj->IsJSReceiver()) return Just(false);
1171 10321 : if (!isolate->IsIsConcatSpreadableLookupChainIntact(JSReceiver::cast(*obj))) {
1172 : // Slow path if @@isConcatSpreadable has been used.
1173 : Handle<Symbol> key(isolate->factory()->is_concat_spreadable_symbol());
1174 : Handle<Object> value;
1175 : MaybeHandle<Object> maybeValue =
1176 6132 : i::Runtime::GetObjectProperty(isolate, obj, key);
1177 8545 : if (!maybeValue.ToHandle(&value)) return Nothing<bool>();
1178 8473 : if (!value->IsUndefined(isolate)) return Just(value->BooleanValue(isolate));
1179 : }
1180 : return Object::IsArray(obj);
1181 : }
1182 :
1183 6083 : Object Slow_ArrayConcat(BuiltinArguments* args, Handle<Object> species,
1184 : Isolate* isolate) {
1185 : int argument_count = args->length();
1186 :
1187 12166 : bool is_array_species = *species == isolate->context()->array_function();
1188 :
1189 : // Pass 1: estimate the length and number of elements of the result.
1190 : // The actual length can be larger if any of the arguments have getters
1191 : // that mutate other arguments (but will otherwise be precise).
1192 : // The number of elements is precise if there are no inherited elements.
1193 :
1194 : ElementsKind kind = PACKED_SMI_ELEMENTS;
1195 :
1196 : uint32_t estimate_result_length = 0;
1197 : uint32_t estimate_nof = 0;
1198 4594053 : FOR_WITH_HANDLE_SCOPE(isolate, int, i = 0, i, i < argument_count, i++, {
1199 : Handle<Object> obj = args->at(i);
1200 : uint32_t length_estimate;
1201 : uint32_t element_estimate;
1202 : if (obj->IsJSArray()) {
1203 : Handle<JSArray> array(Handle<JSArray>::cast(obj));
1204 : length_estimate = static_cast<uint32_t>(array->length()->Number());
1205 : if (length_estimate != 0) {
1206 : ElementsKind array_kind =
1207 : GetPackedElementsKind(array->GetElementsKind());
1208 : kind = GetMoreGeneralElementsKind(kind, array_kind);
1209 : }
1210 : element_estimate = EstimateElementCount(isolate, array);
1211 : } else {
1212 : if (obj->IsHeapObject()) {
1213 : kind = GetMoreGeneralElementsKind(
1214 : kind, obj->IsNumber() ? PACKED_DOUBLE_ELEMENTS : PACKED_ELEMENTS);
1215 : }
1216 : length_estimate = 1;
1217 : element_estimate = 1;
1218 : }
1219 : // Avoid overflows by capping at kMaxElementCount.
1220 : if (JSObject::kMaxElementCount - estimate_result_length < length_estimate) {
1221 : estimate_result_length = JSObject::kMaxElementCount;
1222 : } else {
1223 : estimate_result_length += length_estimate;
1224 : }
1225 : if (JSObject::kMaxElementCount - estimate_nof < element_estimate) {
1226 : estimate_nof = JSObject::kMaxElementCount;
1227 : } else {
1228 : estimate_nof += element_estimate;
1229 : }
1230 : });
1231 :
1232 : // If estimated number of elements is more than half of length, a
1233 : // fixed array (fast case) is more time and space-efficient than a
1234 : // dictionary.
1235 5795 : bool fast_case = is_array_species &&
1236 11167 : (estimate_nof * 2) >= estimate_result_length &&
1237 5084 : isolate->IsIsConcatSpreadableLookupChainIntact();
1238 :
1239 6083 : if (fast_case && kind == PACKED_DOUBLE_ELEMENTS) {
1240 : Handle<FixedArrayBase> storage =
1241 18 : isolate->factory()->NewFixedDoubleArray(estimate_result_length);
1242 : int j = 0;
1243 : bool failure = false;
1244 18 : if (estimate_result_length > 0) {
1245 : Handle<FixedDoubleArray> double_storage =
1246 : Handle<FixedDoubleArray>::cast(storage);
1247 54 : for (int i = 0; i < argument_count; i++) {
1248 : Handle<Object> obj = args->at(i);
1249 27 : if (obj->IsSmi()) {
1250 0 : double_storage->set(j, Smi::ToInt(*obj));
1251 0 : j++;
1252 27 : } else if (obj->IsNumber()) {
1253 9 : double_storage->set(j, obj->Number());
1254 9 : j++;
1255 : } else {
1256 : DisallowHeapAllocation no_gc;
1257 18 : JSArray array = JSArray::cast(*obj);
1258 18 : uint32_t length = static_cast<uint32_t>(array->length()->Number());
1259 18 : switch (array->GetElementsKind()) {
1260 : case HOLEY_DOUBLE_ELEMENTS:
1261 : case PACKED_DOUBLE_ELEMENTS: {
1262 : // Empty array is FixedArray but not FixedDoubleArray.
1263 9 : if (length == 0) break;
1264 : FixedDoubleArray elements =
1265 : FixedDoubleArray::cast(array->elements());
1266 9 : for (uint32_t i = 0; i < length; i++) {
1267 18 : if (elements->is_the_hole(i)) {
1268 : // TODO(jkummerow/verwaest): We could be a bit more clever
1269 : // here: Check if there are no elements/getters on the
1270 : // prototype chain, and if so, allow creation of a holey
1271 : // result array.
1272 : // Same thing below (holey smi case).
1273 : failure = true;
1274 : break;
1275 : }
1276 : double double_value = elements->get_scalar(i);
1277 0 : double_storage->set(j, double_value);
1278 0 : j++;
1279 : }
1280 : break;
1281 : }
1282 : case HOLEY_SMI_ELEMENTS:
1283 : case PACKED_SMI_ELEMENTS: {
1284 : Object the_hole = ReadOnlyRoots(isolate).the_hole_value();
1285 : FixedArray elements(FixedArray::cast(array->elements()));
1286 0 : for (uint32_t i = 0; i < length; i++) {
1287 0 : Object element = elements->get(i);
1288 0 : if (element == the_hole) {
1289 : failure = true;
1290 : break;
1291 : }
1292 : int32_t int_value = Smi::ToInt(element);
1293 0 : double_storage->set(j, int_value);
1294 0 : j++;
1295 : }
1296 : break;
1297 : }
1298 : case HOLEY_ELEMENTS:
1299 : case PACKED_ELEMENTS:
1300 : case DICTIONARY_ELEMENTS:
1301 : case NO_ELEMENTS:
1302 : DCHECK_EQ(0u, length);
1303 : break;
1304 : default:
1305 0 : UNREACHABLE();
1306 : }
1307 : }
1308 27 : if (failure) break;
1309 : }
1310 : }
1311 18 : if (!failure) {
1312 18 : return *isolate->factory()->NewJSArrayWithElements(storage, kind, j);
1313 : }
1314 : // In case of failure, fall through.
1315 : }
1316 :
1317 : Handle<HeapObject> storage;
1318 6074 : if (fast_case) {
1319 : // The backing storage array must have non-existing elements to preserve
1320 : // holes across concat operations.
1321 : storage =
1322 2342 : isolate->factory()->NewFixedArrayWithHoles(estimate_result_length);
1323 3732 : } else if (is_array_species) {
1324 3444 : storage = NumberDictionary::New(isolate, estimate_nof);
1325 : } else {
1326 : DCHECK(species->IsConstructor());
1327 : Handle<Object> length(Smi::kZero, isolate);
1328 : Handle<Object> storage_object;
1329 576 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1330 : isolate, storage_object,
1331 : Execution::New(isolate, species, species, 1, &length));
1332 288 : storage = Handle<HeapObject>::cast(storage_object);
1333 : }
1334 :
1335 6074 : ArrayConcatVisitor visitor(isolate, storage, fast_case);
1336 :
1337 1830244 : for (int i = 0; i < argument_count; i++) {
1338 : Handle<Object> obj = args->at(i);
1339 912301 : Maybe<bool> spreadable = IsConcatSpreadable(isolate, obj);
1340 912355 : MAYBE_RETURN(spreadable, ReadOnlyRoots(isolate).exception());
1341 912247 : if (spreadable.FromJust()) {
1342 7872 : Handle<JSReceiver> object = Handle<JSReceiver>::cast(obj);
1343 7872 : if (!IterateElements(isolate, object, &visitor)) {
1344 162 : return ReadOnlyRoots(isolate).exception();
1345 : }
1346 : } else {
1347 904375 : if (!visitor.visit(0, obj)) return ReadOnlyRoots(isolate).exception();
1348 904375 : visitor.increase_index_offset(1);
1349 : }
1350 : }
1351 :
1352 5858 : if (visitor.exceeds_array_limit()) {
1353 72 : THROW_NEW_ERROR_RETURN_FAILURE(
1354 : isolate, NewRangeError(MessageTemplate::kInvalidArrayLength));
1355 : }
1356 :
1357 5822 : if (is_array_species) {
1358 11176 : return *visitor.ToArray();
1359 : } else {
1360 477 : RETURN_RESULT_OR_FAILURE(isolate, visitor.ToJSReceiver());
1361 : }
1362 : }
1363 :
1364 573804 : bool IsSimpleArray(Isolate* isolate, Handle<JSArray> obj) {
1365 : DisallowHeapAllocation no_gc;
1366 : Map map = obj->map();
1367 : // If there is only the 'length' property we are fine.
1368 573804 : if (map->prototype() ==
1369 2295162 : isolate->native_context()->initial_array_prototype() &&
1370 : map->NumberOfOwnDescriptors() == 1) {
1371 : return true;
1372 : }
1373 : // TODO(cbruni): slower lookup for array subclasses and support slow
1374 : // @@IsConcatSpreadable lookup.
1375 54 : return false;
1376 : }
1377 :
1378 294953 : MaybeHandle<JSArray> Fast_ArrayConcat(Isolate* isolate,
1379 : BuiltinArguments* args) {
1380 294953 : if (!isolate->IsIsConcatSpreadableLookupChainIntact()) {
1381 5151 : return MaybeHandle<JSArray>();
1382 : }
1383 : // We shouldn't overflow when adding another len.
1384 : const int kHalfOfMaxInt = 1 << (kBitsPerInt - 2);
1385 : STATIC_ASSERT(FixedArray::kMaxLength < kHalfOfMaxInt);
1386 : STATIC_ASSERT(FixedDoubleArray::kMaxLength < kHalfOfMaxInt);
1387 : USE(kHalfOfMaxInt);
1388 :
1389 : int n_arguments = args->length();
1390 : int result_len = 0;
1391 : {
1392 : DisallowHeapAllocation no_gc;
1393 : // Iterate through all the arguments performing checks
1394 : // and calculating total length.
1395 1437284 : for (int i = 0; i < n_arguments; i++) {
1396 : Object arg = (*args)[i];
1397 578992 : if (!arg->IsJSArray()) return MaybeHandle<JSArray>();
1398 574956 : if (!HasOnlySimpleReceiverElements(isolate, JSObject::cast(arg))) {
1399 1010 : return MaybeHandle<JSArray>();
1400 : }
1401 : // TODO(cbruni): support fast concatenation of DICTIONARY_ELEMENTS.
1402 1147892 : if (!JSObject::cast(arg)->HasFastElements()) {
1403 142 : return MaybeHandle<JSArray>();
1404 : }
1405 : Handle<JSArray> array(JSArray::cast(arg), isolate);
1406 573804 : if (!IsSimpleArray(isolate, array)) {
1407 54 : return MaybeHandle<JSArray>();
1408 : }
1409 : // The Array length is guaranted to be <= kHalfOfMaxInt thus we won't
1410 : // overflow.
1411 573750 : result_len += Smi::ToInt(array->length());
1412 : DCHECK_GE(result_len, 0);
1413 : // Throw an Error if we overflow the FixedArray limits
1414 573750 : if (FixedDoubleArray::kMaxLength < result_len ||
1415 : FixedArray::kMaxLength < result_len) {
1416 : AllowHeapAllocation gc;
1417 18 : THROW_NEW_ERROR(isolate,
1418 : NewRangeError(MessageTemplate::kInvalidArrayLength),
1419 : JSArray);
1420 : }
1421 : }
1422 : }
1423 284551 : return ElementsAccessor::Concat(isolate, args, n_arguments, result_len);
1424 : }
1425 :
1426 : } // namespace
1427 :
1428 : // ES6 22.1.3.1 Array.prototype.concat
1429 1454520 : BUILTIN(ArrayConcat) {
1430 : HandleScope scope(isolate);
1431 :
1432 : Handle<Object> receiver = args.receiver();
1433 582069 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1434 : isolate, receiver,
1435 : Object::ToObject(isolate, args.receiver(), "Array.prototype.concat"));
1436 : args.set_at(0, *receiver);
1437 :
1438 : Handle<JSArray> result_array;
1439 :
1440 : // Avoid a real species read to avoid extra lookups to the array constructor
1441 869787 : if (V8_LIKELY(receiver->IsJSArray() &&
1442 : Handle<JSArray>::cast(receiver)->HasArrayPrototype(isolate) &&
1443 : isolate->IsArraySpeciesLookupChainIntact())) {
1444 578220 : if (Fast_ArrayConcat(isolate, &args).ToHandle(&result_array)) {
1445 284503 : return *result_array;
1446 : }
1447 4607 : if (isolate->has_pending_exception())
1448 9 : return ReadOnlyRoots(isolate).exception();
1449 : }
1450 : // Reading @@species happens before anything else with a side effect, so
1451 : // we can do it here to determine whether to take the fast path.
1452 : Handle<Object> species;
1453 12262 : ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1454 : isolate, species, Object::ArraySpeciesConstructor(isolate, receiver));
1455 12262 : if (*species == *isolate->array_function()) {
1456 11686 : if (Fast_ArrayConcat(isolate, &args).ToHandle(&result_array)) {
1457 48 : return *result_array;
1458 : }
1459 5795 : if (isolate->has_pending_exception())
1460 0 : return ReadOnlyRoots(isolate).exception();
1461 : }
1462 6083 : return Slow_ArrayConcat(&args, species, isolate);
1463 : }
1464 :
1465 : } // namespace internal
1466 120216 : } // namespace v8
|
