Separating transitions from descriptors.

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 398 matching lines @@
         if (r.IsProperty()) {
           return GetPropertyAttributeWithFailedAccessCheck(receiver,
                                                            &r,
                                                            name,
                                                            continue_search);
         }
         break;
       }
 
       case HANDLER:
-      case MAP_TRANSITION:
-      case CONSTANT_TRANSITION:
+      case TRANSITION:
       case NONEXISTENT:
         UNREACHABLE();
     }
   }
 
   GetIsolate()->ReportFailedAccessCheck(this, v8::ACCESS_HAS);
   return ABSENT;
 }
 
 
@@ skipping 203 matching lines @@
     case CALLBACKS:
       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 CONSTANT_TRANSITION:
-      break;
+    case TRANSITION:
     case NONEXISTENT:
       UNREACHABLE();
       break;
   }
   UNREACHABLE();
   return NULL;
 }
 
 
 MaybeObject* Object::GetElementWithReceiver(Object* receiver, uint32_t index) {
@@ skipping 828 matching lines @@
     if (proto->IsJSObject()) return JSObject::cast(proto)->constructor_name();
   }
   // TODO(rossberg): what about proxies?
   // If the constructor is not present, return "Object".
   return GetHeap()->Object_symbol();
 }
 
 
 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);
 }
 
 
 static bool IsIdentifier(UnicodeCache* cache,
                          unibrow::CharacterStream* buffer) {
   // Checks whether the buffer contains an identifier (no escape).
   if (!buffer->has_more()) return false;
   if (!cache->IsIdentifierStart(buffer->GetNext())) {
     return false;
   }
@@ skipping 25 matching lines @@
     }
     return AddSlowProperty(name, value, attributes);
   }
 
   DescriptorArray* old_descriptors = map()->instance_descriptors();
   // Compute the new index for new field.
   int index = map()->NextFreePropertyIndex();
 
   // 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;
     }
   }
 
   // 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.
   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);
+
+  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) {
     if (TooManyFastProperties(properties()->length(), store_mode)) {
       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.
+  // 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);
 }
 
 
 MaybeObject* JSObject::AddConstantFunctionProperty(
     String* name,
     JSFunction* function,
     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;
     }
   }
 
   // Allocate a new map for the object.
   Object* new_map;

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

Why not "Map* new_map"?

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

Done.

   { MaybeObject* maybe_new_map = map()->CopyDropDescriptors();
     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));
 
   // If the old map is the global object map (from new Object()),
   // then transitions are not added to it, so we are done.
   Heap* heap = GetHeap();
   if (old_map == heap->isolate()->context()->global_context()->
       object_function()->map()) {
     return function;
   }
 
   // Do not add CONSTANT_TRANSITIONS to global objects

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

update comment?

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

Done.

   if (IsGlobalObject()) {
     return function;
   }
 
   // Add a CONSTANT_TRANSITION descriptor to the old map,

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

update comment?

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

Done.

   // so future assignments to this property on other objects
   // of the same type will create a normal field, not a constant function.
   // Don't do this for special properties, with non-trival attributes.
   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;
   }
-  old_map->set_instance_descriptors(DescriptorArray::cast(new_descriptors));
+
+  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;
+  }
+
   Map::cast(new_map)->SetBackPointer(old_map);
