runtime-array.cc 34.7 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/arguments-inl.h"
6
#include "src/conversions-inl.h"
7
#include "src/counters.h"
Marja Hölttä's avatar
Marja Hölttä committed
8
#include "src/debug/debug.h"
9
#include "src/elements.h"
10
#include "src/heap/factory.h"
11 12
#include "src/heap/heap-inl.h"  // For ToBoolean. TODO(jkummerow): Drop.
#include "src/heap/heap-write-barrier-inl.h"
13
#include "src/isolate-inl.h"
14
#include "src/keys.h"
15
#include "src/objects/allocation-site-inl.h"
16
#include "src/objects/arguments-inl.h"
17
#include "src/objects/hash-table-inl.h"
18
#include "src/objects/js-array-inl.h"
19
#include "src/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 31 32
  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;
33 34
}

35 36 37 38 39 40 41 42 43 44
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;
}

45
namespace {
46 47
// Find the next free position. undefined and holes are both considered
// free spots. Returns "Nothing" if an exception occurred.
48
V8_WARN_UNUSED_RESULT
49 50 51 52
Maybe<uint32_t> FindNextFreePosition(Isolate* isolate,
                                     Handle<JSReceiver> receiver,
                                     uint32_t current_pos) {
  for (uint32_t position = current_pos;; ++position) {
53
    Maybe<bool> has_element = JSReceiver::HasOwnProperty(receiver, position);
54 55 56 57 58 59 60 61 62 63 64
    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);
  }
}

65
// As RemoveArrayHoles, but also handles Dictionary elements that stay
66 67
// Dictionary (requires_slow_elements() is true), proxies and objects that
// might have accessors.
68
V8_WARN_UNUSED_RESULT
69 70
Object RemoveArrayHolesGeneric(Isolate* isolate, Handle<JSReceiver> receiver,
                               uint32_t limit) {
71 72 73 74 75
  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;
76
  if (!receiver->IsJSProxy()) {
77 78
    keys = JSReceiver::GetOwnElementIndices(isolate, receiver,
                                            Handle<JSObject>::cast(receiver));
79 80
  }

81 82
  uint32_t num_undefined = 0;
  uint32_t current_pos = 0;
83
  uint32_t num_indices = keys.is_null() ? limit : keys->length();
84 85 86 87 88 89 90 91 92 93

  // 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.
94
  for (uint32_t i = 0; i < num_indices; ++i) {
95
    uint32_t key = keys.is_null() ? i : NumberToUint32(keys->get(i));
96 97 98 99 100 101

    // 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);
102
    MAYBE_RETURN(has_element, ReadOnlyRoots(isolate).exception());
103 104 105 106 107 108 109 110 111 112 113 114 115 116
    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);
117
      MAYBE_RETURN(free_position, ReadOnlyRoots(isolate).exception());
118 119 120 121 122 123 124 125 126 127 128 129
      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.
130 131 132 133
      // Instead, to mark it up as a free space, we set array[key] to undefined.
      // As 'key' will be incremented afterward, this undefined value will not
      // affect 'num_undefined', and the logic afterwards will correctly set
      // the remaining undefineds or delete the remaining properties.
134
      RETURN_FAILURE_ON_EXCEPTION(
135
          isolate, Object::SetElement(isolate, receiver, current_pos, element,
136
                                      ShouldThrow::kThrowOnError));
137 138 139
      RETURN_FAILURE_ON_EXCEPTION(
          isolate, Object::SetElement(isolate, receiver, key,
                                      isolate->factory()->undefined_value(),
140
                                      ShouldThrow::kThrowOnError));
141
      ++current_pos;
142 143 144
    }
  }

145 146 147 148 149 150 151 152
  // current_pos points to the next free space in the array/object. In most
  // cases this corresponds to the 'length' or to the number of non-undefined
  // elements.
  // In cases where an object is 'packed' and 'length' is smaller, e.g.:
  //      { 0: 5, 1: 4, 2: 3, length: 2 }
  // current_pos will be greater than limit, thus, we need to take the minimum.
  uint32_t result = std::min(current_pos, limit);

