contrib/llvm/include/llvm/ADT/DepthFirstIterator.h

   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