Bug 672736: Implement the 'findReferences' shell function. r=jorendorff
authorJim Blandy <jimb@mozilla.com>
Wed, 03 Aug 2011 20:19:38 -0700
changeset 73821 65617cb216fa8ad8ce0a2e68a26d71c36321c54f
parent 73820 c048ca40dcd14c7338d5b5fce020143e1f26ab05
child 73822 5edb33c72ec0c29ba4157ee85480458cfb1aff5e
push id2
push userbsmedberg@mozilla.com
push dateFri, 19 Aug 2011 14:38:13 +0000
reviewersjorendorff
bugs672736
milestone8.0a1
Bug 672736: Implement the 'findReferences' shell function. r=jorendorff findReferences(thing) Walk the entire heap, looking for references to |thing|, and return a "references object" describing what we found. Each property of the references object describes one kind of reference. The property's name is the label supplied to MarkObject, JS_CALL_TRACER, or what have you, prefixed with "edge: " to avoid collisions with system properties (like "toString" and "__proto__"). The property's value is an array of things that refer to |thing| via that kind of reference. Ordinary references from one object to another are named after the property name (with the "edge: " prefix). Garbage collection roots appear as references from 'null'. We use the name given to the root (with the "edge: " prefix) as the name of the reference. Note that the references object does record references from objects that are only reachable via |thing| itself, not just the references reachable themselves from roots that keep |thing| from being collected. (We could make this distinction if it is useful.) If any references are found by the conservative scanner, the references object will have a property named "edge: machine stack"; the referrers will be 'null', because they are roots. js> var o = { x: { y: { z: {} } }} js> findReferences(o.x.y.z) ({'edge: z':[{z:{}}], 'edge: machine stack':[null, null, null, null, null]}) js> o = { get x() { return 42 } } ({get x () {return 42;}}) js> findReferences(Object.getOwnPropertyDescriptor(o, 'x').get) ({'edge: shape; x getter':[{get x () {return 42;}}], 'edge: constructor':[{}], 'edge: machine stack':[null, null, null, null, null], 'edge: get':[{configurable:true, enumerable:true, get:#1=(function () {return 42;}), set:(void 0)}]}) js> findReferences(Math.atan2) ({'edge: atan2':[Math], 'edge: machine stack':[null, null, null, null, null]}) js> findReferences(o) ({'edge: o':[{o:{get x () {return 42;}}}], 'edge: machine stack':[null, null, null, null, null]}) js>
js/src/jsapi.h
js/src/shell/Makefile.in
js/src/shell/js.cpp
js/src/shell/jsheaptools.cpp
js/src/shell/jsheaptools.h
js/src/tests/js1_8_5/extensions/findReferences-01.js
js/src/tests/js1_8_5/extensions/findReferences-02.js
js/src/tests/js1_8_5/extensions/findReferences-03.js
js/src/tests/js1_8_5/extensions/findReferences-04.js
js/src/tests/js1_8_5/extensions/jstests.list
js/src/tests/js1_8_5/extensions/shell.js
--- a/js/src/jsapi.h
+++ b/js/src/jsapi.h
@@ -1666,17 +1666,17 @@ JS_CallTracer(JSTracer *trc, void *thing
  * for the following call to JS_CallTracer.
  *
  * When printer is null, arg must be const char * or char * C string naming
  * the reference and index must be either (size_t)-1 indicating that the name
  * alone describes the reference or it must be an index into some array vector
  * that stores the reference.
  *
  * When printer callback is not null, the arg and index arguments are
- * available to the callback as debugPrinterArg and debugPrintIndex fields
+ * available to the callback as debugPrintArg and debugPrintIndex fields
  * of JSTracer.
  *
  * The storage for name or callback's arguments needs to live only until
  * the following call to JS_CallTracer returns.
  */
 #ifdef DEBUG
 # define JS_SET_TRACING_DETAILS(trc, printer, arg, index)                     \
     JS_BEGIN_MACRO                                                            \
--- a/js/src/shell/Makefile.in
+++ b/js/src/shell/Makefile.in
@@ -44,16 +44,17 @@ VPATH		= @srcdir@
 
 include $(DEPTH)/config/autoconf.mk
 
 PROGRAM         = js$(BIN_SUFFIX)
 CPPSRCS		= \
   js.cpp \
   jsworkers.cpp \
   jsoptparse.cpp \
+  jsheaptools.cpp \
   $(NULL)
 
 DEFINES         += -DEXPORT_JS_API
 
 LIBS      = $(NSPR_LIBS) $(EDITLINE_LIBS) $(DEPTH)/$(LIB_PREFIX)js_static.$(LIB_SUFFIX)
 ifdef MOZ_NATIVE_FFI
 EXTRA_LIBS += $(MOZ_FFI_LIBS)
 endif
--- a/js/src/shell/js.cpp
+++ b/js/src/shell/js.cpp
@@ -71,31 +71,33 @@
 #include "json.h"
 #include "jsparse.h"
 #include "jsreflect.h"
 #include "jsscope.h"
 #include "jsscript.h"
 #include "jstypedarray.h"
 #include "jsxml.h"
 #include "jsperf.h"
+#include "jshashtable.h"
 
 #include "prmjtime.h"
 
 #ifdef JSDEBUGGER
 #include "jsdebug.h"
 #ifdef JSDEBUGGER_JAVA_UI
 #include "jsdjava.h"
 #endif /* JSDEBUGGER_JAVA_UI */
 #ifdef JSDEBUGGER_C_UI
 #include "jsdb.h"
 #endif /* JSDEBUGGER_C_UI */
 #endif /* JSDEBUGGER */
 
 #include "jsoptparse.h"
 #include "jsworkers.h"
+#include "jsheaptools.h"
 
 #include "jsinterpinlines.h"
 #include "jsobjinlines.h"
 #include "jsscriptinlines.h"
 #include "methodjit/MethodJIT.h"
 
 #ifdef XP_UNIX
 #include <unistd.h>
@@ -4500,17 +4502,17 @@ static JSFunctionSpec shell_functions[] 
     JS_FN("help",           Help,           0,0),
     JS_FN("quit",           Quit,           0,0),
     JS_FN("assertEq",       AssertEq,       2,0),
     JS_FN("assertJit",      AssertJit,      0,0),
     JS_FN("gc",             ::GC,           0,0),
     JS_FN("gcparam",        GCParameter,    2,0),
     JS_FN("countHeap",      CountHeap,      0,0),
     JS_FN("makeFinalizeObserver", MakeFinalizeObserver, 0,0),
-    JS_FN("finalizeCount",  FinalizeCount, 0,0),
+    JS_FN("finalizeCount",  FinalizeCount,  0,0),
 #ifdef JS_GC_ZEAL
     JS_FN("gczeal",         GCZeal,         2,0),
     JS_FN("schedulegc",     ScheduleGC,     1,0),
 #endif
     JS_FN("internalConst",  InternalConst,  1,0),
     JS_FN("setDebug",       SetDebug,       1,0),
     JS_FN("setDebuggerHandler", SetDebuggerHandler, 1,0),
     JS_FN("setThrowHook",   SetThrowHook,   1,0),
@@ -4525,16 +4527,17 @@ static JSFunctionSpec shell_functions[] 
     JS_FN("disassemble",    DisassembleToString, 1,0),
     JS_FN("dis",            Disassemble,    1,0),
     JS_FN("disfile",        DisassFile,     1,0),
     JS_FN("dissrc",         DisassWithSrc,  1,0),
     JS_FN("dumpHeap",       DumpHeap,       0,0),
     JS_FN("dumpObject",     DumpObject,     1,0),
     JS_FN("notes",          Notes,          1,0),
     JS_FN("stats",          DumpStats,      1,0),
+    JS_FN("findReferences", FindReferences, 1,0),
 #endif
     JS_FN("dumpStack",      DumpStack,      1,0),
 #ifdef TEST_CVTARGS
     JS_FN("cvtargs",        ConvertArgs,    0,0),
 #endif
     JS_FN("build",          BuildDate,      0,0),
     JS_FN("clear",          Clear,          0,0),
     JS_FN("intern",         Intern,         1,0),
@@ -4658,16 +4661,18 @@ static const char *const shell_help_mess
 "    \"-r\" (disassemble recursively)\n"
 "    \"-l\" (show line numbers)",
 "dissrc([fun])            Disassemble functions with source lines",
 "dumpHeap([fileName[, start[, toFind[, maxDepth[, toIgnore]]]]])\n"
 "  Interface to JS_DumpHeap with output sent to file",
 "dumpObject()             Dump an internal representation of an object",
 "notes([fun])             Show source notes for functions",
 "stats([string ...])      Dump 'arena', 'atom', 'global' stats",
+"findReferences(target)\n"
+"  Walk the heap and return an object describing all references to target",
 #endif
 "dumpStack()              Dump the stack as an array of callees (youngest first)",
 #ifdef TEST_CVTARGS
 "cvtargs(arg1..., arg12)  Test argument formatter",
 #endif
 "build()                  Show build date and time",
 "clear([obj])             Clear properties of object",
 "intern(str)              Internalize str in the atom table",
new file mode 100644
--- /dev/null
+++ b/js/src/shell/jsheaptools.cpp
@@ -0,0 +1,570 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sw=4 et tw=99:
+ *
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is JavaScript shell workers.
+ *
+ * The Initial Developer of the Original Code is
+ * Mozilla Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2010
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Jason Orendorff <jorendorff@mozilla.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#include <string.h>
+
+#include "jsapi.h"
+
+#include "jsalloc.h"
+#include "jscntxt.h"
+#include "jscompartment.h"
+#include "jsfun.h"
+#include "jshashtable.h"
+#include "jsobj.h"
+#include "jsprf.h"
+#include "jsutil.h"
+#include "jsvalue.h"
+#include "jsvector.h"
+
+using namespace js;
+
+#ifdef DEBUG
+
+
+/*** class HeapReverser **************************************************************************/
+
+/*
+ * A class for constructing a map of the JavaScript heap, with all
+ * reference edges reversed.
+ *
+ * Unfortunately, it's not possible to build the results for findReferences
+ * while visiting things solely in the order that JS_TraceRuntime and
+ * JS_TraceChildren reaches them. For example, as you work outward from the
+ * roots, suppose an edge from thing T reaches a "gray" thing G --- G being gray
+ * because you're still in the midst of traversing its descendants. At this
+ * point, you don't know yet whether G will be a referrer or not, and so you
+ * can't tell whether T should be a referrer either. And you won't visit T
+ * again.
+ *
+ * So we take a brute-force approach. We reverse the entire graph, and then walk
+ * outward from |target| to the representable objects that refer to it, stopping
+ * at such objects.
+ */
+
+/* A JSTracer that produces a map of the heap with edges reversed. */
+class HeapReverser : public JSTracer {
+  public:
+    struct Edge;
+
+    /* Metadata for a given Cell we have visited. */
+    class Node {
+      public:
+        Node() { }
+        Node(uint32 kind) : kind(kind), incoming(), marked(false) { }
+
+        /*
+         * Move constructor and move assignment. These allow us to store our
+         * incoming edge Vector in the hash table: Vectors support moves, but
+         * not assignments or copy construction.
+         */
+        Node(MoveRef<Node> rhs)
+          : kind(rhs->kind), incoming(Move(rhs->incoming)), marked(rhs->marked) { }
+        Node &operator=(MoveRef<Node> rhs) {
+            this->~Node();
+            new(this) Node(rhs);
+            return *this;
+        }
+
+        /* What kind of Cell this is. */
+        uint32 kind;
+
+        /*
+         * A vector of this Cell's incoming edges.
+         * This must use SystemAllocPolicy because HashMap requires its elements to
+         * be constructible with no arguments.
+         */
+        Vector<Edge, 0, SystemAllocPolicy> incoming;
+
+        /* A mark bit, for other traversals. */
+        bool marked;
+
+      private:
+        Node(const Node &);
+        Node &operator=(const Node &);
+    };
+
+    /* Metadata for a heap edge we have traversed. */
+    struct Edge {
+      public:
+        Edge(char *name, void *origin) : name(name), origin(origin) { }
+        ~Edge() { free(name); }
+
+        /*
+         * Move constructor and move assignment. These allow us to live in
+         * Vectors without needing to copy our name string when the vector is
+         * resized.
+         */
+        Edge(MoveRef<Edge> rhs) : name(rhs->name), origin(rhs->origin) {
+            rhs->name = NULL;
+        }
+        Edge &operator=(MoveRef<Edge> rhs) {
+            this->~Edge();
+            new(this) Edge(rhs);
+            return *this;
+        }
+
+        /* The name of this heap edge. Owned by this Edge. */
+        char *name;
+
+        /*
+         * The Cell from which this edge originates. NULL means a root. This is
+         * a cell address instead of a Node * because Nodes live in HashMap
+         * table entries; if the HashMap reallocates its table, all pointers to
+         * the Nodes it contains would become invalid. You should look up the
+         * address here in |map| to find its Node.
+         */
+        void *origin;
+    };
+
+    /*
+     * The result of a reversal is a map from Cells' addresses to Node
+     * structures describing their incoming edges.
+     */
+    typedef HashMap<void *, Node> Map;
+    Map map;
+
+    /* Construct a HeapReverser for |context|'s heap. */
+    HeapReverser(JSContext *cx) : map(cx), work(cx), parent(NULL) {
+        context = cx;
+        callback = traverseEdgeWithThis;
+    }
+
+    bool init() { return map.init(); }
+
+    /* Build a reversed map of the heap in |map|. */
+    bool reverseHeap();
+
+  private:    
+    /*
+     * Return the name of the most recent edge this JSTracer has traversed. The
+     * result is allocated with malloc; if we run out of memory, raise an error
+     * in this HeapReverser's context and return NULL.
+     *
+     * This may not be called after that edge's call to traverseEdge has
+     * returned.
+     */
+    char *getEdgeDescription();
+
+    /* Class for setting new parent, and then restoring the original. */
+    class AutoParent {
+      public:
+        AutoParent(HeapReverser *reverser, void *newParent) : reverser(reverser) {
+            savedParent = reverser->parent;
+            reverser->parent = newParent;
+        }
+        ~AutoParent() {
+            reverser->parent = savedParent; 
+        }
+      private:
+        HeapReverser *reverser;
+        void *savedParent;
+    };
+
+    /* A work item in the stack of nodes whose children we need to traverse. */
+    struct Child {
+        Child(void *cell, uint32 kind) : cell(cell), kind(kind) { }
+        void *cell;
+        uint32 kind;
+    };
+
+    /*
+     * A stack of work items. We represent the stack explicitly to avoid
+     * overflowing the C++ stack when traversing long chains of objects.
+     */
+    Vector<Child> work; 
+
+    /* When traverseEdge is called, the Cell and kind at which the edge originated. */
+    void *parent;
+
+    /* Traverse an edge. */
+    bool traverseEdge(void *cell, uint32 kind);
+
+    /*
+     * JS_TraceRuntime and JS_TraceChildren don't propagate error returns,
+     * and out-of-memory errors, by design, don't establish an exception in
+     * |context|, so traverseEdgeWithThis uses this to communicate the
+     * result of the traversal to reverseHeap.
+     */
+    bool traversalStatus;
+
+    /* Static member function wrapping 'traverseEdge'. */
+    static void traverseEdgeWithThis(JSTracer *tracer, void *cell, uint32 kind) {
+        HeapReverser *reverser = static_cast<HeapReverser *>(tracer);
+        reverser->traversalStatus = reverser->traverseEdge(cell, kind);
+    }
+};
+
+bool
+HeapReverser::traverseEdge(void *cell, uint32 kind) {
+    /* Capture this edge before the JSTracer members get overwritten. */
+    char *edgeDescription = getEdgeDescription();
+    if (!edgeDescription)
+        return false;
+    Edge e(edgeDescription, parent);
+
+    Map::AddPtr a = map.lookupForAdd(cell);
+    if (!a) {
+        /*
+         * We've never visited this cell before. Add it to the map (thus
+         * marking it as visited), and put it on the work stack, to be
+         * visited from the main loop.
+         */
+        Node n(kind);
+        uint32 generation = map.generation();
+        if (!map.add(a, cell, Move(n)) ||
+            !work.append(Child(cell, kind)))
+            return false;
+        /* If the map has been resized, re-check the pointer. */
+        if (map.generation() != generation)
+            a = map.lookupForAdd(cell);
+    }
+
+    /* Add this edge to the reversed map. */
+    return a->value.incoming.append(Move(e));
+}
+
+bool
+HeapReverser::reverseHeap() {
+    /* Prime the work stack with the roots of collection. */
+    JS_TraceRuntime(this);
+    if (!traversalStatus)
+        return false;
+
+    /* Traverse children until the stack is empty. */
+    while (!work.empty()) {
+        const Child child = work.popCopy();
+        AutoParent autoParent(this, child.cell);
+        JS_TraceChildren(this, child.cell, child.kind);
+        if (!traversalStatus)
+            return false;
+    }
+
+    return true;
+}
+
+char *
+HeapReverser::getEdgeDescription()
+{
+    if (!debugPrinter && debugPrintIndex == (size_t) -1) {
+        const char *arg = static_cast<const char *>(debugPrintArg);
+        char *name = static_cast<char *>(context->malloc_(strlen(arg) + 1));
+        if (!name)
+            return NULL;
+        strcpy(name, arg);
+        return name;
+    }
+
+    /* Lovely; but a fixed size is required by JSTraceNamePrinter. */
+    static const int nameSize = 200;
+    char *name = static_cast<char *>(context->malloc_(nameSize));
+    if (!name)
+        return NULL;
+    if (debugPrinter)
+        debugPrinter(this, name, nameSize);
+    else
+        JS_snprintf(name, nameSize, "%s[%lu]",
+                    static_cast<const char *>(debugPrintArg), debugPrintIndex);
+
+    /* Shrink storage to fit. */
+    return static_cast<char *>(context->realloc_(name, strlen(name) + 1));
+}
+
+
+/*** class ReferenceFinder ***********************************************************************/
+
+/* A class for finding an object's referrers, given a reversed heap map. */
+class ReferenceFinder {
+  public:
+    ReferenceFinder(JSContext *cx, const HeapReverser &reverser) 
+      : context(cx), reverser(reverser) { }
+
+    /* Produce an object describing all references to |target|. */
+    JSObject *findReferences(JSObject *target);
+
+  private:
+    /* The context in which to do allocation and error-handling. */
+    JSContext *context;
+
+    /* A reversed map of the current heap. */
+    const HeapReverser &reverser;
+
+    /* The results object we're currently building. */
+    JSObject *result;
+
+    /* A list of edges we've traversed to get to a certain point. */
+    class Path {
+      public:
+        Path(const HeapReverser::Edge &edge, Path *next) : edge(edge), next(next) { }
+        
+        /*
+         * Compute the full path represented by this Path. The result is
+         * owned by the caller.
+         */
+        char *computeName(JSContext *cx);
+
+      private:
+        const HeapReverser::Edge &edge;
+        Path *next;
+    };
+
+    struct AutoNodeMarker {
+        AutoNodeMarker(HeapReverser::Node *node) : node(node) { node->marked = true; }
+        ~AutoNodeMarker() { node->marked = false; }
+      private:
+        HeapReverser::Node *node;
+    };
+
+    /* 
+     * Given that we've reached |cell| via |path|, with all Nodes along that
+     * path marked, add paths from all reportable objects reachable from cell
+     * to |result|.
+     */
+    bool visit(void *cell, Path *path);
+
+    /*
+     * If |cell|, of |kind|, is representable as a JavaScript value, return that
+     * value; otherwise, return JSVAL_VOID.
+     */
+    jsval representable(void *cell, int kind) {
+        if (kind == JSTRACE_OBJECT) {
+            JSObject *object = static_cast<JSObject *>(cell);
+
+            /* Certain classes of object are for internal use only. */
+            JSClass *clasp = JS_GET_CLASS(context, object);
+            if (clasp == Jsvalify(&js_BlockClass) ||
+                clasp == Jsvalify(&js_CallClass) ||
+                clasp == Jsvalify(&js_WithClass) ||
+                clasp == Jsvalify(&js_DeclEnvClass))
+                return JSVAL_VOID;
+
+            /* Internal function objects should also not be revealed. */
+            if (JS_ObjectIsFunction(context, object) && IsInternalFunctionObject(object))
+                return JSVAL_VOID;
+
+            return OBJECT_TO_JSVAL(object);
+        }
+
+        return JSVAL_VOID;
+    }
+
+    /* Add |referrer| as something that refers to |target| via |path|. */
+    bool addReferrer(jsval referrer, Path *path);
+};
+
+bool
+ReferenceFinder::visit(void *cell, Path *path)
+{
+    /* In ReferenceFinder, paths will almost certainly fit on the C++ stack. */
+    JS_CHECK_RECURSION(context, return false);
+
+    /* Have we reached a root? Always report that. */
+    if (!cell)
+        return addReferrer(JSVAL_NULL, path);
+        
+    HeapReverser::Map::Ptr p = reverser.map.lookup(cell);
+    JS_ASSERT(p);
+    HeapReverser::Node *node = &p->value;
+
+    /* Is |cell| a representable cell, reached via a non-empty path? */
+    if (path != NULL) {
+        jsval representation = representable(cell, node->kind);
+        if (!JSVAL_IS_VOID(representation))
+            return addReferrer(representation, path);
+    }
+
+    /*
+     * If we've made a cycle, don't traverse further. We *do* want to include
+     * paths from the target to itself, so we don't want to do this check until
+     * after we've possibly reported this cell as a referrer.
+     */
+    if (node->marked)
+        return true;
+    AutoNodeMarker marker(node);
+
+    /* Visit the origins of all |cell|'s incoming edges. */
+    for (size_t i = 0; i < node->incoming.length(); i++) {
+        const HeapReverser::Edge &edge = node->incoming[i];
+        Path extendedPath(edge, path);
+        if (!visit(edge.origin, &extendedPath))
+            return false;
+    }
+
+    return true;
+}
+
+char *
+ReferenceFinder::Path::computeName(JSContext *cx)
+{
+    /* Walk the edge list and compute the total size of the path. */
+    size_t size = 6;
+    for (Path *l = this; l; l = l->next) 
+        size += strlen(l->edge.name) + (l->next ? 2 : 0);
+    size += 1;
+
+    char *path = static_cast<char *>(cx->malloc_(size));
+    if (!path)
+        return NULL;
+
+    /*
+     * Walk the edge list again, and copy the edge names into place, with
+     * appropriate separators. Note that we constructed the edge list from
+     * target to referrer, which means that the list links point *towards* the
+     * target, so we can walk the list and build the path from left to right.
+     */
+    strcpy(path, "edge: ");
+    char *next = path + 6;
+    for (Path *l = this; l; l = l->next) {
+        strcpy(next, l->edge.name);
+        next += strlen(next);
+        if (l->next) {
+            strcpy(next, "; ");
+            next += 2;
+        }
+    }
+    JS_ASSERT(next + 1 == path + size);
+
+    return path;
+}
+
+bool
+ReferenceFinder::addReferrer(jsval referrer, Path *path)
+{
+    if (!context->compartment->wrap(context, Valueify(&referrer)))
+        return NULL;
+
+    char *pathName = path->computeName(context);
+    if (!pathName)
+        return false;
+    AutoReleasePtr releasePathName(context, pathName);
+
+    /* Find the property of the results object named |pathName|. */
+    jsval v;
+    if (!JS_GetProperty(context, result, pathName, &v))
+        return false;
+    if (JSVAL_IS_VOID(v)) {
+        /* Create an array to accumulate referents under this path. */
+        JSObject *array = JS_NewArrayObject(context, 1, &referrer);
+        if (!array)
+            return false;
+        v = OBJECT_TO_JSVAL(array);
+        return !!JS_SetProperty(context, result, pathName, &v);
+    }
+
+    /* The property's value had better be an array. */
+    JS_ASSERT(JSVAL_IS_OBJECT(v) && !JSVAL_IS_NULL(v));
+    JSObject *array = JSVAL_TO_OBJECT(v);
+    JS_ASSERT(JS_IsArrayObject(context, array));
+
+    /* Append our referrer to this array. */
+    jsuint length;
+    return JS_GetArrayLength(context, array, &length) &&
+           JS_SetElement(context, array, length, &referrer);
+}
+
+JSObject *
+ReferenceFinder::findReferences(JSObject *target)
+{
+    result = JS_NewObject(context, NULL, NULL, NULL);
+    if (!result)
+        return NULL;
+    if (!visit(target, NULL))
+        return NULL;
+
+    return result;
+}
+
+/*
+ * findReferences(thing)
+ *
+ * Walk the entire heap, looking for references to |thing|, and return a
+ * "references object" describing what we found.
+ *
+ * Each property of the references object describes one kind of reference. The
+ * property's name is the label supplied to MarkObject, JS_CALL_TRACER, or what
+ * have you, prefixed with "edge: " to avoid collisions with system properties
+ * (like "toString" and "__proto__"). The property's value is an array of things
+ * that refer to |thing| via that kind of reference. Ordinary references from
+ * one object to another are named after the property name (with the "edge: "
+ * prefix).
+ *
+ * Garbage collection roots appear as references from 'null'. We use the name
+ * given to the root (with the "edge: " prefix) as the name of the reference.
+ *
+ * Note that the references object does record references from objects that are
+ * only reachable via |thing| itself, not just the references reachable
+ * themselves from roots that keep |thing| from being collected. (We could make
+ * this distinction if it is useful.)
+ *
+ * If any references are found by the conservative scanner, the references
+ * object will have a property named "edge: machine stack"; the referrers will
+ * be 'null', because they are roots.
+ */
+JSBool
+FindReferences(JSContext *cx, uintN argc, jsval *vp)
+{
+    if (argc < 1) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_MORE_ARGS_NEEDED,
+                             "findReferences", 1, "");
+        return false;
+    }
+
+    jsval target = JS_ARGV(cx, vp)[0];
+    if (!JSVAL_IS_OBJECT(target) || JSVAL_IS_NULL(target)) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_UNEXPECTED_TYPE,
+                             "argument", "not an object");
+        return false;
+    }
+
+    /* Walk the JSRuntime, producing a reversed map of the heap. */
+    HeapReverser reverser(cx);
+    if (!reverser.init() || !reverser.reverseHeap())
+        return false;
+
+    /* Given the reversed map, find the referents of target. */
+    ReferenceFinder finder(cx, reverser);
+    JSObject *references = finder.findReferences(JSVAL_TO_OBJECT(target));
+    if (!references)
+        return false;
+    
+    JS_SET_RVAL(cx, vp, OBJECT_TO_JSVAL(references));
+    return true;
+}
+
+#endif /* DEBUG */
new file mode 100644
--- /dev/null
+++ b/js/src/shell/jsheaptools.h
@@ -0,0 +1,50 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sw=4 et tw=99:
+ *
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is JavaScript shell workers.
+ *
+ * The Initial Developer of the Original Code is
+ * Mozilla Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2010
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Jim Blandy <jimb@mozilla.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#ifndef jsheaptools_h___
+#define jsheaptools_h___
+
+#include "jsapi.h"
+
+#ifdef DEBUG
+JSBool FindReferences(JSContext *cx, uintN argc, jsval *vp);
+#endif /* DEBUG */
+
+#endif /* jsheaptools_h___ */
new file mode 100644
--- /dev/null
+++ b/js/src/tests/js1_8_5/extensions/findReferences-01.js
@@ -0,0 +1,52 @@
+// Any copyright is dedicated to the Public Domain.
+// http://creativecommons.org/licenses/publicdomain/
+// Contributor: Jim Blandy
+
+if (typeof findReferences == "function") {
+    function C() {}
+    var o = new C;
+    o.x = {};               // via ordinary property
+    o[42] = {};             // via numeric property
+    o.myself = o;           // self-references should be reported
+    o.alsoMyself = o;       // multiple self-references should all be reported
+
+    assertEq(referencesVia(o, 'proto', C.prototype), true);
+    assertEq(referencesVia(o, 'parent', this), true);
+    assertEq(referencesVia(o, 'x', o.x), true);
+    assertEq(referencesVia(o, '42', o[42]), true);
+    assertEq(referencesVia(o, 'myself', o), true);
+    assertEq(referencesVia(o, 'alsoMyself', o), true);
+
+    function g() { return 42; }
+    function s(v) { }
+    var p = Object.defineProperty({}, 'a', { get:g, set:s });
+    assertEq(referencesVia(p, 'shape; a getter', g), true);
+    assertEq(referencesVia(p, 'shape; a setter', s), true);
+
+    // If there are multiple objects with the same shape referring to a getter
+    // or setter, findReferences should get all of them, even though the shape
+    // gets 'marked' the first time we visit it.
+    var q = Object.defineProperty({}, 'a', { get:g, set:s });
+    assertEq(referencesVia(p, 'shape; a getter', g), true);
+    assertEq(referencesVia(q, 'shape; a getter', g), true);
+
+    // If we extend each object's shape chain, both should still be able to
+    // reach the getter, even though the two shapes are each traversed twice.
+    p.b = 9;
+    q.b = 9;
+    assertEq(referencesVia(p, 'shape; a getter', g), true);
+    assertEq(referencesVia(q, 'shape; a getter', g), true);
+
+    // These are really just ordinary own property references.
+    assertEq(referencesVia(C, 'prototype', Object.getPrototypeOf(o)), true);
+    assertEq(referencesVia(Object.getPrototypeOf(o), 'constructor', C), true);
+
+    // Dense arrays should work, too.
+    a = [];
+    a[1] = o;
+    assertEq(referencesVia(a, 'element[1]', o), true);
+
+    reportCompare(true, true);
+} else {
+    reportCompare(true, true, "test skipped: findReferences is not a function");
+}
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/js/src/tests/js1_8_5/extensions/findReferences-02.js
@@ -0,0 +1,28 @@
+// Any copyright is dedicated to the Public Domain.
+// http://creativecommons.org/licenses/publicdomain/
+// Contributor: Jim Blandy
+
+if (typeof findReferences == "function") {
+    (function f() {
+         assertEq(referencesVia(arguments, 'callee', f), true);
+     })();
+
+    var o = ({});
+
+    function returnFlat(x) { return function flat() { return x; }; }
+    assertEq(referencesVia(returnFlat(o), 'upvars[0]', o), true);
+
+    function returnHeavy(y) { eval(''); return function heavy() { return y; }; }
+    assertEq(referencesVia(returnHeavy(o), 'parent; y', o), true);
+    assertEq(referencesVia(returnHeavy(o), 'parent; parent', this), true);
+
+    function returnBlock(z) { eval(''); let(w = z) { return function block() { return w; }; }; }
+    assertEq(referencesVia(returnBlock(o), 'parent; w', o), true);
+
+    function returnWithObj(v) { with(v) return function withObj() { return u; }; }
+    assertEq(referencesVia(returnWithObj(o), 'parent; proto', o), true);
+
+    reportCompare(true, true);
+} else {
+    reportCompare(true, true, "test skipped: findReferences is not a function");
+}
new file mode 100644
--- /dev/null
+++ b/js/src/tests/js1_8_5/extensions/findReferences-03.js
@@ -0,0 +1,41 @@
+// Any copyright is dedicated to the Public Domain.
+// http://creativecommons.org/licenses/publicdomain/
+// Contributor: Jim Blandy
+
+if (typeof findReferences == "function") {
+
+    function makeGenerator(c) { eval(c); yield function generatorClosure() { return x; }; }
+    var generator = makeGenerator('var x = 42');
+    var closure = generator.next();
+    referencesVia(closure, 'parent; generator object', generator);
+
+    var o = {};
+
+    assertEq(function f() { return referencesVia(null, 'arguments', arguments); } (), true);
+
+    var rvalueCorrect;
+
+    function finallyHoldsRval() {
+        try {
+            return o;
+        } finally {
+            rvalueCorrect = referencesVia(null, 'rval', o);
+        }
+    }
+    rvalueCorrect = false;
+    finallyHoldsRval();
+    assertEq(rvalueCorrect, true);
+
+    // Because we don't distinguish between JavaScript stack marking and C++
+    // stack marking (both use the conservative scanner), we can't really write
+    // the following tests meaningfully:
+    //   generator frame -> generator object
+    //   stack frame -> local variables
+    //   stack frame -> this
+    //   stack frame -> callee
+    //   for(... in x) loop's reference to x
+
+    reportCompare(true, true);
+} else {
+    reportCompare(true, true, "test skipped: findReferences is not a function");
+}
\ No newline at end of file
new file mode 100644
--- /dev/null
+++ b/js/src/tests/js1_8_5/extensions/findReferences-04.js
@@ -0,0 +1,18 @@
+// Any copyright is dedicated to the Public Domain.
+// http://creativecommons.org/licenses/publicdomain/
+// Contributor: Jim Blandy
+
+if (typeof findReferences == "function") {
+
+    var global = newGlobal('new-compartment');
+    var o = ({});
+    global.o = o;
+
+    // Don't trip a cross-compartment reference assertion.
+    findReferences(o);
+
+    reportCompare(true, true);
+
+} else {
+    reportCompare(true, true, "test skipped: findReferences is not a function");
+}
--- a/js/src/tests/js1_8_5/extensions/jstests.list
+++ b/js/src/tests/js1_8_5/extensions/jstests.list
@@ -25,16 +25,20 @@ skip-if(!xulRuntime.shell) script clone-
 skip-if(!xulRuntime.shell) script clone-leaf-object.js
 skip-if(!xulRuntime.shell) script clone-object.js
 skip-if(!xulRuntime.shell) script clone-typed-array.js
 skip-if(!xulRuntime.shell) script clone-errors.js
 skip-if(!xulRuntime.shell) script clone-forge.js
 skip-if(!xulRuntime.shell) script clone-complex-object.js
 script set-property-non-extensible.js
 script recursion.js
+script findReferences-01.js
+script findReferences-02.js
+script findReferences-03.js
+script findReferences-04.js
 script regress-627859.js
 script regress-627984-1.js
 script regress-627984-2.js
 script regress-627984-3.js
 script regress-627984-4.js
 script regress-627984-5.js
 script regress-627984-6.js
 script regress-627984-7.js
--- a/js/src/tests/js1_8_5/extensions/shell.js
+++ b/js/src/tests/js1_8_5/extensions/shell.js
@@ -165,8 +165,32 @@ var Match =
 
         return matchObject(act, exp);
     }
 
     return { Pattern: Pattern,
              MatchError: MatchError };
 
 })();
+
+function referencesVia(from, edge, to) {
+    edge = "edge: " + edge;
+    var edges = findReferences(to);
+    if (edge in edges && edges[edge].indexOf(from) != -1)
+        return true;
+
+    // Be nice: make it easy to fix if the edge name has just changed.
+    var alternatives = [];
+    for (var e in edges) {
+        if (edges[e].indexOf(from) != -1)
+            alternatives.push(e);
+    }
+    if (alternatives.length == 0) {
+        print("referent not referred to by referrer after all");
+    } else {
+        print("referent is not referenced via: " + uneval(edge));
+        print("but it is referenced via:       " + uneval(alternatives));
+    }
+    print("all incoming edges, from any object:");
+    for (var e in edges)
+        print(e);
+    return false;
+}