summaryrefslogtreecommitdiff
path: root/js/src/jsapi-tests/testUbiNode.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/jsapi-tests/testUbiNode.cpp')
-rw-r--r--js/src/jsapi-tests/testUbiNode.cpp1009
1 files changed, 1009 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..075e777d67
--- /dev/null
+++ b/js/src/jsapi-tests/testUbiNode.cpp
@@ -0,0 +1,1009 @@
+/* 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;
+
+// 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::CompartmentOptions 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);
+ RootedScript script1(cx);
+ CHECK(JS::Compile(cx, options, "", 0, &script1));
+
+ {
+ // ... and then enter global2's zone and create a string and script
+ // there, too.
+ JSAutoCompartment ac(cx, global2);
+
+ RootedString string2(cx, JS_NewStringCopyZ(cx, "A million household uses!"));
+ CHECK(string2);
+ RootedScript script2(cx);
+ CHECK(JS::Compile(cx, options, "", 0, &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());
+
+ JS::CompartmentOptions 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());
+
+ JS::CompileOptions options(cx);
+
+ // Create a script in the original compartment...
+ RootedScript script1(cx);
+ CHECK(JS::Compile(cx, options, "", 0, &script1));
+
+ {
+ // ... and then enter global2's compartment and create a script
+ // there, too.
+ JSAutoCompartment ac(cx, global2);
+
+ RootedScript script2(cx);
+ CHECK(JS::Compile(cx, options, "", 0, &script2));
+
+ CHECK(JS::ubi::Node(script1).compartment() == global1->compartment());
+ CHECK(JS::ubi::Node(script2).compartment() == global2->compartment());
+ }
+
+ return true;
+}
+END_TEST(test_ubiNodeCompartment)
+
+BEGIN_TEST(test_ubiNodeJSObjectConstructorName)
+{
+ JS::RootedValue val(cx);
+ EVAL("this.Ctor = function Ctor() {}; new Ctor", &val);
+ CHECK(val.isObject());
+
+ UniqueTwoByteChars ctorName;
+ CHECK(JS::ubi::Node(&val.toObject()).jsObjectConstructorName(cx, ctorName));
+ CHECK(ctorName);
+ CHECK(js_strcmp(ctorName.get(), u"Ctor") == 0);
+
+ return true;
+}
+END_TEST(test_ubiNodeJSObjectConstructorName)
+
+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() == 3);
+
+ ubiFrame = ubiFrame.parent();
+ CHECK(checkString("one", bufferFunctionDisplayName, getFunctionDisplayName));
+ CHECK(ubiFrame.line() == 2);
+
+ ubiFrame = ubiFrame.parent();
+ CHECK(ubiFrame.functionDisplayName().is<JSAtom*>());
+ CHECK(ubiFrame.functionDisplayName().as<JSAtom*>() == nullptr);
+ CHECK(ubiFrame.line() == 1);
+
+ 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::LazyScript* lazyScript = nullptr;
+ CHECK(JS::ubi::Node(lazyScript).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 js {
+
+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 js
+
+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);
+ CHECK(expectedEdges.init());
+
+ 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.init());
+ 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);
+ CHECK(expectedDominatedSet.init());
+ 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, func->getOrCreateScript(cx));
+ 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.init());
+ CHECK(targets.put(&b));
+
+ maybeShortestPaths = JS::ubi::ShortestPaths::Create(cx, 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(cx);
+
+ JS::ubi::NodeSet targets;
+ CHECK(targets.init());
+ CHECK(targets.put(&b));
+
+ maybeShortestPaths = JS::ubi::ShortestPaths::Create(cx, 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(cx);
+
+ JS::ubi::NodeSet targets;
+ CHECK(targets.init());
+ CHECK(targets.put(&f));
+
+ maybeShortestPaths = JS::ubi::ShortestPaths::Create(cx, 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(cx);
+
+ JS::ubi::NodeSet targets;
+ CHECK(targets.init());
+ CHECK(targets.put(&f));
+
+ maybeShortestPaths = JS::ubi::ShortestPaths::Create(cx, 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, 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.init());
+ CHECK(targets.put(&b));
+
+ maybeShortestPaths = JS::ubi::ShortestPaths::Create(cx, 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
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-16 06:28:42 +0000