-
   return function;
 }
 
 
 // Add property in slow mode
 MaybeObject* JSObject::AddSlowProperty(String* name,
                                        Object* value,
                                        PropertyAttributes attributes) {
   ASSERT(!HasFastProperties());
   StringDictionary* dict = property_dictionary();
@@ skipping 100 matching lines @@
 
 
 MaybeObject* JSObject::ReplaceSlowProperty(String* name,
                                            Object* value,
                                            PropertyAttributes attributes) {
   StringDictionary* dictionary = property_dictionary();
   int old_index = dictionary->FindEntry(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();
   }
 
   PropertyDetails new_details(attributes, NORMAL, new_enumeration_index);
   return SetNormalizedProperty(name, value, new_details);
 }
 
 
 MaybeObject* JSObject::ConvertDescriptorToFieldAndMapTransition(
     String* name,
     Object* new_value,
     PropertyAttributes attributes) {
   Map* old_map = map();
   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.
   if (!HasFastProperties()) {
     return result;
   }
   // Do not add transitions to the map of "new Object()".
   if (map() == GetIsolate()->context()->global_context()->
       object_function()->map()) {
     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;
   }
-  old_map->set_instance_descriptors(DescriptorArray::cast(new_descriptors));
-  map()->SetBackPointer(old_map);
+
+  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);
+  }
   return result;
 }
 
 
 MaybeObject* JSObject::ConvertDescriptorToField(String* name,
                                                 Object* new_value,
                                                 PropertyAttributes attributes) {
   if (map()->unused_property_fields() == 0 &&
       TooManyFastProperties(properties()->length(), MAY_BE_STORE_FROM_KEYED)) {
     Object* obj;
     { MaybeObject* maybe_obj =
           NormalizeProperties(CLEAR_INOBJECT_PROPERTIES, 0);
       if (!maybe_obj->ToObject(&obj)) return maybe_obj;
     }
     return ReplaceSlowProperty(name, new_value, attributes);
   }
 
   int index = map()->NextFreePropertyIndex();
   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;
     }
   }
   DescriptorArray* new_descriptors =
       DescriptorArray::cast(descriptors_unchecked);
 
   // Make a new map for the object.
   Object* new_map_unchecked;
   { MaybeObject* maybe_new_map_unchecked = map()->CopyDropDescriptors();
@@ skipping 273 matching lines @@
       case CALLBACKS: {
         if (!FLAG_es5_readonly && result.IsReadOnly()) break;
         *done = true;
         return SetPropertyWithCallback(result.GetCallbackObject(),
             name, value, result.holder(), strict_mode);
       }
       case HANDLER: {
         return result.proxy()->SetPropertyViaPrototypesWithHandler(
             this, name, value, attributes, strict_mode, done);
       }
-      case MAP_TRANSITION:
-      case CONSTANT_TRANSITION:
-        break;
+      case TRANSITION:
       case NONEXISTENT:
         UNREACHABLE();
         break;
     }
   }
 
   // If we get here with *done true, we have encountered a read-only property.
   if (!FLAG_es5_readonly) *done = false;
   if (*done) {
     if (strict_mode == kNonStrictMode) return value;
     Handle<Object> args[] = { Handle<Object>(name), Handle<Object>(this)};
     return isolate->Throw(*isolate->factory()->NewTypeError(
       "strict_read_only_property", HandleVector(args, ARRAY_SIZE(args))));
   }
   return heap->the_hole_value();
 }
 
 
-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);
-  } 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);
   } else {
     result->NotFound();
   }
 }
 
 
+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) {
     if (!maps->at(i).is_null() && maps->at(i).is_identical_to(map)) return true;
   }
   return false;
 }
 
 
 template <class T>
@@ skipping 29 matching lines @@
 static Map* FindClosestElementsTransition(Map* map, ElementsKind to_kind) {
   Map* current_map = map;
   int index = GetSequenceIndexFromFastElementsKind(map->elements_kind());
   int to_index = IsFastElementsKind(to_kind)
       ? GetSequenceIndexFromFastElementsKind(to_kind)
       : GetSequenceIndexFromFastElementsKind(TERMINAL_FAST_ELEMENTS_KIND);
 
   ASSERT(index <= to_index);
 
   for (; index < to_index; ++index) {
+    if (!current_map->HasElementsTransition()) return current_map;
+    current_map = current_map->elements_transition_map();
+  }
+  if (!IsFastElementsKind(to_kind) && current_map->HasElementsTransition()) {
     Map* next_map = current_map->elements_transition_map();
-    if (next_map == NULL) {
-      return current_map;
-    }
-    current_map = next_map;
+    if (next_map->elements_kind() == to_kind) return next_map;
   }
-  if (!IsFastElementsKind(to_kind)) {
-    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);
-  }
+  ASSERT(IsFastElementsKind(to_kind)
+         ? current_map->elements_kind() == to_kind
+         : current_map->elements_kind() == TERMINAL_FAST_ELEMENTS_KIND);
   return current_map;
 }
 
 
 Map* Map::LookupElementsTransitionMap(ElementsKind to_kind) {
   Map* to_map = FindClosestElementsTransition(this, to_kind);
   if (to_map->elements_kind() == to_kind) return to_map;
   return NULL;
 }
 
 
 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())) &&
          (next_kind == DICTIONARY_ELEMENTS ||
           IsExternalArrayElementsKind(next_kind))));
     ASSERT(!IsFastElementsKind(next_kind) ||
            IsMoreGeneralElementsKindTransition(elements_kind(), next_kind));
     ASSERT(next_kind != elements_kind());
 
     Map* next_map;
     MaybeObject* maybe_next_map =
         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;
 }
 
 
 static MaybeObject* AddMissingElementsTransitions(Map* map,
                                                   ElementsKind to_kind) {
   ASSERT(IsFastElementsKind(map->elements_kind()));
   int index = GetSequenceIndexFromFastElementsKind(map->elements_kind());
   int to_index = IsFastElementsKind(to_kind)
       ? GetSequenceIndexFromFastElementsKind(to_kind)
@@ skipping 25 matching lines @@
 
 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, 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();
 
   if (from_kind == to_kind) {
     return start_map;
   }
 
   Context* global_context = GetIsolate()->context()->global_context();
   bool allow_store_transition =
@@ skipping 14 matching lines @@
   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(DescriptorArray::MAY_BE_SHARED);
     if (!maybe_new_map->To(&new_map)) return maybe_new_map;
     new_map->set_elements_kind(to_kind);
     return new_map;
   }
 
