1// Copyright 2014 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/runtime/runtime-utils.h"
6
7#include "src/arguments.h"
8#include "src/code-stubs.h"
9#include "src/conversions-inl.h"
10#include "src/elements.h"
11#include "src/factory.h"
12#include "src/isolate-inl.h"
13#include "src/keys.h"
14#include "src/messages.h"
15#include "src/prototype.h"
16
17namespace v8 {
18namespace internal {
19
20RUNTIME_FUNCTION(Runtime_FinishArrayPrototypeSetup) {
21  HandleScope scope(isolate);
22  DCHECK(args.length() == 1);
23  CONVERT_ARG_HANDLE_CHECKED(JSArray, prototype, 0);
24  Object* length = prototype->length();
25  CHECK(length->IsSmi());
26  CHECK(Smi::cast(length)->value() == 0);
27  CHECK(prototype->HasFastSmiOrObjectElements());
28  // This is necessary to enable fast checks for absence of elements
29  // on Array.prototype and below.
30  prototype->set_elements(isolate->heap()->empty_fixed_array());
31  return Smi::kZero;
32}
33
34static void InstallCode(
35    Isolate* isolate, Handle<JSObject> holder, const char* name,
36    Handle<Code> code, int argc = -1,
37    BuiltinFunctionId id = static_cast<BuiltinFunctionId>(-1)) {
38  Handle<String> key = isolate->factory()->InternalizeUtf8String(name);
39  Handle<JSFunction> optimized =
40      isolate->factory()->NewFunctionWithoutPrototype(key, code);
41  if (argc < 0) {
42    optimized->shared()->DontAdaptArguments();
43  } else {
44    optimized->shared()->set_internal_formal_parameter_count(argc);
45  }
46  if (id >= 0) {
47    optimized->shared()->set_builtin_function_id(id);
48  }
49  JSObject::AddProperty(holder, key, optimized, NONE);
50}
51
52static void InstallBuiltin(
53    Isolate* isolate, Handle<JSObject> holder, const char* name,
54    Builtins::Name builtin_name, int argc = -1,
55    BuiltinFunctionId id = static_cast<BuiltinFunctionId>(-1)) {
56  InstallCode(isolate, holder, name,
57              handle(isolate->builtins()->builtin(builtin_name), isolate), argc,
58              id);
59}
60
61RUNTIME_FUNCTION(Runtime_SpecialArrayFunctions) {
62  HandleScope scope(isolate);
63  DCHECK(args.length() == 0);
64  Handle<JSObject> holder =
65      isolate->factory()->NewJSObject(isolate->object_function());
66
67  InstallBuiltin(isolate, holder, "pop", Builtins::kArrayPop);
68  if (FLAG_minimal) {
69    InstallBuiltin(isolate, holder, "push", Builtins::kArrayPush);
70  } else {
71    FastArrayPushStub stub(isolate);
72    InstallCode(isolate, holder, "push", stub.GetCode());
73  }
74  InstallBuiltin(isolate, holder, "shift", Builtins::kArrayShift);
75  InstallBuiltin(isolate, holder, "unshift", Builtins::kArrayUnshift);
76  InstallBuiltin(isolate, holder, "slice", Builtins::kArraySlice);
77  InstallBuiltin(isolate, holder, "splice", Builtins::kArraySplice);
78  InstallBuiltin(isolate, holder, "includes", Builtins::kArrayIncludes, 2);
79  InstallBuiltin(isolate, holder, "indexOf", Builtins::kArrayIndexOf, 2);
80  InstallBuiltin(isolate, holder, "keys", Builtins::kArrayPrototypeKeys, 0,
81                 kArrayKeys);
82  InstallBuiltin(isolate, holder, "values", Builtins::kArrayPrototypeValues, 0,
83                 kArrayValues);
84  InstallBuiltin(isolate, holder, "entries", Builtins::kArrayPrototypeEntries,
85                 0, kArrayEntries);
86
87  return *holder;
88}
89
90
91RUNTIME_FUNCTION(Runtime_FixedArrayGet) {
92  SealHandleScope shs(isolate);
93  DCHECK(args.length() == 2);
94  CONVERT_ARG_CHECKED(FixedArray, object, 0);
95  CONVERT_SMI_ARG_CHECKED(index, 1);
96  return object->get(index);
97}
98
99
100RUNTIME_FUNCTION(Runtime_FixedArraySet) {
101  SealHandleScope shs(isolate);
102  DCHECK(args.length() == 3);
103  CONVERT_ARG_CHECKED(FixedArray, object, 0);
104  CONVERT_SMI_ARG_CHECKED(index, 1);
105  CONVERT_ARG_CHECKED(Object, value, 2);
106  object->set(index, value);
107  return isolate->heap()->undefined_value();
108}
109
110
111RUNTIME_FUNCTION(Runtime_TransitionElementsKind) {
112  HandleScope scope(isolate);
113  DCHECK_EQ(2, args.length());
114  CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
115  CONVERT_ARG_HANDLE_CHECKED(Map, to_map, 1);
116  ElementsKind to_kind = to_map->elements_kind();
117  ElementsAccessor::ForKind(to_kind)->TransitionElementsKind(object, to_map);
118  return *object;
119}
120
121
122// Moves all own elements of an object, that are below a limit, to positions
123// starting at zero. All undefined values are placed after non-undefined values,
124// and are followed by non-existing element. Does not change the length
125// property.
126// Returns the number of non-undefined elements collected.
127// Returns -1 if hole removal is not supported by this method.
128RUNTIME_FUNCTION(Runtime_RemoveArrayHoles) {
129  HandleScope scope(isolate);
130  DCHECK(args.length() == 2);
131  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, object, 0);
132  CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[1]);
133  if (object->IsJSProxy()) return Smi::FromInt(-1);
134  return *JSObject::PrepareElementsForSort(Handle<JSObject>::cast(object),
135                                           limit);
136}
137
138
139// Move contents of argument 0 (an array) to argument 1 (an array)
140RUNTIME_FUNCTION(Runtime_MoveArrayContents) {
141  HandleScope scope(isolate);
142  DCHECK(args.length() == 2);
143  CONVERT_ARG_HANDLE_CHECKED(JSArray, from, 0);
144  CONVERT_ARG_HANDLE_CHECKED(JSArray, to, 1);
145  JSObject::ValidateElements(from);
146  JSObject::ValidateElements(to);
147
148  Handle<FixedArrayBase> new_elements(from->elements());
149  ElementsKind from_kind = from->GetElementsKind();
150  Handle<Map> new_map = JSObject::GetElementsTransitionMap(to, from_kind);
151  JSObject::SetMapAndElements(to, new_map, new_elements);
152  to->set_length(from->length());
153
154  JSObject::ResetElements(from);
155  from->set_length(Smi::kZero);
156
157  JSObject::ValidateElements(to);
158  return *to;
159}
160
161
162// How many elements does this object/array have?
163RUNTIME_FUNCTION(Runtime_EstimateNumberOfElements) {
164  HandleScope scope(isolate);
165  DCHECK(args.length() == 1);
166  CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
167  Handle<FixedArrayBase> elements(array->elements(), isolate);
168  SealHandleScope shs(isolate);
169  if (elements->IsDictionary()) {
170    int result =
171        Handle<SeededNumberDictionary>::cast(elements)->NumberOfElements();
172    return Smi::FromInt(result);
173  } else {
174    DCHECK(array->length()->IsSmi());
175    // For packed elements, we know the exact number of elements
176    int length = elements->length();
177    ElementsKind kind = array->GetElementsKind();
178    if (IsFastPackedElementsKind(kind)) {
179      return Smi::FromInt(length);
180    }
181    // For holey elements, take samples from the buffer checking for holes
182    // to generate the estimate.
183    const int kNumberOfHoleCheckSamples = 97;
184    int increment = (length < kNumberOfHoleCheckSamples)
185                        ? 1
186                        : static_cast<int>(length / kNumberOfHoleCheckSamples);
187    ElementsAccessor* accessor = array->GetElementsAccessor();
188    int holes = 0;
189    for (int i = 0; i < length; i += increment) {
190      if (!accessor->HasElement(array, i, elements)) {
191        ++holes;
192      }
193    }
194    int estimate = static_cast<int>((kNumberOfHoleCheckSamples - holes) /
195                                    kNumberOfHoleCheckSamples * length);
196    return Smi::FromInt(estimate);
197  }
198}
199
200
201// Returns an array that tells you where in the [0, length) interval an array
202// might have elements.  Can either return an array of keys (positive integers
203// or undefined) or a number representing the positive length of an interval
204// starting at index 0.
205// Intervals can span over some keys that are not in the object.
206RUNTIME_FUNCTION(Runtime_GetArrayKeys) {
207  HandleScope scope(isolate);
208  DCHECK(args.length() == 2);
209  CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
210  CONVERT_NUMBER_CHECKED(uint32_t, length, Uint32, args[1]);
211  ElementsKind kind = array->GetElementsKind();
212
213  if (IsFastElementsKind(kind) || IsFixedTypedArrayElementsKind(kind)) {
214    uint32_t actual_length = static_cast<uint32_t>(array->elements()->length());
215    return *isolate->factory()->NewNumberFromUint(Min(actual_length, length));
216  }
217
218  if (kind == FAST_STRING_WRAPPER_ELEMENTS) {
219    int string_length =
220        String::cast(Handle<JSValue>::cast(array)->value())->length();
221    int backing_store_length = array->elements()->length();
222    return *isolate->factory()->NewNumberFromUint(
223        Min(length,
224            static_cast<uint32_t>(Max(string_length, backing_store_length))));
225  }
226
227  KeyAccumulator accumulator(isolate, KeyCollectionMode::kOwnOnly,
228                             ALL_PROPERTIES);
229  for (PrototypeIterator iter(isolate, array, kStartAtReceiver);
230       !iter.IsAtEnd(); iter.Advance()) {
231    if (PrototypeIterator::GetCurrent(iter)->IsJSProxy() ||
232        PrototypeIterator::GetCurrent<JSObject>(iter)
233            ->HasIndexedInterceptor()) {
234      // Bail out if we find a proxy or interceptor, likely not worth
235      // collecting keys in that case.
236      return *isolate->factory()->NewNumberFromUint(length);
237    }
238    Handle<JSObject> current = PrototypeIterator::GetCurrent<JSObject>(iter);
239    accumulator.CollectOwnElementIndices(array, current);
240  }
241  // Erase any keys >= length.
242  Handle<FixedArray> keys =
243      accumulator.GetKeys(GetKeysConversion::kKeepNumbers);
244  int j = 0;
245  for (int i = 0; i < keys->length(); i++) {
246    if (NumberToUint32(keys->get(i)) >= length) continue;
247    if (i != j) keys->set(j, keys->get(i));
248    j++;
249  }
250
251  if (j != keys->length()) {
252    isolate->heap()->RightTrimFixedArray<Heap::CONCURRENT_TO_SWEEPER>(
253        *keys, keys->length() - j);
254  }
255
256  return *isolate->factory()->NewJSArrayWithElements(keys);
257}
258
259
260namespace {
261
262Object* ArrayConstructorCommon(Isolate* isolate, Handle<JSFunction> constructor,
263                               Handle<JSReceiver> new_target,
264                               Handle<AllocationSite> site,
265                               Arguments* caller_args) {
266  Factory* factory = isolate->factory();
267
268  // If called through new, new.target can be:
269  // - a subclass of constructor,
270  // - a proxy wrapper around constructor, or
271  // - the constructor itself.
272  // If called through Reflect.construct, it's guaranteed to be a constructor by
273  // REFLECT_CONSTRUCT_PREPARE.
274  DCHECK(new_target->IsConstructor());
275
276  bool holey = false;
277  bool can_use_type_feedback = !site.is_null();
278  bool can_inline_array_constructor = true;
279  if (caller_args->length() == 1) {
280    Handle<Object> argument_one = caller_args->at<Object>(0);
281    if (argument_one->IsSmi()) {
282      int value = Handle<Smi>::cast(argument_one)->value();
283      if (value < 0 ||
284          JSArray::SetLengthWouldNormalize(isolate->heap(), value)) {
285        // the array is a dictionary in this case.
286        can_use_type_feedback = false;
287      } else if (value != 0) {
288        holey = true;
289        if (value >= JSArray::kInitialMaxFastElementArray) {
290          can_inline_array_constructor = false;
291        }
292      }
293    } else {
294      // Non-smi length argument produces a dictionary
295      can_use_type_feedback = false;
296    }
297  }
298
299  Handle<Map> initial_map;
300  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
301      isolate, initial_map,
302      JSFunction::GetDerivedMap(isolate, constructor, new_target));
303
304  ElementsKind to_kind = can_use_type_feedback ? site->GetElementsKind()
305                                               : initial_map->elements_kind();
306  if (holey && !IsFastHoleyElementsKind(to_kind)) {
307    to_kind = GetHoleyElementsKind(to_kind);
308    // Update the allocation site info to reflect the advice alteration.
309    if (!site.is_null()) site->SetElementsKind(to_kind);
310  }
311
312  // We should allocate with an initial map that reflects the allocation site
313  // advice. Therefore we use AllocateJSObjectFromMap instead of passing
314  // the constructor.
315  if (to_kind != initial_map->elements_kind()) {
316    initial_map = Map::AsElementsKind(initial_map, to_kind);
317  }
318
319  // If we don't care to track arrays of to_kind ElementsKind, then
320  // don't emit a memento for them.
321  Handle<AllocationSite> allocation_site;
322  if (AllocationSite::GetMode(to_kind) == TRACK_ALLOCATION_SITE) {
323    allocation_site = site;
324  }
325
326  Handle<JSArray> array = Handle<JSArray>::cast(
327      factory->NewJSObjectFromMap(initial_map, NOT_TENURED, allocation_site));
328
329  factory->NewJSArrayStorage(array, 0, 0, DONT_INITIALIZE_ARRAY_ELEMENTS);
330
331  ElementsKind old_kind = array->GetElementsKind();
332  RETURN_FAILURE_ON_EXCEPTION(
333      isolate, ArrayConstructInitializeElements(array, caller_args));
334  if (!site.is_null() &&
335      (old_kind != array->GetElementsKind() || !can_use_type_feedback ||
336       !can_inline_array_constructor)) {
337    // The arguments passed in caused a transition. This kind of complexity
338    // can't be dealt with in the inlined hydrogen array constructor case.
339    // We must mark the allocationsite as un-inlinable.
340    site->SetDoNotInlineCall();
341  }
342
343  return *array;
344}
345
346}  // namespace
347
348RUNTIME_FUNCTION(Runtime_NewArray) {
349  HandleScope scope(isolate);
350  DCHECK_LE(3, args.length());
351  int const argc = args.length() - 3;
352  // TODO(bmeurer): Remove this Arguments nonsense.
353  Arguments argv(argc, args.arguments() - 1);
354  CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, 0);
355  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, new_target, argc + 1);
356  CONVERT_ARG_HANDLE_CHECKED(HeapObject, type_info, argc + 2);
357  // TODO(bmeurer): Use MaybeHandle to pass around the AllocationSite.
358  Handle<AllocationSite> site = type_info->IsAllocationSite()
359                                    ? Handle<AllocationSite>::cast(type_info)
360                                    : Handle<AllocationSite>::null();
361  return ArrayConstructorCommon(isolate, constructor, new_target, site, &argv);
362}
363
364RUNTIME_FUNCTION(Runtime_NormalizeElements) {
365  HandleScope scope(isolate);
366  DCHECK(args.length() == 1);
367  CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
368  CHECK(!array->HasFixedTypedArrayElements());
369  CHECK(!array->IsJSGlobalProxy());
370  JSObject::NormalizeElements(array);
371  return *array;
372}
373
374
375// GrowArrayElements returns a sentinel Smi if the object was normalized.
376RUNTIME_FUNCTION(Runtime_GrowArrayElements) {
377  HandleScope scope(isolate);
378  DCHECK(args.length() == 2);
379  CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
380  CONVERT_NUMBER_CHECKED(int, key, Int32, args[1]);
381
382  if (key < 0) {
383    return object->elements();
384  }
385
386  uint32_t capacity = static_cast<uint32_t>(object->elements()->length());
387  uint32_t index = static_cast<uint32_t>(key);
388
389  if (index >= capacity) {
390    if (!object->GetElementsAccessor()->GrowCapacity(object, index)) {
391      return Smi::kZero;
392    }
393  }
394
395  // On success, return the fixed array elements.
396  return object->elements();
397}
398
399
400RUNTIME_FUNCTION(Runtime_HasComplexElements) {
401  HandleScope scope(isolate);
402  DCHECK(args.length() == 1);
403  CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
404  for (PrototypeIterator iter(isolate, array, kStartAtReceiver);
405       !iter.IsAtEnd(); iter.Advance()) {
406    if (PrototypeIterator::GetCurrent(iter)->IsJSProxy()) {
407      return isolate->heap()->true_value();
408    }
409    Handle<JSObject> current = PrototypeIterator::GetCurrent<JSObject>(iter);
410    if (current->HasIndexedInterceptor()) {
411      return isolate->heap()->true_value();
412    }
413    if (!current->HasDictionaryElements()) continue;
414    if (current->element_dictionary()->HasComplexElements()) {
415      return isolate->heap()->true_value();
416    }
417  }
418  return isolate->heap()->false_value();
419}
420
421// ES6 22.1.2.2 Array.isArray
422RUNTIME_FUNCTION(Runtime_ArrayIsArray) {
423  HandleScope shs(isolate);
424  DCHECK(args.length() == 1);
425  CONVERT_ARG_HANDLE_CHECKED(Object, object, 0);
426  Maybe<bool> result = Object::IsArray(object);
427  MAYBE_RETURN(result, isolate->heap()->exception());
428  return isolate->heap()->ToBoolean(result.FromJust());
429}
430
431RUNTIME_FUNCTION(Runtime_IsArray) {
432  SealHandleScope shs(isolate);
433  DCHECK(args.length() == 1);
434  CONVERT_ARG_CHECKED(Object, obj, 0);
435  return isolate->heap()->ToBoolean(obj->IsJSArray());
436}
437
438RUNTIME_FUNCTION(Runtime_ArraySpeciesConstructor) {
439  HandleScope scope(isolate);
440  DCHECK(args.length() == 1);
441  CONVERT_ARG_HANDLE_CHECKED(Object, original_array, 0);
442  RETURN_RESULT_OR_FAILURE(
443      isolate, Object::ArraySpeciesConstructor(isolate, original_array));
444}
445
446// ES7 22.1.3.11 Array.prototype.includes
447RUNTIME_FUNCTION(Runtime_ArrayIncludes_Slow) {
448  HandleScope shs(isolate);
449  DCHECK(args.length() == 3);
450  CONVERT_ARG_HANDLE_CHECKED(Object, search_element, 1);
451  CONVERT_ARG_HANDLE_CHECKED(Object, from_index, 2);
452
453  // Let O be ? ToObject(this value).
454  Handle<JSReceiver> object;
455  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
456      isolate, object, Object::ToObject(isolate, handle(args[0], isolate)));
457
458  // Let len be ? ToLength(? Get(O, "length")).
459  int64_t len;
460  {
461    if (object->map()->instance_type() == JS_ARRAY_TYPE) {
462      uint32_t len32 = 0;
463      bool success = JSArray::cast(*object)->length()->ToArrayLength(&len32);
464      DCHECK(success);
465      USE(success);
466      len = len32;
467    } else {
468      Handle<Object> len_;
469      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
470          isolate, len_,
471          Object::GetProperty(object, isolate->factory()->length_string()));
472
473      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, len_,
474                                         Object::ToLength(isolate, len_));
475      len = static_cast<int64_t>(len_->Number());
476      DCHECK_EQ(len, len_->Number());
477    }
478  }
479
480  if (len == 0) return isolate->heap()->false_value();
481
482  // Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step
483  // produces the value 0.)
484  int64_t start_from;
485  {
486    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, from_index,
487                                       Object::ToInteger(isolate, from_index));
488    double fp = from_index->Number();
489    if (fp > len) return isolate->heap()->false_value();
490    start_from = static_cast<int64_t>(fp);
491  }
492
493  int64_t index;
494  if (start_from >= 0) {
495    index = start_from;
496  } else {
497    index = len + start_from;
498    if (index < 0) {
499      index = 0;
500    }
501  }
502
503  // If the receiver is not a special receiver type, and the length is a valid
504  // element index, perform fast operation tailored to specific ElementsKinds.
505  if (object->map()->instance_type() > LAST_SPECIAL_RECEIVER_TYPE &&
506      len < kMaxUInt32 &&
507      JSObject::PrototypeHasNoElements(isolate, JSObject::cast(*object))) {
508    Handle<JSObject> obj = Handle<JSObject>::cast(object);
509    ElementsAccessor* elements = obj->GetElementsAccessor();
510    Maybe<bool> result = elements->IncludesValue(isolate, obj, search_element,
511                                                 static_cast<uint32_t>(index),
512                                                 static_cast<uint32_t>(len));
513    MAYBE_RETURN(result, isolate->heap()->exception());
514    return *isolate->factory()->ToBoolean(result.FromJust());
515  }
516
517  // Otherwise, perform slow lookups for special receiver types
518  for (; index < len; ++index) {
519    // Let elementK be the result of ? Get(O, ! ToString(k)).
520    Handle<Object> element_k;
521    {
522      Handle<Object> index_obj = isolate->factory()->NewNumberFromInt64(index);
523      bool success;
524      LookupIterator it = LookupIterator::PropertyOrElement(
525          isolate, object, index_obj, &success);
526      DCHECK(success);
527      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, element_k,
528                                         Object::GetProperty(&it));
529    }
530
531    // If SameValueZero(searchElement, elementK) is true, return true.
532    if (search_element->SameValueZero(*element_k)) {
533      return isolate->heap()->true_value();
534    }
535  }
536  return isolate->heap()->false_value();
537}
538
539RUNTIME_FUNCTION(Runtime_ArrayIndexOf) {
540  HandleScope shs(isolate);
541  DCHECK(args.length() == 3);
542  CONVERT_ARG_HANDLE_CHECKED(Object, search_element, 1);
543  CONVERT_ARG_HANDLE_CHECKED(Object, from_index, 2);
544
545  // Let O be ? ToObject(this value).
546  Handle<Object> receiver_obj = args.at<Object>(0);
547  if (receiver_obj->IsNull(isolate) || receiver_obj->IsUndefined(isolate)) {
548    THROW_NEW_ERROR_RETURN_FAILURE(
549        isolate, NewTypeError(MessageTemplate::kCalledOnNullOrUndefined,
550                              isolate->factory()->NewStringFromAsciiChecked(
551                                  "Array.prototype.indexOf")));
552  }
553  Handle<JSReceiver> object;
554  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
555      isolate, object, Object::ToObject(isolate, args.at<Object>(0)));
556
557  // Let len be ? ToLength(? Get(O, "length")).
558  int64_t len;
559  {
560    if (object->IsJSArray()) {
561      uint32_t len32 = 0;
562      bool success = JSArray::cast(*object)->length()->ToArrayLength(&len32);
563      DCHECK(success);
564      USE(success);
565      len = len32;
566    } else {
567      Handle<Object> len_;
568      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
569          isolate, len_,
570          Object::GetProperty(object, isolate->factory()->length_string()));
571
572      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, len_,
573                                         Object::ToLength(isolate, len_));
574      len = static_cast<int64_t>(len_->Number());
575      DCHECK_EQ(len, len_->Number());
576    }
577  }
578
579  if (len == 0) return Smi::FromInt(-1);
580
581  // Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step
582  // produces the value 0.)
583  int64_t start_from;
584  {
585    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, from_index,
586                                       Object::ToInteger(isolate, from_index));
587    double fp = from_index->Number();
588    if (fp > len) return Smi::FromInt(-1);
589    start_from = static_cast<int64_t>(fp);
590  }
591
592  int64_t index;
593  if (start_from >= 0) {
594    index = start_from;
595  } else {
596    index = len + start_from;
597    if (index < 0) {
598      index = 0;
599    }
600  }
601
602  // If the receiver is not a special receiver type, and the length is a valid
603  // element index, perform fast operation tailored to specific ElementsKinds.
604  if (object->map()->instance_type() > LAST_SPECIAL_RECEIVER_TYPE &&
605      len < kMaxUInt32 &&
606      JSObject::PrototypeHasNoElements(isolate, JSObject::cast(*object))) {
607    Handle<JSObject> obj = Handle<JSObject>::cast(object);
608    ElementsAccessor* elements = obj->GetElementsAccessor();
609    Maybe<int64_t> result = elements->IndexOfValue(isolate, obj, search_element,
610                                                   static_cast<uint32_t>(index),
611                                                   static_cast<uint32_t>(len));
612    MAYBE_RETURN(result, isolate->heap()->exception());
613    return *isolate->factory()->NewNumberFromInt64(result.FromJust());
614  }
615
616  // Otherwise, perform slow lookups for special receiver types
617  for (; index < len; ++index) {
618    // Let elementK be the result of ? Get(O, ! ToString(k)).
619    Handle<Object> element_k;
620    {
621      Handle<Object> index_obj = isolate->factory()->NewNumberFromInt64(index);
622      bool success;
623      LookupIterator it = LookupIterator::PropertyOrElement(
624          isolate, object, index_obj, &success);
625      DCHECK(success);
626      if (!JSReceiver::HasProperty(&it).FromJust()) {
627        continue;
628      }
629      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, element_k,
630                                         Object::GetProperty(&it));
631      if (search_element->StrictEquals(*element_k)) {
632        return *index_obj;
633      }
634    }
635  }
636  return Smi::FromInt(-1);
637}
638
639RUNTIME_FUNCTION(Runtime_SpreadIterablePrepare) {
640  HandleScope scope(isolate);
641  DCHECK_EQ(1, args.length());
642  CONVERT_ARG_HANDLE_CHECKED(Object, spread, 0);
643
644  if (spread->IsJSArray()) {
645    // Check that the spread arg has fast elements
646    Handle<JSArray> spread_array = Handle<JSArray>::cast(spread);
647    ElementsKind array_kind = spread_array->GetElementsKind();
648
649    // And that it has the orignal ArrayPrototype
650    JSObject* array_proto = JSObject::cast(spread_array->map()->prototype());
651    Map* iterator_map = isolate->initial_array_iterator_prototype()->map();
652
653    // Check that the iterator acts as expected.
654    // If IsArrayIteratorLookupChainIntact(), then we know that the initial
655    // ArrayIterator is being used. If the map of the prototype has changed,
656    // then take the slow path.
657
658    if (isolate->is_initial_array_prototype(array_proto) &&
659        isolate->IsArrayIteratorLookupChainIntact() &&
660        isolate->is_initial_array_iterator_prototype_map(iterator_map)) {
661      if (IsFastPackedElementsKind(array_kind)) {
662        return *spread;
663      }
664      if (IsFastHoleyElementsKind(array_kind) &&
665          isolate->IsFastArrayConstructorPrototypeChainIntact()) {
666        return *spread;
667      }
668    }
669  }
670
671  Handle<JSFunction> spread_iterable_function = isolate->spread_iterable();
672
673  Handle<Object> spreaded;
674  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
675      isolate, spreaded,
676      Execution::Call(isolate, spread_iterable_function,
677                      isolate->factory()->undefined_value(), 1, &spread));
678
679  return *spreaded;
680}
681
682}  // namespace internal
683}  // namespace v8
684