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 <cstddef> 15 #include <iterator> 16 #include <type_traits> 17 18 namespace llvm { 19 20 /// \brief 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 /// 63 template <typename DerivedT, typename IteratorCategoryT, typename T, 64 typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *, 65 typename ReferenceT = T &> 66 class iterator_facade_base 67 : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT, 68 ReferenceT> { 69 protected: 70 enum { 71 IsRandomAccess = 72 std::is_base_of<std::random_access_iterator_tag, IteratorCategoryT>::value, 73 IsBidirectional = 74 std::is_base_of<std::bidirectional_iterator_tag, IteratorCategoryT>::value, 75 }; 76 77 /// A proxy object for computing a reference via indirecting a copy of an 78 /// iterator. This is used in APIs which need to produce a reference via 79 /// indirection but for which the iterator object might be a temporary. The 80 /// proxy preserves the iterator internally and exposes the indirected 81 /// reference via a conversion operator. 82 class ReferenceProxy { 83 friend iterator_facade_base; 84 85 DerivedT I; 86 87 ReferenceProxy(DerivedT I) : I(std::move(I)) {} 88 89 public: 90 operator ReferenceT() const { return *I; } 91 }; 92 93 public: 94 DerivedT operator+(DifferenceTypeT n) const { 95 static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, 96 "Must pass the derived type to this template!"); 97 static_assert( 98 IsRandomAccess, 99 "The '+' operator is only defined for random access iterators."); 100 DerivedT tmp = *static_cast<const DerivedT *>(this); 101 tmp += n; 102 return tmp; 103 } 104 friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) { 105 static_assert( 106 IsRandomAccess, 107 "The '+' operator is only defined for random access iterators."); 108 return i + n; 109 } 110 DerivedT operator-(DifferenceTypeT n) const { 111 static_assert( 112 IsRandomAccess, 113 "The '-' operator is only defined for random access iterators."); 114 DerivedT tmp = *static_cast<const DerivedT *>(this); 115 tmp -= n; 116 return tmp; 117 } 118 119 DerivedT &operator++() { 120 static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, 121 "Must pass the derived type to this template!"); 122 return static_cast<DerivedT *>(this)->operator+=(1); 123 } 124 DerivedT operator++(int) { 125 DerivedT tmp = *static_cast<DerivedT *>(this); 126 ++*static_cast<DerivedT *>(this); 127 return tmp; 128 } 129 DerivedT &operator--() { 130 static_assert( 131 IsBidirectional, 132 "The decrement operator is only defined for bidirectional iterators."); 133 return static_cast<DerivedT *>(this)->operator-=(1); 134 } 135 DerivedT operator--(int) { 136 static_assert( 137 IsBidirectional, 138 "The decrement operator is only defined for bidirectional iterators."); 139 DerivedT tmp = *static_cast<DerivedT *>(this); 140 --*static_cast<DerivedT *>(this); 141 return tmp; 142 } 143 144 bool operator!=(const DerivedT &RHS) const { 145 return !static_cast<const DerivedT *>(this)->operator==(RHS); 146 } 147 148 bool operator>(const DerivedT &RHS) const { 149 static_assert( 150 IsRandomAccess, 151 "Relational operators are only defined for random access iterators."); 152 return !static_cast<const DerivedT *>(this)->operator<(RHS) && 153 !static_cast<const DerivedT *>(this)->operator==(RHS); 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)->operator>(RHS); 160 } 161 bool operator>=(const DerivedT &RHS) const { 162 static_assert( 163 IsRandomAccess, 164 "Relational operators are only defined for random access iterators."); 165 return !static_cast<const DerivedT *>(this)->operator<(RHS); 166 } 167 168 PointerT operator->() { return &static_cast<DerivedT *>(this)->operator*(); } 169 PointerT operator->() const { 170 return &static_cast<const DerivedT *>(this)->operator*(); 171 } 172 ReferenceProxy operator[](DifferenceTypeT n) { 173 static_assert(IsRandomAccess, 174 "Subscripting is only defined for random access iterators."); 175 return ReferenceProxy(static_cast<DerivedT *>(this)->operator+(n)); 176 } 177 ReferenceProxy operator[](DifferenceTypeT n) const { 178 static_assert(IsRandomAccess, 179 "Subscripting is only defined for random access iterators."); 180 return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n)); 181 } 182 }; 183 184 /// \brief CRTP base class for adapting an iterator to a different type. 185 /// 186 /// This class can be used through CRTP to adapt one iterator into another. 187 /// Typically this is done through providing in the derived class a custom \c 188 /// operator* implementation. Other methods can be overridden as well. 189 template < 190 typename DerivedT, typename WrappedIteratorT, 191 typename IteratorCategoryT = 192 typename std::iterator_traits<WrappedIteratorT>::iterator_category, 193 typename T = typename std::iterator_traits<WrappedIteratorT>::value_type, 194 typename DifferenceTypeT = 195 typename std::iterator_traits<WrappedIteratorT>::difference_type, 196 typename PointerT = typename std::conditional< 197 std::is_same<T, typename std::iterator_traits< 198 WrappedIteratorT>::value_type>::value, 199 typename std::iterator_traits<WrappedIteratorT>::pointer, T *>::type, 200 typename ReferenceT = typename std::conditional< 201 std::is_same<T, typename std::iterator_traits< 202 WrappedIteratorT>::value_type>::value, 203 typename std::iterator_traits<WrappedIteratorT>::reference, T &>::type, 204 // Don't provide these, they are mostly to act as aliases below. 205 typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>> 206 class iterator_adaptor_base 207 : public iterator_facade_base<DerivedT, IteratorCategoryT, T, 208 DifferenceTypeT, PointerT, ReferenceT> { 209 typedef typename iterator_adaptor_base::iterator_facade_base BaseT; 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 typedef DifferenceTypeT difference_type; 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 /// \brief 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 /// typedef pointee_iterator<SmallVectorImpl<T *>::iterator> 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>, 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<pointer_iterator<WrappedIteratorT>, 313 WrappedIteratorT, T> { 314 mutable T Ptr; 315 316 public: 317 pointer_iterator() = default; 318 319 explicit pointer_iterator(WrappedIteratorT u) 320 : pointer_iterator::iterator_adaptor_base(std::move(u)) {} 321 322 T &operator*() { return Ptr = &*this->I; } 323 const T &operator*() const { return Ptr = &*this->I; } 324 }; 325 326 template <typename RangeT, typename WrappedIteratorT = 327 decltype(std::begin(std::declval<RangeT>()))> 328 iterator_range<pointer_iterator<WrappedIteratorT>> 329 make_pointer_range(RangeT &&Range) { 330 using PointerIteratorT = pointer_iterator<WrappedIteratorT>; 331 return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))), 332 PointerIteratorT(std::end(std::forward<RangeT>(Range)))); 333 } 334 335 } // end namespace llvm 336 337 #endif // LLVM_ADT_ITERATOR_H 338