Promoting elements transitions to their own field.

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 610 matching lines @@
       return result->holder()->GetPropertyWithCallback(
           receiver, result->GetCallbackObject(), name);
     case HANDLER:
       return result->proxy()->GetPropertyWithHandler(receiver, name);
     case INTERCEPTOR: {
       JSObject* recvr = JSObject::cast(receiver);
       return result->holder()->GetPropertyWithInterceptor(
           recvr, name, attributes);
     }
     case MAP_TRANSITION:
-    case ELEMENTS_TRANSITION:
     case CONSTANT_TRANSITION:
     case NULL_DESCRIPTOR:
       break;
   }
   UNREACHABLE();
   return NULL;
 }
 
 
 MaybeObject* Object::GetElementWithReceiver(Object* receiver, uint32_t index) {
@@ skipping 902 matching lines @@
     }
   }
 
   // Only allow map transition if the object isn't the global object and there
   // is not a transition for the name, or there's a transition for the name but
   // it's unrelated to properties.
   int descriptor_index = old_descriptors->Search(name);
 
   // Element transitions are stored in the descriptor for property "", which is
   // not a identifier and should have forced a switch to slow properties above.
-  ASSERT(descriptor_index == DescriptorArray::kNotFound ||
-      old_descriptors->GetType(descriptor_index) != ELEMENTS_TRANSITION);
-  bool can_insert_transition = descriptor_index == DescriptorArray::kNotFound ||
-      old_descriptors->GetType(descriptor_index) == ELEMENTS_TRANSITION;
+  bool can_insert_transition = descriptor_index == DescriptorArray::kNotFound;
   bool allow_map_transition =
       can_insert_transition &&
       (isolate->context()->global_context()->object_function()->map() != map());
 
   ASSERT(index < map()->inobject_properties() ||
          (index - map()->inobject_properties()) < properties()->length() ||
          map()->unused_property_fields() == 0);
   // Allocate a new map for the object.
   Object* r;
   { MaybeObject* maybe_r = map()->CopyDropDescriptors();
     if (!maybe_r->ToObject(&r)) return maybe_r;
   }
   Map* new_map = Map::cast(r);
   if (allow_map_transition) {
     // Allocate new instance descriptors for the old map with map transition.
     MapTransitionDescriptor d(name, Map::cast(new_map), attributes);
     Object* r;
-    { MaybeObject* maybe_r = old_descriptors->CopyInsert(&d, KEEP_TRANSITIONS);
+    {

[danno, 2012/06/01 13:49:55]

nit: No need for this whitespace change.

[Toon Verwaest, 2012/06/04 09:17:48]

Done.

+      MaybeObject* maybe_r = old_descriptors->CopyInsert(&d, KEEP_TRANSITIONS);
       if (!maybe_r->ToObject(&r)) return maybe_r;
     }
     old_descriptors = DescriptorArray::cast(r);
   }
 
   if (map()->unused_property_fields() == 0) {
     if (properties()->length() > MaxFastProperties()) {
       Object* obj;
       { MaybeObject* maybe_obj =
             NormalizeProperties(CLEAR_INOBJECT_PROPERTIES, 0);
         if (!maybe_obj->ToObject(&obj)) return maybe_obj;
       }
       return AddSlowProperty(name, value, attributes);
     }
     // Make room for the new value
     Object* values;
     { MaybeObject* maybe_values =
           properties()->CopySize(properties()->length() + kFieldsAdded);
       if (!maybe_values->ToObject(&values)) return maybe_values;
     }
     set_properties(FixedArray::cast(values));
     new_map->set_unused_property_fields(kFieldsAdded - 1);
   } else {
     new_map->set_unused_property_fields(map()->unused_property_fields() - 1);
   }
   // We have now allocated all the necessary objects.
   // All the changes can be applied at once, so they are atomic.
-  map()->set_instance_descriptors(old_descriptors);
+  if (allow_map_transition) {
+    map()->set_instance_descriptors(old_descriptors);
+  }
   new_map->SetBackPointer(map());
   new_map->set_instance_descriptors(DescriptorArray::cast(new_descriptors));
   set_map(new_map);
   return FastPropertyAtPut(index, value);
 }
 
 
 MaybeObject* JSObject::AddConstantFunctionProperty(
     String* name,
     JSFunction* function,
@@ skipping 585 matching lines @@
 
 
 Handle<Map> Map::FindTransitionedMap(MapHandleList* candidates) {
   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));
+          MaybeNull(current_map->LookupElementsTransitionMap(kind));
       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 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;
+static Map* FindClosestElementsTransition(Map* map, ElementsKind to_kind) {
+  Map* current_map = map;
+  int index = GetSequenceIndexFromFastElementsKind(map->elements_kind());
+  int to_index = GetSequenceIndexFromFastElementsKind(to_kind);
+  for (; index < to_index; ++index) {
+    Map* next_map = current_map->elements_transition();
+    if (next_map == NULL) {
+      return current_map;
     }
-    return NULL;
+    current_map = next_map;
   }
-
-  FixedArray* map_array = FixedArray::cast(descriptor_contents);
-  for (int i = 0; i < map_array->length(); ++i) {
-    Object* current = map_array->get(i);
-    // Skip undefined slots, they are sentinels for reclaimed maps.
-    if (!current->IsUndefined()) {
-      Map* current_map = Map::cast(map_array->get(i));
-      if (current_map->elements_kind() == elements_kind) {
-        return current_map;
-      }
-    }
-  }
-
-  return NULL;
+  ASSERT(current_map->elements_kind() == to_kind);
+  return current_map;
 }
 
 
