Add m-esr52 at 52.6.0

1 files changed, 214 insertions, 0 deletions

diff --git a/js/src/gc/FindSCCs.h b/js/src/gc/FindSCCs.h
new file mode 100644
index 0000000000..037557e3ee
--- /dev/null
+++ b/js/src/gc/FindSCCs.h
@@ -0,0 +1,214 @@
+/* -*- 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/. */
+
+#ifndef gc_FindSCCs_h
+#define gc_FindSCCs_h
+
+#include "mozilla/Move.h"
+
+#include "jsfriendapi.h"
+#include "jsutil.h"
+
+namespace js {
+namespace gc {
+
+template<class Node>
+struct GraphNodeBase
+{
+    Node*          gcNextGraphNode;
+    Node*          gcNextGraphComponent;
+    unsigned       gcDiscoveryTime;
+    unsigned       gcLowLink;
+
+    GraphNodeBase()
+      : gcNextGraphNode(nullptr),
+        gcNextGraphComponent(nullptr),
+        gcDiscoveryTime(0),
+        gcLowLink(0) {}
+
+    ~GraphNodeBase() {}
+
+    Node* nextNodeInGroup() const {
+        if (gcNextGraphNode && gcNextGraphNode->gcNextGraphComponent == gcNextGraphComponent)
+            return gcNextGraphNode;
+        return nullptr;
+    }
+
+    Node* nextGroup() const {
+        return gcNextGraphComponent;
+    }
+};
+
+/*
+ * Find the strongly connected components of a graph using Tarjan's algorithm,
+ * and return them in topological order.
+ *
+ * Nodes derive from GraphNodeBase and implement findGraphEdges, which calls
+ * finder.addEdgeTo to describe the outgoing edges from that node:
+ *
+ * struct MyComponentFinder;
+ *
+ * struct MyGraphNode : public GraphNodeBase
+ * {
+ *     void findOutgoingEdges(MyComponentFinder& finder)
+ *     {
+ *         for edge in my_outgoing_edges:
+ *             if is_relevant(edge):
+ *                 finder.addEdgeTo(edge.destination)
+ *     }
+ * }
+ *
+ * struct MyComponentFinder : public ComponentFinder<MyGraphNode, MyComponentFinder>
+ * {
+ *     ...
+ * };
+ *
+ * MyComponentFinder finder;
+ * finder.addNode(v);
+ */
+
+template <typename Node, typename Derived>
+class ComponentFinder
+{
+  public:
+    explicit ComponentFinder(uintptr_t sl)
+      : clock(1),
+        stack(nullptr),
+        firstComponent(nullptr),
+        cur(nullptr),
+        stackLimit(sl),
+        stackFull(false)
+    {}
+
+    ~ComponentFinder() {
+        MOZ_ASSERT(!stack);
+        MOZ_ASSERT(!firstComponent);
+    }
+
+    /* Forces all nodes to be added to a single component. */
+    void useOneComponent() { stackFull = true; }
+
+    void addNode(Node* v) {
+        if (v->gcDiscoveryTime == Undefined) {
+            MOZ_ASSERT(v->gcLowLink == Undefined);
+            processNode(v);
+        }
+    }
+
+    Node* getResultsList() {
+        if (stackFull) {
+            /*
+             * All nodes after the stack overflow are in |stack|. Put them all in
+             * one big component of their own.
+             */
+            Node* firstGoodComponent = firstComponent;
+            for (Node* v = stack; v; v = stack) {
+                stack = v->gcNextGraphNode;
+                v->gcNextGraphComponent = firstGoodComponent;
+                v->gcNextGraphNode = firstComponent;
+                firstComponent = v;
+            }
+            stackFull = false;
+        }
+
+        MOZ_ASSERT(!stack);
+
+        Node* result = firstComponent;
+        firstComponent = nullptr;
+
+        for (Node* v = result; v; v = v->gcNextGraphNode) {
+            v->gcDiscoveryTime = Undefined;
+            v->gcLowLink = Undefined;
+        }
+
+        return result;
+    }
+
+    static void mergeGroups(Node* first) {
+        for (Node* v = first; v; v = v->gcNextGraphNode)
+            v->gcNextGraphComponent = nullptr;
+    }
+
+  public:
+    /* Call from implementation of GraphNodeBase::findOutgoingEdges(). */
+    void addEdgeTo(Node* w) {
+        if (w->gcDiscoveryTime == Undefined) {
+            processNode(w);
+            cur->gcLowLink = Min(cur->gcLowLink, w->gcLowLink);
+        } else if (w->gcDiscoveryTime != Finished) {
+            cur->gcLowLink = Min(cur->gcLowLink, w->gcDiscoveryTime);
+        }
+    }
+
+  private:
+    /* Constant used to indicate an unprocessed vertex. */
+    static const unsigned Undefined = 0;
+
+    /* Constant used to indicate an processed vertex that is no longer on the stack. */
+    static const unsigned Finished = (unsigned)-1;
+
+    void processNode(Node* v) {
+        v->gcDiscoveryTime = clock;
+        v->gcLowLink = clock;
+        ++clock;
+
+        v->gcNextGraphNode = stack;
+        stack = v;
+
+        int stackDummy;
+        if (stackFull || !JS_CHECK_STACK_SIZE(stackLimit, &stackDummy)) {
+            stackFull = true;
+            return;
+        }
+
+        Node* old = cur;
+        cur = v;
+        cur->findOutgoingEdges(*static_cast<Derived*>(this));
+        cur = old;
+
+        if (stackFull)
+            return;
+
+        if (v->gcLowLink == v->gcDiscoveryTime) {
+            Node* nextComponent = firstComponent;
+            Node* w;
+            do {
+                MOZ_ASSERT(stack);
+                w = stack;
+                stack = w->gcNextGraphNode;
+
+                /*
+                 * Record that the element is no longer on the stack by setting the
+                 * discovery time to a special value that's not Undefined.
+                 */
+                w->gcDiscoveryTime = Finished;
+
+                /* Figure out which group we're in. */
+                w->gcNextGraphComponent = nextComponent;
+
+                /*
+                 * Prepend the component to the beginning of the output list to
+                 * reverse the list and achieve the desired order.
+                 */
+                w->gcNextGraphNode = firstComponent;
+                firstComponent = w;
+            } while (w != v);
+        }
+    }
+
+  private:
+    unsigned       clock;
+    Node*          stack;
+    Node*          firstComponent;
+    Node*          cur;
+    uintptr_t      stackLimit;
+    bool           stackFull;
+};
+
+} /* namespace gc */
+} /* namespace js */
+
+#endif /* gc_FindSCCs_h */