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/iterator_range.h"
37#include "llvm/ADT/GraphTraits.h"
38#include "llvm/ADT/PointerIntPair.h"
39#include "llvm/ADT/SmallPtrSet.h"
40#include <set>
41#include <vector>
42
43namespace llvm {
44
45// df_iterator_storage - A private class which is used to figure out where to
46// store the visited set.
47template<class SetType, bool External>   // Non-external set
48class df_iterator_storage {
49public:
50  SetType Visited;
51};
52
53template<class SetType>
54class df_iterator_storage<SetType, true> {
55public:
56  df_iterator_storage(SetType &VSet) : Visited(VSet) {}
57  df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {}
58  SetType &Visited;
59};
60
61
62// Generic Depth First Iterator
63template<class GraphT,
64class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>,
65         bool ExtStorage = false, class GT = GraphTraits<GraphT> >
66class df_iterator : public std::iterator<std::forward_iterator_tag,
67                                         typename GT::NodeType, ptrdiff_t>,
68                    public df_iterator_storage<SetType, ExtStorage> {
69  typedef std::iterator<std::forward_iterator_tag,
70                        typename GT::NodeType, ptrdiff_t> super;
71
72  typedef typename GT::NodeType          NodeType;
73  typedef typename GT::ChildIteratorType ChildItTy;
74  typedef PointerIntPair<NodeType*, 1>   PointerIntTy;
75
76  // VisitStack - Used to maintain the ordering.  Top = current block
77  // First element is node pointer, second is the 'next child' to visit
78  // if the int in PointerIntTy is 0, the 'next child' to visit is invalid
79  std::vector<std::pair<PointerIntTy, ChildItTy> > VisitStack;
80private:
81  inline df_iterator(NodeType *Node) {
82    this->Visited.insert(Node);
83    VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0),
84                                        GT::child_begin(Node)));
85  }
86  inline df_iterator() {
87    // End is when stack is empty
88  }
89  inline df_iterator(NodeType *Node, SetType &S)
90    : df_iterator_storage<SetType, ExtStorage>(S) {
91    if (!S.count(Node)) {
92      VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0),
93                                          GT::child_begin(Node)));
94      this->Visited.insert(Node);
95    }
96  }
97  inline df_iterator(SetType &S)
98    : df_iterator_storage<SetType, ExtStorage>(S) {
99    // End is when stack is empty
100  }
101
102  inline void toNext() {
103    do {
104      std::pair<PointerIntTy, ChildItTy> &Top = VisitStack.back();
105      NodeType *Node = Top.first.getPointer();
106      ChildItTy &It  = Top.second;
107      if (!Top.first.getInt()) {
108        // now retrieve the real begin of the children before we dive in
109        It = GT::child_begin(Node);
110        Top.first.setInt(1);
111      }
112
113      while (It != GT::child_end(Node)) {
114        NodeType *Next = *It++;
115        // Has our next sibling been visited?
116        if (Next && !this->Visited.count(Next)) {
117          // No, do it now.
118          this->Visited.insert(Next);
119          VisitStack.push_back(std::make_pair(PointerIntTy(Next, 0),
120                                              GT::child_begin(Next)));
121          return;
122        }
123      }
124
125      // Oops, ran out of successors... go up a level on the stack.
126      VisitStack.pop_back();
127    } while (!VisitStack.empty());
128  }
129
130public:
131  typedef typename super::pointer pointer;
132  typedef df_iterator<GraphT, SetType, ExtStorage, GT> _Self;
133
134  // Provide static begin and end methods as our public "constructors"
135  static inline _Self begin(const GraphT& G) {
136    return _Self(GT::getEntryNode(G));
137  }
138  static inline _Self end(const GraphT& G) { return _Self(); }
139
140  // Static begin and end methods as our public ctors for external iterators
141  static inline _Self begin(const GraphT& G, SetType &S) {
142    return _Self(GT::getEntryNode(G), S);
143  }
144  static inline _Self end(const GraphT& G, SetType &S) { return _Self(S); }
145
146  inline bool operator==(const _Self& x) const {
147    return VisitStack == x.VisitStack;
148  }
149  inline bool operator!=(const _Self& x) const { return !operator==(x); }
150
151  inline pointer operator*() const {
152    return VisitStack.back().first.getPointer();
153  }
154
155  // This is a nonstandard operator-> that dereferences the pointer an extra
156  // time... so that you can actually call methods ON the Node, because
157  // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
158  //
159  inline NodeType *operator->() const { return operator*(); }
160
161  inline _Self& operator++() {   // Preincrement
162    toNext();
163    return *this;
164  }
165
166  // skips all children of the current node and traverses to next node
167  //
168  inline _Self& skipChildren() {
169    VisitStack.pop_back();
170    if (!VisitStack.empty())
171      toNext();
172    return *this;
173  }
174
175  inline _Self operator++(int) { // Postincrement
176    _Self tmp = *this; ++*this; return tmp;
177  }
178
179  // nodeVisited - return true if this iterator has already visited the
180  // specified node.  This is public, and will probably be used to iterate over
181  // nodes that a depth first iteration did not find: ie unreachable nodes.
182  //
183  inline bool nodeVisited(NodeType *Node) const {
184    return this->Visited.count(Node) != 0;
185  }
186
187  /// getPathLength - Return the length of the path from the entry node to the
188  /// current node, counting both nodes.
189  unsigned getPathLength() const { return VisitStack.size(); }
190
191  /// getPath - Return the n'th node in the path from the entry node to the
192  /// current node.
193  NodeType *getPath(unsigned n) const {
194    return VisitStack[n].first.getPointer();
195  }
196};
197
198
199// Provide global constructors that automatically figure out correct types...
200//
201template <class T>
202df_iterator<T> df_begin(const T& G) {
203  return df_iterator<T>::begin(G);
204}
205
206template <class T>
207df_iterator<T> df_end(const T& G) {
208  return df_iterator<T>::end(G);
209}
210
211// Provide an accessor method to use them in range-based patterns.
212template <class T>
213iterator_range<df_iterator<T>> depth_first(const T& G) {
214  return iterator_range<df_iterator<T>>(df_begin(G), df_end(G));
215}
216
217// Provide global definitions of external depth first iterators...
218template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> >
219struct df_ext_iterator : public df_iterator<T, SetTy, true> {
220  df_ext_iterator(const df_iterator<T, SetTy, true> &V)
221    : df_iterator<T, SetTy, true>(V) {}
222};
223
224template <class T, class SetTy>
225df_ext_iterator<T, SetTy> df_ext_begin(const T& G, SetTy &S) {
226  return df_ext_iterator<T, SetTy>::begin(G, S);
227}
228
229template <class T, class SetTy>
230df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) {
231  return df_ext_iterator<T, SetTy>::end(G, S);
232}
233
234
235// Provide global definitions of inverse depth first iterators...
236template <class T,
237  class SetTy = llvm::SmallPtrSet<typename GraphTraits<T>::NodeType*, 8>,
238          bool External = false>
239struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> {
240  idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V)
241    : df_iterator<Inverse<T>, SetTy, External>(V) {}
242};
243
244template <class T>
245idf_iterator<T> idf_begin(const T& G) {
246  return idf_iterator<T>::begin(Inverse<T>(G));
247}
248
249template <class T>
250idf_iterator<T> idf_end(const T& G){
251  return idf_iterator<T>::end(Inverse<T>(G));
252}
253
254// Provide an accessor method to use them in range-based patterns.
255template <class T>
256iterator_range<idf_iterator<T>> inverse_depth_first(const T& G) {
257  return iterator_range<idf_iterator<T>>(idf_begin(G), idf_end(G));
258}
259
260// Provide global definitions of external inverse depth first iterators...
261template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> >
262struct idf_ext_iterator : public idf_iterator<T, SetTy, true> {
263  idf_ext_iterator(const idf_iterator<T, SetTy, true> &V)
264    : idf_iterator<T, SetTy, true>(V) {}
265  idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V)
266    : idf_iterator<T, SetTy, true>(V) {}
267};
268
269template <class T, class SetTy>
270idf_ext_iterator<T, SetTy> idf_ext_begin(const T& G, SetTy &S) {
271  return idf_ext_iterator<T, SetTy>::begin(Inverse<T>(G), S);
272}
273
274template <class T, class SetTy>
275idf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) {
276  return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), S);
277}
278
279} // End llvm namespace
280
281#endif
282