Separating transitions from descriptors.

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index 57483177854d3928d838967bf9c8a98adc7f6a54..f8b87b14ebc115f6f07a25347887e7c30cfcc0c6 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -416,8 +416,7 @@ PropertyAttributes JSObject::GetPropertyAttributeWithFailedAccessCheck(
       }
 
       case HANDLER:
-      case MAP_TRANSITION:
-      case CONSTANT_TRANSITION:
+      case TRANSITION:
       case NONEXISTENT:
         UNREACHABLE();
     }
@@ -641,9 +640,7 @@ MaybeObject* Object::GetProperty(Object* receiver,
       return result->holder()->GetPropertyWithInterceptor(
           recvr, name, attributes);
     }
-    case MAP_TRANSITION:
-    case CONSTANT_TRANSITION:
-      break;
+    case TRANSITION:
     case NONEXISTENT:
       UNREACHABLE();
       break;
@@ -1492,20 +1489,19 @@ String* JSReceiver::constructor_name() {
 
 MaybeObject* JSObject::AddFastPropertyUsingMap(Map* new_map,
                                                String* name,
-                                               Object* value) {
-  int index = new_map->PropertyIndexFor(name);
+                                               Object* value,
+                                               int field_index) {
   if (map()->unused_property_fields() == 0) {
-    ASSERT(map()->unused_property_fields() == 0);
     int new_unused = new_map->unused_property_fields();
     Object* values;
     { MaybeObject* maybe_values =
           properties()->CopySize(properties()->length() + new_unused + 1);
-      if (!maybe_values->ToObject(&values)) return maybe_values;
+      if (!maybe_values->To(&values)) return maybe_values;
     }
     set_properties(FixedArray::cast(values));

[Jakob Kummerow, 2012/06/29 16:31:36]

While you're at it, you can get rid of the cast here by declaring "FixedArray*
values" in the first place.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

   }
   set_map(new_map);
-  return FastPropertyAtPut(index, value);
+  return FastPropertyAtPut(field_index, value);
 }
 
 
@@ -1551,10 +1547,10 @@ MaybeObject* JSObject::AddFastProperty(String* name,
 
   // Allocate new instance descriptors with (name, index) added
   FieldDescriptor new_field(name, index, attributes);
-  Object* new_descriptors;
+  DescriptorArray* new_descriptors;
   { MaybeObject* maybe_new_descriptors =
-        old_descriptors->CopyInsert(&new_field, REMOVE_TRANSITIONS);
-    if (!maybe_new_descriptors->ToObject(&new_descriptors)) {
+        old_descriptors->CopyInsert(&new_field);
+    if (!maybe_new_descriptors->To(&new_descriptors)) {
       return maybe_new_descriptors;
     }
   }
@@ -1562,7 +1558,7 @@ MaybeObject* JSObject::AddFastProperty(String* name,
   // 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);
+  int descriptor_index = old_descriptors->SearchWithCache(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.
@@ -1580,14 +1576,15 @@ MaybeObject* JSObject::AddFastProperty(String* name,
     if (!maybe_r->ToObject(&r)) return maybe_r;
   }
   Map* new_map = Map::cast(r);
+
+  TransitionArray* new_transitions = NULL;
   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);
-      if (!maybe_r->ToObject(&r)) return maybe_r;
+    MaybeObject* maybe_new_transitions =
+        map()->transitions()->CopyInsert(name, new_map);
+    if (!maybe_new_transitions->To(&new_transitions)) {
+      // We have accomplished the main goal, so return success.

[Jakob Kummerow, 2012/06/29 16:31:36]

Huh?

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+      return maybe_new_transitions;
     }
-    old_descriptors = DescriptorArray::cast(r);
   }
 
   if (map()->unused_property_fields() == 0) {
@@ -1610,13 +1607,13 @@ MaybeObject* JSObject::AddFastProperty(String* name,
   } 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.
+  // Apply all changes at once, so they are atomic.
   if (allow_map_transition) {
-    map()->set_instance_descriptors(old_descriptors);
+    MaybeObject* transition_added = map()->set_transitions(new_transitions);
+    if (transition_added->IsFailure()) return transition_added;
   }
+  new_map->set_instance_descriptors(new_descriptors);
   new_map->SetBackPointer(map());
-  new_map->set_instance_descriptors(DescriptorArray::cast(new_descriptors));
   set_map(new_map);
   return FastPropertyAtPut(index, value);
 }
@@ -1628,10 +1625,10 @@ MaybeObject* JSObject::AddConstantFunctionProperty(
     PropertyAttributes attributes) {
   // Allocate new instance descriptors with (name, function) added
   ConstantFunctionDescriptor d(name, function, attributes);
-  Object* new_descriptors;
+  DescriptorArray* new_descriptors;
   { MaybeObject* maybe_new_descriptors =
-        map()->instance_descriptors()->CopyInsert(&d, REMOVE_TRANSITIONS);
-    if (!maybe_new_descriptors->ToObject(&new_descriptors)) {
+        map()->instance_descriptors()->CopyInsert(&d);
+    if (!maybe_new_descriptors->To(&new_descriptors)) {
       return maybe_new_descriptors;
     }
   }
@@ -1642,8 +1639,7 @@ MaybeObject* JSObject::AddConstantFunctionProperty(
     if (!maybe_new_map->ToObject(&new_map)) return maybe_new_map;
   }
 
-  DescriptorArray* descriptors = DescriptorArray::cast(new_descriptors);
-  Map::cast(new_map)->set_instance_descriptors(descriptors);
+  Map::cast(new_map)->set_instance_descriptors(new_descriptors);
   Map* old_map = map();
   set_map(Map::cast(new_map));
 
@@ -1667,17 +1663,22 @@ MaybeObject* JSObject::AddConstantFunctionProperty(
   if (attributes != NONE) {
     return function;
   }
-  ConstTransitionDescriptor mark(name, Map::cast(new_map));
-  { MaybeObject* maybe_new_descriptors =
-        old_map->instance_descriptors()->CopyInsert(&mark, KEEP_TRANSITIONS);
-    if (!maybe_new_descriptors->ToObject(&new_descriptors)) {
-      // We have accomplished the main goal, so return success.
-      return function;
-    }
+
+  TransitionArray* new_transitions;
+  MaybeObject* maybe_new_transitions =

[Jakob Kummerow, 2012/06/29 16:31:36]

Not sure how important it is, but so far we've been pretty consistent in putting
MaybeObjects into their own {}-block. Let's do that here (and below) too.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+      old_map->transitions()->CopyInsert(name, Map::cast(new_map));
+  if (!maybe_new_transitions->To(&new_transitions)) {
+    // We have accomplished the main goal, so return success.

[Jakob Kummerow, 2012/06/29 16:31:36]

I'm not convinced that returning success here is reasonable, but let's leave it
as it is in this CL.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+    return function;
+  }
+
+  MaybeObject* transition_added = old_map->set_transitions(new_transitions);

[Jakob Kummerow, 2012/06/29 16:31:36]

see above.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+  // We have accomplished the main goal, so return success.
+  if (transition_added->IsFailure()) {
+    return function;
   }
-  old_map->set_instance_descriptors(DescriptorArray::cast(new_descriptors));
-  Map::cast(new_map)->SetBackPointer(old_map);
 
+  Map::cast(new_map)->SetBackPointer(old_map);
   return function;
 }
 
@@ -1798,7 +1799,6 @@ MaybeObject* JSObject::ReplaceSlowProperty(String* name,
   int new_enumeration_index = 0;  // 0 means "Use the next available index."
   if (old_index != -1) {
     // All calls to ReplaceSlowProperty have had all transitions removed.
-    ASSERT(!dictionary->ContainsTransition(old_index));
     new_enumeration_index = dictionary->DetailsAt(old_index).index();
   }
 
@@ -1815,7 +1815,7 @@ MaybeObject* JSObject::ConvertDescriptorToFieldAndMapTransition(
   Object* result;
   { MaybeObject* maybe_result =
         ConvertDescriptorToField(name, new_value, attributes);
-    if (!maybe_result->ToObject(&result)) return maybe_result;
+    if (!maybe_result->To(&result)) return maybe_result;
   }
   // If we get to this point we have succeeded - do not return failure
   // after this point.  Later stuff is optional.
@@ -1828,18 +1828,20 @@ MaybeObject* JSObject::ConvertDescriptorToFieldAndMapTransition(
     return result;
   }
 
-  MapTransitionDescriptor transition(name,
-                                     map(),
-                                     attributes);
-  Object* new_descriptors;
-  { MaybeObject* maybe_new_descriptors = old_map->instance_descriptors()->
-        CopyInsert(&transition, KEEP_TRANSITIONS);
-    if (!maybe_new_descriptors->ToObject(&new_descriptors)) {
-      return result;  // Yes, return _result_.
-    }
+  TransitionArray* new_transitions;
+  MaybeObject* maybe_new_transitions =

[Jakob Kummerow, 2012/06/29 16:31:36]

Again, please wrap in {}.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+      old_map->transitions()->CopyInsert(name, map());
+  if (!maybe_new_transitions->To(&new_transitions)) {
+    // We have accomplished the main goal, so return success.
+    return result;
+  }
+
+  MaybeObject* transition_added = old_map->set_transitions(new_transitions);

[Jakob Kummerow, 2012/06/29 16:31:36]

Again.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+  // Return success if failure since we accomplished the main goal. Otherwise
+  // also set backpointer.
+  if (!transition_added->IsFailure()) {
+    map()->SetBackPointer(old_map);
   }
-  old_map->set_instance_descriptors(DescriptorArray::cast(new_descriptors));
-  map()->SetBackPointer(old_map);
   return result;
 }
 
@@ -1861,8 +1863,8 @@ MaybeObject* JSObject::ConvertDescriptorToField(String* name,
   FieldDescriptor new_field(name, index, attributes);
   // Make a new DescriptorArray replacing an entry with FieldDescriptor.
   Object* descriptors_unchecked;
-  { MaybeObject* maybe_descriptors_unchecked = map()->instance_descriptors()->
-                                  CopyInsert(&new_field, REMOVE_TRANSITIONS);
+  { MaybeObject* maybe_descriptors_unchecked =
+        map()->instance_descriptors()->CopyInsert(&new_field);
     if (!maybe_descriptors_unchecked->ToObject(&descriptors_unchecked)) {
       return maybe_descriptors_unchecked;
     }
@@ -2156,9 +2158,7 @@ MaybeObject* JSObject::SetPropertyViaPrototypes(
         return result.proxy()->SetPropertyViaPrototypesWithHandler(
             this, name, value, attributes, strict_mode, done);
       }
-      case MAP_TRANSITION:
-      case CONSTANT_TRANSITION:
-        break;
+      case TRANSITION:
       case NONEXISTENT:
         UNREACHABLE();
         break;
@@ -2177,36 +2177,47 @@ MaybeObject* JSObject::SetPropertyViaPrototypes(
 }
 
 
-void JSObject::LookupInDescriptor(String* name, LookupResult* result) {
-  DescriptorArray* descriptors = map()->instance_descriptors();
+void Map::LookupDescriptor(JSObject* holder,
+                           String* name,
+                           LookupResult* result) {
+  DescriptorArray* descriptors = this->instance_descriptors();
   int number = descriptors->SearchWithCache(name);
   if (number != DescriptorArray::kNotFound) {
-    result->DescriptorResult(this, descriptors->GetDetails(number), number);
+    result->DescriptorResult(holder, descriptors->GetDetails(number), number);
   } else {
     result->NotFound();
   }
 }
 
 
-void Map::LookupInDescriptors(JSObject* holder,
-                              String* name,
-                              LookupResult* result) {
-  DescriptorArray* descriptors = instance_descriptors();
-  DescriptorLookupCache* cache =
-      GetHeap()->isolate()->descriptor_lookup_cache();
-  int number = cache->Lookup(descriptors, name);
-  if (number == DescriptorLookupCache::kAbsent) {
-    number = descriptors->Search(name);
-    cache->Update(descriptors, name, number);
-  }
-  if (number != DescriptorArray::kNotFound) {
-    result->DescriptorResult(holder, descriptors->GetDetails(number), number);
+static void LookupTransition(Map* map,

[Jakob Kummerow, 2012/06/29 16:31:36]

Why is this a local static function? It would be more consistent if it were a
method of the Map class (or even inlined into LookupTransitionOrDescriptor).

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+                             JSObject* holder,
+                             String* name,
+                             LookupResult* result) {
+  TransitionArray* transition_array = map->transitions();
+  int number = transition_array->Search(name);
+  if (number != TransitionArray::kNotFound) {
+    result->TransitionResult(holder, number);
   } else {
     result->NotFound();
   }
 }
 
 
+void Map::LookupTransitionOrDescriptor(JSObject* holder,
+                                       String* name,
+                                       LookupResult* result) {
+  // AccessorPairs containing both a Descriptor and a Transition are shared
+  // between the DescriptorArray and the Transition array. This is why looking
+  // up the AccessorPair solely in the DescriptorArray works.
+  // TODO(verwaest) This should be implemented differently so the
+  // DescriptorArray is free of transitions; and so we can freely share it.
+  this->LookupDescriptor(holder, name, result);
+  if (result->IsFound()) return;
+  LookupTransition(this, holder, name, result);
+}
+
+
 static bool ContainsMap(MapHandleList* maps, Handle<Map> map) {
   ASSERT(!map.is_null());
   for (int i = 0; i < maps->length(); ++i) {
@@ -2256,21 +2267,16 @@ static Map* FindClosestElementsTransition(Map* map, ElementsKind to_kind) {
   ASSERT(index <= to_index);
 
   for (; index < to_index; ++index) {
-    Map* next_map = current_map->elements_transition_map();
-    if (next_map == NULL) {
-      return current_map;
-    }
-    current_map = next_map;
+    if (!current_map->HasElementsTransition()) return current_map;
+    current_map = current_map->elements_transition_map();
   }
-  if (!IsFastElementsKind(to_kind)) {
+  if (!IsFastElementsKind(to_kind) && current_map->HasElementsTransition()) {
     Map* next_map = current_map->elements_transition_map();
-    if (next_map != NULL && next_map->elements_kind() == to_kind) {
-      return next_map;
-    }
-    ASSERT(current_map->elements_kind() == TERMINAL_FAST_ELEMENTS_KIND);
-  } else {
-    ASSERT(current_map->elements_kind() == to_kind);
+    if (next_map->elements_kind() == to_kind) return next_map;
   }
+  ASSERT(IsFastElementsKind(to_kind)
+         ? current_map->elements_kind() == to_kind
+         : current_map->elements_kind() == TERMINAL_FAST_ELEMENTS_KIND);
   return current_map;
 }
 
@@ -2283,7 +2289,7 @@ Map* Map::LookupElementsTransitionMap(ElementsKind to_kind) {
 
 
 MaybeObject* Map::CreateNextElementsTransition(ElementsKind next_kind) {
-    ASSERT(elements_transition_map() == NULL ||
+    ASSERT(!HasElementsTransition() ||
         ((elements_transition_map()->elements_kind() == DICTIONARY_ELEMENTS ||
           IsExternalArrayElementsKind(
               elements_transition_map()->elements_kind())) &&
@@ -2298,9 +2304,11 @@ MaybeObject* Map::CreateNextElementsTransition(ElementsKind next_kind) {
         this->CopyDropTransitions(DescriptorArray::CANNOT_BE_SHARED);
     if (!maybe_next_map->To(&next_map)) return maybe_next_map;
 
+    MaybeObject* added_elements = this->set_elements_transition_map(next_map);

[Jakob Kummerow, 2012/06/29 16:31:36]

Wrap in {} please.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+    if (added_elements->IsFailure()) return added_elements;
+
     next_map->set_elements_kind(next_kind);
     next_map->SetBackPointer(this);
-    this->set_elements_transition_map(next_map);
     return next_map;
 }
 
@@ -2346,22 +2354,6 @@ Handle<Map> JSObject::GetElementsTransitionMap(Handle<JSObject> object,
 }
 
 
-// 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, DescriptorArray::CANNOT_BE_SHARED);
-  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* start_map = map();
   ElementsKind from_kind = start_map->elements_kind();
@@ -2396,7 +2388,6 @@ MaybeObject* JSObject::GetElementsTransitionMapSlow(ElementsKind to_kind) {
     return new_map;
   }
 
-  EnsureMayContainTransitions(start_map);
   Map* closest_map = FindClosestElementsTransition(start_map, to_kind);
 
   if (closest_map->elements_kind() == to_kind) {
@@ -2418,41 +2409,40 @@ void JSObject::LocalLookupRealNamedProperty(String* name,
   }
 
   if (HasFastProperties()) {
-    LookupInDescriptor(name, result);
-    if (result->IsFound()) {
-      // A property, a map transition or a null descriptor was found.
-      // We return all of these result types because
-      // LocalLookupRealNamedProperty is used when setting properties
-      // where map transitions and null descriptors are handled.
-      ASSERT(result->holder() == this && result->IsFastPropertyType());
-      // Disallow caching for uninitialized constants. These can only
-      // occur as fields.
-      if (result->IsField() &&
-          result->IsReadOnly() &&
-          FastPropertyAt(result->GetFieldIndex())->IsTheHole()) {
-        result->DisallowCaching();
-      }
-      return;
+    map()->LookupTransitionOrDescriptor(this, name, result);
+    // A property or a map transition was found. We return all of these result
+    // types because LocalLookupRealNamedProperty is used when setting
+    // properties where map transitions are handled.
+    ASSERT(!result->IsFound() ||
+           (result->holder() == this && result->IsFastPropertyType()));
+    // Disallow caching for uninitialized constants. These can only
+    // occur as fields.
+    if (result->IsField() &&
+        result->IsReadOnly() &&
+        FastPropertyAt(result->GetFieldIndex())->IsTheHole()) {
+      result->DisallowCaching();
     }
-  } else {
-    int entry = property_dictionary()->FindEntry(name);
-    if (entry != StringDictionary::kNotFound) {
-      Object* value = property_dictionary()->ValueAt(entry);
-      if (IsGlobalObject()) {
-        PropertyDetails d = property_dictionary()->DetailsAt(entry);
-        if (d.IsDeleted()) {
-          result->NotFound();
-          return;
-        }
-        value = JSGlobalPropertyCell::cast(value)->value();
+    return;
+  }
+
+  int entry = property_dictionary()->FindEntry(name);
+  if (entry != StringDictionary::kNotFound) {
+    Object* value = property_dictionary()->ValueAt(entry);
+    if (IsGlobalObject()) {
+      PropertyDetails d = property_dictionary()->DetailsAt(entry);
+      if (d.IsDeleted()) {
+        result->NotFound();
+        return;
       }
-      // Make sure to disallow caching for uninitialized constants
-      // found in the dictionary-mode objects.
-      if (value->IsTheHole()) result->DisallowCaching();
-      result->DictionaryResult(this, entry);
-      return;
+      value = JSGlobalPropertyCell::cast(value)->value();
     }
+    // Make sure to disallow caching for uninitialized constants
+    // found in the dictionary-mode objects.
+    if (value->IsTheHole()) result->DisallowCaching();
+    result->DictionaryResult(this, entry);
+    return;
   }
+
   result->NotFound();
 }
 
@@ -2879,7 +2869,7 @@ MaybeObject* JSObject::SetPropertyForResult(LookupResult* result,
     // Neither properties nor transitions found.
     return AddProperty(name, value, attributes, strict_mode, store_mode);
   }
-  if (result->IsReadOnly() && result->IsProperty()) {
+  if (result->IsProperty() && result->IsReadOnly()) {
     if (strict_mode == kStrictMode) {
       Handle<JSObject> self(this);
       Handle<String> hname(name);
@@ -2890,6 +2880,7 @@ MaybeObject* JSObject::SetPropertyForResult(LookupResult* result,
       return value;
     }
   }
+
   // This is a real property that is not read-only, or it is a
   // transition or null descriptor and there are no setters in the prototypes.
   switch (result->type()) {
@@ -2897,14 +2888,6 @@ MaybeObject* JSObject::SetPropertyForResult(LookupResult* result,
       return SetNormalizedProperty(result, value);
     case FIELD:
       return FastPropertyAtPut(result->GetFieldIndex(), value);
-    case MAP_TRANSITION:
-      if (attributes == result->GetAttributes()) {
-        // Only use map transition if the attributes match.
-        return AddFastPropertyUsingMap(result->GetTransitionMap(),
-                                       name,
-                                       value);
-      }
-      return ConvertDescriptorToField(name, value, attributes);
     case CONSTANT_FUNCTION:
       // Only replace the function if necessary.
       if (value == result->GetConstantFunction()) return value;
@@ -2913,10 +2896,6 @@ MaybeObject* JSObject::SetPropertyForResult(LookupResult* result,
       return ConvertDescriptorToField(name, value, attributes);
     case CALLBACKS: {
       Object* callback_object = result->GetCallbackObject();
-      if (callback_object->IsAccessorPair() &&
-          !AccessorPair::cast(callback_object)->ContainsAccessor()) {
-        return ConvertDescriptorToField(name, value, attributes);
-      }
       return SetPropertyWithCallback(callback_object,
                                      name,
                                      value,
@@ -2925,23 +2904,49 @@ MaybeObject* JSObject::SetPropertyForResult(LookupResult* result,
     }
     case INTERCEPTOR:
       return SetPropertyWithInterceptor(name, value, attributes, strict_mode);
-    case CONSTANT_TRANSITION: {
+    case TRANSITION: {
+      Object* transition = result->GetTransitionValue();
+
+      if (transition->IsAccessorPair()) {
+        if (!AccessorPair::cast(transition)->ContainsAccessor()) {
+          return ConvertDescriptorToField(name, value, attributes);
+        }
+        return SetPropertyWithCallback(transition,
+                                       name,
+                                       value,
+                                       result->holder(),
+                                       strict_mode);
+      }
+
+      Map* transition_map = Map::cast(transition);
+      DescriptorArray* descriptors = transition_map->instance_descriptors();
+      int descriptor = descriptors->SearchWithCache(name);
+      PropertyDetails details = descriptors->GetDetails(descriptor);
+      ASSERT(details.type() == FIELD || details.type() == CONSTANT_FUNCTION);
+
+      if (details.type() == FIELD) {
+        if (attributes == details.attributes()) {
+          int field_index = descriptors->GetFieldIndex(descriptor);
+          return AddFastPropertyUsingMap(transition_map,
+                                         name,
+                                         value,
+                                         field_index);
+        }
+        return ConvertDescriptorToField(name, value, attributes);
+      }
+
+      // Is transition to CONSTANT_FUNCTION

[Jakob Kummerow, 2012/06/29 16:31:36]

nit: missing full stop.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+      Object* constant_function = descriptors->GetValue(descriptor);
       // If the same constant function is being added we can simply
       // transition to the target map.
-      Map* target_map = result->GetTransitionMap();
-      DescriptorArray* target_descriptors = target_map->instance_descriptors();
-      int number = target_descriptors->SearchWithCache(name);
-      ASSERT(number != DescriptorArray::kNotFound);
-      ASSERT(target_descriptors->GetType(number) == CONSTANT_FUNCTION);
-      JSFunction* function =
-          JSFunction::cast(target_descriptors->GetValue(number));
-      if (value == function) {
-        set_map(target_map);
-        return value;
+      if (constant_function == value) {
+        set_map(transition_map);
+        return this;
       }
-      // 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);
+      // 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 HANDLER:
     case NONEXISTENT:
@@ -3011,22 +3016,14 @@ MaybeObject* JSObject::SetLocalPropertyIgnoreAttributes(
     return AddProperty(name, value, attributes, kNonStrictMode);
   }
 
-  PropertyDetails details = PropertyDetails(attributes, NORMAL);
-
   // Check of IsReadOnly removed from here in clone.
   switch (result.type()) {
-    case NORMAL:
+    case NORMAL: {
+      PropertyDetails details = PropertyDetails(attributes, NORMAL);
       return SetNormalizedProperty(name, value, details);
+    }
     case FIELD:
       return FastPropertyAtPut(result.GetFieldIndex(), value);
-    case MAP_TRANSITION:
-      if (attributes == result.GetAttributes()) {
-        // Only use map transition if the attributes match.
-        return AddFastPropertyUsingMap(result.GetTransitionMap(),
-                                       name,
-                                       value);
-      }
-      return ConvertDescriptorToField(name, value, attributes);
     case CONSTANT_FUNCTION:
       // Only replace the function if necessary.
       if (value == result.GetConstantFunction()) return value;
@@ -3037,10 +3034,34 @@ MaybeObject* JSObject::SetLocalPropertyIgnoreAttributes(
     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.
+    case TRANSITION: {
+      Object* transition = result.GetTransitionValue();
+
+      if (transition->IsAccessorPair()) {
+        return ConvertDescriptorToField(name, value, attributes);
+      }
+
+      Map* transition_map = Map::cast(transition);
+      DescriptorArray* descriptors = transition_map->instance_descriptors();
+      int descriptor = descriptors->Search(name);
+      PropertyDetails details = descriptors->GetDetails(descriptor);
+      ASSERT(details.type() == FIELD || details.type() == CONSTANT_FUNCTION);
+
+      if (details.type() == FIELD) {
+        if (attributes == details.attributes()) {
+          int field_index = descriptors->GetFieldIndex(descriptor);
+          return AddFastPropertyUsingMap(transition_map,
+                                         name,
+                                         value,
+                                         field_index);
+        }
+        return ConvertDescriptorToField(name, value, attributes);
+      }
+
+      // Was transition to CONSTANT_FUNCTION. 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 HANDLER:
     case NONEXISTENT:
       UNREACHABLE();
@@ -3164,7 +3185,8 @@ PropertyAttributes JSReceiver::GetPropertyAttribute(JSReceiver* receiver,
       case INTERCEPTOR:
         return result->holder()->GetPropertyAttributeWithInterceptor(
             JSObject::cast(receiver), name, continue_search);
-      default:
+      case TRANSITION:
+      case NONEXISTENT:
         UNREACHABLE();
     }
   }
@@ -3321,7 +3343,6 @@ MaybeObject* JSObject::NormalizeProperties(PropertyNormalizationMode mode,
         break;
       }
       case CALLBACKS: {
-        if (!descs->IsProperty(i)) break;
         Object* value = descs->GetCallbacksObject(i);
         if (value->IsAccessorPair()) {
           MaybeObject* maybe_copy =
@@ -3333,12 +3354,11 @@ MaybeObject* JSObject::NormalizeProperties(PropertyNormalizationMode mode,
         if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;
         break;
       }
-      case MAP_TRANSITION:
-      case CONSTANT_TRANSITION:
       case INTERCEPTOR:
         break;
       case HANDLER:
       case NORMAL:
+      case TRANSITION:
       case NONEXISTENT:
         UNREACHABLE();
         break;
@@ -3678,13 +3698,10 @@ MaybeObject* JSObject::GetHiddenPropertiesDictionary(bool create_if_absent) {
     DescriptorArray* descriptors = this->map()->instance_descriptors();
     if ((descriptors->number_of_descriptors() > 0) &&
         (descriptors->GetKey(0) == GetHeap()->hidden_symbol())) {
-      if (descriptors->GetType(0) == FIELD) {
-        Object* hidden_store =
-            this->FastPropertyAt(descriptors->GetFieldIndex(0));
-        return StringDictionary::cast(hidden_store);
-      } else {
-        ASSERT(descriptors->GetType(0) == MAP_TRANSITION);
-      }
+      ASSERT(descriptors->GetType(0) == FIELD);
+      Object* hidden_store =
+          this->FastPropertyAt(descriptors->GetFieldIndex(0));
+      return StringDictionary::cast(hidden_store);
     }
   } else {
     PropertyAttributes attributes;
@@ -3727,12 +3744,9 @@ MaybeObject* JSObject::SetHiddenPropertiesDictionary(
     DescriptorArray* descriptors = this->map()->instance_descriptors();
     if ((descriptors->number_of_descriptors() > 0) &&
         (descriptors->GetKey(0) == GetHeap()->hidden_symbol())) {
-      if (descriptors->GetType(0) == FIELD) {
-        this->FastPropertyAtPut(descriptors->GetFieldIndex(0), dictionary);
-        return this;
-      } else {
-        ASSERT(descriptors->GetType(0) == MAP_TRANSITION);
-      }
+      ASSERT(descriptors->GetType(0) == FIELD);
+      this->FastPropertyAtPut(descriptors->GetFieldIndex(0), dictionary);
+      return this;
     }
   }
   MaybeObject* store_result =
@@ -4167,7 +4181,7 @@ int Map::NumberOfDescribedProperties(PropertyAttributes filter) {
   DescriptorArray* descs = instance_descriptors();
   for (int i = 0; i < descs->number_of_descriptors(); i++) {
     PropertyDetails details = descs->GetDetails(i);
-    if (descs->IsProperty(i) && (details.attributes() & filter) == 0) {
+    if ((details.attributes() & filter) == 0) {
       result++;
     }
   }
@@ -4270,6 +4284,7 @@ void JSObject::LookupCallback(String* name, LookupResult* result) {
        current != heap->null_value() && current->IsJSObject();
        current = JSObject::cast(current)->GetPrototype()) {
     JSObject::cast(current)->LocalLookupRealNamedProperty(name, result);
+    // TODO(verwaest) clean test

[Jakob Kummerow, 2012/06/29 16:31:36]

?

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

     if (result->IsCallbacks()) return;
   }
   result->NotFound();
@@ -4373,7 +4388,7 @@ MaybeObject* JSObject::DefineElementAccessor(uint32_t index,
 MaybeObject* JSObject::CreateAccessorPairFor(String* name) {
   LookupResult result(GetHeap()->isolate());
   LocalLookupRealNamedProperty(name, &result);
-  if (result.IsProperty() && result.IsCallbacks()) {
+  if (result.IsPropertyCallbacks()) {
     // Note that the result can actually have IsDontDelete() == true when we
     // e.g. have to fall back to the slow case while adding a setter after
     // successfully reusing a map transition for a getter. Nevertheless, this is
@@ -4582,8 +4597,7 @@ static MaybeObject* CreateFreshAccessor(JSObject* obj,
   CallbacksDescriptor callbacks_descr2(name, accessors2, attributes);
   DescriptorArray* descriptors2;
   { MaybeObject* maybe_descriptors2 =
-        map1->instance_descriptors()->CopyInsert(&callbacks_descr2,
-                                                 REMOVE_TRANSITIONS);
+        map1->instance_descriptors()->CopyInsert(&callbacks_descr2);
     if (!maybe_descriptors2->To(&descriptors2)) return maybe_descriptors2;
   }
 
@@ -4603,18 +4617,19 @@ static MaybeObject* CreateFreshAccessor(JSObject* obj,
 
   // step 5: create a copy of the descriptors, incl. the new getter/setter pair
   // with the transition
-  CallbacksDescriptor callbacks_descr1(name, accessors1, attributes);
-  DescriptorArray* descriptors1;
-  { MaybeObject* maybe_descriptors1 =
-        map1->instance_descriptors()->CopyInsert(&callbacks_descr1,
-                                                 KEEP_TRANSITIONS);
-    if (!maybe_descriptors1->To(&descriptors1)) return maybe_descriptors1;
+  TransitionArray* new_transitions;
+  MaybeObject* maybe_new_transitions =

[Jakob Kummerow, 2012/06/29 16:31:36]

Wrap in {} please.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+      map1->transitions()->CopyInsert(name, accessors1);
+  if (!maybe_new_transitions->To(&new_transitions)) {
+    // We have accomplished the main goal, so return success.

[Jakob Kummerow, 2012/06/29 16:31:36]

Comment is wrong.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+    return maybe_new_transitions;
   }
 
   // step 6: everything went well so far, so we make our changes visible
-  obj->set_map(map2);
-  map1->set_instance_descriptors(descriptors1);
+  MaybeObject* transition_added = map1->set_transitions(new_transitions);

[Jakob Kummerow, 2012/06/29 16:31:36]

again, {} please.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+  if (transition_added->IsFailure()) return transition_added;
   map2->SetBackPointer(map1);
+  obj->set_map(map2);
   return obj;
 }
 
@@ -4652,8 +4667,7 @@ static MaybeObject* NewCallbackTransition(JSObject* obj,
   CallbacksDescriptor callbacks_descr3(name, accessors3, attributes);
   DescriptorArray* descriptors3;
   { MaybeObject* maybe_descriptors3 =
-        map2->instance_descriptors()->CopyInsert(&callbacks_descr3,
-                                                 REMOVE_TRANSITIONS);
+        map2->instance_descriptors()->CopyInsert(&callbacks_descr3);
     if (!maybe_descriptors3->To(&descriptors3)) return maybe_descriptors3;
   }
 
@@ -4664,10 +4678,19 @@ static MaybeObject* NewCallbackTransition(JSObject* obj,
   }
   map3->set_instance_descriptors(descriptors3);
 
-  // step 4: everything went well so far, so we make our changes visible
+  // step 4: add a new transition to the new map
+  TransitionArray* new_transitions;
+  MaybeObject* maybe_transitions =

[Jakob Kummerow, 2012/06/29 16:31:36]

{}

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+      map2->transitions()->CopyInsert(name, accessors2);
+  if (!maybe_transitions->To(&new_transitions)) return maybe_transitions;
+
+  // step 5: everything went well so far, so we make our changes visible
+  MaybeObject* transition_added = map2->set_transitions(new_transitions);

[Jakob Kummerow, 2012/06/29 16:31:36]

{}

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+  if (transition_added->IsFailure()) return transition_added;
+
+  map3->SetBackPointer(map2);
   obj->set_map(map3);
   accessors2->set(component, map3);
-  map3->SetBackPointer(map2);
   return obj;
 }
 
@@ -4686,7 +4709,8 @@ MaybeObject* JSObject::DefineFastAccessor(String* name,
   }
 
   // If the property is not a JavaScript accessor, fall back to the slow case.
-  if (result.type() != CALLBACKS) return GetHeap()->null_value();
+  if (!result.IsCallbacks()) return GetHeap()->null_value();
+
   Object* callback_value = result.GetCallbackObject();
   if (!callback_value->IsAccessorPair()) return GetHeap()->null_value();
   AccessorPair* accessors = AccessorPair::cast(callback_value);
@@ -4699,7 +4723,6 @@ MaybeObject* JSObject::DefineFastAccessor(String* name,
     return this;
   }
 
-  // When we re-add the same accessor again, there is nothing to do.
   if (entry == accessor && result.GetAttributes() == attributes) return this;
 
   // Only the other accessor has been set so far, create a new transition.
@@ -4741,9 +4764,7 @@ MaybeObject* JSObject::DefineAccessor(AccessorInfo* info) {
   // Try to flatten before operating on the string.
   name->TryFlatten();
 
-  if (!CanSetCallback(name)) {
-    return isolate->heap()->undefined_value();
-  }
+  if (!CanSetCallback(name)) return isolate->heap()->undefined_value();
 
   uint32_t index = 0;
   bool is_element = name->AsArrayIndex(&index);
@@ -4843,7 +4864,7 @@ Object* JSObject::LookupAccessor(String* name, AccessorComponent component) {
       JSObject::cast(obj)->LocalLookup(name, &result);
       if (result.IsProperty()) {
         if (result.IsReadOnly()) return heap->undefined_value();
-        if (result.IsCallbacks()) {
+        if (result.IsPropertyCallbacks()) {
           Object* obj = result.GetCallbackObject();
           if (obj->IsAccessorPair()) {
             return AccessorPair::cast(obj)->GetComponent(component);
@@ -4903,7 +4924,7 @@ MaybeObject* Map::CopyDropDescriptors() {
     JSFunction* ctor = JSFunction::cast(constructor());
     Object* descriptors;
     { MaybeObject* maybe_descriptors =
-          ctor->initial_map()->instance_descriptors()->RemoveTransitions(
+          ctor->initial_map()->instance_descriptors()->Copy(
               DescriptorArray::MAY_BE_SHARED);
       if (!maybe_descriptors->ToObject(&descriptors)) return maybe_descriptors;
     }
@@ -4966,7 +4987,7 @@ MaybeObject* Map::CopyDropTransitions(
   }
   Object* descriptors;
   { MaybeObject* maybe_descriptors =
-        instance_descriptors()->RemoveTransitions(shared_mode);
+        instance_descriptors()->Copy(shared_mode);
     if (!maybe_descriptors->ToObject(&descriptors)) return maybe_descriptors;
   }
   cast(new_map)->set_instance_descriptors(DescriptorArray::cast(descriptors));
@@ -5030,18 +5051,18 @@ void Map::RemoveFromCodeCache(String* name, Code* code, int index) {
 // field of the contens array while it is running.
 class IntrusiveMapTransitionIterator {
  public:
-  explicit IntrusiveMapTransitionIterator(DescriptorArray* descriptor_array)
-      : descriptor_array_(descriptor_array) { }
+  explicit IntrusiveMapTransitionIterator(TransitionArray* transition_array)
+      : transition_array_(transition_array) { }
 
   void Start() {
     ASSERT(!IsIterating());
-    if (descriptor_array_->MayContainTransitions())
-      *DescriptorArrayHeader() = Smi::FromInt(0);
+    if (transition_array_ != NULL)
+      *TransitionArrayHeader() = Smi::FromInt(0);

[Jakob Kummerow, 2012/06/29 16:31:36]

nit: {} please.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

   }
 
   bool IsIterating() {
-    return descriptor_array_->MayContainTransitions() &&
-           (*DescriptorArrayHeader())->IsSmi();
+    return transition_array_ != NULL &&
+           (*TransitionArrayHeader())->IsSmi();
   }
 
   Map* Next() {
@@ -5051,66 +5072,52 @@ class IntrusiveMapTransitionIterator {
     // 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 raw_index = Smi::cast(*TransitionArrayHeader())->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:
-          // 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();
-          } else {
-            ++index;
-            accessor = accessors->getter();
-          }
-          ++raw_index;
-          if (accessor->IsMap()) {
-            *DescriptorArrayHeader() = Smi::FromInt(raw_index);
-            return static_cast<Map*>(accessor);
-          }
-          break;
-        }
-        case NORMAL:
-        case FIELD:
-        case CONSTANT_FUNCTION:
-        case HANDLER:
-        case INTERCEPTOR:
-          // We definitely have no map transition.
-          raw_index += 2;
+    int number_of_transitions = transition_array_->number_of_transitions();
+    while (index < number_of_transitions) {
+      Object* value = transition_array_->GetValue(index);
+      if (value->IsMap()) {
+        *TransitionArrayHeader() = Smi::FromInt(raw_index + 2);
+        return static_cast<Map*>(value);
+      } else if (value->IsAccessorPair()) {
+        // We might have a map transition in a getter or in a setter.
+        AccessorPair* accessors = static_cast<AccessorPair*>(value);
+        Object* accessor;
+        if ((raw_index & 1) == 0) {
+          accessor = accessors->setter();
+        } else {
           ++index;
-          break;
-        case NONEXISTENT:
-          UNREACHABLE();
-          break;
+          accessor = accessors->getter();
+        }
+        ++raw_index;
+        if (accessor->IsMap()) {
+          *TransitionArrayHeader() = Smi::FromInt(raw_index);
+          return static_cast<Map*>(accessor);
+        }
+        break;

[Jakob Kummerow, 2012/06/29 16:31:36]

This doesn't look right. Did you mean "continue"? As an alternative, remove this
statement, and put the "We definitely have no map transition" part into an "else
{...}" block.

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

       }
+      // We definitely have no map transition.
+      raw_index += 2;
+      ++index;
     }
-    if (index == descriptor_array_->number_of_descriptors()) {
-      Map* elements_transition = descriptor_array_->elements_transition_map();
+    if (index == transition_array_->number_of_transitions()) {
+      Map* elements_transition = transition_array_->elements();
       if (elements_transition != NULL) {
-        *DescriptorArrayHeader() = Smi::FromInt(raw_index + 2);
+        *TransitionArrayHeader() = Smi::FromInt(raw_index + 2);
         return elements_transition;
       }
     }
-    *DescriptorArrayHeader() = descriptor_array_->GetHeap()->fixed_array_map();
+    *TransitionArrayHeader() = transition_array_->GetHeap()->fixed_array_map();
     return NULL;
   }
 
  private:
-  Object** DescriptorArrayHeader() {
-    return HeapObject::RawField(descriptor_array_, DescriptorArray::kMapOffset);
+  Object** TransitionArrayHeader() {
+    return HeapObject::RawField(transition_array_, TransitionArray::kMapOffset);
   }
 
-  DescriptorArray* descriptor_array_;
+  TransitionArray* transition_array_;
 };
 
 
@@ -5210,22 +5217,24 @@ class TraversableMap : public Map {
 
   // Can either be Smi (no instance descriptors), or a descriptor array with the
   // header overwritten as a Smi (thus iterating).
-  DescriptorArray* MutatedInstanceDescriptors() {
+  TransitionArray* MutatedTransitions() {
+    if (!instance_descriptors()->HasTransitionArray()) return NULL;
     Object* object =
-        *HeapObject::RawField(this, kInstanceDescriptorsOrBitField3Offset);
+        *HeapObject::RawField(instance_descriptors(),
+                              DescriptorArray::kTransitionsOffset);
     if (object->IsSmi()) {
-      return GetHeap()->empty_descriptor_array();
+      return NULL;
     } else {
-      DescriptorArray* descriptor_array =
-          static_cast<DescriptorArray*>(object);
-      return descriptor_array;
+      TransitionArray* transition_array =
+          static_cast<TransitionArray*>(object);
+      return transition_array;
     }
   }
 
   // Start iterating over this map's children, possibly destroying a FixedArray
   // map (see explanation above).
   void ChildIteratorStart() {
-    IntrusiveMapTransitionIterator(instance_descriptors()).Start();
+    IntrusiveMapTransitionIterator(transitions()).Start();
     IntrusivePrototypeTransitionIterator(
         unchecked_prototype_transitions()).Start();
   }
@@ -5240,7 +5249,7 @@ class TraversableMap : public Map {
       if (next != NULL) return static_cast<TraversableMap*>(next);
     }
     IntrusiveMapTransitionIterator
-        descriptor_iterator(MutatedInstanceDescriptors());
+        descriptor_iterator(MutatedTransitions());
     if (descriptor_iterator.IsIterating()) {
       Map* next = descriptor_iterator.Next();
       if (next != NULL) return static_cast<TraversableMap*>(next);
@@ -5872,47 +5881,29 @@ MaybeObject* DescriptorArray::CopyFrom(int dst_index,
 }
 
 
-MaybeObject* DescriptorArray::CopyInsert(Descriptor* descriptor,
-                                         TransitionFlag transition_flag) {
-  // Transitions are only kept when inserting another transition.
-  // This precondition is not required by this function's implementation, but
-  // is currently required by the semantics of maps, so we check it.
-  // Conversely, we filter after replacing, so replacing a transition and
-  // removing all other transitions is not supported.
-  bool remove_transitions = transition_flag == REMOVE_TRANSITIONS;
-  ASSERT(remove_transitions == !descriptor->ContainsTransition());
-
+MaybeObject* DescriptorArray::CopyInsert(Descriptor* descriptor) {
   // Ensure the key is a symbol.
   { MaybeObject* maybe_result = descriptor->KeyToSymbol();
     if (maybe_result->IsFailure()) return maybe_result;
   }
 
-  int new_size = 0;
-  for (int i = 0; i < number_of_descriptors(); i++) {
-    if (remove_transitions && IsTransitionOnly(i)) continue;
-    new_size++;
-  }
+  int new_size = number_of_descriptors();
 
   // If key is in descriptor, we replace it in-place when filtering.
   // Count a null descriptor for key as inserted, not replaced.
-  int index = Search(descriptor->GetKey());
+  int index = SearchWithCache(descriptor->GetKey());
   const bool replacing = (index != kNotFound);
   bool keep_enumeration_index = false;
-  if (!replacing) {
-    ++new_size;
-  } else if (!IsTransitionOnly(index)) {
+  if (replacing) {
     // 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.
+  } else {
     ++new_size;
   }
 
   DescriptorArray* new_descriptors;
-  { SharedMode mode = remove_transitions ? MAY_BE_SHARED : CANNOT_BE_SHARED;
-    MaybeObject* maybe_result = Allocate(new_size, mode);
+  { MaybeObject* maybe_result = Allocate(new_size, MAY_BE_SHARED);
     if (!maybe_result->To(&new_descriptors)) return maybe_result;
   }
 
@@ -5921,17 +5912,11 @@ MaybeObject* DescriptorArray::CopyInsert(Descriptor* descriptor,
   // 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_map();
-  if ((!remove_transitions) && (old_elements_transition != NULL)) {
-    new_descriptors->set_elements_transition_map(old_elements_transition);
+  if (keep_enumeration_index) {
+    descriptor->SetEnumerationIndex(GetDetails(index).index());
+  } else {
+    descriptor->SetEnumerationIndex(enumeration_index);
+    ++enumeration_index;
   }
   new_descriptors->SetNextEnumerationIndex(enumeration_index);
 
@@ -5946,11 +5931,9 @@ MaybeObject* DescriptorArray::CopyInsert(Descriptor* descriptor,
       insertion_index = to_index++;
       if (replacing) from_index++;
     } else {
-      if (!(remove_transitions && IsTransitionOnly(from_index))) {
-        MaybeObject* copy_result =
-            new_descriptors->CopyFrom(to_index++, this, from_index, witness);
-        if (copy_result->IsFailure()) return copy_result;
-      }
+      MaybeObject* copy_result =
+          new_descriptors->CopyFrom(to_index++, this, from_index, witness);
+      if (copy_result->IsFailure()) return copy_result;
       from_index++;
     }
   }
@@ -5966,31 +5949,23 @@ MaybeObject* DescriptorArray::CopyInsert(Descriptor* descriptor,
 }
 
 
-MaybeObject* DescriptorArray::RemoveTransitions(SharedMode shared_mode) {
+MaybeObject* DescriptorArray::Copy(SharedMode shared_mode) {
   // 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++;
-  }
+  int number_of_descriptors = this->number_of_descriptors();
   DescriptorArray* new_descriptors;
-  { MaybeObject* maybe_result = Allocate(new_number_of_descriptors,
+  { MaybeObject* maybe_result = Allocate(number_of_descriptors,
                                          shared_mode);
     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;
-    }
+  for (int i = 0; i < number_of_descriptors; i++) {
+    MaybeObject* copy_result =
+        new_descriptors->CopyFrom(i, this, i, witness);
+    if (copy_result->IsFailure()) return copy_result;
   }
-  ASSERT(next_descriptor == new_descriptors->number_of_descriptors());
   new_descriptors->SetNextEnumerationIndex(NextEnumerationIndex());
-
   return new_descriptors;
 }
 
@@ -6057,43 +6032,6 @@ void DescriptorArray::Sort(const WhitenessWitness& witness) {
 }
 
 
-int DescriptorArray::BinarySearch(String* name, int low, int high) {
-  uint32_t hash = name->Hash();
-  int limit = 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;
-    } else {
-      low = mid + 1;
-    }
-  }
-
-  for (; low <= limit && GetKey(low)->Hash() == hash; ++low) {
-    if (GetKey(low)->Equals(name)) return low;
-  }
-
-  return kNotFound;
-}
-
-
-int DescriptorArray::LinearSearch(SearchMode mode, String* name, int len) {
-  uint32_t hash = name->Hash();
-  for (int number = 0; number < len; number++) {
-    String* entry = GetKey(number);
-    if (mode == EXPECT_SORTED && entry->Hash() > hash) break;
-    if (name->Equals(entry)) return number;
-  }
-  return kNotFound;
-}
-
-
 MaybeObject* AccessorPair::CopyWithoutTransitions() {
   Heap* heap = GetHeap();
   AccessorPair* copy;
@@ -7336,17 +7274,6 @@ void String::PrintOn(FILE* file) {
 }
 
 
-// Clear a possible back pointer in case the transition leads to a dead map.
-// Return true in case a back pointer has been cleared and false otherwise.
-static bool ClearBackPointer(Heap* heap, Object* target) {
-  ASSERT(target->IsMap());
-  Map* map = Map::cast(target);
-  if (Marking::MarkBitFrom(map).Get()) return false;
-  map->SetBackPointer(heap->undefined_value(), SKIP_WRITE_BARRIER);
-  return true;
-}
-
-
 // This function should only be called from within the GC, since it uses
 // IncrementLiveBytesFromGC. If called from anywhere else, this results in an
 // inconsistent live-bytes count.
@@ -7387,57 +7314,45 @@ static void RightTrimFixedArray(Heap* heap, FixedArray* elms, int to_trim) {
 }
 
 
-// If the descriptor describes a transition to a dead map, the back pointer
-// of this map is cleared and we return true. Otherwise we return false.
-static bool ClearNonLiveTransitionsFromDescriptor(Heap* heap,
-                                                  DescriptorArray* d,
-                                                  int descriptor_index) {
-  // If the pair (value, details) is a map transition, check if the target is
-  // 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.
-  PropertyDetails details(d->GetDetails(descriptor_index));
-  switch (details.type()) {
-    case MAP_TRANSITION:
-    case CONSTANT_TRANSITION:
-      return ClearBackPointer(heap, d->GetValue(descriptor_index));
-    case CALLBACKS: {
-      Object* object = d->GetValue(descriptor_index);
-      if (object->IsAccessorPair()) {
-        bool cleared = true;
-        AccessorPair* accessors = AccessorPair::cast(object);
-        Object* getter = accessors->getter();
-        if (getter->IsMap()) {
-          if (ClearBackPointer(heap, getter)) {
-            accessors->set_getter(heap->the_hole_value());
-          } else {
-            cleared = false;
-          }
-        } else if (!getter->IsTheHole()) {
-          cleared = false;
-        }
-        Object* setter = accessors->setter();
-        if (setter->IsMap()) {
-          if (ClearBackPointer(heap, setter)) {
-            accessors->set_setter(heap->the_hole_value());
-          } else {
-            cleared = false;
-          }
-        } else if (!setter->IsTheHole()) {
-          cleared = false;
-        }
-        return cleared;
-      }
-      return false;
-    }
-    case NORMAL:
-    case FIELD:
-    case CONSTANT_FUNCTION:
-    case HANDLER:
-    case INTERCEPTOR:
-      return false;
-    case NONEXISTENT:
-      break;
+// Clear a possible back pointer in case the transition leads to a dead map.
+// Return true in case a back pointer has been cleared and false otherwise.
+static bool ClearBackPointer(Heap* heap, Object* target) {
+  ASSERT(target->IsMap());
+  Map* map = Map::cast(target);
+  if (Marking::MarkBitFrom(map).Get()) return false;
+  map->SetBackPointer(heap->undefined_value(), SKIP_WRITE_BARRIER);
+  return true;
+}
+
+
+static bool ClearAccessorComponent(Heap* heap,
+                                   AccessorPair* accessors,
+                                   AccessorComponent component) {
+  Object* component_value = accessors->get(component);
+  if (!component_value->IsMap()) return true;
+  if (ClearBackPointer(heap, component_value)) {
+    accessors->set(component, heap->the_hole_value());
+    return true;
+  }
+  return false;
+}
+
+
+static bool ClearNonLiveTransition(Heap* heap,
+                                   TransitionArray* t,
+                                   int transition_index) {
+  // If the value is a map, check if the target is live. If not, clear the
+  // transition. 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.
+  Object* value = t->GetValue(transition_index);
+  if (value->IsMap()) {
+      return ClearBackPointer(heap, t->GetValue(transition_index));

[Jakob Kummerow, 2012/06/29 16:31:36]

nit: indentation is off

[Toon Verwaest, 2012/07/05 12:56:11]

Done.

+  } else if (value->IsAccessorPair()) {
+    AccessorPair* accessors = AccessorPair::cast(value);
+    bool getter = ClearAccessorComponent(heap, accessors, ACCESSOR_GETTER);
+    bool setter = ClearAccessorComponent(heap, accessors, ACCESSOR_SETTER);
+    return getter && setter;

[Jakob Kummerow, 2012/06/29 16:31:36]

Shouldn't this be "getter || setter"?

[Toon Verwaest, 2012/07/05 12:56:11]

No. Getter and setter are booleans indicating that their related component was
cleared. Only if both components are cleared we can clear the whole pair.

On 2012/06/29 16:31:36, Jakob wrote:

   }
   UNREACHABLE();
   return true;
@@ -7448,57 +7363,50 @@ static bool ClearNonLiveTransitionsFromDescriptor(Heap* heap,
 // because it cannot be called from outside the GC and we already have methods
 // depending on the transitions layout in the GC anyways.
 void Map::ClearNonLiveTransitions(Heap* heap) {
-  Object* array = *RawField(this, Map::kInstanceDescriptorsOrBitField3Offset);
-  // If there are no descriptors to be cleared, return.
+  TransitionArray* t = transitions();
+  // If there are no transitions to be cleared, return.
   // TODO(verwaest) Should be an assert, otherwise back pointers are not
   // properly cleared.
-  if (array->IsSmi()) return;
-  DescriptorArray* d = DescriptorArray::cast(array);
+  if (t == NULL) return;
+
+  int transition_index = 0;
 
-  int descriptor_index = 0;
   // Compact all live descriptors to the left.
-  for (int i = 0; i < d->number_of_descriptors(); ++i) {
-    if (!ClearNonLiveTransitionsFromDescriptor(heap, d, i)) {
-      if (i != descriptor_index) {
-        String* key = d->GetKey(i);
-        Object* value = d->GetValue(i);
-        d->SetKeyUnchecked(heap, descriptor_index, key);
-        d->SetDetailsUnchecked(descriptor_index, d->GetDetails(i).AsSmi());
-        d->SetValueUnchecked(heap, descriptor_index, value);
+  for (int i = 0; i < t->number_of_transitions(); ++i) {
+    if (!ClearNonLiveTransition(heap, t, i)) {
+      if (i != transition_index) {
+        String* key = t->GetKey(i);
+        Object* value = t->GetValue(i);
+        t->SetKeyUnchecked(heap, transition_index, key);
+        t->SetValueUnchecked(heap, transition_index, value);
         MarkCompactCollector* collector = heap->mark_compact_collector();
-        Object** key_slot = d->GetKeySlot(descriptor_index);
+        Object** key_slot = t->GetKeySlot(transition_index);
         collector->RecordSlot(key_slot, key_slot, key);
-        if (value->IsHeapObject()) {
-          Object** value_slot = d->GetValueSlot(descriptor_index);
-          collector->RecordSlot(value_slot, value_slot, value);
-        }
+        Object** value_slot = t->GetValueSlot(transition_index);
+        collector->RecordSlot(value_slot, value_slot, value);
       }
-      descriptor_index++;
+      transition_index++;
     }
   }
 
-  Map* elements_transition = d->elements_transition_map();
-  if (elements_transition != NULL &&
-      ClearBackPointer(heap, elements_transition)) {
-    elements_transition = NULL;
-    d->ClearElementsTransition();
+  if (t->HasElementsTransition() && ClearBackPointer(heap, t->elements())) {
+    t->ClearElements();
   } else {
-    // If there are no descriptors to be cleared, return.
+    // If there are no transitions to be cleared, return.
     // TODO(verwaest) Should be an assert, otherwise back pointers are not
     // properly cleared.
-    if (descriptor_index == d->number_of_descriptors()) return;
+    if (transition_index == t->number_of_transitions()) return;
   }
 
-  // If the final descriptor array does not contain any live descriptors, remove
-  // the descriptor array from the map.
-  if (descriptor_index == 0 && elements_transition == NULL) {
-    ClearDescriptorArray();
-    return;
+  // If the final transition array does not contain any live transitions, remove
+  // the transition array from the map.
+  if (transition_index == 0 && !t->HasElementsTransition()) {
+    return ClearTransitions();
   }
 
-  int trim = d->number_of_descriptors() - descriptor_index;
+  int trim = t->number_of_transitions() - transition_index;
   if (trim > 0) {
-    RightTrimFixedArray(heap, d, trim * DescriptorArray::kDescriptorSize);
+    RightTrimFixedArray(heap, t, trim * TransitionArray::kTransitionSize);
   }
 }
 
@@ -10693,10 +10601,10 @@ void JSObject::GetLocalPropertyNames(FixedArray* storage, int index) {
   ASSERT(storage->length() >= (NumberOfLocalProperties() - index));
   if (HasFastProperties()) {
     DescriptorArray* descs = map()->instance_descriptors();
+    ASSERT(storage->length() >= index + descs->number_of_descriptors());
     for (int i = 0; i < descs->number_of_descriptors(); i++) {
-      if (descs->IsProperty(i)) storage->set(index++, descs->GetKey(i));
+      storage->set(index + i, descs->GetKey(i));
     }
-    ASSERT(storage->length() >= index);
   } else {
     property_dictionary()->CopyKeysTo(storage,
                                       index,
@@ -11324,32 +11232,6 @@ int StringDictionary::FindEntry(String* key) {
 }
 
 
-bool StringDictionary::ContainsTransition(int entry) {
-  switch (DetailsAt(entry).type()) {
-    case MAP_TRANSITION:
-    case CONSTANT_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:
-    case HANDLER:
-    case INTERCEPTOR:
-      return false;
-    case NONEXISTENT:
-      UNREACHABLE();
-      break;
-  }
-  UNREACHABLE();  // Keep the compiler happy.
-  return false;
-}
-
-
 template<typename Shape, typename Key>
 MaybeObject* HashTable<Shape, Key>::Rehash(HashTable* new_table, Key key) {
   ASSERT(NumberOfElements() < new_table->Capacity());