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 18namespace 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/// 63template <typename DerivedT, typename IteratorCategoryT, typename T, 64 typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *, 65 typename ReferenceT = T &> 66class iterator_facade_base { 67public: 68 using iterator_category = IteratorCategoryT; 69 using value_type = T; 70 using difference_type = DifferenceTypeT; 71 using pointer = PointerT; 72 using reference = ReferenceT; 73 74protected: 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 98public: 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. 196template < 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 &>> 211class 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 216protected: 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 228public: 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 293template <typename WrappedIteratorT, 294 typename T = std::remove_reference_t<decltype( 295 **std::declval<WrappedIteratorT>())>> 296struct 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 309template <typename RangeT, typename WrappedIteratorT = 310 decltype(std::begin(std::declval<RangeT>()))> 311iterator_range<pointee_iterator<WrappedIteratorT>> 312make_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 318template <typename WrappedIteratorT, 319 typename T = decltype(&*std::declval<WrappedIteratorT>())> 320class 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 327public: 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 337template <typename RangeT, typename WrappedIteratorT = 338 decltype(std::begin(std::declval<RangeT>()))> 339iterator_range<pointer_iterator<WrappedIteratorT>> 340make_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 346template <typename WrappedIteratorT, 347 typename T1 = std::remove_reference_t<decltype( 348 **std::declval<WrappedIteratorT>())>, 349 typename T2 = std::add_pointer_t<T1>> 350using raw_pointer_iterator = 351 pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>; 352 353// Wrapper iterator over iterator ItType, adding DataRef to the type of ItType, 354// to create NodeRef = std::pair<InnerTypeOfItType, DataRef>. 355template <typename ItType, typename NodeRef, typename DataRef> 356class WrappedPairNodeDataIterator 357 : public iterator_adaptor_base< 358 WrappedPairNodeDataIterator<ItType, NodeRef, DataRef>, ItType, 359 typename std::iterator_traits<ItType>::iterator_category, NodeRef, 360 std::ptrdiff_t, NodeRef *, NodeRef &> { 361 using BaseT = iterator_adaptor_base< 362 WrappedPairNodeDataIterator, ItType, 363 typename std::iterator_traits<ItType>::iterator_category, NodeRef, 364 std::ptrdiff_t, NodeRef *, NodeRef &>; 365 366 const DataRef DR; 367 mutable NodeRef NR; 368 369public: 370 WrappedPairNodeDataIterator(ItType Begin, const DataRef DR) 371 : BaseT(Begin), DR(DR) { 372 NR.first = DR; 373 } 374 375 NodeRef &operator*() const { 376 NR.second = *this->I; 377 return NR; 378 } 379}; 380 381} // end namespace llvm 382 383#endif // LLVM_ADT_ITERATOR_H 384