runtime-array.cc 33.5 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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
  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);
    MAYBE_RETURN(has_element, isolate->heap()->exception());
    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);
      MAYBE_RETURN(free_position, isolate->heap()->exception());
      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 151 152

  // 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);
    MAYBE_RETURN(delete_result, isolate->heap()->exception());
  }
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());
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 191 192 193 194 195 196 197 198 199 200
    }
    // Convert to fast elements.
    Handle<Map> new_map =
        JSObject::GetElementsTransitionMap(object, HOLEY_ELEMENTS);

    PretenureFlag tenure =
        isolate->heap()->InNewSpace(*object) ? NOT_TENURED : TENURED;
    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.
201 202
    int array_length = FixedArrayBase::cast(object->elements())->length();
    return Smi::FromInt(Min(limit, static_cast<uint32_t>(array_length)));
203 204 205 206 207 208 209 210 211 212 213 214 215 216
  } 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.

  Handle<FixedArrayBase> elements_base(object->elements());
  uint32_t elements_length = static_cast<uint32_t>(elements_base->length());
  if (limit > elements_length) {
    limit = elements_length;
  }
  if (limit == 0) {
217
    return Smi::kZero;
218 219 220 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 293
  }

  uint32_t result = 0;
  if (elements_base->map() == isolate->heap()->fixed_double_array_map()) {
    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++;
    }
  }

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

297 298 299
// 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.
300
V8_WARN_UNUSED_RESULT
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 326
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
327 328 329 330 331 332
// 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) {
333 334 335 336 337 338
  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) {
339
        MAYBE_RETURN_NULL(ConditionalCopy(isolate, current, object, i));
340 341
      }
    } else {
342 343
      Handle<FixedArray> keys = JSReceiver::GetOwnElementIndices(
          isolate, object, Handle<JSObject>::cast(current));
344 345 346 347 348 349 350 351 352

      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;

353
        MAYBE_RETURN_NULL(ConditionalCopy(isolate, current, object, idx));
354 355 356
      }
    }
  }
357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392
  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)) {
      return isolate->heap()->exception();
    }
  }

  // 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);
393
}
394 395 396 397

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

  Handle<FixedArrayBase> new_elements(from->elements());
  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());

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

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


// How many elements does this object/array have?
RUNTIME_FUNCTION(Runtime_EstimateNumberOfElements) {
420
  DisallowHeapAllocation no_gc;
421
  HandleScope scope(isolate);
422
  DCHECK_EQ(1, args.length());
423 424
  CONVERT_ARG_CHECKED(JSArray, array, 0);
  FixedArrayBase* elements = array->elements();
425 426
  SealHandleScope shs(isolate);
  if (elements->IsDictionary()) {
427
    int result = NumberDictionary::cast(elements)->NumberOfElements();
428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445
    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) {
446
      if (!accessor->HasElement(array, i, elements)) {
447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463
        ++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);
464
  DCHECK_EQ(2, args.length());
465 466
  CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
  CONVERT_NUMBER_CHECKED(uint32_t, length, Uint32, args[1]);
467
  ElementsKind kind = array->GetElementsKind();
468

469 470 471 472 473 474
  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) {
475 476 477 478 479 480 481 482
    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))));
  }

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

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

508 509 510 511 512 513 514 515 516 517 518 519
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.
520
    if (!isolate->IsArraySpeciesLookupChainIntact() ||
521 522 523 524
        !JSArray::cast(*receiver)->HasArrayPrototype(isolate)) {
      return Smi::FromInt(0);
    }
  } else {
525 526 527 528 529
    int len;
    if (!receiver->IsJSObject() ||
        !JSSloppyArgumentsObject::GetSloppyArgumentsLength(
            isolate, Handle<JSObject>::cast(receiver), &len) ||
        (length > static_cast<uint32_t>(len))) {
530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545
      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);
}

546 547 548 549 550 551 552 553 554 555 556 557 558
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();
559 560 561

  Factory* factory = isolate->factory();

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

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

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

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

606 607 608 609 610 611 612 613 614 615
  // 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()) {
    initial_map = Map::AsElementsKind(initial_map, to_kind);
  }

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

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

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

  ElementsKind old_kind = array->GetElementsKind();
626 627
  RETURN_FAILURE_ON_EXCEPTION(isolate,
                              ArrayConstructInitializeElements(array, &argv));
628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646
  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();
      }
    }
647
  }
648

649 650 651 652 653
  return *array;
}

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

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

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

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

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

  return object->elements();
}


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

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

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

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

723 724 725
// ES7 22.1.3.11 Array.prototype.includes
RUNTIME_FUNCTION(Runtime_ArrayIncludes_Slow) {
  HandleScope shs(isolate);
726
  DCHECK_EQ(3, args.length());
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 756 757 758 759 760
  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());
    }
  }

  if (len == 0) return isolate->heap()->false_value();

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

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

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

  // If the receiver is not a special receiver type, and the length is a valid
  // element index, perform fast operation tailored to specific ElementsKinds.
791
  if (!object->map()->IsSpecialReceiverMap() && len < kMaxUInt32 &&
792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823
      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));
    MAYBE_RETURN(result, isolate->heap()->exception());
    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)) {
      return isolate->heap()->true_value();
    }
  }
  return isolate->heap()->false_value();
}

824 825
RUNTIME_FUNCTION(Runtime_ArrayIndexOf) {
  HandleScope shs(isolate);
826
  DCHECK_EQ(3, args.length());
827 828 829 830 831
  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;
832 833 834
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
      isolate, object,
      Object::ToObject(isolate, args.at(0), "Array.prototype.indexOf"));
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 867

  // 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);
868 869 870 871 872 873 874
    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();
    }
875 876 877 878 879 880 881 882 883 884 885 886 887 888
  }

  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.
889
  if (!object->map()->IsSpecialReceiverMap() && len < kMaxUInt32 &&
890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909
      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));
    MAYBE_RETURN(result, isolate->heap()->exception());
    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);
910 911 912
      Maybe<bool> present = JSReceiver::HasProperty(&it);
      MAYBE_RETURN(present, isolate->heap()->exception());
      if (!present.FromJust()) continue;
913 914 915 916 917 918 919 920 921 922
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, element_k,
                                         Object::GetProperty(&it));
      if (search_element->StrictEquals(*element_k)) {
        return *index_obj;
      }
    }
  }
  return Smi::FromInt(-1);
}

923 924
}  // namespace internal
}  // namespace v8