Bug 961323 - Add a method for finding shortest retaining paths of `JS::ubi::Node` heap graphs; r=jimb
☠☠ backed out by ea6f3bbe55c1 ☠ ☠
authorNick Fitzgerald <fitzgen@gmail.com>
Thu, 11 Feb 2016 10:38:00 +0100
changeset 284090 09836ef7b0f6d04967cc49cbb62ae92ecd8acfb0
parent 284089 2914d1a8153ce484747d462e92f540d0f6dc16aa
child 284091 20d90d9a12cecdad38a72b43e4c28d9b6f0ac5e8
push id29995
push usercbook@mozilla.com
push dateFri, 12 Feb 2016 14:16:12 +0000
treeherdermozilla-central@218d16a9ddcc [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjimb
bugs961323
milestone47.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 961323 - Add a method for finding shortest retaining paths of `JS::ubi::Node` heap graphs; r=jimb This commit adds `JS::ubi::ShortestPaths` which can find the N shortest retaining paths starting from some root for any number of target nodes.
js/public/UbiNode.h
js/public/UbiNodeDominatorTree.h
js/public/UbiNodeShortestPaths.h
js/src/builtin/TestingFunctions.cpp
js/src/jit-test/tests/heap-analysis/shortestPaths.js
js/src/jsapi-tests/testUbiNode.cpp
js/src/moz.build
js/src/vm/UbiNodeShortestPaths.cpp
--- a/js/public/UbiNode.h
+++ b/js/public/UbiNode.h
@@ -803,16 +803,18 @@ class Node {
         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; }
     };
 };
 
