path: root/js/src/jsapi-tests/testUbiNode.cpp

/* 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