/* -*- 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