Refactored PathTracer in heap.cc....

src/heap.h

Index: src/heap.h
===================================================================
--- src/heap.h	(revision 6858)
+++ src/heap.h	(working copy)
@@ -30,6 +30,7 @@
 
 #include <math.h>
 
+#include "list.h"
 #include "spaces.h"
 #include "splay-tree-inl.h"
 #include "v8-counters.h"
@@ -2152,6 +2153,108 @@
 };
 
 
+#if defined(DEBUG) || defined(LIVE_OBJECT_LIST)
+// Helper class for tracing paths to a search target Object from all roots.
+// The TracePathFrom() method can be used to trace paths from a specific
+// object to the search target object.
+//
+// The "what_to_find" can be kFindFirst or kFindAll.  If kFindFirst is
+// specified, tracing will stop after the first match.  If kFindAll is
+// specified, then tracing will be done for all matches.
+class PathTracer: public ObjectVisitor {
+ public:
+  PathTracer(Object* search_target,

[mnaganov (inactive), 2011/02/21 10:59:46]

When using raw pointers, you should instantiate AssertNoAllocation somewhere to
make sure that no GCs occur while you are operating on them. E.g. you can put it
into members list of this class. With GC helpers this wasn't an issue because
they were intended to be used during GC phases.

[marklam, 2011/02/21 17:45:15]

Done.  Thanks for pointing this out.  Since PathTracer holds on to a naked
pointer, I added an AssertNoAllocation as a member field.  This ensures that no
gc is done for the entire lifetime of the tracer.

+             bool search_for_any_global,

[mnaganov (inactive), 2011/02/21 10:59:46]

I have a concern about argument types. I'd suggest to use enums here (I'm not
sure why are you using 'int' for 'what_to_find', not enum.) For the last
argument, you can reuse VisitMode enum.

[marklam, 2011/02/21 17:45:15]

Done.  I had mistakenly believed that enums are not scoped to the declaring
class in C++.  Thanks for making me revisit this.

+             int what_to_find,
+             bool skip_weak_refs)
+      : search_target_(search_target),
+        search_for_any_global_(search_for_any_global),
+        found_target_(false),
+        found_target_in_trace_(false),

[marklam, 2011/02/20 08:23:07]

There's a need to distinguish found_target_in_trace_ from the global
found_target_ because VisitPointers() is called for the range of one pointer at
a time.  This exposes a bug where TracePathFrom() needs to reset the found flag
for the current trace, but we also need a global flag to indicate whether the
target was found at all.  This wasn't a problem before because we did not
support the kFindFirst mode previously.

The solution is to separate these 2 found flags where found_target_in_trace_
tracks whether the target was found in the current trace path, and found_target_
tracks whether the target was found at all.

+        what_to_find_(what_to_find),
+        skip_weak_refs_(skip_weak_refs),
+        object_stack_(20),
+        mark_visitor(this),
+        unmark_visitor(this) {}
+
+  void VisitPointers(Object** start, Object** end) {
+    bool done = ((what_to_find_ == kFindFirst) && found_target_);
+    // Visit all HeapObject pointers in [start, end)
+    for (Object** p = start; !done && (p < end); p++) {
+      if ((*p)->IsHeapObject()) {
+        TracePathFrom(p);
+        done = ((what_to_find_ == kFindFirst) && found_target_);
+      }
+    }
+  }
+
+  void Reset() {
+    found_target_ = false;
+    object_stack_.Clear();
+  }
+  void TracePathFrom(Object** root);
+
+  bool found() const { return found_target_; }
+
+  // Values for the "what_to_find" argument of the constructor.

[mnaganov (inactive), 2011/02/21 10:59:46]

As a bonus of using enums, you will not need comments of such kind.

[marklam, 2011/02/21 17:45:15]

Done.

+  static const int kFindFirst = 1;  // Will stop the search after first match.
+  static const int kFindAll = 0;  // Will find all matches.
+
+ protected:
+  class MarkVisitor: public ObjectVisitor {

[mnaganov (inactive), 2011/02/21 10:59:46]

Does this really need to be put in the header file? You can use scoped pointers
to visitors as class members and implement those helper classes inside the .cpp
file.

[marklam, 2011/02/21 17:45:15]

Done.  I moved this into heap.cc, and instantiate them in TracePathFrom() and
passed them around instead of having them as member fields.  They serve as
utility classes anyway whose life cycle is tied with the trace path operation. 
So, this is cleaner.

+   public:
+    explicit MarkVisitor(PathTracer* tracer) : tracer_(tracer) {}
+    void VisitPointers(Object** start, Object** end) {
+      // Scan all HeapObject pointers in [start, end)
+      for (Object** p = start; !tracer_->found() && (p < end); p++) {
+        if ((*p)->IsHeapObject())
+          tracer_->MarkRecursively(p);
+      }
+    }
+
+   private:
+    PathTracer* tracer_;
+  };
+
+
+  class UnmarkVisitor: public ObjectVisitor {
+   public:
+    explicit UnmarkVisitor(PathTracer* tracer) : tracer_(tracer) {}
+    void VisitPointers(Object** start, Object** end) {
+      // Scan all HeapObject pointers in [start, end)
+      for (Object** p = start; p < end; p++) {
+        if ((*p)->IsHeapObject())
+          tracer_->UnmarkRecursively(p);
+      }
+    }
+
+   private:
+    PathTracer* tracer_;
+  };
+
+  PathTracer();

[mnaganov (inactive), 2011/02/21 10:59:46]

I think what you need here is DISALLOW_IMPLICIT_CONSTRUCTORS macro.

[marklam, 2011/02/21 17:45:15]

Done.

+
+  void MarkRecursively(Object** p);
+  void UnmarkRecursively(Object** p);
+  virtual void ProcessResults();
+
+  // Tags 0, 1, and 3 are used. Use 2 for marking visited HeapObject.
+  static const int kMarkTag = 2;
+
+  Object* search_target_;
+  bool search_for_any_global_;
+  bool found_target_;
+  bool found_target_in_trace_;
+  bool what_to_find_;
+  bool skip_weak_refs_;
+  List<Object*> object_stack_;
+
+  MarkVisitor mark_visitor;
+  UnmarkVisitor unmark_visitor;
+};
+#endif  // DEBUG || LIVE_OBJECT_LIST
+
+
 } }  // namespace v8::internal
 
 #endif  // V8_HEAP_H_