+using NodeSet = js::HashSet<Node, js::DefaultHasher<Node>, js::SystemAllocPolicy>;
+using NodeSetPtr = mozilla::UniquePtr<NodeSet, JS::DeletePolicy<NodeSet>>;
 
 /*** Edge and EdgeRange ***************************************************************************/
 
 using EdgeName = UniqueTwoByteChars;
 
 // An outgoing edge to a referent node.
 class Edge {
   public:
--- a/js/public/UbiNodeDominatorTree.h
+++ b/js/public/UbiNodeDominatorTree.h
@@ -66,18 +66,16 @@ namespace ubi {
  *
  * [0]: http://www.cs.rice.edu/~keith/EMBED/dom.pdf
  */
 class JS_PUBLIC_API(DominatorTree)
 {
   private:
     // Types.
 
-    using NodeSet = js::HashSet<Node, js::DefaultHasher<Node>, js::SystemAllocPolicy>;
-    using NodeSetPtr = mozilla::UniquePtr<NodeSet, JS::DeletePolicy<NodeSet>>;
     using PredecessorSets = js::HashMap<Node, NodeSetPtr, js::DefaultHasher<Node>,
                                         js::SystemAllocPolicy>;
     using NodeToIndexMap = js::HashMap<Node, uint32_t, js::DefaultHasher<Node>,
                                        js::SystemAllocPolicy>;
     class DominatedSets;
 
   public:
     class DominatedSetRange;
new file mode 100644
--- /dev/null
+++ b/js/public/UbiNodeShortestPaths.h
@@ -0,0 +1,331 @@
+/* -*- 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_UbiNodeShortestPaths_h
+#define js_UbiNodeShortestPaths_h
+
+#include "mozilla/Maybe.h"
+#include "mozilla/Move.h"
+
+#include "jsalloc.h"
+
+#include "js/UbiNodeBreadthFirst.h"
+#include "js/Vector.h"
+
+namespace JS {
+namespace ubi {
+
+/**
+ * A back edge along a path in the heap graph.
+ */
+struct JS_PUBLIC_API(BackEdge)
+{
+  private:
+    Node predecessor_;
+    EdgeName name_;
+
+  public:
+    using Ptr = mozilla::UniquePtr<BackEdge, JS::DeletePolicy<BackEdge>>;
+
+    BackEdge() : predecessor_(), name_(nullptr) { }
+
+    bool init(const Node& predecessor, Edge& edge) {
+        MOZ_ASSERT(!predecessor_);
+        MOZ_ASSERT(!name_);
+
+        predecessor_ = predecessor;
+        name_ = mozilla::Move(edge.name);
+        return true;
+    }
+
+    BackEdge(const BackEdge&) = delete;
+    BackEdge& operator=(const BackEdge&) = delete;
+
+    BackEdge(BackEdge&& rhs)
+      : predecessor_(rhs.predecessor_)
+      , name_(mozilla::Move(rhs.name_))
+    {
+        MOZ_ASSERT(&rhs != this);
+    }
+
+    BackEdge& operator=(BackEdge&& rhs) {
+        this->~BackEdge();
+        new(this) BackEdge(Move(rhs));
+        return *this;
+    }
+
+    Ptr clone() const;
+
+    const EdgeName& name() const { return name_; }
+    EdgeName& name() { return name_; }
+
+    const JS::ubi::Node& predecessor() const { return predecessor_; }
+};
+
+/**
+ * A path is a series of back edges from which we discovered a target node.
+ */
+using Path = mozilla::Vector<BackEdge*>;
+
+/**
+ * The `JS::ubi::ShortestPaths` type represents a collection of up to N shortest
+ * retaining paths for each of a target set of nodes, starting from the same
+ * root node.
+ */
+struct JS_PUBLIC_API(ShortestPaths)
+{
+  private:
+    // Types, type aliases, and data members.
+
+    using BackEdgeVector = mozilla::Vector<BackEdge::Ptr>;
+    using NodeToBackEdgeVectorMap = js::HashMap<Node, BackEdgeVector, js::DefaultHasher<Node>,
+                                                js::SystemAllocPolicy>;
+
+    struct Handler;
+    using Traversal = BreadthFirst<Handler>;
+
+    /**
+     * A `JS::ubi::BreadthFirst` traversal handler that records back edges for
+     * how we reached each node, allowing us to reconstruct the shortest
+     * retaining paths after the traversal.
+     */
+    struct Handler
+    {
+        using NodeData = BackEdge;
+
+        ShortestPaths& shortestPaths;
+        size_t totalMaxPathsToRecord;
+        size_t totalPathsRecorded;
+
+        explicit Handler(ShortestPaths& shortestPaths)
+          : shortestPaths(shortestPaths)
+          , totalMaxPathsToRecord(shortestPaths.targets_.count() * shortestPaths.maxNumPaths_)
+          , totalPathsRecorded(0)
+        {
+        }
+
+        bool
+        operator()(Traversal& traversal, JS::ubi::Node origin, JS::ubi::Edge& edge,
+                   BackEdge* back, bool first)
+        {
+            MOZ_ASSERT(back);
+            MOZ_ASSERT(traversal.visited.has(origin));
+            MOZ_ASSERT(totalPathsRecorded < totalMaxPathsToRecord);
+
+            if (first && !back->init(origin, edge))
+                return false;
+
+            if (!shortestPaths.targets_.has(edge.referent))
+                return true;
+
+            // If `first` is true, then we moved the edge's name into `back` in
+            // the above call to `init`. So clone that back edge to get the
+            // correct edge name. If `first` is not true, then our edge name is
+            // still in `edge`. This accounts for the asymmetry between
+            // `back->clone()` in the first branch, and the `init` call in the
+            // second branch.
+
+            auto ptr = shortestPaths.paths_.lookupForAdd(edge.referent);
+            if (first) {
+                MOZ_ASSERT(!ptr);
+                BackEdgeVector paths;
+                if (!paths.reserve(shortestPaths.maxNumPaths_))
+                    return false;
+                auto cloned = back->clone();
+                if (!cloned)
+                    return false;
+                paths.infallibleAppend(mozilla::Move(cloned));
+                if (!shortestPaths.paths_.add(ptr, edge.referent, mozilla::Move(paths)))
+                    return false;
+                totalPathsRecorded++;
+            } else if (ptr->value().length() < shortestPaths.maxNumPaths_) {
+                MOZ_ASSERT(ptr);
+                BackEdge::Ptr thisBackEdge(js_new<BackEdge>());
+                if (!thisBackEdge || !thisBackEdge->init(origin, edge))
+                    return false;
+                ptr->value().infallibleAppend(mozilla::Move(thisBackEdge));
+                totalPathsRecorded++;
+            }
+
+            MOZ_ASSERT(totalPathsRecorded <= totalMaxPathsToRecord);
+            if (totalPathsRecorded == totalMaxPathsToRecord)
+                traversal.stop();
+
+            return true;
+        }
+
+    };
+
+    // The maximum number of paths to record for each node.
+    uint32_t maxNumPaths_;
+
+    // The root node we are starting the search from.
+    Node root_;
+
+    // The set of nodes we are searching for paths to.
+    NodeSet targets_;
+
+    // The resulting paths.
+    NodeToBackEdgeVectorMap paths_;
+
+    // Need to keep alive the traversal's back edges so we can walk them later
+    // when the traversal is over when recreating the shortest paths.
+    Traversal::NodeMap backEdges_;
+
+  private:
+    // Private methods.
+
+    ShortestPaths(uint32_t maxNumPaths, const Node& root, NodeSet&& targets)
+      : maxNumPaths_(maxNumPaths)
+      , root_(root)
+      , targets_(mozilla::Move(targets))
+      , paths_()
+      , backEdges_()
+    {
+        MOZ_ASSERT(maxNumPaths_ > 0);
+        MOZ_ASSERT(root_);
+        MOZ_ASSERT(targets_.initialized());
+    }
+
+    bool initialized() const {
+        return targets_.initialized() &&
+               paths_.initialized() &&
+               backEdges_.initialized();
+    }
+
+  public:
+    // Public methods.
+
+    ShortestPaths(ShortestPaths&& rhs)
+      : maxNumPaths_(rhs.maxNumPaths_)
+      , root_(rhs.root_)
+      , targets_(mozilla::Move(rhs.targets_))
+      , paths_(mozilla::Move(rhs.paths_))
+      , backEdges_(mozilla::Move(rhs.backEdges_))
+    {
+        MOZ_ASSERT(this != &rhs, "self-move is not allowed");
+    }
+
+    ShortestPaths& operator=(ShortestPaths&& rhs) {
+        this->~ShortestPaths();
+        new (this) ShortestPaths(mozilla::Move(rhs));
+        return *this;
+    }
+
+    ShortestPaths(const ShortestPaths&) = delete;
+    ShortestPaths& operator=(const ShortestPaths&) = delete;
+
+    /**
+     * Construct a new `JS::ubi::ShortestPaths`, finding up to `maxNumPaths`
+     * shortest retaining paths for each target node in `targets` starting from
+     * `root`.
+     *
+     * The resulting `ShortestPaths` instance must not outlive the
+     * `JS::ubi::Node` graph it was constructed from.
+     *
+     *   - For `JS::ubi::Node` graphs backed by the live heap graph, this means
+     *     that the `ShortestPaths`'s lifetime _must_ be contained within the
+     *     scope of the provided `AutoCheckCannotGC` reference because a GC will
+     *     invalidate the nodes.
+     *
+     *   - For `JS::ubi::Node` graphs backed by some other offline structure
+     *     provided by the embedder, the resulting `ShortestPaths`'s lifetime is
+     *     bounded by that offline structure's lifetime.
+     *
+     * Returns `mozilla::Nothing()` on OOM failure. It is the caller's
+     * responsibility to handle and report the OOM.
+     */
+    static mozilla::Maybe<ShortestPaths>
+    Create(JSRuntime* rt, AutoCheckCannotGC& noGC, uint32_t maxNumPaths, const Node& root, NodeSet&& targets) {
+        MOZ_ASSERT(targets.count() > 0);
+        MOZ_ASSERT(maxNumPaths > 0);
+
+        size_t count = targets.count();
+        ShortestPaths paths(maxNumPaths, root, mozilla::Move(targets));
+        if (!paths.paths_.init(count))
+            return mozilla::Nothing();
+
+        Handler handler(paths);
+        Traversal traversal(rt, handler, noGC);
+        traversal.wantNames = true;
+        if (!traversal.init() || !traversal.addStartVisited(root) || !traversal.traverse())
+            return mozilla::Nothing();
+
+        // Take ownership of the back edges we created while traversing the
+        // graph so that we can follow them from `paths_` and don't
+        // use-after-free.
+        paths.backEdges_ = mozilla::Move(traversal.visited);
+
+        MOZ_ASSERT(paths.initialized());
+        return mozilla::Some(mozilla::Move(paths));
+    }
+
+    /**
+     * Get a range that iterates over each target node we searched for retaining
+     * paths for. The returned range must not outlive the `ShortestPaths`
+     * instance.
+     */
+    NodeSet::Range eachTarget() const {
+        MOZ_ASSERT(initialized());
+        return targets_.all();
+    }
+
+    /**
+     * Invoke the provided functor/lambda/callable once for each retaining path
+     * discovered for `target`. The `func` is passed a single `JS::ubi::Path&`
+     * argument, which contains each edge along the path ordered starting from
+     * the root and ending at the target, and must not outlive the scope of the
+     * call.
+     *
+     * Note that it is possible that we did not find any paths from the root to
+     * the given target, in which case `func` will not be invoked.
+     */
+    template <class Func>
+    bool forEachPath(const Node& target, Func func) {
+        MOZ_ASSERT(initialized());
+        MOZ_ASSERT(targets_.has(target));
+
+        auto ptr = paths_.lookup(target);
+
+        // We didn't find any paths to this target, so nothing to do here.
+        if (!ptr)
+            return true;
+
+        MOZ_ASSERT(ptr->value().length() <= maxNumPaths_);
+
+        Path path;
+        for (const auto& backEdge : ptr->value()) {
+            path.clear();
+
+            if (!path.append(backEdge.get()))
+                return false;
+
+            Node here = backEdge->predecessor();
+            MOZ_ASSERT(here);
+
+            while (here != root_) {
+                auto p = backEdges_.lookup(here);
+                MOZ_ASSERT(p);
+                if (!path.append(&p->value()))
+                    return false;
+                here = p->value().predecessor();
+                MOZ_ASSERT(here);
+            }
+
+            path.reverse();
+
+            if (!func(path))
+                return false;
+        }
+
+        return true;
+    }
+};
+
+} // namespace ubi
+} // namespace JS
+
+#endif // js_UbiNodeShortestPaths_h
--- a/js/src/builtin/TestingFunctions.cpp
+++ b/js/src/builtin/TestingFunctions.cpp
@@ -22,16 +22,17 @@
 #include "asmjs/Wasm.h"
 #include "jit/InlinableNatives.h"
 #include "jit/JitFrameIterator.h"
 #include "js/Debug.h"
 #include "js/HashTable.h"
 #include "js/StructuredClone.h"
 #include "js/UbiNode.h"
 #include "js/UbiNodeBreadthFirst.h"
+#include "js/UbiNodeShortestPaths.h"
 #include "js/UniquePtr.h"
 #include "js/Vector.h"
 #include "vm/GlobalObject.h"
 #include "vm/Interpreter.h"
 #include "vm/ProxyObject.h"
 #include "vm/SavedStacks.h"
 #include "vm/Stack.h"
 #include "vm/TraceLogging.h"
@@ -2537,16 +2538,187 @@ FindPath(JSContext* cx, unsigned argc, V
         result->setDenseElement(length - i - 1, ObjectValue(*obj));
     }
 
     args.rval().setObject(*result);
     return true;
 }
 
 static bool
