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