runtime-array.cc 15.1 KB
Newer Older
1 2 3 4
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

Marja Hölttä's avatar
Marja Hölttä committed
5
#include "src/debug/debug.h"
6 7
#include "src/execution/arguments-inl.h"
#include "src/execution/isolate-inl.h"
8
#include "src/execution/protectors-inl.h"
9
#include "src/heap/factory.h"
10 11
#include "src/heap/heap-inl.h"  // For ToBoolean. TODO(jkummerow): Drop.
#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 22 23 24 25 26

namespace v8 {
namespace internal {

RUNTIME_FUNCTION(Runtime_TransitionElementsKind) {
  HandleScope scope(isolate);
27
  DCHECK_EQ(2, args.length());
28
  CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
29 30
  CONVERT_ARG_HANDLE_CHECKED(Map, to_map, 1);
  ElementsKind to_kind = to_map->elements_kind();
31 32 33 34 35
  if (ElementsAccessor::ForKind(to_kind)
          ->TransitionElementsKind(object, to_map)
          .IsNothing()) {
    // TODO(victorgomes): EffectControlLinearizer::LowerTransitionElementsKind
    // does not handle exceptions.
36 37
    FATAL(
        "Fatal JavaScript invalid size error when transitioning elements kind");
38 39
    UNREACHABLE();
  }
40
  return *object;
41 42
}

43 44 45 46 47 48 49 50 51 52
RUNTIME_FUNCTION(Runtime_TransitionElementsKindWithKind) {
  HandleScope scope(isolate);
  DCHECK_EQ(2, args.length());
  CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
  CONVERT_ARG_HANDLE_CHECKED(Smi, elements_kind_smi, 1);
  ElementsKind to_kind = static_cast<ElementsKind>(elements_kind_smi->value());
  JSObject::TransitionElementsKind(object, to_kind);
  return *object;
}

53 54 55 56
RUNTIME_FUNCTION(Runtime_NewArray) {
  HandleScope scope(isolate);
  DCHECK_LE(3, args.length());
  int const argc = args.length() - 3;
57
  // argv points to the arguments constructed by the JavaScript call.
58 59
  JavaScriptArguments argv(argc, args.address_of_arg_at(0));
  CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, argc);
60 61 62 63 64 65
  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, new_target, argc + 1);
  CONVERT_ARG_HANDLE_CHECKED(HeapObject, type_info, argc + 2);
  // TODO(bmeurer): Use MaybeHandle to pass around the AllocationSite.
  Handle<AllocationSite> site = type_info->IsAllocationSite()
                                    ? Handle<AllocationSite>::cast(type_info)
                                    : Handle<AllocationSite>::null();
66 67 68

  Factory* factory = isolate->factory();

69 70 71 72 73 74 75 76
  // If called through new, new.target can be:
  // - a subclass of constructor,
  // - a proxy wrapper around constructor, or
  // - the constructor itself.
  // If called through Reflect.construct, it's guaranteed to be a constructor by
  // REFLECT_CONSTRUCT_PREPARE.
  DCHECK(new_target->IsConstructor());

77
  bool holey = false;
78
  bool can_use_type_feedback = !site.is_null();
79
  bool can_inline_array_constructor = true;
80 81
  if (argv.length() == 1) {
    Handle<Object> argument_one = argv.at<Object>(0);
82 83
    if (argument_one->IsSmi()) {
      int value = Handle<Smi>::cast(argument_one)->value();
84 85
      if (value < 0 ||
          JSArray::SetLengthWouldNormalize(isolate->heap(), value)) {
86 87 88 89
        // the array is a dictionary in this case.
        can_use_type_feedback = false;
      } else if (value != 0) {
        holey = true;
90
        if (value >= JSArray::kInitialMaxFastElementArray) {
91 92
          can_inline_array_constructor = false;
        }
93 94 95 96 97 98 99
      }
    } else {
      // Non-smi length argument produces a dictionary
      can_use_type_feedback = false;
    }
  }

100 101 102 103
  Handle<Map> initial_map;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
      isolate, initial_map,
      JSFunction::GetDerivedMap(isolate, constructor, new_target));
104

105 106
  ElementsKind to_kind = can_use_type_feedback ? site->GetElementsKind()
                                               : initial_map->elements_kind();
107
  if (holey && !IsHoleyElementsKind(to_kind)) {
108 109 110 111
    to_kind = GetHoleyElementsKind(to_kind);
    // Update the allocation site info to reflect the advice alteration.
    if (!site.is_null()) site->SetElementsKind(to_kind);
  }
