Line data Source code
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 : /// 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 : ///
77 : template <typename DerivedT, typename IteratorCategoryT, typename T,
78 : typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *,
79 : typename ReferenceT = T &>
80 : class iterator_facade_base {
81 : public:
82 : using iterator_category = IteratorCategoryT;
83 : using value_type = T;
84 : using difference_type = DifferenceTypeT;
85 : using pointer = PointerT;
86 : using reference = ReferenceT;
87 :
88 : protected:
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 23868 : PointerProxy(RefT &&R) : R(std::forward<RefT>(R)) {}
123 :
124 : public:
125 23868 : PointerT operator->() const { return &R; }
126 : };
127 :
128 : public:
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 56150 : bool operator!=(const DerivedT &RHS) const {
181 56150 : 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 23868 : PointerProxy operator->() const {
206 23868 : 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.
220 : template <
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 &>>
235 : class 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 :
240 : protected:
241 : WrappedIteratorT I;
242 :
243 : iterator_adaptor_base() = default;
244 :
245 0 : 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 0 : }
249 :
250 : const WrappedIteratorT &wrapped() const { return I; }
251 :
252 : public:
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 0 : DerivedT &operator++() {
281 0 : ++I;
282 0 : 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
317 : template <typename WrappedIteratorT,
318 : typename T = std::remove_reference_t<decltype(
319 : **std::declval<WrappedIteratorT>())>>
320 : struct 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 :
333 : template <typename RangeT, typename WrappedIteratorT =
334 : decltype(std::begin(std::declval<RangeT>()))>
335 : iterator_range<pointee_iterator<WrappedIteratorT>>
336 : make_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 :
342 : template <typename WrappedIteratorT,
343 : typename T = decltype(&*std::declval<WrappedIteratorT>())>
344 : class 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 :
351 : public:
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 :
360 : template <typename RangeT, typename WrappedIteratorT =
361 : decltype(std::begin(std::declval<RangeT>()))>
362 : iterator_range<pointer_iterator<WrappedIteratorT>>
363 : make_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 :
369 : template <typename WrappedIteratorT,
370 : typename T1 = std::remove_reference_t<decltype(
371 : **std::declval<WrappedIteratorT>())>,
372 : typename T2 = std::add_pointer_t<T1>>
373 : using raw_pointer_iterator =
374 : pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>;
375 :
376 : } // end namespace llvm
377 :
378 : #endif // LLVM_ADT_ITERATOR_H
|