153 154 155
  // Set [current_pos, current_pos + num_undefined) to undefined.
  for (uint32_t i = 0; i < num_undefined; ++i) {
    RETURN_FAILURE_ON_EXCEPTION(
156 157
        isolate, Object::SetElement(isolate, receiver, current_pos++,
                                    isolate->factory()->undefined_value(),
158
                                    ShouldThrow::kThrowOnError));
159
  }
160 161 162 163
  // 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);
164 165

  // Deleting everything after the undefineds up unto the limit.
166 167
  for (uint32_t i = num_indices; i > 0;) {
    --i;
168
    uint32_t key = keys.is_null() ? i : NumberToUint32(keys->get(i));
169 170 171 172
    if (key < current_pos) break;
    if (key >= limit) continue;

    Maybe<bool> delete_result = JSReceiver::DeleteElement(receiver, key);
173
    MAYBE_RETURN(delete_result, ReadOnlyRoots(isolate).exception());
174
  }
175

176
  return *isolate->factory()->NewNumberFromUint(result);
177 178 179 180 181 182
}

// 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.
183
V8_WARN_UNUSED_RESULT
184 185
Object RemoveArrayHoles(Isolate* isolate, Handle<JSReceiver> receiver,
                        uint32_t limit) {
186
  if (receiver->IsJSProxy()) {
187
    return RemoveArrayHolesGeneric(isolate, receiver, limit);
188
  }
189 190

  Handle<JSObject> object = Handle<JSObject>::cast(receiver);
191 192
  if (object->HasStringWrapperElements()) {
    int len = String::cast(Handle<JSValue>::cast(object)->value())->length();
193
    DCHECK_LE(len, limit);
194
    return Smi::FromInt(len);
195 196
  }

197
  if (object->HasSloppyArgumentsElements() || !object->map()->is_extensible()) {
198
    return RemoveArrayHolesGeneric(isolate, receiver, limit);
199 200
  }

201 202 203 204
  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.
205
    Handle<NumberDictionary> dict(object->element_dictionary(), isolate);
206 207
    if (object->IsJSArray() || dict->requires_slow_elements() ||
        dict->max_number_key() >= limit) {
208
      return RemoveArrayHolesGeneric(isolate, receiver, limit);
209 210 211 212 213
    }
    // Convert to fast elements.
    Handle<Map> new_map =
        JSObject::GetElementsTransitionMap(object, HOLEY_ELEMENTS);

214 215 216
    AllocationType allocation = ObjectInYoungGeneration(*object)
                                    ? AllocationType::kYoung
                                    : AllocationType::kOld;
217
    Handle<FixedArray> fast_elements =
218
        isolate->factory()->NewFixedArray(dict->NumberOfElements(), allocation);
219 220 221 222 223 224
    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.
225 226 227 228
    // TODO(bmeurer, v8:4153): Change this to size_t later.
    uint32_t array_length =
        static_cast<uint32_t>(Handle<JSTypedArray>::cast(receiver)->length());
    return Smi::FromInt(Min(limit, array_length));
229 230 231 232 233 234 235 236
  } 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.

237
  Handle<FixedArrayBase> elements_base(object->elements(), isolate);
238 239 240 241 242
  uint32_t elements_length = static_cast<uint32_t>(elements_base->length());
  if (limit > elements_length) {
    limit = elements_length;
  }
  if (limit == 0) {
243
    return Smi::kZero;
244 245 246
  }

  uint32_t result = 0;
247
  if (elements_base->map() == ReadOnlyRoots(isolate).fixed_double_array_map()) {
248
    FixedDoubleArray elements = FixedDoubleArray::cast(*elements_base);
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
    // 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 {
275
    FixedArray elements = FixedArray::cast(*elements_base);
276 277 278 279 280 281 282 283 284 285
    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++) {
286
      Object current = elements->get(i);
287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319
      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++;
    }
  }

320
  DCHECK_LE(result, limit);
321
  return *isolate->factory()->NewNumberFromUint(result);
322 323
}

