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 
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
86     : public std::iterator<std::forward_iterator_tag, typename GT::NodeRef>,
87       public df_iterator_storage<SetType, ExtStorage> {
88   using super = std::iterator<std::forward_iterator_tag, typename GT::NodeRef>;
89   using NodeRef = typename GT::NodeRef;
90   using ChildItTy = typename GT::ChildIteratorType;
91 
92   // First element is node reference, second is the 'next child' to visit.
93   // The second child is initialized lazily to pick up graph changes during the
94   // DFS.
95   using StackElement = std::pair<NodeRef, Optional<ChildItTy>>;
96 
97   // VisitStack - Used to maintain the ordering.  Top = current block
98   std::vector<StackElement> VisitStack;
99 
100 private:
101   inline df_iterator(NodeRef Node) {
102     this->Visited.insert(Node);
103     VisitStack.push_back(StackElement(Node, None));
104   }
105 
106   inline df_iterator() = default; // End is when stack is empty
107 
108   inline df_iterator(NodeRef Node, SetType &S)
109       : df_iterator_storage<SetType, ExtStorage>(S) {
110     if (this->Visited.insert(Node).second)
111       VisitStack.push_back(StackElement(Node, None));
112   }
113 
114   inline df_iterator(SetType &S)
115     : df_iterator_storage<SetType, ExtStorage>(S) {
116     // End is when stack is empty
117   }
118 
119   inline void toNext() {
120     do {
121       NodeRef Node = VisitStack.back().first;
122       Optional<ChildItTy> &Opt = VisitStack.back().second;
123 
124       if (!Opt)
125         Opt.emplace(GT::child_begin(Node));
126 
127       // Notice that we directly mutate *Opt here, so that
128       // VisitStack.back().second actually gets updated as the iterator
129       // increases.
130       while (*Opt != GT::child_end(Node)) {
131         NodeRef Next = *(*Opt)++;
132         // Has our next sibling been visited?
133         if (this->Visited.insert(Next).second) {
134           // No, do it now.
135           VisitStack.push_back(StackElement(Next, None));
136           return;
137         }
138       }
139       this->Visited.completed(Node);
140 
141       // Oops, ran out of successors... go up a level on the stack.
142       VisitStack.pop_back();
143     } while (!VisitStack.empty());
144   }
145 
146 public:
147   using pointer = typename super::pointer;
148 
149   // Provide static begin and end methods as our public "constructors"
150   static df_iterator begin(const GraphT &G) {
151     return df_iterator(GT::getEntryNode(G));
152   }
153   static df_iterator end(const GraphT &G) { return df_iterator(); }
154 
155   // Static begin and end methods as our public ctors for external iterators
156   static df_iterator begin(const GraphT &G, SetType &S) {
157     return df_iterator(GT::getEntryNode(G), S);
158   }
159   static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); }
160 
161   bool operator==(const df_iterator &x) const {
162     return VisitStack == x.VisitStack;
163   }
164   bool operator!=(const df_iterator &x) const { return !(*this == x); }
165 
166   const NodeRef &operator*() const { return VisitStack.back().first; }
167 
168   // This is a nonstandard operator-> that dereferences the pointer an extra
169   // time... so that you can actually call methods ON the Node, because
170   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
171   //
172   NodeRef operator->() const { return **this; }
173 
174   df_iterator &operator++() { // Preincrement
175     toNext();
176     return *this;
177   }
178 
179   /// Skips all children of the current node and traverses to next node
180   ///
181   /// Note: This function takes care of incrementing the iterator. If you
182   /// always increment and call this function, you risk walking off the end.
183   df_iterator &skipChildren() {
184     VisitStack.pop_back();
185     if (!VisitStack.empty())
186       toNext();
187     return *this;
188   }
189 
190   df_iterator operator++(int) { // Postincrement
191     df_iterator tmp = *this;
192     ++*this;
193     return tmp;
194   }
195 
196   // nodeVisited - return true if this iterator has already visited the
197   // specified node.  This is public, and will probably be used to iterate over
198   // nodes that a depth first iteration did not find: ie unreachable nodes.
199   //
200   bool nodeVisited(NodeRef Node) const {
201     return this->Visited.count(Node) != 0;
202   }
203 
204   /// getPathLength - Return the length of the path from the entry node to the
205   /// current node, counting both nodes.
206   unsigned getPathLength() const { return VisitStack.size(); }
207 
208   /// getPath - Return the n'th node in the path from the entry node to the
209   /// current node.
210   NodeRef getPath(unsigned n) const { return VisitStack[n].first; }
211 };
212 
213 // Provide global constructors that automatically figure out correct types...
214 //
215 template <class T>
216 df_iterator<T> df_begin(const T& G) {
217   return df_iterator<T>::begin(G);
218 }
219 
220 template <class T>
221 df_iterator<T> df_end(const T& G) {
222   return df_iterator<T>::end(G);
223 }
224 
225 // Provide an accessor method to use them in range-based patterns.
226 template <class T>
227 iterator_range<df_iterator<T>> depth_first(const T& G) {
228   return make_range(df_begin(G), df_end(G));
229 }
230 
231 // Provide global definitions of external depth first iterators...
232 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>>
233 struct df_ext_iterator : public df_iterator<T, SetTy, true> {
234   df_ext_iterator(const df_iterator<T, SetTy, true> &V)
235     : df_iterator<T, SetTy, true>(V) {}
236 };
237 
238 template <class T, class SetTy>
239 df_ext_iterator<T, SetTy> df_ext_begin(const T& G, SetTy &S) {
240   return df_ext_iterator<T, SetTy>::begin(G, S);
241 }
242 
243 template <class T, class SetTy>
244 df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) {
245   return df_ext_iterator<T, SetTy>::end(G, S);
246 }
247 
248 template <class T, class SetTy>
249 iterator_range<df_ext_iterator<T, SetTy>> depth_first_ext(const T& G,
250                                                           SetTy &S) {
251   return make_range(df_ext_begin(G, S), df_ext_end(G, S));
252 }
253 
254 // Provide global definitions of inverse depth first iterators...
255 template <class T,
256           class SetTy =
257               df_iterator_default_set<typename GraphTraits<T>::NodeRef>,
258           bool External = false>
259 struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> {
260   idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V)
261     : df_iterator<Inverse<T>, SetTy, External>(V) {}
262 };
263 
264 template <class T>
265 idf_iterator<T> idf_begin(const T& G) {
266   return idf_iterator<T>::begin(Inverse<T>(G));
267 }
268 
269 template <class T>
270 idf_iterator<T> idf_end(const T& G){
271   return idf_iterator<T>::end(Inverse<T>(G));
272 }
273 
274 // Provide an accessor method to use them in range-based patterns.
275 template <class T>
276 iterator_range<idf_iterator<T>> inverse_depth_first(const T& G) {
277   return make_range(idf_begin(G), idf_end(G));
278 }
279 
280 // Provide global definitions of external inverse depth first iterators...
281 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>>
282 struct idf_ext_iterator : public idf_iterator<T, SetTy, true> {
283   idf_ext_iterator(const idf_iterator<T, SetTy, true> &V)
284     : idf_iterator<T, SetTy, true>(V) {}
285   idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V)
286     : idf_iterator<T, SetTy, true>(V) {}
287 };
288 
289 template <class T, class SetTy>
290 idf_ext_iterator<T, SetTy> idf_ext_begin(const T& G, SetTy &S) {
291   return idf_ext_iterator<T, SetTy>::begin(Inverse<T>(G), S);
292 }
293 
294 template <class T, class SetTy>
295 idf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) {
296   return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), S);
297 }
298 
299 template <class T, class SetTy>
300 iterator_range<idf_ext_iterator<T, SetTy>> inverse_depth_first_ext(const T& G,
301                                                                    SetTy &S) {
302   return make_range(idf_ext_begin(G, S), idf_ext_end(G, S));
303 }
304 
305 } // end namespace llvm
306 
307 #endif // LLVM_ADT_DEPTHFIRSTITERATOR_H
308