runtime-array.cc 33.6 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.

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"
Marja Hölttä's avatar
Marja Hölttä committed
10
#include "src/debug/debug.h"
11
#include "src/elements.h"
12
#include "src/heap/factory.h"
13
#include "src/isolate-inl.h"
14
#include "src/keys.h"
15
#include "src/messages.h"
16
#include "src/objects/arguments-inl.h"
17
#include "src/objects/hash-table-inl.h"
18
#include "src/prototype.h"
19 20 21 22 23 24

namespace v8 {
namespace internal {

RUNTIME_FUNCTION(Runtime_TransitionElementsKind) {
  HandleScope scope(isolate);
25
  DCHECK_EQ(2, args.length());
26
  CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
27 28 29 30
  CONVERT_ARG_HANDLE_CHECKED(Map, to_map, 1);
  ElementsKind to_kind = to_map->elements_kind();
  ElementsAccessor::ForKind(to_kind)->TransitionElementsKind(object, to_map);
  return *object;
31 32
}

33
namespace {
34 35
// Find the next free position. undefined and holes are both considered
// free spots. Returns "Nothing" if an exception occurred.
36
V8_WARN_UNUSED_RESULT
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
Maybe<uint32_t> FindNextFreePosition(Isolate* isolate,
                                     Handle<JSReceiver> receiver,
                                     uint32_t current_pos) {
  for (uint32_t position = current_pos;; ++position) {
    Maybe<bool> has_element = JSReceiver::HasElement(receiver, position);
    MAYBE_RETURN(has_element, Nothing<uint32_t>());
    if (!has_element.FromJust()) return Just(position);

    Handle<Object> element;
    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
        isolate, element, JSReceiver::GetElement(isolate, receiver, position),
        Nothing<uint32_t>());
    if (element->IsUndefined(isolate)) return Just(position);
  }
}

53
// As RemoveArrayHoles, but also handles Dictionary elements that stay
54 55
// Dictionary (requires_slow_elements() is true), proxies and objects that
// might have accessors.
56 57 58
V8_WARN_UNUSED_RESULT
Object* RemoveArrayHolesGeneric(Isolate* isolate, Handle<JSReceiver> receiver,
                                uint32_t limit) {
59 60 61 62 63 64 65 66 67 68
  HandleScope scope(isolate);

  // For proxies, we do not collect the keys, instead we use all indices in
  // the full range of [0, limit).
  Handle<FixedArray> keys;
  if (receiver->IsJSProxy()) {
    CHECK(Smi::IsValid(limit));
    keys = isolate->factory()->NewFixedArray(limit);
    for (uint32_t i = 0; i < limit; ++i) {
      keys->set(i, Smi::FromInt(i));
69
    }
70
  } else {
71 72
    keys = JSReceiver::GetOwnElementIndices(isolate, receiver,
                                            Handle<JSObject>::cast(receiver));
73 74
  }

75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
  uint32_t num_undefined = 0;
  uint32_t current_pos = 0;
  int num_indices = keys->length();

  // Compact keys with undefined values and moves non-undefined
  // values to the front.
  // The loop does two things simultaneously:
  //   (1) Count the number of 'undefined', i.e.
  //       i.e.: HasProperty(receiver, key) && Get(receiver, key) == undefined
  //   (2) Move all non-undefined values to the front. The variable current_pos
  //       is used to track free spots in the array starting at the beginning.
  //       Holes and 'undefined' are considered free spots.
  //       A hole is when HasElement(receiver, key) is false.
  for (int i = 0; i < num_indices; ++i) {
    uint32_t key = NumberToUint32(keys->get(i));

    // We only care about array indices that are smaller than the limit.
    // The keys are sorted, so we can break as soon as we encounter the first.
    if (key >= limit) break;

    Maybe<bool> has_element = JSReceiver::HasElement(receiver, key);
96
    MAYBE_RETURN(has_element, ReadOnlyRoots(isolate).exception());
97 98 99 100 101 102 103 104 105 106 107 108 109 110
    if (!has_element.FromJust()) {
      continue;
    }

    Handle<Object> element;
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
        isolate, element, JSReceiver::GetElement(isolate, receiver, key));

    if (element->IsUndefined(isolate)) {
      ++num_undefined;
    } else {
      // Find next free position to move elements to.
      Maybe<uint32_t> free_position =
          FindNextFreePosition(isolate, receiver, current_pos);
111
      MAYBE_RETURN(free_position, ReadOnlyRoots(isolate).exception());
112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
      current_pos = free_position.FromJust();

      // Do not move elements that are already in the "packed" area.
      if (key <= current_pos) continue;

      // array[current_pos] = array[key].
      // Deleting array[key] is done later. This is to preserve the same
      // semantics as the old JS implementation when working with non-extensible
      // objects:
      // If the array contains undefineds, the position at 'key' might later
      // bet set to 'undefined'. If we delete the element now and later set it
      // to undefined, the set operation would throw an exception.
      RETURN_FAILURE_ON_EXCEPTION(
          isolate, JSReceiver::SetElement(isolate, receiver, current_pos,
                                          element, LanguageMode::kStrict));
      ++current_pos;
128 129 130
    }
  }

131 132 133 134 135 136 137 138
  // Set [current_pos, current_pos + num_undefined) to undefined.
  uint32_t result = current_pos;
  for (uint32_t i = 0; i < num_undefined; ++i) {
    RETURN_FAILURE_ON_EXCEPTION(
        isolate, JSReceiver::SetElement(isolate, receiver, current_pos++,
                                        isolate->factory()->undefined_value(),
                                        LanguageMode::kStrict));
  }
139 140 141 142
  // TODO(szuend): Re-enable when we also copy from the prototype chain for
  //               JSArrays. Then we can use HasOwnProperty instead of
  //               HasElement and this condition will hold.
  // DCHECK_LE(current_pos, num_indices);
143 144 145 146 147 148 149 150

