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