1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sts=4 et sw=4 tw=99:
3 */
4 /* This Source Code Form is subject to the terms of the Mozilla Public
5 * License, v. 2.0. If a copy of the MPL was not distributed with this
6 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7
8 #include <stdarg.h>
9 #include <string.h>
10
11 #include "gc/FindSCCs.h"
12 #include "jsapi-tests/tests.h"
13
14 static const unsigned MaxVertices = 10;
15
16 using js::gc::ComponentFinder;
17 using js::gc::GraphNodeBase;
18
19 struct TestComponentFinder;
20
21 struct TestNode : public GraphNodeBase<TestNode> {
22 unsigned index;
23 bool hasEdge[MaxVertices];
24
25 void findOutgoingEdges(TestComponentFinder& finder);
26 };
27
28 struct TestComponentFinder
29 : public ComponentFinder<TestNode, TestComponentFinder> {
TestComponentFinderTestComponentFinder30 explicit TestComponentFinder(uintptr_t sl)
31 : ComponentFinder<TestNode, TestComponentFinder>(sl) {}
32 };
33
34 static TestNode Vertex[MaxVertices];
35
findOutgoingEdges(TestComponentFinder & finder)36 void TestNode::findOutgoingEdges(TestComponentFinder& finder) {
37 for (unsigned i = 0; i < MaxVertices; ++i) {
38 if (hasEdge[i]) finder.addEdgeTo(&Vertex[i]);
39 }
40 }
41
BEGIN_TEST(testFindSCCs)42 BEGIN_TEST(testFindSCCs) {
43 // no vertices
44
45 setup(0);
46 run();
47 CHECK(end());
48
49 // no edges
50
51 setup(1);
52 run();
53 CHECK(group(0, -1));
54 CHECK(end());
55
56 setup(3);
57 run();
58 CHECK(group(2, -1));
59 CHECK(group(1, -1));
60 CHECK(group(0, -1));
61 CHECK(end());
62
63 // linear
64
65 setup(3);
66 edge(0, 1);
67 edge(1, 2);
68 run();
69 CHECK(group(0, -1));
70 CHECK(group(1, -1));
71 CHECK(group(2, -1));
72 CHECK(end());
73
74 // tree
75
76 setup(3);
77 edge(0, 1);
78 edge(0, 2);
79 run();
80 CHECK(group(0, -1));
81 CHECK(group(2, -1));
82 CHECK(group(1, -1));
83 CHECK(end());
84
85 // cycles
86
87 setup(3);
88 edge(0, 1);
89 edge(1, 2);
90 edge(2, 0);
91 run();
92 CHECK(group(0, 1, 2, -1));
93 CHECK(end());
94
95 setup(4);
96 edge(0, 1);
97 edge(1, 2);
98 edge(2, 1);
99 edge(2, 3);
100 run();
101 CHECK(group(0, -1));
102 CHECK(group(1, 2, -1));
103 CHECK(group(3, -1));
104 CHECK(end());
105
106 // remaining
107
108 setup(2);
109 edge(0, 1);
110 run();
111 CHECK(remaining(0, 1, -1));
112 CHECK(end());
113
114 setup(2);
115 edge(0, 1);
116 run();
117 CHECK(group(0, -1));
118 CHECK(remaining(1, -1));
119 CHECK(end());
120
121 setup(2);
122 edge(0, 1);
123 run();
124 CHECK(group(0, -1));
125 CHECK(group(1, -1));
126 CHECK(remaining(-1));
127 CHECK(end());
128
129 return true;
130 }
131
132 unsigned vertex_count;
133 TestComponentFinder* finder;
134 TestNode* resultsList;
135
setup(unsigned count)136 void setup(unsigned count) {
137 vertex_count = count;
138 for (unsigned i = 0; i < MaxVertices; ++i) {
139 TestNode& v = Vertex[i];
140 v.gcNextGraphNode = nullptr;
141 v.index = i;
142 memset(&v.hasEdge, 0, sizeof(v.hasEdge));
143 }
144 }
145
edge(unsigned src_index,unsigned dest_index)146 void edge(unsigned src_index, unsigned dest_index) {
147 Vertex[src_index].hasEdge[dest_index] = true;
148 }
149
run()150 void run() {
151 finder =
152 new TestComponentFinder(cx->nativeStackLimit[JS::StackForSystemCode]);
153 for (unsigned i = 0; i < vertex_count; ++i) finder->addNode(&Vertex[i]);
154 resultsList = finder->getResultsList();
155 }
156
group(int vertex,...)157 bool group(int vertex, ...) {
158 TestNode* v = resultsList;
159
160 va_list ap;
161 va_start(ap, vertex);
162 while (vertex != -1) {
163 CHECK(v != nullptr);
164 CHECK(v->index == unsigned(vertex));
165 v = v->nextNodeInGroup();
166 vertex = va_arg(ap, int);
167 }
168 va_end(ap);
169
170 CHECK(v == nullptr);
171 resultsList = resultsList->nextGroup();
172 return true;
173 }
174
remaining(int vertex,...)175 bool remaining(int vertex, ...) {
176 TestNode* v = resultsList;
177
178 va_list ap;
179 va_start(ap, vertex);
180 while (vertex != -1) {
181 CHECK(v != nullptr);
182 CHECK(v->index == unsigned(vertex));
183 v = (TestNode*)v->gcNextGraphNode;
184 vertex = va_arg(ap, int);
185 }
186 va_end(ap);
187
188 CHECK(v == nullptr);
189 resultsList = nullptr;
190 return true;
191 }
192
end()193 bool end() {
194 CHECK(resultsList == nullptr);
195
196 delete finder;
197 finder = nullptr;
198 return true;
199 }
200 END_TEST(testFindSCCs)
201
202 struct TestComponentFinder2;
203
204 struct TestNode2 : public GraphNodeBase<TestNode2> {
205 TestNode2* edge;
206
TestNode2TestNode2207 TestNode2() : edge(nullptr) {}
208 void findOutgoingEdges(TestComponentFinder2& finder);
209 };
210
211 struct TestComponentFinder2
212 : public ComponentFinder<TestNode2, TestComponentFinder2> {
TestComponentFinder2TestComponentFinder2213 explicit TestComponentFinder2(uintptr_t sl)
214 : ComponentFinder<TestNode2, TestComponentFinder2>(sl) {}
215 };
216
findOutgoingEdges(TestComponentFinder2 & finder)217 void TestNode2::findOutgoingEdges(TestComponentFinder2& finder) {
218 if (edge) finder.addEdgeTo(edge);
219 }
220
BEGIN_TEST(testFindSCCsStackLimit)221 BEGIN_TEST(testFindSCCsStackLimit) {
222 /*
223 * Test what happens if recusion causes the stack to become full while
224 * traversing the graph.
225 *
226 * The test case is a large number of vertices, almost all of which are
227 * arranged in a linear chain. The last few are left unlinked to exercise
228 * adding vertices after the stack full condition has already been detected.
229 *
230 * Such an arrangement with no cycles would normally result in one group for
231 * each vertex, but since the stack is exhasted in processing a single group
232 * is returned containing all the vertices.
233 */
234 const unsigned max = 1000000;
235 const unsigned initial = 10;
236
237 TestNode2* vertices = new TestNode2[max]();
238 for (unsigned i = initial; i < (max - 10); ++i)
239 vertices[i].edge = &vertices[i + 1];
240
241 TestComponentFinder2 finder(cx->nativeStackLimit[JS::StackForSystemCode]);
242 for (unsigned i = 0; i < max; ++i) finder.addNode(&vertices[i]);
243
244 TestNode2* r = finder.getResultsList();
245 CHECK(r);
246 TestNode2* v = r;
247
248 unsigned count = 0;
249 while (v) {
250 ++count;
251 v = v->nextNodeInGroup();
252 }
253 CHECK(count == max - initial);
254
255 count = 0;
256 v = r->nextGroup();
257 while (v) {
258 ++count;
259 CHECK(!v->nextNodeInGroup());
260 v = v->nextGroup();
261 }
262
263 delete[] vertices;
264 return true;
265 }
266 END_TEST(testFindSCCsStackLimit)
267