112

113 114 115
  // We should allocate with an initial map that reflects the allocation site
  // advice. Therefore we use AllocateJSObjectFromMap instead of passing
  // the constructor.
116
  initial_map = Map::AsElementsKind(isolate, initial_map, to_kind);
117 118 119 120

  // If we don't care to track arrays of to_kind ElementsKind, then
  // don't emit a memento for them.
  Handle<AllocationSite> allocation_site;
121
  if (AllocationSite::ShouldTrack(to_kind)) {
122
    allocation_site = site;
123 124
  }

125 126
  Handle<JSArray> array = Handle<JSArray>::cast(factory->NewJSObjectFromMap(
      initial_map, AllocationType::kYoung, allocation_site));
127

128 129 130
  factory->NewJSArrayStorage(array, 0, 0, DONT_INITIALIZE_ARRAY_ELEMENTS);

  ElementsKind old_kind = array->GetElementsKind();
131 132
  RETURN_FAILURE_ON_EXCEPTION(isolate,
                              ArrayConstructInitializeElements(array, &argv));
133 134 135 136
  if (!site.is_null()) {
    if ((old_kind != array->GetElementsKind() || !can_use_type_feedback ||
         !can_inline_array_constructor)) {
      // The arguments passed in caused a transition. This kind of complexity
137
      // can't be dealt with in the inlined optimized array constructor case.
138 139 140 141 142 143 144 145 146 147
      // We must mark the allocationsite as un-inlinable.
      site->SetDoNotInlineCall();
    }
  } else {
    if (old_kind != array->GetElementsKind() || !can_inline_array_constructor) {
      // We don't have an AllocationSite for this Array constructor invocation,
      // i.e. it might a call from Array#map or from an Array subclass, so we
      // just flip the bit on the global protector cell instead.
      // TODO(bmeurer): Find a better way to mark this. Global protectors
      // tend to back-fire over time...
148 149
      if (Protectors::IsArrayConstructorIntact(isolate)) {
        Protectors::InvalidateArrayConstructor(isolate);
150 151
      }
    }
152
  }
153

154 155 156 157 158
  return *array;
}

RUNTIME_FUNCTION(Runtime_NormalizeElements) {
  HandleScope scope(isolate);
159
  DCHECK_EQ(1, args.length());
160
  CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
161
  CHECK(!array->HasTypedArrayElements());
162
  CHECK(!array->IsJSGlobalProxy());
163 164 165 166
  JSObject::NormalizeElements(array);
  return *array;
}

167 168
// GrowArrayElements returns a sentinel Smi if the object was normalized or if
// the key is negative.
169 170
RUNTIME_FUNCTION(Runtime_GrowArrayElements) {
  HandleScope scope(isolate);
171
  DCHECK_EQ(2, args.length());
172
  CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
173 174 175 176 177 178 179 180 181 182 183 184 185 186
  CONVERT_ARG_HANDLE_CHECKED(Object, key, 1);
  uint32_t index;
  if (key->IsSmi()) {
    int value = Smi::ToInt(*key);
    if (value < 0) return Smi::zero();
    index = static_cast<uint32_t>(value);
  } else {
    CHECK(key->IsHeapNumber());
    double value = HeapNumber::cast(*key).value();
    if (value < 0 || value > std::numeric_limits<uint32_t>::max()) {
      return Smi::zero();
    }
    index = static_cast<uint32_t>(value);
  }
187

188
  uint32_t capacity = static_cast<uint32_t>(object->elements().length());
189 190

  if (index >= capacity) {
191 192 193 194 195
    bool has_grown;
    MAYBE_ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, has_grown,
        object->GetElementsAccessor()->GrowCapacity(object, index));
    if (!has_grown) {
196
      return Smi::zero();
197 198 199 200 201 202
    }
  }

  return object->elements();
}

203 204 205
// ES6 22.1.2.2 Array.isArray
RUNTIME_FUNCTION(Runtime_ArrayIsArray) {
  HandleScope shs(isolate);
206
  DCHECK_EQ(1, args.length());
207 208
  CONVERT_ARG_HANDLE_CHECKED(Object, object, 0);
  Maybe<bool> result = Object::IsArray(object);
209
  MAYBE_RETURN(result, ReadOnlyRoots(isolate).exception());
210 211
  return isolate->heap()->ToBoolean(result.FromJust());
}
212

