diff options
Diffstat (limited to 'js/src/jsapi-tests/testFindSCCs.cpp')
| -rw-r--r-- | js/src/jsapi-tests/testFindSCCs.cpp | 285 |
1 files changed, 285 insertions, 0 deletions
diff --git a/js/src/jsapi-tests/testFindSCCs.cpp b/js/src/jsapi-tests/testFindSCCs.cpp new file mode 100644 index 000000000..66b698a91 --- /dev/null +++ b/js/src/jsapi-tests/testFindSCCs.cpp @@ -0,0 +1,285 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + */ +/* 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::GraphNodeBase; +using js::gc::ComponentFinder; + +struct TestComponentFinder; + +struct TestNode : public GraphNodeBase<TestNode> +{ + unsigned index; + bool hasEdge[MaxVertices]; + + void findOutgoingEdges(TestComponentFinder& finder); +}; + +struct TestComponentFinder : public ComponentFinder<TestNode, TestComponentFinder> +{ + explicit TestComponentFinder(uintptr_t sl) + : ComponentFinder<TestNode, TestComponentFinder>(sl) + {} +}; + +static TestNode Vertex[MaxVertices]; + +void +TestNode::findOutgoingEdges(TestComponentFinder& finder) +{ + for (unsigned i = 0; i < MaxVertices; ++i) { + if (hasEdge[i]) + finder.addEdgeTo(&Vertex[i]); + } +} + +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); + edge(0, 1); + edge(1, 2); + run(); + CHECK(group(0, -1)); + CHECK(group(1, -1)); + CHECK(group(2, -1)); + CHECK(end()); + + // tree + + setup(3); + edge(0, 1); + edge(0, 2); + run(); + CHECK(group(0, -1)); + CHECK(group(2, -1)); + CHECK(group(1, -1)); + CHECK(end()); + + // cycles + + setup(3); + edge(0, 1); + edge(1, 2); + edge(2, 0); + run(); + CHECK(group(0, 1, 2, -1)); + CHECK(end()); + + setup(4); + edge(0, 1); + edge(1, 2); + edge(2, 1); + edge(2, 3); + run(); + CHECK(group(0, -1)); + CHECK(group(1, 2, -1)); + CHECK(group(3, -1)); + CHECK(end()); + + // remaining + + setup(2); + edge(0, 1); + run(); + CHECK(remaining(0, 1, -1)); + CHECK(end()); + + setup(2); + edge(0, 1); + run(); + CHECK(group(0, -1)); + CHECK(remaining(1, -1)); + CHECK(end()); + + setup(2); + 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.gcNextGraphNode = nullptr; + v.index = i; + memset(&v.hasEdge, 0, sizeof(v.hasEdge)); + } +} + +void edge(unsigned src_index, unsigned dest_index) +{ + Vertex[src_index].hasEdge[dest_index] = true; +} + +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) + +struct TestComponentFinder2; + +struct TestNode2 : public GraphNodeBase<TestNode2> +{ + TestNode2* edge; + + TestNode2() : edge(nullptr) {} + void findOutgoingEdges(TestComponentFinder2& finder); +}; + +struct TestComponentFinder2 : public ComponentFinder<TestNode2, TestComponentFinder2> +{ + explicit TestComponentFinder2(uintptr_t sl) + : ComponentFinder<TestNode2, TestComponentFinder2>(sl) + {} +}; + +void +TestNode2::findOutgoingEdges(TestComponentFinder2& finder) +{ + if (edge) + finder.addEdgeTo(edge); +} + +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; + + TestNode2* vertices = new TestNode2[max](); + for (unsigned i = initial; i < (max - 10); ++i) + vertices[i].edge = &vertices[i + 1]; + + TestComponentFinder2 finder(cx->nativeStackLimit[js::StackForSystemCode]); + for (unsigned i = 0; i < max; ++i) + finder.addNode(&vertices[i]); + + TestNode2* r = finder.getResultsList(); + CHECK(r); + TestNode2* 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) |