324 325 326
// 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.
327
V8_WARN_UNUSED_RESULT
328 329 330 331 332 333 334 335 336 337 338 339
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(
340
      isolate, source_element, JSReceiver::GetElement(isolate, target, index),
341 342 343 344 345
      Nothing<bool>());

  Handle<Object> set_result;
  ASSIGN_RETURN_ON_EXCEPTION_VALUE(
      isolate, set_result,
346
      Object::SetElement(isolate, target, index, source_element,
347
                         ShouldThrow::kThrowOnError),
348 349 350 351 352 353
      Nothing<bool>());

  return Just(true);
}

// Copy elements in the range 0..length from objects prototype chain
354 355 356 357 358 359
// 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) {
360 361 362 363 364 365
  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) {
366
        MAYBE_RETURN_NULL(ConditionalCopy(isolate, current, object, i));
367 368
      }
    } else {
369 370
      Handle<FixedArray> keys = JSReceiver::GetOwnElementIndices(
          isolate, object, Handle<JSObject>::cast(current));
371 372 373 374 375 376 377 378 379

      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;

380
        MAYBE_RETURN_NULL(ConditionalCopy(isolate, current, object, idx));
381 382 383
      }
    }
  }
384 385 386 387 388 389 390 391 392 393 394 395 396
  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)) {
397
      return ReadOnlyRoots(isolate).exception();
398 399 400 401 402 403
    }
  }

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

415 416 417 418
  // Skip copying from prototype for JSArrays with ElementsProtector intact and
  // the original array prototype.
  if (!object->IsJSArray() || !isolate->IsNoElementsProtectorIntact() ||
      object->map()->prototype() != initial_array_proto) {
419 420 421 422
    RETURN_FAILURE_ON_EXCEPTION(isolate,
                                CopyFromPrototype(isolate, object, length));
  }
  return RemoveArrayHoles(isolate, object, length);
423
}
424 425 426

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

476 477 478 479 480 481
  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) {
482 483 484 485 486 487 488 489
    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))));
  }

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

511
  keys = FixedArray::ShrinkOrEmpty(isolate, keys, j);
512
  return *isolate->factory()->NewJSArrayWithElements(keys);
513 514
}

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

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.
558
  Arguments argv(argc, args.address_of_arg_at(1));
559 560 561 562 563 564 565
  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();
566 567 568

  Factory* factory = isolate->factory();

569 570 571 572 573 574 575 576
  // 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());

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

600 601 602 603
  Handle<Map> initial_map;
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
      isolate, initial_map,
      JSFunction::GetDerivedMap(isolate, constructor, new_target));
604

605 606
  ElementsKind to_kind = can_use_type_feedback ? site->GetElementsKind()
                                               : initial_map->elements_kind();
607
  if (holey && !IsHoleyElementsKind(to_kind)) {
608 609 610 611
    to_kind = GetHoleyElementsKind(to_kind);
    // Update the allocation site info to reflect the advice alteration.
    if (!site.is_null()) site->SetElementsKind(to_kind);
  }
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.
616
  initial_map = Map::AsElementsKind(isolate, initial_map, to_kind);
617 618 619 620

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

625 626
  Handle<JSArray> array = Handle<JSArray>::cast(factory->NewJSObjectFromMap(
      initial_map, AllocationType::kYoung, allocation_site));
627

628 629 630
  factory->NewJSArrayStorage(array, 0, 0, DONT_INITIALIZE_ARRAY_ELEMENTS);

  ElementsKind old_kind = array->GetElementsKind();
631 632
  RETURN_FAILURE_ON_EXCEPTION(isolate,
                              ArrayConstructInitializeElements(array, &argv));
633 634 635 636
  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
637
      // can't be dealt with in the inlined optimized array constructor case.
638 639 640 641 642 643 644 645 646 647 648 649 650 651
      // 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();
      }
    }
652
  }
653

654 655 656 657 658
  return *array;
}

RUNTIME_FUNCTION(Runtime_NormalizeElements) {
  HandleScope scope(isolate);
659
  DCHECK_EQ(1, args.length());
660
  CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
661 662
  CHECK(!array->HasFixedTypedArrayElements());
  CHECK(!array->IsJSGlobalProxy());
663 664 665 666
  JSObject::NormalizeElements(array);
  return *array;
}

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