213
RUNTIME_FUNCTION(Runtime_IsArray) {
214
  SealHandleScope shs(isolate);
215
  DCHECK_EQ(1, args.length());
216
  CONVERT_ARG_CHECKED(Object, obj, 0);
217
  return isolate->heap()->ToBoolean(obj.IsJSArray());
218 219
}

220 221
RUNTIME_FUNCTION(Runtime_ArraySpeciesConstructor) {
  HandleScope scope(isolate);
222
  DCHECK_EQ(1, args.length());
223
  CONVERT_ARG_HANDLE_CHECKED(Object, original_array, 0);
224 225
  RETURN_RESULT_OR_FAILURE(
      isolate, Object::ArraySpeciesConstructor(isolate, original_array));
226 227
}

228 229 230
// ES7 22.1.3.11 Array.prototype.includes
RUNTIME_FUNCTION(Runtime_ArrayIncludes_Slow) {
  HandleScope shs(isolate);
231
  DCHECK_EQ(3, args.length());
232 233 234 235 236 237
  CONVERT_ARG_HANDLE_CHECKED(Object, search_element, 1);
  CONVERT_ARG_HANDLE_CHECKED(Object, from_index, 2);

  // Let O be ? ToObject(this value).
  Handle<JSReceiver> object;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
238 239
      isolate, object,
      Object::ToObject(isolate, Handle<Object>(args[0], isolate)));
240 241 242 243

  // Let len be ? ToLength(? Get(O, "length")).
  int64_t len;
  {
244
    if (object->map().instance_type() == JS_ARRAY_TYPE) {
245
      uint32_t len32 = 0;
246
      bool success = JSArray::cast(*object).length().ToArrayLength(&len32);
247 248 249 250 251 252 253
      DCHECK(success);
      USE(success);
      len = len32;
    } else {
      Handle<Object> len_;
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
          isolate, len_,
254 255
          Object::GetProperty(isolate, object,
                              isolate->factory()->length_string()));
256 257 258 259 260 261 262 263

      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, len_,
                                         Object::ToLength(isolate, len_));
      len = static_cast<int64_t>(len_->Number());
      DCHECK_EQ(len, len_->Number());
    }
  }

264
  if (len == 0) return ReadOnlyRoots(isolate).false_value();
265 266 267

  // Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step
  // produces the value 0.)
268 269
  int64_t index = 0;
  if (!from_index->IsUndefined(isolate)) {
270 271 272
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, from_index,
                                       Object::ToInteger(isolate, from_index));

273
    if (V8_LIKELY(from_index->IsSmi())) {
jgruber's avatar
jgruber committed
274
      int start_from = Smi::ToInt(*from_index);
275 276 277 278 279 280 281 282
      if (start_from < 0) {
        index = std::max<int64_t>(len + start_from, 0);
      } else {
        index = start_from;
      }
    } else {
      DCHECK(from_index->IsHeapNumber());
      double start_from = from_index->Number();
283
      if (start_from >= len) return ReadOnlyRoots(isolate).false_value();
284 285 286 287 288 289 290
      if (V8_LIKELY(std::isfinite(start_from))) {
        if (start_from < 0) {
          index = static_cast<int64_t>(std::max<double>(start_from + len, 0));
        } else {
          index = start_from;
        }
      }
291
    }
292 293

    DCHECK_GE(index, 0);
294 295 296 297
  }

  // If the receiver is not a special receiver type, and the length is a valid
  // element index, perform fast operation tailored to specific ElementsKinds.
298 299
  if (!object->map().IsSpecialReceiverMap() &&
      len <= JSObject::kMaxElementCount &&
300 301 302
      JSObject::PrototypeHasNoElements(isolate, JSObject::cast(*object))) {
    Handle<JSObject> obj = Handle<JSObject>::cast(object);
    ElementsAccessor* elements = obj->GetElementsAccessor();
303 304
    Maybe<bool> result =
        elements->IncludesValue(isolate, obj, search_element, index, len);
305
    MAYBE_RETURN(result, ReadOnlyRoots(isolate).exception());
306 307 308
    return *isolate->factory()->ToBoolean(result.FromJust());
  }

309
  // Otherwise, perform slow lookups for special receiver types.
