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
18namespace 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/// Iterators are expected to have const rules analogous to pointers, with a
39/// single, const-qualified operator*() that returns ReferenceT. This matches
40/// the second and third pointers in the following example:
41/// \code
42/// int Value;
43/// { int *I = &Value; } // ReferenceT 'int&'
44/// { int *const I = &Value; } // ReferenceT 'int&'; const
45/// { const int *I = &Value; } // ReferenceT 'const int&'
46/// { const int *const I = &Value; } // ReferenceT 'const int&'; const
47/// \endcode
48/// If an iterator facade returns a handle to its own state, then T (and
49/// PointerT and ReferenceT) should usually be const-qualified. Otherwise, if
50/// clients are expected to modify the handle itself, the field can be declared
51/// mutable or use const_cast.
52///
53/// Classes wishing to use `iterator_facade_base` should implement the following
54/// methods:
55///
56/// Forward Iterators:
57/// (All of the following methods)
58/// - DerivedT &operator=(const DerivedT &R);
59/// - bool operator==(const DerivedT &R) const;
60/// - T &operator*() const;
61/// - DerivedT &operator++();
62///
63/// Bidirectional Iterators:
64/// (All methods of forward iterators, plus the following)
65/// - DerivedT &operator--();
66///
67/// Random-access Iterators:
68/// (All methods of bidirectional iterators excluding the following)
69/// - DerivedT &operator++();
70/// - DerivedT &operator--();
71/// (and plus the following)
72/// - bool operator<(const DerivedT &RHS) const;
73/// - DifferenceTypeT operator-(const DerivedT &R) const;
74/// - DerivedT &operator+=(DifferenceTypeT N);
75/// - DerivedT &operator-=(DifferenceTypeT N);
76///
77template <typename DerivedT, typename IteratorCategoryT, typename T,
78 typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *,
79 typename ReferenceT = T &>
80class iterator_facade_base {
81public:
82 using iterator_category = IteratorCategoryT;
83 using value_type = T;
84 using difference_type = DifferenceTypeT;
85 using pointer = PointerT;
86 using reference = ReferenceT;
87
88protected:
89 enum {
90 IsRandomAccess = std::is_base_of<std::random_access_iterator_tag,
91 IteratorCategoryT>::value,
92 IsBidirectional = std::is_base_of<std::bidirectional_iterator_tag,
93 IteratorCategoryT>::value,
94 };
95
96 /// A proxy object for computing a reference via indirecting a copy of an
97 /// iterator. This is used in APIs which need to produce a reference via
98 /// indirection but for which the iterator object might be a temporary. The
99 /// proxy preserves the iterator internally and exposes the indirected
100 /// reference via a conversion operator.
101 class ReferenceProxy {
102 friend iterator_facade_base;
103
104 DerivedT I;
105
106 ReferenceProxy(DerivedT I) : I(std::move(I)) {}
107
108 public:
109 operator ReferenceT() const { return *I; }
110 };
111
112 /// A proxy object for computing a pointer via indirecting a copy of a
113 /// reference. This is used in APIs which need to produce a pointer but for
114 /// which the reference might be a temporary. The proxy preserves the
115 /// reference internally and exposes the pointer via a arrow operator.
116 class PointerProxy {
117 friend iterator_facade_base;
118
119 ReferenceT R;
120
121 template <typename RefT>
122 PointerProxy(RefT &&R) : R(std::forward<RefT>(R)) {}
123
124 public:
125 PointerT operator->() const { return &R; }
126 };
127
128public:
129 DerivedT operator+(DifferenceTypeT n) const {
130 static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
131 "Must pass the derived type to this template!");
132 static_assert(
133 IsRandomAccess,
134 "The '+' operator is only defined for random access iterators.");
135 DerivedT tmp = *static_cast<const DerivedT *>(this);
136 tmp += n;
137 return tmp;
138 }
139 friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) {
140 static_assert(
141 IsRandomAccess,
142 "The '+' operator is only defined for random access iterators.");
143 return i + n;
144 }
145 DerivedT operator-(DifferenceTypeT n) const {
146 static_assert(
147 IsRandomAccess,
148 "The '-' operator is only defined for random access iterators.");
149 DerivedT tmp = *static_cast<const DerivedT *>(this);
150 tmp -= n;
151 return tmp;
152 }
153
154 DerivedT &operator++() {
155 static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
156 "Must pass the derived type to this template!");
157 return static_cast<DerivedT *>(this)->operator+=(1);
158 }
159 DerivedT operator++(int) {
160 DerivedT tmp = *static_cast<DerivedT *>(this);
161 ++*static_cast<DerivedT *>(this);
162 return tmp;
163 }
164 DerivedT &operator--() {
165 static_assert(
166 IsBidirectional,
167 "The decrement operator is only defined for bidirectional iterators.");
168 return static_cast<DerivedT *>(this)->operator-=(1);
169 }
170 DerivedT operator--(int) {
171 static_assert(
172 IsBidirectional,
173 "The decrement operator is only defined for bidirectional iterators.");
174 DerivedT tmp = *static_cast<DerivedT *>(this);
175 --*static_cast<DerivedT *>(this);
176 return tmp;
177 }
178
179#ifndef __cpp_impl_three_way_comparison
180 bool operator!=(const DerivedT &RHS) const {
181 return !(static_cast<const DerivedT &>(*this) == RHS);
182 }
183#endif
184
185 bool operator>(const DerivedT &RHS) const {
186 static_assert(
187 IsRandomAccess,
188 "Relational operators are only defined for random access iterators.");
189 return !(static_cast<const DerivedT &>(*this) < RHS) &&
190 !(static_cast<const DerivedT &>(*this) == RHS);
191 }
192 bool operator<=(const DerivedT &RHS) const {
193 static_assert(
194 IsRandomAccess,
195 "Relational operators are only defined for random access iterators.");
196 return !(static_cast<const DerivedT &>(*this) > RHS);
197 }
198 bool operator>=(const DerivedT &RHS) const {
199 static_assert(
200 IsRandomAccess,
201 "Relational operators are only defined for random access iterators.");
202 return !(static_cast<const DerivedT &>(*this) < RHS);
203 }
204
205 PointerProxy operator->() const {
206 return static_cast<const DerivedT *>(this)->operator*();
207 }
208 ReferenceProxy operator[](DifferenceTypeT n) const {
209 static_assert(IsRandomAccess,
210 "Subscripting is only defined for random access iterators.");
211 return static_cast<const DerivedT *>(this)->operator+(n);
212 }
213};
214
215/// CRTP base class for adapting an iterator to a different type.
216///
217/// This class can be used through CRTP to adapt one iterator into another.
218/// Typically this is done through providing in the derived class a custom \c
219/// operator* implementation. Other methods can be overridden as well.
220template <
221 typename DerivedT, typename WrappedIteratorT,
222 typename IteratorCategoryT =
223 typename std::iterator_traits<WrappedIteratorT>::iterator_category,
224 typename T = typename std::iterator_traits<WrappedIteratorT>::value_type,
225 typename DifferenceTypeT =
226 typename std::iterator_traits<WrappedIteratorT>::difference_type,
227 typename PointerT = std::conditional_t<
228 std::is_same<T, typename std::iterator_traits<
229 WrappedIteratorT>::value_type>::value,
230 typename std::iterator_traits<WrappedIteratorT>::pointer, T *>,
231 typename ReferenceT = std::conditional_t<
232 std::is_same<T, typename std::iterator_traits<
233 WrappedIteratorT>::value_type>::value,
234 typename std::iterator_traits<WrappedIteratorT>::reference, T &>>
235class iterator_adaptor_base
236 : public iterator_facade_base<DerivedT, IteratorCategoryT, T,
237 DifferenceTypeT, PointerT, ReferenceT> {
238 using BaseT = typename iterator_adaptor_base::iterator_facade_base;
239
240protected:
241 WrappedIteratorT I;
242
243 iterator_adaptor_base() = default;
244
245 explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) {
246 static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value,
247 "Must pass the derived type to this template!");
248 }
249
250 const WrappedIteratorT &wrapped() const { return I; }
251
252public:
253 using difference_type = DifferenceTypeT;
254
255 DerivedT &operator+=(difference_type n) {
256 static_assert(
257 BaseT::IsRandomAccess,
258 "The '+=' operator is only defined for random access iterators.");
259 I += n;
260 return *static_cast<DerivedT *>(this);
261 }
262 DerivedT &operator-=(difference_type n) {
263 static_assert(
264 BaseT::IsRandomAccess,
265 "The '-=' operator is only defined for random access iterators.");
266 I -= n;
267 return *static_cast<DerivedT *>(this);
268 }
269 using BaseT::operator-;
270 difference_type operator-(const DerivedT &RHS) const {
271 static_assert(
272 BaseT::IsRandomAccess,
273 "The '-' operator is only defined for random access iterators.");
274 return I - RHS.I;
275 }
276
277 // We have to explicitly provide ++ and -- rather than letting the facade
278 // forward to += because WrappedIteratorT might not support +=.
279 using BaseT::operator++;
280 DerivedT &operator++() {
281 ++I;
282 return *static_cast<DerivedT *>(this);
283 }
284 using BaseT::operator--;
285 DerivedT &operator--() {
286 static_assert(
287 BaseT::IsBidirectional,
288 "The decrement operator is only defined for bidirectional iterators.");
289 --I;
290 return *static_cast<DerivedT *>(this);
291 }
292
293 friend bool operator==(const iterator_adaptor_base &LHS,
294 const iterator_adaptor_base &RHS) {
295 return LHS.I == RHS.I;
296 }
297 friend bool operator<(const iterator_adaptor_base &LHS,
298 const iterator_adaptor_base &RHS) {
299 static_assert(
300 BaseT::IsRandomAccess,
301 "Relational operators are only defined for random access iterators.");
302 return LHS.I < RHS.I;
303 }
304
305 ReferenceT operator*() const { return *I; }
306};
307
308/// An iterator type that allows iterating over the pointees via some
309/// other iterator.
310///
311/// The typical usage of this is to expose a type that iterates over Ts, but
312/// which is implemented with some iterator over T*s:
313///
314/// \code
315/// using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>;
316/// \endcode
317template <typename WrappedIteratorT,
318 typename T = std::remove_reference_t<decltype(
319 **std::declval<WrappedIteratorT>())>>
320struct pointee_iterator
321 : iterator_adaptor_base<
322 pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT,
323 typename std::iterator_traits<WrappedIteratorT>::iterator_category,
324 T> {
325 pointee_iterator() = default;
326 template <typename U>
327 pointee_iterator(U &&u)
328 : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
329
330 T &operator*() const { return **this->I; }
331};
332
333template <typename RangeT, typename WrappedIteratorT =
334 decltype(std::begin(std::declval<RangeT>()))>
335iterator_range<pointee_iterator<WrappedIteratorT>>
336make_pointee_range(RangeT &&Range) {
337 using PointeeIteratorT = pointee_iterator<WrappedIteratorT>;
338 return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))),
339 PointeeIteratorT(std::end(std::forward<RangeT>(Range))));
340}
341
342template <typename WrappedIteratorT,
343 typename T = decltype(&*std::declval<WrappedIteratorT>())>
344class pointer_iterator
345 : public iterator_adaptor_base<
346 pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT,
347 typename std::iterator_traits<WrappedIteratorT>::iterator_category,
348 T> {
349 mutable T Ptr;
350
351public:
352 pointer_iterator() = default;
353
354 explicit pointer_iterator(WrappedIteratorT u)
355 : pointer_iterator::iterator_adaptor_base(std::move(u)) {}
356
357 T &operator*() const { return Ptr = &*this->I; }
358};
359
360template <typename RangeT, typename WrappedIteratorT =
361 decltype(std::begin(std::declval<RangeT>()))>
362iterator_range<pointer_iterator<WrappedIteratorT>>
363make_pointer_range(RangeT &&Range) {
364 using PointerIteratorT = pointer_iterator<WrappedIteratorT>;
365 return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))),
366 PointerIteratorT(std::end(std::forward<RangeT>(Range))));
367}
368
369template <typename WrappedIteratorT,
370 typename T1 = std::remove_reference_t<decltype(
371 **std::declval<WrappedIteratorT>())>,
372 typename T2 = std::add_pointer_t<T1>>
373using raw_pointer_iterator =
374 pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>;
375
376} // end namespace llvm
377
378#endif // LLVM_ADT_ITERATOR_H
379

source code of include/llvm-17/llvm/ADT/iterator.h