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 <cstddef>
14 #include <iterator>
15 
16 namespace 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.
35 template <typename DerivedT, typename IteratorCategoryT, typename T,
36           typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *,
37           typename ReferenceT = T &>
38 class iterator_facade_base
39     : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT,
40                            ReferenceT> {
41 protected:
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 
49 public:
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.
135 template <
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>>
145 class 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 
150 protected:
151   WrappedIteratorT I;
152 
153   iterator_adaptor_base() = default;
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)
I(std::forward<U &&> (u))163       : I(std::forward<U &&>(u)) {}
164 
165 public:
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
226 template <typename WrappedIteratorT,
227           typename T = typename std::remove_reference<
228               decltype(**std::declval<WrappedIteratorT>())>::type>
229 struct pointee_iterator
230     : iterator_adaptor_base<
231           pointee_iterator<WrappedIteratorT>, WrappedIteratorT,
232           typename std::iterator_traits<WrappedIteratorT>::iterator_category,
233           T> {
234   pointee_iterator() = default;
235   template <typename U>
pointee_iteratorpointee_iterator236   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