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