1//===- iterator.h - Utilities for using and defining iterators --*- 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#ifndef LLVM_ADT_ITERATOR_H
11#define LLVM_ADT_ITERATOR_H
12
13#include <iterator>
14#include <cstddef>
15
16namespace llvm {
17
18/// \brief CRTP base class which implements the entire standard iterator facade
19/// in terms of a minimal subset of the interface.
20///
21/// Use this when it is reasonable to implement most of the iterator
22/// functionality in terms of a core subset. If you need special behavior or
23/// there are performance implications for this, you may want to override the
24/// relevant members instead.
25///
26/// Note, one abstraction that this does *not* provide is implementing
27/// subtraction in terms of addition by negating the difference. Negation isn't
28/// always information preserving, and I can see very reasonable iterator
29/// designs where this doesn't work well. It doesn't really force much added
30/// boilerplate anyways.
31///
32/// Another abstraction that this doesn't provide is implementing increment in
33/// terms of addition of one. These aren't equivalent for all iterator
34/// categories, and respecting that adds a lot of complexity for little gain.
35template <typename DerivedT, typename IteratorCategoryT, typename T,
36          typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *,
37          typename ReferenceT = T &>
38class iterator_facade_base
39    : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT,
40                           ReferenceT> {
41protected:
42  enum {
43    IsRandomAccess =
44        std::is_base_of<std::random_access_iterator_tag, IteratorCategoryT>::value,
45    IsBidirectional =
46        std::is_base_of<std::bidirectional_iterator_tag, IteratorCategoryT>::value,
47  };
48
49public:
50  DerivedT operator+(DifferenceTypeT n) const {
51    static_assert(
52        IsRandomAccess,
53        "The '+' operator is only defined for random access iterators.");
54    DerivedT tmp = *static_cast<const DerivedT *>(this);
55    tmp += n;
56    return tmp;
57  }
58  friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) {
59    static_assert(
60        IsRandomAccess,
61        "The '+' operator is only defined for random access iterators.");
62    return i + n;
63  }
64  DerivedT operator-(DifferenceTypeT n) const {
65    static_assert(
66        IsRandomAccess,
67        "The '-' operator is only defined for random access iterators.");
68    DerivedT tmp = *static_cast<const DerivedT *>(this);
69    tmp -= n;
70    return tmp;
71  }
72
73  DerivedT &operator++() {
74    return static_cast<DerivedT *>(this)->operator+=(1);
75  }
76  DerivedT operator++(int) {
77    DerivedT tmp = *static_cast<DerivedT *>(this);
78    ++*static_cast<DerivedT *>(this);
79    return tmp;
80  }
81  DerivedT &operator--() {
82    static_assert(
83        IsBidirectional,
84        "The decrement operator is only defined for bidirectional iterators.");
85    return static_cast<DerivedT *>(this)->operator-=(1);
86  }
87  DerivedT operator--(int) {
88    static_assert(
89        IsBidirectional,
90        "The decrement operator is only defined for bidirectional iterators.");
91    DerivedT tmp = *static_cast<DerivedT *>(this);
92    --*static_cast<DerivedT *>(this);
93    return tmp;
94  }
95
96  bool operator!=(const DerivedT &RHS) const {
97    return !static_cast<const DerivedT *>(this)->operator==(RHS);
98  }
99
100  bool operator>(const DerivedT &RHS) const {
101    static_assert(
102        IsRandomAccess,
103        "Relational operators are only defined for random access iterators.");
104    return !static_cast<const DerivedT *>(this)->operator<(RHS) &&
105           !static_cast<const DerivedT *>(this)->operator==(RHS);
106  }
107  bool operator<=(const DerivedT &RHS) const {
108    static_assert(
109        IsRandomAccess,
110        "Relational operators are only defined for random access iterators.");
111    return !static_cast<const DerivedT *>(this)->operator>(RHS);
112  }
113  bool operator>=(const DerivedT &RHS) const {
114    static_assert(
115        IsRandomAccess,
116        "Relational operators are only defined for random access iterators.");
117    return !static_cast<const DerivedT *>(this)->operator<(RHS);
118  }
119
120  PointerT operator->() const {
121    return &static_cast<const DerivedT *>(this)->operator*();
122  }
123  ReferenceT operator[](DifferenceTypeT n) const {
124    static_assert(IsRandomAccess,
125                  "Subscripting is only defined for random access iterators.");
126    return *static_cast<const DerivedT *>(this)->operator+(n);
127  }
128};
129
130/// \brief CRTP base class for adapting an iterator to a different type.
131///
132/// This class can be used through CRTP to adapt one iterator into another.
133/// Typically this is done through providing in the derived class a custom \c
134/// operator* implementation. Other methods can be overridden as well.
135template <
136    typename DerivedT, typename WrappedIteratorT,
137    typename IteratorCategoryT =
138        typename std::iterator_traits<WrappedIteratorT>::iterator_category,
139    typename T = typename std::iterator_traits<WrappedIteratorT>::value_type,
140    typename DifferenceTypeT =
141        typename std::iterator_traits<WrappedIteratorT>::difference_type,
142    typename PointerT = T *, typename ReferenceT = T &,
143    // Don't provide these, they are mostly to act as aliases below.
144    typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>>
145class iterator_adaptor_base
146    : public iterator_facade_base<DerivedT, IteratorCategoryT, T,
147                                  DifferenceTypeT, PointerT, ReferenceT> {
148  typedef typename iterator_adaptor_base::iterator_facade_base BaseT;
149
150protected:
151  WrappedIteratorT I;
152
153  iterator_adaptor_base() {}
154
155  template <typename U>
156  explicit iterator_adaptor_base(
157      U &&u,
158      typename std::enable_if<
159          !std::is_base_of<typename std::remove_cv<
160                               typename std::remove_reference<U>::type>::type,
161                           DerivedT>::value,
162          int>::type = 0)
163      : I(std::forward<U &&>(u)) {}
164
165public:
166  typedef DifferenceTypeT difference_type;
167
168  DerivedT &operator+=(difference_type n) {
169    static_assert(
170        BaseT::IsRandomAccess,
171        "The '+=' operator is only defined for random access iterators.");
172    I += n;
173    return *static_cast<DerivedT *>(this);
174  }
175  DerivedT &operator-=(difference_type n) {
176    static_assert(
177        BaseT::IsRandomAccess,
178        "The '-=' operator is only defined for random access iterators.");
179    I -= n;
180    return *static_cast<DerivedT *>(this);
181  }
182  using BaseT::operator-;
183  difference_type operator-(const DerivedT &RHS) const {
184    static_assert(
185        BaseT::IsRandomAccess,
186        "The '-' operator is only defined for random access iterators.");
187    return I - RHS.I;
188  }
189
190  // We have to explicitly provide ++ and -- rather than letting the facade
191  // forward to += because WrappedIteratorT might not support +=.
192  using BaseT::operator++;
193  DerivedT &operator++() {
194    ++I;
195    return *static_cast<DerivedT *>(this);
196  }
197  using BaseT::operator--;
198  DerivedT &operator--() {
199    static_assert(
200        BaseT::IsBidirectional,
201        "The decrement operator is only defined for bidirectional iterators.");
202    --I;
203    return *static_cast<DerivedT *>(this);
204  }
205
206  bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
207  bool operator<(const DerivedT &RHS) const {
208    static_assert(
209        BaseT::IsRandomAccess,
210        "Relational operators are only defined for random access iterators.");
211    return I < RHS.I;
212  }
213
214  ReferenceT operator*() const { return *I; }
215};
216
217/// \brief An iterator type that allows iterating over the pointees via some
218/// other iterator.
219///
220/// The typical usage of this is to expose a type that iterates over Ts, but
221/// which is implemented with some iterator over T*s:
222///
223/// \code
224///   typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator;
225/// \endcode
226template <typename WrappedIteratorT,
227          typename T = typename std::remove_reference<
228              decltype(**std::declval<WrappedIteratorT>())>::type>
229struct pointee_iterator
230    : iterator_adaptor_base<
231          pointee_iterator<WrappedIteratorT>, WrappedIteratorT,
232          typename std::iterator_traits<WrappedIteratorT>::iterator_category,
233          T> {
234  pointee_iterator() {}
235  template <typename U>
236  pointee_iterator(U &&u)
237      : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
238
239  T &operator*() const { return **this->I; }
240};
241
242}
243
244#endif
245