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/. */
7 #ifndef js_UbiNodeBreadthFirst_h
8 #define js_UbiNodeBreadthFirst_h
10 #include "js/HashTable.h"
11 #include "js/UbiNode.h"
12 #include "js/Vector.h"
17 // A breadth-first traversal template for graphs of ubi::Nodes.
19 // No GC may occur while an instance of this template is live.
21 // The provided Handler type should have two members:
25 // The value type of |BreadthFirst<Handler>::visited|, the HashMap of
26 // ubi::Nodes that have been visited so far. Since the algorithm needs a
27 // hash table like this for its own use anyway, it is simple to let
28 // Handler store its own metadata about each node in the same table.
30 // For example, if you want to find a shortest path to each node from any
31 // traversal starting point, your |NodeData| type could record the first
32 // edge to reach each node, and the node from which it originates. Then,
33 // when the traversal is complete, you can walk backwards from any node
34 // to some starting point, and the path recorded will be a shortest path.
36 // This type must have a default constructor. If this type owns any other
37 // resources, move constructors and assignment operators are probably a
40 // bool operator() (BreadthFirst& traversal,
41 // Node origin, const Edge& edge,
42 // Handler::NodeData* referentData, bool first);
44 // The visitor function, called to report that we have traversed
45 // |edge| from |origin|. This is called once for each edge we traverse.
46 // As this is a breadth-first search, any prior calls to the visitor
47 // function were for origin nodes not further from the start nodes than
50 // |traversal| is this traversal object, passed along for convenience.
52 // |referentData| is a pointer to the value of the entry in
53 // |traversal.visited| for |edge.referent|; the visitor function can
54 // store whatever metadata it likes about |edge.referent| there.
56 // |first| is true if this is the first time we have visited an edge
57 // leading to |edge.referent|. This could be stored in NodeData, but
58 // the algorithm knows whether it has just created the entry in
59 // |traversal.visited|, so it passes it along for convenience.
61 // The visitor function may call |traversal.abandonReferent()| if it
62 // doesn't want to traverse the outgoing edges of |edge.referent|. You can
63 // use this to limit the traversal to a given portion of the graph: it will
64 // never visit nodes reachable only through nodes that you have abandoned.
65 // Note that |abandonReferent| must be called the first time the given node
66 // is reached; that is, |first| must be true.
68 // The visitor function may call |doNotMarkReferentAsVisited()| if it
69 // does not want a node to be considered 'visited' (and added to the
70 // 'visited' set). This is useful when the visitor has custom logic to
71 // determine whether an edge is 'interesting'.
73 // The visitor function may call |traversal.stop()| if it doesn't want
74 // to visit any more nodes at all.
76 // The visitor function may consult |traversal.visited| for information
77 // about other nodes, but it should not add or remove entries.
79 // The visitor function should return true on success, or false if an
80 // error occurs. A false return value terminates the traversal
81 // immediately, and causes BreadthFirst<Handler>::traverse to return
83 template <typename Handler
>
85 // Construct a breadth-first traversal object that reports the nodes it
86 // reaches to |handler|. The traversal asserts that no GC happens in its
87 // runtime during its lifetime.
89 // We do nothing with noGC, other than require it to exist, with a lifetime
90 // that encloses our own.
91 BreadthFirst(JSContext
* cx
, Handler
& handler
, const JS::AutoRequireNoGC
& noGC
)
97 traversalBegun(false),
99 abandonRequested(false),
100 markReferentAsVisited(false) {}
102 // Add |node| as a starting point for the traversal. You may add
103 // as many starting points as you like. Return false on OOM.
104 bool addStart(Node node
) { return pending
.append(node
); }
106 // Add |node| as a starting point for the traversal (see addStart) and also
107 // add it to the |visited| set. Return false on OOM.
108 bool addStartVisited(Node node
) {
109 typename
NodeMap::AddPtr ptr
= visited
.lookupForAdd(node
);
110 if (!ptr
&& !visited
.add(ptr
, node
, typename
Handler::NodeData())) {
113 return addStart(node
);
116 // True if the handler wants us to compute edge names; doing so can be
117 // expensive in time and memory. True by default.
120 // Traverse the graph in breadth-first order, starting at the given
121 // start nodes, applying |handler::operator()| for each edge traversed
122 // as described above.
124 // This should be called only once per instance of this class.
126 // Return false on OOM or error return from |handler::operator()|.
128 MOZ_ASSERT(!traversalBegun
);
129 traversalBegun
= true;
131 // While there are pending nodes, visit them.
132 while (!pending
.empty()) {
133 Node origin
= pending
.front();
136 // Get a range containing all origin's outgoing edges.
137 auto range
= origin
.edges(cx
, wantNames
);
142 // Traverse each edge.
143 for (; !range
->empty(); range
->popFront()) {
144 MOZ_ASSERT(!stopRequested
);
146 Edge
& edge
= range
->front();
147 typename
NodeMap::AddPtr a
= visited
.lookupForAdd(edge
.referent
);
150 // Pass a pointer to a stack-allocated NodeData if the referent is not
152 typename
Handler::NodeData nodeData
;
153 typename
Handler::NodeData
* nodeDataPtr
=
154 first
? &nodeData
: &a
->value();
156 // Report this edge to the visitor function.
157 markReferentAsVisited
= true;
158 if (!handler(*this, origin
, edge
, nodeDataPtr
, first
)) {
162 if (first
&& markReferentAsVisited
) {
163 // This is the first time we've reached |edge.referent| and the
164 // handler wants it marked as visited.
165 if (!visited
.add(a
, edge
.referent
, std::move(nodeData
))) {
174 // Arrange to traverse this edge's referent's outgoing edges
175 // later --- unless |handler| asked us not to.
176 if (abandonRequested
) {
177 // Skip the enqueue; reset flag for future iterations.
178 abandonRequested
= false;
180 if (!pending
.append(edge
.referent
)) {
190 // Stop traversal, and return true from |traverse| without visiting any
191 // more nodes. Only |handler::operator()| should call this function; it
192 // may do so to stop the traversal early, without returning false and
193 // then making |traverse|'s caller disambiguate that result from a real
195 void stop() { stopRequested
= true; }
197 // Request that the current edge's referent's outgoing edges not be
198 // traversed. This must be called the first time that referent is reached.
199 // Other edges *to* that referent will still be traversed.
200 void abandonReferent() { abandonRequested
= true; }
202 // Request the the current edge's referent not be added to the |visited| set
203 // if this is the first time we're visiting it.
204 void doNotMarkReferentAsVisited() { markReferentAsVisited
= false; }
206 // The context with which we were constructed.
209 // A map associating each node N that we have reached with a
210 // Handler::NodeData, for |handler|'s use. This is public, so that
211 // |handler| can access it to see the traversal thus far.
212 using NodeMap
= js::HashMap
<Node
, typename
Handler::NodeData
,
213 js::DefaultHasher
<Node
>, js::SystemAllocPolicy
>;
217 // Our handler object.
220 // A queue template. Appending and popping the front are constant time.
221 // Wasted space is never more than some recent actual population plus the
222 // current population.
223 template <typename T
>
225 js::Vector
<T
, 0, js::SystemAllocPolicy
> head
, tail
;
229 Queue() : head(), tail(), frontIndex(0) {}
230 bool empty() { return frontIndex
>= head
.length(); }
232 MOZ_ASSERT(!empty());
233 return head
[frontIndex
];
236 MOZ_ASSERT(!empty());
238 if (frontIndex
>= head
.length()) {
244 bool append(const T
& elt
) {
245 return frontIndex
== 0 ? head
.append(elt
) : tail
.append(elt
);
249 // A queue of nodes that we have reached, but whose outgoing edges we
250 // have not yet traversed. Nodes reachable in fewer edges are enqueued
254 // True if our traverse function has been called.
257 // True if we've been asked to stop the traversal.
260 // True if we've been asked to abandon the current edge's referent.
261 bool abandonRequested
;
263 // True if the node should be added to the |visited| set after calling the
265 bool markReferentAsVisited
;
271 #endif // js_UbiNodeBreadthFirst_h