Include parent field/list index in retaining path.

runtime/vm/object_graph.cc

Index: runtime/vm/object_graph.cc
===================================================================
--- runtime/vm/object_graph.cc	(revision 37797)
+++ runtime/vm/object_graph.cc	(working copy)
@@ -20,9 +20,7 @@
 // its children are processed, to give the visitor a complete chain of parents.
 //
 // TODO(koda): Potential optimizations:
-// - Linked chunks instead of std::vector.
-// - Use smi/heap tag bit instead of full-word sentinel.
-// - Extend RawObject with incremental iteration (one child at a time).
+// - Use tag bit instead of full-word sentinel.
 class ObjectGraph::Stack : public ObjectPointerVisitor {
  public:
   explicit Stack(Isolate* isolate)
@@ -33,7 +31,7 @@
     for (RawObject** current = first; current <= last; ++current) {
       if ((*current)->IsHeapObject() && !(*current)->IsMarked()) {
         (*current)->SetMarkBit();
-        data_.Add(*current);
+        data_.Add(current);
       }
     }
   }
@@ -41,19 +39,19 @@
   // Traverses the object graph from the current state.
   void TraverseGraph(ObjectGraph::Visitor* visitor) {
     while (!data_.is_empty()) {
-      RawObject* obj = data_.Last();
-      if (obj == kSentinel) {
+      RawObject** obj_ptr = data_.Last();
+      if (obj_ptr == kSentinel) {
         data_.RemoveLast();
         // The node below the sentinel has already been visited.
         data_.RemoveLast();
         continue;
       }
-      ASSERT(obj->IsHeapObject());
+      ASSERT((*obj_ptr)->IsHeapObject());
       data_.Add(kSentinel);
       StackIterator it(this, data_.length() - 2);
       switch (visitor->VisitObject(&it)) {
         case ObjectGraph::Visitor::kProceed:
-          obj->VisitPointers(this);
+          (*obj_ptr)->VisitPointers(this);
           break;
         case ObjectGraph::Visitor::kBacktrack:
           break;
@@ -64,35 +62,62 @@
   }
 
  private:
-  static RawObject* const kSentinel;
+  static RawObject** const kSentinel;
   static const intptr_t kInitialCapacity = 1024;
-  GrowableArray<RawObject*> data_;
+  static const intptr_t kNoParent = -1;
+
+  intptr_t Parent(intptr_t index) const {
+    // The parent is just below the next sentinel.
+    for (intptr_t i = index; i >= 1; --i) {
+      if (data_[i] == kSentinel) {
+        return i - 1;
+      }
+    }
+    return kNoParent;
+  }
+
+  GrowableArray<RawObject**> data_;
   friend class StackIterator;
   DISALLOW_COPY_AND_ASSIGN(Stack);
 };
 
 
-// We only visit heap objects, so any Smi works as the sentinel.
-RawObject* const ObjectGraph::Stack::kSentinel = Smi::New(0);
+RawObject** const ObjectGraph::Stack::kSentinel = NULL;
 
 
 RawObject* ObjectGraph::StackIterator::Get() const {
-  return stack_->data_[index_];
+  return *(stack_->data_[index_]);
 }
 
 
 bool ObjectGraph::StackIterator::MoveToParent() {
-  // The parent is just below the next sentinel.
-  for (int i = index_; i >= 1; --i) {
-    if (stack_->data_[i] == Stack::kSentinel) {
-      index_ = i - 1;
-      return true;
-    }
+  intptr_t parent = stack_->Parent(index_);
+  if (parent == Stack::kNoParent) {
+    return false;
+  } else {
+    index_ = parent;
+    return true;
   }
-  return false;
 }
 
 
+intptr_t ObjectGraph::StackIterator::OffsetFromParentInWords() const {
+  intptr_t parent = stack_->Parent(index_);
+  if (parent == Stack::kNoParent) {
+    return -1;
+  }
+  RawObject** parent_ptr = stack_->data_[parent];
+  uword parent_start = RawObject::ToAddr(*parent_ptr);
+  RawObject** child_ptr = stack_->data_[index_];
+  uword child_ptr_addr = reinterpret_cast<uword>(child_ptr);
+  intptr_t offset = child_ptr_addr - parent_start;
+  ASSERT(offset > 0);
+  ASSERT(offset < (*parent_ptr)->Size());
+  ASSERT(Utils::IsAligned(offset, kWordSize));
+  return offset >> kWordSizeLog2;
+}
+
+
 class Unmarker : public ObjectVisitor {
  public:
   explicit Unmarker(Isolate* isolate) : ObjectVisitor(isolate) { }
@@ -224,10 +249,15 @@
     } else {
       HANDLESCOPE(Isolate::Current());
       Object& current = Object::Handle();
+      Smi& offset_from_parent = Smi::Handle();
       do {
-        if (!path_.IsNull() && length_ < path_.Length()) {
+        intptr_t obj_index = length_ * 2;
+        intptr_t offset_index = obj_index + 1;
+        if (!path_.IsNull() && offset_index < path_.Length()) {
           current = it->Get();
-          path_.SetAt(length_, current);
+          path_.SetAt(obj_index, current);
+          offset_from_parent = Smi::New(it->OffsetFromParentInWords());
+          path_.SetAt(offset_index, offset_from_parent);
         }
         ++length_;
       } while (it->MoveToParent());