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/// 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///
63template <typename DerivedT, typename IteratorCategoryT, typename T,
64 typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *,
65 typename ReferenceT = T &>
66class iterator_facade_base {
67public:
68 using iterator_category = IteratorCategoryT;
69 using value_type = T;
70 using difference_type = DifferenceTypeT;
71 using pointer = PointerT;
72 using reference = ReferenceT;
73
74protected:
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
92 ReferenceProxy(DerivedT I) : I(std::move(I)) {}
93
94 public:
95 operator ReferenceT() const { return *I; }
96 };
97
98public:
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.
196template <
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 &>>
211class 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
216protected:
217 WrappedIteratorT I;
218
219 iterator_adaptor_base() = default;
220
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
226 const WrappedIteratorT &wrapped() const { return I; }
227
228public:
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
293template <typename WrappedIteratorT,
294 typename T = std::remove_reference_t<decltype(
295 **std::declval<WrappedIteratorT>())>>
296struct 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>
303 pointee_iterator(U &&u)
304 : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
305
306 T &operator*() const { return **this->I; }
307};
308
309template <typename RangeT, typename WrappedIteratorT =
310 decltype(std::begin(std::declval<RangeT>()))>
311iterator_range<pointee_iterator<WrappedIteratorT>>
312make_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
318template <typename WrappedIteratorT,
319 typename T = decltype(&*std::declval<WrappedIteratorT>())>
320class 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
327public:
328 pointer_iterator() = default;
329
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
337template <typename RangeT, typename WrappedIteratorT =
338 decltype(std::begin(std::declval<RangeT>()))>
339iterator_range<pointer_iterator<WrappedIteratorT>>
340make_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
346template <typename WrappedIteratorT,
347 typename T1 = std::remove_reference_t<decltype(
348 **std::declval<WrappedIteratorT>())>,
349 typename T2 = std::add_pointer_t<T1>>
350using raw_pointer_iterator =
351 pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>;
352
353// Wrapper iterator over iterator ItType, adding DataRef to the type of ItType,
354// to create NodeRef = std::pair<InnerTypeOfItType, DataRef>.
355template <typename ItType, typename NodeRef, typename DataRef>
356class WrappedPairNodeDataIterator
357 : public iterator_adaptor_base<
358 WrappedPairNodeDataIterator<ItType, NodeRef, DataRef>, ItType,
359 typename std::iterator_traits<ItType>::iterator_category, NodeRef,
360 std::ptrdiff_t, NodeRef *, NodeRef &> {
361 using BaseT = iterator_adaptor_base<
362 WrappedPairNodeDataIterator, ItType,
363 typename std::iterator_traits<ItType>::iterator_category, NodeRef,
364 std::ptrdiff_t, NodeRef *, NodeRef &>;
365
366 const DataRef DR;
367 mutable NodeRef NR;
368
369public:
370 WrappedPairNodeDataIterator(ItType Begin, const DataRef DR)
371 : BaseT(Begin), DR(DR) {
372 NR.first = DR;
373 }
374
375 NodeRef &operator*() const {
376 NR.second = *this->I;
377 return NR;
378 }
379};
380
381} // end namespace llvm
382
383#endif // LLVM_ADT_ITERATOR_H
384