1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sts=4 et sw=4 tw=99:
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_UbiNodeTraverse_h
8 #define js_UbiNodeTraverse_h
10 #include "js/UbiNode.h"
11 #include "js/Utility.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 function
47 // were for origin nodes not further from the start nodes than |origin|.
49 // |traversal| is this traversal object, passed along for convenience.
51 // |referentData| is a pointer to the value of the entry in
52 // |traversal.visited| for |edge.referent|; the visitor function can
53 // store whatever metadata it likes about |edge.referent| there.
55 // |first| is true if this is the first time we have visited an edge
56 // leading to |edge.referent|. This could be stored in NodeData, but
57 // the algorithm knows whether it has just created the entry in
58 // |traversal.visited|, so it passes it along for convenience.
60 // The visitor function may call |traversal.abandonReferent()| if it
61 // doesn't want to traverse the outgoing edges of |edge.referent|. You can
62 // use this to limit the traversal to a given portion of the graph: it will
63 // never visit nodes reachable only through nodes that you have abandoned.
64 // Note that |abandonReferent| must be called the first time the given node
65 // is reached; that is, |first| must be true.
67 // The visitor function may call |traversal.stop()| if it doesn't want
68 // to visit any more nodes at all.
70 // The visitor function may consult |traversal.visited| for information
71 // about other nodes, but it should not add or remove entries.
73 // The visitor function should return true on success, or false if an
74 // error occurs. A false return value terminates the traversal
75 // immediately, and causes BreadthFirst<Handler>::traverse to return
77 template<typename Handler
>
80 // Construct a breadth-first traversal object that reports the nodes it
81 // reaches to |handler|. The traversal object reports OOM on |cx|, and
82 // asserts that no GC happens in |cx|'s runtime during its lifetime.
84 // We do nothing with noGC, other than require it to exist, with a lifetime
85 // that encloses our own.
86 BreadthFirst(JSContext
* cx
, Handler
& handler
, const JS::AutoCheckCannotGC
& noGC
)
87 : wantNames(true), cx(cx
), visited(cx
), handler(handler
), pending(cx
),
88 traversalBegun(false), stopRequested(false), abandonRequested(false)
91 // Initialize this traversal object. Return false on OOM.
92 bool init() { return visited
.init(); }
94 // Add |node| as a starting point for the traversal. You may add
95 // as many starting points as you like. Return false on OOM.
96 bool addStart(Node node
) { return pending
.append(node
); }
98 // True if the handler wants us to compute edge names; doing so can be
99 // expensive in time and memory. True by default.
102 // Traverse the graph in breadth-first order, starting at the given
103 // start nodes, applying |handler::operator()| for each edge traversed
104 // as described above.
106 // This should be called only once per instance of this class.
108 // Return false on OOM or error return from |handler::operator()|.
111 MOZ_ASSERT(!traversalBegun
);
112 traversalBegun
= true;
114 // While there are pending nodes, visit them, until we've found a path to the target.
115 while (!pending
.empty()) {
116 Node origin
= pending
.front();
119 // Get a range containing all origin's outgoing edges.
120 js::ScopedJSDeletePtr
<EdgeRange
> range(origin
.edges(cx
, wantNames
));
124 // Traverse each edge.
125 for (; !range
->empty(); range
->popFront()) {
126 MOZ_ASSERT(!stopRequested
);
128 const Edge
& edge
= range
->front();
129 typename
NodeMap::AddPtr a
= visited
.lookupForAdd(edge
.referent
);
133 // This is the first time we've reached |edge.referent|.
134 // Mark it as visited.
135 if (!visited
.add(a
, edge
.referent
, typename
Handler::NodeData()))
141 // Report this edge to the visitor function.
142 if (!handler(*this, origin
, edge
, &a
->value(), first
))
148 // Arrange to traverse this edge's referent's outgoing edges
149 // later --- unless |handler| asked us not to.
150 if (abandonRequested
) {
151 // Skip the enqueue; reset flag for future iterations.
152 abandonRequested
= false;
154 if (!pending
.append(edge
.referent
))
163 // Stop traversal, and return true from |traverse| without visiting any
164 // more nodes. Only |handler::operator()| should call this function; it
165 // may do so to stop the traversal early, without returning false and
166 // then making |traverse|'s caller disambiguate that result from a real
168 void stop() { stopRequested
= true; }
170 // Request that the current edge's referent's outgoing edges not be
171 // traversed. This must be called the first time that referent is reached.
172 // Other edges *to* that referent will still be traversed.
173 void abandonReferent() { abandonRequested
= true; }
175 // The context with which we were constructed.
178 // A map associating each node N that we have reached with a
179 // Handler::NodeData, for |handler|'s use. This is public, so that
180 // |handler| can access it to see the traversal thus far.
181 typedef js::HashMap
<Node
, typename
Handler::NodeData
> NodeMap
;
185 // Our handler object.
188 // A queue template. Appending and popping the front are constant time.
189 // Wasted space is never more than some recent actual population plus the
190 // current population.
191 template <typename T
>
193 js::Vector
<T
, 0> head
, tail
;
196 explicit Queue(JSContext
* cx
) : head(cx
), tail(cx
), frontIndex(0) { }
197 bool empty() { return frontIndex
>= head
.length(); }
199 MOZ_ASSERT(!empty());
200 return head
[frontIndex
];
203 MOZ_ASSERT(!empty());
205 if (frontIndex
>= head
.length()) {
211 bool append(const T
& elt
) {
212 return frontIndex
== 0 ? head
.append(elt
) : tail
.append(elt
);
216 // A queue of nodes that we have reached, but whose outgoing edges we
217 // have not yet traversed. Nodes reachable in fewer edges are enqueued
221 // True if our traverse function has been called.
224 // True if we've been asked to stop the traversal.
227 // True if we've been asked to abandon the current edge's referent.
228 bool abandonRequested
;
234 #endif // js_UbiNodeTraverse.h