1 files changed, 241 insertions, 0 deletions
diff --git a/js/src/jsapi-tests/testFindSCCs.cpp b/js/src/jsapi-tests/testFindSCCs.cpp
new file mode 100644
index 0000000000..2c0db7daa1
--- /dev/null
+++ b/js/src/jsapi-tests/testFindSCCs.cpp
@@ -0,0 +1,241 @@
+/* -*- 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>;
+
+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)