include/llvm/ADT/DepthFirstIterator.h

   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