-  EnsureMayContainTransitions(start_map);
   Map* closest_map = FindClosestElementsTransition(start_map, to_kind);
 
   if (closest_map->elements_kind() == to_kind) {
     return closest_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.
     return JSObject::cast(proto)->LocalLookupRealNamedProperty(name, result);
   }
 
   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();
+    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();
+    }
+    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;
       }
-      return;
+      value = JSGlobalPropertyCell::cast(value)->value();
     }
-  } 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();
-      }
-      // Make sure to disallow caching for uninitialized constants
-      // found in the dictionary-mode objects.
-      if (value->IsTheHole()) result->DisallowCaching();
-      result->DictionaryResult(this, entry);
-      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;
   }
+
   result->NotFound();
 }
 
 
 void JSObject::LookupRealNamedProperty(String* name, LookupResult* result) {
   LocalLookupRealNamedProperty(name, result);
   if (result->IsProperty()) return;
 
   LookupRealNamedPropertyInPrototypes(name, result);
 }
@@ skipping 406 matching lines @@
     bool done = false;
     MaybeObject* result_object =
         SetPropertyViaPrototypes(name, value, attributes, strict_mode, &done);
     if (done) return result_object;
   }
 
   if (!result->IsFound()) {
     // 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);
       Handle<Object> args[] = { hname, self };
       return heap->isolate()->Throw(*heap->isolate()->factory()->NewTypeError(
           "strict_read_only_property", HandleVector(args, ARRAY_SIZE(args))));
     } else {
       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()) {
     case NORMAL:
       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;
       // Preserve the attributes of this existing property.
       attributes = result->GetAttributes();
       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,
                                      result->holder(),
                                      strict_mode);
     }
     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:
       UNREACHABLE();
       return value;
   }
   UNREACHABLE();  // keep the compiler happy
   return value;
 }
 
@@ skipping 49 matching lines @@
         value,
         attributes);
   }
 
   // Check for accessor in prototype chain removed here in clone.
   if (!result.IsFound()) {
     // Neither properties nor transitions found.
     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;
       // 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.
+    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();
   }
   UNREACHABLE();  // keep the compiler happy
   return value;
 }
 
 
 PropertyAttributes JSObject::GetPropertyAttributePostInterceptor(
@@ skipping 103 matching lines @@
       case CONSTANT_FUNCTION:
       case CALLBACKS:
         return result->GetAttributes();
       case HANDLER: {
         return JSProxy::cast(result->proxy())->GetPropertyAttributeWithHandler(
             receiver, name);
       }
       case INTERCEPTOR:
         return result->holder()->GetPropertyAttributeWithInterceptor(
             JSObject::cast(receiver), name, continue_search);
-      default:
+      case TRANSITION:
+      case NONEXISTENT:
         UNREACHABLE();
     }
   }
   return ABSENT;
 }
 
 
 PropertyAttributes JSReceiver::GetLocalPropertyAttribute(String* name) {
   // Check whether the name is an array index.
   uint32_t index = 0;
@@ skipping 136 matching lines @@
       case FIELD: {
         PropertyDetails d =
             PropertyDetails(details.attributes(), NORMAL, details.index());
         Object* value = FastPropertyAt(descs->GetFieldIndex(i));
         MaybeObject* maybe_dictionary =
             dictionary->Add(descs->GetKey(i), value, d);
         if (!maybe_dictionary->To(&dictionary)) return maybe_dictionary;
         break;
       }
       case CALLBACKS: {
-        if (!descs->IsProperty(i)) break;
         Object* value = descs->GetCallbacksObject(i);
         if (value->IsAccessorPair()) {
           MaybeObject* maybe_copy =
               AccessorPair::cast(value)->CopyWithoutTransitions();
           if (!maybe_copy->To(&value)) return maybe_copy;
         }
         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 INTERCEPTOR:
         break;
       case HANDLER:
       case NORMAL:
+      case TRANSITION:
       case NONEXISTENT:
         UNREACHABLE();
         break;
     }
   }
 
   Heap* current_heap = GetHeap();
 
   // Copy the next enumeration index from instance descriptor.
   int index = map_of_this->instance_descriptors()->NextEnumerationIndex();