  // Deleting everything after the undefineds up unto the limit.
  for (int i = num_indices - 1; i >= 0; --i) {
    uint32_t key = NumberToUint32(keys->get(i));
    if (key < current_pos) break;
    if (key >= limit) continue;

    Maybe<bool> delete_result = JSReceiver::DeleteElement(receiver, key);
151
    MAYBE_RETURN(delete_result, ReadOnlyRoots(isolate).exception());
152
  }
153

154
  return *isolate->factory()->NewNumberFromUint(result);
155 156 157 158 159 160
}

// Collects all defined (non-hole) and non-undefined (array) elements at the
// start of the elements array.  If the object is in dictionary mode, it is
// converted to fast elements mode.  Undefined values are placed after
// non-undefined values.  Returns the number of non-undefined values.
161 162 163
V8_WARN_UNUSED_RESULT
Object* RemoveArrayHoles(Isolate* isolate, Handle<JSReceiver> receiver,
                         uint32_t limit) {
164
  if (receiver->IsJSProxy()) {
165
    return RemoveArrayHolesGeneric(isolate, receiver, limit);
166
  }
167 168

  Handle<JSObject> object = Handle<JSObject>::cast(receiver);
169 170
  if (object->HasStringWrapperElements()) {
    int len = String::cast(Handle<JSValue>::cast(object)->value())->length();
171
    return Smi::FromInt(len);
172 173
  }

174
  if (object->HasSloppyArgumentsElements() || !object->map()->is_extensible()) {
175
    return RemoveArrayHolesGeneric(isolate, receiver, limit);
176 177
  }

178 179 180 181
  JSObject::ValidateElements(*object);
  if (object->HasDictionaryElements()) {
    // Convert to fast elements containing only the existing properties.
    // Ordering is irrelevant, since we are going to sort anyway.
182
    Handle<NumberDictionary> dict(object->element_dictionary(), isolate);
183 184
    if (object->IsJSArray() || dict->requires_slow_elements() ||
        dict->max_number_key() >= limit) {
185
      return RemoveArrayHolesGeneric(isolate, receiver, limit);
186 187 188 189 190
    }
    // Convert to fast elements.
    Handle<Map> new_map =
        JSObject::GetElementsTransitionMap(object, HOLEY_ELEMENTS);

191
    PretenureFlag tenure = Heap::InNewSpace(*object) ? NOT_TENURED : TENURED;
192 193 194 195 196 197 198 199
    Handle<FixedArray> fast_elements =
        isolate->factory()->NewFixedArray(dict->NumberOfElements(), tenure);
    dict->CopyValuesTo(*fast_elements);

    JSObject::SetMapAndElements(object, new_map, fast_elements);
    JSObject::ValidateElements(*object);
  } else if (object->HasFixedTypedArrayElements()) {
    // Typed arrays cannot have holes or undefined elements.
200 201
    int array_length = FixedArrayBase::cast(object->elements())->length();
    return Smi::FromInt(Min(limit, static_cast<uint32_t>(array_length)));
202 203 204 205 206 207 208 209
  } else if (!object->HasDoubleElements()) {
    JSObject::EnsureWritableFastElements(object);
  }
  DCHECK(object->HasSmiOrObjectElements() || object->HasDoubleElements());

  // Collect holes at the end, undefined before that and the rest at the
  // start, and return the number of non-hole, non-undefined values.

210
  Handle<FixedArrayBase> elements_base(object->elements(), isolate);
211 212 213 214 215
  uint32_t elements_length = static_cast<uint32_t>(elements_base->length());
  if (limit > elements_length) {
    limit = elements_length;
  }
  if (limit == 0) {
216
    return Smi::kZero;
217 218 219
  }

  uint32_t result = 0;
220
  if (elements_base->map() == ReadOnlyRoots(isolate).fixed_double_array_map()) {
221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292
    FixedDoubleArray* elements = FixedDoubleArray::cast(*elements_base);
    // Split elements into defined and the_hole, in that order.
    unsigned int holes = limit;
    // Assume most arrays contain no holes and undefined values, so minimize the
    // number of stores of non-undefined, non-the-hole values.
    for (unsigned int i = 0; i < holes; i++) {
      if (elements->is_the_hole(i)) {
        holes--;
      } else {
        continue;
      }
      // Position i needs to be filled.
      while (holes > i) {
        if (elements->is_the_hole(holes)) {
          holes--;
        } else {
          elements->set(i, elements->get_scalar(holes));
          break;
        }
      }
    }
    result = holes;
    while (holes < limit) {
      elements->set_the_hole(holes);
      holes++;
    }
  } else {
    FixedArray* elements = FixedArray::cast(*elements_base);
    DisallowHeapAllocation no_gc;

    // Split elements into defined, undefined and the_hole, in that order.  Only
    // count locations for undefined and the hole, and fill them afterwards.
    WriteBarrierMode write_barrier = elements->GetWriteBarrierMode(no_gc);
    unsigned int undefs = limit;
    unsigned int holes = limit;
    // Assume most arrays contain no holes and undefined values, so minimize the
    // number of stores of non-undefined, non-the-hole values.
    for (unsigned int i = 0; i < undefs; i++) {
      Object* current = elements->get(i);
      if (current->IsTheHole(isolate)) {
        holes--;
        undefs--;
      } else if (current->IsUndefined(isolate)) {
        undefs--;
      } else {
        continue;
      }
      // Position i needs to be filled.
      while (undefs > i) {
        current = elements->get(undefs);
        if (current->IsTheHole(isolate)) {
          holes--;
          undefs--;
        } else if (current->IsUndefined(isolate)) {
          undefs--;
        } else {
          elements->set(i, current, write_barrier);
          break;
        }
      }
    }
    result = undefs;
    while (undefs < holes) {
      elements->set_undefined(isolate, undefs);
      undefs++;
    }
    while (holes < limit) {
      elements->set_the_hole(isolate, holes);
      holes++;
    }
  }

293
  return *isolate->factory()->NewNumberFromUint(result);
294 295
}

296 297 298
// Copy element at index from source to target only if target does not have the
// element on its own. Returns true if a copy occurred, false if not
// and Nothing if an exception occurred.
299
V8_WARN_UNUSED_RESULT
300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325
Maybe<bool> ConditionalCopy(Isolate* isolate, Handle<JSReceiver> source,
                            Handle<JSReceiver> target, uint32_t index) {
  Maybe<bool> source_has_prop = JSReceiver::HasOwnProperty(source, index);
  MAYBE_RETURN(source_has_prop, Nothing<bool>());
  if (!source_has_prop.FromJust()) return Just(false);

  Maybe<bool> target_has_prop = JSReceiver::HasOwnProperty(target, index);
  MAYBE_RETURN(target_has_prop, Nothing<bool>());
  if (target_has_prop.FromJust()) return Just(false);

  Handle<Object> source_element;
  ASSIGN_RETURN_ON_EXCEPTION_VALUE(
      isolate, source_element, JSReceiver::GetElement(isolate, source, index),
      Nothing<bool>());

  Handle<Object> set_result;
  ASSIGN_RETURN_ON_EXCEPTION_VALUE(
      isolate, set_result,
      JSReceiver::SetElement(isolate, target, index, source_element,
                             LanguageMode::kStrict),
      Nothing<bool>());

  return Just(true);
}

// Copy elements in the range 0..length from objects prototype chain
326 327 328 329 330 331
// to object itself, if object has holes. Returns null on error and undefined on
// success.
V8_WARN_UNUSED_RESULT
MaybeHandle<Object> CopyFromPrototype(Isolate* isolate,
                                      Handle<JSReceiver> object,
                                      uint32_t length) {
332 333 334 335 336 337
  for (PrototypeIterator iter(isolate, object, kStartAtPrototype);
       !iter.IsAtEnd(); iter.Advance()) {
    Handle<JSReceiver> current(PrototypeIterator::GetCurrent<JSReceiver>(iter));

    if (current->IsJSProxy()) {
      for (uint32_t i = 0; i < length; ++i) {
338
        MAYBE_RETURN_NULL(ConditionalCopy(isolate, current, object, i));
339 340
      }
    } else {
341 342
      Handle<FixedArray> keys = JSReceiver::GetOwnElementIndices(
          isolate, object, Handle<JSObject>::cast(current));
343 344 345 346 347 348 349 350 351

      uint32_t num_indices = keys->length();
      for (uint32_t i = 0; i < num_indices; ++i) {
        uint32_t idx = NumberToUint32(keys->get(i));

        // Prototype might have indices that go past length, but we are only
        // interested in the range [0, length).
        if (idx >= length) break;

352
        MAYBE_RETURN_NULL(ConditionalCopy(isolate, current, object, idx));
353 354 355
      }
    }
  }
356 357 358 359 360 361 362 363 364 365 366 367 368
  return isolate->factory()->undefined_value();
}

}  // namespace

