1 //===- iterator.h - Utilities for using and defining iterators --*- 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 #ifndef LLVM_ADT_ITERATOR_H
10 #define LLVM_ADT_ITERATOR_H
11
12 #include "llvm/ADT/iterator_range.h"
13 #include <cstddef>
14 #include <iterator>
15 #include <type_traits>
16 #include <utility>
17
18 namespace llvm {
19
20 /// CRTP base class which implements the entire standard iterator facade
21 /// in terms of a minimal subset of the interface.
22 ///
23 /// Use this when it is reasonable to implement most of the iterator
24 /// functionality in terms of a core subset. If you need special behavior or
25 /// there are performance implications for this, you may want to override the
26 /// relevant members instead.
27 ///
28 /// Note, one abstraction that this does *not* provide is implementing
29 /// subtraction in terms of addition by negating the difference. Negation isn't
30 /// always information preserving, and I can see very reasonable iterator
31 /// designs where this doesn't work well. It doesn't really force much added
32 /// boilerplate anyways.
33 ///
34 /// Another abstraction that this doesn't provide is implementing increment in
35 /// terms of addition of one. These aren't equivalent for all iterator
36 /// categories, and respecting that adds a lot of complexity for little gain.
37 ///
38 /// Classes wishing to use `iterator_facade_base` should implement the following
39 /// methods:
40 ///
41 /// Forward Iterators:
42 /// (All of the following methods)
43 /// - DerivedT &operator=(const DerivedT &R);
44 /// - bool operator==(const DerivedT &R) const;
45 /// - const T &operator*() const;
46 /// - T &operator*();
47 /// - DerivedT &operator++();
48 ///
49 /// Bidirectional Iterators:
50 /// (All methods of forward iterators, plus the following)
51 /// - DerivedT &operator--();
52 ///
53 /// Random-access Iterators:
54 /// (All methods of bidirectional iterators excluding the following)
55 /// - DerivedT &operator++();
56 /// - DerivedT &operator--();
57 /// (and plus the following)
58 /// - bool operator<(const DerivedT &RHS) const;
59 /// - DifferenceTypeT operator-(const DerivedT &R) const;
60 /// - DerivedT &operator+=(DifferenceTypeT N);
61 /// - DerivedT &operator-=(DifferenceTypeT N);
62 ///
63 template <typename DerivedT, typename IteratorCategoryT, typename T,
64 typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *,
65 typename ReferenceT = T &>
66 class iterator_facade_base {
67 public:
68 using iterator_category = IteratorCategoryT;
69 using value_type = T;
70 using difference_type = DifferenceTypeT;
71 using pointer = PointerT;
72 using reference = ReferenceT;
73
74 protected:
75 enum {
76 IsRandomAccess = std::is_base_of<std::random_access_iterator_tag,
77 IteratorCategoryT>::value,
78 IsBidirectional = std::is_base_of<std::bidirectional_iterator_tag,
79 IteratorCategoryT>::value,
80 };
81
82 /// A proxy object for computing a reference via indirecting a copy of an
83 /// iterator. This is used in APIs which need to produce a reference via
84 /// indirection but for which the iterator object might be a temporary. The
85 /// proxy preserves the iterator internally and exposes the indirected
86 /// reference via a conversion operator.
87 class ReferenceProxy {
88 friend iterator_facade_base;
89
90 DerivedT I;
91
ReferenceProxy(DerivedT I)92 ReferenceProxy(DerivedT I) : I(std::move(I)) {}
93
94 public:
ReferenceT()95 operator ReferenceT() const { return *I; }
96 };
97
98 public:
99 DerivedT operator+(DifferenceTypeT n) const {
100 static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
101 "Must pass the derived type to this template!");
102 static_assert(
103 IsRandomAccess,
104 "The '+' operator is only defined for random access iterators.");
105 DerivedT tmp = *static_cast<const DerivedT *>(this);
106 tmp += n;
107 return tmp;
108 }
109 friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) {
110 static_assert(
111 IsRandomAccess,
112 "The '+' operator is only defined for random access iterators.");
113 return i + n;
114 }
115 DerivedT operator-(DifferenceTypeT n) const {
116 static_assert(
117 IsRandomAccess,
118 "The '-' operator is only defined for random access iterators.");
119 DerivedT tmp = *static_cast<const DerivedT *>(this);
120 tmp -= n;
121 return tmp;
122 }
123
124 DerivedT &operator++() {
125 static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
126 "Must pass the derived type to this template!");
127 return static_cast<DerivedT *>(this)->operator+=(1);
128 }
129 DerivedT operator++(int) {
130 DerivedT tmp = *static_cast<DerivedT *>(this);
131 ++*static_cast<DerivedT *>(this);
132 return tmp;
133 }
134 DerivedT &operator--() {
135 static_assert(
136 IsBidirectional,
137 "The decrement operator is only defined for bidirectional iterators.");
138 return static_cast<DerivedT *>(this)->operator-=(1);
139 }
140 DerivedT operator--(int) {
141 static_assert(
142 IsBidirectional,
143 "The decrement operator is only defined for bidirectional iterators.");
144 DerivedT tmp = *static_cast<DerivedT *>(this);
145 --*static_cast<DerivedT *>(this);
146 return tmp;
147 }
148
149 #ifndef __cpp_impl_three_way_comparison
150 bool operator!=(const DerivedT &RHS) const {
151 return !(static_cast<const DerivedT &>(*this) == RHS);
152 }
153 #endif
154
155 bool operator>(const DerivedT &RHS) const {
156 static_assert(
157 IsRandomAccess,
158 "Relational operators are only defined for random access iterators.");
159 return !(static_cast<const DerivedT &>(*this) < RHS) &&
160 !(static_cast<const DerivedT &>(*this) == RHS);
161 }
162 bool operator<=(const DerivedT &RHS) const {
163 static_assert(
164 IsRandomAccess,
165 "Relational operators are only defined for random access iterators.");
166 return !(static_cast<const DerivedT &>(*this) > RHS);
167 }
168 bool operator>=(const DerivedT &RHS) const {
169 static_assert(
170 IsRandomAccess,
171 "Relational operators are only defined for random access iterators.");
172 return !(static_cast<const DerivedT &>(*this) < RHS);
173 }
174
175 PointerT operator->() { return &static_cast<DerivedT *>(this)->operator*(); }
176 PointerT operator->() const {
177 return &static_cast<const DerivedT *>(this)->operator*();
178 }
179 ReferenceProxy operator[](DifferenceTypeT n) {
180 static_assert(IsRandomAccess,
181 "Subscripting is only defined for random access iterators.");
182 return ReferenceProxy(static_cast<DerivedT *>(this)->operator+(n));
183 }
184 ReferenceProxy operator[](DifferenceTypeT n) const {
185 static_assert(IsRandomAccess,
186 "Subscripting is only defined for random access iterators.");
187 return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n));
188 }
189 };
190
191 /// CRTP base class for adapting an iterator to a different type.
192 ///
193 /// This class can be used through CRTP to adapt one iterator into another.
194 /// Typically this is done through providing in the derived class a custom \c
195 /// operator* implementation. Other methods can be overridden as well.
196 template <
197 typename DerivedT, typename WrappedIteratorT,
198 typename IteratorCategoryT =
199 typename std::iterator_traits<WrappedIteratorT>::iterator_category,
200 typename T = typename std::iterator_traits<WrappedIteratorT>::value_type,
201 typename DifferenceTypeT =
202 typename std::iterator_traits<WrappedIteratorT>::difference_type,
203 typename PointerT = std::conditional_t<
204 std::is_same<T, typename std::iterator_traits<
205 WrappedIteratorT>::value_type>::value,
206 typename std::iterator_traits<WrappedIteratorT>::pointer, T *>,
207 typename ReferenceT = std::conditional_t<
208 std::is_same<T, typename std::iterator_traits<
209 WrappedIteratorT>::value_type>::value,
210 typename std::iterator_traits<WrappedIteratorT>::reference, T &>>
211 class iterator_adaptor_base
212 : public iterator_facade_base<DerivedT, IteratorCategoryT, T,
213 DifferenceTypeT, PointerT, ReferenceT> {
214 using BaseT = typename iterator_adaptor_base::iterator_facade_base;
215
216 protected:
217 WrappedIteratorT I;
218
219 iterator_adaptor_base() = default;
220
iterator_adaptor_base(WrappedIteratorT u)221 explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) {
222 static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value,
223 "Must pass the derived type to this template!");
224 }
225
wrapped()226 const WrappedIteratorT &wrapped() const { return I; }
227
228 public:
229 using difference_type = DifferenceTypeT;
230
231 DerivedT &operator+=(difference_type n) {
232 static_assert(
233 BaseT::IsRandomAccess,
234 "The '+=' operator is only defined for random access iterators.");
235 I += n;
236 return *static_cast<DerivedT *>(this);
237 }
238 DerivedT &operator-=(difference_type n) {
239 static_assert(
240 BaseT::IsRandomAccess,
241 "The '-=' operator is only defined for random access iterators.");
242 I -= n;
243 return *static_cast<DerivedT *>(this);
244 }
245 using BaseT::operator-;
246 difference_type operator-(const DerivedT &RHS) const {
247 static_assert(
248 BaseT::IsRandomAccess,
249 "The '-' operator is only defined for random access iterators.");
250 return I - RHS.I;
251 }
252
253 // We have to explicitly provide ++ and -- rather than letting the facade
254 // forward to += because WrappedIteratorT might not support +=.
255 using BaseT::operator++;
256 DerivedT &operator++() {
257 ++I;
258 return *static_cast<DerivedT *>(this);
259 }
260 using BaseT::operator--;
261 DerivedT &operator--() {
262 static_assert(
263 BaseT::IsBidirectional,
264 "The decrement operator is only defined for bidirectional iterators.");
265 --I;
266 return *static_cast<DerivedT *>(this);
267 }
268
269 friend bool operator==(const iterator_adaptor_base &LHS,
270 const iterator_adaptor_base &RHS) {
271 return LHS.I == RHS.I;
272 }
273 friend bool operator<(const iterator_adaptor_base &LHS,
274 const iterator_adaptor_base &RHS) {
275 static_assert(
276 BaseT::IsRandomAccess,
277 "Relational operators are only defined for random access iterators.");
278 return LHS.I < RHS.I;
279 }
280
281 ReferenceT operator*() const { return *I; }
282 };
283
284 /// An iterator type that allows iterating over the pointees via some
285 /// other iterator.
286 ///
287 /// The typical usage of this is to expose a type that iterates over Ts, but
288 /// which is implemented with some iterator over T*s:
289 ///
290 /// \code
291 /// using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>;
292 /// \endcode
293 template <typename WrappedIteratorT,
294 typename T = std::remove_reference_t<decltype(
295 **std::declval<WrappedIteratorT>())>>
296 struct pointee_iterator
297 : iterator_adaptor_base<
298 pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT,
299 typename std::iterator_traits<WrappedIteratorT>::iterator_category,
300 T> {
301 pointee_iterator() = default;
302 template <typename U>
pointee_iteratorpointee_iterator303 pointee_iterator(U &&u)
304 : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
305
306 T &operator*() const { return **this->I; }
307 };
308
309 template <typename RangeT, typename WrappedIteratorT =
310 decltype(std::begin(std::declval<RangeT>()))>
311 iterator_range<pointee_iterator<WrappedIteratorT>>
make_pointee_range(RangeT && Range)312 make_pointee_range(RangeT &&Range) {
313 using PointeeIteratorT = pointee_iterator<WrappedIteratorT>;
314 return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))),
315 PointeeIteratorT(std::end(std::forward<RangeT>(Range))));
316 }
317
318 template <typename WrappedIteratorT,
319 typename T = decltype(&*std::declval<WrappedIteratorT>())>
320 class pointer_iterator
321 : public iterator_adaptor_base<
322 pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT,
323 typename std::iterator_traits<WrappedIteratorT>::iterator_category,
324 T> {
325 mutable T Ptr;
326
327 public:
328 pointer_iterator() = default;
329
pointer_iterator(WrappedIteratorT u)330 explicit pointer_iterator(WrappedIteratorT u)
331 : pointer_iterator::iterator_adaptor_base(std::move(u)) {}
332
333 T &operator*() { return Ptr = &*this->I; }
334 const T &operator*() const { return Ptr = &*this->I; }
335 };
336
337 template <typename RangeT, typename WrappedIteratorT =
338 decltype(std::begin(std::declval<RangeT>()))>
339 iterator_range<pointer_iterator<WrappedIteratorT>>
make_pointer_range(RangeT && Range)340 make_pointer_range(RangeT &&Range) {
341 using PointerIteratorT = pointer_iterator<WrappedIteratorT>;
342 return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))),
343 PointerIteratorT(std::end(std::forward<RangeT>(Range))));
344 }
345
346 template <typename WrappedIteratorT,
347 typename T1 = std::remove_reference_t<decltype(
348 **std::declval<WrappedIteratorT>())>,
349 typename T2 = std::add_pointer_t<T1>>
350 using raw_pointer_iterator =
351 pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>;
352
353 } // end namespace llvm
354
355 #endif // LLVM_ADT_ITERATOR_H
356