diff -r 000000000000 -r 6474c204b198 js/src/gc/FindSCCs.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/js/src/gc/FindSCCs.h	Wed Dec 31 06:09:35 2014 +0100
@@ -0,0 +1,204 @@
+/* -*- 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 "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 MyGraphNode : public GraphNodeBase
+ * {
+ *     void findOutgoingEdges(ComponentFinder<MyGraphNode> &finder)
+ *     {
+ *         for edge in my_outgoing_edges:
+ *             if is_relevant(edge):
+ *                 finder.addEdgeTo(edge.destination)
+ *     }
+ * }
+ *
+ * ComponentFinder<MyGraphNode> finder;
+ * finder.addNode(v);
+ */
+template<class Node>
+class ComponentFinder
+{
+  public:
+    ComponentFinder(uintptr_t sl)
+      : clock(1),
+        stack(nullptr),
+        firstComponent(nullptr),
+        cur(nullptr),
+        stackLimit(sl),
+        stackFull(false)
+    {}
+
+    ~ComponentFinder() {
+        JS_ASSERT(!stack);
+        JS_ASSERT(!firstComponent);
+    }
+
+    /* Forces all nodes to be added to a single component. */
+    void useOneComponent() { stackFull = true; }
+
+    void addNode(Node *v) {
+        if (v->gcDiscoveryTime == Undefined) {
+            JS_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;
+        }
+
+        JS_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(*this);
+        cur = old;
+
+        if (stackFull)
+            return;
+
+        if (v->gcLowLink == v->gcDiscoveryTime) {
+            Node *nextComponent = firstComponent;
+            Node *w;
+            do {
+                JS_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 */