Bug 960786: SpiderMonkey should provide an introspection API for memory heap analysis (ubi::Node) r=sfink
authorJim Blandy <jimb@mozilla.com>
Mon, 16 Jun 2014 15:18:57 -0700
changeset 188952 3d405f960e94e79b07f3720683d3a04829af176b
parent 188951 0033c281d90d6bcde616011a70589591bf52902a
child 188953 412e31d5a16947768ec3a8e645fe5b739ce2464b
push id1
push userroot
push dateMon, 20 Oct 2014 17:29:22 +0000
reviewerssfink
bugs960786
milestone33.0a1
Bug 960786: SpiderMonkey should provide an introspection API for memory heap analysis (ubi::Node) r=sfink
js/public/UbiNode.h
js/public/UbiNodeTraverse.h
js/src/builtin/TestingFunctions.cpp
js/src/jit-test/tests/heap-analysis/findPath.js
js/src/jsapi-tests/testIntTypesABI.cpp
js/src/moz.build
js/src/tests/js1_8_5/extensions/shell.js
js/src/vm/UbiNode.cpp
new file mode 100644
--- /dev/null
+++ b/js/public/UbiNode.h
@@ -0,0 +1,462 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef js_UbiNode_h
+#define js_UbiNode_h
+
+#include "mozilla/Alignment.h"
+#include "mozilla/Assertions.h"
+#include "mozilla/Attributes.h"
+#include "mozilla/Move.h"
+
+#include "jspubtd.h"
+
+#include "js/GCAPI.h"
+#include "js/HashTable.h"
+#include "js/TypeDecls.h"
+
+// JS::ubi::Node
+//
+// JS::ubi::Node is a pointer-like type designed for internal use by heap
+// analysis tools. A ubi::Node can refer to:
+//
+// - a JS value, like a string or object;
+// - an internal SpiderMonkey structure, like a shape or a scope chain object
+// - an instance of some embedding-provided type: in Firefox, an XPCOM
+//   object, or an internal DOM node class instance
+//
+// A ubi::Node instance provides metadata about its referent, and can
+// enumerate its referent's outgoing edges, so you can implement heap analysis
+// algorithms that walk the graph - finding paths between objects, or
+// computing heap dominator trees, say - using ubi::Node, while remaining
+// ignorant of the details of the types you're operating on.
+//
+// Of course, when it comes to presenting the results in a developer-facing
+// tool, you'll need to stop being ignorant of those details, because you have
+// to discuss the ubi::Nodes' referents with the developer. Here, ubi::Node
+// can hand you dynamically checked, properly typed pointers to the original
+// objects via the as<T> method, or generate descriptions of the referent
+// itself.
+//
+// ubi::Node instances are lightweight (two-word) value types. Instances:
+// - compare equal if and only if they refer to the same object;
+// - have hash values that respect their equality relation; and
+// - have serializations that are only equal if the ubi::Nodes are equal.
+//
+// A ubi::Node is only valid for as long as its referent is alive; if its
+// referent goes away, the ubi::Node becomes a dangling pointer. A ubi::Node
+// that refers to a GC-managed object is not automatically a GC root; if the
+// GC frees or relocates its referent, the ubi::Node becomes invalid. A
+// ubi::Node that refers to a reference-counted object does not bump the
+// reference count.
+//
+// ubi::Node values require no supporting data structures, making them
+// feasible for use in memory-constrained devices --- ideally, the memory
+// requirements of the algorithm which uses them will be the limiting factor,
+// not the demands of ubi::Node itself.
+//
+// One can construct a ubi::Node value given a pointer to a type that ubi::Node
+// supports. In the other direction, one can convert a ubi::Node back to a
+// pointer; these downcasts are checked dynamically. In particular, one can
+// convert a 'JSRuntime *' to a ubi::Node, yielding a node with an outgoing edge
+// for every root registered with the runtime; starting from this, one can walk
+// the entire heap. (Of course, one could also start traversal at any other kind
+// of type to which one has a pointer.)
+//
+//
+// Extending ubi::Node To Handle Your Embedding's Types
+//
+// To add support for a new ubi::Node referent type R, you must define a
+// specialization of the ubi::Concrete template, ubi::Concrete<R>, which
+// inherits from ubi::Base. ubi::Node itself uses the specialization for
+// compile-time information (i.e. the checked conversions between R * and
+// ubi::Node), and the inheritance for run-time dispatching.
+//
+//
+// ubi::Node Exposes Implementation Details
+//
+// In many cases, a JavaScript developer's view of their data differs
+// substantially from its actual implementation. For example, while the
+// ECMAScript specification describes objects as maps from property names to
+// sets of attributes (like ECMAScript's [[Value]]), in practice many objects
+// have only a pointer to a shape, shared with other similar objects, and
+// indexed slots that contain the [[Value]] attributes. As another example, a
+// string produced by concatenating two other strings may sometimes be
+// represented by a "rope", a structure that points to the two original
+// strings.
+//
+
+// We intend to use ubi::Node to write tools that report memory usage, so it's
+// important that ubi::Node accurately portray how much memory nodes consume.
+// Thus, for example, when data that apparently belongs to multiple nodes is
+// in fact shared in a common structure, ubi::Node's graph uses a separate
+// node for that shared structure, and presents edges to it from the data's
+// apparent owners. For example, ubi::Node exposes SpiderMonkey objects'
+// shapes and base shapes, and exposes rope string and substring structure,
+// because these optimizations become visible when a tool reports how much
+// memory a structure consumes.
+//
+// However, fine granularity is not a goal. When a particular object is the
+// exclusive owner of a separate block of memory, ubi::Node may present the
+// object and its block as a single node, and add their sizes together when
+// reporting the node's size, as there is no meaningful loss of data in this
+// case. Thus, for example, a ubi::Node referring to a JavaScript object, when
+// asked for the object's size in bytes, includes the object's slot and
+// element arrays' sizes in the total. There is no separate ubi::Node value
+// representing the slot and element arrays, since they are owned exclusively
+// by the object.
+//
+//
+// Presenting Analysis Results To JavaScript Developers
+//
+// If an analysis provides its results in terms of ubi::Node values, a user
+// interface presenting those results will generally need to clean them up
+// before they can be understood by JavaScript developers. For example,
+// JavaScript developers should not need to understand shapes, only JavaScript
+// objects. Similarly, they should not need to understand the distinction
+// between DOM nodes and the JavaScript shadow objects that represent them.
+//
+//
+// Rooting Restrictions
+//
+// At present there is no way to root ubi::Node instances, so instances can't be
+// live across any operation that might GC. Analyses using ubi::Node must either
+// run to completion and convert their results to some other rootable type, or
+// save their intermediate state in some rooted structure if they must GC before
+// they complete. (For algorithms like path-finding and dominator tree
+// computation, we implement the algorithm avoiding any operation that could
+// cause a GC --- and use AutoCheckCannotGC to verify this.)
+//
+// If this restriction prevents us from implementing interesting tools, we may
+// teach the GC how to root ubi::Nodes, fix up hash tables that use them as
+// keys, etc.
+
+
+// Forward declarations of SpiderMonkey's ubi::Node reference types.
+namespace js {
+class LazyScript;
+class Shape;
+class BaseShape;
+namespace jit {
+class JitCode;
+}
+namespace types {
+struct TypeObject;
+}
+}
+
+
+namespace JS {
+namespace ubi {
+
+class Edge;
+class EdgeRange;
+
+// The base class implemented by each ubi::Node referent type. Subclasses must
+// not add data members to this class.
+class Base {
+    friend class Node;
+
+    // For performance's sake, we'd prefer to avoid a virtual destructor; and
+    // an empty constructor seems consistent with the 'lightweight value type'
+    // visible behavior we're trying to achieve. But if the destructor isn't
+    // virtual, and a subclass overrides it, the subclass's destructor will be
+    // ignored. Is there a way to make the compiler catch that error?
+
+  protected:
+    // Space for the actual pointer. Concrete subclasses should define a
+    // properly typed 'get' member function to access this.
+    void *ptr;
+
+    Base(void *ptr) : ptr(ptr) { }
+
+  public:
+    bool operator==(const Base &rhs) const {
+        // Some compilers will indeed place objects of different types at
+        // the same address, so technically, we should include the vtable
+        // in this comparison. But it seems unlikely to cause problems in
+        // practice.
+        return ptr == rhs.ptr;
+    }
+    bool operator!=(const Base &rhs) const { return !(*this == rhs); }
+
+    // Return a human-readable name for the referent's type. The result should
+    // be statically allocated. (You can use MOZ_UTF16("strings") for this.)
+    //
+    // This must always return Concrete<T>::concreteTypeName; we use that
+    // pointer as a tag for this particular referent type.
+    virtual const jschar *typeName() const = 0;
+
+    // Return the size of this node, in bytes. Include any structures that this
+    // node owns exclusively that are not exposed as their own ubi::Nodes.
+    virtual size_t size() const = 0;
+
+    // Return an EdgeRange that initially contains all the referent's outgoing
+    // edges. The EdgeRange should be freed with 'js_delete'. (You could use
+    // ScopedDJSeletePtr<EdgeRange> to manage it.) On OOM, report an exception
+    // on |cx| and return nullptr.
+    virtual EdgeRange *edges(JSContext *cx) const = 0;
+
+  private:
+    Base(const Base &rhs) MOZ_DELETE;
+    Base &operator=(const Base &rhs) MOZ_DELETE;
+};
+
+// A traits template with a specialization for each referent type that
+// ubi::Node supports. The specialization must be the concrete subclass of
+// Base that represents a pointer to the referent type. It must also
+// include the members described here.
+template<typename Referent>
+struct Concrete {
+    // The specific jschar array returned by Concrete<T>::typeName.
+    static const jschar concreteTypeName[];
+
+    // Construct an instance of this concrete class in |storage| referring
+    // to |referent|. Implementations typically use a placement 'new'.
+    //
+    // In some cases, |referent| will contain dynamic type information that
+    // identifies it a some more specific subclass of |Referent|. For example,
+    // when |Referent| is |JSObject|, then |referent->getClass()| could tell us
+    // that it's actually a JSFunction. Similarly, if |Referent| is
+    // |nsISupports|, we would like a ubi::Node that knows its final
+    // implementation type.
+    //
+    // So, we delegate the actual construction to this specialization, which
+    // knows Referent's details.
+    static void construct(void *storage, Referent *referent);
+};
+
+// A container for a Base instance; all members simply forward to the contained instance.
+// This container allows us to pass ubi::Node instances by value.
+class Node {
+    // Storage in which we allocate Base subclasses.
+    mozilla::AlignedStorage2<Base> storage;
+    Base *base() { return storage.addr(); }
+    const Base *base() const { return storage.addr(); }
+
+    template<typename T>
+    void construct(T *ptr) {
+        static_assert(sizeof(Concrete<T>) == sizeof(*base()),
+                      "ubi::Base specializations must be the same size as ubi::Base");
+        Concrete<T>::construct(base(), ptr);
+    }
+
+    typedef void (Node::* ConvertibleToBool)();
+    void nonNull() {}
+
+  public:
+    Node() { construct<void>(nullptr); }
+
+    template<typename T>
+    Node(T *ptr) {
+        construct(ptr);
+    }
+    template<typename T>
+    Node &operator=(T *ptr) {
+        construct(ptr);
+        return *this;
+    }
+
+    // We can construct and assign from rooted forms of pointers.
+    template<typename T>
+    Node(const Rooted<T *> &root) {
+        construct(root.get());
+    }
+    template<typename T>
+    Node &operator=(const Rooted<T *> &root) {
+        construct(root.get());
+        return *this;
+    }
+
+    // Constructors accepting SpiderMonkey's other generic-pointer-ish types.
+    Node(JS::Value value);
+    Node(JSGCTraceKind kind, void *ptr);
+
+    // copy construction and copy assignment just use memcpy, since we know
+    // instances contain nothing but a vtable pointer and a data pointer.
+    //
+    // To be completely correct, concrete classes could provide a virtual
+    // 'construct' member function, which we could invoke on rhs to construct an
+    // instance in our storage. But this is good enough; there's no need to jump
+    // through vtables for copying and assignment that are just going to move
+    // two words around. The compiler knows how to optimize memcpy.
+    Node(const Node &rhs) {
+        memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u));
+    }
+
+    Node &operator=(const Node &rhs) {
+        memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u));
+        return *this;
+    }
+
+    bool operator==(const Node &rhs) const { return *base() == *rhs.base(); }
+    bool operator!=(const Node &rhs) const { return *base() != *rhs.base(); }
+
+    operator ConvertibleToBool() const {
+        return base()->ptr ? &Node::nonNull : 0;
+    }
+
+    template<typename T>
+    bool is() const {
+        return base()->typeName() == Concrete<T>::concreteTypeName;
+    }
+
+    template<typename T>
+    T *as() const {
+        MOZ_ASSERT(is<T>());
+        return static_cast<T *>(base()->ptr);
+    }
+
+    template<typename T>
+    T *asOrNull() const {
+        return is<T>() ? static_cast<T *>(base()->ptr) : nullptr;
+    }
+
+    // If this node refers to something that can be represented as a
+    // JavaScript value that is safe to expose to JavaScript code, return that
+    // value. Otherwise return UndefinedValue(). JSStrings and some (but not
+    // all!) JSObjects can be exposed.
+    JS::Value exposeToJS() const;
+
+    const jschar *typeName()        const { return base()->typeName(); }
+    size_t size()                   const { return base()->size(); }
+    EdgeRange *edges(JSContext *cx) const { return base()->edges(cx); }
+
+    // A hash policy for ubi::Nodes.
+    // This simply uses the stock PointerHasher on the ubi::Node's pointer.
+    // We specialize DefaultHasher below to make this the default.
+    class HashPolicy {
+        typedef js::PointerHasher<void *, mozilla::tl::FloorLog2<sizeof(void *)>::value> PtrHash;
+
+      public:
+        typedef Node Lookup;
+
+        static js::HashNumber hash(const Lookup &l) { return PtrHash::hash(l.base()->ptr); }
+        static bool match(const Node &k, const Lookup &l) { return k == l; }
+        static void rekey(Node &k, const Node &newKey) { k = newKey; }
+    };
+};
+
+
+// Edge is the abstract base class representing an outgoing edge of a node.
+// Edges are owned by EdgeRanges, and need not have assignment operators or copy
+// constructors.
+//
+// Each Edge class should inherit from this base class, overriding as
+// appropriate.
+class Edge {
+  protected:
+    Edge() : name(nullptr), referent() { }
+    virtual ~Edge() { }
+
+  public:
+    // This edge's name.
+    //
+    // The storage is owned by this Edge, and will be freed when this Edge is
+    // destructed.
+    //
+    // (In real life we'll want a better representation for names, to avoid
+    // creating tons of strings when the names follow a pattern; and we'll need
+    // to think about lifetimes carefully to ensure traversal stays cheap.)
+    const jschar *name;
+
+    // This edge's referent.
+    Node referent;
+
+  private:
+    Edge(const Edge &) MOZ_DELETE;
+    Edge &operator=(const Edge &) MOZ_DELETE;
+};
+
+
+// EdgeRange is an abstract base class for iterating over a node's outgoing
+// edges. (This is modeled after js::HashTable<K,V>::Range.)
+//
+// Concrete instances of this class need not be as lightweight as Node itself,
+// since they're usually only instantiated while iterating over a particular
+// object's edges. For example, a dumb implementation for JS Cells might use
+// JS_TraceChildren to to get the outgoing edges, and then store them in an
+// array internal to the EdgeRange.
+class EdgeRange {
+  protected:
+    // The current front edge of this range, or nullptr if this range is empty.
+    Edge *front_;
+
+    EdgeRange() : front_(nullptr) { }
+
+  public:
+    virtual ~EdgeRange() { };
+
+    // True if there are no more edges in this range.
+    bool empty() const { return !front_; }
+
+    // The front edge of this range. This is owned by the EdgeRange, and is
+    // only guaranteed to live until the next call to popFront, or until
+    // the EdgeRange is destructed.
+    const Edge &front() { return *front_; }
+
+    // Remove the front edge from this range. This should only be called if
+    // !empty().
+    virtual void popFront() = 0;
+
+  private:
+    EdgeRange(const EdgeRange &) MOZ_DELETE;
+    EdgeRange &operator=(const EdgeRange &) MOZ_DELETE;
+};
+
+
+// Concrete classes for ubi::Node referent types.
+
+// A reusable ubi::Concrete specialization base class for types supported by
+// JS_TraceChildren.
+template<typename Referent>
+class TracerConcrete : public Base {
+    const jschar *typeName() const MOZ_OVERRIDE { return concreteTypeName; }
+    size_t size() const MOZ_OVERRIDE { return 0; } // not implemented yet; bug 1011300
+    EdgeRange *edges(JSContext *) const MOZ_OVERRIDE;
+
+    TracerConcrete(Referent *ptr) : Base(ptr) { }
+
+  public:
+    static const jschar concreteTypeName[];
+    static void construct(void *storage, Referent *ptr) { new (storage) TracerConcrete(ptr); };
+};
+
+template<> struct Concrete<JSObject> : TracerConcrete<JSObject> { };
+template<> struct Concrete<JSString> : TracerConcrete<JSString> { };
+template<> struct Concrete<JSScript> : TracerConcrete<JSScript> { };
+template<> struct Concrete<js::LazyScript> : TracerConcrete<js::LazyScript> { };
+template<> struct Concrete<js::jit::JitCode> : TracerConcrete<js::jit::JitCode> { };
+template<> struct Concrete<js::Shape> : TracerConcrete<js::Shape> { };
+template<> struct Concrete<js::BaseShape> : TracerConcrete<js::BaseShape> { };
+template<> struct Concrete<js::types::TypeObject> : TracerConcrete<js::types::TypeObject> { };
+
+// The ubi::Node null pointer. Any attempt to operate on a null ubi::Node asserts.
+template<>
+class Concrete<void> : public Base {
+    const jschar *typeName() const MOZ_OVERRIDE;
+    size_t size() const MOZ_OVERRIDE;
+    EdgeRange *edges(JSContext *cx) const MOZ_OVERRIDE;
+
+    Concrete(void *ptr) : Base(ptr) { }
+
+  public:
+    static void construct(void *storage, void *ptr) { new (storage) Concrete(ptr); }
+    static const jschar concreteTypeName[];
+};
+
+
+} // namespace ubi
+} // namespace JS
+
+namespace js {
+
+// Make ubi::Node::HashPolicy the default hash policy for ubi::Node.
+template<> struct DefaultHasher<JS::ubi::Node> : JS::ubi::Node::HashPolicy { };
+
+} // namespace js
+
+#endif // js_UbiNode_h
new file mode 100644
--- /dev/null
+++ b/js/public/UbiNodeTraverse.h
@@ -0,0 +1,208 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef js_UbiNodeTraverse_h
+#define js_UbiNodeTraverse_h
+
+#include "js/UbiNode.h"
+#include "js/Utility.h"
+#include "js/Vector.h"
+
+namespace JS {
+namespace ubi {
+
+// A breadth-first traversal template for graphs of ubi::Nodes.
+//
+// No GC may occur while an instance of this template is live.
+//
+// The provided Handler type should have two members:
+//
+//   typename NodeData;
+//
+//      The value type of |BreadthFirst<Handler>::visited|, the HashMap of
+//      ubi::Nodes that have been visited so far. Since the algorithm needs a
+//      hash table like this for its own use anyway, it is simple to let
+//      Handler store its own metadata about each node in the same table.
+//
+//      For example, if you want to find a shortest path to each node from any
+//      traversal starting point, your |NodeData| type could record the first
+//      edge to reach each node, and the node from which it originates. Then,
+//      when the traversal is complete, you can walk backwards from any node
+//      to some starting point, and the path recorded will be a shortest path.
+//
+//      This type must have a default constructor. If this type owns any other
+//      resources, move constructors and assignment operators are probably a
+//      good idea, too.
+//
+//   bool operator() (BreadthFirst &traversal,
+//                    Node origin, const Edge &edge,
+//                    Handler::NodeData *referentData, bool first);
+//
+//      The visitor function, called to report that we have traversed
+//      |edge| from |origin|. This is called once for each edge we traverse.
+//      As this is a breadth-first search, any prior calls to the visitor function
+//      were for origin nodes not further from the start nodes than |origin|.
+//
+//      |traversal| is this traversal object, passed along for convenience.
+//
+//      |referentData| is a pointer to the value of the entry in
+//      |traversal.visited| for |edge.referent|; the visitor function can
+//      store whatever metadata it likes about |edge.referent| there.
+//
+//      |first| is true if this is the first time we have visited an edge
+//      leading to |edge.referent|. This could be stored in NodeData, but
+//      the algorithm knows whether it has just created the entry in
+//      |traversal.visited|, so it passes it along for convenience.
+//
+//      The visitor function may call |traversal.stop()| if it doesn't want
+//      to visit any more nodes.
+//
+//      The visitor function may consult |traversal.visited| for information
+//      about other nodes, but it should not add or remove entries.
+//
+//      The visitor function should return true on success, or false if an
+//      error occurs. A false return value terminates the traversal
+//      immediately, and causes BreadthFirst<Handler>::traverse to return
+//      false.
+template<typename Handler>
+struct BreadthFirst {
+
+    // Construct a breadth-first traversal object that reports the nodes it
+    // reaches to |handler|. The traversal object reports OOM on |cx|, and
+    // asserts that no GC happens in |cx|'s runtime during its lifetime.
+    //
+    // We do nothing with noGC, other than require it to exist, with a lifetime
+    // that encloses our own.
+    BreadthFirst(JSContext *cx, Handler &handler, const JS::AutoCheckCannotGC &noGC)
+      : cx(cx), visited(cx), handler(handler), pending(cx),
+        traversalBegun(false), stopRequested(false)
+    { }
+
+    // Initialize this traversal object. Return false on OOM.
+    bool init() { return visited.init(); }
+
+    // Add |node| as a starting point for the traversal. You may add
+    // as many starting points as you like. Return false on OOM.
+    bool addStart(Node node) { return pending.append(node); }
+
+    // Traverse the graph in breadth-first order, starting at the given
+    // start nodes, applying |handler::operator()| for each edge traversed
+    // as described above.
+    //
+    // This should be called only once per instance of this class.
+    //
+    // Return false on OOM or error return from |handler::operator()|.
+    bool traverse()
+    {
+        MOZ_ASSERT(!traversalBegun);
+        traversalBegun = true;
+
+        // While there are pending nodes, visit them, until we've found a path to the target.
+        while (!pending.empty()) {
+            Node origin = pending.front();
+            pending.popFront();
+
+            // Get a range containing all origin's outgoing edges.
+            js::ScopedJSDeletePtr<EdgeRange> range(origin.edges(cx));
+            if (!range)
+                return false;
+
+            // Traverse each edge.
+            for (; !range->empty(); range->popFront()) {
+                MOZ_ASSERT(!stopRequested);
+
+                const Edge &edge = range->front();
+                typename NodeMap::AddPtr a = visited.lookupForAdd(edge.referent);
+                bool first = !a;
+
+                if (first) {
+                    // This is the first time we've reached |edge.referent|.
+                    // Create an entry for it in |visited|, and arrange to
+                    // traverse its outgoing edges later.
+                    if (!visited.add(a, edge.referent, typename Handler::NodeData()) ||
+                        !pending.append(edge.referent)) {
+                        return false;
+                    }
+                }
+
+                MOZ_ASSERT(a);
+
+                // Report this edge to the visitor function.
+                if (!handler(*this, origin, edge, &a->value(), first))
+                    return false;
+
+                if (stopRequested)
+                    return true;
+            }
+        }
+
+        return true;
+    }
+
+    // Stop traversal, and return true from |traverse| without visiting any
+    // more nodes. Only |handler::operator()| should call this function; it
+    // may do so to stop the traversal early, without returning false and
+    // then making |traverse|'s caller disambiguate that result from a real
+    // error.
+    void stop() { stopRequested = true; }
+
+    // The context with which we were constructed.
+    JSContext *cx;
+
+    // A map associating each node N that we have reached with a
+    // Handler::NodeData, for |handler|'s use. This is public, so that
+    // |handler| can access it to see the traversal thus far.
+    typedef js::HashMap<Node, typename Handler::NodeData> NodeMap;
+    NodeMap visited;
+
+  private:
+    // Our handler object.
+    Handler &handler;
+
+    // A queue template. Appending and popping the front are constant time.
+    // Wasted space is never more than some recent actual population plus the
+    // current population.
+    template <typename T>
+    class Queue {
+        js::Vector<T, 0> head, tail;
+        size_t frontIndex;
+      public:
+        Queue(JSContext *cx) : head(cx), tail(cx), frontIndex(0) { }
+        bool empty() { return frontIndex >= head.length(); }
+        T &front() {
+            MOZ_ASSERT(!empty());
+            return head[frontIndex];
+        }
+        void popFront() {
+            MOZ_ASSERT(!empty());
+            frontIndex++;
+            if (frontIndex >= head.length()) {
+                head.clearAndFree();
+                head.swap(tail);
+                frontIndex = 0;
+            }
+        }
+        bool append(const T &elt) {
+            return frontIndex == 0 ? head.append(elt) : tail.append(elt);
+        }
+    };
+
+    // A queue of nodes that we have reached, but whose outgoing edges we
+    // have not yet traversed. Nodes reachable in fewer edges are enqueued
+    // earlier.
+    Queue<Node> pending;
+
+    // True if our traverse function has been called.
+    bool traversalBegun;
+
+    // True if we've been asked to stop the traversal.
+    bool stopRequested;
+};
+
+} // namespace ubi
+} // namespace JS
+
+#endif // js_UbiNodeTraverse.h
--- a/js/src/builtin/TestingFunctions.cpp
+++ b/js/src/builtin/TestingFunctions.cpp
@@ -1,43 +1,52 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "builtin/TestingFunctions.h"
 