@@ skipping 319 matching lines @@
 MaybeObject* JSObject::GetHiddenPropertiesDictionary(bool create_if_absent) {
   ASSERT(!IsJSGlobalProxy());
   if (HasFastProperties()) {
     // If the object has fast properties, check whether the first slot
     // in the descriptor array matches the hidden symbol. Since the
     // hidden symbols hash code is zero (and no other string has hash
     // code zero) it will always occupy the first entry if present.
     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;
     // You can't install a getter on a property indexed by the hidden symbol,
     // so we can be sure that GetLocalPropertyPostInterceptor returns a real
     // object.
     Object* lookup =
         GetLocalPropertyPostInterceptor(this,
                                         GetHeap()->hidden_symbol(),
                                         &attributes)->ToObjectUnchecked();
@@ skipping 22 matching lines @@
   ASSERT(!IsJSGlobalProxy());
   ASSERT(HasHiddenProperties());
   if (HasFastProperties()) {
     // If the object has fast properties, check whether the first slot
     // in the descriptor array matches the hidden symbol. Since the
     // hidden symbols hash code is zero (and no other string has hash
     // code zero) it will always occupy the first entry if present.
     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 =
       SetPropertyPostInterceptor(GetHeap()->hidden_symbol(),
                                  dictionary,
                                  DONT_ENUM,
                                  kNonStrictMode,
                                  OMIT_EXTENSIBILITY_CHECK);
   if (store_result->IsFailure()) return store_result;
   return this;
@@ skipping 414 matching lines @@
   }
   return true;
 }
 
 
 int Map::NumberOfDescribedProperties(PropertyAttributes filter) {
   int result = 0;
   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++;
     }
   }
   return result;
 }
 
 
 int Map::PropertyIndexFor(String* name) {
   DescriptorArray* descs = instance_descriptors();
   for (int i = 0; i < descs->number_of_descriptors(); i++) {
@@ skipping 82 matching lines @@
 }
 
 
 // Search object and its prototype chain for callback properties.
 void JSObject::LookupCallback(String* name, LookupResult* result) {
   Heap* heap = GetHeap();
   for (Object* current = this;
        current != heap->null_value() && current->IsJSObject();
        current = JSObject::cast(current)->GetPrototype()) {
     JSObject::cast(current)->LocalLookupRealNamedProperty(name, result);
+    // 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();
 }
 
 
 // Try to update an accessor in an elements dictionary. Return true if the
 // update succeeded, and false otherwise.
 static bool UpdateGetterSetterInDictionary(
     SeededNumberDictionary* dictionary,
@@ skipping 83 matching lines @@
   }
   accessors->SetComponents(getter, setter);
 
   return SetElementCallback(index, accessors, attributes);
 }
 
 
 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
     // OK, because the assertion only holds for the whole addition of both
     // accessors, not for the addition of each part. See first comment in
     // DefinePropertyAccessor below.
     Object* obj = result.GetCallbackObject();
     if (obj->IsAccessorPair()) {
       return AccessorPair::cast(obj)->CopyWithoutTransitions();
     }
@@ skipping 188 matching lines @@
   { MaybeObject* maybe_accessors2 = heap->AllocateAccessorPair();
     if (!maybe_accessors2->To(&accessors2)) return maybe_accessors2;
   }
   accessors2->set(component, accessor);
 
   // step 2: create a copy of the descriptors, incl. the new getter/setter pair
   Map* map1 = obj->map();
   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;
   }
 
   // step 3: create a new map with the new descriptors
   Map* map2;
   { MaybeObject* maybe_map2 = map1->CopyDropDescriptors();
     if (!maybe_map2->To(&map2)) return maybe_map2;
   }
   map2->set_instance_descriptors(descriptors2);
 
   // step 4: create a new getter/setter pair with a transition to the new map
   AccessorPair* accessors1;
   { MaybeObject* maybe_accessors1 = heap->AllocateAccessorPair();
     if (!maybe_accessors1->To(&accessors1)) return maybe_accessors1;
   }
   accessors1->set(component, map2);
 
   // 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
