elements.cc 77.7 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "v8.h"

30
#include "arguments.h"
31 32
#include "objects.h"
#include "elements.h"
33
#include "utils.h"
34
#include "v8conversions.h"
35 36 37 38 39 40 41 42

// Each concrete ElementsAccessor can handle exactly one ElementsKind,
// several abstract ElementsAccessor classes are used to allow sharing
// common code.
//
// Inheritance hierarchy:
// - ElementsAccessorBase                        (abstract)
//   - FastElementsAccessor                      (abstract)
43 44 45 46 47
//     - FastSmiOrObjectElementsAccessor
//       - FastPackedSmiElementsAccessor
//       - FastHoleySmiElementsAccessor
//       - FastPackedObjectElementsAccessor
//       - FastHoleyObjectElementsAccessor
48
//     - FastDoubleElementsAccessor
49 50
//       - FastPackedDoubleElementsAccessor
//       - FastHoleyDoubleElementsAccessor
51 52 53 54 55 56 57 58 59 60 61 62 63 64
//   - ExternalElementsAccessor                  (abstract)
//     - ExternalByteElementsAccessor
//     - ExternalUnsignedByteElementsAccessor
//     - ExternalShortElementsAccessor
//     - ExternalUnsignedShortElementsAccessor
//     - ExternalIntElementsAccessor
//     - ExternalUnsignedIntElementsAccessor
//     - ExternalFloatElementsAccessor
//     - ExternalDoubleElementsAccessor
//     - PixelElementsAccessor
//   - DictionaryElementsAccessor
//   - NonStrictArgumentsElementsAccessor


