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