elements.cc 184 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/elements.h"
6

7 8
#include "src/arguments.h"
#include "src/conversions.h"
9
#include "src/frames.h"
10
#include "src/heap/factory.h"
11
#include "src/heap/heap-inl.h"  // For MaxNumberToStringCacheSize.
12
#include "src/heap/heap-write-barrier-inl.h"
13
#include "src/isolate-inl.h"
14
#include "src/keys.h"
15
#include "src/message-template.h"
16
#include "src/objects-inl.h"
17
#include "src/objects/arguments-inl.h"
18
#include "src/objects/hash-table-inl.h"
19
#include "src/objects/js-array-buffer-inl.h"
20
#include "src/objects/js-array-inl.h"
21
#include "src/objects/slots-atomic-inl.h"
22
#include "src/objects/slots.h"
23
#include "src/utils.h"
24 25 26 27 28 29 30 31

// 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)
32 33 34 35 36
//     - FastSmiOrObjectElementsAccessor
//       - FastPackedSmiElementsAccessor
//       - FastHoleySmiElementsAccessor
//       - FastPackedObjectElementsAccessor
//       - FastHoleyObjectElementsAccessor
37
//     - FastDoubleElementsAccessor
38 39
//       - FastPackedDoubleElementsAccessor
//       - FastHoleyDoubleElementsAccessor
40 41 42 43 44 45 46 47 48 49
//   - TypedElementsAccessor: template, with instantiations:
//     - FixedUint8ElementsAccessor
//     - FixedInt8ElementsAccessor
//     - FixedUint16ElementsAccessor
//     - FixedInt16ElementsAccessor
//     - FixedUint32ElementsAccessor
//     - FixedInt32ElementsAccessor
//     - FixedFloat32ElementsAccessor
//     - FixedFloat64ElementsAccessor
//     - FixedUint8ClampedElementsAccessor
50 51
//     - FixedBigUint64ElementsAccessor
//     - FixedBigInt64ElementsAccessor
52
//   - DictionaryElementsAccessor
53
//   - SloppyArgumentsElementsAccessor
54 55
//     - FastSloppyArgumentsElementsAccessor
//     - SlowSloppyArgumentsElementsAccessor
56 57 58
//   - StringWrapperElementsAccessor
//     - FastStringWrapperElementsAccessor
//     - SlowStringWrapperElementsAccessor
59

60 61 62 63
namespace v8 {
namespace internal {


64 65 66
namespace {


67 68
static const int kPackedSizeNotKnown = -1;

cbruni's avatar
cbruni committed
69 70
enum Where { AT_START, AT_END };

71

72 73 74 75 76
// 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.
77
#define ELEMENTS_LIST(V)                                                      \
78 79 80 81 82
  V(FastPackedSmiElementsAccessor, PACKED_SMI_ELEMENTS, FixedArray)           \
  V(FastHoleySmiElementsAccessor, HOLEY_SMI_ELEMENTS, FixedArray)             \
  V(FastPackedObjectElementsAccessor, PACKED_ELEMENTS, FixedArray)            \
  V(FastHoleyObjectElementsAccessor, HOLEY_ELEMENTS, FixedArray)              \
  V(FastPackedDoubleElementsAccessor, PACKED_DOUBLE_ELEMENTS,                 \
83
    FixedDoubleArray)                                                         \
84
  V(FastHoleyDoubleElementsAccessor, HOLEY_DOUBLE_ELEMENTS, FixedDoubleArray) \
85
  V(DictionaryElementsAccessor, DICTIONARY_ELEMENTS, NumberDictionary)        \
86 87 88 89
  V(FastSloppyArgumentsElementsAccessor, FAST_SLOPPY_ARGUMENTS_ELEMENTS,      \
    FixedArray)                                                               \
  V(SlowSloppyArgumentsElementsAccessor, SLOW_SLOPPY_ARGUMENTS_ELEMENTS,      \
    FixedArray)                                                               \
90 91 92 93
  V(FastStringWrapperElementsAccessor, FAST_STRING_WRAPPER_ELEMENTS,          \
    FixedArray)                                                               \
  V(SlowStringWrapperElementsAccessor, SLOW_STRING_WRAPPER_ELEMENTS,          \
    FixedArray)                                                               \
94 95 96 97 98 99 100 101 102
  V(FixedUint8ElementsAccessor, UINT8_ELEMENTS, FixedUint8Array)              \
  V(FixedInt8ElementsAccessor, INT8_ELEMENTS, FixedInt8Array)                 \
  V(FixedUint16ElementsAccessor, UINT16_ELEMENTS, FixedUint16Array)           \
  V(FixedInt16ElementsAccessor, INT16_ELEMENTS, FixedInt16Array)              \
  V(FixedUint32ElementsAccessor, UINT32_ELEMENTS, FixedUint32Array)           \
  V(FixedInt32ElementsAccessor, INT32_ELEMENTS, FixedInt32Array)              \
  V(FixedFloat32ElementsAccessor, FLOAT32_ELEMENTS, FixedFloat32Array)        \
  V(FixedFloat64ElementsAccessor, FLOAT64_ELEMENTS, FixedFloat64Array)        \
  V(FixedUint8ClampedElementsAccessor, UINT8_CLAMPED_ELEMENTS,                \
103 104 105
    FixedUint8ClampedArray)                                                   \
  V(FixedBigUint64ElementsAccessor, BIGUINT64_ELEMENTS, FixedBigUint64Array)  \
  V(FixedBigInt64ElementsAccessor, BIGINT64_ELEMENTS, FixedBigInt64Array)
106 107 108 109 110 111

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

112 113 114 115 116 117 118 119
#define ELEMENTS_TRAITS(Class, KindParam, Store)    \
  template <>                                       \
  class ElementsKindTraits<KindParam> {             \
   public: /* NOLINT */                             \
    static constexpr ElementsKind Kind = KindParam; \
    typedef Store BackingStore;                     \
  };                                                \
  constexpr ElementsKind ElementsKindTraits<KindParam>::Kind;
120 121 122
ELEMENTS_LIST(ELEMENTS_TRAITS)
#undef ELEMENTS_TRAITS

123
V8_WARN_UNUSED_RESULT
124
MaybeHandle<Object> ThrowArrayLengthRangeError(Isolate* isolate) {
125
  THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kInvalidArrayLength),
126
                  Object);
127 128
}

129 130 131 132 133
WriteBarrierMode GetWriteBarrierMode(ElementsKind kind) {
  if (IsSmiElementsKind(kind)) return SKIP_WRITE_BARRIER;
  if (IsDoubleElementsKind(kind)) return SKIP_WRITE_BARRIER;
  return UPDATE_WRITE_BARRIER;
}
134

135
void CopyObjectToObjectElements(Isolate* isolate, FixedArrayBase from_base,
136
                                ElementsKind from_kind, uint32_t from_start,
137
                                FixedArrayBase to_base, ElementsKind to_kind,
138
                                uint32_t to_start, int raw_copy_size) {
139 140
  ReadOnlyRoots roots(isolate);
  DCHECK(to_base->map() != roots.fixed_cow_array_map());
141
  DisallowHeapAllocation no_allocation;
142 143
  int copy_size = raw_copy_size;
  if (raw_copy_size < 0) {
144
    DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
145
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
146 147
    copy_size = Min(from_base->length() - from_start,
                    to_base->length() - to_start);
148
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
149
      int start = to_start + copy_size;
150
      int length = to_base->length() - start;
151
      if (length > 0) {
152 153
        MemsetTagged(FixedArray::cast(to_base)->RawFieldOfElementAt(start),
                     roots.the_hole_value(), length);
154 155
      }
    }
156
  }
157
  DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
158
         (copy_size + static_cast<int>(from_start)) <= from_base->length());
159
  if (copy_size == 0) return;
160 161
  FixedArray from = FixedArray::cast(from_base);
  FixedArray to = FixedArray::cast(to_base);
162 163
  DCHECK(IsSmiOrObjectElementsKind(from_kind));
  DCHECK(IsSmiOrObjectElementsKind(to_kind));
164 165

  WriteBarrierMode write_barrier_mode =
166
      (IsObjectElementsKind(from_kind) && IsObjectElementsKind(to_kind))
167 168 169
          ? UPDATE_WRITE_BARRIER
          : SKIP_WRITE_BARRIER;
  for (int i = 0; i < copy_size; i++) {
170
    Object value = from->get(from_start + i);
171
    to->set(to_start + i, value, write_barrier_mode);
172 173 174
  }
}

175
static void CopyDictionaryToObjectElements(
176 177
    Isolate* isolate, FixedArrayBase from_base, uint32_t from_start,
    FixedArrayBase to_base, ElementsKind to_kind, uint32_t to_start,
178
    int raw_copy_size) {
179
  DisallowHeapAllocation no_allocation;
180
  NumberDictionary from = NumberDictionary::cast(from_base);
181 182
  int copy_size = raw_copy_size;
  if (raw_copy_size < 0) {
183
    DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
184 185 186
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
    copy_size = from->max_number_key() + 1 - from_start;
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
187
      int start = to_start + copy_size;
188
      int length = to_base->length() - start;
189
      if (length > 0) {
190 191
        MemsetTagged(FixedArray::cast(to_base)->RawFieldOfElementAt(start),
                     ReadOnlyRoots(isolate).the_hole_value(), length);
192 193 194
      }
    }
  }
195
  DCHECK(to_base != from_base);
196
  DCHECK(IsSmiOrObjectElementsKind(to_kind));
197
  if (copy_size == 0) return;
198
  FixedArray to = FixedArray::cast(to_base);
199 200 201 202
  uint32_t to_length = to->length();
  if (to_start + copy_size > to_length) {
    copy_size = to_length - to_start;
  }
203
  WriteBarrierMode write_barrier_mode = GetWriteBarrierMode(to_kind);
204
  for (int i = 0; i < copy_size; i++) {
205
    int entry = from->FindEntry(isolate, i + from_start);
206
    if (entry != NumberDictionary::kNotFound) {
207
      Object value = from->ValueAt(entry);
208
      DCHECK(!value->IsTheHole(isolate));
209
      to->set(i + to_start, value, write_barrier_mode);
210
    } else {
211
      to->set_the_hole(isolate, i + to_start);
212 213
    }
  }
214 215
}

216 217 218
// NOTE: this method violates the handlified function signature convention:
// raw pointer parameters in the function that allocates.
// See ElementsAccessorBase::CopyElements() for details.
219
static void CopyDoubleToObjectElements(Isolate* isolate,
220
                                       FixedArrayBase from_base,
221
                                       uint32_t from_start,
222
                                       FixedArrayBase to_base,
223
                                       uint32_t to_start, int raw_copy_size) {
224 225
  int copy_size = raw_copy_size;
  if (raw_copy_size < 0) {
226
    DisallowHeapAllocation no_allocation;
227
    DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
228
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
229 230
    copy_size = Min(from_base->length() - from_start,
                    to_base->length() - to_start);
231
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
232 233 234 235
      // 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;
236
      int length = to_base->length() - start;
237
      if (length > 0) {
238 239
        MemsetTagged(FixedArray::cast(to_base)->RawFieldOfElementAt(start),
                     ReadOnlyRoots(isolate).the_hole_value(), length);
240 241
      }
    }
242
  }
243

244
  DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
245
         (copy_size + static_cast<int>(from_start)) <= from_base->length());
246
  if (copy_size == 0) return;
247 248 249 250 251

  // From here on, the code below could actually allocate. Therefore the raw
  // values are wrapped into handles.
  Handle<FixedDoubleArray> from(FixedDoubleArray::cast(from_base), isolate);
  Handle<FixedArray> to(FixedArray::cast(to_base), isolate);
252

253 254 255
  // Use an outer loop to not waste too much time on creating HandleScopes.
  // On the other hand we might overflow a single handle scope depending on
  // the copy_size.
256 257
  int offset = 0;
  while (offset < copy_size) {
258
    HandleScope scope(isolate);
259 260
    offset += 100;
    for (int i = offset - 100; i < offset && i < copy_size; ++i) {
261 262
      Handle<Object> value =
          FixedDoubleArray::get(*from, i + from_start, isolate);
263
      to->set(i + to_start, *value, UPDATE_WRITE_BARRIER);
264 265 266 267
    }
  }
}

268
static void CopyDoubleToDoubleElements(FixedArrayBase from_base,
269
                                       uint32_t from_start,
270
                                       FixedArrayBase to_base,
271
                                       uint32_t to_start, int raw_copy_size) {
272
  DisallowHeapAllocation no_allocation;
273 274
  int copy_size = raw_copy_size;
  if (raw_copy_size < 0) {
275
    DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
276
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
277 278
    copy_size = Min(from_base->length() - from_start,
                    to_base->length() - to_start);
279
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
280
      for (int i = to_start + copy_size; i < to_base->length(); ++i) {
281
        FixedDoubleArray::cast(to_base)->set_the_hole(i);
282 283
      }
    }
284
  }
285
  DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
286
         (copy_size + static_cast<int>(from_start)) <= from_base->length());
287
  if (copy_size == 0) return;
288 289
  FixedDoubleArray from = FixedDoubleArray::cast(from_base);
  FixedDoubleArray to = FixedDoubleArray::cast(to_base);
290 291 292 293
  Address to_address = to->address() + FixedDoubleArray::kHeaderSize;
  Address from_address = from->address() + FixedDoubleArray::kHeaderSize;
  to_address += kDoubleSize * to_start;
  from_address += kDoubleSize * from_start;
294
  int words_per_double = (kDoubleSize / kSystemPointerSize);
295
  CopyWords(to_address, from_address,
296
            static_cast<size_t>(words_per_double * copy_size));
297 298
}

299 300 301
static void CopySmiToDoubleElements(FixedArrayBase from_base,
                                    uint32_t from_start, FixedArrayBase to_base,
                                    uint32_t to_start, int raw_copy_size) {
302
  DisallowHeapAllocation no_allocation;
303 304
  int copy_size = raw_copy_size;
  if (raw_copy_size < 0) {
305
    DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
306
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
307
    copy_size = from_base->length() - from_start;
308
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
309
      for (int i = to_start + copy_size; i < to_base->length(); ++i) {
310
        FixedDoubleArray::cast(to_base)->set_the_hole(i);
311 312 313
      }
    }
  }
314
  DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
315
         (copy_size + static_cast<int>(from_start)) <= from_base->length());
316
  if (copy_size == 0) return;
317
  FixedArray from = FixedArray::cast(from_base);
318
  FixedDoubleArray to = FixedDoubleArray::cast(to_base);
319
  Object the_hole = from->GetReadOnlyRoots().the_hole_value();
320 321
  for (uint32_t from_end = from_start + static_cast<uint32_t>(copy_size);
       from_start < from_end; from_start++, to_start++) {
322
    Object hole_or_smi = from->get(from_start);
323
    if (hole_or_smi == the_hole) {
324 325
      to->set_the_hole(to_start);
    } else {
jgruber's avatar
jgruber committed
326
      to->set(to_start, Smi::ToInt(hole_or_smi));
327 328 329 330
    }
  }
}

331
static void CopyPackedSmiToDoubleElements(FixedArrayBase from_base,
332
                                          uint32_t from_start,
333
                                          FixedArrayBase to_base,
334
                                          uint32_t to_start, int packed_size,
335
                                          int raw_copy_size) {
336
  DisallowHeapAllocation no_allocation;
337 338 339
  int copy_size = raw_copy_size;
  uint32_t to_end;
  if (raw_copy_size < 0) {
340
    DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
341
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
342
    copy_size = packed_size - from_start;
343
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
344
      to_end = to_base->length();
345
      for (uint32_t i = to_start + copy_size; i < to_end; ++i) {
346
        FixedDoubleArray::cast(to_base)->set_the_hole(i);
347
      }
348 349 350 351 352 353
    } else {
      to_end = to_start + static_cast<uint32_t>(copy_size);
    }
  } else {
    to_end = to_start + static_cast<uint32_t>(copy_size);
  }
354 355 356
  DCHECK(static_cast<int>(to_end) <= to_base->length());
  DCHECK(packed_size >= 0 && packed_size <= copy_size);
  DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
357
         (copy_size + static_cast<int>(from_start)) <= from_base->length());
358
  if (copy_size == 0) return;
359
  FixedArray from = FixedArray::cast(from_base);
360
  FixedDoubleArray to = FixedDoubleArray::cast(to_base);
361 362
  for (uint32_t from_end = from_start + static_cast<uint32_t>(packed_size);
       from_start < from_end; from_start++, to_start++) {
363
    Object smi = from->get(from_start);
364
    DCHECK(!smi->IsTheHole());
jgruber's avatar
jgruber committed
365
    to->set(to_start, Smi::ToInt(smi));
366 367 368
  }
}

369
static void CopyObjectToDoubleElements(FixedArrayBase from_base,
370
                                       uint32_t from_start,
371
                                       FixedArrayBase to_base,
372
                                       uint32_t to_start, int raw_copy_size) {
373
  DisallowHeapAllocation no_allocation;
374 375
  int copy_size = raw_copy_size;
  if (raw_copy_size < 0) {
376
    DCHECK(raw_copy_size == ElementsAccessor::kCopyToEnd ||
377
           raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
378
    copy_size = from_base->length() - from_start;
379
    if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
380
      for (int i = to_start + copy_size; i < to_base->length(); ++i) {
381
        FixedDoubleArray::cast(to_base)->set_the_hole(i);
382 383 384
      }
    }
  }
385
  DCHECK((copy_size + static_cast<int>(to_start)) <= to_base->length() &&
386
         (copy_size + static_cast<int>(from_start)) <= from_base->length());
387
  if (copy_size == 0) return;
388
  FixedArray from = FixedArray::cast(from_base);
389
  FixedDoubleArray to = FixedDoubleArray::cast(to_base);
390
  Object the_hole = from->GetReadOnlyRoots().the_hole_value();
391 392
  for (uint32_t from_end = from_start + copy_size;
       from_start < from_end; from_start++, to_start++) {
393
    Object hole_or_object = from->get(from_start);
394
    if (hole_or_object == the_hole) {
395
      to->set_the_hole(to_start);
396
    } else {
397
      to->set(to_start, hole_or_object->Number());
398 399 400 401
    }
  }
}

402
static void CopyDictionaryToDoubleElements(
403 404
    Isolate* isolate, FixedArrayBase from_base, uint32_t from_start,
    FixedArrayBase to_base, uint32_t to_start, int raw_copy_size) {
405
  DisallowHeapAllocation no_allocation;
406
  NumberDictionary from = NumberDictionary::cast(from_base);
407 408
  int copy_size = raw_copy_size;
  if (copy_size < 0) {
409
    DCHECK(copy_size == ElementsAccessor::kCopyToEnd ||
410 411 412
           copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
    copy_size = from->max_number_key() + 1 - from_start;
    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
      }
    }
  }
  if (copy_size == 0) return;
419
  FixedDoubleArray to = FixedDoubleArray::cast(to_base);
420 421 422 423
  uint32_t to_length = to->length();
  if (to_start + copy_size > to_length) {
    copy_size = to_length - to_start;
  }
424
  for (int i = 0; i < copy_size; i++) {
425
    int entry = from->FindEntry(isolate, i + from_start);
426
    if (entry != NumberDictionary::kNotFound) {
427 428 429 430 431 432 433
      to->set(i + to_start, from->ValueAt(entry)->Number());
    } else {
      to->set_the_hole(i + to_start);
    }
  }
}

434 435
static void TraceTopFrame(Isolate* isolate) {
  StackFrameIterator it(isolate);
436 437 438 439 440 441
  if (it.done()) {
    PrintF("unknown location (no JavaScript frames present)");
    return;
  }
  StackFrame* raw_frame = it.frame();
  if (raw_frame->is_internal()) {
442
    Code current_code_object =
443 444 445
        isolate->heap()->GcSafeFindCodeForInnerPointer(raw_frame->pc());
    if (current_code_object->builtin_index() ==
        Builtins::kFunctionPrototypeApply) {
446 447 448 449 450
      PrintF("apply from ");
      it.Advance();
      raw_frame = it.frame();
    }
  }
451
  JavaScriptFrame::PrintTop(isolate, stdout, false, true);
452 453
}

454
static void SortIndices(
455
    Isolate* isolate, Handle<FixedArray> indices, uint32_t sort_size,
456
    WriteBarrierMode write_barrier_mode = UPDATE_WRITE_BARRIER) {
457
  // Use AtomicSlot wrapper to ensure that std::sort uses atomic load and
458
  // store operations that are safe for concurrent marking.
459
  AtomicSlot start(indices->GetFirstElementAddress());
460
  std::sort(start, start + sort_size,
461 462 463
            [isolate](Tagged_t elementA, Tagged_t elementB) {
              // TODO(ishell): revisit the code below
              STATIC_ASSERT(kTaggedSize == kSystemPointerSize);
464 465 466 467
#ifdef V8_COMPRESS_POINTERS
              Object a(DecompressTaggedAny(isolate->isolate_root(), elementA));
              Object b(DecompressTaggedAny(isolate->isolate_root(), elementB));
#else
468 469
              Object a(elementA);
              Object b(elementB);
470
#endif
471 472 473 474 475 476 477 478
              if (a->IsSmi() || !a->IsUndefined(isolate)) {
                if (!b->IsSmi() && b->IsUndefined(isolate)) {
                  return true;
                }
                return a->Number() < b->Number();
              }
              return !b->IsSmi() && b->IsUndefined(isolate);
            });
479
  if (write_barrier_mode != SKIP_WRITE_BARRIER) {
480
    FIXED_ARRAY_ELEMENTS_WRITE_BARRIER(isolate->heap(), *indices, 0, sort_size);
481 482
  }
}
483

484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504
static Maybe<bool> IncludesValueSlowPath(Isolate* isolate,
                                         Handle<JSObject> receiver,
                                         Handle<Object> value,
                                         uint32_t start_from, uint32_t length) {
  bool search_for_hole = value->IsUndefined(isolate);
  for (uint32_t k = start_from; k < length; ++k) {
    LookupIterator it(isolate, receiver, k);
    if (!it.IsFound()) {
      if (search_for_hole) return Just(true);
      continue;
    }
    Handle<Object> element_k;
    ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_k,
                                     Object::GetProperty(&it), Nothing<bool>());

    if (value->SameValueZero(*element_k)) return Just(true);
  }

  return Just(false);
}

505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524
static Maybe<int64_t> IndexOfValueSlowPath(Isolate* isolate,
                                           Handle<JSObject> receiver,
                                           Handle<Object> value,
                                           uint32_t start_from,
                                           uint32_t length) {
  for (uint32_t k = start_from; k < length; ++k) {
    LookupIterator it(isolate, receiver, k);
    if (!it.IsFound()) {
      continue;
    }
    Handle<Object> element_k;
    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
        isolate, element_k, Object::GetProperty(&it), Nothing<int64_t>());

    if (value->StrictEquals(*element_k)) return Just<int64_t>(k);
  }

  return Just<int64_t>(-1);
}

525 526 527 528 529 530 531 532
// The InternalElementsAccessor is a helper class to expose otherwise protected
// methods to its subclasses. Namely, we don't want to publicly expose methods
// that take an entry (instead of an index) as an argument.
class InternalElementsAccessor : public ElementsAccessor {
 public:
  explicit InternalElementsAccessor(const char* name)
      : ElementsAccessor(name) {}

533
  uint32_t GetEntryForIndex(Isolate* isolate, JSObject holder,
534
                            FixedArrayBase backing_store,
535
                            uint32_t index) override = 0;
536

537
  PropertyDetails GetDetails(JSObject holder, uint32_t entry) override = 0;
538 539
};

540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556
// 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).
557
template <typename Subclass, typename ElementsTraitsParam>
558
class ElementsAccessorBase : public InternalElementsAccessor {
559
 public:
560
  explicit ElementsAccessorBase(const char* name)
561
      : InternalElementsAccessor(name) {}
562 563 564 565

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

566
  static ElementsKind kind() { return ElementsTraits::Kind; }
567

568
  static void ValidateContents(JSObject holder, int length) {}
569

570
  static void ValidateImpl(JSObject holder) {
571
    FixedArrayBase fixed_array_base = holder->elements();
572 573
    if (!fixed_array_base->IsHeapObject()) return;
    // Arrays that have been shifted in place can't be verified.
574
    if (fixed_array_base->IsFiller()) return;
575 576
    int length = 0;
    if (holder->IsJSArray()) {
577
      Object length_obj = JSArray::cast(holder)->length();
578
      if (length_obj->IsSmi()) {
jgruber's avatar
jgruber committed
579
        length = Smi::ToInt(length_obj);
580 581 582 583
      }
    } else {
      length = fixed_array_base->length();
    }
584
    Subclass::ValidateContents(holder, length);
585 586
  }

587
  void Validate(JSObject holder) final {
588
    DisallowHeapAllocation no_gc;
589
    Subclass::ValidateImpl(holder);
590 591
  }

592
  static bool IsPackedImpl(JSObject holder, FixedArrayBase backing_store,
593 594
                           uint32_t start, uint32_t end) {
    DisallowHeapAllocation no_gc;
595
    if (IsFastPackedElementsKind(kind())) return true;
596
    Isolate* isolate = holder->GetIsolate();
597
    for (uint32_t i = start; i < end; i++) {
598 599
      if (!Subclass::HasElementImpl(isolate, holder, i, backing_store,
                                    ALL_PROPERTIES)) {
600 601 602 603 604 605
        return false;
      }
    }
    return true;
  }

606
  static void TryTransitionResultArrayToPacked(Handle<JSArray> array) {
607
    if (!IsHoleyElementsKind(kind())) return;
608 609
    Handle<FixedArrayBase> backing_store(array->elements(),
                                         array->GetIsolate());
jgruber's avatar
jgruber committed
610
    int length = Smi::ToInt(array->length());
611 612
    if (!Subclass::IsPackedImpl(*array, *backing_store, 0, length)) return;

613 614 615 616 617 618 619 620 621 622
    ElementsKind packed_kind = GetPackedElementsKind(kind());
    Handle<Map> new_map =
        JSObject::GetElementsTransitionMap(array, packed_kind);
    JSObject::MigrateToMap(array, new_map);
    if (FLAG_trace_elements_transitions) {
      JSObject::PrintElementsTransition(stdout, array, kind(), backing_store,
                                        packed_kind, backing_store);
    }
  }

623 624
  bool HasElement(JSObject holder, uint32_t index, FixedArrayBase backing_store,
                  PropertyFilter filter) final {
625 626
    return Subclass::HasElementImpl(holder->GetIsolate(), holder, index,
                                    backing_store, filter);
627 628
  }

629
  static bool HasElementImpl(Isolate* isolate, JSObject holder, uint32_t index,
630
                             FixedArrayBase backing_store,
631
                             PropertyFilter filter = ALL_PROPERTIES) {
632 633
    return Subclass::GetEntryForIndexImpl(isolate, holder, backing_store, index,
                                          filter) != kMaxUInt32;
634 635
  }

636
  bool HasEntry(JSObject holder, uint32_t entry) final {
637 638 639 640
    return Subclass::HasEntryImpl(holder->GetIsolate(), holder->elements(),
                                  entry);
  }

641
  static bool HasEntryImpl(Isolate* isolate, FixedArrayBase backing_store,
642 643 644 645
                           uint32_t entry) {
    UNIMPLEMENTED();
  }

646
  bool HasAccessors(JSObject holder) final {
647
    return Subclass::HasAccessorsImpl(holder, holder->elements());
648 649
  }

650
  static bool HasAccessorsImpl(JSObject holder, FixedArrayBase backing_store) {
651 652 653
    return false;
  }

654
  Handle<Object> Get(Handle<JSObject> holder, uint32_t entry) final {
655
    return Subclass::GetInternalImpl(holder, entry);
656 657
  }

658 659 660
  static Handle<Object> GetInternalImpl(Handle<JSObject> holder,
                                        uint32_t entry) {
    return Subclass::GetImpl(holder->GetIsolate(), holder->elements(), entry);
661 662
  }

663
  static Handle<Object> GetImpl(Isolate* isolate, FixedArrayBase backing_store,
664
                                uint32_t entry) {
665 666
    uint32_t index = GetIndexForEntryImpl(backing_store, entry);
    return handle(BackingStore::cast(backing_store)->get(index), isolate);
667 668
  }

669
  void Set(Handle<JSObject> holder, uint32_t entry, Object value) final {
670
    Subclass::SetImpl(holder, entry, value);
671 672
  }

673 674 675
  void Reconfigure(Handle<JSObject> object, Handle<FixedArrayBase> store,
                   uint32_t entry, Handle<Object> value,
                   PropertyAttributes attributes) final {
676
    Subclass::ReconfigureImpl(object, store, entry, value, attributes);
677 678 679
  }