-static MaybeObject* AddElementsTransitionMapToDescriptor(
-    Object* descriptor_contents,
-    Map* new_map) {
-  // Nothing was in the descriptor for an ELEMENTS_TRANSITION,
-  // simply add the map.
-  if (descriptor_contents == NULL) {
-    return new_map;
-  }
-
-  // There was already a map in the descriptor, create a 2-element FixedArray
-  // to contain the existing map plus the new one.
-  FixedArray* new_array;
-  Heap* heap = new_map->GetHeap();
-  if (descriptor_contents->IsMap()) {
-    // Must tenure, DescriptorArray expects no new-space objects.
-    MaybeObject* maybe_new_array = heap->AllocateFixedArray(2, TENURED);
-    if (!maybe_new_array->To<FixedArray>(&new_array)) {
-      return maybe_new_array;
-    }
-    new_array->set(0, descriptor_contents);
-    new_array->set(1, new_map);
-    return new_array;
-  }
-
-  // The descriptor already contained a list of maps for different ElementKinds
-  // of ELEMENTS_TRANSITION, first check the existing array for an undefined
-  // slot, and if that's not available, create a FixedArray to hold the existing
-  // maps plus the new one and fill it in.
-  FixedArray* array = FixedArray::cast(descriptor_contents);
-  for (int i = 0; i < array->length(); ++i) {
-    if (array->get(i)->IsUndefined()) {
-      array->set(i, new_map);
-      return array;
-    }
-  }
-
-  // Must tenure, DescriptorArray expects no new-space objects.
-  MaybeObject* maybe_new_array =
-      heap->AllocateFixedArray(array->length() + 1, TENURED);
-  if (!maybe_new_array->To<FixedArray>(&new_array)) {
-    return maybe_new_array;
-  }
-  int i = 0;
-  while (i < array->length()) {
-    new_array->set(i, array->get(i));
-    ++i;
-  }
-  new_array->set(i, new_map);
-  return new_array;
-}
-
-
-String* Map::elements_transition_sentinel_name() {
-  return GetHeap()->empty_symbol();
-}
-
-
-Object* Map::GetDescriptorContents(String* sentinel_name,
-                                   bool* safe_to_add_transition) {
-  // Get the cached index for the descriptors lookup, or find and cache it.
-  DescriptorArray* descriptors = instance_descriptors();
-  DescriptorLookupCache* cache = GetIsolate()->descriptor_lookup_cache();
-  int index = cache->Lookup(descriptors, sentinel_name);
-  if (index == DescriptorLookupCache::kAbsent) {
-    index = descriptors->Search(sentinel_name);
-    cache->Update(descriptors, sentinel_name, index);
-  }
-  // If the transition already exists, return its descriptor.
-  if (index != DescriptorArray::kNotFound) {
-    PropertyDetails details = descriptors->GetDetails(index);
-    if (details.type() == ELEMENTS_TRANSITION) {
-      return descriptors->GetValue(index);
-    } else {
-      if (safe_to_add_transition != NULL) {
-        *safe_to_add_transition = false;
-      }
+Map* Map::LookupElementsTransitionMap(ElementsKind to_kind) {
+  if (this->instance_descriptors()->MayContainTransitions() &&
+      IsMoreGeneralElementsKindTransition(this->elements_kind(), to_kind)) {
+    Map* to_map = FindClosestElementsTransition(this, to_kind);
+    if (to_map->elements_kind() == to_kind) {
+      return to_map;
     }
   }
   return NULL;
 }
 
 
-Map* Map::LookupElementsTransitionMap(ElementsKind to_kind,
-                                      bool* safe_to_add_transition) {
-  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);
+MaybeObject* Map::CreateNextElementsTransition(ElementsKind next_kind) {
+    ASSERT(elements_transition() == NULL);
+    ASSERT(GetSequenceIndexFromFastElementsKind(elements_kind()) ==
+           (GetSequenceIndexFromFastElementsKind(next_kind) - 1));
 
+    Map* next_map;
+    MaybeObject* maybe_next_map = this->CopyDropTransitions(true);
+    if (!maybe_next_map->To(&next_map)) return maybe_next_map;
 
-    // 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,
-                                               to_kind);
-    ASSERT(maybe_transition_map == NULL || maybe_transition_map->IsMap());
-    return maybe_transition_map;
-  }
-  return NULL;
+    next_map->set_elements_kind(next_kind);
+    next_map->SetBackPointer(this);
+    this->set_elements_transition(next_map);
+    return next_map;
 }
 
 
-MaybeObject* Map::AddElementsTransition(ElementsKind to_kind,
-                                        Map* transitioned_map) {
-  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 has been found to be true
-      // earlier.
-      ASSERT(safe_to_add);
+static MaybeObject* AddMissingElementsTransitions(Map* map,
+                                                  ElementsKind to_kind) {
+  int index = GetSequenceIndexFromFastElementsKind(map->elements_kind()) + 1;
+  int to_index = GetSequenceIndexFromFastElementsKind(to_kind);
+  ASSERT(index <= to_index);
 
-      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);
-    }
+  Map* current_map = map;
+
+  for (; index <= to_index; ++index) {
+      ElementsKind next_kind = GetFastElementsKindFromSequenceIndex(index);
+      MaybeObject* maybe_next_map =
+          current_map->CreateNextElementsTransition(next_kind);
+      if (!maybe_next_map->To(&current_map)) return maybe_next_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,
-                                           transitioned_map);
-  Object* new_contents;
-  if (!maybe_new_contents->ToObject(&new_contents)) {
-    return maybe_new_contents;
-  }
-
-  ElementsTransitionDescriptor desc(elements_transition_sentinel_name(),
-                                    new_contents);
-  Object* new_descriptors;
-  MaybeObject* maybe_new_descriptors =
-      instance_descriptors()->CopyInsert(&desc, KEEP_TRANSITIONS);
-  if (!maybe_new_descriptors->ToObject(&new_descriptors)) {
-    return maybe_new_descriptors;
-  }
-  set_instance_descriptors(DescriptorArray::cast(new_descriptors));
-  transitioned_map->SetBackPointer(this);
-  return this;
+  ASSERT(current_map->elements_kind() == to_kind);
+  return current_map;
 }
 
 
 Handle<Map> JSObject::GetElementsTransitionMap(Handle<JSObject> object,
                                                ElementsKind to_kind) {
   Isolate* isolate = object->GetIsolate();
   CALL_HEAP_FUNCTION(isolate,
                      object->GetElementsTransitionMap(isolate, to_kind),
                      Map);
 }
 
 
