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