tor-browser

testFindSCCs.cpp (4839B)

---

/* -*- 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>;

MOZ_RUNINIT 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)