include/llvm/ADT/iterator.h

   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     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     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     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     return static_cast<DerivedT *>(this)->operator+=(1);
 125   }
 126   DerivedT operator++(int) {
 127     DerivedT tmp = *static_cast<DerivedT *>(this);
 128     ++*static_cast<DerivedT *>(this);
 129     return tmp;
 130   }
 131   DerivedT &operator--() {
 132     static_assert(
 133         IsBidirectional,
 134         "The decrement operator is only defined for bidirectional iterators.");
 135     return static_cast<DerivedT *>(this)->operator-=(1);
 136   }
 137   DerivedT operator--(int) {
 138     static_assert(
 139         IsBidirectional,
 140         "The decrement operator is only defined for bidirectional iterators.");
 141     DerivedT tmp = *static_cast<DerivedT *>(this);
 142     --*static_cast<DerivedT *>(this);
 143     return tmp;
 144   }
 145
 146   bool operator!=(const DerivedT &RHS) const {
 147     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   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   }
 163   bool operator>=(const DerivedT &RHS) const {
 164     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   PointerT operator->() { return &static_cast<DerivedT *>(this)->operator*(); }
 171   PointerT operator->() const {
 172     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     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   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   DerivedT &operator+=(difference_type n) {
 229     static_assert(
 230         BaseT::IsRandomAccess,
 231         "The '+=' operator is only defined for random access iterators.");
 232     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     I -= n;
 240     return *static_cast<DerivedT *>(this);
 241   }
 242   using BaseT::operator-;
 243   difference_type operator-(const DerivedT &RHS) const {
 244     static_assert(
 245         BaseT::IsRandomAccess,
 246         "The '-' operator is only defined for random access iterators.");
 247     return I - RHS.I;
 248   }
 249
 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   DerivedT &operator++() {
 254     ++I;
 255     return *static_cast<DerivedT *>(this);
 256   }
 257   using BaseT::operator--;
 258   DerivedT &operator--() {
 259     static_assert(
 260         BaseT::IsBidirectional,
 261         "The decrement operator is only defined for bidirectional iterators.");
 262     --I;
 263     return *static_cast<DerivedT *>(this);
 264   }
 265
 266   bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
 267   bool operator<(const DerivedT &RHS) const {
 268     static_assert(
 269         BaseT::IsRandomAccess,
 270         "Relational operators are only defined for random access iterators.");
 271     return I < RHS.I;
 272   }
 273
 274   ReferenceT operator*() const { return *I; }
 275 };
 276
 277 /// An iterator type that allows iterating over the pointees via some
 278 /// other iterator.
 279 ///
 280 /// The typical usage of this is to expose a type that iterates over Ts, but
 281 /// which is implemented with some iterator over T*s:
 282 ///
 283 /// \code
 284 ///   using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>;
 285 /// \endcode
 286 template <typename WrappedIteratorT,
 287           typename T = typename std::remove_reference<
 288               decltype(**std::declval<WrappedIteratorT>())>::type>
 289 struct pointee_iterator
 290     : iterator_adaptor_base<
 291           pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT,
 292           typename std::iterator_traits<WrappedIteratorT>::iterator_category,
 293           T> {
 294   pointee_iterator() = default;
 295   template <typename U>
 296   pointee_iterator(U &&u)
 297       : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
 298
 299   T &operator*() const { return **this->I; }
 300 };
 301
 302 template <typename RangeT, typename WrappedIteratorT =
 303                                decltype(std::begin(std::declval<RangeT>()))>
 304 iterator_range<pointee_iterator<WrappedIteratorT>>
 305 make_pointee_range(RangeT &&Range) {
 306   using PointeeIteratorT = pointee_iterator<WrappedIteratorT>;
 307   return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))),
 308                     PointeeIteratorT(std::end(std::forward<RangeT>(Range))));
 309 }
 310
 311 template <typename WrappedIteratorT,
 312           typename T = decltype(&*std::declval<WrappedIteratorT>())>
 313 class pointer_iterator
 314     : public iterator_adaptor_base<pointer_iterator<WrappedIteratorT, T>,
 315                                    WrappedIteratorT, T> {
 316   mutable T Ptr;
 317
 318 public:
 319   pointer_iterator() = default;
 320
 321   explicit pointer_iterator(WrappedIteratorT u)
 322       : pointer_iterator::iterator_adaptor_base(std::move(u)) {}
 323
 324   T &operator*() { return Ptr = &*this->I; }
 325   const T &operator*() const { return Ptr = &*this->I; }
 326 };
 327
 328 template <typename RangeT, typename WrappedIteratorT =
 329                                decltype(std::begin(std::declval<RangeT>()))>
 330 iterator_range<pointer_iterator<WrappedIteratorT>>
 331 make_pointer_range(RangeT &&Range) {
 332   using PointerIteratorT = pointer_iterator<WrappedIteratorT>;
 333   return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))),
 334                     PointerIteratorT(std::end(std::forward<RangeT>(Range))));
 335 }
 336
 337 } // end namespace llvm
 338
 339 #endif // LLVM_ADT_ITERATOR_H