+#include "mozilla/Move.h"
+#include "mozilla/Scoped.h"
+
 #include "jsapi.h"
 #include "jscntxt.h"
 #include "jsfriendapi.h"
 #include "jsgc.h"
 #include "jsobj.h"
 #ifndef JS_MORE_DETERMINISTIC
 #include "jsprf.h"
 #endif
 #include "jswrapper.h"
 
 #include "jit/AsmJS.h"
 #include "jit/AsmJSLink.h"
+#include "js/HashTable.h"
 #include "js/StructuredClone.h"
+#include "js/UbiNode.h"
+#include "js/UbiNodeTraverse.h"
+#include "js/Vector.h"
 #include "vm/ForkJoin.h"
 #include "vm/GlobalObject.h"
 #include "vm/Interpreter.h"
 #include "vm/ProxyObject.h"
 #include "vm/SavedStacks.h"
 #include "vm/TraceLogging.h"
 
 #include "jscntxtinlines.h"
 #include "jsobjinlines.h"
 
 using namespace js;
 using namespace JS;
 
 using mozilla::ArrayLength;
+using mozilla::Move;
+using mozilla::ScopedFreePtr;
 
 // If fuzzingSafe is set, remove functionality that could cause problems with
 // fuzzers. Set this via the environment variable MOZ_FUZZING_SAFE.
 static bool fuzzingSafe = false;
 
 static bool
 GetBuildConfiguration(JSContext *cx, unsigned argc, jsval *vp)
 {
@@ -1646,16 +1655,224 @@ ReportLargeAllocationFailure(JSContext *
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     void *buf = cx->runtime()->onOutOfMemoryCanGC(NULL, JSRuntime::LARGE_ALLOCATION);
     js_free(buf);
     args.rval().setUndefined();
     return true;
 }
 
+namespace heaptools {
+
+// An edge to a node from its predecessor in a path through the graph.
+class BackEdge {
+    // The node from which this edge starts.
+    JS::ubi::Node predecessor_;
+
+    // The name of this edge. We own this storage.
+    ScopedFreePtr<jschar> name_;
+
+  public:
+    BackEdge() : name_(nullptr) { }
+    // Construct an initialized back edge. Take ownership of |name|.
+    BackEdge(JS::ubi::Node predecessor, jschar *name)
+        : predecessor_(predecessor), name_(name) { }
+    BackEdge(BackEdge &&rhs) : predecessor_(rhs.predecessor_), name_(rhs.name_.forget()) { }
+    BackEdge &operator=(BackEdge &&rhs) {
+        MOZ_ASSERT(&rhs != this);
+        this->~BackEdge();
+        new(this) BackEdge(Move(rhs));
+        return *this;
+    }
+
+    jschar *forgetName() { return name_.forget(); }
+    JS::ubi::Node predecessor() const { return predecessor_; }
+
+  private:
+    // No copy constructor or copying assignment.
+    BackEdge(const BackEdge &) MOZ_DELETE;
+    BackEdge &operator=(const BackEdge &) MOZ_DELETE;
+};
+
+// A path-finding handler class for use with JS::ubi::BreadthFirst.
+struct FindPathHandler {
+    typedef BackEdge NodeData;
+    typedef JS::ubi::BreadthFirst<FindPathHandler> Traversal;
+
+    FindPathHandler(JS::ubi::Node start, JS::ubi::Node target,
+                    AutoValueVector &nodes, Vector<ScopedFreePtr<jschar> > &edges)
+      : start(start), target(target), foundPath(false),
+        nodes(nodes), edges(edges) { }
+
+    bool
+    operator()(Traversal &traversal, JS::ubi::Node origin, const JS::ubi::Edge &edge,
+               BackEdge *backEdge, bool first)
+    {
+        // We take care of each node the first time we visit it, so there's
+        // nothing to be done on subsequent visits.
+        if (!first)
+            return true;
+
+        // Record how we reached this node. This is the last edge on a
+        // shortest path to this node.
+        jschar *edgeName = js_strdup(traversal.cx, edge.name);
+        if (!edgeName)
+            return false;
+        *backEdge = mozilla::Move(BackEdge(origin, edgeName));
+
+        // Have we reached our final target node?
+        if (edge.referent == target) {
+            // Record the path that got us here, which must be a shortest path.
+            if (!recordPath(traversal))
+                return false;
+            foundPath = true;
+            traversal.stop();
+        }
+
+        return true;
+    }
+
+    // We've found a path to our target. Walk the backlinks to produce the
+    // (reversed) path, saving the path in |nodes| and |edges|. |nodes| is
+    // rooted, so it can hold the path's nodes as we leave the scope of
+    // the AutoCheckCannotGC.
+    bool recordPath(Traversal &traversal) {
+        JS::ubi::Node here = target;
+
+        do {
+            Traversal::NodeMap::Ptr p = traversal.visited.lookup(here);
+            MOZ_ASSERT(p);
+            JS::ubi::Node predecessor = p->value().predecessor();
+            if (!nodes.append(predecessor.exposeToJS()) ||
+                !edges.append(p->value().forgetName()))
+                return false;
+            here = predecessor;
+        } while (here != start);
+
+        return true;
+    }
+
+    // The node we're starting from.
+    JS::ubi::Node start;
+
+    // The node we're looking for.
+    JS::ubi::Node target;
+
+    // True if we found a path to target, false if we didn't.
+    bool foundPath;
+
+    // The nodes and edges of the path --- should we find one. The path is
+    // stored in reverse order, because that's how it's easiest for us to
+    // construct it:
+    // - edges[i] is the name of the edge from nodes[i] to nodes[i-1].
+    // - edges[0] is the name of the edge from nodes[0] to the target.
+    // - The last node, nodes[n-1], is the start node.
+    AutoValueVector &nodes;
+    Vector<ScopedFreePtr<jschar> > &edges;
+};
+
+} // namespace heaptools
+
+static bool
+FindPath(JSContext *cx, unsigned argc, jsval *vp)
+{
+    CallArgs args = CallArgsFromVp(argc, vp);
+    if (argc < 2) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_MORE_ARGS_NEEDED,
+                             "findPath", "1", "");
+        return false;
+    }
+
+    // We don't ToString non-objects given as 'start' or 'target'. We can't
+    // see edges to non-string primitive values, and it doesn't make much
+    // sense to ask for paths to or from a freshly allocated string, so
+    // if a non-string primitive appears here it's probably a mistake.
+    if (!args[0].isObject() && !args[0].isString()) {
+        js_ReportValueErrorFlags(cx, JSREPORT_ERROR, JSMSG_UNEXPECTED_TYPE,
+                                 JSDVG_SEARCH_STACK, args[0], JS::NullPtr(),
+                                 "neither an object nor a string", NULL);
+        return false;
+    }
+
+    if (!args[1].isObject() && !args[1].isString()) {
+        js_ReportValueErrorFlags(cx, JSREPORT_ERROR, JSMSG_UNEXPECTED_TYPE,
+                                 JSDVG_SEARCH_STACK, args[0], JS::NullPtr(),
+                                 "neither an object nor a string", NULL);
+        return false;
+    }
+
+    AutoValueVector nodes(cx);
+    Vector<ScopedFreePtr<jschar> > edges(cx);
+
+    {
+        // We can't tolerate the GC moving things around while we're searching
+        // the heap. Check that nothing we do causes a GC.
+        JS::AutoCheckCannotGC autoCannotGC;
+
+        JS::ubi::Node start(args[0]), target(args[1]);
+
+        heaptools::FindPathHandler handler(start, target, nodes, edges);
+        heaptools::FindPathHandler::Traversal traversal(cx, handler, autoCannotGC);
+        if (!traversal.init() || !traversal.addStart(start))
+            return false;
+
+        if (!traversal.traverse())
+            return false;
+
+        if (!handler.foundPath) {
+            // We didn't find any paths from the start to the target.
+            args.rval().setUndefined();
+            return true;
+        }
+    }
+
+    // |nodes| and |edges| contain the path from |start| to |target|, reversed.
+    // Construct a JavaScript array describing the path from the start to the
+    // target. Each element has the form:
+    //
+    //   { node: <object or string>, edge: <string describing outgoing edge from node> }
+    //
+    // or, if the node is some internal thing, that isn't a proper
+    // JavaScript value:
+    //
+    //   { node: undefined, edge: <string> }
+    size_t length = nodes.length();
+    RootedObject result(cx, NewDenseAllocatedArray(cx, length));
+    if (!result)
+        return false;
+    result->ensureDenseInitializedLength(cx, 0, length);
+
+    // Walk |nodes| and |edges| in the stored order, and construct the result
+    // array in start-to-target order.
+    for (size_t i = 0; i < length; i++) {
+        // Build an object describing the node and edge.
+        RootedObject obj(cx, NewBuiltinClassInstance<JSObject>(cx));
+        if (!obj)
+            return false;
+
+        if (!JS_DefineProperty(cx, obj, "node", nodes[i],
+                               JSPROP_ENUMERATE, nullptr, nullptr))
+            return false;
+
+        RootedString edge(cx, js_NewString<CanGC>(cx, edges[i].get(), js_strlen(edges[i])));
+        if (!edge)
+            return false;
+        edges[i].forget();
+        RootedValue edgeString(cx, StringValue(edge));
+        if (!JS_DefineProperty(cx, obj, "edge", edgeString,
+                               JSPROP_ENUMERATE, nullptr, nullptr))
+            return false;
+
+        result->setDenseElement(length - i - 1, ObjectValue(*obj));
+    }
+
+    args.rval().setObject(*result);
+    return true;
+}
+
 static const JSFunctionSpecWithHelp TestingFunctions[] = {
     JS_FN_HELP("gc", ::GC, 0, 0,
 "gc([obj] | 'compartment')",
 "  Run the garbage collector. When obj is given, GC only its compartment.\n"
 "  If 'compartment' is given, GC any compartments that were scheduled for\n"
 "  GC via schedulegc."),
 
     JS_FN_HELP("minorgc", ::MinorGC, 0, 0,
@@ -1926,16 +2143,29 @@ static const JSFunctionSpecWithHelp Test
 "  Report OOM, then clear the exception and return undefined. For crash testing."),
 
     JS_FN_HELP("reportLargeAllocationFailure", ReportLargeAllocationFailure, 0, 0,
 "reportLargeAllocationFailure()",
 "  Call the large allocation failure callback, as though a large malloc call failed,\n"
 "  then return undefined. In Gecko, this sends a memory pressure notification, which\n"
 "  can free up some memory."),
 
+    JS_FN_HELP("findPath", FindPath, 2, 0,
+"findPath(start, target)",
+"  Return an array describing one of the shortest paths of GC heap edges from\n"
+"  |start| to |target|, or |undefined| if |target| is unreachable from |start|.\n"
+"  Each element of the array is either of the form:\n"
+"    { node: <object or string>, edge: <string describing edge from node> }\n"
+"  if the node is a JavaScript object or value; or of the form:\n"
+"    { type: <string describing node>, edge: <string describing edge> }\n"
+"  if the node is some internal thing that is not a proper JavaScript value\n"
+"  (like a shape or a scope chain element). The destination of the i'th array\n"
+"  element's edge is the node of the i+1'th array element; the destination of\n"
+"  the last array element is implicitly |target|.\n"),
+
 #ifdef DEBUG
     JS_FN_HELP("dumpObject", DumpObject, 1, 0,
 "dumpObject()",
 "  Dump an internal representation of an object."),
 #endif
 
     JS_FS_HELP_END
 };
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/heap-analysis/findPath.js
@@ -0,0 +1,44 @@
+load(libdir + "match.js")
+
+// At the moment, findPath just returns the names as provided by ubi::Node,
+// which just uses JS_TraceChildren for now. However, we have various plans
+// to improve the quality of ubi::Node's metadata, to improve the precision
+// and clarity of the results here.
+
+var o = { w: { x: { y: { z: {} } } } };
+Match.Pattern([{node: {}, edge: "w"},
+               {node: {}, edge: "x"},
+               {node: {}, edge: "y"},
+               {node: {}, edge: "z"}])
+  .assert(findPath(o, o.w.x.y.z));
+print(uneval(findPath(o, o.w.x.y.z)));
+
+var a = [ , o ];
+Match.Pattern([{node: {}, edge: "objectElements[1]"}])
+  .assert(findPath(a, o));
+print(uneval(findPath(a, o)));
+
+function C() {}
+C.prototype.obj = {};
+var c = new C;
+Match.Pattern([{node: {}, edge: "type"},
+               {node: Match.Pattern.ANY, edge: "type_proto"},
+               {node: { constructor: Match.Pattern.ANY }, edge: "obj"}])
+  .assert(findPath(c, c.obj));
+print(uneval(findPath(c, c.obj)));
+
+function f(x) { return function g(y) { return x+y; }; }
+var o = {}
+var gc = f(o);
+Match.Pattern([{node: gc, edge: "fun_callscope"},
+               {node: Match.Pattern.ANY, edge: "x"}])
+  .assert(findPath(gc, o));
+print(uneval(findPath(gc, o)));
+
+Match.Pattern([{node: {}, edge: "shape"},
+               {node: Match.Pattern.ANY, edge: "base"},
+               {node: Match.Pattern.ANY, edge: "parent"},
+               {node: {}, edge: "o"}])
+  .assert(findPath(o, o));
+print(findPath(o, o).map((e) => e.edge).toString());
+
--- a/js/src/jsapi-tests/testIntTypesABI.cpp
+++ b/js/src/jsapi-tests/testIntTypesABI.cpp
@@ -29,16 +29,17 @@
 #include "js/ProfilingStack.h"
 #include "js/PropertyKey.h"
 #include "js/RequiredDefines.h"
 #include "js/RootingAPI.h"
 #include "js/SliceBudget.h"
 #include "js/StructuredClone.h"
 #include "js/TracingAPI.h"
 #include "js/TypeDecls.h"
