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/conversions-inl.h"
9#include "src/elements.h"
10#include "src/factory.h"
11#include "src/isolate-inl.h"
12#include "src/key-accumulator.h"
13#include "src/messages.h"
14#include "src/prototype.h"
15
16namespace v8 {
17namespace internal {
18
19RUNTIME_FUNCTION(Runtime_FinishArrayPrototypeSetup) {
20  HandleScope scope(isolate);
21  DCHECK(args.length() == 1);
22  CONVERT_ARG_HANDLE_CHECKED(JSArray, prototype, 0);
23  Object* length = prototype->length();
24  RUNTIME_ASSERT(length->IsSmi() && Smi::cast(length)->value() == 0);
25  RUNTIME_ASSERT(prototype->HasFastSmiOrObjectElements());
26  // This is necessary to enable fast checks for absence of elements
27  // on Array.prototype and below.
28  prototype->set_elements(isolate->heap()->empty_fixed_array());
29  return Smi::FromInt(0);
30}
31
32
33static void InstallBuiltin(Isolate* isolate, Handle<JSObject> holder,
34                           const char* name, Builtins::Name builtin_name) {
35  Handle<String> key = isolate->factory()->InternalizeUtf8String(name);
36  Handle<Code> code(isolate->builtins()->builtin(builtin_name));
37  Handle<JSFunction> optimized =
38      isolate->factory()->NewFunctionWithoutPrototype(key, code);
39  optimized->shared()->DontAdaptArguments();
40  JSObject::AddProperty(holder, key, optimized, NONE);
41}
42
43
44RUNTIME_FUNCTION(Runtime_SpecialArrayFunctions) {
45  HandleScope scope(isolate);
46  DCHECK(args.length() == 0);
47  Handle<JSObject> holder =
48      isolate->factory()->NewJSObject(isolate->object_function());
49
50  InstallBuiltin(isolate, holder, "pop", Builtins::kArrayPop);
51  InstallBuiltin(isolate, holder, "push", Builtins::kArrayPush);
52  InstallBuiltin(isolate, holder, "shift", Builtins::kArrayShift);
53  InstallBuiltin(isolate, holder, "unshift", Builtins::kArrayUnshift);
54  InstallBuiltin(isolate, holder, "slice", Builtins::kArraySlice);
55  InstallBuiltin(isolate, holder, "splice", Builtins::kArraySplice);
56
57  return *holder;
58}
59
60
61RUNTIME_FUNCTION(Runtime_FixedArrayGet) {
62  SealHandleScope shs(isolate);
63  DCHECK(args.length() == 2);
64  CONVERT_ARG_CHECKED(FixedArray, object, 0);
65  CONVERT_SMI_ARG_CHECKED(index, 1);
66  return object->get(index);
67}
68
69
70RUNTIME_FUNCTION(Runtime_FixedArraySet) {
71  SealHandleScope shs(isolate);
72  DCHECK(args.length() == 3);
73  CONVERT_ARG_CHECKED(FixedArray, object, 0);
74  CONVERT_SMI_ARG_CHECKED(index, 1);
75  CONVERT_ARG_CHECKED(Object, value, 2);
76  object->set(index, value);
77  return isolate->heap()->undefined_value();
78}
79
80
81RUNTIME_FUNCTION(Runtime_TransitionElementsKind) {
82  HandleScope scope(isolate);
83  RUNTIME_ASSERT(args.length() == 2);
84  CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
85  CONVERT_ARG_HANDLE_CHECKED(Map, map, 1);
86  JSObject::TransitionElementsKind(array, map->elements_kind());
87  return *array;
88}
89
90
91// Push an object unto an array of objects if it is not already in the
92// array.  Returns true if the element was pushed on the stack and
93// false otherwise.
94RUNTIME_FUNCTION(Runtime_PushIfAbsent) {
95  HandleScope scope(isolate);
96  DCHECK(args.length() == 2);
97  CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
98  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, element, 1);
99  RUNTIME_ASSERT(array->HasFastSmiOrObjectElements());
100  int length = Smi::cast(array->length())->value();
101  FixedArray* elements = FixedArray::cast(array->elements());
102  for (int i = 0; i < length; i++) {
103    if (elements->get(i) == *element) return isolate->heap()->false_value();
104  }
105
106  // Strict not needed. Used for cycle detection in Array join implementation.
107  RETURN_FAILURE_ON_EXCEPTION(
108      isolate, JSObject::AddDataElement(array, length, element, NONE));
109  JSObject::ValidateElements(array);
110  return isolate->heap()->true_value();
111}
112
113
114// Moves all own elements of an object, that are below a limit, to positions
115// starting at zero. All undefined values are placed after non-undefined values,
116// and are followed by non-existing element. Does not change the length
117// property.
118// Returns the number of non-undefined elements collected.
119// Returns -1 if hole removal is not supported by this method.
120RUNTIME_FUNCTION(Runtime_RemoveArrayHoles) {
121  HandleScope scope(isolate);
122  DCHECK(args.length() == 2);
123  CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
124  CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[1]);
125  return *JSObject::PrepareElementsForSort(object, limit);
126}
127
128
129// Move contents of argument 0 (an array) to argument 1 (an array)
130RUNTIME_FUNCTION(Runtime_MoveArrayContents) {
131  HandleScope scope(isolate);
132  DCHECK(args.length() == 2);
133  CONVERT_ARG_HANDLE_CHECKED(JSArray, from, 0);
134  CONVERT_ARG_HANDLE_CHECKED(JSArray, to, 1);
135  JSObject::ValidateElements(from);
136  JSObject::ValidateElements(to);
137
138  Handle<FixedArrayBase> new_elements(from->elements());
139  ElementsKind from_kind = from->GetElementsKind();
140  Handle<Map> new_map = JSObject::GetElementsTransitionMap(to, from_kind);
141  JSObject::SetMapAndElements(to, new_map, new_elements);
142  to->set_length(from->length());
143
144  JSObject::ResetElements(from);
145  from->set_length(Smi::FromInt(0));
146
147  JSObject::ValidateElements(to);
148  return *to;
149}
150
151
152// How many elements does this object/array have?
153RUNTIME_FUNCTION(Runtime_EstimateNumberOfElements) {
154  HandleScope scope(isolate);
155  DCHECK(args.length() == 1);
156  CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
157  Handle<FixedArrayBase> elements(array->elements(), isolate);
158  SealHandleScope shs(isolate);
159  if (elements->IsDictionary()) {
160    int result =
161        Handle<SeededNumberDictionary>::cast(elements)->NumberOfElements();
162    return Smi::FromInt(result);
163  } else {
164    DCHECK(array->length()->IsSmi());
165    // For packed elements, we know the exact number of elements
166    int length = elements->length();
167    ElementsKind kind = array->GetElementsKind();
168    if (IsFastPackedElementsKind(kind)) {
169      return Smi::FromInt(length);
170    }
171    // For holey elements, take samples from the buffer checking for holes
172    // to generate the estimate.
173    const int kNumberOfHoleCheckSamples = 97;
174    int increment = (length < kNumberOfHoleCheckSamples)
175                        ? 1
176                        : static_cast<int>(length / kNumberOfHoleCheckSamples);
177    ElementsAccessor* accessor = array->GetElementsAccessor();
178    int holes = 0;
179    for (int i = 0; i < length; i += increment) {
180      if (!accessor->HasElement(array, i, elements)) {
181        ++holes;
182      }
183    }
184    int estimate = static_cast<int>((kNumberOfHoleCheckSamples - holes) /
185                                    kNumberOfHoleCheckSamples * length);
186    return Smi::FromInt(estimate);
187  }
188}
189
190
191// Returns an array that tells you where in the [0, length) interval an array
192// might have elements.  Can either return an array of keys (positive integers
193// or undefined) or a number representing the positive length of an interval
194// starting at index 0.
195// Intervals can span over some keys that are not in the object.
196RUNTIME_FUNCTION(Runtime_GetArrayKeys) {
197  HandleScope scope(isolate);
198  DCHECK(args.length() == 2);
199  CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
200  CONVERT_NUMBER_CHECKED(uint32_t, length, Uint32, args[1]);
201
202  if (!array->elements()->IsDictionary()) {
203    RUNTIME_ASSERT(array->HasFastSmiOrObjectElements() ||
204                   array->HasFastDoubleElements());
205    uint32_t actual_length = static_cast<uint32_t>(array->elements()->length());
206    return *isolate->factory()->NewNumberFromUint(Min(actual_length, length));
207  }
208
209  KeyAccumulator accumulator(isolate, ALL_PROPERTIES);
210  // No need to separate protoype levels since we only get numbers/element keys
211  for (PrototypeIterator iter(isolate, array,
212                              PrototypeIterator::START_AT_RECEIVER);
213       !iter.IsAtEnd(); iter.Advance()) {
214    if (PrototypeIterator::GetCurrent(iter)->IsJSProxy() ||
215        PrototypeIterator::GetCurrent<JSObject>(iter)
216            ->HasIndexedInterceptor()) {
217      // Bail out if we find a proxy or interceptor, likely not worth
218      // collecting keys in that case.
219      return *isolate->factory()->NewNumberFromUint(length);
220    }
221    accumulator.NextPrototype();
222    Handle<JSObject> current = PrototypeIterator::GetCurrent<JSObject>(iter);
223    JSObject::CollectOwnElementKeys(current, &accumulator, ALL_PROPERTIES);
224  }
225  // Erase any keys >= length.
226  // TODO(adamk): Remove this step when the contract of %GetArrayKeys
227  // is changed to let this happen on the JS side.
228  Handle<FixedArray> keys = accumulator.GetKeys(KEEP_NUMBERS);
229  for (int i = 0; i < keys->length(); i++) {
230    if (NumberToUint32(keys->get(i)) >= length) keys->set_undefined(i);
231  }
232  return *isolate->factory()->NewJSArrayWithElements(keys);
233}
234
235
236namespace {
237
238Object* ArrayConstructorCommon(Isolate* isolate, Handle<JSFunction> constructor,
239                               Handle<JSReceiver> new_target,
240                               Handle<AllocationSite> site,
241                               Arguments* caller_args) {
242  Factory* factory = isolate->factory();
243
244  // If called through new, new.target can be:
245  // - a subclass of constructor,
246  // - a proxy wrapper around constructor, or
247  // - the constructor itself.
248  // If called through Reflect.construct, it's guaranteed to be a constructor by
249  // REFLECT_CONSTRUCT_PREPARE.
250  DCHECK(new_target->IsConstructor());
251
252  bool holey = false;
253  bool can_use_type_feedback = !site.is_null();
254  bool can_inline_array_constructor = true;
255  if (caller_args->length() == 1) {
256    Handle<Object> argument_one = caller_args->at<Object>(0);
257    if (argument_one->IsSmi()) {
258      int value = Handle<Smi>::cast(argument_one)->value();
259      if (value < 0 ||
260          JSArray::SetLengthWouldNormalize(isolate->heap(), value)) {
261        // the array is a dictionary in this case.
262        can_use_type_feedback = false;
263      } else if (value != 0) {
264        holey = true;
265        if (value >= JSArray::kInitialMaxFastElementArray) {
266          can_inline_array_constructor = false;
267        }
268      }
269    } else {
270      // Non-smi length argument produces a dictionary
271      can_use_type_feedback = false;
272    }
273  }
274
275  Handle<Map> initial_map;
276  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
277      isolate, initial_map,
278      JSFunction::GetDerivedMap(isolate, constructor, new_target));
279
280  ElementsKind to_kind = can_use_type_feedback ? site->GetElementsKind()
281                                               : initial_map->elements_kind();
282  if (holey && !IsFastHoleyElementsKind(to_kind)) {
283    to_kind = GetHoleyElementsKind(to_kind);
284    // Update the allocation site info to reflect the advice alteration.
285    if (!site.is_null()) site->SetElementsKind(to_kind);
286  }
287
288  // We should allocate with an initial map that reflects the allocation site
289  // advice. Therefore we use AllocateJSObjectFromMap instead of passing
290  // the constructor.
291  if (to_kind != initial_map->elements_kind()) {
292    initial_map = Map::AsElementsKind(initial_map, to_kind);
293  }
294
295  // If we don't care to track arrays of to_kind ElementsKind, then
296  // don't emit a memento for them.
297  Handle<AllocationSite> allocation_site;
298  if (AllocationSite::GetMode(to_kind) == TRACK_ALLOCATION_SITE) {
299    allocation_site = site;
300  }
301
302  Handle<JSArray> array = Handle<JSArray>::cast(
303      factory->NewJSObjectFromMap(initial_map, NOT_TENURED, allocation_site));
304
305  factory->NewJSArrayStorage(array, 0, 0, DONT_INITIALIZE_ARRAY_ELEMENTS);
306
307  ElementsKind old_kind = array->GetElementsKind();
308  RETURN_FAILURE_ON_EXCEPTION(
309      isolate, ArrayConstructInitializeElements(array, caller_args));
310  if (!site.is_null() &&
311      (old_kind != array->GetElementsKind() || !can_use_type_feedback ||
312       !can_inline_array_constructor)) {
313    // The arguments passed in caused a transition. This kind of complexity
314    // can't be dealt with in the inlined hydrogen array constructor case.
315    // We must mark the allocationsite as un-inlinable.
316    site->SetDoNotInlineCall();
317  }
318
319  return *array;
320}
321
322}  // namespace
323
324
325RUNTIME_FUNCTION(Runtime_NewArray) {
326  HandleScope scope(isolate);
327  DCHECK_LE(3, args.length());
328  int const argc = args.length() - 3;
329  // TODO(bmeurer): Remove this Arguments nonsense.
330  Arguments argv(argc, args.arguments() - 1);
331  CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, 0);
332  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, new_target, argc + 1);
333  CONVERT_ARG_HANDLE_CHECKED(HeapObject, type_info, argc + 2);
334  // TODO(bmeurer): Use MaybeHandle to pass around the AllocationSite.
335  Handle<AllocationSite> site = type_info->IsAllocationSite()
336                                    ? Handle<AllocationSite>::cast(type_info)
337                                    : Handle<AllocationSite>::null();
338  return ArrayConstructorCommon(isolate, constructor, new_target, site, &argv);
339}
340
341
342RUNTIME_FUNCTION(Runtime_ArrayConstructor) {
343  HandleScope scope(isolate);
344  // If we get 2 arguments then they are the stub parameters (constructor, type
345  // info).  If we get 4, then the first one is a pointer to the arguments
346  // passed by the caller, and the last one is the length of the arguments
347  // passed to the caller (redundant, but useful to check on the deoptimizer
348  // with an assert).
349  Arguments empty_args(0, NULL);
350  bool no_caller_args = args.length() == 2;
351  DCHECK(no_caller_args || args.length() == 4);
352  int parameters_start = no_caller_args ? 0 : 1;
353  Arguments* caller_args =
354      no_caller_args ? &empty_args : reinterpret_cast<Arguments*>(args[0]);
355  CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, parameters_start);
356  CONVERT_ARG_HANDLE_CHECKED(Object, type_info, parameters_start + 1);
357#ifdef DEBUG
358  if (!no_caller_args) {
359    CONVERT_SMI_ARG_CHECKED(arg_count, parameters_start + 2);
360    DCHECK(arg_count == caller_args->length());
361  }
362#endif
363
364  Handle<AllocationSite> site;
365  if (!type_info.is_null() &&
366      *type_info != isolate->heap()->undefined_value()) {
367    site = Handle<AllocationSite>::cast(type_info);
368    DCHECK(!site->SitePointsToLiteral());
369  }
370
371  return ArrayConstructorCommon(isolate, constructor, constructor, site,
372                                caller_args);
373}
374
375
376RUNTIME_FUNCTION(Runtime_InternalArrayConstructor) {
377  HandleScope scope(isolate);
378  Arguments empty_args(0, NULL);
379  bool no_caller_args = args.length() == 1;
380  DCHECK(no_caller_args || args.length() == 3);
381  int parameters_start = no_caller_args ? 0 : 1;
382  Arguments* caller_args =
383      no_caller_args ? &empty_args : reinterpret_cast<Arguments*>(args[0]);
384  CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, parameters_start);
385#ifdef DEBUG
386  if (!no_caller_args) {
387    CONVERT_SMI_ARG_CHECKED(arg_count, parameters_start + 1);
388    DCHECK(arg_count == caller_args->length());
389  }
390#endif
391  return ArrayConstructorCommon(isolate, constructor, constructor,
392                                Handle<AllocationSite>::null(), caller_args);
393}
394
395
396RUNTIME_FUNCTION(Runtime_NormalizeElements) {
397  HandleScope scope(isolate);
398  DCHECK(args.length() == 1);
399  CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
400  RUNTIME_ASSERT(!array->HasFixedTypedArrayElements() &&
401                 !array->IsJSGlobalProxy());
402  JSObject::NormalizeElements(array);
403  return *array;
404}
405
406
407// GrowArrayElements returns a sentinel Smi if the object was normalized.
408RUNTIME_FUNCTION(Runtime_GrowArrayElements) {
409  HandleScope scope(isolate);
410  DCHECK(args.length() == 2);
411  CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
412  CONVERT_NUMBER_CHECKED(int, key, Int32, args[1]);
413
414  if (key < 0) {
415    return object->elements();
416  }
417
418  uint32_t capacity = static_cast<uint32_t>(object->elements()->length());
419  uint32_t index = static_cast<uint32_t>(key);
420
421  if (index >= capacity) {
422    if (object->WouldConvertToSlowElements(index)) {
423      // We don't want to allow operations that cause lazy deopt. Return a Smi
424      // as a signal that optimized code should eagerly deoptimize.
425      return Smi::FromInt(0);
426    }
427
428    uint32_t new_capacity = JSObject::NewElementsCapacity(index + 1);
429    object->GetElementsAccessor()->GrowCapacityAndConvert(object, new_capacity);
430  }
431
432  // On success, return the fixed array elements.
433  return object->elements();
434}
435
436
437RUNTIME_FUNCTION(Runtime_HasComplexElements) {
438  HandleScope scope(isolate);
439  DCHECK(args.length() == 1);
440  CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
441  for (PrototypeIterator iter(isolate, array,
442                              PrototypeIterator::START_AT_RECEIVER);
443       !iter.IsAtEnd(); iter.Advance()) {
444    if (PrototypeIterator::GetCurrent(iter)->IsJSProxy()) {
445      return isolate->heap()->true_value();
446    }
447    Handle<JSObject> current = PrototypeIterator::GetCurrent<JSObject>(iter);
448    if (current->HasIndexedInterceptor()) {
449      return isolate->heap()->true_value();
450    }
451    if (!current->HasDictionaryElements()) continue;
452    if (current->element_dictionary()->HasComplexElements()) {
453      return isolate->heap()->true_value();
454    }
455  }
456  return isolate->heap()->false_value();
457}
458
459
460RUNTIME_FUNCTION(Runtime_IsArray) {
461  SealHandleScope shs(isolate);
462  DCHECK(args.length() == 1);
463  CONVERT_ARG_CHECKED(Object, obj, 0);
464  return isolate->heap()->ToBoolean(obj->IsJSArray());
465}
466
467
468RUNTIME_FUNCTION(Runtime_HasCachedArrayIndex) {
469  SealHandleScope shs(isolate);
470  DCHECK(args.length() == 1);
471  return isolate->heap()->false_value();
472}
473
474
475RUNTIME_FUNCTION(Runtime_GetCachedArrayIndex) {
476  // This can never be reached, because Runtime_HasCachedArrayIndex always
477  // returns false.
478  UNIMPLEMENTED();
479  return nullptr;
480}
481
482
483RUNTIME_FUNCTION(Runtime_FastOneByteArrayJoin) {
484  SealHandleScope shs(isolate);
485  DCHECK(args.length() == 2);
486  // Returning undefined means that this fast path fails and one has to resort
487  // to a slow path.
488  return isolate->heap()->undefined_value();
489}
490
491
492RUNTIME_FUNCTION(Runtime_ArraySpeciesConstructor) {
493  HandleScope scope(isolate);
494  DCHECK(args.length() == 1);
495  CONVERT_ARG_HANDLE_CHECKED(Object, original_array, 0);
496  Handle<Object> constructor;
497  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
498      isolate, constructor,
499      Object::ArraySpeciesConstructor(isolate, original_array));
500  return *constructor;
501}
502
503}  // namespace internal
504}  // namespace v8
505