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