+ShortestPaths(JSContext* cx, unsigned argc, Value* vp)
+{
+    CallArgs args = CallArgsFromVp(argc, vp);
+    if (!args.requireAtLeast(cx, "shortestPaths", 3))
+        return false;
+
+    // We don't ToString non-objects given as 'start' or 'target', because this
+    // test is all about object identity, and ToString doesn't preserve that.
+    // Non-GCThing endpoints don't make much sense.
+    if (!args[0].isObject() && !args[0].isString() && !args[0].isSymbol()) {
+        ReportValueErrorFlags(cx, JSREPORT_ERROR, JSMSG_UNEXPECTED_TYPE,
+                              JSDVG_SEARCH_STACK, args[0], nullptr,
+                              "not an object, string, or symbol", nullptr);
+        return false;
+    }
+
+    if (!args[1].isObject() || !args[1].toObject().is<ArrayObject>()) {
+        ReportValueErrorFlags(cx, JSREPORT_ERROR, JSMSG_UNEXPECTED_TYPE,
+                              JSDVG_SEARCH_STACK, args[1], nullptr,
+                              "not an array object", nullptr);
+        return false;
+    }
+
+    RootedArrayObject objs(cx, &args[1].toObject().as<ArrayObject>());
+    size_t length = objs->getDenseInitializedLength();
+    if (length == 0) {
+        ReportValueErrorFlags(cx, JSREPORT_ERROR, JSMSG_UNEXPECTED_TYPE,
+                              JSDVG_SEARCH_STACK, args[1], nullptr,
+                              "not a dense array object with one or more elements", nullptr);
+        return false;
+    }
+
+    for (size_t i = 0; i < length; i++) {
+        RootedValue el(cx, objs->getDenseElement(i));
+        if (!el.isObject() && !el.isString() && !el.isSymbol()) {
+            ReportValueErrorFlags(cx, JSREPORT_ERROR, JSMSG_UNEXPECTED_TYPE,
+                                  JSDVG_SEARCH_STACK, el, nullptr,
+                                  "not an object, string, or symbol", nullptr);
+            return false;
+        }
+    }
+
+    int32_t maxNumPaths;
+    if (!JS::ToInt32(cx, args[2], &maxNumPaths))
+        return false;
+    if (maxNumPaths <= 0) {
+        ReportValueErrorFlags(cx, JSREPORT_ERROR, JSMSG_UNEXPECTED_TYPE,
+                              JSDVG_SEARCH_STACK, args[2], nullptr,
+                              "not greater than 0", nullptr);
+        return false;
+    }
+
+    // We accumulate the results into a GC-stable form, due to the fact that the
+    // JS::ubi::ShortestPaths lifetime (when operating on the live heap graph)
+    // is bounded within an AutoCheckCannotGC.
+    Rooted<GCVector<GCVector<GCVector<Value>>>> values(cx, GCVector<GCVector<GCVector<Value>>>(cx));
+    Vector<Vector<Vector<JS::ubi::EdgeName>>> names(cx);
+
+    {
+        JS::AutoCheckCannotGC noGC(cx->runtime());
+
+        JS::ubi::NodeSet targets;
+        if (!targets.init()) {
+            ReportOutOfMemory(cx);
+            return false;
+        }
+
+        for (size_t i = 0; i < length; i++) {
+            RootedValue val(cx, objs->getDenseElement(i));
+            JS::ubi::Node node(val);
+            if (!targets.put(node)) {
+                ReportOutOfMemory(cx);
+                return false;
+            }
+        }
+
+        JS::ubi::Node root(args[0]);
+        auto maybeShortestPaths = JS::ubi::ShortestPaths::Create(cx->runtime(), noGC, maxNumPaths,
+                                                                 root, mozilla::Move(targets));
+        if (maybeShortestPaths.isNothing()) {
+            ReportOutOfMemory(cx);
+            return false;
+        }
+        auto& shortestPaths = *maybeShortestPaths;
+
+        for (size_t i = 0; i < length; i++) {
+            if (!values.append(GCVector<GCVector<Value>>(cx)) ||
+                !names.append(Vector<Vector<JS::ubi::EdgeName>>(cx)))
+            {
+                return false;
+            }
+
+            RootedValue val(cx, objs->getDenseElement(i));
+            JS::ubi::Node target(val);
+
+            bool ok = shortestPaths.forEachPath(target, [&](JS::ubi::Path& path) {
+                Rooted<GCVector<Value>> pathVals(cx, GCVector<Value>(cx));
+                Vector<JS::ubi::EdgeName> pathNames(cx);
+
+                for (auto& part : path) {
+                    if (!pathVals.append(part->predecessor().exposeToJS()) ||
+                        !pathNames.append(mozilla::Move(part->name())))
+                    {
+                        return false;
+                    }
+                }
+
+                return values.back().append(mozilla::Move(pathVals.get())) &&
+                       names.back().append(mozilla::Move(pathNames));
+            });
+
+            if (!ok)
+                return false;
+        }
+    }
+
+    MOZ_ASSERT(values.length() == names.length());
+    MOZ_ASSERT(values.length() == length);
+
+    RootedArrayObject results(cx, NewDenseFullyAllocatedArray(cx, length));
+    if (!results)
+        return false;
+    results->ensureDenseInitializedLength(cx, 0, length);
+
+    for (size_t i = 0; i < length; i++) {
+        size_t numPaths = values[i].length();
+        MOZ_ASSERT(names[i].length() == numPaths);
+
+        RootedArrayObject pathsArray(cx, NewDenseFullyAllocatedArray(cx, numPaths));
+        if (!pathsArray)
+            return false;
+        pathsArray->ensureDenseInitializedLength(cx, 0, numPaths);
+
+        for (size_t j = 0; j < numPaths; j++) {
+            size_t pathLength = values[i][j].length();
+            MOZ_ASSERT(names[i][j].length() == pathLength);
+
+            RootedArrayObject path(cx, NewDenseFullyAllocatedArray(cx, pathLength));
+            if (!path)
+                return false;
+            path->ensureDenseInitializedLength(cx, 0, pathLength);
+
+            for (size_t k = 0; k < pathLength; k++) {
+                RootedPlainObject part(cx, NewBuiltinClassInstance<PlainObject>(cx));
+                if (!part)
+                    return false;
+
+                RootedValue predecessor(cx, values[i][j][k]);
+                if (!JS_DefineProperty(cx, part, "predecessor", predecessor, JSPROP_ENUMERATE))
+                    return false;
+
+                if (names[i][j][k]) {
+                    RootedString edge(cx, NewStringCopyZ<CanGC>(cx, names[i][j][k].get()));
+                    if (!edge || !JS_DefineProperty(cx, part, "edge", edge, JSPROP_ENUMERATE))
+                        return false;
+                }
+
+                path->setDenseElement(k, ObjectValue(*part));
+            }
+
+            pathsArray->setDenseElement(j, ObjectValue(*path));
+        }
+
+        results->setDenseElement(i, ObjectValue(*pathsArray));
+    }
+
+    args.rval().setObject(*results);
+    return true;
+}
+
+static bool
 EvalReturningScope(JSContext* cx, unsigned argc, Value* vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     if (!args.requireAtLeast(cx, "evalReturningScope", 1))
         return false;
 
     RootedString str(cx, ToString(cx, args[0]));
     if (!str)
@@ -3545,16 +3717,23 @@ gc::ZealModeHelpText),
 "    { 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"),
 
