Line data Source code
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/. */
6 :
7 : #ifndef js_UbiNodeBreadthFirst_h
8 : #define js_UbiNodeBreadthFirst_h
9 :
10 : #include "js/UbiNode.h"
11 : #include "js/Utility.h"
12 : #include "js/Vector.h"
13 :
14 : namespace JS {
15 : namespace ubi {
16 :
17 : // A breadth-first traversal template for graphs of ubi::Nodes.
18 : //
19 : // No GC may occur while an instance of this template is live.
20 : //
21 : // The provided Handler type should have two members:
22 : //
23 : // typename NodeData;
24 : //
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.
29 : //
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.
35 : //
36 : // This type must have a default constructor. If this type owns any other
37 : // resources, move constructors and assignment operators are probably a
38 : // good idea, too.
39 : //
40 : // bool operator() (BreadthFirst& traversal,
41 : // Node origin, const Edge& edge,
42 : // Handler::NodeData* referentData, bool first);
43 : //
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|.
48 : //
49 : // |traversal| is this traversal object, passed along for convenience.
50 : //
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.
54 : //
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.
59 : //
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.
66 : //
67 : // The visitor function may call |traversal.stop()| if it doesn't want
68 : // to visit any more nodes at all.
69 : //
70 : // The visitor function may consult |traversal.visited| for information
71 : // about other nodes, but it should not add or remove entries.
72 : //
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
76 : // false.
77 : template<typename Handler>
78 0 : struct BreadthFirst {
79 :
80 : // Construct a breadth-first traversal object that reports the nodes it
81 : // reaches to |handler|. The traversal asserts that no GC happens in its
82 : // runtime during its lifetime.
83 : //
84 : // We do nothing with noGC, other than require it to exist, with a lifetime
85 : // that encloses our own.
86 0 : BreadthFirst(JSContext* cx, Handler& handler, const JS::AutoCheckCannotGC& noGC)
87 : : wantNames(true), cx(cx), visited(), handler(handler), pending(),
88 0 : traversalBegun(false), stopRequested(false), abandonRequested(false)
89 0 : { }
90 :
91 : // Initialize this traversal object. Return false on OOM.
92 0 : bool init() { return visited.init(); }
93 :
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 0 : bool addStart(Node node) { return pending.append(node); }
97 :
98 : // Add |node| as a starting point for the traversal (see addStart) and also
99 : // add it to the |visited| set. Return false on OOM.
100 0 : bool addStartVisited(Node node) {
101 0 : typename NodeMap::AddPtr ptr = visited.lookupForAdd(node);
102 0 : if (!ptr && !visited.add(ptr, node, typename Handler::NodeData()))
103 0 : return false;
104 0 : return addStart(node);
105 : }
106 :
107 : // True if the handler wants us to compute edge names; doing so can be
108 : // expensive in time and memory. True by default.
109 : bool wantNames;
110 :
111 : // Traverse the graph in breadth-first order, starting at the given
112 : // start nodes, applying |handler::operator()| for each edge traversed
113 : // as described above.
114 : //
115 : // This should be called only once per instance of this class.
116 : //
117 : // Return false on OOM or error return from |handler::operator()|.
118 0 : bool traverse()
119 : {
120 0 : MOZ_ASSERT(!traversalBegun);
121 0 : traversalBegun = true;
122 :
123 : // While there are pending nodes, visit them.
124 0 : while (!pending.empty()) {
125 0 : Node origin = pending.front();
126 0 : pending.popFront();
127 :
128 : // Get a range containing all origin's outgoing edges.
129 0 : auto range = origin.edges(cx, wantNames);
130 0 : if (!range)
131 0 : return false;
132 :
133 : // Traverse each edge.
134 0 : for (; !range->empty(); range->popFront()) {
135 0 : MOZ_ASSERT(!stopRequested);
136 :
137 0 : Edge& edge = range->front();
138 0 : typename NodeMap::AddPtr a = visited.lookupForAdd(edge.referent);
139 0 : bool first = !a;
140 :
141 0 : if (first) {
142 : // This is the first time we've reached |edge.referent|.
143 : // Mark it as visited.
144 0 : if (!visited.add(a, edge.referent, typename Handler::NodeData()))
145 0 : return false;
146 : }
147 :
148 0 : MOZ_ASSERT(a);
149 :
150 : // Report this edge to the visitor function.
151 0 : if (!handler(*this, origin, edge, &a->value(), first))
152 0 : return false;
153 :
154 0 : if (stopRequested)
155 0 : return true;
156 :
157 : // Arrange to traverse this edge's referent's outgoing edges
158 : // later --- unless |handler| asked us not to.
159 0 : if (abandonRequested) {
160 : // Skip the enqueue; reset flag for future iterations.
161 0 : abandonRequested = false;
162 0 : } else if (first) {
163 0 : if (!pending.append(edge.referent))
164 0 : return false;
165 : }
166 : }
167 : }
168 :
169 0 : return true;
170 : }
171 :
172 : // Stop traversal, and return true from |traverse| without visiting any
173 : // more nodes. Only |handler::operator()| should call this function; it
174 : // may do so to stop the traversal early, without returning false and
175 : // then making |traverse|'s caller disambiguate that result from a real
176 : // error.
177 0 : void stop() { stopRequested = true; }
178 :
179 : // Request that the current edge's referent's outgoing edges not be
180 : // traversed. This must be called the first time that referent is reached.
181 : // Other edges *to* that referent will still be traversed.
182 0 : void abandonReferent() { abandonRequested = true; }
183 :
184 : // The context with which we were constructed.
185 : JSContext* cx;
186 :
187 : // A map associating each node N that we have reached with a
188 : // Handler::NodeData, for |handler|'s use. This is public, so that
189 : // |handler| can access it to see the traversal thus far.
190 : using NodeMap = js::HashMap<Node, typename Handler::NodeData, js::DefaultHasher<Node>,
191 : js::SystemAllocPolicy>;
192 : NodeMap visited;
193 :
194 : private:
195 : // Our handler object.
196 : Handler& handler;
197 :
198 : // A queue template. Appending and popping the front are constant time.
199 : // Wasted space is never more than some recent actual population plus the
200 : // current population.
201 : template <typename T>
202 0 : class Queue {
203 : js::Vector<T, 0, js::SystemAllocPolicy> head, tail;
204 : size_t frontIndex;
205 : public:
206 0 : Queue() : head(), tail(), frontIndex(0) { }
207 0 : bool empty() { return frontIndex >= head.length(); }
208 0 : T& front() {
209 0 : MOZ_ASSERT(!empty());
210 0 : return head[frontIndex];
211 : }
212 0 : void popFront() {
213 0 : MOZ_ASSERT(!empty());
214 0 : frontIndex++;
215 0 : if (frontIndex >= head.length()) {
216 0 : head.clearAndFree();
217 0 : head.swap(tail);
218 0 : frontIndex = 0;
219 : }
220 0 : }
221 0 : bool append(const T& elt) {
222 0 : return frontIndex == 0 ? head.append(elt) : tail.append(elt);
223 : }
224 : };
225 :
226 : // A queue of nodes that we have reached, but whose outgoing edges we
227 : // have not yet traversed. Nodes reachable in fewer edges are enqueued
228 : // earlier.
229 : Queue<Node> pending;
230 :
231 : // True if our traverse function has been called.
232 : bool traversalBegun;
233 :
234 : // True if we've been asked to stop the traversal.
235 : bool stopRequested;
236 :
237 : // True if we've been asked to abandon the current edge's referent.
238 : bool abandonRequested;
239 : };
240 :
241 : } // namespace ubi
242 : } // namespace JS
243 :
244 : #endif // js_UbiNodeBreadthFirst_h
|