+// If the map is using the empty descriptor array, install a new empty
+// descriptor array that will contain an element transition.
+// TODO(verwaest) Goes away once the descriptor array is immutable.
+static MaybeObject* EnsureMayContainTransitions(Map* map) {
+  if (map->instance_descriptors()->MayContainTransitions()) return map;
+  DescriptorArray* descriptor_array;
+  MaybeObject* maybe_descriptor_array = DescriptorArray::Allocate(0, true);
+  if (!maybe_descriptor_array->To(&descriptor_array)) {
+    return maybe_descriptor_array;
+  }
+  map->set_instance_descriptors(descriptor_array);
+  return map;
+}
+
+
 MaybeObject* JSObject::GetElementsTransitionMapSlow(ElementsKind to_kind) {
-  Map* current_map = map();
-  ElementsKind from_kind = current_map->elements_kind();
+  Map* start_map = map();
+  ElementsKind from_kind = start_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
-  // with elements that switch back and forth between dictionary and fast
-  // element modes.
-  if (from_kind == DICTIONARY_ELEMENTS &&
-      IsFastElementsKind(to_kind)) {
-    safe_to_add_transition = false;
+  if (from_kind == to_kind) {
+    return start_map;
   }
 
-  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;
-    }
+  Context* global_context = GetIsolate()->context()->global_context();
+  bool allow_store_transition =
+       // Only remember the map transition if the object's map is NOT equal to

[danno, 2012/06/01 13:49:55]

nit: indentation

[Toon Verwaest, 2012/06/04 09:17:48]

Done.

+       // the global object_function's map and there is not an already existing
+       // non-matching element transition.
+       (global_context->object_function()->map() != map()) &&
+       !start_map->IsUndefined() && !start_map->is_shared() &&
+       // Only store fast element maps in ascending generality.
+       IsTransitionableFastElementsKind(from_kind) &&
+       IsFastElementsKind(to_kind) &&
+       IsMoreGeneralElementsKindTransition(from_kind, to_kind);
+
+  if (!allow_store_transition) {
+    // Create a new free-floating map only if we are not allowed to store it.
+    Map* new_map = NULL;
+    MaybeObject* maybe_new_map = start_map->CopyDropTransitions(false);
+    if (!maybe_new_map->To(&new_map)) return maybe_new_map;
+    new_map->set_elements_kind(to_kind);
+    return new_map;
   }
 
-  Map* new_map = NULL;
+  EnsureMayContainTransitions(start_map);
+  Map* closest_map = FindClosestElementsTransition(start_map, to_kind);
 
-  // No transition to an existing map for the given ElementsKind. Make a new
-  // one.
-  { MaybeObject* maybe_map = current_map->CopyDropTransitions();
-    if (!maybe_map->To(&new_map)) return maybe_map;
+  if (closest_map->elements_kind() == to_kind) {
+    return closest_map;
   }
 
-  new_map->set_elements_kind(to_kind);
-
-  // Only remember the map transition if the object's map is NOT equal to the
-  // global object_function's map and there is not an already existing
-  // non-matching element transition.
-  Context* global_context = GetIsolate()->context()->global_context();
-  bool allow_map_transition = safe_to_add_transition &&
-      (global_context->object_function()->map() != map());
-  if (allow_map_transition) {
-    MaybeObject* maybe_transition =
-        current_map->AddElementsTransition(to_kind, new_map);
-    if (maybe_transition->IsFailure()) return maybe_transition;
-  }
-  return new_map;
+  return AddMissingElementsTransitions(closest_map, to_kind);
 }
 
 
 void JSObject::LocalLookupRealNamedProperty(String* name,
                                             LookupResult* result) {
   if (IsJSGlobalProxy()) {
     Object* proto = GetPrototype();
     if (proto->IsNull()) return result->NotFound();
     ASSERT(proto->IsJSGlobalObject());
     // A GlobalProxy's prototype should always be a proper JSObject.
@@ skipping 498 matching lines @@
           JSFunction::cast(target_descriptors->GetValue(number));
       if (value == function) {
         set_map(target_map);
         return value;
       }
       // Otherwise, replace with a MAP_TRANSITION to a new map with a
       // FIELD, even if the value is a constant function.
       return ConvertDescriptorToFieldAndMapTransition(name, value, attributes);
     }
     case NULL_DESCRIPTOR:
-    case ELEMENTS_TRANSITION:
       return ConvertDescriptorToFieldAndMapTransition(name, value, attributes);
     case HANDLER:
       UNREACHABLE();
       return value;
   }
   UNREACHABLE();  // keep the compiler happy
   return value;
 }
 
 
