michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include <stdarg.h>
michael@0: #include <string.h>
michael@0: 
michael@0: #include "gc/FindSCCs.h"
michael@0: #include "jsapi-tests/tests.h"
michael@0: 
michael@0: static const unsigned MaxVertices = 10;
michael@0: 
michael@0: using js::gc::GraphNodeBase;
michael@0: using js::gc::ComponentFinder;
michael@0: 
michael@0: struct TestNode : public GraphNodeBase<TestNode>
michael@0: {
michael@0:     unsigned   index;
michael@0:     bool       hasEdge[MaxVertices];
michael@0: 
michael@0:     void findOutgoingEdges(ComponentFinder<TestNode> &finder);
michael@0: };
michael@0: 
michael@0: static TestNode Vertex[MaxVertices];
michael@0: 
michael@0: void
michael@0: TestNode::findOutgoingEdges(ComponentFinder<TestNode> &finder)
michael@0: {
michael@0:     for (unsigned i = 0; i < MaxVertices; ++i) {
michael@0:         if (hasEdge[i])
michael@0:             finder.addEdgeTo(&Vertex[i]);
michael@0:     }
michael@0: }
michael@0: 
michael@0: BEGIN_TEST(testFindSCCs)
michael@0: {
michael@0:     // no vertices
michael@0: 
michael@0:     setup(0);
michael@0:     run();
michael@0:     CHECK(end());
michael@0: 
michael@0:     // no edges
michael@0: 
michael@0:     setup(1);
michael@0:     run();
michael@0:     CHECK(group(0, -1));
michael@0:     CHECK(end());
michael@0: 
michael@0:     setup(3);
michael@0:     run();
michael@0:     CHECK(group(2, -1));
michael@0:     CHECK(group(1, -1));
michael@0:     CHECK(group(0, -1));
michael@0:     CHECK(end());
michael@0: 
michael@0:     // linear
michael@0: 
michael@0:     setup(3);
michael@0:     edge(0, 1);
michael@0:     edge(1, 2);
michael@0:     run();
michael@0:     CHECK(group(0, -1));
michael@0:     CHECK(group(1, -1));
michael@0:     CHECK(group(2, -1));
michael@0:     CHECK(end());
michael@0: 
michael@0:     // tree
michael@0: 
michael@0:     setup(3);
michael@0:     edge(0, 1);
michael@0:     edge(0, 2);
michael@0:     run();
michael@0:     CHECK(group(0, -1));
michael@0:     CHECK(group(2, -1));
michael@0:     CHECK(group(1, -1));
michael@0:     CHECK(end());
michael@0: 
michael@0:     // cycles
michael@0: 
michael@0:     setup(3);
michael@0:     edge(0, 1);
michael@0:     edge(1, 2);
michael@0:     edge(2, 0);
michael@0:     run();
michael@0:     CHECK(group(0, 1, 2, -1));
michael@0:     CHECK(end());
michael@0: 
michael@0:     setup(4);
michael@0:     edge(0, 1);
michael@0:     edge(1, 2);
michael@0:     edge(2, 1);
michael@0:     edge(2, 3);
michael@0:     run();
michael@0:     CHECK(group(0, -1));
michael@0:     CHECK(group(1, 2, -1));
michael@0:     CHECK(group(3, -1));
michael@0:     CHECK(end());
michael@0: 
michael@0:     // remaining
michael@0: 
michael@0:     setup(2);
michael@0:     edge(0, 1);
michael@0:     run();
michael@0:     CHECK(remaining(0, 1, -1));
michael@0:     CHECK(end());
michael@0: 
michael@0:     setup(2);
michael@0:     edge(0, 1);
michael@0:     run();
michael@0:     CHECK(group(0, -1));
michael@0:     CHECK(remaining(1, -1));
michael@0:     CHECK(end());
michael@0: 
michael@0:     setup(2);
michael@0:     edge(0, 1);
michael@0:     run();
michael@0:     CHECK(group(0, -1));
michael@0:     CHECK(group(1, -1));
michael@0:     CHECK(remaining(-1));
michael@0:     CHECK(end());
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: unsigned vertex_count;
michael@0: ComponentFinder<TestNode> *finder;
michael@0: TestNode *resultsList;
michael@0: 
michael@0: void setup(unsigned count)
michael@0: {
michael@0:     vertex_count = count;
michael@0:     for (unsigned i = 0; i < MaxVertices; ++i) {
michael@0:         TestNode &v = Vertex[i];
michael@0:         v.gcNextGraphNode = nullptr;
michael@0:         v.index = i;
michael@0:         memset(&v.hasEdge, 0, sizeof(v.hasEdge));
michael@0:     }
michael@0: }
michael@0: 
michael@0: void edge(unsigned src_index, unsigned dest_index)
michael@0: {
michael@0:     Vertex[src_index].hasEdge[dest_index] = true;
michael@0: }
michael@0: 
michael@0: void run()
michael@0: {
michael@0:     finder = new ComponentFinder<TestNode>(rt->mainThread.nativeStackLimit[js::StackForSystemCode]);
michael@0:     for (unsigned i = 0; i < vertex_count; ++i)
michael@0:         finder->addNode(&Vertex[i]);
michael@0:     resultsList = finder->getResultsList();
michael@0: }
michael@0: 
michael@0: bool group(int vertex, ...)
michael@0: {
michael@0:     TestNode *v = resultsList;
michael@0: 
michael@0:     va_list ap;
michael@0:     va_start(ap, vertex);
michael@0:     while (vertex != -1) {
michael@0:         CHECK(v != nullptr);
michael@0:         CHECK(v->index == unsigned(vertex));
michael@0:         v = v->nextNodeInGroup();
michael@0:         vertex = va_arg(ap, int);
michael@0:     }
michael@0:     va_end(ap);
michael@0: 
michael@0:     CHECK(v == nullptr);
michael@0:     resultsList = resultsList->nextGroup();
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool remaining(int vertex, ...)
michael@0: {
michael@0:     TestNode *v = resultsList;
michael@0: 
michael@0:     va_list ap;
michael@0:     va_start(ap, vertex);
michael@0:     while (vertex != -1) {
michael@0:         CHECK(v != nullptr);
michael@0:         CHECK(v->index == unsigned(vertex));
michael@0:         v = (TestNode *)v->gcNextGraphNode;
michael@0:         vertex = va_arg(ap, int);
michael@0:     }
michael@0:     va_end(ap);
michael@0: 
michael@0:     CHECK(v == nullptr);
michael@0:     resultsList = nullptr;
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool end()
michael@0: {
michael@0:     CHECK(resultsList == nullptr);
michael@0: 
michael@0:     delete finder;
michael@0:     finder = nullptr;
michael@0:     return true;
michael@0: }
michael@0: END_TEST(testFindSCCs)
michael@0: 
michael@0: struct TestNode2 : public GraphNodeBase<TestNode2>
michael@0: {
michael@0:     TestNode2 *edge;
michael@0: 
michael@0:     TestNode2() :
michael@0:         edge(nullptr)
michael@0:     {
michael@0:     }
michael@0: 
michael@0:     void
michael@0:     findOutgoingEdges(ComponentFinder<TestNode2> &finder) {
michael@0:         if (edge)
michael@0:             finder.addEdgeTo(edge);
michael@0:     }
michael@0: };
michael@0: 
michael@0: BEGIN_TEST(testFindSCCsStackLimit)
michael@0: {
michael@0:     /*
michael@0:      * Test what happens if recusion causes the stack to become full while
michael@0:      * traversing the graph.
michael@0:      *
michael@0:      * The test case is a large number of vertices, almost all of which are
michael@0:      * arranged in a linear chain.  The last few are left unlinked to exercise
michael@0:      * adding vertices after the stack full condition has already been detected.
michael@0:      *
michael@0:      * Such an arrangement with no cycles would normally result in one group for
michael@0:      * each vertex, but since the stack is exhasted in processing a single group
michael@0:      * is returned containing all the vertices.
michael@0:      */
michael@0:     const unsigned max = 1000000;
michael@0:     const unsigned initial = 10;
michael@0: 
michael@0:     TestNode2 *vertices = new TestNode2[max]();
michael@0:     for (unsigned i = initial; i < (max - 10); ++i)
michael@0:         vertices[i].edge = &vertices[i + 1];
michael@0: 
michael@0:     ComponentFinder<TestNode2> finder(rt->mainThread.nativeStackLimit[js::StackForSystemCode]);
michael@0:     for (unsigned i = 0; i < max; ++i)
michael@0:         finder.addNode(&vertices[i]);
michael@0: 
michael@0:     TestNode2 *r = finder.getResultsList();
michael@0:     CHECK(r);
michael@0:     TestNode2 *v = r;
michael@0: 
michael@0:     unsigned count = 0;
michael@0:     while (v) {
michael@0:         ++count;
michael@0:         v = v->nextNodeInGroup();
michael@0:     }
michael@0:     CHECK(count == max - initial);
michael@0: 
michael@0:     count = 0;
michael@0:     v = r->nextGroup();
michael@0:     while (v) {
michael@0:         ++count;
michael@0:         CHECK(!v->nextNodeInGroup());
michael@0:         v = v->nextGroup();
michael@0:     }
michael@0: 
michael@0:     delete [] vertices;
michael@0:     return true;
michael@0: }
michael@0: END_TEST(testFindSCCsStackLimit)