src/elements.cc

   1 // Copyright 2012 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/conversions.h"
   9 #include "src/elements.h"
  10 #include "src/messages.h"
  11 #include "src/objects.h"
  12 #include "src/utils.h"
  13
  14 // Each concrete ElementsAccessor can handle exactly one ElementsKind,
  15 // several abstract ElementsAccessor classes are used to allow sharing
  16 // common code.
  17 //
  18 // Inheritance hierarchy:
  19 // - ElementsAccessorBase                        (abstract)
  20 //   - FastElementsAccessor                      (abstract)
  21 //     - FastSmiOrObjectElementsAccessor
  22 //       - FastPackedSmiElementsAccessor
  23 //       - FastHoleySmiElementsAccessor
  24 //       - FastPackedObjectElementsAccessor
  25 //       - FastHoleyObjectElementsAccessor
  26 //     - FastDoubleElementsAccessor
  27 //       - FastPackedDoubleElementsAccessor
  28 //       - FastHoleyDoubleElementsAccessor
  29 //   - TypedElementsAccessor: template, with instantiations:
  30 //     - ExternalInt8ElementsAccessor
  31 //     - ExternalUint8ElementsAccessor
  32 //     - ExternalInt16ElementsAccessor
  33 //     - ExternalUint16ElementsAccessor
  34 //     - ExternalInt32ElementsAccessor
  35 //     - ExternalUint32ElementsAccessor
  36 //     - ExternalFloat32ElementsAccessor
  37 //     - ExternalFloat64ElementsAccessor
  38 //     - ExternalUint8ClampedElementsAccessor
  39 //     - FixedUint8ElementsAccessor
  40 //     - FixedInt8ElementsAccessor
  41 //     - FixedUint16ElementsAccessor
  42 //     - FixedInt16ElementsAccessor
  43 //     - FixedUint32ElementsAccessor
  44 //     - FixedInt32ElementsAccessor
  45 //     - FixedFloat32ElementsAccessor
  46 //     - FixedFloat64ElementsAccessor
  47 //     - FixedUint8ClampedElementsAccessor
  48 //   - DictionaryElementsAccessor
  49 //   - SloppyArgumentsElementsAccessor
  50 //     - FastSloppyArgumentsElementsAccessor
  51 //     - SlowSloppyArgumentsElementsAccessor
  52
  53
  54 namespace v8 {
  55 namespace internal {
  56
  57
  58 namespace {
  59
  60
  61 static const int kPackedSizeNotKnown = -1;
  62
  63
  64 // First argument in list is the accessor class, the second argument is the
  65 // accessor ElementsKind, and the third is the backing store class.  Use the
  66 // fast element handler for smi-only arrays.  The implementation is currently
  67 // identical.  Note that the order must match that of the ElementsKind enum for
  68 // the |accessor_array[]| below to work.
  69 #define ELEMENTS_LIST(V)                                                      \
  70   V(FastPackedSmiElementsAccessor, FAST_SMI_ELEMENTS, FixedArray)             \
  71   V(FastHoleySmiElementsAccessor, FAST_HOLEY_SMI_ELEMENTS, FixedArray)        \
  72   V(FastPackedObjectElementsAccessor, FAST_ELEMENTS, FixedArray)              \
  73   V(FastHoleyObjectElementsAccessor, FAST_HOLEY_ELEMENTS, FixedArray)         \
  74   V(FastPackedDoubleElementsAccessor, FAST_DOUBLE_ELEMENTS, FixedDoubleArray) \
  75   V(FastHoleyDoubleElementsAccessor, FAST_HOLEY_DOUBLE_ELEMENTS,              \
  76     FixedDoubleArray)                                                         \
  77   V(DictionaryElementsAccessor, DICTIONARY_ELEMENTS, SeededNumberDictionary)  \
  78   V(FastSloppyArgumentsElementsAccessor, FAST_SLOPPY_ARGUMENTS_ELEMENTS,      \
  79     FixedArray)                                                               \
  80   V(SlowSloppyArgumentsElementsAccessor, SLOW_SLOPPY_ARGUMENTS_ELEMENTS,      \
  81     FixedArray)                                                               \
  82   V(ExternalInt8ElementsAccessor, EXTERNAL_INT8_ELEMENTS, ExternalInt8Array)  \
  83   V(ExternalUint8ElementsAccessor, EXTERNAL_UINT8_ELEMENTS,                   \
  84     ExternalUint8Array)                                                       \
  85   V(ExternalInt16ElementsAccessor, EXTERNAL_INT16_ELEMENTS,                   \
  86     ExternalInt16Array)                                                       \
  87   V(ExternalUint16ElementsAccessor, EXTERNAL_UINT16_ELEMENTS,                 \
  88     ExternalUint16Array)                                                      \
  89   V(ExternalInt32ElementsAccessor, EXTERNAL_INT32_ELEMENTS,                   \
  90     ExternalInt32Array)                                                       \
  91   V(ExternalUint32ElementsAccessor, EXTERNAL_UINT32_ELEMENTS,                 \
  92     ExternalUint32Array)                                                      \
  93   V(ExternalFloat32ElementsAccessor, EXTERNAL_FLOAT32_ELEMENTS,               \
  94     ExternalFloat32Array)                                                     \
  95   V(ExternalFloat64ElementsAccessor, EXTERNAL_FLOAT64_ELEMENTS,               \
  96     ExternalFloat64Array)                                                     \
  97   V(ExternalUint8ClampedElementsAccessor, EXTERNAL_UINT8_CLAMPED_ELEMENTS,    \
  98     ExternalUint8ClampedArray)                                                \
  99   V(FixedUint8ElementsAccessor, UINT8_ELEMENTS, FixedUint8Array)              \
 100   V(FixedInt8ElementsAccessor, INT8_ELEMENTS, FixedInt8Array)                 \
 101   V(FixedUint16ElementsAccessor, UINT16_ELEMENTS, FixedUint16Array)           \
 102   V(FixedInt16ElementsAccessor, INT16_ELEMENTS, FixedInt16Array)              \
 103   V(FixedUint32ElementsAccessor, UINT32_ELEMENTS, FixedUint32Array)           \
 104   V(FixedInt32ElementsAccessor, INT32_ELEMENTS, FixedInt32Array)              \
 105   V(FixedFloat32ElementsAccessor, FLOAT32_ELEMENTS, FixedFloat32Array)        \
 106   V(FixedFloat64ElementsAccessor, FLOAT64_ELEMENTS, FixedFloat64Array)        \
 107   V(FixedUint8ClampedElementsAccessor, UINT8_CLAMPED_ELEMENTS,                \
 108     FixedUint8ClampedArray)
 109
 110
 111 template<ElementsKind Kind> class ElementsKindTraits {
 112  public:
 113   typedef FixedArrayBase BackingStore;
 114 };
 115
 116 #define ELEMENTS_TRAITS(Class, KindParam, Store)               \
 117 template<> class ElementsKindTraits<KindParam> {               \
 118  public:   /* NOLINT */                                        \
 119   static const ElementsKind Kind = KindParam;                  \
 120   typedef Store BackingStore;                                  \
 121 };
 122 ELEMENTS_LIST(ELEMENTS_TRAITS)
 123 #undef ELEMENTS_TRAITS
 124
 125
 126 static bool HasIndex(Handle<FixedArray> array, Handle<Object> index_handle) {
 127   DisallowHeapAllocation no_gc;
 128   Object* index = *index_handle;
 129   int len0 = array->length();
 130   for (int i = 0; i < len0; i++) {
 131     Object* element = array->get(i);
 132     if (index->KeyEquals(element)) return true;
 133   }
 134   return false;
 135 }
 136
 137
 138 MUST_USE_RESULT
 139 static MaybeHandle<Object> ThrowArrayLengthRangeError(Isolate* isolate) {
 140   THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kInvalidArrayLength),
 141                   Object);
 142 }
 143
 144
 145 static void CopyObjectToObjectElements(FixedArrayBase* from_base,
 146                                        ElementsKind from_kind,
 147                                        uint32_t from_start,
 148                                        FixedArrayBase* to_base,
 149                                        ElementsKind to_kind, uint32_t to_start,
 150                                        int raw_copy_size) {
 151   DCHECK(to_base->map() !=
 152       from_base->GetIsolate()->heap()->fixed_cow_array_map());
 153   DisallowHeapAllocation no_allocation;
 154   int copy_size = raw_copy_size;
 155   if (raw_copy_size < 0) {
 156     DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
 157            raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
 158     copy_size = Min(from_base->length() - from_start,
 159                     to_base->length() - to_start);
 160     if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
 161       int start = to_start + copy_size;
 162       int length = to_base->length() - start;
 163       if (length > 0) {
 164         Heap* heap = from_base->GetHeap();
 165         MemsetPointer(FixedArray::cast(to_base)->data_start() + start,
 166                       heap->the_hole_value(), length);
 167       }
 168     }
 169   }
 170   DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
 171          (copy_size + static_cast<int>(from_start)) <= from_base->length());
 172   if (copy_size == 0) return;
 173   FixedArray* from = FixedArray::cast(from_base);
 174   FixedArray* to = FixedArray::cast(to_base);
 175   DCHECK(IsFastSmiOrObjectElementsKind(from_kind));
 176   DCHECK(IsFastSmiOrObjectElementsKind(to_kind));
 177   Address to_address = to->address() + FixedArray::kHeaderSize;
 178   Address from_address = from->address() + FixedArray::kHeaderSize;
 179   CopyWords(reinterpret_cast<Object**>(to_address) + to_start,
 180             reinterpret_cast<Object**>(from_address) + from_start,
 181             static_cast<size_t>(copy_size));
 182   if (IsFastObjectElementsKind(from_kind) &&
 183       IsFastObjectElementsKind(to_kind)) {
 184     Heap* heap = from->GetHeap();
 185     if (!heap->InNewSpace(to)) {
 186       heap->RecordWrites(to->address(),
 187                          to->OffsetOfElementAt(to_start),
 188                          copy_size);
 189     }
 190     heap->incremental_marking()->RecordWrites(to);
 191   }
 192 }
 193
 194
 195 static void CopyDictionaryToObjectElements(
 196     FixedArrayBase* from_base, uint32_t from_start, FixedArrayBase* to_base,
 197     ElementsKind to_kind, uint32_t to_start, int raw_copy_size) {
 198   DisallowHeapAllocation no_allocation;
 199   SeededNumberDictionary* from = SeededNumberDictionary::cast(from_base);
 200   int copy_size = raw_copy_size;
 201   Heap* heap = from->GetHeap();
 202   if (raw_copy_size < 0) {
 203     DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
 204            raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
 205     copy_size = from->max_number_key() + 1 - from_start;
 206     if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
 207       int start = to_start + copy_size;
 208       int length = to_base->length() - start;
 209       if (length > 0) {
 210         Heap* heap = from->GetHeap();
 211         MemsetPointer(FixedArray::cast(to_base)->data_start() + start,
 212                       heap->the_hole_value(), length);
 213       }
 214     }
 215   }
 216   DCHECK(to_base != from_base);
 217   DCHECK(IsFastSmiOrObjectElementsKind(to_kind));
 218   if (copy_size == 0) return;
 219   FixedArray* to = FixedArray::cast(to_base);
 220   uint32_t to_length = to->length();
 221   if (to_start + copy_size > to_length) {
 222     copy_size = to_length - to_start;
 223   }
 224   for (int i = 0; i < copy_size; i++) {
 225     int entry = from->FindEntry(i + from_start);
 226     if (entry != SeededNumberDictionary::kNotFound) {
 227       Object* value = from->ValueAt(entry);
 228       DCHECK(!value->IsTheHole());
 229       to->set(i + to_start, value, SKIP_WRITE_BARRIER);
 230     } else {
 231       to->set_the_hole(i + to_start);
 232     }
 233   }
 234   if (IsFastObjectElementsKind(to_kind)) {
 235     if (!heap->InNewSpace(to)) {
 236       heap->RecordWrites(to->address(),
 237                          to->OffsetOfElementAt(to_start),
 238                          copy_size);
 239     }
 240     heap->incremental_marking()->RecordWrites(to);
 241   }
 242 }
 243
 244
 245 // NOTE: this method violates the handlified function signature convention:
 246 // raw pointer parameters in the function that allocates.
 247 // See ElementsAccessorBase::CopyElements() for details.
 248 static void CopyDoubleToObjectElements(FixedArrayBase* from_base,
 249                                        uint32_t from_start,
 250                                        FixedArrayBase* to_base,
 251                                        ElementsKind to_kind, uint32_t to_start,
 252                                        int raw_copy_size) {
 253   DCHECK(IsFastSmiOrObjectElementsKind(to_kind));
 254   int copy_size = raw_copy_size;
 255   if (raw_copy_size < 0) {
 256     DisallowHeapAllocation no_allocation;
 257     DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
 258            raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
 259     copy_size = Min(from_base->length() - from_start,
 260                     to_base->length() - to_start);
 261     if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
 262       // Also initialize the area that will be copied over since HeapNumber
 263       // allocation below can cause an incremental marking step, requiring all
 264       // existing heap objects to be propertly initialized.
 265       int start = to_start;
 266       int length = to_base->length() - start;
 267       if (length > 0) {
 268         Heap* heap = from_base->GetHeap();
 269         MemsetPointer(FixedArray::cast(to_base)->data_start() + start,
 270                       heap->the_hole_value(), length);
 271       }
 272     }
 273   }
 274   DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
 275          (copy_size + static_cast<int>(from_start)) <= from_base->length());
 276   if (copy_size == 0) return;
 277
 278   // From here on, the code below could actually allocate. Therefore the raw
 279   // values are wrapped into handles.
 280   Isolate* isolate = from_base->GetIsolate();
 281   Handle<FixedDoubleArray> from(FixedDoubleArray::cast(from_base), isolate);
 282   Handle<FixedArray> to(FixedArray::cast(to_base), isolate);
 283   for (int i = 0; i < copy_size; ++i) {
 284     HandleScope scope(isolate);
 285     if (IsFastSmiElementsKind(to_kind)) {
 286       UNIMPLEMENTED();
 287     } else {
 288       DCHECK(IsFastObjectElementsKind(to_kind));
 289       Handle<Object> value = FixedDoubleArray::get(from, i + from_start);
 290       to->set(i + to_start, *value, UPDATE_WRITE_BARRIER);
 291     }
 292   }
 293 }
 294
 295
 296 static void CopyDoubleToDoubleElements(FixedArrayBase* from_base,
 297                                        uint32_t from_start,
 298                                        FixedArrayBase* to_base,
 299                                        uint32_t to_start, int raw_copy_size) {
 300   DisallowHeapAllocation no_allocation;
 301   int copy_size = raw_copy_size;
 302   if (raw_copy_size < 0) {
 303     DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
 304            raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
 305     copy_size = Min(from_base->length() - from_start,
 306                     to_base->length() - to_start);
 307     if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
 308       for (int i = to_start + copy_size; i < to_base->length(); ++i) {
 309         FixedDoubleArray::cast(to_base)->set_the_hole(i);
 310       }
 311     }
 312   }
 313   DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
 314          (copy_size + static_cast<int>(from_start)) <= from_base->length());
 315   if (copy_size == 0) return;
 316   FixedDoubleArray* from = FixedDoubleArray::cast(from_base);
 317   FixedDoubleArray* to = FixedDoubleArray::cast(to_base);
 318   Address to_address = to->address() + FixedDoubleArray::kHeaderSize;
 319   Address from_address = from->address() + FixedDoubleArray::kHeaderSize;
 320   to_address += kDoubleSize * to_start;
 321   from_address += kDoubleSize * from_start;
 322   int words_per_double = (kDoubleSize / kPointerSize);
 323   CopyWords(reinterpret_cast<Object**>(to_address),
 324             reinterpret_cast<Object**>(from_address),
 325             static_cast<size_t>(words_per_double * copy_size));
 326 }
 327
 328
 329 static void CopySmiToDoubleElements(FixedArrayBase* from_base,
 330                                     uint32_t from_start,
 331                                     FixedArrayBase* to_base, uint32_t to_start,
 332                                     int raw_copy_size) {
 333   DisallowHeapAllocation no_allocation;
 334   int copy_size = raw_copy_size;
 335   if (raw_copy_size < 0) {
 336     DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
 337            raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
 338     copy_size = from_base->length() - from_start;
 339     if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
 340       for (int i = to_start + copy_size; i < to_base->length(); ++i) {
 341         FixedDoubleArray::cast(to_base)->set_the_hole(i);
 342       }
 343     }
 344   }
 345   DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
 346          (copy_size + static_cast<int>(from_start)) <= from_base->length());
 347   if (copy_size == 0) return;
 348   FixedArray* from = FixedArray::cast(from_base);
 349   FixedDoubleArray* to = FixedDoubleArray::cast(to_base);
 350   Object* the_hole = from->GetHeap()->the_hole_value();
 351   for (uint32_t from_end = from_start + static_cast<uint32_t>(copy_size);
 352        from_start < from_end; from_start++, to_start++) {
 353     Object* hole_or_smi = from->get(from_start);
 354     if (hole_or_smi == the_hole) {
 355       to->set_the_hole(to_start);
 356     } else {
 357       to->set(to_start, Smi::cast(hole_or_smi)->value());
 358     }
 359   }
 360 }
 361
 362
 363 static void CopyPackedSmiToDoubleElements(FixedArrayBase* from_base,
 364                                           uint32_t from_start,
 365                                           FixedArrayBase* to_base,
 366                                           uint32_t to_start, int packed_size,
 367                                           int raw_copy_size) {
 368   DisallowHeapAllocation no_allocation;
 369   int copy_size = raw_copy_size;
 370   uint32_t to_end;
 371   if (raw_copy_size < 0) {
 372     DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
 373            raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
 374     copy_size = packed_size - from_start;
 375     if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
 376       to_end = to_base->length();
 377       for (uint32_t i = to_start + copy_size; i < to_end; ++i) {
 378         FixedDoubleArray::cast(to_base)->set_the_hole(i);
 379       }
 380     } else {
 381       to_end = to_start + static_cast<uint32_t>(copy_size);
 382     }
 383   } else {
 384     to_end = to_start + static_cast<uint32_t>(copy_size);
 385   }
 386   DCHECK(static_cast<int>(to_end) <= to_base->length());
 387   DCHECK(packed_size >= 0 && packed_size <= copy_size);
 388   DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
 389          (copy_size + static_cast<int>(from_start)) <= from_base->length());
 390   if (copy_size == 0) return;
 391   FixedArray* from = FixedArray::cast(from_base);
 392   FixedDoubleArray* to = FixedDoubleArray::cast(to_base);
 393   for (uint32_t from_end = from_start + static_cast<uint32_t>(packed_size);
 394        from_start < from_end; from_start++, to_start++) {
 395     Object* smi = from->get(from_start);
 396     DCHECK(!smi->IsTheHole());
 397     to->set(to_start, Smi::cast(smi)->value());
 398   }
 399 }
 400
 401
 402 static void CopyObjectToDoubleElements(FixedArrayBase* from_base,
 403                                        uint32_t from_start,
 404                                        FixedArrayBase* to_base,
 405                                        uint32_t to_start, int raw_copy_size) {
 406   DisallowHeapAllocation no_allocation;
 407   int copy_size = raw_copy_size;
 408   if (raw_copy_size < 0) {
 409     DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
 410            raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
 411     copy_size = from_base->length() - from_start;
 412     if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
 413       for (int i = to_start + copy_size; i < to_base->length(); ++i) {
 414         FixedDoubleArray::cast(to_base)->set_the_hole(i);
 415       }
 416     }
 417   }
 418   DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
 419          (copy_size + static_cast<int>(from_start)) <= from_base->length());
 420   if (copy_size == 0) return;
 421   FixedArray* from = FixedArray::cast(from_base);
 422   FixedDoubleArray* to = FixedDoubleArray::cast(to_base);
 423   Object* the_hole = from->GetHeap()->the_hole_value();
 424   for (uint32_t from_end = from_start + copy_size;
 425        from_start < from_end; from_start++, to_start++) {
 426     Object* hole_or_object = from->get(from_start);
 427     if (hole_or_object == the_hole) {
 428       to->set_the_hole(to_start);
 429     } else {
 430       to->set(to_start, hole_or_object->Number());
 431     }
 432   }
 433 }
 434
 435
 436 static void CopyDictionaryToDoubleElements(FixedArrayBase* from_base,
 437                                            uint32_t from_start,
 438                                            FixedArrayBase* to_base,
 439                                            uint32_t to_start,
 440                                            int raw_copy_size) {
 441   DisallowHeapAllocation no_allocation;
 442   SeededNumberDictionary* from = SeededNumberDictionary::cast(from_base);
 443   int copy_size = raw_copy_size;
 444   if (copy_size < 0) {
 445     DCHECK(copy_size == ElementsAccessor::kCopyToEnd ||
 446            copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
 447     copy_size = from->max_number_key() + 1 - from_start;
 448     if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
 449       for (int i = to_start + copy_size; i < to_base->length(); ++i) {
 450         FixedDoubleArray::cast(to_base)->set_the_hole(i);
 451       }
 452     }
 453   }
 454   if (copy_size == 0) return;
 455   FixedDoubleArray* to = FixedDoubleArray::cast(to_base);
 456   uint32_t to_length = to->length();
 457   if (to_start + copy_size > to_length) {
 458     copy_size = to_length - to_start;
 459   }
 460   for (int i = 0; i < copy_size; i++) {
 461     int entry = from->FindEntry(i + from_start);
 462     if (entry != SeededNumberDictionary::kNotFound) {
 463       to->set(i + to_start, from->ValueAt(entry)->Number());
 464     } else {
 465       to->set_the_hole(i + to_start);
 466     }
 467   }
 468 }
 469
 470
 471 static void TraceTopFrame(Isolate* isolate) {
 472   StackFrameIterator it(isolate);
 473   if (it.done()) {
 474     PrintF("unknown location (no JavaScript frames present)");
 475     return;
 476   }
 477   StackFrame* raw_frame = it.frame();
 478   if (raw_frame->is_internal()) {
 479     Code* apply_builtin = isolate->builtins()->builtin(
 480         Builtins::kFunctionApply);
 481     if (raw_frame->unchecked_code() == apply_builtin) {
 482       PrintF("apply from ");
 483       it.Advance();
 484       raw_frame = it.frame();
 485     }
 486   }
 487   JavaScriptFrame::PrintTop(isolate, stdout, false, true);
 488 }
 489
 490
 491 // Base class for element handler implementations. Contains the
 492 // the common logic for objects with different ElementsKinds.
 493 // Subclasses must specialize method for which the element
 494 // implementation differs from the base class implementation.
 495 //
 496 // This class is intended to be used in the following way:
 497 //
 498 //   class SomeElementsAccessor :
 499 //       public ElementsAccessorBase<SomeElementsAccessor,
 500 //                                   BackingStoreClass> {
 501 //     ...
 502 //   }
 503 //
 504 // This is an example of the Curiously Recurring Template Pattern (see
 505 // http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern).  We use
 506 // CRTP to guarantee aggressive compile time optimizations (i.e.  inlining and
 507 // specialization of SomeElementsAccessor methods).
 508 template <typename ElementsAccessorSubclass,
 509           typename ElementsTraitsParam>
 510 class ElementsAccessorBase : public ElementsAccessor {
 511  public:
 512   explicit ElementsAccessorBase(const char* name)
 513       : ElementsAccessor(name) { }
 514
 515   typedef ElementsTraitsParam ElementsTraits;
 516   typedef typename ElementsTraitsParam::BackingStore BackingStore;
 517
 518   static ElementsKind kind() { return ElementsTraits::Kind; }
 519
 520   static void ValidateContents(Handle<JSObject> holder, int length) {
 521   }
 522
 523   static void ValidateImpl(Handle<JSObject> holder) {
 524     Handle<FixedArrayBase> fixed_array_base(holder->elements());
 525     if (!fixed_array_base->IsHeapObject()) return;
 526     // Arrays that have been shifted in place can't be verified.
 527     if (fixed_array_base->IsFiller()) return;
 528     int length = 0;
 529     if (holder->IsJSArray()) {
 530       Object* length_obj = Handle<JSArray>::cast(holder)->length();
 531       if (length_obj->IsSmi()) {
 532         length = Smi::cast(length_obj)->value();
 533       }
 534     } else {
 535       length = fixed_array_base->length();
 536     }
 537     ElementsAccessorSubclass::ValidateContents(holder, length);
 538   }
 539
 540   void Validate(Handle<JSObject> holder) final {
 541     DisallowHeapAllocation no_gc;
 542     ElementsAccessorSubclass::ValidateImpl(holder);
 543   }
 544
 545   virtual bool HasElement(Handle<JSObject> holder, uint32_t index,
 546                           Handle<FixedArrayBase> backing_store) final {
 547     return ElementsAccessorSubclass::GetEntryForIndexImpl(
 548                *holder, *backing_store, index) != kMaxUInt32;
 549   }
 550
 551   virtual Handle<Object> Get(Handle<FixedArrayBase> backing_store,
 552                              uint32_t entry) final {
 553     return ElementsAccessorSubclass::GetImpl(backing_store, entry);
 554   }
 555
 556   static Handle<Object> GetImpl(Handle<FixedArrayBase> backing_store,
 557                                 uint32_t entry) {
 558     uint32_t index = GetIndexForEntryImpl(*backing_store, entry);
 559     return BackingStore::get(Handle<BackingStore>::cast(backing_store), index);
 560   }
 561
 562   virtual void Set(FixedArrayBase* backing_store, uint32_t entry,
 563                    Object* value) final {
 564     ElementsAccessorSubclass::SetImpl(backing_store, entry, value);
 565   }
 566
 567   static void SetImpl(FixedArrayBase* backing_store, uint32_t entry,
 568                       Object* value) {
 569     BackingStore::cast(backing_store)->SetValue(entry, value);
 570   }
 571
 572   virtual void Reconfigure(Handle<JSObject> object,
 573                            Handle<FixedArrayBase> store, uint32_t entry,
 574                            Handle<Object> value,
 575                            PropertyAttributes attributes) final {
 576     ElementsAccessorSubclass::ReconfigureImpl(object, store, entry, value,
 577                                               attributes);
 578   }
 579
 580   static void ReconfigureImpl(Handle<JSObject> object,
 581                               Handle<FixedArrayBase> store, uint32_t entry,
 582                               Handle<Object> value,
 583                               PropertyAttributes attributes) {
 584     UNREACHABLE();
 585   }
 586
 587   virtual void Add(Handle<JSObject> object, uint32_t index,
 588                    Handle<Object> value, PropertyAttributes attributes,
 589                    uint32_t new_capacity) final {
 590     ElementsAccessorSubclass::AddImpl(object, index, value, attributes,
 591                                       new_capacity);
 592   }
 593
 594   static void AddImpl(Handle<JSObject> object, uint32_t index,
 595                       Handle<Object> value, PropertyAttributes attributes,
 596                       uint32_t new_capacity) {
 597     UNREACHABLE();
 598   }
 599
 600   virtual void SetLength(Handle<JSArray> array, uint32_t length) final {
 601     ElementsAccessorSubclass::SetLengthImpl(array, length,
 602                                             handle(array->elements()));
 603   }
 604
 605   static void SetLengthImpl(Handle<JSArray> array, uint32_t length,
 606                             Handle<FixedArrayBase> backing_store);
 607
 608   static Handle<FixedArrayBase> ConvertElementsWithCapacity(
 609       Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
 610       ElementsKind from_kind, uint32_t capacity) {
 611     Isolate* isolate = object->GetIsolate();
 612     Handle<FixedArrayBase> elements;
 613     if (IsFastDoubleElementsKind(kind())) {
 614       elements = isolate->factory()->NewFixedDoubleArray(capacity);
 615     } else {
 616       elements = isolate->factory()->NewUninitializedFixedArray(capacity);
 617     }
 618
 619     int packed = kPackedSizeNotKnown;
 620     if (IsFastPackedElementsKind(from_kind) && object->IsJSArray()) {
 621       packed = Smi::cast(JSArray::cast(*object)->length())->value();
 622     }
 623
 624     ElementsAccessorSubclass::CopyElementsImpl(
 625         *old_elements, 0, *elements, from_kind, 0, packed,
 626         ElementsAccessor::kCopyToEndAndInitializeToHole);
 627     return elements;
 628   }
 629
 630   static void GrowCapacityAndConvertImpl(Handle<JSObject> object,
 631                                          uint32_t capacity) {
 632     ElementsKind from_kind = object->GetElementsKind();
 633     if (IsFastSmiOrObjectElementsKind(from_kind)) {
 634       // Array optimizations rely on the prototype lookups of Array objects
 635       // always returning undefined. If there is a store to the initial
 636       // prototype object, make sure all of these optimizations are invalidated.
 637       object->GetIsolate()->UpdateArrayProtectorOnSetLength(object);
 638     }
 639     Handle<FixedArrayBase> old_elements(object->elements());
 640     // This method should only be called if there's a reason to update the
 641     // elements.
 642     DCHECK(IsFastDoubleElementsKind(from_kind) !=
 643                IsFastDoubleElementsKind(kind()) ||
 644            IsDictionaryElementsKind(from_kind) ||
 645            static_cast<uint32_t>(old_elements->length()) < capacity);
 646     Handle<FixedArrayBase> elements =
 647         ConvertElementsWithCapacity(object, old_elements, from_kind, capacity);
 648
 649     ElementsKind to_kind = kind();
 650     if (IsHoleyElementsKind(from_kind)) to_kind = GetHoleyElementsKind(to_kind);
 651     Handle<Map> new_map = JSObject::GetElementsTransitionMap(object, to_kind);
 652     JSObject::SetMapAndElements(object, new_map, elements);
 653
 654     // Transition through the allocation site as well if present.
 655     JSObject::UpdateAllocationSite(object, to_kind);
 656
 657     if (FLAG_trace_elements_transitions) {
 658       JSObject::PrintElementsTransition(stdout, object, from_kind, old_elements,
 659                                         to_kind, elements);
 660     }
 661   }
 662
 663   virtual void GrowCapacityAndConvert(Handle<JSObject> object,
 664                                       uint32_t capacity) final {
 665     ElementsAccessorSubclass::GrowCapacityAndConvertImpl(object, capacity);
 666   }
 667
 668   virtual void Delete(Handle<JSObject> obj, uint32_t entry) final {
 669     ElementsAccessorSubclass::DeleteImpl(obj, entry);
 670   }
 671
 672   static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start,
 673                                FixedArrayBase* to, ElementsKind from_kind,
 674                                uint32_t to_start, int packed_size,
 675                                int copy_size) {
 676     UNREACHABLE();
 677   }
 678
 679   virtual void CopyElements(Handle<FixedArrayBase> from, uint32_t from_start,
 680                             ElementsKind from_kind, Handle<FixedArrayBase> to,
 681                             uint32_t to_start, int copy_size) final {
 682     DCHECK(!from.is_null());
 683     // NOTE: the ElementsAccessorSubclass::CopyElementsImpl() methods
 684     // violate the handlified function signature convention:
 685     // raw pointer parameters in the function that allocates. This is done
 686     // intentionally to avoid ArrayConcat() builtin performance degradation.
 687     // See the comment in another ElementsAccessorBase::CopyElements() for
 688     // details.
 689     ElementsAccessorSubclass::CopyElementsImpl(*from, from_start, *to,
 690                                                from_kind, to_start,
 691                                                kPackedSizeNotKnown, copy_size);
 692   }
 693
 694   virtual void CopyElements(JSObject* from_holder, uint32_t from_start,
 695                             ElementsKind from_kind, Handle<FixedArrayBase> to,
 696                             uint32_t to_start, int copy_size) final {
 697     int packed_size = kPackedSizeNotKnown;
 698     bool is_packed = IsFastPackedElementsKind(from_kind) &&
 699         from_holder->IsJSArray();
 700     if (is_packed) {
 701       packed_size =
 702           Smi::cast(JSArray::cast(from_holder)->length())->value();
 703       if (copy_size >= 0 && packed_size > copy_size) {
 704         packed_size = copy_size;
 705       }
 706     }
 707     FixedArrayBase* from = from_holder->elements();
 708     // NOTE: the ElementsAccessorSubclass::CopyElementsImpl() methods
 709     // violate the handlified function signature convention:
 710     // raw pointer parameters in the function that allocates. This is done
 711     // intentionally to avoid ArrayConcat() builtin performance degradation.
 712     //
 713     // Details: The idea is that allocations actually happen only in case of
 714     // copying from object with fast double elements to object with object
 715     // elements. In all the other cases there are no allocations performed and
 716     // handle creation causes noticeable performance degradation of the builtin.
 717     ElementsAccessorSubclass::CopyElementsImpl(
 718         from, from_start, *to, from_kind, to_start, packed_size, copy_size);
 719   }
 720
 721   virtual Handle<FixedArray> AddElementsToFixedArray(
 722       Handle<JSObject> receiver, Handle<FixedArray> to,
 723       FixedArray::KeyFilter filter) final {
 724     Handle<FixedArrayBase> from(receiver->elements());
 725
 726     int len0 = to->length();
 727 #ifdef ENABLE_SLOW_DCHECKS
 728     if (FLAG_enable_slow_asserts) {
 729       for (int i = 0; i < len0; i++) {
 730         DCHECK(!to->get(i)->IsTheHole());
 731       }
 732     }
 733 #endif
 734
 735     // Optimize if 'other' is empty.
 736     // We cannot optimize if 'this' is empty, as other may have holes.
 737     uint32_t len1 = ElementsAccessorSubclass::GetCapacityImpl(*receiver, *from);
 738     if (len1 == 0) return to;
 739
 740     Isolate* isolate = from->GetIsolate();
 741
 742     // Compute how many elements are not in other.
 743     uint32_t extra = 0;
 744     for (uint32_t y = 0; y < len1; y++) {
 745       if (ElementsAccessorSubclass::HasEntryImpl(*from, y)) {
 746         Handle<Object> value = ElementsAccessorSubclass::GetImpl(from, y);
 747
 748         DCHECK(!value->IsTheHole());
 749         DCHECK(!value->IsAccessorPair());
 750         DCHECK(!value->IsExecutableAccessorInfo());
 751         if (filter == FixedArray::NON_SYMBOL_KEYS && value->IsSymbol()) {
 752           continue;
 753         }
 754         if (!HasIndex(to, value)) {
 755           extra++;
 756         }
 757       }
 758     }
 759
 760     if (extra == 0) return to;
 761
 762     // Allocate the result
 763     Handle<FixedArray> result = isolate->factory()->NewFixedArray(len0 + extra);
 764
 765     // Fill in the content
 766     {
 767       DisallowHeapAllocation no_gc;
 768       WriteBarrierMode mode = result->GetWriteBarrierMode(no_gc);
 769       for (int i = 0; i < len0; i++) {
 770         Object* e = to->get(i);
 771         DCHECK(e->IsString() || e->IsNumber());
 772         result->set(i, e, mode);
 773       }
 774     }
 775     // Fill in the extra values.
 776     uint32_t entry = 0;
 777     for (uint32_t y = 0; y < len1; y++) {
 778       if (ElementsAccessorSubclass::HasEntryImpl(*from, y)) {
 779         Handle<Object> value = ElementsAccessorSubclass::GetImpl(from, y);
 780         DCHECK(!value->IsAccessorPair());
 781         DCHECK(!value->IsExecutableAccessorInfo());
 782         if (filter == FixedArray::NON_SYMBOL_KEYS && value->IsSymbol()) {
 783           continue;
 784         }
 785         if (!value->IsTheHole() && !HasIndex(to, value)) {
 786           result->set(len0 + entry, *value);
 787           entry++;
 788         }
 789       }
 790     }
 791     DCHECK(extra == entry);
 792     return result;
 793   }
 794
 795   static uint32_t GetCapacityImpl(JSObject* holder,
 796                                   FixedArrayBase* backing_store) {
 797     return backing_store->length();
 798   }
 799
 800   uint32_t GetCapacity(JSObject* holder, FixedArrayBase* backing_store) final {
 801     return ElementsAccessorSubclass::GetCapacityImpl(holder, backing_store);
 802   }
 803
 804   static bool HasEntryImpl(FixedArrayBase* backing_store, uint32_t entry) {
 805     return true;
 806   }
 807
 808   static uint32_t GetIndexForEntryImpl(FixedArrayBase* backing_store,
 809                                        uint32_t entry) {
 810     return entry;
 811   }
 812
 813   static uint32_t GetEntryForIndexImpl(JSObject* holder,
 814                                        FixedArrayBase* backing_store,
 815                                        uint32_t index) {
 816     if (IsHoleyElementsKind(kind())) {
 817       return index < ElementsAccessorSubclass::GetCapacityImpl(holder,
 818                                                                backing_store) &&
 819                      !BackingStore::cast(backing_store)->is_the_hole(index)
 820                  ? index
 821                  : kMaxUInt32;
 822     } else {
 823       Smi* smi_length = Smi::cast(JSArray::cast(holder)->length());
 824       uint32_t length = static_cast<uint32_t>(smi_length->value());
 825       return index < length ? index : kMaxUInt32;
 826     }
 827   }
 828
 829   virtual uint32_t GetEntryForIndex(JSObject* holder,
 830                                     FixedArrayBase* backing_store,
 831                                     uint32_t index) final {
 832     return ElementsAccessorSubclass::GetEntryForIndexImpl(holder, backing_store,
 833                                                           index);
 834   }
 835
 836   static PropertyDetails GetDetailsImpl(FixedArrayBase* backing_store,
 837                                         uint32_t entry) {
 838     return PropertyDetails(NONE, DATA, 0, PropertyCellType::kNoCell);
 839   }
 840
 841   virtual PropertyDetails GetDetails(FixedArrayBase* backing_store,
 842                                      uint32_t entry) final {
 843     return ElementsAccessorSubclass::GetDetailsImpl(backing_store, entry);
 844   }
 845
 846  private:
 847   DISALLOW_COPY_AND_ASSIGN(ElementsAccessorBase);
 848 };
 849
 850
 851 class DictionaryElementsAccessor
 852     : public ElementsAccessorBase<DictionaryElementsAccessor,
 853                                   ElementsKindTraits<DICTIONARY_ELEMENTS> > {
 854  public:
 855   explicit DictionaryElementsAccessor(const char* name)
 856       : ElementsAccessorBase<DictionaryElementsAccessor,
 857                              ElementsKindTraits<DICTIONARY_ELEMENTS> >(name) {}
 858
 859   static void SetLengthImpl(Handle<JSArray> array, uint32_t length,
 860                             Handle<FixedArrayBase> backing_store) {
 861     Handle<SeededNumberDictionary> dict =
 862         Handle<SeededNumberDictionary>::cast(backing_store);
 863     Isolate* isolate = array->GetIsolate();
 864     int capacity = dict->Capacity();
 865     uint32_t old_length = 0;
 866     CHECK(array->length()->ToArrayLength(&old_length));
 867     if (length < old_length) {
 868       if (dict->requires_slow_elements()) {
 869         // Find last non-deletable element in range of elements to be
 870         // deleted and adjust range accordingly.
 871         for (int entry = 0; entry < capacity; entry++) {
 872           DisallowHeapAllocation no_gc;
 873           Object* index = dict->KeyAt(entry);
 874           if (index->IsNumber()) {
 875             uint32_t number = static_cast<uint32_t>(index->Number());
 876             if (length <= number && number < old_length) {
 877               PropertyDetails details = dict->DetailsAt(entry);
 878               if (!details.IsConfigurable()) length = number + 1;
 879             }
 880           }
 881         }
 882       }
 883
 884       if (length == 0) {
 885         // Flush the backing store.
 886         JSObject::ResetElements(array);
 887       } else {
 888         DisallowHeapAllocation no_gc;
 889         // Remove elements that should be deleted.
 890         int removed_entries = 0;
 891         Handle<Object> the_hole_value = isolate->factory()->the_hole_value();
 892         for (int entry = 0; entry < capacity; entry++) {
 893           Object* index = dict->KeyAt(entry);
 894           if (index->IsNumber()) {
 895             uint32_t number = static_cast<uint32_t>(index->Number());
 896             if (length <= number && number < old_length) {
 897               dict->SetEntry(entry, the_hole_value, the_hole_value);
 898               removed_entries++;
 899             }
 900           }
 901         }
 902
 903         // Update the number of elements.
 904         dict->ElementsRemoved(removed_entries);
 905       }
 906     }
 907
 908     Handle<Object> length_obj = isolate->factory()->NewNumberFromUint(length);
 909     array->set_length(*length_obj);
 910   }
 911
 912   static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start,
 913                                FixedArrayBase* to, ElementsKind from_kind,
 914                                uint32_t to_start, int packed_size,
 915                                int copy_size) {
 916     UNREACHABLE();
 917   }
 918
 919
 920   static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) {
 921     // TODO(verwaest): Remove reliance on index in Shrink.
 922     Handle<SeededNumberDictionary> dict(
 923         SeededNumberDictionary::cast(obj->elements()));
 924     uint32_t index = GetIndexForEntryImpl(*dict, entry);
 925     Handle<Object> result = SeededNumberDictionary::DeleteProperty(dict, entry);
 926     USE(result);
 927     DCHECK(result->IsTrue());
 928     Handle<FixedArray> new_elements =
 929         SeededNumberDictionary::Shrink(dict, index);
 930     obj->set_elements(*new_elements);
 931   }
 932
 933   static Object* GetRaw(FixedArrayBase* store, uint32_t entry) {
 934     SeededNumberDictionary* backing_store = SeededNumberDictionary::cast(store);
 935     return backing_store->ValueAt(entry);
 936   }
 937
 938   static Handle<Object> GetImpl(Handle<FixedArrayBase> store, uint32_t entry) {
 939     Isolate* isolate = store->GetIsolate();
 940     return handle(GetRaw(*store, entry), isolate);
 941   }
 942
 943   static void SetImpl(FixedArrayBase* store, uint32_t entry, Object* value) {
 944     SeededNumberDictionary* dictionary = SeededNumberDictionary::cast(store);
 945     dictionary->ValueAtPut(entry, value);
 946   }
 947
 948   static void ReconfigureImpl(Handle<JSObject> object,
 949                               Handle<FixedArrayBase> store, uint32_t entry,
 950                               Handle<Object> value,
 951                               PropertyAttributes attributes) {
 952     SeededNumberDictionary* dictionary = SeededNumberDictionary::cast(*store);
 953     if (attributes != NONE) object->RequireSlowElements(dictionary);
 954     dictionary->ValueAtPut(entry, *value);
 955     PropertyDetails details = dictionary->DetailsAt(entry);
 956     details = PropertyDetails(attributes, DATA, details.dictionary_index(),
 957                               PropertyCellType::kNoCell);
 958     dictionary->DetailsAtPut(entry, details);
 959   }
 960
 961   static void AddImpl(Handle<JSObject> object, uint32_t index,
 962                       Handle<Object> value, PropertyAttributes attributes,
 963                       uint32_t new_capacity) {
 964     PropertyDetails details(attributes, DATA, 0, PropertyCellType::kNoCell);
 965     Handle<SeededNumberDictionary> dictionary =
 966         object->HasFastElements()
 967             ? JSObject::NormalizeElements(object)
 968             : handle(SeededNumberDictionary::cast(object->elements()));
 969     Handle<SeededNumberDictionary> new_dictionary =
 970         SeededNumberDictionary::AddNumberEntry(dictionary, index, value,
 971                                                details);
 972     if (attributes != NONE) object->RequireSlowElements(*new_dictionary);
 973     if (dictionary.is_identical_to(new_dictionary)) return;
 974     object->set_elements(*new_dictionary);
 975   }
 976
 977   static bool HasEntryImpl(FixedArrayBase* store, uint32_t entry) {
 978     DisallowHeapAllocation no_gc;
 979     SeededNumberDictionary* dict = SeededNumberDictionary::cast(store);
 980     Object* index = dict->KeyAt(entry);
 981     return !index->IsTheHole();
 982   }
 983
 984   static uint32_t GetIndexForEntryImpl(FixedArrayBase* store, uint32_t entry) {
 985     DisallowHeapAllocation no_gc;
 986     SeededNumberDictionary* dict = SeededNumberDictionary::cast(store);
 987     uint32_t result = 0;
 988     CHECK(dict->KeyAt(entry)->ToArrayIndex(&result));
 989     return result;
 990   }
 991
 992   static uint32_t GetEntryForIndexImpl(JSObject* holder, FixedArrayBase* store,
 993                                        uint32_t index) {
 994     DisallowHeapAllocation no_gc;
 995     SeededNumberDictionary* dict = SeededNumberDictionary::cast(store);
 996     int entry = dict->FindEntry(index);
 997     return entry == SeededNumberDictionary::kNotFound
 998                ? kMaxUInt32
 999                : static_cast<uint32_t>(entry);
1000   }
1001
1002   static PropertyDetails GetDetailsImpl(FixedArrayBase* backing_store,
1003                                         uint32_t entry) {
1004     return SeededNumberDictionary::cast(backing_store)->DetailsAt(entry);
1005   }
1006 };
1007
1008
1009 // Super class for all fast element arrays.
1010 template<typename FastElementsAccessorSubclass,
1011          typename KindTraits>
1012 class FastElementsAccessor
1013     : public ElementsAccessorBase<FastElementsAccessorSubclass, KindTraits> {
1014  public:
1015   explicit FastElementsAccessor(const char* name)
1016       : ElementsAccessorBase<FastElementsAccessorSubclass,
1017                              KindTraits>(name) {}
1018
1019   typedef typename KindTraits::BackingStore BackingStore;
1020
1021   static void DeleteAtEnd(Handle<JSObject> obj,
1022                           Handle<BackingStore> backing_store, uint32_t entry) {
1023     uint32_t length = static_cast<uint32_t>(backing_store->length());
1024     Heap* heap = obj->GetHeap();
1025     for (; entry > 0; entry--) {
1026       if (!backing_store->is_the_hole(entry - 1)) break;
1027     }
1028     if (entry == 0) {
1029       FixedArray* empty = heap->empty_fixed_array();
1030       if (obj->HasFastArgumentsElements()) {
1031         FixedArray::cast(obj->elements())->set(1, empty);
1032       } else {
1033         obj->set_elements(empty);
1034       }
1035       return;
1036     }
1037
1038     heap->RightTrimFixedArray<Heap::CONCURRENT_TO_SWEEPER>(*backing_store,
1039                                                            length - entry);
1040   }
1041
1042   static void DeleteCommon(Handle<JSObject> obj, uint32_t entry,
1043                            Handle<FixedArrayBase> store) {
1044     DCHECK(obj->HasFastSmiOrObjectElements() ||
1045            obj->HasFastDoubleElements() ||
1046            obj->HasFastArgumentsElements());
1047     Handle<BackingStore> backing_store = Handle<BackingStore>::cast(store);
1048     if (!obj->IsJSArray() &&
1049         entry == static_cast<uint32_t>(store->length()) - 1) {
1050       DeleteAtEnd(obj, backing_store, entry);
1051       return;
1052     }
1053
1054     backing_store->set_the_hole(entry);
1055
1056     // TODO(verwaest): Move this out of elements.cc.
1057     // If an old space backing store is larger than a certain size and
1058     // has too few used values, normalize it.
1059     // To avoid doing the check on every delete we require at least
1060     // one adjacent hole to the value being deleted.
1061     const int kMinLengthForSparsenessCheck = 64;
1062     if (backing_store->length() < kMinLengthForSparsenessCheck) return;
1063     if (backing_store->GetHeap()->InNewSpace(*backing_store)) return;
1064     uint32_t length = 0;
1065     if (obj->IsJSArray()) {
1066       JSArray::cast(*obj)->length()->ToArrayLength(&length);
1067     } else {
1068       length = static_cast<uint32_t>(store->length());
1069     }
1070     if ((entry > 0 && backing_store->is_the_hole(entry - 1)) ||
1071         (entry + 1 < length && backing_store->is_the_hole(entry + 1))) {
1072       if (!obj->IsJSArray()) {
1073         uint32_t i;
1074         for (i = entry + 1; i < length; i++) {
1075           if (!backing_store->is_the_hole(i)) break;
1076         }
1077         if (i == length) {
1078           DeleteAtEnd(obj, backing_store, entry);
1079           return;
1080         }
1081       }
1082       int num_used = 0;
1083       for (int i = 0; i < backing_store->length(); ++i) {
1084         if (!backing_store->is_the_hole(i)) ++num_used;
1085         // Bail out early if more than 1/4 is used.
1086         if (4 * num_used > backing_store->length()) break;
1087       }
1088       if (4 * num_used <= backing_store->length()) {
1089         JSObject::NormalizeElements(obj);
1090       }
1091     }
1092   }
1093
1094   static void ReconfigureImpl(Handle<JSObject> object,
1095                               Handle<FixedArrayBase> store, uint32_t entry,
1096                               Handle<Object> value,
1097                               PropertyAttributes attributes) {
1098     Handle<SeededNumberDictionary> dictionary =
1099         JSObject::NormalizeElements(object);
1100     entry = dictionary->FindEntry(entry);
1101     DictionaryElementsAccessor::ReconfigureImpl(object, dictionary, entry,
1102                                                 value, attributes);
1103   }
1104
1105   static void AddImpl(Handle<JSObject> object, uint32_t index,
1106                       Handle<Object> value, PropertyAttributes attributes,
1107                       uint32_t new_capacity) {
1108     DCHECK_EQ(NONE, attributes);
1109     ElementsKind from_kind = object->GetElementsKind();
1110     ElementsKind to_kind = FastElementsAccessorSubclass::kind();
1111     if (IsDictionaryElementsKind(from_kind) ||
1112         IsFastDoubleElementsKind(from_kind) !=
1113             IsFastDoubleElementsKind(to_kind) ||
1114         FastElementsAccessorSubclass::GetCapacityImpl(
1115             *object, object->elements()) != new_capacity) {
1116       FastElementsAccessorSubclass::GrowCapacityAndConvertImpl(object,
1117                                                                new_capacity);
1118     } else {
1119       if (from_kind != to_kind) {
1120         JSObject::TransitionElementsKind(object, to_kind);
1121       }
1122       if (IsFastSmiOrObjectElementsKind(from_kind)) {
1123         DCHECK(IsFastSmiOrObjectElementsKind(to_kind));
1124         JSObject::EnsureWritableFastElements(object);
1125       }
1126     }
1127     FastElementsAccessorSubclass::SetImpl(object->elements(), index, *value);
1128   }
1129
1130   static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) {
1131     ElementsKind kind = KindTraits::Kind;
1132     if (IsFastPackedElementsKind(kind)) {
1133       JSObject::TransitionElementsKind(obj, GetHoleyElementsKind(kind));
1134     }
1135     if (IsFastSmiOrObjectElementsKind(KindTraits::Kind)) {
1136       JSObject::EnsureWritableFastElements(obj);
1137     }
1138     DeleteCommon(obj, entry, handle(obj->elements()));
1139   }
1140
1141   static bool HasEntryImpl(FixedArrayBase* backing_store, uint32_t entry) {
1142     return !BackingStore::cast(backing_store)->is_the_hole(entry);
1143   }
1144
1145   static void ValidateContents(Handle<JSObject> holder, int length) {
1146 #if DEBUG
1147     Isolate* isolate = holder->GetIsolate();
1148     HandleScope scope(isolate);
1149     Handle<FixedArrayBase> elements(holder->elements(), isolate);
1150     Map* map = elements->map();
1151     DCHECK((IsFastSmiOrObjectElementsKind(KindTraits::Kind) &&
1152             (map == isolate->heap()->fixed_array_map() ||
1153              map == isolate->heap()->fixed_cow_array_map())) ||
1154            (IsFastDoubleElementsKind(KindTraits::Kind) ==
1155             ((map == isolate->heap()->fixed_array_map() && length == 0) ||
1156              map == isolate->heap()->fixed_double_array_map())));
1157     if (length == 0) return;  // nothing to do!
1158     DisallowHeapAllocation no_gc;
1159     Handle<BackingStore> backing_store = Handle<BackingStore>::cast(elements);
1160     if (IsFastSmiElementsKind(KindTraits::Kind)) {
1161       for (int i = 0; i < length; i++) {
1162         DCHECK(BackingStore::get(backing_store, i)->IsSmi() ||
1163                (IsFastHoleyElementsKind(KindTraits::Kind) &&
1164                 backing_store->is_the_hole(i)));
1165       }
1166     }
1167 #endif
1168   }
1169 };
1170
1171
1172 template<typename FastElementsAccessorSubclass,
1173          typename KindTraits>
1174 class FastSmiOrObjectElementsAccessor
1175     : public FastElementsAccessor<FastElementsAccessorSubclass, KindTraits> {
1176  public:
1177   explicit FastSmiOrObjectElementsAccessor(const char* name)
1178       : FastElementsAccessor<FastElementsAccessorSubclass,
1179                              KindTraits>(name) {}
1180
1181   static Object* GetRaw(FixedArray* backing_store, uint32_t entry) {
1182     uint32_t index = FastElementsAccessorSubclass::GetIndexForEntryImpl(
1183         backing_store, entry);
1184     return backing_store->get(index);
1185   }
1186
1187   // NOTE: this method violates the handlified function signature convention:
1188   // raw pointer parameters in the function that allocates.
1189   // See ElementsAccessor::CopyElements() for details.
1190   // This method could actually allocate if copying from double elements to
1191   // object elements.
1192   static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start,
1193                                FixedArrayBase* to, ElementsKind from_kind,
1194                                uint32_t to_start, int packed_size,
1195                                int copy_size) {
1196     DisallowHeapAllocation no_gc;
1197     ElementsKind to_kind = KindTraits::Kind;
1198     switch (from_kind) {
1199       case FAST_SMI_ELEMENTS:
1200       case FAST_HOLEY_SMI_ELEMENTS:
1201       case FAST_ELEMENTS:
1202       case FAST_HOLEY_ELEMENTS:
1203         CopyObjectToObjectElements(from, from_kind, from_start, to, to_kind,
1204                                    to_start, copy_size);
1205         break;
1206       case FAST_DOUBLE_ELEMENTS:
1207       case FAST_HOLEY_DOUBLE_ELEMENTS: {
1208         AllowHeapAllocation allow_allocation;
1209         CopyDoubleToObjectElements(
1210             from, from_start, to, to_kind, to_start, copy_size);
1211         break;
1212       }
1213       case DICTIONARY_ELEMENTS:
1214         CopyDictionaryToObjectElements(from, from_start, to, to_kind, to_start,
1215                                        copy_size);
1216         break;
1217       case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
1218       case SLOW_SLOPPY_ARGUMENTS_ELEMENTS:
1219         UNREACHABLE();
1220 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size)                       \
1221       case EXTERNAL_##TYPE##_ELEMENTS:                                        \
1222       case TYPE##_ELEMENTS:                                                   \
1223         UNREACHABLE();
1224       TYPED_ARRAYS(TYPED_ARRAY_CASE)
1225 #undef TYPED_ARRAY_CASE
1226     }
1227   }
1228 };
1229
1230
1231 class FastPackedSmiElementsAccessor
1232     : public FastSmiOrObjectElementsAccessor<
1233         FastPackedSmiElementsAccessor,
1234         ElementsKindTraits<FAST_SMI_ELEMENTS> > {
1235  public:
1236   explicit FastPackedSmiElementsAccessor(const char* name)
1237       : FastSmiOrObjectElementsAccessor<
1238           FastPackedSmiElementsAccessor,
1239           ElementsKindTraits<FAST_SMI_ELEMENTS> >(name) {}
1240 };
1241
1242
1243 class FastHoleySmiElementsAccessor
1244     : public FastSmiOrObjectElementsAccessor<
1245         FastHoleySmiElementsAccessor,
1246         ElementsKindTraits<FAST_HOLEY_SMI_ELEMENTS> > {
1247  public:
1248   explicit FastHoleySmiElementsAccessor(const char* name)
1249       : FastSmiOrObjectElementsAccessor<
1250           FastHoleySmiElementsAccessor,
1251           ElementsKindTraits<FAST_HOLEY_SMI_ELEMENTS> >(name) {}
1252 };
1253
1254
1255 class FastPackedObjectElementsAccessor
1256     : public FastSmiOrObjectElementsAccessor<
1257         FastPackedObjectElementsAccessor,
1258         ElementsKindTraits<FAST_ELEMENTS> > {
1259  public:
1260   explicit FastPackedObjectElementsAccessor(const char* name)
1261       : FastSmiOrObjectElementsAccessor<
1262           FastPackedObjectElementsAccessor,
1263           ElementsKindTraits<FAST_ELEMENTS> >(name) {}
1264 };
1265
1266
1267 class FastHoleyObjectElementsAccessor
1268     : public FastSmiOrObjectElementsAccessor<
1269         FastHoleyObjectElementsAccessor,
1270         ElementsKindTraits<FAST_HOLEY_ELEMENTS> > {
1271  public:
1272   explicit FastHoleyObjectElementsAccessor(const char* name)
1273       : FastSmiOrObjectElementsAccessor<
1274           FastHoleyObjectElementsAccessor,
1275           ElementsKindTraits<FAST_HOLEY_ELEMENTS> >(name) {}
1276 };
1277
1278
1279 template<typename FastElementsAccessorSubclass,
1280          typename KindTraits>
1281 class FastDoubleElementsAccessor
1282     : public FastElementsAccessor<FastElementsAccessorSubclass, KindTraits> {
1283  public:
1284   explicit FastDoubleElementsAccessor(const char* name)
1285       : FastElementsAccessor<FastElementsAccessorSubclass,
1286                              KindTraits>(name) {}
1287
1288   static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start,
1289                                FixedArrayBase* to, ElementsKind from_kind,
1290                                uint32_t to_start, int packed_size,
1291                                int copy_size) {
1292     DisallowHeapAllocation no_allocation;
1293     switch (from_kind) {
1294       case FAST_SMI_ELEMENTS:
1295         CopyPackedSmiToDoubleElements(from, from_start, to, to_start,
1296                                       packed_size, copy_size);
1297         break;
1298       case FAST_HOLEY_SMI_ELEMENTS:
1299         CopySmiToDoubleElements(from, from_start, to, to_start, copy_size);
1300         break;
1301       case FAST_DOUBLE_ELEMENTS:
1302       case FAST_HOLEY_DOUBLE_ELEMENTS:
1303         CopyDoubleToDoubleElements(from, from_start, to, to_start, copy_size);
1304         break;
1305       case FAST_ELEMENTS:
1306       case FAST_HOLEY_ELEMENTS:
1307         CopyObjectToDoubleElements(from, from_start, to, to_start, copy_size);
1308         break;
1309       case DICTIONARY_ELEMENTS:
1310         CopyDictionaryToDoubleElements(from, from_start, to, to_start,
1311                                        copy_size);
1312         break;
1313       case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
1314       case SLOW_SLOPPY_ARGUMENTS_ELEMENTS:
1315         UNREACHABLE();
1316
1317 #define TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size)                       \
1318       case EXTERNAL_##TYPE##_ELEMENTS:                                        \
1319       case TYPE##_ELEMENTS:                                                   \
1320         UNREACHABLE();
1321       TYPED_ARRAYS(TYPED_ARRAY_CASE)
1322 #undef TYPED_ARRAY_CASE
1323     }
1324   }
1325 };
1326
1327
1328 class FastPackedDoubleElementsAccessor
1329     : public FastDoubleElementsAccessor<
1330         FastPackedDoubleElementsAccessor,
1331         ElementsKindTraits<FAST_DOUBLE_ELEMENTS> > {
1332  public:
1333   explicit FastPackedDoubleElementsAccessor(const char* name)
1334       : FastDoubleElementsAccessor<
1335           FastPackedDoubleElementsAccessor,
1336           ElementsKindTraits<FAST_DOUBLE_ELEMENTS> >(name) {}
1337 };
1338
1339
1340 class FastHoleyDoubleElementsAccessor
1341     : public FastDoubleElementsAccessor<
1342         FastHoleyDoubleElementsAccessor,
1343         ElementsKindTraits<FAST_HOLEY_DOUBLE_ELEMENTS> > {
1344  public:
1345   explicit FastHoleyDoubleElementsAccessor(const char* name)
1346       : FastDoubleElementsAccessor<
1347           FastHoleyDoubleElementsAccessor,
1348           ElementsKindTraits<FAST_HOLEY_DOUBLE_ELEMENTS> >(name) {}
1349 };
1350
1351
1352 // Super class for all external element arrays.
1353 template<ElementsKind Kind>
1354 class TypedElementsAccessor
1355     : public ElementsAccessorBase<TypedElementsAccessor<Kind>,
1356                                   ElementsKindTraits<Kind> > {
1357  public:
1358   explicit TypedElementsAccessor(const char* name)
1359       : ElementsAccessorBase<AccessorClass,
1360                              ElementsKindTraits<Kind> >(name) {}
1361
1362   typedef typename ElementsKindTraits<Kind>::BackingStore BackingStore;
1363   typedef TypedElementsAccessor<Kind> AccessorClass;
1364
1365   static Handle<Object> GetImpl(Handle<FixedArrayBase> backing_store,
1366                                 uint32_t entry) {
1367     uint32_t index = GetIndexForEntryImpl(*backing_store, entry);
1368     return BackingStore::get(Handle<BackingStore>::cast(backing_store), index);
1369   }
1370
1371   static PropertyDetails GetDetailsImpl(FixedArrayBase* backing_store,
1372                                         uint32_t entry) {
1373     return PropertyDetails(DONT_DELETE, DATA, 0, PropertyCellType::kNoCell);
1374   }
1375
1376   static void SetLengthImpl(Handle<JSArray> array, uint32_t length,
1377                             Handle<FixedArrayBase> backing_store) {
1378     // External arrays do not support changing their length.
1379     UNREACHABLE();
1380   }
1381
1382   static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) {
1383     UNREACHABLE();
1384   }
1385
1386   static uint32_t GetIndexForEntryImpl(FixedArrayBase* backing_store,
1387                                        uint32_t entry) {
1388     return entry;
1389   }
1390
1391   static uint32_t GetEntryForIndexImpl(JSObject* holder,
1392                                        FixedArrayBase* backing_store,
1393                                        uint32_t index) {
1394     return index < AccessorClass::GetCapacityImpl(holder, backing_store)
1395                ? index
1396                : kMaxUInt32;
1397   }
1398
1399   static uint32_t GetCapacityImpl(JSObject* holder,
1400                                   FixedArrayBase* backing_store) {
1401     JSArrayBufferView* view = JSArrayBufferView::cast(holder);
1402     if (view->WasNeutered()) return 0;
1403     return backing_store->length();
1404   }
1405 };
1406
1407
1408
1409 #define EXTERNAL_ELEMENTS_ACCESSOR(Type, type, TYPE, ctype, size)    \
1410   typedef TypedElementsAccessor<EXTERNAL_##TYPE##_ELEMENTS>          \
1411       External##Type##ElementsAccessor;
1412
1413 TYPED_ARRAYS(EXTERNAL_ELEMENTS_ACCESSOR)
1414 #undef EXTERNAL_ELEMENTS_ACCESSOR
1415
1416 #define FIXED_ELEMENTS_ACCESSOR(Type, type, TYPE, ctype, size)       \
1417   typedef TypedElementsAccessor<TYPE##_ELEMENTS >                    \
1418       Fixed##Type##ElementsAccessor;
1419
1420 TYPED_ARRAYS(FIXED_ELEMENTS_ACCESSOR)
1421 #undef FIXED_ELEMENTS_ACCESSOR
1422
1423
1424 template <typename SloppyArgumentsElementsAccessorSubclass,
1425           typename ArgumentsAccessor, typename KindTraits>
1426 class SloppyArgumentsElementsAccessor
1427     : public ElementsAccessorBase<SloppyArgumentsElementsAccessorSubclass,
1428                                   KindTraits> {
1429  public:
1430   explicit SloppyArgumentsElementsAccessor(const char* name)
1431       : ElementsAccessorBase<SloppyArgumentsElementsAccessorSubclass,
1432                              KindTraits>(name) {
1433     USE(KindTraits::Kind);
1434   }
1435
1436   static Handle<Object> GetImpl(Handle<FixedArrayBase> parameters,
1437                                 uint32_t entry) {
1438     Isolate* isolate = parameters->GetIsolate();
1439     Handle<FixedArray> parameter_map = Handle<FixedArray>::cast(parameters);
1440     uint32_t length = parameter_map->length() - 2;
1441     if (entry < length) {
1442       DisallowHeapAllocation no_gc;
1443       Object* probe = parameter_map->get(entry + 2);
1444       Context* context = Context::cast(parameter_map->get(0));
1445       int context_entry = Smi::cast(probe)->value();
1446       DCHECK(!context->get(context_entry)->IsTheHole());
1447       return handle(context->get(context_entry), isolate);
1448     } else {
1449       // Object is not mapped, defer to the arguments.
1450       Handle<FixedArray> arguments(FixedArray::cast(parameter_map->get(1)),
1451                                    isolate);
1452       Handle<Object> result =
1453           ArgumentsAccessor::GetImpl(arguments, entry - length);
1454       // Elements of the arguments object in slow mode might be slow aliases.
1455       if (result->IsAliasedArgumentsEntry()) {
1456         DisallowHeapAllocation no_gc;
1457         AliasedArgumentsEntry* alias = AliasedArgumentsEntry::cast(*result);
1458         Context* context = Context::cast(parameter_map->get(0));
1459         int context_entry = alias->aliased_context_slot();
1460         DCHECK(!context->get(context_entry)->IsTheHole());
1461         return handle(context->get(context_entry), isolate);
1462       }
1463       return result;
1464     }
1465   }
1466
1467   static void GrowCapacityAndConvertImpl(Handle<JSObject> object,
1468                                          uint32_t capacity) {
1469     UNREACHABLE();
1470   }
1471
1472   static void SetImpl(FixedArrayBase* store, uint32_t entry, Object* value) {
1473     FixedArray* parameter_map = FixedArray::cast(store);
1474     uint32_t length = parameter_map->length() - 2;
1475     if (entry < length) {
1476       Object* probe = parameter_map->get(entry + 2);
1477       Context* context = Context::cast(parameter_map->get(0));
1478       int context_entry = Smi::cast(probe)->value();
1479       DCHECK(!context->get(context_entry)->IsTheHole());
1480       context->set(context_entry, value);
1481     } else {
1482       FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
1483       Object* current = ArgumentsAccessor::GetRaw(arguments, entry - length);
1484       if (current->IsAliasedArgumentsEntry()) {
1485         AliasedArgumentsEntry* alias = AliasedArgumentsEntry::cast(current);
1486         Context* context = Context::cast(parameter_map->get(0));
1487         int context_entry = alias->aliased_context_slot();
1488         DCHECK(!context->get(context_entry)->IsTheHole());
1489         context->set(context_entry, value);
1490       } else {
1491         ArgumentsAccessor::SetImpl(arguments, entry - length, value);
1492       }
1493     }
1494   }
1495
1496   static void SetLengthImpl(Handle<JSArray> array, uint32_t length,
1497                             Handle<FixedArrayBase> parameter_map) {
1498     // Sloppy arguments objects are not arrays.
1499     UNREACHABLE();
1500   }
1501
1502   static uint32_t GetCapacityImpl(JSObject* holder,
1503                                   FixedArrayBase* backing_store) {
1504     FixedArray* parameter_map = FixedArray::cast(backing_store);
1505     FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1));
1506     return parameter_map->length() - 2 +
1507            ArgumentsAccessor::GetCapacityImpl(holder, arguments);
1508   }
1509
1510   static bool HasEntryImpl(FixedArrayBase* parameters, uint32_t entry) {
1511     FixedArray* parameter_map = FixedArray::cast(parameters);
1512     uint32_t length = parameter_map->length() - 2;
1513     if (entry < length) {
1514       return !GetParameterMapArg(parameter_map, entry)->IsTheHole();
1515     }
1516
1517     FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1));
1518     return ArgumentsAccessor::HasEntryImpl(arguments, entry - length);
1519   }
1520
1521   static uint32_t GetIndexForEntryImpl(FixedArrayBase* parameters,
1522                                        uint32_t entry) {
1523     FixedArray* parameter_map = FixedArray::cast(parameters);
1524     uint32_t length = parameter_map->length() - 2;
1525     if (entry < length) return entry;
1526
1527     FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
1528     return ArgumentsAccessor::GetIndexForEntryImpl(arguments, entry - length);
1529   }
1530
1531   static uint32_t GetEntryForIndexImpl(JSObject* holder,
1532                                        FixedArrayBase* parameters,
1533                                        uint32_t index) {
1534     FixedArray* parameter_map = FixedArray::cast(parameters);
1535     Object* probe = GetParameterMapArg(parameter_map, index);
1536     if (!probe->IsTheHole()) return index;
1537
1538     FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
1539     uint32_t entry =
1540         ArgumentsAccessor::GetEntryForIndexImpl(holder, arguments, index);
1541     if (entry == kMaxUInt32) return entry;
1542     return (parameter_map->length() - 2) + entry;
1543   }
1544
1545   static PropertyDetails GetDetailsImpl(FixedArrayBase* parameters,
1546                                         uint32_t entry) {
1547     FixedArray* parameter_map = FixedArray::cast(parameters);
1548     uint32_t length = parameter_map->length() - 2;
1549     if (entry < length) {
1550       return PropertyDetails(NONE, DATA, 0, PropertyCellType::kNoCell);
1551     }
1552     FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
1553     return ArgumentsAccessor::GetDetailsImpl(arguments, entry - length);
1554   }
1555
1556   static Object* GetParameterMapArg(FixedArray* parameter_map, uint32_t index) {
1557     uint32_t length = parameter_map->length() - 2;
1558     return index < length
1559                ? parameter_map->get(index + 2)
1560                : Object::cast(parameter_map->GetHeap()->the_hole_value());
1561   }
1562
1563   static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) {
1564     FixedArray* parameter_map = FixedArray::cast(obj->elements());
1565     uint32_t length = static_cast<uint32_t>(parameter_map->length()) - 2;
1566     if (entry < length) {
1567       // TODO(kmillikin): We could check if this was the last aliased
1568       // parameter, and revert to normal elements in that case.  That
1569       // would enable GC of the context.
1570       parameter_map->set_the_hole(entry + 2);
1571     } else {
1572       SloppyArgumentsElementsAccessorSubclass::DeleteFromArguments(
1573           obj, entry - length);
1574     }
1575   }
1576 };
1577
1578
1579 class SlowSloppyArgumentsElementsAccessor
1580     : public SloppyArgumentsElementsAccessor<
1581           SlowSloppyArgumentsElementsAccessor, DictionaryElementsAccessor,
1582           ElementsKindTraits<SLOW_SLOPPY_ARGUMENTS_ELEMENTS> > {
1583  public:
1584   explicit SlowSloppyArgumentsElementsAccessor(const char* name)
1585       : SloppyArgumentsElementsAccessor<
1586             SlowSloppyArgumentsElementsAccessor, DictionaryElementsAccessor,
1587             ElementsKindTraits<SLOW_SLOPPY_ARGUMENTS_ELEMENTS> >(name) {}
1588
1589   static void DeleteFromArguments(Handle<JSObject> obj, uint32_t entry) {
1590     Handle<FixedArray> parameter_map(FixedArray::cast(obj->elements()));
1591     Handle<SeededNumberDictionary> dict(
1592         SeededNumberDictionary::cast(parameter_map->get(1)));
1593     // TODO(verwaest): Remove reliance on index in Shrink.
1594     uint32_t index = GetIndexForEntryImpl(*dict, entry);
1595     Handle<Object> result = SeededNumberDictionary::DeleteProperty(dict, entry);
1596     USE(result);
1597     DCHECK(result->IsTrue());
1598     Handle<FixedArray> new_elements =
1599         SeededNumberDictionary::Shrink(dict, index);
1600     parameter_map->set(1, *new_elements);
1601   }
1602
1603   static void AddImpl(Handle<JSObject> object, uint32_t index,
1604                       Handle<Object> value, PropertyAttributes attributes,
1605                       uint32_t new_capacity) {
1606     Handle<FixedArray> parameter_map(FixedArray::cast(object->elements()));
1607     Handle<FixedArrayBase> old_elements(
1608         FixedArrayBase::cast(parameter_map->get(1)));
1609     Handle<SeededNumberDictionary> dictionary =
1610         old_elements->IsSeededNumberDictionary()
1611             ? Handle<SeededNumberDictionary>::cast(old_elements)
1612             : JSObject::NormalizeElements(object);
1613     PropertyDetails details(attributes, DATA, 0, PropertyCellType::kNoCell);
1614     Handle<SeededNumberDictionary> new_dictionary =
1615         SeededNumberDictionary::AddNumberEntry(dictionary, index, value,
1616                                                details);
1617     if (attributes != NONE) object->RequireSlowElements(*new_dictionary);
1618     if (*dictionary != *new_dictionary) {
1619       FixedArray::cast(object->elements())->set(1, *new_dictionary);
1620     }
1621   }
1622
1623   static void ReconfigureImpl(Handle<JSObject> object,
1624                               Handle<FixedArrayBase> store, uint32_t entry,
1625                               Handle<Object> value,
1626                               PropertyAttributes attributes) {
1627     Handle<FixedArray> parameter_map = Handle<FixedArray>::cast(store);
1628     uint32_t length = parameter_map->length() - 2;
1629     if (entry < length) {
1630       Object* probe = parameter_map->get(entry + 2);
1631       DCHECK(!probe->IsTheHole());
1632       Context* context = Context::cast(parameter_map->get(0));
1633       int context_entry = Smi::cast(probe)->value();
1634       DCHECK(!context->get(context_entry)->IsTheHole());
1635       context->set(context_entry, *value);
1636
1637       // Redefining attributes of an aliased element destroys fast aliasing.
1638       parameter_map->set_the_hole(entry + 2);
1639       // For elements that are still writable we re-establish slow aliasing.
1640       if ((attributes & READ_ONLY) == 0) {
1641         Isolate* isolate = store->GetIsolate();
1642         value = isolate->factory()->NewAliasedArgumentsEntry(context_entry);
1643       }
1644
1645       PropertyDetails details(attributes, DATA, 0, PropertyCellType::kNoCell);
1646       Handle<SeededNumberDictionary> arguments(
1647           SeededNumberDictionary::cast(parameter_map->get(1)));
1648       arguments = SeededNumberDictionary::AddNumberEntry(arguments, entry,
1649                                                          value, details);
1650       // If the attributes were NONE, we would have called set rather than
1651       // reconfigure.
1652       DCHECK_NE(NONE, attributes);
1653       object->RequireSlowElements(*arguments);
1654       parameter_map->set(1, *arguments);
1655     } else {
1656       Handle<FixedArrayBase> arguments(
1657           FixedArrayBase::cast(parameter_map->get(1)));
1658       DictionaryElementsAccessor::ReconfigureImpl(
1659           object, arguments, entry - length, value, attributes);
1660     }
1661   }
1662 };
1663
1664
1665 class FastSloppyArgumentsElementsAccessor
1666     : public SloppyArgumentsElementsAccessor<
1667           FastSloppyArgumentsElementsAccessor, FastHoleyObjectElementsAccessor,
1668           ElementsKindTraits<FAST_SLOPPY_ARGUMENTS_ELEMENTS> > {
1669  public:
1670   explicit FastSloppyArgumentsElementsAccessor(const char* name)
1671       : SloppyArgumentsElementsAccessor<
1672             FastSloppyArgumentsElementsAccessor,
1673             FastHoleyObjectElementsAccessor,
1674             ElementsKindTraits<FAST_SLOPPY_ARGUMENTS_ELEMENTS> >(name) {}
1675
1676   static void DeleteFromArguments(Handle<JSObject> obj, uint32_t entry) {
1677     FixedArray* parameter_map = FixedArray::cast(obj->elements());
1678     Handle<FixedArray> arguments(FixedArray::cast(parameter_map->get(1)));
1679     FastHoleyObjectElementsAccessor::DeleteCommon(obj, entry, arguments);
1680   }
1681
1682   static void AddImpl(Handle<JSObject> object, uint32_t index,
1683                       Handle<Object> value, PropertyAttributes attributes,
1684                       uint32_t new_capacity) {
1685     DCHECK_EQ(NONE, attributes);
1686     Handle<FixedArray> parameter_map(FixedArray::cast(object->elements()));
1687     Handle<FixedArrayBase> old_elements(
1688         FixedArrayBase::cast(parameter_map->get(1)));
1689     if (old_elements->IsSeededNumberDictionary() ||
1690         static_cast<uint32_t>(old_elements->length()) < new_capacity) {
1691       GrowCapacityAndConvertImpl(object, new_capacity);
1692     }
1693     FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
1694     // For fast holey objects, the entry equals the index. The code above made
1695     // sure that there's enough space to store the value. We cannot convert
1696     // index to entry explicitly since the slot still contains the hole, so the
1697     // current EntryForIndex would indicate that it is "absent" by returning
1698     // kMaxUInt32.
1699     FastHoleyObjectElementsAccessor::SetImpl(arguments, index, *value);
1700   }
1701
1702   static void ReconfigureImpl(Handle<JSObject> object,
1703                               Handle<FixedArrayBase> store, uint32_t entry,
1704                               Handle<Object> value,
1705                               PropertyAttributes attributes) {
1706     Handle<SeededNumberDictionary> dictionary =
1707         JSObject::NormalizeElements(object);
1708     FixedArray::cast(*store)->set(1, *dictionary);
1709     uint32_t length = static_cast<uint32_t>(store->length()) - 2;
1710     if (entry >= length) {
1711       entry = dictionary->FindEntry(entry - length) + length;
1712     }
1713     SlowSloppyArgumentsElementsAccessor::ReconfigureImpl(object, store, entry,
1714                                                          value, attributes);
1715   }
1716
1717   static void CopyElementsImpl(FixedArrayBase* from, uint32_t from_start,
1718                                FixedArrayBase* to, ElementsKind from_kind,
1719                                uint32_t to_start, int packed_size,
1720                                int copy_size) {
1721     DCHECK(!to->IsDictionary());
1722     if (from_kind == SLOW_SLOPPY_ARGUMENTS_ELEMENTS) {
1723       CopyDictionaryToObjectElements(from, from_start, to, FAST_HOLEY_ELEMENTS,
1724                                      to_start, copy_size);
1725     } else {
1726       DCHECK_EQ(FAST_SLOPPY_ARGUMENTS_ELEMENTS, from_kind);
1727       CopyObjectToObjectElements(from, FAST_HOLEY_ELEMENTS, from_start, to,
1728                                  FAST_HOLEY_ELEMENTS, to_start, copy_size);
1729     }
1730   }
1731
1732   static void GrowCapacityAndConvertImpl(Handle<JSObject> object,
1733                                          uint32_t capacity) {
1734     Handle<FixedArray> parameter_map(FixedArray::cast(object->elements()));
1735     Handle<FixedArray> old_elements(FixedArray::cast(parameter_map->get(1)));
1736     ElementsKind from_kind = object->GetElementsKind();
1737     // This method should only be called if there's a reason to update the
1738     // elements.
1739     DCHECK(from_kind == SLOW_SLOPPY_ARGUMENTS_ELEMENTS ||
1740            static_cast<uint32_t>(old_elements->length()) < capacity);
1741     Handle<FixedArrayBase> elements =
1742         ConvertElementsWithCapacity(object, old_elements, from_kind, capacity);
1743     Handle<Map> new_map = JSObject::GetElementsTransitionMap(
1744         object, FAST_SLOPPY_ARGUMENTS_ELEMENTS);
1745     JSObject::MigrateToMap(object, new_map);
1746     parameter_map->set(1, *elements);
1747     JSObject::ValidateElements(object);
1748   }
1749 };
1750
1751
1752 template <typename ElementsAccessorSubclass, typename ElementsKindTraits>
1753 void ElementsAccessorBase<ElementsAccessorSubclass, ElementsKindTraits>::
1754     SetLengthImpl(Handle<JSArray> array, uint32_t length,
1755                   Handle<FixedArrayBase> backing_store) {
1756   DCHECK(!array->SetLengthWouldNormalize(length));
1757   DCHECK(IsFastElementsKind(array->GetElementsKind()));
1758   uint32_t old_length = 0;
1759   CHECK(array->length()->ToArrayIndex(&old_length));
1760
1761   if (old_length < length) {
1762     ElementsKind kind = array->GetElementsKind();
1763     if (!IsFastHoleyElementsKind(kind)) {
1764       kind = GetHoleyElementsKind(kind);
1765       JSObject::TransitionElementsKind(array, kind);
1766     }
1767   }
1768
1769   // Check whether the backing store should be shrunk.
1770   uint32_t capacity = backing_store->length();
1771   if (length == 0) {
1772     array->initialize_elements();
1773   } else if (length <= capacity) {
1774     if (array->HasFastSmiOrObjectElements()) {
1775       backing_store = JSObject::EnsureWritableFastElements(array);
1776     }
1777     if (2 * length <= capacity) {
1778       // If more than half the elements won't be used, trim the array.
1779       array->GetHeap()->RightTrimFixedArray<Heap::CONCURRENT_TO_SWEEPER>(
1780           *backing_store, capacity - length);
1781     } else {
1782       // Otherwise, fill the unused tail with holes.
1783       for (uint32_t i = length; i < old_length; i++) {
1784         BackingStore::cast(*backing_store)->set_the_hole(i);
1785       }
1786     }
1787   } else {
1788     // Check whether the backing store should be expanded.
1789     capacity = Max(length, JSObject::NewElementsCapacity(capacity));
1790     ElementsAccessorSubclass::GrowCapacityAndConvertImpl(array, capacity);
1791   }
1792
1793   array->set_length(Smi::FromInt(length));
1794   JSObject::ValidateElements(array);
1795 }
1796 }  // namespace
1797
1798
1799 void CheckArrayAbuse(Handle<JSObject> obj, const char* op, uint32_t index,
1800                      bool allow_appending) {
1801   DisallowHeapAllocation no_allocation;
1802   Object* raw_length = NULL;
1803   const char* elements_type = "array";
1804   if (obj->IsJSArray()) {
1805     JSArray* array = JSArray::cast(*obj);
1806     raw_length = array->length();
1807   } else {
1808     raw_length = Smi::FromInt(obj->elements()->length());
1809     elements_type = "object";
1810   }
1811
1812   if (raw_length->IsNumber()) {
1813     double n = raw_length->Number();
1814     if (FastI2D(FastD2UI(n)) == n) {
1815       int32_t int32_length = DoubleToInt32(n);
1816       uint32_t compare_length = static_cast<uint32_t>(int32_length);
1817       if (allow_appending) compare_length++;
1818       if (index >= compare_length) {
1819         PrintF("[OOB %s %s (%s length = %d, element accessed = %d) in ",
1820                elements_type, op, elements_type, static_cast<int>(int32_length),
1821                static_cast<int>(index));
1822         TraceTopFrame(obj->GetIsolate());
1823         PrintF("]\n");
1824       }
1825     } else {
1826       PrintF("[%s elements length not integer value in ", elements_type);
1827       TraceTopFrame(obj->GetIsolate());
1828       PrintF("]\n");
1829     }
1830   } else {
1831     PrintF("[%s elements length not a number in ", elements_type);
1832     TraceTopFrame(obj->GetIsolate());
1833     PrintF("]\n");
1834   }
1835 }
1836
1837
1838 MaybeHandle<Object> ArrayConstructInitializeElements(Handle<JSArray> array,
1839                                                      Arguments* args) {
1840   if (args->length() == 0) {
1841     // Optimize the case where there are no parameters passed.
1842     JSArray::Initialize(array, JSArray::kPreallocatedArrayElements);
1843     return array;
1844
1845   } else if (args->length() == 1 && args->at<Object>(0)->IsNumber()) {
1846     uint32_t length;
1847     if (!args->at<Object>(0)->ToArrayLength(&length)) {
1848       return ThrowArrayLengthRangeError(array->GetIsolate());
1849     }
1850
1851     // Optimize the case where there is one argument and the argument is a small
1852     // smi.
1853     if (length > 0 && length < JSObject::kInitialMaxFastElementArray) {
1854       ElementsKind elements_kind = array->GetElementsKind();
1855       JSArray::Initialize(array, length, length);
1856
1857       if (!IsFastHoleyElementsKind(elements_kind)) {
1858         elements_kind = GetHoleyElementsKind(elements_kind);
1859         JSObject::TransitionElementsKind(array, elements_kind);
1860       }
1861     } else if (length == 0) {
1862       JSArray::Initialize(array, JSArray::kPreallocatedArrayElements);
1863     } else {
1864       // Take the argument as the length.
1865       JSArray::Initialize(array, 0);
1866       JSArray::SetLength(array, length);
1867     }
1868     return array;
1869   }
1870
1871   Factory* factory = array->GetIsolate()->factory();
1872
1873   // Set length and elements on the array.
1874   int number_of_elements = args->length();
1875   JSObject::EnsureCanContainElements(
1876       array, args, 0, number_of_elements, ALLOW_CONVERTED_DOUBLE_ELEMENTS);
1877
1878   // Allocate an appropriately typed elements array.
1879   ElementsKind elements_kind = array->GetElementsKind();
1880   Handle<FixedArrayBase> elms;
1881   if (IsFastDoubleElementsKind(elements_kind)) {
1882     elms = Handle<FixedArrayBase>::cast(
1883         factory->NewFixedDoubleArray(number_of_elements));
1884   } else {
1885     elms = Handle<FixedArrayBase>::cast(
1886         factory->NewFixedArrayWithHoles(number_of_elements));
1887   }
1888
1889   // Fill in the content
1890   switch (array->GetElementsKind()) {
1891     case FAST_HOLEY_SMI_ELEMENTS:
1892     case FAST_SMI_ELEMENTS: {
1893       Handle<FixedArray> smi_elms = Handle<FixedArray>::cast(elms);
1894       for (int entry = 0; entry < number_of_elements; entry++) {
1895         smi_elms->set(entry, (*args)[entry], SKIP_WRITE_BARRIER);
1896       }
1897       break;
1898     }
1899     case FAST_HOLEY_ELEMENTS:
1900     case FAST_ELEMENTS: {
1901       DisallowHeapAllocation no_gc;
1902       WriteBarrierMode mode = elms->GetWriteBarrierMode(no_gc);
1903       Handle<FixedArray> object_elms = Handle<FixedArray>::cast(elms);
1904       for (int entry = 0; entry < number_of_elements; entry++) {
1905         object_elms->set(entry, (*args)[entry], mode);
1906       }
1907       break;
1908     }
1909     case FAST_HOLEY_DOUBLE_ELEMENTS:
1910     case FAST_DOUBLE_ELEMENTS: {
1911       Handle<FixedDoubleArray> double_elms =
1912           Handle<FixedDoubleArray>::cast(elms);
1913       for (int entry = 0; entry < number_of_elements; entry++) {
1914         double_elms->set(entry, (*args)[entry]->Number());
1915       }
1916       break;
1917     }
1918     default:
1919       UNREACHABLE();
1920       break;
1921   }
1922
1923   array->set_elements(*elms);
1924   array->set_length(Smi::FromInt(number_of_elements));
1925   return array;
1926 }
1927
1928
1929 void ElementsAccessor::InitializeOncePerProcess() {
1930   static ElementsAccessor* accessor_array[] = {
1931 #define ACCESSOR_ARRAY(Class, Kind, Store) new Class(#Kind),
1932       ELEMENTS_LIST(ACCESSOR_ARRAY)
1933 #undef ACCESSOR_ARRAY
1934   };
1935
1936   STATIC_ASSERT((sizeof(accessor_array) / sizeof(*accessor_array)) ==
1937                 kElementsKindCount);
1938
1939   elements_accessors_ = accessor_array;
1940 }
1941
1942
1943 void ElementsAccessor::TearDown() {
1944   if (elements_accessors_ == NULL) return;
1945 #define ACCESSOR_DELETE(Class, Kind, Store) delete elements_accessors_[Kind];
1946   ELEMENTS_LIST(ACCESSOR_DELETE)
1947 #undef ACCESSOR_DELETE
1948   elements_accessors_ = NULL;
1949 }
1950
1951
1952 ElementsAccessor** ElementsAccessor::elements_accessors_ = NULL;
1953 }  // namespace internal
1954 }  // namespace v8