RUNTIME_FUNCTION(Runtime_PrepareElementsForSort) {
  HandleScope scope(isolate);
  DCHECK_EQ(2, args.length());
  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, object, 0);
  CONVERT_NUMBER_CHECKED(uint32_t, length, Uint32, args[1]);

  if (isolate->debug_execution_mode() == DebugInfo::kSideEffects) {
    if (!isolate->debug()->PerformSideEffectCheckForObject(object)) {
369
      return ReadOnlyRoots(isolate).exception();
370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391
    }
  }

  // Counter for sorting arrays that have non-packed elements and where either
  // the ElementsProtector is invalid or the prototype does not match
  // Array.prototype.
  if (object->IsJSArray() &&
      !Handle<JSArray>::cast(object)->HasFastPackedElements()) {
    JSObject* initial_array_proto = JSObject::cast(
        isolate->native_context()->get(Context::INITIAL_ARRAY_PROTOTYPE_INDEX));
    if (!isolate->IsNoElementsProtectorIntact() ||
        object->map()->prototype() != initial_array_proto) {
      isolate->CountUsage(
          v8::Isolate::kArrayPrototypeSortJSArrayModifiedPrototype);
    }
  }

  if (!object->IsJSArray()) {
    RETURN_FAILURE_ON_EXCEPTION(isolate,
                                CopyFromPrototype(isolate, object, length));
  }
  return RemoveArrayHoles(isolate, object, length);
