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/debug/debug.h"
6#include "src/execution/arguments-inl.h"
7#include "src/execution/isolate-inl.h"
8#include "src/execution/protectors-inl.h"
9#include "src/heap/factory.h"
10#include "src/heap/heap-inl.h"  // For ToBoolean. TODO(jkummerow): Drop.
11#include "src/heap/heap-write-barrier-inl.h"
12#include "src/logging/counters.h"
13#include "src/numbers/conversions-inl.h"
14#include "src/objects/allocation-site-inl.h"
15#include "src/objects/arguments-inl.h"
16#include "src/objects/elements.h"
17#include "src/objects/hash-table-inl.h"
18#include "src/objects/js-array-inl.h"
19#include "src/objects/prototype.h"
20#include "src/runtime/runtime-utils.h"
21
22namespace v8 {
23namespace internal {
24
25RUNTIME_FUNCTION(Runtime_TransitionElementsKind) {
26  HandleScope scope(isolate);
27  DCHECK_EQ(2, args.length());
28  Handle<JSObject> object = args.at<JSObject>(0);
29  Handle<Map> to_map = args.at<Map>(1);
30  ElementsKind to_kind = to_map->elements_kind();
31  if (ElementsAccessor::ForKind(to_kind)
32          ->TransitionElementsKind(object, to_map)
33          .IsNothing()) {
34    // TODO(victorgomes): EffectControlLinearizer::LowerTransitionElementsKind
35    // does not handle exceptions.
36    FATAL(
37        "Fatal JavaScript invalid size error when transitioning elements kind");
38    UNREACHABLE();
39  }
40  return *object;
41}
42
43RUNTIME_FUNCTION(Runtime_TransitionElementsKindWithKind) {
44  HandleScope scope(isolate);
45  DCHECK_EQ(2, args.length());
46  Handle<JSObject> object = args.at<JSObject>(0);
47  ElementsKind to_kind = static_cast<ElementsKind>(args.smi_value_at(1));
48  JSObject::TransitionElementsKind(object, to_kind);
49  return *object;
50}
51
52RUNTIME_FUNCTION(Runtime_NewArray) {
53  HandleScope scope(isolate);
54  DCHECK_LE(3, args.length());
55  int const argc = args.length() - 3;
56  // argv points to the arguments constructed by the JavaScript call.
57  JavaScriptArguments argv(argc, args.address_of_arg_at(0));
58  Handle<JSFunction> constructor = args.at<JSFunction>(argc);
59  Handle<JSReceiver> new_target = args.at<JSReceiver>(argc + 1);
60  Handle<HeapObject> type_info = args.at<HeapObject>(argc + 2);
61  // TODO(bmeurer): Use MaybeHandle to pass around the AllocationSite.
62  Handle<AllocationSite> site = type_info->IsAllocationSite()
63                                    ? Handle<AllocationSite>::cast(type_info)
64                                    : Handle<AllocationSite>::null();
65
66  Factory* factory = isolate->factory();
67
68  // If called through new, new.target can be:
69  // - a subclass of constructor,
70  // - a proxy wrapper around constructor, or
71  // - the constructor itself.
72  // If called through Reflect.construct, it's guaranteed to be a constructor by
73  // REFLECT_CONSTRUCT_PREPARE.
74  DCHECK(new_target->IsConstructor());
75
76  bool holey = false;
77  bool can_use_type_feedback = !site.is_null();
78  bool can_inline_array_constructor = true;
79  if (argv.length() == 1) {
80    Handle<Object> argument_one = argv.at<Object>(0);
81    if (argument_one->IsSmi()) {
82      int value = Handle<Smi>::cast(argument_one)->value();
83      if (value < 0 ||
84          JSArray::SetLengthWouldNormalize(isolate->heap(), value)) {
85        // the array is a dictionary in this case.
86        can_use_type_feedback = false;
87      } else if (value != 0) {
88        holey = true;
89        if (value >= JSArray::kInitialMaxFastElementArray) {
90          can_inline_array_constructor = false;
91        }
92      }
93    } else {
94      // Non-smi length argument produces a dictionary
95      can_use_type_feedback = false;
96    }
97  }
98
99  Handle<Map> initial_map;
100  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
101      isolate, initial_map,
102      JSFunction::GetDerivedMap(isolate, constructor, new_target));
103
104  ElementsKind to_kind = can_use_type_feedback ? site->GetElementsKind()
105                                               : initial_map->elements_kind();
106  if (holey && !IsHoleyElementsKind(to_kind)) {
107    to_kind = GetHoleyElementsKind(to_kind);
108    // Update the allocation site info to reflect the advice alteration.
109    if (!site.is_null()) site->SetElementsKind(to_kind);
110  }
111
112  // We should allocate with an initial map that reflects the allocation site
113  // advice. Therefore we use AllocateJSObjectFromMap instead of passing
114  // the constructor.
115  initial_map = Map::AsElementsKind(isolate, initial_map, to_kind);
116
117  // If we don't care to track arrays of to_kind ElementsKind, then
118  // don't emit a memento for them.
119  Handle<AllocationSite> allocation_site;
120  if (AllocationSite::ShouldTrack(to_kind)) {
121    allocation_site = site;
122  }
123
124  Handle<JSArray> array = Handle<JSArray>::cast(factory->NewJSObjectFromMap(
125      initial_map, AllocationType::kYoung, allocation_site));
126
127  factory->NewJSArrayStorage(array, 0, 0, DONT_INITIALIZE_ARRAY_ELEMENTS);
128
129  ElementsKind old_kind = array->GetElementsKind();
130  RETURN_FAILURE_ON_EXCEPTION(isolate,
131                              ArrayConstructInitializeElements(array, &argv));
132  if (!site.is_null()) {
133    if ((old_kind != array->GetElementsKind() || !can_use_type_feedback ||
134         !can_inline_array_constructor)) {
135      // The arguments passed in caused a transition. This kind of complexity
136      // can't be dealt with in the inlined optimized array constructor case.
137      // We must mark the allocationsite as un-inlinable.
138      site->SetDoNotInlineCall();
139    }
140  } else {
141    if (old_kind != array->GetElementsKind() || !can_inline_array_constructor) {
142      // We don't have an AllocationSite for this Array constructor invocation,
143      // i.e. it might a call from Array#map or from an Array subclass, so we
144      // just flip the bit on the global protector cell instead.
145      // TODO(bmeurer): Find a better way to mark this. Global protectors
146      // tend to back-fire over time...
147      if (Protectors::IsArrayConstructorIntact(isolate)) {
148        Protectors::InvalidateArrayConstructor(isolate);
149      }
150    }
151  }
152
153  return *array;
154}
155
156RUNTIME_FUNCTION(Runtime_NormalizeElements) {
157  HandleScope scope(isolate);
158  DCHECK_EQ(1, args.length());
159  Handle<JSObject> array = args.at<JSObject>(0);
160  CHECK(!array->HasTypedArrayOrRabGsabTypedArrayElements());
161  CHECK(!array->IsJSGlobalProxy());
162  JSObject::NormalizeElements(array);
163  return *array;
164}
165
166// GrowArrayElements returns a sentinel Smi if the object was normalized or if
167// the key is negative.
168RUNTIME_FUNCTION(Runtime_GrowArrayElements) {
169  HandleScope scope(isolate);
170  DCHECK_EQ(2, args.length());
171  Handle<JSObject> object = args.at<JSObject>(0);
172  Handle<Object> key = args.at(1);
173  uint32_t index;
174  if (key->IsSmi()) {
175    int value = Smi::ToInt(*key);
176    if (value < 0) return Smi::zero();
177    index = static_cast<uint32_t>(value);
178  } else {
179    CHECK(key->IsHeapNumber());
180    double value = HeapNumber::cast(*key).value();
181    if (value < 0 || value > std::numeric_limits<uint32_t>::max()) {
182      return Smi::zero();
183    }
184    index = static_cast<uint32_t>(value);
185  }
186
187  uint32_t capacity = static_cast<uint32_t>(object->elements().length());
188
189  if (index >= capacity) {
190    bool has_grown;
191    MAYBE_ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
192        isolate, has_grown,
193        object->GetElementsAccessor()->GrowCapacity(object, index));
194    if (!has_grown) {
195      return Smi::zero();
196    }
197  }
198
199  return object->elements();
200}
201
202// ES6 22.1.2.2 Array.isArray
203RUNTIME_FUNCTION(Runtime_ArrayIsArray) {
204  HandleScope shs(isolate);
205  DCHECK_EQ(1, args.length());
206  Handle<Object> object = args.at(0);
207  Maybe<bool> result = Object::IsArray(object);
208  MAYBE_RETURN(result, ReadOnlyRoots(isolate).exception());
209  return isolate->heap()->ToBoolean(result.FromJust());
210}
211
212RUNTIME_FUNCTION(Runtime_IsArray) {
213  SealHandleScope shs(isolate);
214  DCHECK_EQ(1, args.length());
215  Object obj = args[0];
216  return isolate->heap()->ToBoolean(obj.IsJSArray());
217}
218
219RUNTIME_FUNCTION(Runtime_ArraySpeciesConstructor) {
220  HandleScope scope(isolate);
221  DCHECK_EQ(1, args.length());
222  Handle<Object> original_array = args.at(0);
223  RETURN_RESULT_OR_FAILURE(
224      isolate, Object::ArraySpeciesConstructor(isolate, original_array));
225}
226
227// ES7 22.1.3.11 Array.prototype.includes
228RUNTIME_FUNCTION(Runtime_ArrayIncludes_Slow) {
229  HandleScope shs(isolate);
230  DCHECK_EQ(3, args.length());
231  Handle<Object> search_element = args.at(1);
232  Handle<Object> from_index = args.at(2);
233
234  // Let O be ? ToObject(this value).
235  Handle<JSReceiver> object;
236  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
237      isolate, object,
238      Object::ToObject(isolate, Handle<Object>(args[0], isolate)));
239
240  // Let len be ? ToLength(? Get(O, "length")).
241  int64_t len;
242  {
243    if (object->map().instance_type() == JS_ARRAY_TYPE) {
244      uint32_t len32 = 0;
245      bool success = JSArray::cast(*object).length().ToArrayLength(&len32);
246      DCHECK(success);
247      USE(success);
248      len = len32;
249    } else {
250      Handle<Object> len_;
251      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
252          isolate, len_,
253          Object::GetProperty(isolate, object,
254                              isolate->factory()->length_string()));
255
256      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, len_,
257                                         Object::ToLength(isolate, len_));
258      len = static_cast<int64_t>(len_->Number());
259      DCHECK_EQ(len, len_->Number());
260    }
261  }
262
263  if (len == 0) return ReadOnlyRoots(isolate).false_value();
264
265  // Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step
266  // produces the value 0.)
267  int64_t index = 0;
268  if (!from_index->IsUndefined(isolate)) {
269    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, from_index,
270                                       Object::ToInteger(isolate, from_index));
271
272    if (V8_LIKELY(from_index->IsSmi())) {
273      int start_from = Smi::ToInt(*from_index);
274      if (start_from < 0) {
275        index = std::max<int64_t>(len + start_from, 0);
276      } else {
277        index = start_from;
278      }
279    } else {
280      DCHECK(from_index->IsHeapNumber());
281      double start_from = from_index->Number();
282      if (start_from >= len) return ReadOnlyRoots(isolate).false_value();
283      if (V8_LIKELY(std::isfinite(start_from))) {
284        if (start_from < 0) {
285          index = static_cast<int64_t>(std::max<double>(start_from + len, 0));
286        } else {
287          index = start_from;
288        }
289      }
290    }
291
292    DCHECK_GE(index, 0);
293  }
294
295  // If the receiver is not a special receiver type, and the length is a valid
296  // element index, perform fast operation tailored to specific ElementsKinds.
297  if (!object->map().IsSpecialReceiverMap() &&
298      len <= JSObject::kMaxElementCount &&
299      JSObject::PrototypeHasNoElements(isolate, JSObject::cast(*object))) {
300    Handle<JSObject> obj = Handle<JSObject>::cast(object);
301    ElementsAccessor* elements = obj->GetElementsAccessor();
302    Maybe<bool> result =
303        elements->IncludesValue(isolate, obj, search_element, index, len);
304    MAYBE_RETURN(result, ReadOnlyRoots(isolate).exception());
305    return *isolate->factory()->ToBoolean(result.FromJust());
306  }
307
308  // Otherwise, perform slow lookups for special receiver types.
309  for (; index < len; ++index) {
310    HandleScope iteration_hs(isolate);
311
312    // Let elementK be the result of ? Get(O, ! ToString(k)).
313    Handle<Object> element_k;
314    {
315      PropertyKey key(isolate, static_cast<double>(index));
316      LookupIterator it(isolate, object, key);
317      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, element_k,
318                                         Object::GetProperty(&it));
319    }
320
321    // If SameValueZero(searchElement, elementK) is true, return true.
322    if (search_element->SameValueZero(*element_k)) {
323      return ReadOnlyRoots(isolate).true_value();
324    }
325  }
326  return ReadOnlyRoots(isolate).false_value();
327}
328
329RUNTIME_FUNCTION(Runtime_ArrayIndexOf) {
330  HandleScope hs(isolate);
331  DCHECK_EQ(3, args.length());
332  Handle<Object> search_element = args.at(1);
333  Handle<Object> from_index = args.at(2);
334
335  // Let O be ? ToObject(this value).
336  Handle<JSReceiver> object;
337  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
338      isolate, object,
339      Object::ToObject(isolate, args.at(0), "Array.prototype.indexOf"));
340
341  // Let len be ? ToLength(? Get(O, "length")).
342  int64_t len;
343  {
344    if (object->IsJSArray()) {
345      uint32_t len32 = 0;
346      bool success = JSArray::cast(*object).length().ToArrayLength(&len32);
347      DCHECK(success);
348      USE(success);
349      len = len32;
350    } else {
351      Handle<Object> len_;
352      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
353          isolate, len_,
354          Object::GetProperty(isolate, object,
355                              isolate->factory()->length_string()));
356
357      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, len_,
358                                         Object::ToLength(isolate, len_));
359      len = static_cast<int64_t>(len_->Number());
360      DCHECK_EQ(len, len_->Number());
361    }
362  }
363
364  if (len == 0) return Smi::FromInt(-1);
365
366  // Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step
367  // produces the value 0.)
368  int64_t start_from;
369  {
370    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, from_index,
371                                       Object::ToInteger(isolate, from_index));
372    double fp = from_index->Number();
373    if (fp > len) return Smi::FromInt(-1);
374    if (V8_LIKELY(fp >=
375                  static_cast<double>(std::numeric_limits<int64_t>::min()))) {
376      DCHECK(fp < static_cast<double>(std::numeric_limits<int64_t>::max()));
377      start_from = static_cast<int64_t>(fp);
378    } else {
379      start_from = std::numeric_limits<int64_t>::min();
380    }
381  }
382
383  int64_t index;
384  if (start_from >= 0) {
385    index = start_from;
386  } else {
387    index = len + start_from;
388    if (index < 0) {
389      index = 0;
390    }
391  }
392
393  // If the receiver is not a special receiver type, and the length fits
394  // uint32_t, perform fast operation tailored to specific ElementsKinds.
395  if (!object->map().IsSpecialReceiverMap() && len <= kMaxUInt32 &&
396      JSObject::PrototypeHasNoElements(isolate, JSObject::cast(*object))) {
397    Handle<JSObject> obj = Handle<JSObject>::cast(object);
398    ElementsAccessor* elements = obj->GetElementsAccessor();
399    Maybe<int64_t> result = elements->IndexOfValue(isolate, obj, search_element,
400                                                   static_cast<uint32_t>(index),
401                                                   static_cast<uint32_t>(len));
402    MAYBE_RETURN(result, ReadOnlyRoots(isolate).exception());
403    return *isolate->factory()->NewNumberFromInt64(result.FromJust());
404  }
405
406  // Otherwise, perform slow lookups for special receiver types.
407  for (; index < len; ++index) {
408    HandleScope iteration_hs(isolate);
409    // Let elementK be the result of ? Get(O, ! ToString(k)).
410    Handle<Object> element_k;
411    {
412      PropertyKey key(isolate, static_cast<double>(index));
413      LookupIterator it(isolate, object, key);
414      Maybe<bool> present = JSReceiver::HasProperty(&it);
415      MAYBE_RETURN(present, ReadOnlyRoots(isolate).exception());
416      if (!present.FromJust()) continue;
417      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, element_k,
418                                         Object::GetProperty(&it));
419      if (search_element->StrictEquals(*element_k)) {
420        return *isolate->factory()->NewNumberFromInt64(index);
421      }
422    }
423  }
424  return Smi::FromInt(-1);
425}
426
427}  // namespace internal
428}  // namespace v8
429