/* -*- 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:
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(*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 */