392
}
393 394 395 396

// Move contents of argument 0 (an array) to argument 1 (an array)
RUNTIME_FUNCTION(Runtime_MoveArrayContents) {
  HandleScope scope(isolate);
397
  DCHECK_EQ(2, args.length());
398 399
  CONVERT_ARG_HANDLE_CHECKED(JSArray, from, 0);
  CONVERT_ARG_HANDLE_CHECKED(JSArray, to, 1);
400 401
  JSObject::ValidateElements(*from);
  JSObject::ValidateElements(*to);
402

403
  Handle<FixedArrayBase> new_elements(from->elements(), isolate);
404 405 406 407 408
  ElementsKind from_kind = from->GetElementsKind();
  Handle<Map> new_map = JSObject::GetElementsTransitionMap(to, from_kind);
  JSObject::SetMapAndElements(to, new_map, new_elements);
  to->set_length(from->length());

409
  from->initialize_elements();
410
  from->set_length(Smi::kZero);
411

412
  JSObject::ValidateElements(*to);
413 414 415 416 417 418
  return *to;
}


// How many elements does this object/array have?
RUNTIME_FUNCTION(Runtime_EstimateNumberOfElements) {
419
  DisallowHeapAllocation no_gc;
420
  HandleScope scope(isolate);
421
  DCHECK_EQ(1, args.length());
422 423
  CONVERT_ARG_CHECKED(JSArray, array, 0);
  FixedArrayBase* elements = array->elements();
424
  SealHandleScope shs(isolate);
425
  if (elements->IsNumberDictionary()) {
426
    int result = NumberDictionary::cast(elements)->NumberOfElements();
427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444
    return Smi::FromInt(result);
  } else {
    DCHECK(array->length()->IsSmi());
    // For packed elements, we know the exact number of elements
    int length = elements->length();
    ElementsKind kind = array->GetElementsKind();
    if (IsFastPackedElementsKind(kind)) {
      return Smi::FromInt(length);
    }
    // For holey elements, take samples from the buffer checking for holes
    // to generate the estimate.
    const int kNumberOfHoleCheckSamples = 97;
    int increment = (length < kNumberOfHoleCheckSamples)
                        ? 1
                        : static_cast<int>(length / kNumberOfHoleCheckSamples);
    ElementsAccessor* accessor = array->GetElementsAccessor();
    int holes = 0;
    for (int i = 0; i < length; i += increment) {
445
      if (!accessor->HasElement(array, i, elements)) {
446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462
        ++holes;
      }
    }
    int estimate = static_cast<int>((kNumberOfHoleCheckSamples - holes) /
                                    kNumberOfHoleCheckSamples * length);
    return Smi::FromInt(estimate);
  }
}


