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