+    JS_FN_HELP("shortestPaths", ShortestPaths, 3, 0,
+"shortestPaths(start, targets, maxNumPaths)",
+"  Return an array of arrays of shortest retaining paths. There is an array of\n"
+"  shortest retaining paths for each object in |targets|. The maximum number of\n"
+"  paths in each of those arrays is bounded by |maxNumPaths|. Each element in a\n"
+"  path is of the form |{ predecessor, edge }|."),
+
 #ifdef DEBUG
     JS_FN_HELP("dumpObject", DumpObject, 1, 0,
 "dumpObject()",
 "  Dump an internal representation of an object."),
 #endif
 
     JS_FN_HELP("sharedMemoryEnabled", SharedMemoryEnabled, 0, 0,
 "sharedMemoryEnabled()",
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/heap-analysis/shortestPaths.js
@@ -0,0 +1,44 @@
+// The shortestPaths function exists solely to let the fuzzers go to town and
+// exercise the code paths it calls into, hence there is nothing to assert here.
+//
+// The actual behavior of JS::ubi::ShortestPaths is tested in
+// js/src/jsapi-tests/testUbiNode.cpp, where we can actually control the
+// structure of the heap graph to test specific shapes.
+
+function f(x) {
+  return x + x;
+}
+
+var g = f.bind(null, 5);
+
+var o = {
+  p: g
+};
+
+function dumpPaths(results) {
+  results = results.map(paths => {
+    return paths.map(path => {
+      return path.map(part => {
+        return {
+          predecessor: Object.prototype.toString.call(part.predecessor),
+          edge: part.edge
+        };
+      });
+    });
+  });
+  print(JSON.stringify(results, null, 2));
+}
+
+print("shortestPaths(this, [Object, f, o.p], 5)");
+var paths = shortestPaths(this, [Object, f, o.p], 5);
+dumpPaths(paths);
+
+print();
+print("shortestPaths(o, [f], 1)")
+paths = shortestPaths(o, [f], 1);
+dumpPaths(paths);
+
+print();
+print("shortestPaths(this, [f], 5)")
+paths = shortestPaths(this, [f], 5);
+dumpPaths(paths);
--- a/js/src/jsapi-tests/testUbiNode.cpp
+++ b/js/src/jsapi-tests/testUbiNode.cpp
@@ -1,16 +1,17 @@
 /* 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 "js/UbiNode.h"
 #include "js/UbiNodeDominatorTree.h"
 #include "js/UbiNodePostOrder.h"
+#include "js/UbiNodeShortestPaths.h"
 #include "jsapi-tests/tests.h"
 #include "vm/SavedFrame.h"
 
 using JS::RootedObject;
 using JS::RootedScript;
 using JS::RootedString;
 using namespace js;
 
@@ -18,18 +19,25 @@ using namespace js;
 // graphs for testing traversals with.
 struct FakeNode
 {
     char                name;
     JS::ubi::EdgeVector edges;
 
     explicit FakeNode(char name) : name(name), edges() { }
 
-    bool addEdgeTo(FakeNode& referent) {
+    bool addEdgeTo(FakeNode& referent, const char16_t* edgeName = nullptr) {
         JS::ubi::Node node(&referent);
+
+        if (edgeName) {
+            auto ownedName = js::DuplicateString(edgeName);
+            MOZ_RELEASE_ASSERT(ownedName);
+            return edges.emplaceBack(ownedName.release(), node);
+        }
+
         return edges.emplaceBack(nullptr, node);
     }
 };
 
 namespace JS {
 namespace ubi {
 
 template<>
@@ -645,8 +653,356 @@ BEGIN_TEST(test_JS_ubi_Node_scriptFilena
     const char* filename = node.scriptFilename();
     CHECK(filename);
     CHECK(strcmp(filename, script->filename()) == 0);
     CHECK(strcmp(filename, "my-cool-filename.js") == 0);
 
     return true;
 }
 END_TEST(test_JS_ubi_Node_scriptFilename)
+
+#define LAMBDA_CHECK(cond)                                                         \
+    do {                                                                           \
+        if (!(cond)) {                                                             \
+            fprintf(stderr,"%s:%d:CHECK failed: " #cond "\n", __FILE__, __LINE__); \
+            return false;                                                          \
+        }                                                                          \
+    } while (false)
+
+static void
+dumpPath(JS::ubi::Path& path)
+{
+    for (size_t i = 0; i < path.length(); i++) {
+        fprintf(stderr, "path[%llu]->predecessor() = '%c'\n",
+                (long long unsigned) i,
+                path[i]->predecessor().as<FakeNode>()->name);
+    }
+}
+
+BEGIN_TEST(test_JS_ubi_ShortestPaths_no_path)
+{
+    // Create the following graph:
+    //
+    //     .---.      .---.    .---.
+    //     | a | <--> | c |    | b |
+    //     '---'      '---'    '---'
+    FakeNode a('a');
+    FakeNode b('b');
+    FakeNode c('c');
+    CHECK(a.addEdgeTo(c));
+    CHECK(c.addEdgeTo(a));
+
+    mozilla::Maybe<JS::ubi::ShortestPaths> maybeShortestPaths;
+    {
+        JS::AutoCheckCannotGC noGC(rt);
+
+        JS::ubi::NodeSet targets;
+        CHECK(targets.init());
+        CHECK(targets.put(&b));
+
+        maybeShortestPaths = JS::ubi::ShortestPaths::Create(rt, noGC, 10, &a,
+                                                            mozilla::Move(targets));
+    }
+
+    CHECK(maybeShortestPaths);
+    auto& paths = *maybeShortestPaths;
+
+    size_t numPathsFound = 0;
+    bool ok = paths.forEachPath(&b, [&](JS::ubi::Path& path) {
+        numPathsFound++;
+        dumpPath(path);
+        return true;
+    });
+    CHECK(ok);
+    CHECK(numPathsFound == 0);
+
+    return true;
+}
+END_TEST(test_JS_ubi_ShortestPaths_no_path)
+
+BEGIN_TEST(test_JS_ubi_ShortestPaths_one_path)
+{
+    // Create the following graph:
+    //
+    //     .---.      .---.     .---.
+    //     | a | <--> | c | --> | b |
+    //     '---'      '---'     '---'
+    FakeNode a('a');
+    FakeNode b('b');
+    FakeNode c('c');
+    CHECK(a.addEdgeTo(c));
+    CHECK(c.addEdgeTo(a));
+    CHECK(c.addEdgeTo(b));
+
+    mozilla::Maybe<JS::ubi::ShortestPaths> maybeShortestPaths;
+    {
+        JS::AutoCheckCannotGC noGC(rt);
+
+        JS::ubi::NodeSet targets;
+        CHECK(targets.init());
+        CHECK(targets.put(&b));
+
+        maybeShortestPaths = JS::ubi::ShortestPaths::Create(rt, noGC, 10, &a,
+                                                            mozilla::Move(targets));
+    }
+
+    CHECK(maybeShortestPaths);
+    auto& paths = *maybeShortestPaths;
+
+    size_t numPathsFound = 0;
+    bool ok = paths.forEachPath(&b, [&](JS::ubi::Path& path) {
+        numPathsFound++;
+
+        dumpPath(path);
+        LAMBDA_CHECK(path.length() == 2);
+        LAMBDA_CHECK(path[0]->predecessor() == JS::ubi::Node(&a));
+        LAMBDA_CHECK(path[1]->predecessor() == JS::ubi::Node(&c));
+
+        return true;
+    });
+
+    CHECK(ok);
+    CHECK(numPathsFound == 1);
+
+    return true;
+}
+END_TEST(test_JS_ubi_ShortestPaths_one_path)
+
+BEGIN_TEST(test_JS_ubi_ShortestPaths_multiple_paths)
+{
+    // Create the following graph:
+    //
+    //                .---.
+    //          .-----| a |-----.
+    //          |     '---'     |
+    //          V       |       V
+    //        .---.     |     .---.
+    //        | b |     |     | d |
+    //        '---'     |     '---'
+    //          |       |       |
+    //          V       |       V
+    //        .---.     |     .---.
+    //        | c |     |     | e |
+    //        '---'     V     '---'
+    //          |     .---.     |
+    //          '---->| f |<----'
+    //                '---'
+    FakeNode a('a');
+    FakeNode b('b');
+    FakeNode c('c');
+    FakeNode d('d');
+    FakeNode e('e');
+    FakeNode f('f');
+    CHECK(a.addEdgeTo(b));
+    CHECK(a.addEdgeTo(f));
+    CHECK(a.addEdgeTo(d));
+    CHECK(b.addEdgeTo(c));
+    CHECK(c.addEdgeTo(f));
+    CHECK(d.addEdgeTo(e));
+    CHECK(e.addEdgeTo(f));
+
+    mozilla::Maybe<JS::ubi::ShortestPaths> maybeShortestPaths;
+    {
+        JS::AutoCheckCannotGC noGC(rt);
+
+        JS::ubi::NodeSet targets;
+        CHECK(targets.init());
+        CHECK(targets.put(&f));
+
+        maybeShortestPaths = JS::ubi::ShortestPaths::Create(rt, noGC, 10, &a,
+                                                            mozilla::Move(targets));
+    }
+
+    CHECK(maybeShortestPaths);
+    auto& paths = *maybeShortestPaths;
+
+    size_t numPathsFound = 0;
+    bool ok = paths.forEachPath(&f, [&](JS::ubi::Path& path) {
+        numPathsFound++;
+        dumpPath(path);
+
+        switch (path.back()->predecessor().as<FakeNode>()->name) {
+            case 'a': {
+                LAMBDA_CHECK(path.length() == 1);
+                break;
+            }
+
+            case 'c': {
+                LAMBDA_CHECK(path.length() == 3);
+                LAMBDA_CHECK(path[0]->predecessor() == JS::ubi::Node(&a));
+                LAMBDA_CHECK(path[1]->predecessor() == JS::ubi::Node(&b));
+                LAMBDA_CHECK(path[2]->predecessor() == JS::ubi::Node(&c));
+                break;
+            }
+
+            case 'e': {
+                LAMBDA_CHECK(path.length() == 3);
+                LAMBDA_CHECK(path[0]->predecessor() == JS::ubi::Node(&a));
+                LAMBDA_CHECK(path[1]->predecessor() == JS::ubi::Node(&d));
+                LAMBDA_CHECK(path[2]->predecessor() == JS::ubi::Node(&e));
+                break;
+            }
+
+            default: {
+                // Unexpected path!
+                LAMBDA_CHECK(false);
+            }
+        }
+
+        return true;
+    });
+
+    CHECK(ok);
+    fprintf(stderr, "numPathsFound = %llu\n", (long long unsigned) numPathsFound);
+    CHECK(numPathsFound == 3);
+
+    return true;
+}
+END_TEST(test_JS_ubi_ShortestPaths_multiple_paths)
+
+BEGIN_TEST(test_JS_ubi_ShortestPaths_more_paths_than_max)
+{
+    // Create the following graph:
+    //
+    //                .---.
+    //          .-----| a |-----.
+    //          |     '---'     |
+    //          V       |       V
+    //        .---.     |     .---.
+    //        | b |     |     | d |
+    //        '---'     |     '---'
+    //          |       |       |
+    //          V       |       V
+    //        .---.     |     .---.
+    //        | c |     |     | e |
+    //        '---'     V     '---'
+    //          |     .---.     |
+    //          '---->| f |<----'
+    //                '---'
+    FakeNode a('a');
+    FakeNode b('b');
+    FakeNode c('c');
+    FakeNode d('d');
+    FakeNode e('e');
+    FakeNode f('f');
+    CHECK(a.addEdgeTo(b));
+    CHECK(a.addEdgeTo(f));
+    CHECK(a.addEdgeTo(d));
+    CHECK(b.addEdgeTo(c));
+    CHECK(c.addEdgeTo(f));
+    CHECK(d.addEdgeTo(e));
+    CHECK(e.addEdgeTo(f));
+
+    mozilla::Maybe<JS::ubi::ShortestPaths> maybeShortestPaths;
+    {
+        JS::AutoCheckCannotGC noGC(rt);
+
+        JS::ubi::NodeSet targets;
+        CHECK(targets.init());
+        CHECK(targets.put(&f));
+
+        maybeShortestPaths = JS::ubi::ShortestPaths::Create(rt, noGC, 1, &a,
+                                                            mozilla::Move(targets));
+    }
+
+    CHECK(maybeShortestPaths);
+    auto& paths = *maybeShortestPaths;
+
+    size_t numPathsFound = 0;
+    bool ok = paths.forEachPath(&f, [&](JS::ubi::Path& path) {
+        numPathsFound++;
+        dumpPath(path);
+        return true;
+    });
+
+    CHECK(ok);
+    fprintf(stderr, "numPathsFound = %llu\n", (long long unsigned) numPathsFound);
+    CHECK(numPathsFound == 1);
+
+    return true;
+}
+END_TEST(test_JS_ubi_ShortestPaths_more_paths_than_max)
+
+BEGIN_TEST(test_JS_ubi_ShortestPaths_multiple_edges_to_target)
+{
+    // Create the following graph:
+    //
+    //                .---.
+    //          .-----| a |-----.
+    //          |     '---'     |
+    //          |       |       |
+    //          |x      |y      |z
+    //          |       |       |
+    //          |       V       |
+    //          |     .---.     |
+    //          '---->| b |<----'
+    //                '---'
+    FakeNode a('a');
+    FakeNode b('b');
+    CHECK(a.addEdgeTo(b, MOZ_UTF16("x")));
+    CHECK(a.addEdgeTo(b, MOZ_UTF16("y")));
+    CHECK(a.addEdgeTo(b, MOZ_UTF16("z")));
+
+    mozilla::Maybe<JS::ubi::ShortestPaths> maybeShortestPaths;
+    {
+        JS::AutoCheckCannotGC noGC(rt);
+
+        JS::ubi::NodeSet targets;
+        CHECK(targets.init());
+        CHECK(targets.put(&b));
+
+        maybeShortestPaths = JS::ubi::ShortestPaths::Create(rt, noGC, 10, &a,
+                                                            mozilla::Move(targets));
+    }
+
+    CHECK(maybeShortestPaths);
+    auto& paths = *maybeShortestPaths;
+
+    size_t numPathsFound = 0;
+    bool foundX = false;
+    bool foundY = false;
+    bool foundZ = false;
+
+    bool ok = paths.forEachPath(&b, [&](JS::ubi::Path& path) {
+        numPathsFound++;
+        dumpPath(path);
+
+        LAMBDA_CHECK(path.length() == 1);
+        LAMBDA_CHECK(path.back()->name());
+        LAMBDA_CHECK(js_strlen(path.back()->name().get()) == 1);
+
+        auto c = uint8_t(path.back()->name().get()[0]);
+        fprintf(stderr, "Edge name = '%c'\n", c);
+
+        switch (c) {
+            case 'x': {
+                foundX = true;
+                break;
+            }
+            case 'y': {
+                foundY = true;
+                break;
+            }
+            case 'z': {
+                foundZ = true;
+                break;
+            }
+            default: {
+                // Unexpected edge!
+                LAMBDA_CHECK(false);
+            }
+        }
+
+        return true;
+    });
+
+    CHECK(ok);
+    fprintf(stderr, "numPathsFound = %llu\n", (long long unsigned) numPathsFound);
+    CHECK(numPathsFound == 3);
+    CHECK(foundX);
+    CHECK(foundY);
+    CHECK(foundZ);
+
+    return true;
+}
+END_TEST(test_JS_ubi_ShortestPaths_multiple_edges_to_target)
+
+#undef LAMBDA_CHECK
--- a/js/src/moz.build
+++ b/js/src/moz.build
@@ -131,16 +131,17 @@ EXPORTS.js += [
     '../public/TracingAPI.h',
     '../public/TrackedOptimizationInfo.h',
     '../public/TypeDecls.h',
     '../public/UbiNode.h',
     '../public/UbiNodeBreadthFirst.h',
     '../public/UbiNodeCensus.h',
     '../public/UbiNodeDominatorTree.h',
     '../public/UbiNodePostOrder.h',
+    '../public/UbiNodeShortestPaths.h',
     '../public/UniquePtr.h',
     '../public/Utility.h',
     '../public/Value.h',
     '../public/Vector.h',
     '../public/WeakMapPtr.h',
 ]
 
 UNIFIED_SOURCES += [
@@ -334,16 +335,17 @@ UNIFIED_SOURCES += [
     'vm/StructuredClone.cpp',
     'vm/Symbol.cpp',
     'vm/TaggedProto.cpp',
     'vm/Time.cpp',
     'vm/TypedArrayObject.cpp',
     'vm/TypeInference.cpp',
     'vm/UbiNode.cpp',
     'vm/UbiNodeCensus.cpp',
+    'vm/UbiNodeShortestPaths.cpp',
     'vm/UnboxedObject.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
new file mode 100644
--- /dev/null
+++ b/js/src/vm/UbiNodeShortestPaths.cpp
@@ -0,0 +1,31 @@
+/* -*- 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/UbiNodeShortestPaths.h"
+
+#include "jsstr.h"
+
+namespace JS {
+namespace ubi {
+
+JS_PUBLIC_API(BackEdge::Ptr)
+BackEdge::clone() const
+{
+    BackEdge::Ptr clone(js_new<BackEdge>());
+    if (!clone)
+        return nullptr;
+
+    clone->predecessor_ = predecessor();
+    if (name()) {
+        clone->name_ = js::DuplicateString(name().get());
+        if (!clone->name_)
+            return nullptr;
+    }
+    return mozilla::Move(clone);
+}
+
+} // namespace ubi
+} // namespace JS