summaryrefslogtreecommitdiff
path: root/js/public/UbiNodeBreadthFirst.h
diff options
context:
space:
mode:
Diffstat (limited to 'js/public/UbiNodeBreadthFirst.h')
-rw-r--r--js/public/UbiNodeBreadthFirst.h244
1 files changed, 244 insertions, 0 deletions
diff --git a/js/public/UbiNodeBreadthFirst.h b/js/public/UbiNodeBreadthFirst.h
new file mode 100644
index 0000000000..8446dbc6af
--- /dev/null
+++ b/js/public/UbiNodeBreadthFirst.h
@@ -0,0 +1,244 @@
+/* -*- 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 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 |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::AutoCheckCannotGC& noGC)
+ : wantNames(true), cx(cx), visited(), handler(handler), pending(),
+ traversalBegun(false), stopRequested(false), abandonRequested(false)
+ { }
+
+ // Initialize this traversal object. Return false on OOM.
+ bool init() { return visited.init(); }
+
+ // 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;
+
+ if (first) {
+ // This is the first time we've reached |edge.referent|.
+ // Mark it as visited.
+ if (!visited.add(a, edge.referent, typename Handler::NodeData()))
+ return false;
+ }
+
+ MOZ_ASSERT(a);
+
+ // Report this edge to the visitor function.
+ if (!handler(*this, origin, edge, &a->value(), first))
+ 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; }
+
+ // 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;
+};
+
+} // namespace ubi
+} // namespace JS
+
+#endif // js_UbiNodeBreadthFirst_h