1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jsapi-tests/testFindSCCs.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,268 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + */
1.7 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.8 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.9 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.10 +
1.11 +#include <stdarg.h>
1.12 +#include <string.h>
1.13 +
1.14 +#include "gc/FindSCCs.h"
1.15 +#include "jsapi-tests/tests.h"
1.16 +
1.17 +static const unsigned MaxVertices = 10;
1.18 +
1.19 +using js::gc::GraphNodeBase;
1.20 +using js::gc::ComponentFinder;
1.21 +
1.22 +struct TestNode : public GraphNodeBase<TestNode>
1.23 +{
1.24 + unsigned index;
1.25 + bool hasEdge[MaxVertices];
1.26 +
1.27 + void findOutgoingEdges(ComponentFinder<TestNode> &finder);
1.28 +};
1.29 +
1.30 +static TestNode Vertex[MaxVertices];
1.31 +
1.32 +void
1.33 +TestNode::findOutgoingEdges(ComponentFinder<TestNode> &finder)
1.34 +{
1.35 + for (unsigned i = 0; i < MaxVertices; ++i) {
1.36 + if (hasEdge[i])
1.37 + finder.addEdgeTo(&Vertex[i]);
1.38 + }
1.39 +}
1.40 +
1.41 +BEGIN_TEST(testFindSCCs)
1.42 +{
1.43 + // no vertices
1.44 +
1.45 + setup(0);
1.46 + run();
1.47 + CHECK(end());
1.48 +
1.49 + // no edges
1.50 +
1.51 + setup(1);
1.52 + run();
1.53 + CHECK(group(0, -1));
1.54 + CHECK(end());
1.55 +
1.56 + setup(3);
1.57 + run();
1.58 + CHECK(group(2, -1));
1.59 + CHECK(group(1, -1));
1.60 + CHECK(group(0, -1));
1.61 + CHECK(end());
1.62 +
1.63 + // linear
1.64 +
1.65 + setup(3);
1.66 + edge(0, 1);
1.67 + edge(1, 2);
1.68 + run();
1.69 + CHECK(group(0, -1));
1.70 + CHECK(group(1, -1));
1.71 + CHECK(group(2, -1));
1.72 + CHECK(end());
1.73 +
1.74 + // tree
1.75 +
1.76 + setup(3);
1.77 + edge(0, 1);
1.78 + edge(0, 2);
1.79 + run();
1.80 + CHECK(group(0, -1));
1.81 + CHECK(group(2, -1));
1.82 + CHECK(group(1, -1));
1.83 + CHECK(end());
1.84 +
1.85 + // cycles
1.86 +
1.87 + setup(3);
1.88 + edge(0, 1);
1.89 + edge(1, 2);
1.90 + edge(2, 0);
1.91 + run();
1.92 + CHECK(group(0, 1, 2, -1));
1.93 + CHECK(end());
1.94 +
1.95 + setup(4);
1.96 + edge(0, 1);
1.97 + edge(1, 2);
1.98 + edge(2, 1);
1.99 + edge(2, 3);
1.100 + run();
1.101 + CHECK(group(0, -1));
1.102 + CHECK(group(1, 2, -1));
1.103 + CHECK(group(3, -1));
1.104 + CHECK(end());
1.105 +
1.106 + // remaining
1.107 +
1.108 + setup(2);
1.109 + edge(0, 1);
1.110 + run();
1.111 + CHECK(remaining(0, 1, -1));
1.112 + CHECK(end());
1.113 +
1.114 + setup(2);
1.115 + edge(0, 1);
1.116 + run();
1.117 + CHECK(group(0, -1));
1.118 + CHECK(remaining(1, -1));
1.119 + CHECK(end());
1.120 +
1.121 + setup(2);
1.122 + edge(0, 1);
1.123 + run();
1.124 + CHECK(group(0, -1));
1.125 + CHECK(group(1, -1));
1.126 + CHECK(remaining(-1));
1.127 + CHECK(end());
1.128 +
1.129 + return true;
1.130 +}
1.131 +
1.132 +unsigned vertex_count;
1.133 +ComponentFinder<TestNode> *finder;
1.134 +TestNode *resultsList;
1.135 +
1.136 +void setup(unsigned count)
1.137 +{
1.138 + vertex_count = count;
1.139 + for (unsigned i = 0; i < MaxVertices; ++i) {
1.140 + TestNode &v = Vertex[i];
1.141 + v.gcNextGraphNode = nullptr;
1.142 + v.index = i;
1.143 + memset(&v.hasEdge, 0, sizeof(v.hasEdge));
1.144 + }
1.145 +}
1.146 +
1.147 +void edge(unsigned src_index, unsigned dest_index)
1.148 +{
1.149 + Vertex[src_index].hasEdge[dest_index] = true;
1.150 +}
1.151 +
1.152 +void run()
1.153 +{
1.154 + finder = new ComponentFinder<TestNode>(rt->mainThread.nativeStackLimit[js::StackForSystemCode]);
1.155 + for (unsigned i = 0; i < vertex_count; ++i)
1.156 + finder->addNode(&Vertex[i]);
1.157 + resultsList = finder->getResultsList();
1.158 +}
1.159 +
1.160 +bool group(int vertex, ...)
1.161 +{
1.162 + TestNode *v = resultsList;
1.163 +
1.164 + va_list ap;
1.165 + va_start(ap, vertex);
1.166 + while (vertex != -1) {
1.167 + CHECK(v != nullptr);
1.168 + CHECK(v->index == unsigned(vertex));
1.169 + v = v->nextNodeInGroup();
1.170 + vertex = va_arg(ap, int);
1.171 + }
1.172 + va_end(ap);
1.173 +
1.174 + CHECK(v == nullptr);
1.175 + resultsList = resultsList->nextGroup();
1.176 + return true;
1.177 +}
1.178 +
1.179 +bool remaining(int vertex, ...)
1.180 +{
1.181 + TestNode *v = resultsList;
1.182 +
1.183 + va_list ap;
1.184 + va_start(ap, vertex);
1.185 + while (vertex != -1) {
1.186 + CHECK(v != nullptr);
1.187 + CHECK(v->index == unsigned(vertex));
1.188 + v = (TestNode *)v->gcNextGraphNode;
1.189 + vertex = va_arg(ap, int);
1.190 + }
1.191 + va_end(ap);
1.192 +
1.193 + CHECK(v == nullptr);
1.194 + resultsList = nullptr;
1.195 + return true;
1.196 +}
1.197 +
1.198 +bool end()
1.199 +{
1.200 + CHECK(resultsList == nullptr);
1.201 +
1.202 + delete finder;
1.203 + finder = nullptr;
1.204 + return true;
1.205 +}
1.206 +END_TEST(testFindSCCs)
1.207 +
1.208 +struct TestNode2 : public GraphNodeBase<TestNode2>
1.209 +{
1.210 + TestNode2 *edge;
1.211 +
1.212 + TestNode2() :
1.213 + edge(nullptr)
1.214 + {
1.215 + }
1.216 +
1.217 + void
1.218 + findOutgoingEdges(ComponentFinder<TestNode2> &finder) {
1.219 + if (edge)
1.220 + finder.addEdgeTo(edge);
1.221 + }
1.222 +};
1.223 +
1.224 +BEGIN_TEST(testFindSCCsStackLimit)
1.225 +{
1.226 + /*
1.227 + * Test what happens if recusion causes the stack to become full while
1.228 + * traversing the graph.
1.229 + *
1.230 + * The test case is a large number of vertices, almost all of which are
1.231 + * arranged in a linear chain. The last few are left unlinked to exercise
1.232 + * adding vertices after the stack full condition has already been detected.
1.233 + *
1.234 + * Such an arrangement with no cycles would normally result in one group for
1.235 + * each vertex, but since the stack is exhasted in processing a single group
1.236 + * is returned containing all the vertices.
1.237 + */
1.238 + const unsigned max = 1000000;
1.239 + const unsigned initial = 10;
1.240 +
1.241 + TestNode2 *vertices = new TestNode2[max]();
1.242 + for (unsigned i = initial; i < (max - 10); ++i)
1.243 + vertices[i].edge = &vertices[i + 1];
1.244 +
1.245 + ComponentFinder<TestNode2> finder(rt->mainThread.nativeStackLimit[js::StackForSystemCode]);
1.246 + for (unsigned i = 0; i < max; ++i)
1.247 + finder.addNode(&vertices[i]);
1.248 +
1.249 + TestNode2 *r = finder.getResultsList();
1.250 + CHECK(r);
1.251 + TestNode2 *v = r;
1.252 +
1.253 + unsigned count = 0;
1.254 + while (v) {
1.255 + ++count;
1.256 + v = v->nextNodeInGroup();
1.257 + }
1.258 + CHECK(count == max - initial);
1.259 +
1.260 + count = 0;
1.261 + v = r->nextGroup();
1.262 + while (v) {
1.263 + ++count;
1.264 + CHECK(!v->nextNodeInGroup());
1.265 + v = v->nextGroup();
1.266 + }
1.267 +
1.268 + delete [] vertices;
1.269 + return true;
1.270 +}
1.271 +END_TEST(testFindSCCsStackLimit)
