From 36d22d82aa202bb199967e9512281e9a53db42c9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 21:33:14 +0200 Subject: Adding upstream version 115.7.0esr. Signed-off-by: Daniel Baumann --- js/src/gc/FindSCCs.h | 207 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 207 insertions(+) create mode 100644 js/src/gc/FindSCCs.h (limited to 'js/src/gc/FindSCCs.h') diff --git a/js/src/gc/FindSCCs.h b/js/src/gc/FindSCCs.h new file mode 100644 index 0000000000..97069bcd09 --- /dev/null +++ b/js/src/gc/FindSCCs.h @@ -0,0 +1,207 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- + * vim: set ts=8 sts=2 et sw=2 tw=80: + * 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/Assertions.h" // MOZ_ASSERT + +#include // std::min + +#include "js/AllocPolicy.h" // js::SystemAllocPolicy +#include "js/friend/StackLimits.h" // js::AutoCheckRecursionLimit +#include "js/HashTable.h" // js::HashSet, js::DefaultHasher + +namespace js { +namespace gc { + +template +struct GraphNodeBase { + using NodeSet = + js::HashSet, js::SystemAllocPolicy>; + + NodeSet gcGraphEdges; + Node* gcNextGraphNode = nullptr; + Node* gcNextGraphComponent = nullptr; + unsigned gcDiscoveryTime = 0; + unsigned gcLowLink = 0; + + 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 add target edge pointers to + * sourceNode.gcGraphEdges to describe the graph: + * + * struct MyGraphNode : public GraphNodeBase + * { + * ... + * } + * + * MyGraphNode node1, node2, node3; + * node1.gcGraphEdges.put(node2); // Error checking elided. + * node2.gcGraphEdges.put(node3); + * node3.gcGraphEdges.put(node2); + * + * ComponentFinder finder; + * finder.addNode(node1); + * finder.addNode(node2); + * finder.addNode(node3); + * MyGraphNode* result = finder.getResultsList(); + */ + +template +class ComponentFinder { + public: + explicit ComponentFinder(JSContext* cx) : cx(cx) {} + + ~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; + } + } + + private: + // Constant used to indicate an unprocessed vertex. + static const unsigned Undefined = 0; + + // Constant used to indicate a processed vertex that is no longer on the + // stack. + static const unsigned Finished = (unsigned)-1; + + void addEdgeTo(Node* w) { + if (w->gcDiscoveryTime == Undefined) { + processNode(w); + cur->gcLowLink = std::min(cur->gcLowLink, w->gcLowLink); + } else if (w->gcDiscoveryTime != Finished) { + cur->gcLowLink = std::min(cur->gcLowLink, w->gcDiscoveryTime); + } + } + + void processNode(Node* v) { + v->gcDiscoveryTime = clock; + v->gcLowLink = clock; + ++clock; + + v->gcNextGraphNode = stack; + stack = v; + + if (stackFull) { + return; + } + + AutoCheckRecursionLimit recursion(cx); + if (!recursion.checkSystemDontReport(cx)) { + stackFull = true; + return; + } + + Node* old = cur; + cur = v; + for (auto r = cur->gcGraphEdges.all(); !r.empty(); r.popFront()) { + addEdgeTo(r.front()); + } + 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 = 1; + Node* stack = nullptr; + Node* firstComponent = nullptr; + Node* cur = nullptr; + JSContext* cx; + bool stackFull = false; +}; + +} /* namespace gc */ +} /* namespace js */ + +#endif /* gc_FindSCCs_h */ -- cgit v1.2.3