+#include "js/UbiNode.h"
 #include "js/Utility.h"
 #include "js/Value.h"
 #include "js/Vector.h"
 #include "js/WeakMapPtr.h"
 #include "jsapi-tests/tests.h"
 
 /*
  * Verify that our public (and intended to be public, versus being that way
--- a/js/src/moz.build
+++ b/js/src/moz.build
@@ -81,16 +81,18 @@ EXPORTS.js += [
     '../public/ProfilingStack.h',
     '../public/PropertyKey.h',
     '../public/RequiredDefines.h',
     '../public/RootingAPI.h',
     '../public/SliceBudget.h',
     '../public/StructuredClone.h',
     '../public/TracingAPI.h',
     '../public/TypeDecls.h',
+    '../public/UbiNode.h',
+    '../public/UbiNodeTraverse.h',
     '../public/Utility.h',
     '../public/Value.h',
     '../public/Vector.h',
     '../public/WeakMapPtr.h',
 ]
 
 UNIFIED_SOURCES += [
     'assembler/jit/ExecutableAllocator.cpp',
@@ -186,16 +188,17 @@ UNIFIED_SOURCES += [
     'vm/SharedArrayObject.cpp',
     'vm/SPSProfiler.cpp',
     'vm/Stack.cpp',
     'vm/String.cpp',
     'vm/StringBuffer.cpp',
     'vm/StructuredClone.cpp',
     'vm/ThreadPool.cpp',
     'vm/TypedArrayObject.cpp',
+    'vm/UbiNode.cpp',
     'vm/Unicode.cpp',
     'vm/Value.cpp',
     'vm/WeakMapPtr.cpp',
     'vm/Xdr.cpp'
 ]
 
 # jsarray.cpp and jsatom.cpp cannot be built in unified mode because
 # xpcshell is broken during packaging when compiled with gcc-4.8.2
--- a/js/src/tests/js1_8_5/extensions/shell.js
+++ b/js/src/tests/js1_8_5/extensions/shell.js
@@ -78,16 +78,20 @@ var Match =
             (x === null) ||
             (typeof x === "object" && x instanceof RegExp);
     }
 
     function isObject(x) {
         return (x !== null) && (typeof x === "object");
     }
 
+    function isFunction(x) {
+        return typeof x === "function";
+    }
+
     function isArrayLike(x) {
         return isObject(x) && ("length" in x);
     }
 
     function matchAtom(act, exp) {
         if ((typeof exp) === "number" && isNaN(exp)) {
             if ((typeof act) !== "number" || !isNaN(act))
                 throw new MatchError("expected NaN, got: " + quote(act));
@@ -129,16 +133,25 @@ var Match =
             if (!(key in act))
                 throw new MatchError("expected property " + key.quote() + " not found in " + quote(act));
             match(act[key], exp[key]);
         }
 
         return true;
     }
 
+    function matchFunction(act, exp) {
+        if (!isFunction(act))
+            throw new MatchError("expected function, got " + quote(act));
+
+        if (act !== exp)
+            throw new MatchError("expected function: " + exp +
+                                 "\nbut got different function: " + act);
+    }
+
     function matchArray(act, exp) {
         if (!isObject(act) || !("length" in act))
             throw new MatchError("expected array-like object, got " + quote(act));
 
         var length = exp.length;
         if (act.length !== exp.length)
             throw new MatchError("expected array-like object of length " + length + ", got " + quote(act));
 
@@ -161,16 +174,19 @@ var Match =
             return exp.match(act);
 
         if (isAtom(exp))
             return matchAtom(act, exp);
 
         if (isArrayLike(exp))
             return matchArray(act, exp);
 
+        if (isFunction(exp))
+            return matchFunction(act, exp);
+
         return matchObject(act, exp);
     }
 
     return { Pattern: Pattern,
              MatchError: MatchError };
 
 })();
 
new file mode 100644
--- /dev/null
+++ b/js/src/vm/UbiNode.cpp
@@ -0,0 +1,226 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "js/UbiNode.h"
+
+#include "mozilla/Assertions.h"
+#include "mozilla/Attributes.h"
+#include "mozilla/Scoped.h"
+
+#include "jscntxt.h"
+
+#include "js/TracingAPI.h"
+#include "js/TypeDecls.h"
+#include "js/Utility.h"
+#include "js/Vector.h"
+#include "vm/ScopeObject.h"
+
+#include "jsobjinlines.h"
+
+using JS::Value;
+using JS::ubi::Concrete;
+using JS::ubi::Edge;
+using JS::ubi::EdgeRange;
+using JS::ubi::Node;
+using JS::ubi::TracerConcrete;
+
+// All operations on null ubi::Nodes assert.
+const jschar *Concrete<void>::typeName() const      { MOZ_ASSUME_UNREACHABLE("null ubi::Node"); }
+size_t Concrete<void>::size() const                 { MOZ_ASSUME_UNREACHABLE("null ubi::Node"); }
+EdgeRange *Concrete<void>::edges(JSContext *) const { MOZ_ASSUME_UNREACHABLE("null ubi::Node"); }
+
+
+Node::Node(JSGCTraceKind kind, void *ptr)
+{
+    switch (kind) {
+      case JSTRACE_OBJECT:      construct(static_cast<JSObject *>(ptr));              break;
+      case JSTRACE_STRING:      construct(static_cast<JSString *>(ptr));              break;
+      case JSTRACE_SCRIPT:      construct(static_cast<JSScript *>(ptr));              break;
+      case JSTRACE_LAZY_SCRIPT: construct(static_cast<js::LazyScript *>(ptr));        break;
+      case JSTRACE_JITCODE:     construct(static_cast<js::jit::JitCode *>(ptr));      break;
+      case JSTRACE_SHAPE:       construct(static_cast<js::Shape *>(ptr));             break;
+      case JSTRACE_BASE_SHAPE:  construct(static_cast<js::BaseShape *>(ptr));         break;
+      case JSTRACE_TYPE_OBJECT: construct(static_cast<js::types::TypeObject *>(ptr)); break;
+
+      default:
+        MOZ_ASSUME_UNREACHABLE("bad JSGCTraceKind passed to JS::ubi::Node::Node");
+    }
+}
+
+
+Node::Node(Value value)
+{
+    if (value.isObject())
+        construct(&value.toObject());
+    else if (value.isString())
+        construct(value.toString());
+    else
+        construct<void>(nullptr);
+}
+
+Value
+Node::exposeToJS() const
+{
+    Value v;
+
+    if (is<JSObject>()) {
+        JSObject &obj = *as<JSObject>();
+        if (obj.is<js::ScopeObject>()) {
+            v.setUndefined();
+        } else if (obj.is<JSFunction>() && IsInternalFunctionObject(&obj)) {
+            v.setUndefined();
+        } else {
+            v.setObject(obj);
+        }
+    } else if (is<JSString>()) {
+        v.setString(as<JSString>());
+    } else {
+        v.setUndefined();
+    }
+
+    return v;
+}
+
+// A dumb Edge concrete class. All but the most essential members have the
+// default behavior.
+class SimpleEdge : public Edge {
+    SimpleEdge(SimpleEdge &) MOZ_DELETE;
+    SimpleEdge &operator=(const SimpleEdge &) MOZ_DELETE;
+
+  public:
+    SimpleEdge() : Edge() { }
+
+    // Construct an initialized SimpleEdge, taking ownership of |name|.
+    SimpleEdge(jschar *name, const Node &referent) {
+        this->name = name;
+        this->referent = referent;
+    }
+    ~SimpleEdge() {
+        js_free(const_cast<jschar *>(name));
+    }
+
+    // Move construction and assignment.
+    SimpleEdge(SimpleEdge &&rhs) {
+        name = rhs.name;
+        referent = rhs.referent;
+
+        rhs.name = nullptr;
+    }
+    SimpleEdge &operator=(SimpleEdge &&rhs) {
+        MOZ_ASSERT(&rhs != this);
+        this->~SimpleEdge();
+        new(this) SimpleEdge(mozilla::Move(rhs));
+        return *this;
+    }
+};
+
+
+typedef mozilla::Vector<SimpleEdge, 8, js::TempAllocPolicy> SimpleEdgeVector;
+
+
+// A JSTracer subclass that adds a SimpleEdge to a Vector for each edge on
+// which it is invoked.
+class SimpleEdgeVectorTracer : public JSTracer {
+    // The vector to which we add SimpleEdges.
+    SimpleEdgeVector *vec;
+
+    static void staticCallback(JSTracer *trc, void **thingp, JSGCTraceKind kind) {
+        static_cast<SimpleEdgeVectorTracer *>(trc)->callback(thingp, kind);
+    }
+
+    void callback(void **thingp, JSGCTraceKind kind) {
+        if (!okay)
+            return;
+
+        // Ask the tracer to compute an edge name for us.
+        char buffer[1024];
+        const char *name = getTracingEdgeName(buffer, sizeof(buffer));
+
+        // Convert the name to jschars.
+        jschar *jsname = js_pod_malloc<jschar>(strlen(name) + 1);
+        if (!jsname) {
+            okay = false;
+            return;
+        }
+
+        size_t i;
+        for (i = 0; name[i]; i++)
+            jsname[i] = name[i];
+        jsname[i] = '\0';
+
+        // The simplest code is correct! The temporary SimpleEdge takes
+        // ownership of name; if the append succeeds, the vector element
+        // then takes ownership; if the append fails, then the temporary
+        // retains it, and its destructor will free it.
+        if (!vec->append(mozilla::Move(SimpleEdge(jsname, Node(kind, *thingp))))) {
+            okay = false;
+            return;
+        }
+    }
+
+  public:
+    // True if no errors (OOM, say) have yet occurred.
+    bool okay;
+
+    SimpleEdgeVectorTracer(JSContext *cx, SimpleEdgeVector *vec)
+        : JSTracer(JS_GetRuntime(cx), staticCallback), vec(vec), okay(true) {
+    }
+};
+
+
+// An EdgeRange concrete class that simply holds a vector of SimpleEdges,
+// populated by the init method.
+class SimpleEdgeRange : public EdgeRange {
+    SimpleEdgeVector edges;
+    size_t i;
+
+    void settle() {
+        front_ = i < edges.length() ? &edges[i] : nullptr;
+    }
+
+  public:
+    SimpleEdgeRange(JSContext *cx) : edges(cx), i(0) { }
+
+    bool init(JSContext *cx, void *thing, JSGCTraceKind kind) {
+        SimpleEdgeVectorTracer tracer(cx, &edges);
+        JS_TraceChildren(&tracer, thing, kind);
+        settle();
+        return tracer.okay;
+    }
+
+    void popFront() MOZ_OVERRIDE { i++; settle(); }
+};
+
+
+template<typename Referent>
+EdgeRange *
+TracerConcrete<Referent>::edges(JSContext *cx) const {
+    js::ScopedJSDeletePtr<SimpleEdgeRange> r(js_new<SimpleEdgeRange>(cx));
+    if (!r)
+        return nullptr;
+
+    if (!r->init(cx, ptr, ::js::gc::MapTypeToTraceKind<Referent>::kind))
+        return nullptr;
+
+    return r.forget();
+}
+
+template<> const jschar TracerConcrete<JSObject>::concreteTypeName[] =
+    MOZ_UTF16("JSObject");
+template<> const jschar TracerConcrete<JSString>::concreteTypeName[] =
+    MOZ_UTF16("JSString");
+template<> const jschar TracerConcrete<JSScript>::concreteTypeName[] =
+    MOZ_UTF16("JSScript");
+template<> const jschar TracerConcrete<js::LazyScript>::concreteTypeName[] =
+    MOZ_UTF16("js::LazyScript");
+template<> const jschar TracerConcrete<js::jit::JitCode>::concreteTypeName[] =
+    MOZ_UTF16("js::jit::JitCode");
+template<> const jschar TracerConcrete<js::Shape>::concreteTypeName[] =
+    MOZ_UTF16("js::Shape");
+template<> const jschar TracerConcrete<js::BaseShape>::concreteTypeName[] =
+    MOZ_UTF16("js::BaseShape");
+template<> const jschar TracerConcrete<js::types::TypeObject>::concreteTypeName[] =
+    MOZ_UTF16("js::types::TypeObject");