1 // Copyright 2014 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/runtime/runtime-utils.h"
6
7 #include "src/arguments.h"
8 #include "src/code-stubs.h"
9 #include "src/conversions-inl.h"
10 #include "src/debug/debug.h"
11 #include "src/elements.h"
12 #include "src/heap/factory.h"
13 #include "src/isolate-inl.h"
14 #include "src/keys.h"
15 #include "src/messages.h"
16 #include "src/objects/hash-table-inl.h"
17 #include "src/prototype.h"
18
19 namespace v8 {
20 namespace internal {
21
RUNTIME_FUNCTION(Runtime_TransitionElementsKind)22 RUNTIME_FUNCTION(Runtime_TransitionElementsKind) {
23 HandleScope scope(isolate);
24 DCHECK_EQ(2, args.length());
25 CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
26 CONVERT_ARG_HANDLE_CHECKED(Map, to_map, 1);
27 ElementsKind to_kind = to_map->elements_kind();
28 ElementsAccessor::ForKind(to_kind)->TransitionElementsKind(object, to_map);
29 return *object;
30 }
31
32 namespace {
33 // Find the next free position. undefined and holes are both considered
34 // free spots. Returns "Nothing" if an exception occurred.
35 V8_WARN_UNUSED_RESULT
FindNextFreePosition(Isolate * isolate,Handle<JSReceiver> receiver,uint32_t current_pos)36 Maybe<uint32_t> FindNextFreePosition(Isolate* isolate,
37 Handle<JSReceiver> receiver,
38 uint32_t current_pos) {
39 for (uint32_t position = current_pos;; ++position) {
40 Maybe<bool> has_element = JSReceiver::HasElement(receiver, position);
41 MAYBE_RETURN(has_element, Nothing<uint32_t>());
42 if (!has_element.FromJust()) return Just(position);
43
44 Handle<Object> element;
45 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
46 isolate, element, JSReceiver::GetElement(isolate, receiver, position),
47 Nothing<uint32_t>());
48 if (element->IsUndefined(isolate)) return Just(position);
49 }
50 }
51
52 // As RemoveArrayHoles, but also handles Dictionary elements that stay
53 // Dictionary (requires_slow_elements() is true), proxies and objects that
54 // might have accessors.
55 V8_WARN_UNUSED_RESULT
RemoveArrayHolesGeneric(Isolate * isolate,Handle<JSReceiver> receiver,uint32_t limit)56 Object* RemoveArrayHolesGeneric(Isolate* isolate, Handle<JSReceiver> receiver,
57 uint32_t limit) {
58 HandleScope scope(isolate);
59
60 // For proxies, we do not collect the keys, instead we use all indices in
61 // the full range of [0, limit).
62 Handle<FixedArray> keys;
63 if (receiver->IsJSProxy()) {
64 CHECK(Smi::IsValid(limit));
65 keys = isolate->factory()->NewFixedArray(limit);
66 for (uint32_t i = 0; i < limit; ++i) {
67 keys->set(i, Smi::FromInt(i));
68 }
69 } else {
70 keys = JSReceiver::GetOwnElementIndices(isolate, receiver,
71 Handle<JSObject>::cast(receiver));
72 }
73
74 uint32_t num_undefined = 0;
75 uint32_t current_pos = 0;
76 int num_indices = keys->length();
77
78 // Compact keys with undefined values and moves non-undefined
79 // values to the front.
80 // The loop does two things simultaneously:
81 // (1) Count the number of 'undefined', i.e.
82 // i.e.: HasProperty(receiver, key) && Get(receiver, key) == undefined
83 // (2) Move all non-undefined values to the front. The variable current_pos
84 // is used to track free spots in the array starting at the beginning.
85 // Holes and 'undefined' are considered free spots.
86 // A hole is when HasElement(receiver, key) is false.
87 for (int i = 0; i < num_indices; ++i) {
88 uint32_t key = NumberToUint32(keys->get(i));
89
90 // We only care about array indices that are smaller than the limit.
91 // The keys are sorted, so we can break as soon as we encounter the first.
92 if (key >= limit) break;
93
94 Maybe<bool> has_element = JSReceiver::HasElement(receiver, key);
95 MAYBE_RETURN(has_element, isolate->heap()->exception());
96 if (!has_element.FromJust()) {
97 continue;
98 }
99
100 Handle<Object> element;
101 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
102 isolate, element, JSReceiver::GetElement(isolate, receiver, key));
103
104 if (element->IsUndefined(isolate)) {
105 ++num_undefined;
106 } else {
107 // Find next free position to move elements to.
108 Maybe<uint32_t> free_position =
109 FindNextFreePosition(isolate, receiver, current_pos);
110 MAYBE_RETURN(free_position, isolate->heap()->exception());
111 current_pos = free_position.FromJust();
112
113 // Do not move elements that are already in the "packed" area.
114 if (key <= current_pos) continue;
115
116 // array[current_pos] = array[key].
117 // Deleting array[key] is done later. This is to preserve the same
118 // semantics as the old JS implementation when working with non-extensible
119 // objects:
120 // If the array contains undefineds, the position at 'key' might later
121 // bet set to 'undefined'. If we delete the element now and later set it
122 // to undefined, the set operation would throw an exception.
123 RETURN_FAILURE_ON_EXCEPTION(
124 isolate, JSReceiver::SetElement(isolate, receiver, current_pos,
125 element, LanguageMode::kStrict));
126 ++current_pos;
127 }
128 }
129
130 // Set [current_pos, current_pos + num_undefined) to undefined.
131 uint32_t result = current_pos;
132 for (uint32_t i = 0; i < num_undefined; ++i) {
133 RETURN_FAILURE_ON_EXCEPTION(
134 isolate, JSReceiver::SetElement(isolate, receiver, current_pos++,
135 isolate->factory()->undefined_value(),
136 LanguageMode::kStrict));
137 }
138 // TODO(szuend): Re-enable when we also copy from the prototype chain for
139 // JSArrays. Then we can use HasOwnProperty instead of
140 // HasElement and this condition will hold.
141 // DCHECK_LE(current_pos, num_indices);
142
143 // Deleting everything after the undefineds up unto the limit.
144 for (int i = num_indices - 1; i >= 0; --i) {
145 uint32_t key = NumberToUint32(keys->get(i));
146 if (key < current_pos) break;
147 if (key >= limit) continue;
148
149 Maybe<bool> delete_result = JSReceiver::DeleteElement(receiver, key);
150 MAYBE_RETURN(delete_result, isolate->heap()->exception());
151 }
152
153 return *isolate->factory()->NewNumberFromUint(result);
154 }
155
156 // Collects all defined (non-hole) and non-undefined (array) elements at the
157 // start of the elements array. If the object is in dictionary mode, it is
158 // converted to fast elements mode. Undefined values are placed after
159 // non-undefined values. Returns the number of non-undefined values.
160 V8_WARN_UNUSED_RESULT
RemoveArrayHoles(Isolate * isolate,Handle<JSReceiver> receiver,uint32_t limit)161 Object* RemoveArrayHoles(Isolate* isolate, Handle<JSReceiver> receiver,
162 uint32_t limit) {
163 if (receiver->IsJSProxy()) {
164 return RemoveArrayHolesGeneric(isolate, receiver, limit);
165 }
166
167 Handle<JSObject> object = Handle<JSObject>::cast(receiver);
168 if (object->HasStringWrapperElements()) {
169 int len = String::cast(Handle<JSValue>::cast(object)->value())->length();
170 return Smi::FromInt(len);
171 }
172
173 if (object->HasSloppyArgumentsElements() || !object->map()->is_extensible()) {
174 return RemoveArrayHolesGeneric(isolate, receiver, limit);
175 }
176
177 JSObject::ValidateElements(*object);
178 if (object->HasDictionaryElements()) {
179 // Convert to fast elements containing only the existing properties.
180 // Ordering is irrelevant, since we are going to sort anyway.
181 Handle<NumberDictionary> dict(object->element_dictionary());
182 if (object->IsJSArray() || dict->requires_slow_elements() ||
183 dict->max_number_key() >= limit) {
184 return RemoveArrayHolesGeneric(isolate, receiver, limit);
185 }
186 // Convert to fast elements.
187 Handle<Map> new_map =
188 JSObject::GetElementsTransitionMap(object, HOLEY_ELEMENTS);
189
190 PretenureFlag tenure =
191 isolate->heap()->InNewSpace(*object) ? NOT_TENURED : TENURED;
192 Handle<FixedArray> fast_elements =
193 isolate->factory()->NewFixedArray(dict->NumberOfElements(), tenure);
194 dict->CopyValuesTo(*fast_elements);
195
196 JSObject::SetMapAndElements(object, new_map, fast_elements);
197 JSObject::ValidateElements(*object);
198 } else if (object->HasFixedTypedArrayElements()) {
199 // Typed arrays cannot have holes or undefined elements.
200 int array_length = FixedArrayBase::cast(object->elements())->length();
201 return Smi::FromInt(Min(limit, static_cast<uint32_t>(array_length)));
202 } else if (!object->HasDoubleElements()) {
203 JSObject::EnsureWritableFastElements(object);
204 }
205 DCHECK(object->HasSmiOrObjectElements() || object->HasDoubleElements());
206
207 // Collect holes at the end, undefined before that and the rest at the
208 // start, and return the number of non-hole, non-undefined values.
209
210 Handle<FixedArrayBase> elements_base(object->elements());
211 uint32_t elements_length = static_cast<uint32_t>(elements_base->length());
212 if (limit > elements_length) {
213 limit = elements_length;
214 }
215 if (limit == 0) {
216 return Smi::kZero;
217 }
218
219 uint32_t result = 0;
220 if (elements_base->map() == isolate->heap()->fixed_double_array_map()) {
221 FixedDoubleArray* elements = FixedDoubleArray::cast(*elements_base);
222 // Split elements into defined and the_hole, in that order.
223 unsigned int holes = limit;
224 // Assume most arrays contain no holes and undefined values, so minimize the
225 // number of stores of non-undefined, non-the-hole values.
226 for (unsigned int i = 0; i < holes; i++) {
227 if (elements->is_the_hole(i)) {
228 holes--;
229 } else {
230 continue;
231 }
232 // Position i needs to be filled.
233 while (holes > i) {
234 if (elements->is_the_hole(holes)) {
235 holes--;
236 } else {
237 elements->set(i, elements->get_scalar(holes));
238 break;
239 }
240 }
241 }
242 result = holes;
243 while (holes < limit) {
244 elements->set_the_hole(holes);
245 holes++;
246 }
247 } else {
248 FixedArray* elements = FixedArray::cast(*elements_base);
249 DisallowHeapAllocation no_gc;
250
251 // Split elements into defined, undefined and the_hole, in that order. Only
252 // count locations for undefined and the hole, and fill them afterwards.
253 WriteBarrierMode write_barrier = elements->GetWriteBarrierMode(no_gc);
254 unsigned int undefs = limit;
255 unsigned int holes = limit;
256 // Assume most arrays contain no holes and undefined values, so minimize the
257 // number of stores of non-undefined, non-the-hole values.
258 for (unsigned int i = 0; i < undefs; i++) {
259 Object* current = elements->get(i);
260 if (current->IsTheHole(isolate)) {
261 holes--;
262 undefs--;
263 } else if (current->IsUndefined(isolate)) {
264 undefs--;
265 } else {
266 continue;
267 }
268 // Position i needs to be filled.
269 while (undefs > i) {
270 current = elements->get(undefs);
271 if (current->IsTheHole(isolate)) {
272 holes--;
273 undefs--;
274 } else if (current->IsUndefined(isolate)) {
275 undefs--;
276 } else {
277 elements->set(i, current, write_barrier);
278 break;
279 }
280 }
281 }
282 result = undefs;
283 while (undefs < holes) {
284 elements->set_undefined(isolate, undefs);
285 undefs++;
286 }
287 while (holes < limit) {
288 elements->set_the_hole(isolate, holes);
289 holes++;
290 }
291 }
292
293 return *isolate->factory()->NewNumberFromUint(result);
294 }
295
296 // Copy element at index from source to target only if target does not have the
297 // element on its own. Returns true if a copy occurred, false if not
298 // and Nothing if an exception occurred.
299 V8_WARN_UNUSED_RESULT
ConditionalCopy(Isolate * isolate,Handle<JSReceiver> source,Handle<JSReceiver> target,uint32_t index)300 Maybe<bool> ConditionalCopy(Isolate* isolate, Handle<JSReceiver> source,
301 Handle<JSReceiver> target, uint32_t index) {
302 Maybe<bool> source_has_prop = JSReceiver::HasOwnProperty(source, index);
303 MAYBE_RETURN(source_has_prop, Nothing<bool>());
304 if (!source_has_prop.FromJust()) return Just(false);
305
306 Maybe<bool> target_has_prop = JSReceiver::HasOwnProperty(target, index);
307 MAYBE_RETURN(target_has_prop, Nothing<bool>());
308 if (target_has_prop.FromJust()) return Just(false);
309
310 Handle<Object> source_element;
311 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
312 isolate, source_element, JSReceiver::GetElement(isolate, source, index),
313 Nothing<bool>());
314
315 Handle<Object> set_result;
316 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
317 isolate, set_result,
318 JSReceiver::SetElement(isolate, target, index, source_element,
319 LanguageMode::kStrict),
320 Nothing<bool>());
321
322 return Just(true);
323 }
324
325 // Copy elements in the range 0..length from objects prototype chain
326 // to object itself, if object has holes. Returns null on error and undefined on
327 // success.
328 V8_WARN_UNUSED_RESULT
CopyFromPrototype(Isolate * isolate,Handle<JSReceiver> object,uint32_t length)329 MaybeHandle<Object> CopyFromPrototype(Isolate* isolate,
330 Handle<JSReceiver> object,
331 uint32_t length) {
332 for (PrototypeIterator iter(isolate, object, kStartAtPrototype);
333 !iter.IsAtEnd(); iter.Advance()) {
334 Handle<JSReceiver> current(PrototypeIterator::GetCurrent<JSReceiver>(iter));
335
336 if (current->IsJSProxy()) {
337 for (uint32_t i = 0; i < length; ++i) {
338 MAYBE_RETURN_NULL(ConditionalCopy(isolate, current, object, i));
339 }
340 } else {
341 Handle<FixedArray> keys = JSReceiver::GetOwnElementIndices(
342 isolate, object, Handle<JSObject>::cast(current));
343
344 uint32_t num_indices = keys->length();
345 for (uint32_t i = 0; i < num_indices; ++i) {
346 uint32_t idx = NumberToUint32(keys->get(i));
347
348 // Prototype might have indices that go past length, but we are only
349 // interested in the range [0, length).
350 if (idx >= length) break;
351
352 MAYBE_RETURN_NULL(ConditionalCopy(isolate, current, object, idx));
353 }
354 }
355 }
356 return isolate->factory()->undefined_value();
357 }
358
359 } // namespace
360
RUNTIME_FUNCTION(Runtime_PrepareElementsForSort)361 RUNTIME_FUNCTION(Runtime_PrepareElementsForSort) {
362 HandleScope scope(isolate);
363 DCHECK_EQ(2, args.length());
364 CONVERT_ARG_HANDLE_CHECKED(JSReceiver, object, 0);
365 CONVERT_NUMBER_CHECKED(uint32_t, length, Uint32, args[1]);
366
367 if (isolate->debug_execution_mode() == DebugInfo::kSideEffects) {
368 if (!isolate->debug()->PerformSideEffectCheckForObject(object)) {
369 return isolate->heap()->exception();
370 }
371 }
372
373 // Counter for sorting arrays that have non-packed elements and where either
374 // the ElementsProtector is invalid or the prototype does not match
375 // Array.prototype.
376 if (object->IsJSArray() &&
377 !Handle<JSArray>::cast(object)->HasFastPackedElements()) {
378 JSObject* initial_array_proto = JSObject::cast(
379 isolate->native_context()->get(Context::INITIAL_ARRAY_PROTOTYPE_INDEX));
380 if (!isolate->IsNoElementsProtectorIntact() ||
381 object->map()->prototype() != initial_array_proto) {
382 isolate->CountUsage(
383 v8::Isolate::kArrayPrototypeSortJSArrayModifiedPrototype);
384 }
385 }
386
387 if (!object->IsJSArray()) {
388 RETURN_FAILURE_ON_EXCEPTION(isolate,
389 CopyFromPrototype(isolate, object, length));
390 }
391 return RemoveArrayHoles(isolate, object, length);
392 }
393
394 // Move contents of argument 0 (an array) to argument 1 (an array)
RUNTIME_FUNCTION(Runtime_MoveArrayContents)395 RUNTIME_FUNCTION(Runtime_MoveArrayContents) {
396 HandleScope scope(isolate);
397 DCHECK_EQ(2, args.length());
398 CONVERT_ARG_HANDLE_CHECKED(JSArray, from, 0);
399 CONVERT_ARG_HANDLE_CHECKED(JSArray, to, 1);
400 JSObject::ValidateElements(*from);
401 JSObject::ValidateElements(*to);
402
403 Handle<FixedArrayBase> new_elements(from->elements());
404 ElementsKind from_kind = from->GetElementsKind();
405 Handle<Map> new_map = JSObject::GetElementsTransitionMap(to, from_kind);
406 JSObject::SetMapAndElements(to, new_map, new_elements);
407 to->set_length(from->length());
408
409 from->initialize_elements();
410 from->set_length(Smi::kZero);
411
412 JSObject::ValidateElements(*to);
413 return *to;
414 }
415
416
417 // How many elements does this object/array have?
RUNTIME_FUNCTION(Runtime_EstimateNumberOfElements)418 RUNTIME_FUNCTION(Runtime_EstimateNumberOfElements) {
419 DisallowHeapAllocation no_gc;
420 HandleScope scope(isolate);
421 DCHECK_EQ(1, args.length());
422 CONVERT_ARG_CHECKED(JSArray, array, 0);
423 FixedArrayBase* elements = array->elements();
424 SealHandleScope shs(isolate);
425 if (elements->IsDictionary()) {
426 int result = NumberDictionary::cast(elements)->NumberOfElements();
427 return Smi::FromInt(result);
428 } else {
429 DCHECK(array->length()->IsSmi());
430 // For packed elements, we know the exact number of elements
431 int length = elements->length();
432 ElementsKind kind = array->GetElementsKind();
433 if (IsFastPackedElementsKind(kind)) {
434 return Smi::FromInt(length);
435 }
436 // For holey elements, take samples from the buffer checking for holes
437 // to generate the estimate.
438 const int kNumberOfHoleCheckSamples = 97;
439 int increment = (length < kNumberOfHoleCheckSamples)
440 ? 1
441 : static_cast<int>(length / kNumberOfHoleCheckSamples);
442 ElementsAccessor* accessor = array->GetElementsAccessor();
443 int holes = 0;
444 for (int i = 0; i < length; i += increment) {
445 if (!accessor->HasElement(array, i, elements)) {
446 ++holes;
447 }
448 }
449 int estimate = static_cast<int>((kNumberOfHoleCheckSamples - holes) /
450 kNumberOfHoleCheckSamples * length);
451 return Smi::FromInt(estimate);
452 }
453 }
454
455
456 // Returns an array that tells you where in the [0, length) interval an array
457 // might have elements. Can either return an array of keys (positive integers
458 // or undefined) or a number representing the positive length of an interval
459 // starting at index 0.
460 // Intervals can span over some keys that are not in the object.
RUNTIME_FUNCTION(Runtime_GetArrayKeys)461 RUNTIME_FUNCTION(Runtime_GetArrayKeys) {
462 HandleScope scope(isolate);
463 DCHECK_EQ(2, args.length());
464 CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
465 CONVERT_NUMBER_CHECKED(uint32_t, length, Uint32, args[1]);
466 ElementsKind kind = array->GetElementsKind();
467
468 if (IsFastElementsKind(kind) || IsFixedTypedArrayElementsKind(kind)) {
469 uint32_t actual_length = static_cast<uint32_t>(array->elements()->length());
470 return *isolate->factory()->NewNumberFromUint(Min(actual_length, length));
471 }
472
473 if (kind == FAST_STRING_WRAPPER_ELEMENTS) {
474 int string_length =
475 String::cast(Handle<JSValue>::cast(array)->value())->length();
476 int backing_store_length = array->elements()->length();
477 return *isolate->factory()->NewNumberFromUint(
478 Min(length,
479 static_cast<uint32_t>(Max(string_length, backing_store_length))));
480 }
481
482 KeyAccumulator accumulator(isolate, KeyCollectionMode::kOwnOnly,
483 ALL_PROPERTIES);
484 for (PrototypeIterator iter(isolate, array, kStartAtReceiver);
485 !iter.IsAtEnd(); iter.Advance()) {
486 Handle<JSReceiver> current(PrototypeIterator::GetCurrent<JSReceiver>(iter));
487 if (current->HasComplexElements()) {
488 return *isolate->factory()->NewNumberFromUint(length);
489 }
490 accumulator.CollectOwnElementIndices(array,
491 Handle<JSObject>::cast(current));
492 }
493 // Erase any keys >= length.
494 Handle<FixedArray> keys =
495 accumulator.GetKeys(GetKeysConversion::kKeepNumbers);
496 int j = 0;
497 for (int i = 0; i < keys->length(); i++) {
498 if (NumberToUint32(keys->get(i)) >= length) continue;
499 if (i != j) keys->set(j, keys->get(i));
500 j++;
501 }
502
503 if (j != keys->length()) {
504 isolate->heap()->RightTrimFixedArray(*keys, keys->length() - j);
505 }
506
507 return *isolate->factory()->NewJSArrayWithElements(keys);
508 }
509
RUNTIME_FUNCTION(Runtime_TrySliceSimpleNonFastElements)510 RUNTIME_FUNCTION(Runtime_TrySliceSimpleNonFastElements) {
511 HandleScope scope(isolate);
512 DCHECK_EQ(3, args.length());
513 CONVERT_ARG_HANDLE_CHECKED(JSReceiver, receiver, 0);
514 CONVERT_SMI_ARG_CHECKED(first, 1);
515 CONVERT_SMI_ARG_CHECKED(count, 2);
516 uint32_t length = first + count;
517
518 // Only handle elements kinds that have a ElementsAccessor Slice
519 // implementation.
520 if (receiver->IsJSArray()) {
521 // This "fastish" path must make sure the destination array is a JSArray.
522 if (!isolate->IsArraySpeciesLookupChainIntact() ||
523 !JSArray::cast(*receiver)->HasArrayPrototype(isolate)) {
524 return Smi::FromInt(0);
525 }
526 } else {
527 int len;
528 if (!receiver->IsJSObject() ||
529 !JSSloppyArgumentsObject::GetSloppyArgumentsLength(
530 isolate, Handle<JSObject>::cast(receiver), &len) ||
531 (length > static_cast<uint32_t>(len))) {
532 return Smi::FromInt(0);
533 }
534 }
535
536 // This "fastish" path must also ensure that elements are simple (no
537 // geters/setters), no elements on prototype chain.
538 Handle<JSObject> object(Handle<JSObject>::cast(receiver));
539 if (!JSObject::PrototypeHasNoElements(isolate, *object) ||
540 object->HasComplexElements()) {
541 return Smi::FromInt(0);
542 }
543
544 ElementsAccessor* accessor = object->GetElementsAccessor();
545 return *accessor->Slice(object, first, length);
546 }
547
RUNTIME_FUNCTION(Runtime_NewArray)548 RUNTIME_FUNCTION(Runtime_NewArray) {
549 HandleScope scope(isolate);
550 DCHECK_LE(3, args.length());
551 int const argc = args.length() - 3;
552 // TODO(bmeurer): Remove this Arguments nonsense.
553 Arguments argv(argc, args.arguments() - 1);
554 CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, 0);
555 CONVERT_ARG_HANDLE_CHECKED(JSReceiver, new_target, argc + 1);
556 CONVERT_ARG_HANDLE_CHECKED(HeapObject, type_info, argc + 2);
557 // TODO(bmeurer): Use MaybeHandle to pass around the AllocationSite.
558 Handle<AllocationSite> site = type_info->IsAllocationSite()
559 ? Handle<AllocationSite>::cast(type_info)
560 : Handle<AllocationSite>::null();
561
562 Factory* factory = isolate->factory();
563
564 // If called through new, new.target can be:
565 // - a subclass of constructor,
566 // - a proxy wrapper around constructor, or
567 // - the constructor itself.
568 // If called through Reflect.construct, it's guaranteed to be a constructor by
569 // REFLECT_CONSTRUCT_PREPARE.
570 DCHECK(new_target->IsConstructor());
571
572 bool holey = false;
573 bool can_use_type_feedback = !site.is_null();
574 bool can_inline_array_constructor = true;
575 if (argv.length() == 1) {
576 Handle<Object> argument_one = argv.at<Object>(0);
577 if (argument_one->IsSmi()) {
578 int value = Handle<Smi>::cast(argument_one)->value();
579 if (value < 0 ||
580 JSArray::SetLengthWouldNormalize(isolate->heap(), value)) {
581 // the array is a dictionary in this case.
582 can_use_type_feedback = false;
583 } else if (value != 0) {
584 holey = true;
585 if (value >= JSArray::kInitialMaxFastElementArray) {
586 can_inline_array_constructor = false;
587 }
588 }
589 } else {
590 // Non-smi length argument produces a dictionary
591 can_use_type_feedback = false;
592 }
593 }
594
595 Handle<Map> initial_map;
596 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
597 isolate, initial_map,
598 JSFunction::GetDerivedMap(isolate, constructor, new_target));
599
600 ElementsKind to_kind = can_use_type_feedback ? site->GetElementsKind()
601 : initial_map->elements_kind();
602 if (holey && !IsHoleyElementsKind(to_kind)) {
603 to_kind = GetHoleyElementsKind(to_kind);
604 // Update the allocation site info to reflect the advice alteration.
605 if (!site.is_null()) site->SetElementsKind(to_kind);
606 }
607
608 // We should allocate with an initial map that reflects the allocation site
609 // advice. Therefore we use AllocateJSObjectFromMap instead of passing
610 // the constructor.
611 if (to_kind != initial_map->elements_kind()) {
612 initial_map = Map::AsElementsKind(initial_map, to_kind);
613 }
614
615 // If we don't care to track arrays of to_kind ElementsKind, then
616 // don't emit a memento for them.
617 Handle<AllocationSite> allocation_site;
618 if (AllocationSite::ShouldTrack(to_kind)) {
619 allocation_site = site;
620 }
621
622 Handle<JSArray> array = Handle<JSArray>::cast(
623 factory->NewJSObjectFromMap(initial_map, NOT_TENURED, allocation_site));
624
625 factory->NewJSArrayStorage(array, 0, 0, DONT_INITIALIZE_ARRAY_ELEMENTS);
626
627 ElementsKind old_kind = array->GetElementsKind();
628 RETURN_FAILURE_ON_EXCEPTION(isolate,
629 ArrayConstructInitializeElements(array, &argv));
630 if (!site.is_null()) {
631 if ((old_kind != array->GetElementsKind() || !can_use_type_feedback ||
632 !can_inline_array_constructor)) {
633 // The arguments passed in caused a transition. This kind of complexity
634 // can't be dealt with in the inlined hydrogen array constructor case.
635 // We must mark the allocationsite as un-inlinable.
636 site->SetDoNotInlineCall();
637 }
638 } else {
639 if (old_kind != array->GetElementsKind() || !can_inline_array_constructor) {
640 // We don't have an AllocationSite for this Array constructor invocation,
641 // i.e. it might a call from Array#map or from an Array subclass, so we
642 // just flip the bit on the global protector cell instead.
643 // TODO(bmeurer): Find a better way to mark this. Global protectors
644 // tend to back-fire over time...
645 if (isolate->IsArrayConstructorIntact()) {
646 isolate->InvalidateArrayConstructorProtector();
647 }
648 }
649 }
650
651 return *array;
652 }
653
RUNTIME_FUNCTION(Runtime_NormalizeElements)654 RUNTIME_FUNCTION(Runtime_NormalizeElements) {
655 HandleScope scope(isolate);
656 DCHECK_EQ(1, args.length());
657 CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
658 CHECK(!array->HasFixedTypedArrayElements());
659 CHECK(!array->IsJSGlobalProxy());
660 JSObject::NormalizeElements(array);
661 return *array;
662 }
663
664 // GrowArrayElements returns a sentinel Smi if the object was normalized or if
665 // the key is negative.
RUNTIME_FUNCTION(Runtime_GrowArrayElements)666 RUNTIME_FUNCTION(Runtime_GrowArrayElements) {
667 HandleScope scope(isolate);
668 DCHECK_EQ(2, args.length());
669 CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
670 CONVERT_NUMBER_CHECKED(int, key, Int32, args[1]);
671
672 if (key < 0) return Smi::kZero;
673
674 uint32_t capacity = static_cast<uint32_t>(object->elements()->length());
675 uint32_t index = static_cast<uint32_t>(key);
676
677 if (index >= capacity) {
678 if (!object->GetElementsAccessor()->GrowCapacity(object, index)) {
679 return Smi::kZero;
680 }
681 }
682
683 return object->elements();
684 }
685
686
RUNTIME_FUNCTION(Runtime_HasComplexElements)687 RUNTIME_FUNCTION(Runtime_HasComplexElements) {
688 HandleScope scope(isolate);
689 DCHECK_EQ(1, args.length());
690 CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
691 for (PrototypeIterator iter(isolate, array, kStartAtReceiver);
692 !iter.IsAtEnd(); iter.Advance()) {
693 if (PrototypeIterator::GetCurrent<JSReceiver>(iter)->HasComplexElements()) {
694 return isolate->heap()->true_value();
695 }
696 }
697 return isolate->heap()->false_value();
698 }
699
700 // ES6 22.1.2.2 Array.isArray
RUNTIME_FUNCTION(Runtime_ArrayIsArray)701 RUNTIME_FUNCTION(Runtime_ArrayIsArray) {
702 HandleScope shs(isolate);
703 DCHECK_EQ(1, args.length());
704 CONVERT_ARG_HANDLE_CHECKED(Object, object, 0);
705 Maybe<bool> result = Object::IsArray(object);
706 MAYBE_RETURN(result, isolate->heap()->exception());
707 return isolate->heap()->ToBoolean(result.FromJust());
708 }
709
RUNTIME_FUNCTION(Runtime_IsArray)710 RUNTIME_FUNCTION(Runtime_IsArray) {
711 SealHandleScope shs(isolate);
712 DCHECK_EQ(1, args.length());
713 CONVERT_ARG_CHECKED(Object, obj, 0);
714 return isolate->heap()->ToBoolean(obj->IsJSArray());
715 }
716
RUNTIME_FUNCTION(Runtime_ArraySpeciesConstructor)717 RUNTIME_FUNCTION(Runtime_ArraySpeciesConstructor) {
718 HandleScope scope(isolate);
719 DCHECK_EQ(1, args.length());
720 CONVERT_ARG_HANDLE_CHECKED(Object, original_array, 0);
721 RETURN_RESULT_OR_FAILURE(
722 isolate, Object::ArraySpeciesConstructor(isolate, original_array));
723 }
724
725 // ES7 22.1.3.11 Array.prototype.includes
RUNTIME_FUNCTION(Runtime_ArrayIncludes_Slow)726 RUNTIME_FUNCTION(Runtime_ArrayIncludes_Slow) {
727 HandleScope shs(isolate);
728 DCHECK_EQ(3, args.length());
729 CONVERT_ARG_HANDLE_CHECKED(Object, search_element, 1);
730 CONVERT_ARG_HANDLE_CHECKED(Object, from_index, 2);
731
732 // Let O be ? ToObject(this value).
733 Handle<JSReceiver> object;
734 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
735 isolate, object, Object::ToObject(isolate, handle(args[0], isolate)));
736
737 // Let len be ? ToLength(? Get(O, "length")).
738 int64_t len;
739 {
740 if (object->map()->instance_type() == JS_ARRAY_TYPE) {
741 uint32_t len32 = 0;
742 bool success = JSArray::cast(*object)->length()->ToArrayLength(&len32);
743 DCHECK(success);
744 USE(success);
745 len = len32;
746 } else {
747 Handle<Object> len_;
748 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
749 isolate, len_,
750 Object::GetProperty(object, isolate->factory()->length_string()));
751
752 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, len_,
753 Object::ToLength(isolate, len_));
754 len = static_cast<int64_t>(len_->Number());
755 DCHECK_EQ(len, len_->Number());
756 }
757 }
758
759 if (len == 0) return isolate->heap()->false_value();
760
761 // Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step
762 // produces the value 0.)
763 int64_t index = 0;
764 if (!from_index->IsUndefined(isolate)) {
765 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, from_index,
766 Object::ToInteger(isolate, from_index));
767
768 if (V8_LIKELY(from_index->IsSmi())) {
769 int start_from = Smi::ToInt(*from_index);
770 if (start_from < 0) {
771 index = std::max<int64_t>(len + start_from, 0);
772 } else {
773 index = start_from;
774 }
775 } else {
776 DCHECK(from_index->IsHeapNumber());
777 double start_from = from_index->Number();
778 if (start_from >= len) return isolate->heap()->false_value();
779 if (V8_LIKELY(std::isfinite(start_from))) {
780 if (start_from < 0) {
781 index = static_cast<int64_t>(std::max<double>(start_from + len, 0));
782 } else {
783 index = start_from;
784 }
785 }
786 }
787
788 DCHECK_GE(index, 0);
789 }
790
791 // If the receiver is not a special receiver type, and the length is a valid
792 // element index, perform fast operation tailored to specific ElementsKinds.
793 if (!object->map()->IsSpecialReceiverMap() && len < kMaxUInt32 &&
794 JSObject::PrototypeHasNoElements(isolate, JSObject::cast(*object))) {
795 Handle<JSObject> obj = Handle<JSObject>::cast(object);
796 ElementsAccessor* elements = obj->GetElementsAccessor();
797 Maybe<bool> result = elements->IncludesValue(isolate, obj, search_element,
798 static_cast<uint32_t>(index),
799 static_cast<uint32_t>(len));
800 MAYBE_RETURN(result, isolate->heap()->exception());
801 return *isolate->factory()->ToBoolean(result.FromJust());
802 }
803
804 // Otherwise, perform slow lookups for special receiver types
805 for (; index < len; ++index) {
806 // Let elementK be the result of ? Get(O, ! ToString(k)).
807 Handle<Object> element_k;
808 {
809 Handle<Object> index_obj = isolate->factory()->NewNumberFromInt64(index);
810 bool success;
811 LookupIterator it = LookupIterator::PropertyOrElement(
812 isolate, object, index_obj, &success);
813 DCHECK(success);
814 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, element_k,
815 Object::GetProperty(&it));
816 }
817
818 // If SameValueZero(searchElement, elementK) is true, return true.
819 if (search_element->SameValueZero(*element_k)) {
820 return isolate->heap()->true_value();
821 }
822 }
823 return isolate->heap()->false_value();
824 }
825
RUNTIME_FUNCTION(Runtime_ArrayIndexOf)826 RUNTIME_FUNCTION(Runtime_ArrayIndexOf) {
827 HandleScope shs(isolate);
828 DCHECK_EQ(3, args.length());
829 CONVERT_ARG_HANDLE_CHECKED(Object, search_element, 1);
830 CONVERT_ARG_HANDLE_CHECKED(Object, from_index, 2);
831
832 // Let O be ? ToObject(this value).
833 Handle<JSReceiver> object;
834 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
835 isolate, object,
836 Object::ToObject(isolate, args.at(0), "Array.prototype.indexOf"));
837
838 // Let len be ? ToLength(? Get(O, "length")).
839 int64_t len;
840 {
841 if (object->IsJSArray()) {
842 uint32_t len32 = 0;
843 bool success = JSArray::cast(*object)->length()->ToArrayLength(&len32);
844 DCHECK(success);
845 USE(success);
846 len = len32;
847 } else {
848 Handle<Object> len_;
849 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
850 isolate, len_,
851 Object::GetProperty(object, isolate->factory()->length_string()));
852
853 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, len_,
854 Object::ToLength(isolate, len_));
855 len = static_cast<int64_t>(len_->Number());
856 DCHECK_EQ(len, len_->Number());
857 }
858 }
859
860 if (len == 0) return Smi::FromInt(-1);
861
862 // Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step
863 // produces the value 0.)
864 int64_t start_from;
865 {
866 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, from_index,
867 Object::ToInteger(isolate, from_index));
868 double fp = from_index->Number();
869 if (fp > len) return Smi::FromInt(-1);
870 if (V8_LIKELY(fp >=
871 static_cast<double>(std::numeric_limits<int64_t>::min()))) {
872 DCHECK(fp < std::numeric_limits<int64_t>::max());
873 start_from = static_cast<int64_t>(fp);
874 } else {
875 start_from = std::numeric_limits<int64_t>::min();
876 }
877 }
878
879 int64_t index;
880 if (start_from >= 0) {
881 index = start_from;
882 } else {
883 index = len + start_from;
884 if (index < 0) {
885 index = 0;
886 }
887 }
888
889 // If the receiver is not a special receiver type, and the length is a valid
890 // element index, perform fast operation tailored to specific ElementsKinds.
891 if (!object->map()->IsSpecialReceiverMap() && len < kMaxUInt32 &&
892 JSObject::PrototypeHasNoElements(isolate, JSObject::cast(*object))) {
893 Handle<JSObject> obj = Handle<JSObject>::cast(object);
894 ElementsAccessor* elements = obj->GetElementsAccessor();
895 Maybe<int64_t> result = elements->IndexOfValue(isolate, obj, search_element,
896 static_cast<uint32_t>(index),
897 static_cast<uint32_t>(len));
898 MAYBE_RETURN(result, isolate->heap()->exception());
899 return *isolate->factory()->NewNumberFromInt64(result.FromJust());
900 }
901
902 // Otherwise, perform slow lookups for special receiver types
903 for (; index < len; ++index) {
904 // Let elementK be the result of ? Get(O, ! ToString(k)).
905 Handle<Object> element_k;
906 {
907 Handle<Object> index_obj = isolate->factory()->NewNumberFromInt64(index);
908 bool success;
909 LookupIterator it = LookupIterator::PropertyOrElement(
910 isolate, object, index_obj, &success);
911 DCHECK(success);
912 Maybe<bool> present = JSReceiver::HasProperty(&it);
913 MAYBE_RETURN(present, isolate->heap()->exception());
914 if (!present.FromJust()) continue;
915 ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, element_k,
916 Object::GetProperty(&it));
917 if (search_element->StrictEquals(*element_k)) {
918 return *index_obj;
919 }
920 }
921 }
922 return Smi::FromInt(-1);
923 }
924
925 } // namespace internal
926 } // namespace v8
927