675
  if (key < 0) return Smi::kZero;
676 677 678 679 680

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

  if (index >= capacity) {
681
    if (!object->GetElementsAccessor()->GrowCapacity(object, index)) {
682
      return Smi::kZero;
683 684 685 686 687 688 689
    }
  }

  return object->elements();
}


690 691
RUNTIME_FUNCTION(Runtime_HasComplexElements) {
  HandleScope scope(isolate);
692
  DCHECK_EQ(1, args.length());
693
  CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
694
  for (PrototypeIterator iter(isolate, array, kStartAtReceiver);
695
       !iter.IsAtEnd(); iter.Advance()) {
696
    if (PrototypeIterator::GetCurrent<JSReceiver>(iter)->HasComplexElements()) {
697
      return ReadOnlyRoots(isolate).true_value();
698 699
    }
  }
700
  return ReadOnlyRoots(isolate).false_value();
701 702
}

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

713
RUNTIME_FUNCTION(Runtime_IsArray) {
714
  SealHandleScope shs(isolate);
715
  DCHECK_EQ(1, args.length());
716 717 718 719
  CONVERT_ARG_CHECKED(Object, obj, 0);
  return isolate->heap()->ToBoolean(obj->IsJSArray());
}

720 721
RUNTIME_FUNCTION(Runtime_ArraySpeciesConstructor) {
  HandleScope scope(isolate);
722
  DCHECK_EQ(1, args.length());
723
  CONVERT_ARG_HANDLE_CHECKED(Object, original_array, 0);
724 725
  RETURN_RESULT_OR_FAILURE(
      isolate, Object::ArraySpeciesConstructor(isolate, original_array));
726 727
}

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

  // 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_,
754 755
          Object::GetProperty(isolate, object,
                              isolate->factory()->length_string()));
756 757 758 759 760 761 762 763

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

764
  if (len == 0) return ReadOnlyRoots(isolate).false_value();
765 766 767

  // Let n be ? ToInteger(fromIndex). (If fromIndex is undefined, this step
  // produces the value 0.)
768 769
  int64_t index = 0;
  if (!from_index->IsUndefined(isolate)) {
770 771 772
    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, from_index,
                                       Object::ToInteger(isolate, from_index));

773
    if (V8_LIKELY(from_index->IsSmi())) {
jgruber's avatar
jgruber committed
774
      int start_from = Smi::ToInt(*from_index);
775 776 777 778 779 780 781 782
      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();
783
      if (start_from >= len) return ReadOnlyRoots(isolate).false_value();
784 785 786 787 788 789 790
      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;
        }
      }
791
    }
792 793

    DCHECK_GE(index, 0);
794 795 796 797
  }

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

831
RUNTIME_FUNCTION(Runtime_ArrayIndexOf) {
832
  HandleScope hs(isolate);
833
  DCHECK_EQ(3, args.length());
834 835 836 837 838
  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;
839 840 841
  ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
      isolate, object,
      Object::ToObject(isolate, args.at(0), "Array.prototype.indexOf"));
842 843 844 845 846 847 848 849 850 851 852 853 854 855

  // 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_,
856 857
          Object::GetProperty(isolate, object,
                              isolate->factory()->length_string()));
858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875

      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);
876 877 878 879 880 881 882
    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();
    }
883 884 885 886 887 888 889 890 891 892 893 894
  }

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

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

  // Otherwise, perform slow lookups for special receiver types
  for (; index < len; ++index) {
910
    HandleScope iteration_hs(isolate);
911 912 913 914 915 916 917 918
    // 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);
919
      Maybe<bool> present = JSReceiver::HasProperty(&it);
920
      MAYBE_RETURN(present, ReadOnlyRoots(isolate).exception());
921
      if (!present.FromJust()) continue;
922 923 924 925 926 927 928 929 930 931
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, element_k,
                                         Object::GetProperty(&it));
      if (search_element->StrictEquals(*element_k)) {
        return *index_obj;
      }
    }
  }
  return Smi::FromInt(-1);
}

932 933
}  // namespace internal
}  // namespace v8