// Returns an array that tells you where in the [0, length) interval an array
// might have elements.  Can either return an array of keys (positive integers
// or undefined) or a number representing the positive length of an interval
// starting at index 0.
// Intervals can span over some keys that are not in the object.
RUNTIME_FUNCTION(Runtime_GetArrayKeys) {
  HandleScope scope(isolate);
463
  DCHECK_EQ(2, args.length());
464 465
  CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
  CONVERT_NUMBER_CHECKED(uint32_t, length, Uint32, args[1]);
466
  ElementsKind kind = array->GetElementsKind();
467

468 469 470 471 472 473
  if (IsFastElementsKind(kind) || IsFixedTypedArrayElementsKind(kind)) {
    uint32_t actual_length = static_cast<uint32_t>(array->elements()->length());
    return *isolate->factory()->NewNumberFromUint(Min(actual_length, length));
  }

  if (kind == FAST_STRING_WRAPPER_ELEMENTS) {
474 475 476 477 478 479 480 481
    int string_length =
        String::cast(Handle<JSValue>::cast(array)->value())->length();
    int backing_store_length = array->elements()->length();
    return *isolate->factory()->NewNumberFromUint(
        Min(length,
            static_cast<uint32_t>(Max(string_length, backing_store_length))));
  }

482 483
  KeyAccumulator accumulator(isolate, KeyCollectionMode::kOwnOnly,
                             ALL_PROPERTIES);
484
  for (PrototypeIterator iter(isolate, array, kStartAtReceiver);
485
       !iter.IsAtEnd(); iter.Advance()) {
486 487
    Handle<JSReceiver> current(PrototypeIterator::GetCurrent<JSReceiver>(iter));
    if (current->HasComplexElements()) {
488 489
      return *isolate->factory()->NewNumberFromUint(length);
    }
490 491
    accumulator.CollectOwnElementIndices(array,
                                         Handle<JSObject>::cast(current));
492 493
  }
  // Erase any keys >= length.
494 495
  Handle<FixedArray> keys =
      accumulator.GetKeys(GetKeysConversion::kKeepNumbers);
496
  int j = 0;
497
  for (int i = 0; i < keys->length(); i++) {
498 499 500
    if (NumberToUint32(keys->get(i)) >= length) continue;
    if (i != j) keys->set(j, keys->get(i));
    j++;
501
  }
502

503
  keys = FixedArray::ShrinkOrEmpty(isolate, keys, j);
504
  return *isolate->factory()->NewJSArrayWithElements(keys);
505 506
}