@@ skipping 77 matching lines @@
       // Preserve the attributes of this existing property.
       attributes = result.GetAttributes();
       return ConvertDescriptorToField(name, value, attributes);
     case CALLBACKS:
     case INTERCEPTOR:
       // Override callback in clone
       return ConvertDescriptorToField(name, value, attributes);
     case CONSTANT_TRANSITION:
       // Replace with a MAP_TRANSITION to a new map with a FIELD, even
       // if the value is a function.
-      return ConvertDescriptorToFieldAndMapTransition(name, value, attributes);
     case NULL_DESCRIPTOR:
-    case ELEMENTS_TRANSITION:
       return ConvertDescriptorToFieldAndMapTransition(name, value, attributes);
     case HANDLER:
       UNREACHABLE();
   }
   UNREACHABLE();  // keep the compiler happy
   return value;
 }
 
 
 PropertyAttributes JSObject::GetPropertyAttributePostInterceptor(
@@ skipping 270 matching lines @@
         }
         MaybeObject* maybe_dictionary =
             dictionary->Add(descs->GetKey(i), value, details);
         if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;
         break;
       }
       case MAP_TRANSITION:
       case CONSTANT_TRANSITION:
       case NULL_DESCRIPTOR:
       case INTERCEPTOR:
-      case ELEMENTS_TRANSITION:
         break;
       case HANDLER:
       case NORMAL:
         UNREACHABLE();
         break;
     }
   }
 
   Heap* current_heap = GetHeap();
 
@@ skipping 765 matching lines @@
   { MaybeObject* maybe = NormalizeElements();
     if (!maybe->To<SeededNumberDictionary>(&dictionary)) return maybe;
   }
   ASSERT(HasDictionaryElements() || HasDictionaryArgumentsElements());
   // Make sure that we never go back to fast case.
   dictionary->set_requires_slow_elements();
 
   // Do a map transition, other objects with this map may still
   // be extensible.
   Map* new_map;
-  { MaybeObject* maybe = map()->CopyDropTransitions();
+  { MaybeObject* maybe = map()->CopyDropTransitions(false);

[danno, 2012/06/01 13:49:55]

This should be an enum rather than a bool, it's really difficult to see what the
parameter means at the usage site.

[Toon Verwaest, 2012/06/04 09:17:48]

Done.

     if (!maybe->To<Map>(&new_map)) return maybe;
   }
   new_map->set_is_extensible(false);
   set_map(new_map);
   ASSERT(!map()->is_extensible());
   return new_map;
 }
 
 
 // Tests for the fast common case for property enumeration:
@@ skipping 759 matching lines @@
   Map::cast(result)->set_inobject_properties(inobject_properties());
   Map::cast(result)->set_unused_property_fields(unused_property_fields());
 
   // If the map has pre-allocated properties always start out with a descriptor
   // array describing these properties.
   if (pre_allocated_property_fields() > 0) {
     ASSERT(constructor()->IsJSFunction());
     JSFunction* ctor = JSFunction::cast(constructor());
     Object* descriptors;
     { MaybeObject* maybe_descriptors =
-          ctor->initial_map()->instance_descriptors()->RemoveTransitions();
+          ctor->initial_map()->instance_descriptors()->RemoveTransitions(false);
       if (!maybe_descriptors->ToObject(&descriptors)) return maybe_descriptors;
     }
     Map::cast(result)->set_instance_descriptors(
         DescriptorArray::cast(descriptors));
     Map::cast(result)->set_pre_allocated_property_fields(
         pre_allocated_property_fields());
   }
   Map::cast(result)->set_bit_field(bit_field());
   Map::cast(result)->set_bit_field2(bit_field2());
   Map::cast(result)->set_bit_field3(bit_field3());
