Sketch for TraverseTransitionTree.

src/objects.cc

Index: src/objects.cc
diff --git a/src/objects.cc b/src/objects.cc
index 0941e792f04e98f3391c5a8757da74902d74e21e..07710ff134a014a4ef49f61f85be1d67cf1a547e 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -4935,75 +4935,193 @@ void Map::RemoveFromCodeCache(String* name, Code* code, int index) {
 }
 
 
-void Map::TraverseTransitionTree(TraverseCallback callback, void* data) {
-  // Traverse the transition tree without using a stack.  We do this by
-  // reversing the pointers in the maps and descriptor arrays.
-  Map* current = this;
-  Map* meta_map = GetHeap()->meta_map();
-  Object** map_or_index_field = NULL;
-  while (current != meta_map) {
-    DescriptorArray* d = reinterpret_cast<DescriptorArray*>(
-        *RawField(current, Map::kInstanceDescriptorsOrBitField3Offset));
-    if (!d->IsEmpty()) {
-      FixedArray* contents = reinterpret_cast<FixedArray*>(
-          d->get(DescriptorArray::kContentArrayIndex));
-      map_or_index_field = RawField(contents, HeapObject::kMapOffset);
-      Object* map_or_index = *map_or_index_field;
-      bool map_done = true;  // Controls a nested continue statement.
-      for (int i = map_or_index->IsSmi() ? Smi::cast(map_or_index)->value() : 0;
-           i < contents->length();
+class IntrusiveIterationState {
+ public:
+  IntrusiveIterationState(HeapObject* obj)
+      : obj_(obj) { }
+
+  Object* Get() {
+    return *HeapObject::RawField(obj_, HeapObject::kMapOffset);
+  }
+
+  void Set(Object* s) {
+    *HeapObject::RawField(obj_, HeapObject::kMapOffset) = s;
+  }
+
+ private:
+  HeapObject* obj_;
+};
+
+
+class IntrusiveFixedArrayIterator {
+ public:
+  IntrusiveFixedArrayIterator(FixedArray* array)
+      : state_(array) { }
+
+  bool IsIterating() {
+    return state_.Get()->IsSmi();
+  }
+
+  int GetIndex() {
+    return Smi::cast(state_.Get())->value();
+  }
+
+  void SetIndex(int index) {
+    state_.Set(Smi::FromInt(index));
+  }
+
+  void Stop() {
+    state_.Set(HEAP->fixed_array_map());
+  }
+
+ private:
+  IntrusiveIterationState state_;
+};
+
+
+class IntrusiveMapIterator {
+ public:
+  IntrusiveMapIterator(Map* map)
+      : current_(map) { }
+
+  void DescendInto(Map* child) {
+    Map* parent = Current();
+    SetCurrent(child);
+    ASSERT(Parent() == HEAP->meta_map());
+    SetParent(parent);
+  }
+
+  Map* Ascend() {
+    // We are done with the current map.
+    // Before ascending reset iteration state.
+    StopMapTransitionsIteration();
+    StopPrototypeTransitionsIteration();
+
+    Map* parent = Parent();
+    SetParent(HEAP->meta_map());
+
+    Map* current = Current();
+    SetCurrent(parent);
+
+    return current;
+  }
+
+  bool HasMore() {
+    return Current() != HEAP->meta_map();
+  }
+
+
+  Map* NextUnvisitedChild() {
+    Map* child = NULL;
+
+    child = NextUnvisitedMapTransition();
+    if (child != NULL) return child;
+
+    child = NextUnvisitedPrototypeTransition();
+    if (child != NULL) return child;
+
+    return NULL;
+  }
+
+ private:
+  Map* current_;
+
+  Map* Current() {
+    return current_;
+  }
+
+  void SetCurrent(Map* current) {
+    current_ = current;
+  }
+
+  Map* Parent() {
+    return reinterpret_cast<Map*>(IntrusiveIterationState(current_).Get());
+  }
+
+  void SetParent(Map* parent) {
+    IntrusiveIterationState(current_).Set(parent);
+  }
+
+  FixedArray* ContentArray() {
+    DescriptorArray* d = Current()->instance_descriptors();
+    return reinterpret_cast<FixedArray*>(
+        d->get(DescriptorArray::kContentArrayIndex));
+  }
+
+  bool HasContentArray() {
+    return !Current()->instance_descriptors()->IsEmpty();
+  }
+
+  void StopMapTransitionsIteration() {
+    if (HasContentArray()) {
+      IntrusiveFixedArrayIterator it(ContentArray());
+      it.Stop();
+    }
+  }
+
+  Map* NextUnvisitedMapTransition() {
+    if (HasContentArray()) {
+      FixedArray* content = ContentArray();
+
+      IntrusiveFixedArrayIterator it(content);
+      for (int i = it.IsIterating() ? it.GetIndex() : 0;
+           i < content->length();
            i += 2) {
-        PropertyDetails details(Smi::cast(contents->get(i + 1)));
+        PropertyDetails details(Smi::cast(content->get(i + 1)));
         if (details.IsTransition()) {
           // Found a map in the transition array.  We record our progress in
           // the transition array by recording the current map in the map field
           // of the next map and recording the index in the transition array in
           // the map field of the array.
-          Map* next = Map::cast(contents->get(i));
-          next->set_map_no_write_barrier(current);
-          *map_or_index_field = Smi::FromInt(i + 2);
-          current = next;
-          map_done = false;
-          break;
+          Map* child = Map::cast(content->get(i));
+          it.SetIndex(i + 2);
+          return child;
         }
       }
-      if (!map_done) continue;
-    } else {
-      map_or_index_field = NULL;
-    }
-    // That was the regular transitions, now for the prototype transitions.
-    FixedArray* prototype_transitions =
-        current->unchecked_prototype_transitions();
-    Object** proto_map_or_index_field =
-        RawField(prototype_transitions, HeapObject::kMapOffset);
-    Object* map_or_index = *proto_map_or_index_field;
-    const int start = kProtoTransitionHeaderSize + kProtoTransitionMapOffset;
-    int i = map_or_index->IsSmi() ? Smi::cast(map_or_index)->value() : start;
-    if (i < prototype_transitions->length()) {
-      // Found a map in the prototype transition array.  Record progress in
-      // an analogous way to the regular transitions array above.
-      Object* perhaps_map = prototype_transitions->get(i);
-      if (perhaps_map->IsMap()) {
-        Map* next = Map::cast(perhaps_map);
-        next->set_map_no_write_barrier(current);
-        *proto_map_or_index_field =
-            Smi::FromInt(i + kProtoTransitionElementsPerEntry);
-        current = next;
-        continue;
-      }
     }
-    *proto_map_or_index_field = GetHeap()->fixed_array_map();
-    if (map_or_index_field != NULL) {
-      *map_or_index_field = GetHeap()->fixed_array_map();
+    return NULL;
+  }
+
+  void StopPrototypeTransitionsIteration() {
+    FixedArray* array = Current()->unchecked_prototype_transitions();
+    IntrusiveFixedArrayIterator it(array);
+    it.Stop();
+  }
+
+  Map* NextUnvisitedPrototypeTransition() {
+    FixedArray* array = Current()->unchecked_prototype_transitions();
+    IntrusiveFixedArrayIterator it(array);
+
+    static const int kFirstMapIndex =
+        (Map::kProtoTransitionHeaderSize + Map::kProtoTransitionMapOffset);
+
+    int index = it.IsIterating() ? it.GetIndex() : kFirstMapIndex;
+
+    if (index < array->length()) {
+      Object* child = array->get(index);
+      if (child->IsMap()) {
+        it.SetIndex(index + Map::kProtoTransitionElementsPerEntry);
+        return Map::cast(child);
+      }
     }
 
-    // The callback expects a map to have a real map as its map, so we save
-    // the map field, which is being used to track the traversal and put the
-    // correct map (the meta_map) in place while we do the callback.
-    Map* prev = current->map();
-    current->set_map_no_write_barrier(meta_map);
-    callback(current, data);
-    current = prev;
+    return NULL;
+  }
+};
+
+
+void Map::TraverseTransitionTree(TraverseCallback callback, void* data) {
+  // Traverse the transition tree without using a stack.  We do this by
+  // reversing the pointers in the maps and descriptor arrays.
+  IntrusiveMapIterator it(this);
+  while (it.HasMore()) {
+    Map* child = it.NextUnvisitedChild();
+    if (child != NULL) {
+      it.DescendInto(child);
+    } else {
+      Map* map = it.Ascend();
+      callback(map, data);
+    }
   }
 }