507 508 509 510 511 512 513 514 515 516 517 518
RUNTIME_FUNCTION(Runtime_TrySliceSimpleNonFastElements) {
  HandleScope scope(isolate);
  DCHECK_EQ(3, args.length());
  CONVERT_ARG_HANDLE_CHECKED(JSReceiver, receiver, 0);
  CONVERT_SMI_ARG_CHECKED(first, 1);
  CONVERT_SMI_ARG_CHECKED(count, 2);
  uint32_t length = first + count;

  // Only handle elements kinds that have a ElementsAccessor Slice
  // implementation.
  if (receiver->IsJSArray()) {
    // This "fastish" path must make sure the destination array is a JSArray.
519
    if (!isolate->IsArraySpeciesLookupChainIntact() ||
520 521 522 523
        !JSArray::cast(*receiver)->HasArrayPrototype(isolate)) {
      return Smi::FromInt(0);
    }
  } else {
524 525 526 527 528
    int len;
    if (!receiver->IsJSObject() ||
        !JSSloppyArgumentsObject::GetSloppyArgumentsLength(
            isolate, Handle<JSObject>::cast(receiver), &len) ||
        (length > static_cast<uint32_t>(len))) {
529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544
      return Smi::FromInt(0);
    }
  }

  // This "fastish" path must also ensure that elements are simple (no
  // geters/setters), no elements on prototype chain.
  Handle<JSObject> object(Handle<JSObject>::cast(receiver));
  if (!JSObject::PrototypeHasNoElements(isolate, *object) ||
      object->HasComplexElements()) {
    return Smi::FromInt(0);
  }

  ElementsAccessor* accessor = object->GetElementsAccessor();
  return *accessor->Slice(object, first, length);
}

545 546 547 548 549 550 551 552 553 554 555 556 557
RUNTIME_FUNCTION(Runtime_NewArray) {
  HandleScope scope(isolate);
  DCHECK_LE(3, args.length());
  int const argc = args.length() - 3;
  // TODO(bmeurer): Remove this Arguments nonsense.
  Arguments argv(argc, args.arguments() - 1);
  CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, 0);
  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();
558 559 560

  Factory* factory = isolate->factory();

561 562 563 564 565 566 567 568
  // 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());

569
  bool holey = false;
570
  bool can_use_type_feedback = !site.is_null();
571
  bool can_inline_array_constructor = true;
572 573
  if (argv.length() == 1) {
    Handle<Object> argument_one = argv.at<Object>(0);
574 575
    if (argument_one->IsSmi()) {
      int value = Handle<Smi>::cast(argument_one)->value();
576 577
      if (value < 0 ||
          JSArray::SetLengthWouldNormalize(isolate->heap(), value)) {
578 579 580 581
        // the array is a dictionary in this case.
        can_use_type_feedback = false;
      } else if (value != 0) {
        holey = true;
582
        if (value >= JSArray::kInitialMaxFastElementArray) {
583 584
          can_inline_array_constructor = false;
        }
585 586 587 588 589 590 591
      }
    } else {
      // Non-smi length argument produces a dictionary
      can_use_type_feedback = false;
    }
  }

592 593 594 595
  Handle<Map> initial_map;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
      isolate, initial_map,
      JSFunction::GetDerivedMap(isolate, constructor, new_target));
596

597 598
  ElementsKind to_kind = can_use_type_feedback ? site->GetElementsKind()
                                               : initial_map->elements_kind();
599
  if (holey && !IsHoleyElementsKind(to_kind)) {
600 601 602 603
    to_kind = GetHoleyElementsKind(to_kind);
    // Update the allocation site info to reflect the advice alteration.
    if (!site.is_null()) site->SetElementsKind(to_kind);
  }
604

605 606 607 608
  // We should allocate with an initial map that reflects the allocation site
  // advice. Therefore we use AllocateJSObjectFromMap instead of passing
  // the constructor.
  if (to_kind != initial_map->elements_kind()) {
609
    initial_map = Map::AsElementsKind(isolate, initial_map, to_kind);
610 611 612 613 614
  }

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

619 620 621
  Handle<JSArray> array = Handle<JSArray>::cast(
      factory->NewJSObjectFromMap(initial_map, NOT_TENURED, allocation_site));

622 623 624
  factory->NewJSArrayStorage(array, 0, 0, DONT_INITIALIZE_ARRAY_ELEMENTS);

  ElementsKind old_kind = array->GetElementsKind();
625 626
  RETURN_FAILURE_ON_EXCEPTION(isolate,
                              ArrayConstructInitializeElements(array, &argv));
627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645
  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
      // can't be dealt with in the inlined hydrogen array constructor case.
      // 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...
      if (isolate->IsArrayConstructorIntact()) {
        isolate->InvalidateArrayConstructorProtector();
      }
    }
646
  }
647

648 649 650 651 652
  return *array;
}