+  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);
-  map1->set_instance_descriptors(descriptors1);
-  map2->SetBackPointer(map1);
   return obj;
 }
 
 
 static bool TransitionToSameAccessor(Object* map,
                                      String* name,
                                      AccessorComponent component,
                                      Object* accessor,
                                      PropertyAttributes attributes ) {
   DescriptorArray* descs = Map::cast(map)->instance_descriptors();
@@ skipping 17 matching lines @@
   { MaybeObject* maybe_accessors3 = accessors2->CopyWithoutTransitions();
     if (!maybe_accessors3->To(&accessors3)) return maybe_accessors3;
   }
   accessors3->set(component, accessor);
 
   // step 2: create a copy of the descriptors, incl. the new getter/setter pair
   Map* map2 = obj->map();
   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;
   }
 
   // step 3: create a new map with the new descriptors
   Map* map3;
   { MaybeObject* maybe_map3 = map2->CopyDropDescriptors();
     if (!maybe_map3->To(&map3)) return maybe_map3;
   }
   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;
 }
 
 
 MaybeObject* JSObject::DefineFastAccessor(String* name,
                                           AccessorComponent component,
                                           Object* accessor,
                                           PropertyAttributes attributes) {
   ASSERT(accessor->IsSpecFunction() || accessor->IsUndefined());
   LookupResult result(GetIsolate());
   LocalLookup(name, &result);
 
   // If we have a new property, create a fresh accessor plus a transition to it.
   if (!result.IsFound()) {
     return CreateFreshAccessor(this, name, component, accessor, attributes);
   }
 
   // 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);
 
   // Follow a callback transition, if there is a fitting one.
   Object* entry = accessors->get(component);
   if (entry->IsMap() &&
       TransitionToSameAccessor(entry, name, component, accessor, attributes)) {
     set_map(Map::cast(entry));
     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.
   if (entry->IsTheHole()) {
     return NewCallbackTransition(this,
                                  name,
                                  component,
                                  accessor,
                                  attributes,
                                  accessors);
@@ skipping 21 matching lines @@
     return JSObject::cast(proto)->DefineAccessor(info);
   }
 
   // Make sure that the top context does not change when doing callbacks or
   // interceptor calls.
   AssertNoContextChange ncc;
 
   // 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);
 
   if (is_element) {
     if (IsJSArray()) return isolate->heap()->undefined_value();
 
     // Accessors overwrite previous callbacks (cf. with getters/setters).
     switch (GetElementsKind()) {
       case FAST_SMI_ELEMENTS:
@@ skipping 79 matching lines @@
       }
     }
   } else {
     for (Object* obj = this;
          obj != heap->null_value();
          obj = JSObject::cast(obj)->GetPrototype()) {
       LookupResult result(heap->isolate());
       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);
           }
         }
       }
     }
   }
   return heap->undefined_value();
 }
@@ skipping 39 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()->Copy(
               DescriptorArray::MAY_BE_SHARED);
       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());
@@ skipping 42 matching lines @@
 
 
 MaybeObject* Map::CopyDropTransitions(
     DescriptorArray::SharedMode shared_mode) {
   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(shared_mode);
+        instance_descriptors()->Copy(shared_mode);
     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) {
@@ skipping 43 matching lines @@
   // RemoveFromCodeCache so the code cache must be there.
   ASSERT(!code_cache()->IsFixedArray());
   CodeCache::cast(code_cache())->RemoveByIndex(name, code, index);
 }
 
 
 // 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) { }
+  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() {
     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 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;
+    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;
+          accessor = accessors->getter();
         }
