src/runtime/runtime-array.cc

   1 // Copyright 2014 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/v8.h"
   6
   7 #include "src/arguments.h"
   8 #include "src/elements.h"
   9 #include "src/messages.h"
  10 #include "src/runtime/runtime-utils.h"
  11
  12 namespace v8 {
  13 namespace internal {
  14
  15 RUNTIME_FUNCTION(Runtime_FinishArrayPrototypeSetup) {
  16   HandleScope scope(isolate);
  17   DCHECK(args.length() == 1);
  18   CONVERT_ARG_HANDLE_CHECKED(JSArray, prototype, 0);
  19   Object* length = prototype->length();
  20   RUNTIME_ASSERT(length->IsSmi() && Smi::cast(length)->value() == 0);
  21   RUNTIME_ASSERT(prototype->HasFastSmiOrObjectElements());
  22   // This is necessary to enable fast checks for absence of elements
  23   // on Array.prototype and below.
  24   prototype->set_elements(isolate->heap()->empty_fixed_array());
  25   return Smi::FromInt(0);
  26 }
  27
  28
  29 static void InstallBuiltin(Isolate* isolate, Handle<JSObject> holder,
  30                            const char* name, Builtins::Name builtin_name) {
  31   Handle<String> key = isolate->factory()->InternalizeUtf8String(name);
  32   Handle<Code> code(isolate->builtins()->builtin(builtin_name));
  33   Handle<JSFunction> optimized =
  34       isolate->factory()->NewFunctionWithoutPrototype(key, code);
  35   optimized->shared()->DontAdaptArguments();
  36   JSObject::AddProperty(holder, key, optimized, NONE);
  37 }
  38
  39
  40 RUNTIME_FUNCTION(Runtime_SpecialArrayFunctions) {
  41   HandleScope scope(isolate);
  42   DCHECK(args.length() == 0);
  43   Handle<JSObject> holder =
  44       isolate->factory()->NewJSObject(isolate->object_function());
  45
  46   InstallBuiltin(isolate, holder, "pop", Builtins::kArrayPop);
  47   InstallBuiltin(isolate, holder, "push", Builtins::kArrayPush);
  48   InstallBuiltin(isolate, holder, "shift", Builtins::kArrayShift);
  49   InstallBuiltin(isolate, holder, "unshift", Builtins::kArrayUnshift);
  50   InstallBuiltin(isolate, holder, "slice", Builtins::kArraySlice);
  51   InstallBuiltin(isolate, holder, "splice", Builtins::kArraySplice);
  52   InstallBuiltin(isolate, holder, "concat", Builtins::kArrayConcat);
  53
  54   return *holder;
  55 }
  56
  57
  58 RUNTIME_FUNCTION(Runtime_FixedArrayGet) {
  59   SealHandleScope shs(isolate);
  60   DCHECK(args.length() == 2);
  61   CONVERT_ARG_CHECKED(FixedArray, object, 0);
  62   CONVERT_SMI_ARG_CHECKED(index, 1);
  63   return object->get(index);
  64 }
  65
  66
  67 RUNTIME_FUNCTION(Runtime_FixedArraySet) {
  68   SealHandleScope shs(isolate);
  69   DCHECK(args.length() == 3);
  70   CONVERT_ARG_CHECKED(FixedArray, object, 0);
  71   CONVERT_SMI_ARG_CHECKED(index, 1);
  72   CONVERT_ARG_CHECKED(Object, value, 2);
  73   object->set(index, value);
  74   return isolate->heap()->undefined_value();
  75 }
  76
  77
  78 RUNTIME_FUNCTION(Runtime_TransitionElementsKind) {
  79   HandleScope scope(isolate);
  80   RUNTIME_ASSERT(args.length() == 2);
  81   CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
  82   CONVERT_ARG_HANDLE_CHECKED(Map, map, 1);
  83   JSObject::TransitionElementsKind(array, map->elements_kind());
  84   return *array;
  85 }
  86
  87
  88 // Push an object unto an array of objects if it is not already in the
  89 // array.  Returns true if the element was pushed on the stack and
  90 // false otherwise.
  91 RUNTIME_FUNCTION(Runtime_PushIfAbsent) {
  92   HandleScope scope(isolate);
  93   DCHECK(args.length() == 2);
  94   CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
  95   CONVERT_ARG_HANDLE_CHECKED(JSReceiver, element, 1);
  96   RUNTIME_ASSERT(array->HasFastSmiOrObjectElements());
  97   int length = Smi::cast(array->length())->value();
  98   FixedArray* elements = FixedArray::cast(array->elements());
  99   for (int i = 0; i < length; i++) {
 100     if (elements->get(i) == *element) return isolate->heap()->false_value();
 101   }
 102
 103   // Strict not needed. Used for cycle detection in Array join implementation.
 104   RETURN_FAILURE_ON_EXCEPTION(
 105       isolate, JSObject::AddDataElement(array, length, element, NONE));
 106   JSObject::ValidateElements(array);
 107   return isolate->heap()->true_value();
 108 }
 109
 110
 111 /**
 112  * A simple visitor visits every element of Array's.
 113  * The backend storage can be a fixed array for fast elements case,
 114  * or a dictionary for sparse array. Since Dictionary is a subtype
 115  * of FixedArray, the class can be used by both fast and slow cases.
 116  * The second parameter of the constructor, fast_elements, specifies
 117  * whether the storage is a FixedArray or Dictionary.
 118  *
 119  * An index limit is used to deal with the situation that a result array
 120  * length overflows 32-bit non-negative integer.
 121  */
 122 class ArrayConcatVisitor {
 123  public:
 124   ArrayConcatVisitor(Isolate* isolate, Handle<FixedArray> storage,
 125                      bool fast_elements)
 126       : isolate_(isolate),
 127         storage_(Handle<FixedArray>::cast(
 128             isolate->global_handles()->Create(*storage))),
 129         index_offset_(0u),
 130         bit_field_(FastElementsField::encode(fast_elements) |
 131                    ExceedsLimitField::encode(false)) {}
 132
 133   ~ArrayConcatVisitor() { clear_storage(); }
 134
 135   void visit(uint32_t i, Handle<Object> elm) {
 136     if (i > JSObject::kMaxElementCount - index_offset_) {
 137       set_exceeds_array_limit(true);
 138       return;
 139     }
 140     uint32_t index = index_offset_ + i;
 141
 142     if (fast_elements()) {
 143       if (index < static_cast<uint32_t>(storage_->length())) {
 144         storage_->set(index, *elm);
 145         return;
 146       }
 147       // Our initial estimate of length was foiled, possibly by
 148       // getters on the arrays increasing the length of later arrays
 149       // during iteration.
 150       // This shouldn't happen in anything but pathological cases.
 151       SetDictionaryMode();
 152       // Fall-through to dictionary mode.
 153     }
 154     DCHECK(!fast_elements());
 155     Handle<SeededNumberDictionary> dict(
 156         SeededNumberDictionary::cast(*storage_));
 157     Handle<SeededNumberDictionary> result =
 158         SeededNumberDictionary::AtNumberPut(dict, index, elm);
 159     if (!result.is_identical_to(dict)) {
 160       // Dictionary needed to grow.
 161       clear_storage();
 162       set_storage(*result);
 163     }
 164   }
 165
 166   void increase_index_offset(uint32_t delta) {
 167     if (JSObject::kMaxElementCount - index_offset_ < delta) {
 168       index_offset_ = JSObject::kMaxElementCount;
 169     } else {
 170       index_offset_ += delta;
 171     }
 172     // If the initial length estimate was off (see special case in visit()),
 173     // but the array blowing the limit didn't contain elements beyond the
 174     // provided-for index range, go to dictionary mode now.
 175     if (fast_elements() &&
 176         index_offset_ >
 177             static_cast<uint32_t>(FixedArrayBase::cast(*storage_)->length())) {
 178       SetDictionaryMode();
 179     }
 180   }
 181
 182   bool exceeds_array_limit() const {
 183     return ExceedsLimitField::decode(bit_field_);
 184   }
 185
 186   Handle<JSArray> ToArray() {
 187     Handle<JSArray> array = isolate_->factory()->NewJSArray(0);
 188     Handle<Object> length =
 189         isolate_->factory()->NewNumber(static_cast<double>(index_offset_));
 190     Handle<Map> map = JSObject::GetElementsTransitionMap(
 191         array, fast_elements() ? FAST_HOLEY_ELEMENTS : DICTIONARY_ELEMENTS);
 192     array->set_map(*map);
 193     array->set_length(*length);
 194     array->set_elements(*storage_);
 195     return array;
 196   }
 197
 198  private:
 199   // Convert storage to dictionary mode.
 200   void SetDictionaryMode() {
 201     DCHECK(fast_elements());
 202     Handle<FixedArray> current_storage(*storage_);
 203     Handle<SeededNumberDictionary> slow_storage(
 204         SeededNumberDictionary::New(isolate_, current_storage->length()));
 205     uint32_t current_length = static_cast<uint32_t>(current_storage->length());
 206     for (uint32_t i = 0; i < current_length; i++) {
 207       HandleScope loop_scope(isolate_);
 208       Handle<Object> element(current_storage->get(i), isolate_);
 209       if (!element->IsTheHole()) {
 210         Handle<SeededNumberDictionary> new_storage =
 211             SeededNumberDictionary::AtNumberPut(slow_storage, i, element);
 212         if (!new_storage.is_identical_to(slow_storage)) {
 213           slow_storage = loop_scope.CloseAndEscape(new_storage);
 214         }
 215       }
 216     }
 217     clear_storage();
 218     set_storage(*slow_storage);
 219     set_fast_elements(false);
 220   }
 221
 222   inline void clear_storage() {
 223     GlobalHandles::Destroy(Handle<Object>::cast(storage_).location());
 224   }
 225
 226   inline void set_storage(FixedArray* storage) {
 227     storage_ =
 228         Handle<FixedArray>::cast(isolate_->global_handles()->Create(storage));
 229   }
 230
 231   class FastElementsField : public BitField<bool, 0, 1> {};
 232   class ExceedsLimitField : public BitField<bool, 1, 1> {};
 233
 234   bool fast_elements() const { return FastElementsField::decode(bit_field_); }
 235   void set_fast_elements(bool fast) {
 236     bit_field_ = FastElementsField::update(bit_field_, fast);
 237   }
 238   void set_exceeds_array_limit(bool exceeds) {
 239     bit_field_ = ExceedsLimitField::update(bit_field_, exceeds);
 240   }
 241
 242   Isolate* isolate_;
 243   Handle<FixedArray> storage_;  // Always a global handle.
 244   // Index after last seen index. Always less than or equal to
 245   // JSObject::kMaxElementCount.
 246   uint32_t index_offset_;
 247   uint32_t bit_field_;
 248 };
 249
 250
 251 static uint32_t EstimateElementCount(Handle<JSArray> array) {
 252   uint32_t length = static_cast<uint32_t>(array->length()->Number());
 253   int element_count = 0;
 254   switch (array->GetElementsKind()) {
 255     case FAST_SMI_ELEMENTS:
 256     case FAST_HOLEY_SMI_ELEMENTS:
 257     case FAST_ELEMENTS:
 258     case FAST_HOLEY_ELEMENTS: {
 259       // Fast elements can't have lengths that are not representable by
 260       // a 32-bit signed integer.
 261       DCHECK(static_cast<int32_t>(FixedArray::kMaxLength) >= 0);
 262       int fast_length = static_cast<int>(length);
 263       Handle<FixedArray> elements(FixedArray::cast(array->elements()));
 264       for (int i = 0; i < fast_length; i++) {
 265         if (!elements->get(i)->IsTheHole()) element_count++;
 266       }
 267       break;
 268     }
 269     case FAST_DOUBLE_ELEMENTS:
 270     case FAST_HOLEY_DOUBLE_ELEMENTS: {
 271       // Fast elements can't have lengths that are not representable by
 272       // a 32-bit signed integer.
 273       DCHECK(static_cast<int32_t>(FixedDoubleArray::kMaxLength) >= 0);
 274       int fast_length = static_cast<int>(length);
 275       if (array->elements()->IsFixedArray()) {
 276         DCHECK(FixedArray::cast(array->elements())->length() == 0);
 277         break;
 278       }
 279       Handle<FixedDoubleArray> elements(
 280           FixedDoubleArray::cast(array->elements()));
 281       for (int i = 0; i < fast_length; i++) {
 282         if (!elements->is_the_hole(i)) element_count++;
 283       }
 284       break;
 285     }
 286     case DICTIONARY_ELEMENTS: {
 287       Handle<SeededNumberDictionary> dictionary(
 288           SeededNumberDictionary::cast(array->elements()));
 289       int capacity = dictionary->Capacity();
 290       for (int i = 0; i < capacity; i++) {
 291         Handle<Object> key(dictionary->KeyAt(i), array->GetIsolate());
 292         if (dictionary->IsKey(*key)) {
 293           element_count++;
 294         }
 295       }
 296       break;
 297     }
 298     case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
 299     case SLOW_SLOPPY_ARGUMENTS_ELEMENTS:
 300 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
 301   case EXTERNAL_##TYPE##_ELEMENTS:                      \
 302   case TYPE##_ELEMENTS:
 303
 304       TYPED_ARRAYS(TYPED_ARRAY_CASE)
 305 #undef TYPED_ARRAY_CASE
 306       // External arrays are always dense.
 307       return length;
 308   }
 309   // As an estimate, we assume that the prototype doesn't contain any
 310   // inherited elements.
 311   return element_count;
 312 }
 313
 314
 315 template <class ExternalArrayClass, class ElementType>
 316 static void IterateTypedArrayElements(Isolate* isolate,
 317                                       Handle<JSObject> receiver,
 318                                       bool elements_are_ints,
 319                                       bool elements_are_guaranteed_smis,
 320                                       ArrayConcatVisitor* visitor) {
 321   Handle<ExternalArrayClass> array(
 322       ExternalArrayClass::cast(receiver->elements()));
 323   uint32_t len = static_cast<uint32_t>(array->length());
 324
 325   DCHECK(visitor != NULL);
 326   if (elements_are_ints) {
 327     if (elements_are_guaranteed_smis) {
 328       for (uint32_t j = 0; j < len; j++) {
 329         HandleScope loop_scope(isolate);
 330         Handle<Smi> e(Smi::FromInt(static_cast<int>(array->get_scalar(j))),
 331                       isolate);
 332         visitor->visit(j, e);
 333       }
 334     } else {
 335       for (uint32_t j = 0; j < len; j++) {
 336         HandleScope loop_scope(isolate);
 337         int64_t val = static_cast<int64_t>(array->get_scalar(j));
 338         if (Smi::IsValid(static_cast<intptr_t>(val))) {
 339           Handle<Smi> e(Smi::FromInt(static_cast<int>(val)), isolate);
 340           visitor->visit(j, e);
 341         } else {
 342           Handle<Object> e =
 343               isolate->factory()->NewNumber(static_cast<ElementType>(val));
 344           visitor->visit(j, e);
 345         }
 346       }
 347     }
 348   } else {
 349     for (uint32_t j = 0; j < len; j++) {
 350       HandleScope loop_scope(isolate);
 351       Handle<Object> e = isolate->factory()->NewNumber(array->get_scalar(j));
 352       visitor->visit(j, e);
 353     }
 354   }
 355 }
 356
 357
 358 // Used for sorting indices in a List<uint32_t>.
 359 static int compareUInt32(const uint32_t* ap, const uint32_t* bp) {
 360   uint32_t a = *ap;
 361   uint32_t b = *bp;
 362   return (a == b) ? 0 : (a < b) ? -1 : 1;
 363 }
 364
 365
 366 static void CollectElementIndices(Handle<JSObject> object, uint32_t range,
 367                                   List<uint32_t>* indices) {
 368   Isolate* isolate = object->GetIsolate();
 369   ElementsKind kind = object->GetElementsKind();
 370   switch (kind) {
 371     case FAST_SMI_ELEMENTS:
 372     case FAST_ELEMENTS:
 373     case FAST_HOLEY_SMI_ELEMENTS:
 374     case FAST_HOLEY_ELEMENTS: {
 375       Handle<FixedArray> elements(FixedArray::cast(object->elements()));
 376       uint32_t length = static_cast<uint32_t>(elements->length());
 377       if (range < length) length = range;
 378       for (uint32_t i = 0; i < length; i++) {
 379         if (!elements->get(i)->IsTheHole()) {
 380           indices->Add(i);
 381         }
 382       }
 383       break;
 384     }
 385     case FAST_HOLEY_DOUBLE_ELEMENTS:
 386     case FAST_DOUBLE_ELEMENTS: {
 387       if (object->elements()->IsFixedArray()) {
 388         DCHECK(object->elements()->length() == 0);
 389         break;
 390       }
 391       Handle<FixedDoubleArray> elements(
 392           FixedDoubleArray::cast(object->elements()));
 393       uint32_t length = static_cast<uint32_t>(elements->length());
 394       if (range < length) length = range;
 395       for (uint32_t i = 0; i < length; i++) {
 396         if (!elements->is_the_hole(i)) {
 397           indices->Add(i);
 398         }
 399       }
 400       break;
 401     }
 402     case DICTIONARY_ELEMENTS: {
 403       Handle<SeededNumberDictionary> dict(
 404           SeededNumberDictionary::cast(object->elements()));
 405       uint32_t capacity = dict->Capacity();
 406       for (uint32_t j = 0; j < capacity; j++) {
 407         HandleScope loop_scope(isolate);
 408         Handle<Object> k(dict->KeyAt(j), isolate);
 409         if (dict->IsKey(*k)) {
 410           DCHECK(k->IsNumber());
 411           uint32_t index = static_cast<uint32_t>(k->Number());
 412           if (index < range) {
 413             indices->Add(index);
 414           }
 415         }
 416       }
 417       break;
 418     }
 419 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
 420   case TYPE##_ELEMENTS:                                 \
 421   case EXTERNAL_##TYPE##_ELEMENTS:
 422
 423       TYPED_ARRAYS(TYPED_ARRAY_CASE)
 424 #undef TYPED_ARRAY_CASE
 425       {
 426         uint32_t length = static_cast<uint32_t>(
 427             FixedArrayBase::cast(object->elements())->length());
 428         if (range <= length) {
 429           length = range;
 430           // We will add all indices, so we might as well clear it first
 431           // and avoid duplicates.
 432           indices->Clear();
 433         }
 434         for (uint32_t i = 0; i < length; i++) {
 435           indices->Add(i);
 436         }
 437         if (length == range) return;  // All indices accounted for already.
 438         break;
 439       }
 440     case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
 441     case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: {
 442       MaybeHandle<Object> length_obj =
 443           Object::GetProperty(object, isolate->factory()->length_string());
 444       double length_num = length_obj.ToHandleChecked()->Number();
 445       uint32_t length = static_cast<uint32_t>(DoubleToInt32(length_num));
 446       ElementsAccessor* accessor = object->GetElementsAccessor();
 447       for (uint32_t i = 0; i < length; i++) {
 448         if (accessor->HasElement(object, i)) {
 449           indices->Add(i);
 450         }
 451       }
 452       break;
 453     }
 454   }
 455
 456   PrototypeIterator iter(isolate, object);
 457   if (!iter.IsAtEnd()) {
 458     // The prototype will usually have no inherited element indices,
 459     // but we have to check.
 460     CollectElementIndices(
 461         Handle<JSObject>::cast(PrototypeIterator::GetCurrent(iter)), range,
 462         indices);
 463   }
 464 }
 465
 466
 467 static bool IterateElementsSlow(Isolate* isolate, Handle<JSObject> receiver,
 468                                 uint32_t length, ArrayConcatVisitor* visitor) {
 469   for (uint32_t i = 0; i < length; ++i) {
 470     HandleScope loop_scope(isolate);
 471     Maybe<bool> maybe = JSReceiver::HasElement(receiver, i);
 472     if (!maybe.IsJust()) return false;
 473     if (maybe.FromJust()) {
 474       Handle<Object> element_value;
 475       ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_value,
 476                                        Object::GetElement(isolate, receiver, i),
 477                                        false);
 478       visitor->visit(i, element_value);
 479     }
 480   }
 481   visitor->increase_index_offset(length);
 482   return true;
 483 }
 484
 485
 486 /**
 487  * A helper function that visits elements of a JSObject in numerical
 488  * order.
 489  *
 490  * The visitor argument called for each existing element in the array
 491  * with the element index and the element's value.
 492  * Afterwards it increments the base-index of the visitor by the array
 493  * length.
 494  * Returns false if any access threw an exception, otherwise true.
 495  */
 496 static bool IterateElements(Isolate* isolate, Handle<JSObject> receiver,
 497                             ArrayConcatVisitor* visitor) {
 498   uint32_t length = 0;
 499
 500   if (receiver->IsJSArray()) {
 501     Handle<JSArray> array(Handle<JSArray>::cast(receiver));
 502     length = static_cast<uint32_t>(array->length()->Number());
 503   } else {
 504     Handle<Object> val;
 505     Handle<Object> key(isolate->heap()->length_string(), isolate);
 506     ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, val,
 507         Runtime::GetObjectProperty(isolate, receiver, key), false);
 508     // TODO(caitp): Support larger element indexes (up to 2^53-1).
 509     if (!val->ToUint32(&length)) {
 510       ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, val,
 511           Execution::ToLength(isolate, val), false);
 512       val->ToUint32(&length);
 513     }
 514   }
 515
 516   if (!(receiver->IsJSArray() || receiver->IsJSTypedArray())) {
 517     // For classes which are not known to be safe to access via elements alone,
 518     // use the slow case.
 519     return IterateElementsSlow(isolate, receiver, length, visitor);
 520   }
 521
 522   switch (receiver->GetElementsKind()) {
 523     case FAST_SMI_ELEMENTS:
 524     case FAST_ELEMENTS:
 525     case FAST_HOLEY_SMI_ELEMENTS:
 526     case FAST_HOLEY_ELEMENTS: {
 527       // Run through the elements FixedArray and use HasElement and GetElement
 528       // to check the prototype for missing elements.
 529       Handle<FixedArray> elements(FixedArray::cast(receiver->elements()));
 530       int fast_length = static_cast<int>(length);
 531       DCHECK(fast_length <= elements->length());
 532       for (int j = 0; j < fast_length; j++) {
 533         HandleScope loop_scope(isolate);
 534         Handle<Object> element_value(elements->get(j), isolate);
 535         if (!element_value->IsTheHole()) {
 536           visitor->visit(j, element_value);
 537         } else {
 538           Maybe<bool> maybe = JSReceiver::HasElement(receiver, j);
 539           if (!maybe.IsJust()) return false;
 540           if (maybe.FromJust()) {
 541             // Call GetElement on receiver, not its prototype, or getters won't
 542             // have the correct receiver.
 543             ASSIGN_RETURN_ON_EXCEPTION_VALUE(
 544                 isolate, element_value,
 545                 Object::GetElement(isolate, receiver, j), false);
 546             visitor->visit(j, element_value);
 547           }
 548         }
 549       }
 550       break;
 551     }
 552     case FAST_HOLEY_DOUBLE_ELEMENTS:
 553     case FAST_DOUBLE_ELEMENTS: {
 554       // Empty array is FixedArray but not FixedDoubleArray.
 555       if (length == 0) break;
 556       // Run through the elements FixedArray and use HasElement and GetElement
 557       // to check the prototype for missing elements.
 558       if (receiver->elements()->IsFixedArray()) {
 559         DCHECK(receiver->elements()->length() == 0);
 560         break;
 561       }
 562       Handle<FixedDoubleArray> elements(
 563           FixedDoubleArray::cast(receiver->elements()));
 564       int fast_length = static_cast<int>(length);
 565       DCHECK(fast_length <= elements->length());
 566       for (int j = 0; j < fast_length; j++) {
 567         HandleScope loop_scope(isolate);
 568         if (!elements->is_the_hole(j)) {
 569           double double_value = elements->get_scalar(j);
 570           Handle<Object> element_value =
 571               isolate->factory()->NewNumber(double_value);
 572           visitor->visit(j, element_value);
 573         } else {
 574           Maybe<bool> maybe = JSReceiver::HasElement(receiver, j);
 575           if (!maybe.IsJust()) return false;
 576           if (maybe.FromJust()) {
 577             // Call GetElement on receiver, not its prototype, or getters won't
 578             // have the correct receiver.
 579             Handle<Object> element_value;
 580             ASSIGN_RETURN_ON_EXCEPTION_VALUE(
 581                 isolate, element_value,
 582                 Object::GetElement(isolate, receiver, j), false);
 583             visitor->visit(j, element_value);
 584           }
 585         }
 586       }
 587       break;
 588     }
 589     case DICTIONARY_ELEMENTS: {
 590       Handle<SeededNumberDictionary> dict(receiver->element_dictionary());
 591       List<uint32_t> indices(dict->Capacity() / 2);
 592       // Collect all indices in the object and the prototypes less
 593       // than length. This might introduce duplicates in the indices list.
 594       CollectElementIndices(receiver, length, &indices);
 595       indices.Sort(&compareUInt32);
 596       int j = 0;
 597       int n = indices.length();
 598       while (j < n) {
 599         HandleScope loop_scope(isolate);
 600         uint32_t index = indices[j];
 601         Handle<Object> element;
 602         ASSIGN_RETURN_ON_EXCEPTION_VALUE(
 603             isolate, element, Object::GetElement(isolate, receiver, index),
 604             false);
 605         visitor->visit(index, element);
 606         // Skip to next different index (i.e., omit duplicates).
 607         do {
 608           j++;
 609         } while (j < n && indices[j] == index);
 610       }
 611       break;
 612     }
 613     case EXTERNAL_UINT8_CLAMPED_ELEMENTS: {
 614       Handle<ExternalUint8ClampedArray> pixels(
 615           ExternalUint8ClampedArray::cast(receiver->elements()));
 616       for (uint32_t j = 0; j < length; j++) {
 617         Handle<Smi> e(Smi::FromInt(pixels->get_scalar(j)), isolate);
 618         visitor->visit(j, e);
 619       }
 620       break;
 621     }
 622     case UINT8_CLAMPED_ELEMENTS: {
 623       Handle<FixedUint8ClampedArray> pixels(
 624       FixedUint8ClampedArray::cast(receiver->elements()));
 625       for (uint32_t j = 0; j < length; j++) {
 626         Handle<Smi> e(Smi::FromInt(pixels->get_scalar(j)), isolate);
 627         visitor->visit(j, e);
 628       }
 629       break;
 630     }
 631     case EXTERNAL_INT8_ELEMENTS: {
 632       IterateTypedArrayElements<ExternalInt8Array, int8_t>(
 633           isolate, receiver, true, true, visitor);
 634       break;
 635     }
 636     case INT8_ELEMENTS: {
 637       IterateTypedArrayElements<FixedInt8Array, int8_t>(
 638       isolate, receiver, true, true, visitor);
 639       break;
 640     }
 641     case EXTERNAL_UINT8_ELEMENTS: {
 642       IterateTypedArrayElements<ExternalUint8Array, uint8_t>(
 643           isolate, receiver, true, true, visitor);
 644       break;
 645     }
 646     case UINT8_ELEMENTS: {
 647       IterateTypedArrayElements<FixedUint8Array, uint8_t>(
 648       isolate, receiver, true, true, visitor);
 649       break;
 650     }
 651     case EXTERNAL_INT16_ELEMENTS: {
 652       IterateTypedArrayElements<ExternalInt16Array, int16_t>(
 653           isolate, receiver, true, true, visitor);
 654       break;
 655     }
 656     case INT16_ELEMENTS: {
 657       IterateTypedArrayElements<FixedInt16Array, int16_t>(
 658       isolate, receiver, true, true, visitor);
 659       break;
 660     }
 661     case EXTERNAL_UINT16_ELEMENTS: {
 662       IterateTypedArrayElements<ExternalUint16Array, uint16_t>(
 663           isolate, receiver, true, true, visitor);
 664       break;
 665     }
 666     case UINT16_ELEMENTS: {
 667       IterateTypedArrayElements<FixedUint16Array, uint16_t>(
 668       isolate, receiver, true, true, visitor);
 669       break;
 670     }
 671     case EXTERNAL_INT32_ELEMENTS: {
 672       IterateTypedArrayElements<ExternalInt32Array, int32_t>(
 673           isolate, receiver, true, false, visitor);
 674       break;
 675     }
 676     case INT32_ELEMENTS: {
 677       IterateTypedArrayElements<FixedInt32Array, int32_t>(
 678       isolate, receiver, true, false, visitor);
 679       break;
 680     }
 681     case EXTERNAL_UINT32_ELEMENTS: {
 682       IterateTypedArrayElements<ExternalUint32Array, uint32_t>(
 683           isolate, receiver, true, false, visitor);
 684       break;
 685     }
 686     case UINT32_ELEMENTS: {
 687       IterateTypedArrayElements<FixedUint32Array, uint32_t>(
 688       isolate, receiver, true, false, visitor);
 689       break;
 690     }
 691     case EXTERNAL_FLOAT32_ELEMENTS: {
 692       IterateTypedArrayElements<ExternalFloat32Array, float>(
 693           isolate, receiver, false, false, visitor);
 694       break;
 695     }
 696     case FLOAT32_ELEMENTS: {
 697       IterateTypedArrayElements<FixedFloat32Array, float>(
 698       isolate, receiver, false, false, visitor);
 699       break;
 700     }
 701     case EXTERNAL_FLOAT64_ELEMENTS: {
 702       IterateTypedArrayElements<ExternalFloat64Array, double>(
 703           isolate, receiver, false, false, visitor);
 704       break;
 705     }
 706     case FLOAT64_ELEMENTS: {
 707       IterateTypedArrayElements<FixedFloat64Array, double>(
 708       isolate, receiver, false, false, visitor);
 709       break;
 710     }
 711     case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
 712     case SLOW_SLOPPY_ARGUMENTS_ELEMENTS: {
 713       for (uint32_t index = 0; index < length; index++) {
 714         HandleScope loop_scope(isolate);
 715         Handle<Object> element;
 716         ASSIGN_RETURN_ON_EXCEPTION_VALUE(
 717             isolate, element, Object::GetElement(isolate, receiver, index),
 718             false);
 719         visitor->visit(index, element);
 720       }
 721       break;
 722     }
 723   }
 724   visitor->increase_index_offset(length);
 725   return true;
 726 }
 727
 728
 729 static bool IsConcatSpreadable(Isolate* isolate, Handle<Object> obj) {
 730   HandleScope handle_scope(isolate);
 731   if (!obj->IsSpecObject()) return false;
 732   if (FLAG_harmony_concat_spreadable) {
 733     Handle<Symbol> key(isolate->factory()->is_concat_spreadable_symbol());
 734     Handle<Object> value;
 735     MaybeHandle<Object> maybeValue =
 736         i::Runtime::GetObjectProperty(isolate, obj, key);
 737     if (maybeValue.ToHandle(&value)) {
 738       if (!value->IsUndefined()) {
 739         return value->BooleanValue();
 740       }
 741     }
 742   }
 743   return obj->IsJSArray();
 744 }
 745
 746
 747 /**
 748  * Array::concat implementation.
 749  * See ECMAScript 262, 15.4.4.4.
 750  * TODO(581): Fix non-compliance for very large concatenations and update to
 751  * following the ECMAScript 5 specification.
 752  */
 753 RUNTIME_FUNCTION(Runtime_ArrayConcat) {
 754   HandleScope handle_scope(isolate);
 755   DCHECK(args.length() == 1);
 756
 757   CONVERT_ARG_HANDLE_CHECKED(JSArray, arguments, 0);
 758   int argument_count = static_cast<int>(arguments->length()->Number());
 759   RUNTIME_ASSERT(arguments->HasFastObjectElements());
 760   Handle<FixedArray> elements(FixedArray::cast(arguments->elements()));
 761
 762   // Pass 1: estimate the length and number of elements of the result.
 763   // The actual length can be larger if any of the arguments have getters
 764   // that mutate other arguments (but will otherwise be precise).
 765   // The number of elements is precise if there are no inherited elements.
 766
 767   ElementsKind kind = FAST_SMI_ELEMENTS;
 768
 769   uint32_t estimate_result_length = 0;
 770   uint32_t estimate_nof_elements = 0;
 771   for (int i = 0; i < argument_count; i++) {
 772     HandleScope loop_scope(isolate);
 773     Handle<Object> obj(elements->get(i), isolate);
 774     uint32_t length_estimate;
 775     uint32_t element_estimate;
 776     if (obj->IsJSArray()) {
 777       Handle<JSArray> array(Handle<JSArray>::cast(obj));
 778       length_estimate = static_cast<uint32_t>(array->length()->Number());
 779       if (length_estimate != 0) {
 780         ElementsKind array_kind =
 781             GetPackedElementsKind(array->map()->elements_kind());
 782         if (IsMoreGeneralElementsKindTransition(kind, array_kind)) {
 783           kind = array_kind;
 784         }
 785       }
 786       element_estimate = EstimateElementCount(array);
 787     } else {
 788       if (obj->IsHeapObject()) {
 789         if (obj->IsNumber()) {
 790           if (IsMoreGeneralElementsKindTransition(kind, FAST_DOUBLE_ELEMENTS)) {
 791             kind = FAST_DOUBLE_ELEMENTS;
 792           }
 793         } else if (IsMoreGeneralElementsKindTransition(kind, FAST_ELEMENTS)) {
 794           kind = FAST_ELEMENTS;
 795         }
 796       }
 797       length_estimate = 1;
 798       element_estimate = 1;
 799     }
 800     // Avoid overflows by capping at kMaxElementCount.
 801     if (JSObject::kMaxElementCount - estimate_result_length < length_estimate) {
 802       estimate_result_length = JSObject::kMaxElementCount;
 803     } else {
 804       estimate_result_length += length_estimate;
 805     }
 806     if (JSObject::kMaxElementCount - estimate_nof_elements < element_estimate) {
 807       estimate_nof_elements = JSObject::kMaxElementCount;
 808     } else {
 809       estimate_nof_elements += element_estimate;
 810     }
 811   }
 812
 813   // If estimated number of elements is more than half of length, a
 814   // fixed array (fast case) is more time and space-efficient than a
 815   // dictionary.
 816   bool fast_case = (estimate_nof_elements * 2) >= estimate_result_length;
 817
 818   if (fast_case && kind == FAST_DOUBLE_ELEMENTS) {
 819     Handle<FixedArrayBase> storage =
 820         isolate->factory()->NewFixedDoubleArray(estimate_result_length);
 821     int j = 0;
 822     bool failure = false;
 823     if (estimate_result_length > 0) {
 824       Handle<FixedDoubleArray> double_storage =
 825           Handle<FixedDoubleArray>::cast(storage);
 826       for (int i = 0; i < argument_count; i++) {
 827         Handle<Object> obj(elements->get(i), isolate);
 828         if (obj->IsSmi()) {
 829           double_storage->set(j, Smi::cast(*obj)->value());
 830           j++;
 831         } else if (obj->IsNumber()) {
 832           double_storage->set(j, obj->Number());
 833           j++;
 834         } else {
 835           JSArray* array = JSArray::cast(*obj);
 836           uint32_t length = static_cast<uint32_t>(array->length()->Number());
 837           switch (array->map()->elements_kind()) {
 838             case FAST_HOLEY_DOUBLE_ELEMENTS:
 839             case FAST_DOUBLE_ELEMENTS: {
 840               // Empty array is FixedArray but not FixedDoubleArray.
 841               if (length == 0) break;
 842               FixedDoubleArray* elements =
 843                   FixedDoubleArray::cast(array->elements());
 844               for (uint32_t i = 0; i < length; i++) {
 845                 if (elements->is_the_hole(i)) {
 846                   // TODO(jkummerow/verwaest): We could be a bit more clever
 847                   // here: Check if there are no elements/getters on the
 848                   // prototype chain, and if so, allow creation of a holey
 849                   // result array.
 850                   // Same thing below (holey smi case).
 851                   failure = true;
 852                   break;
 853                 }
 854                 double double_value = elements->get_scalar(i);
 855                 double_storage->set(j, double_value);
 856                 j++;
 857               }
 858               break;
 859             }
 860             case FAST_HOLEY_SMI_ELEMENTS:
 861             case FAST_SMI_ELEMENTS: {
 862               FixedArray* elements(FixedArray::cast(array->elements()));
 863               for (uint32_t i = 0; i < length; i++) {
 864                 Object* element = elements->get(i);
 865                 if (element->IsTheHole()) {
 866                   failure = true;
 867                   break;
 868                 }
 869                 int32_t int_value = Smi::cast(element)->value();
 870                 double_storage->set(j, int_value);
 871                 j++;
 872               }
 873               break;
 874             }
 875             case FAST_HOLEY_ELEMENTS:
 876             case FAST_ELEMENTS:
 877             case DICTIONARY_ELEMENTS:
 878               DCHECK_EQ(0u, length);
 879               break;
 880             default:
 881               UNREACHABLE();
 882           }
 883         }
 884         if (failure) break;
 885       }
 886     }
 887     if (!failure) {
 888       Handle<JSArray> array = isolate->factory()->NewJSArray(0);
 889       Smi* length = Smi::FromInt(j);
 890       Handle<Map> map;
 891       map = JSObject::GetElementsTransitionMap(array, kind);
 892       array->set_map(*map);
 893       array->set_length(length);
 894       array->set_elements(*storage);
 895       return *array;
 896     }
 897     // In case of failure, fall through.
 898   }
 899
 900   Handle<FixedArray> storage;
 901   if (fast_case) {
 902     // The backing storage array must have non-existing elements to preserve
 903     // holes across concat operations.
 904     storage =
 905         isolate->factory()->NewFixedArrayWithHoles(estimate_result_length);
 906   } else {
 907     // TODO(126): move 25% pre-allocation logic into Dictionary::Allocate
 908     uint32_t at_least_space_for =
 909         estimate_nof_elements + (estimate_nof_elements >> 2);
 910     storage = Handle<FixedArray>::cast(
 911         SeededNumberDictionary::New(isolate, at_least_space_for));
 912   }
 913
 914   ArrayConcatVisitor visitor(isolate, storage, fast_case);
 915
 916   for (int i = 0; i < argument_count; i++) {
 917     Handle<Object> obj(elements->get(i), isolate);
 918     bool spreadable = IsConcatSpreadable(isolate, obj);
 919     if (isolate->has_pending_exception()) return isolate->heap()->exception();
 920     if (spreadable) {
 921       Handle<JSObject> object = Handle<JSObject>::cast(obj);
 922       if (!IterateElements(isolate, object, &visitor)) {
 923         return isolate->heap()->exception();
 924       }
 925     } else {
 926       visitor.visit(0, obj);
 927       visitor.increase_index_offset(1);
 928     }
 929   }
 930
 931   if (visitor.exceeds_array_limit()) {
 932     THROW_NEW_ERROR_RETURN_FAILURE(
 933         isolate, NewRangeError(MessageTemplate::kInvalidArrayLength));
 934   }
 935   return *visitor.ToArray();
 936 }
 937
 938
 939 // Moves all own elements of an object, that are below a limit, to positions
 940 // starting at zero. All undefined values are placed after non-undefined values,
 941 // and are followed by non-existing element. Does not change the length
 942 // property.
 943 // Returns the number of non-undefined elements collected.
 944 // Returns -1 if hole removal is not supported by this method.
 945 RUNTIME_FUNCTION(Runtime_RemoveArrayHoles) {
 946   HandleScope scope(isolate);
 947   DCHECK(args.length() == 2);
 948   CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
 949   CONVERT_NUMBER_CHECKED(uint32_t, limit, Uint32, args[1]);
 950   return *JSObject::PrepareElementsForSort(object, limit);
 951 }
 952
 953
 954 // Move contents of argument 0 (an array) to argument 1 (an array)
 955 RUNTIME_FUNCTION(Runtime_MoveArrayContents) {
 956   HandleScope scope(isolate);
 957   DCHECK(args.length() == 2);
 958   CONVERT_ARG_HANDLE_CHECKED(JSArray, from, 0);
 959   CONVERT_ARG_HANDLE_CHECKED(JSArray, to, 1);
 960   JSObject::ValidateElements(from);
 961   JSObject::ValidateElements(to);
 962
 963   Handle<FixedArrayBase> new_elements(from->elements());
 964   ElementsKind from_kind = from->GetElementsKind();
 965   Handle<Map> new_map = JSObject::GetElementsTransitionMap(to, from_kind);
 966   JSObject::SetMapAndElements(to, new_map, new_elements);
 967   to->set_length(from->length());
 968
 969   JSObject::ResetElements(from);
 970   from->set_length(Smi::FromInt(0));
 971
 972   JSObject::ValidateElements(to);
 973   return *to;
 974 }
 975
 976
 977 // How many elements does this object/array have?
 978 RUNTIME_FUNCTION(Runtime_EstimateNumberOfElements) {
 979   HandleScope scope(isolate);
 980   DCHECK(args.length() == 1);
 981   CONVERT_ARG_HANDLE_CHECKED(JSArray, array, 0);
 982   Handle<FixedArrayBase> elements(array->elements(), isolate);
 983   SealHandleScope shs(isolate);
 984   if (elements->IsDictionary()) {
 985     int result =
 986         Handle<SeededNumberDictionary>::cast(elements)->NumberOfElements();
 987     return Smi::FromInt(result);
 988   } else {
 989     DCHECK(array->length()->IsSmi());
 990     // For packed elements, we know the exact number of elements
 991     int length = elements->length();
 992     ElementsKind kind = array->GetElementsKind();
 993     if (IsFastPackedElementsKind(kind)) {
 994       return Smi::FromInt(length);
 995     }
 996     // For holey elements, take samples from the buffer checking for holes
 997     // to generate the estimate.
 998     const int kNumberOfHoleCheckSamples = 97;
 999     int increment = (length < kNumberOfHoleCheckSamples)
1000                         ? 1
1001                         : static_cast<int>(length / kNumberOfHoleCheckSamples);
1002     ElementsAccessor* accessor = array->GetElementsAccessor();
1003     int holes = 0;
1004     for (int i = 0; i < length; i += increment) {
1005       if (!accessor->HasElement(array, i, elements)) {
1006         ++holes;
1007       }
1008     }
1009     int estimate = static_cast<int>((kNumberOfHoleCheckSamples - holes) /
1010                                     kNumberOfHoleCheckSamples * length);
1011     return Smi::FromInt(estimate);
1012   }
1013 }
1014
1015
1016 // Returns an array that tells you where in the [0, length) interval an array
1017 // might have elements.  Can either return an array of keys (positive integers
1018 // or undefined) or a number representing the positive length of an interval
1019 // starting at index 0.
1020 // Intervals can span over some keys that are not in the object.
1021 RUNTIME_FUNCTION(Runtime_GetArrayKeys) {
1022   HandleScope scope(isolate);
1023   DCHECK(args.length() == 2);
1024   CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
1025   CONVERT_NUMBER_CHECKED(uint32_t, length, Uint32, args[1]);
1026   if (array->elements()->IsDictionary()) {
1027     Handle<FixedArray> keys = isolate->factory()->empty_fixed_array();
1028     for (PrototypeIterator iter(isolate, array,
1029                                 PrototypeIterator::START_AT_RECEIVER);
1030          !iter.IsAtEnd(); iter.Advance()) {
1031       if (PrototypeIterator::GetCurrent(iter)->IsJSProxy() ||
1032           JSObject::cast(*PrototypeIterator::GetCurrent(iter))
1033               ->HasIndexedInterceptor()) {
1034         // Bail out if we find a proxy or interceptor, likely not worth
1035         // collecting keys in that case.
1036         return *isolate->factory()->NewNumberFromUint(length);
1037       }
1038       Handle<JSObject> current =
1039           Handle<JSObject>::cast(PrototypeIterator::GetCurrent(iter));
1040       Handle<FixedArray> current_keys =
1041           isolate->factory()->NewFixedArray(current->NumberOfOwnElements(NONE));
1042       current->GetOwnElementKeys(*current_keys, NONE);
1043       ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
1044           isolate, keys, FixedArray::UnionOfKeys(keys, current_keys));
1045     }
1046     // Erase any keys >= length.
1047     // TODO(adamk): Remove this step when the contract of %GetArrayKeys
1048     // is changed to let this happen on the JS side.
1049     for (int i = 0; i < keys->length(); i++) {
1050       if (NumberToUint32(keys->get(i)) >= length) keys->set_undefined(i);
1051     }
1052     return *isolate->factory()->NewJSArrayWithElements(keys);
1053   } else {
1054     RUNTIME_ASSERT(array->HasFastSmiOrObjectElements() ||
1055                    array->HasFastDoubleElements());
1056     uint32_t actual_length = static_cast<uint32_t>(array->elements()->length());
1057     return *isolate->factory()->NewNumberFromUint(Min(actual_length, length));
1058   }
1059 }
1060
1061
1062 static Object* ArrayConstructorCommon(Isolate* isolate,
1063                                       Handle<JSFunction> constructor,
1064                                       Handle<JSFunction> original_constructor,
1065                                       Handle<AllocationSite> site,
1066                                       Arguments* caller_args) {
1067   Factory* factory = isolate->factory();
1068
1069   bool holey = false;
1070   bool can_use_type_feedback = true;
1071   bool can_inline_array_constructor = true;
1072   if (caller_args->length() == 1) {
1073     Handle<Object> argument_one = caller_args->at<Object>(0);
1074     if (argument_one->IsSmi()) {
1075       int value = Handle<Smi>::cast(argument_one)->value();
1076       if (value < 0 ||
1077           JSArray::SetLengthWouldNormalize(isolate->heap(), value)) {
1078         // the array is a dictionary in this case.
1079         can_use_type_feedback = false;
1080       } else if (value != 0) {
1081         holey = true;
1082         if (value >= JSObject::kInitialMaxFastElementArray) {
1083           can_inline_array_constructor = false;
1084         }
1085       }
1086     } else {
1087       // Non-smi length argument produces a dictionary
1088       can_use_type_feedback = false;
1089     }
1090   }
1091
1092   Handle<JSArray> array;
1093   if (!site.is_null() && can_use_type_feedback) {
1094     ElementsKind to_kind = site->GetElementsKind();
1095     if (holey && !IsFastHoleyElementsKind(to_kind)) {
1096       to_kind = GetHoleyElementsKind(to_kind);
1097       // Update the allocation site info to reflect the advice alteration.
1098       site->SetElementsKind(to_kind);
1099     }
1100
1101     // We should allocate with an initial map that reflects the allocation site
1102     // advice. Therefore we use AllocateJSObjectFromMap instead of passing
1103     // the constructor.
1104     Handle<Map> initial_map(constructor->initial_map(), isolate);
1105     if (to_kind != initial_map->elements_kind()) {
1106       initial_map = Map::AsElementsKind(initial_map, to_kind);
1107     }
1108
1109     // If we don't care to track arrays of to_kind ElementsKind, then
1110     // don't emit a memento for them.
1111     Handle<AllocationSite> allocation_site;
1112     if (AllocationSite::GetMode(to_kind) == TRACK_ALLOCATION_SITE) {
1113       allocation_site = site;
1114     }
1115
1116     array = Handle<JSArray>::cast(
1117         factory->NewJSObjectFromMap(initial_map, NOT_TENURED, allocation_site));
1118   } else {
1119     array = Handle<JSArray>::cast(factory->NewJSObject(constructor));
1120
1121     // We might need to transition to holey
1122     ElementsKind kind = constructor->initial_map()->elements_kind();
1123     if (holey && !IsFastHoleyElementsKind(kind)) {
1124       kind = GetHoleyElementsKind(kind);
1125       JSObject::TransitionElementsKind(array, kind);
1126     }
1127   }
1128
1129   factory->NewJSArrayStorage(array, 0, 0, DONT_INITIALIZE_ARRAY_ELEMENTS);
1130
1131   ElementsKind old_kind = array->GetElementsKind();
1132   RETURN_FAILURE_ON_EXCEPTION(
1133       isolate, ArrayConstructInitializeElements(array, caller_args));
1134   if (!site.is_null() &&
1135       (old_kind != array->GetElementsKind() || !can_use_type_feedback ||
1136        !can_inline_array_constructor)) {
1137     // The arguments passed in caused a transition. This kind of complexity
1138     // can't be dealt with in the inlined hydrogen array constructor case.
1139     // We must mark the allocationsite as un-inlinable.
1140     site->SetDoNotInlineCall();
1141   }
1142
1143   // Set up the prototoype using original function.
1144   // TODO(dslomov): instead of setting the __proto__,
1145   // use and cache the correct map.
1146   if (*original_constructor != *constructor) {
1147     if (original_constructor->has_instance_prototype()) {
1148       Handle<Object> prototype =
1149           handle(original_constructor->instance_prototype(), isolate);
1150       RETURN_FAILURE_ON_EXCEPTION(
1151           isolate, JSObject::SetPrototype(array, prototype, false));
1152     }
1153   }
1154
1155   return *array;
1156 }
1157
1158
1159 RUNTIME_FUNCTION(Runtime_ArrayConstructor) {
1160   HandleScope scope(isolate);
1161   // If we get 2 arguments then they are the stub parameters (constructor, type
1162   // info).  If we get 4, then the first one is a pointer to the arguments
1163   // passed by the caller, and the last one is the length of the arguments
1164   // passed to the caller (redundant, but useful to check on the deoptimizer
1165   // with an assert).
1166   Arguments empty_args(0, NULL);
1167   bool no_caller_args = args.length() == 2;
1168   DCHECK(no_caller_args || args.length() == 4);
1169   int parameters_start = no_caller_args ? 0 : 1;
1170   Arguments* caller_args =
1171       no_caller_args ? &empty_args : reinterpret_cast<Arguments*>(args[0]);
1172   CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, parameters_start);
1173   CONVERT_ARG_HANDLE_CHECKED(Object, type_info, parameters_start + 1);
1174 #ifdef DEBUG
1175   if (!no_caller_args) {
1176     CONVERT_SMI_ARG_CHECKED(arg_count, parameters_start + 2);
1177     DCHECK(arg_count == caller_args->length());
1178   }
1179 #endif
1180
1181   Handle<AllocationSite> site;
1182   if (!type_info.is_null() &&
1183       *type_info != isolate->heap()->undefined_value()) {
1184     site = Handle<AllocationSite>::cast(type_info);
1185     DCHECK(!site->SitePointsToLiteral());
1186   }
1187
1188   return ArrayConstructorCommon(isolate, constructor, constructor, site,
1189                                 caller_args);
1190 }
1191
1192
1193 RUNTIME_FUNCTION(Runtime_ArrayConstructorWithSubclassing) {
1194   HandleScope scope(isolate);
1195   int args_length = args.length();
1196   CHECK(args_length >= 2);
1197
1198   // This variables and checks work around -Werror=strict-overflow.
1199   int pre_last_arg_index = args_length - 2;
1200   int last_arg_index = args_length - 1;
1201   CHECK(pre_last_arg_index >= 0);
1202   CHECK(last_arg_index >= 0);
1203
1204   CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, pre_last_arg_index);
1205   CONVERT_ARG_HANDLE_CHECKED(JSFunction, original_constructor, last_arg_index);
1206   Arguments caller_args(args_length - 2, args.arguments());
1207   return ArrayConstructorCommon(isolate, constructor, original_constructor,
1208                                 Handle<AllocationSite>::null(), &caller_args);
1209 }
1210
1211
1212 RUNTIME_FUNCTION(Runtime_InternalArrayConstructor) {
1213   HandleScope scope(isolate);
1214   Arguments empty_args(0, NULL);
1215   bool no_caller_args = args.length() == 1;
1216   DCHECK(no_caller_args || args.length() == 3);
1217   int parameters_start = no_caller_args ? 0 : 1;
1218   Arguments* caller_args =
1219       no_caller_args ? &empty_args : reinterpret_cast<Arguments*>(args[0]);
1220   CONVERT_ARG_HANDLE_CHECKED(JSFunction, constructor, parameters_start);
1221 #ifdef DEBUG
1222   if (!no_caller_args) {
1223     CONVERT_SMI_ARG_CHECKED(arg_count, parameters_start + 1);
1224     DCHECK(arg_count == caller_args->length());
1225   }
1226 #endif
1227   return ArrayConstructorCommon(isolate, constructor, constructor,
1228                                 Handle<AllocationSite>::null(), caller_args);
1229 }
1230
1231
1232 RUNTIME_FUNCTION(Runtime_NormalizeElements) {
1233   HandleScope scope(isolate);
1234   DCHECK(args.length() == 1);
1235   CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
1236   RUNTIME_ASSERT(!array->HasExternalArrayElements() &&
1237                  !array->HasFixedTypedArrayElements() &&
1238                  !array->IsJSGlobalProxy());
1239   JSObject::NormalizeElements(array);
1240   return *array;
1241 }
1242
1243
1244 // GrowArrayElements returns a sentinel Smi if the object was normalized.
1245 RUNTIME_FUNCTION(Runtime_GrowArrayElements) {
1246   HandleScope scope(isolate);
1247   DCHECK(args.length() == 2);
1248   CONVERT_ARG_HANDLE_CHECKED(JSObject, object, 0);
1249   CONVERT_NUMBER_CHECKED(int, key, Int32, args[1]);
1250
1251   if (key < 0) {
1252     return object->elements();
1253   }
1254
1255   uint32_t capacity = static_cast<uint32_t>(object->elements()->length());
1256   uint32_t index = static_cast<uint32_t>(key);
1257
1258   if (index >= capacity) {
1259     if (object->WouldConvertToSlowElements(index)) {
1260       // We don't want to allow operations that cause lazy deopt. Return a Smi
1261       // as a signal that optimized code should eagerly deoptimize.
1262       return Smi::FromInt(0);
1263     }
1264
1265     uint32_t new_capacity = JSObject::NewElementsCapacity(index + 1);
1266     object->GetElementsAccessor()->GrowCapacityAndConvert(object, new_capacity);
1267   }
1268
1269   // On success, return the fixed array elements.
1270   return object->elements();
1271 }
1272
1273
1274 RUNTIME_FUNCTION(Runtime_HasComplexElements) {
1275   HandleScope scope(isolate);
1276   DCHECK(args.length() == 1);
1277   CONVERT_ARG_HANDLE_CHECKED(JSObject, array, 0);
1278   for (PrototypeIterator iter(isolate, array,
1279                               PrototypeIterator::START_AT_RECEIVER);
1280        !iter.IsAtEnd(); iter.Advance()) {
1281     if (PrototypeIterator::GetCurrent(iter)->IsJSProxy()) {
1282       return isolate->heap()->true_value();
1283     }
1284     Handle<JSObject> current =
1285         Handle<JSObject>::cast(PrototypeIterator::GetCurrent(iter));
1286     if (current->HasIndexedInterceptor()) {
1287       return isolate->heap()->true_value();
1288     }
1289     if (!current->HasDictionaryElements()) continue;
1290     if (current->element_dictionary()->HasComplexElements()) {
1291       return isolate->heap()->true_value();
1292     }
1293   }
1294   return isolate->heap()->false_value();
1295 }
1296
1297
1298 RUNTIME_FUNCTION(Runtime_IsArray) {
1299   SealHandleScope shs(isolate);
1300   DCHECK(args.length() == 1);
1301   CONVERT_ARG_CHECKED(Object, obj, 0);
1302   return isolate->heap()->ToBoolean(obj->IsJSArray());
1303 }
1304
1305
1306 RUNTIME_FUNCTION(Runtime_HasCachedArrayIndex) {
1307   SealHandleScope shs(isolate);
1308   DCHECK(args.length() == 1);
1309   return isolate->heap()->false_value();
1310 }
1311
1312
1313 RUNTIME_FUNCTION(Runtime_GetCachedArrayIndex) {
1314   // This can never be reached, because Runtime_HasCachedArrayIndex always
1315   // returns false.
1316   UNIMPLEMENTED();
1317   return nullptr;
1318 }
1319
1320
1321 RUNTIME_FUNCTION(Runtime_FastOneByteArrayJoin) {
1322   SealHandleScope shs(isolate);
1323   DCHECK(args.length() == 2);
1324   // Returning undefined means that this fast path fails and one has to resort
1325   // to a slow path.
1326   return isolate->heap()->undefined_value();
1327 }
1328 }  // namespace internal
1329 }  // namespace v8