  static void ReconfigureImpl(Handle<JSObject> object,
680
                              Handle<FixedArrayBase> store, uint32_t entry,
681 682 683 684 685
                              Handle<Object> value,
                              PropertyAttributes attributes) {
    UNREACHABLE();
  }

686 687
  void Add(Handle<JSObject> object, uint32_t index, Handle<Object> value,
           PropertyAttributes attributes, uint32_t new_capacity) final {
688
    Subclass::AddImpl(object, index, value, attributes, new_capacity);
689 690
  }

691
  static void AddImpl(Handle<JSObject> object, uint32_t index,
692 693 694 695 696
                      Handle<Object> value, PropertyAttributes attributes,
                      uint32_t new_capacity) {
    UNREACHABLE();
  }

697 698
  uint32_t Push(Handle<JSArray> receiver, Arguments* args,
                uint32_t push_size) final {
699
    return Subclass::PushImpl(receiver, args, push_size);
700 701
  }

702
  static uint32_t PushImpl(Handle<JSArray> receiver, Arguments* args,
703
                           uint32_t push_sized) {
704 705 706
    UNREACHABLE();
  }

707
  uint32_t Unshift(Handle<JSArray> receiver, Arguments* args,
708
                   uint32_t unshift_size) final {
709
    return Subclass::UnshiftImpl(receiver, args, unshift_size);
710 711
  }

712
  static uint32_t UnshiftImpl(Handle<JSArray> receiver, Arguments* args,
713 714 715 716
                              uint32_t unshift_size) {
    UNREACHABLE();
  }

717 718
  Handle<JSObject> Slice(Handle<JSObject> receiver, uint32_t start,
                         uint32_t end) final {
719
    return Subclass::SliceImpl(receiver, start, end);
720 721
  }

722 723
  static Handle<JSObject> SliceImpl(Handle<JSObject> receiver, uint32_t start,
                                    uint32_t end) {
724
    UNREACHABLE();
725 726
  }

727
  Handle<Object> Pop(Handle<JSArray> receiver) final {
728
    return Subclass::PopImpl(receiver);
cbruni's avatar
cbruni committed
729 730
  }

731
  static Handle<Object> PopImpl(Handle<JSArray> receiver) {
cbruni's avatar
cbruni committed
732 733
    UNREACHABLE();
  }
734

735
  Handle<Object> Shift(Handle<JSArray> receiver) final {
736
    return Subclass::ShiftImpl(receiver);
737 738
  }

739
  static Handle<Object> ShiftImpl(Handle<JSArray> receiver) {
740 741 742
    UNREACHABLE();
  }

743
  void SetLength(Handle<JSArray> array, uint32_t length) final {
744
    Subclass::SetLengthImpl(array->GetIsolate(), array, length,
745
                            handle(array->elements(), array->GetIsolate()));
746 747
  }

748 749
  static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array,
                            uint32_t length,
750 751 752 753 754 755 756 757
                            Handle<FixedArrayBase> backing_store) {
    DCHECK(!array->SetLengthWouldNormalize(length));
    DCHECK(IsFastElementsKind(array->GetElementsKind()));
    uint32_t old_length = 0;
    CHECK(array->length()->ToArrayIndex(&old_length));

    if (old_length < length) {
      ElementsKind kind = array->GetElementsKind();
758
      if (!IsHoleyElementsKind(kind)) {
759 760 761 762 763 764 765
        kind = GetHoleyElementsKind(kind);
        JSObject::TransitionElementsKind(array, kind);
      }
    }

    // Check whether the backing store should be shrunk.
    uint32_t capacity = backing_store->length();
766
    old_length = Min(old_length, capacity);
767 768 769
    if (length == 0) {
      array->initialize_elements();
    } else if (length <= capacity) {
770
      if (IsSmiOrObjectElementsKind(kind())) {
771 772 773 774
        JSObject::EnsureWritableFastElements(array);
        if (array->elements() != *backing_store) {
          backing_store = handle(array->elements(), isolate);
        }
775
      }
776
      if (2 * length + JSObject::kMinAddedElementsCapacity <= capacity) {
777
        // If more than half the elements won't be used, trim the array.
778 779 780 781 782 783 784
        // Do not trim from short arrays to prevent frequent trimming on
        // repeated pop operations.
        // Leave some space to allow for subsequent push operations.
        int elements_to_trim = length + 1 == old_length
                                   ? (capacity - length) / 2
                                   : capacity - length;
        isolate->heap()->RightTrimFixedArray(*backing_store, elements_to_trim);
785 786 787 788
        // Fill the non-trimmed elements with holes.
        BackingStore::cast(*backing_store)
            ->FillWithHoles(length,
                            std::min(old_length, capacity - elements_to_trim));
789 790
      } else {
        // Otherwise, fill the unused tail with holes.
791
        BackingStore::cast(*backing_store)->FillWithHoles(length, old_length);
792 793 794 795
      }
    } else {
      // Check whether the backing store should be expanded.
      capacity = Max(length, JSObject::NewElementsCapacity(capacity));
796
      Subclass::GrowCapacityAndConvertImpl(array, capacity);
797 798 799
    }

    array->set_length(Smi::FromInt(length));
800
    JSObject::ValidateElements(*array);
801
  }
802

803
  uint32_t NumberOfElements(JSObject receiver) final {
804 805 806
    return Subclass::NumberOfElementsImpl(receiver, receiver->elements());
  }

807
  static uint32_t NumberOfElementsImpl(JSObject receiver,
808
                                       FixedArrayBase backing_store) {
809 810 811
    UNREACHABLE();
  }

812
  static uint32_t GetMaxIndex(JSObject receiver, FixedArrayBase elements) {
813
    if (receiver->IsJSArray()) {
814
      DCHECK(JSArray::cast(receiver)->length()->IsSmi());
815
      return static_cast<uint32_t>(
jgruber's avatar
jgruber committed
816
          Smi::ToInt(JSArray::cast(receiver)->length()));
817
    }
818
    return Subclass::GetCapacityImpl(receiver, elements);
819 820
  }

821
  static uint32_t GetMaxNumberOfEntries(JSObject receiver,
822
                                        FixedArrayBase elements) {
823 824 825
    return Subclass::GetMaxIndex(receiver, elements);
  }

826 827 828
  static Handle<FixedArrayBase> ConvertElementsWithCapacity(
      Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
      ElementsKind from_kind, uint32_t capacity) {
829
    return ConvertElementsWithCapacity(
830
        object, old_elements, from_kind, capacity, 0, 0,
831 832 833 834 835 836
        ElementsAccessor::kCopyToEndAndInitializeToHole);
  }

  static Handle<FixedArrayBase> ConvertElementsWithCapacity(
      Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
      ElementsKind from_kind, uint32_t capacity, int copy_size) {
837 838 839 840 841 842 843 844
    return ConvertElementsWithCapacity(object, old_elements, from_kind,
                                       capacity, 0, 0, copy_size);
  }

  static Handle<FixedArrayBase> ConvertElementsWithCapacity(
      Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
      ElementsKind from_kind, uint32_t capacity, uint32_t src_index,
      uint32_t dst_index, int copy_size) {
845
    Isolate* isolate = object->GetIsolate();
846
    Handle<FixedArrayBase> new_elements;
847
    if (IsDoubleElementsKind(kind())) {
848
      new_elements = isolate->factory()->NewFixedDoubleArray(capacity);
849
    } else {
850
      new_elements = isolate->factory()->NewUninitializedFixedArray(capacity);
851 852
    }

853
    int packed_size = kPackedSizeNotKnown;
854
    if (IsFastPackedElementsKind(from_kind) && object->IsJSArray()) {
jgruber's avatar
jgruber committed
855
      packed_size = Smi::ToInt(JSArray::cast(*object)->length());
856 857
    }

858
    Subclass::CopyElementsImpl(isolate, *old_elements, src_index, *new_elements,
859
                               from_kind, dst_index, packed_size, copy_size);
860 861

    return new_elements;
862 863
  }

864 865
  static void TransitionElementsKindImpl(Handle<JSObject> object,
                                         Handle<Map> to_map) {
866
    Handle<Map> from_map = handle(object->map(), object->GetIsolate());
867 868
    ElementsKind from_kind = from_map->elements_kind();
    ElementsKind to_kind = to_map->elements_kind();
869
    if (IsHoleyElementsKind(from_kind)) {
870 871 872 873 874 875 876 877
      to_kind = GetHoleyElementsKind(to_kind);
    }
    if (from_kind != to_kind) {
      // This method should never be called for any other case.
      DCHECK(IsFastElementsKind(from_kind));
      DCHECK(IsFastElementsKind(to_kind));
      DCHECK_NE(TERMINAL_FAST_ELEMENTS_KIND, from_kind);

878 879
      Handle<FixedArrayBase> from_elements(object->elements(),
                                           object->GetIsolate());
880 881
      if (object->elements() ==
              object->GetReadOnlyRoots().empty_fixed_array() ||
882
          IsDoubleElementsKind(from_kind) == IsDoubleElementsKind(to_kind)) {
883 884 885 886
        // No change is needed to the elements() buffer, the transition
        // only requires a map change.
        JSObject::MigrateToMap(object, to_map);
      } else {
887 888 889
        DCHECK(
            (IsSmiElementsKind(from_kind) && IsDoubleElementsKind(to_kind)) ||
            (IsDoubleElementsKind(from_kind) && IsObjectElementsKind(to_kind)));
890 891 892 893 894 895
        uint32_t capacity = static_cast<uint32_t>(object->elements()->length());
        Handle<FixedArrayBase> elements = ConvertElementsWithCapacity(
            object, from_elements, from_kind, capacity);
        JSObject::SetMapAndElements(object, to_map, elements);
      }
      if (FLAG_trace_elements_transitions) {
896 897 898
        JSObject::PrintElementsTransition(
            stdout, object, from_kind, from_elements, to_kind,
            handle(object->elements(), object->GetIsolate()));
899 900 901 902
      }
    }
  }

903
  static void GrowCapacityAndConvertImpl(Handle<JSObject> object,
904
                                         uint32_t capacity) {
905
    ElementsKind from_kind = object->GetElementsKind();
906
    if (IsSmiOrObjectElementsKind(from_kind)) {
907 908 909
      // Array optimizations rely on the prototype lookups of Array objects
      // always returning undefined. If there is a store to the initial
      // prototype object, make sure all of these optimizations are invalidated.
910
      object->GetIsolate()->UpdateNoElementsProtectorOnSetLength(object);
911
    }
912 913
    Handle<FixedArrayBase> old_elements(object->elements(),
                                        object->GetIsolate());
914 915
    // This method should only be called if there's a reason to update the
    // elements.
916
    DCHECK(IsDoubleElementsKind(from_kind) != IsDoubleElementsKind(kind()) ||
917 918
           IsDictionaryElementsKind(from_kind) ||
           static_cast<uint32_t>(old_elements->length()) < capacity);
919 920 921 922 923 924 925
    Subclass::BasicGrowCapacityAndConvertImpl(object, old_elements, from_kind,
                                              kind(), capacity);
  }

  static void BasicGrowCapacityAndConvertImpl(
      Handle<JSObject> object, Handle<FixedArrayBase> old_elements,
      ElementsKind from_kind, ElementsKind to_kind, uint32_t capacity) {
926 927 928
    Handle<FixedArrayBase> elements =
        ConvertElementsWithCapacity(object, old_elements, from_kind, capacity);

929
    if (IsHoleyElementsKind(from_kind)) {
930
      to_kind = GetHoleyElementsKind(to_kind);
931
    }
932 933 934 935 936 937 938 939 940 941
    Handle<Map> new_map = JSObject::GetElementsTransitionMap(object, to_kind);
    JSObject::SetMapAndElements(object, new_map, elements);

    // Transition through the allocation site as well if present.
    JSObject::UpdateAllocationSite(object, to_kind);

    if (FLAG_trace_elements_transitions) {
      JSObject::PrintElementsTransition(stdout, object, from_kind, old_elements,
                                        to_kind, elements);
    }
942 943
  }

944 945 946 947
  void TransitionElementsKind(Handle<JSObject> object, Handle<Map> map) final {
    Subclass::TransitionElementsKindImpl(object, map);
  }

948 949
  void GrowCapacityAndConvert(Handle<JSObject> object,
                              uint32_t capacity) final {
950
    Subclass::GrowCapacityAndConvertImpl(object, capacity);
951 952
  }

953 954 955 956 957 958 959
  bool GrowCapacity(Handle<JSObject> object, uint32_t index) final {
    // This function is intended to be called from optimized code. We don't
    // want to trigger lazy deopts there, so refuse to handle cases that would.
    if (object->map()->is_prototype_map() ||
        object->WouldConvertToSlowElements(index)) {
      return false;
    }
960 961
    Handle<FixedArrayBase> old_elements(object->elements(),
                                        object->GetIsolate());
962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977
    uint32_t new_capacity = JSObject::NewElementsCapacity(index + 1);
    DCHECK(static_cast<uint32_t>(old_elements->length()) < new_capacity);
    Handle<FixedArrayBase> elements =
        ConvertElementsWithCapacity(object, old_elements, kind(), new_capacity);

    DCHECK_EQ(object->GetElementsKind(), kind());
    // Transition through the allocation site as well if present.
    if (JSObject::UpdateAllocationSite<AllocationSiteUpdateMode::kCheckOnly>(
            object, kind())) {
      return false;
    }

    object->set_elements(*elements);
    return true;
  }

978
  void Delete(Handle<JSObject> obj, uint32_t entry) final {
979
    Subclass::DeleteImpl(obj, entry);
980
  }
981

982 983
  static void CopyElementsImpl(Isolate* isolate, FixedArrayBase from,
                               uint32_t from_start, FixedArrayBase to,
984 985
                               ElementsKind from_kind, uint32_t to_start,
                               int packed_size, int copy_size) {
986
    UNREACHABLE();
987 988
  }

989
  void CopyElements(JSObject from_holder, uint32_t from_start,
990 991
                    ElementsKind from_kind, Handle<FixedArrayBase> to,
                    uint32_t to_start, int copy_size) final {
992 993 994 995
    int packed_size = kPackedSizeNotKnown;
    bool is_packed = IsFastPackedElementsKind(from_kind) &&
        from_holder->IsJSArray();
    if (is_packed) {
jgruber's avatar
jgruber committed
996
      packed_size = Smi::ToInt(JSArray::cast(from_holder)->length());
997 998
      if (copy_size >= 0 && packed_size > copy_size) {
        packed_size = copy_size;
999 1000
      }
    }
1001
    FixedArrayBase from = from_holder->elements();
1002
    // NOTE: the Subclass::CopyElementsImpl() methods
1003 1004 1005 1006 1007 1008 1009 1010
    // violate the handlified function signature convention:
    // raw pointer parameters in the function that allocates. This is done
    // intentionally to avoid ArrayConcat() builtin performance degradation.
    //
    // Details: The idea is that allocations actually happen only in case of
    // copying from object with fast double elements to object with object
    // elements. In all the other cases there are no allocations performed and
    // handle creation causes noticeable performance degradation of the builtin.
1011 1012
    Subclass::CopyElementsImpl(from_holder->GetIsolate(), from, from_start, *to,
                               from_kind, to_start, packed_size, copy_size);
1013 1014
  }

1015 1016
  void CopyElements(Isolate* isolate, Handle<FixedArrayBase> source,
                    ElementsKind source_kind,
1017
                    Handle<FixedArrayBase> destination, int size) override {
1018 1019
    Subclass::CopyElementsImpl(isolate, *source, 0, *destination, source_kind,
                               0, kPackedSizeNotKnown, size);
1020 1021
  }

1022 1023
  void CopyTypedArrayElementsSlice(JSTypedArray source,
                                   JSTypedArray destination, size_t start,
1024
                                   size_t end) override {
1025 1026 1027
    Subclass::CopyTypedArrayElementsSliceImpl(source, destination, start, end);
  }

1028 1029
  static void CopyTypedArrayElementsSliceImpl(JSTypedArray source,
                                              JSTypedArray destination,
1030 1031 1032 1033
                                              size_t start, size_t end) {
    UNREACHABLE();
  }

1034 1035
  Object CopyElements(Handle<Object> source, Handle<JSObject> destination,
                      size_t length, uint32_t offset) final {
1036 1037
    return Subclass::CopyElementsHandleImpl(source, destination, length,
                                            offset);
1038 1039
  }

1040 1041 1042
  static Object CopyElementsHandleImpl(Handle<Object> source,
                                       Handle<JSObject> destination,
                                       size_t length, uint32_t offset) {
1043 1044 1045
    UNREACHABLE();
  }

1046
  Handle<NumberDictionary> Normalize(Handle<JSObject> object) final {
1047 1048
    return Subclass::NormalizeImpl(
        object, handle(object->elements(), object->GetIsolate()));
1049 1050
  }

1051
  static Handle<NumberDictionary> NormalizeImpl(
1052 1053 1054 1055
      Handle<JSObject> object, Handle<FixedArrayBase> elements) {
    UNREACHABLE();
  }

1056 1057 1058
  Maybe<bool> CollectValuesOrEntries(Isolate* isolate, Handle<JSObject> object,
                                     Handle<FixedArray> values_or_entries,
                                     bool get_entries, int* nof_items,
1059
                                     PropertyFilter filter) override {
1060
    return Subclass::CollectValuesOrEntriesImpl(
1061 1062 1063 1064 1065 1066 1067
        isolate, object, values_or_entries, get_entries, nof_items, filter);
  }

  static Maybe<bool> CollectValuesOrEntriesImpl(
      Isolate* isolate, Handle<JSObject> object,
      Handle<FixedArray> values_or_entries, bool get_entries, int* nof_items,
      PropertyFilter filter) {
1068
    DCHECK_EQ(*nof_items, 0);
1069 1070
    KeyAccumulator accumulator(isolate, KeyCollectionMode::kOwnOnly,
                               ALL_PROPERTIES);
1071
    Subclass::CollectElementIndicesImpl(
1072
        object, handle(object->elements(), isolate), &accumulator);
1073 1074
    Handle<FixedArray> keys = accumulator.GetKeys();

1075 1076
    int count = 0;
    int i = 0;
1077
    ElementsKind original_elements_kind = object->GetElementsKind();
1078 1079

    for (; i < keys->length(); ++i) {
1080 1081 1082 1083
      Handle<Object> key(keys->get(i), isolate);
      uint32_t index;
      if (!key->ToUint32(&index)) continue;

1084
      DCHECK_EQ(object->GetElementsKind(), original_elements_kind);
1085
      uint32_t entry = Subclass::GetEntryForIndexImpl(
1086
          isolate, *object, object->elements(), index, filter);
1087
      if (entry == kMaxUInt32) continue;
1088
      PropertyDetails details = Subclass::GetDetailsImpl(*object, entry);
1089

1090
      Handle<Object> value;
1091
      if (details.kind() == kData) {
1092
        value = Subclass::GetImpl(isolate, object->elements(), entry);
1093
      } else {
1094
        // This might modify the elements and/or change the elements kind.
1095 1096 1097 1098
        LookupIterator it(isolate, object, index, LookupIterator::OWN);
        ASSIGN_RETURN_ON_EXCEPTION_VALUE(
            isolate, value, Object::GetProperty(&it), Nothing<bool>());
      }
1099 1100
      if (get_entries) value = MakeEntryPair(isolate, index, value);
      values_or_entries->set(count++, *value);
1101
      if (object->GetElementsKind() != original_elements_kind) break;
1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118
    }

    // Slow path caused by changes in elements kind during iteration.
    for (; i < keys->length(); i++) {
      Handle<Object> key(keys->get(i), isolate);
      uint32_t index;
      if (!key->ToUint32(&index)) continue;

      if (filter & ONLY_ENUMERABLE) {
        InternalElementsAccessor* accessor =
            reinterpret_cast<InternalElementsAccessor*>(
                object->GetElementsAccessor());
        uint32_t entry = accessor->GetEntryForIndex(isolate, *object,
                                                    object->elements(), index);
        if (entry == kMaxUInt32) continue;
        PropertyDetails details = accessor->GetDetails(*object, entry);
        if (!details.IsEnumerable()) continue;
1119
      }
1120 1121 1122 1123 1124 1125 1126

      Handle<Object> value;
      LookupIterator it(isolate, object, index, LookupIterator::OWN);
      ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, value, Object::GetProperty(&it),
                                       Nothing<bool>());

      if (get_entries) value = MakeEntryPair(isolate, index, value);
1127 1128 1129 1130 1131 1132 1133
      values_or_entries->set(count++, *value);
    }

    *nof_items = count;
    return Just(true);
  }

1134 1135
  void CollectElementIndices(Handle<JSObject> object,
                             Handle<FixedArrayBase> backing_store,
1136 1137 1138
                             KeyAccumulator* keys) final {
    if (keys->filter() & ONLY_ALL_CAN_READ) return;
    Subclass::CollectElementIndicesImpl(object, backing_store, keys);
1139 1140
  }

1141 1142
  static void CollectElementIndicesImpl(Handle<JSObject> object,
                                        Handle<FixedArrayBase> backing_store,
1143
                                        KeyAccumulator* keys) {
1144
    DCHECK_NE(DICTIONARY_ELEMENTS, kind());
1145
    // Non-dictionary elements can't have all-can-read accessors.
1146
    uint32_t length = Subclass::GetMaxIndex(*object, *backing_store);
1147
    PropertyFilter filter = keys->filter();
1148 1149
    Isolate* isolate = keys->isolate();
    Factory* factory = isolate->factory();
1150
    for (uint32_t i = 0; i < length; i++) {
1151 1152
      if (Subclass::HasElementImpl(isolate, *object, i, *backing_store,
                                   filter)) {
1153
        keys->AddKey(factory->NewNumberFromUint(i));
1154 1155 1156 1157
      }
    }
  }

1158 1159 1160
  static Handle<FixedArray> DirectCollectElementIndicesImpl(
      Isolate* isolate, Handle<JSObject> object,
      Handle<FixedArrayBase> backing_store, GetKeysConversion convert,
1161 1162
      PropertyFilter filter, Handle<FixedArray> list, uint32_t* nof_indices,
      uint32_t insertion_index = 0) {
1163
    uint32_t length = Subclass::GetMaxIndex(*object, *backing_store);
1164 1165
    uint32_t const kMaxStringTableEntries =
        isolate->heap()->MaxNumberToStringCacheSize();
1166
    for (uint32_t i = 0; i < length; i++) {
1167 1168
      if (Subclass::HasElementImpl(isolate, *object, i, *backing_store,
                                   filter)) {
1169
        if (convert == GetKeysConversion::kConvertToString) {
1170 1171 1172
          bool use_cache = i < kMaxStringTableEntries;
          Handle<String> index_string =
              isolate->factory()->Uint32ToString(i, use_cache);
1173 1174
          list->set(insertion_index, *index_string);
        } else {
1175
          list->set(insertion_index, Smi::FromInt(i));
1176 1177 1178 1179 1180 1181 1182 1183
        }
        insertion_index++;
      }
    }
    *nof_indices = insertion_index;
    return list;
  }

1184 1185 1186 1187
  MaybeHandle<FixedArray> PrependElementIndices(
      Handle<JSObject> object, Handle<FixedArrayBase> backing_store,
      Handle<FixedArray> keys, GetKeysConversion convert,
      PropertyFilter filter) final {
1188 1189
    return Subclass::PrependElementIndicesImpl(object, backing_store, keys,
                                               convert, filter);
1190 1191
  }

