Adding upstream version 86.0.1.upstream/86.0.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 969 insertions, 0 deletions

diff --git a/js/src/jsapi-tests/testUbiNode.cpp b/js/src/jsapi-tests/testUbiNode.cpp
new file mode 100644
index 0000000000..bbaba0161f
--- /dev/null
+++ b/js/src/jsapi-tests/testUbiNode.cpp
@@ -0,0 +1,969 @@
+/* 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 "mozilla/Utf8.h"  // mozilla::Utf8Unit
+
+#include "builtin/TestingFunctions.h"
+#include "js/CompilationAndEvaluation.h"  // JS::Compile
+#include "js/SourceText.h"                // JS::Source{Ownership,Text}
+#include "js/UbiNode.h"
+#include "js/UbiNodeDominatorTree.h"
+#include "js/UbiNodePostOrder.h"
+#include "js/UbiNodeShortestPaths.h"
+#include "jsapi-tests/tests.h"
+#include "util/Text.h"
+#include "vm/Realm.h"
+#include "vm/SavedFrame.h"
+
+#include "vm/JSObject-inl.h"
+
+using JS::RootedObject;
+using JS::RootedScript;
+using JS::RootedString;
+using namespace js;
+
+// A helper JS::ubi::Node concrete implementation that can be used to make mock
+// graphs for testing traversals with.
+struct FakeNode {
+  char name;
+  JS::ubi::EdgeVector edges;
+
+  explicit FakeNode(char name) : name(name), edges() {}
+
+  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 <>
+class Concrete<FakeNode> : public Base {
+ protected:
+  explicit Concrete(FakeNode* ptr) : Base(ptr) {}
+  FakeNode& get() const { return *static_cast<FakeNode*>(ptr); }
+
+ public:
+  static void construct(void* storage, FakeNode* ptr) {
+    new (storage) Concrete(ptr);
+  }
+
+  UniquePtr<EdgeRange> edges(JSContext* cx, bool wantNames) const override {
+    return UniquePtr<EdgeRange>(js_new<PreComputedEdgeRange>(get().edges));
+  }
+
+  Node::Size size(mozilla::MallocSizeOf) const override { return 1; }
+
+  static const char16_t concreteTypeName[];
+  const char16_t* typeName() const override { return concreteTypeName; }
+};
+
+const char16_t Concrete<FakeNode>::concreteTypeName[] = u"FakeNode";
+
+}  // namespace ubi
+}  // namespace JS
+
+// ubi::Node::zone works
+BEGIN_TEST(test_ubiNodeZone) {
+  RootedObject global1(cx, JS::CurrentGlobalOrNull(cx));
+  CHECK(global1);
+  CHECK(JS::ubi::Node(global1).zone() == cx->zone());
+
+  JS::RealmOptions globalOptions;
+  RootedObject global2(
+      cx, JS_NewGlobalObject(cx, getGlobalClass(), nullptr,
+                             JS::FireOnNewGlobalHook, globalOptions));
+  CHECK(global2);
+  CHECK(global1->zone() != global2->zone());
+  CHECK(JS::ubi::Node(global2).zone() == global2->zone());
+  CHECK(JS::ubi::Node(global2).zone() != global1->zone());
+
+  JS::CompileOptions options(cx);
+
+  // Create a string and a script in the original zone...
+  RootedString string1(
+      cx, JS_NewStringCopyZ(cx, "Simpson's Individual Stringettes!"));
+  CHECK(string1);
+
+  JS::SourceText<mozilla::Utf8Unit> emptySrcBuf;
+  CHECK(emptySrcBuf.init(cx, "", 0, JS::SourceOwnership::Borrowed));
+
+  RootedScript script1(cx, JS::Compile(cx, options, emptySrcBuf));
+  CHECK(script1);
+
+  {
+    // ... and then enter global2's zone and create a string and script
+    // there, too.
+    JSAutoRealm ar(cx, global2);
+
+    RootedString string2(cx,
+                         JS_NewStringCopyZ(cx, "A million household uses!"));
+    CHECK(string2);
+    RootedScript script2(cx, JS::Compile(cx, options, emptySrcBuf));
+    CHECK(script2);
+
+    CHECK(JS::ubi::Node(string1).zone() == global1->zone());
+    CHECK(JS::ubi::Node(script1).zone() == global1->zone());
+
+    CHECK(JS::ubi::Node(string2).zone() == global2->zone());
+    CHECK(JS::ubi::Node(script2).zone() == global2->zone());
+  }
+
+  return true;
+}
+END_TEST(test_ubiNodeZone)
+
+// ubi::Node::compartment works
+BEGIN_TEST(test_ubiNodeCompartment) {
+  RootedObject global1(cx, JS::CurrentGlobalOrNull(cx));
+  CHECK(global1);
+  CHECK(JS::ubi::Node(global1).compartment() == cx->compartment());
+  CHECK(JS::ubi::Node(global1).realm() == cx->realm());
+
+  JS::RealmOptions globalOptions;
+  RootedObject global2(
+      cx, JS_NewGlobalObject(cx, getGlobalClass(), nullptr,
+                             JS::FireOnNewGlobalHook, globalOptions));
+  CHECK(global2);
+  CHECK(global1->compartment() != global2->compartment());
+  CHECK(JS::ubi::Node(global2).compartment() == global2->compartment());
+  CHECK(JS::ubi::Node(global2).compartment() != global1->compartment());
+  CHECK(JS::ubi::Node(global2).realm() == global2->nonCCWRealm());
+  CHECK(JS::ubi::Node(global2).realm() != global1->nonCCWRealm());
+
+  JS::CompileOptions options(cx);
+
+  JS::SourceText<mozilla::Utf8Unit> emptySrcBuf;
+  CHECK(emptySrcBuf.init(cx, "", 0, JS::SourceOwnership::Borrowed));
+
+  // Create a script in the original realm...
+  RootedScript script1(cx, JS::Compile(cx, options, emptySrcBuf));
+  CHECK(script1);
+
+  {
+    // ... and then enter global2's realm and create a script
+    // there, too.
+    JSAutoRealm ar(cx, global2);
+
+    RootedScript script2(cx, JS::Compile(cx, options, emptySrcBuf));
+    CHECK(script2);
+
+    CHECK(JS::ubi::Node(script1).compartment() == global1->compartment());
+    CHECK(JS::ubi::Node(script2).compartment() == global2->compartment());
+    CHECK(JS::ubi::Node(script1).realm() == global1->nonCCWRealm());
+    CHECK(JS::ubi::Node(script2).realm() == global2->nonCCWRealm());
+
+    // Now create a wrapper for global1 in global2's compartment.
+    RootedObject wrappedGlobal1(cx, global1);
+    CHECK(cx->compartment()->wrap(cx, &wrappedGlobal1));
+
+    // Cross-compartment wrappers have a compartment() but not a realm().
+    CHECK(JS::ubi::Node(wrappedGlobal1).zone() == cx->zone());
+    CHECK(JS::ubi::Node(wrappedGlobal1).compartment() == cx->compartment());
+    CHECK(JS::ubi::Node(wrappedGlobal1).realm() == nullptr);
+  }
+
+  return true;
+}
+END_TEST(test_ubiNodeCompartment)
+
+template <typename F, typename G>
+static bool checkString(const char* expected, F fillBufferFunction,
+                        G stringGetterFunction) {
+  auto expectedLength = strlen(expected);
+  char16_t buf[1024];
+  if (fillBufferFunction(mozilla::RangedPtr<char16_t>(buf, 1024), 1024) !=
+          expectedLength ||
+      !EqualChars(buf, expected, expectedLength)) {
+    return false;
+  }
+
+  auto string = stringGetterFunction();
+  // Expecting a |JSAtom*| from a live |JS::ubi::StackFrame|.
+  if (!string.template is<JSAtom*>() ||
+      !StringEqualsAscii(string.template as<JSAtom*>(), expected)) {
+    return false;
+  }
+
+  return true;
+}
+
+BEGIN_TEST(test_ubiStackFrame) {
+  CHECK(js::DefineTestingFunctions(cx, global, false, false));
+
+  JS::RootedValue val(cx);
+  CHECK(
+      evaluate("(function one() {                      \n"   // 1
+               "  return (function two() {             \n"   // 2
+               "    return (function three() {         \n"   // 3
+               "      return saveStack();              \n"   // 4
+               "    }());                              \n"   // 5
+               "  }());                                \n"   // 6
+               "}());                                  \n",  // 7
+               "filename.js", 1, &val));
+
+  CHECK(val.isObject());
+  JS::RootedObject obj(cx, &val.toObject());
+
+  CHECK(obj->is<SavedFrame>());
+  JS::Rooted<SavedFrame*> savedFrame(cx, &obj->as<SavedFrame>());
+
+  JS::ubi::StackFrame ubiFrame(savedFrame);
+
+  // All frames should be from the "filename.js" source.
+  while (ubiFrame) {
+    CHECK(checkString(
+        "filename.js",
+        [&](mozilla::RangedPtr<char16_t> ptr, size_t length) {
+          return ubiFrame.source(ptr, length);
+        },
+        [&] { return ubiFrame.source(); }));
+    ubiFrame = ubiFrame.parent();
+  }
+
+  ubiFrame = savedFrame;
+
+  auto bufferFunctionDisplayName = [&](mozilla::RangedPtr<char16_t> ptr,
+                                       size_t length) {
+    return ubiFrame.functionDisplayName(ptr, length);
+  };
+  auto getFunctionDisplayName = [&] { return ubiFrame.functionDisplayName(); };
+
+  CHECK(
+      checkString("three", bufferFunctionDisplayName, getFunctionDisplayName));
+  CHECK(ubiFrame.line() == 4);
+
+  ubiFrame = ubiFrame.parent();
+  CHECK(checkString("two", bufferFunctionDisplayName, getFunctionDisplayName));
+  CHECK(ubiFrame.line() == 5);
+
+  ubiFrame = ubiFrame.parent();
+  CHECK(checkString("one", bufferFunctionDisplayName, getFunctionDisplayName));
+  CHECK(ubiFrame.line() == 6);
+
+  ubiFrame = ubiFrame.parent();
+  CHECK(ubiFrame.functionDisplayName().is<JSAtom*>());
+  CHECK(ubiFrame.functionDisplayName().as<JSAtom*>() == nullptr);
+  CHECK(ubiFrame.line() == 7);
+
+  ubiFrame = ubiFrame.parent();
+  CHECK(!ubiFrame);
+
+  return true;
+}
+END_TEST(test_ubiStackFrame)
+
+BEGIN_TEST(test_ubiCoarseType) {
+  // Test that our explicit coarseType() overrides work as expected.
+
+  JSObject* obj = nullptr;
+  CHECK(JS::ubi::Node(obj).coarseType() == JS::ubi::CoarseType::Object);
+
+  JSScript* script = nullptr;
+  CHECK(JS::ubi::Node(script).coarseType() == JS::ubi::CoarseType::Script);
+
+  js::BaseScript* baseScript = nullptr;
+  CHECK(JS::ubi::Node(baseScript).coarseType() == JS::ubi::CoarseType::Script);
+
+  js::jit::JitCode* jitCode = nullptr;
+  CHECK(JS::ubi::Node(jitCode).coarseType() == JS::ubi::CoarseType::Script);
+
+  JSString* str = nullptr;
+  CHECK(JS::ubi::Node(str).coarseType() == JS::ubi::CoarseType::String);
+
+  // Test that the default when coarseType() is not overridden is Other.
+
+  JS::Symbol* sym = nullptr;
+  CHECK(JS::ubi::Node(sym).coarseType() == JS::ubi::CoarseType::Other);
+
+  return true;
+}
+END_TEST(test_ubiCoarseType)
+
+struct ExpectedEdge {
+  char from;
+  char to;
+
+  ExpectedEdge(FakeNode& fromNode, FakeNode& toNode)
+      : from(fromNode.name), to(toNode.name) {}
+};
+
+namespace mozilla {
+
+template <>
+struct DefaultHasher<ExpectedEdge> {
+  using Lookup = ExpectedEdge;
+
+  static HashNumber hash(const Lookup& l) {
+    return mozilla::AddToHash(l.from, l.to);
+  }
+
+  static bool match(const ExpectedEdge& k, const Lookup& l) {
+    return k.from == l.from && k.to == l.to;
+  }
+};
+
+}  // namespace mozilla
+
+BEGIN_TEST(test_ubiPostOrder) {
+  // Construct the following graph:
+  //
+  //                          .-----.
+  //                          |     |
+  //                  .-------|  r  |---------------.
+  //                  |       |     |               |
+  //                  |       '-----'               |
+  //                  |                             |
+  //               .--V--.                       .--V--.
+  //               |     |                       |     |
+  //        .------|  a  |------.           .----|  e  |----.
+  //        |      |     |      |           |    |     |    |
+  //        |      '--^--'      |           |    '-----'    |
+  //        |         |         |           |               |
+  //     .--V--.      |      .--V--.     .--V--.         .--V--.
+  //     |     |      |      |     |     |     |         |     |
+  //     |  b  |      '------|  c  |----->  f  |--------->  g  |
+  //     |     |             |     |     |     |         |     |
+  //     '-----'             '-----'     '-----'         '-----'
+  //        |                   |
+  //        |      .-----.      |
+  //        |      |     |      |
+  //        '------>  d  <------'
+  //               |     |
+  //               '-----'
+  //
+
+  FakeNode r('r');
+  FakeNode a('a');
+  FakeNode b('b');
+  FakeNode c('c');
+  FakeNode d('d');
+  FakeNode e('e');
+  FakeNode f('f');
+  FakeNode g('g');
+
+  js::HashSet<ExpectedEdge> expectedEdges(cx);
+
+  auto declareEdge = [&](FakeNode& from, FakeNode& to) {
+    return from.addEdgeTo(to) && expectedEdges.putNew(ExpectedEdge(from, to));
+  };
+
+  CHECK(declareEdge(r, a));
+  CHECK(declareEdge(r, e));
+  CHECK(declareEdge(a, b));
+  CHECK(declareEdge(a, c));
+  CHECK(declareEdge(b, d));
+  CHECK(declareEdge(c, a));
+  CHECK(declareEdge(c, d));
+  CHECK(declareEdge(c, f));
+  CHECK(declareEdge(e, f));
+  CHECK(declareEdge(e, g));
+  CHECK(declareEdge(f, g));
+
+  js::Vector<char, 8, js::SystemAllocPolicy> visited;
+  {
+    // Do a PostOrder traversal, starting from r. Accumulate the names of
+    // the nodes we visit in `visited`. Remove edges we traverse from
+    // `expectedEdges` as we find them to ensure that we only find each edge
+    // once.
+
+    JS::AutoCheckCannotGC nogc(cx);
+    JS::ubi::PostOrder traversal(cx, nogc);
+    CHECK(traversal.addStart(&r));
+
+    auto onNode = [&](const JS::ubi::Node& node) {
+      return visited.append(node.as<FakeNode>()->name);
+    };
+
+    auto onEdge = [&](const JS::ubi::Node& origin, const JS::ubi::Edge& edge) {
+      ExpectedEdge e(*origin.as<FakeNode>(), *edge.referent.as<FakeNode>());
+      if (!expectedEdges.has(e)) {
+        fprintf(stderr, "Error: Unexpected edge from %c to %c!\n",
+                origin.as<FakeNode>()->name,
+                edge.referent.as<FakeNode>()->name);
+        return false;
+      }
+
+      expectedEdges.remove(e);
+      return true;
+    };
+
+    CHECK(traversal.traverse(onNode, onEdge));
+  }
+
+  fprintf(stderr, "visited.length() = %lu\n", (unsigned long)visited.length());
+  for (size_t i = 0; i < visited.length(); i++) {
+    fprintf(stderr, "visited[%lu] = '%c'\n", (unsigned long)i, visited[i]);
+  }
+
+  CHECK(visited.length() == 8);
+  CHECK(visited[0] == 'g');
+  CHECK(visited[1] == 'f');
+  CHECK(visited[2] == 'e');
+  CHECK(visited[3] == 'd');
+  CHECK(visited[4] == 'c');
+  CHECK(visited[5] == 'b');
+  CHECK(visited[6] == 'a');
+  CHECK(visited[7] == 'r');
+
+  // We found all the edges we expected.
+  CHECK(expectedEdges.count() == 0);
+
+  return true;
+}
+END_TEST(test_ubiPostOrder)
+
+BEGIN_TEST(test_JS_ubi_DominatorTree) {
+  // Construct the following graph:
+  //
+  //                                  .-----.
+  //                                  |     <--------------------------------.
+  //          .--------+--------------|  r  |--------------.                 |
+  //          |        |              |     |              |                 |
+  //          |        |              '-----'              |                 |
+  //          |     .--V--.                             .--V--.              |
+  //          |     |     |                             |     |              |
+  //          |     |  b  |                             |  c  |--------.     |
+  //          |     |     |                             |     |        |     |
+  //          |     '-----'                             '-----'        |     |
+  //       .--V--.     |                                   |        .--V--.  |
+  //       |     |     |                                   |        |     |  |
+  //       |  a  <-----+                                   |   .----|  g  |  |
+  //       |     |     |                              .----'   |    |     |  |
+  //       '-----'     |                              |        |    '-----'  |
+  //          |        |                              |        |       |     |
+  //       .--V--.     |    .-----.                .--V--.     |       |     |
+  //       |     |     |    |     |                |     |     |       |     |
+  //       |  d  <-----+---->  e  <----.           |  f  |     |       |     |
+  //       |     |          |     |    |           |     |     |       |     |
+  //       '-----'          '-----'    |           '-----'     |       |     |
+  //          |     .-----.    |       |              |        |    .--V--.  |
+  //          |     |     |    |       |              |      .-'    |     |  |
+  //          '----->  l  |    |       |              |      |      |  j  |  |
+  //                |     |    '--.    |              |      |      |     |  |
+  //                '-----'       |    |              |      |      '-----'  |
+  //                   |       .--V--. |              |   .--V--.      |     |
+  //                   |       |     | |              |   |     |      |     |
+  //                   '------->  h  |-'              '--->  i  <------'     |
+  //                           |     |          .--------->     |            |
+  //                           '-----'          |         '-----'            |
+  //                              |          .-----.         |               |
+  //                              |          |     |         |               |
+  //                              '---------->  k  <---------'               |
+  //                                         |     |                         |
+  //                                         '-----'                         |
+  //                                            |                            |
+  //                                            '----------------------------'
+  //
+  // This graph has the following dominator tree:
+  //
+  //     r
+  //     |-- a
+  //     |-- b
+  //     |-- c
+  //     |   |-- f
+  //     |   `-- g
+  //     |       `-- j
+  //     |-- d
+  //     |   `-- l
+  //     |-- e
+  //     |-- i
+  //     |-- k
+  //     `-- h
+  //
+  // This graph and dominator tree are taken from figures 1 and 2 of "A Fast
+  // Algorithm for Finding Dominators in a Flowgraph" by Lengauer et al:
+  // http://www.cs.princeton.edu/courses/archive/spr03/cs423/download/dominators.pdf.
+
+  FakeNode r('r');
+  FakeNode a('a');
+  FakeNode b('b');
+  FakeNode c('c');
+  FakeNode d('d');
+  FakeNode e('e');
+  FakeNode f('f');
+  FakeNode g('g');
+  FakeNode h('h');
+  FakeNode i('i');
+  FakeNode j('j');
+  FakeNode k('k');
+  FakeNode l('l');
+
+  CHECK(r.addEdgeTo(a));
+  CHECK(r.addEdgeTo(b));
+  CHECK(r.addEdgeTo(c));
+  CHECK(a.addEdgeTo(d));
+  CHECK(b.addEdgeTo(a));
+  CHECK(b.addEdgeTo(d));
+  CHECK(b.addEdgeTo(e));
+  CHECK(c.addEdgeTo(f));
+  CHECK(c.addEdgeTo(g));
+  CHECK(d.addEdgeTo(l));
+  CHECK(e.addEdgeTo(h));
+  CHECK(f.addEdgeTo(i));
+  CHECK(g.addEdgeTo(i));
+  CHECK(g.addEdgeTo(j));
+  CHECK(h.addEdgeTo(e));
+  CHECK(h.addEdgeTo(k));
+  CHECK(i.addEdgeTo(k));
+  CHECK(j.addEdgeTo(i));
+  CHECK(k.addEdgeTo(r));
+  CHECK(k.addEdgeTo(i));
+  CHECK(l.addEdgeTo(h));
+
+  mozilla::Maybe<JS::ubi::DominatorTree> maybeTree;
+  {
+    JS::AutoCheckCannotGC noGC(cx);
+    maybeTree = JS::ubi::DominatorTree::Create(cx, noGC, &r);
+  }
+
+  CHECK(maybeTree.isSome());
+  auto& tree = *maybeTree;
+
+  // We return the null JS::ubi::Node for nodes that were not reachable in the
+  // graph when computing the dominator tree.
+  FakeNode m('m');
+  CHECK(tree.getImmediateDominator(&m) == JS::ubi::Node());
+  CHECK(tree.getDominatedSet(&m).isNothing());
+
+  struct {
+    FakeNode& dominated;
+    FakeNode& dominator;
+  } domination[] = {{r, r}, {a, r}, {b, r}, {c, r}, {d, r}, {e, r}, {f, c},
+                    {g, c}, {h, r}, {i, r}, {j, g}, {k, r}, {l, d}};
+
+  for (auto& relation : domination) {
+    // Test immediate dominator.
+    fprintf(
+        stderr, "%c's immediate dominator is %c\n", relation.dominated.name,
+        tree.getImmediateDominator(&relation.dominator).as<FakeNode>()->name);
+    CHECK(tree.getImmediateDominator(&relation.dominated) ==
+          JS::ubi::Node(&relation.dominator));
+
+    // Test the dominated set. Build up the expected dominated set based on
+    // the set of nodes immediately dominated by this one in `domination`,
+    // then iterate over the actual dominated set and check against the
+    // expected set.
+
+    auto& node = relation.dominated;
+    fprintf(stderr, "Checking %c's dominated set:\n", node.name);
+
+    js::HashSet<char> expectedDominatedSet(cx);
+    for (auto& rel : domination) {
+      if (&rel.dominator == &node) {
+        fprintf(stderr, "    Expecting %c\n", rel.dominated.name);
+        CHECK(expectedDominatedSet.putNew(rel.dominated.name));
+      }
+    }
+
+    auto maybeActualDominatedSet = tree.getDominatedSet(&node);
+    CHECK(maybeActualDominatedSet.isSome());
+    auto& actualDominatedSet = *maybeActualDominatedSet;
+
+    for (const auto& dominated : actualDominatedSet) {
+      fprintf(stderr, "    Found %c\n", dominated.as<FakeNode>()->name);
+      CHECK(expectedDominatedSet.has(dominated.as<FakeNode>()->name));
+      expectedDominatedSet.remove(dominated.as<FakeNode>()->name);
+    }
+
+    // Ensure we found them all and aren't still expecting nodes we never
+    // got.
+    CHECK(expectedDominatedSet.count() == 0);
+
+    fprintf(stderr, "Done checking %c's dominated set.\n\n", node.name);
+  }
+
+  struct {
+    FakeNode& node;
+    JS::ubi::Node::Size retainedSize;
+  } sizes[] = {
+      {r, 13}, {a, 1}, {b, 1}, {c, 4}, {d, 2}, {e, 1}, {f, 1},
+      {g, 2},  {h, 1}, {i, 1}, {j, 1}, {k, 1}, {l, 1},
+  };
+
+  for (auto& expected : sizes) {
+    JS::ubi::Node::Size actual = 0;
+    CHECK(tree.getRetainedSize(&expected.node, nullptr, actual));
+    CHECK(actual == expected.retainedSize);
+  }
+
+  return true;
+}
+END_TEST(test_JS_ubi_DominatorTree)
+
+BEGIN_TEST(test_JS_ubi_Node_scriptFilename) {
+  JS::RootedValue val(cx);
+  CHECK(
+      evaluate("(function one() {                      \n"   // 1
+               "  return (function two() {             \n"   // 2
+               "    return (function three() {         \n"   // 3
+               "      return function four() {};       \n"   // 4
+               "    }());                              \n"   // 5
+               "  }());                                \n"   // 6
+               "}());                                  \n",  // 7
+               "my-cool-filename.js", 1, &val));
+
+  CHECK(val.isObject());
+  JS::RootedObject obj(cx, &val.toObject());
+
+  CHECK(obj->is<JSFunction>());
+  JS::RootedFunction func(cx, &obj->as<JSFunction>());
+
+  JS::RootedScript script(cx, JSFunction::getOrCreateScript(cx, func));
+  CHECK(script);
+  CHECK(script->filename());
+
+  JS::ubi::Node node(script);
+  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(cx);
+
+    JS::ubi::NodeSet targets;
+    CHECK(targets.put(&b));
+
+    maybeShortestPaths =
+        JS::ubi::ShortestPaths::Create(cx, noGC, 10, &a, std::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(cx);
+
+    JS::ubi::NodeSet targets;
+    CHECK(targets.put(&b));
+
+    maybeShortestPaths =
+        JS::ubi::ShortestPaths::Create(cx, noGC, 10, &a, std::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(cx);
+
+    JS::ubi::NodeSet targets;
+    CHECK(targets.put(&f));
+
+    maybeShortestPaths =
+        JS::ubi::ShortestPaths::Create(cx, noGC, 10, &a, std::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(cx);
+
+    JS::ubi::NodeSet targets;
+    CHECK(targets.put(&f));
+
+    maybeShortestPaths =
+        JS::ubi::ShortestPaths::Create(cx, noGC, 1, &a, std::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, u"x"));
+  CHECK(a.addEdgeTo(b, u"y"));
+  CHECK(a.addEdgeTo(b, u"z"));
+
+  mozilla::Maybe<JS::ubi::ShortestPaths> maybeShortestPaths;
+  {
+    JS::AutoCheckCannotGC noGC(cx);
+
+    JS::ubi::NodeSet targets;
+    CHECK(targets.put(&b));
+
+    maybeShortestPaths =
+        JS::ubi::ShortestPaths::Create(cx, noGC, 10, &a, std::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