contrib/llvm/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 class iterator_adaptor_base
 207     : public iterator_facade_base<DerivedT, IteratorCategoryT, T,
 208                                   DifferenceTypeT, PointerT, ReferenceT> {
 209   using BaseT = typename iterator_adaptor_base::iterator_facade_base;
 210
 211 protected:
 212   WrappedIteratorT I;
 213
 214   iterator_adaptor_base() = default;
 215
 216   explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) {
 217     static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value,
 218                   "Must pass the derived type to this template!");
 219   }
 220
 221   const WrappedIteratorT &wrapped() const { return I; }
 222
 223 public:
 224   using difference_type = DifferenceTypeT;
 225
 226   DerivedT &operator+=(difference_type n) {
 227     static_assert(
 228         BaseT::IsRandomAccess,
 229         "The '+=' operator is only defined for random access iterators.");
 230     I += n;
 231     return *static_cast<DerivedT *>(this);
 232   }
 233   DerivedT &operator-=(difference_type n) {
 234     static_assert(
 235         BaseT::IsRandomAccess,
 236         "The '-=' operator is only defined for random access iterators.");
 237     I -= n;
 238     return *static_cast<DerivedT *>(this);
 239   }
 240   using BaseT::operator-;
 241   difference_type operator-(const DerivedT &RHS) const {
 242     static_assert(
 243         BaseT::IsRandomAccess,
 244         "The '-' operator is only defined for random access iterators.");
 245     return I - RHS.I;
 246   }
 247
 248   // We have to explicitly provide ++ and -- rather than letting the facade
 249   // forward to += because WrappedIteratorT might not support +=.
 250   using BaseT::operator++;
 251   DerivedT &operator++() {
 252     ++I;
 253     return *static_cast<DerivedT *>(this);
 254   }
 255   using BaseT::operator--;
 256   DerivedT &operator--() {
 257     static_assert(
 258         BaseT::IsBidirectional,
 259         "The decrement operator is only defined for bidirectional iterators.");
 260     --I;
 261     return *static_cast<DerivedT *>(this);
 262   }
 263
 264   bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
 265   bool operator<(const DerivedT &RHS) const {
 266     static_assert(
 267         BaseT::IsRandomAccess,
 268         "Relational operators are only defined for random access iterators.");
 269     return I < RHS.I;
 270   }
 271
 272   ReferenceT operator*() const { return *I; }
 273 };
 274
 275 /// An iterator type that allows iterating over the pointees via some
 276 /// other iterator.
 277 ///
 278 /// The typical usage of this is to expose a type that iterates over Ts, but
 279 /// which is implemented with some iterator over T*s:
 280 ///
 281 /// \code
 282 ///   using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>;
 283 /// \endcode
 284 template <typename WrappedIteratorT,
 285           typename T = typename std::remove_reference<
 286               decltype(**std::declval<WrappedIteratorT>())>::type>
 287 struct pointee_iterator
 288     : iterator_adaptor_base<
 289           pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT,
 290           typename std::iterator_traits<WrappedIteratorT>::iterator_category,
 291           T> {
 292   pointee_iterator() = default;
 293   template <typename U>
 294   pointee_iterator(U &&u)
 295       : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
 296
 297   T &operator*() const { return **this->I; }
 298 };
 299
 300 template <typename RangeT, typename WrappedIteratorT =
 301                                decltype(std::begin(std::declval<RangeT>()))>
 302 iterator_range<pointee_iterator<WrappedIteratorT>>
 303 make_pointee_range(RangeT &&Range) {
 304   using PointeeIteratorT = pointee_iterator<WrappedIteratorT>;
 305   return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))),
 306                     PointeeIteratorT(std::end(std::forward<RangeT>(Range))));
 307 }
 308
 309 template <typename WrappedIteratorT,
 310           typename T = decltype(&*std::declval<WrappedIteratorT>())>
 311 class pointer_iterator
 312     : public iterator_adaptor_base<
 313           pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT,
 314           typename std::iterator_traits<WrappedIteratorT>::iterator_category,
 315           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 // Wrapper iterator over iterator ItType, adding DataRef to the type of ItType,
 338 // to create NodeRef = std::pair<InnerTypeOfItType, DataRef>.
 339 template <typename ItType, typename NodeRef, typename DataRef>
 340 class WrappedPairNodeDataIterator
 341     : public iterator_adaptor_base<
 342           WrappedPairNodeDataIterator<ItType, NodeRef, DataRef>, ItType,
 343           typename std::iterator_traits<ItType>::iterator_category, NodeRef,
 344           std::ptrdiff_t, NodeRef *, NodeRef &> {
 345   using BaseT = iterator_adaptor_base<
 346       WrappedPairNodeDataIterator, ItType,
 347       typename std::iterator_traits<ItType>::iterator_category, NodeRef,
 348       std::ptrdiff_t, NodeRef *, NodeRef &>;
 349
 350   const DataRef DR;
 351   mutable NodeRef NR;
 352
 353 public:
 354   WrappedPairNodeDataIterator(ItType Begin, const DataRef DR)
 355       : BaseT(Begin), DR(DR) {
 356     NR.first = DR;
 357   }
 358
 359   NodeRef &operator*() const {
 360     NR.second = *this->I;
 361     return NR;
 362   }
 363 };
 364
 365 } // end namespace llvm
 366
 367 #endif // LLVM_ADT_ITERATOR_H