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