1192
  static MaybeHandle<FixedArray> PrependElementIndicesImpl(
1193 1194 1195 1196 1197 1198
      Handle<JSObject> object, Handle<FixedArrayBase> backing_store,
      Handle<FixedArray> keys, GetKeysConversion convert,
      PropertyFilter filter) {
    Isolate* isolate = object->GetIsolate();
    uint32_t nof_property_keys = keys->length();
    uint32_t initial_list_length =
1199
        Subclass::GetMaxNumberOfEntries(*object, *backing_store);
1200

1201
    initial_list_length += nof_property_keys;
1202 1203 1204 1205 1206
    if (initial_list_length > FixedArray::kMaxLength ||
        initial_list_length < nof_property_keys) {
      return isolate->Throw<FixedArray>(isolate->factory()->NewRangeError(
          MessageTemplate::kInvalidArrayLength));
    }
1207 1208

    // Collect the element indices into a new list.
1209 1210 1211 1212 1213 1214 1215 1216
    MaybeHandle<FixedArray> raw_array =
        isolate->factory()->TryNewFixedArray(initial_list_length);
    Handle<FixedArray> combined_keys;

    // If we have a holey backing store try to precisely estimate the backing
    // store size as a last emergency measure if we cannot allocate the big
    // array.
    if (!raw_array.ToHandle(&combined_keys)) {
1217
      if (IsHoleyOrDictionaryElementsKind(kind())) {
1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228
        // If we overestimate the result list size we might end up in the
        // large-object space which doesn't free memory on shrinking the list.
        // Hence we try to estimate the final size for holey backing stores more
        // precisely here.
        initial_list_length =
            Subclass::NumberOfElementsImpl(*object, *backing_store);
        initial_list_length += nof_property_keys;
      }
      combined_keys = isolate->factory()->NewFixedArray(initial_list_length);
    }

1229
    uint32_t nof_indices = 0;
1230 1231
    bool needs_sorting = IsDictionaryElementsKind(kind()) ||
                         IsSloppyArgumentsElementsKind(kind());
1232
    combined_keys = Subclass::DirectCollectElementIndicesImpl(
1233 1234 1235
        isolate, object, backing_store,
        needs_sorting ? GetKeysConversion::kKeepNumbers : convert, filter,
        combined_keys, &nof_indices);
1236

1237
    if (needs_sorting) {
1238
      SortIndices(isolate, combined_keys, nof_indices);
1239 1240
      // Indices from dictionary elements should only be converted after
      // sorting.
1241
      if (convert == GetKeysConversion::kConvertToString) {
1242 1243
        for (uint32_t i = 0; i < nof_indices; i++) {
          Handle<Object> index_string = isolate->factory()->Uint32ToString(
1244
              combined_keys->get(i)->Number());
1245 1246 1247 1248 1249 1250
          combined_keys->set(i, *index_string);
        }
      }
    }

    // Copy over the passed-in property keys.
1251 1252 1253
    CopyObjectToObjectElements(isolate, *keys, PACKED_ELEMENTS, 0,
                               *combined_keys, PACKED_ELEMENTS, nof_indices,
                               nof_property_keys);
1254

1255 1256
    // For holey elements and arguments we might have to shrink the collected
    // keys since the estimates might be off.
1257 1258
    if (IsHoleyOrDictionaryElementsKind(kind()) ||
        IsSloppyArgumentsElementsKind(kind())) {
1259 1260 1261
      // Shrink combined_keys to the final size.
      int final_size = nof_indices + nof_property_keys;
      DCHECK_LE(final_size, combined_keys->length());
1262
      return FixedArray::ShrinkOrEmpty(isolate, combined_keys, final_size);
1263 1264 1265 1266
    }

    return combined_keys;
  }
1267

1268 1269 1270
  void AddElementsToKeyAccumulator(Handle<JSObject> receiver,
                                   KeyAccumulator* accumulator,
                                   AddKeyConversion convert) final {
1271
    Subclass::AddElementsToKeyAccumulatorImpl(receiver, accumulator, convert);
1272 1273
  }

1274
  static uint32_t GetCapacityImpl(JSObject holder,
1275
                                  FixedArrayBase backing_store) {
1276
    return backing_store->length();
1277 1278
  }

1279
  uint32_t GetCapacity(JSObject holder, FixedArrayBase backing_store) final {
1280
    return Subclass::GetCapacityImpl(holder, backing_store);
1281 1282
  }

1283 1284
  static Object FillImpl(Handle<JSObject> receiver, Handle<Object> obj_value,
                         uint32_t start, uint32_t end) {
1285 1286 1287
    UNREACHABLE();
  }

1288 1289
  Object Fill(Handle<JSObject> receiver, Handle<Object> obj_value,
              uint32_t start, uint32_t end) override {
1290
    return Subclass::FillImpl(receiver, obj_value, start, end);
1291 1292
  }

1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306
  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
                                       Handle<JSObject> receiver,
                                       Handle<Object> value,
                                       uint32_t start_from, uint32_t length) {
    return IncludesValueSlowPath(isolate, receiver, value, start_from, length);
  }

  Maybe<bool> IncludesValue(Isolate* isolate, Handle<JSObject> receiver,
                            Handle<Object> value, uint32_t start_from,
                            uint32_t length) final {
    return Subclass::IncludesValueImpl(isolate, receiver, value, start_from,
                                       length);
  }

1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320
  static Maybe<int64_t> IndexOfValueImpl(Isolate* isolate,
                                         Handle<JSObject> receiver,
                                         Handle<Object> value,
                                         uint32_t start_from, uint32_t length) {
    return IndexOfValueSlowPath(isolate, receiver, value, start_from, length);
  }

  Maybe<int64_t> IndexOfValue(Isolate* isolate, Handle<JSObject> receiver,
                              Handle<Object> value, uint32_t start_from,
                              uint32_t length) final {
    return Subclass::IndexOfValueImpl(isolate, receiver, value, start_from,
                                      length);
  }

1321
  static Maybe<int64_t> LastIndexOfValueImpl(Handle<JSObject> receiver,
1322 1323 1324 1325 1326
                                             Handle<Object> value,
                                             uint32_t start_from) {
    UNREACHABLE();
  }

1327
  Maybe<int64_t> LastIndexOfValue(Handle<JSObject> receiver,
1328 1329
                                  Handle<Object> value,
                                  uint32_t start_from) final {
1330
    return Subclass::LastIndexOfValueImpl(receiver, value, start_from);
1331 1332
  }

1333
  static void ReverseImpl(JSObject receiver) { UNREACHABLE(); }
1334

1335
  void Reverse(JSObject receiver) final { Subclass::ReverseImpl(receiver); }
1336

1337
  static uint32_t GetIndexForEntryImpl(FixedArrayBase backing_store,
1338 1339
                                       uint32_t entry) {
    return entry;
1340 1341
  }

1342
  static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject holder,
1343
                                       FixedArrayBase backing_store,
1344
                                       uint32_t index, PropertyFilter filter) {
1345
    DCHECK(IsFastElementsKind(kind()));
1346
    uint32_t length = Subclass::GetMaxIndex(holder, backing_store);
1347
    if (IsHoleyElementsKind(kind())) {
1348
      return index < length &&
1349 1350
                     !BackingStore::cast(backing_store)
                          ->is_the_hole(isolate, index)
1351 1352 1353 1354 1355
                 ? index
                 : kMaxUInt32;
    } else {
      return index < length ? index : kMaxUInt32;
    }
1356 1357
  }

1358
  uint32_t GetEntryForIndex(Isolate* isolate, JSObject holder,
1359
                            FixedArrayBase backing_store,
1360
                            uint32_t index) final {
1361
    return Subclass::GetEntryForIndexImpl(isolate, holder, backing_store, index,
1362
                                          ALL_PROPERTIES);
1363 1364
  }

1365
  static PropertyDetails GetDetailsImpl(FixedArrayBase backing_store,
1366
                                        uint32_t entry) {
1367
    return PropertyDetails(kData, NONE, PropertyCellType::kNoCell);
1368 1369
  }

1370
  static PropertyDetails GetDetailsImpl(JSObject holder, uint32_t entry) {
1371
    return PropertyDetails(kData, NONE, PropertyCellType::kNoCell);
1372 1373
  }

1374
  PropertyDetails GetDetails(JSObject holder, uint32_t entry) final {
1375
    return Subclass::GetDetailsImpl(holder, entry);
1376 1377
  }

1378 1379 1380 1381
  Handle<FixedArray> CreateListFromArrayLike(Isolate* isolate,
                                             Handle<JSObject> object,
                                             uint32_t length) final {
    return Subclass::CreateListFromArrayLikeImpl(isolate, object, length);
1382
  }
1383

1384 1385 1386
  static Handle<FixedArray> CreateListFromArrayLikeImpl(Isolate* isolate,
                                                        Handle<JSObject> object,
                                                        uint32_t length) {
1387 1388 1389
    UNREACHABLE();
  }

1390 1391 1392 1393 1394
 private:
  DISALLOW_COPY_AND_ASSIGN(ElementsAccessorBase);
};


1395 1396 1397 1398 1399 1400 1401 1402
class DictionaryElementsAccessor
    : public ElementsAccessorBase<DictionaryElementsAccessor,
                                  ElementsKindTraits<DICTIONARY_ELEMENTS> > {
 public:
  explicit DictionaryElementsAccessor(const char* name)
      : ElementsAccessorBase<DictionaryElementsAccessor,
                             ElementsKindTraits<DICTIONARY_ELEMENTS> >(name) {}

1403
  static uint32_t GetMaxIndex(JSObject receiver, FixedArrayBase elements) {
1404 1405 1406 1407
    // We cannot properly estimate this for dictionaries.
    UNREACHABLE();
  }

1408
  static uint32_t GetMaxNumberOfEntries(JSObject receiver,
1409
                                        FixedArrayBase backing_store) {
1410 1411 1412
    return NumberOfElementsImpl(receiver, backing_store);
  }

1413
  static uint32_t NumberOfElementsImpl(JSObject receiver,
1414
                                       FixedArrayBase backing_store) {
1415
    NumberDictionary dict = NumberDictionary::cast(backing_store);
1416
    return dict->NumberOfElements();
1417 1418
  }

1419 1420
  static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array,
                            uint32_t length,
1421
                            Handle<FixedArrayBase> backing_store) {
1422 1423
    Handle<NumberDictionary> dict =
        Handle<NumberDictionary>::cast(backing_store);
1424 1425 1426
    int capacity = dict->Capacity();
    uint32_t old_length = 0;
    CHECK(array->length()->ToArrayLength(&old_length));
1427 1428
    {
      DisallowHeapAllocation no_gc;
1429
      ReadOnlyRoots roots(isolate);
1430 1431 1432 1433 1434
      if (length < old_length) {
        if (dict->requires_slow_elements()) {
          // Find last non-deletable element in range of elements to be
          // deleted and adjust range accordingly.
          for (int entry = 0; entry < capacity; entry++) {
1435
            Object index = dict->KeyAt(entry);
1436
            if (dict->IsKey(roots, index)) {
1437 1438 1439 1440 1441
              uint32_t number = static_cast<uint32_t>(index->Number());
              if (length <= number && number < old_length) {
                PropertyDetails details = dict->DetailsAt(entry);
                if (!details.IsConfigurable()) length = number + 1;
              }
1442 1443 1444 1445
            }
          }
        }

1446 1447 1448 1449 1450 1451 1452
        if (length == 0) {
          // Flush the backing store.
          array->initialize_elements();
        } else {
          // Remove elements that should be deleted.
          int removed_entries = 0;
          for (int entry = 0; entry < capacity; entry++) {
1453
            Object index = dict->KeyAt(entry);
1454
            if (dict->IsKey(roots, index)) {
1455 1456
              uint32_t number = static_cast<uint32_t>(index->Number());
              if (length <= number && number < old_length) {
1457
                dict->ClearEntry(isolate, entry);
1458 1459
                removed_entries++;
              }
1460 1461 1462
            }
          }

1463 1464 1465 1466
          if (removed_entries > 0) {
            // Update the number of elements.
            dict->ElementsRemoved(removed_entries);
          }
1467
        }
1468 1469 1470 1471 1472 1473 1474
      }
    }

    Handle<Object> length_obj = isolate->factory()->NewNumberFromUint(length);
    array->set_length(*length_obj);
  }

1475 1476
  static void CopyElementsImpl(Isolate* isolate, FixedArrayBase from,
                               uint32_t from_start, FixedArrayBase to,
1477 1478
                               ElementsKind from_kind, uint32_t to_start,
                               int packed_size, int copy_size) {
1479 1480 1481
    UNREACHABLE();
  }

1482 1483 1484 1485 1486 1487 1488 1489 1490 1491
  static Handle<JSObject> SliceImpl(Handle<JSObject> receiver, uint32_t start,
                                    uint32_t end) {
    Isolate* isolate = receiver->GetIsolate();
    uint32_t result_length = end < start ? 0u : end - start;

    // Result must also be a dictionary.
    Handle<JSArray> result_array =
        isolate->factory()->NewJSArray(0, HOLEY_ELEMENTS);
    JSObject::NormalizeElements(result_array);
    result_array->set_length(Smi::FromInt(result_length));
1492
    Handle<NumberDictionary> source_dict(
1493
        NumberDictionary::cast(receiver->elements()), isolate);
1494
    int entry_count = source_dict->Capacity();
1495
    ReadOnlyRoots roots(isolate);
1496
    for (int i = 0; i < entry_count; i++) {
1497
      Object key = source_dict->KeyAt(i);
1498
      if (!source_dict->ToKey(roots, i, &key)) continue;
1499 1500 1501
      uint64_t key_value = NumberToInt64(key);
      if (key_value >= start && key_value < end) {
        Handle<NumberDictionary> dest_dict(
1502
            NumberDictionary::cast(result_array->elements()), isolate);
1503 1504 1505 1506 1507
        Handle<Object> value(source_dict->ValueAt(i), isolate);
        PropertyDetails details = source_dict->DetailsAt(i);
        PropertyAttributes attr = details.attributes();
        AddImpl(result_array, static_cast<uint32_t>(key_value) - start, value,
                attr, 0);
1508 1509 1510 1511 1512
      }
    }

    return result_array;
  }
1513

1514
  static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) {
1515 1516
    Handle<NumberDictionary> dict(NumberDictionary::cast(obj->elements()),
                                  obj->GetIsolate());
1517
    dict = NumberDictionary::DeleteEntry(obj->GetIsolate(), dict, entry);
1518
    obj->set_elements(*dict);
1519 1520
  }

1521
  static bool HasAccessorsImpl(JSObject holder, FixedArrayBase backing_store) {
1522
    DisallowHeapAllocation no_gc;
1523
    NumberDictionary dict = NumberDictionary::cast(backing_store);
1524 1525
    if (!dict->requires_slow_elements()) return false;
    int capacity = dict->Capacity();
1526
    ReadOnlyRoots roots = holder->GetReadOnlyRoots();
1527
    for (int i = 0; i < capacity; i++) {
1528
      Object key = dict->KeyAt(i);
1529
      if (!dict->IsKey(roots, key)) continue;
1530
      PropertyDetails details = dict->DetailsAt(i);
1531
      if (details.kind() == kAccessor) return true;
1532 1533 1534 1535
    }
    return false;
  }

1536
  static Object GetRaw(FixedArrayBase store, uint32_t entry) {
1537
    NumberDictionary backing_store = NumberDictionary::cast(store);
1538 1539 1540
    return backing_store->ValueAt(entry);
  }

1541
  static Handle<Object> GetImpl(Isolate* isolate, FixedArrayBase backing_store,
1542 1543
                                uint32_t entry) {
    return handle(GetRaw(backing_store, entry), isolate);
1544 1545 1546
  }

  static inline void SetImpl(Handle<JSObject> holder, uint32_t entry,
1547
                             Object value) {
1548 1549 1550
    SetImpl(holder->elements(), entry, value);
  }

1551
  static inline void SetImpl(FixedArrayBase backing_store, uint32_t entry,
1552
                             Object value) {
1553
    NumberDictionary::cast(backing_store)->ValueAtPut(entry, value);
1554 1555 1556
  }

  static void ReconfigureImpl(Handle<JSObject> object,
1557
                              Handle<FixedArrayBase> store, uint32_t entry,
1558 1559
                              Handle<Object> value,
                              PropertyAttributes attributes) {
1560
    NumberDictionary dictionary = NumberDictionary::cast(*store);
1561
    if (attributes != NONE) object->RequireSlowElements(dictionary);
1562 1563
    dictionary->ValueAtPut(entry, *value);
    PropertyDetails details = dictionary->DetailsAt(entry);
1564 1565 1566
    details = PropertyDetails(kData, attributes, PropertyCellType::kNoCell,
                              details.dictionary_index());

1567
    dictionary->DetailsAtPut(object->GetIsolate(), entry, details);
1568 1569
  }

1570
  static void AddImpl(Handle<JSObject> object, uint32_t index,
1571 1572
                      Handle<Object> value, PropertyAttributes attributes,
                      uint32_t new_capacity) {
1573
    PropertyDetails details(kData, attributes, PropertyCellType::kNoCell);
1574
    Handle<NumberDictionary> dictionary =
1575
        object->HasFastElements() || object->HasFastStringWrapperElements()
1576
            ? JSObject::NormalizeElements(object)
1577 1578
            : handle(NumberDictionary::cast(object->elements()),
                     object->GetIsolate());
1579 1580
    Handle<NumberDictionary> new_dictionary = NumberDictionary::Add(
        object->GetIsolate(), dictionary, index, value, details);
1581
    new_dictionary->UpdateMaxNumberKey(index, object);
1582
    if (attributes != NONE) object->RequireSlowElements(*new_dictionary);
1583 1584 1585 1586
    if (dictionary.is_identical_to(new_dictionary)) return;
    object->set_elements(*new_dictionary);
  }

1587
  static bool HasEntryImpl(Isolate* isolate, FixedArrayBase store,
1588
                           uint32_t entry) {
1589
    DisallowHeapAllocation no_gc;
1590
    NumberDictionary dict = NumberDictionary::cast(store);
1591
    Object index = dict->KeyAt(entry);
1592
    return !index->IsTheHole(isolate);
1593 1594
  }

1595
  static uint32_t GetIndexForEntryImpl(FixedArrayBase store, uint32_t entry) {
1596
    DisallowHeapAllocation no_gc;
1597
    NumberDictionary dict = NumberDictionary::cast(store);
1598
    uint32_t result = 0;
1599
    CHECK(dict->KeyAt(entry)->ToArrayIndex(&result));
1600 1601 1602
    return result;
  }

1603
  static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject holder,
1604
                                       FixedArrayBase store, uint32_t index,
1605
                                       PropertyFilter filter) {
1606
    DisallowHeapAllocation no_gc;
1607
    NumberDictionary dictionary = NumberDictionary::cast(store);
1608
    int entry = dictionary->FindEntry(isolate, index);
1609
    if (entry == NumberDictionary::kNotFound) return kMaxUInt32;
1610
    if (filter != ALL_PROPERTIES) {
1611 1612 1613 1614 1615
      PropertyDetails details = dictionary->DetailsAt(entry);
      PropertyAttributes attr = details.attributes();
      if ((attr & filter) != 0) return kMaxUInt32;
    }
    return static_cast<uint32_t>(entry);
1616 1617
  }

1618
  static PropertyDetails GetDetailsImpl(JSObject holder, uint32_t entry) {
1619 1620 1621
    return GetDetailsImpl(holder->elements(), entry);
  }

1622
  static PropertyDetails GetDetailsImpl(FixedArrayBase backing_store,
1623
                                        uint32_t entry) {
1624
    return NumberDictionary::cast(backing_store)->DetailsAt(entry);
1625
  }
1626

1627
  static uint32_t FilterKey(Handle<NumberDictionary> dictionary, int entry,
1628
                            Object raw_key, PropertyFilter filter) {
1629 1630 1631 1632 1633
    DCHECK(raw_key->IsNumber());
    DCHECK_LE(raw_key->Number(), kMaxUInt32);
    PropertyDetails details = dictionary->DetailsAt(entry);
    PropertyAttributes attr = details.attributes();
    if ((attr & filter) != 0) return kMaxUInt32;
1634
    return static_cast<uint32_t>(raw_key->Number());
1635 1636
  }

1637
  static uint32_t GetKeyForEntryImpl(Isolate* isolate,
1638
                                     Handle<NumberDictionary> dictionary,
1639 1640
                                     int entry, PropertyFilter filter) {
    DisallowHeapAllocation no_gc;
1641
    Object raw_key = dictionary->KeyAt(entry);
1642
    if (!dictionary->IsKey(ReadOnlyRoots(isolate), raw_key)) return kMaxUInt32;
1643 1644 1645
    return FilterKey(dictionary, entry, raw_key, filter);
  }

1646 1647
  static void CollectElementIndicesImpl(Handle<JSObject> object,
                                        Handle<FixedArrayBase> backing_store,
1648 1649
                                        KeyAccumulator* keys) {
    if (keys->filter() & SKIP_STRINGS) return;
1650
    Isolate* isolate = keys->isolate();
1651 1652
    Handle<NumberDictionary> dictionary =
        Handle<NumberDictionary>::cast(backing_store);
1653
    int capacity = dictionary->Capacity();
1654 1655
    Handle<FixedArray> elements = isolate->factory()->NewFixedArray(
        GetMaxNumberOfEntries(*object, *backing_store));
1656
    int insertion_index = 0;
1657
    PropertyFilter filter = keys->filter();
1658
    ReadOnlyRoots roots(isolate);
1659
    for (int i = 0; i < capacity; i++) {
1660
      Object raw_key = dictionary->KeyAt(i);
1661
      if (!dictionary->IsKey(roots, raw_key)) continue;
1662 1663
      uint32_t key = FilterKey(dictionary, i, raw_key, filter);
      if (key == kMaxUInt32) {
1664
        keys->AddShadowingKey(raw_key);
1665 1666 1667
        continue;
      }
      elements->set(insertion_index, raw_key);
1668 1669
      insertion_index++;
    }
1670
    SortIndices(isolate, elements, insertion_index);
1671 1672
    for (int i = 0; i < insertion_index; i++) {
      keys->AddKey(elements->get(i));
1673 1674
    }
  }
1675

1676 1677 1678
  static Handle<FixedArray> DirectCollectElementIndicesImpl(
      Isolate* isolate, Handle<JSObject> object,
      Handle<FixedArrayBase> backing_store, GetKeysConversion convert,
1679 1680
      PropertyFilter filter, Handle<FixedArray> list, uint32_t* nof_indices,
      uint32_t insertion_index = 0) {
1681 1682
    if (filter & SKIP_STRINGS) return list;
    if (filter & ONLY_ALL_CAN_READ) return list;
1683

1684 1685
    Handle<NumberDictionary> dictionary =
        Handle<NumberDictionary>::cast(backing_store);
1686 1687
    uint32_t capacity = dictionary->Capacity();
    for (uint32_t i = 0; i < capacity; i++) {
1688
      uint32_t key = GetKeyForEntryImpl(isolate, dictionary, i, filter);
1689 1690 1691 1692 1693 1694 1695 1696 1697
      if (key == kMaxUInt32) continue;
      Handle<Object> index = isolate->factory()->NewNumberFromUint(key);
      list->set(insertion_index, *index);
      insertion_index++;
    }
    *nof_indices = insertion_index;
    return list;
  }

1698 1699 1700
  static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver,
                                              KeyAccumulator* accumulator,
                                              AddKeyConversion convert) {
1701
    Isolate* isolate = accumulator->isolate();
1702 1703
    Handle<NumberDictionary> dictionary(
        NumberDictionary::cast(receiver->elements()), isolate);
1704
    int capacity = dictionary->Capacity();
1705
    ReadOnlyRoots roots(isolate);
1706
    for (int i = 0; i < capacity; i++) {
1707
      Object k = dictionary->KeyAt(i);
1708
      if (!dictionary->IsKey(roots, k)) continue;
1709
      Object value = dictionary->ValueAt(i);
1710
      DCHECK(!value->IsTheHole(isolate));
1711 1712 1713 1714 1715
      DCHECK(!value->IsAccessorPair());
      DCHECK(!value->IsAccessorInfo());
      accumulator->AddKey(value, convert);
    }
  }
1716 1717 1718 1719 1720

  static bool IncludesValueFastPath(Isolate* isolate, Handle<JSObject> receiver,
                                    Handle<Object> value, uint32_t start_from,
                                    uint32_t length, Maybe<bool>* result) {
    DisallowHeapAllocation no_gc;
1721
    NumberDictionary dictionary = NumberDictionary::cast(receiver->elements());
1722
    int capacity = dictionary->Capacity();
1723 1724
    Object the_hole = ReadOnlyRoots(isolate).the_hole_value();
    Object undefined = ReadOnlyRoots(isolate).undefined_value();
1725 1726 1727 1728 1729

    // Scan for accessor properties. If accessors are present, then elements
    // must be accessed in order via the slow path.
    bool found = false;
    for (int i = 0; i < capacity; ++i) {
1730
      Object k = dictionary->KeyAt(i);
1731 1732 1733 1734 1735 1736 1737 1738
      if (k == the_hole) continue;
      if (k == undefined) continue;

      uint32_t index;
      if (!k->ToArrayIndex(&index) || index < start_from || index >= length) {
        continue;
      }

1739
      if (dictionary->DetailsAt(i).kind() == kAccessor) {
1740 1741 1742 1743
        // Restart from beginning in slow path, otherwise we may observably
        // access getters out of order
        return false;
      } else if (!found) {
1744
        Object element_k = dictionary->ValueAt(i);
1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766
        if (value->SameValueZero(element_k)) found = true;
      }
    }

    *result = Just(found);
    return true;
  }

  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
                                       Handle<JSObject> receiver,
                                       Handle<Object> value,
                                       uint32_t start_from, uint32_t length) {
    DCHECK(JSObject::PrototypeHasNoElements(isolate, *receiver));
    bool search_for_hole = value->IsUndefined(isolate);

    if (!search_for_hole) {
      Maybe<bool> result = Nothing<bool>();
      if (DictionaryElementsAccessor::IncludesValueFastPath(
              isolate, receiver, value, start_from, length, &result)) {
        return result;
      }
    }
1767 1768
    ElementsKind original_elements_kind = receiver->GetElementsKind();
    USE(original_elements_kind);
1769 1770
    Handle<NumberDictionary> dictionary(
        NumberDictionary::cast(receiver->elements()), isolate);
1771 1772 1773
    // Iterate through entire range, as accessing elements out of order is
    // observable
    for (uint32_t k = start_from; k < length; ++k) {
1774
      DCHECK_EQ(receiver->GetElementsKind(), original_elements_kind);
1775
      int entry = dictionary->FindEntry(isolate, k);
1776
      if (entry == NumberDictionary::kNotFound) {
1777 1778 1779 1780
        if (search_for_hole) return Just(true);
        continue;
      }

1781
      PropertyDetails details = GetDetailsImpl(*dictionary, entry);
1782 1783
      switch (details.kind()) {
        case kData: {
1784
          Object element_k = dictionary->ValueAt(entry);
1785 1786 1787 1788 1789 1790 1791 1792 1793 1794
          if (value->SameValueZero(element_k)) return Just(true);
          break;
        }
        case kAccessor: {
          LookupIterator it(isolate, receiver, k,
                            LookupIterator::OWN_SKIP_INTERCEPTOR);
          DCHECK(it.IsFound());
          DCHECK_EQ(it.state(), LookupIterator::ACCESSOR);
          Handle<Object> element_k;

1795 1796 1797
          ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_k,
                                           Object::GetPropertyWithAccessor(&it),
                                           Nothing<bool>());
1798 1799 1800

          if (value->SameValueZero(*element_k)) return Just(true);

1801
          // Bailout to slow path if elements on prototype changed
1802 1803 1804 1805
          if (!JSObject::PrototypeHasNoElements(isolate, *receiver)) {
            return IncludesValueSlowPath(isolate, receiver, value, k + 1,
                                         length);
          }
1806 1807 1808 1809 1810

          // Continue if elements unchanged
          if (*dictionary == receiver->elements()) continue;

          // Otherwise, bailout or update elements
1811 1812 1813 1814 1815 1816 1817 1818

          // If switched to initial elements, return true if searching for
          // undefined, and false otherwise.
          if (receiver->map()->GetInitialElements() == receiver->elements()) {
            return Just(search_for_hole);
          }

          // If switched to fast elements, continue with the correct accessor.
1819
          if (receiver->GetElementsKind() != DICTIONARY_ELEMENTS) {
1820 1821 1822
            ElementsAccessor* accessor = receiver->GetElementsAccessor();
            return accessor->IncludesValue(isolate, receiver, value, k + 1,
                                           length);
1823
          }
1824 1825
          dictionary =
              handle(NumberDictionary::cast(receiver->elements()), isolate);
1826 1827 1828 1829 1830 1831
          break;
        }
      }
    }
    return Just(false);
  }
