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_UbiNodePostOrder_h
8 : #define js_UbiNodePostOrder_h
9 :
10 : #include "mozilla/Attributes.h"
11 : #include "mozilla/Maybe.h"
12 : #include "mozilla/Move.h"
13 :
14 : #include "jsalloc.h"
15 :
16 : #include "js/UbiNode.h"
17 : #include "js/Utility.h"
18 : #include "js/Vector.h"
19 :
20 : namespace JS {
21 : namespace ubi {
22 :
23 : /**
24 : * A post-order depth-first traversal of `ubi::Node` graphs.
25 : *
26 : * No GC may occur while an instance of `PostOrder` is live.
27 : *
28 : * The `NodeVisitor` type provided to `PostOrder::traverse` must have the
29 : * following member:
30 : *
31 : * bool operator()(Node& node)
32 : *
33 : * The node visitor method. This method is called once for each `node`
34 : * reachable from the start set in post-order.
35 : *
36 : * This visitor function should return true on success, or false if an error
37 : * occurs. A false return value terminates the traversal immediately, and
38 : * causes `PostOrder::traverse` to return false.
39 : *
40 : * The `EdgeVisitor` type provided to `PostOrder::traverse` must have the
41 : * following member:
42 : *
43 : * bool operator()(Node& origin, Edge& edge)
44 : *
45 : * The edge visitor method. This method is called once for each outgoing
46 : * `edge` from `origin` that is reachable from the start set.
47 : *
48 : * NB: UNLIKE NODES, THERE IS NO GUARANTEED ORDER IN WHICH EDGES AND THEIR
49 : * ORIGINS ARE VISITED!
50 : *
51 : * This visitor function should return true on success, or false if an error
52 : * occurs. A false return value terminates the traversal immediately, and
53 : * causes `PostOrder::traverse` to return false.
54 : */
55 0 : struct PostOrder {
56 : private:
57 0 : struct OriginAndEdges {
58 : Node origin;
59 : EdgeVector edges;
60 :
61 0 : OriginAndEdges(const Node& node, EdgeVector&& edges)
62 0 : : origin(node)
63 0 : , edges(mozilla::Move(edges))
64 0 : { }
65 :
66 : OriginAndEdges(const OriginAndEdges& rhs) = delete;
67 : OriginAndEdges& operator=(const OriginAndEdges& rhs) = delete;
68 :
69 0 : OriginAndEdges(OriginAndEdges&& rhs)
70 0 : : origin(rhs.origin)
71 0 : , edges(mozilla::Move(rhs.edges))
72 : {
73 0 : MOZ_ASSERT(&rhs != this, "self-move disallowed");
74 0 : }
75 :
76 : OriginAndEdges& operator=(OriginAndEdges&& rhs) {
77 : this->~OriginAndEdges();
78 : new (this) OriginAndEdges(mozilla::Move(rhs));
79 : return *this;
80 : }
81 : };
82 :
83 : using Stack = js::Vector<OriginAndEdges, 256, js::SystemAllocPolicy>;
84 : using Set = js::HashSet<Node, js::DefaultHasher<Node>, js::SystemAllocPolicy>;
85 :
86 : JSContext* cx;
87 : Set seen;
88 : Stack stack;
89 : #ifdef DEBUG
90 : bool traversed;
91 : #endif
92 :
93 : private:
94 0 : MOZ_MUST_USE bool fillEdgesFromRange(EdgeVector& edges, js::UniquePtr<EdgeRange>& range) {
95 0 : MOZ_ASSERT(range);
96 0 : for ( ; !range->empty(); range->popFront()) {
97 0 : if (!edges.append(mozilla::Move(range->front())))
98 0 : return false;
99 : }
100 0 : return true;
101 : }
102 :
103 0 : MOZ_MUST_USE bool pushForTraversing(const Node& node) {
104 0 : EdgeVector edges;
105 0 : auto range = node.edges(cx, /* wantNames */ false);
106 0 : return range &&
107 0 : fillEdgesFromRange(edges, range) &&
108 0 : stack.append(OriginAndEdges(node, mozilla::Move(edges)));
109 : }
110 :
111 :
112 : public:
113 : // Construct a post-order traversal object.
114 : //
115 : // The traversal asserts that no GC happens in its runtime during its
116 : // lifetime via the `AutoCheckCannotGC&` parameter. We do nothing with it,
117 : // other than require it to exist with a lifetime that encloses our own.
118 0 : PostOrder(JSContext* cx, AutoCheckCannotGC&)
119 0 : : cx(cx)
120 : , seen()
121 : , stack()
122 : #ifdef DEBUG
123 0 : , traversed(false)
124 : #endif
125 0 : { }
126 :
127 : // Initialize this traversal object. Return false on OOM.
128 0 : MOZ_MUST_USE bool init() { return seen.init(); }
129 :
130 : // Add `node` as a starting point for the traversal. You may add
131 : // as many starting points as you like. Returns false on OOM.
132 0 : MOZ_MUST_USE bool addStart(const Node& node) {
133 0 : if (!seen.put(node))
134 0 : return false;
135 0 : return pushForTraversing(node);
136 : }
137 :
138 : // Traverse the graph in post-order, starting with the set of nodes passed
139 : // to `addStart` and applying `onNode::operator()` for each node in the
140 : // graph and `onEdge::operator()` for each edge in the graph, as described
141 : // above.
142 : //
143 : // This should be called only once per instance of this class.
144 : //
145 : // Return false on OOM or error return from `onNode::operator()` or
146 : // `onEdge::operator()`.
147 : template<typename NodeVisitor, typename EdgeVisitor>
148 0 : MOZ_MUST_USE bool traverse(NodeVisitor onNode, EdgeVisitor onEdge) {
149 : #ifdef DEBUG
150 0 : MOZ_ASSERT(!traversed, "Can only traverse() once!");
151 0 : traversed = true;
152 : #endif
153 :
154 0 : while (!stack.empty()) {
155 0 : auto& origin = stack.back().origin;
156 0 : auto& edges = stack.back().edges;
157 :
158 0 : if (edges.empty()) {
159 0 : if (!onNode(origin))
160 0 : return false;
161 0 : stack.popBack();
162 0 : continue;
163 : }
164 :
165 0 : Edge edge = mozilla::Move(edges.back());
166 0 : edges.popBack();
167 :
168 0 : if (!onEdge(origin, edge))
169 0 : return false;
170 :
171 0 : auto ptr = seen.lookupForAdd(edge.referent);
172 : // We've already seen this node, don't follow its edges.
173 0 : if (ptr)
174 0 : continue;
175 :
176 : // Mark the referent as seen and follow its edges.
177 0 : if (!seen.add(ptr, edge.referent) ||
178 0 : !pushForTraversing(edge.referent))
179 : {
180 0 : return false;
181 : }
182 : }
183 :
184 0 : return true;
185 : }
186 : };
187 :
188 : } // namespace ubi
189 : } // namespace JS
190 :
191 : #endif // js_UbiNodePostOrder_h
|
