summaryrefslogtreecommitdiffstats
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.cpp971
1 files changed, 971 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..bbe11d928b
--- /dev/null
+++ b/js/src/jsapi-tests/testUbiNode.cpp
@@ -0,0 +1,971 @@
+/* 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/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:
+ // 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
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-24 23:29:33 +0000