-        case NORMAL:
-        case FIELD:
-        case CONSTANT_FUNCTION:
-        case HANDLER:
-        case INTERCEPTOR:
-          // We definitely have no map transition.
-          raw_index += 2;
-          ++index;
-          break;
-        case NONEXISTENT:
-          UNREACHABLE();
-          break;
+        ++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_;
 };
 
 
 // An iterator over all prototype transitions, reusing the map field of the
 // underlying array while it is running.
 class IntrusivePrototypeTransitionIterator {
  public:
   explicit IntrusivePrototypeTransitionIterator(HeapObject* proto_trans)
       : proto_trans_(proto_trans) { }
 
@@ skipping 79 matching lines @@
 
   // Reset the current map's map, returning the parent previously stored in it.
   TraversableMap* GetAndResetParent() {
     TraversableMap* old_parent = static_cast<TraversableMap*>(map());
     set_map_no_write_barrier(GetHeap()->meta_map());
     return old_parent;
   }
 
   // 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();
   }
 
   // If we have an unvisited child map, return that one and advance. If we have
   // none, return NULL and reset any destroyed FixedArray maps.
   TraversableMap* ChildIteratorNext() {
     IntrusivePrototypeTransitionIterator
         proto_iterator(unchecked_prototype_transitions());
     if (proto_iterator.IsIterating()) {
       Map* next = proto_iterator.Next();
       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);
     }
     return NULL;
   }
 };
 
 
 // Traverse the transition tree in postorder without using the C++ stack by
@@ skipping 611 matching lines @@
     MaybeObject* maybe_copy =
         AccessorPair::cast(value)->CopyWithoutTransitions();
     if (!maybe_copy->To(&value)) return maybe_copy;
   }
   Descriptor desc(src->GetKey(src_index), value, details);
   Set(dst_index, &desc, witness);
   return this;
 }
 
 
-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;
   }
 
   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_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);
 
   // Copy the descriptors, filtering out transitions and null descriptors,

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

update comment?

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

Done.

   // 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 (!(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++;
     }
   }
   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(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;
 }
 
 // We need the whiteness witness since sort will reshuffle the entries in the
 // descriptor array. If the descriptor array 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();
@@ skipping 46 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;
-
-  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;
   { MaybeObject* maybe_copy = heap->AllocateAccessorPair();
     if (!maybe_copy->To(&copy)) return maybe_copy;
   }
   copy->set_getter(getter()->IsMap() ? heap->the_hole_value() : getter());
   copy->set_setter(setter()->IsMap() ? heap->the_hole_value() : setter());
   return copy;
 }
@@ skipping 1222 matching lines @@
 
 
 void String::PrintOn(FILE* file) {
   int length = this->length();
   for (int i = 0; i < length; i++) {
     fprintf(file, "%c", Get(i));
   }
 }
 
 
-// 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.
 static void RightTrimFixedArray(Heap* heap, FixedArray* elms, int to_trim) {
   ASSERT(elms->map() != HEAP->fixed_cow_array_map());
   // For now this trick is only applied to fixed arrays in new and paged space.
   // In large object space the object's start must coincide with chunk
   // and thus the trick is just not applicable.
   ASSERT(!HEAP->lo_space()->Contains(elms));
 
@@ skipping 20 matching lines @@
 
   elms->set_length(len - to_trim);
 
   // Maintain marking consistency for IncrementalMarking.
   if (Marking::IsBlack(Marking::MarkBitFrom(elms))) {
     MemoryChunk::IncrementLiveBytesFromGC(elms->address(), -size_delta);
   }
 }
 
 
-// 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;
 }
 
 
 // TODO(mstarzinger): This method should be moved into MarkCompactCollector,
 // 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 descriptor_index = 0;
+  int transition_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);
   }
 }
 
 
 int Map::Hash() {
   // For performance reasons we only hash the 3 most variable fields of a map:
   // constructor, prototype and bit_field2.
 
   // Shift away the tag.
   int hash = (static_cast<uint32_t>(
@@ skipping 3174 matching lines @@
 }
 
 
 // Fill in the names of local properties into the supplied storage. The main
 // purpose of this function is to provide reflection information for the object
 // mirrors.
 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,
                                       StringDictionary::UNSORTED);
   }
 }
 
 
 int JSObject::NumberOfLocalElements(PropertyAttributes filter) {
   return GetLocalElementKeys(NULL, filter);
@@ skipping 607 matching lines @@
       set(index, key);
       return entry;
     }
     ASSERT(element->IsTheHole() || !String::cast(element)->Equals(key));
     entry = NextProbe(entry, count++, capacity);
   }
   return kNotFound;
 }
 
 
-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());
 
   AssertNoAllocation no_gc;
   WriteBarrierMode mode = new_table->GetWriteBarrierMode(no_gc);
 
   // Copy prefix to new array.
   for (int i = kPrefixStartIndex;
        i < kPrefixStartIndex + Shape::kPrefixSize;
@@ skipping 2014 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