1 | //===- llvm/ADT/DepthFirstIterator.h - Depth First iterator -----*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | /// |
9 | /// \file |
10 | /// This file builds on the ADT/GraphTraits.h file to build generic depth |
11 | /// first graph iterator. This file exposes the following functions/types: |
12 | /// |
13 | /// df_begin/df_end/df_iterator |
14 | /// * Normal depth-first iteration - visit a node and then all of its |
15 | /// children. |
16 | /// |
17 | /// idf_begin/idf_end/idf_iterator |
18 | /// * Depth-first iteration on the 'inverse' graph. |
19 | /// |
20 | /// df_ext_begin/df_ext_end/df_ext_iterator |
21 | /// * Normal depth-first iteration - visit a node and then all of its |
22 | /// children. This iterator stores the 'visited' set in an external set, |
23 | /// which allows it to be more efficient, and allows external clients to |
24 | /// use the set for other purposes. |
25 | /// |
26 | /// idf_ext_begin/idf_ext_end/idf_ext_iterator |
27 | /// * Depth-first iteration on the 'inverse' graph. |
28 | /// This iterator stores the 'visited' set in an external set, which |
29 | /// allows it to be more efficient, and allows external clients to use |
30 | /// the set for other purposes. |
31 | /// |
32 | //===----------------------------------------------------------------------===// |
33 | |
34 | #ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H |
35 | #define LLVM_ADT_DEPTHFIRSTITERATOR_H |
36 | |
37 | #include "llvm/ADT/GraphTraits.h" |
38 | #include "llvm/ADT/SmallPtrSet.h" |
39 | #include "llvm/ADT/iterator_range.h" |
40 | #include <iterator> |
41 | #include <optional> |
42 | #include <utility> |
43 | #include <vector> |
44 | |
45 | namespace llvm { |
46 | |
47 | // df_iterator_storage - A private class which is used to figure out where to |
48 | // store the visited set. |
49 | template<class SetType, bool External> // Non-external set |
50 | class df_iterator_storage { |
51 | public: |
52 | SetType Visited; |
53 | }; |
54 | |
55 | template<class SetType> |
56 | class df_iterator_storage<SetType, true> { |
57 | public: |
58 | df_iterator_storage(SetType &VSet) : Visited(VSet) {} |
59 | df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {} |
60 | |
61 | SetType &Visited; |
62 | }; |
63 | |
64 | // The visited stated for the iteration is a simple set augmented with |
65 | // one more method, completed, which is invoked when all children of a |
66 | // node have been processed. It is intended to distinguish of back and |
67 | // cross edges in the spanning tree but is not used in the common case. |
68 | template <typename NodeRef, unsigned SmallSize=8> |
69 | struct df_iterator_default_set : public SmallPtrSet<NodeRef, SmallSize> { |
70 | using BaseSet = SmallPtrSet<NodeRef, SmallSize>; |
71 | using iterator = typename BaseSet::iterator; |
72 | |
73 | std::pair<iterator,bool> insert(NodeRef N) { return BaseSet::insert(N); } |
74 | template <typename IterT> |
75 | void insert(IterT Begin, IterT End) { BaseSet::insert(Begin,End); } |
76 | |
77 | void completed(NodeRef) {} |
78 | }; |
79 | |
80 | // Generic Depth First Iterator |
81 | template <class GraphT, |
82 | class SetType = |
83 | df_iterator_default_set<typename GraphTraits<GraphT>::NodeRef>, |
84 | bool ExtStorage = false, class GT = GraphTraits<GraphT>> |
85 | class df_iterator : public df_iterator_storage<SetType, ExtStorage> { |
86 | public: |
87 | using iterator_category = std::forward_iterator_tag; |
88 | using value_type = typename GT::NodeRef; |
89 | using difference_type = std::ptrdiff_t; |
90 | using pointer = value_type *; |
91 | using reference = const value_type &; |
92 | |
93 | private: |
94 | using NodeRef = typename GT::NodeRef; |
95 | using ChildItTy = typename GT::ChildIteratorType; |
96 | |
97 | // First element is node reference, second is the 'next child' to visit. |
98 | // The second child is initialized lazily to pick up graph changes during the |
99 | // DFS. |
100 | using StackElement = std::pair<NodeRef, std::optional<ChildItTy>>; |
101 | |
102 | // VisitStack - Used to maintain the ordering. Top = current block |
103 | std::vector<StackElement> VisitStack; |
104 | |
105 | inline df_iterator(NodeRef Node) { |
106 | this->Visited.insert(Node); |
107 | VisitStack.push_back(StackElement(Node, std::nullopt)); |
108 | } |
109 | |
110 | inline df_iterator() = default; // End is when stack is empty |
111 | |
112 | inline df_iterator(NodeRef Node, SetType &S) |
113 | : df_iterator_storage<SetType, ExtStorage>(S) { |
114 | if (this->Visited.insert(Node).second) |
115 | VisitStack.push_back(StackElement(Node, std::nullopt)); |
116 | } |
117 | |
118 | inline df_iterator(SetType &S) |
119 | : df_iterator_storage<SetType, ExtStorage>(S) { |
120 | // End is when stack is empty |
121 | } |
122 | |
123 | inline void toNext() { |
124 | do { |
125 | NodeRef Node = VisitStack.back().first; |
126 | std::optional<ChildItTy> &Opt = VisitStack.back().second; |
127 | |
128 | if (!Opt) |
129 | Opt.emplace(GT::child_begin(Node)); |
130 | |
131 | // Notice that we directly mutate *Opt here, so that |
132 | // VisitStack.back().second actually gets updated as the iterator |
133 | // increases. |
134 | while (*Opt != GT::child_end(Node)) { |
135 | NodeRef Next = *(*Opt)++; |
136 | // Has our next sibling been visited? |
137 | if (this->Visited.insert(Next).second) { |
138 | // No, do it now. |
139 | VisitStack.push_back(StackElement(Next, std::nullopt)); |
140 | return; |
141 | } |
142 | } |
143 | this->Visited.completed(Node); |
144 | |
145 | // Oops, ran out of successors... go up a level on the stack. |
146 | VisitStack.pop_back(); |
147 | } while (!VisitStack.empty()); |
148 | } |
149 | |
150 | public: |
151 | // Provide static begin and end methods as our public "constructors" |
152 | static df_iterator begin(const GraphT &G) { |
153 | return df_iterator(GT::getEntryNode(G)); |
154 | } |
155 | static df_iterator end(const GraphT &G) { return df_iterator(); } |
156 | |
157 | // Static begin and end methods as our public ctors for external iterators |
158 | static df_iterator begin(const GraphT &G, SetType &S) { |
159 | return df_iterator(GT::getEntryNode(G), S); |
160 | } |
161 | static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); } |
162 | |
163 | bool operator==(const df_iterator &x) const { |
164 | return VisitStack == x.VisitStack; |
165 | } |
166 | bool operator!=(const df_iterator &x) const { return !(*this == x); } |
167 | |
168 | reference operator*() const { return VisitStack.back().first; } |
169 | |
170 | // This is a nonstandard operator-> that dereferences the pointer an extra |
171 | // time... so that you can actually call methods ON the Node, because |
172 | // the contained type is a pointer. This allows BBIt->getTerminator() f.e. |
173 | // |
174 | NodeRef operator->() const { return **this; } |
175 | |
176 | df_iterator &operator++() { // Preincrement |
177 | toNext(); |
178 | return *this; |
179 | } |
180 | |
181 | /// Skips all children of the current node and traverses to next node |
182 | /// |
183 | /// Note: This function takes care of incrementing the iterator. If you |
184 | /// always increment and call this function, you risk walking off the end. |
185 | df_iterator &skipChildren() { |
186 | VisitStack.pop_back(); |
187 | if (!VisitStack.empty()) |
188 | toNext(); |
189 | return *this; |
190 | } |
191 | |
192 | df_iterator operator++(int) { // Postincrement |
193 | df_iterator tmp = *this; |
194 | ++*this; |
195 | return tmp; |
196 | } |
197 | |
198 | // nodeVisited - return true if this iterator has already visited the |
199 | // specified node. This is public, and will probably be used to iterate over |
200 | // nodes that a depth first iteration did not find: ie unreachable nodes. |
201 | // |
202 | bool nodeVisited(NodeRef Node) const { |
203 | return this->Visited.contains(Node); |
204 | } |
205 | |
206 | /// getPathLength - Return the length of the path from the entry node to the |
207 | /// current node, counting both nodes. |
208 | unsigned getPathLength() const { return VisitStack.size(); } |
209 | |
210 | /// getPath - Return the n'th node in the path from the entry node to the |
211 | /// current node. |
212 | NodeRef getPath(unsigned n) const { return VisitStack[n].first; } |
213 | }; |
214 | |
215 | // Provide global constructors that automatically figure out correct types... |
216 | // |
217 | template <class T> |
218 | df_iterator<T> df_begin(const T& G) { |
219 | return df_iterator<T>::begin(G); |
220 | } |
221 | |
222 | template <class T> |
223 | df_iterator<T> df_end(const T& G) { |
224 | return df_iterator<T>::end(G); |
225 | } |
226 | |
227 | // Provide an accessor method to use them in range-based patterns. |
228 | template <class T> |
229 | iterator_range<df_iterator<T>> depth_first(const T& G) { |
230 | return make_range(df_begin(G), df_end(G)); |
231 | } |
232 | |
233 | // Provide global definitions of external depth first iterators... |
234 | template <class T, class SetTy = df_iterator_default_set<typename GraphTraits<T>::NodeRef>> |
235 | struct df_ext_iterator : public df_iterator<T, SetTy, true> { |
236 | df_ext_iterator(const df_iterator<T, SetTy, true> &V) |
237 | : df_iterator<T, SetTy, true>(V) {} |
238 | }; |
239 | |
240 | template <class T, class SetTy> |
241 | df_ext_iterator<T, SetTy> df_ext_begin(const T& G, SetTy &S) { |
242 | return df_ext_iterator<T, SetTy>::begin(G, S); |
243 | } |
244 | |
245 | template <class T, class SetTy> |
246 | df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) { |
247 | return df_ext_iterator<T, SetTy>::end(G, S); |
248 | } |
249 | |
250 | template <class T, class SetTy> |
251 | iterator_range<df_ext_iterator<T, SetTy>> depth_first_ext(const T& G, |
252 | SetTy &S) { |
253 | return make_range(df_ext_begin(G, S), df_ext_end(G, S)); |
254 | } |
255 | |
256 | // Provide global definitions of inverse depth first iterators... |
257 | template <class T, |
258 | class SetTy = |
259 | df_iterator_default_set<typename GraphTraits<T>::NodeRef>, |
260 | bool External = false> |
261 | struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> { |
262 | idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V) |
263 | : df_iterator<Inverse<T>, SetTy, External>(V) {} |
264 | }; |
265 | |
266 | template <class T> |
267 | idf_iterator<T> idf_begin(const T& G) { |
268 | return idf_iterator<T>::begin(Inverse<T>(G)); |
269 | } |
270 | |
271 | template <class T> |
272 | idf_iterator<T> idf_end(const T& G){ |
273 | return idf_iterator<T>::end(Inverse<T>(G)); |
274 | } |
275 | |
276 | // Provide an accessor method to use them in range-based patterns. |
277 | template <class T> |
278 | iterator_range<idf_iterator<T>> inverse_depth_first(const T& G) { |
279 | return make_range(idf_begin(G), idf_end(G)); |
280 | } |
281 | |
282 | // Provide global definitions of external inverse depth first iterators... |
283 | template <class T, class SetTy = df_iterator_default_set<typename GraphTraits<T>::NodeRef>> |
284 | struct idf_ext_iterator : public idf_iterator<T, SetTy, true> { |
285 | idf_ext_iterator(const idf_iterator<T, SetTy, true> &V) |
286 | : idf_iterator<T, SetTy, true>(V) {} |
287 | idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V) |
288 | : idf_iterator<T, SetTy, true>(V) {} |
289 | }; |
290 | |
291 | template <class T, class SetTy> |
292 | idf_ext_iterator<T, SetTy> idf_ext_begin(const T& G, SetTy &S) { |
293 | return idf_ext_iterator<T, SetTy>::begin(Inverse<T>(G), S); |
294 | } |
295 | |
296 | template <class T, class SetTy> |
297 | idf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) { |
298 | return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), S); |
299 | } |
300 | |
301 | template <class T, class SetTy> |
302 | iterator_range<idf_ext_iterator<T, SetTy>> inverse_depth_first_ext(const T& G, |
303 | SetTy &S) { |
304 | return make_range(idf_ext_begin(G, S), idf_ext_end(G, S)); |
305 | } |
306 | |
307 | } // end namespace llvm |
308 | |
309 | #endif // LLVM_ADT_DEPTHFIRSTITERATOR_H |
310 | |