1 // Copyright 2016 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/builtins/builtins.h"
6 #include "src/builtins/builtins-utils.h"
7
8 #include "src/code-factory.h"
9 #include "src/contexts.h"
10 #include "src/elements.h"
11
12 namespace v8 {
13 namespace internal {
14
15 namespace {
16
ClampedToInteger(Isolate * isolate,Object * object,int * out)17 inline bool ClampedToInteger(Isolate* isolate, Object* object, int* out) {
18 // This is an extended version of ECMA-262 7.1.11 handling signed values
19 // Try to convert object to a number and clamp values to [kMinInt, kMaxInt]
20 if (object->IsSmi()) {
21 *out = Smi::cast(object)->value();
22 return true;
23 } else if (object->IsHeapNumber()) {
24 double value = HeapNumber::cast(object)->value();
25 if (std::isnan(value)) {
26 *out = 0;
27 } else if (value > kMaxInt) {
28 *out = kMaxInt;
29 } else if (value < kMinInt) {
30 *out = kMinInt;
31 } else {
32 *out = static_cast<int>(value);
33 }
34 return true;
35 } else if (object->IsUndefined(isolate) || object->IsNull(isolate)) {
36 *out = 0;
37 return true;
38 } else if (object->IsBoolean()) {
39 *out = object->IsTrue(isolate);
40 return true;
41 }
42 return false;
43 }
44
GetSloppyArgumentsLength(Isolate * isolate,Handle<JSObject> object,int * out)45 inline bool GetSloppyArgumentsLength(Isolate* isolate, Handle<JSObject> object,
46 int* out) {
47 Context* context = *isolate->native_context();
48 Map* map = object->map();
49 if (map != context->sloppy_arguments_map() &&
50 map != context->strict_arguments_map() &&
51 map != context->fast_aliased_arguments_map()) {
52 return false;
53 }
54 DCHECK(object->HasFastElements() || object->HasFastArgumentsElements());
55 Object* len_obj = object->InObjectPropertyAt(JSArgumentsObject::kLengthIndex);
56 if (!len_obj->IsSmi()) return false;
57 *out = Max(0, Smi::cast(len_obj)->value());
58 return *out <= object->elements()->length();
59 }
60
IsJSArrayFastElementMovingAllowed(Isolate * isolate,JSArray * receiver)61 inline bool IsJSArrayFastElementMovingAllowed(Isolate* isolate,
62 JSArray* receiver) {
63 return JSObject::PrototypeHasNoElements(isolate, receiver);
64 }
65
HasSimpleElements(JSObject * current)66 inline bool HasSimpleElements(JSObject* current) {
67 return current->map()->instance_type() > LAST_CUSTOM_ELEMENTS_RECEIVER &&
68 !current->GetElementsAccessor()->HasAccessors(current);
69 }
70
HasOnlySimpleReceiverElements(Isolate * isolate,JSObject * receiver)71 inline bool HasOnlySimpleReceiverElements(Isolate* isolate,
72 JSObject* receiver) {
73 // Check that we have no accessors on the receiver's elements.
74 if (!HasSimpleElements(receiver)) return false;
75 return JSObject::PrototypeHasNoElements(isolate, receiver);
76 }
77
HasOnlySimpleElements(Isolate * isolate,JSReceiver * receiver)78 inline bool HasOnlySimpleElements(Isolate* isolate, JSReceiver* receiver) {
79 DisallowHeapAllocation no_gc;
80 PrototypeIterator iter(isolate, receiver, kStartAtReceiver);
81 for (; !iter.IsAtEnd(); iter.Advance()) {
82 if (iter.GetCurrent()->IsJSProxy()) return false;
83 JSObject* current = iter.GetCurrent<JSObject>();
84 if (!HasSimpleElements(current)) return false;
85 }
86 return true;
87 }
88
89 // Returns |false| if not applicable.
90 MUST_USE_RESULT
EnsureJSArrayWithWritableFastElements(Isolate * isolate,Handle<Object> receiver,BuiltinArguments * args,int first_added_arg)91 inline bool EnsureJSArrayWithWritableFastElements(Isolate* isolate,
92 Handle<Object> receiver,
93 BuiltinArguments* args,
94 int first_added_arg) {
95 if (!receiver->IsJSArray()) return false;
96 Handle<JSArray> array = Handle<JSArray>::cast(receiver);
97 ElementsKind origin_kind = array->GetElementsKind();
98 if (IsDictionaryElementsKind(origin_kind)) return false;
99 if (!array->map()->is_extensible()) return false;
100 if (args == nullptr) return true;
101
102 // If there may be elements accessors in the prototype chain, the fast path
103 // cannot be used if there arguments to add to the array.
104 if (!IsJSArrayFastElementMovingAllowed(isolate, *array)) return false;
105
106 // Adding elements to the array prototype would break code that makes sure
107 // it has no elements. Handle that elsewhere.
108 if (isolate->IsAnyInitialArrayPrototype(array)) return false;
109
110 // Need to ensure that the arguments passed in args can be contained in
111 // the array.
112 int args_length = args->length();
113 if (first_added_arg >= args_length) return true;
114
115 if (IsFastObjectElementsKind(origin_kind)) return true;
116 ElementsKind target_kind = origin_kind;
117 {
118 DisallowHeapAllocation no_gc;
119 for (int i = first_added_arg; i < args_length; i++) {
120 Object* arg = (*args)[i];
121 if (arg->IsHeapObject()) {
122 if (arg->IsHeapNumber()) {
123 target_kind = FAST_DOUBLE_ELEMENTS;
124 } else {
125 target_kind = FAST_ELEMENTS;
126 break;
127 }
128 }
129 }
130 }
131 if (target_kind != origin_kind) {
132 // Use a short-lived HandleScope to avoid creating several copies of the
133 // elements handle which would cause issues when left-trimming later-on.
134 HandleScope scope(isolate);
135 JSObject::TransitionElementsKind(array, target_kind);
136 }
137 return true;
138 }
139
CallJsIntrinsic(Isolate * isolate,Handle<JSFunction> function,BuiltinArguments args)140 MUST_USE_RESULT static Object* CallJsIntrinsic(Isolate* isolate,
141 Handle<JSFunction> function,
142 BuiltinArguments args) {
143 HandleScope handleScope(isolate);
144 int argc = args.length() - 1;
145 ScopedVector<Handle<Object>> argv(argc);
146 for (int i = 0; i < argc; ++i) {
147 argv[i] = args.at<Object>(i + 1);
148 }
149 RETURN_RESULT_OR_FAILURE(
150 isolate,
151 Execution::Call(isolate, function, args.receiver(), argc, argv.start()));
152 }
153
DoArrayPush(Isolate * isolate,BuiltinArguments args)154 Object* DoArrayPush(Isolate* isolate, BuiltinArguments args) {
155 HandleScope scope(isolate);
156 Handle<Object> receiver = args.receiver();
157 if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, &args, 1)) {
158 return CallJsIntrinsic(isolate, isolate->array_push(), args);
159 }
160 // Fast Elements Path
161 int to_add = args.length() - 1;
162 Handle<JSArray> array = Handle<JSArray>::cast(receiver);
163 int len = Smi::cast(array->length())->value();
164 if (to_add == 0) return Smi::FromInt(len);
165
166 // Currently fixed arrays cannot grow too big, so we should never hit this.
167 DCHECK_LE(to_add, Smi::kMaxValue - Smi::cast(array->length())->value());
168
169 if (JSArray::HasReadOnlyLength(array)) {
170 return CallJsIntrinsic(isolate, isolate->array_push(), args);
171 }
172
173 ElementsAccessor* accessor = array->GetElementsAccessor();
174 int new_length = accessor->Push(array, &args, to_add);
175 return Smi::FromInt(new_length);
176 }
177 } // namespace
178
BUILTIN(ArrayPush)179 BUILTIN(ArrayPush) { return DoArrayPush(isolate, args); }
180
181 // TODO(verwaest): This is a temporary helper until the FastArrayPush stub can
182 // tailcall to the builtin directly.
RUNTIME_FUNCTION(Runtime_ArrayPush)183 RUNTIME_FUNCTION(Runtime_ArrayPush) {
184 DCHECK_EQ(2, args.length());
185 Arguments* incoming = reinterpret_cast<Arguments*>(args[0]);
186 // Rewrap the arguments as builtins arguments.
187 int argc = incoming->length() + BuiltinArguments::kNumExtraArgsWithReceiver;
188 BuiltinArguments caller_args(argc, incoming->arguments() + 1);
189 return DoArrayPush(isolate, caller_args);
190 }
191
BUILTIN(ArrayPop)192 BUILTIN(ArrayPop) {
193 HandleScope scope(isolate);
194 Handle<Object> receiver = args.receiver();
195 if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, nullptr, 0)) {
196 return CallJsIntrinsic(isolate, isolate->array_pop(), args);
197 }
198
199 Handle<JSArray> array = Handle<JSArray>::cast(receiver);
200
201 uint32_t len = static_cast<uint32_t>(Smi::cast(array->length())->value());
202 if (len == 0) return isolate->heap()->undefined_value();
203
204 if (JSArray::HasReadOnlyLength(array)) {
205 return CallJsIntrinsic(isolate, isolate->array_pop(), args);
206 }
207
208 Handle<Object> result;
209 if (IsJSArrayFastElementMovingAllowed(isolate, JSArray::cast(*receiver))) {
210 // Fast Elements Path
211 result = array->GetElementsAccessor()->Pop(array);
212 } else {
213 // Use Slow Lookup otherwise
214 uint32_t new_length = len - 1;
215 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
216 isolate, result, JSReceiver::GetElement(isolate, array, new_length));
217 JSArray::SetLength(array, new_length);
218 }
219 return *result;
220 }
221
BUILTIN(ArrayShift)222 BUILTIN(ArrayShift) {
223 HandleScope scope(isolate);
224 Heap* heap = isolate->heap();
225 Handle<Object> receiver = args.receiver();
226 if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, nullptr, 0) ||
227 !IsJSArrayFastElementMovingAllowed(isolate, JSArray::cast(*receiver))) {
228 return CallJsIntrinsic(isolate, isolate->array_shift(), args);
229 }
230 Handle<JSArray> array = Handle<JSArray>::cast(receiver);
231
232 int len = Smi::cast(array->length())->value();
233 if (len == 0) return heap->undefined_value();
234
235 if (JSArray::HasReadOnlyLength(array)) {
236 return CallJsIntrinsic(isolate, isolate->array_shift(), args);
237 }
238
239 Handle<Object> first = array->GetElementsAccessor()->Shift(array);
240 return *first;
241 }
242
BUILTIN(ArrayUnshift)243 BUILTIN(ArrayUnshift) {
244 HandleScope scope(isolate);
245 Handle<Object> receiver = args.receiver();
246 if (!EnsureJSArrayWithWritableFastElements(isolate, receiver, &args, 1)) {
247 return CallJsIntrinsic(isolate, isolate->array_unshift(), args);
248 }
249 Handle<JSArray> array = Handle<JSArray>::cast(receiver);
250 int to_add = args.length() - 1;
251 if (to_add == 0) return array->length();
252
253 // Currently fixed arrays cannot grow too big, so we should never hit this.
254 DCHECK_LE(to_add, Smi::kMaxValue - Smi::cast(array->length())->value());
255
256 if (JSArray::HasReadOnlyLength(array)) {
257 return CallJsIntrinsic(isolate, isolate->array_unshift(), args);
258 }
259
260 ElementsAccessor* accessor = array->GetElementsAccessor();
261 int new_length = accessor->Unshift(array, &args, to_add);
262 return Smi::FromInt(new_length);
263 }
264
BUILTIN(ArraySlice)265 BUILTIN(ArraySlice) {
266 HandleScope scope(isolate);
267 Handle<Object> receiver = args.receiver();
268 int len = -1;
269 int relative_start = 0;
270 int relative_end = 0;
271
272 if (receiver->IsJSArray()) {
273 DisallowHeapAllocation no_gc;
274 JSArray* array = JSArray::cast(*receiver);
275 if (V8_UNLIKELY(!array->HasFastElements() ||
276 !IsJSArrayFastElementMovingAllowed(isolate, array) ||
277 !isolate->IsArraySpeciesLookupChainIntact() ||
278 // If this is a subclass of Array, then call out to JS
279 !array->HasArrayPrototype(isolate))) {
280 AllowHeapAllocation allow_allocation;
281 return CallJsIntrinsic(isolate, isolate->array_slice(), args);
282 }
283 len = Smi::cast(array->length())->value();
284 } else if (receiver->IsJSObject() &&
285 GetSloppyArgumentsLength(isolate, Handle<JSObject>::cast(receiver),
286 &len)) {
287 // Array.prototype.slice.call(arguments, ...) is quite a common idiom
288 // (notably more than 50% of invocations in Web apps).
289 // Treat it in C++ as well.
290 DCHECK(JSObject::cast(*receiver)->HasFastElements() ||
291 JSObject::cast(*receiver)->HasFastArgumentsElements());
292 } else {
293 AllowHeapAllocation allow_allocation;
294 return CallJsIntrinsic(isolate, isolate->array_slice(), args);
295 }
296 DCHECK_LE(0, len);
297 int argument_count = args.length() - 1;
298 // Note carefully chosen defaults---if argument is missing,
299 // it's undefined which gets converted to 0 for relative_start
300 // and to len for relative_end.
301 relative_start = 0;
302 relative_end = len;
303 if (argument_count > 0) {
304 DisallowHeapAllocation no_gc;
305 if (!ClampedToInteger(isolate, args[1], &relative_start)) {
306 AllowHeapAllocation allow_allocation;
307 return CallJsIntrinsic(isolate, isolate->array_slice(), args);
308 }
309 if (argument_count > 1) {
310 Object* end_arg = args[2];
311 // slice handles the end_arg specially
312 if (end_arg->IsUndefined(isolate)) {
313 relative_end = len;
314 } else if (!ClampedToInteger(isolate, end_arg, &relative_end)) {
315 AllowHeapAllocation allow_allocation;
316 return CallJsIntrinsic(isolate, isolate->array_slice(), args);
317 }
318 }
319 }
320
321 // ECMAScript 232, 3rd Edition, Section 15.4.4.10, step 6.
322 uint32_t actual_start = (relative_start < 0) ? Max(len + relative_start, 0)
323 : Min(relative_start, len);
324
325 // ECMAScript 232, 3rd Edition, Section 15.4.4.10, step 8.
326 uint32_t actual_end =
327 (relative_end < 0) ? Max(len + relative_end, 0) : Min(relative_end, len);
328
329 Handle<JSObject> object = Handle<JSObject>::cast(receiver);
330 ElementsAccessor* accessor = object->GetElementsAccessor();
331 return *accessor->Slice(object, actual_start, actual_end);
332 }
333
BUILTIN(ArraySplice)334 BUILTIN(ArraySplice) {
335 HandleScope scope(isolate);
336 Handle<Object> receiver = args.receiver();
337 if (V8_UNLIKELY(
338 !EnsureJSArrayWithWritableFastElements(isolate, receiver, &args, 3) ||
339 // If this is a subclass of Array, then call out to JS.
340 !Handle<JSArray>::cast(receiver)->HasArrayPrototype(isolate) ||
341 // If anything with @@species has been messed with, call out to JS.
342 !isolate->IsArraySpeciesLookupChainIntact())) {
343 return CallJsIntrinsic(isolate, isolate->array_splice(), args);
344 }
345 Handle<JSArray> array = Handle<JSArray>::cast(receiver);
346
347 int argument_count = args.length() - 1;
348 int relative_start = 0;
349 if (argument_count > 0) {
350 DisallowHeapAllocation no_gc;
351 if (!ClampedToInteger(isolate, args[1], &relative_start)) {
352 AllowHeapAllocation allow_allocation;
353 return CallJsIntrinsic(isolate, isolate->array_splice(), args);
354 }
355 }
356 int len = Smi::cast(array->length())->value();
357 // clip relative start to [0, len]
358 int actual_start = (relative_start < 0) ? Max(len + relative_start, 0)
359 : Min(relative_start, len);
360
361 int actual_delete_count;
362 if (argument_count == 1) {
363 // SpiderMonkey, TraceMonkey and JSC treat the case where no delete count is
364 // given as a request to delete all the elements from the start.
365 // And it differs from the case of undefined delete count.
366 // This does not follow ECMA-262, but we do the same for compatibility.
367 DCHECK(len - actual_start >= 0);
368 actual_delete_count = len - actual_start;
369 } else {
370 int delete_count = 0;
371 DisallowHeapAllocation no_gc;
372 if (argument_count > 1) {
373 if (!ClampedToInteger(isolate, args[2], &delete_count)) {
374 AllowHeapAllocation allow_allocation;
375 return CallJsIntrinsic(isolate, isolate->array_splice(), args);
376 }
377 }
378 actual_delete_count = Min(Max(delete_count, 0), len - actual_start);
379 }
380
381 int add_count = (argument_count > 1) ? (argument_count - 2) : 0;
382 int new_length = len - actual_delete_count + add_count;
383
384 if (new_length != len && JSArray::HasReadOnlyLength(array)) {
385 AllowHeapAllocation allow_allocation;
386 return CallJsIntrinsic(isolate, isolate->array_splice(), args);
387 }
388 ElementsAccessor* accessor = array->GetElementsAccessor();
389 Handle<JSArray> result_array = accessor->Splice(
390 array, actual_start, actual_delete_count, &args, add_count);
391 return *result_array;
392 }
393
394 // Array Concat -------------------------------------------------------------
395
396 namespace {
397
398 /**
399 * A simple visitor visits every element of Array's.
400 * The backend storage can be a fixed array for fast elements case,
401 * or a dictionary for sparse array. Since Dictionary is a subtype
402 * of FixedArray, the class can be used by both fast and slow cases.
403 * The second parameter of the constructor, fast_elements, specifies
404 * whether the storage is a FixedArray or Dictionary.
405 *
406 * An index limit is used to deal with the situation that a result array
407 * length overflows 32-bit non-negative integer.
408 */
409 class ArrayConcatVisitor {
410 public:
ArrayConcatVisitor(Isolate * isolate,Handle<HeapObject> storage,bool fast_elements)411 ArrayConcatVisitor(Isolate* isolate, Handle<HeapObject> storage,
412 bool fast_elements)
413 : isolate_(isolate),
414 storage_(isolate->global_handles()->Create(*storage)),
415 index_offset_(0u),
416 bit_field_(
417 FastElementsField::encode(fast_elements) |
418 ExceedsLimitField::encode(false) |
419 IsFixedArrayField::encode(storage->IsFixedArray()) |
420 HasSimpleElementsField::encode(storage->IsFixedArray() ||
421 storage->map()->instance_type() >
422 LAST_CUSTOM_ELEMENTS_RECEIVER)) {
423 DCHECK(!(this->fast_elements() && !is_fixed_array()));
424 }
425
~ArrayConcatVisitor()426 ~ArrayConcatVisitor() { clear_storage(); }
427
visit(uint32_t i,Handle<Object> elm)428 MUST_USE_RESULT bool visit(uint32_t i, Handle<Object> elm) {
429 uint32_t index = index_offset_ + i;
430
431 if (i >= JSObject::kMaxElementCount - index_offset_) {
432 set_exceeds_array_limit(true);
433 // Exception hasn't been thrown at this point. Return true to
434 // break out, and caller will throw. !visit would imply that
435 // there is already a pending exception.
436 return true;
437 }
438
439 if (!is_fixed_array()) {
440 LookupIterator it(isolate_, storage_, index, LookupIterator::OWN);
441 MAYBE_RETURN(
442 JSReceiver::CreateDataProperty(&it, elm, Object::THROW_ON_ERROR),
443 false);
444 return true;
445 }
446
447 if (fast_elements()) {
448 if (index < static_cast<uint32_t>(storage_fixed_array()->length())) {
449 storage_fixed_array()->set(index, *elm);
450 return true;
451 }
452 // Our initial estimate of length was foiled, possibly by
453 // getters on the arrays increasing the length of later arrays
454 // during iteration.
455 // This shouldn't happen in anything but pathological cases.
456 SetDictionaryMode();
457 // Fall-through to dictionary mode.
458 }
459 DCHECK(!fast_elements());
460 Handle<SeededNumberDictionary> dict(
461 SeededNumberDictionary::cast(*storage_));
462 // The object holding this backing store has just been allocated, so
463 // it cannot yet be used as a prototype.
464 Handle<SeededNumberDictionary> result =
465 SeededNumberDictionary::AtNumberPut(dict, index, elm, false);
466 if (!result.is_identical_to(dict)) {
467 // Dictionary needed to grow.
468 clear_storage();
469 set_storage(*result);
470 }
471 return true;
472 }
473
increase_index_offset(uint32_t delta)474 void increase_index_offset(uint32_t delta) {
475 if (JSObject::kMaxElementCount - index_offset_ < delta) {
476 index_offset_ = JSObject::kMaxElementCount;
477 } else {
478 index_offset_ += delta;
479 }
480 // If the initial length estimate was off (see special case in visit()),
481 // but the array blowing the limit didn't contain elements beyond the
482 // provided-for index range, go to dictionary mode now.
483 if (fast_elements() &&
484 index_offset_ >
485 static_cast<uint32_t>(FixedArrayBase::cast(*storage_)->length())) {
486 SetDictionaryMode();
487 }
488 }
489
exceeds_array_limit() const490 bool exceeds_array_limit() const {
491 return ExceedsLimitField::decode(bit_field_);
492 }
493
ToArray()494 Handle<JSArray> ToArray() {
495 DCHECK(is_fixed_array());
496 Handle<JSArray> array = isolate_->factory()->NewJSArray(0);
497 Handle<Object> length =
498 isolate_->factory()->NewNumber(static_cast<double>(index_offset_));
499 Handle<Map> map = JSObject::GetElementsTransitionMap(
500 array, fast_elements() ? FAST_HOLEY_ELEMENTS : DICTIONARY_ELEMENTS);
501 array->set_map(*map);
502 array->set_length(*length);
503 array->set_elements(*storage_fixed_array());
504 return array;
505 }
506
507 // Storage is either a FixedArray (if is_fixed_array()) or a JSReciever
508 // (otherwise)
storage_fixed_array()509 Handle<FixedArray> storage_fixed_array() {
510 DCHECK(is_fixed_array());
511 DCHECK(has_simple_elements());
512 return Handle<FixedArray>::cast(storage_);
513 }
storage_jsreceiver()514 Handle<JSReceiver> storage_jsreceiver() {
515 DCHECK(!is_fixed_array());
516 return Handle<JSReceiver>::cast(storage_);
517 }
has_simple_elements() const518 bool has_simple_elements() const {
519 return HasSimpleElementsField::decode(bit_field_);
520 }
521
522 private:
523 // Convert storage to dictionary mode.
SetDictionaryMode()524 void SetDictionaryMode() {
525 DCHECK(fast_elements() && is_fixed_array());
526 Handle<FixedArray> current_storage = storage_fixed_array();
527 Handle<SeededNumberDictionary> slow_storage(
528 SeededNumberDictionary::New(isolate_, current_storage->length()));
529 uint32_t current_length = static_cast<uint32_t>(current_storage->length());
530 FOR_WITH_HANDLE_SCOPE(
531 isolate_, uint32_t, i = 0, i, i < current_length, i++, {
532 Handle<Object> element(current_storage->get(i), isolate_);
533 if (!element->IsTheHole(isolate_)) {
534 // The object holding this backing store has just been allocated, so
535 // it cannot yet be used as a prototype.
536 Handle<SeededNumberDictionary> new_storage =
537 SeededNumberDictionary::AtNumberPut(slow_storage, i, element,
538 false);
539 if (!new_storage.is_identical_to(slow_storage)) {
540 slow_storage = loop_scope.CloseAndEscape(new_storage);
541 }
542 }
543 });
544 clear_storage();
545 set_storage(*slow_storage);
546 set_fast_elements(false);
547 }
548
clear_storage()549 inline void clear_storage() { GlobalHandles::Destroy(storage_.location()); }
550
set_storage(FixedArray * storage)551 inline void set_storage(FixedArray* storage) {
552 DCHECK(is_fixed_array());
553 DCHECK(has_simple_elements());
554 storage_ = isolate_->global_handles()->Create(storage);
555 }
556
557 class FastElementsField : public BitField<bool, 0, 1> {};
558 class ExceedsLimitField : public BitField<bool, 1, 1> {};
559 class IsFixedArrayField : public BitField<bool, 2, 1> {};
560 class HasSimpleElementsField : public BitField<bool, 3, 1> {};
561
fast_elements() const562 bool fast_elements() const { return FastElementsField::decode(bit_field_); }
set_fast_elements(bool fast)563 void set_fast_elements(bool fast) {
564 bit_field_ = FastElementsField::update(bit_field_, fast);
565 }
set_exceeds_array_limit(bool exceeds)566 void set_exceeds_array_limit(bool exceeds) {
567 bit_field_ = ExceedsLimitField::update(bit_field_, exceeds);
568 }
is_fixed_array() const569 bool is_fixed_array() const { return IsFixedArrayField::decode(bit_field_); }
570
571 Isolate* isolate_;
572 Handle<Object> storage_; // Always a global handle.
573 // Index after last seen index. Always less than or equal to
574 // JSObject::kMaxElementCount.
575 uint32_t index_offset_;
576 uint32_t bit_field_;
577 };
578
EstimateElementCount(Handle<JSArray> array)579 uint32_t EstimateElementCount(Handle<JSArray> array) {
580 DisallowHeapAllocation no_gc;
581 uint32_t length = static_cast<uint32_t>(array->length()->Number());
582 int element_count = 0;
583 switch (array->GetElementsKind()) {
584 case FAST_SMI_ELEMENTS:
585 case FAST_HOLEY_SMI_ELEMENTS:
586 case FAST_ELEMENTS:
587 case FAST_HOLEY_ELEMENTS: {
588 // Fast elements can't have lengths that are not representable by
589 // a 32-bit signed integer.
590 DCHECK(static_cast<int32_t>(FixedArray::kMaxLength) >= 0);
591 int fast_length = static_cast<int>(length);
592 Isolate* isolate = array->GetIsolate();
593 FixedArray* elements = FixedArray::cast(array->elements());
594 for (int i = 0; i < fast_length; i++) {
595 if (!elements->get(i)->IsTheHole(isolate)) element_count++;
596 }
597 break;
598 }
599 case FAST_DOUBLE_ELEMENTS:
600 case FAST_HOLEY_DOUBLE_ELEMENTS: {
601 // Fast elements can't have lengths that are not representable by
602 // a 32-bit signed integer.
603 DCHECK(static_cast<int32_t>(FixedDoubleArray::kMaxLength) >= 0);
604 int fast_length = static_cast<int>(length);
605 if (array->elements()->IsFixedArray()) {
606 DCHECK(FixedArray::cast(array->elements())->length() == 0);
607 break;
608 }
609 FixedDoubleArray* elements = FixedDoubleArray::cast(array->elements());
610 for (int i = 0; i < fast_length; i++) {
611 if (!elements->is_the_hole(i)) element_count++;
612 }
613 break;
614 }
615 case DICTIONARY_ELEMENTS: {
616 SeededNumberDictionary* dictionary =
617 SeededNumberDictionary::cast(array->elements());
618 Isolate* isolate = dictionary->GetIsolate();
619 int capacity = dictionary->Capacity();
620 for (int i = 0; i < capacity; i++) {
621 Object* key = dictionary->KeyAt(i);
622 if (dictionary->IsKey(isolate, key)) {
623 element_count++;
624 }
625 }
626 break;
627 }
628 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) case TYPE##_ELEMENTS:
629
630 TYPED_ARRAYS(TYPED_ARRAY_CASE)
631 #undef TYPED_ARRAY_CASE
632 // External arrays are always dense.
633 return length;
634 case NO_ELEMENTS:
635 return 0;
636 case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
637 case SLOW_SLOPPY_ARGUMENTS_ELEMENTS:
638 case FAST_STRING_WRAPPER_ELEMENTS:
639 case SLOW_STRING_WRAPPER_ELEMENTS:
640 UNREACHABLE();
641 return 0;
642 }
643 // As an estimate, we assume that the prototype doesn't contain any
644 // inherited elements.
645 return element_count;
646 }
647
648 // Used for sorting indices in a List<uint32_t>.
compareUInt32(const uint32_t * ap,const uint32_t * bp)649 int compareUInt32(const uint32_t* ap, const uint32_t* bp) {
650 uint32_t a = *ap;
651 uint32_t b = *bp;
652 return (a == b) ? 0 : (a < b) ? -1 : 1;
653 }
654
CollectElementIndices(Handle<JSObject> object,uint32_t range,List<uint32_t> * indices)655 void CollectElementIndices(Handle<JSObject> object, uint32_t range,
656 List<uint32_t>* indices) {
657 Isolate* isolate = object->GetIsolate();
658 ElementsKind kind = object->GetElementsKind();
659 switch (kind) {
660 case FAST_SMI_ELEMENTS:
661 case FAST_ELEMENTS:
662 case FAST_HOLEY_SMI_ELEMENTS:
663 case FAST_HOLEY_ELEMENTS: {
664 DisallowHeapAllocation no_gc;
665 FixedArray* elements = FixedArray::cast(object->elements());
666 uint32_t length = static_cast<uint32_t>(elements->length());
667 if (range < length) length = range;
668 for (uint32_t i = 0; i < length; i++) {
669 if (!elements->get(i)->IsTheHole(isolate)) {
670 indices->Add(i);
671 }
672 }
673 break;
674 }
675 case FAST_HOLEY_DOUBLE_ELEMENTS:
676 case FAST_DOUBLE_ELEMENTS: {
677 if (object->elements()->IsFixedArray()) {
678 DCHECK(object->elements()->length() == 0);
679 break;
680 }
681 Handle<FixedDoubleArray> elements(
682 FixedDoubleArray::cast(object->elements()));
683 uint32_t length = static_cast<uint32_t>(elements->length());
684 if (range < length) length = range;
685 for (uint32_t i = 0; i < length; i++) {
686 if (!elements->is_the_hole(i)) {
687 indices->Add(i);
688 }
689 }
690 break;
691 }
692 case DICTIONARY_ELEMENTS: {
693 DisallowHeapAllocation no_gc;
694 SeededNumberDictionary* dict =
695 SeededNumberDictionary::cast(object->elements());
696 uint32_t capacity = dict->Capacity();
697 FOR_WITH_HANDLE_SCOPE(isolate, uint32_t, j = 0, j, j < capacity, j++, {
698 Object* k = dict->KeyAt(j);
699 if (!dict->IsKey(isolate, k)) continue;
700 DCHECK(k->IsNumber());
701 uint32_t index = static_cast<uint32_t>(k->Number());
702 if (index < range) {
703 indices->Add(index);
704 }
705 });
706 break;
707 }
708 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) case TYPE##_ELEMENTS:
709
710 TYPED_ARRAYS(TYPED_ARRAY_CASE)
711 #undef TYPED_ARRAY_CASE
712 {
713 uint32_t length = static_cast<uint32_t>(
714 FixedArrayBase::cast(object->elements())->length());
715 if (range <= length) {
716 length = range;
717 // We will add all indices, so we might as well clear it first
718 // and avoid duplicates.
719 indices->Clear();
720 }
721 for (uint32_t i = 0; i < length; i++) {
722 indices->Add(i);
723 }
724 if (length == range) return; // All indices accounted for already.
725 break;
726 }
727 case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
728 case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: {
729 ElementsAccessor* accessor = object->GetElementsAccessor();
730 for (uint32_t i = 0; i < range; i++) {
731 if (accessor->HasElement(object, i)) {
732 indices->Add(i);
733 }
734 }
735 break;
736 }
737 case FAST_STRING_WRAPPER_ELEMENTS:
738 case SLOW_STRING_WRAPPER_ELEMENTS: {
739 DCHECK(object->IsJSValue());
740 Handle<JSValue> js_value = Handle<JSValue>::cast(object);
741 DCHECK(js_value->value()->IsString());
742 Handle<String> string(String::cast(js_value->value()), isolate);
743 uint32_t length = static_cast<uint32_t>(string->length());
744 uint32_t i = 0;
745 uint32_t limit = Min(length, range);
746 for (; i < limit; i++) {
747 indices->Add(i);
748 }
749 ElementsAccessor* accessor = object->GetElementsAccessor();
750 for (; i < range; i++) {
751 if (accessor->HasElement(object, i)) {
752 indices->Add(i);
753 }
754 }
755 break;
756 }
757 case NO_ELEMENTS:
758 break;
759 }
760
761 PrototypeIterator iter(isolate, object);
762 if (!iter.IsAtEnd()) {
763 // The prototype will usually have no inherited element indices,
764 // but we have to check.
765 CollectElementIndices(PrototypeIterator::GetCurrent<JSObject>(iter), range,
766 indices);
767 }
768 }
769
IterateElementsSlow(Isolate * isolate,Handle<JSReceiver> receiver,uint32_t length,ArrayConcatVisitor * visitor)770 bool IterateElementsSlow(Isolate* isolate, Handle<JSReceiver> receiver,
771 uint32_t length, ArrayConcatVisitor* visitor) {
772 FOR_WITH_HANDLE_SCOPE(isolate, uint32_t, i = 0, i, i < length, ++i, {
773 Maybe<bool> maybe = JSReceiver::HasElement(receiver, i);
774 if (!maybe.IsJust()) return false;
775 if (maybe.FromJust()) {
776 Handle<Object> element_value;
777 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
778 isolate, element_value, JSReceiver::GetElement(isolate, receiver, i),
779 false);
780 if (!visitor->visit(i, element_value)) return false;
781 }
782 });
783 visitor->increase_index_offset(length);
784 return true;
785 }
786 /**
787 * A helper function that visits "array" elements of a JSReceiver in numerical
788 * order.
789 *
790 * The visitor argument called for each existing element in the array
791 * with the element index and the element's value.
792 * Afterwards it increments the base-index of the visitor by the array
793 * length.
794 * Returns false if any access threw an exception, otherwise true.
795 */
IterateElements(Isolate * isolate,Handle<JSReceiver> receiver,ArrayConcatVisitor * visitor)796 bool IterateElements(Isolate* isolate, Handle<JSReceiver> receiver,
797 ArrayConcatVisitor* visitor) {
798 uint32_t length = 0;
799
800 if (receiver->IsJSArray()) {
801 Handle<JSArray> array = Handle<JSArray>::cast(receiver);
802 length = static_cast<uint32_t>(array->length()->Number());
803 } else {
804 Handle<Object> val;
805 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
806 isolate, val, Object::GetLengthFromArrayLike(isolate, receiver), false);
807 // TODO(caitp): Support larger element indexes (up to 2^53-1).
808 if (!val->ToUint32(&length)) {
809 length = 0;
810 }
811 // TODO(cbruni): handle other element kind as well
812 return IterateElementsSlow(isolate, receiver, length, visitor);
813 }
814
815 if (!HasOnlySimpleElements(isolate, *receiver) ||
816 !visitor->has_simple_elements()) {
817 return IterateElementsSlow(isolate, receiver, length, visitor);
818 }
819 Handle<JSObject> array = Handle<JSObject>::cast(receiver);
820
821 switch (array->GetElementsKind()) {
822 case FAST_SMI_ELEMENTS:
823 case FAST_ELEMENTS:
824 case FAST_HOLEY_SMI_ELEMENTS:
825 case FAST_HOLEY_ELEMENTS: {
826 // Run through the elements FixedArray and use HasElement and GetElement
827 // to check the prototype for missing elements.
828 Handle<FixedArray> elements(FixedArray::cast(array->elements()));
829 int fast_length = static_cast<int>(length);
830 DCHECK(fast_length <= elements->length());
831 FOR_WITH_HANDLE_SCOPE(isolate, int, j = 0, j, j < fast_length, j++, {
832 Handle<Object> element_value(elements->get(j), isolate);
833 if (!element_value->IsTheHole(isolate)) {
834 if (!visitor->visit(j, element_value)) return false;
835 } else {
836 Maybe<bool> maybe = JSReceiver::HasElement(array, j);
837 if (!maybe.IsJust()) return false;
838 if (maybe.FromJust()) {
839 // Call GetElement on array, not its prototype, or getters won't
840 // have the correct receiver.
841 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
842 isolate, element_value,
843 JSReceiver::GetElement(isolate, array, j), false);
844 if (!visitor->visit(j, element_value)) return false;
845 }
846 }
847 });
848 break;
849 }
850 case FAST_HOLEY_DOUBLE_ELEMENTS:
851 case FAST_DOUBLE_ELEMENTS: {
852 // Empty array is FixedArray but not FixedDoubleArray.
853 if (length == 0) break;
854 // Run through the elements FixedArray and use HasElement and GetElement
855 // to check the prototype for missing elements.
856 if (array->elements()->IsFixedArray()) {
857 DCHECK(array->elements()->length() == 0);
858 break;
859 }
860 Handle<FixedDoubleArray> elements(
861 FixedDoubleArray::cast(array->elements()));
862 int fast_length = static_cast<int>(length);
863 DCHECK(fast_length <= elements->length());
864 FOR_WITH_HANDLE_SCOPE(isolate, int, j = 0, j, j < fast_length, j++, {
865 if (!elements->is_the_hole(j)) {
866 double double_value = elements->get_scalar(j);
867 Handle<Object> element_value =
868 isolate->factory()->NewNumber(double_value);
869 if (!visitor->visit(j, element_value)) return false;
870 } else {
871 Maybe<bool> maybe = JSReceiver::HasElement(array, j);
872 if (!maybe.IsJust()) return false;
873 if (maybe.FromJust()) {
874 // Call GetElement on array, not its prototype, or getters won't
875 // have the correct receiver.
876 Handle<Object> element_value;
877 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
878 isolate, element_value,
879 JSReceiver::GetElement(isolate, array, j), false);
880 if (!visitor->visit(j, element_value)) return false;
881 }
882 }
883 });
884 break;
885 }
886
887 case DICTIONARY_ELEMENTS: {
888 Handle<SeededNumberDictionary> dict(array->element_dictionary());
889 List<uint32_t> indices(dict->Capacity() / 2);
890 // Collect all indices in the object and the prototypes less
891 // than length. This might introduce duplicates in the indices list.
892 CollectElementIndices(array, length, &indices);
893 indices.Sort(&compareUInt32);
894 int n = indices.length();
895 FOR_WITH_HANDLE_SCOPE(isolate, int, j = 0, j, j < n, (void)0, {
896 uint32_t index = indices[j];
897 Handle<Object> element;
898 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
899 isolate, element, JSReceiver::GetElement(isolate, array, index),
900 false);
901 if (!visitor->visit(index, element)) return false;
902 // Skip to next different index (i.e., omit duplicates).
903 do {
904 j++;
905 } while (j < n && indices[j] == index);
906 });
907 break;
908 }
909 case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
910 case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: {
911 FOR_WITH_HANDLE_SCOPE(
912 isolate, uint32_t, index = 0, index, index < length, index++, {
913 Handle<Object> element;
914 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
915 isolate, element, JSReceiver::GetElement(isolate, array, index),
916 false);
917 if (!visitor->visit(index, element)) return false;
918 });
919 break;
920 }
921 case NO_ELEMENTS:
922 break;
923 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) case TYPE##_ELEMENTS:
924 TYPED_ARRAYS(TYPED_ARRAY_CASE)
925 #undef TYPED_ARRAY_CASE
926 return IterateElementsSlow(isolate, receiver, length, visitor);
927 case FAST_STRING_WRAPPER_ELEMENTS:
928 case SLOW_STRING_WRAPPER_ELEMENTS:
929 // |array| is guaranteed to be an array or typed array.
930 UNREACHABLE();
931 break;
932 }
933 visitor->increase_index_offset(length);
934 return true;
935 }
936
IsConcatSpreadable(Isolate * isolate,Handle<Object> obj)937 static Maybe<bool> IsConcatSpreadable(Isolate* isolate, Handle<Object> obj) {
938 HandleScope handle_scope(isolate);
939 if (!obj->IsJSReceiver()) return Just(false);
940 if (!isolate->IsIsConcatSpreadableLookupChainIntact(JSReceiver::cast(*obj))) {
941 // Slow path if @@isConcatSpreadable has been used.
942 Handle<Symbol> key(isolate->factory()->is_concat_spreadable_symbol());
943 Handle<Object> value;
944 MaybeHandle<Object> maybeValue =
945 i::Runtime::GetObjectProperty(isolate, obj, key);
946 if (!maybeValue.ToHandle(&value)) return Nothing<bool>();
947 if (!value->IsUndefined(isolate)) return Just(value->BooleanValue());
948 }
949 return Object::IsArray(obj);
950 }
951
Slow_ArrayConcat(BuiltinArguments * args,Handle<Object> species,Isolate * isolate)952 Object* Slow_ArrayConcat(BuiltinArguments* args, Handle<Object> species,
953 Isolate* isolate) {
954 int argument_count = args->length();
955
956 bool is_array_species = *species == isolate->context()->array_function();
957
958 // Pass 1: estimate the length and number of elements of the result.
959 // The actual length can be larger if any of the arguments have getters
960 // that mutate other arguments (but will otherwise be precise).
961 // The number of elements is precise if there are no inherited elements.
962
963 ElementsKind kind = FAST_SMI_ELEMENTS;
964
965 uint32_t estimate_result_length = 0;
966 uint32_t estimate_nof_elements = 0;
967 FOR_WITH_HANDLE_SCOPE(isolate, int, i = 0, i, i < argument_count, i++, {
968 Handle<Object> obj((*args)[i], isolate);
969 uint32_t length_estimate;
970 uint32_t element_estimate;
971 if (obj->IsJSArray()) {
972 Handle<JSArray> array(Handle<JSArray>::cast(obj));
973 length_estimate = static_cast<uint32_t>(array->length()->Number());
974 if (length_estimate != 0) {
975 ElementsKind array_kind =
976 GetPackedElementsKind(array->GetElementsKind());
977 kind = GetMoreGeneralElementsKind(kind, array_kind);
978 }
979 element_estimate = EstimateElementCount(array);
980 } else {
981 if (obj->IsHeapObject()) {
982 kind = GetMoreGeneralElementsKind(
983 kind, obj->IsNumber() ? FAST_DOUBLE_ELEMENTS : FAST_ELEMENTS);
984 }
985 length_estimate = 1;
986 element_estimate = 1;
987 }
988 // Avoid overflows by capping at kMaxElementCount.
989 if (JSObject::kMaxElementCount - estimate_result_length < length_estimate) {
990 estimate_result_length = JSObject::kMaxElementCount;
991 } else {
992 estimate_result_length += length_estimate;
993 }
994 if (JSObject::kMaxElementCount - estimate_nof_elements < element_estimate) {
995 estimate_nof_elements = JSObject::kMaxElementCount;
996 } else {
997 estimate_nof_elements += element_estimate;
998 }
999 });
1000
1001 // If estimated number of elements is more than half of length, a
1002 // fixed array (fast case) is more time and space-efficient than a
1003 // dictionary.
1004 bool fast_case =
1005 is_array_species && (estimate_nof_elements * 2) >= estimate_result_length;
1006
1007 if (fast_case && kind == FAST_DOUBLE_ELEMENTS) {
1008 Handle<FixedArrayBase> storage =
1009 isolate->factory()->NewFixedDoubleArray(estimate_result_length);
1010 int j = 0;
1011 bool failure = false;
1012 if (estimate_result_length > 0) {
1013 Handle<FixedDoubleArray> double_storage =
1014 Handle<FixedDoubleArray>::cast(storage);
1015 for (int i = 0; i < argument_count; i++) {
1016 Handle<Object> obj((*args)[i], isolate);
1017 if (obj->IsSmi()) {
1018 double_storage->set(j, Smi::cast(*obj)->value());
1019 j++;
1020 } else if (obj->IsNumber()) {
1021 double_storage->set(j, obj->Number());
1022 j++;
1023 } else {
1024 DisallowHeapAllocation no_gc;
1025 JSArray* array = JSArray::cast(*obj);
1026 uint32_t length = static_cast<uint32_t>(array->length()->Number());
1027 switch (array->GetElementsKind()) {
1028 case FAST_HOLEY_DOUBLE_ELEMENTS:
1029 case FAST_DOUBLE_ELEMENTS: {
1030 // Empty array is FixedArray but not FixedDoubleArray.
1031 if (length == 0) break;
1032 FixedDoubleArray* elements =
1033 FixedDoubleArray::cast(array->elements());
1034 for (uint32_t i = 0; i < length; i++) {
1035 if (elements->is_the_hole(i)) {
1036 // TODO(jkummerow/verwaest): We could be a bit more clever
1037 // here: Check if there are no elements/getters on the
1038 // prototype chain, and if so, allow creation of a holey
1039 // result array.
1040 // Same thing below (holey smi case).
1041 failure = true;
1042 break;
1043 }
1044 double double_value = elements->get_scalar(i);
1045 double_storage->set(j, double_value);
1046 j++;
1047 }
1048 break;
1049 }
1050 case FAST_HOLEY_SMI_ELEMENTS:
1051 case FAST_SMI_ELEMENTS: {
1052 Object* the_hole = isolate->heap()->the_hole_value();
1053 FixedArray* elements(FixedArray::cast(array->elements()));
1054 for (uint32_t i = 0; i < length; i++) {
1055 Object* element = elements->get(i);
1056 if (element == the_hole) {
1057 failure = true;
1058 break;
1059 }
1060 int32_t int_value = Smi::cast(element)->value();
1061 double_storage->set(j, int_value);
1062 j++;
1063 }
1064 break;
1065 }
1066 case FAST_HOLEY_ELEMENTS:
1067 case FAST_ELEMENTS:
1068 case DICTIONARY_ELEMENTS:
1069 case NO_ELEMENTS:
1070 DCHECK_EQ(0u, length);
1071 break;
1072 default:
1073 UNREACHABLE();
1074 }
1075 }
1076 if (failure) break;
1077 }
1078 }
1079 if (!failure) {
1080 return *isolate->factory()->NewJSArrayWithElements(storage, kind, j);
1081 }
1082 // In case of failure, fall through.
1083 }
1084
1085 Handle<HeapObject> storage;
1086 if (fast_case) {
1087 // The backing storage array must have non-existing elements to preserve
1088 // holes across concat operations.
1089 storage =
1090 isolate->factory()->NewFixedArrayWithHoles(estimate_result_length);
1091 } else if (is_array_species) {
1092 // TODO(126): move 25% pre-allocation logic into Dictionary::Allocate
1093 uint32_t at_least_space_for =
1094 estimate_nof_elements + (estimate_nof_elements >> 2);
1095 storage = SeededNumberDictionary::New(isolate, at_least_space_for);
1096 } else {
1097 DCHECK(species->IsConstructor());
1098 Handle<Object> length(Smi::kZero, isolate);
1099 Handle<Object> storage_object;
1100 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1101 isolate, storage_object,
1102 Execution::New(isolate, species, species, 1, &length));
1103 storage = Handle<HeapObject>::cast(storage_object);
1104 }
1105
1106 ArrayConcatVisitor visitor(isolate, storage, fast_case);
1107
1108 for (int i = 0; i < argument_count; i++) {
1109 Handle<Object> obj((*args)[i], isolate);
1110 Maybe<bool> spreadable = IsConcatSpreadable(isolate, obj);
1111 MAYBE_RETURN(spreadable, isolate->heap()->exception());
1112 if (spreadable.FromJust()) {
1113 Handle<JSReceiver> object = Handle<JSReceiver>::cast(obj);
1114 if (!IterateElements(isolate, object, &visitor)) {
1115 return isolate->heap()->exception();
1116 }
1117 } else {
1118 if (!visitor.visit(0, obj)) return isolate->heap()->exception();
1119 visitor.increase_index_offset(1);
1120 }
1121 }
1122
1123 if (visitor.exceeds_array_limit()) {
1124 THROW_NEW_ERROR_RETURN_FAILURE(
1125 isolate, NewRangeError(MessageTemplate::kInvalidArrayLength));
1126 }
1127
1128 if (is_array_species) {
1129 return *visitor.ToArray();
1130 } else {
1131 return *visitor.storage_jsreceiver();
1132 }
1133 }
1134
IsSimpleArray(Isolate * isolate,Handle<JSArray> obj)1135 bool IsSimpleArray(Isolate* isolate, Handle<JSArray> obj) {
1136 DisallowHeapAllocation no_gc;
1137 Map* map = obj->map();
1138 // If there is only the 'length' property we are fine.
1139 if (map->prototype() ==
1140 isolate->native_context()->initial_array_prototype() &&
1141 map->NumberOfOwnDescriptors() == 1) {
1142 return true;
1143 }
1144 // TODO(cbruni): slower lookup for array subclasses and support slow
1145 // @@IsConcatSpreadable lookup.
1146 return false;
1147 }
1148
Fast_ArrayConcat(Isolate * isolate,BuiltinArguments * args)1149 MaybeHandle<JSArray> Fast_ArrayConcat(Isolate* isolate,
1150 BuiltinArguments* args) {
1151 if (!isolate->IsIsConcatSpreadableLookupChainIntact()) {
1152 return MaybeHandle<JSArray>();
1153 }
1154 // We shouldn't overflow when adding another len.
1155 const int kHalfOfMaxInt = 1 << (kBitsPerInt - 2);
1156 STATIC_ASSERT(FixedArray::kMaxLength < kHalfOfMaxInt);
1157 STATIC_ASSERT(FixedDoubleArray::kMaxLength < kHalfOfMaxInt);
1158 USE(kHalfOfMaxInt);
1159
1160 int n_arguments = args->length();
1161 int result_len = 0;
1162 {
1163 DisallowHeapAllocation no_gc;
1164 // Iterate through all the arguments performing checks
1165 // and calculating total length.
1166 for (int i = 0; i < n_arguments; i++) {
1167 Object* arg = (*args)[i];
1168 if (!arg->IsJSArray()) return MaybeHandle<JSArray>();
1169 if (!HasOnlySimpleReceiverElements(isolate, JSObject::cast(arg))) {
1170 return MaybeHandle<JSArray>();
1171 }
1172 // TODO(cbruni): support fast concatenation of DICTIONARY_ELEMENTS.
1173 if (!JSObject::cast(arg)->HasFastElements()) {
1174 return MaybeHandle<JSArray>();
1175 }
1176 Handle<JSArray> array(JSArray::cast(arg), isolate);
1177 if (!IsSimpleArray(isolate, array)) {
1178 return MaybeHandle<JSArray>();
1179 }
1180 // The Array length is guaranted to be <= kHalfOfMaxInt thus we won't
1181 // overflow.
1182 result_len += Smi::cast(array->length())->value();
1183 DCHECK(result_len >= 0);
1184 // Throw an Error if we overflow the FixedArray limits
1185 if (FixedDoubleArray::kMaxLength < result_len ||
1186 FixedArray::kMaxLength < result_len) {
1187 AllowHeapAllocation gc;
1188 THROW_NEW_ERROR(isolate,
1189 NewRangeError(MessageTemplate::kInvalidArrayLength),
1190 JSArray);
1191 }
1192 }
1193 }
1194 return ElementsAccessor::Concat(isolate, args, n_arguments, result_len);
1195 }
1196
1197 } // namespace
1198
1199 // ES6 22.1.3.1 Array.prototype.concat
BUILTIN(ArrayConcat)1200 BUILTIN(ArrayConcat) {
1201 HandleScope scope(isolate);
1202
1203 Handle<Object> receiver = args.receiver();
1204 // TODO(bmeurer): Do we really care about the exact exception message here?
1205 if (receiver->IsNull(isolate) || receiver->IsUndefined(isolate)) {
1206 THROW_NEW_ERROR_RETURN_FAILURE(
1207 isolate, NewTypeError(MessageTemplate::kCalledOnNullOrUndefined,
1208 isolate->factory()->NewStringFromAsciiChecked(
1209 "Array.prototype.concat")));
1210 }
1211 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1212 isolate, receiver, Object::ToObject(isolate, args.receiver()));
1213 args[0] = *receiver;
1214
1215 Handle<JSArray> result_array;
1216
1217 // Avoid a real species read to avoid extra lookups to the array constructor
1218 if (V8_LIKELY(receiver->IsJSArray() &&
1219 Handle<JSArray>::cast(receiver)->HasArrayPrototype(isolate) &&
1220 isolate->IsArraySpeciesLookupChainIntact())) {
1221 if (Fast_ArrayConcat(isolate, &args).ToHandle(&result_array)) {
1222 return *result_array;
1223 }
1224 if (isolate->has_pending_exception()) return isolate->heap()->exception();
1225 }
1226 // Reading @@species happens before anything else with a side effect, so
1227 // we can do it here to determine whether to take the fast path.
1228 Handle<Object> species;
1229 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1230 isolate, species, Object::ArraySpeciesConstructor(isolate, receiver));
1231 if (*species == *isolate->array_function()) {
1232 if (Fast_ArrayConcat(isolate, &args).ToHandle(&result_array)) {
1233 return *result_array;
1234 }
1235 if (isolate->has_pending_exception()) return isolate->heap()->exception();
1236 }
1237 return Slow_ArrayConcat(&args, species, isolate);
1238 }
1239
Generate_ArrayIsArray(CodeStubAssembler * assembler)1240 void Builtins::Generate_ArrayIsArray(CodeStubAssembler* assembler) {
1241 typedef compiler::Node Node;
1242 typedef CodeStubAssembler::Label Label;
1243
1244 Node* object = assembler->Parameter(1);
1245 Node* context = assembler->Parameter(4);
1246
1247 Label call_runtime(assembler), return_true(assembler),
1248 return_false(assembler);
1249
1250 assembler->GotoIf(assembler->TaggedIsSmi(object), &return_false);
1251 Node* instance_type = assembler->LoadInstanceType(object);
1252
1253 assembler->GotoIf(assembler->Word32Equal(
1254 instance_type, assembler->Int32Constant(JS_ARRAY_TYPE)),
1255 &return_true);
1256
1257 // TODO(verwaest): Handle proxies in-place.
1258 assembler->Branch(assembler->Word32Equal(
1259 instance_type, assembler->Int32Constant(JS_PROXY_TYPE)),
1260 &call_runtime, &return_false);
1261
1262 assembler->Bind(&return_true);
1263 assembler->Return(assembler->BooleanConstant(true));
1264
1265 assembler->Bind(&return_false);
1266 assembler->Return(assembler->BooleanConstant(false));
1267
1268 assembler->Bind(&call_runtime);
1269 assembler->Return(
1270 assembler->CallRuntime(Runtime::kArrayIsArray, context, object));
1271 }
1272
Generate_ArrayIncludes(CodeStubAssembler * assembler)1273 void Builtins::Generate_ArrayIncludes(CodeStubAssembler* assembler) {
1274 typedef compiler::Node Node;
1275 typedef CodeStubAssembler::Label Label;
1276 typedef CodeStubAssembler::Variable Variable;
1277
1278 Node* array = assembler->Parameter(0);
1279 Node* search_element = assembler->Parameter(1);
1280 Node* start_from = assembler->Parameter(2);
1281 Node* context = assembler->Parameter(3 + 2);
1282
1283 Node* intptr_zero = assembler->IntPtrConstant(0);
1284 Node* intptr_one = assembler->IntPtrConstant(1);
1285
1286 Node* the_hole = assembler->TheHoleConstant();
1287 Node* undefined = assembler->UndefinedConstant();
1288 Node* heap_number_map = assembler->HeapNumberMapConstant();
1289
1290 Variable len_var(assembler, MachineType::PointerRepresentation()),
1291 index_var(assembler, MachineType::PointerRepresentation()),
1292 start_from_var(assembler, MachineType::PointerRepresentation());
1293
1294 Label init_k(assembler), return_true(assembler), return_false(assembler),
1295 call_runtime(assembler);
1296
1297 Label init_len(assembler);
1298
1299 index_var.Bind(intptr_zero);
1300 len_var.Bind(intptr_zero);
1301
1302 // Take slow path if not a JSArray, if retrieving elements requires
1303 // traversing prototype, or if access checks are required.
1304 assembler->BranchIfFastJSArray(array, context, &init_len, &call_runtime);
1305
1306 assembler->Bind(&init_len);
1307 {
1308 // Handle case where JSArray length is not an Smi in the runtime
1309 Node* len = assembler->LoadObjectField(array, JSArray::kLengthOffset);
1310 assembler->GotoUnless(assembler->TaggedIsSmi(len), &call_runtime);
1311
1312 len_var.Bind(assembler->SmiToWord(len));
1313 assembler->Branch(assembler->WordEqual(len_var.value(), intptr_zero),
1314 &return_false, &init_k);
1315 }
1316
1317 assembler->Bind(&init_k);
1318 {
1319 Label done(assembler), init_k_smi(assembler), init_k_heap_num(assembler),
1320 init_k_zero(assembler), init_k_n(assembler);
1321 Node* tagged_n = assembler->ToInteger(context, start_from);
1322
1323 assembler->Branch(assembler->TaggedIsSmi(tagged_n), &init_k_smi,
1324 &init_k_heap_num);
1325
1326 assembler->Bind(&init_k_smi);
1327 {
1328 start_from_var.Bind(assembler->SmiUntag(tagged_n));
1329 assembler->Goto(&init_k_n);
1330 }
1331
1332 assembler->Bind(&init_k_heap_num);
1333 {
1334 Label do_return_false(assembler);
1335 // This round is lossless for all valid lengths.
1336 Node* fp_len = assembler->RoundIntPtrToFloat64(len_var.value());
1337 Node* fp_n = assembler->LoadHeapNumberValue(tagged_n);
1338 assembler->GotoIf(assembler->Float64GreaterThanOrEqual(fp_n, fp_len),
1339 &do_return_false);
1340 start_from_var.Bind(assembler->ChangeInt32ToIntPtr(
1341 assembler->TruncateFloat64ToWord32(fp_n)));
1342 assembler->Goto(&init_k_n);
1343
1344 assembler->Bind(&do_return_false);
1345 {
1346 index_var.Bind(intptr_zero);
1347 assembler->Goto(&return_false);
1348 }
1349 }
1350
1351 assembler->Bind(&init_k_n);
1352 {
1353 Label if_positive(assembler), if_negative(assembler), done(assembler);
1354 assembler->Branch(
1355 assembler->IntPtrLessThan(start_from_var.value(), intptr_zero),
1356 &if_negative, &if_positive);
1357
1358 assembler->Bind(&if_positive);
1359 {
1360 index_var.Bind(start_from_var.value());
1361 assembler->Goto(&done);
1362 }
1363
1364 assembler->Bind(&if_negative);
1365 {
1366 index_var.Bind(
1367 assembler->IntPtrAdd(len_var.value(), start_from_var.value()));
1368 assembler->Branch(
1369 assembler->IntPtrLessThan(index_var.value(), intptr_zero),
1370 &init_k_zero, &done);
1371 }
1372
1373 assembler->Bind(&init_k_zero);
1374 {
1375 index_var.Bind(intptr_zero);
1376 assembler->Goto(&done);
1377 }
1378
1379 assembler->Bind(&done);
1380 }
1381 }
1382
1383 static int32_t kElementsKind[] = {
1384 FAST_SMI_ELEMENTS, FAST_HOLEY_SMI_ELEMENTS, FAST_ELEMENTS,
1385 FAST_HOLEY_ELEMENTS, FAST_DOUBLE_ELEMENTS, FAST_HOLEY_DOUBLE_ELEMENTS,
1386 };
1387
1388 Label if_smiorobjects(assembler), if_packed_doubles(assembler),
1389 if_holey_doubles(assembler);
1390 Label* element_kind_handlers[] = {&if_smiorobjects, &if_smiorobjects,
1391 &if_smiorobjects, &if_smiorobjects,
1392 &if_packed_doubles, &if_holey_doubles};
1393
1394 Node* map = assembler->LoadMap(array);
1395 Node* elements_kind = assembler->LoadMapElementsKind(map);
1396 Node* elements = assembler->LoadElements(array);
1397 assembler->Switch(elements_kind, &return_false, kElementsKind,
1398 element_kind_handlers, arraysize(kElementsKind));
1399
1400 assembler->Bind(&if_smiorobjects);
1401 {
1402 Variable search_num(assembler, MachineRepresentation::kFloat64);
1403 Label ident_loop(assembler, &index_var),
1404 heap_num_loop(assembler, &search_num),
1405 string_loop(assembler, &index_var), simd_loop(assembler),
1406 undef_loop(assembler, &index_var), not_smi(assembler),
1407 not_heap_num(assembler);
1408
1409 assembler->GotoUnless(assembler->TaggedIsSmi(search_element), ¬_smi);
1410 search_num.Bind(assembler->SmiToFloat64(search_element));
1411 assembler->Goto(&heap_num_loop);
1412
1413 assembler->Bind(¬_smi);
1414 assembler->GotoIf(assembler->WordEqual(search_element, undefined),
1415 &undef_loop);
1416 Node* map = assembler->LoadMap(search_element);
1417 assembler->GotoIf(assembler->WordNotEqual(map, heap_number_map),
1418 ¬_heap_num);
1419 search_num.Bind(assembler->LoadHeapNumberValue(search_element));
1420 assembler->Goto(&heap_num_loop);
1421
1422 assembler->Bind(¬_heap_num);
1423 Node* search_type = assembler->LoadMapInstanceType(map);
1424 assembler->GotoIf(assembler->IsStringInstanceType(search_type),
1425 &string_loop);
1426 assembler->GotoIf(
1427 assembler->Word32Equal(search_type,
1428 assembler->Int32Constant(SIMD128_VALUE_TYPE)),
1429 &simd_loop);
1430 assembler->Goto(&ident_loop);
1431
1432 assembler->Bind(&ident_loop);
1433 {
1434 assembler->GotoUnless(
1435 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1436 &return_false);
1437 Node* element_k = assembler->LoadFixedArrayElement(
1438 elements, index_var.value(), 0, CodeStubAssembler::INTPTR_PARAMETERS);
1439 assembler->GotoIf(assembler->WordEqual(element_k, search_element),
1440 &return_true);
1441
1442 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1443 assembler->Goto(&ident_loop);
1444 }
1445
1446 assembler->Bind(&undef_loop);
1447 {
1448 assembler->GotoUnless(
1449 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1450 &return_false);
1451 Node* element_k = assembler->LoadFixedArrayElement(
1452 elements, index_var.value(), 0, CodeStubAssembler::INTPTR_PARAMETERS);
1453 assembler->GotoIf(assembler->WordEqual(element_k, undefined),
1454 &return_true);
1455 assembler->GotoIf(assembler->WordEqual(element_k, the_hole),
1456 &return_true);
1457
1458 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1459 assembler->Goto(&undef_loop);
1460 }
1461
1462 assembler->Bind(&heap_num_loop);
1463 {
1464 Label nan_loop(assembler, &index_var),
1465 not_nan_loop(assembler, &index_var);
1466 assembler->BranchIfFloat64IsNaN(search_num.value(), &nan_loop,
1467 ¬_nan_loop);
1468
1469 assembler->Bind(¬_nan_loop);
1470 {
1471 Label continue_loop(assembler), not_smi(assembler);
1472 assembler->GotoUnless(
1473 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1474 &return_false);
1475 Node* element_k = assembler->LoadFixedArrayElement(
1476 elements, index_var.value(), 0,
1477 CodeStubAssembler::INTPTR_PARAMETERS);
1478 assembler->GotoUnless(assembler->TaggedIsSmi(element_k), ¬_smi);
1479 assembler->Branch(
1480 assembler->Float64Equal(search_num.value(),
1481 assembler->SmiToFloat64(element_k)),
1482 &return_true, &continue_loop);
1483
1484 assembler->Bind(¬_smi);
1485 assembler->GotoIf(assembler->WordNotEqual(assembler->LoadMap(element_k),
1486 heap_number_map),
1487 &continue_loop);
1488 assembler->Branch(
1489 assembler->Float64Equal(search_num.value(),
1490 assembler->LoadHeapNumberValue(element_k)),
1491 &return_true, &continue_loop);
1492
1493 assembler->Bind(&continue_loop);
1494 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1495 assembler->Goto(¬_nan_loop);
1496 }
1497
1498 assembler->Bind(&nan_loop);
1499 {
1500 Label continue_loop(assembler);
1501 assembler->GotoUnless(
1502 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1503 &return_false);
1504 Node* element_k = assembler->LoadFixedArrayElement(
1505 elements, index_var.value(), 0,
1506 CodeStubAssembler::INTPTR_PARAMETERS);
1507 assembler->GotoIf(assembler->TaggedIsSmi(element_k), &continue_loop);
1508 assembler->GotoIf(assembler->WordNotEqual(assembler->LoadMap(element_k),
1509 heap_number_map),
1510 &continue_loop);
1511 assembler->BranchIfFloat64IsNaN(
1512 assembler->LoadHeapNumberValue(element_k), &return_true,
1513 &continue_loop);
1514
1515 assembler->Bind(&continue_loop);
1516 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1517 assembler->Goto(&nan_loop);
1518 }
1519 }
1520
1521 assembler->Bind(&string_loop);
1522 {
1523 Label continue_loop(assembler);
1524 assembler->GotoUnless(
1525 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1526 &return_false);
1527 Node* element_k = assembler->LoadFixedArrayElement(
1528 elements, index_var.value(), 0, CodeStubAssembler::INTPTR_PARAMETERS);
1529 assembler->GotoIf(assembler->TaggedIsSmi(element_k), &continue_loop);
1530 assembler->GotoUnless(assembler->IsStringInstanceType(
1531 assembler->LoadInstanceType(element_k)),
1532 &continue_loop);
1533
1534 // TODO(bmeurer): Consider inlining the StringEqual logic here.
1535 Callable callable = CodeFactory::StringEqual(assembler->isolate());
1536 Node* result =
1537 assembler->CallStub(callable, context, search_element, element_k);
1538 assembler->Branch(
1539 assembler->WordEqual(assembler->BooleanConstant(true), result),
1540 &return_true, &continue_loop);
1541
1542 assembler->Bind(&continue_loop);
1543 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1544 assembler->Goto(&string_loop);
1545 }
1546
1547 assembler->Bind(&simd_loop);
1548 {
1549 Label continue_loop(assembler, &index_var),
1550 loop_body(assembler, &index_var);
1551 Node* map = assembler->LoadMap(search_element);
1552
1553 assembler->Goto(&loop_body);
1554 assembler->Bind(&loop_body);
1555 assembler->GotoUnless(
1556 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1557 &return_false);
1558
1559 Node* element_k = assembler->LoadFixedArrayElement(
1560 elements, index_var.value(), 0, CodeStubAssembler::INTPTR_PARAMETERS);
1561 assembler->GotoIf(assembler->TaggedIsSmi(element_k), &continue_loop);
1562
1563 Node* map_k = assembler->LoadMap(element_k);
1564 assembler->BranchIfSimd128Equal(search_element, map, element_k, map_k,
1565 &return_true, &continue_loop);
1566
1567 assembler->Bind(&continue_loop);
1568 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1569 assembler->Goto(&loop_body);
1570 }
1571 }
1572
1573 assembler->Bind(&if_packed_doubles);
1574 {
1575 Label nan_loop(assembler, &index_var), not_nan_loop(assembler, &index_var),
1576 hole_loop(assembler, &index_var), search_notnan(assembler);
1577 Variable search_num(assembler, MachineRepresentation::kFloat64);
1578
1579 assembler->GotoUnless(assembler->TaggedIsSmi(search_element),
1580 &search_notnan);
1581 search_num.Bind(assembler->SmiToFloat64(search_element));
1582 assembler->Goto(¬_nan_loop);
1583
1584 assembler->Bind(&search_notnan);
1585 assembler->GotoIf(assembler->WordNotEqual(
1586 assembler->LoadMap(search_element), heap_number_map),
1587 &return_false);
1588
1589 search_num.Bind(assembler->LoadHeapNumberValue(search_element));
1590
1591 assembler->BranchIfFloat64IsNaN(search_num.value(), &nan_loop,
1592 ¬_nan_loop);
1593
1594 // Search for HeapNumber
1595 assembler->Bind(¬_nan_loop);
1596 {
1597 Label continue_loop(assembler);
1598 assembler->GotoUnless(
1599 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1600 &return_false);
1601 Node* element_k = assembler->LoadFixedDoubleArrayElement(
1602 elements, index_var.value(), MachineType::Float64(), 0,
1603 CodeStubAssembler::INTPTR_PARAMETERS);
1604 assembler->Branch(assembler->Float64Equal(element_k, search_num.value()),
1605 &return_true, &continue_loop);
1606 assembler->Bind(&continue_loop);
1607 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1608 assembler->Goto(¬_nan_loop);
1609 }
1610
1611 // Search for NaN
1612 assembler->Bind(&nan_loop);
1613 {
1614 Label continue_loop(assembler);
1615 assembler->GotoUnless(
1616 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1617 &return_false);
1618 Node* element_k = assembler->LoadFixedDoubleArrayElement(
1619 elements, index_var.value(), MachineType::Float64(), 0,
1620 CodeStubAssembler::INTPTR_PARAMETERS);
1621 assembler->BranchIfFloat64IsNaN(element_k, &return_true, &continue_loop);
1622 assembler->Bind(&continue_loop);
1623 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1624 assembler->Goto(&nan_loop);
1625 }
1626 }
1627
1628 assembler->Bind(&if_holey_doubles);
1629 {
1630 Label nan_loop(assembler, &index_var), not_nan_loop(assembler, &index_var),
1631 hole_loop(assembler, &index_var), search_notnan(assembler);
1632 Variable search_num(assembler, MachineRepresentation::kFloat64);
1633
1634 assembler->GotoUnless(assembler->TaggedIsSmi(search_element),
1635 &search_notnan);
1636 search_num.Bind(assembler->SmiToFloat64(search_element));
1637 assembler->Goto(¬_nan_loop);
1638
1639 assembler->Bind(&search_notnan);
1640 assembler->GotoIf(assembler->WordEqual(search_element, undefined),
1641 &hole_loop);
1642 assembler->GotoIf(assembler->WordNotEqual(
1643 assembler->LoadMap(search_element), heap_number_map),
1644 &return_false);
1645
1646 search_num.Bind(assembler->LoadHeapNumberValue(search_element));
1647
1648 assembler->BranchIfFloat64IsNaN(search_num.value(), &nan_loop,
1649 ¬_nan_loop);
1650
1651 // Search for HeapNumber
1652 assembler->Bind(¬_nan_loop);
1653 {
1654 Label continue_loop(assembler);
1655 assembler->GotoUnless(
1656 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1657 &return_false);
1658
1659 // Load double value or continue if it contains a double hole.
1660 Node* element_k = assembler->LoadFixedDoubleArrayElement(
1661 elements, index_var.value(), MachineType::Float64(), 0,
1662 CodeStubAssembler::INTPTR_PARAMETERS, &continue_loop);
1663
1664 assembler->Branch(assembler->Float64Equal(element_k, search_num.value()),
1665 &return_true, &continue_loop);
1666 assembler->Bind(&continue_loop);
1667 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1668 assembler->Goto(¬_nan_loop);
1669 }
1670
1671 // Search for NaN
1672 assembler->Bind(&nan_loop);
1673 {
1674 Label continue_loop(assembler);
1675 assembler->GotoUnless(
1676 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1677 &return_false);
1678
1679 // Load double value or continue if it contains a double hole.
1680 Node* element_k = assembler->LoadFixedDoubleArrayElement(
1681 elements, index_var.value(), MachineType::Float64(), 0,
1682 CodeStubAssembler::INTPTR_PARAMETERS, &continue_loop);
1683
1684 assembler->BranchIfFloat64IsNaN(element_k, &return_true, &continue_loop);
1685 assembler->Bind(&continue_loop);
1686 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1687 assembler->Goto(&nan_loop);
1688 }
1689
1690 // Search for the Hole
1691 assembler->Bind(&hole_loop);
1692 {
1693 assembler->GotoUnless(
1694 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1695 &return_false);
1696
1697 // Check if the element is a double hole, but don't load it.
1698 assembler->LoadFixedDoubleArrayElement(
1699 elements, index_var.value(), MachineType::None(), 0,
1700 CodeStubAssembler::INTPTR_PARAMETERS, &return_true);
1701
1702 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1703 assembler->Goto(&hole_loop);
1704 }
1705 }
1706
1707 assembler->Bind(&return_true);
1708 assembler->Return(assembler->BooleanConstant(true));
1709
1710 assembler->Bind(&return_false);
1711 assembler->Return(assembler->BooleanConstant(false));
1712
1713 assembler->Bind(&call_runtime);
1714 assembler->Return(assembler->CallRuntime(Runtime::kArrayIncludes_Slow,
1715 context, array, search_element,
1716 start_from));
1717 }
1718
Generate_ArrayIndexOf(CodeStubAssembler * assembler)1719 void Builtins::Generate_ArrayIndexOf(CodeStubAssembler* assembler) {
1720 typedef compiler::Node Node;
1721 typedef CodeStubAssembler::Label Label;
1722 typedef CodeStubAssembler::Variable Variable;
1723
1724 Node* array = assembler->Parameter(0);
1725 Node* search_element = assembler->Parameter(1);
1726 Node* start_from = assembler->Parameter(2);
1727 Node* context = assembler->Parameter(3 + 2);
1728
1729 Node* intptr_zero = assembler->IntPtrConstant(0);
1730 Node* intptr_one = assembler->IntPtrConstant(1);
1731
1732 Node* undefined = assembler->UndefinedConstant();
1733 Node* heap_number_map = assembler->HeapNumberMapConstant();
1734
1735 Variable len_var(assembler, MachineType::PointerRepresentation()),
1736 index_var(assembler, MachineType::PointerRepresentation()),
1737 start_from_var(assembler, MachineType::PointerRepresentation());
1738
1739 Label init_k(assembler), return_found(assembler), return_not_found(assembler),
1740 call_runtime(assembler);
1741
1742 Label init_len(assembler);
1743
1744 index_var.Bind(intptr_zero);
1745 len_var.Bind(intptr_zero);
1746
1747 // Take slow path if not a JSArray, if retrieving elements requires
1748 // traversing prototype, or if access checks are required.
1749 assembler->BranchIfFastJSArray(array, context, &init_len, &call_runtime);
1750
1751 assembler->Bind(&init_len);
1752 {
1753 // Handle case where JSArray length is not an Smi in the runtime
1754 Node* len = assembler->LoadObjectField(array, JSArray::kLengthOffset);
1755 assembler->GotoUnless(assembler->TaggedIsSmi(len), &call_runtime);
1756
1757 len_var.Bind(assembler->SmiToWord(len));
1758 assembler->Branch(assembler->WordEqual(len_var.value(), intptr_zero),
1759 &return_not_found, &init_k);
1760 }
1761
1762 assembler->Bind(&init_k);
1763 {
1764 Label done(assembler), init_k_smi(assembler), init_k_heap_num(assembler),
1765 init_k_zero(assembler), init_k_n(assembler);
1766 Node* tagged_n = assembler->ToInteger(context, start_from);
1767
1768 assembler->Branch(assembler->TaggedIsSmi(tagged_n), &init_k_smi,
1769 &init_k_heap_num);
1770
1771 assembler->Bind(&init_k_smi);
1772 {
1773 start_from_var.Bind(assembler->SmiUntag(tagged_n));
1774 assembler->Goto(&init_k_n);
1775 }
1776
1777 assembler->Bind(&init_k_heap_num);
1778 {
1779 Label do_return_not_found(assembler);
1780 // This round is lossless for all valid lengths.
1781 Node* fp_len = assembler->RoundIntPtrToFloat64(len_var.value());
1782 Node* fp_n = assembler->LoadHeapNumberValue(tagged_n);
1783 assembler->GotoIf(assembler->Float64GreaterThanOrEqual(fp_n, fp_len),
1784 &do_return_not_found);
1785 start_from_var.Bind(assembler->ChangeInt32ToIntPtr(
1786 assembler->TruncateFloat64ToWord32(fp_n)));
1787 assembler->Goto(&init_k_n);
1788
1789 assembler->Bind(&do_return_not_found);
1790 {
1791 index_var.Bind(intptr_zero);
1792 assembler->Goto(&return_not_found);
1793 }
1794 }
1795
1796 assembler->Bind(&init_k_n);
1797 {
1798 Label if_positive(assembler), if_negative(assembler), done(assembler);
1799 assembler->Branch(
1800 assembler->IntPtrLessThan(start_from_var.value(), intptr_zero),
1801 &if_negative, &if_positive);
1802
1803 assembler->Bind(&if_positive);
1804 {
1805 index_var.Bind(start_from_var.value());
1806 assembler->Goto(&done);
1807 }
1808
1809 assembler->Bind(&if_negative);
1810 {
1811 index_var.Bind(
1812 assembler->IntPtrAdd(len_var.value(), start_from_var.value()));
1813 assembler->Branch(
1814 assembler->IntPtrLessThan(index_var.value(), intptr_zero),
1815 &init_k_zero, &done);
1816 }
1817
1818 assembler->Bind(&init_k_zero);
1819 {
1820 index_var.Bind(intptr_zero);
1821 assembler->Goto(&done);
1822 }
1823
1824 assembler->Bind(&done);
1825 }
1826 }
1827
1828 static int32_t kElementsKind[] = {
1829 FAST_SMI_ELEMENTS, FAST_HOLEY_SMI_ELEMENTS, FAST_ELEMENTS,
1830 FAST_HOLEY_ELEMENTS, FAST_DOUBLE_ELEMENTS, FAST_HOLEY_DOUBLE_ELEMENTS,
1831 };
1832
1833 Label if_smiorobjects(assembler), if_packed_doubles(assembler),
1834 if_holey_doubles(assembler);
1835 Label* element_kind_handlers[] = {&if_smiorobjects, &if_smiorobjects,
1836 &if_smiorobjects, &if_smiorobjects,
1837 &if_packed_doubles, &if_holey_doubles};
1838
1839 Node* map = assembler->LoadMap(array);
1840 Node* elements_kind = assembler->LoadMapElementsKind(map);
1841 Node* elements = assembler->LoadElements(array);
1842 assembler->Switch(elements_kind, &return_not_found, kElementsKind,
1843 element_kind_handlers, arraysize(kElementsKind));
1844
1845 assembler->Bind(&if_smiorobjects);
1846 {
1847 Variable search_num(assembler, MachineRepresentation::kFloat64);
1848 Label ident_loop(assembler, &index_var),
1849 heap_num_loop(assembler, &search_num),
1850 string_loop(assembler, &index_var), simd_loop(assembler),
1851 undef_loop(assembler, &index_var), not_smi(assembler),
1852 not_heap_num(assembler);
1853
1854 assembler->GotoUnless(assembler->TaggedIsSmi(search_element), ¬_smi);
1855 search_num.Bind(assembler->SmiToFloat64(search_element));
1856 assembler->Goto(&heap_num_loop);
1857
1858 assembler->Bind(¬_smi);
1859 assembler->GotoIf(assembler->WordEqual(search_element, undefined),
1860 &undef_loop);
1861 Node* map = assembler->LoadMap(search_element);
1862 assembler->GotoIf(assembler->WordNotEqual(map, heap_number_map),
1863 ¬_heap_num);
1864 search_num.Bind(assembler->LoadHeapNumberValue(search_element));
1865 assembler->Goto(&heap_num_loop);
1866
1867 assembler->Bind(¬_heap_num);
1868 Node* search_type = assembler->LoadMapInstanceType(map);
1869 assembler->GotoIf(assembler->IsStringInstanceType(search_type),
1870 &string_loop);
1871 assembler->GotoIf(
1872 assembler->Word32Equal(search_type,
1873 assembler->Int32Constant(SIMD128_VALUE_TYPE)),
1874 &simd_loop);
1875 assembler->Goto(&ident_loop);
1876
1877 assembler->Bind(&ident_loop);
1878 {
1879 assembler->GotoUnless(
1880 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1881 &return_not_found);
1882 Node* element_k = assembler->LoadFixedArrayElement(
1883 elements, index_var.value(), 0, CodeStubAssembler::INTPTR_PARAMETERS);
1884 assembler->GotoIf(assembler->WordEqual(element_k, search_element),
1885 &return_found);
1886
1887 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1888 assembler->Goto(&ident_loop);
1889 }
1890
1891 assembler->Bind(&undef_loop);
1892 {
1893 assembler->GotoUnless(
1894 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1895 &return_not_found);
1896 Node* element_k = assembler->LoadFixedArrayElement(
1897 elements, index_var.value(), 0, CodeStubAssembler::INTPTR_PARAMETERS);
1898 assembler->GotoIf(assembler->WordEqual(element_k, undefined),
1899 &return_found);
1900
1901 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1902 assembler->Goto(&undef_loop);
1903 }
1904
1905 assembler->Bind(&heap_num_loop);
1906 {
1907 Label not_nan_loop(assembler, &index_var);
1908 assembler->BranchIfFloat64IsNaN(search_num.value(), &return_not_found,
1909 ¬_nan_loop);
1910
1911 assembler->Bind(¬_nan_loop);
1912 {
1913 Label continue_loop(assembler), not_smi(assembler);
1914 assembler->GotoUnless(
1915 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1916 &return_not_found);
1917 Node* element_k = assembler->LoadFixedArrayElement(
1918 elements, index_var.value(), 0,
1919 CodeStubAssembler::INTPTR_PARAMETERS);
1920 assembler->GotoUnless(assembler->TaggedIsSmi(element_k), ¬_smi);
1921 assembler->Branch(
1922 assembler->Float64Equal(search_num.value(),
1923 assembler->SmiToFloat64(element_k)),
1924 &return_found, &continue_loop);
1925
1926 assembler->Bind(¬_smi);
1927 assembler->GotoIf(assembler->WordNotEqual(assembler->LoadMap(element_k),
1928 heap_number_map),
1929 &continue_loop);
1930 assembler->Branch(
1931 assembler->Float64Equal(search_num.value(),
1932 assembler->LoadHeapNumberValue(element_k)),
1933 &return_found, &continue_loop);
1934
1935 assembler->Bind(&continue_loop);
1936 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1937 assembler->Goto(¬_nan_loop);
1938 }
1939 }
1940
1941 assembler->Bind(&string_loop);
1942 {
1943 Label continue_loop(assembler);
1944 assembler->GotoUnless(
1945 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1946 &return_not_found);
1947 Node* element_k = assembler->LoadFixedArrayElement(
1948 elements, index_var.value(), 0, CodeStubAssembler::INTPTR_PARAMETERS);
1949 assembler->GotoIf(assembler->TaggedIsSmi(element_k), &continue_loop);
1950 assembler->GotoUnless(assembler->IsStringInstanceType(
1951 assembler->LoadInstanceType(element_k)),
1952 &continue_loop);
1953
1954 // TODO(bmeurer): Consider inlining the StringEqual logic here.
1955 Callable callable = CodeFactory::StringEqual(assembler->isolate());
1956 Node* result =
1957 assembler->CallStub(callable, context, search_element, element_k);
1958 assembler->Branch(
1959 assembler->WordEqual(assembler->BooleanConstant(true), result),
1960 &return_found, &continue_loop);
1961
1962 assembler->Bind(&continue_loop);
1963 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1964 assembler->Goto(&string_loop);
1965 }
1966
1967 assembler->Bind(&simd_loop);
1968 {
1969 Label continue_loop(assembler, &index_var),
1970 loop_body(assembler, &index_var);
1971 Node* map = assembler->LoadMap(search_element);
1972
1973 assembler->Goto(&loop_body);
1974 assembler->Bind(&loop_body);
1975 assembler->GotoUnless(
1976 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
1977 &return_not_found);
1978
1979 Node* element_k = assembler->LoadFixedArrayElement(
1980 elements, index_var.value(), 0, CodeStubAssembler::INTPTR_PARAMETERS);
1981 assembler->GotoIf(assembler->TaggedIsSmi(element_k), &continue_loop);
1982
1983 Node* map_k = assembler->LoadMap(element_k);
1984 assembler->BranchIfSimd128Equal(search_element, map, element_k, map_k,
1985 &return_found, &continue_loop);
1986
1987 assembler->Bind(&continue_loop);
1988 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
1989 assembler->Goto(&loop_body);
1990 }
1991 }
1992
1993 assembler->Bind(&if_packed_doubles);
1994 {
1995 Label not_nan_loop(assembler, &index_var), search_notnan(assembler);
1996 Variable search_num(assembler, MachineRepresentation::kFloat64);
1997
1998 assembler->GotoUnless(assembler->TaggedIsSmi(search_element),
1999 &search_notnan);
2000 search_num.Bind(assembler->SmiToFloat64(search_element));
2001 assembler->Goto(¬_nan_loop);
2002
2003 assembler->Bind(&search_notnan);
2004 assembler->GotoIf(assembler->WordNotEqual(
2005 assembler->LoadMap(search_element), heap_number_map),
2006 &return_not_found);
2007
2008 search_num.Bind(assembler->LoadHeapNumberValue(search_element));
2009
2010 assembler->BranchIfFloat64IsNaN(search_num.value(), &return_not_found,
2011 ¬_nan_loop);
2012
2013 // Search for HeapNumber
2014 assembler->Bind(¬_nan_loop);
2015 {
2016 Label continue_loop(assembler);
2017 assembler->GotoUnless(
2018 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
2019 &return_not_found);
2020 Node* element_k = assembler->LoadFixedDoubleArrayElement(
2021 elements, index_var.value(), MachineType::Float64(), 0,
2022 CodeStubAssembler::INTPTR_PARAMETERS);
2023 assembler->Branch(assembler->Float64Equal(element_k, search_num.value()),
2024 &return_found, &continue_loop);
2025 assembler->Bind(&continue_loop);
2026 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
2027 assembler->Goto(¬_nan_loop);
2028 }
2029 }
2030
2031 assembler->Bind(&if_holey_doubles);
2032 {
2033 Label not_nan_loop(assembler, &index_var), search_notnan(assembler);
2034 Variable search_num(assembler, MachineRepresentation::kFloat64);
2035
2036 assembler->GotoUnless(assembler->TaggedIsSmi(search_element),
2037 &search_notnan);
2038 search_num.Bind(assembler->SmiToFloat64(search_element));
2039 assembler->Goto(¬_nan_loop);
2040
2041 assembler->Bind(&search_notnan);
2042 assembler->GotoIf(assembler->WordNotEqual(
2043 assembler->LoadMap(search_element), heap_number_map),
2044 &return_not_found);
2045
2046 search_num.Bind(assembler->LoadHeapNumberValue(search_element));
2047
2048 assembler->BranchIfFloat64IsNaN(search_num.value(), &return_not_found,
2049 ¬_nan_loop);
2050
2051 // Search for HeapNumber
2052 assembler->Bind(¬_nan_loop);
2053 {
2054 Label continue_loop(assembler);
2055 assembler->GotoUnless(
2056 assembler->UintPtrLessThan(index_var.value(), len_var.value()),
2057 &return_not_found);
2058
2059 // Load double value or continue if it contains a double hole.
2060 Node* element_k = assembler->LoadFixedDoubleArrayElement(
2061 elements, index_var.value(), MachineType::Float64(), 0,
2062 CodeStubAssembler::INTPTR_PARAMETERS, &continue_loop);
2063
2064 assembler->Branch(assembler->Float64Equal(element_k, search_num.value()),
2065 &return_found, &continue_loop);
2066 assembler->Bind(&continue_loop);
2067 index_var.Bind(assembler->IntPtrAdd(index_var.value(), intptr_one));
2068 assembler->Goto(¬_nan_loop);
2069 }
2070 }
2071
2072 assembler->Bind(&return_found);
2073 assembler->Return(assembler->ChangeInt32ToTagged(index_var.value()));
2074
2075 assembler->Bind(&return_not_found);
2076 assembler->Return(assembler->NumberConstant(-1));
2077
2078 assembler->Bind(&call_runtime);
2079 assembler->Return(assembler->CallRuntime(Runtime::kArrayIndexOf, context,
2080 array, search_element, start_from));
2081 }
2082
2083 namespace {
2084
2085 template <IterationKind kIterationKind>
Generate_ArrayPrototypeIterationMethod(CodeStubAssembler * assembler)2086 void Generate_ArrayPrototypeIterationMethod(CodeStubAssembler* assembler) {
2087 typedef compiler::Node Node;
2088 typedef CodeStubAssembler::Label Label;
2089 typedef CodeStubAssembler::Variable Variable;
2090
2091 Node* receiver = assembler->Parameter(0);
2092 Node* context = assembler->Parameter(3);
2093
2094 Variable var_array(assembler, MachineRepresentation::kTagged);
2095 Variable var_map(assembler, MachineRepresentation::kTagged);
2096 Variable var_type(assembler, MachineRepresentation::kWord32);
2097
2098 Label if_isnotobject(assembler, Label::kDeferred);
2099 Label create_array_iterator(assembler);
2100
2101 assembler->GotoIf(assembler->TaggedIsSmi(receiver), &if_isnotobject);
2102 var_array.Bind(receiver);
2103 var_map.Bind(assembler->LoadMap(receiver));
2104 var_type.Bind(assembler->LoadMapInstanceType(var_map.value()));
2105 assembler->Branch(assembler->IsJSReceiverInstanceType(var_type.value()),
2106 &create_array_iterator, &if_isnotobject);
2107
2108 assembler->Bind(&if_isnotobject);
2109 {
2110 Callable callable = CodeFactory::ToObject(assembler->isolate());
2111 Node* result = assembler->CallStub(callable, context, receiver);
2112 var_array.Bind(result);
2113 var_map.Bind(assembler->LoadMap(result));
2114 var_type.Bind(assembler->LoadMapInstanceType(var_map.value()));
2115 assembler->Goto(&create_array_iterator);
2116 }
2117
2118 assembler->Bind(&create_array_iterator);
2119 assembler->Return(assembler->CreateArrayIterator(
2120 var_array.value(), var_map.value(), var_type.value(), context,
2121 kIterationKind));
2122 }
2123
2124 } // namespace
2125
Generate_ArrayPrototypeValues(CodeStubAssembler * assembler)2126 void Builtins::Generate_ArrayPrototypeValues(CodeStubAssembler* assembler) {
2127 Generate_ArrayPrototypeIterationMethod<IterationKind::kValues>(assembler);
2128 }
2129
Generate_ArrayPrototypeEntries(CodeStubAssembler * assembler)2130 void Builtins::Generate_ArrayPrototypeEntries(CodeStubAssembler* assembler) {
2131 Generate_ArrayPrototypeIterationMethod<IterationKind::kEntries>(assembler);
2132 }
2133
Generate_ArrayPrototypeKeys(CodeStubAssembler * assembler)2134 void Builtins::Generate_ArrayPrototypeKeys(CodeStubAssembler* assembler) {
2135 Generate_ArrayPrototypeIterationMethod<IterationKind::kKeys>(assembler);
2136 }
2137
Generate_ArrayIteratorPrototypeNext(CodeStubAssembler * assembler)2138 void Builtins::Generate_ArrayIteratorPrototypeNext(
2139 CodeStubAssembler* assembler) {
2140 typedef compiler::Node Node;
2141 typedef CodeStubAssembler::Label Label;
2142 typedef CodeStubAssembler::Variable Variable;
2143
2144 Node* iterator = assembler->Parameter(0);
2145 Node* context = assembler->Parameter(3);
2146
2147 Variable var_value(assembler, MachineRepresentation::kTagged);
2148 Variable var_done(assembler, MachineRepresentation::kTagged);
2149
2150 // Required, or else `throw_bad_receiver` fails a DCHECK due to these
2151 // variables not being bound along all paths, despite not being used.
2152 var_done.Bind(assembler->TrueConstant());
2153 var_value.Bind(assembler->UndefinedConstant());
2154
2155 Label throw_bad_receiver(assembler, Label::kDeferred);
2156 Label set_done(assembler);
2157 Label allocate_key_result(assembler);
2158 Label allocate_entry_if_needed(assembler);
2159 Label allocate_iterator_result(assembler);
2160 Label generic_values(assembler);
2161
2162 // If O does not have all of the internal slots of an Array Iterator Instance
2163 // (22.1.5.3), throw a TypeError exception
2164 assembler->GotoIf(assembler->TaggedIsSmi(iterator), &throw_bad_receiver);
2165 Node* instance_type = assembler->LoadInstanceType(iterator);
2166 assembler->GotoIf(
2167 assembler->Uint32LessThan(
2168 assembler->Int32Constant(LAST_ARRAY_ITERATOR_TYPE -
2169 FIRST_ARRAY_ITERATOR_TYPE),
2170 assembler->Int32Sub(instance_type, assembler->Int32Constant(
2171 FIRST_ARRAY_ITERATOR_TYPE))),
2172 &throw_bad_receiver);
2173
2174 // Let a be O.[[IteratedObject]].
2175 Node* array = assembler->LoadObjectField(
2176 iterator, JSArrayIterator::kIteratedObjectOffset);
2177
2178 // Let index be O.[[ArrayIteratorNextIndex]].
2179 Node* index =
2180 assembler->LoadObjectField(iterator, JSArrayIterator::kNextIndexOffset);
2181 Node* orig_map = assembler->LoadObjectField(
2182 iterator, JSArrayIterator::kIteratedObjectMapOffset);
2183 Node* array_map = assembler->LoadMap(array);
2184
2185 Label if_isfastarray(assembler), if_isnotfastarray(assembler);
2186
2187 assembler->Branch(assembler->WordEqual(orig_map, array_map), &if_isfastarray,
2188 &if_isnotfastarray);
2189
2190 assembler->Bind(&if_isfastarray);
2191 {
2192 CSA_ASSERT(assembler,
2193 assembler->Word32Equal(assembler->LoadMapInstanceType(array_map),
2194 assembler->Int32Constant(JS_ARRAY_TYPE)));
2195
2196 Node* length = assembler->LoadObjectField(array, JSArray::kLengthOffset);
2197
2198 CSA_ASSERT(assembler, assembler->TaggedIsSmi(length));
2199 CSA_ASSERT(assembler, assembler->TaggedIsSmi(index));
2200
2201 assembler->GotoUnless(assembler->SmiBelow(index, length), &set_done);
2202
2203 Node* one = assembler->SmiConstant(Smi::FromInt(1));
2204 assembler->StoreObjectFieldNoWriteBarrier(
2205 iterator, JSArrayIterator::kNextIndexOffset,
2206 assembler->IntPtrAdd(assembler->BitcastTaggedToWord(index),
2207 assembler->BitcastTaggedToWord(one)));
2208
2209 var_done.Bind(assembler->FalseConstant());
2210 Node* elements = assembler->LoadElements(array);
2211
2212 static int32_t kInstanceType[] = {
2213 JS_FAST_ARRAY_KEY_ITERATOR_TYPE,
2214 JS_FAST_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2215 JS_FAST_HOLEY_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2216 JS_FAST_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2217 JS_FAST_HOLEY_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2218 JS_FAST_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2219 JS_FAST_HOLEY_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2220 JS_FAST_SMI_ARRAY_VALUE_ITERATOR_TYPE,
2221 JS_FAST_HOLEY_SMI_ARRAY_VALUE_ITERATOR_TYPE,
2222 JS_FAST_ARRAY_VALUE_ITERATOR_TYPE,
2223 JS_FAST_HOLEY_ARRAY_VALUE_ITERATOR_TYPE,
2224 JS_FAST_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE,
2225 JS_FAST_HOLEY_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE,
2226 };
2227
2228 Label packed_object_values(assembler), holey_object_values(assembler),
2229 packed_double_values(assembler), holey_double_values(assembler);
2230 Label* kInstanceTypeHandlers[] = {
2231 &allocate_key_result, &packed_object_values, &holey_object_values,
2232 &packed_object_values, &holey_object_values, &packed_double_values,
2233 &holey_double_values, &packed_object_values, &holey_object_values,
2234 &packed_object_values, &holey_object_values, &packed_double_values,
2235 &holey_double_values};
2236
2237 assembler->Switch(instance_type, &throw_bad_receiver, kInstanceType,
2238 kInstanceTypeHandlers, arraysize(kInstanceType));
2239
2240 assembler->Bind(&packed_object_values);
2241 {
2242 var_value.Bind(assembler->LoadFixedArrayElement(
2243 elements, index, 0, CodeStubAssembler::SMI_PARAMETERS));
2244 assembler->Goto(&allocate_entry_if_needed);
2245 }
2246
2247 assembler->Bind(&packed_double_values);
2248 {
2249 Node* value = assembler->LoadFixedDoubleArrayElement(
2250 elements, index, MachineType::Float64(), 0,
2251 CodeStubAssembler::SMI_PARAMETERS);
2252 var_value.Bind(assembler->AllocateHeapNumberWithValue(value));
2253 assembler->Goto(&allocate_entry_if_needed);
2254 }
2255
2256 assembler->Bind(&holey_object_values);
2257 {
2258 // Check the array_protector cell, and take the slow path if it's invalid.
2259 Node* invalid =
2260 assembler->SmiConstant(Smi::FromInt(Isolate::kProtectorInvalid));
2261 Node* cell = assembler->LoadRoot(Heap::kArrayProtectorRootIndex);
2262 Node* cell_value =
2263 assembler->LoadObjectField(cell, PropertyCell::kValueOffset);
2264 assembler->GotoIf(assembler->WordEqual(cell_value, invalid),
2265 &generic_values);
2266
2267 var_value.Bind(assembler->UndefinedConstant());
2268 Node* value = assembler->LoadFixedArrayElement(
2269 elements, index, 0, CodeStubAssembler::SMI_PARAMETERS);
2270 assembler->GotoIf(
2271 assembler->WordEqual(value, assembler->TheHoleConstant()),
2272 &allocate_entry_if_needed);
2273 var_value.Bind(value);
2274 assembler->Goto(&allocate_entry_if_needed);
2275 }
2276
2277 assembler->Bind(&holey_double_values);
2278 {
2279 // Check the array_protector cell, and take the slow path if it's invalid.
2280 Node* invalid =
2281 assembler->SmiConstant(Smi::FromInt(Isolate::kProtectorInvalid));
2282 Node* cell = assembler->LoadRoot(Heap::kArrayProtectorRootIndex);
2283 Node* cell_value =
2284 assembler->LoadObjectField(cell, PropertyCell::kValueOffset);
2285 assembler->GotoIf(assembler->WordEqual(cell_value, invalid),
2286 &generic_values);
2287
2288 var_value.Bind(assembler->UndefinedConstant());
2289 Node* value = assembler->LoadFixedDoubleArrayElement(
2290 elements, index, MachineType::Float64(), 0,
2291 CodeStubAssembler::SMI_PARAMETERS, &allocate_entry_if_needed);
2292 var_value.Bind(assembler->AllocateHeapNumberWithValue(value));
2293 assembler->Goto(&allocate_entry_if_needed);
2294 }
2295 }
2296
2297 assembler->Bind(&if_isnotfastarray);
2298 {
2299 Label if_istypedarray(assembler), if_isgeneric(assembler);
2300
2301 // If a is undefined, return CreateIterResultObject(undefined, true)
2302 assembler->GotoIf(
2303 assembler->WordEqual(array, assembler->UndefinedConstant()),
2304 &allocate_iterator_result);
2305
2306 Node* array_type = assembler->LoadInstanceType(array);
2307 assembler->Branch(
2308 assembler->Word32Equal(array_type,
2309 assembler->Int32Constant(JS_TYPED_ARRAY_TYPE)),
2310 &if_istypedarray, &if_isgeneric);
2311
2312 assembler->Bind(&if_isgeneric);
2313 {
2314 Label if_wasfastarray(assembler);
2315
2316 Node* length = nullptr;
2317 {
2318 Variable var_length(assembler, MachineRepresentation::kTagged);
2319 Label if_isarray(assembler), if_isnotarray(assembler), done(assembler);
2320 assembler->Branch(
2321 assembler->Word32Equal(array_type,
2322 assembler->Int32Constant(JS_ARRAY_TYPE)),
2323 &if_isarray, &if_isnotarray);
2324
2325 assembler->Bind(&if_isarray);
2326 {
2327 var_length.Bind(
2328 assembler->LoadObjectField(array, JSArray::kLengthOffset));
2329
2330 // Invalidate protector cell if needed
2331 assembler->Branch(
2332 assembler->WordNotEqual(orig_map, assembler->UndefinedConstant()),
2333 &if_wasfastarray, &done);
2334
2335 assembler->Bind(&if_wasfastarray);
2336 {
2337 Label if_invalid(assembler, Label::kDeferred);
2338 // A fast array iterator transitioned to a slow iterator during
2339 // iteration. Invalidate fast_array_iteration_prtoector cell to
2340 // prevent potential deopt loops.
2341 assembler->StoreObjectFieldNoWriteBarrier(
2342 iterator, JSArrayIterator::kIteratedObjectMapOffset,
2343 assembler->UndefinedConstant());
2344 assembler->GotoIf(
2345 assembler->Uint32LessThanOrEqual(
2346 instance_type, assembler->Int32Constant(
2347 JS_GENERIC_ARRAY_KEY_ITERATOR_TYPE)),
2348 &done);
2349
2350 Node* invalid = assembler->SmiConstant(
2351 Smi::FromInt(Isolate::kProtectorInvalid));
2352 Node* cell = assembler->LoadRoot(
2353 Heap::kFastArrayIterationProtectorRootIndex);
2354 assembler->StoreObjectFieldNoWriteBarrier(cell, Cell::kValueOffset,
2355 invalid);
2356 assembler->Goto(&done);
2357 }
2358 }
2359
2360 assembler->Bind(&if_isnotarray);
2361 {
2362 Node* length_string = assembler->HeapConstant(
2363 assembler->isolate()->factory()->length_string());
2364 Callable get_property =
2365 CodeFactory::GetProperty(assembler->isolate());
2366 Node* length =
2367 assembler->CallStub(get_property, context, array, length_string);
2368 Callable to_length = CodeFactory::ToLength(assembler->isolate());
2369 var_length.Bind(assembler->CallStub(to_length, context, length));
2370 assembler->Goto(&done);
2371 }
2372
2373 assembler->Bind(&done);
2374 length = var_length.value();
2375 }
2376
2377 assembler->GotoUnlessNumberLessThan(index, length, &set_done);
2378
2379 assembler->StoreObjectField(iterator, JSArrayIterator::kNextIndexOffset,
2380 assembler->NumberInc(index));
2381 var_done.Bind(assembler->FalseConstant());
2382
2383 assembler->Branch(
2384 assembler->Uint32LessThanOrEqual(
2385 instance_type,
2386 assembler->Int32Constant(JS_GENERIC_ARRAY_KEY_ITERATOR_TYPE)),
2387 &allocate_key_result, &generic_values);
2388
2389 assembler->Bind(&generic_values);
2390 {
2391 Callable get_property = CodeFactory::GetProperty(assembler->isolate());
2392 var_value.Bind(
2393 assembler->CallStub(get_property, context, array, index));
2394 assembler->Goto(&allocate_entry_if_needed);
2395 }
2396 }
2397
2398 assembler->Bind(&if_istypedarray);
2399 {
2400 Node* length = nullptr;
2401 {
2402 Variable var_length(assembler, MachineRepresentation::kTagged);
2403 Label if_isdetached(assembler, Label::kDeferred),
2404 if_isnotdetached(assembler), done(assembler);
2405
2406 Node* buffer =
2407 assembler->LoadObjectField(array, JSTypedArray::kBufferOffset);
2408 assembler->Branch(assembler->IsDetachedBuffer(buffer), &if_isdetached,
2409 &if_isnotdetached);
2410
2411 assembler->Bind(&if_isnotdetached);
2412 {
2413 var_length.Bind(
2414 assembler->LoadObjectField(array, JSTypedArray::kLengthOffset));
2415 assembler->Goto(&done);
2416 }
2417
2418 assembler->Bind(&if_isdetached);
2419 {
2420 // TODO(caitp): If IsDetached(buffer) is true, throw a TypeError, per
2421 // https://github.com/tc39/ecma262/issues/713
2422 var_length.Bind(assembler->SmiConstant(Smi::kZero));
2423 assembler->Goto(&done);
2424 }
2425
2426 assembler->Bind(&done);
2427 length = var_length.value();
2428 }
2429 CSA_ASSERT(assembler, assembler->TaggedIsSmi(length));
2430 CSA_ASSERT(assembler, assembler->TaggedIsSmi(index));
2431
2432 assembler->GotoUnless(assembler->SmiBelow(index, length), &set_done);
2433
2434 Node* one = assembler->SmiConstant(Smi::FromInt(1));
2435 assembler->StoreObjectFieldNoWriteBarrier(
2436 iterator, JSArrayIterator::kNextIndexOffset,
2437 assembler->IntPtrAdd(assembler->BitcastTaggedToWord(index),
2438 assembler->BitcastTaggedToWord(one)));
2439 var_done.Bind(assembler->FalseConstant());
2440
2441 Node* elements = assembler->LoadElements(array);
2442 Node* base_ptr = assembler->LoadObjectField(
2443 elements, FixedTypedArrayBase::kBasePointerOffset);
2444 Node* external_ptr = assembler->LoadObjectField(
2445 elements, FixedTypedArrayBase::kExternalPointerOffset);
2446 Node* data_ptr = assembler->IntPtrAdd(base_ptr, external_ptr);
2447
2448 static int32_t kInstanceType[] = {
2449 JS_TYPED_ARRAY_KEY_ITERATOR_TYPE,
2450 JS_UINT8_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2451 JS_UINT8_CLAMPED_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2452 JS_INT8_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2453 JS_UINT16_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2454 JS_INT16_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2455 JS_UINT32_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2456 JS_INT32_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2457 JS_FLOAT32_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2458 JS_FLOAT64_ARRAY_KEY_VALUE_ITERATOR_TYPE,
2459 JS_UINT8_ARRAY_VALUE_ITERATOR_TYPE,
2460 JS_UINT8_CLAMPED_ARRAY_VALUE_ITERATOR_TYPE,
2461 JS_INT8_ARRAY_VALUE_ITERATOR_TYPE,
2462 JS_UINT16_ARRAY_VALUE_ITERATOR_TYPE,
2463 JS_INT16_ARRAY_VALUE_ITERATOR_TYPE,
2464 JS_UINT32_ARRAY_VALUE_ITERATOR_TYPE,
2465 JS_INT32_ARRAY_VALUE_ITERATOR_TYPE,
2466 JS_FLOAT32_ARRAY_VALUE_ITERATOR_TYPE,
2467 JS_FLOAT64_ARRAY_VALUE_ITERATOR_TYPE,
2468 };
2469
2470 Label uint8_values(assembler), int8_values(assembler),
2471 uint16_values(assembler), int16_values(assembler),
2472 uint32_values(assembler), int32_values(assembler),
2473 float32_values(assembler), float64_values(assembler);
2474 Label* kInstanceTypeHandlers[] = {
2475 &allocate_key_result, &uint8_values, &uint8_values,
2476 &int8_values, &uint16_values, &int16_values,
2477 &uint32_values, &int32_values, &float32_values,
2478 &float64_values, &uint8_values, &uint8_values,
2479 &int8_values, &uint16_values, &int16_values,
2480 &uint32_values, &int32_values, &float32_values,
2481 &float64_values,
2482 };
2483
2484 var_done.Bind(assembler->FalseConstant());
2485 assembler->Switch(instance_type, &throw_bad_receiver, kInstanceType,
2486 kInstanceTypeHandlers, arraysize(kInstanceType));
2487
2488 assembler->Bind(&uint8_values);
2489 {
2490 Node* value_uint8 = assembler->LoadFixedTypedArrayElement(
2491 data_ptr, index, UINT8_ELEMENTS, CodeStubAssembler::SMI_PARAMETERS);
2492 var_value.Bind(assembler->SmiFromWord(value_uint8));
2493 assembler->Goto(&allocate_entry_if_needed);
2494 }
2495
2496 assembler->Bind(&int8_values);
2497 {
2498 Node* value_int8 = assembler->LoadFixedTypedArrayElement(
2499 data_ptr, index, INT8_ELEMENTS, CodeStubAssembler::SMI_PARAMETERS);
2500 var_value.Bind(assembler->SmiFromWord(value_int8));
2501 assembler->Goto(&allocate_entry_if_needed);
2502 }
2503
2504 assembler->Bind(&uint16_values);
2505 {
2506 Node* value_uint16 = assembler->LoadFixedTypedArrayElement(
2507 data_ptr, index, UINT16_ELEMENTS,
2508 CodeStubAssembler::SMI_PARAMETERS);
2509 var_value.Bind(assembler->SmiFromWord(value_uint16));
2510 assembler->Goto(&allocate_entry_if_needed);
2511 }
2512
2513 assembler->Bind(&int16_values);
2514 {
2515 Node* value_int16 = assembler->LoadFixedTypedArrayElement(
2516 data_ptr, index, INT16_ELEMENTS, CodeStubAssembler::SMI_PARAMETERS);
2517 var_value.Bind(assembler->SmiFromWord(value_int16));
2518 assembler->Goto(&allocate_entry_if_needed);
2519 }
2520
2521 assembler->Bind(&uint32_values);
2522 {
2523 Node* value_uint32 = assembler->LoadFixedTypedArrayElement(
2524 data_ptr, index, UINT32_ELEMENTS,
2525 CodeStubAssembler::SMI_PARAMETERS);
2526 var_value.Bind(assembler->ChangeUint32ToTagged(value_uint32));
2527 assembler->Goto(&allocate_entry_if_needed);
2528 }
2529 assembler->Bind(&int32_values);
2530 {
2531 Node* value_int32 = assembler->LoadFixedTypedArrayElement(
2532 data_ptr, index, INT32_ELEMENTS, CodeStubAssembler::SMI_PARAMETERS);
2533 var_value.Bind(assembler->ChangeInt32ToTagged(value_int32));
2534 assembler->Goto(&allocate_entry_if_needed);
2535 }
2536 assembler->Bind(&float32_values);
2537 {
2538 Node* value_float32 = assembler->LoadFixedTypedArrayElement(
2539 data_ptr, index, FLOAT32_ELEMENTS,
2540 CodeStubAssembler::SMI_PARAMETERS);
2541 var_value.Bind(assembler->AllocateHeapNumberWithValue(
2542 assembler->ChangeFloat32ToFloat64(value_float32)));
2543 assembler->Goto(&allocate_entry_if_needed);
2544 }
2545 assembler->Bind(&float64_values);
2546 {
2547 Node* value_float64 = assembler->LoadFixedTypedArrayElement(
2548 data_ptr, index, FLOAT64_ELEMENTS,
2549 CodeStubAssembler::SMI_PARAMETERS);
2550 var_value.Bind(assembler->AllocateHeapNumberWithValue(value_float64));
2551 assembler->Goto(&allocate_entry_if_needed);
2552 }
2553 }
2554 }
2555
2556 assembler->Bind(&set_done);
2557 {
2558 assembler->StoreObjectFieldNoWriteBarrier(
2559 iterator, JSArrayIterator::kIteratedObjectOffset,
2560 assembler->UndefinedConstant());
2561 assembler->Goto(&allocate_iterator_result);
2562 }
2563
2564 assembler->Bind(&allocate_key_result);
2565 {
2566 var_value.Bind(index);
2567 var_done.Bind(assembler->FalseConstant());
2568 assembler->Goto(&allocate_iterator_result);
2569 }
2570
2571 assembler->Bind(&allocate_entry_if_needed);
2572 {
2573 assembler->GotoIf(
2574 assembler->Int32GreaterThan(
2575 instance_type,
2576 assembler->Int32Constant(LAST_ARRAY_KEY_VALUE_ITERATOR_TYPE)),
2577 &allocate_iterator_result);
2578
2579 Node* elements = assembler->AllocateFixedArray(FAST_ELEMENTS,
2580 assembler->Int32Constant(2));
2581 assembler->StoreFixedArrayElement(elements, assembler->Int32Constant(0),
2582 index, SKIP_WRITE_BARRIER);
2583 assembler->StoreFixedArrayElement(elements, assembler->Int32Constant(1),
2584 var_value.value(), SKIP_WRITE_BARRIER);
2585
2586 Node* entry = assembler->Allocate(JSArray::kSize);
2587 Node* map = assembler->LoadContextElement(
2588 assembler->LoadNativeContext(context),
2589 Context::JS_ARRAY_FAST_ELEMENTS_MAP_INDEX);
2590
2591 assembler->StoreMapNoWriteBarrier(entry, map);
2592 assembler->StoreObjectFieldRoot(entry, JSArray::kPropertiesOffset,
2593 Heap::kEmptyFixedArrayRootIndex);
2594 assembler->StoreObjectFieldNoWriteBarrier(entry, JSArray::kElementsOffset,
2595 elements);
2596 assembler->StoreObjectFieldNoWriteBarrier(
2597 entry, JSArray::kLengthOffset, assembler->SmiConstant(Smi::FromInt(2)));
2598
2599 var_value.Bind(entry);
2600 assembler->Goto(&allocate_iterator_result);
2601 }
2602
2603 assembler->Bind(&allocate_iterator_result);
2604 {
2605 Node* result = assembler->Allocate(JSIteratorResult::kSize);
2606 Node* map =
2607 assembler->LoadContextElement(assembler->LoadNativeContext(context),
2608 Context::ITERATOR_RESULT_MAP_INDEX);
2609 assembler->StoreMapNoWriteBarrier(result, map);
2610 assembler->StoreObjectFieldRoot(result, JSIteratorResult::kPropertiesOffset,
2611 Heap::kEmptyFixedArrayRootIndex);
2612 assembler->StoreObjectFieldRoot(result, JSIteratorResult::kElementsOffset,
2613 Heap::kEmptyFixedArrayRootIndex);
2614 assembler->StoreObjectFieldNoWriteBarrier(
2615 result, JSIteratorResult::kValueOffset, var_value.value());
2616 assembler->StoreObjectFieldNoWriteBarrier(
2617 result, JSIteratorResult::kDoneOffset, var_done.value());
2618 assembler->Return(result);
2619 }
2620
2621 assembler->Bind(&throw_bad_receiver);
2622 {
2623 // The {receiver} is not a valid JSArrayIterator.
2624 Node* result = assembler->CallRuntime(
2625 Runtime::kThrowIncompatibleMethodReceiver, context,
2626 assembler->HeapConstant(assembler->factory()->NewStringFromAsciiChecked(
2627 "Array Iterator.prototype.next", TENURED)),
2628 iterator);
2629 assembler->Return(result);
2630 }
2631 }
2632
2633 } // namespace internal
2634 } // namespace v8
2635