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