Add m-esr52 at 52.6.0

1 files changed, 285 insertions, 0 deletions

diff --git a/js/src/jsapi-tests/testFindSCCs.cpp b/js/src/jsapi-tests/testFindSCCs.cpp
new file mode 100644
index 000000000..66b698a91
--- /dev/null
+++ b/js/src/jsapi-tests/testFindSCCs.cpp
@@ -0,0 +1,285 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ */
+/* 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::GraphNodeBase;
+using js::gc::ComponentFinder;
+
+struct TestComponentFinder;
+
+struct TestNode : public GraphNodeBase<TestNode>
+{
+    unsigned   index;
+    bool       hasEdge[MaxVertices];
+
+    void findOutgoingEdges(TestComponentFinder& finder);
+};
+
+struct TestComponentFinder : public ComponentFinder<TestNode, TestComponentFinder>
+{
+    explicit TestComponentFinder(uintptr_t sl)
+      : ComponentFinder<TestNode, TestComponentFinder>(sl)
+    {}
+};
+
+static TestNode Vertex[MaxVertices];
+
+void
+TestNode::findOutgoingEdges(TestComponentFinder& finder)
+{
+    for (unsigned i = 0; i < MaxVertices; ++i) {
+        if (hasEdge[i])
+            finder.addEdgeTo(&Vertex[i]);
+    }
+}
+
+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);
+    edge(0, 1);
+    edge(1, 2);
+    run();
+    CHECK(group(0, -1));
+    CHECK(group(1, -1));
+    CHECK(group(2, -1));
+    CHECK(end());
+
+    // tree
+
+    setup(3);
+    edge(0, 1);
+    edge(0, 2);
+    run();
+    CHECK(group(0, -1));
+    CHECK(group(2, -1));
+    CHECK(group(1, -1));
+    CHECK(end());
+
+    // cycles
+
+    setup(3);
+    edge(0, 1);
+    edge(1, 2);
+    edge(2, 0);
+    run();
+    CHECK(group(0, 1, 2, -1));
+    CHECK(end());
+
+    setup(4);
+    edge(0, 1);
+    edge(1, 2);
+    edge(2, 1);
+    edge(2, 3);
+    run();
+    CHECK(group(0, -1));
+    CHECK(group(1, 2, -1));
+    CHECK(group(3, -1));
+    CHECK(end());
+
+    // remaining
+
+    setup(2);
+    edge(0, 1);
+    run();
+    CHECK(remaining(0, 1, -1));
+    CHECK(end());
+
+    setup(2);
+    edge(0, 1);
+    run();
+    CHECK(group(0, -1));
+    CHECK(remaining(1, -1));
+    CHECK(end());
+
+    setup(2);
+    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.gcNextGraphNode = nullptr;
+        v.index = i;
+        memset(&v.hasEdge, 0, sizeof(v.hasEdge));
+    }
+}
+
+void edge(unsigned src_index, unsigned dest_index)
+{
+    Vertex[src_index].hasEdge[dest_index] = true;
+}
+
+void run()
+{
+    finder = new TestComponentFinder(cx->nativeStackLimit[js::StackForSystemCode]);
+    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)
+
+struct TestComponentFinder2;
+
+struct TestNode2 : public GraphNodeBase<TestNode2>
+{
+    TestNode2* edge;
+
+    TestNode2() : edge(nullptr) {}
+    void findOutgoingEdges(TestComponentFinder2& finder);
+};
+
+struct TestComponentFinder2 : public ComponentFinder<TestNode2, TestComponentFinder2>
+{
+    explicit TestComponentFinder2(uintptr_t sl)
+      : ComponentFinder<TestNode2, TestComponentFinder2>(sl)
+    {}
+};
+
+void
+TestNode2::findOutgoingEdges(TestComponentFinder2& finder)
+{
+    if (edge)
+        finder.addEdgeTo(edge);
+}
+
+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;
+
+    TestNode2* vertices = new TestNode2[max]();
+    for (unsigned i = initial; i < (max - 10); ++i)
+        vertices[i].edge = &vertices[i + 1];
+
+    TestComponentFinder2 finder(cx->nativeStackLimit[js::StackForSystemCode]);
+    for (unsigned i = 0; i < max; ++i)
+        finder.addNode(&vertices[i]);
+
+    TestNode2* r = finder.getResultsList();
+    CHECK(r);
+    TestNode2* 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)