@@ skipping 32 matching lines @@
 #ifdef DEBUG
   if (FLAG_verify_heap && Map::cast(result)->is_shared()) {
     Map::cast(result)->SharedMapVerify();
   }
 #endif
 
   return result;
 }
 
 
-MaybeObject* Map::CopyDropTransitions() {
+MaybeObject* Map::CopyDropTransitions(bool mutable_transitions) {
   Object* new_map;
   { MaybeObject* maybe_new_map = CopyDropDescriptors();
     if (!maybe_new_map->ToObject(&new_map)) return maybe_new_map;
   }
   Object* descriptors;
   { MaybeObject* maybe_descriptors =
-        instance_descriptors()->RemoveTransitions();
+        instance_descriptors()->RemoveTransitions(mutable_transitions);
     if (!maybe_descriptors->ToObject(&descriptors)) return maybe_descriptors;
   }
   cast(new_map)->set_instance_descriptors(DescriptorArray::cast(descriptors));
   return new_map;
 }
 
 void Map::UpdateCodeCache(Handle<Map> map,
                           Handle<String> name,
                           Handle<Code> code) {
   Isolate* isolate = map->GetIsolate();
@@ skipping 45 matching lines @@
 
 // An iterator over all map transitions in an descriptor array, reusing the map
 // field of the contens array while it is running.
 class IntrusiveMapTransitionIterator {
  public:
   explicit IntrusiveMapTransitionIterator(DescriptorArray* descriptor_array)
       : descriptor_array_(descriptor_array) { }
 
   void Start() {
     ASSERT(!IsIterating());
-    if (HasDescriptors()) *DescriptorArrayHeader() = Smi::FromInt(0);
+    if (descriptor_array_->MayContainTransitions())

[danno, 2012/06/01 13:49:55]

This is confusing. What does descriptor iteration have to do with transition?
Perhaps another predicate name, even if it does the same thing? 

[Toon Verwaest, 2012/06/04 09:17:48]

As discussed offline, won't change since it is actually only related to
transitions, not so much to descriptors.

On 2012/06/01 13:49:55, danno wrote:

+      *DescriptorArrayHeader() = Smi::FromInt(0);
   }
 
   bool IsIterating() {
-    return HasDescriptors() && (*DescriptorArrayHeader())->IsSmi();
+    return descriptor_array_->MayContainTransitions() &&
+           (*DescriptorArrayHeader())->IsSmi();
   }
 
   Map* Next() {
     ASSERT(IsIterating());
     // Attention, tricky index manipulation ahead: Two consecutive indices are
     // assigned to each descriptor. Most descriptors directly advance to the
     // next descriptor by adding 2 to the index. The exceptions are the
     // CALLBACKS entries: An even index means we look at its getter, and an odd
     // index means we look at its setter.
     int raw_index = Smi::cast(*DescriptorArrayHeader())->value();
     int index = raw_index / 2;
     int number_of_descriptors = descriptor_array_->number_of_descriptors();
     while (index < number_of_descriptors) {
       PropertyDetails details(descriptor_array_->GetDetails(index));
       switch (details.type()) {
         case MAP_TRANSITION:
         case CONSTANT_TRANSITION:
-        case ELEMENTS_TRANSITION:
           // We definitely have a map transition.
           *DescriptorArrayHeader() = Smi::FromInt(raw_index + 2);
           return static_cast<Map*>(descriptor_array_->GetValue(index));
         case CALLBACKS: {
           // We might have a map transition in a getter or in a setter.
           AccessorPair* accessors =
               static_cast<AccessorPair*>(descriptor_array_->GetValue(index));
           Object* accessor;
           if ((raw_index & 1) == 0) {
             accessor = accessors->setter();
@@ skipping 13 matching lines @@
         case CONSTANT_FUNCTION:
         case HANDLER:
         case INTERCEPTOR:
         case NULL_DESCRIPTOR:
           // We definitely have no map transition.
           raw_index += 2;
           ++index;
           break;
       }
     }
+    if (index == descriptor_array_->number_of_descriptors()) {
+      Map* elements_transition = descriptor_array_->elements_transition();
+      if (elements_transition != NULL) {
+        *DescriptorArrayHeader() = Smi::FromInt(index + 1);
+        return elements_transition;
+      }
+    }
     *DescriptorArrayHeader() = descriptor_array_->GetHeap()->fixed_array_map();
     return NULL;
   }
 
  private:
-  bool HasDescriptors() {
-    return descriptor_array_->length() > DescriptorArray::kFirstIndex;
-  }
-
   Object** DescriptorArrayHeader() {
     return HeapObject::RawField(descriptor_array_, DescriptorArray::kMapOffset);
   }
 
   DescriptorArray* descriptor_array_;
 };
 
 
 // An iterator over all prototype transitions, reusing the map field of the
 // underlying array while it is running.
@@ skipping 668 matching lines @@
 bool FixedArray::IsEqualTo(FixedArray* other) {
   if (length() != other->length()) return false;
   for (int i = 0 ; i < length(); ++i) {
     if (get(i) != other->get(i)) return false;
   }
   return true;
 }
 #endif
 
 
-MaybeObject* DescriptorArray::Allocate(int number_of_descriptors) {
+MaybeObject* DescriptorArray::Allocate(int number_of_descriptors,
+                                       bool mutable_transition) {
   Heap* heap = Isolate::Current()->heap();
-  if (number_of_descriptors == 0) {
+  if (number_of_descriptors == 0 && !mutable_transition) {
     return heap->empty_descriptor_array();
   }
   // Allocate the array of keys.
   Object* array;
   { MaybeObject* maybe_array =
         heap->AllocateFixedArray(ToKeyIndex(number_of_descriptors));
     if (!maybe_array->ToObject(&array)) return maybe_array;
   }
   // Do not use DescriptorArray::cast on incomplete object.
   FixedArray* result = FixedArray::cast(array);
 
   result->set(kBitField3StorageIndex, Smi::FromInt(0));
+  result->set(kTransitionsIndex, Smi::FromInt(0));
   result->set(kEnumerationIndexIndex,
               Smi::FromInt(PropertyDetails::kInitialIndex));
   return result;
 }
 
 
 void DescriptorArray::SetEnumCache(FixedArray* bridge_storage,
                                    FixedArray* new_cache,
                                    Object* new_index_cache) {
   ASSERT(bridge_storage->length() >= kEnumCacheBridgeLength);
@@ skipping 83 matching lines @@
     // We are replacing an existing descriptor. We keep the enumeration index
     // of a visible property.
     keep_enumeration_index = true;
   } else if (remove_transitions) {
     // Replaced descriptor has been counted as removed if it is a transition
     // that will be replaced. Adjust count in this case.
     ++new_size;
   }
 
   DescriptorArray* new_descriptors;
-  { MaybeObject* maybe_result = Allocate(new_size);
+  { MaybeObject* maybe_result = Allocate(new_size, !remove_transitions);
     if (!maybe_result->To(&new_descriptors)) return maybe_result;
   }
 
   DescriptorArray::WhitenessWitness witness(new_descriptors);
 
   // Set the enumeration index in the descriptors and set the enumeration index
   // in the result.
   int enumeration_index = NextEnumerationIndex();
   if (!descriptor->ContainsTransition()) {
     if (keep_enumeration_index) {
       descriptor->SetEnumerationIndex(GetDetails(index).index());
     } else {
       descriptor->SetEnumerationIndex(enumeration_index);
       ++enumeration_index;
     }
   }
+  Map* old_elements_transition = elements_transition();
+  if ((!remove_transitions) && (old_elements_transition != NULL)) {
+    new_descriptors->set_elements_transition(old_elements_transition);
+  }
   new_descriptors->SetNextEnumerationIndex(enumeration_index);
 
   // Copy the descriptors, filtering out transitions and null descriptors,
   // and inserting or replacing a descriptor.
   int to_index = 0;
   int insertion_index = -1;
   int from_index = 0;
   while (from_index < number_of_descriptors()) {
     if (insertion_index < 0 &&
         InsertionPointFound(GetKey(from_index), descriptor->GetKey())) {
       insertion_index = to_index++;
       if (replacing) from_index++;
     } else {
       if (!(IsNullDescriptor(from_index) ||
             (remove_transitions && IsTransitionOnly(from_index)))) {
         MaybeObject* copy_result =
             new_descriptors->CopyFrom(to_index++, this, from_index, witness);
         if (copy_result->IsFailure()) return copy_result;
       }
       from_index++;
     }
   }
   if (insertion_index < 0) insertion_index = to_index++;
+
+  ASSERT(insertion_index < new_descriptors->number_of_descriptors());
   new_descriptors->Set(insertion_index, descriptor, witness);
 
   ASSERT(to_index == new_descriptors->number_of_descriptors());
   SLOW_ASSERT(new_descriptors->IsSortedNoDuplicates());
 
   return new_descriptors;
 }
 
 
-MaybeObject* DescriptorArray::RemoveTransitions() {
+MaybeObject* DescriptorArray::RemoveTransitions(bool mutable_transitions) {
   // Allocate the new descriptor array.
   int new_number_of_descriptors = 0;
   for (int i = 0; i < number_of_descriptors(); i++) {
     if (IsProperty(i)) new_number_of_descriptors++;
   }
   DescriptorArray* new_descriptors;
-  { MaybeObject* maybe_result = Allocate(new_number_of_descriptors);
+  { MaybeObject* maybe_result = Allocate(new_number_of_descriptors,
+                                         mutable_transitions);
     if (!maybe_result->To(&new_descriptors)) return maybe_result;
   }
 
   // Copy the content.
   DescriptorArray::WhitenessWitness witness(new_descriptors);
   int next_descriptor = 0;
   for (int i = 0; i < number_of_descriptors(); i++) {
     if (IsProperty(i)) {
       MaybeObject* copy_result =
           new_descriptors->CopyFrom(next_descriptor++, this, i, witness);
       if (copy_result->IsFailure()) return copy_result;
     }
   }
   ASSERT(next_descriptor == new_descriptors->number_of_descriptors());
 
   return new_descriptors;
 }
 
+
 // The whiteness witness is needed since sort will reshuffle the entries in the
 // descriptor array. If the descriptor array were to be were to be black, the
 // shuffling would move a slot that was already recorded as pointing into an
 // evacuation candidate. This would result in missing updates upon evacuation.
 void DescriptorArray::SortUnchecked(const WhitenessWitness& witness) {
   // In-place heap sort.
   int len = number_of_descriptors();
 
   // Bottom-up max-heap construction.
   // Index of the last node with children
@@ skipping 45 matching lines @@
 
 
 void DescriptorArray::Sort(const WhitenessWitness& witness) {
   SortUnchecked(witness);
   SLOW_ASSERT(IsSortedNoDuplicates());
 }
 
 
 int DescriptorArray::BinarySearch(String* name, int low, int high) {
   uint32_t hash = name->Hash();
+  int limit = high;
 
-  while (low <= high) {
+  ASSERT(low <= high);
+
+  while (low != high) {
     int mid = (low + high) / 2;
     String* mid_name = GetKey(mid);
     uint32_t mid_hash = mid_name->Hash();
 
-    if (mid_hash > hash) {
-      high = mid - 1;
-      continue;
+    if (mid_hash >= hash) {
+      high = mid;
+    } else {
+      low = mid + 1;
     }
-    if (mid_hash < hash) {
-      low = mid + 1;
-      continue;
-    }
-    // Found an element with the same hash-code.
-    ASSERT(hash == mid_hash);
-    // There might be more, so we find the first one and
-    // check them all to see if we have a match.
-    if (name == mid_name  && !IsNullDescriptor(mid)) return mid;
-    while ((mid > low) && (GetKey(mid - 1)->Hash() == hash)) mid--;
-    for (; (mid <= high) && (GetKey(mid)->Hash() == hash); mid++) {
-      if (GetKey(mid)->Equals(name) && !IsNullDescriptor(mid)) return mid;
-    }
-    break;
   }
+
+  for (; low <= limit && GetKey(low)->Hash() == hash; ++low) {
+    if (GetKey(low)->Equals(name) && !IsNullDescriptor(low))
+      return low;
+  }
+
   return kNotFound;
 }
 
 
 int DescriptorArray::LinearSearch(String* name, int len) {
   uint32_t hash = name->Hash();
   for (int number = 0; number < len; number++) {
     String* entry = GetKey(number);
-    if ((entry->Hash() == hash) &&
-        name->Equals(entry) &&
-        !IsNullDescriptor(number)) {
+    if (entry->Hash() > hash) break;
+    if (name->Equals(entry) && !IsNullDescriptor(number)) {
       return number;
     }
   }
   return kNotFound;
 }
 
 
 MaybeObject* AccessorPair::CopyWithoutTransitions() {
   Heap* heap = GetHeap();
   AccessorPair* copy;
@@ skipping 1263 matching lines @@
     // live. If not, null the descriptor. Also drop the back pointer for that
     // map transition, so that this map is not reached again by following a back
     // pointer from that non-live map.
     bool keep_entry = false;
     PropertyDetails details(d->GetDetails(i));
     switch (details.type()) {
       case MAP_TRANSITION:
       case CONSTANT_TRANSITION:
         ClearBackPointer(heap, d->GetValue(i), &keep_entry);
         break;
-      case ELEMENTS_TRANSITION: {
-        Object* object = d->GetValue(i);
-        if (object->IsMap()) {
-          ClearBackPointer(heap, object, &keep_entry);
-        } else {
-          FixedArray* array = FixedArray::cast(object);
-          for (int j = 0; j < array->length(); ++j) {
-            if (ClearBackPointer(heap, array->get(j), &keep_entry)) {
-              array->set_undefined(j);
-            }
-          }
-        }
-        break;
-      }
       case CALLBACKS: {
         Object* object = d->GetValue(i);
         if (object->IsAccessorPair()) {
           AccessorPair* accessors = AccessorPair::cast(object);
           if (ClearBackPointer(heap, accessors->getter(), &keep_entry)) {
             accessors->set_getter(heap->the_hole_value());
           }
           if (ClearBackPointer(heap, accessors->setter(), &keep_entry)) {
             accessors->set_setter(heap->the_hole_value());
           }
@@ skipping 139 matching lines @@
 }
 
 
 MaybeObject* JSFunction::SetInstancePrototype(Object* value) {
   ASSERT(value->IsJSReceiver());
   Heap* heap = GetHeap();
   if (has_initial_map()) {
     // If the function has allocated the initial map
     // replace it with a copy containing the new prototype.
     Map* new_map;
-    MaybeObject* maybe_new_map = initial_map()->CopyDropTransitions();
+    MaybeObject* maybe_new_map = initial_map()->CopyDropTransitions(false);
     if (!maybe_new_map->To(&new_map)) return maybe_new_map;
     new_map->set_prototype(value);
     MaybeObject* maybe_object =
         set_initial_map_and_cache_transitions(new_map);
     if (maybe_object->IsFailure()) return maybe_object;
   } else {
     // Put the value in the initial map field until an initial map is
     // needed.  At that point, a new initial map is created and the
     // prototype is put into the initial map where it belongs.
     set_prototype_or_initial_map(value);
   }
   heap->ClearInstanceofCache();
   return value;
 }
 
 
 MaybeObject* JSFunction::SetPrototype(Object* value) {
   ASSERT(should_have_prototype());
   Object* construct_prototype = value;
 
   // If the value is not a JSReceiver, store the value in the map's
   // constructor field so it can be accessed.  Also, set the prototype
   // used for constructing objects to the original object prototype.
   // See ECMA-262 13.2.2.
   if (!value->IsJSReceiver()) {
     // Copy the map so this does not affect unrelated functions.
     // Remove map transitions because they point to maps with a
     // different prototype.
     Map* new_map;
-    { MaybeObject* maybe_new_map = map()->CopyDropTransitions();
+    { MaybeObject* maybe_new_map = map()->CopyDropTransitions(false);
       if (!maybe_new_map->To(&new_map)) return maybe_new_map;
     }
     Heap* heap = new_map->GetHeap();
     set_map(new_map);
     new_map->set_constructor(value);
     new_map->set_non_instance_prototype(true);
     construct_prototype =
         heap->isolate()->context()->global_context()->
             initial_object_prototype();
   } else {
@@ skipping 846 matching lines @@
 
 const char* Code::PropertyType2String(PropertyType type) {
   switch (type) {
     case NORMAL: return "NORMAL";
     case FIELD: return "FIELD";
     case CONSTANT_FUNCTION: return "CONSTANT_FUNCTION";
     case CALLBACKS: return "CALLBACKS";
     case HANDLER: return "HANDLER";
     case INTERCEPTOR: return "INTERCEPTOR";
     case MAP_TRANSITION: return "MAP_TRANSITION";
-    case ELEMENTS_TRANSITION: return "ELEMENTS_TRANSITION";
     case CONSTANT_TRANSITION: return "CONSTANT_TRANSITION";
     case NULL_DESCRIPTOR: return "NULL_DESCRIPTOR";
   }
   UNREACHABLE();  // keep the compiler happy
   return NULL;
 }
 
 
 void Code::PrintExtraICState(FILE* out, Kind kind, ExtraICState extra) {
   const char* name = NULL;
@@ skipping 370 matching lines @@
   }
 
   // Set the new prototype of the object.
   Map* map = real_receiver->map();
 
   // Nothing to do if prototype is already set.
   if (map->prototype() == value) return value;
 
   Object* new_map = map->GetPrototypeTransition(value);
   if (new_map == NULL) {
-    { MaybeObject* maybe_new_map = map->CopyDropTransitions();
+    { MaybeObject* maybe_new_map = map->CopyDropTransitions(false);
       if (!maybe_new_map->ToObject(&new_map)) return maybe_new_map;
     }
 
     { MaybeObject* maybe_new_cache =
           map->PutPrototypeTransition(value, Map::cast(new_map));
       if (maybe_new_cache->IsFailure()) return maybe_new_cache;
     }
 
     Map::cast(new_map)->set_prototype(value);
   }
@@ skipping 2260 matching lines @@
     entry = NextProbe(entry, count++, capacity);
   }
   return kNotFound;
 }
 
 
 bool StringDictionary::ContainsTransition(int entry) {
   switch (DetailsAt(entry).type()) {
     case MAP_TRANSITION:
     case CONSTANT_TRANSITION:
-    case ELEMENTS_TRANSITION:
       return true;
     case CALLBACKS: {
       Object* value = ValueAt(entry);
       if (!value->IsAccessorPair()) return false;
       AccessorPair* accessors = AccessorPair::cast(value);
       return accessors->getter()->IsMap() || accessors->setter()->IsMap();
     }
     case NORMAL:
     case FIELD:
     case CONSTANT_FUNCTION:
@@ skipping 1429 matching lines @@
       if (type == NORMAL &&
           (!value->IsJSFunction() || heap->InNewSpace(value))) {
         number_of_fields += 1;
       }
     }
   }
 
   // Allocate the instance descriptor.
   DescriptorArray* descriptors;
   { MaybeObject* maybe_descriptors =
-        DescriptorArray::Allocate(instance_descriptor_length);
+        DescriptorArray::Allocate(instance_descriptor_length, false);
     if (!maybe_descriptors->To<DescriptorArray>(&descriptors)) {
       return maybe_descriptors;
     }
   }
 
   DescriptorArray::WhitenessWitness witness(descriptors);
 
   int inobject_props = obj->map()->inobject_properties();
   int number_of_allocated_fields =
       number_of_fields + unused_property_fields - inobject_props;
@@ skipping 583 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