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// This file builds on the ADT/GraphTraits.h file to build generic depth
10// first graph iterator. This file exposes the following functions/types:
11//
12// df_begin/df_end/df_iterator
13// * Normal depth-first iteration - visit a node and then all of its children.
14//
15// idf_begin/idf_end/idf_iterator
16// * Depth-first iteration on the 'inverse' graph.
17//
18// df_ext_begin/df_ext_end/df_ext_iterator
19// * Normal depth-first iteration - visit a node and then all of its children.
20// This iterator stores the 'visited' set in an external set, which allows
21// it to be more efficient, and allows external clients to use the set for
22// other purposes.
23//
24// idf_ext_begin/idf_ext_end/idf_ext_iterator
25// * Depth-first iteration on the 'inverse' graph.
26// This iterator stores the 'visited' set in an external set, which allows
27// it to be more efficient, and allows external clients to use the set for
28// other purposes.
29//
30//===----------------------------------------------------------------------===//
31
32#ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H
33#define LLVM_ADT_DEPTHFIRSTITERATOR_H
34
35#include "llvm/ADT/GraphTraits.h"
36#include "llvm/ADT/None.h"
37#include "llvm/ADT/Optional.h"
38#include "llvm/ADT/SmallPtrSet.h"
39#include "llvm/ADT/iterator_range.h"
40#include <iterator>
41#include <set>
42#include <utility>
43#include <vector>
44
45namespace llvm {
46
47// df_iterator_storage - A private class which is used to figure out where to
48// store the visited set.
49template<class SetType, bool External> // Non-external set
50class df_iterator_storage {
51public:
52 SetType Visited;
53};
54
55template<class SetType>
56class df_iterator_storage<SetType, true> {
57public:
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.
68template <typename NodeRef, unsigned SmallSize=8>
69struct 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
81template <class GraphT,
82 class SetType =
83 df_iterator_default_set<typename GraphTraits<GraphT>::NodeRef>,
84 bool ExtStorage = false, class GT = GraphTraits<GraphT>>
85class df_iterator : public df_iterator_storage<SetType, ExtStorage> {
86public:
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 = value_type &;
92
93private:
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, 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, None));
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, None));
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 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, None));
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
150public:
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 const NodeRef &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//
217template <class T>
218df_iterator<T> df_begin(const T& G) {
219 return df_iterator<T>::begin(G);
220}
221
222template <class T>
223df_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.
228template <class T>
229iterator_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...
234template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>>
235struct 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
240template <class T, class SetTy>
241df_ext_iterator<T, SetTy> df_ext_begin(const T& G, SetTy &S) {
242 return df_ext_iterator<T, SetTy>::begin(G, S);
243}
244
245template <class T, class SetTy>
246df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) {
247 return df_ext_iterator<T, SetTy>::end(G, S);
248}
249
250template <class T, class SetTy>
251iterator_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...
257template <class T,
258 class SetTy =
259 df_iterator_default_set<typename GraphTraits<T>::NodeRef>,
260 bool External = false>
261struct 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
266template <class T>
267idf_iterator<T> idf_begin(const T& G) {
268 return idf_iterator<T>::begin(Inverse<T>(G));
269}
270
271template <class T>
272idf_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.
277template <class T>
278iterator_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...
283template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>>
284struct 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
291template <class T, class SetTy>
292idf_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
296template <class T, class SetTy>
297idf_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
301template <class T, class SetTy>
302iterator_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