65 66 67 68
namespace v8 {
namespace internal {


69 70 71
static const int kPackedSizeNotKnown = -1;


72 73 74 75 76 77
// First argument in list is the accessor class, the second argument is the
// accessor ElementsKind, and the third is the backing store class.  Use the
// fast element handler for smi-only arrays.  The implementation is currently
// identical.  Note that the order must match that of the ElementsKind enum for
// the |accessor_array[]| below to work.
#define ELEMENTS_LIST(V)                                                \
78 79 80 81 82 83 84 85 86
  V(FastPackedSmiElementsAccessor, FAST_SMI_ELEMENTS, FixedArray)       \
  V(FastHoleySmiElementsAccessor, FAST_HOLEY_SMI_ELEMENTS,              \
    FixedArray)                                                         \
  V(FastPackedObjectElementsAccessor, FAST_ELEMENTS, FixedArray)        \
  V(FastHoleyObjectElementsAccessor, FAST_HOLEY_ELEMENTS, FixedArray)   \
  V(FastPackedDoubleElementsAccessor, FAST_DOUBLE_ELEMENTS,             \
    FixedDoubleArray)                                                   \
  V(FastHoleyDoubleElementsAccessor, FAST_HOLEY_DOUBLE_ELEMENTS,        \
    FixedDoubleArray)                                                   \
87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
  V(DictionaryElementsAccessor, DICTIONARY_ELEMENTS,                    \
    SeededNumberDictionary)                                             \
  V(NonStrictArgumentsElementsAccessor, NON_STRICT_ARGUMENTS_ELEMENTS,  \
    FixedArray)                                                         \
  V(ExternalByteElementsAccessor, EXTERNAL_BYTE_ELEMENTS,               \
    ExternalByteArray)                                                  \
  V(ExternalUnsignedByteElementsAccessor,                               \
    EXTERNAL_UNSIGNED_BYTE_ELEMENTS, ExternalUnsignedByteArray)         \
  V(ExternalShortElementsAccessor, EXTERNAL_SHORT_ELEMENTS,             \
    ExternalShortArray)                                                 \
  V(ExternalUnsignedShortElementsAccessor,                              \
    EXTERNAL_UNSIGNED_SHORT_ELEMENTS, ExternalUnsignedShortArray)       \
  V(ExternalIntElementsAccessor, EXTERNAL_INT_ELEMENTS,                 \
    ExternalIntArray)                                                   \
  V(ExternalUnsignedIntElementsAccessor,                                \
    EXTERNAL_UNSIGNED_INT_ELEMENTS, ExternalUnsignedIntArray)           \
  V(ExternalFloatElementsAccessor,                                      \
    EXTERNAL_FLOAT_ELEMENTS, ExternalFloatArray)                        \
  V(ExternalDoubleElementsAccessor,                                     \
    EXTERNAL_DOUBLE_ELEMENTS, ExternalDoubleArray)                      \
  V(PixelElementsAccessor, EXTERNAL_PIXEL_ELEMENTS, ExternalPixelArray)


template<ElementsKind Kind> class ElementsKindTraits {
 public:
  typedef FixedArrayBase BackingStore;
};

#define ELEMENTS_TRAITS(Class, KindParam, Store)               \
template<> class ElementsKindTraits<KindParam> {               \
117
  public:                                                      \
118 119 120 121 122 123 124
  static const ElementsKind Kind = KindParam;                  \
  typedef Store BackingStore;                                  \
};
ELEMENTS_LIST(ELEMENTS_TRAITS)
#undef ELEMENTS_TRAITS


125 126 127
ElementsAccessor** ElementsAccessor::elements_accessors_;


128
static bool HasKey(FixedArray* array, Object* key) {
129 130 131 132 133 134 135 136 137 138 139 140 141
  int len0 = array->length();
  for (int i = 0; i < len0; i++) {
    Object* element = array->get(i);
    if (element->IsSmi() && element == key) return true;
    if (element->IsString() &&
        key->IsString() && String::cast(element)->Equals(String::cast(key))) {
      return true;
    }
  }
  return false;
}


142 143 144 145 146 147 148 149
static Failure* ThrowArrayLengthRangeError(Heap* heap) {
  HandleScope scope(heap->isolate());
  return heap->isolate()->Throw(
      *heap->isolate()->factory()->NewRangeError("invalid_array_length",
          HandleVector<Object>(NULL, 0)));
}


150
static void CopyObjectToObjectElements(FixedArrayBase* from_base,
151 152
                                       ElementsKind from_kind,
                                       uint32_t from_start,
153
                                       FixedArrayBase* to_base,
154 155 156
                                       ElementsKind to_kind,
                                       uint32_t to_start,
                                       int raw_copy_size) {
157 158
  ASSERT(to_base->map() !=
      from_base->GetIsolate()->heap()->fixed_cow_array_map());
159
  DisallowHeapAllocation no_allocation;
160 161 162 163
  int copy_size = raw_copy_size;
  if (raw_copy_size < 0) {
    ASSERT(raw_copy_size == ElementsAccessor::kCopyToEnd ||
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
164 165
    copy_size = Min(from_base->length() - from_start,
                    to_base->length() - to_start);
166
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
167
      int start = to_start + copy_size;
168
      int length = to_base->length() - start;
169
      if (length > 0) {
170 171 172
        Heap* heap = from_base->GetHeap();
        MemsetPointer(FixedArray::cast(to_base)->data_start() + start,
                      heap->the_hole_value(), length);
173 174
      }
    }
175
  }
176 177
  ASSERT((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
         (copy_size + static_cast<int>(from_start)) <= from_base->length());
178
  if (copy_size == 0) return;
179 180
  FixedArray* from = FixedArray::cast(from_base);
  FixedArray* to = FixedArray::cast(to_base);
181 182
  ASSERT(IsFastSmiOrObjectElementsKind(from_kind));
  ASSERT(IsFastSmiOrObjectElementsKind(to_kind));
183 184 185 186
  Address to_address = to->address() + FixedArray::kHeaderSize;
  Address from_address = from->address() + FixedArray::kHeaderSize;
  CopyWords(reinterpret_cast<Object**>(to_address) + to_start,
            reinterpret_cast<Object**>(from_address) + from_start,
187
            static_cast<size_t>(copy_size));
188 189
  if (IsFastObjectElementsKind(from_kind) &&
      IsFastObjectElementsKind(to_kind)) {
190 191 192 193
    Heap* heap = from->GetHeap();
    if (!heap->InNewSpace(to)) {
      heap->RecordWrites(to->address(),
                         to->OffsetOfElementAt(to_start),
194 195
                         copy_size);
    }
196
    heap->incremental_marking()->RecordWrites(to);
197 198 199 200
  }
}


201
static void CopyDictionaryToObjectElements(FixedArrayBase* from_base,
202
                                           uint32_t from_start,
203
                                           FixedArrayBase* to_base,
204 205
                                           ElementsKind to_kind,
                                           uint32_t to_start,
206
                                           int raw_copy_size) {
207
  SeededNumberDictionary* from = SeededNumberDictionary::cast(from_base);
208
  DisallowHeapAllocation no_allocation;
209 210 211 212 213 214 215
  int copy_size = raw_copy_size;
  Heap* heap = from->GetHeap();
  if (raw_copy_size < 0) {
    ASSERT(raw_copy_size == ElementsAccessor::kCopyToEnd ||
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
    copy_size = from->max_number_key() + 1 - from_start;
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
216
      int start = to_start + copy_size;
217
      int length = to_base->length() - start;
218 219
      if (length > 0) {
        Heap* heap = from->GetHeap();
220 221
        MemsetPointer(FixedArray::cast(to_base)->data_start() + start,
                      heap->the_hole_value(), length);
222 223 224
      }
    }
  }
225
  ASSERT(to_base != from_base);
226
  ASSERT(IsFastSmiOrObjectElementsKind(to_kind));
227
  if (copy_size == 0) return;
228
  FixedArray* to = FixedArray::cast(to_base);
229 230 231 232
  uint32_t to_length = to->length();
  if (to_start + copy_size > to_length) {
    copy_size = to_length - to_start;
  }
233 234 235 236 237 238 239 240 241 242
  for (int i = 0; i < copy_size; i++) {
    int entry = from->FindEntry(i + from_start);
    if (entry != SeededNumberDictionary::kNotFound) {
      Object* value = from->ValueAt(entry);
      ASSERT(!value->IsTheHole());
      to->set(i + to_start, value, SKIP_WRITE_BARRIER);
    } else {
      to->set_the_hole(i + to_start);
    }
  }
243
  if (IsFastObjectElementsKind(to_kind)) {
244 245 246 247
    if (!heap->InNewSpace(to)) {
      heap->RecordWrites(to->address(),
                         to->OffsetOfElementAt(to_start),
                         copy_size);
248
    }
249
    heap->incremental_marking()->RecordWrites(to);
250 251 252 253 254
  }
}


MUST_USE_RESULT static MaybeObject* CopyDoubleToObjectElements(
255
    FixedArrayBase* from_base,
256
    uint32_t from_start,
257
    FixedArrayBase* to_base,
258 259
    ElementsKind to_kind,
    uint32_t to_start,
260
    int raw_copy_size) {
261
  ASSERT(IsFastSmiOrObjectElementsKind(to_kind));
262 263 264 265
  int copy_size = raw_copy_size;
  if (raw_copy_size < 0) {
    ASSERT(raw_copy_size == ElementsAccessor::kCopyToEnd ||
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
266 267
    copy_size = Min(from_base->length() - from_start,
                    to_base->length() - to_start);
268
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
269 270 271 272
      // Also initialize the area that will be copied over since HeapNumber
      // allocation below can cause an incremental marking step, requiring all
      // existing heap objects to be propertly initialized.
      int start = to_start;
273
      int length = to_base->length() - start;
274
      if (length > 0) {
275 276 277
        Heap* heap = from_base->GetHeap();
        MemsetPointer(FixedArray::cast(to_base)->data_start() + start,
                      heap->the_hole_value(), length);
278 279
      }
    }
280
  }
281 282 283 284 285
  ASSERT((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
         (copy_size + static_cast<int>(from_start)) <= from_base->length());
  if (copy_size == 0) return from_base;
  FixedDoubleArray* from = FixedDoubleArray::cast(from_base);
  FixedArray* to = FixedArray::cast(to_base);
286
  for (int i = 0; i < copy_size; ++i) {
287
    if (IsFastSmiElementsKind(to_kind)) {
288 289 290
      UNIMPLEMENTED();
      return Failure::Exception();
    } else {
291
      MaybeObject* maybe_value = from->get(i + from_start);
292
      Object* value;
293 294
      ASSERT(IsFastObjectElementsKind(to_kind));
      // Because Double -> Object elements transitions allocate HeapObjects
295 296 297 298 299 300
      // iteratively, the allocate must succeed within a single GC cycle,
      // otherwise the retry after the GC will also fail. In order to ensure
      // that no GC is triggered, allocate HeapNumbers from old space if they
      // can't be taken from new space.
      if (!maybe_value->ToObject(&value)) {
        ASSERT(maybe_value->IsRetryAfterGC() || maybe_value->IsOutOfMemory());
301
        Heap* heap = from->GetHeap();
302
        MaybeObject* maybe_value_object =
303
            heap->AllocateHeapNumber(from->get_scalar(i + from_start),
304 305 306
                                     TENURED);
        if (!maybe_value_object->ToObject(&value)) return maybe_value_object;
      }
307
      to->set(i + to_start, value, UPDATE_WRITE_BARRIER);
308 309
    }
  }
310
  return to;
311 312 313
}


314
static void CopyDoubleToDoubleElements(FixedArrayBase* from_base,
315
                                       uint32_t from_start,
316
                                       FixedArrayBase* to_base,
317
                                       uint32_t to_start,
318 319 320 321 322
                                       int raw_copy_size) {
  int copy_size = raw_copy_size;
  if (raw_copy_size < 0) {
    ASSERT(raw_copy_size == ElementsAccessor::kCopyToEnd ||
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
323 324
    copy_size = Min(from_base->length() - from_start,
                    to_base->length() - to_start);
325
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
326 327
      for (int i = to_start + copy_size; i < to_base->length(); ++i) {
        FixedDoubleArray::cast(to_base)->set_the_hole(i);
328 329
      }
    }
330
  }
331 332
  ASSERT((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
         (copy_size + static_cast<int>(from_start)) <= from_base->length());
333
  if (copy_size == 0) return;
334 335
  FixedDoubleArray* from = FixedDoubleArray::cast(from_base);
  FixedDoubleArray* to = FixedDoubleArray::cast(to_base);
336 337 338 339
  Address to_address = to->address() + FixedDoubleArray::kHeaderSize;
  Address from_address = from->address() + FixedDoubleArray::kHeaderSize;
  to_address += kDoubleSize * to_start;
  from_address += kDoubleSize * from_start;
340
  int words_per_double = (kDoubleSize / kPointerSize);
341 342
  CopyWords(reinterpret_cast<Object**>(to_address),
            reinterpret_cast<Object**>(from_address),
343
            static_cast<size_t>(words_per_double * copy_size));
344 345 346
}


347
static void CopySmiToDoubleElements(FixedArrayBase* from_base,
348
                                    uint32_t from_start,
349
                                    FixedArrayBase* to_base,
350 351 352 353 354 355
                                    uint32_t to_start,
                                    int raw_copy_size) {
  int copy_size = raw_copy_size;
  if (raw_copy_size < 0) {
    ASSERT(raw_copy_size == ElementsAccessor::kCopyToEnd ||
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
356
    copy_size = from_base->length() - from_start;
357
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
358 359
      for (int i = to_start + copy_size; i < to_base->length(); ++i) {
        FixedDoubleArray::cast(to_base)->set_the_hole(i);
360 361 362
      }
    }
  }
363 364
  ASSERT((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
         (copy_size + static_cast<int>(from_start)) <= from_base->length());
365
  if (copy_size == 0) return;
366 367
  FixedArray* from = FixedArray::cast(from_base);
  FixedDoubleArray* to = FixedDoubleArray::cast(to_base);
368 369 370 371 372 373 374 375 376 377 378 379 380
  Object* the_hole = from->GetHeap()->the_hole_value();
  for (uint32_t from_end = from_start + static_cast<uint32_t>(copy_size);
       from_start < from_end; from_start++, to_start++) {
    Object* hole_or_smi = from->get(from_start);
    if (hole_or_smi == the_hole) {
      to->set_the_hole(to_start);
    } else {
      to->set(to_start, Smi::cast(hole_or_smi)->value());
    }
  }
}


381
static void CopyPackedSmiToDoubleElements(FixedArrayBase* from_base,
382
                                          uint32_t from_start,
383
                                          FixedArrayBase* to_base,
384 385 386 387 388 389 390 391
                                          uint32_t to_start,
                                          int packed_size,
                                          int raw_copy_size) {
  int copy_size = raw_copy_size;
  uint32_t to_end;
  if (raw_copy_size < 0) {
    ASSERT(raw_copy_size == ElementsAccessor::kCopyToEnd ||
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
392
    copy_size = packed_size - from_start;
393
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
394
      to_end = to_base->length();
395
      for (uint32_t i = to_start + copy_size; i < to_end; ++i) {
396
        FixedDoubleArray::cast(to_base)->set_the_hole(i);
397
      }
398 399 400 401 402 403
    } else {
      to_end = to_start + static_cast<uint32_t>(copy_size);
    }
  } else {
    to_end = to_start + static_cast<uint32_t>(copy_size);
  }
404
  ASSERT(static_cast<int>(to_end) <= to_base->length());
405
  ASSERT(packed_size >= 0 && packed_size <= copy_size);
406 407
  ASSERT((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
         (copy_size + static_cast<int>(from_start)) <= from_base->length());
408
  if (copy_size == 0) return;
409 410
  FixedArray* from = FixedArray::cast(from_base);
  FixedDoubleArray* to = FixedDoubleArray::cast(to_base);
411 412 413 414 415 416 417 418 419
  for (uint32_t from_end = from_start + static_cast<uint32_t>(packed_size);
       from_start < from_end; from_start++, to_start++) {
    Object* smi = from->get(from_start);
    ASSERT(!smi->IsTheHole());
    to->set(to_start, Smi::cast(smi)->value());
  }
}


420
static void CopyObjectToDoubleElements(FixedArrayBase* from_base,
421
                                       uint32_t from_start,
422
                                       FixedArrayBase* to_base,
423 424 425 426 427 428
                                       uint32_t to_start,
                                       int raw_copy_size) {
  int copy_size = raw_copy_size;
  if (raw_copy_size < 0) {
    ASSERT(raw_copy_size == ElementsAccessor::kCopyToEnd ||
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
429
    copy_size = from_base->length() - from_start;
430
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
431 432
      for (int i = to_start + copy_size; i < to_base->length(); ++i) {
        FixedDoubleArray::cast(to_base)->set_the_hole(i);
433 434 435
      }
    }
  }
436 437
  ASSERT((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
         (copy_size + static_cast<int>(from_start)) <= from_base->length());
438
  if (copy_size == 0) return;
439 440
  FixedArray* from = FixedArray::cast(from_base);
  FixedDoubleArray* to = FixedDoubleArray::cast(to_base);
441 442 443 444 445 446
  Object* the_hole = from->GetHeap()->the_hole_value();
  for (uint32_t from_end = from_start + copy_size;
       from_start < from_end; from_start++, to_start++) {
    Object* hole_or_object = from->get(from_start);
    if (hole_or_object == the_hole) {
      to->set_the_hole(to_start);
447
    } else {
448
      to->set(to_start, hole_or_object->Number());
449 450 451 452 453
    }
  }
}


454
static void CopyDictionaryToDoubleElements(FixedArrayBase* from_base,
455
                                           uint32_t from_start,
456
                                           FixedArrayBase* to_base,
457 458
                                           uint32_t to_start,
                                           int raw_copy_size) {
459
  SeededNumberDictionary* from = SeededNumberDictionary::cast(from_base);
460 461 462 463 464 465
  int copy_size = raw_copy_size;
  if (copy_size < 0) {
    ASSERT(copy_size == ElementsAccessor::kCopyToEnd ||
           copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
    copy_size = from->max_number_key() + 1 - from_start;
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
466 467
      for (int i = to_start + copy_size; i < to_base->length(); ++i) {
        FixedDoubleArray::cast(to_base)->set_the_hole(i);
468 469 470 471
      }
    }
  }
  if (copy_size == 0) return;
472
  FixedDoubleArray* to = FixedDoubleArray::cast(to_base);
473 474 475 476
  uint32_t to_length = to->length();
  if (to_start + copy_size > to_length) {
    copy_size = to_length - to_start;
  }
477 478 479 480 481 482 483 484 485 486 487
  for (int i = 0; i < copy_size; i++) {
    int entry = from->FindEntry(i + from_start);
    if (entry != SeededNumberDictionary::kNotFound) {
      to->set(i + to_start, from->ValueAt(entry)->Number());
    } else {
      to->set_the_hole(i + to_start);
    }
  }
}


488 489
static void TraceTopFrame(Isolate* isolate) {
  StackFrameIterator it(isolate);
490 491 492 493 494 495 496 497 498 499 500 501 502 503
  if (it.done()) {
    PrintF("unknown location (no JavaScript frames present)");
    return;
  }
  StackFrame* raw_frame = it.frame();
  if (raw_frame->is_internal()) {
    Code* apply_builtin = isolate->builtins()->builtin(
        Builtins::kFunctionApply);
    if (raw_frame->unchecked_code() == apply_builtin) {
      PrintF("apply from ");
      it.Advance();
      raw_frame = it.frame();
    }
  }
504
  JavaScriptFrame::PrintTop(isolate, stdout, false, true);
505 506 507
}


508 509
void CheckArrayAbuse(JSObject* obj, const char* op, uint32_t key,
                     bool allow_appending) {
510 511 512 513 514 515 516 517 518 519 520 521 522 523
  Object* raw_length = NULL;
  const char* elements_type = "array";
  if (obj->IsJSArray()) {
    JSArray* array = JSArray::cast(obj);
    raw_length = array->length();
  } else {
    raw_length = Smi::FromInt(obj->elements()->length());
    elements_type = "object";
  }

  if (raw_length->IsNumber()) {
    double n = raw_length->Number();
    if (FastI2D(FastD2UI(n)) == n) {
      int32_t int32_length = DoubleToInt32(n);
524 525 526
      uint32_t compare_length = static_cast<uint32_t>(int32_length);
      if (allow_appending) compare_length++;
      if (key >= compare_length) {
527 528 529 530
        PrintF("[OOB %s %s (%s length = %d, element accessed = %d) in ",
               elements_type, op, elements_type,
               static_cast<int>(int32_length),
               static_cast<int>(key));
531
        TraceTopFrame(obj->GetIsolate());
532 533 534 535
        PrintF("]\n");
      }
    } else {
      PrintF("[%s elements length not integer value in ", elements_type);
536
      TraceTopFrame(obj->GetIsolate());
537 538 539 540
      PrintF("]\n");
    }
  } else {
    PrintF("[%s elements length not a number in ", elements_type);
541
    TraceTopFrame(obj->GetIsolate());
542 543 544 545 546
    PrintF("]\n");
  }
}


547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563
// Base class for element handler implementations. Contains the
// the common logic for objects with different ElementsKinds.
// Subclasses must specialize method for which the element
// implementation differs from the base class implementation.
//
// This class is intended to be used in the following way:
//
//   class SomeElementsAccessor :
//       public ElementsAccessorBase<SomeElementsAccessor,
//                                   BackingStoreClass> {
//     ...
//   }
//
// This is an example of the Curiously Recurring Template Pattern (see
// http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern).  We use
// CRTP to guarantee aggressive compile time optimizations (i.e.  inlining and
// specialization of SomeElementsAccessor methods).
564 565
template <typename ElementsAccessorSubclass,
          typename ElementsTraitsParam>
566
class ElementsAccessorBase : public ElementsAccessor {
567
 protected:
568 569 570 571 572 573 574
  explicit ElementsAccessorBase(const char* name)
      : ElementsAccessor(name) { }

  typedef ElementsTraitsParam ElementsTraits;
  typedef typename ElementsTraitsParam::BackingStore BackingStore;

  virtual ElementsKind kind() const { return ElementsTraits::Kind; }
575

576 577 578 579 580 581 582 583 584
  static void ValidateContents(JSObject* holder, int length) {
  }

  static void ValidateImpl(JSObject* holder) {
    FixedArrayBase* fixed_array_base = holder->elements();
    // When objects are first allocated, its elements are Failures.
    if (fixed_array_base->IsFailure()) return;
    if (!fixed_array_base->IsHeapObject()) return;
    // Arrays that have been shifted in place can't be verified.
585
    if (fixed_array_base->IsFiller()) return;
586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601
    int length = 0;
    if (holder->IsJSArray()) {
      Object* length_obj = JSArray::cast(holder)->length();
      if (length_obj->IsSmi()) {
        length = Smi::cast(length_obj)->value();
      }
    } else {
      length = fixed_array_base->length();
    }
    ElementsAccessorSubclass::ValidateContents(holder, length);
  }

  virtual void Validate(JSObject* holder) {
    ElementsAccessorSubclass::ValidateImpl(holder);
  }

602 603 604
  static bool HasElementImpl(Object* receiver,
                             JSObject* holder,
                             uint32_t key,
605
                             FixedArrayBase* backing_store) {
606 607
    return ElementsAccessorSubclass::GetAttributesImpl(
        receiver, holder, key, backing_store) != ABSENT;
608 609 610 611 612 613 614 615 616 617
  }

  virtual bool HasElement(Object* receiver,
                          JSObject* holder,
                          uint32_t key,
                          FixedArrayBase* backing_store) {
    if (backing_store == NULL) {
      backing_store = holder->elements();
    }
    return ElementsAccessorSubclass::HasElementImpl(
618
        receiver, holder, key, backing_store);
619 620
  }

621 622 623 624
  MUST_USE_RESULT virtual MaybeObject* Get(Object* receiver,
                                           JSObject* holder,
                                           uint32_t key,
                                           FixedArrayBase* backing_store) {
625 626 627
    if (backing_store == NULL) {
      backing_store = holder->elements();
    }
628

629 630 631 632 633 634 635 636
    if (!IsExternalArrayElementsKind(ElementsTraits::Kind) &&
        FLAG_trace_js_array_abuse) {
      CheckArrayAbuse(holder, "elements read", key);
    }

    if (IsExternalArrayElementsKind(ElementsTraits::Kind) &&
        FLAG_trace_external_array_abuse) {
      CheckArrayAbuse(holder, "external elements read", key);
637 638
    }

639
    return ElementsAccessorSubclass::GetImpl(
640
        receiver, holder, key, backing_store);
641 642
  }

643 644 645
  MUST_USE_RESULT static MaybeObject* GetImpl(Object* receiver,
                                              JSObject* obj,
                                              uint32_t key,
646
                                              FixedArrayBase* backing_store) {
647
    return (key < ElementsAccessorSubclass::GetCapacityImpl(backing_store))
648
           ? BackingStore::cast(backing_store)->get(key)
649
           : backing_store->GetHeap()->the_hole_value();
650 651
  }

652 653 654 655 656 657 658 659 660
  MUST_USE_RESULT virtual PropertyAttributes GetAttributes(
      Object* receiver,
      JSObject* holder,
      uint32_t key,
      FixedArrayBase* backing_store) {
    if (backing_store == NULL) {
      backing_store = holder->elements();
    }
    return ElementsAccessorSubclass::GetAttributesImpl(
661
        receiver, holder, key, backing_store);
662 663 664 665 666 667
  }

  MUST_USE_RESULT static PropertyAttributes GetAttributesImpl(
        Object* receiver,
        JSObject* obj,
        uint32_t key,
668
        FixedArrayBase* backing_store) {
669 670 671
    if (key >= ElementsAccessorSubclass::GetCapacityImpl(backing_store)) {
      return ABSENT;
    }
672
    return BackingStore::cast(backing_store)->is_the_hole(key) ? ABSENT : NONE;
673 674
  }

675 676 677 678 679 680 681 682 683
  MUST_USE_RESULT virtual PropertyType GetType(
      Object* receiver,
      JSObject* holder,
      uint32_t key,
      FixedArrayBase* backing_store) {
    if (backing_store == NULL) {
      backing_store = holder->elements();
    }
    return ElementsAccessorSubclass::GetTypeImpl(
684
        receiver, holder, key, backing_store);
685 686 687 688 689 690
  }

  MUST_USE_RESULT static PropertyType GetTypeImpl(
        Object* receiver,
        JSObject* obj,
        uint32_t key,
691
        FixedArrayBase* backing_store) {
692 693 694
    if (key >= ElementsAccessorSubclass::GetCapacityImpl(backing_store)) {
      return NONEXISTENT;
    }
695 696
    return BackingStore::cast(backing_store)->is_the_hole(key)
        ? NONEXISTENT : FIELD;
697 698 699 700 701 702 703 704 705 706 707
  }

  MUST_USE_RESULT virtual AccessorPair* GetAccessorPair(
      Object* receiver,
      JSObject* holder,
      uint32_t key,
      FixedArrayBase* backing_store) {
    if (backing_store == NULL) {
      backing_store = holder->elements();
    }
    return ElementsAccessorSubclass::GetAccessorPairImpl(
708
        receiver, holder, key, backing_store);
709 710 711 712 713 714
  }

  MUST_USE_RESULT static AccessorPair* GetAccessorPairImpl(
        Object* receiver,
        JSObject* obj,
        uint32_t key,
715
        FixedArrayBase* backing_store) {
716 717 718
    return NULL;
  }

719 720
  MUST_USE_RESULT virtual MaybeObject* SetLength(JSArray* array,
                                                 Object* length) {
721
    return ElementsAccessorSubclass::SetLengthImpl(
722
        array, length, array->elements());
723 724
  }

725 726 727
  MUST_USE_RESULT static MaybeObject* SetLengthImpl(
      JSObject* obj,
      Object* length,
728
      FixedArrayBase* backing_store);
729

730 731 732 733
  MUST_USE_RESULT virtual MaybeObject* SetCapacityAndLength(
      JSArray* array,
      int capacity,
      int length) {
734 735 736 737 738 739
    return ElementsAccessorSubclass::SetFastElementsCapacityAndLength(
        array,
        capacity,
        length);
  }

740 741 742 743
  MUST_USE_RESULT static MaybeObject* SetFastElementsCapacityAndLength(
      JSObject* obj,
      int capacity,
      int length) {
744 745 746 747
    UNIMPLEMENTED();
    return obj;
  }

748 749 750
  MUST_USE_RESULT virtual MaybeObject* Delete(JSObject* obj,
                                              uint32_t key,
                                              JSReceiver::DeleteMode mode) = 0;
751

752 753 754
  MUST_USE_RESULT static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                                       uint32_t from_start,
                                                       FixedArrayBase* to,
755
                                                       ElementsKind from_kind,
756
                                                       uint32_t to_start,
757
                                                       int packed_size,
758
                                                       int copy_size) {
759 760 761 762
    UNREACHABLE();
    return NULL;
  }

763 764
  MUST_USE_RESULT virtual MaybeObject* CopyElements(JSObject* from_holder,
                                                    uint32_t from_start,
765
                                                    ElementsKind from_kind,
766 767 768 769
                                                    FixedArrayBase* to,
                                                    uint32_t to_start,
                                                    int copy_size,
                                                    FixedArrayBase* from) {
770
    int packed_size = kPackedSizeNotKnown;
771 772 773
    if (from == NULL) {
      from = from_holder->elements();
    }
774 775

    if (from_holder) {
776
      bool is_packed = IsFastPackedElementsKind(from_kind) &&
777 778 779 780 781 782 783 784
          from_holder->IsJSArray();
      if (is_packed) {
        packed_size = Smi::cast(JSArray::cast(from_holder)->length())->value();
        if (copy_size >= 0 && packed_size > copy_size) {
          packed_size = copy_size;
        }
      }
    }
785
    return ElementsAccessorSubclass::CopyElementsImpl(
786
        from, from_start, to, from_kind, to_start, packed_size, copy_size);
787 788
  }

789 790 791 792 793
  MUST_USE_RESULT virtual MaybeObject* AddElementsToFixedArray(
      Object* receiver,
      JSObject* holder,
      FixedArray* to,
      FixedArrayBase* from) {
794
    int len0 = to->length();
795 796 797
#ifdef DEBUG
    if (FLAG_enable_slow_asserts) {
      for (int i = 0; i < len0; i++) {
798
        ASSERT(!to->get(i)->IsTheHole());
799 800 801
      }
    }
#endif
802 803 804
    if (from == NULL) {
      from = holder->elements();
    }
805 806

    // Optimize if 'other' is empty.
807
    // We cannot optimize if 'this' is empty, as other may have holes.
808
    uint32_t len1 = ElementsAccessorSubclass::GetCapacityImpl(from);
809
    if (len1 == 0) return to;
810 811

    // Compute how many elements are not in other.
812
    uint32_t extra = 0;
813
    for (uint32_t y = 0; y < len1; y++) {
814
      uint32_t key = ElementsAccessorSubclass::GetKeyForIndexImpl(from, y);
815
      if (ElementsAccessorSubclass::HasElementImpl(
816
              receiver, holder, key, from)) {
817
        MaybeObject* maybe_value =
818
            ElementsAccessorSubclass::GetImpl(receiver, holder, key, from);
819
        Object* value;
820
        if (!maybe_value->To(&value)) return maybe_value;
821 822 823 824 825
        ASSERT(!value->IsTheHole());
        if (!HasKey(to, value)) {
          extra++;
        }
      }
826 827
    }

828
    if (extra == 0) return to;
829 830 831

    // Allocate the result
    FixedArray* result;
832 833
    MaybeObject* maybe_obj = from->GetHeap()->AllocateFixedArray(len0 + extra);
    if (!maybe_obj->To(&result)) return maybe_obj;
834 835 836

    // Fill in the content
    {
837
      DisallowHeapAllocation no_gc;
838 839
      WriteBarrierMode mode = result->GetWriteBarrierMode(no_gc);
      for (int i = 0; i < len0; i++) {
840
        Object* e = to->get(i);
841 842 843 844
        ASSERT(e->IsString() || e->IsNumber());
        result->set(i, e, mode);
      }
    }
845
    // Fill in the extra values.
846
    uint32_t index = 0;
847
    for (uint32_t y = 0; y < len1; y++) {
848
      uint32_t key =
849
          ElementsAccessorSubclass::GetKeyForIndexImpl(from, y);
850
      if (ElementsAccessorSubclass::HasElementImpl(
851
              receiver, holder, key, from)) {
852
        MaybeObject* maybe_value =
853
            ElementsAccessorSubclass::GetImpl(receiver, holder, key, from);
854
        Object* value;
855
        if (!maybe_value->To(&value)) return maybe_value;
856 857 858 859
        if (!value->IsTheHole() && !HasKey(to, value)) {
          result->set(len0 + index, value);
          index++;
        }
860 861 862 863 864 865
      }
    }
    ASSERT(extra == index);
    return result;
  }

866
 protected:
867
  static uint32_t GetCapacityImpl(FixedArrayBase* backing_store) {
868
    return backing_store->length();
869 870
  }

871
  virtual uint32_t GetCapacity(FixedArrayBase* backing_store) {
872
    return ElementsAccessorSubclass::GetCapacityImpl(backing_store);
873 874
  }

875
  static uint32_t GetKeyForIndexImpl(FixedArrayBase* backing_store,
876
                                     uint32_t index) {
877 878 879 880
    return index;
  }

  virtual uint32_t GetKeyForIndex(FixedArrayBase* backing_store,
881
                                  uint32_t index) {
882
    return ElementsAccessorSubclass::GetKeyForIndexImpl(backing_store, index);
883 884 885 886 887 888 889
  }

 private:
  DISALLOW_COPY_AND_ASSIGN(ElementsAccessorBase);
};


890 891
// Super class for all fast element arrays.
template<typename FastElementsAccessorSubclass,
892
         typename KindTraits,
893
         int ElementSize>
894
class FastElementsAccessor
895
    : public ElementsAccessorBase<FastElementsAccessorSubclass, KindTraits> {
896 897 898
 public:
  explicit FastElementsAccessor(const char* name)
      : ElementsAccessorBase<FastElementsAccessorSubclass,
899
                             KindTraits>(name) {}
900
 protected:
901
  friend class ElementsAccessorBase<FastElementsAccessorSubclass, KindTraits>;
902
  friend class NonStrictArgumentsElementsAccessor;
903 904

  typedef typename KindTraits::BackingStore BackingStore;
905 906 907

  // Adjusts the length of the fast backing store or returns the new length or
  // undefined in case conversion to a slow backing store should be performed.
908
  static MaybeObject* SetLengthWithoutNormalize(FixedArrayBase* backing_store,
909 910 911 912
                                                JSArray* array,
                                                Object* length_object,
                                                uint32_t length) {
    uint32_t old_capacity = backing_store->length();
913
    Object* old_length = array->length();
914 915
    bool same_or_smaller_size = old_length->IsSmi() &&
        static_cast<uint32_t>(Smi::cast(old_length)->value()) >= length;
916 917
    ElementsKind kind = array->GetElementsKind();

918
    if (!same_or_smaller_size && IsFastElementsKind(kind) &&
919 920 921 922 923
        !IsFastHoleyElementsKind(kind)) {
      kind = GetHoleyElementsKind(kind);
      MaybeObject* maybe_obj = array->TransitionElementsKind(kind);
      if (maybe_obj->IsFailure()) return maybe_obj;
    }
924 925 926

    // Check whether the backing store should be shrunk.
    if (length <= old_capacity) {
927
      if (array->HasFastSmiOrObjectElements()) {
928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943
        MaybeObject* maybe_obj = array->EnsureWritableFastElements();
        if (!maybe_obj->To(&backing_store)) return maybe_obj;
      }
      if (2 * length <= old_capacity) {
        // If more than half the elements won't be used, trim the array.
        if (length == 0) {
          array->initialize_elements();
        } else {
          backing_store->set_length(length);
          Address filler_start = backing_store->address() +
              BackingStore::OffsetOfElementAt(length);
          int filler_size = (old_capacity - length) * ElementSize;
          array->GetHeap()->CreateFillerObjectAt(filler_start, filler_size);
        }
      } else {
        // Otherwise, fill the unused tail with holes.
944
        int old_length = FastD2IChecked(array->length()->Number());
945
        for (int i = length; i < old_length; i++) {
946
          BackingStore::cast(backing_store)->set_the_hole(i);
947 948 949 950 951 952 953 954 955 956 957 958
        }
      }
      return length_object;
    }

    // Check whether the backing store should be expanded.
    uint32_t min = JSObject::NewElementsCapacity(old_capacity);
    uint32_t new_capacity = length > min ? length : min;
    if (!array->ShouldConvertToSlowElements(new_capacity)) {
      MaybeObject* result = FastElementsAccessorSubclass::
          SetFastElementsCapacityAndLength(array, new_capacity, length);
      if (result->IsFailure()) return result;
959
      array->ValidateElements();
960 961 962 963 964 965
      return length_object;
    }

    // Request conversion to slow elements.
    return array->GetHeap()->undefined_value();
  }
966

967
  static MaybeObject* DeleteCommon(JSObject* obj,
968 969 970 971
                                   uint32_t key,
                                   JSReceiver::DeleteMode mode) {
    ASSERT(obj->HasFastSmiOrObjectElements() ||
           obj->HasFastDoubleElements() ||
972
           obj->HasFastArgumentsElements());
973
    Heap* heap = obj->GetHeap();
974 975 976 977 978 979 980 981 982
    Object* elements = obj->elements();
    if (elements == heap->empty_fixed_array()) {
      return heap->true_value();
    }
    typename KindTraits::BackingStore* backing_store =
        KindTraits::BackingStore::cast(elements);
    bool is_non_strict_arguments_elements_map =
        backing_store->map() == heap->non_strict_arguments_elements_map();
    if (is_non_strict_arguments_elements_map) {
983 984
      backing_store = KindTraits::BackingStore::cast(
          FixedArray::cast(backing_store)->get(1));
985 986 987 988 989
    }
    uint32_t length = static_cast<uint32_t>(
        obj->IsJSArray()
        ? Smi::cast(JSArray::cast(obj)->length())->value()
        : backing_store->length());
990
    if (key < length) {
991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004
      if (!is_non_strict_arguments_elements_map) {
        ElementsKind kind = KindTraits::Kind;
        if (IsFastPackedElementsKind(kind)) {
          MaybeObject* transitioned =
              obj->TransitionElementsKind(GetHoleyElementsKind(kind));
          if (transitioned->IsFailure()) return transitioned;
        }
        if (IsFastSmiOrObjectElementsKind(KindTraits::Kind)) {
          Object* writable;
          MaybeObject* maybe = obj->EnsureWritableFastElements();
          if (!maybe->ToObject(&writable)) return maybe;
          backing_store = KindTraits::BackingStore::cast(writable);
        }
      }
1005
      backing_store->set_the_hole(key);
1006 1007 1008 1009 1010 1011 1012
      // If an old space backing store is larger than a certain size and
      // has too few used values, normalize it.
      // To avoid doing the check on every delete we require at least
      // one adjacent hole to the value being deleted.
      const int kMinLengthForSparsenessCheck = 64;
      if (backing_store->length() >= kMinLengthForSparsenessCheck &&
          !heap->InNewSpace(backing_store) &&
1013 1014
          ((key > 0 && backing_store->is_the_hole(key - 1)) ||
           (key + 1 < length && backing_store->is_the_hole(key + 1)))) {
1015 1016
        int num_used = 0;
        for (int i = 0; i < backing_store->length(); ++i) {
1017
          if (!backing_store->is_the_hole(i)) ++num_used;
1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029
          // Bail out early if more than 1/4 is used.
          if (4 * num_used > backing_store->length()) break;
        }
        if (4 * num_used <= backing_store->length()) {
          MaybeObject* result = obj->NormalizeElements();
          if (result->IsFailure()) return result;
        }
      }
    }
    return heap->true_value();
  }

1030 1031 1032 1033 1034 1035 1036 1037 1038 1039
  virtual MaybeObject* Delete(JSObject* obj,
                              uint32_t key,
                              JSReceiver::DeleteMode mode) {
    return DeleteCommon(obj, key, mode);
  }

  static bool HasElementImpl(
      Object* receiver,
      JSObject* holder,
      uint32_t key,
1040
      FixedArrayBase* backing_store) {
1041 1042 1043
    if (key >= static_cast<uint32_t>(backing_store->length())) {
      return false;
    }
1044
    return !BackingStore::cast(backing_store)->is_the_hole(key);
1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070
  }

  static void ValidateContents(JSObject* holder, int length) {
#if DEBUG
    FixedArrayBase* elements = holder->elements();
    Heap* heap = elements->GetHeap();
    Map* map = elements->map();
    ASSERT((IsFastSmiOrObjectElementsKind(KindTraits::Kind) &&
            (map == heap->fixed_array_map() ||
             map == heap->fixed_cow_array_map())) ||
           (IsFastDoubleElementsKind(KindTraits::Kind) ==
            ((map == heap->fixed_array_map() && length == 0) ||
             map == heap->fixed_double_array_map())));
    for (int i = 0; i < length; i++) {
      typename KindTraits::BackingStore* backing_store =
          KindTraits::BackingStore::cast(elements);
      ASSERT((!IsFastSmiElementsKind(KindTraits::Kind) ||
              static_cast<Object*>(backing_store->get(i))->IsSmi()) ||
             (IsFastHoleyElementsKind(KindTraits::Kind) ==
              backing_store->is_the_hole(i)));
    }
#endif
  }
};


1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105
static inline ElementsKind ElementsKindForArray(FixedArrayBase* array) {
  switch (array->map()->instance_type()) {
    case FIXED_ARRAY_TYPE:
      if (array->IsDictionary()) {
        return DICTIONARY_ELEMENTS;
      } else {
        return FAST_HOLEY_ELEMENTS;
      }
    case FIXED_DOUBLE_ARRAY_TYPE:
      return FAST_HOLEY_DOUBLE_ELEMENTS;
    case EXTERNAL_BYTE_ARRAY_TYPE:
      return EXTERNAL_BYTE_ELEMENTS;
    case EXTERNAL_UNSIGNED_BYTE_ARRAY_TYPE:
      return EXTERNAL_UNSIGNED_BYTE_ELEMENTS;
    case EXTERNAL_SHORT_ARRAY_TYPE:
      return EXTERNAL_SHORT_ELEMENTS;
    case EXTERNAL_UNSIGNED_SHORT_ARRAY_TYPE:
      return EXTERNAL_UNSIGNED_SHORT_ELEMENTS;
    case EXTERNAL_INT_ARRAY_TYPE:
      return EXTERNAL_INT_ELEMENTS;
    case EXTERNAL_UNSIGNED_INT_ARRAY_TYPE:
      return EXTERNAL_UNSIGNED_INT_ELEMENTS;
    case EXTERNAL_FLOAT_ARRAY_TYPE:
      return EXTERNAL_FLOAT_ELEMENTS;
    case EXTERNAL_DOUBLE_ARRAY_TYPE:
      return EXTERNAL_DOUBLE_ELEMENTS;
    case EXTERNAL_PIXEL_ARRAY_TYPE:
      return EXTERNAL_PIXEL_ELEMENTS;
    default:
      UNREACHABLE();
  }
  return FAST_HOLEY_ELEMENTS;
}


1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117
template<typename FastElementsAccessorSubclass,
         typename KindTraits>
class FastSmiOrObjectElementsAccessor
    : public FastElementsAccessor<FastElementsAccessorSubclass,
                                  KindTraits,
                                  kPointerSize> {
 public:
  explicit FastSmiOrObjectElementsAccessor(const char* name)
      : FastElementsAccessor<FastElementsAccessorSubclass,
                             KindTraits,
                             kPointerSize>(name) {}

1118 1119 1120
  static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                       uint32_t from_start,
                                       FixedArrayBase* to,
1121
                                       ElementsKind from_kind,
1122
                                       uint32_t to_start,
1123
                                       int packed_size,
1124
                                       int copy_size) {
1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150
    ElementsKind to_kind = KindTraits::Kind;
    switch (from_kind) {
      case FAST_SMI_ELEMENTS:
      case FAST_HOLEY_SMI_ELEMENTS:
      case FAST_ELEMENTS:
      case FAST_HOLEY_ELEMENTS:
        CopyObjectToObjectElements(
            from, from_kind, from_start, to, to_kind, to_start, copy_size);
        return to->GetHeap()->undefined_value();
      case FAST_DOUBLE_ELEMENTS:
      case FAST_HOLEY_DOUBLE_ELEMENTS:
        return CopyDoubleToObjectElements(
            from, from_start, to, to_kind, to_start, copy_size);
      case DICTIONARY_ELEMENTS:
        CopyDictionaryToObjectElements(
            from, from_start, to, to_kind, to_start, copy_size);
        return to->GetHeap()->undefined_value();
      case NON_STRICT_ARGUMENTS_ELEMENTS: {
        // TODO(verwaest): This is a temporary hack to support extending
        // NON_STRICT_ARGUMENTS_ELEMENTS in SetFastElementsCapacityAndLength.
        // This case should be UNREACHABLE().
        FixedArray* parameter_map = FixedArray::cast(from);
        FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1));
        ElementsKind from_kind = ElementsKindForArray(arguments);
        return CopyElementsImpl(arguments, from_start, to, from_kind,
                                to_start, packed_size, copy_size);
1151
      }
1152 1153 1154 1155 1156 1157 1158 1159 1160 1161
      case EXTERNAL_BYTE_ELEMENTS:
      case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
      case EXTERNAL_SHORT_ELEMENTS:
      case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
      case EXTERNAL_INT_ELEMENTS:
      case EXTERNAL_UNSIGNED_INT_ELEMENTS:
      case EXTERNAL_FLOAT_ELEMENTS:
      case EXTERNAL_DOUBLE_ELEMENTS:
      case EXTERNAL_PIXEL_ELEMENTS:
        UNREACHABLE();
1162
    }
1163
    return NULL;
1164 1165 1166
  }


1167 1168 1169
  static MaybeObject* SetFastElementsCapacityAndLength(JSObject* obj,
                                                       uint32_t capacity,
                                                       uint32_t length) {
1170 1171 1172 1173
    JSObject::SetFastElementsCapacitySmiMode set_capacity_mode =
        obj->HasFastSmiElements()
            ? JSObject::kAllowSmiElements
            : JSObject::kDontAllowSmiElements;
1174 1175 1176 1177
    return obj->SetFastElementsCapacityAndLength(capacity,
                                                 length,
                                                 set_capacity_mode);
  }
1178
};
1179

1180

1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201
class FastPackedSmiElementsAccessor
    : public FastSmiOrObjectElementsAccessor<
        FastPackedSmiElementsAccessor,
        ElementsKindTraits<FAST_SMI_ELEMENTS> > {
 public:
  explicit FastPackedSmiElementsAccessor(const char* name)
      : FastSmiOrObjectElementsAccessor<
          FastPackedSmiElementsAccessor,
          ElementsKindTraits<FAST_SMI_ELEMENTS> >(name) {}
};


class FastHoleySmiElementsAccessor
    : public FastSmiOrObjectElementsAccessor<
        FastHoleySmiElementsAccessor,
        ElementsKindTraits<FAST_HOLEY_SMI_ELEMENTS> > {
 public:
  explicit FastHoleySmiElementsAccessor(const char* name)
      : FastSmiOrObjectElementsAccessor<
          FastHoleySmiElementsAccessor,
          ElementsKindTraits<FAST_HOLEY_SMI_ELEMENTS> >(name) {}
1202 1203 1204
};


1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230
class FastPackedObjectElementsAccessor
    : public FastSmiOrObjectElementsAccessor<
        FastPackedObjectElementsAccessor,
        ElementsKindTraits<FAST_ELEMENTS> > {
 public:
  explicit FastPackedObjectElementsAccessor(const char* name)
      : FastSmiOrObjectElementsAccessor<
          FastPackedObjectElementsAccessor,
          ElementsKindTraits<FAST_ELEMENTS> >(name) {}
};


class FastHoleyObjectElementsAccessor
    : public FastSmiOrObjectElementsAccessor<
        FastHoleyObjectElementsAccessor,
        ElementsKindTraits<FAST_HOLEY_ELEMENTS> > {
 public:
  explicit FastHoleyObjectElementsAccessor(const char* name)
      : FastSmiOrObjectElementsAccessor<
          FastHoleyObjectElementsAccessor,
          ElementsKindTraits<FAST_HOLEY_ELEMENTS> >(name) {}
};


template<typename FastElementsAccessorSubclass,
         typename KindTraits>
1231
class FastDoubleElementsAccessor
1232 1233
    : public FastElementsAccessor<FastElementsAccessorSubclass,
                                  KindTraits,
1234
                                  kDoubleSize> {
1235 1236
 public:
  explicit FastDoubleElementsAccessor(const char* name)
1237 1238
      : FastElementsAccessor<FastElementsAccessorSubclass,
                             KindTraits,
1239 1240
                             kDoubleSize>(name) {}

1241 1242 1243
  static MaybeObject* SetFastElementsCapacityAndLength(JSObject* obj,
                                                       uint32_t capacity,
                                                       uint32_t length) {
1244 1245
    return obj->SetFastDoubleElementsCapacityAndLength(capacity,
                                                       length);
1246 1247
  }

1248
 protected:
1249 1250 1251
  static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                       uint32_t from_start,
                                       FixedArrayBase* to,
1252
                                       ElementsKind from_kind,
1253
                                       uint32_t to_start,
1254
                                       int packed_size,
1255
                                       int copy_size) {
1256
    switch (from_kind) {
1257
      case FAST_SMI_ELEMENTS:
1258 1259 1260
        CopyPackedSmiToDoubleElements(
            from, from_start, to, to_start, packed_size, copy_size);
        break;
1261
      case FAST_HOLEY_SMI_ELEMENTS:
1262 1263
        CopySmiToDoubleElements(from, from_start, to, to_start, copy_size);
        break;
1264
      case FAST_DOUBLE_ELEMENTS:
1265
      case FAST_HOLEY_DOUBLE_ELEMENTS:
1266
        CopyDoubleToDoubleElements(from, from_start, to, to_start, copy_size);
1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285
        break;
      case FAST_ELEMENTS:
      case FAST_HOLEY_ELEMENTS:
        CopyObjectToDoubleElements(from, from_start, to, to_start, copy_size);
        break;
      case DICTIONARY_ELEMENTS:
        CopyDictionaryToDoubleElements(
            from, from_start, to, to_start, copy_size);
        break;
      case NON_STRICT_ARGUMENTS_ELEMENTS:
      case EXTERNAL_BYTE_ELEMENTS:
      case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
      case EXTERNAL_SHORT_ELEMENTS:
      case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
      case EXTERNAL_INT_ELEMENTS:
      case EXTERNAL_UNSIGNED_INT_ELEMENTS:
      case EXTERNAL_FLOAT_ELEMENTS:
      case EXTERNAL_DOUBLE_ELEMENTS:
      case EXTERNAL_PIXEL_ELEMENTS:
1286 1287 1288 1289
        UNREACHABLE();
    }
    return to->GetHeap()->undefined_value();
  }
1290
};
1291

1292

1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318
class FastPackedDoubleElementsAccessor
    : public FastDoubleElementsAccessor<
        FastPackedDoubleElementsAccessor,
        ElementsKindTraits<FAST_DOUBLE_ELEMENTS> > {
 public:
  friend class ElementsAccessorBase<FastPackedDoubleElementsAccessor,
                                    ElementsKindTraits<FAST_DOUBLE_ELEMENTS> >;
  explicit FastPackedDoubleElementsAccessor(const char* name)
      : FastDoubleElementsAccessor<
          FastPackedDoubleElementsAccessor,
          ElementsKindTraits<FAST_DOUBLE_ELEMENTS> >(name) {}
};


class FastHoleyDoubleElementsAccessor
    : public FastDoubleElementsAccessor<
        FastHoleyDoubleElementsAccessor,
        ElementsKindTraits<FAST_HOLEY_DOUBLE_ELEMENTS> > {
 public:
  friend class ElementsAccessorBase<
    FastHoleyDoubleElementsAccessor,
    ElementsKindTraits<FAST_HOLEY_DOUBLE_ELEMENTS> >;
  explicit FastHoleyDoubleElementsAccessor(const char* name)
      : FastDoubleElementsAccessor<
          FastHoleyDoubleElementsAccessor,
          ElementsKindTraits<FAST_HOLEY_DOUBLE_ELEMENTS> >(name) {}
1319 1320 1321 1322 1323
};


// Super class for all external element arrays.
template<typename ExternalElementsAccessorSubclass,
1324
         ElementsKind Kind>
1325 1326
class ExternalElementsAccessor
    : public ElementsAccessorBase<ExternalElementsAccessorSubclass,
1327
                                  ElementsKindTraits<Kind> > {
1328 1329 1330
 public:
  explicit ExternalElementsAccessor(const char* name)
      : ElementsAccessorBase<ExternalElementsAccessorSubclass,
1331
                             ElementsKindTraits<Kind> >(name) {}
1332

1333
 protected:
1334 1335
  typedef typename ElementsKindTraits<Kind>::BackingStore BackingStore;

1336
  friend class ElementsAccessorBase<ExternalElementsAccessorSubclass,
1337
                                    ElementsKindTraits<Kind> >;
1338

1339 1340 1341
  MUST_USE_RESULT static MaybeObject* GetImpl(Object* receiver,
                                              JSObject* obj,
                                              uint32_t key,
1342
                                              FixedArrayBase* backing_store) {
1343 1344
    return
        key < ExternalElementsAccessorSubclass::GetCapacityImpl(backing_store)
1345
        ? BackingStore::cast(backing_store)->get(key)
1346
        : backing_store->GetHeap()->undefined_value();
1347
  }
1348

1349 1350 1351 1352
  MUST_USE_RESULT static PropertyAttributes GetAttributesImpl(
      Object* receiver,
      JSObject* obj,
      uint32_t key,
1353
      FixedArrayBase* backing_store) {
1354 1355
    return
        key < ExternalElementsAccessorSubclass::GetCapacityImpl(backing_store)
1356 1357 1358 1359 1360 1361 1362
          ? NONE : ABSENT;
  }

  MUST_USE_RESULT static PropertyType GetTypeImpl(
      Object* receiver,
      JSObject* obj,
      uint32_t key,
1363
      FixedArrayBase* backing_store) {
1364 1365 1366
    return
        key < ExternalElementsAccessorSubclass::GetCapacityImpl(backing_store)
          ? FIELD : NONEXISTENT;
1367 1368
  }

1369 1370 1371
  MUST_USE_RESULT static MaybeObject* SetLengthImpl(
      JSObject* obj,
      Object* length,
1372
      FixedArrayBase* backing_store) {
1373 1374 1375 1376 1377
    // External arrays do not support changing their length.
    UNREACHABLE();
    return obj;
  }

1378 1379 1380
  MUST_USE_RESULT virtual MaybeObject* Delete(JSObject* obj,
                                              uint32_t key,
                                              JSReceiver::DeleteMode mode) {
1381 1382 1383
    // External arrays always ignore deletes.
    return obj->GetHeap()->true_value();
  }
1384

1385
  static bool HasElementImpl(Object* receiver,
1386
                             JSObject* holder,
1387
                             uint32_t key,
1388
                             FixedArrayBase* backing_store) {
1389 1390 1391 1392
    uint32_t capacity =
        ExternalElementsAccessorSubclass::GetCapacityImpl(backing_store);
    return key < capacity;
  }
1393 1394 1395 1396 1397
};


class ExternalByteElementsAccessor
    : public ExternalElementsAccessor<ExternalByteElementsAccessor,
1398
                                      EXTERNAL_BYTE_ELEMENTS> {
1399 1400 1401
 public:
  explicit ExternalByteElementsAccessor(const char* name)
      : ExternalElementsAccessor<ExternalByteElementsAccessor,
1402
                                 EXTERNAL_BYTE_ELEMENTS>(name) {}
1403 1404 1405 1406 1407
};


class ExternalUnsignedByteElementsAccessor
    : public ExternalElementsAccessor<ExternalUnsignedByteElementsAccessor,
1408
                                      EXTERNAL_UNSIGNED_BYTE_ELEMENTS> {
1409 1410 1411
 public:
  explicit ExternalUnsignedByteElementsAccessor(const char* name)
      : ExternalElementsAccessor<ExternalUnsignedByteElementsAccessor,
1412
                                 EXTERNAL_UNSIGNED_BYTE_ELEMENTS>(name) {}
1413 1414 1415 1416 1417
};


class ExternalShortElementsAccessor
    : public ExternalElementsAccessor<ExternalShortElementsAccessor,
1418
                                      EXTERNAL_SHORT_ELEMENTS> {
1419 1420 1421
 public:
  explicit ExternalShortElementsAccessor(const char* name)
      : ExternalElementsAccessor<ExternalShortElementsAccessor,
1422
                                 EXTERNAL_SHORT_ELEMENTS>(name) {}
1423 1424 1425 1426 1427
};


class ExternalUnsignedShortElementsAccessor
    : public ExternalElementsAccessor<ExternalUnsignedShortElementsAccessor,
1428
                                      EXTERNAL_UNSIGNED_SHORT_ELEMENTS> {
1429 1430 1431
 public:
  explicit ExternalUnsignedShortElementsAccessor(const char* name)
      : ExternalElementsAccessor<ExternalUnsignedShortElementsAccessor,
1432
                                 EXTERNAL_UNSIGNED_SHORT_ELEMENTS>(name) {}
1433 1434 1435 1436 1437
};


class ExternalIntElementsAccessor
    : public ExternalElementsAccessor<ExternalIntElementsAccessor,
1438
                                      EXTERNAL_INT_ELEMENTS> {
1439 1440 1441
 public:
  explicit ExternalIntElementsAccessor(const char* name)
      : ExternalElementsAccessor<ExternalIntElementsAccessor,
1442
                                 EXTERNAL_INT_ELEMENTS>(name) {}
1443 1444 1445 1446 1447
};


class ExternalUnsignedIntElementsAccessor
    : public ExternalElementsAccessor<ExternalUnsignedIntElementsAccessor,
1448
                                      EXTERNAL_UNSIGNED_INT_ELEMENTS> {
1449 1450 1451
 public:
  explicit ExternalUnsignedIntElementsAccessor(const char* name)
      : ExternalElementsAccessor<ExternalUnsignedIntElementsAccessor,
1452
                                 EXTERNAL_UNSIGNED_INT_ELEMENTS>(name) {}
1453 1454 1455 1456 1457
};


class ExternalFloatElementsAccessor
    : public ExternalElementsAccessor<ExternalFloatElementsAccessor,
1458
                                      EXTERNAL_FLOAT_ELEMENTS> {
1459 1460 1461
 public:
  explicit ExternalFloatElementsAccessor(const char* name)
      : ExternalElementsAccessor<ExternalFloatElementsAccessor,
1462
                                 EXTERNAL_FLOAT_ELEMENTS>(name) {}
1463 1464 1465 1466 1467
};


class ExternalDoubleElementsAccessor
    : public ExternalElementsAccessor<ExternalDoubleElementsAccessor,
1468
                                      EXTERNAL_DOUBLE_ELEMENTS> {
1469 1470 1471
 public:
  explicit ExternalDoubleElementsAccessor(const char* name)
      : ExternalElementsAccessor<ExternalDoubleElementsAccessor,
1472
                                 EXTERNAL_DOUBLE_ELEMENTS>(name) {}
1473 1474 1475 1476 1477
};


class PixelElementsAccessor
    : public ExternalElementsAccessor<PixelElementsAccessor,
1478
                                      EXTERNAL_PIXEL_ELEMENTS> {
1479 1480 1481
 public:
  explicit PixelElementsAccessor(const char* name)
      : ExternalElementsAccessor<PixelElementsAccessor,
1482
                                 EXTERNAL_PIXEL_ELEMENTS>(name) {}
1483 1484 1485 1486 1487
};


class DictionaryElementsAccessor
    : public ElementsAccessorBase<DictionaryElementsAccessor,
1488
                                  ElementsKindTraits<DICTIONARY_ELEMENTS> > {
1489
 public:
1490 1491
  explicit DictionaryElementsAccessor(const char* name)
      : ElementsAccessorBase<DictionaryElementsAccessor,
1492
                             ElementsKindTraits<DICTIONARY_ELEMENTS> >(name) {}
1493

1494 1495
  // Adjusts the length of the dictionary backing store and returns the new
  // length according to ES5 section 15.4.5.2 behavior.
1496
  MUST_USE_RESULT static MaybeObject* SetLengthWithoutNormalize(
1497
      FixedArrayBase* store,
1498 1499 1500
      JSArray* array,
      Object* length_object,
      uint32_t length) {
1501
    SeededNumberDictionary* dict = SeededNumberDictionary::cast(store);
1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525
    Heap* heap = array->GetHeap();
    int capacity = dict->Capacity();
    uint32_t new_length = length;
    uint32_t old_length = static_cast<uint32_t>(array->length()->Number());
    if (new_length < old_length) {
      // Find last non-deletable element in range of elements to be
      // deleted and adjust range accordingly.
      for (int i = 0; i < capacity; i++) {
        Object* key = dict->KeyAt(i);
        if (key->IsNumber()) {
          uint32_t number = static_cast<uint32_t>(key->Number());
          if (new_length <= number && number < old_length) {
            PropertyDetails details = dict->DetailsAt(i);
            if (details.IsDontDelete()) new_length = number + 1;
          }
        }
      }
      if (new_length != length) {
        MaybeObject* maybe_object = heap->NumberFromUint32(new_length);
        if (!maybe_object->To(&length_object)) return maybe_object;
      }
    }

    if (new_length == 0) {
1526 1527 1528 1529 1530 1531 1532
      // If the length of a slow array is reset to zero, we clear
      // the array and flush backing storage. This has the added
      // benefit that the array returns to fast mode.
      Object* obj;
      MaybeObject* maybe_obj = array->ResetElements();
      if (!maybe_obj->ToObject(&obj)) return maybe_obj;
    } else {
1533 1534 1535 1536 1537 1538 1539 1540 1541 1542
      // Remove elements that should be deleted.
      int removed_entries = 0;
      Object* the_hole_value = heap->the_hole_value();
      for (int i = 0; i < capacity; i++) {
        Object* key = dict->KeyAt(i);
        if (key->IsNumber()) {
          uint32_t number = static_cast<uint32_t>(key->Number());
          if (new_length <= number && number < old_length) {
            dict->SetEntry(i, the_hole_value, the_hole_value);
            removed_entries++;
1543 1544 1545
          }
        }
      }
1546 1547 1548

      // Update the number of elements.
      dict->ElementsRemoved(removed_entries);
1549 1550 1551 1552
    }
    return length_object;
  }

1553 1554 1555 1556
  MUST_USE_RESULT static MaybeObject* DeleteCommon(
      JSObject* obj,
      uint32_t key,
      JSReceiver::DeleteMode mode) {
1557 1558 1559 1560
    Isolate* isolate = obj->GetIsolate();
    Heap* heap = isolate->heap();
    FixedArray* backing_store = FixedArray::cast(obj->elements());
    bool is_arguments =
1561
        (obj->GetElementsKind() == NON_STRICT_ARGUMENTS_ELEMENTS);
1562 1563 1564
    if (is_arguments) {
      backing_store = FixedArray::cast(backing_store->get(1));
    }
1565 1566
    SeededNumberDictionary* dictionary =
        SeededNumberDictionary::cast(backing_store);
1567
    int entry = dictionary->FindEntry(key);
1568
    if (entry != SeededNumberDictionary::kNotFound) {
1569
      Object* result = dictionary->DeleteProperty(entry, mode);
1570 1571 1572 1573
      if (result == heap->false_value()) {
        if (mode == JSObject::STRICT_DELETION) {
          // Deleting a non-configurable property in strict mode.
          HandleScope scope(isolate);
1574
          Handle<Object> holder(obj, isolate);
1575 1576 1577 1578 1579 1580
          Handle<Object> name = isolate->factory()->NewNumberFromUint(key);
          Handle<Object> args[2] = { name, holder };
          Handle<Object> error =
              isolate->factory()->NewTypeError("strict_delete_property",
                                               HandleVector(args, 2));
          return isolate->Throw(*error);
1581
        }
1582
        return heap->false_value();
1583
      }
1584 1585 1586 1587 1588 1589 1590 1591 1592
      MaybeObject* maybe_elements = dictionary->Shrink(key);
      FixedArray* new_elements = NULL;
      if (!maybe_elements->To(&new_elements)) {
        return maybe_elements;
      }
      if (is_arguments) {
        FixedArray::cast(obj->elements())->set(1, new_elements);
      } else {
        obj->set_elements(new_elements);
1593 1594 1595 1596 1597
      }
    }
    return heap->true_value();
  }

1598 1599 1600
  MUST_USE_RESULT static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                                       uint32_t from_start,
                                                       FixedArrayBase* to,
1601
                                                       ElementsKind from_kind,
1602
                                                       uint32_t to_start,
1603
                                                       int packed_size,
1604
                                                       int copy_size) {
1605 1606
    UNREACHABLE();
    return NULL;
1607 1608 1609
  }


1610 1611
 protected:
  friend class ElementsAccessorBase<DictionaryElementsAccessor,
1612
                                    ElementsKindTraits<DICTIONARY_ELEMENTS> >;
1613

1614 1615 1616
  MUST_USE_RESULT virtual MaybeObject* Delete(JSObject* obj,
                                              uint32_t key,
                                              JSReceiver::DeleteMode mode) {
1617
    return DeleteCommon(obj, key, mode);
1618 1619
  }

1620 1621 1622 1623
  MUST_USE_RESULT static MaybeObject* GetImpl(
      Object* receiver,
      JSObject* obj,
      uint32_t key,
1624 1625
      FixedArrayBase* store) {
    SeededNumberDictionary* backing_store = SeededNumberDictionary::cast(store);
1626
    int entry = backing_store->FindEntry(key);
1627
    if (entry != SeededNumberDictionary::kNotFound) {
1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639
      Object* element = backing_store->ValueAt(entry);
      PropertyDetails details = backing_store->DetailsAt(entry);
      if (details.type() == CALLBACKS) {
        return obj->GetElementWithCallback(receiver,
                                           element,
                                           key,
                                           obj);
      } else {
        return element;
      }
    }
    return obj->GetHeap()->the_hole_value();
1640
  }
1641

1642 1643 1644 1645
  MUST_USE_RESULT static PropertyAttributes GetAttributesImpl(
      Object* receiver,
      JSObject* obj,
      uint32_t key,
1646 1647 1648 1649
      FixedArrayBase* backing_store) {
    SeededNumberDictionary* dictionary =
        SeededNumberDictionary::cast(backing_store);
    int entry = dictionary->FindEntry(key);
1650
    if (entry != SeededNumberDictionary::kNotFound) {
1651
      return dictionary->DetailsAt(entry).attributes();
1652 1653 1654 1655
    }
    return ABSENT;
  }

1656 1657 1658 1659
  MUST_USE_RESULT static PropertyType GetTypeImpl(
      Object* receiver,
      JSObject* obj,
      uint32_t key,
1660 1661
      FixedArrayBase* store) {
    SeededNumberDictionary* backing_store = SeededNumberDictionary::cast(store);
1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672
    int entry = backing_store->FindEntry(key);
    if (entry != SeededNumberDictionary::kNotFound) {
      return backing_store->DetailsAt(entry).type();
    }
    return NONEXISTENT;
  }

  MUST_USE_RESULT static AccessorPair* GetAccessorPairImpl(
      Object* receiver,
      JSObject* obj,
      uint32_t key,
1673 1674
      FixedArrayBase* store) {
    SeededNumberDictionary* backing_store = SeededNumberDictionary::cast(store);
1675 1676 1677 1678 1679 1680 1681 1682 1683
    int entry = backing_store->FindEntry(key);
    if (entry != SeededNumberDictionary::kNotFound &&
        backing_store->DetailsAt(entry).type() == CALLBACKS &&
        backing_store->ValueAt(entry)->IsAccessorPair()) {
      return AccessorPair::cast(backing_store->ValueAt(entry));
    }
    return NULL;
  }

1684
  static bool HasElementImpl(Object* receiver,
1685
                             JSObject* holder,
1686
                             uint32_t key,
1687 1688
                             FixedArrayBase* backing_store) {
    return SeededNumberDictionary::cast(backing_store)->FindEntry(key) !=
1689 1690 1691
        SeededNumberDictionary::kNotFound;
  }

1692
  static uint32_t GetKeyForIndexImpl(FixedArrayBase* store,
1693
                                     uint32_t index) {
1694
    SeededNumberDictionary* dict = SeededNumberDictionary::cast(store);
1695 1696
    Object* key = dict->KeyAt(index);
    return Smi::cast(key)->value();
1697
  }
1698 1699 1700
};


1701 1702 1703
class NonStrictArgumentsElementsAccessor : public ElementsAccessorBase<
    NonStrictArgumentsElementsAccessor,
    ElementsKindTraits<NON_STRICT_ARGUMENTS_ELEMENTS> > {
1704 1705
 public:
  explicit NonStrictArgumentsElementsAccessor(const char* name)
1706 1707 1708
      : ElementsAccessorBase<
          NonStrictArgumentsElementsAccessor,
          ElementsKindTraits<NON_STRICT_ARGUMENTS_ELEMENTS> >(name) {}
1709
 protected:
1710 1711 1712
  friend class ElementsAccessorBase<
      NonStrictArgumentsElementsAccessor,
      ElementsKindTraits<NON_STRICT_ARGUMENTS_ELEMENTS> >;
1713

1714 1715 1716
  MUST_USE_RESULT static MaybeObject* GetImpl(Object* receiver,
                                              JSObject* obj,
                                              uint32_t key,
1717 1718
                                              FixedArrayBase* parameters) {
    FixedArray* parameter_map = FixedArray::cast(parameters);
1719
    Object* probe = GetParameterMapArg(obj, parameter_map, key);
1720
    if (!probe->IsTheHole()) {
1721 1722 1723 1724 1725 1726 1727
      Context* context = Context::cast(parameter_map->get(0));
      int context_index = Smi::cast(probe)->value();
      ASSERT(!context->get(context_index)->IsTheHole());
      return context->get(context_index);
    } else {
      // Object is not mapped, defer to the arguments.
      FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
1728
      MaybeObject* maybe_result = ElementsAccessor::ForArray(arguments)->Get(
1729
          receiver, obj, key, arguments);
1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741
      Object* result;
      if (!maybe_result->ToObject(&result)) return maybe_result;
      // Elements of the arguments object in slow mode might be slow aliases.
      if (result->IsAliasedArgumentsEntry()) {
        AliasedArgumentsEntry* entry = AliasedArgumentsEntry::cast(result);
        Context* context = Context::cast(parameter_map->get(0));
        int context_index = entry->aliased_context_slot();
        ASSERT(!context->get(context_index)->IsTheHole());
        return context->get(context_index);
      } else {
        return result;
      }
1742 1743
    }
  }
1744

1745 1746 1747 1748
  MUST_USE_RESULT static PropertyAttributes GetAttributesImpl(
      Object* receiver,
      JSObject* obj,
      uint32_t key,
1749 1750
      FixedArrayBase* backing_store) {
    FixedArray* parameter_map = FixedArray::cast(backing_store);
1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761
    Object* probe = GetParameterMapArg(obj, parameter_map, key);
    if (!probe->IsTheHole()) {
      return NONE;
    } else {
      // If not aliased, check the arguments.
      FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
      return ElementsAccessor::ForArray(arguments)->GetAttributes(
          receiver, obj, key, arguments);
    }
  }

1762 1763 1764 1765
  MUST_USE_RESULT static PropertyType GetTypeImpl(
      Object* receiver,
      JSObject* obj,
      uint32_t key,
1766 1767
      FixedArrayBase* parameters) {
    FixedArray* parameter_map = FixedArray::cast(parameters);
1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782
    Object* probe = GetParameterMapArg(obj, parameter_map, key);
    if (!probe->IsTheHole()) {
      return FIELD;
    } else {
      // If not aliased, check the arguments.
      FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
      return ElementsAccessor::ForArray(arguments)->GetType(
          receiver, obj, key, arguments);
    }
  }

  MUST_USE_RESULT static AccessorPair* GetAccessorPairImpl(
      Object* receiver,
      JSObject* obj,
      uint32_t key,
1783 1784
      FixedArrayBase* parameters) {
    FixedArray* parameter_map = FixedArray::cast(parameters);
1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795
    Object* probe = GetParameterMapArg(obj, parameter_map, key);
    if (!probe->IsTheHole()) {
      return NULL;
    } else {
      // If not aliased, check the arguments.
      FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
      return ElementsAccessor::ForArray(arguments)->GetAccessorPair(
          receiver, obj, key, arguments);
    }
  }

1796 1797 1798
  MUST_USE_RESULT static MaybeObject* SetLengthImpl(
      JSObject* obj,
      Object* length,
1799
      FixedArrayBase* parameter_map) {
1800 1801 1802 1803 1804 1805
    // TODO(mstarzinger): This was never implemented but will be used once we
    // correctly implement [[DefineOwnProperty]] on arrays.
    UNIMPLEMENTED();
    return obj;
  }

1806 1807 1808
  MUST_USE_RESULT virtual MaybeObject* Delete(JSObject* obj,
                                              uint32_t key,
                                              JSReceiver::DeleteMode mode) {
1809
    FixedArray* parameter_map = FixedArray::cast(obj->elements());
1810
    Object* probe = GetParameterMapArg(obj, parameter_map, key);
1811
    if (!probe->IsTheHole()) {
1812 1813 1814
      // TODO(kmillikin): We could check if this was the last aliased
      // parameter, and revert to normal elements in that case.  That
      // would enable GC of the context.
1815
      parameter_map->set_the_hole(key + 2);
1816 1817 1818
    } else {
      FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
      if (arguments->IsDictionary()) {
1819
        return DictionaryElementsAccessor::DeleteCommon(obj, key, mode);
1820
      } else {
1821 1822 1823 1824
        // It's difficult to access the version of DeleteCommon that is declared
        // in the templatized super class, call the concrete implementation in
        // the class for the most generalized ElementsKind subclass.
        return FastHoleyObjectElementsAccessor::DeleteCommon(obj, key, mode);
1825 1826 1827 1828
      }
    }
    return obj->GetHeap()->true_value();
  }
1829

1830 1831 1832
  MUST_USE_RESULT static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                                       uint32_t from_start,
                                                       FixedArrayBase* to,
1833
                                                       ElementsKind from_kind,
1834
                                                       uint32_t to_start,
1835
                                                       int packed_size,
1836
                                                       int copy_size) {
1837 1838
    UNREACHABLE();
    return NULL;
1839 1840
  }

1841 1842
  static uint32_t GetCapacityImpl(FixedArrayBase* backing_store) {
    FixedArray* parameter_map = FixedArray::cast(backing_store);
1843 1844 1845
    FixedArrayBase* arguments = FixedArrayBase::cast(parameter_map->get(1));
    return Max(static_cast<uint32_t>(parameter_map->length() - 2),
               ForArray(arguments)->GetCapacity(arguments));
1846 1847
  }

1848
  static uint32_t GetKeyForIndexImpl(FixedArrayBase* dict,
1849
                                     uint32_t index) {
1850 1851 1852
    return index;
  }

1853
  static bool HasElementImpl(Object* receiver,
1854
                             JSObject* holder,
1855
                             uint32_t key,
1856 1857
                             FixedArrayBase* parameters) {
    FixedArray* parameter_map = FixedArray::cast(parameters);
1858
    Object* probe = GetParameterMapArg(holder, parameter_map, key);
1859 1860 1861
    if (!probe->IsTheHole()) {
      return true;
    } else {
1862 1863
      FixedArrayBase* arguments =
          FixedArrayBase::cast(FixedArray::cast(parameter_map)->get(1));
1864
      ElementsAccessor* accessor = ElementsAccessor::ForArray(arguments);
1865
      return !accessor->Get(receiver, holder, key, arguments)->IsTheHole();
1866 1867 1868 1869
    }
  }

