summaryrefslogtreecommitdiffstats
path: root/js/src/jsapi-tests/testFindSCCs.cpp
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-28 14:29:10 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-28 14:29:10 +0000
commit2aa4a82499d4becd2284cdb482213d541b8804dd (patch)
treeb80bf8bf13c3766139fbacc530efd0dd9d54394c /js/src/jsapi-tests/testFindSCCs.cpp
parentInitial commit. (diff)
downloadfirefox-2aa4a82499d4becd2284cdb482213d541b8804dd.tar.xz
firefox-2aa4a82499d4becd2284cdb482213d541b8804dd.zip
Adding upstream version 86.0.1.upstream/86.0.1upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r--js/src/jsapi-tests/testFindSCCs.cpp242
1 files changed, 242 insertions, 0 deletions
diff --git a/js/src/jsapi-tests/testFindSCCs.cpp b/js/src/jsapi-tests/testFindSCCs.cpp
new file mode 100644
index 0000000000..3353e3c910
--- /dev/null
+++ b/js/src/jsapi-tests/testFindSCCs.cpp
@@ -0,0 +1,242 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ */
+/* 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 <stdarg.h>
+#include <string.h>
+
+#include "gc/FindSCCs.h"
+#include "jsapi-tests/tests.h"
+
+static const unsigned MaxVertices = 10;
+
+using js::gc::ComponentFinder;
+using js::gc::GraphNodeBase;
+
+struct TestNode : public GraphNodeBase<TestNode> {
+ unsigned index;
+};
+
+using TestComponentFinder = ComponentFinder<TestNode>;
+
+static TestNode Vertex[MaxVertices];
+
+BEGIN_TEST(testFindSCCs) {
+ // no vertices
+
+ setup(0);
+ run();
+ CHECK(end());
+
+ // no edges
+
+ setup(1);
+ run();
+ CHECK(group(0, -1));
+ CHECK(end());
+
+ setup(3);
+ run();
+ CHECK(group(2, -1));
+ CHECK(group(1, -1));
+ CHECK(group(0, -1));
+ CHECK(end());
+
+ // linear
+
+ setup(3);
+ CHECK(edge(0, 1));
+ CHECK(edge(1, 2));
+ run();
+ CHECK(group(0, -1));
+ CHECK(group(1, -1));
+ CHECK(group(2, -1));
+ CHECK(end());
+
+ // tree
+
+ setup(3);
+ CHECK(edge(0, 1));
+ CHECK(edge(0, 2));
+ run();
+ CHECK(group(0, -1));
+ if (resultsList && resultsList->index == 1) {
+ CHECK(group(1, -1));
+ CHECK(group(2, -1));
+ } else {
+ CHECK(group(2, -1));
+ CHECK(group(1, -1));
+ }
+ CHECK(end());
+
+ // cycles
+
+ setup(3);
+ CHECK(edge(0, 1));
+ CHECK(edge(1, 2));
+ CHECK(edge(2, 0));
+ run();
+ CHECK(group(0, 1, 2, -1));
+ CHECK(end());
+
+ setup(4);
+ CHECK(edge(0, 1));
+ CHECK(edge(1, 2));
+ CHECK(edge(2, 1));
+ CHECK(edge(2, 3));
+ run();
+ CHECK(group(0, -1));
+ CHECK(group(1, 2, -1));
+ CHECK(group(3, -1));
+ CHECK(end());
+
+ // remaining
+
+ setup(2);
+ CHECK(edge(0, 1));
+ run();
+ CHECK(remaining(0, 1, -1));
+ CHECK(end());
+
+ setup(2);
+ CHECK(edge(0, 1));
+ run();
+ CHECK(group(0, -1));
+ CHECK(remaining(1, -1));
+ CHECK(end());
+
+ setup(2);
+ CHECK(edge(0, 1));
+ run();
+ CHECK(group(0, -1));
+ CHECK(group(1, -1));
+ CHECK(remaining(-1));
+ CHECK(end());
+
+ return true;
+}
+
+unsigned vertex_count;
+TestComponentFinder* finder;
+TestNode* resultsList;
+
+void setup(unsigned count) {
+ vertex_count = count;
+ for (unsigned i = 0; i < MaxVertices; ++i) {
+ TestNode& v = Vertex[i];
+ v.gcGraphEdges.clear();
+ v.gcNextGraphNode = nullptr;
+ v.index = i;
+ }
+}
+
+bool edge(unsigned src_index, unsigned dest_index) {
+ return Vertex[src_index].gcGraphEdges.put(&Vertex[dest_index]);
+}
+
+void run() {
+ finder =
+ new TestComponentFinder(cx->nativeStackLimit[JS::StackForSystemCode]);
+ for (unsigned i = 0; i < vertex_count; ++i) {
+ finder->addNode(&Vertex[i]);
+ }
+ resultsList = finder->getResultsList();
+}
+
+bool group(int vertex, ...) {
+ TestNode* v = resultsList;
+
+ va_list ap;
+ va_start(ap, vertex);
+ while (vertex != -1) {
+ CHECK(v != nullptr);
+ CHECK(v->index == unsigned(vertex));
+ v = v->nextNodeInGroup();
+ vertex = va_arg(ap, int);
+ }
+ va_end(ap);
+
+ CHECK(v == nullptr);
+ resultsList = resultsList->nextGroup();
+ return true;
+}
+
+bool remaining(int vertex, ...) {
+ TestNode* v = resultsList;
+
+ va_list ap;
+ va_start(ap, vertex);
+ while (vertex != -1) {
+ CHECK(v != nullptr);
+ CHECK(v->index == unsigned(vertex));
+ v = (TestNode*)v->gcNextGraphNode;
+ vertex = va_arg(ap, int);
+ }
+ va_end(ap);
+
+ CHECK(v == nullptr);
+ resultsList = nullptr;
+ return true;
+}
+
+bool end() {
+ CHECK(resultsList == nullptr);
+
+ delete finder;
+ finder = nullptr;
+ return true;
+}
+END_TEST(testFindSCCs)
+
+BEGIN_TEST(testFindSCCsStackLimit) {
+ /*
+ * Test what happens if recusion causes the stack to become full while
+ * traversing the graph.
+ *
+ * The test case is a large number of vertices, almost all of which are
+ * arranged in a linear chain. The last few are left unlinked to exercise
+ * adding vertices after the stack full condition has already been detected.
+ *
+ * Such an arrangement with no cycles would normally result in one group for
+ * each vertex, but since the stack is exhasted in processing a single group
+ * is returned containing all the vertices.
+ */
+ const unsigned max = 1000000;
+ const unsigned initial = 10;
+
+ TestNode* vertices = new TestNode[max]();
+ for (unsigned i = initial; i < (max - 10); ++i) {
+ CHECK(vertices[i].gcGraphEdges.put(&vertices[i + 1]));
+ }
+
+ TestComponentFinder finder(cx->nativeStackLimit[JS::StackForSystemCode]);
+ for (unsigned i = 0; i < max; ++i) {
+ finder.addNode(&vertices[i]);
+ }
+
+ TestNode* r = finder.getResultsList();
+ CHECK(r);
+ TestNode* v = r;
+
+ unsigned count = 0;
+ while (v) {
+ ++count;
+ v = v->nextNodeInGroup();
+ }
+ CHECK(count == max - initial);
+
+ count = 0;
+ v = r->nextGroup();
+ while (v) {
+ ++count;
+ CHECK(!v->nextNodeInGroup());
+ v = v->nextGroup();
+ }
+
+ delete[] vertices;
+ return true;
+}
+END_TEST(testFindSCCsStackLimit)