1832 1833 1834 1835 1836 1837 1838

  static Maybe<int64_t> IndexOfValueImpl(Isolate* isolate,
                                         Handle<JSObject> receiver,
                                         Handle<Object> value,
                                         uint32_t start_from, uint32_t length) {
    DCHECK(JSObject::PrototypeHasNoElements(isolate, *receiver));

1839 1840
    ElementsKind original_elements_kind = receiver->GetElementsKind();
    USE(original_elements_kind);
1841 1842
    Handle<NumberDictionary> dictionary(
        NumberDictionary::cast(receiver->elements()), isolate);
1843 1844 1845
    // Iterate through entire range, as accessing elements out of order is
    // observable.
    for (uint32_t k = start_from; k < length; ++k) {
1846
      DCHECK_EQ(receiver->GetElementsKind(), original_elements_kind);
1847
      int entry = dictionary->FindEntry(isolate, k);
1848
      if (entry == NumberDictionary::kNotFound) continue;
1849 1850 1851 1852

      PropertyDetails details = GetDetailsImpl(*dictionary, entry);
      switch (details.kind()) {
        case kData: {
1853
          Object element_k = dictionary->ValueAt(entry);
1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865
          if (value->StrictEquals(element_k)) {
            return Just<int64_t>(k);
          }
          break;
        }
        case kAccessor: {
          LookupIterator it(isolate, receiver, k,
                            LookupIterator::OWN_SKIP_INTERCEPTOR);
          DCHECK(it.IsFound());
          DCHECK_EQ(it.state(), LookupIterator::ACCESSOR);
          Handle<Object> element_k;

1866 1867 1868
          ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_k,
                                           Object::GetPropertyWithAccessor(&it),
                                           Nothing<int64_t>());
1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886

          if (value->StrictEquals(*element_k)) return Just<int64_t>(k);

          // Bailout to slow path if elements on prototype changed.
          if (!JSObject::PrototypeHasNoElements(isolate, *receiver)) {
            return IndexOfValueSlowPath(isolate, receiver, value, k + 1,
                                        length);
          }

          // Continue if elements unchanged.
          if (*dictionary == receiver->elements()) continue;

          // Otherwise, bailout or update elements.
          if (receiver->GetElementsKind() != DICTIONARY_ELEMENTS) {
            // Otherwise, switch to slow path.
            return IndexOfValueSlowPath(isolate, receiver, value, k + 1,
                                        length);
          }
1887 1888
          dictionary =
              handle(NumberDictionary::cast(receiver->elements()), isolate);
1889 1890 1891 1892 1893 1894
          break;
        }
      }
    }
    return Just<int64_t>(-1);
  }
1895

1896
  static void ValidateContents(JSObject holder, int length) {
1897 1898 1899 1900
    DisallowHeapAllocation no_gc;
#if DEBUG
    DCHECK_EQ(holder->map()->elements_kind(), DICTIONARY_ELEMENTS);
    if (!FLAG_enable_slow_asserts) return;
1901
    ReadOnlyRoots roots = holder->GetReadOnlyRoots();
1902
    NumberDictionary dictionary = NumberDictionary::cast(holder->elements());
1903 1904 1905 1906 1907
    // Validate the requires_slow_elements and max_number_key values.
    int capacity = dictionary->Capacity();
    bool requires_slow_elements = false;
    int max_key = 0;
    for (int i = 0; i < capacity; ++i) {
1908
      Object k;
1909
      if (!dictionary->ToKey(roots, i, &k)) continue;
1910
      DCHECK_LE(0.0, k->Number());
1911
      if (k->Number() > NumberDictionary::kRequiresSlowElementsLimit) {
1912 1913
        requires_slow_elements = true;
      } else {
jgruber's avatar
jgruber committed
1914
        max_key = Max(max_key, Smi::ToInt(k));
1915 1916 1917 1918 1919 1920 1921 1922 1923
      }
    }
    if (requires_slow_elements) {
      DCHECK(dictionary->requires_slow_elements());
    } else if (!dictionary->requires_slow_elements()) {
      DCHECK_LE(max_key, dictionary->max_number_key());
    }
#endif
  }
1924 1925
};

1926

1927
// Super class for all fast element arrays.
1928 1929
template <typename Subclass, typename KindTraits>
class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
1930 1931
 public:
  explicit FastElementsAccessor(const char* name)
1932
      : ElementsAccessorBase<Subclass, KindTraits>(name) {}
1933

1934
  typedef typename KindTraits::BackingStore BackingStore;
1935

1936 1937
  static Handle<NumberDictionary> NormalizeImpl(Handle<JSObject> object,
                                                Handle<FixedArrayBase> store) {
1938
    Isolate* isolate = object->GetIsolate();
1939
    ElementsKind kind = Subclass::kind();
1940 1941 1942

    // Ensure that notifications fire if the array or object prototypes are
    // normalizing.
1943 1944
    if (IsSmiOrObjectElementsKind(kind) ||
        kind == FAST_STRING_WRAPPER_ELEMENTS) {
1945
      isolate->UpdateNoElementsProtectorOnNormalizeElements(object);
1946 1947 1948
    }

    int capacity = object->GetFastElementsUsage();
1949 1950
    Handle<NumberDictionary> dictionary =
        NumberDictionary::New(isolate, capacity);
1951 1952 1953

    PropertyDetails details = PropertyDetails::Empty();
    int j = 0;
1954
    int max_number_key = -1;
1955
    for (int i = 0; j < capacity; i++) {
1956
      if (IsHoleyElementsKind(kind)) {
1957
        if (BackingStore::cast(*store)->is_the_hole(isolate, i)) continue;
1958
      }
1959
      max_number_key = i;
1960
      Handle<Object> value = Subclass::GetImpl(isolate, *store, i);
1961 1962
      dictionary =
          NumberDictionary::Add(isolate, dictionary, i, value, details);
1963 1964
      j++;
    }
1965 1966 1967 1968 1969

    if (max_number_key > 0) {
      dictionary->UpdateMaxNumberKey(static_cast<uint32_t>(max_number_key),
                                     object);
    }
1970 1971 1972
    return dictionary;
  }

1973 1974 1975
  static void DeleteAtEnd(Handle<JSObject> obj,
                          Handle<BackingStore> backing_store, uint32_t entry) {
    uint32_t length = static_cast<uint32_t>(backing_store->length());
1976
    Isolate* isolate = obj->GetIsolate();
1977
    for (; entry > 0; entry--) {
1978
      if (!backing_store->is_the_hole(isolate, entry - 1)) break;
1979 1980
    }
    if (entry == 0) {
1981
      FixedArray empty = ReadOnlyRoots(isolate).empty_fixed_array();
1982 1983 1984
      // Dynamically ask for the elements kind here since we manually redirect
      // the operations for argument backing stores.
      if (obj->GetElementsKind() == FAST_SLOPPY_ARGUMENTS_ELEMENTS) {
1985
        SloppyArgumentsElements::cast(obj->elements())->set_arguments(empty);
1986 1987 1988 1989 1990 1991
      } else {
        obj->set_elements(empty);
      }
      return;
    }

1992
    isolate->heap()->RightTrimFixedArray(*backing_store, length - entry);
1993 1994
  }

1995
  static void DeleteCommon(Handle<JSObject> obj, uint32_t entry,
1996
                           Handle<FixedArrayBase> store) {
1997
    DCHECK(obj->HasSmiOrObjectElements() || obj->HasDoubleElements() ||
1998 1999
           obj->HasFastArgumentsElements() ||
           obj->HasFastStringWrapperElements());
2000
    Handle<BackingStore> backing_store = Handle<BackingStore>::cast(store);
2001 2002 2003 2004 2005 2006
    if (!obj->IsJSArray() &&
        entry == static_cast<uint32_t>(store->length()) - 1) {
      DeleteAtEnd(obj, backing_store, entry);
      return;
    }

2007
    Isolate* isolate = obj->GetIsolate();
2008
    backing_store->set_the_hole(isolate, entry);
2009 2010 2011 2012 2013 2014

    // TODO(verwaest): Move this out of elements.cc.
    // If an old space backing store is larger than a certain size and
    // has too few used values, normalize it.
    const int kMinLengthForSparsenessCheck = 64;
    if (backing_store->length() < kMinLengthForSparsenessCheck) return;
2015
    // TODO(ulan): Check if it works with young large objects.
2016
    if (ObjectInYoungGeneration(*backing_store)) return;
2017 2018 2019 2020 2021
    uint32_t length = 0;
    if (obj->IsJSArray()) {
      JSArray::cast(*obj)->length()->ToArrayLength(&length);
    } else {
      length = static_cast<uint32_t>(store->length());
2022
    }
2023 2024 2025 2026 2027 2028 2029 2030

    // To avoid doing the check on every delete, use a counter-based heuristic.
    const int kLengthFraction = 16;
    // The above constant must be large enough to ensure that we check for
    // normalization frequently enough. At a minimum, it should be large
    // enough to reliably hit the "window" of remaining elements count where
    // normalization would be beneficial.
    STATIC_ASSERT(kLengthFraction >=
2031 2032
                  NumberDictionary::kEntrySize *
                      NumberDictionary::kPreferFastElementsSizeFactor);
2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044
    size_t current_counter = isolate->elements_deletion_counter();
    if (current_counter < length / kLengthFraction) {
      isolate->set_elements_deletion_counter(current_counter + 1);
      return;
    }
    // Reset the counter whenever the full check is performed.
    isolate->set_elements_deletion_counter(0);

    if (!obj->IsJSArray()) {
      uint32_t i;
      for (i = entry + 1; i < length; i++) {
        if (!backing_store->is_the_hole(isolate, i)) break;
2045
      }
2046 2047 2048 2049 2050 2051 2052 2053 2054 2055
      if (i == length) {
        DeleteAtEnd(obj, backing_store, entry);
        return;
      }
    }
    int num_used = 0;
    for (int i = 0; i < backing_store->length(); ++i) {
      if (!backing_store->is_the_hole(isolate, i)) {
        ++num_used;
        // Bail out if a number dictionary wouldn't be able to save much space.
2056 2057 2058
        if (NumberDictionary::kPreferFastElementsSizeFactor *
                NumberDictionary::ComputeCapacity(num_used) *
                NumberDictionary::kEntrySize >
2059 2060
            static_cast<uint32_t>(backing_store->length())) {
          return;
2061
        }
2062 2063
      }
    }
2064
    JSObject::NormalizeElements(obj);
2065 2066
  }

2067
  static void ReconfigureImpl(Handle<JSObject> object,
2068
                              Handle<FixedArrayBase> store, uint32_t entry,
2069 2070
                              Handle<Object> value,
                              PropertyAttributes attributes) {
2071
    Handle<NumberDictionary> dictionary = JSObject::NormalizeElements(object);
2072
    entry = dictionary->FindEntry(object->GetIsolate(), entry);
2073 2074
    DictionaryElementsAccessor::ReconfigureImpl(object, dictionary, entry,
                                                value, attributes);
2075 2076
  }

2077
  static void AddImpl(Handle<JSObject> object, uint32_t index,
2078 2079 2080 2081
                      Handle<Object> value, PropertyAttributes attributes,
                      uint32_t new_capacity) {
    DCHECK_EQ(NONE, attributes);
    ElementsKind from_kind = object->GetElementsKind();
2082
    ElementsKind to_kind = Subclass::kind();
2083
    if (IsDictionaryElementsKind(from_kind) ||
2084
        IsDoubleElementsKind(from_kind) != IsDoubleElementsKind(to_kind) ||
2085 2086 2087
        Subclass::GetCapacityImpl(*object, object->elements()) !=
            new_capacity) {
      Subclass::GrowCapacityAndConvertImpl(object, new_capacity);
2088
    } else {
2089
      if (IsFastElementsKind(from_kind) && from_kind != to_kind) {
2090 2091
        JSObject::TransitionElementsKind(object, to_kind);
      }
2092 2093
      if (IsSmiOrObjectElementsKind(from_kind)) {
        DCHECK(IsSmiOrObjectElementsKind(to_kind));
2094 2095 2096
        JSObject::EnsureWritableFastElements(object);
      }
    }
2097
    Subclass::SetImpl(object, index, *value);
2098 2099
  }

2100
  static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) {
2101 2102 2103 2104
    ElementsKind kind = KindTraits::Kind;
    if (IsFastPackedElementsKind(kind)) {
      JSObject::TransitionElementsKind(obj, GetHoleyElementsKind(kind));
    }
2105
    if (IsSmiOrObjectElementsKind(KindTraits::Kind)) {
2106 2107
      JSObject::EnsureWritableFastElements(obj);
    }
2108
    DeleteCommon(obj, entry, handle(obj->elements(), obj->GetIsolate()));
2109 2110
  }

2111
  static bool HasEntryImpl(Isolate* isolate, FixedArrayBase backing_store,
2112 2113 2114 2115
                           uint32_t entry) {
    return !BackingStore::cast(backing_store)->is_the_hole(isolate, entry);
  }

2116
  static uint32_t NumberOfElementsImpl(JSObject receiver,
2117
                                       FixedArrayBase backing_store) {
2118 2119 2120 2121 2122 2123 2124 2125
    uint32_t max_index = Subclass::GetMaxIndex(receiver, backing_store);
    if (IsFastPackedElementsKind(Subclass::kind())) return max_index;
    Isolate* isolate = receiver->GetIsolate();
    uint32_t count = 0;
    for (uint32_t i = 0; i < max_index; i++) {
      if (Subclass::HasEntryImpl(isolate, backing_store, i)) count++;
    }
    return count;
2126 2127
  }

2128 2129 2130
  static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver,
                                              KeyAccumulator* accumulator,
                                              AddKeyConversion convert) {
2131 2132
    Isolate* isolate = accumulator->isolate();
    Handle<FixedArrayBase> elements(receiver->elements(), isolate);
2133
    uint32_t length = Subclass::GetMaxNumberOfEntries(*receiver, *elements);
2134 2135
    for (uint32_t i = 0; i < length; i++) {
      if (IsFastPackedElementsKind(KindTraits::Kind) ||
2136
          HasEntryImpl(isolate, *elements, i)) {
2137
        accumulator->AddKey(Subclass::GetImpl(isolate, *elements, i), convert);
2138 2139 2140 2141
      }
    }
  }

2142
  static void ValidateContents(JSObject holder, int length) {
2143
#if DEBUG
2144
    Isolate* isolate = holder->GetIsolate();
2145
    Heap* heap = isolate->heap();
2146
    FixedArrayBase elements = holder->elements();
2147
    Map map = elements->map();
2148
    if (IsSmiOrObjectElementsKind(KindTraits::Kind)) {
2149
      DCHECK_NE(map, ReadOnlyRoots(heap).fixed_double_array_map());
2150
    } else if (IsDoubleElementsKind(KindTraits::Kind)) {
2151 2152
      DCHECK_NE(map, ReadOnlyRoots(heap).fixed_cow_array_map());
      if (map == ReadOnlyRoots(heap).fixed_array_map()) DCHECK_EQ(0, length);
2153 2154 2155
    } else {
      UNREACHABLE();
    }
2156
    if (length == 0) return;  // nothing to do!
2157
#if ENABLE_SLOW_DCHECKS
2158
    DisallowHeapAllocation no_gc;
2159
    BackingStore backing_store = BackingStore::cast(elements);
2160
    if (IsSmiElementsKind(KindTraits::Kind)) {
2161
      HandleScope scope(isolate);
2162
      for (int i = 0; i < length; i++) {
2163
        DCHECK(BackingStore::get(backing_store, i, isolate)->IsSmi() ||
2164
               (IsHoleyElementsKind(KindTraits::Kind) &&
2165
                backing_store->is_the_hole(isolate, i)));
2166
      }
2167 2168
    } else if (KindTraits::Kind == PACKED_ELEMENTS ||
               KindTraits::Kind == PACKED_DOUBLE_ELEMENTS) {
2169
      for (int i = 0; i < length; i++) {
2170
        DCHECK(!backing_store->is_the_hole(isolate, i));
2171 2172
      }
    } else {
2173
      DCHECK(IsHoleyElementsKind(KindTraits::Kind));
2174
    }
2175
#endif
2176 2177
#endif
  }
2178

2179
  static Handle<Object> PopImpl(Handle<JSArray> receiver) {
2180
    return Subclass::RemoveElement(receiver, AT_END);
2181 2182
  }

2183
  static Handle<Object> ShiftImpl(Handle<JSArray> receiver) {
2184
    return Subclass::RemoveElement(receiver, AT_START);
cbruni's avatar
cbruni committed
2185 2186
  }

2187
  static uint32_t PushImpl(Handle<JSArray> receiver,
2188
                           Arguments* args, uint32_t push_size) {
2189 2190
    Handle<FixedArrayBase> backing_store(receiver->elements(),
                                         receiver->GetIsolate());
2191 2192
    return Subclass::AddArguments(receiver, backing_store, args, push_size,
                                  AT_END);
2193
  }
2194

2195 2196
  static uint32_t UnshiftImpl(Handle<JSArray> receiver,
                              Arguments* args, uint32_t unshift_size) {
2197 2198
    Handle<FixedArrayBase> backing_store(receiver->elements(),
                                         receiver->GetIsolate());
2199 2200
    return Subclass::AddArguments(receiver, backing_store, args, unshift_size,
                                  AT_START);
2201 2202
  }

2203 2204
  static Handle<JSObject> SliceImpl(Handle<JSObject> receiver, uint32_t start,
                                    uint32_t end) {
2205
    Isolate* isolate = receiver->GetIsolate();
2206 2207
    Handle<FixedArrayBase> backing_store(receiver->elements(), isolate);
    int result_len = end < start ? 0u : end - start;
2208 2209 2210
    Handle<JSArray> result_array = isolate->factory()->NewJSArray(
        KindTraits::Kind, result_len, result_len);
    DisallowHeapAllocation no_gc;
2211 2212 2213
    Subclass::CopyElementsImpl(isolate, *backing_store, start,
                               result_array->elements(), KindTraits::Kind, 0,
                               kPackedSizeNotKnown, result_len);
2214
    Subclass::TryTransitionResultArrayToPacked(result_array);
2215 2216 2217
    return result_array;
  }

2218 2219 2220 2221 2222 2223
  static void MoveElements(Isolate* isolate, Handle<JSArray> receiver,
                           Handle<FixedArrayBase> backing_store, int dst_index,
                           int src_index, int len, int hole_start,
                           int hole_end) {
    Heap* heap = isolate->heap();
    Handle<BackingStore> dst_elms = Handle<BackingStore>::cast(backing_store);
2224 2225
    if (len > JSArray::kMaxCopyElements && dst_index == 0 &&
        heap->CanMoveObjectStart(*dst_elms)) {
2226 2227
      // Update all the copies of this backing_store handle.
      *dst_elms.location() =
2228 2229
          BackingStore::cast(heap->LeftTrimFixedArray(*dst_elms, src_index))
              ->ptr();
2230 2231 2232 2233 2234 2235
      receiver->set_elements(*dst_elms);
      // Adjust the hole offset as the array has been shrunk.
      hole_end -= src_index;
      DCHECK_LE(hole_start, backing_store->length());
      DCHECK_LE(hole_end, backing_store->length());
    } else if (len != 0) {
2236 2237
      WriteBarrierMode mode = GetWriteBarrierMode(KindTraits::Kind);
      dst_elms->MoveElements(heap, dst_index, src_index, len, mode);
2238 2239 2240 2241 2242 2243
    }
    if (hole_start != hole_end) {
      dst_elms->FillWithHoles(hole_start, hole_end);
    }
  }

2244 2245
  static Object FillImpl(Handle<JSObject> receiver, Handle<Object> obj_value,
                         uint32_t start, uint32_t end) {
2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269
    // Ensure indexes are within array bounds
    DCHECK_LE(0, start);
    DCHECK_LE(start, end);

    // Make sure COW arrays are copied.
    if (IsSmiOrObjectElementsKind(Subclass::kind())) {
      JSObject::EnsureWritableFastElements(receiver);
    }

    // Make sure we have enough space.
    uint32_t capacity =
        Subclass::GetCapacityImpl(*receiver, receiver->elements());
    if (end > capacity) {
      Subclass::GrowCapacityAndConvertImpl(receiver, end);
      CHECK_EQ(Subclass::kind(), receiver->GetElementsKind());
    }
    DCHECK_LE(end, Subclass::GetCapacityImpl(*receiver, receiver->elements()));

    for (uint32_t index = start; index < end; ++index) {
      Subclass::SetImpl(receiver, index, *obj_value);
    }
    return *receiver;
  }

2270 2271 2272 2273 2274 2275
  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
                                       Handle<JSObject> receiver,
                                       Handle<Object> search_value,
                                       uint32_t start_from, uint32_t length) {
    DCHECK(JSObject::PrototypeHasNoElements(isolate, *receiver));
    DisallowHeapAllocation no_gc;
2276
    FixedArrayBase elements_base = receiver->elements();
2277 2278 2279
    Object the_hole = ReadOnlyRoots(isolate).the_hole_value();
    Object undefined = ReadOnlyRoots(isolate).undefined_value();
    Object value = *search_value;
2280

2281 2282
    if (start_from >= length) return Just(false);

2283
    // Elements beyond the capacity of the backing store treated as undefined.
2284 2285 2286 2287 2288
    uint32_t elements_length = static_cast<uint32_t>(elements_base->length());
    if (value == undefined && elements_length < length) return Just(true);
    if (elements_length == 0) {
      DCHECK_NE(value, undefined);
      return Just(false);
2289 2290
    }

2291
    length = std::min(elements_length, length);
2292 2293 2294

    if (!value->IsNumber()) {
      if (value == undefined) {
2295 2296 2297 2298
        // Search for `undefined` or The Hole. Even in the case of
        // PACKED_DOUBLE_ELEMENTS or PACKED_SMI_ELEMENTS, we might encounter The
        // Hole here, since the {length} used here can be larger than
        // JSArray::length.
2299
        if (IsSmiOrObjectElementsKind(Subclass::kind())) {
2300 2301 2302
          auto elements = FixedArray::cast(receiver->elements());

          for (uint32_t k = start_from; k < length; ++k) {
2303
            Object element_k = elements->get(k);
2304

2305
            if (element_k == the_hole || element_k == undefined) {
2306 2307 2308 2309 2310
              return Just(true);
            }
          }
          return Just(false);
        } else {
2311 2312 2313
          // Search for The Hole in HOLEY_DOUBLE_ELEMENTS or
          // PACKED_DOUBLE_ELEMENTS.
          DCHECK(IsDoubleElementsKind(Subclass::kind()));
2314 2315 2316
          auto elements = FixedDoubleArray::cast(receiver->elements());

          for (uint32_t k = start_from; k < length; ++k) {
2317
            if (elements->is_the_hole(k)) {
2318 2319 2320 2321 2322
              return Just(true);
            }
          }
          return Just(false);
        }
2323
      } else if (!IsObjectElementsKind(Subclass::kind())) {
2324
        // Search for non-number, non-Undefined value, with either
2325 2326
        // PACKED_SMI_ELEMENTS, PACKED_DOUBLE_ELEMENTS, HOLEY_SMI_ELEMENTS or
        // HOLEY_DOUBLE_ELEMENTS. Guaranteed to return false, since these
2327 2328 2329 2330
        // elements kinds can only contain Number values or undefined.
        return Just(false);
      } else {
        // Search for non-number, non-Undefined value with either
2331
        // PACKED_ELEMENTS or HOLEY_ELEMENTS.
2332
        DCHECK(IsObjectElementsKind(Subclass::kind()));
2333 2334 2335
        auto elements = FixedArray::cast(receiver->elements());

        for (uint32_t k = start_from; k < length; ++k) {
2336
          Object element_k = elements->get(k);
2337
          if (element_k == the_hole) {
2338 2339 2340 2341 2342 2343 2344 2345 2346 2347
            continue;
          }

          if (value->SameValueZero(element_k)) return Just(true);
        }
        return Just(false);
      }
    } else {
      if (!value->IsNaN()) {
        double search_value = value->Number();
2348
        if (IsDoubleElementsKind(Subclass::kind())) {
2349 2350
          // Search for non-NaN Number in PACKED_DOUBLE_ELEMENTS or
          // HOLEY_DOUBLE_ELEMENTS --- Skip TheHole, and trust UCOMISD or
2351 2352 2353 2354
          // similar operation for result.
          auto elements = FixedDoubleArray::cast(receiver->elements());

          for (uint32_t k = start_from; k < length; ++k) {
2355
            if (elements->is_the_hole(k)) {
2356 2357 2358 2359 2360 2361
              continue;
            }
            if (elements->get_scalar(k) == search_value) return Just(true);
          }
          return Just(false);
        } else {
2362 2363
          // Search for non-NaN Number in PACKED_ELEMENTS, HOLEY_ELEMENTS,
          // PACKED_SMI_ELEMENTS or HOLEY_SMI_ELEMENTS --- Skip non-Numbers,
2364 2365 2366 2367
          // and trust UCOMISD or similar operation for result
          auto elements = FixedArray::cast(receiver->elements());

          for (uint32_t k = start_from; k < length; ++k) {
2368
            Object element_k = elements->get(k);
2369 2370 2371 2372 2373 2374 2375 2376
            if (element_k->IsNumber() && element_k->Number() == search_value) {
              return Just(true);
            }
          }
          return Just(false);
        }
      } else {
        // Search for NaN --- NaN cannot be represented with Smi elements, so
2377
        // abort if ElementsKind is PACKED_SMI_ELEMENTS or HOLEY_SMI_ELEMENTS
2378
        if (IsSmiElementsKind(Subclass::kind())) return Just(false);
2379

2380
        if (IsDoubleElementsKind(Subclass::kind())) {
2381 2382
          // Search for NaN in PACKED_DOUBLE_ELEMENTS or
          // HOLEY_DOUBLE_ELEMENTS --- Skip The Hole and trust
2383 2384 2385 2386
          // std::isnan(elementK) for result
          auto elements = FixedDoubleArray::cast(receiver->elements());

          for (uint32_t k = start_from; k < length; ++k) {
2387
            if (elements->is_the_hole(k)) {
2388 2389 2390 2391 2392 2393
              continue;
            }
            if (std::isnan(elements->get_scalar(k))) return Just(true);
          }
          return Just(false);
        } else {
2394 2395
          // Search for NaN in PACKED_ELEMENTS, HOLEY_ELEMENTS,
          // PACKED_SMI_ELEMENTS or HOLEY_SMI_ELEMENTS. Return true if
2396
          // elementK->IsHeapNumber() && std::isnan(elementK->Number())
2397
          DCHECK(IsSmiOrObjectElementsKind(Subclass::kind()));
2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408
          auto elements = FixedArray::cast(receiver->elements());

          for (uint32_t k = start_from; k < length; ++k) {
            if (elements->get(k)->IsNaN()) return Just(true);
          }
          return Just(false);
        }
      }
    }
  }

