Source code
Revision control
Copy as Markdown
Other Tools
/* -*- 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
#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);
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);
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)