RUNTIME_FUNCTION(Runtime_NormalizeElements) {
  HandleScope scope(isolate);
653
  DCHECK_EQ(1, args.length());
654
  CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
655 656
  CHECK(!array->HasFixedTypedArrayElements());
  CHECK(!array->IsJSGlobalProxy());
657 658 659 660
  JSObject::NormalizeElements(array);
  return *array;
}

661 662
// GrowArrayElements returns a sentinel Smi if the object was normalized or if
// the key is negative.
663 664
RUNTIME_FUNCTION(Runtime_GrowArrayElements) {
  HandleScope scope(isolate);
665
  DCHECK_EQ(2, args.length());
666
  CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
667
  CONVERT_NUMBER_CHECKED(int, key, Int32, args[1]);
668

669
  if (key < 0) return Smi::kZero;
670 671 672 673 674

  uint32_t capacity = static_cast<uint32_t>(object->elements()->length());
  uint32_t index = static_cast<uint32_t>(key);

  if (index >= capacity) {
675
    if (!object->GetElementsAccessor()->GrowCapacity(object, index)) {
676
      return Smi::kZero;
677 678 679 680 681 682 683
    }
  }

  return object->elements();
}


684 685
RUNTIME_FUNCTION(Runtime_HasComplexElements) {
  HandleScope scope(isolate);
686
  DCHECK_EQ(1, args.length());
687
  CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
688
  for (PrototypeIterator iter(isolate, array, kStartAtReceiver);
689
       !iter.IsAtEnd(); iter.Advance()) {
690
    if (PrototypeIterator::GetCurrent<JSReceiver>(iter)->HasComplexElements()) {
691
      return ReadOnlyRoots(isolate).true_value();
692 693
    }
  }
694
  return ReadOnlyRoots(isolate).false_value();
695 696
}

697 698 699
// ES6 22.1.2.2 Array.isArray
RUNTIME_FUNCTION(Runtime_ArrayIsArray) {
  HandleScope shs(isolate);
700
  DCHECK_EQ(1, args.length());
701 702
  CONVERT_ARG_HANDLE_CHECKED(Object, object, 0);
  Maybe<bool> result = Object::IsArray(object);
703
  MAYBE_RETURN(result, ReadOnlyRoots(isolate).exception());
704 705
  return isolate->heap()->ToBoolean(result.FromJust());
}
706

707
RUNTIME_FUNCTION(Runtime_IsArray) {
708
  SealHandleScope shs(isolate);
709
  DCHECK_EQ(1, args.length());
710 711 712 713
  CONVERT_ARG_CHECKED(Object, obj, 0);
  return isolate->heap()->ToBoolean(obj->IsJSArray());
}

714 715
RUNTIME_FUNCTION(Runtime_ArraySpeciesConstructor) {
  HandleScope scope(isolate);
716
  DCHECK_EQ(1, args.length());
717
  CONVERT_ARG_HANDLE_CHECKED(Object, original_array, 0);
718 719
  RETURN_RESULT_OR_FAILURE(
      isolate, Object::ArraySpeciesConstructor(isolate, original_array));
720 721
}

722 723 724
// ES7 22.1.3.11 Array.prototype.includes
RUNTIME_FUNCTION(Runtime_ArrayIncludes_Slow) {
  HandleScope shs(isolate);
725
  DCHECK_EQ(3, args.length());
726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755
  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(
      isolate, object, Object::ToObject(isolate, handle(args[0], isolate)));

  // Let len be ? ToLength(? Get(O, "length")).
  int64_t len;
  {
    if (object->map()->instance_type() == JS_ARRAY_TYPE) {
      uint32_t len32 = 0;
      bool success = JSArray::cast(*object)->length()->ToArrayLength(&len32);
      DCHECK(success);
      USE(success);
      len = len32;
    } else {
      Handle<Object> len_;
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
          isolate, len_,
          Object::GetProperty(object, isolate->factory()->length_string()));

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

756
  if (len == 0) return ReadOnlyRoots(isolate).false_value();
757 758 759

  // Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step
  // produces the value 0.)
760 761
  int64_t index = 0;
  if (!from_index->IsUndefined(isolate)) {
762 763 764
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, from_index,
                                       Object::ToInteger(isolate, from_index));

765
    if (V8_LIKELY(from_index->IsSmi())) {
jgruber's avatar
jgruber committed
766
      int start_from = Smi::ToInt(*from_index);
767 768 769 770 771 772 773 774
      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();
775
      if (start_from >= len) return ReadOnlyRoots(isolate).false_value();
776 777 778 779 780 781 782
      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;
        }
      }
783
    }