2409 2410 2411
  static Handle<FixedArray> CreateListFromArrayLikeImpl(Isolate* isolate,
                                                        Handle<JSObject> object,
                                                        uint32_t length) {
2412
    Handle<FixedArray> result = isolate->factory()->NewFixedArray(length);
2413
    Handle<FixedArrayBase> elements(object->elements(), isolate);
2414
    for (uint32_t i = 0; i < length; i++) {
2415
      if (!Subclass::HasElementImpl(isolate, *object, i, *elements)) continue;
2416 2417 2418 2419 2420 2421 2422 2423 2424 2425
      Handle<Object> value;
      value = Subclass::GetImpl(isolate, *elements, i);
      if (value->IsName()) {
        value = isolate->factory()->InternalizeName(Handle<Name>::cast(value));
      }
      result->set(i, *value);
    }
    return result;
  }

cbruni's avatar
cbruni committed
2426 2427
  static Handle<Object> RemoveElement(Handle<JSArray> receiver,
                                      Where remove_position) {
2428
    Isolate* isolate = receiver->GetIsolate();
2429
    ElementsKind kind = KindTraits::Kind;
2430
    if (IsSmiOrObjectElementsKind(kind)) {
2431 2432 2433 2434
      HandleScope scope(isolate);
      JSObject::EnsureWritableFastElements(receiver);
    }
    Handle<FixedArrayBase> backing_store(receiver->elements(), isolate);
jgruber's avatar
jgruber committed
2435
    uint32_t length = static_cast<uint32_t>(Smi::ToInt(receiver->length()));
2436
    DCHECK_GT(length, 0);
cbruni's avatar
cbruni committed
2437 2438
    int new_length = length - 1;
    int remove_index = remove_position == AT_START ? 0 : new_length;
2439 2440
    Handle<Object> result =
        Subclass::GetImpl(isolate, *backing_store, remove_index);
cbruni's avatar
cbruni committed
2441
    if (remove_position == AT_START) {
2442 2443
      Subclass::MoveElements(isolate, receiver, backing_store, 0, 1, new_length,
                             0, 0);
cbruni's avatar
cbruni committed
2444
    }
2445
    Subclass::SetLengthImpl(isolate, receiver, new_length, backing_store);
2446

2447
    if (IsHoleyElementsKind(kind) && result->IsTheHole(isolate)) {
2448
      return isolate->factory()->undefined_value();
cbruni's avatar
cbruni committed
2449 2450 2451 2452 2453 2454 2455
    }
    return result;
  }

  static uint32_t AddArguments(Handle<JSArray> receiver,
                               Handle<FixedArrayBase> backing_store,
                               Arguments* args, uint32_t add_size,
2456
                               Where add_position) {
jgruber's avatar
jgruber committed
2457
    uint32_t length = Smi::ToInt(receiver->length());
2458
    DCHECK_LT(0, add_size);
cbruni's avatar
cbruni committed
2459 2460 2461 2462 2463 2464
    uint32_t elms_len = backing_store->length();
    // Check we do not overflow the new_length.
    DCHECK(add_size <= static_cast<uint32_t>(Smi::kMaxValue - length));
    uint32_t new_length = length + add_size;

    if (new_length > elms_len) {
2465
      // New backing storage is needed.
cbruni's avatar
cbruni committed
2466 2467
      uint32_t capacity = JSObject::NewElementsCapacity(new_length);
      // If we add arguments to the start we have to shift the existing objects.
2468
      int copy_dst_index = add_position == AT_START ? add_size : 0;
cbruni's avatar
cbruni committed
2469
      // Copy over all objects to a new backing_store.
2470
      backing_store = Subclass::ConvertElementsWithCapacity(
cbruni's avatar
cbruni committed
2471 2472 2473
          receiver, backing_store, KindTraits::Kind, capacity, 0,
          copy_dst_index, ElementsAccessor::kCopyToEndAndInitializeToHole);
      receiver->set_elements(*backing_store);
2474
    } else if (add_position == AT_START) {
cbruni's avatar
cbruni committed
2475 2476 2477
      // If the backing store has enough capacity and we add elements to the
      // start we have to shift the existing objects.
      Isolate* isolate = receiver->GetIsolate();
2478 2479
      Subclass::MoveElements(isolate, receiver, backing_store, add_size, 0,
                             length, 0, 0);
cbruni's avatar
cbruni committed
2480
    }
2481

2482
    int insertion_index = add_position == AT_START ? 0 : length;
cbruni's avatar
cbruni committed
2483
    // Copy the arguments to the start.
2484
    Subclass::CopyArguments(args, backing_store, add_size, 1, insertion_index);
cbruni's avatar
cbruni committed
2485 2486 2487 2488 2489 2490 2491 2492 2493 2494
    // Set the length.
    receiver->set_length(Smi::FromInt(new_length));
    return new_length;
  }

  static void CopyArguments(Arguments* args, Handle<FixedArrayBase> dst_store,
                            uint32_t copy_size, uint32_t src_index,
                            uint32_t dst_index) {
    // Add the provided values.
    DisallowHeapAllocation no_gc;
2495
    FixedArrayBase raw_backing_store = *dst_store;
cbruni's avatar
cbruni committed
2496 2497
    WriteBarrierMode mode = raw_backing_store->GetWriteBarrierMode(no_gc);
    for (uint32_t i = 0; i < copy_size; i++) {
2498
      Object argument = (*args)[src_index + i];
2499
      DCHECK(!argument->IsTheHole());
2500
      Subclass::SetImpl(raw_backing_store, dst_index + i, argument, mode);
2501 2502
    }
  }
2503 2504
};

2505
template <typename Subclass, typename KindTraits>
2506
class FastSmiOrObjectElementsAccessor
2507
    : public FastElementsAccessor<Subclass, KindTraits> {
2508 2509
 public:
  explicit FastSmiOrObjectElementsAccessor(const char* name)
2510
      : FastElementsAccessor<Subclass, KindTraits>(name) {}
2511

2512
  static inline void SetImpl(Handle<JSObject> holder, uint32_t entry,
2513
                             Object value) {
2514 2515 2516
    SetImpl(holder->elements(), entry, value);
  }

2517
  static inline void SetImpl(FixedArrayBase backing_store, uint32_t entry,
2518
                             Object value) {
2519 2520 2521
    FixedArray::cast(backing_store)->set(entry, value);
  }

2522
  static inline void SetImpl(FixedArrayBase backing_store, uint32_t entry,
2523
                             Object value, WriteBarrierMode mode) {
2524 2525 2526
    FixedArray::cast(backing_store)->set(entry, value, mode);
  }

2527
  static Object GetRaw(FixedArray backing_store, uint32_t entry) {
2528
    uint32_t index = Subclass::GetIndexForEntryImpl(backing_store, entry);
2529 2530 2531
    return backing_store->get(index);
  }

2532 2533 2534 2535 2536
  // NOTE: this method violates the handlified function signature convention:
  // raw pointer parameters in the function that allocates.
  // See ElementsAccessor::CopyElements() for details.
  // This method could actually allocate if copying from double elements to
  // object elements.
2537 2538
  static void CopyElementsImpl(Isolate* isolate, FixedArrayBase from,
                               uint32_t from_start, FixedArrayBase to,
2539 2540
                               ElementsKind from_kind, uint32_t to_start,
                               int packed_size, int copy_size) {
2541
    DisallowHeapAllocation no_gc;
2542 2543
    ElementsKind to_kind = KindTraits::Kind;
    switch (from_kind) {
2544 2545 2546 2547
      case PACKED_SMI_ELEMENTS:
      case HOLEY_SMI_ELEMENTS:
      case PACKED_ELEMENTS:
      case HOLEY_ELEMENTS:
2548 2549
        CopyObjectToObjectElements(isolate, from, from_kind, from_start, to,
                                   to_kind, to_start, copy_size);
2550
        break;
2551 2552
      case PACKED_DOUBLE_ELEMENTS:
      case HOLEY_DOUBLE_ELEMENTS: {
2553
        AllowHeapAllocation allow_allocation;
2554
        DCHECK(IsObjectElementsKind(to_kind));
2555 2556
        CopyDoubleToObjectElements(isolate, from, from_start, to, to_start,
                                   copy_size);
2557
        break;
2558
      }
2559
      case DICTIONARY_ELEMENTS:
2560 2561
        CopyDictionaryToObjectElements(isolate, from, from_start, to, to_kind,
                                       to_start, copy_size);
2562
        break;
2563 2564
      case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
      case SLOW_SLOPPY_ARGUMENTS_ELEMENTS:
2565 2566
      case FAST_STRING_WRAPPER_ELEMENTS:
      case SLOW_STRING_WRAPPER_ELEMENTS:
2567 2568
#define TYPED_ARRAY_CASE(Type, type, TYPE, ctype) case TYPE##_ELEMENTS:
        TYPED_ARRAYS(TYPED_ARRAY_CASE)
2569
#undef TYPED_ARRAY_CASE
2570 2571 2572 2573 2574 2575
      // This function is currently only used for JSArrays with non-zero
      // length.
      UNREACHABLE();
      break;
      case NO_ELEMENTS:
        break;  // Nothing to do.
2576 2577
    }
  }
2578

2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597
  static Maybe<bool> CollectValuesOrEntriesImpl(
      Isolate* isolate, Handle<JSObject> object,
      Handle<FixedArray> values_or_entries, bool get_entries, int* nof_items,
      PropertyFilter filter) {
    int count = 0;
    if (get_entries) {
      // Collecting entries needs to allocate, so this code must be handlified.
      Handle<FixedArray> elements(FixedArray::cast(object->elements()),
                                  isolate);
      uint32_t length = elements->length();
      for (uint32_t index = 0; index < length; ++index) {
        if (!Subclass::HasEntryImpl(isolate, *elements, index)) continue;
        Handle<Object> value = Subclass::GetImpl(isolate, *elements, index);
        value = MakeEntryPair(isolate, index, value);
        values_or_entries->set(count++, *value);
      }
    } else {
      // No allocations here, so we can avoid handlification overhead.
      DisallowHeapAllocation no_gc;
2598
      FixedArray elements = FixedArray::cast(object->elements());
2599 2600 2601
      uint32_t length = elements->length();
      for (uint32_t index = 0; index < length; ++index) {
        if (!Subclass::HasEntryImpl(isolate, elements, index)) continue;
2602
        Object value = GetRaw(elements, index);
2603 2604 2605 2606 2607 2608 2609
        values_or_entries->set(count++, value);
      }
    }
    *nof_items = count;
    return Just(true);
  }

2610 2611 2612 2613 2614 2615
  static Maybe<int64_t> IndexOfValueImpl(Isolate* isolate,
                                         Handle<JSObject> receiver,
                                         Handle<Object> search_value,
                                         uint32_t start_from, uint32_t length) {
    DCHECK(JSObject::PrototypeHasNoElements(isolate, *receiver));
    DisallowHeapAllocation no_gc;
2616
    FixedArrayBase elements_base = receiver->elements();
2617
    Object value = *search_value;
2618 2619 2620 2621 2622 2623

    if (start_from >= length) return Just<int64_t>(-1);

    length = std::min(static_cast<uint32_t>(elements_base->length()), length);

    // Only FAST_{,HOLEY_}ELEMENTS can store non-numbers.
2624
    if (!value->IsNumber() && !IsObjectElementsKind(Subclass::kind())) {
2625 2626 2627 2628 2629
      return Just<int64_t>(-1);
    }
    // NaN can never be found by strict equality.
    if (value->IsNaN()) return Just<int64_t>(-1);

2630 2631 2632 2633
    // k can be greater than receiver->length() below, but it is bounded by
    // elements_base->length() so we never read out of bounds. This means that
    // elements->get(k) can return the hole, for which the StrictEquals will
    // always fail.
2634
    FixedArray elements = FixedArray::cast(receiver->elements());
2635 2636 2637 2638 2639
    for (uint32_t k = start_from; k < length; ++k) {
      if (value->StrictEquals(elements->get(k))) return Just<int64_t>(k);
    }
    return Just<int64_t>(-1);
  }
2640
};
2641

2642 2643
class FastPackedSmiElementsAccessor
    : public FastSmiOrObjectElementsAccessor<
2644 2645
          FastPackedSmiElementsAccessor,
          ElementsKindTraits<PACKED_SMI_ELEMENTS>> {
2646 2647 2648
 public:
  explicit FastPackedSmiElementsAccessor(const char* name)
      : FastSmiOrObjectElementsAccessor<
2649 2650
            FastPackedSmiElementsAccessor,
            ElementsKindTraits<PACKED_SMI_ELEMENTS>>(name) {}
2651 2652 2653 2654
};

class FastHoleySmiElementsAccessor
    : public FastSmiOrObjectElementsAccessor<
2655 2656
          FastHoleySmiElementsAccessor,
          ElementsKindTraits<HOLEY_SMI_ELEMENTS>> {
2657 2658
 public:
  explicit FastHoleySmiElementsAccessor(const char* name)
2659 2660 2661
      : FastSmiOrObjectElementsAccessor<FastHoleySmiElementsAccessor,
                                        ElementsKindTraits<HOLEY_SMI_ELEMENTS>>(
            name) {}
2662 2663
};

2664 2665
class FastPackedObjectElementsAccessor
    : public FastSmiOrObjectElementsAccessor<
2666 2667
          FastPackedObjectElementsAccessor,
          ElementsKindTraits<PACKED_ELEMENTS>> {
2668 2669
 public:
  explicit FastPackedObjectElementsAccessor(const char* name)
2670 2671 2672
      : FastSmiOrObjectElementsAccessor<FastPackedObjectElementsAccessor,
                                        ElementsKindTraits<PACKED_ELEMENTS>>(
            name) {}
2673 2674 2675 2676
};

class FastHoleyObjectElementsAccessor
    : public FastSmiOrObjectElementsAccessor<
2677
          FastHoleyObjectElementsAccessor, ElementsKindTraits<HOLEY_ELEMENTS>> {
2678 2679
 public:
  explicit FastHoleyObjectElementsAccessor(const char* name)
2680 2681 2682
      : FastSmiOrObjectElementsAccessor<FastHoleyObjectElementsAccessor,
                                        ElementsKindTraits<HOLEY_ELEMENTS>>(
            name) {}
2683 2684
};

2685
template <typename Subclass, typename KindTraits>
2686
class FastDoubleElementsAccessor
2687
    : public FastElementsAccessor<Subclass, KindTraits> {
2688 2689
 public:
  explicit FastDoubleElementsAccessor(const char* name)
2690
      : FastElementsAccessor<Subclass, KindTraits>(name) {}
2691

2692
  static Handle<Object> GetImpl(Isolate* isolate, FixedArrayBase backing_store,
2693
                                uint32_t entry) {
2694 2695 2696 2697 2698
    return FixedDoubleArray::get(FixedDoubleArray::cast(backing_store), entry,
                                 isolate);
  }

  static inline void SetImpl(Handle<JSObject> holder, uint32_t entry,
2699
                             Object value) {
2700 2701 2702
    SetImpl(holder->elements(), entry, value);
  }

2703
  static inline void SetImpl(FixedArrayBase backing_store, uint32_t entry,
2704
                             Object value) {
2705 2706 2707
    FixedDoubleArray::cast(backing_store)->set(entry, value->Number());
  }

2708
  static inline void SetImpl(FixedArrayBase backing_store, uint32_t entry,
2709
                             Object value, WriteBarrierMode mode) {
2710 2711 2712
    FixedDoubleArray::cast(backing_store)->set(entry, value->Number());
  }

2713 2714
  static void CopyElementsImpl(Isolate* isolate, FixedArrayBase from,
                               uint32_t from_start, FixedArrayBase to,
2715 2716
                               ElementsKind from_kind, uint32_t to_start,
                               int packed_size, int copy_size) {
2717
    DisallowHeapAllocation no_allocation;
2718
    switch (from_kind) {
2719
      case PACKED_SMI_ELEMENTS:
2720
        CopyPackedSmiToDoubleElements(from, from_start, to, to_start,
2721
                                      packed_size, copy_size);
2722
        break;
2723
      case HOLEY_SMI_ELEMENTS:
2724
        CopySmiToDoubleElements(from, from_start, to, to_start, copy_size);
2725
        break;
2726 2727
      case PACKED_DOUBLE_ELEMENTS:
      case HOLEY_DOUBLE_ELEMENTS:
2728
        CopyDoubleToDoubleElements(from, from_start, to, to_start, copy_size);
2729
        break;
2730 2731
      case PACKED_ELEMENTS:
      case HOLEY_ELEMENTS:
2732
        CopyObjectToDoubleElements(from, from_start, to, to_start, copy_size);
2733 2734
        break;
      case DICTIONARY_ELEMENTS:
2735
        CopyDictionaryToDoubleElements(isolate, from, from_start, to, to_start,
2736
                                       copy_size);
2737
        break;
2738 2739
      case FAST_SLOPPY_ARGUMENTS_ELEMENTS:
      case SLOW_SLOPPY_ARGUMENTS_ELEMENTS:
2740 2741 2742
      case FAST_STRING_WRAPPER_ELEMENTS:
      case SLOW_STRING_WRAPPER_ELEMENTS:
      case NO_ELEMENTS:
2743 2744
#define TYPED_ARRAY_CASE(Type, type, TYPE, ctype) case TYPE##_ELEMENTS:
        TYPED_ARRAYS(TYPED_ARRAY_CASE)
2745
#undef TYPED_ARRAY_CASE
2746 2747 2748 2749
      // This function is currently only used for JSArrays with non-zero
      // length.
      UNREACHABLE();
      break;
2750 2751
    }
  }
2752

2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772
  static Maybe<bool> CollectValuesOrEntriesImpl(
      Isolate* isolate, Handle<JSObject> object,
      Handle<FixedArray> values_or_entries, bool get_entries, int* nof_items,
      PropertyFilter filter) {
    Handle<FixedDoubleArray> elements(
        FixedDoubleArray::cast(object->elements()), isolate);
    int count = 0;
    uint32_t length = elements->length();
    for (uint32_t index = 0; index < length; ++index) {
      if (!Subclass::HasEntryImpl(isolate, *elements, index)) continue;
      Handle<Object> value = Subclass::GetImpl(isolate, *elements, index);
      if (get_entries) {
        value = MakeEntryPair(isolate, index, value);
      }
      values_or_entries->set(count++, *value);
    }
    *nof_items = count;
    return Just(true);
  }

2773 2774 2775 2776 2777 2778
  static Maybe<int64_t> IndexOfValueImpl(Isolate* isolate,
                                         Handle<JSObject> receiver,
                                         Handle<Object> search_value,
                                         uint32_t start_from, uint32_t length) {
    DCHECK(JSObject::PrototypeHasNoElements(isolate, *receiver));
    DisallowHeapAllocation no_gc;
2779
    FixedArrayBase elements_base = receiver->elements();
2780
    Object value = *search_value;
2781 2782 2783

    length = std::min(static_cast<uint32_t>(elements_base->length()), length);

2784 2785
    if (start_from >= length) return Just<int64_t>(-1);

2786 2787 2788 2789 2790 2791 2792
    if (!value->IsNumber()) {
      return Just<int64_t>(-1);
    }
    if (value->IsNaN()) {
      return Just<int64_t>(-1);
    }
    double numeric_search_value = value->Number();
2793
    FixedDoubleArray elements = FixedDoubleArray::cast(receiver->elements());
2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804

    for (uint32_t k = start_from; k < length; ++k) {
      if (elements->is_the_hole(k)) {
        continue;
      }
      if (elements->get_scalar(k) == numeric_search_value) {
        return Just<int64_t>(k);
      }
    }
    return Just<int64_t>(-1);
  }
2805
};
2806

2807 2808
class FastPackedDoubleElementsAccessor
    : public FastDoubleElementsAccessor<
2809 2810
          FastPackedDoubleElementsAccessor,
          ElementsKindTraits<PACKED_DOUBLE_ELEMENTS>> {
2811 2812
 public:
  explicit FastPackedDoubleElementsAccessor(const char* name)
2813 2814 2815
      : FastDoubleElementsAccessor<FastPackedDoubleElementsAccessor,
                                   ElementsKindTraits<PACKED_DOUBLE_ELEMENTS>>(
            name) {}
2816 2817 2818 2819
};

class FastHoleyDoubleElementsAccessor
    : public FastDoubleElementsAccessor<
2820 2821
          FastHoleyDoubleElementsAccessor,
          ElementsKindTraits<HOLEY_DOUBLE_ELEMENTS>> {
2822 2823
 public:
  explicit FastHoleyDoubleElementsAccessor(const char* name)
2824 2825 2826
      : FastDoubleElementsAccessor<FastHoleyDoubleElementsAccessor,
                                   ElementsKindTraits<HOLEY_DOUBLE_ELEMENTS>>(
            name) {}
2827 2828 2829 2830
};


// Super class for all external element arrays.
2831
template <ElementsKind Kind, typename ctype>
2832
class TypedElementsAccessor
2833 2834
    : public ElementsAccessorBase<TypedElementsAccessor<Kind, ctype>,
                                  ElementsKindTraits<Kind>> {
2835
 public:
2836
  explicit TypedElementsAccessor(const char* name)
2837
      : ElementsAccessorBase<AccessorClass,
2838
                             ElementsKindTraits<Kind> >(name) {}
2839

2840
  typedef typename ElementsKindTraits<Kind>::BackingStore BackingStore;
2841
  typedef TypedElementsAccessor<Kind, ctype> AccessorClass;
2842

2843
  static inline void SetImpl(Handle<JSObject> holder, uint32_t entry,
2844
                             Object value) {
2845 2846 2847
    SetImpl(holder->elements(), entry, value);
  }

2848
  static inline void SetImpl(FixedArrayBase backing_store, uint32_t entry,
2849
                             Object value) {
2850 2851 2852
    BackingStore::cast(backing_store)->SetValue(entry, value);
  }

2853
  static inline void SetImpl(FixedArrayBase backing_store, uint32_t entry,
2854
                             Object value, WriteBarrierMode mode) {
2855 2856 2857
    BackingStore::cast(backing_store)->SetValue(entry, value);
  }

2858
  static Handle<Object> GetImpl(Isolate* isolate, FixedArrayBase backing_store,
2859
                                uint32_t entry) {
2860
    return BackingStore::get(isolate, BackingStore::cast(backing_store), entry);
2861 2862
  }

2863
  static PropertyDetails GetDetailsImpl(JSObject holder, uint32_t entry) {
2864
    return PropertyDetails(kData, DONT_DELETE, PropertyCellType::kNoCell);
2865
  }
2866

2867
  static PropertyDetails GetDetailsImpl(FixedArrayBase backing_store,
2868
                                        uint32_t entry) {
2869
    return PropertyDetails(kData, DONT_DELETE, PropertyCellType::kNoCell);
2870 2871
  }

2872
  static bool HasElementImpl(Isolate* isolate, JSObject holder, uint32_t index,
2873
                             FixedArrayBase backing_store,
2874
                             PropertyFilter filter) {
2875
    return index < AccessorClass::GetCapacityImpl(holder, backing_store);
2876 2877
  }

2878
  static bool HasAccessorsImpl(JSObject holder, FixedArrayBase backing_store) {
2879 2880 2881
    return false;
  }

2882 2883
  static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array,
                            uint32_t length,
2884
                            Handle<FixedArrayBase> backing_store) {
2885 2886 2887 2888
    // External arrays do not support changing their length.
    UNREACHABLE();
  }

2889
  static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) {
2890
    UNREACHABLE();
2891
  }
2892

2893
  static uint32_t GetIndexForEntryImpl(FixedArrayBase backing_store,
2894 2895 2896 2897
                                       uint32_t entry) {
    return entry;
  }

2898
  static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject holder,
2899
                                       FixedArrayBase backing_store,
