js/src/gc/FindSCCs.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef gc_FindSCCs_h
   8 #define gc_FindSCCs_h
   9
  10 #include "mozilla/Assertions.h"  // MOZ_ASSERT
  11
  12 #include <algorithm>  // std::min
  13
  14 #include "js/AllocPolicy.h"         // js::SystemAllocPolicy
  15 #include "js/friend/StackLimits.h"  // js::AutoCheckRecursionLimit
  16 #include "js/HashTable.h"           // js::HashSet, js::DefaultHasher
  17
  18 namespace js {
  19 namespace gc {
  20
  21 template <typename Node>
  22 struct GraphNodeBase {
  23   using NodeSet =
  24       js::HashSet<Node*, js::DefaultHasher<Node*>, js::SystemAllocPolicy>;
  25
  26   NodeSet gcGraphEdges;
  27   Node* gcNextGraphNode = nullptr;
  28   Node* gcNextGraphComponent = nullptr;
  29   unsigned gcDiscoveryTime = 0;
  30   unsigned gcLowLink = 0;
  31
  32   Node* nextNodeInGroup() const {
  33     if (gcNextGraphNode &&
  34         gcNextGraphNode->gcNextGraphComponent == gcNextGraphComponent) {
  35       return gcNextGraphNode;
  36     }
  37     return nullptr;
  38   }
  39
  40   Node* nextGroup() const { return gcNextGraphComponent; }
  41 };
  42
  43 /*
  44  * Find the strongly connected components of a graph using Tarjan's algorithm,
  45  * and return them in topological order.
  46  *
  47  * Nodes derive from GraphNodeBase and add target edge pointers to
  48  * sourceNode.gcGraphEdges to describe the graph:
  49  *
  50  * struct MyGraphNode : public GraphNodeBase<MyGraphNode>
  51  * {
  52  *   ...
  53  * }
  54  *
  55  * MyGraphNode node1, node2, node3;
  56  * node1.gcGraphEdges.put(node2); // Error checking elided.
  57  * node2.gcGraphEdges.put(node3);
  58  * node3.gcGraphEdges.put(node2);
  59  *
  60  * ComponentFinder<MyGraphNode> finder;
  61  * finder.addNode(node1);
  62  * finder.addNode(node2);
  63  * finder.addNode(node3);
  64  * MyGraphNode* result = finder.getResultsList();
  65  */
  66
  67 template <typename Node>
  68 class ComponentFinder {
  69  public:
  70   explicit ComponentFinder(JSContext* cx) : cx(cx) {}
  71
  72   ~ComponentFinder() {
  73     MOZ_ASSERT(!stack);
  74     MOZ_ASSERT(!firstComponent);
  75   }
  76
  77   /* Forces all nodes to be added to a single component. */
  78   void useOneComponent() { stackFull = true; }
  79
  80   void addNode(Node* v) {
  81     if (v->gcDiscoveryTime == Undefined) {
  82       MOZ_ASSERT(v->gcLowLink == Undefined);
  83       processNode(v);
  84     }
  85   }
  86
  87   Node* getResultsList() {
  88     if (stackFull) {
  89       /*
  90        * All nodes after the stack overflow are in |stack|. Put them all in
  91        * one big component of their own.
  92        */
  93       Node* firstGoodComponent = firstComponent;
  94       for (Node* v = stack; v; v = stack) {
  95         stack = v->gcNextGraphNode;
  96         v->gcNextGraphComponent = firstGoodComponent;
  97         v->gcNextGraphNode = firstComponent;
  98         firstComponent = v;
  99       }
 100       stackFull = false;
 101     }
 102
 103     MOZ_ASSERT(!stack);
 104
 105     Node* result = firstComponent;
 106     firstComponent = nullptr;
 107
 108     for (Node* v = result; v; v = v->gcNextGraphNode) {
 109       v->gcDiscoveryTime = Undefined;
 110       v->gcLowLink = Undefined;
 111     }
 112
 113     return result;
 114   }
 115
 116   static void mergeGroups(Node* first) {
 117     for (Node* v = first; v; v = v->gcNextGraphNode) {
 118       v->gcNextGraphComponent = nullptr;
 119     }
 120   }
 121
 122  private:
 123   // Constant used to indicate an unprocessed vertex.
 124   static const unsigned Undefined = 0;
 125
 126   // Constant used to indicate a processed vertex that is no longer on the
 127   // stack.
 128   static const unsigned Finished = (unsigned)-1;
 129
 130   void addEdgeTo(Node* w) {
 131     if (w->gcDiscoveryTime == Undefined) {
 132       processNode(w);
 133       cur->gcLowLink = std::min(cur->gcLowLink, w->gcLowLink);
 134     } else if (w->gcDiscoveryTime != Finished) {
 135       cur->gcLowLink = std::min(cur->gcLowLink, w->gcDiscoveryTime);
 136     }
 137   }
 138
 139   void processNode(Node* v) {
 140     v->gcDiscoveryTime = clock;
 141     v->gcLowLink = clock;
 142     ++clock;
 143
 144     v->gcNextGraphNode = stack;
 145     stack = v;
 146
 147     if (stackFull) {
 148       return;
 149     }
 150
 151     AutoCheckRecursionLimit recursion(cx);
 152     if (!recursion.checkSystemDontReport(cx)) {
 153       stackFull = true;
 154       return;
 155     }
 156
 157     Node* old = cur;
 158     cur = v;
 159     for (auto r = cur->gcGraphEdges.all(); !r.empty(); r.popFront()) {
 160       addEdgeTo(r.front());
 161     }
 162     cur = old;
 163
 164     if (stackFull) {
 165       return;
 166     }
 167
 168     if (v->gcLowLink == v->gcDiscoveryTime) {
 169       Node* nextComponent = firstComponent;
 170       Node* w;
 171       do {
 172         MOZ_ASSERT(stack);
 173         w = stack;
 174         stack = w->gcNextGraphNode;
 175
 176         /*
 177          * Record that the element is no longer on the stack by setting the
 178          * discovery time to a special value that's not Undefined.
 179          */
 180         w->gcDiscoveryTime = Finished;
 181
 182         /* Figure out which group we're in. */
 183         w->gcNextGraphComponent = nextComponent;
 184
 185         /*
 186          * Prepend the component to the beginning of the output list to
 187          * reverse the list and achieve the desired order.
 188          */
 189         w->gcNextGraphNode = firstComponent;
 190         firstComponent = w;
 191       } while (w != v);
 192     }
 193   }
 194
 195  private:
 196   unsigned clock = 1;
 197   Node* stack = nullptr;
 198   Node* firstComponent = nullptr;
 199   Node* cur = nullptr;
 200   JSContext* cx;
 201   bool stackFull = false;
 202 };
 203
 204 } /* namespace gc */
 205 } /* namespace js */
 206
 207 #endif /* gc_FindSCCs_h */