include/llvm/ADT/iterator.h

   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   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.
 190 template <
 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 = typename std::conditional<
 198         std::is_same<T, typename std::iterator_traits<
 199                             WrappedIteratorT>::value_type>::value,
 200         typename std::iterator_traits<WrappedIteratorT>::pointer, T *>::type,
 201     typename ReferenceT = typename std::conditional<
 202         std::is_same<T, typename std::iterator_traits<
 203                             WrappedIteratorT>::value_type>::value,
 204         typename std::iterator_traits<WrappedIteratorT>::reference, T &>::type>
 205 class 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
 210 protected:
 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
 222 public:
 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
 283 template <typename WrappedIteratorT,
 284           typename T = typename std::remove_reference<
 285               decltype(**std::declval<WrappedIteratorT>())>::type>
 286 struct 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
 299 template <typename RangeT, typename WrappedIteratorT =
 300                                decltype(std::begin(std::declval<RangeT>()))>
 301 iterator_range<pointee_iterator<WrappedIteratorT>>
 302 make_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
 308 template <typename WrappedIteratorT,
 309           typename T = decltype(&*std::declval<WrappedIteratorT>())>
 310 class 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
 317 public:
 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
 327 template <typename RangeT, typename WrappedIteratorT =
 328                                decltype(std::begin(std::declval<RangeT>()))>
 329 iterator_range<pointer_iterator<WrappedIteratorT>>
 330 make_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
 336 // Wrapper iterator over iterator ItType, adding DataRef to the type of ItType,
 337 // to create NodeRef = std::pair<InnerTypeOfItType, DataRef>.
 338 template <typename ItType, typename NodeRef, typename DataRef>
 339 class WrappedPairNodeDataIterator
 340     : public iterator_adaptor_base<
 341           WrappedPairNodeDataIterator<ItType, NodeRef, DataRef>, ItType,
 342           typename std::iterator_traits<ItType>::iterator_category, NodeRef,
 343           std::ptrdiff_t, NodeRef *, NodeRef &> {
 344   using BaseT = iterator_adaptor_base<
 345       WrappedPairNodeDataIterator, ItType,
 346       typename std::iterator_traits<ItType>::iterator_category, NodeRef,
 347       std::ptrdiff_t, NodeRef *, NodeRef &>;
 348
 349   const DataRef DR;
 350   mutable NodeRef NR;
 351
 352 public:
 353   WrappedPairNodeDataIterator(ItType Begin, const DataRef DR)
 354       : BaseT(Begin), DR(DR) {
 355     NR.first = DR;
 356   }
 357
 358   NodeRef &operator*() const {
 359     NR.second = *this->I;
 360     return NR;
 361   }
 362 };
 363
 364 } // end namespace llvm
 365
 366 #endif // LLVM_ADT_ITERATOR_H