2900
                                       uint32_t index, PropertyFilter filter) {
2901 2902
    return index < AccessorClass::GetCapacityImpl(holder, backing_store)
               ? index
2903
               : kMaxUInt32;
2904
  }
2905

2906
  static bool WasDetached(JSObject holder) {
2907
    JSArrayBufferView view = JSArrayBufferView::cast(holder);
2908
    return view->WasDetached();
2909 2910
  }

2911
  static uint32_t GetCapacityImpl(JSObject holder,
2912
                                  FixedArrayBase backing_store) {
2913
    if (WasDetached(holder)) return 0;
2914 2915
    return backing_store->length();
  }
2916

2917
  static uint32_t NumberOfElementsImpl(JSObject receiver,
2918
                                       FixedArrayBase backing_store) {
2919 2920 2921
    return AccessorClass::GetCapacityImpl(receiver, backing_store);
  }

2922 2923 2924
  static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver,
                                              KeyAccumulator* accumulator,
                                              AddKeyConversion convert) {
2925
    Isolate* isolate = receiver->GetIsolate();
2926
    Handle<FixedArrayBase> elements(receiver->elements(), isolate);
2927 2928
    uint32_t length = AccessorClass::GetCapacityImpl(*receiver, *elements);
    for (uint32_t i = 0; i < length; i++) {
2929
      Handle<Object> value = AccessorClass::GetImpl(isolate, *elements, i);
2930 2931 2932
      accumulator->AddKey(value, convert);
    }
  }
2933 2934 2935 2936 2937 2938 2939

  static Maybe<bool> CollectValuesOrEntriesImpl(
      Isolate* isolate, Handle<JSObject> object,
      Handle<FixedArray> values_or_entries, bool get_entries, int* nof_items,
      PropertyFilter filter) {
    int count = 0;
    if ((filter & ONLY_CONFIGURABLE) == 0) {
2940
      Handle<FixedArrayBase> elements(object->elements(), isolate);
2941 2942
      uint32_t length = AccessorClass::GetCapacityImpl(*object, *elements);
      for (uint32_t index = 0; index < length; ++index) {
2943 2944
        Handle<Object> value =
            AccessorClass::GetImpl(isolate, *elements, index);
2945 2946 2947 2948 2949 2950 2951 2952 2953
        if (get_entries) {
          value = MakeEntryPair(isolate, index, value);
        }
        values_or_entries->set(count++, *value);
      }
    }
    *nof_items = count;
    return Just(true);
  }
2954

2955 2956
  static Object FillImpl(Handle<JSObject> receiver, Handle<Object> obj_value,
                         uint32_t start, uint32_t end) {
2957
    Handle<JSTypedArray> array = Handle<JSTypedArray>::cast(receiver);
2958
    DCHECK(!array->WasDetached());
2959
    DCHECK(obj_value->IsNumeric());
2960

2961
    ctype value = BackingStore::FromHandle(obj_value);
2962 2963

    // Ensure indexes are within array bounds
2964 2965 2966
    CHECK_LE(0, start);
    CHECK_LE(start, end);
    CHECK_LE(end, array->length_value());
2967 2968

    DisallowHeapAllocation no_gc;
2969
    BackingStore elements = BackingStore::cast(receiver->elements());
2970 2971 2972 2973 2974
    ctype* data = static_cast<ctype*>(elements->DataPtr());
    std::fill(data + start, data + end, value);
    return *array;
  }

2975 2976 2977 2978 2979
  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
                                       Handle<JSObject> receiver,
                                       Handle<Object> value,
                                       uint32_t start_from, uint32_t length) {
    DisallowHeapAllocation no_gc;
2980

2981
    // TODO(caitp): return Just(false) here when implementing strict throwing on
2982 2983
    // detached views.
    if (WasDetached(*receiver)) {
2984 2985 2986
      return Just(value->IsUndefined(isolate) && length > start_from);
    }

2987
    BackingStore elements = BackingStore::cast(receiver->elements());
2988 2989 2990 2991
    if (value->IsUndefined(isolate) &&
        length > static_cast<uint32_t>(elements->length())) {
      return Just(true);
    }
2992
    ctype typed_search_value;
2993 2994 2995 2996 2997 2998
    // Prototype has no elements, and not searching for the hole --- limit
    // search to backing store length.
    if (static_cast<uint32_t>(elements->length()) < length) {
      length = elements->length();
    }

2999 3000 3001 3002 3003
    if (Kind == BIGINT64_ELEMENTS || Kind == BIGUINT64_ELEMENTS) {
      if (!value->IsBigInt()) return Just(false);
      bool lossless;
      typed_search_value = BackingStore::FromHandle(value, &lossless);
      if (!lossless) return Just(false);
3004
    } else {
3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026
      if (!value->IsNumber()) return Just(false);
      double search_value = value->Number();
      if (!std::isfinite(search_value)) {
        // Integral types cannot represent +Inf or NaN.
        if (Kind < FLOAT32_ELEMENTS || Kind > FLOAT64_ELEMENTS) {
          return Just(false);
        }
        if (std::isnan(search_value)) {
          for (uint32_t k = start_from; k < length; ++k) {
            double element_k = elements->get_scalar(k);
            if (std::isnan(element_k)) return Just(true);
          }
          return Just(false);
        }
      } else if (search_value < std::numeric_limits<ctype>::lowest() ||
                 search_value > std::numeric_limits<ctype>::max()) {
        // Return false if value can't be represented in this space.
        return Just(false);
      }
      typed_search_value = static_cast<ctype>(search_value);
      if (static_cast<double>(typed_search_value) != search_value) {
        return Just(false);  // Loss of precision.
3027 3028
      }
    }
3029 3030 3031 3032 3033 3034

    for (uint32_t k = start_from; k < length; ++k) {
      ctype element_k = elements->get_scalar(k);
      if (element_k == typed_search_value) return Just(true);
    }
    return Just(false);
3035
  }
3036 3037 3038 3039 3040 3041 3042

  static Maybe<int64_t> IndexOfValueImpl(Isolate* isolate,
                                         Handle<JSObject> receiver,
                                         Handle<Object> value,
                                         uint32_t start_from, uint32_t length) {
    DisallowHeapAllocation no_gc;

3043
    if (WasDetached(*receiver)) return Just<int64_t>(-1);
3044

3045
    BackingStore elements = BackingStore::cast(receiver->elements());
3046
    ctype typed_search_value;
3047

3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066
    if (Kind == BIGINT64_ELEMENTS || Kind == BIGUINT64_ELEMENTS) {
      if (!value->IsBigInt()) return Just<int64_t>(-1);
      bool lossless;
      typed_search_value = BackingStore::FromHandle(value, &lossless);
      if (!lossless) return Just<int64_t>(-1);
    } else {
      if (!value->IsNumber()) return Just<int64_t>(-1);
      double search_value = value->Number();
      if (!std::isfinite(search_value)) {
        // Integral types cannot represent +Inf or NaN.
        if (Kind < FLOAT32_ELEMENTS || Kind > FLOAT64_ELEMENTS) {
          return Just<int64_t>(-1);
        }
        if (std::isnan(search_value)) {
          return Just<int64_t>(-1);
        }
      } else if (search_value < std::numeric_limits<ctype>::lowest() ||
                 search_value > std::numeric_limits<ctype>::max()) {
        // Return false if value can't be represented in this ElementsKind.
3067 3068
        return Just<int64_t>(-1);
      }
3069 3070 3071 3072
      typed_search_value = static_cast<ctype>(search_value);
      if (static_cast<double>(typed_search_value) != search_value) {
        return Just<int64_t>(-1);  // Loss of precision.
      }
3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086
    }

    // Prototype has no elements, and not searching for the hole --- limit
    // search to backing store length.
    if (static_cast<uint32_t>(elements->length()) < length) {
      length = elements->length();
    }

    for (uint32_t k = start_from; k < length; ++k) {
      ctype element_k = elements->get_scalar(k);
      if (element_k == typed_search_value) return Just<int64_t>(k);
    }
    return Just<int64_t>(-1);
  }
3087

3088
  static Maybe<int64_t> LastIndexOfValueImpl(Handle<JSObject> receiver,
3089 3090 3091
                                             Handle<Object> value,
                                             uint32_t start_from) {
    DisallowHeapAllocation no_gc;
3092
    DCHECK(!WasDetached(*receiver));
3093

3094
    BackingStore elements = BackingStore::cast(receiver->elements());
3095
    ctype typed_search_value;
3096

3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115
    if (Kind == BIGINT64_ELEMENTS || Kind == BIGUINT64_ELEMENTS) {
      if (!value->IsBigInt()) return Just<int64_t>(-1);
      bool lossless;
      typed_search_value = BackingStore::FromHandle(value, &lossless);
      if (!lossless) return Just<int64_t>(-1);
    } else {
      if (!value->IsNumber()) return Just<int64_t>(-1);
      double search_value = value->Number();
      if (!std::isfinite(search_value)) {
        if (std::is_integral<ctype>::value) {
          // Integral types cannot represent +Inf or NaN.
          return Just<int64_t>(-1);
        } else if (std::isnan(search_value)) {
          // Strict Equality Comparison of NaN is always false.
          return Just<int64_t>(-1);
        }
      } else if (search_value < std::numeric_limits<ctype>::lowest() ||
                 search_value > std::numeric_limits<ctype>::max()) {
        // Return -1 if value can't be represented in this ElementsKind.
3116 3117
        return Just<int64_t>(-1);
      }
3118 3119 3120 3121
      typed_search_value = static_cast<ctype>(search_value);
      if (static_cast<double>(typed_search_value) != search_value) {
        return Just<int64_t>(-1);  // Loss of precision.
      }
3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132
    }

    DCHECK_LT(start_from, elements->length());

    uint32_t k = start_from;
    do {
      ctype element_k = elements->get_scalar(k);
      if (element_k == typed_search_value) return Just<int64_t>(k);
    } while (k-- != 0);
    return Just<int64_t>(-1);
  }
3133

3134
  static void ReverseImpl(JSObject receiver) {
3135
    DisallowHeapAllocation no_gc;
3136
    DCHECK(!WasDetached(receiver));
3137

3138
    BackingStore elements = BackingStore::cast(receiver->elements());
3139 3140 3141 3142 3143 3144 3145

    uint32_t len = elements->length();
    if (len == 0) return;

    ctype* data = static_cast<ctype*>(elements->DataPtr());
    std::reverse(data, data + len);
  }
3146

3147 3148 3149
  static Handle<FixedArray> CreateListFromArrayLikeImpl(Isolate* isolate,
                                                        Handle<JSObject> object,
                                                        uint32_t length) {
3150
    DCHECK(!WasDetached(*object));
3151 3152
    DCHECK(object->IsJSTypedArray());
    Handle<FixedArray> result = isolate->factory()->NewFixedArray(length);
3153 3154
    Handle<BackingStore> elements(BackingStore::cast(object->elements()),
                                  isolate);
3155 3156 3157 3158 3159 3160 3161
    for (uint32_t i = 0; i < length; i++) {
      Handle<Object> value = AccessorClass::GetImpl(isolate, *elements, i);
      result->set(i, *value);
    }
    return result;
  }

3162 3163
  static void CopyTypedArrayElementsSliceImpl(JSTypedArray source,
                                              JSTypedArray destination,
3164 3165 3166
                                              size_t start, size_t end) {
    DisallowHeapAllocation no_gc;
    DCHECK_EQ(destination->GetElementsKind(), AccessorClass::kind());
3167 3168
    CHECK(!source->WasDetached());
    CHECK(!destination->WasDetached());
3169
    DCHECK_LE(start, end);
3170
    DCHECK_LE(end, source->length_value());
3171

3172 3173
    size_t count = end - start;
    DCHECK_LE(count, destination->length_value());
3174

3175
    FixedTypedArrayBase src_elements =
3176
        FixedTypedArrayBase::cast(source->elements());
3177
    BackingStore dest_elements = BackingStore::cast(destination->elements());
3178

3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191
    size_t element_size = source->element_size();
    uint8_t* source_data =
        static_cast<uint8_t*>(src_elements->DataPtr()) + start * element_size;

    // Fast path for the same type result array
    if (source->type() == destination->type()) {
      uint8_t* dest_data = static_cast<uint8_t*>(dest_elements->DataPtr());

      // The spec defines the copy-step iteratively, which means that we
      // cannot use memcpy if the buffer is shared.
      uint8_t* end_ptr = source_data + count * element_size;
      while (source_data < end_ptr) {
        *dest_data++ = *source_data++;
3192
      }
3193
      return;
3194 3195
    }

3196
    switch (source->GetElementsKind()) {
3197
#define TYPED_ARRAY_CASE(Type, type, TYPE, ctype)                           \
3198 3199 3200 3201 3202 3203 3204 3205 3206
  case TYPE##_ELEMENTS:                                                     \
    CopyBetweenBackingStores<Type##ArrayTraits>(source_data, dest_elements, \
                                                count, 0);                  \
    break;
      TYPED_ARRAYS(TYPED_ARRAY_CASE)
#undef TYPED_ARRAY_CASE
      default:
        UNREACHABLE();
        break;
3207 3208
    }
  }
3209 3210 3211 3212 3213 3214 3215 3216

  static bool HasSimpleRepresentation(InstanceType type) {
    return !(type == FIXED_FLOAT32_ARRAY_TYPE ||
             type == FIXED_FLOAT64_ARRAY_TYPE ||
             type == FIXED_UINT8_CLAMPED_ARRAY_TYPE);
  }

  template <typename SourceTraits>
3217 3218
  static void CopyBetweenBackingStores(void* source_data_ptr, BackingStore dest,
                                       size_t length, uint32_t offset) {
3219
    DisallowHeapAllocation no_gc;
3220
    for (uint32_t i = 0; i < length; i++) {
3221 3222 3223 3224 3225
      // We use scalar accessors to avoid boxing/unboxing, so there are no
      // allocations.
      typename SourceTraits::ElementType elem =
          FixedTypedArray<SourceTraits>::get_scalar_from_data_ptr(
              source_data_ptr, i);
3226
      dest->set(offset + i, dest->from(elem));
3227 3228 3229
    }
  }

3230 3231
  static void CopyElementsFromTypedArray(JSTypedArray source,
                                         JSTypedArray destination,
3232
                                         size_t length, uint32_t offset) {
3233
    // The source is a typed array, so we know we don't need to do ToNumber
3234
    // side-effects, as the source elements will always be a number.
3235 3236
    DisallowHeapAllocation no_gc;

3237 3238
    CHECK(!source->WasDetached());
    CHECK(!destination->WasDetached());
3239

3240
    FixedTypedArrayBase source_elements =
3241
        FixedTypedArrayBase::cast(source->elements());
3242
    BackingStore destination_elements =
3243
        BackingStore::cast(destination->elements());
3244

3245
    DCHECK_LE(offset, destination->length_value());
3246
    DCHECK_LE(length, destination->length_value() - offset);
3247
    DCHECK(source->length()->IsSmi());
3248
    DCHECK_LE(length, source->length_value());
3249 3250 3251 3252 3253 3254

    InstanceType source_type = source_elements->map()->instance_type();
    InstanceType destination_type =
        destination_elements->map()->instance_type();

    bool same_type = source_type == destination_type;
3255
    bool same_size = source->element_size() == destination->element_size();
3256 3257 3258
    bool both_are_simple = HasSimpleRepresentation(source_type) &&
                           HasSimpleRepresentation(destination_type);

3259 3260
    uint8_t* source_data = static_cast<uint8_t*>(source_elements->DataPtr());
    uint8_t* dest_data = static_cast<uint8_t*>(destination_elements->DataPtr());
3261 3262
    size_t source_byte_length = source->byte_length();
    size_t dest_byte_length = destination->byte_length();
3263

3264 3265 3266 3267 3268
    // We can simply copy the backing store if the types are the same, or if
    // we are converting e.g. Uint8 <-> Int8, as the binary representation
    // will be the same. This is not the case for floats or clamped Uint8,
    // which have special conversion operations.
    if (same_type || (same_size && both_are_simple)) {
3269
      size_t element_size = source->element_size();
3270 3271
      std::memmove(dest_data + offset * element_size, source_data,
                   length * element_size);
3272
    } else {
3273
      std::unique_ptr<uint8_t[]> cloned_source_elements;
3274 3275 3276 3277

      // If the typedarrays are overlapped, clone the source.
      if (dest_data + dest_byte_length > source_data &&
          source_data + source_byte_length > dest_data) {
3278 3279 3280 3281
        cloned_source_elements.reset(new uint8_t[source_byte_length]);
        std::memcpy(cloned_source_elements.get(), source_data,
                    source_byte_length);
        source_data = cloned_source_elements.get();
3282 3283
      }

3284
      switch (source->GetElementsKind()) {
3285
#define TYPED_ARRAY_CASE(Type, type, TYPE, ctype)           \
3286 3287 3288
  case TYPE##_ELEMENTS:                                     \
    CopyBetweenBackingStores<Type##ArrayTraits>(            \
        source_data, destination_elements, length, offset); \
3289 3290 3291 3292 3293 3294 3295 3296 3297 3298
    break;
        TYPED_ARRAYS(TYPED_ARRAY_CASE)
        default:
          UNREACHABLE();
          break;
      }
#undef TYPED_ARRAY_CASE
    }
  }

3299
  static bool HoleyPrototypeLookupRequired(Isolate* isolate, Context context,
3300
                                           JSArray source) {
3301 3302 3303
    DisallowHeapAllocation no_gc;
    DisallowJavascriptExecution no_js(isolate);

3304
#ifdef V8_ENABLE_FORCE_SLOW_PATH
3305 3306 3307
    if (isolate->force_slow_path()) return true;
#endif

3308
    Object source_proto = source->map()->prototype();
3309

3310 3311 3312 3313
    // Null prototypes are OK - we don't need to do prototype chain lookups on
    // them.
    if (source_proto->IsNull(isolate)) return false;
    if (source_proto->IsJSProxy()) return true;
3314 3315
    if (!context->native_context()->is_initial_array_prototype(
            JSObject::cast(source_proto))) {
3316 3317
      return true;
    }
3318 3319

    return !isolate->IsNoElementsProtectorIntact(context);
3320 3321
  }

3322 3323 3324
  static bool TryCopyElementsFastNumber(Context context, JSArray source,
                                        JSTypedArray destination, size_t length,
                                        uint32_t offset) {
3325
    if (Kind == BIGINT64_ELEMENTS || Kind == BIGUINT64_ELEMENTS) return false;
3326
    Isolate* isolate = source->GetIsolate();
3327
    DisallowHeapAllocation no_gc;
3328 3329
    DisallowJavascriptExecution no_js(isolate);

3330
    CHECK(!destination->WasDetached());
3331

3332 3333 3334 3335 3336 3337 3338 3339 3340 3341
    size_t current_length;
    DCHECK(source->length()->IsNumber() &&
           TryNumberToSize(source->length(), &current_length) &&
           length <= current_length);
    USE(current_length);

    size_t dest_length = destination->length_value();
    DCHECK(length + offset <= dest_length);
    USE(dest_length);

3342
    ElementsKind kind = source->GetElementsKind();
3343
    BackingStore dest = BackingStore::cast(destination->elements());
3344

3345 3346 3347 3348 3349
    // When we find the hole, we normally have to look up the element on the
    // prototype chain, which is not handled here and we return false instead.
    // When the array has the original array prototype, and that prototype has
    // not been changed in a way that would affect lookups, we can just convert
    // the hole into undefined.
3350
    if (HoleyPrototypeLookupRequired(isolate, context, source)) return false;
3351

3352
    Object undefined = ReadOnlyRoots(isolate).undefined_value();
3353 3354

    // Fastpath for packed Smi kind.
3355
    if (kind == PACKED_SMI_ELEMENTS) {
3356
      FixedArray source_store = FixedArray::cast(source->elements());
3357 3358

      for (uint32_t i = 0; i < length; i++) {
3359
        Object elem = source_store->get(i);
3360
        DCHECK(elem->IsSmi());
jgruber's avatar
jgruber committed
3361
        int int_value = Smi::ToInt(elem);
3362
        dest->set(offset + i, dest->from(int_value));
3363 3364
      }
      return true;
3365
    } else if (kind == HOLEY_SMI_ELEMENTS) {
3366
      FixedArray source_store = FixedArray::cast(source->elements());
3367 3368
      for (uint32_t i = 0; i < length; i++) {
        if (source_store->is_the_hole(isolate, i)) {
3369
          dest->SetValue(offset + i, undefined);
3370
        } else {
3371
          Object elem = source_store->get(i);
3372
          DCHECK(elem->IsSmi());
jgruber's avatar
jgruber committed
3373
          int int_value = Smi::ToInt(elem);
3374
          dest->set(offset + i, dest->from(int_value));
3375 3376 3377
        }
      }
      return true;
3378
    } else if (kind == PACKED_DOUBLE_ELEMENTS) {
3379 3380
      // Fastpath for packed double kind. We avoid boxing and then immediately
      // unboxing the double here by using get_scalar.
3381
      FixedDoubleArray source_store =
3382 3383 3384 3385 3386 3387
          FixedDoubleArray::cast(source->elements());

      for (uint32_t i = 0; i < length; i++) {
        // Use the from_double conversion for this specific TypedArray type,
        // rather than relying on C++ to convert elem.
        double elem = source_store->get_scalar(i);
3388
        dest->set(offset + i, dest->from(elem));
3389 3390
      }
      return true;
3391
    } else if (kind == HOLEY_DOUBLE_ELEMENTS) {
3392
      FixedDoubleArray source_store =
3393 3394 3395
          FixedDoubleArray::cast(source->elements());
      for (uint32_t i = 0; i < length; i++) {
        if (source_store->is_the_hole(i)) {
3396
          dest->SetValue(offset + i, undefined);
3397 3398
        } else {
          double elem = source_store->get_scalar(i);
3399
          dest->set(offset + i, dest->from(elem));
3400 3401 3402
        }
      }
      return true;
3403 3404 3405 3406
    }
    return false;
  }

3407 3408 3409
  static Object CopyElementsHandleSlow(Handle<Object> source,
                                       Handle<JSTypedArray> destination,
                                       size_t length, uint32_t offset) {
3410
    Isolate* isolate = destination->GetIsolate();
3411
    Handle<BackingStore> destination_elements(
3412
        BackingStore::cast(destination->elements()), isolate);
3413
    for (uint32_t i = 0; i < length; i++) {
3414
      LookupIterator it(isolate, source, i);
3415 3416 3417
      Handle<Object> elem;
      ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, elem,
                                         Object::GetProperty(&it));
3418 3419 3420 3421 3422
      if (Kind == BIGINT64_ELEMENTS || Kind == BIGUINT64_ELEMENTS) {
        ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, elem,
                                           BigInt::FromObject(isolate, elem));
      } else {
        ASSIGN_RETURN_FAILURE_ON_EXCEPTION(isolate, elem,
3423
                                           Object::ToNumber(isolate, elem));
3424
      }
3425

3426
      if (V8_UNLIKELY(destination->WasDetached())) {
3427
        const char* op = "set";
3428
        const MessageTemplate message = MessageTemplate::kDetachedOperation;
3429 3430 3431 3432 3433
        Handle<String> operation =
            isolate->factory()->NewStringFromAsciiChecked(op);
        THROW_NEW_ERROR_RETURN_FAILURE(isolate,
                                       NewTypeError(message, operation));
      }
3434 3435
      // The spec says we store the length, then get each element, so we don't
      // need to check changes to length.
3436
      destination_elements->SetValue(offset + i, *elem);
3437
    }
3438
    return *isolate->factory()->undefined_value();
3439 3440
  }

3441 3442 3443
  // This doesn't guarantee that the destination array will be completely
  // filled. The caller must do this by passing a source with equal length, if
  // that is required.
3444 3445 3446
  static Object CopyElementsHandleImpl(Handle<Object> source,
                                       Handle<JSObject> destination,
                                       size_t length, uint32_t offset) {
3447
    Isolate* isolate = destination->GetIsolate();
3448 3449
    Handle<JSTypedArray> destination_ta =
        Handle<JSTypedArray>::cast(destination);
3450
    DCHECK_LE(offset + length, destination_ta->length_value());
3451
    CHECK(!destination_ta->WasDetached());
3452

3453 3454
    if (length == 0) return *isolate->factory()->undefined_value();

3455 3456 3457
    // All conversions from TypedArrays can be done without allocation.
    if (source->IsJSTypedArray()) {
      Handle<JSTypedArray> source_ta = Handle<JSTypedArray>::cast(source);
3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475
      ElementsKind source_kind = source_ta->GetElementsKind();
      bool source_is_bigint =
          source_kind == BIGINT64_ELEMENTS || source_kind == BIGUINT64_ELEMENTS;
      bool target_is_bigint =
          Kind == BIGINT64_ELEMENTS || Kind == BIGUINT64_ELEMENTS;
      if (target_is_bigint) {
        if (V8_UNLIKELY(!source_is_bigint)) {
          Handle<Object> first =
              JSReceiver::GetElement(isolate, source_ta, 0).ToHandleChecked();
          THROW_NEW_ERROR_RETURN_FAILURE(
              isolate, NewTypeError(MessageTemplate::kBigIntFromObject, first));
        }
      } else {
        if (V8_UNLIKELY(source_is_bigint)) {
          THROW_NEW_ERROR_RETURN_FAILURE(
              isolate, NewTypeError(MessageTemplate::kBigIntToNumber));
        }
      }
3476 3477
      // If we have to copy more elements than we have in the source, we need to
      // do special handling and conversion; that happens in the slow case.
3478
      if (!source_ta->WasDetached() &&
3479
          length + offset <= source_ta->length_value()) {
3480 3481 3482
        CopyElementsFromTypedArray(*source_ta, *destination_ta, length, offset);
        return *isolate->factory()->undefined_value();
      }
3483 3484 3485 3486
    }

    // Fast cases for packed numbers kinds where we don't need to allocate.
    if (source->IsJSArray()) {
3487 3488 3489 3490 3491 3492 3493 3494 3495 3496 3497
      Handle<JSArray> source_js_array = Handle<JSArray>::cast(source);
      size_t current_length;
      if (source_js_array->length()->IsNumber() &&
          TryNumberToSize(source_js_array->length(), &current_length)) {
        if (length <= current_length) {
          Handle<JSArray> source_array = Handle<JSArray>::cast(source);
          if (TryCopyElementsFastNumber(isolate->context(), *source_array,
                                        *destination_ta, length, offset)) {
            return *isolate->factory()->undefined_value();
          }
        }
3498 3499 3500 3501
      }
    }
    // Final generic case that handles prototype chain lookups, getters, proxies
    // and observable side effects via valueOf, etc.
3502
    return CopyElementsHandleSlow(source, destination_ta, length, offset);
3503
  }
