Implement tracking and optimizations of packed arrays

src/elements.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 21 matching lines @@
 #include "utils.h"
 
 
 // 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)
-//     - FastObjectElementsAccessor
+//     - FastSmiOrObjectElementsAccessor
+//       - FastPackedSmiElementsAccessor
+//       - FastHoleySmiElementsAccessor
+//       - FastPackedObjectElementsAccessor
+//       - FastHoleyObjectElementsAccessor
 //     - FastDoubleElementsAccessor
+//       - FastPackedDoubleElementsAccessor
+//       - FastHoleyDoubleElementsAccessor
 //   - ExternalElementsAccessor                  (abstract)
 //     - ExternalByteElementsAccessor
 //     - ExternalUnsignedByteElementsAccessor
 //     - ExternalShortElementsAccessor
 //     - ExternalUnsignedShortElementsAccessor
 //     - ExternalIntElementsAccessor
 //     - ExternalUnsignedIntElementsAccessor
 //     - ExternalFloatElementsAccessor
 //     - ExternalDoubleElementsAccessor
 //     - PixelElementsAccessor
 //   - DictionaryElementsAccessor
 //   - NonStrictArgumentsElementsAccessor
 
 
 namespace v8 {
 namespace internal {
 
 
 // First argument in list is the accessor class, the second argument is the
 // accessor ElementsKind, and the third is the backing store class.  Use the
 // fast element handler for smi-only arrays.  The implementation is currently
 // identical.  Note that the order must match that of the ElementsKind enum for
 // the |accessor_array[]| below to work.
 #define ELEMENTS_LIST(V)                                                \
-  V(FastObjectElementsAccessor, FAST_SMI_ONLY_ELEMENTS, FixedArray)     \
-  V(FastObjectElementsAccessor, FAST_ELEMENTS, FixedArray)              \
-  V(FastDoubleElementsAccessor, FAST_DOUBLE_ELEMENTS, FixedDoubleArray) \
+  V(FastPackedSmiElementsAccessor, FAST_SMI_ELEMENTS, FixedArray)       \
+  V(FastHoleySmiElementsAccessor, FAST_HOLEY_SMI_ELEMENTS,              \
+    FixedArray)                                                         \
+  V(FastPackedObjectElementsAccessor, FAST_ELEMENTS, FixedArray)        \
+  V(FastHoleyObjectElementsAccessor, FAST_HOLEY_ELEMENTS, FixedArray)   \
+  V(FastPackedDoubleElementsAccessor, FAST_DOUBLE_ELEMENTS,             \
+    FixedDoubleArray)                                                   \
+  V(FastHoleyDoubleElementsAccessor, FAST_HOLEY_DOUBLE_ELEMENTS,        \
+    FixedDoubleArray)                                                   \
   V(DictionaryElementsAccessor, DICTIONARY_ELEMENTS,                    \
     SeededNumberDictionary)                                             \
   V(NonStrictArgumentsElementsAccessor, NON_STRICT_ARGUMENTS_ELEMENTS,  \
     FixedArray)                                                         \
   V(ExternalByteElementsAccessor, EXTERNAL_BYTE_ELEMENTS,               \
     ExternalByteArray)                                                  \
   V(ExternalUnsignedByteElementsAccessor,                               \
     EXTERNAL_UNSIGNED_BYTE_ELEMENTS, ExternalUnsignedByteArray)         \
   V(ExternalShortElementsAccessor, EXTERNAL_SHORT_ELEMENTS,             \
     ExternalShortArray)                                                 \
@@ skipping 51 matching lines @@
 
 
 void CopyObjectToObjectElements(FixedArray* from,
                                 ElementsKind from_kind,
                                 uint32_t from_start,
                                 FixedArray* to,
                                 ElementsKind to_kind,
                                 uint32_t to_start,
                                 int raw_copy_size) {
   ASSERT(to->map() != HEAP->fixed_cow_array_map());
-  ASSERT(from_kind == FAST_ELEMENTS || from_kind == FAST_SMI_ONLY_ELEMENTS);
-  ASSERT(to_kind == FAST_ELEMENTS || to_kind == FAST_SMI_ONLY_ELEMENTS);
+  ASSERT(IsFastSmiOrObjectElementsKind(from_kind));
+  ASSERT(IsFastSmiOrObjectElementsKind(to_kind));
   int copy_size = raw_copy_size;
   if (raw_copy_size < 0) {
     ASSERT(raw_copy_size == ElementsAccessor::kCopyToEnd ||
            raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
     copy_size = Min(from->length() - from_start,
                     to->length() - to_start);
 #ifdef DEBUG
-    // FAST_ELEMENT arrays cannot be uninitialized. Ensure they are already
+    // FAST_*_ELEMENTS arrays cannot be uninitialized. Ensure they are already
     // marked with the hole.
     if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
       for (int i = to_start + copy_size; i < to->length(); ++i) {
         ASSERT(to->get(i)->IsTheHole());
       }
     }
 #endif
   }
   ASSERT((copy_size + static_cast<int>(to_start)) <= to->length() &&
          (copy_size + static_cast<int>(from_start)) <= from->length());
   if (copy_size == 0) return;
   Address to_address = to->address() + FixedArray::kHeaderSize;
   Address from_address = from->address() + FixedArray::kHeaderSize;
   CopyWords(reinterpret_cast<Object**>(to_address) + to_start,
             reinterpret_cast<Object**>(from_address) + from_start,
             copy_size);
-  if (from_kind == FAST_ELEMENTS && to_kind == FAST_ELEMENTS) {
+  if (IsFastObjectElementsKind(from_kind) &&
+      IsFastObjectElementsKind(to_kind)) {
     Heap* heap = from->GetHeap();
     if (!heap->InNewSpace(to)) {
       heap->RecordWrites(to->address(),
                          to->OffsetOfElementAt(to_start),
                          copy_size);
     }
     heap->incremental_marking()->RecordWrites(to);
   }
 }
 
 
 static void CopyDictionaryToObjectElements(SeededNumberDictionary* from,
                                            uint32_t from_start,
                                            FixedArray* to,
                                            ElementsKind to_kind,
                                            uint32_t to_start,
                                            int raw_copy_size) {
   int copy_size = raw_copy_size;
   Heap* heap = from->GetHeap();
   if (raw_copy_size < 0) {
     ASSERT(raw_copy_size == ElementsAccessor::kCopyToEnd ||
            raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
     copy_size = from->max_number_key() + 1 - from_start;
 #ifdef DEBUG
-    // FAST_ELEMENT arrays cannot be uninitialized. Ensure they are already
+    // Fast object arrays cannot be uninitialized. Ensure they are already
     // marked with the hole.
     if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
       for (int i = to_start + copy_size; i < to->length(); ++i) {
         ASSERT(to->get(i)->IsTheHole());
       }
     }
 #endif
   }
   ASSERT(to != from);
-  ASSERT(to_kind == FAST_ELEMENTS || to_kind == FAST_SMI_ONLY_ELEMENTS);
+  ASSERT(IsFastSmiOrObjectElementsKind(to_kind));
   if (copy_size == 0) return;
   uint32_t to_length = to->length();
   if (to_start + copy_size > to_length) {
     copy_size = to_length - to_start;
   }
   for (int i = 0; i < copy_size; i++) {
     int entry = from->FindEntry(i + from_start);
     if (entry != SeededNumberDictionary::kNotFound) {
       Object* value = from->ValueAt(entry);
       ASSERT(!value->IsTheHole());
       to->set(i + to_start, value, SKIP_WRITE_BARRIER);
     } else {
       to->set_the_hole(i + to_start);
     }
   }
-  if (to_kind == FAST_ELEMENTS) {
+  if (IsFastObjectElementsKind(to_kind)) {
     if (!heap->InNewSpace(to)) {
       heap->RecordWrites(to->address(),
                          to->OffsetOfElementAt(to_start),
                          copy_size);
     }
     heap->incremental_marking()->RecordWrites(to);
   }
 }
 
 
 MUST_USE_RESULT static MaybeObject* CopyDoubleToObjectElements(
     FixedDoubleArray* from,
     uint32_t from_start,
     FixedArray* to,
     ElementsKind to_kind,
     uint32_t to_start,
     int raw_copy_size) {
-  ASSERT(to_kind == FAST_ELEMENTS || to_kind == FAST_SMI_ONLY_ELEMENTS);
+  ASSERT(IsFastSmiOrObjectElementsKind(to_kind));
   int copy_size = raw_copy_size;
   if (raw_copy_size < 0) {
     ASSERT(raw_copy_size == ElementsAccessor::kCopyToEnd ||
            raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole);
     copy_size = Min(from->length() - from_start,
                     to->length() - to_start);
 #ifdef DEBUG
-    // FAST_ELEMENT arrays cannot be uninitialized. Ensure they are already
+    // FAST_*_ELEMENTS arrays cannot be uninitialized. Ensure they are already
     // marked with the hole.
     if (raw_copy_size == ElementsAccessor::kCopyToEndAndInitializeToHole) {
       for (int i = to_start + copy_size; i < to->length(); ++i) {
         ASSERT(to->get(i)->IsTheHole());
       }
     }
 #endif
   }
   ASSERT((copy_size + static_cast<int>(to_start)) <= to->length() &&
          (copy_size + static_cast<int>(from_start)) <= from->length());
   if (copy_size == 0) return from;
   for (int i = 0; i < copy_size; ++i) {
-    if (to_kind == FAST_SMI_ONLY_ELEMENTS) {
+    if (IsFastSmiElementsKind(to_kind)) {
       UNIMPLEMENTED();
       return Failure::Exception();
     } else {
       MaybeObject* maybe_value = from->get(i + from_start);
       Object* value;
-      ASSERT(to_kind == FAST_ELEMENTS);
-      // Because FAST_DOUBLE_ELEMENTS -> FAST_ELEMENT allocate HeapObjects
+      ASSERT(IsFastObjectElementsKind(to_kind));
+      // Because Double -> Object elements transitions allocate HeapObjects
       // iteratively, the allocate must succeed within a single GC cycle,
       // otherwise the retry after the GC will also fail. In order to ensure
       // that no GC is triggered, allocate HeapNumbers from old space if they
       // can't be taken from new space.
       if (!maybe_value->ToObject(&value)) {
         ASSERT(maybe_value->IsRetryAfterGC() || maybe_value->IsOutOfMemory());
         Heap* heap = from->GetHeap();
         MaybeObject* maybe_value_object =
             heap->AllocateHeapNumber(from->get_scalar(i + from_start),
                                      TENURED);
@@ skipping 121 matching lines @@
 class ElementsAccessorBase : public ElementsAccessor {
  protected:
   explicit ElementsAccessorBase(const char* name)
       : ElementsAccessor(name) { }
 
   typedef ElementsTraitsParam ElementsTraits;
   typedef typename ElementsTraitsParam::BackingStore BackingStore;
 
   virtual ElementsKind kind() const { return ElementsTraits::Kind; }
 
+  static void ValidateContents(JSObject* holder, int length) {
+  }
+
+  static void ValidateImpl(JSObject* holder) {
+    FixedArrayBase* fixed_array_base = holder->elements();
+    // When objects are first allocated, its elements are Failures.
+    if (fixed_array_base->IsFailure()) return;
+    if (!fixed_array_base->IsHeapObject()) return;
+    Map* map = fixed_array_base->map();
+    // Arrays that have been shifted in place can't be verified.
+    Heap* heap = holder->GetHeap();
+    if (map == heap->raw_unchecked_one_pointer_filler_map() ||
+        map == heap->raw_unchecked_two_pointer_filler_map() ||
+        map == heap->free_space_map()) {
+      return;
+    }
+    int length = 0;
+    if (holder->IsJSArray()) {
+      Object* length_obj = JSArray::cast(holder)->length();
+      if (length_obj->IsSmi()) {
+        length = Smi::cast(length_obj)->value();
+      }
+    } else {
+      length = fixed_array_base->length();
+    }
+    ElementsAccessorSubclass::ValidateContents(holder, length);
+  }
+
+  virtual void Validate(JSObject* holder) {
+    ElementsAccessorSubclass::ValidateImpl(holder);
+  }
+
   static bool HasElementImpl(Object* receiver,
                              JSObject* holder,
                              uint32_t key,
                              BackingStore* backing_store) {
     MaybeObject* element =
         ElementsAccessorSubclass::GetImpl(receiver, holder, key, backing_store);
     return !element->IsTheHole();
   }
 
   virtual bool HasElement(Object* receiver,
@@ skipping 30 matching lines @@
   virtual MaybeObject* SetLength(JSArray* array,
                                  Object* length) {
     return ElementsAccessorSubclass::SetLengthImpl(
         array, length, BackingStore::cast(array->elements()));
   }
 
   static MaybeObject* SetLengthImpl(JSObject* obj,
                                     Object* length,
                                     BackingStore* backing_store);
 
-  virtual MaybeObject* SetCapacityAndLength(JSArray* array,
-                                            int capacity,
-                                            int length) {
+  virtual MaybeObject* SetCapacityAndLength(

[Jakob Kummerow, 2012/05/13 21:55:27]

nit: both this and the following change seem unnecessary.

[danno, 2012/05/22 11:05:21]

Done.

+      JSArray* array,
+      int capacity,
+      int length) {
     return ElementsAccessorSubclass::SetFastElementsCapacityAndLength(
         array,
         capacity,
         length);
   }
 
-  static MaybeObject* SetFastElementsCapacityAndLength(JSObject* obj,
-                                                       int capacity,
-                                                       int length) {
+  static MaybeObject* SetFastElementsCapacityAndLength(
+      JSObject* obj,
+      int capacity,
+      int length) {
     UNIMPLEMENTED();
     return obj;
   }
 
   virtual MaybeObject* Delete(JSObject* obj,
                               uint32_t key,
                               JSReceiver::DeleteMode mode) = 0;
 
   static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                        uint32_t from_start,
@@ skipping 134 matching lines @@
          typename KindTraits,
          int ElementSize>
 class FastElementsAccessor
     : public ElementsAccessorBase<FastElementsAccessorSubclass, KindTraits> {
  public:
   explicit FastElementsAccessor(const char* name)
       : ElementsAccessorBase<FastElementsAccessorSubclass,
                              KindTraits>(name) {}
  protected:
   friend class ElementsAccessorBase<FastElementsAccessorSubclass, KindTraits>;
+  friend class NonStrictArgumentsElementsAccessor;
 
   typedef typename KindTraits::BackingStore BackingStore;
 
   // Adjusts the length of the fast backing store or returns the new length or
   // undefined in case conversion to a slow backing store should be performed.
   static MaybeObject* SetLengthWithoutNormalize(BackingStore* backing_store,
                                                 JSArray* array,
                                                 Object* length_object,
                                                 uint32_t length) {
     uint32_t old_capacity = backing_store->length();
+    Object* old_length = array->length();
+    bool same_size = old_length->IsSmi() &&
+        static_cast<uint32_t>(Smi::cast(old_length)->value()) == length;
+    ElementsKind kind = array->GetElementsKind();
+
+    if (!same_size && IsFastElementsKind(kind) &&
+        !IsFastHoleyElementsKind(kind)) {
+      kind = GetHoleyElementsKind(kind);
+      MaybeObject* maybe_obj = array->TransitionElementsKind(kind);
+      if (maybe_obj->IsFailure()) return maybe_obj;
+    }
 
     // Check whether the backing store should be shrunk.
     if (length <= old_capacity) {
-      if (array->HasFastTypeElements()) {
+      if (array->HasFastSmiOrObjectElements()) {
         MaybeObject* maybe_obj = array->EnsureWritableFastElements();
         if (!maybe_obj->To(&backing_store)) return maybe_obj;
       }
       if (2 * length <= old_capacity) {
         // If more than half the elements won't be used, trim the array.
         if (length == 0) {
           array->initialize_elements();
         } else {
           backing_store->set_length(length);
           Address filler_start = backing_store->address() +
@@ skipping 11 matching lines @@
       return length_object;
     }
 
     // Check whether the backing store should be expanded.
     uint32_t min = JSObject::NewElementsCapacity(old_capacity);
     uint32_t new_capacity = length > min ? length : min;
     if (!array->ShouldConvertToSlowElements(new_capacity)) {
       MaybeObject* result = FastElementsAccessorSubclass::
           SetFastElementsCapacityAndLength(array, new_capacity, length);
       if (result->IsFailure()) return result;
+      array->ValidateElements();
       return length_object;
     }
 
     // Request conversion to slow elements.
     return array->GetHeap()->undefined_value();
   }
-};
-
-
-class FastObjectElementsAccessor
-    : public FastElementsAccessor<FastObjectElementsAccessor,
-                                  ElementsKindTraits<FAST_ELEMENTS>,
-                                  kPointerSize> {
- public:
-  explicit FastObjectElementsAccessor(const char* name)
-      : FastElementsAccessor<FastObjectElementsAccessor,
-                             ElementsKindTraits<FAST_ELEMENTS>,
-                             kPointerSize>(name) {}
 
   static MaybeObject* DeleteCommon(JSObject* obj,
-                                   uint32_t key) {
-    ASSERT(obj->HasFastElements() ||
-           obj->HasFastSmiOnlyElements() ||
+                                   uint32_t key,
+                                   JSReceiver::DeleteMode mode) {
+    ASSERT(obj->HasFastSmiOrObjectElements() ||
+           obj->HasFastDoubleElements() ||
            obj->HasFastArgumentsElements());
+    typename KindTraits::BackingStore* backing_store =
+        KindTraits::BackingStore::cast(obj->elements());
     Heap* heap = obj->GetHeap();
-    FixedArray* backing_store = FixedArray::cast(obj->elements());
     if (backing_store->map() == heap->non_strict_arguments_elements_map()) {
-      backing_store = FixedArray::cast(backing_store->get(1));
+      backing_store =
+          KindTraits::BackingStore::cast(
+              FixedArray::cast(backing_store)->get(1));
     } else {
-      Object* writable;
-      MaybeObject* maybe = obj->EnsureWritableFastElements();
-      if (!maybe->ToObject(&writable)) return maybe;
-      backing_store = FixedArray::cast(writable);
+      ElementsKind kind = KindTraits::Kind;
+      if (IsFastPackedElementsKind(kind)) {
+        MaybeObject* transitioned =
+            obj->TransitionElementsKind(GetHoleyElementsKind(kind));
+        if (transitioned->IsFailure()) return transitioned;
+      }
+      if (IsFastSmiOrObjectElementsKind(KindTraits::Kind)) {
+        Object* writable;
+        MaybeObject* maybe = obj->EnsureWritableFastElements();
+        if (!maybe->ToObject(&writable)) return maybe;
+        backing_store = KindTraits::BackingStore::cast(writable);
+      }
     }
     uint32_t length = static_cast<uint32_t>(
         obj->IsJSArray()
         ? Smi::cast(JSArray::cast(obj)->length())->value()
         : backing_store->length());
     if (key < length) {
       backing_store->set_the_hole(key);
       // If an old space backing store is larger than a certain size and
       // has too few used values, normalize it.
       // To avoid doing the check on every delete we require at least
       // one adjacent hole to the value being deleted.
-      Object* hole = heap->the_hole_value();
       const int kMinLengthForSparsenessCheck = 64;
       if (backing_store->length() >= kMinLengthForSparsenessCheck &&
           !heap->InNewSpace(backing_store) &&
-          ((key > 0 && backing_store->get(key - 1) == hole) ||
-           (key + 1 < length && backing_store->get(key + 1) == hole))) {
+          ((key > 0 && backing_store->is_the_hole(key - 1)) ||
+           (key + 1 < length && backing_store->is_the_hole(key + 1)))) {
         int num_used = 0;
         for (int i = 0; i < backing_store->length(); ++i) {
-          if (backing_store->get(i) != hole) ++num_used;
+          if (!backing_store->is_the_hole(i)) ++num_used;
           // Bail out early if more than 1/4 is used.
           if (4 * num_used > backing_store->length()) break;
         }
         if (4 * num_used <= backing_store->length()) {
           MaybeObject* result = obj->NormalizeElements();
           if (result->IsFailure()) return result;
         }
       }
     }
     return heap->true_value();
   }
 
+  virtual MaybeObject* Delete(JSObject* obj,
+                              uint32_t key,
+                              JSReceiver::DeleteMode mode) {
+    return DeleteCommon(obj, key, mode);
+  }
+
+  static bool HasElementImpl(
+      Object* receiver,
+      JSObject* holder,
+      uint32_t key,
+      typename KindTraits::BackingStore* backing_store) {
+    return key < static_cast<uint32_t>(backing_store->length()) &&
+        !backing_store->is_the_hole(key);
+  }
+
+  static void ValidateContents(JSObject* holder, int length) {
+#if DEBUG
+    FixedArrayBase* elements = holder->elements();
+    Heap* heap = elements->GetHeap();
+    Map* map = elements->map();
+    ASSERT((IsFastSmiOrObjectElementsKind(KindTraits::Kind) &&
+            (map == heap->fixed_array_map() ||
+             map == heap->fixed_cow_array_map())) ||
+           (IsFastDoubleElementsKind(KindTraits::Kind) ==
+            ((map == heap->fixed_array_map() && length == 0) ||
+             map == heap->fixed_double_array_map())));
+    for (int i = 0; i < length; i++) {
+      typename KindTraits::BackingStore* backing_store =
+          KindTraits::BackingStore::cast(elements);
+      ASSERT((!IsFastSmiElementsKind(KindTraits::Kind) ||
+              static_cast<Object*>(backing_store->get(i))->IsSmi()) ||
+             (IsFastHoleyElementsKind(KindTraits::Kind) ==
+              backing_store->is_the_hole(i)));
+    }
+#endif
+  }
+};
+
+
+template<typename FastElementsAccessorSubclass,
+         typename KindTraits>
+class FastSmiOrObjectElementsAccessor
+    : public FastElementsAccessor<FastElementsAccessorSubclass,
+                                  KindTraits,
+                                  kPointerSize> {
+ public:
+  explicit FastSmiOrObjectElementsAccessor(const char* name)
+      : FastElementsAccessor<FastElementsAccessorSubclass,
+                             KindTraits,
+                             kPointerSize>(name) {}
+
   static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                        uint32_t from_start,
                                        FixedArrayBase* to,
                                        ElementsKind to_kind,
                                        uint32_t to_start,
                                        int copy_size) {
-    switch (to_kind) {
-      case FAST_SMI_ONLY_ELEMENTS:
-      case FAST_ELEMENTS: {
-        CopyObjectToObjectElements(
-            FixedArray::cast(from), ElementsTraits::Kind, from_start,
-            FixedArray::cast(to), to_kind, to_start, copy_size);
-        return from;
-      }
-      case FAST_DOUBLE_ELEMENTS:
-        CopyObjectToDoubleElements(
-            FixedArray::cast(from), from_start,
-            FixedDoubleArray::cast(to), to_start, copy_size);
-        return from;
-      default:
-        UNREACHABLE();
-    }
+    if (IsFastSmiOrObjectElementsKind(to_kind)) {
+      CopyObjectToObjectElements(
+          FixedArray::cast(from), KindTraits::Kind, from_start,
+          FixedArray::cast(to), to_kind, to_start, copy_size);
+    } else if (IsFastDoubleElementsKind(to_kind)) {
+      CopyObjectToDoubleElements(
+          FixedArray::cast(from), from_start,
+          FixedDoubleArray::cast(to), to_start, copy_size);
+    } else {
+      UNREACHABLE();
+     }

[Jakob Kummerow, 2012/05/13 21:55:27]

nit: indentation

[danno, 2012/05/22 11:05:21]

Done.

     return to->GetHeap()->undefined_value();
   }
 
 
-  static MaybeObject* SetFastElementsCapacityAndLength(JSObject* obj,
-                                                       uint32_t capacity,
-                                                       uint32_t length) {
-    JSObject::SetFastElementsCapacityMode set_capacity_mode =
-        obj->HasFastSmiOnlyElements()
+  static MaybeObject* SetFastElementsCapacityAndLength(
+      JSObject* obj,

[Jakob Kummerow, 2012/05/13 21:55:27]

nit: unnecessary formatting change?

[danno, 2012/05/22 11:05:21]

Done.

+      uint32_t capacity,
+      uint32_t length) {
+    JSObject::SetFastElementsCapacitySmiMode set_capacity_mode =
+        obj->HasFastSmiElements()
             ? JSObject::kAllowSmiOnlyElements
             : JSObject::kDontAllowSmiOnlyElements;
     return obj->SetFastElementsCapacityAndLength(capacity,
                                                  length,
                                                  set_capacity_mode);
   }
-
- protected:
-  friend class FastElementsAccessor<FastObjectElementsAccessor,
-                                    ElementsKindTraits<FAST_ELEMENTS>,
-                                    kPointerSize>;
-
-  virtual MaybeObject* Delete(JSObject* obj,
-                              uint32_t key,
-                              JSReceiver::DeleteMode mode) {
-    return DeleteCommon(obj, key);
-  }
 };
 
 
+class FastPackedSmiElementsAccessor
+    : public FastSmiOrObjectElementsAccessor<
+        FastPackedSmiElementsAccessor,
+        ElementsKindTraits<FAST_SMI_ELEMENTS> > {
+ public:
+  explicit FastPackedSmiElementsAccessor(const char* name)
+      : FastSmiOrObjectElementsAccessor<
+          FastPackedSmiElementsAccessor,
+          ElementsKindTraits<FAST_SMI_ELEMENTS> >(name) {}
+};
+

[Jakob Kummerow, 2012/05/13 21:55:27]

nit: two empty lines (several more times below)

[danno, 2012/05/22 11:05:21]

Done.

+class FastHoleySmiElementsAccessor
+    : public FastSmiOrObjectElementsAccessor<
+        FastHoleySmiElementsAccessor,
+        ElementsKindTraits<FAST_HOLEY_SMI_ELEMENTS> > {
+ public:
+  explicit FastHoleySmiElementsAccessor(const char* name)
+      : FastSmiOrObjectElementsAccessor<
+          FastHoleySmiElementsAccessor,
+          ElementsKindTraits<FAST_HOLEY_SMI_ELEMENTS> >(name) {}
+};
+
+class FastPackedObjectElementsAccessor
+    : public FastSmiOrObjectElementsAccessor<
+        FastPackedObjectElementsAccessor,
+        ElementsKindTraits<FAST_ELEMENTS> > {
+ public:
+  explicit FastPackedObjectElementsAccessor(const char* name)
+      : FastSmiOrObjectElementsAccessor<
+          FastPackedObjectElementsAccessor,
+          ElementsKindTraits<FAST_ELEMENTS> >(name) {}
+};
+
+class FastHoleyObjectElementsAccessor
+    : public FastSmiOrObjectElementsAccessor<
+        FastHoleyObjectElementsAccessor,
+        ElementsKindTraits<FAST_HOLEY_ELEMENTS> > {
+ public:
+  explicit FastHoleyObjectElementsAccessor(const char* name)
+      : FastSmiOrObjectElementsAccessor<
+          FastHoleyObjectElementsAccessor,
+          ElementsKindTraits<FAST_HOLEY_ELEMENTS> >(name) {}
+};
+
+template<typename FastElementsAccessorSubclass,
+         typename KindTraits>
 class FastDoubleElementsAccessor
-    : public FastElementsAccessor<FastDoubleElementsAccessor,
-                                  ElementsKindTraits<FAST_DOUBLE_ELEMENTS>,
+    : public FastElementsAccessor<FastElementsAccessorSubclass,
+                                  KindTraits,
                                   kDoubleSize> {
  public:
   explicit FastDoubleElementsAccessor(const char* name)
-      : FastElementsAccessor<FastDoubleElementsAccessor,
-                             ElementsKindTraits<FAST_DOUBLE_ELEMENTS>,
+      : FastElementsAccessor<FastElementsAccessorSubclass,
+                             KindTraits,
                              kDoubleSize>(name) {}
 
-  static MaybeObject* SetFastElementsCapacityAndLength(JSObject* obj,
-                                                       uint32_t capacity,
-                                                       uint32_t length) {
-    return obj->SetFastDoubleElementsCapacityAndLength(capacity, length);
+  static MaybeObject* SetFastElementsCapacityAndLength(

[Jakob Kummerow, 2012/05/13 21:55:27]

nit: yet more formatting changes

[danno, 2012/05/22 11:05:21]

Done.

+      JSObject* obj,
+      uint32_t capacity,
+      uint32_t length) {
+    return obj->SetFastDoubleElementsCapacityAndLength(capacity,
+                                                       length);
   }
 
  protected:
-  friend class ElementsAccessorBase<FastDoubleElementsAccessor,
-                                    ElementsKindTraits<FAST_DOUBLE_ELEMENTS> >;
-  friend class FastElementsAccessor<FastDoubleElementsAccessor,
-                                    ElementsKindTraits<FAST_DOUBLE_ELEMENTS>,
-                                    kDoubleSize>;
-
   static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                        uint32_t from_start,
                                        FixedArrayBase* to,
                                        ElementsKind to_kind,
                                        uint32_t to_start,
                                        int copy_size) {
     switch (to_kind) {
-      case FAST_SMI_ONLY_ELEMENTS:
+      case FAST_SMI_ELEMENTS:
       case FAST_ELEMENTS:
+      case FAST_HOLEY_SMI_ELEMENTS:
+      case FAST_HOLEY_ELEMENTS:
         return CopyDoubleToObjectElements(
             FixedDoubleArray::cast(from), from_start, FixedArray::cast(to),
             to_kind, to_start, copy_size);
       case FAST_DOUBLE_ELEMENTS:
+      case FAST_HOLEY_DOUBLE_ELEMENTS:
         CopyDoubleToDoubleElements(FixedDoubleArray::cast(from), from_start,
                                    FixedDoubleArray::cast(to),
                                    to_start, copy_size);
         return from;
       default:
         UNREACHABLE();
     }
     return to->GetHeap()->undefined_value();
   }
-
-  virtual MaybeObject* Delete(JSObject* obj,
-                              uint32_t key,
-                              JSReceiver::DeleteMode mode) {
-    int length = obj->IsJSArray()
-        ? Smi::cast(JSArray::cast(obj)->length())->value()
-        : FixedDoubleArray::cast(obj->elements())->length();
-    if (key < static_cast<uint32_t>(length)) {
-      FixedDoubleArray::cast(obj->elements())->set_the_hole(key);
-    }
-    return obj->GetHeap()->true_value();
-  }
-
-  static bool HasElementImpl(Object* receiver,
-                             JSObject* holder,
-                             uint32_t key,
-                             FixedDoubleArray* backing_store) {
-    return key < static_cast<uint32_t>(backing_store->length()) &&
-        !backing_store->is_the_hole(key);
-  }
 };
 
 
+class FastPackedDoubleElementsAccessor
+    : public FastDoubleElementsAccessor<
+  FastPackedDoubleElementsAccessor,

[Jakob Kummerow, 2012/05/13 21:55:27]

nit: indentation (same for FastHoleyDoubleElementsAccessor)

[danno, 2012/05/22 11:05:21]

Done.

+  ElementsKindTraits<FAST_DOUBLE_ELEMENTS> > {
+ public:
+  friend class ElementsAccessorBase<FastPackedDoubleElementsAccessor,
+                                    ElementsKindTraits<FAST_DOUBLE_ELEMENTS> >;
+  explicit FastPackedDoubleElementsAccessor(const char* name)
+      : FastDoubleElementsAccessor<
+    FastPackedDoubleElementsAccessor,

[Jakob Kummerow, 2012/05/13 21:55:27]

again

[danno, 2012/05/22 11:05:21]

Done.

+    ElementsKindTraits<FAST_DOUBLE_ELEMENTS> >(name) {}
+};
+
+class FastHoleyDoubleElementsAccessor
+    : public FastDoubleElementsAccessor<
+  FastHoleyDoubleElementsAccessor,
+  ElementsKindTraits<FAST_HOLEY_DOUBLE_ELEMENTS> > {
+ public:
+  friend class ElementsAccessorBase<
+    FastHoleyDoubleElementsAccessor,
+    ElementsKindTraits<FAST_HOLEY_DOUBLE_ELEMENTS> >;
+  explicit FastHoleyDoubleElementsAccessor(const char* name)
+      : FastDoubleElementsAccessor<
+    FastHoleyDoubleElementsAccessor,
+    ElementsKindTraits<FAST_HOLEY_DOUBLE_ELEMENTS> >(name) {}
+};
+
 // Super class for all external element arrays.
 template<typename ExternalElementsAccessorSubclass,
          ElementsKind Kind>
 class ExternalElementsAccessor
     : public ElementsAccessorBase<ExternalElementsAccessorSubclass,
                                   ElementsKindTraits<Kind> > {
  public:
   explicit ExternalElementsAccessor(const char* name)
       : ElementsAccessorBase<ExternalElementsAccessorSubclass,
                              ElementsKindTraits<Kind> >(name) {}
@@ skipping 240 matching lines @@
     return heap->true_value();
   }
 
   static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                        uint32_t from_start,
                                        FixedArrayBase* to,
                                        ElementsKind to_kind,
                                        uint32_t to_start,
                                        int copy_size) {
     switch (to_kind) {
-      case FAST_SMI_ONLY_ELEMENTS:
+      case FAST_SMI_ELEMENTS:
       case FAST_ELEMENTS:
+      case FAST_HOLEY_SMI_ELEMENTS:
+      case FAST_HOLEY_ELEMENTS:
         CopyDictionaryToObjectElements(
             SeededNumberDictionary::cast(from), from_start,
             FixedArray::cast(to), to_kind, to_start, copy_size);
         return from;
       case FAST_DOUBLE_ELEMENTS:
+      case FAST_HOLEY_DOUBLE_ELEMENTS:
         CopyDictionaryToDoubleElements(
             SeededNumberDictionary::cast(from), from_start,
             FixedDoubleArray::cast(to), to_start, copy_size);
         return from;
       default:
         UNREACHABLE();
     }
     return to->GetHeap()->undefined_value();
   }
 
@@ skipping 104 matching lines @@
     if (!probe->IsTheHole()) {
       // TODO(kmillikin): We could check if this was the last aliased
       // parameter, and revert to normal elements in that case.  That
       // would enable GC of the context.
       parameter_map->set_the_hole(key + 2);
     } else {
       FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
       if (arguments->IsDictionary()) {
         return DictionaryElementsAccessor::DeleteCommon(obj, key, mode);
       } else {
-        return FastObjectElementsAccessor::DeleteCommon(obj, key);
+        // It's difficult to access the version of DeleteCommon that is declared
+        // in the templatized super class, call the concrete implementation in
+        // the class for the most generalized ElementsKind subclass.
+        return FastHoleyObjectElementsAccessor::DeleteCommon(obj, key, mode);
       }
     }
     return obj->GetHeap()->true_value();
   }
 
   static MaybeObject* CopyElementsImpl(FixedArrayBase* from,
                                        uint32_t from_start,
                                        FixedArrayBase* to,
                                        ElementsKind to_kind,
                                        uint32_t to_start,
@@ skipping 43 matching lines @@
   }
 };
 
 
 ElementsAccessor* ElementsAccessor::ForArray(FixedArrayBase* array) {
   switch (array->map()->instance_type()) {
     case FIXED_ARRAY_TYPE:
       if (array->IsDictionary()) {
         return elements_accessors_[DICTIONARY_ELEMENTS];
       } else {
-        return elements_accessors_[FAST_ELEMENTS];
+        return elements_accessors_[FAST_HOLEY_ELEMENTS];
       }
     case EXTERNAL_BYTE_ARRAY_TYPE:
       return elements_accessors_[EXTERNAL_BYTE_ELEMENTS];
     case EXTERNAL_UNSIGNED_BYTE_ARRAY_TYPE:
       return elements_accessors_[EXTERNAL_UNSIGNED_BYTE_ELEMENTS];
     case EXTERNAL_SHORT_ARRAY_TYPE:
       return elements_accessors_[EXTERNAL_SHORT_ELEMENTS];
     case EXTERNAL_UNSIGNED_SHORT_ARRAY_TYPE:
       return elements_accessors_[EXTERNAL_UNSIGNED_SHORT_ELEMENTS];
     case EXTERNAL_INT_ARRAY_TYPE:
@@ skipping 90 matching lines @@
   if (!maybe_obj->To(&new_backing_store)) return maybe_obj;
   new_backing_store->set(0, length);
   { MaybeObject* result = array->SetContent(new_backing_store);
     if (result->IsFailure()) return result;
   }
   return array;
 }
 
 
 } }  // namespace v8::internal