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