Source code
Revision control
Copy as Markdown
Other Tools
/* 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
#include "mozilla/Utf8.h" // mozilla::Utf8Unit
#include "builtin/TestingFunctions.h"
#include "js/CompilationAndEvaluation.h" // JS::Compile
#include "js/GlobalObject.h" // JS_NewGlobalObject
#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/Compartment.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:
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