Implement tracking and optimizations of packed arrays

src/objects.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 38 matching lines @@
 #include "vm-state-inl.h"
 
 #ifdef ENABLE_DISASSEMBLER
 #include "disasm.h"
 #include "disassembler.h"
 #endif
 
 namespace v8 {
 namespace internal {
 
-void PrintElementsKind(FILE* out, ElementsKind kind) {
-  ElementsAccessor* accessor = ElementsAccessor::ForKind(kind);
-  PrintF(out, "%s", accessor->name());
-}
-
 
 MUST_USE_RESULT static MaybeObject* CreateJSValue(JSFunction* constructor,
                                                   Object* value) {
   Object* result;
   { MaybeObject* maybe_result =
         constructor->GetHeap()->AllocateJSObject(constructor);
     if (!maybe_result->ToObject(&result)) return maybe_result;
   }
   JSValue::cast(result)->set_value(value);
   return result;
@@ skipping 462 matching lines @@
 bool JSObject::IsDirty() {
   Object* cons_obj = map()->constructor();
   if (!cons_obj->IsJSFunction())
     return true;
   JSFunction* fun = JSFunction::cast(cons_obj);
   if (!fun->shared()->IsApiFunction())
     return true;
   // If the object is fully fast case and has the same map it was
   // created with then no changes can have been made to it.
   return map() != fun->initial_map()
-      || !HasFastElements()
+      || !HasFastObjectElements()
       || !HasFastProperties();
 }
 
 
 Handle<Object> Object::GetProperty(Handle<Object> object,
                                    Handle<Object> receiver,
                                    LookupResult* result,
                                    Handle<String> key,
                                    PropertyAttributes* attributes) {
   Isolate* isolate = object->IsHeapObject()
@@ skipping 338 matching lines @@
       cs->set_second(heap->empty_string(), SKIP_WRITE_BARRIER);
       return result;
     }
     default:
       return this;
   }
 }
 
 
 bool String::MakeExternal(v8::String::ExternalStringResource* resource) {
-  // Externalizing twice leaks the external resource, so it's
-  // prohibited by the API.
+  // Externalizing twice leaks the external resource, so its prohibited by the

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

Why this change? Original version was correct.

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

Done.

+  // API.
   ASSERT(!this->IsExternalString());
 #ifdef DEBUG
   if (FLAG_enable_slow_asserts) {
     // Assert that the resource and the string are equivalent.
     ASSERT(static_cast<size_t>(this->length()) == resource->length());
     ScopedVector<uc16> smart_chars(this->length());
     String::WriteToFlat(this, smart_chars.start(), 0, this->length());
     ASSERT(memcmp(smart_chars.start(),
                   resource->data(),
                   resource->length() * sizeof(smart_chars[0])) == 0);
@@ skipping 143 matching lines @@
     }
     accumulator->Put('>');
   }
   return;
 }
 
 
 void JSObject::JSObjectShortPrint(StringStream* accumulator) {
   switch (map()->instance_type()) {
     case JS_ARRAY_TYPE: {
-      double length = JSArray::cast(this)->length()->Number();
+      double length = JSArray::cast(this)->length()->IsUndefined()
+          ? 0 :

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

nit: I'd put the colon on the next line, directly below the question mark.

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

Done.

+          JSArray::cast(this)->length()->Number();
       accumulator->Add("<JS Array[%u]>", static_cast<uint32_t>(length));
       break;
     }
     case JS_WEAK_MAP_TYPE: {
       accumulator->Add("<JS WeakMap>");
       break;
     }
     case JS_REGEXP_TYPE: {
       accumulator->Add("<JS RegExp>");
       break;
@@ skipping 1111 matching lines @@
 
 
 template <class T>
 static Handle<T> MaybeNull(T* p) {
   if (p == NULL) return Handle<T>::null();
   return Handle<T>(p);
 }
 
 
 Handle<Map> Map::FindTransitionedMap(MapHandleList* candidates) {
-  ElementsKind elms_kind = elements_kind();
-  if (elms_kind == FAST_DOUBLE_ELEMENTS) {
-    bool dummy = true;
-    Handle<Map> fast_map =
-        MaybeNull(LookupElementsTransitionMap(FAST_ELEMENTS, &dummy));
-    if (!fast_map.is_null() && ContainsMap(candidates, fast_map)) {
-      return fast_map;
+  ElementsKind kind = elements_kind();
+  Handle<Map> transitioned_map = Handle<Map>::null();
+  Handle<Map> current_map(this);
+  bool packed = IsFastPackedElementsKind(kind);
+  if (IsTransitionableFastElementsKind(kind)) {
+    while (CanTransitionToMoreGeneralFastElementsKind(kind, false)) {
+      kind = GetNextMoreGeneralFastElementsKind(kind, false);
+      bool dummy = true;
+      Handle<Map> maybe_transitioned_map =
+          MaybeNull(current_map->LookupElementsTransitionMap(kind, &dummy));
+      if (maybe_transitioned_map.is_null()) break;
+      if (ContainsMap(candidates, maybe_transitioned_map) &&
+          (packed || !IsFastPackedElementsKind(kind))) {
+        transitioned_map = maybe_transitioned_map;
+        if (!IsFastPackedElementsKind(kind)) packed = false;
+      }
+      current_map = maybe_transitioned_map;
     }
-    return Handle<Map>::null();
   }
-  if (elms_kind == FAST_SMI_ONLY_ELEMENTS) {
-    bool dummy = true;
-    Handle<Map> double_map =
-        MaybeNull(LookupElementsTransitionMap(FAST_DOUBLE_ELEMENTS, &dummy));
-    // In the current implementation, if the DOUBLE map doesn't exist, the
-    // FAST map can't exist either.
-    if (double_map.is_null()) return Handle<Map>::null();
-    Handle<Map> fast_map =
-        MaybeNull(double_map->LookupElementsTransitionMap(FAST_ELEMENTS,
-                                                          &dummy));
-    if (!fast_map.is_null() && ContainsMap(candidates, fast_map)) {
-      return fast_map;
-    }
-    if (ContainsMap(candidates, double_map)) return double_map;
-  }
-  return Handle<Map>::null();
+  return transitioned_map;
 }
 
+
 static Map* GetElementsTransitionMapFromDescriptor(Object* descriptor_contents,
                                                    ElementsKind elements_kind) {
   if (descriptor_contents->IsMap()) {
     Map* map = Map::cast(descriptor_contents);
     if (map->elements_kind() == elements_kind) {
       return map;
     }
     return NULL;
   }
 
@@ skipping 88 matching lines @@
     } else {
       if (safe_to_add_transition != NULL) {
         *safe_to_add_transition = false;
       }
     }
   }
   return NULL;
 }
 
 
-Map* Map::LookupElementsTransitionMap(ElementsKind elements_kind,
+Map* Map::LookupElementsTransitionMap(ElementsKind to_kind,
                                       bool* safe_to_add_transition) {
-  // Special case: indirect SMI->FAST transition (cf. comment in
-  // AddElementsTransition()).
-  if (this->elements_kind() == FAST_SMI_ONLY_ELEMENTS &&
-      elements_kind == FAST_ELEMENTS) {
-    Map* double_map = this->LookupElementsTransitionMap(FAST_DOUBLE_ELEMENTS,
-                                                        safe_to_add_transition);
-    if (double_map == NULL) return double_map;
-    return double_map->LookupElementsTransitionMap(FAST_ELEMENTS,
+  ElementsKind from_kind = elements_kind();
+  if (IsFastElementsKind(from_kind) && IsFastElementsKind(to_kind)) {
+    if (!IsMoreGeneralElementsKindTransition(from_kind, to_kind)) {
+      if (safe_to_add_transition) *safe_to_add_transition = false;
+      return NULL;
+    }
+    ElementsKind transitioned_from_kind =
+        GetNextMoreGeneralFastElementsKind(from_kind, false);
+
+
+    // If the transition is a single step in the transition sequence, fall
+    // through to looking it up and returning it. If it requires several steps,
+    // divide and conquer.
+    if (transitioned_from_kind != to_kind) {
+      // If the transition is several steps in the lattice, divide and conquer.
+      Map* from_map = LookupElementsTransitionMap(transitioned_from_kind,
+                                                  safe_to_add_transition);
+      if (from_map == NULL) return NULL;
+      return from_map->LookupElementsTransitionMap(to_kind,
                                                    safe_to_add_transition);
+    }
   }
   Object* descriptor_contents = GetDescriptorContents(
       elements_transition_sentinel_name(), safe_to_add_transition);
   if (descriptor_contents != NULL) {
     Map* maybe_transition_map =
         GetElementsTransitionMapFromDescriptor(descriptor_contents,
-                                               elements_kind);
+                                               to_kind);
     ASSERT(maybe_transition_map == NULL || maybe_transition_map->IsMap());
     return maybe_transition_map;
   }
   return NULL;
 }
 
 
-MaybeObject* Map::AddElementsTransition(ElementsKind elements_kind,
+MaybeObject* Map::AddElementsTransition(ElementsKind to_kind,
                                         Map* transitioned_map) {
-  // The map transition graph should be a tree, therefore the transition
-  // from SMI to FAST elements is not done directly, but by going through
-  // DOUBLE elements first.
-  if (this->elements_kind() == FAST_SMI_ONLY_ELEMENTS &&
-      elements_kind == FAST_ELEMENTS) {
-    bool safe_to_add = true;
-    Map* double_map = this->LookupElementsTransitionMap(
-        FAST_DOUBLE_ELEMENTS, &safe_to_add);
-    // This method is only called when safe_to_add_transition has been found
-    // to be true earlier.
-    ASSERT(safe_to_add);
+  ElementsKind from_kind = elements_kind();
+  if (IsFastElementsKind(from_kind) && IsFastElementsKind(to_kind)) {
+    ASSERT(IsMoreGeneralElementsKindTransition(from_kind, to_kind));
+    ElementsKind transitioned_from_kind =
+        GetNextMoreGeneralFastElementsKind(from_kind, false);
+    // The map transitions graph should be a tree, therefore transitions to
+    // ElementsKind that are not adjacent in the ElementsKind sequence are not
+    // done directly, but instead by going through intermediate ElementsKinds
+    // first.
+    if (to_kind != transitioned_from_kind) {
+      bool safe_to_add = true;
+      Map* intermediate_map = LookupElementsTransitionMap(
+          transitioned_from_kind, &safe_to_add);
+      // This method is only called when safe_to_add_transition has been found

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

nit: s/safe_to_add_transition/safe_to_add/

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

Done.

+      // to be true earlier.
+      ASSERT(safe_to_add);
 
-    if (double_map == NULL) {
-      MaybeObject* maybe_map = this->CopyDropTransitions();
-      if (!maybe_map->To(&double_map)) return maybe_map;
-      double_map->set_elements_kind(FAST_DOUBLE_ELEMENTS);
-      MaybeObject* maybe_double_transition = this->AddElementsTransition(
-          FAST_DOUBLE_ELEMENTS, double_map);
-      if (maybe_double_transition->IsFailure()) return maybe_double_transition;
+      if (intermediate_map == NULL) {
+        MaybeObject* maybe_map = CopyDropTransitions();
+        if (!maybe_map->To(&intermediate_map)) return maybe_map;
+        intermediate_map->set_elements_kind(transitioned_from_kind);
+        MaybeObject* maybe_transition = AddElementsTransition(
+            transitioned_from_kind, intermediate_map);
+        if (maybe_transition->IsFailure()) return maybe_transition;
+      }
+      return intermediate_map->AddElementsTransition(to_kind, transitioned_map);
     }
-    return double_map->AddElementsTransition(FAST_ELEMENTS, transitioned_map);
   }
 
   bool safe_to_add_transition = true;
   Object* descriptor_contents = GetDescriptorContents(
       elements_transition_sentinel_name(), &safe_to_add_transition);
   // This method is only called when safe_to_add_transition has been found
   // to be true earlier.
   ASSERT(safe_to_add_transition);
   MaybeObject* maybe_new_contents =
       AddElementsTransitionMapToDescriptor(descriptor_contents,
@@ skipping 30 matching lines @@
   ElementsKind from_kind = current_map->elements_kind();
 
   if (from_kind == to_kind) return current_map;
 
   // Only objects with FastProperties can have DescriptorArrays and can track
   // element-related maps. Also don't add descriptors to maps that are shared.
   bool safe_to_add_transition = HasFastProperties() &&
       !current_map->IsUndefined() &&
       !current_map->is_shared();
 
-  // Prevent long chains of DICTIONARY -> FAST_ELEMENTS maps caused by objects
+  // Prevent long chains of DICTIONARY -> FAST_*_ELEMENTS maps caused by objects
   // with elements that switch back and forth between dictionary and fast
-  // element mode.
-  if (from_kind == DICTIONARY_ELEMENTS && to_kind == FAST_ELEMENTS) {
+  // element modes.
+  if (from_kind == DICTIONARY_ELEMENTS &&
+      IsFastObjectElementsKind(to_kind)) {

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

Wouldn't it make sense to check for any FAST kind here? Not sure if it would
ever happen in practice, but we don't want long chains of e.g. DICTIONARY <->
FAST_SMI maps either.

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

Done.

     safe_to_add_transition = false;
   }
 
   if (safe_to_add_transition) {
     // It's only safe to manipulate the descriptor array if it would be
     // safe to add a transition.
     Map* maybe_transition_map = current_map->LookupElementsTransitionMap(
         to_kind, &safe_to_add_transition);
     if (maybe_transition_map != NULL) {
       return maybe_transition_map;
@@ skipping 1015 matching lines @@
   // Find the backing store.
   FixedArrayBase* array = FixedArrayBase::cast(elements());
   Map* old_map = array->map();
   bool is_arguments =
       (old_map == old_map->GetHeap()->non_strict_arguments_elements_map());
   if (is_arguments) {
     array = FixedArrayBase::cast(FixedArray::cast(array)->get(1));
   }
   if (array->IsDictionary()) return array;
 
-  ASSERT(HasFastElements() ||
-         HasFastSmiOnlyElements() ||
+  ASSERT(HasFastSmiOrObjectElements() ||
          HasFastDoubleElements() ||
          HasFastArgumentsElements());
   // Compute the effective length and allocate a new backing store.
   int length = IsJSArray()
       ? Smi::cast(JSArray::cast(this)->length())->value()
       : array->length();
   int old_capacity = 0;
   int used_elements = 0;
   GetElementsCapacityAndUsage(&old_capacity, &used_elements);
   SeededNumberDictionary* dictionary = NULL;
@@ skipping 14 matching lines @@
       } else {
         // Objects must be allocated in the old object space, since the
         // overall number of HeapNumbers needed for the conversion might
         // exceed the capacity of new space, and we would fail repeatedly
         // trying to convert the FixedDoubleArray.
         MaybeObject* maybe_value_object =
             GetHeap()->AllocateHeapNumber(double_array->get_scalar(i), TENURED);
         if (!maybe_value_object->ToObject(&value)) return maybe_value_object;
       }
     } else {
-      ASSERT(old_map->has_fast_elements() ||
-             old_map->has_fast_smi_only_elements());
+      ASSERT(old_map->has_fast_smi_or_object_elements());
       value = FixedArray::cast(array)->get(i);
     }
     PropertyDetails details = PropertyDetails(NONE, NORMAL);
     if (!value->IsTheHole()) {
       Object* result;
       MaybeObject* maybe_result =
           dictionary->AddNumberEntry(i, value, details);
       if (!maybe_result->ToObject(&result)) return maybe_result;
       dictionary = SeededNumberDictionary::cast(result);
     }
@@ skipping 466 matching lines @@
   if (IsJSProxy()) {
     return JSProxy::cast(this)->DeletePropertyWithHandler(name, mode);
   }
   return JSObject::cast(this)->DeleteProperty(name, mode);
 }
 
 
 bool JSObject::ReferencesObjectFromElements(FixedArray* elements,
                                             ElementsKind kind,
                                             Object* object) {
-  ASSERT(kind == FAST_ELEMENTS ||
+  ASSERT(IsFastObjectElementsKind(kind) ||
          kind == DICTIONARY_ELEMENTS);
-  if (kind == FAST_ELEMENTS) {
+  if (IsFastObjectElementsKind(kind)) {
     int length = IsJSArray()
         ? Smi::cast(JSArray::cast(this)->length())->value()
         : elements->length();
     for (int i = 0; i < length; ++i) {
       Object* element = elements->get(i);
       if (!element->IsTheHole() && element == object) return true;
     }
   } else {
     Object* key =
         SeededNumberDictionary::cast(elements)->SlowReverseLookup(object);
@@ skipping 31 matching lines @@
     case EXTERNAL_PIXEL_ELEMENTS:
     case EXTERNAL_BYTE_ELEMENTS:
     case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
     case EXTERNAL_SHORT_ELEMENTS:
     case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
     case EXTERNAL_INT_ELEMENTS:
     case EXTERNAL_UNSIGNED_INT_ELEMENTS:
     case EXTERNAL_FLOAT_ELEMENTS:
     case EXTERNAL_DOUBLE_ELEMENTS:
     case FAST_DOUBLE_ELEMENTS:
+    case FAST_HOLEY_DOUBLE_ELEMENTS:
       // Raw pixels and external arrays do not reference other
       // objects.
       break;
-    case FAST_SMI_ONLY_ELEMENTS:
+    case FAST_SMI_ELEMENTS:
+    case FAST_HOLEY_SMI_ELEMENTS:
       break;
     case FAST_ELEMENTS:
+    case FAST_HOLEY_ELEMENTS:
     case DICTIONARY_ELEMENTS: {
       FixedArray* elements = FixedArray::cast(this->elements());
       if (ReferencesObjectFromElements(elements, kind, obj)) return true;
       break;
     }
     case NON_STRICT_ARGUMENTS_ELEMENTS: {
       FixedArray* parameter_map = FixedArray::cast(elements());
       // Check the mapped parameters.
       int length = parameter_map->length();
       for (int i = 2; i < length; ++i) {
         Object* value = parameter_map->get(i);
         if (!value->IsTheHole() && value == obj) return true;
       }
       // Check the arguments.
       FixedArray* arguments = FixedArray::cast(parameter_map->get(1));
-      kind = arguments->IsDictionary() ? DICTIONARY_ELEMENTS : FAST_ELEMENTS;
+      kind = arguments->IsDictionary() ? DICTIONARY_ELEMENTS :
+          FAST_HOLEY_ELEMENTS;
       if (ReferencesObjectFromElements(arguments, kind, obj)) return true;
       break;
     }
   }
 
   // For functions check the context.
   if (IsJSFunction()) {
     // Get the constructor function for arguments array.
     JSObject* arguments_boilerplate =
         heap->isolate()->context()->global_context()->
@@ skipping 213 matching lines @@
   for (Object* current = this;
        current != heap->null_value();
        current = JSObject::cast(current)->GetPrototype()) {
     JSReceiver::cast(current)->LocalLookup(name, result);
     if (result->IsProperty()) return;
   }
   result->NotFound();
 }
 
 
-// Search object and it's prototype chain for callback properties.
+// Search object and its prototype chain for callback properties.
 void JSObject::LookupCallback(String* name, LookupResult* result) {
   Heap* heap = GetHeap();
   for (Object* current = this;
        current != heap->null_value() && current->IsJSObject();
        current = JSObject::cast(current)->GetPrototype()) {
     JSObject::cast(current)->LocalLookupRealNamedProperty(name, result);
     if (result->IsFound() && result->type() == CALLBACKS) return;
   }
   result->NotFound();
 }
@@ skipping 23 matching lines @@
   }
   return false;
 }
 
 
 MaybeObject* JSObject::DefineElementAccessor(uint32_t index,
                                              Object* getter,
                                              Object* setter,
                                              PropertyAttributes attributes) {
   switch (GetElementsKind()) {
-    case FAST_SMI_ONLY_ELEMENTS:
+    case FAST_SMI_ELEMENTS:
     case FAST_ELEMENTS:
     case FAST_DOUBLE_ELEMENTS:
+    case FAST_HOLEY_SMI_ELEMENTS:
+    case FAST_HOLEY_ELEMENTS:
+    case FAST_HOLEY_DOUBLE_ELEMENTS:
       break;
     case EXTERNAL_PIXEL_ELEMENTS:
     case EXTERNAL_BYTE_ELEMENTS:
     case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
     case EXTERNAL_SHORT_ELEMENTS:
     case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
     case EXTERNAL_INT_ELEMENTS:
     case EXTERNAL_UNSIGNED_INT_ELEMENTS:
     case EXTERNAL_FLOAT_ELEMENTS:
     case EXTERNAL_DOUBLE_ELEMENTS:
@@ skipping 96 matching lines @@
   accessors->SetComponents(getter, setter);
   return SetPropertyCallback(name, accessors, attributes);
 }
 
 
 bool JSObject::CanSetCallback(String* name) {
   ASSERT(!IsAccessCheckNeeded() ||
          GetIsolate()->MayNamedAccess(this, name, v8::ACCESS_SET));
 
   // Check if there is an API defined callback object which prohibits
-  // callback overwriting in this object or it's prototype chain.
+  // callback overwriting in this object or its prototype chain.
   // This mechanism is needed for instance in a browser setting, where
   // certain accessors such as window.location should not be allowed
   // to be overwritten because allowing overwriting could potentially
   // cause security problems.
   LookupResult callback_result(GetIsolate());
   LookupCallback(name, &callback_result);
   if (callback_result.IsProperty()) {
     Object* obj = callback_result.GetCallbackObject();
     if (obj->IsAccessorInfo() &&
         AccessorInfo::cast(obj)->prohibits_overwriting()) {
@@ skipping 301 matching lines @@
   }
 
   uint32_t index = 0;
   bool is_element = name->AsArrayIndex(&index);
 
   if (is_element) {
     if (IsJSArray()) return isolate->heap()->undefined_value();
 
     // Accessors overwrite previous callbacks (cf. with getters/setters).
     switch (GetElementsKind()) {
-      case FAST_SMI_ONLY_ELEMENTS:
+      case FAST_SMI_ELEMENTS:
       case FAST_ELEMENTS:
       case FAST_DOUBLE_ELEMENTS:
+      case FAST_HOLEY_SMI_ELEMENTS:
+      case FAST_HOLEY_ELEMENTS:
+      case FAST_HOLEY_DOUBLE_ELEMENTS:
         break;
       case EXTERNAL_PIXEL_ELEMENTS:
       case EXTERNAL_BYTE_ELEMENTS:
       case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
       case EXTERNAL_SHORT_ELEMENTS:
       case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
       case EXTERNAL_INT_ELEMENTS:
       case EXTERNAL_UNSIGNED_INT_ELEMENTS:
       case EXTERNAL_FLOAT_ELEMENTS:
       case EXTERNAL_DOUBLE_ELEMENTS:
@@ skipping 3832 matching lines @@
   PrintF("RelocInfo (size = %d)\n", relocation_size());
   for (RelocIterator it(this); !it.done(); it.next()) it.rinfo()->Print(out);
   PrintF(out, "\n");
 }
 #endif  // ENABLE_DISASSEMBLER
 
 
 MaybeObject* JSObject::SetFastElementsCapacityAndLength(
     int capacity,
     int length,
-    SetFastElementsCapacityMode set_capacity_mode) {
+    SetFastElementsCapacitySmiMode smi_mode) {
   Heap* heap = GetHeap();
   // We should never end in here with a pixel or external array.
   ASSERT(!HasExternalArrayElements());
 
   // Allocate a new fast elements backing store.
   FixedArray* new_elements;
   { MaybeObject* maybe = heap->AllocateFixedArrayWithHoles(capacity);
     if (!maybe->To(&new_elements)) return maybe;
   }
 
-  // Find the new map to use for this object if there is a map change.
-  Map* new_map = NULL;
-  if (elements()->map() != heap->non_strict_arguments_elements_map()) {
-    // The resized array has FAST_SMI_ONLY_ELEMENTS if the capacity mode forces
-    // it, or if it's allowed and the old elements array contained only SMIs.
-    bool has_fast_smi_only_elements =
-        (set_capacity_mode == kForceSmiOnlyElements) ||
-        ((set_capacity_mode == kAllowSmiOnlyElements) &&
-         (elements()->map()->has_fast_smi_only_elements() ||
-          elements() == heap->empty_fixed_array()));
-    ElementsKind elements_kind = has_fast_smi_only_elements
-        ? FAST_SMI_ONLY_ELEMENTS
-        : FAST_ELEMENTS;
-    MaybeObject* maybe = GetElementsTransitionMap(GetIsolate(), elements_kind);
-    if (!maybe->To(&new_map)) return maybe;
+  ElementsKind elements_kind = GetElementsKind();
+  ElementsKind new_elements_kind;
+  // The resized array has FAST_*_SMI_ELEMENTS if the capacity mode forces it,
+  // or if it's allowed and the old elements array contained only SMIs.
+  bool has_fast_smi_elements =
+      (smi_mode == kForceSmiOnlyElements) ||
+      ((smi_mode == kAllowSmiOnlyElements) && HasFastSmiElements());
+  if (has_fast_smi_elements) {
+    if (IsHoleyElementsKind(elements_kind)) {
+      new_elements_kind = FAST_HOLEY_SMI_ELEMENTS;
+    } else {
+      new_elements_kind = FAST_SMI_ELEMENTS;
+    }
+  } else {
+    if (IsHoleyElementsKind(elements_kind)) {
+      new_elements_kind = FAST_HOLEY_ELEMENTS;
+    } else {
+      new_elements_kind = FAST_ELEMENTS;
+    }
   }
-
   FixedArrayBase* old_elements = elements();
-  ElementsKind elements_kind = GetElementsKind();
   ElementsAccessor* accessor = ElementsAccessor::ForKind(elements_kind);
-  ElementsKind to_kind = (elements_kind == FAST_SMI_ONLY_ELEMENTS)
-      ? FAST_SMI_ONLY_ELEMENTS
-      : FAST_ELEMENTS;
-  //  int copy_size = Min(old_elements_raw->length(), new_elements->length());
-  accessor->CopyElements(this, new_elements, to_kind);
+  accessor->CopyElements(this, new_elements, new_elements_kind);
   if (elements_kind != NON_STRICT_ARGUMENTS_ELEMENTS) {
+    Map* new_map = map();
+    if (new_elements_kind != elements_kind) {
+      MaybeObject* maybe =
+          GetElementsTransitionMap(GetIsolate(), new_elements_kind);
+      if (!maybe->To(&new_map)) return maybe;
+    }
+    ValidateElements();
     set_map_and_elements(new_map, new_elements);
   } else {
     FixedArray* parameter_map = FixedArray::cast(old_elements);
     parameter_map->set(1, new_elements);
   }
 
   if (FLAG_trace_elements_transitions) {
     PrintElementsTransition(stdout, elements_kind, old_elements,
                             GetElementsKind(), new_elements);
   }
 
-  // Update the length if necessary.
   if (IsJSArray()) {
     JSArray::cast(this)->set_length(Smi::FromInt(length));
   }
-
   return new_elements;
 }
 
 
 MaybeObject* JSObject::SetFastDoubleElementsCapacityAndLength(
     int capacity,
     int length) {
   Heap* heap = GetHeap();
   // We should never end in here with a pixel or external array.
   ASSERT(!HasExternalArrayElements());
 
   FixedDoubleArray* elems;
   { MaybeObject* maybe_obj =
         heap->AllocateUninitializedFixedDoubleArray(capacity);
     if (!maybe_obj->To(&elems)) return maybe_obj;
   }
 
+  ElementsKind elements_kind = GetElementsKind();
+  ElementsKind new_elements_kind = elements_kind;
+  if (IsHoleyElementsKind(elements_kind)) {
+    new_elements_kind = FAST_HOLEY_DOUBLE_ELEMENTS;
+  } else {
+    new_elements_kind = FAST_DOUBLE_ELEMENTS;
+  }
+
   Map* new_map;
   { MaybeObject* maybe_obj =
-        GetElementsTransitionMap(heap->isolate(), FAST_DOUBLE_ELEMENTS);
+        GetElementsTransitionMap(heap->isolate(), new_elements_kind);
     if (!maybe_obj->To(&new_map)) return maybe_obj;
   }
 
   FixedArrayBase* old_elements = elements();
-  ElementsKind elements_kind = GetElementsKind();
   ElementsAccessor* accessor = ElementsAccessor::ForKind(elements_kind);
   accessor->CopyElements(this, elems, FAST_DOUBLE_ELEMENTS);
   if (elements_kind != NON_STRICT_ARGUMENTS_ELEMENTS) {
+    ValidateElements();
     set_map_and_elements(new_map, elems);
   } else {
     FixedArray* parameter_map = FixedArray::cast(old_elements);
     parameter_map->set(1, elems);
   }
 
   if (FLAG_trace_elements_transitions) {
     PrintElementsTransition(stdout, elements_kind, old_elements,
-                            FAST_DOUBLE_ELEMENTS, elems);
+                            GetElementsKind(), elems);
   }
 
   if (IsJSArray()) {
     JSArray::cast(this)->set_length(Smi::FromInt(length));
   }
 
   return this;
 }
 
 
@@ skipping 259 matching lines @@
     return HasElementWithInterceptor(this, index) ? INTERCEPTED_ELEMENT
                                                   : UNDEFINED_ELEMENT;
   }
 
   // Handle [] on String objects.
   if (this->IsStringObjectWithCharacterAt(index)) {
     return STRING_CHARACTER_ELEMENT;
   }
 
   switch (GetElementsKind()) {
-    case FAST_SMI_ONLY_ELEMENTS:
-    case FAST_ELEMENTS: {
+    case FAST_SMI_ELEMENTS:
+    case FAST_ELEMENTS:
+    case FAST_HOLEY_SMI_ELEMENTS:
+    case FAST_HOLEY_ELEMENTS: {
       uint32_t length = IsJSArray() ?
           static_cast<uint32_t>
               (Smi::cast(JSArray::cast(this)->length())->value()) :
           static_cast<uint32_t>(FixedArray::cast(elements())->length());
       if ((index < length) &&
           !FixedArray::cast(elements())->get(index)->IsTheHole()) {
         return FAST_ELEMENT;
       }
       break;
     }
-    case FAST_DOUBLE_ELEMENTS: {
+    case FAST_DOUBLE_ELEMENTS:
+    case FAST_HOLEY_DOUBLE_ELEMENTS: {
       uint32_t length = IsJSArray() ?
           static_cast<uint32_t>
               (Smi::cast(JSArray::cast(this)->length())->value()) :
           static_cast<uint32_t>(FixedDoubleArray::cast(elements())->length());
       if ((index < length) &&
           !FixedDoubleArray::cast(elements())->is_the_hole(index)) {
         return FAST_ELEMENT;
       }
       break;
     }
@@ skipping 263 matching lines @@
 }
 
 
 // Adding n elements in fast case is O(n*n).
 // Note: revisit design to have dual undefined values to capture absent
 // elements.
 MaybeObject* JSObject::SetFastElement(uint32_t index,
                                       Object* value,
                                       StrictModeFlag strict_mode,
                                       bool check_prototype) {
-  ASSERT(HasFastTypeElements() ||
+  ASSERT(HasFastSmiOrObjectElements() ||
          HasFastArgumentsElements());
 
   FixedArray* backing_store = FixedArray::cast(elements());
   if (backing_store->map() == GetHeap()->non_strict_arguments_elements_map()) {
     backing_store = FixedArray::cast(backing_store->get(1));
   } else {
     MaybeObject* maybe = EnsureWritableFastElements();
     if (!maybe->To(&backing_store)) return maybe;
   }
   uint32_t capacity = static_cast<uint32_t>(backing_store->length());
 
   if (check_prototype &&
       (index >= capacity || backing_store->get(index)->IsTheHole())) {
     bool found;
     MaybeObject* result = SetElementWithCallbackSetterInPrototypes(index,
                                                                    value,
                                                                    &found,
                                                                    strict_mode);
     if (found) return result;
   }
 
   uint32_t new_capacity = capacity;
   // Check if the length property of this object needs to be updated.
   uint32_t array_length = 0;
   bool must_update_array_length = false;
+  bool introduces_holes = true;
   if (IsJSArray()) {
     CHECK(JSArray::cast(this)->length()->ToArrayIndex(&array_length));
+    introduces_holes = index > array_length;
     if (index >= array_length) {
       must_update_array_length = true;
       array_length = index + 1;
     }
+  } else {
+    introduces_holes = index >= capacity;
   }
+
+  // If the array is growing, and it's not growth by a single element at the
+  // end, make sure that the ElementsKind is HOLEY.
+  ElementsKind elements_kind = GetElementsKind();
+  if (introduces_holes &&
+      IsFastElementsKind(elements_kind) &&
+      !IsFastHoleyElementsKind(elements_kind)) {
+    ElementsKind transitioned_kind = GetHoleyElementsKind(elements_kind);
+    MaybeObject* maybe = TransitionElementsKind(transitioned_kind);
+    if (maybe->IsFailure()) return maybe;
+  }
+
   // Check if the capacity of the backing store needs to be increased, or if
   // a transition to slow elements is necessary.
   if (index >= capacity) {
     bool convert_to_slow = true;
     if ((index - capacity) < kMaxGap) {
       new_capacity = NewElementsCapacity(index + 1);
       ASSERT(new_capacity > index);
       if (!ShouldConvertToSlowElements(new_capacity)) {
         convert_to_slow = false;
       }
     }
     if (convert_to_slow) {
       MaybeObject* result = NormalizeElements();
       if (result->IsFailure()) return result;
       return SetDictionaryElement(index, value, NONE, strict_mode,
                                   check_prototype);
     }
   }
   // Convert to fast double elements if appropriate.
-  if (HasFastSmiOnlyElements() && !value->IsSmi() && value->IsNumber()) {
+  if (HasFastSmiElements() && !value->IsSmi() && value->IsNumber()) {
     MaybeObject* maybe =
-        SetFastDoubleElementsCapacityAndLength(new_capacity, array_length);
+        SetFastDoubleElementsCapacityAndLength(new_capacity,
+                                               array_length);

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

nit: why the line break?

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

Done.

     if (maybe->IsFailure()) return maybe;
     FixedDoubleArray::cast(elements())->set(index, value->Number());
+    ValidateElements();
     return value;
   }
-  // Change elements kind from SMI_ONLY to generic FAST if necessary.
-  if (HasFastSmiOnlyElements() && !value->IsSmi()) {
+  // Change elements kind from Smi-only to generic FAST if necessary.
+  if (HasFastSmiElements() && !value->IsSmi()) {
     Map* new_map;
-    { MaybeObject* maybe_new_map = GetElementsTransitionMap(GetIsolate(),
-                                                            FAST_ELEMENTS);
-      if (!maybe_new_map->To(&new_map)) return maybe_new_map;
-    }
+    ElementsKind kind = HasFastHoleyElements()
+        ? FAST_HOLEY_ELEMENTS
+        : FAST_ELEMENTS;
+    MaybeObject* maybe_new_map = GetElementsTransitionMap(GetIsolate(),
+                                                          kind);
+    if (!maybe_new_map->To(&new_map)) return maybe_new_map;
+
     set_map(new_map);
-    if (FLAG_trace_elements_transitions) {

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

I don't see why you would remove this.

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

Because it's a dupe of the transition printing done in
SetFastElementsCapacityAndLength if it actually changes ElementsKind. 
On 2012/05/13 21:55:27, Jakob wrote:

-      PrintElementsTransition(stdout, FAST_SMI_ONLY_ELEMENTS, elements(),
-                              FAST_ELEMENTS, elements());
-    }
   }
   // Increase backing store capacity if that's been decided previously.
   if (new_capacity != capacity) {
     FixedArray* new_elements;
-    SetFastElementsCapacityMode set_capacity_mode =
-        value->IsSmi() && HasFastSmiOnlyElements()
+    SetFastElementsCapacitySmiMode smi_mode =
+        value->IsSmi() && HasFastSmiElements()
             ? kAllowSmiOnlyElements
             : kDontAllowSmiOnlyElements;
     { MaybeObject* maybe =
           SetFastElementsCapacityAndLength(new_capacity,
                                            array_length,
-                                           set_capacity_mode);
+                                           smi_mode);
       if (!maybe->To(&new_elements)) return maybe;
     }
     new_elements->set(index, value);
+#if DEBUG
+    ValidateElements();

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

Calls to ValidateElements() aren't wrapped in an #if DEBUG elsewhere (e.g. in
line 9420). Aren't they essentially no-ops in non-DEBUG mode anyway?

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

Done.

+#endif
     return value;
   }
+
   // Finally, set the new element and length.
   ASSERT(elements()->IsFixedArray());
   backing_store->set(index, value);
   if (must_update_array_length) {
     JSArray::cast(this)->set_length(Smi::FromInt(array_length));
   }
   return value;
 }
 
 
@@ skipping 103 matching lines @@
   }
 
   // Attempt to put this object back in fast case.
   if (ShouldConvertToFastElements()) {
     uint32_t new_length = 0;
     if (IsJSArray()) {
       CHECK(JSArray::cast(this)->length()->ToArrayIndex(&new_length));
     } else {
       new_length = dictionary->max_number_key() + 1;
     }
-    SetFastElementsCapacityMode set_capacity_mode = FLAG_smi_only_arrays
+    SetFastElementsCapacitySmiMode smi_mode = FLAG_smi_only_arrays
         ? kAllowSmiOnlyElements
         : kDontAllowSmiOnlyElements;
     bool has_smi_only_elements = false;
     bool should_convert_to_fast_double_elements =
         ShouldConvertToFastDoubleElements(&has_smi_only_elements);
     if (has_smi_only_elements) {
-      set_capacity_mode = kForceSmiOnlyElements;
+      smi_mode = kForceSmiOnlyElements;
     }
     MaybeObject* result = should_convert_to_fast_double_elements
-        ? SetFastDoubleElementsCapacityAndLength(new_length, new_length)
+        ? SetFastDoubleElementsCapacityAndLength(new_length,

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

nit: why the line break?

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

Done.

+                                                 new_length)
         : SetFastElementsCapacityAndLength(new_length,
                                            new_length,
-                                           set_capacity_mode);
+                                           smi_mode);
+    ValidateElements();
     if (result->IsFailure()) return result;
 #ifdef DEBUG
     if (FLAG_trace_normalization) {
       PrintF("Object elements are fast case again:\n");
       Print();
     }
 #endif
   }
   return value;
 }
@@ skipping 18 matching lines @@
     MaybeObject* result = SetElementWithCallbackSetterInPrototypes(index,
                                                                    value,
                                                                    &found,
                                                                    strict_mode);
     if (found) return result;
   }
 
   // If the value object is not a heap number, switch to fast elements and try
   // again.
   bool value_is_smi = value->IsSmi();
+  bool introduces_holes = true;
+  uint32_t length = elms_length;
+  if (IsJSArray()) {
+    CHECK(JSArray::cast(this)->length()->ToArrayIndex(&length));
+    introduces_holes = index > length;
+  } else {
+    introduces_holes = index >= elms_length;
+  }
+
   if (!value->IsNumber()) {
-    Object* obj;
-    uint32_t length = elms_length;
-    if (IsJSArray()) {
-      CHECK(JSArray::cast(this)->length()->ToArrayIndex(&length));
-    }
     MaybeObject* maybe_obj = SetFastElementsCapacityAndLength(
         elms_length,
         length,
         kDontAllowSmiOnlyElements);
-    if (!maybe_obj->ToObject(&obj)) return maybe_obj;
-    return SetFastElement(index,
-                          value,
-                          strict_mode,
-                          check_prototype);
+    if (maybe_obj->IsFailure()) return maybe_obj;
+    maybe_obj = SetFastElement(index, value, strict_mode, check_prototype);
+    if (maybe_obj->IsFailure()) return maybe_obj;
+    ValidateElements();
+    return maybe_obj;
   }
 
   double double_value = value_is_smi
       ? static_cast<double>(Smi::cast(value)->value())
       : HeapNumber::cast(value)->value();
 
+  // If the array is growing, and it's not growth by a single element at the
+  // end, make sure that the ElementsKind is HOLEY.
+  ElementsKind elements_kind = GetElementsKind();
+  if (introduces_holes && !IsFastHoleyElementsKind(elements_kind)) {
+    ElementsKind transitioned_kind = GetHoleyElementsKind(elements_kind);
+    MaybeObject* maybe = TransitionElementsKind(transitioned_kind);
+    if (maybe->IsFailure()) return maybe;
+  }
+
   // Check whether there is extra space in the fixed array.
   if (index < elms_length) {
     FixedDoubleArray* elms = FixedDoubleArray::cast(elements());
     elms->set(index, double_value);
     if (IsJSArray()) {
       // Update the length of the array if needed.
       uint32_t array_length = 0;
       CHECK(JSArray::cast(this)->length()->ToArrayIndex(&array_length));
       if (index >= array_length) {
         JSArray::cast(this)->set_length(Smi::FromInt(index + 1));
       }
     }
     return value;
   }
 
   // Allow gap in fast case.
   if ((index - elms_length) < kMaxGap) {
     // Try allocating extra space.
     int new_capacity = NewElementsCapacity(index+1);
     if (!ShouldConvertToSlowElements(new_capacity)) {
       ASSERT(static_cast<uint32_t>(new_capacity) > index);
-      Object* obj;
-      { MaybeObject* maybe_obj =
-            SetFastDoubleElementsCapacityAndLength(new_capacity,
-                                                   index + 1);
-        if (!maybe_obj->ToObject(&obj)) return maybe_obj;
-      }
+      MaybeObject* maybe_obj =
+          SetFastDoubleElementsCapacityAndLength(new_capacity, index + 1);
+      if (maybe_obj->IsFailure()) return maybe_obj;
       FixedDoubleArray::cast(elements())->set(index, double_value);
+      ValidateElements();
       return value;
     }
   }
 
   // Otherwise default to slow case.
   ASSERT(HasFastDoubleElements());
   ASSERT(map()->has_fast_double_elements());
   ASSERT(elements()->IsFixedDoubleArray());
   Object* obj;
   { MaybeObject* maybe_obj = NormalizeElements();
@@ skipping 123 matching lines @@
                                                     Object* value,
                                                     PropertyAttributes attr,
                                                     StrictModeFlag strict_mode,
                                                     bool check_prototype,
                                                     SetPropertyMode set_mode) {
   ASSERT(HasDictionaryElements() ||
          HasDictionaryArgumentsElements() ||
          (attr & (DONT_DELETE | DONT_ENUM | READ_ONLY)) == 0);
   Isolate* isolate = GetIsolate();
   switch (GetElementsKind()) {
-    case FAST_SMI_ONLY_ELEMENTS:
+    case FAST_SMI_ELEMENTS:
     case FAST_ELEMENTS:
+    case FAST_HOLEY_SMI_ELEMENTS:
+    case FAST_HOLEY_ELEMENTS:
       return SetFastElement(index, value, strict_mode, check_prototype);
     case FAST_DOUBLE_ELEMENTS:
+    case FAST_HOLEY_DOUBLE_ELEMENTS:
       return SetFastDoubleElement(index, value, strict_mode, check_prototype);
     case EXTERNAL_PIXEL_ELEMENTS: {
       ExternalPixelArray* pixels = ExternalPixelArray::cast(elements());
       return pixels->SetValue(index, value);
     }
     case EXTERNAL_BYTE_ELEMENTS: {
       ExternalByteArray* array = ExternalByteArray::cast(elements());
       return array->SetValue(index, value);
     }
     case EXTERNAL_UNSIGNED_BYTE_ELEMENTS: {
@@ skipping 70 matching lines @@
                                                 ElementsKind to_kind) {
   CALL_HEAP_FUNCTION(object->GetIsolate(),
                      object->TransitionElementsKind(to_kind),
                      Object);
 }
 
 
 MaybeObject* JSObject::TransitionElementsKind(ElementsKind to_kind) {
   ElementsKind from_kind = map()->elements_kind();
 
+  if (IsFastHoleyElementsKind(from_kind)) {
+    to_kind = GetHoleyElementsKind(to_kind);
+  }
+
   Isolate* isolate = GetIsolate();
-  if (from_kind == FAST_SMI_ONLY_ELEMENTS &&
-      (to_kind == FAST_ELEMENTS ||
-       elements() == isolate->heap()->empty_fixed_array())) {
+
+  if (elements() == isolate->heap()->empty_fixed_array() ||
+      (IsFastSmiOrObjectElementsKind(from_kind) &&
+       IsFastSmiOrObjectElementsKind(to_kind)) ||
+      (from_kind == FAST_DOUBLE_ELEMENTS &&
+       to_kind == FAST_HOLEY_DOUBLE_ELEMENTS)) {
+    // No change is needed to the elements() buffer, the transition
+    // only requires a map change.
     MaybeObject* maybe_new_map = GetElementsTransitionMap(isolate, to_kind);
     Map* new_map;
     if (!maybe_new_map->To(&new_map)) return maybe_new_map;
     set_map(new_map);
     if (FLAG_trace_elements_transitions) {
       FixedArrayBase* elms = FixedArrayBase::cast(elements());
       PrintElementsTransition(stdout, from_kind, elms, to_kind, elms);
     }
     return this;
   }
 
   FixedArrayBase* elms = FixedArrayBase::cast(elements());
   uint32_t capacity = static_cast<uint32_t>(elms->length());
   uint32_t length = capacity;
 
   if (IsJSArray()) {
     Object* raw_length = JSArray::cast(this)->length();
     if (raw_length->IsUndefined()) {
       // If length is undefined, then JSArray is being initialized and has no
       // elements, assume a length of zero.
       length = 0;
     } else {
       CHECK(JSArray::cast(this)->length()->ToArrayIndex(&length));
     }
   }
 
-  if (from_kind == FAST_SMI_ONLY_ELEMENTS &&
-      to_kind == FAST_DOUBLE_ELEMENTS) {
+  if (IsFastSmiElementsKind(from_kind) &&
+      IsFastDoubleElementsKind(to_kind)) {
     MaybeObject* maybe_result =
         SetFastDoubleElementsCapacityAndLength(capacity, length);
     if (maybe_result->IsFailure()) return maybe_result;
+    ValidateElements();
     return this;
   }
 
-  if (from_kind == FAST_DOUBLE_ELEMENTS && to_kind == FAST_ELEMENTS) {
+  if (IsFastDoubleElementsKind(from_kind) &&
+      IsFastObjectElementsKind(to_kind)) {
     MaybeObject* maybe_result = SetFastElementsCapacityAndLength(
         capacity, length, kDontAllowSmiOnlyElements);
     if (maybe_result->IsFailure()) return maybe_result;
+    ValidateElements();
     return this;
   }
 
   // This method should never be called for any other case than the ones
   // handled above.
   UNREACHABLE();
   return GetIsolate()->heap()->null_value();
 }
 
 
 // static
 bool Map::IsValidElementsTransition(ElementsKind from_kind,
                                     ElementsKind to_kind) {
-  return
-      (from_kind == FAST_SMI_ONLY_ELEMENTS &&
-          (to_kind == FAST_DOUBLE_ELEMENTS || to_kind == FAST_ELEMENTS)) ||
-      (from_kind == FAST_DOUBLE_ELEMENTS && to_kind == FAST_ELEMENTS);
+  // Transitions can't go backwards.
+  if (!IsMoreGeneralElementsKindTransition(from_kind, to_kind)) {
+    return false;
+  }
+
+  // Transitions from HOLEY -> PACKED are not allowed.
+  return !IsFastHoleyElementsKind(from_kind) ||
+      IsFastHoleyElementsKind(to_kind);
 }
 
 
 MaybeObject* JSArray::JSArrayUpdateLengthFromIndex(uint32_t index,
                                                    Object* value) {
   uint32_t old_len = 0;
   CHECK(length()->ToArrayIndex(&old_len));
   // Check to see if we need to update the length. For now, we make
   // sure that the length stays within 32-bits (unsigned).
   if (index >= old_len && index != 0xffffffff) {
@@ skipping 70 matching lines @@
           FixedArray::cast(FixedArray::cast(backing_store_base)->get(1));
       backing_store = FixedArray::cast(backing_store_base);
       if (backing_store->IsDictionary()) {
         SeededNumberDictionary* dictionary =
             SeededNumberDictionary::cast(backing_store);
         *capacity = dictionary->Capacity();
         *used = dictionary->NumberOfElements();
         break;
       }
       // Fall through.
-    case FAST_SMI_ONLY_ELEMENTS:
+    case FAST_SMI_ELEMENTS:
     case FAST_ELEMENTS:
+    case FAST_HOLEY_SMI_ELEMENTS:
+    case FAST_HOLEY_ELEMENTS:
       backing_store = FixedArray::cast(backing_store_base);
       *capacity = backing_store->length();
       for (int i = 0; i < *capacity; ++i) {
         if (!backing_store->get(i)->IsTheHole()) ++(*used);
       }
       break;
     case DICTIONARY_ELEMENTS: {
       SeededNumberDictionary* dictionary =
           SeededNumberDictionary::cast(FixedArray::cast(elements()));
       *capacity = dictionary->Capacity();
       *used = dictionary->NumberOfElements();
       break;
     }
-    case FAST_DOUBLE_ELEMENTS: {
+    case FAST_DOUBLE_ELEMENTS:
+    case FAST_HOLEY_DOUBLE_ELEMENTS: {
       FixedDoubleArray* elms = FixedDoubleArray::cast(elements());
       *capacity = elms->length();
       for (int i = 0; i < *capacity; i++) {
         if (!elms->is_the_hole(i)) ++(*used);
       }
       break;
     }
     case EXTERNAL_BYTE_ELEMENTS:
     case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
     case EXTERNAL_SHORT_ELEMENTS:
@@ skipping 249 matching lines @@
     if (!heap->isolate()->MayIndexedAccess(this, index, v8::ACCESS_HAS)) {
       heap->isolate()->ReportFailedAccessCheck(this, v8::ACCESS_HAS);
       return false;
     }
   }
 
   // Handle [] on String objects.
   if (this->IsStringObjectWithCharacterAt(index)) return true;
 
   switch (GetElementsKind()) {
-    case FAST_SMI_ONLY_ELEMENTS:
-    case FAST_ELEMENTS: {
-      uint32_t length = IsJSArray() ?
+    case FAST_SMI_ELEMENTS:
+    case FAST_ELEMENTS:
+    case FAST_HOLEY_SMI_ELEMENTS:
+    case FAST_HOLEY_ELEMENTS: {
+     uint32_t length = IsJSArray() ?
           static_cast<uint32_t>(
               Smi::cast(JSArray::cast(this)->length())->value()) :
           static_cast<uint32_t>(FixedArray::cast(elements())->length());
       return (index < length) &&
           !FixedArray::cast(elements())->get(index)->IsTheHole();
     }
-    case FAST_DOUBLE_ELEMENTS: {
+    case FAST_DOUBLE_ELEMENTS:
+    case FAST_HOLEY_DOUBLE_ELEMENTS: {
       uint32_t length = IsJSArray() ?
           static_cast<uint32_t>(
               Smi::cast(JSArray::cast(this)->length())->value()) :
           static_cast<uint32_t>(FixedDoubleArray::cast(elements())->length());
       return (index < length) &&
           !FixedDoubleArray::cast(elements())->is_the_hole(index);
       break;
     }
     case EXTERNAL_PIXEL_ELEMENTS: {
       ExternalPixelArray* pixels = ExternalPixelArray::cast(elements());
@@ skipping 179 matching lines @@
 }
 
 
 int JSObject::NumberOfLocalElements(PropertyAttributes filter) {
   return GetLocalElementKeys(NULL, filter);
 }
 
 
 int JSObject::NumberOfEnumElements() {
   // Fast case for objects with no elements.
-  if (!IsJSValue() && HasFastElements()) {
+  if (!IsJSValue() && HasFastObjectElements()) {
     uint32_t length = IsJSArray() ?
         static_cast<uint32_t>(
             Smi::cast(JSArray::cast(this)->length())->value()) :
         static_cast<uint32_t>(FixedArray::cast(elements())->length());
     if (length == 0) return 0;
   }
   // Compute the number of enumerable elements.
   return NumberOfLocalElements(static_cast<PropertyAttributes>(DONT_ENUM));
 }
 
 
 int JSObject::GetLocalElementKeys(FixedArray* storage,
                                   PropertyAttributes filter) {
   int counter = 0;
   switch (GetElementsKind()) {
-    case FAST_SMI_ONLY_ELEMENTS:
-    case FAST_ELEMENTS: {
+    case FAST_SMI_ELEMENTS:
+    case FAST_ELEMENTS:
+    case FAST_HOLEY_SMI_ELEMENTS:
+    case FAST_HOLEY_ELEMENTS: {
       int length = IsJSArray() ?
           Smi::cast(JSArray::cast(this)->length())->value() :
           FixedArray::cast(elements())->length();
       for (int i = 0; i < length; i++) {
         if (!FixedArray::cast(elements())->get(i)->IsTheHole()) {
           if (storage != NULL) {
             storage->set(counter, Smi::FromInt(i));
           }
           counter++;
         }
       }
       ASSERT(!storage || storage->length() >= counter);
       break;
     }
-    case FAST_DOUBLE_ELEMENTS: {
+    case FAST_DOUBLE_ELEMENTS:
+    case FAST_HOLEY_DOUBLE_ELEMENTS: {
       int length = IsJSArray() ?
           Smi::cast(JSArray::cast(this)->length())->value() :
           FixedDoubleArray::cast(elements())->length();
       for (int i = 0; i < length; i++) {
         if (!FixedDoubleArray::cast(elements())->is_the_hole(i)) {
           if (storage != NULL) {
             storage->set(counter, Smi::FromInt(i));
           }
           counter++;
         }
@@ skipping 912 matching lines @@
     // Convert to fast elements containing only the existing properties.
     // Ordering is irrelevant, since we are going to sort anyway.
     SeededNumberDictionary* dict = element_dictionary();
     if (IsJSArray() || dict->requires_slow_elements() ||
         dict->max_number_key() >= limit) {
       return PrepareSlowElementsForSort(limit);
     }
     // Convert to fast elements.
 
     Object* obj;
-    { MaybeObject* maybe_obj = GetElementsTransitionMap(GetIsolate(),
-                                                        FAST_ELEMENTS);
-      if (!maybe_obj->ToObject(&obj)) return maybe_obj;
-    }
+    MaybeObject* maybe_obj = GetElementsTransitionMap(GetIsolate(),
+                                                      FAST_HOLEY_ELEMENTS);
+    if (!maybe_obj->ToObject(&obj)) return maybe_obj;
     Map* new_map = Map::cast(obj);
 
     PretenureFlag tenure = heap->InNewSpace(this) ? NOT_TENURED: TENURED;
     Object* new_array;
     { MaybeObject* maybe_new_array =
           heap->AllocateFixedArray(dict->NumberOfElements(), tenure);
       if (!maybe_new_array->ToObject(&new_array)) return maybe_new_array;
     }
     FixedArray* fast_elements = FixedArray::cast(new_array);
     dict->CopyValuesTo(fast_elements);
+    ValidateElements();
 
-    set_map(new_map);
-    set_elements(fast_elements);
+    set_map_and_elements(new_map, fast_elements);
   } else if (HasExternalArrayElements()) {
     // External arrays cannot have holes or undefined elements.
     return Smi::FromInt(ExternalArray::cast(elements())->length());
   } else if (!HasFastDoubleElements()) {
     Object* obj;
     { MaybeObject* maybe_obj = EnsureWritableFastElements();
       if (!maybe_obj->ToObject(&obj)) return maybe_obj;
     }
   }
-  ASSERT(HasFastTypeElements() || HasFastDoubleElements());
+  ASSERT(HasFastSmiOrObjectElements() || HasFastDoubleElements());
 
   // Collect holes at the end, undefined before that and the rest at the
   // start, and return the number of non-hole, non-undefined values.
 
   FixedArrayBase* elements_base = FixedArrayBase::cast(this->elements());
   uint32_t elements_length = static_cast<uint32_t>(elements_base->length());
   if (limit > elements_length) {
     limit = elements_length ;
   }
   if (limit == 0) {
@@ skipping 1656 matching lines @@
   set_year(Smi::FromInt(year), SKIP_WRITE_BARRIER);
   set_month(Smi::FromInt(month), SKIP_WRITE_BARRIER);
   set_day(Smi::FromInt(day), SKIP_WRITE_BARRIER);
   set_weekday(Smi::FromInt(weekday), SKIP_WRITE_BARRIER);
   set_hour(Smi::FromInt(hour), SKIP_WRITE_BARRIER);
   set_min(Smi::FromInt(min), SKIP_WRITE_BARRIER);
   set_sec(Smi::FromInt(sec), SKIP_WRITE_BARRIER);
 }
 
 } }  // namespace v8::internal