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
19namespace 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///
64template <typename DerivedT, typename IteratorCategoryT, typename T,
65          typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *,
66          typename ReferenceT = T &>
67class iterator_facade_base
68    : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT,
69                           ReferenceT> {
70protected:
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
94public:
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  bool operator!=(const DerivedT &RHS) const {
146    return !static_cast<const DerivedT *>(this)->operator==(RHS);
147  }
148
149  bool operator>(const DerivedT &RHS) const {
150    static_assert(
151        IsRandomAccess,
152        "Relational operators are only defined for random access iterators.");
153    return !static_cast<const DerivedT *>(this)->operator<(RHS) &&
154           !static_cast<const DerivedT *>(this)->operator==(RHS);
155  }
156  bool operator<=(const DerivedT &RHS) const {
157    static_assert(
158        IsRandomAccess,
159        "Relational operators are only defined for random access iterators.");
160    return !static_cast<const DerivedT *>(this)->operator>(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)->operator<(RHS);
167  }
168
169  PointerT operator->() { return &static_cast<DerivedT *>(this)->operator*(); }
170  PointerT operator->() const {
171    return &static_cast<const DerivedT *>(this)->operator*();
172  }
173  ReferenceProxy operator[](DifferenceTypeT n) {
174    static_assert(IsRandomAccess,
175                  "Subscripting is only defined for random access iterators.");
176    return ReferenceProxy(static_cast<DerivedT *>(this)->operator+(n));
177  }
178  ReferenceProxy operator[](DifferenceTypeT n) const {
179    static_assert(IsRandomAccess,
180                  "Subscripting is only defined for random access iterators.");
181    return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n));
182  }
183};
184
185/// CRTP base class for adapting an iterator to a different type.
186///
187/// This class can be used through CRTP to adapt one iterator into another.
188/// Typically this is done through providing in the derived class a custom \c
189/// operator* implementation. Other methods can be overridden as well.
190template <
191    typename DerivedT, typename WrappedIteratorT,
192    typename IteratorCategoryT =
193        typename std::iterator_traits<WrappedIteratorT>::iterator_category,
194    typename T = typename std::iterator_traits<WrappedIteratorT>::value_type,
195    typename DifferenceTypeT =
196        typename std::iterator_traits<WrappedIteratorT>::difference_type,
197    typename PointerT = std::conditional_t<
198        std::is_same<T, typename std::iterator_traits<
199                            WrappedIteratorT>::value_type>::value,
200        typename std::iterator_traits<WrappedIteratorT>::pointer, T *>,
201    typename ReferenceT = std::conditional_t<
202        std::is_same<T, typename std::iterator_traits<
203                            WrappedIteratorT>::value_type>::value,
204        typename std::iterator_traits<WrappedIteratorT>::reference, T &>>
205class iterator_adaptor_base
206    : public iterator_facade_base<DerivedT, IteratorCategoryT, T,
207                                  DifferenceTypeT, PointerT, ReferenceT> {
208  using BaseT = typename iterator_adaptor_base::iterator_facade_base;
209
210protected:
211  WrappedIteratorT I;
212
213  iterator_adaptor_base() = default;
214
215  explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) {
216    static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value,
217                  "Must pass the derived type to this template!");
218  }
219
220  const WrappedIteratorT &wrapped() const { return I; }
221
222public:
223  using difference_type = DifferenceTypeT;
224
225  DerivedT &operator+=(difference_type n) {
226    static_assert(
227        BaseT::IsRandomAccess,
228        "The '+=' operator is only defined for random access iterators.");
229    I += n;
230    return *static_cast<DerivedT *>(this);
231  }
232  DerivedT &operator-=(difference_type n) {
233    static_assert(
234        BaseT::IsRandomAccess,
235        "The '-=' operator is only defined for random access iterators.");
236    I -= n;
237    return *static_cast<DerivedT *>(this);
238  }
239  using BaseT::operator-;
240  difference_type operator-(const DerivedT &RHS) const {
241    static_assert(
242        BaseT::IsRandomAccess,
243        "The '-' operator is only defined for random access iterators.");
244    return I - RHS.I;
245  }
246
247  // We have to explicitly provide ++ and -- rather than letting the facade
248  // forward to += because WrappedIteratorT might not support +=.
249  using BaseT::operator++;
250  DerivedT &operator++() {
251    ++I;
252    return *static_cast<DerivedT *>(this);
253  }
254  using BaseT::operator--;
255  DerivedT &operator--() {
256    static_assert(
257        BaseT::IsBidirectional,
258        "The decrement operator is only defined for bidirectional iterators.");
259    --I;
260    return *static_cast<DerivedT *>(this);
261  }
262
263  bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
264  bool operator<(const DerivedT &RHS) const {
265    static_assert(
266        BaseT::IsRandomAccess,
267        "Relational operators are only defined for random access iterators.");
268    return I < RHS.I;
269  }
270
271  ReferenceT operator*() const { return *I; }
272};
273
274/// An iterator type that allows iterating over the pointees via some
275/// other iterator.
276///
277/// The typical usage of this is to expose a type that iterates over Ts, but
278/// which is implemented with some iterator over T*s:
279///
280/// \code
281///   using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>;
282/// \endcode
283template <typename WrappedIteratorT,
284          typename T = std::remove_reference_t<decltype(
285              **std::declval<WrappedIteratorT>())>>
286struct pointee_iterator
287    : iterator_adaptor_base<
288          pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT,
289          typename std::iterator_traits<WrappedIteratorT>::iterator_category,
290          T> {
291  pointee_iterator() = default;
292  template <typename U>
293  pointee_iterator(U &&u)
294      : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
295
296  T &operator*() const { return **this->I; }
297};
298
299template <typename RangeT, typename WrappedIteratorT =
300                               decltype(std::begin(std::declval<RangeT>()))>
301iterator_range<pointee_iterator<WrappedIteratorT>>
302make_pointee_range(RangeT &&Range) {
303  using PointeeIteratorT = pointee_iterator<WrappedIteratorT>;
304  return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))),
305                    PointeeIteratorT(std::end(std::forward<RangeT>(Range))));
306}
307
308template <typename WrappedIteratorT,
309          typename T = decltype(&*std::declval<WrappedIteratorT>())>
310class pointer_iterator
311    : public iterator_adaptor_base<
312          pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT,
313          typename std::iterator_traits<WrappedIteratorT>::iterator_category,
314          T> {
315  mutable T Ptr;
316
317public:
318  pointer_iterator() = default;
319
320  explicit pointer_iterator(WrappedIteratorT u)
321      : pointer_iterator::iterator_adaptor_base(std::move(u)) {}
322
323  T &operator*() { return Ptr = &*this->I; }
324  const T &operator*() const { return Ptr = &*this->I; }
325};
326
327template <typename RangeT, typename WrappedIteratorT =
328                               decltype(std::begin(std::declval<RangeT>()))>
329iterator_range<pointer_iterator<WrappedIteratorT>>
330make_pointer_range(RangeT &&Range) {
331  using PointerIteratorT = pointer_iterator<WrappedIteratorT>;
332  return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))),
333                    PointerIteratorT(std::end(std::forward<RangeT>(Range))));
334}
335
336template <typename WrappedIteratorT,
337          typename T1 = std::remove_reference_t<decltype(
338              **std::declval<WrappedIteratorT>())>,
339          typename T2 = std::add_pointer_t<T1>>
340using raw_pointer_iterator =
341    pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>;
342
343// Wrapper iterator over iterator ItType, adding DataRef to the type of ItType,
344// to create NodeRef = std::pair<InnerTypeOfItType, DataRef>.
345template <typename ItType, typename NodeRef, typename DataRef>
346class WrappedPairNodeDataIterator
347    : public iterator_adaptor_base<
348          WrappedPairNodeDataIterator<ItType, NodeRef, DataRef>, ItType,
349          typename std::iterator_traits<ItType>::iterator_category, NodeRef,
350          std::ptrdiff_t, NodeRef *, NodeRef &> {
351  using BaseT = iterator_adaptor_base<
352      WrappedPairNodeDataIterator, ItType,
353      typename std::iterator_traits<ItType>::iterator_category, NodeRef,
354      std::ptrdiff_t, NodeRef *, NodeRef &>;
355
356  const DataRef DR;
357  mutable NodeRef NR;
358
359public:
360  WrappedPairNodeDataIterator(ItType Begin, const DataRef DR)
361      : BaseT(Begin), DR(DR) {
362    NR.first = DR;
363  }
364
365  NodeRef &operator*() const {
366    NR.second = *this->I;
367    return NR;
368  }
369};
370
371} // end namespace llvm
372
373#endif // LLVM_ADT_ITERATOR_H
374