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