3504
};
3505

3506 3507
#define FIXED_ELEMENTS_ACCESSOR(Type, type, TYPE, ctype) \
  typedef TypedElementsAccessor<TYPE##_ELEMENTS, ctype>  \
3508
      Fixed##Type##ElementsAccessor;
3509

3510 3511
TYPED_ARRAYS(FIXED_ELEMENTS_ACCESSOR)
#undef FIXED_ELEMENTS_ACCESSOR
3512

3513
template <typename Subclass, typename ArgumentsAccessor, typename KindTraits>
3514
class SloppyArgumentsElementsAccessor
3515
    : public ElementsAccessorBase<Subclass, KindTraits> {
3516 3517
 public:
  explicit SloppyArgumentsElementsAccessor(const char* name)
3518
      : ElementsAccessorBase<Subclass, KindTraits>(name) {
3519 3520
    USE(KindTraits::Kind);
  }
3521

3522
  static void ConvertArgumentsStoreResult(
3523
      Handle<SloppyArgumentsElements> elements, Handle<Object> result) {
3524 3525 3526
    UNREACHABLE();
  }

3527
  static Handle<Object> GetImpl(Isolate* isolate, FixedArrayBase parameters,
3528
                                uint32_t entry) {
3529 3530 3531
    Handle<SloppyArgumentsElements> elements(
        SloppyArgumentsElements::cast(parameters), isolate);
    uint32_t length = elements->parameter_map_length();
3532
    if (entry < length) {
3533
      // Read context mapped entry.
3534
      DisallowHeapAllocation no_gc;
3535
      Object probe = elements->get_mapped_entry(entry);
3536
      DCHECK(!probe->IsTheHole(isolate));
3537
      Context context = elements->context();
jgruber's avatar
jgruber committed
3538
      int context_entry = Smi::ToInt(probe);
3539
      DCHECK(!context->get(context_entry)->IsTheHole(isolate));
3540
      return handle(context->get(context_entry), isolate);
3541
    } else {
3542
      // Entry is not context mapped, defer to the arguments.
3543
      Handle<Object> result = ArgumentsAccessor::GetImpl(
3544 3545
          isolate, elements->arguments(), entry - length);
      return Subclass::ConvertArgumentsStoreResult(isolate, elements, result);
3546 3547
    }
  }
3548

3549 3550 3551 3552 3553
  static void TransitionElementsKindImpl(Handle<JSObject> object,
                                         Handle<Map> map) {
    UNREACHABLE();
  }

3554 3555
  static void GrowCapacityAndConvertImpl(Handle<JSObject> object,
                                         uint32_t capacity) {
3556
    UNREACHABLE();
3557 3558
  }

3559
  static inline void SetImpl(Handle<JSObject> holder, uint32_t entry,
3560
                             Object value) {
3561 3562 3563
    SetImpl(holder->elements(), entry, value);
  }

3564
  static inline void SetImpl(FixedArrayBase store, uint32_t entry,
3565
                             Object value) {
3566
    SloppyArgumentsElements elements = SloppyArgumentsElements::cast(store);
3567
    uint32_t length = elements->parameter_map_length();
3568
    if (entry < length) {
3569 3570
      // Store context mapped entry.
      DisallowHeapAllocation no_gc;
3571
      Object probe = elements->get_mapped_entry(entry);
3572
      DCHECK(!probe->IsTheHole());
3573
      Context context = elements->context();
jgruber's avatar
jgruber committed
3574
      int context_entry = Smi::ToInt(probe);
3575
      DCHECK(!context->get(context_entry)->IsTheHole());
3576
      context->set(context_entry, value);
3577
    } else {
3578
      //  Entry is not context mapped defer to arguments.
3579
      FixedArray arguments = elements->arguments();
3580
      Object current = ArgumentsAccessor::GetRaw(arguments, entry - length);
3581
      if (current->IsAliasedArgumentsEntry()) {
3582
        AliasedArgumentsEntry alias = AliasedArgumentsEntry::cast(current);
3583
        Context context = elements->context();
3584
        int context_entry = alias->aliased_context_slot();
3585
        DCHECK(!context->get(context_entry)->IsTheHole());
3586 3587 3588 3589
        context->set(context_entry, value);
      } else {
        ArgumentsAccessor::SetImpl(arguments, entry - length, value);
      }
3590 3591 3592
    }
  }

3593 3594
  static void SetLengthImpl(Isolate* isolate, Handle<JSArray> array,
                            uint32_t length,
3595 3596 3597
                            Handle<FixedArrayBase> parameter_map) {
    // Sloppy arguments objects are not arrays.
    UNREACHABLE();
3598 3599
  }

3600
  static uint32_t GetCapacityImpl(JSObject holder, FixedArrayBase store) {
3601
    SloppyArgumentsElements elements = SloppyArgumentsElements::cast(store);
3602
    FixedArray arguments = elements->arguments();
3603
    return elements->parameter_map_length() +
3604
           ArgumentsAccessor::GetCapacityImpl(holder, arguments);
3605 3606
  }

3607
  static uint32_t GetMaxNumberOfEntries(JSObject holder,
3608
                                        FixedArrayBase backing_store) {
3609
    SloppyArgumentsElements elements =
3610
        SloppyArgumentsElements::cast(backing_store);
3611
    FixedArrayBase arguments = elements->arguments();
3612
    return elements->parameter_map_length() +
3613 3614 3615
           ArgumentsAccessor::GetMaxNumberOfEntries(holder, arguments);
  }

3616
  static uint32_t NumberOfElementsImpl(JSObject receiver,
3617
                                       FixedArrayBase backing_store) {
3618
    Isolate* isolate = receiver->GetIsolate();
3619
    SloppyArgumentsElements elements =
3620
        SloppyArgumentsElements::cast(backing_store);
3621
    FixedArrayBase arguments = elements->arguments();
3622
    uint32_t nof_elements = 0;
3623
    uint32_t length = elements->parameter_map_length();
3624
    for (uint32_t entry = 0; entry < length; entry++) {
3625
      if (HasParameterMapArg(isolate, elements, entry)) nof_elements++;
3626 3627 3628 3629 3630
    }
    return nof_elements +
           ArgumentsAccessor::NumberOfElementsImpl(receiver, arguments);
  }

3631 3632 3633
  static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver,
                                              KeyAccumulator* accumulator,
                                              AddKeyConversion convert) {
3634 3635 3636
    Isolate* isolate = accumulator->isolate();
    Handle<FixedArrayBase> elements(receiver->elements(), isolate);
    uint32_t length = GetCapacityImpl(*receiver, *elements);
3637
    for (uint32_t entry = 0; entry < length; entry++) {
3638
      if (!HasEntryImpl(isolate, *elements, entry)) continue;
3639
      Handle<Object> value = GetImpl(isolate, *elements, entry);
3640 3641 3642 3643
      accumulator->AddKey(value, convert);
    }
  }

3644
  static bool HasEntryImpl(Isolate* isolate, FixedArrayBase parameters,
3645
                           uint32_t entry) {
3646
    SloppyArgumentsElements elements =
3647 3648
        SloppyArgumentsElements::cast(parameters);
    uint32_t length = elements->parameter_map_length();
3649
    if (entry < length) {
3650
      return HasParameterMapArg(isolate, elements, entry);
3651
    }
3652
    FixedArrayBase arguments = elements->arguments();
3653
    return ArgumentsAccessor::HasEntryImpl(isolate, arguments, entry - length);
3654 3655
  }

3656
  static bool HasAccessorsImpl(JSObject holder, FixedArrayBase backing_store) {
3657
    SloppyArgumentsElements elements =
3658
        SloppyArgumentsElements::cast(backing_store);
3659
    FixedArray arguments = elements->arguments();
3660 3661 3662
    return ArgumentsAccessor::HasAccessorsImpl(holder, arguments);
  }

3663
  static uint32_t GetIndexForEntryImpl(FixedArrayBase parameters,
3664
                                       uint32_t entry) {
3665
    SloppyArgumentsElements elements =
3666 3667
        SloppyArgumentsElements::cast(parameters);
    uint32_t length = elements->parameter_map_length();
3668
    if (entry < length) return entry;
3669
    FixedArray arguments = elements->arguments();
3670
    return ArgumentsAccessor::GetIndexForEntryImpl(arguments, entry - length);
3671 3672
  }

3673
  static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject holder,
3674
                                       FixedArrayBase parameters,
3675
                                       uint32_t index, PropertyFilter filter) {
3676
    SloppyArgumentsElements elements =
3677 3678
        SloppyArgumentsElements::cast(parameters);
    if (HasParameterMapArg(isolate, elements, index)) return index;
3679
    FixedArray arguments = elements->arguments();
3680 3681
    uint32_t entry = ArgumentsAccessor::GetEntryForIndexImpl(
        isolate, holder, arguments, index, filter);
3682
    if (entry == kMaxUInt32) return kMaxUInt32;
3683 3684
    // Arguments entries could overlap with the dictionary entries, hence offset
    // them by the number of context mapped entries.
3685
    return elements->parameter_map_length() + entry;
3686 3687
  }

3688
  static PropertyDetails GetDetailsImpl(JSObject holder, uint32_t entry) {
3689
    SloppyArgumentsElements elements =
3690 3691
        SloppyArgumentsElements::cast(holder->elements());
    uint32_t length = elements->parameter_map_length();
3692
    if (entry < length) {
3693
      return PropertyDetails(kData, NONE, PropertyCellType::kNoCell);
3694
    }
3695
    FixedArray arguments = elements->arguments();
3696
    return ArgumentsAccessor::GetDetailsImpl(arguments, entry - length);
3697
  }
3698

3699
  static bool HasParameterMapArg(Isolate* isolate,
3700
                                 SloppyArgumentsElements elements,
3701 3702
                                 uint32_t index) {
    uint32_t length = elements->parameter_map_length();
3703
    if (index >= length) return false;
3704
    return !elements->get_mapped_entry(index)->IsTheHole(isolate);
3705
  }
3706

3707
  static void DeleteImpl(Handle<JSObject> obj, uint32_t entry) {
3708
    Handle<SloppyArgumentsElements> elements(
3709
        SloppyArgumentsElements::cast(obj->elements()), obj->GetIsolate());
3710
    uint32_t length = elements->parameter_map_length();
3711 3712 3713 3714 3715 3716 3717
    uint32_t delete_or_entry = entry;
    if (entry < length) {
      delete_or_entry = kMaxUInt32;
    }
    Subclass::SloppyDeleteImpl(obj, elements, delete_or_entry);
    // SloppyDeleteImpl allocates a new dictionary elements store. For making
    // heap verification happy we postpone clearing out the mapped entry.
3718
    if (entry < length) {
3719 3720
      elements->set_mapped_entry(entry,
                                 obj->GetReadOnlyRoots().the_hole_value());
3721 3722
    }
  }
3723

3724 3725 3726 3727 3728 3729 3730
  static void SloppyDeleteImpl(Handle<JSObject> obj,
                               Handle<SloppyArgumentsElements> elements,
                               uint32_t entry) {
    // Implemented in subclasses.
    UNREACHABLE();
  }

3731 3732
  static void CollectElementIndicesImpl(Handle<JSObject> object,
                                        Handle<FixedArrayBase> backing_store,
3733
                                        KeyAccumulator* keys) {
3734 3735 3736 3737 3738
    Isolate* isolate = keys->isolate();
    uint32_t nof_indices = 0;
    Handle<FixedArray> indices = isolate->factory()->NewFixedArray(
        GetCapacityImpl(*object, *backing_store));
    DirectCollectElementIndicesImpl(isolate, object, backing_store,
3739 3740
                                    GetKeysConversion::kKeepNumbers,
                                    ENUMERABLE_STRINGS, indices, &nof_indices);
3741
    SortIndices(isolate, indices, nof_indices);
3742 3743
    for (uint32_t i = 0; i < nof_indices; i++) {
      keys->AddKey(indices->get(i));
3744 3745 3746 3747 3748 3749 3750 3751
    }
  }

  static Handle<FixedArray> DirectCollectElementIndicesImpl(
      Isolate* isolate, Handle<JSObject> object,
      Handle<FixedArrayBase> backing_store, GetKeysConversion convert,
      PropertyFilter filter, Handle<FixedArray> list, uint32_t* nof_indices,
      uint32_t insertion_index = 0) {
3752 3753 3754
    Handle<SloppyArgumentsElements> elements =
        Handle<SloppyArgumentsElements>::cast(backing_store);
    uint32_t length = elements->parameter_map_length();
3755 3756

    for (uint32_t i = 0; i < length; ++i) {
3757
      if (elements->get_mapped_entry(i)->IsTheHole(isolate)) continue;
3758
      if (convert == GetKeysConversion::kConvertToString) {
3759 3760 3761
        Handle<String> index_string = isolate->factory()->Uint32ToString(i);
        list->set(insertion_index, *index_string);
      } else {
3762
        list->set(insertion_index, Smi::FromInt(i));
3763 3764 3765 3766
      }
      insertion_index++;
    }

3767
    Handle<FixedArray> store(elements->arguments(), isolate);
3768 3769 3770 3771
    return ArgumentsAccessor::DirectCollectElementIndicesImpl(
        isolate, object, store, convert, filter, list, nof_indices,
        insertion_index);
  }
3772 3773 3774 3775 3776 3777

  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
                                       Handle<JSObject> object,
                                       Handle<Object> value,
                                       uint32_t start_from, uint32_t length) {
    DCHECK(JSObject::PrototypeHasNoElements(isolate, *object));
3778
    Handle<Map> original_map(object->map(), isolate);
3779 3780
    Handle<SloppyArgumentsElements> elements(
        SloppyArgumentsElements::cast(object->elements()), isolate);
3781 3782 3783
    bool search_for_hole = value->IsUndefined(isolate);

    for (uint32_t k = start_from; k < length; ++k) {
3784
      DCHECK_EQ(object->map(), *original_map);
3785 3786
      uint32_t entry =
          GetEntryForIndexImpl(isolate, *object, *elements, k, ALL_PROPERTIES);
3787 3788 3789 3790 3791
      if (entry == kMaxUInt32) {
        if (search_for_hole) return Just(true);
        continue;
      }

3792
      Handle<Object> element_k = Subclass::GetImpl(isolate, *elements, entry);
3793 3794 3795 3796 3797 3798 3799 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 3812 3813

      if (element_k->IsAccessorPair()) {
        LookupIterator it(isolate, object, k, LookupIterator::OWN);
        DCHECK(it.IsFound());
        DCHECK_EQ(it.state(), LookupIterator::ACCESSOR);
        ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_k,
                                         Object::GetPropertyWithAccessor(&it),
                                         Nothing<bool>());

        if (value->SameValueZero(*element_k)) return Just(true);

        if (object->map() != *original_map) {
          // Some mutation occurred in accessor. Abort "fast" path
          return IncludesValueSlowPath(isolate, object, value, k + 1, length);
        }
      } else if (value->SameValueZero(*element_k)) {
        return Just(true);
      }
    }
    return Just(false);
  }
3814 3815 3816 3817 3818 3819

  static Maybe<int64_t> IndexOfValueImpl(Isolate* isolate,
                                         Handle<JSObject> object,
                                         Handle<Object> value,
                                         uint32_t start_from, uint32_t length) {
    DCHECK(JSObject::PrototypeHasNoElements(isolate, *object));
3820
    Handle<Map> original_map(object->map(), isolate);
3821 3822
    Handle<SloppyArgumentsElements> elements(
        SloppyArgumentsElements::cast(object->elements()), isolate);
3823 3824

    for (uint32_t k = start_from; k < length; ++k) {
3825
      DCHECK_EQ(object->map(), *original_map);
3826 3827
      uint32_t entry =
          GetEntryForIndexImpl(isolate, *object, *elements, k, ALL_PROPERTIES);
3828 3829 3830 3831
      if (entry == kMaxUInt32) {
        continue;
      }

3832
      Handle<Object> element_k = Subclass::GetImpl(isolate, *elements, entry);
3833 3834 3835 3836 3837 3838 3839 3840 3841 3842 3843 3844 3845 3846 3847 3848 3849 3850 3851 3852 3853 3854 3855

      if (element_k->IsAccessorPair()) {
        LookupIterator it(isolate, object, k, LookupIterator::OWN);
        DCHECK(it.IsFound());
        DCHECK_EQ(it.state(), LookupIterator::ACCESSOR);
        ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_k,
                                         Object::GetPropertyWithAccessor(&it),
                                         Nothing<int64_t>());

        if (value->StrictEquals(*element_k)) {
          return Just<int64_t>(k);
        }

        if (object->map() != *original_map) {
          // Some mutation occurred in accessor. Abort "fast" path.
          return IndexOfValueSlowPath(isolate, object, value, k + 1, length);
        }
      } else if (value->StrictEquals(*element_k)) {
        return Just<int64_t>(k);
      }
    }
    return Just<int64_t>(-1);
  }
3856 3857 3858 3859 3860 3861 3862 3863

  static Handle<JSObject> SliceImpl(Handle<JSObject> receiver, uint32_t start,
                                    uint32_t end) {
    Isolate* isolate = receiver->GetIsolate();
    uint32_t result_len = end < start ? 0u : end - start;
    Handle<JSArray> result_array =
        isolate->factory()->NewJSArray(HOLEY_ELEMENTS, result_len, result_len);
    DisallowHeapAllocation no_gc;
3864 3865
    FixedArray elements = FixedArray::cast(result_array->elements());
    FixedArray parameters = FixedArray::cast(receiver->elements());
3866 3867 3868 3869 3870 3871 3872 3873 3874 3875 3876 3877 3878
    uint32_t insertion_index = 0;
    for (uint32_t i = start; i < end; i++) {
      uint32_t entry = GetEntryForIndexImpl(isolate, *receiver, parameters, i,
                                            ALL_PROPERTIES);
      if (entry != kMaxUInt32 && HasEntryImpl(isolate, parameters, entry)) {
        elements->set(insertion_index, *GetImpl(isolate, parameters, entry));
      } else {
        elements->set_the_hole(isolate, insertion_index);
      }
      insertion_index++;
    }
    return result_array;
  }
3879 3880 3881
};


3882 3883 3884 3885 3886 3887 3888 3889 3890 3891
class SlowSloppyArgumentsElementsAccessor
    : public SloppyArgumentsElementsAccessor<
          SlowSloppyArgumentsElementsAccessor, DictionaryElementsAccessor,
          ElementsKindTraits<SLOW_SLOPPY_ARGUMENTS_ELEMENTS> > {
 public:
  explicit SlowSloppyArgumentsElementsAccessor(const char* name)
      : SloppyArgumentsElementsAccessor<
            SlowSloppyArgumentsElementsAccessor, DictionaryElementsAccessor,
            ElementsKindTraits<SLOW_SLOPPY_ARGUMENTS_ELEMENTS> >(name) {}

3892 3893 3894 3895 3896 3897
  static Handle<Object> ConvertArgumentsStoreResult(
      Isolate* isolate, Handle<SloppyArgumentsElements> elements,
      Handle<Object> result) {
    // Elements of the arguments object in slow mode might be slow aliases.
    if (result->IsAliasedArgumentsEntry()) {
      DisallowHeapAllocation no_gc;
3898
      AliasedArgumentsEntry alias = AliasedArgumentsEntry::cast(*result);
3899
      Context context = elements->context();
3900 3901 3902 3903 3904 3905
      int context_entry = alias->aliased_context_slot();
      DCHECK(!context->get(context_entry)->IsTheHole(isolate));
      return handle(context->get(context_entry), isolate);
    }
    return result;
  }
3906 3907 3908 3909 3910
  static void SloppyDeleteImpl(Handle<JSObject> obj,
                               Handle<SloppyArgumentsElements> elements,
                               uint32_t entry) {
    // No need to delete a context mapped entry from the arguments elements.
    if (entry == kMaxUInt32) return;
3911
    Isolate* isolate = obj->GetIsolate();
3912 3913
    Handle<NumberDictionary> dict(NumberDictionary::cast(elements->arguments()),
                                  isolate);
3914
    int length = elements->parameter_map_length();
3915
    dict = NumberDictionary::DeleteEntry(isolate, dict, entry - length);
3916
    elements->set_arguments(*dict);
3917
  }
3918
  static void AddImpl(Handle<JSObject> object, uint32_t index,
3919 3920
                      Handle<Object> value, PropertyAttributes attributes,
                      uint32_t new_capacity) {
3921 3922 3923 3924 3925
    Isolate* isolate = object->GetIsolate();
    Handle<SloppyArgumentsElements> elements(
        SloppyArgumentsElements::cast(object->elements()), isolate);
    Handle<FixedArrayBase> old_arguments(
        FixedArrayBase::cast(elements->arguments()), isolate);
3926 3927 3928
    Handle<NumberDictionary> dictionary =
        old_arguments->IsNumberDictionary()
            ? Handle<NumberDictionary>::cast(old_arguments)
3929
            : JSObject::NormalizeElements(object);
3930
    PropertyDetails details(kData, attributes, PropertyCellType::kNoCell);
3931
    Handle<NumberDictionary> new_dictionary =
3932
        NumberDictionary::Add(isolate, dictionary, index, value, details);
3933
    if (attributes != NONE) object->RequireSlowElements(*new_dictionary);
3934
    if (*dictionary != *new_dictionary) {
3935
      elements->set_arguments(*new_dictionary);
3936 3937 3938 3939
    }
  }

  static void ReconfigureImpl(Handle<JSObject> object,
3940
                              Handle<FixedArrayBase> store, uint32_t entry,
3941 3942
                              Handle<Object> value,
                              PropertyAttributes attributes) {
3943
    Isolate* isolate = object->GetIsolate();
3944 3945 3946
    Handle<SloppyArgumentsElements> elements =
        Handle<SloppyArgumentsElements>::cast(store);
    uint32_t length = elements->parameter_map_length();
3947
    if (entry < length) {
3948
      Object probe = elements->get_mapped_entry(entry);
3949
      DCHECK(!probe->IsTheHole(isolate));
3950
      Context context = elements->context();
jgruber's avatar
jgruber committed
3951
      int context_entry = Smi::ToInt(probe);
3952
      DCHECK(!context->get(context_entry)->IsTheHole(isolate));
3953
      context->set(context_entry, *value);
3954 3955

      // Redefining attributes of an aliased element destroys fast aliasing.
3956 3957
      elements->set_mapped_entry(entry,
                                 ReadOnlyRoots(isolate).the_hole_value());
3958 3959
      // For elements that are still writable we re-establish slow aliasing.
      if ((attributes & READ_ONLY) == 0) {
3960
        value = isolate->factory()->NewAliasedArgumentsEntry(context_entry);
3961 3962
      }

3963
      PropertyDetails details(kData, attributes, PropertyCellType::kNoCell);
3964 3965
      Handle<NumberDictionary> arguments(
          NumberDictionary::cast(elements->arguments()), isolate);
3966 3967
      arguments =
          NumberDictionary::Add(isolate, arguments, entry, value, details);
3968 3969 3970 3971
      // If the attributes were NONE, we would have called set rather than
      // reconfigure.
      DCHECK_NE(NONE, attributes);
      object->RequireSlowElements(*arguments);
3972
      elements->set_arguments(*arguments);
3973
    } else {
3974
      Handle<FixedArrayBase> arguments(elements->arguments(), isolate);
3975
      DictionaryElementsAccessor::ReconfigureImpl(
3976
          object, arguments, entry - length, value, attributes);
3977 3978 3979 3980 3981
    }
  }
};