310
  for (; index < len; ++index) {
311 312
    HandleScope iteration_hs(isolate);

313 314 315
    // Let elementK be the result of ? Get(O, ! ToString(k)).
    Handle<Object> element_k;
    {
316
      PropertyKey key(isolate, static_cast<double>(index));
317
      LookupIterator it(isolate, object, key);
318 319 320 321 322 323
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, element_k,
                                         Object::GetProperty(&it));
    }

    // If SameValueZero(searchElement, elementK) is true, return true.
    if (search_element->SameValueZero(*element_k)) {
324
      return ReadOnlyRoots(isolate).true_value();
325 326
    }
  }
327
  return ReadOnlyRoots(isolate).false_value();
328 329
}

330
RUNTIME_FUNCTION(Runtime_ArrayIndexOf) {
331
  HandleScope hs(isolate);
332
  DCHECK_EQ(3, args.length());
333 334 335 336 337
  CONVERT_ARG_HANDLE_CHECKED(Object, search_element, 1);
  CONVERT_ARG_HANDLE_CHECKED(Object, from_index, 2);

  // Let O be ? ToObject(this value).
  Handle<JSReceiver> object;
338 339 340
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
      isolate, object,
      Object::ToObject(isolate, args.at(0), "Array.prototype.indexOf"));
341 342 343 344 345 346

  // Let len be ? ToLength(? Get(O, "length")).
  int64_t len;
  {
    if (object->IsJSArray()) {
      uint32_t len32 = 0;
347
      bool success = JSArray::cast(*object).length().ToArrayLength(&len32);
348 349 350 351 352 353 354
      DCHECK(success);
      USE(success);
      len = len32;
    } else {
      Handle<Object> len_;
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
          isolate, len_,
355 356
          Object::GetProperty(isolate, object,
                              isolate->factory()->length_string()));
357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374

      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, len_,
                                         Object::ToLength(isolate, len_));
      len = static_cast<int64_t>(len_->Number());
      DCHECK_EQ(len, len_->Number());
    }
  }

  if (len == 0) return Smi::FromInt(-1);

  // Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step
  // produces the value 0.)
  int64_t start_from;
  {
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, from_index,
                                       Object::ToInteger(isolate, from_index));
    double fp = from_index->Number();
    if (fp > len) return Smi::FromInt(-1);
375 376
    if (V8_LIKELY(fp >=
                  static_cast<double>(std::numeric_limits<int64_t>::min()))) {
377
      DCHECK(fp < static_cast<double>(std::numeric_limits<int64_t>::max()));
378 379 380 381
      start_from = static_cast<int64_t>(fp);
    } else {
      start_from = std::numeric_limits<int64_t>::min();
    }
382 383 384 385 386 387 388 389 390 391 392 393
  }

  int64_t index;
  if (start_from >= 0) {
    index = start_from;
  } else {
    index = len + start_from;
    if (index < 0) {
      index = 0;
    }
  }

394 395
  // If the receiver is not a special receiver type, and the length fits
  // uint32_t, perform fast operation tailored to specific ElementsKinds.
396
  if (!object->map().IsSpecialReceiverMap() && len <= kMaxUInt32 &&
397 398 399 400 401 402
      JSObject::PrototypeHasNoElements(isolate, JSObject::cast(*object))) {
    Handle<JSObject> obj = Handle<JSObject>::cast(object);
    ElementsAccessor* elements = obj->GetElementsAccessor();
    Maybe<int64_t> result = elements->IndexOfValue(isolate, obj, search_element,
                                                   static_cast<uint32_t>(index),
                                                   static_cast<uint32_t>(len));
403
    MAYBE_RETURN(result, ReadOnlyRoots(isolate).exception());
404 405 406
    return *isolate->factory()->NewNumberFromInt64(result.FromJust());
  }

407
  // Otherwise, perform slow lookups for special receiver types.
408
  for (; index < len; ++index) {
409
    HandleScope iteration_hs(isolate);
410 411 412
    // Let elementK be the result of ? Get(O, ! ToString(k)).
    Handle<Object> element_k;
    {
413
      PropertyKey key(isolate, static_cast<double>(index));
414
      LookupIterator it(isolate, object, key);
415
      Maybe<bool> present = JSReceiver::HasProperty(&it);
416
      MAYBE_RETURN(present, ReadOnlyRoots(isolate).exception());
417
      if (!present.FromJust()) continue;
418 419 420
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, element_k,
                                         Object::GetProperty(&it));
      if (search_element->StrictEquals(*element_k)) {
421
        return *isolate->factory()->NewNumberFromInt64(index);
422 423 424 425 426 427
      }
    }
  }
  return Smi::FromInt(-1);
}

428 429
}  // namespace internal
}  // namespace v8