1 files changed, 271 insertions, 0 deletions
diff --git a/js/public/UbiNodeBreadthFirst.h b/js/public/UbiNodeBreadthFirst.h
new file mode 100644
index 0000000000..2f269fbf37
--- /dev/null
+++ b/js/public/UbiNodeBreadthFirst.h
@@ -0,0 +1,271 @@
+/* -*- 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 js_UbiNodeBreadthFirst_h
+#define js_UbiNodeBreadthFirst_h
+
+#include "js/UbiNode.h"
+#include "js/Utility.h"
+#include "js/Vector.h"
+
+namespace JS {
+namespace ubi {
+
+// A breadth-first traversal template for graphs of ubi::Nodes.
+//
+// No GC may occur while an instance of this template is live.
+//
+// The provided Handler type should have two members:
+//
+//   typename NodeData;
+//
+//      The value type of |BreadthFirst<Handler>::visited|, the HashMap of
+//      ubi::Nodes that have been visited so far. Since the algorithm needs a
+//      hash table like this for its own use anyway, it is simple to let
+//      Handler store its own metadata about each node in the same table.
+//
+//      For example, if you want to find a shortest path to each node from any
+//      traversal starting point, your |NodeData| type could record the first
+//      edge to reach each node, and the node from which it originates. Then,
+//      when the traversal is complete, you can walk backwards from any node
+//      to some starting point, and the path recorded will be a shortest path.
+//
+//      This type must have a default constructor. If this type owns any other
+//      resources, move constructors and assignment operators are probably a
+//      good idea, too.
+//
+//   bool operator() (BreadthFirst& traversal,
+//                    Node origin, const Edge& edge,
+//                    Handler::NodeData* referentData, bool first);
+//
+//      The visitor function, called to report that we have traversed
+//      |edge| from |origin|. This is called once for each edge we traverse.
+//      As this is a breadth-first search, any prior calls to the visitor
+//      function were for origin nodes not further from the start nodes than
+//      |origin|.
+//
+//      |traversal| is this traversal object, passed along for convenience.
+//
+//      |referentData| is a pointer to the value of the entry in
+//      |traversal.visited| for |edge.referent|; the visitor function can
+//      store whatever metadata it likes about |edge.referent| there.
+//
+//      |first| is true if this is the first time we have visited an edge
+//      leading to |edge.referent|. This could be stored in NodeData, but
+//      the algorithm knows whether it has just created the entry in
+//      |traversal.visited|, so it passes it along for convenience.
+//
+//      The visitor function may call |traversal.abandonReferent()| if it
+//      doesn't want to traverse the outgoing edges of |edge.referent|. You can
+//      use this to limit the traversal to a given portion of the graph: it will
+//      never visit nodes reachable only through nodes that you have abandoned.
+//      Note that |abandonReferent| must be called the first time the given node
+//      is reached; that is, |first| must be true.
+//
+//      The visitor function may call |doNotMarkReferentAsVisited()| if it
+//      does not want a node to be considered 'visited' (and added to the
+//      'visited' set). This is useful when the visitor has custom logic to
+//      determine whether an edge is 'interesting'.
+//
+//      The visitor function may call |traversal.stop()| if it doesn't want
+//      to visit any more nodes at all.
+//
+//      The visitor function may consult |traversal.visited| for information
+//      about other nodes, but it should not add or remove entries.
+//
+//      The visitor function should return true on success, or false if an
+//      error occurs. A false return value terminates the traversal
+//      immediately, and causes BreadthFirst<Handler>::traverse to return
+//      false.
+template <typename Handler>
+struct BreadthFirst {
+  // Construct a breadth-first traversal object that reports the nodes it
+  // reaches to |handler|. The traversal asserts that no GC happens in its
+  // runtime during its lifetime.
+  //
+  // We do nothing with noGC, other than require it to exist, with a lifetime
+  // that encloses our own.
+  BreadthFirst(JSContext* cx, Handler& handler, const JS::AutoRequireNoGC& noGC)
+      : wantNames(true),
+        cx(cx),
+        visited(),
+        handler(handler),
+        pending(),
+        traversalBegun(false),
+        stopRequested(false),
+        abandonRequested(false),
+        markReferentAsVisited(false) {}
+
+  // Add |node| as a starting point for the traversal. You may add
+  // as many starting points as you like. Return false on OOM.
+  bool addStart(Node node) { return pending.append(node); }
+
+  // Add |node| as a starting point for the traversal (see addStart) and also
+  // add it to the |visited| set. Return false on OOM.
+  bool addStartVisited(Node node) {
+    typename NodeMap::AddPtr ptr = visited.lookupForAdd(node);
+    if (!ptr && !visited.add(ptr, node, typename Handler::NodeData())) {
+      return false;
+    }
+    return addStart(node);
+  }
+
+  // True if the handler wants us to compute edge names; doing so can be
+  // expensive in time and memory. True by default.
+  bool wantNames;
+
+  // Traverse the graph in breadth-first order, starting at the given
+  // start nodes, applying |handler::operator()| for each edge traversed
+  // as described above.
+  //
+  // This should be called only once per instance of this class.
+  //
+  // Return false on OOM or error return from |handler::operator()|.
+  bool traverse() {
+    MOZ_ASSERT(!traversalBegun);
+    traversalBegun = true;
+
+    // While there are pending nodes, visit them.
+    while (!pending.empty()) {
+      Node origin = pending.front();
+      pending.popFront();
+
+      // Get a range containing all origin's outgoing edges.
+      auto range = origin.edges(cx, wantNames);
+      if (!range) {
+        return false;
+      }
+
+      // Traverse each edge.
+      for (; !range->empty(); range->popFront()) {
+        MOZ_ASSERT(!stopRequested);
+
+        Edge& edge = range->front();
+        typename NodeMap::AddPtr a = visited.lookupForAdd(edge.referent);
+        bool first = !a;
+
+        // Pass a pointer to a stack-allocated NodeData if the referent is not
+        // in |visited|.
+        typename Handler::NodeData nodeData;
+        typename Handler::NodeData* nodeDataPtr =
+            first ? &nodeData : &a->value();
+
+        // Report this edge to the visitor function.
+        markReferentAsVisited = true;
+        if (!handler(*this, origin, edge, nodeDataPtr, first)) {
+          return false;
+        }
+
+        if (first && markReferentAsVisited) {
+          // This is the first time we've reached |edge.referent| and the
+          // handler wants it marked as visited.
+          if (!visited.add(a, edge.referent, std::move(nodeData))) {
+            return false;
+          }
+        }
+
+        if (stopRequested) {
+          return true;
+        }
+
+        // Arrange to traverse this edge's referent's outgoing edges
+        // later --- unless |handler| asked us not to.
+        if (abandonRequested) {
+          // Skip the enqueue; reset flag for future iterations.
+          abandonRequested = false;
+        } else if (first) {
+          if (!pending.append(edge.referent)) {
+            return false;
+          }
+        }
+      }
+    }
+
+    return true;
+  }
+
+  // Stop traversal, and return true from |traverse| without visiting any
+  // more nodes. Only |handler::operator()| should call this function; it
+  // may do so to stop the traversal early, without returning false and
+  // then making |traverse|'s caller disambiguate that result from a real
+  // error.
+  void stop() { stopRequested = true; }
+
+  // Request that the current edge's referent's outgoing edges not be
+  // traversed. This must be called the first time that referent is reached.
+  // Other edges *to* that referent will still be traversed.
+  void abandonReferent() { abandonRequested = true; }
+
+  // Request the the current edge's referent not be added to the |visited| set
+  // if this is the first time we're visiting it.
+  void doNotMarkReferentAsVisited() { markReferentAsVisited = false; }
+
+  // The context with which we were constructed.
+  JSContext* cx;
+
+  // A map associating each node N that we have reached with a
+  // Handler::NodeData, for |handler|'s use. This is public, so that
+  // |handler| can access it to see the traversal thus far.
+  using NodeMap = js::HashMap<Node, typename Handler::NodeData,
+                              js::DefaultHasher<Node>, js::SystemAllocPolicy>;
+  NodeMap visited;
+
+ private:
+  // Our handler object.
+  Handler& handler;
+
+  // A queue template. Appending and popping the front are constant time.
+  // Wasted space is never more than some recent actual population plus the
+  // current population.
+  template <typename T>
+  class Queue {
+    js::Vector<T, 0, js::SystemAllocPolicy> head, tail;
+    size_t frontIndex;
+
+   public:
+    Queue() : head(), tail(), frontIndex(0) {}
+    bool empty() { return frontIndex >= head.length(); }
+    T& front() {
+      MOZ_ASSERT(!empty());
+      return head[frontIndex];
+    }
+    void popFront() {
+      MOZ_ASSERT(!empty());
+      frontIndex++;
+      if (frontIndex >= head.length()) {
+        head.clearAndFree();
+        head.swap(tail);
+        frontIndex = 0;
+      }
+    }
+    bool append(const T& elt) {
+      return frontIndex == 0 ? head.append(elt) : tail.append(elt);
+    }
+  };
+
+  // A queue of nodes that we have reached, but whose outgoing edges we
+  // have not yet traversed. Nodes reachable in fewer edges are enqueued
+  // earlier.
+  Queue<Node> pending;
+
+  // True if our traverse function has been called.
+  bool traversalBegun;
+
+  // True if we've been asked to stop the traversal.
+  bool stopRequested;
+
+  // True if we've been asked to abandon the current edge's referent.
+  bool abandonRequested;
+
+  // True if the node should be added to the |visited| set after calling the
+  // handler.
+  bool markReferentAsVisited;
+};
+
+}  // namespace ubi
+}  // namespace JS
+
+#endif  // js_UbiNodeBreadthFirst_h