3982 3983 3984 3985 3986 3987 3988 3989 3990 3991 3992
class FastSloppyArgumentsElementsAccessor
    : public SloppyArgumentsElementsAccessor<
          FastSloppyArgumentsElementsAccessor, FastHoleyObjectElementsAccessor,
          ElementsKindTraits<FAST_SLOPPY_ARGUMENTS_ELEMENTS> > {
 public:
  explicit FastSloppyArgumentsElementsAccessor(const char* name)
      : SloppyArgumentsElementsAccessor<
            FastSloppyArgumentsElementsAccessor,
            FastHoleyObjectElementsAccessor,
            ElementsKindTraits<FAST_SLOPPY_ARGUMENTS_ELEMENTS> >(name) {}

3993 3994 3995 3996 3997 3998 3999
  static Handle<Object> ConvertArgumentsStoreResult(
      Isolate* isolate, Handle<SloppyArgumentsElements> paramtere_map,
      Handle<Object> result) {
    DCHECK(!result->IsAliasedArgumentsEntry());
    return result;
  }

4000
  static Handle<FixedArray> GetArguments(Isolate* isolate,
4001
                                         FixedArrayBase store) {
4002
    SloppyArgumentsElements elements = SloppyArgumentsElements::cast(store);
4003
    return Handle<FixedArray>(elements->arguments(), isolate);
4004 4005
  }

4006
  static Handle<NumberDictionary> NormalizeImpl(
4007
      Handle<JSObject> object, Handle<FixedArrayBase> elements) {
4008
    Handle<FixedArray> arguments =
4009
        GetArguments(object->GetIsolate(), *elements);
4010 4011 4012
    return FastHoleyObjectElementsAccessor::NormalizeImpl(object, arguments);
  }

4013
  static Handle<NumberDictionary> NormalizeArgumentsElements(
4014 4015
      Handle<JSObject> object, Handle<SloppyArgumentsElements> elements,
      uint32_t* entry) {
4016
    Handle<NumberDictionary> dictionary = JSObject::NormalizeElements(object);
4017 4018 4019 4020 4021 4022
    elements->set_arguments(*dictionary);
    // kMaxUInt32 indicates that a context mapped element got deleted. In this
    // case we only normalize the elements (aka. migrate to SLOW_SLOPPY).
    if (*entry == kMaxUInt32) return dictionary;
    uint32_t length = elements->parameter_map_length();
    if (*entry >= length) {
4023 4024
      *entry =
          dictionary->FindEntry(object->GetIsolate(), *entry - length) + length;
4025 4026 4027 4028 4029 4030 4031 4032 4033 4034
    }
    return dictionary;
  }

  static void SloppyDeleteImpl(Handle<JSObject> obj,
                               Handle<SloppyArgumentsElements> elements,
                               uint32_t entry) {
    // Always normalize element on deleting an entry.
    NormalizeArgumentsElements(obj, elements, &entry);
    SlowSloppyArgumentsElementsAccessor::SloppyDeleteImpl(obj, elements, entry);
4035 4036
  }

4037
  static void AddImpl(Handle<JSObject> object, uint32_t index,
4038 4039 4040
                      Handle<Object> value, PropertyAttributes attributes,
                      uint32_t new_capacity) {
    DCHECK_EQ(NONE, attributes);
4041 4042 4043 4044
    Isolate* isolate = object->GetIsolate();
    Handle<SloppyArgumentsElements> elements(
        SloppyArgumentsElements::cast(object->elements()), isolate);
    Handle<FixedArray> old_arguments(elements->arguments(), isolate);
4045
    if (old_arguments->IsNumberDictionary() ||
4046
        static_cast<uint32_t>(old_arguments->length()) < new_capacity) {
4047 4048
      GrowCapacityAndConvertImpl(object, new_capacity);
    }
4049
    FixedArray arguments = elements->arguments();
4050 4051 4052 4053 4054 4055
    // For fast holey objects, the entry equals the index. The code above made
    // sure that there's enough space to store the value. We cannot convert
    // index to entry explicitly since the slot still contains the hole, so the
    // current EntryForIndex would indicate that it is "absent" by returning
    // kMaxUInt32.
    FastHoleyObjectElementsAccessor::SetImpl(arguments, index, *value);
4056
  }
4057

4058
  static void ReconfigureImpl(Handle<JSObject> object,
4059
                              Handle<FixedArrayBase> store, uint32_t entry,
4060 4061
                              Handle<Object> value,
                              PropertyAttributes attributes) {
4062 4063
    DCHECK_EQ(object->elements(), *store);
    Handle<SloppyArgumentsElements> elements(
4064
        SloppyArgumentsElements::cast(*store), object->GetIsolate());
4065
    NormalizeArgumentsElements(object, elements, &entry);
4066
    SlowSloppyArgumentsElementsAccessor::ReconfigureImpl(object, store, entry,
4067
                                                         value, attributes);
4068
  }
4069

4070 4071
  static void CopyElementsImpl(Isolate* isolate, FixedArrayBase from,
                               uint32_t from_start, FixedArrayBase to,
4072 4073
                               ElementsKind from_kind, uint32_t to_start,
                               int packed_size, int copy_size) {
4074 4075
    DCHECK(!to->IsDictionary());
    if (from_kind == SLOW_SLOPPY_ARGUMENTS_ELEMENTS) {
4076 4077
      CopyDictionaryToObjectElements(isolate, from, from_start, to,
                                     HOLEY_ELEMENTS, to_start, copy_size);
4078 4079
    } else {
      DCHECK_EQ(FAST_SLOPPY_ARGUMENTS_ELEMENTS, from_kind);
4080
      CopyObjectToObjectElements(isolate, from, HOLEY_ELEMENTS, from_start, to,
4081
                                 HOLEY_ELEMENTS, to_start, copy_size);
4082 4083 4084 4085 4086
    }
  }

  static void GrowCapacityAndConvertImpl(Handle<JSObject> object,
                                         uint32_t capacity) {
4087 4088 4089 4090 4091
    Isolate* isolate = object->GetIsolate();
    Handle<SloppyArgumentsElements> elements(
        SloppyArgumentsElements::cast(object->elements()), isolate);
    Handle<FixedArray> old_arguments(FixedArray::cast(elements->arguments()),
                                     isolate);
4092 4093 4094 4095
    ElementsKind from_kind = object->GetElementsKind();
    // This method should only be called if there's a reason to update the
    // elements.
    DCHECK(from_kind == SLOW_SLOPPY_ARGUMENTS_ELEMENTS ||
4096 4097 4098
           static_cast<uint32_t>(old_arguments->length()) < capacity);
    Handle<FixedArrayBase> arguments =
        ConvertElementsWithCapacity(object, old_arguments, from_kind, capacity);
4099 4100 4101
    Handle<Map> new_map = JSObject::GetElementsTransitionMap(
        object, FAST_SLOPPY_ARGUMENTS_ELEMENTS);
    JSObject::MigrateToMap(object, new_map);
4102
    elements->set_arguments(FixedArray::cast(*arguments));
4103
    JSObject::ValidateElements(*object);
4104 4105 4106
  }
};

4107
template <typename Subclass, typename BackingStoreAccessor, typename KindTraits>
4108
class StringWrapperElementsAccessor
4109
    : public ElementsAccessorBase<Subclass, KindTraits> {
4110 4111
 public:
  explicit StringWrapperElementsAccessor(const char* name)
4112
      : ElementsAccessorBase<Subclass, KindTraits>(name) {
4113 4114 4115
    USE(KindTraits::Kind);
  }

4116 4117 4118 4119 4120
  static Handle<Object> GetInternalImpl(Handle<JSObject> holder,
                                        uint32_t entry) {
    return GetImpl(holder, entry);
  }

4121 4122 4123 4124 4125 4126
  static Handle<Object> GetImpl(Handle<JSObject> holder, uint32_t entry) {
    Isolate* isolate = holder->GetIsolate();
    Handle<String> string(GetString(*holder), isolate);
    uint32_t length = static_cast<uint32_t>(string->length());
    if (entry < length) {
      return isolate->factory()->LookupSingleCharacterStringFromCode(
4127
          String::Flatten(isolate, string)->Get(entry));
4128
    }
4129 4130 4131 4132
    return BackingStoreAccessor::GetImpl(isolate, holder->elements(),
                                         entry - length);
  }

4133
  static Handle<Object> GetImpl(Isolate* isolate, FixedArrayBase elements,
4134 4135
                                uint32_t entry) {
    UNREACHABLE();
4136 4137
  }

4138
  static PropertyDetails GetDetailsImpl(JSObject holder, uint32_t entry) {
4139 4140 4141 4142
    uint32_t length = static_cast<uint32_t>(GetString(holder)->length());
    if (entry < length) {
      PropertyAttributes attributes =
          static_cast<PropertyAttributes>(READ_ONLY | DONT_DELETE);
4143
      return PropertyDetails(kData, attributes, PropertyCellType::kNoCell);
4144 4145 4146 4147
    }
    return BackingStoreAccessor::GetDetailsImpl(holder, entry - length);
  }

4148
  static uint32_t GetEntryForIndexImpl(Isolate* isolate, JSObject holder,
4149
                                       FixedArrayBase backing_store,
4150 4151 4152 4153
                                       uint32_t index, PropertyFilter filter) {
    uint32_t length = static_cast<uint32_t>(GetString(holder)->length());
    if (index < length) return index;
    uint32_t backing_store_entry = BackingStoreAccessor::GetEntryForIndexImpl(
4154
        isolate, holder, backing_store, index, filter);
4155 4156 4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167
    if (backing_store_entry == kMaxUInt32) return kMaxUInt32;
    DCHECK(backing_store_entry < kMaxUInt32 - length);
    return backing_store_entry + length;
  }

  static void DeleteImpl(Handle<JSObject> holder, uint32_t entry) {
    uint32_t length = static_cast<uint32_t>(GetString(*holder)->length());
    if (entry < length) {
      return;  // String contents can't be deleted.
    }
    BackingStoreAccessor::DeleteImpl(holder, entry - length);
  }

4168
  static void SetImpl(Handle<JSObject> holder, uint32_t entry, Object value) {
4169 4170 4171 4172 4173 4174 4175 4176 4177 4178 4179
    uint32_t length = static_cast<uint32_t>(GetString(*holder)->length());
    if (entry < length) {
      return;  // String contents are read-only.
    }
    BackingStoreAccessor::SetImpl(holder->elements(), entry - length, value);
  }

  static void AddImpl(Handle<JSObject> object, uint32_t index,
                      Handle<Object> value, PropertyAttributes attributes,
                      uint32_t new_capacity) {
    DCHECK(index >= static_cast<uint32_t>(GetString(*object)->length()));
4180 4181 4182 4183 4184 4185
    // Explicitly grow fast backing stores if needed. Dictionaries know how to
    // extend their capacity themselves.
    if (KindTraits::Kind == FAST_STRING_WRAPPER_ELEMENTS &&
        (object->GetElementsKind() == SLOW_STRING_WRAPPER_ELEMENTS ||
         BackingStoreAccessor::GetCapacityImpl(*object, object->elements()) !=
             new_capacity)) {
4186
      GrowCapacityAndConvertImpl(object, new_capacity);
4187 4188 4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207 4208
    }
    BackingStoreAccessor::AddImpl(object, index, value, attributes,
                                  new_capacity);
  }

  static void ReconfigureImpl(Handle<JSObject> object,
                              Handle<FixedArrayBase> store, uint32_t entry,
                              Handle<Object> value,
                              PropertyAttributes attributes) {
    uint32_t length = static_cast<uint32_t>(GetString(*object)->length());
    if (entry < length) {
      return;  // String contents can't be reconfigured.
    }
    BackingStoreAccessor::ReconfigureImpl(object, store, entry - length, value,
                                          attributes);
  }

  static void AddElementsToKeyAccumulatorImpl(Handle<JSObject> receiver,
                                              KeyAccumulator* accumulator,
                                              AddKeyConversion convert) {
    Isolate* isolate = receiver->GetIsolate();
    Handle<String> string(GetString(*receiver), isolate);
4209
    string = String::Flatten(isolate, string);
4210 4211 4212 4213 4214 4215 4216 4217 4218 4219 4220 4221 4222
    uint32_t length = static_cast<uint32_t>(string->length());
    for (uint32_t i = 0; i < length; i++) {
      accumulator->AddKey(
          isolate->factory()->LookupSingleCharacterStringFromCode(
              string->Get(i)),
          convert);
    }
    BackingStoreAccessor::AddElementsToKeyAccumulatorImpl(receiver, accumulator,
                                                          convert);
  }

  static void CollectElementIndicesImpl(Handle<JSObject> object,
                                        Handle<FixedArrayBase> backing_store,
4223
                                        KeyAccumulator* keys) {
4224
    uint32_t length = GetString(*object)->length();
4225
    Factory* factory = keys->isolate()->factory();
4226
    for (uint32_t i = 0; i < length; i++) {
4227
      keys->AddKey(factory->NewNumberFromUint(i));
4228
    }
4229 4230
    BackingStoreAccessor::CollectElementIndicesImpl(object, backing_store,
                                                    keys);
4231 4232
  }

4233 4234
  static void GrowCapacityAndConvertImpl(Handle<JSObject> object,
                                         uint32_t capacity) {
4235 4236
    Handle<FixedArrayBase> old_elements(object->elements(),
                                        object->GetIsolate());
4237
    ElementsKind from_kind = object->GetElementsKind();
4238 4239 4240 4241 4242
    if (from_kind == FAST_STRING_WRAPPER_ELEMENTS) {
      // The optimizing compiler relies on the prototype lookups of String
      // objects always returning undefined. If there's a store to the
      // initial String.prototype object, make sure all the optimizations
      // are invalidated.
4243
      object->GetIsolate()->UpdateNoElementsProtectorOnSetLength(object);
4244
    }
4245 4246 4247 4248 4249 4250 4251 4252 4253
    // This method should only be called if there's a reason to update the
    // elements.
    DCHECK(from_kind == SLOW_STRING_WRAPPER_ELEMENTS ||
           static_cast<uint32_t>(old_elements->length()) < capacity);
    Subclass::BasicGrowCapacityAndConvertImpl(object, old_elements, from_kind,
                                              FAST_STRING_WRAPPER_ELEMENTS,
                                              capacity);
  }

4254 4255
  static void CopyElementsImpl(Isolate* isolate, FixedArrayBase from,
                               uint32_t from_start, FixedArrayBase to,
4256 4257
                               ElementsKind from_kind, uint32_t to_start,
                               int packed_size, int copy_size) {
4258 4259
    DCHECK(!to->IsDictionary());
    if (from_kind == SLOW_STRING_WRAPPER_ELEMENTS) {
4260 4261
      CopyDictionaryToObjectElements(isolate, from, from_start, to,
                                     HOLEY_ELEMENTS, to_start, copy_size);
4262 4263
    } else {
      DCHECK_EQ(FAST_STRING_WRAPPER_ELEMENTS, from_kind);
4264
      CopyObjectToObjectElements(isolate, from, HOLEY_ELEMENTS, from_start, to,
4265
                                 HOLEY_ELEMENTS, to_start, copy_size);
4266
    }
4267 4268
  }

4269
  static uint32_t NumberOfElementsImpl(JSObject object,
4270
                                       FixedArrayBase backing_store) {
4271 4272 4273 4274 4275
    uint32_t length = GetString(object)->length();
    return length +
           BackingStoreAccessor::NumberOfElementsImpl(object, backing_store);
  }

4276
 private:
4277
  static String GetString(JSObject holder) {
4278
    DCHECK(holder->IsJSValue());
4279
    JSValue js_value = JSValue::cast(holder);
4280 4281 4282 4283 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293
    DCHECK(js_value->value()->IsString());
    return String::cast(js_value->value());
  }
};

class FastStringWrapperElementsAccessor
    : public StringWrapperElementsAccessor<
          FastStringWrapperElementsAccessor, FastHoleyObjectElementsAccessor,
          ElementsKindTraits<FAST_STRING_WRAPPER_ELEMENTS>> {
 public:
  explicit FastStringWrapperElementsAccessor(const char* name)
      : StringWrapperElementsAccessor<
            FastStringWrapperElementsAccessor, FastHoleyObjectElementsAccessor,
            ElementsKindTraits<FAST_STRING_WRAPPER_ELEMENTS>>(name) {}
4294

4295
  static Handle<NumberDictionary> NormalizeImpl(
4296 4297 4298
      Handle<JSObject> object, Handle<FixedArrayBase> elements) {
    return FastHoleyObjectElementsAccessor::NormalizeImpl(object, elements);
  }
4299 4300 4301 4302 4303 4304 4305 4306 4307 4308 4309
};

class SlowStringWrapperElementsAccessor
    : public StringWrapperElementsAccessor<
          SlowStringWrapperElementsAccessor, DictionaryElementsAccessor,
          ElementsKindTraits<SLOW_STRING_WRAPPER_ELEMENTS>> {
 public:
  explicit SlowStringWrapperElementsAccessor(const char* name)
      : StringWrapperElementsAccessor<
            SlowStringWrapperElementsAccessor, DictionaryElementsAccessor,
            ElementsKindTraits<SLOW_STRING_WRAPPER_ELEMENTS>>(name) {}
4310

4311
  static bool HasAccessorsImpl(JSObject holder, FixedArrayBase backing_store) {
4312 4313
    return DictionaryElementsAccessor::HasAccessorsImpl(holder, backing_store);
  }
4314
};
4315

4316 4317 4318
}  // namespace


4319
void CheckArrayAbuse(Handle<JSObject> obj, const char* op, uint32_t index,
4320 4321
                     bool allow_appending) {
  DisallowHeapAllocation no_allocation;
4322
  Object raw_length;
4323 4324
  const char* elements_type = "array";
  if (obj->IsJSArray()) {
4325
    JSArray array = JSArray::cast(*obj);
4326 4327 4328 4329 4330 4331 4332 4333 4334 4335 4336 4337
    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);
      uint32_t compare_length = static_cast<uint32_t>(int32_length);
      if (allow_appending) compare_length++;
4338
      if (index >= compare_length) {
4339 4340
        PrintF("[OOB %s %s (%s length = %d, element accessed = %d) in ",
               elements_type, op, elements_type, static_cast<int>(int32_length),
4341
               static_cast<int>(index));
4342 4343 4344 4345 4346 4347 4348 4349 4350 4351 4352 4353 4354 4355
        TraceTopFrame(obj->GetIsolate());
        PrintF("]\n");
      }
    } else {
      PrintF("[%s elements length not integer value in ", elements_type);
      TraceTopFrame(obj->GetIsolate());
      PrintF("]\n");
    }
  } else {
    PrintF("[%s elements length not a number in ", elements_type);
    TraceTopFrame(obj->GetIsolate());
    PrintF("]\n");
  }
}
4356 4357


4358 4359
MaybeHandle<Object> ArrayConstructInitializeElements(Handle<JSArray> array,
                                                     Arguments* args) {
4360 4361 4362 4363 4364
  if (args->length() == 0) {
    // Optimize the case where there are no parameters passed.
    JSArray::Initialize(array, JSArray::kPreallocatedArrayElements);
    return array;

4365
  } else if (args->length() == 1 && args->at(0)->IsNumber()) {
4366
    uint32_t length;
4367
    if (!args->at(0)->ToArrayLength(&length)) {
4368 4369 4370 4371 4372
      return ThrowArrayLengthRangeError(array->GetIsolate());
    }

    // Optimize the case where there is one argument and the argument is a small
    // smi.
4373
    if (length > 0 && length < JSArray::kInitialMaxFastElementArray) {
4374 4375 4376
      ElementsKind elements_kind = array->GetElementsKind();
      JSArray::Initialize(array, length, length);

4377
      if (!IsHoleyElementsKind(elements_kind)) {
4378 4379
        elements_kind = GetHoleyElementsKind(elements_kind);
        JSObject::TransitionElementsKind(array, elements_kind);
4380
      }
4381 4382
    } else if (length == 0) {
      JSArray::Initialize(array, JSArray::kPreallocatedArrayElements);
4383 4384 4385 4386
    } else {
      // Take the argument as the length.
      JSArray::Initialize(array, 0);
      JSArray::SetLength(array, length);
4387
    }
4388
    return array;
4389 4390
  }

4391 4392
  Factory* factory = array->GetIsolate()->factory();

4393 4394
  // Set length and elements on the array.
  int number_of_elements = args->length();
4395 4396
  JSObject::EnsureCanContainElements(
      array, args, 0, number_of_elements, ALLOW_CONVERTED_DOUBLE_ELEMENTS);
4397 4398 4399

  // Allocate an appropriately typed elements array.
  ElementsKind elements_kind = array->GetElementsKind();
4400
  Handle<FixedArrayBase> elms;
4401
  if (IsDoubleElementsKind(elements_kind)) {
4402 4403
    elms = Handle<FixedArrayBase>::cast(
        factory->NewFixedDoubleArray(number_of_elements));
4404
  } else {
4405 4406
    elms = Handle<FixedArrayBase>::cast(
        factory->NewFixedArrayWithHoles(number_of_elements));
4407 4408 4409
  }

  // Fill in the content
4410
  switch (elements_kind) {
4411 4412
    case HOLEY_SMI_ELEMENTS:
    case PACKED_SMI_ELEMENTS: {
4413
      Handle<FixedArray> smi_elms = Handle<FixedArray>::cast(elms);
4414 4415
      for (int entry = 0; entry < number_of_elements; entry++) {
        smi_elms->set(entry, (*args)[entry], SKIP_WRITE_BARRIER);
4416 4417 4418
      }
      break;
    }
4419 4420
    case HOLEY_ELEMENTS:
    case PACKED_ELEMENTS: {
4421
      DisallowHeapAllocation no_gc;
4422
      WriteBarrierMode mode = elms->GetWriteBarrierMode(no_gc);
4423
      Handle<FixedArray> object_elms = Handle<FixedArray>::cast(elms);
4424 4425
      for (int entry = 0; entry < number_of_elements; entry++) {
        object_elms->set(entry, (*args)[entry], mode);
4426 4427 4428
      }
      break;
    }
4429 4430
    case HOLEY_DOUBLE_ELEMENTS:
    case PACKED_DOUBLE_ELEMENTS: {
4431 4432
      Handle<FixedDoubleArray> double_elms =
          Handle<FixedDoubleArray>::cast(elms);
4433 4434
      for (int entry = 0; entry < number_of_elements; entry++) {
        double_elms->set(entry, (*args)[entry]->Number());
4435 4436 4437 4438 4439 4440 4441 4442
      }
      break;
    }
    default:
      UNREACHABLE();
      break;
  }

4443
  array->set_elements(*elms);
4444 4445 4446 4447
  array->set_length(Smi::FromInt(number_of_elements));
  return array;
}

4448
void CopyFastNumberJSArrayElementsToTypedArray(Address raw_context,
4449 4450
                                               Address raw_source,
                                               Address raw_destination,
4451 4452
                                               uintptr_t length,
                                               uintptr_t offset) {
4453 4454 4455
  Context context = Context::cast(Object(raw_context));
  JSArray source = JSArray::cast(Object(raw_source));
  JSTypedArray destination = JSTypedArray::cast(Object(raw_destination));
4456 4457

  switch (destination->GetElementsKind()) {
4458
#define TYPED_ARRAYS_CASE(Type, type, TYPE, ctype)                             \
4459 4460 4461 4462 4463
  case TYPE##_ELEMENTS:                                                        \
    CHECK(Fixed##Type##ElementsAccessor::TryCopyElementsFastNumber(            \
        context, source, destination, length, static_cast<uint32_t>(offset))); \
    break;
    TYPED_ARRAYS(TYPED_ARRAYS_CASE)
4464 4465 4466 4467 4468 4469
#undef TYPED_ARRAYS_CASE
    default:
      UNREACHABLE();
  }
}

4470 4471
void CopyTypedArrayElementsToTypedArray(Address raw_source,
                                        Address raw_destination,
4472
                                        uintptr_t length, uintptr_t offset) {
4473 4474
  JSTypedArray source = JSTypedArray::cast(Object(raw_source));
  JSTypedArray destination = JSTypedArray::cast(Object(raw_destination));
4475

4476
  switch (destination->GetElementsKind()) {
4477
#define TYPED_ARRAYS_CASE(Type, type, TYPE, ctype)                   \
4478 4479 4480 4481 4482
  case TYPE##_ELEMENTS:                                              \
    Fixed##Type##ElementsAccessor::CopyElementsFromTypedArray(       \
        source, destination, length, static_cast<uint32_t>(offset)); \
    break;
    TYPED_ARRAYS(TYPED_ARRAYS_CASE)
4483 4484 4485 4486 4487
#undef TYPED_ARRAYS_CASE
    default:
      UNREACHABLE();
  }
}
4488

4489 4490
void CopyTypedArrayElementsSlice(Address raw_source, Address raw_destination,
                                 uintptr_t start, uintptr_t end) {
4491 4492
  JSTypedArray source = JSTypedArray::cast(Object(raw_source));
  JSTypedArray destination = JSTypedArray::cast(Object(raw_destination));
4493

4494 4495 4496 4497
  destination->GetElementsAccessor()->CopyTypedArrayElementsSlice(
      source, destination, start, end);
}

4498 4499 4500 4501 4502 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512
void ElementsAccessor::InitializeOncePerProcess() {
  static ElementsAccessor* accessor_array[] = {
#define ACCESSOR_ARRAY(Class, Kind, Store) new Class(#Kind),
      ELEMENTS_LIST(ACCESSOR_ARRAY)
#undef ACCESSOR_ARRAY
  };

  STATIC_ASSERT((sizeof(accessor_array) / sizeof(*accessor_array)) ==
                kElementsKindCount);

  elements_accessors_ = accessor_array;
}


void ElementsAccessor::TearDown() {
4513
  if (elements_accessors_ == nullptr) return;
4514 4515 4516
#define ACCESSOR_DELETE(Class, Kind, Store) delete elements_accessors_[Kind];
  ELEMENTS_LIST(ACCESSOR_DELETE)
#undef ACCESSOR_DELETE
4517
  elements_accessors_ = nullptr;
4518 4519
}

4520
Handle<JSArray> ElementsAccessor::Concat(Isolate* isolate, Arguments* args,
4521 4522
                                         uint32_t concat_size,
                                         uint32_t result_len) {
4523
  ElementsKind result_elements_kind = GetInitialFastElementsKind();
4524
  bool has_raw_doubles = false;
4525 4526
  {
    DisallowHeapAllocation no_gc;
4527
    bool is_holey = false;
4528
    for (uint32_t i = 0; i < concat_size; i++) {
4529
      Object arg = (*args)[i];
4530
      ElementsKind arg_kind = JSArray::cast(arg)->GetElementsKind();
4531 4532
      has_raw_doubles = has_raw_doubles || IsDoubleElementsKind(arg_kind);
      is_holey = is_holey || IsHoleyElementsKind(arg_kind);
4533 4534
      result_elements_kind =
          GetMoreGeneralElementsKind(result_elements_kind, arg_kind);
4535 4536
    }
    if (is_holey) {
4537
      result_elements_kind = GetHoleyElementsKind(result_elements_kind);
4538 4539 4540 4541 4542 4543
    }
  }

  // If a double array is concatted into a fast elements array, the fast
  // elements array needs to be initialized to contain proper holes, since
  // boxing doubles may cause incremental marking.
4544
  bool requires_double_boxing =
4545
      has_raw_doubles && !IsDoubleElementsKind(result_elements_kind);
4546 4547 4548
  ArrayStorageAllocationMode mode = requires_double_boxing
                                        ? INITIALIZE_ARRAY_ELEMENTS_WITH_HOLE
                                        : DONT_INITIALIZE_ARRAY_ELEMENTS;
4549
  Handle<JSArray> result_array = isolate->factory()->NewJSArray(
4550
      result_elements_kind, result_len, result_len, mode);
4551
  if (result_len == 0) return result_array;
4552 4553

  uint32_t insertion_index = 0;
4554
  Handle<FixedArrayBase> storage(result_array->elements(), isolate);
4555
  ElementsAccessor* accessor = ElementsAccessor::ForKind(result_elements_kind);
4556 4557 4558
  for (uint32_t i = 0; i < concat_size; i++) {
    // It is crucial to keep |array| in a raw pointer form to avoid
    // performance degradation.
4559
    JSArray array = JSArray::cast((*args)[i]);
4560 4561 4562 4563 4564 4565
    uint32_t len = 0;
    array->length()->ToArrayLength(&len);
    if (len == 0) continue;
    ElementsKind from_kind = array->GetElementsKind();
    accessor->CopyElements(array, 0, from_kind, storage, insertion_index, len);
    insertion_index += len;
4566 4567
  }

4568
  DCHECK_EQ(insertion_index, result_len);
4569 4570 4571
  return result_array;
}

4572
ElementsAccessor** ElementsAccessor::elements_accessors_ = nullptr;
4573 4574

#undef ELEMENTS_LIST
4575 4576
}  // namespace internal
}  // namespace v8