784 785

    DCHECK_GE(index, 0);
786 787 788 789
  }

  // If the receiver is not a special receiver type, and the length is a valid
  // element index, perform fast operation tailored to specific ElementsKinds.
790
  if (!object->map()->IsSpecialReceiverMap() && len < kMaxUInt32 &&
791 792 793 794 795 796
      JSObject::PrototypeHasNoElements(isolate, JSObject::cast(*object))) {
    Handle<JSObject> obj = Handle<JSObject>::cast(object);
    ElementsAccessor* elements = obj->GetElementsAccessor();
    Maybe<bool> result = elements->IncludesValue(isolate, obj, search_element,
                                                 static_cast<uint32_t>(index),
                                                 static_cast<uint32_t>(len));
797
    MAYBE_RETURN(result, ReadOnlyRoots(isolate).exception());
798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816
    return *isolate->factory()->ToBoolean(result.FromJust());
  }

  // Otherwise, perform slow lookups for special receiver types
  for (; index < len; ++index) {
    // Let elementK be the result of ? Get(O, ! ToString(k)).
    Handle<Object> element_k;
    {
      Handle<Object> index_obj = isolate->factory()->NewNumberFromInt64(index);
      bool success;
      LookupIterator it = LookupIterator::PropertyOrElement(
          isolate, object, index_obj, &success);
      DCHECK(success);
      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)) {
817
      return ReadOnlyRoots(isolate).true_value();
818 819
    }
  }
820
  return ReadOnlyRoots(isolate).false_value();
821 822
}

823 824
RUNTIME_FUNCTION(Runtime_ArrayIndexOf) {
  HandleScope shs(isolate);
825
  DCHECK_EQ(3, args.length());
826 827 828 829 830
  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;
831 832 833
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
      isolate, object,
      Object::ToObject(isolate, args.at(0), "Array.prototype.indexOf"));
834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866

  // Let len be ? ToLength(? Get(O, "length")).
  int64_t len;
  {
    if (object->IsJSArray()) {
      uint32_t len32 = 0;
      bool success = JSArray::cast(*object)->length()->ToArrayLength(&len32);
      DCHECK(success);
      USE(success);
      len = len32;
    } else {
      Handle<Object> len_;
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
          isolate, len_,
          Object::GetProperty(object, isolate->factory()->length_string()));

      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);
867 868 869 870 871 872 873
    if (V8_LIKELY(fp >=
                  static_cast<double>(std::numeric_limits<int64_t>::min()))) {
      DCHECK(fp < std::numeric_limits<int64_t>::max());
      start_from = static_cast<int64_t>(fp);
    } else {
      start_from = std::numeric_limits<int64_t>::min();
    }
874 875 876 877 878 879 880 881 882 883 884 885 886 887
  }

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

  // If the receiver is not a special receiver type, and the length is a valid
  // element index, perform fast operation tailored to specific ElementsKinds.
888
  if (!object->map()->IsSpecialReceiverMap() && len < kMaxUInt32 &&
889 890 891 892 893 894
      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));
895
    MAYBE_RETURN(result, ReadOnlyRoots(isolate).exception());
896 897 898 899 900 901 902 903 904 905 906 907 908
    return *isolate->factory()->NewNumberFromInt64(result.FromJust());
  }

  // Otherwise, perform slow lookups for special receiver types
  for (; index < len; ++index) {
    // Let elementK be the result of ? Get(O, ! ToString(k)).
    Handle<Object> element_k;
    {
      Handle<Object> index_obj = isolate->factory()->NewNumberFromInt64(index);
      bool success;
      LookupIterator it = LookupIterator::PropertyOrElement(
          isolate, object, index_obj, &success);
      DCHECK(success);
909
      Maybe<bool> present = JSReceiver::HasProperty(&it);
910
      MAYBE_RETURN(present, ReadOnlyRoots(isolate).exception());
911
      if (!present.FromJust()) continue;
912 913 914 915 916 917 918 919 920 921
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, element_k,
                                         Object::GetProperty(&it));
      if (search_element->StrictEquals(*element_k)) {
        return *index_obj;
      }
    }
  }
  return Smi::FromInt(-1);
}

922 923
}  // namespace internal
}  // namespace v8