llvm/ADT/iterator.h

0001 //===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_ADT_ITERATOR_H
0010 #define LLVM_ADT_ITERATOR_H
0011
0012 #include "llvm/ADT/iterator_range.h"
0013 #include <cstddef>
0014 #include <iterator>
0015 #include <type_traits>
0016 #include <utility>
0017
0018 namespace llvm {
0019
0020 /// CRTP base class which implements the entire standard iterator facade
0021 /// in terms of a minimal subset of the interface.
0022 ///
0023 /// Use this when it is reasonable to implement most of the iterator
0024 /// functionality in terms of a core subset. If you need special behavior or
0025 /// there are performance implications for this, you may want to override the
0026 /// relevant members instead.
0027 ///
0028 /// Note, one abstraction that this does *not* provide is implementing
0029 /// subtraction in terms of addition by negating the difference. Negation isn't
0030 /// always information preserving, and I can see very reasonable iterator
0031 /// designs where this doesn't work well. It doesn't really force much added
0032 /// boilerplate anyways.
0033 ///
0034 /// Another abstraction that this doesn't provide is implementing increment in
0035 /// terms of addition of one. These aren't equivalent for all iterator
0036 /// categories, and respecting that adds a lot of complexity for little gain.
0037 ///
0038 /// Iterators are expected to have const rules analogous to pointers, with a
0039 /// single, const-qualified operator*() that returns ReferenceT. This matches
0040 /// the second and third pointers in the following example:
0041 /// \code
0042 ///   int Value;
0043 ///   { int *I = &Value; }             // ReferenceT 'int&'
0044 ///   { int *const I = &Value; }       // ReferenceT 'int&'; const
0045 ///   { const int *I = &Value; }       // ReferenceT 'const int&'
0046 ///   { const int *const I = &Value; } // ReferenceT 'const int&'; const
0047 /// \endcode
0048 /// If an iterator facade returns a handle to its own state, then T (and
0049 /// PointerT and ReferenceT) should usually be const-qualified. Otherwise, if
0050 /// clients are expected to modify the handle itself, the field can be declared
0051 /// mutable or use const_cast.
0052 ///
0053 /// Classes wishing to use `iterator_facade_base` should implement the following
0054 /// methods:
0055 ///
0056 /// Forward Iterators:
0057 ///   (All of the following methods)
0058 ///   - DerivedT &operator=(const DerivedT &R);
0059 ///   - bool operator==(const DerivedT &R) const;
0060 ///   - T &operator*() const;
0061 ///   - DerivedT &operator++();
0062 ///
0063 /// Bidirectional Iterators:
0064 ///   (All methods of forward iterators, plus the following)
0065 ///   - DerivedT &operator--();
0066 ///
0067 /// Random-access Iterators:
0068 ///   (All methods of bidirectional iterators excluding the following)
0069 ///   - DerivedT &operator++();
0070 ///   - DerivedT &operator--();
0071 ///   (and plus the following)
0072 ///   - bool operator<(const DerivedT &RHS) const;
0073 ///   - DifferenceTypeT operator-(const DerivedT &R) const;
0074 ///   - DerivedT &operator+=(DifferenceTypeT N);
0075 ///   - DerivedT &operator-=(DifferenceTypeT N);
0076 ///
0077 template <typename DerivedT, typename IteratorCategoryT, typename T,
0078           typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *,
0079           typename ReferenceT = T &>
0080 class iterator_facade_base {
0081 public:
0082   using iterator_category = IteratorCategoryT;
0083   using value_type = T;
0084   using difference_type = DifferenceTypeT;
0085   using pointer = PointerT;
0086   using reference = ReferenceT;
0087
0088 protected:
0089   enum {
0090     IsRandomAccess = std::is_base_of<std::random_access_iterator_tag,
0091                                      IteratorCategoryT>::value,
0092     IsBidirectional = std::is_base_of<std::bidirectional_iterator_tag,
0093                                       IteratorCategoryT>::value,
0094   };
0095
0096   /// A proxy object for computing a reference via indirecting a copy of an
0097   /// iterator. This is used in APIs which need to produce a reference via
0098   /// indirection but for which the iterator object might be a temporary. The
0099   /// proxy preserves the iterator internally and exposes the indirected
0100   /// reference via a conversion operator.
0101   class ReferenceProxy {
0102     friend iterator_facade_base;
0103
0104     DerivedT I;
0105
0106     ReferenceProxy(DerivedT I) : I(std::move(I)) {}
0107
0108   public:
0109     operator ReferenceT() const { return *I; }
0110   };
0111
0112   /// A proxy object for computing a pointer via indirecting a copy of a
0113   /// reference. This is used in APIs which need to produce a pointer but for
0114   /// which the reference might be a temporary. The proxy preserves the
0115   /// reference internally and exposes the pointer via a arrow operator.
0116   class PointerProxy {
0117     friend iterator_facade_base;
0118
0119     ReferenceT R;
0120
0121     template <typename RefT>
0122     PointerProxy(RefT &&R) : R(std::forward<RefT>(R)) {}
0123
0124   public:
0125     PointerT operator->() const { return &R; }
0126   };
0127
0128 public:
0129   DerivedT operator+(DifferenceTypeT n) const {
0130     static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
0131                   "Must pass the derived type to this template!");
0132     static_assert(
0133         IsRandomAccess,
0134         "The '+' operator is only defined for random access iterators.");
0135     DerivedT tmp = *static_cast<const DerivedT *>(this);
0136     tmp += n;
0137     return tmp;
0138   }
0139   friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) {
0140     static_assert(
0141         IsRandomAccess,
0142         "The '+' operator is only defined for random access iterators.");
0143     return i + n;
0144   }
0145   DerivedT operator-(DifferenceTypeT n) const {
0146     static_assert(
0147         IsRandomAccess,
0148         "The '-' operator is only defined for random access iterators.");
0149     DerivedT tmp = *static_cast<const DerivedT *>(this);
0150     tmp -= n;
0151     return tmp;
0152   }
0153
0154   DerivedT &operator++() {
0155     static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value,
0156                   "Must pass the derived type to this template!");
0157     return static_cast<DerivedT *>(this)->operator+=(1);
0158   }
0159   DerivedT operator++(int) {
0160     DerivedT tmp = *static_cast<DerivedT *>(this);
0161     ++*static_cast<DerivedT *>(this);
0162     return tmp;
0163   }
0164   DerivedT &operator--() {
0165     static_assert(
0166         IsBidirectional,
0167         "The decrement operator is only defined for bidirectional iterators.");
0168     return static_cast<DerivedT *>(this)->operator-=(1);
0169   }
0170   DerivedT operator--(int) {
0171     static_assert(
0172         IsBidirectional,
0173         "The decrement operator is only defined for bidirectional iterators.");
0174     DerivedT tmp = *static_cast<DerivedT *>(this);
0175     --*static_cast<DerivedT *>(this);
0176     return tmp;
0177   }
0178
0179 #ifndef __cpp_impl_three_way_comparison
0180   bool operator!=(const DerivedT &RHS) const {
0181     return !(static_cast<const DerivedT &>(*this) == RHS);
0182   }
0183 #endif
0184
0185   bool operator>(const DerivedT &RHS) const {
0186     static_assert(
0187         IsRandomAccess,
0188         "Relational operators are only defined for random access iterators.");
0189     return !(static_cast<const DerivedT &>(*this) < RHS) &&
0190            !(static_cast<const DerivedT &>(*this) == RHS);
0191   }
0192   bool operator<=(const DerivedT &RHS) const {
0193     static_assert(
0194         IsRandomAccess,
0195         "Relational operators are only defined for random access iterators.");
0196     return !(static_cast<const DerivedT &>(*this) > RHS);
0197   }
0198   bool operator>=(const DerivedT &RHS) const {
0199     static_assert(
0200         IsRandomAccess,
0201         "Relational operators are only defined for random access iterators.");
0202     return !(static_cast<const DerivedT &>(*this) < RHS);
0203   }
0204
0205   PointerProxy operator->() const {
0206     return static_cast<const DerivedT *>(this)->operator*();
0207   }
0208   ReferenceProxy operator[](DifferenceTypeT n) const {
0209     static_assert(IsRandomAccess,
0210                   "Subscripting is only defined for random access iterators.");
0211     return static_cast<const DerivedT *>(this)->operator+(n);
0212   }
0213 };
0214
0215 /// CRTP base class for adapting an iterator to a different type.
0216 ///
0217 /// This class can be used through CRTP to adapt one iterator into another.
0218 /// Typically this is done through providing in the derived class a custom \c
0219 /// operator* implementation. Other methods can be overridden as well.
0220 template <
0221     typename DerivedT, typename WrappedIteratorT,
0222     typename IteratorCategoryT =
0223         typename std::iterator_traits<WrappedIteratorT>::iterator_category,
0224     typename T = typename std::iterator_traits<WrappedIteratorT>::value_type,
0225     typename DifferenceTypeT =
0226         typename std::iterator_traits<WrappedIteratorT>::difference_type,
0227     typename PointerT = std::conditional_t<
0228         std::is_same<T, typename std::iterator_traits<
0229                             WrappedIteratorT>::value_type>::value,
0230         typename std::iterator_traits<WrappedIteratorT>::pointer, T *>,
0231     typename ReferenceT = std::conditional_t<
0232         std::is_same<T, typename std::iterator_traits<
0233                             WrappedIteratorT>::value_type>::value,
0234         typename std::iterator_traits<WrappedIteratorT>::reference, T &>>
0235 class iterator_adaptor_base
0236     : public iterator_facade_base<DerivedT, IteratorCategoryT, T,
0237                                   DifferenceTypeT, PointerT, ReferenceT> {
0238   using BaseT = typename iterator_adaptor_base::iterator_facade_base;
0239
0240 protected:
0241   WrappedIteratorT I;
0242
0243   iterator_adaptor_base() = default;
0244
0245   explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) {
0246     static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value,
0247                   "Must pass the derived type to this template!");
0248   }
0249
0250   const WrappedIteratorT &wrapped() const { return I; }
0251
0252 public:
0253   using difference_type = DifferenceTypeT;
0254
0255   DerivedT &operator+=(difference_type n) {
0256     static_assert(
0257         BaseT::IsRandomAccess,
0258         "The '+=' operator is only defined for random access iterators.");
0259     I += n;
0260     return *static_cast<DerivedT *>(this);
0261   }
0262   DerivedT &operator-=(difference_type n) {
0263     static_assert(
0264         BaseT::IsRandomAccess,
0265         "The '-=' operator is only defined for random access iterators.");
0266     I -= n;
0267     return *static_cast<DerivedT *>(this);
0268   }
0269   using BaseT::operator-;
0270   difference_type operator-(const DerivedT &RHS) const {
0271     static_assert(
0272         BaseT::IsRandomAccess,
0273         "The '-' operator is only defined for random access iterators.");
0274     return I - RHS.I;
0275   }
0276
0277   // We have to explicitly provide ++ and -- rather than letting the facade
0278   // forward to += because WrappedIteratorT might not support +=.
0279   using BaseT::operator++;
0280   DerivedT &operator++() {
0281     ++I;
0282     return *static_cast<DerivedT *>(this);
0283   }
0284   using BaseT::operator--;
0285   DerivedT &operator--() {
0286     static_assert(
0287         BaseT::IsBidirectional,
0288         "The decrement operator is only defined for bidirectional iterators.");
0289     --I;
0290     return *static_cast<DerivedT *>(this);
0291   }
0292
0293   friend bool operator==(const iterator_adaptor_base &LHS,
0294                          const iterator_adaptor_base &RHS) {
0295     return LHS.I == RHS.I;
0296   }
0297   friend bool operator<(const iterator_adaptor_base &LHS,
0298                         const iterator_adaptor_base &RHS) {
0299     static_assert(
0300         BaseT::IsRandomAccess,
0301         "Relational operators are only defined for random access iterators.");
0302     return LHS.I < RHS.I;
0303   }
0304
0305   ReferenceT operator*() const { return *I; }
0306 };
0307
0308 /// An iterator type that allows iterating over the pointees via some
0309 /// other iterator.
0310 ///
0311 /// The typical usage of this is to expose a type that iterates over Ts, but
0312 /// which is implemented with some iterator over T*s:
0313 ///
0314 /// \code
0315 ///   using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>;
0316 /// \endcode
0317 template <typename WrappedIteratorT,
0318           typename T = std::remove_reference_t<decltype(
0319               **std::declval<WrappedIteratorT>())>>
0320 struct pointee_iterator
0321     : iterator_adaptor_base<
0322           pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT,
0323           typename std::iterator_traits<WrappedIteratorT>::iterator_category,
0324           T> {
0325   pointee_iterator() = default;
0326   template <typename U>
0327   pointee_iterator(U &&u)
0328       : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
0329
0330   T &operator*() const { return **this->I; }
0331 };
0332
0333 template <typename RangeT, typename WrappedIteratorT =
0334                                decltype(std::begin(std::declval<RangeT>()))>
0335 iterator_range<pointee_iterator<WrappedIteratorT>>
0336 make_pointee_range(RangeT &&Range) {
0337   using PointeeIteratorT = pointee_iterator<WrappedIteratorT>;
0338   return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))),
0339                     PointeeIteratorT(std::end(std::forward<RangeT>(Range))));
0340 }
0341
0342 template <typename WrappedIteratorT,
0343           typename T = decltype(&*std::declval<WrappedIteratorT>())>
0344 class pointer_iterator
0345     : public iterator_adaptor_base<
0346           pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT,
0347           typename std::iterator_traits<WrappedIteratorT>::iterator_category,
0348           T> {
0349   mutable T Ptr;
0350
0351 public:
0352   pointer_iterator() = default;
0353
0354   explicit pointer_iterator(WrappedIteratorT u)
0355       : pointer_iterator::iterator_adaptor_base(std::move(u)) {}
0356
0357   T &operator*() const { return Ptr = &*this->I; }
0358 };
0359
0360 template <typename RangeT, typename WrappedIteratorT =
0361                                decltype(std::begin(std::declval<RangeT>()))>
0362 iterator_range<pointer_iterator<WrappedIteratorT>>
0363 make_pointer_range(RangeT &&Range) {
0364   using PointerIteratorT = pointer_iterator<WrappedIteratorT>;
0365   return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))),
0366                     PointerIteratorT(std::end(std::forward<RangeT>(Range))));
0367 }
0368
0369 template <typename WrappedIteratorT,
0370           typename T1 = std::remove_reference_t<decltype(
0371               **std::declval<WrappedIteratorT>())>,
0372           typename T2 = std::add_pointer_t<T1>>
0373 using raw_pointer_iterator =
0374     pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>;
0375
0376 } // end namespace llvm
0377
0378 #endif // LLVM_ADT_ITERATOR_H