 private:
1870 1871
  static Object* GetParameterMapArg(JSObject* holder,
                                    FixedArray* parameter_map,
1872
                                    uint32_t key) {
1873 1874 1875
    uint32_t length = holder->IsJSArray()
        ? Smi::cast(JSArray::cast(holder)->length())->value()
        : parameter_map->length();
1876
    return key < (length - 2)
1877 1878
        ? parameter_map->get(key + 2)
        : parameter_map->GetHeap()->the_hole_value();
1879
  }
1880 1881 1882
};


1883
ElementsAccessor* ElementsAccessor::ForArray(FixedArrayBase* array) {
1884
  return elements_accessors_[ElementsKindForArray(array)];
1885 1886 1887
}


1888 1889
void ElementsAccessor::InitializeOncePerProcess() {
  static ElementsAccessor* accessor_array[] = {
1890
#define ACCESSOR_ARRAY(Class, Kind, Store) new Class(#Kind),
1891 1892
    ELEMENTS_LIST(ACCESSOR_ARRAY)
#undef ACCESSOR_ARRAY
1893 1894
  };

1895 1896 1897
  STATIC_ASSERT((sizeof(accessor_array) / sizeof(*accessor_array)) ==
                kElementsKindCount);

1898 1899 1900 1901
  elements_accessors_ = accessor_array;
}


1902 1903 1904 1905 1906 1907 1908 1909
void ElementsAccessor::TearDown() {
#define ACCESSOR_DELETE(Class, Kind, Store) delete elements_accessors_[Kind];
  ELEMENTS_LIST(ACCESSOR_DELETE)
#undef ACCESSOR_DELETE
  elements_accessors_ = NULL;
}


1910
template <typename ElementsAccessorSubclass, typename ElementsKindTraits>
1911 1912
MUST_USE_RESULT MaybeObject* ElementsAccessorBase<ElementsAccessorSubclass,
                                                  ElementsKindTraits>::
1913 1914
    SetLengthImpl(JSObject* obj,
                  Object* length,
1915
                  FixedArrayBase* backing_store) {
1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942
  JSArray* array = JSArray::cast(obj);

  // Fast case: The new length fits into a Smi.
  MaybeObject* maybe_smi_length = length->ToSmi();
  Object* smi_length = Smi::FromInt(0);
  if (maybe_smi_length->ToObject(&smi_length) && smi_length->IsSmi()) {
    const int value = Smi::cast(smi_length)->value();
    if (value >= 0) {
      Object* new_length;
      MaybeObject* result = ElementsAccessorSubclass::
          SetLengthWithoutNormalize(backing_store, array, smi_length, value);
      if (!result->ToObject(&new_length)) return result;
      ASSERT(new_length->IsSmi() || new_length->IsUndefined());
      if (new_length->IsSmi()) {
        array->set_length(Smi::cast(new_length));
        return array;
      }
    } else {
      return ThrowArrayLengthRangeError(array->GetHeap());
    }
  }

  // Slow case: The new length does not fit into a Smi or conversion
  // to slow elements is needed for other reasons.
  if (length->IsNumber()) {
    uint32_t value;
    if (length->ToArrayIndex(&value)) {
1943
      SeededNumberDictionary* dictionary;
1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963
      MaybeObject* maybe_object = array->NormalizeElements();
      if (!maybe_object->To(&dictionary)) return maybe_object;
      Object* new_length;
      MaybeObject* result = DictionaryElementsAccessor::
          SetLengthWithoutNormalize(dictionary, array, length, value);
      if (!result->ToObject(&new_length)) return result;
      ASSERT(new_length->IsNumber());
      array->set_length(new_length);
      return array;
    } else {
      return ThrowArrayLengthRangeError(array->GetHeap());
    }
  }

  // Fall-back case: The new length is not a number so make the array
  // size one and set only element to length.
  FixedArray* new_backing_store;
  MaybeObject* maybe_obj = array->GetHeap()->AllocateFixedArray(1);
  if (!maybe_obj->To(&new_backing_store)) return maybe_obj;
  new_backing_store->set(0, length);
1964 1965 1966
  { MaybeObject* result = array->SetContent(new_backing_store);
    if (result->IsFailure()) return result;
  }
1967 1968 1969 1970
  return array;
}


1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040
MUST_USE_RESULT MaybeObject* ArrayConstructInitializeElements(
    JSArray* array, Arguments* args) {
  Heap* heap = array->GetIsolate()->heap();

  // Optimize the case where there is one argument and the argument is a
  // small smi.
  if (args->length() == 1) {
    Object* obj = (*args)[0];
    if (obj->IsSmi()) {
      int len = Smi::cast(obj)->value();
      if (len > 0 && len < JSObject::kInitialMaxFastElementArray) {
        ElementsKind elements_kind = array->GetElementsKind();
        MaybeObject* maybe_array = array->Initialize(len, len);
        if (maybe_array->IsFailure()) return maybe_array;

        if (!IsFastHoleyElementsKind(elements_kind)) {
          elements_kind = GetHoleyElementsKind(elements_kind);
          maybe_array = array->TransitionElementsKind(elements_kind);
          if (maybe_array->IsFailure()) return maybe_array;
        }

        return array;
      } else if (len == 0) {
        return array->Initialize(JSArray::kPreallocatedArrayElements);
      }
    }

    // Take the argument as the length.
    MaybeObject* maybe_obj = array->Initialize(0);
    if (!maybe_obj->To(&obj)) return maybe_obj;

    return array->SetElementsLength((*args)[0]);
  }

  // Optimize the case where there are no parameters passed.
  if (args->length() == 0) {
    return array->Initialize(JSArray::kPreallocatedArrayElements);
  }

  // Set length and elements on the array.
  int number_of_elements = args->length();
  MaybeObject* maybe_object =
      array->EnsureCanContainElements(args, 0, number_of_elements,
                                      ALLOW_CONVERTED_DOUBLE_ELEMENTS);
  if (maybe_object->IsFailure()) return maybe_object;

  // Allocate an appropriately typed elements array.
  MaybeObject* maybe_elms;
  ElementsKind elements_kind = array->GetElementsKind();
  if (IsFastDoubleElementsKind(elements_kind)) {
    maybe_elms = heap->AllocateUninitializedFixedDoubleArray(
        number_of_elements);
  } else {
    maybe_elms = heap->AllocateFixedArrayWithHoles(number_of_elements);
  }
  FixedArrayBase* elms;
  if (!maybe_elms->To(&elms)) return maybe_elms;

  // Fill in the content
  switch (array->GetElementsKind()) {
    case FAST_HOLEY_SMI_ELEMENTS:
    case FAST_SMI_ELEMENTS: {
      FixedArray* smi_elms = FixedArray::cast(elms);
      for (int index = 0; index < number_of_elements; index++) {
        smi_elms->set(index, (*args)[index], SKIP_WRITE_BARRIER);
      }
      break;
    }
    case FAST_HOLEY_ELEMENTS:
    case FAST_ELEMENTS: {
2041
      DisallowHeapAllocation no_gc;
2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066
      WriteBarrierMode mode = elms->GetWriteBarrierMode(no_gc);
      FixedArray* object_elms = FixedArray::cast(elms);
      for (int index = 0; index < number_of_elements; index++) {
        object_elms->set(index, (*args)[index], mode);
      }
      break;
    }
    case FAST_HOLEY_DOUBLE_ELEMENTS:
    case FAST_DOUBLE_ELEMENTS: {
      FixedDoubleArray* double_elms = FixedDoubleArray::cast(elms);
      for (int index = 0; index < number_of_elements; index++) {
        double_elms->set(index, (*args)[index]->Number());
      }
      break;
    }
    default:
      UNREACHABLE();
      break;
  }

  array->set_elements(elms);
  array->set_length(Smi::FromInt(number_of_elements));
  return array;
}

2067
} }  // namespace v8::internal