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 <cstddef> 14 #include <iterator> 15 #include <type_traits> 16 #include <utility> 17 18 namespace llvm { 19 20 /// 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: 68 using iterator_category = IteratorCategoryT; 69 using value_type = T; 70 using difference_type = DifferenceTypeT; 71 using pointer = PointerT; 72 using reference = ReferenceT; 73 74 protected: 75 enum { 76 IsRandomAccess = std::is_base_of<std::random_access_iterator_tag, 77 IteratorCategoryT>::value, 78 IsBidirectional = std::is_base_of<std::bidirectional_iterator_tag, 79 IteratorCategoryT>::value, 80 }; 81 82 /// A proxy object for computing a reference via indirecting a copy of an 83 /// iterator. This is used in APIs which need to produce a reference via 84 /// indirection but for which the iterator object might be a temporary. The 85 /// proxy preserves the iterator internally and exposes the indirected 86 /// reference via a conversion operator. 87 class ReferenceProxy { 88 friend iterator_facade_base; 89 90 DerivedT I; 91 92 ReferenceProxy(DerivedT I) : I(std::move(I)) {} 93 94 public: 95 operator ReferenceT() const { return *I; } 96 }; 97 98 public: 99 DerivedT operator+(DifferenceTypeT n) const { 100 static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, 101 "Must pass the derived type to this template!"); 102 static_assert( 103 IsRandomAccess, 104 "The '+' operator is only defined for random access iterators."); 105 DerivedT tmp = *static_cast<const DerivedT *>(this); 106 tmp += n; 107 return tmp; 108 } 109 friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) { 110 static_assert( 111 IsRandomAccess, 112 "The '+' operator is only defined for random access iterators."); 113 return i + n; 114 } 115 DerivedT operator-(DifferenceTypeT n) const { 116 static_assert( 117 IsRandomAccess, 118 "The '-' operator is only defined for random access iterators."); 119 DerivedT tmp = *static_cast<const DerivedT *>(this); 120 tmp -= n; 121 return tmp; 122 } 123 124 DerivedT &operator++() { 125 static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, 126 "Must pass the derived type to this template!"); 127 return static_cast<DerivedT *>(this)->operator+=(1); 128 } 129 DerivedT operator++(int) { 130 DerivedT tmp = *static_cast<DerivedT *>(this); 131 ++*static_cast<DerivedT *>(this); 132 return tmp; 133 } 134 DerivedT &operator--() { 135 static_assert( 136 IsBidirectional, 137 "The decrement operator is only defined for bidirectional iterators."); 138 return static_cast<DerivedT *>(this)->operator-=(1); 139 } 140 DerivedT operator--(int) { 141 static_assert( 142 IsBidirectional, 143 "The decrement operator is only defined for bidirectional iterators."); 144 DerivedT tmp = *static_cast<DerivedT *>(this); 145 --*static_cast<DerivedT *>(this); 146 return tmp; 147 } 148 149 #ifndef __cpp_impl_three_way_comparison 150 bool operator!=(const DerivedT &RHS) const { 151 return !(static_cast<const DerivedT &>(*this) == RHS); 152 } 153 #endif 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) < RHS) && 160 !(static_cast<const DerivedT &>(*this) == 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) > RHS); 167 } 168 bool operator>=(const DerivedT &RHS) const { 169 static_assert( 170 IsRandomAccess, 171 "Relational operators are only defined for random access iterators."); 172 return !(static_cast<const DerivedT &>(*this) < RHS); 173 } 174 175 PointerT operator->() { return &static_cast<DerivedT *>(this)->operator*(); } 176 PointerT operator->() const { 177 return &static_cast<const DerivedT *>(this)->operator*(); 178 } 179 ReferenceProxy operator[](DifferenceTypeT n) { 180 static_assert(IsRandomAccess, 181 "Subscripting is only defined for random access iterators."); 182 return ReferenceProxy(static_cast<DerivedT *>(this)->operator+(n)); 183 } 184 ReferenceProxy operator[](DifferenceTypeT n) const { 185 static_assert(IsRandomAccess, 186 "Subscripting is only defined for random access iterators."); 187 return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n)); 188 } 189 }; 190 191 /// CRTP base class for adapting an iterator to a different type. 192 /// 193 /// This class can be used through CRTP to adapt one iterator into another. 194 /// Typically this is done through providing in the derived class a custom \c 195 /// operator* implementation. Other methods can be overridden as well. 196 template < 197 typename DerivedT, typename WrappedIteratorT, 198 typename IteratorCategoryT = 199 typename std::iterator_traits<WrappedIteratorT>::iterator_category, 200 typename T = typename std::iterator_traits<WrappedIteratorT>::value_type, 201 typename DifferenceTypeT = 202 typename std::iterator_traits<WrappedIteratorT>::difference_type, 203 typename PointerT = std::conditional_t< 204 std::is_same<T, typename std::iterator_traits< 205 WrappedIteratorT>::value_type>::value, 206 typename std::iterator_traits<WrappedIteratorT>::pointer, T *>, 207 typename ReferenceT = std::conditional_t< 208 std::is_same<T, typename std::iterator_traits< 209 WrappedIteratorT>::value_type>::value, 210 typename std::iterator_traits<WrappedIteratorT>::reference, T &>> 211 class iterator_adaptor_base 212 : public iterator_facade_base<DerivedT, IteratorCategoryT, T, 213 DifferenceTypeT, PointerT, ReferenceT> { 214 using BaseT = typename iterator_adaptor_base::iterator_facade_base; 215 216 protected: 217 WrappedIteratorT I; 218 219 iterator_adaptor_base() = default; 220 221 explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) { 222 static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value, 223 "Must pass the derived type to this template!"); 224 } 225 226 const WrappedIteratorT &wrapped() const { return I; } 227 228 public: 229 using difference_type = DifferenceTypeT; 230 231 DerivedT &operator+=(difference_type n) { 232 static_assert( 233 BaseT::IsRandomAccess, 234 "The '+=' operator is only defined for random access iterators."); 235 I += n; 236 return *static_cast<DerivedT *>(this); 237 } 238 DerivedT &operator-=(difference_type n) { 239 static_assert( 240 BaseT::IsRandomAccess, 241 "The '-=' operator is only defined for random access iterators."); 242 I -= n; 243 return *static_cast<DerivedT *>(this); 244 } 245 using BaseT::operator-; 246 difference_type operator-(const DerivedT &RHS) const { 247 static_assert( 248 BaseT::IsRandomAccess, 249 "The '-' operator is only defined for random access iterators."); 250 return I - RHS.I; 251 } 252 253 // We have to explicitly provide ++ and -- rather than letting the facade 254 // forward to += because WrappedIteratorT might not support +=. 255 using BaseT::operator++; 256 DerivedT &operator++() { 257 ++I; 258 return *static_cast<DerivedT *>(this); 259 } 260 using BaseT::operator--; 261 DerivedT &operator--() { 262 static_assert( 263 BaseT::IsBidirectional, 264 "The decrement operator is only defined for bidirectional iterators."); 265 --I; 266 return *static_cast<DerivedT *>(this); 267 } 268 269 friend bool operator==(const iterator_adaptor_base &LHS, 270 const iterator_adaptor_base &RHS) { 271 return LHS.I == RHS.I; 272 } 273 friend bool operator<(const iterator_adaptor_base &LHS, 274 const iterator_adaptor_base &RHS) { 275 static_assert( 276 BaseT::IsRandomAccess, 277 "Relational operators are only defined for random access iterators."); 278 return LHS.I < RHS.I; 279 } 280 281 ReferenceT operator*() const { return *I; } 282 }; 283 284 /// An iterator type that allows iterating over the pointees via some 285 /// other iterator. 286 /// 287 /// The typical usage of this is to expose a type that iterates over Ts, but 288 /// which is implemented with some iterator over T*s: 289 /// 290 /// \code 291 /// using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>; 292 /// \endcode 293 template <typename WrappedIteratorT, 294 typename T = std::remove_reference_t<decltype( 295 **std::declval<WrappedIteratorT>())>> 296 struct pointee_iterator 297 : iterator_adaptor_base< 298 pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT, 299 typename std::iterator_traits<WrappedIteratorT>::iterator_category, 300 T> { 301 pointee_iterator() = default; 302 template <typename U> 303 pointee_iterator(U &&u) 304 : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {} 305 306 T &operator*() const { return **this->I; } 307 }; 308 309 template <typename RangeT, typename WrappedIteratorT = 310 decltype(std::begin(std::declval<RangeT>()))> 311 iterator_range<pointee_iterator<WrappedIteratorT>> 312 make_pointee_range(RangeT &&Range) { 313 using PointeeIteratorT = pointee_iterator<WrappedIteratorT>; 314 return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))), 315 PointeeIteratorT(std::end(std::forward<RangeT>(Range)))); 316 } 317 318 template <typename WrappedIteratorT, 319 typename T = decltype(&*std::declval<WrappedIteratorT>())> 320 class pointer_iterator 321 : public iterator_adaptor_base< 322 pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT, 323 typename std::iterator_traits<WrappedIteratorT>::iterator_category, 324 T> { 325 mutable T Ptr; 326 327 public: 328 pointer_iterator() = default; 329 330 explicit pointer_iterator(WrappedIteratorT u) 331 : pointer_iterator::iterator_adaptor_base(std::move(u)) {} 332 333 T &operator*() { return Ptr = &*this->I; } 334 const T &operator*() const { return Ptr = &*this->I; } 335 }; 336 337 template <typename RangeT, typename WrappedIteratorT = 338 decltype(std::begin(std::declval<RangeT>()))> 339 iterator_range<pointer_iterator<WrappedIteratorT>> 340 make_pointer_range(RangeT &&Range) { 341 using PointerIteratorT = pointer_iterator<WrappedIteratorT>; 342 return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))), 343 PointerIteratorT(std::end(std::forward<RangeT>(Range)))); 344 } 345 346 template <typename WrappedIteratorT, 347 typename T1 = std::remove_reference_t<decltype( 348 **std::declval<WrappedIteratorT>())>, 349 typename T2 = std::add_pointer_t<T1>> 350 using raw_pointer_iterator = 351 pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>; 352 353 } // end namespace llvm 354 355 #endif // LLVM_ADT_ITERATOR_H 356