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 = 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 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 // 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