js/public/UbiNodePostOrder.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 js_UbiNodePostOrder_h
   8 #define js_UbiNodePostOrder_h
   9
  10 #include "mozilla/Attributes.h"
  11
  12 #include <utility>
  13
  14 #include "js/UbiNode.h"
  15 #include "js/Vector.h"
  16
  17 namespace js {
  18 class SystemAllocPolicy;
  19 }
  20
  21 namespace JS {
  22 class AutoCheckCannotGC;
  23
  24 namespace ubi {
  25
  26 /**
  27  * A post-order depth-first traversal of `ubi::Node` graphs.
  28  *
  29  * No GC may occur while an instance of `PostOrder` is live.
  30  *
  31  * The `NodeVisitor` type provided to `PostOrder::traverse` must have the
  32  * following member:
  33  *
  34  *   bool operator()(Node& node)
  35  *
  36  *     The node visitor method. This method is called once for each `node`
  37  *     reachable from the start set in post-order.
  38  *
  39  *     This visitor function should return true on success, or false if an error
  40  *     occurs. A false return value terminates the traversal immediately, and
  41  *     causes `PostOrder::traverse` to return false.
  42  *
  43  * The `EdgeVisitor` type provided to `PostOrder::traverse` must have the
  44  * following member:
  45  *
  46  *   bool operator()(Node& origin, Edge& edge)
  47  *
  48  *     The edge visitor method. This method is called once for each outgoing
  49  *     `edge` from `origin` that is reachable from the start set.
  50  *
  51  *     NB: UNLIKE NODES, THERE IS NO GUARANTEED ORDER IN WHICH EDGES AND THEIR
  52  *     ORIGINS ARE VISITED!
  53  *
  54  *     This visitor function should return true on success, or false if an error
  55  *     occurs. A false return value terminates the traversal immediately, and
  56  *     causes `PostOrder::traverse` to return false.
  57  */
  58 struct PostOrder {
  59  private:
  60   struct OriginAndEdges {
  61     Node origin;
  62     EdgeVector edges;
  63
  64     OriginAndEdges(const Node& node, EdgeVector&& edges)
  65         : origin(node), edges(std::move(edges)) {}
  66
  67     OriginAndEdges(const OriginAndEdges& rhs) = delete;
  68     OriginAndEdges& operator=(const OriginAndEdges& rhs) = delete;
  69
  70     OriginAndEdges(OriginAndEdges&& rhs)
  71         : origin(rhs.origin), edges(std::move(rhs.edges)) {
  72       MOZ_ASSERT(&rhs != this, "self-move disallowed");
  73     }
  74
  75     OriginAndEdges& operator=(OriginAndEdges&& rhs) {
  76       this->~OriginAndEdges();
  77       new (this) OriginAndEdges(std::move(rhs));
  78       return *this;
  79     }
  80   };
  81
  82   using Stack = js::Vector<OriginAndEdges, 256, js::SystemAllocPolicy>;
  83   using Set = js::HashSet<Node, js::DefaultHasher<Node>, js::SystemAllocPolicy>;
  84
  85   JSContext* cx;
  86   Set seen;
  87   Stack stack;
  88 #ifdef DEBUG
  89   bool traversed;
  90 #endif
  91
  92  private:
  93   [[nodiscard]] bool fillEdgesFromRange(EdgeVector& edges,
  94                                         js::UniquePtr<EdgeRange>& range) {
  95     MOZ_ASSERT(range);
  96     for (; !range->empty(); range->popFront()) {
  97       if (!edges.append(std::move(range->front()))) {
  98         return false;
  99       }
 100     }
 101     return true;
 102   }
 103
 104   [[nodiscard]] bool pushForTraversing(const Node& node) {
 105     EdgeVector edges;
 106     auto range = node.edges(cx, /* wantNames */ false);
 107     return range && fillEdgesFromRange(edges, range) &&
 108            stack.append(OriginAndEdges(node, std::move(edges)));
 109   }
 110
 111  public:
 112   // Construct a post-order traversal object.
 113   //
 114   // The traversal asserts that no GC happens in its runtime during its
 115   // lifetime via the `AutoCheckCannotGC&` parameter. We do nothing with it,
 116   // other than require it to exist with a lifetime that encloses our own.
 117   PostOrder(JSContext* cx, AutoCheckCannotGC&)
 118       : cx(cx),
 119         seen(),
 120         stack()
 121 #ifdef DEBUG
 122         ,
 123         traversed(false)
 124 #endif
 125   {
 126   }
 127
 128   // Add `node` as a starting point for the traversal. You may add
 129   // as many starting points as you like. Returns false on OOM.
 130   [[nodiscard]] bool addStart(const Node& node) {
 131     if (!seen.put(node)) {
 132       return false;
 133     }
 134     return pushForTraversing(node);
 135   }
 136
 137   // Traverse the graph in post-order, starting with the set of nodes passed
 138   // to `addStart` and applying `onNode::operator()` for each node in the
 139   // graph and `onEdge::operator()` for each edge in the graph, as described
 140   // above.
 141   //
 142   // This should be called only once per instance of this class.
 143   //
 144   // Return false on OOM or error return from `onNode::operator()` or
 145   // `onEdge::operator()`.
 146   template <typename NodeVisitor, typename EdgeVisitor>
 147   [[nodiscard]] bool traverse(NodeVisitor onNode, EdgeVisitor onEdge) {
 148 #ifdef DEBUG
 149     MOZ_ASSERT(!traversed, "Can only traverse() once!");
 150     traversed = true;
 151 #endif
 152
 153     while (!stack.empty()) {
 154       auto& origin = stack.back().origin;
 155       auto& edges = stack.back().edges;
 156
 157       if (edges.empty()) {
 158         if (!onNode(origin)) {
 159           return false;
 160         }
 161         stack.popBack();
 162         continue;
 163       }
 164
 165       Edge edge = std::move(edges.back());
 166       edges.popBack();
 167
 168       if (!onEdge(origin, edge)) {
 169         return false;
 170       }
 171
 172       auto ptr = seen.lookupForAdd(edge.referent);
 173       // We've already seen this node, don't follow its edges.
 174       if (ptr) {
 175         continue;
 176       }
 177
 178       // Mark the referent as seen and follow its edges.
 179       if (!seen.add(ptr, edge.referent) || !pushForTraversing(edge.referent)) {
 180         return false;
 181       }
 182     }
 183
 184     return true;
 185   }
 186 };
 187
 188 }  // namespace ubi
 189 }  // namespace JS
 190
 191 #endif  // js_UbiNodePostOrder_h