1274955Ssvnmir//===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===// 2274955Ssvnmir// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6274955Ssvnmir// 7274955Ssvnmir//===----------------------------------------------------------------------===// 8274955Ssvnmir 9274955Ssvnmir#ifndef LLVM_ADT_ITERATOR_H 10274955Ssvnmir#define LLVM_ADT_ITERATOR_H 11274955Ssvnmir 12321369Sdim#include "llvm/ADT/iterator_range.h" 13321369Sdim#include <algorithm> 14280031Sdim#include <cstddef> 15274955Ssvnmir#include <iterator> 16314564Sdim#include <type_traits> 17321369Sdim#include <utility> 18274955Ssvnmir 19274955Ssvnmirnamespace llvm { 20274955Ssvnmir 21341825Sdim/// CRTP base class which implements the entire standard iterator facade 22274955Ssvnmir/// in terms of a minimal subset of the interface. 23274955Ssvnmir/// 24274955Ssvnmir/// Use this when it is reasonable to implement most of the iterator 25274955Ssvnmir/// functionality in terms of a core subset. If you need special behavior or 26274955Ssvnmir/// there are performance implications for this, you may want to override the 27274955Ssvnmir/// relevant members instead. 28274955Ssvnmir/// 29274955Ssvnmir/// Note, one abstraction that this does *not* provide is implementing 30274955Ssvnmir/// subtraction in terms of addition by negating the difference. Negation isn't 31274955Ssvnmir/// always information preserving, and I can see very reasonable iterator 32274955Ssvnmir/// designs where this doesn't work well. It doesn't really force much added 33274955Ssvnmir/// boilerplate anyways. 34274955Ssvnmir/// 35274955Ssvnmir/// Another abstraction that this doesn't provide is implementing increment in 36274955Ssvnmir/// terms of addition of one. These aren't equivalent for all iterator 37274955Ssvnmir/// categories, and respecting that adds a lot of complexity for little gain. 38314564Sdim/// 39314564Sdim/// Classes wishing to use `iterator_facade_base` should implement the following 40314564Sdim/// methods: 41314564Sdim/// 42314564Sdim/// Forward Iterators: 43314564Sdim/// (All of the following methods) 44314564Sdim/// - DerivedT &operator=(const DerivedT &R); 45314564Sdim/// - bool operator==(const DerivedT &R) const; 46314564Sdim/// - const T &operator*() const; 47314564Sdim/// - T &operator*(); 48314564Sdim/// - DerivedT &operator++(); 49314564Sdim/// 50314564Sdim/// Bidirectional Iterators: 51314564Sdim/// (All methods of forward iterators, plus the following) 52314564Sdim/// - DerivedT &operator--(); 53314564Sdim/// 54314564Sdim/// Random-access Iterators: 55314564Sdim/// (All methods of bidirectional iterators excluding the following) 56314564Sdim/// - DerivedT &operator++(); 57314564Sdim/// - DerivedT &operator--(); 58314564Sdim/// (and plus the following) 59314564Sdim/// - bool operator<(const DerivedT &RHS) const; 60314564Sdim/// - DifferenceTypeT operator-(const DerivedT &R) const; 61314564Sdim/// - DerivedT &operator+=(DifferenceTypeT N); 62314564Sdim/// - DerivedT &operator-=(DifferenceTypeT N); 63314564Sdim/// 64274955Ssvnmirtemplate <typename DerivedT, typename IteratorCategoryT, typename T, 65274955Ssvnmir typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *, 66274955Ssvnmir typename ReferenceT = T &> 67274955Ssvnmirclass iterator_facade_base 68274955Ssvnmir : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT, 69274955Ssvnmir ReferenceT> { 70274955Ssvnmirprotected: 71274955Ssvnmir enum { 72327952Sdim IsRandomAccess = std::is_base_of<std::random_access_iterator_tag, 73327952Sdim IteratorCategoryT>::value, 74327952Sdim IsBidirectional = std::is_base_of<std::bidirectional_iterator_tag, 75327952Sdim IteratorCategoryT>::value, 76274955Ssvnmir }; 77274955Ssvnmir 78309124Sdim /// A proxy object for computing a reference via indirecting a copy of an 79309124Sdim /// iterator. This is used in APIs which need to produce a reference via 80309124Sdim /// indirection but for which the iterator object might be a temporary. The 81309124Sdim /// proxy preserves the iterator internally and exposes the indirected 82309124Sdim /// reference via a conversion operator. 83309124Sdim class ReferenceProxy { 84309124Sdim friend iterator_facade_base; 85309124Sdim 86309124Sdim DerivedT I; 87309124Sdim 88309124Sdim ReferenceProxy(DerivedT I) : I(std::move(I)) {} 89309124Sdim 90309124Sdim public: 91309124Sdim operator ReferenceT() const { return *I; } 92309124Sdim }; 93309124Sdim 94274955Ssvnmirpublic: 95274955Ssvnmir DerivedT operator+(DifferenceTypeT n) const { 96321369Sdim static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, 97321369Sdim "Must pass the derived type to this template!"); 98274955Ssvnmir static_assert( 99274955Ssvnmir IsRandomAccess, 100274955Ssvnmir "The '+' operator is only defined for random access iterators."); 101274955Ssvnmir DerivedT tmp = *static_cast<const DerivedT *>(this); 102274955Ssvnmir tmp += n; 103274955Ssvnmir return tmp; 104274955Ssvnmir } 105274955Ssvnmir friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) { 106274955Ssvnmir static_assert( 107274955Ssvnmir IsRandomAccess, 108274955Ssvnmir "The '+' operator is only defined for random access iterators."); 109274955Ssvnmir return i + n; 110274955Ssvnmir } 111274955Ssvnmir DerivedT operator-(DifferenceTypeT n) const { 112274955Ssvnmir static_assert( 113274955Ssvnmir IsRandomAccess, 114274955Ssvnmir "The '-' operator is only defined for random access iterators."); 115274955Ssvnmir DerivedT tmp = *static_cast<const DerivedT *>(this); 116274955Ssvnmir tmp -= n; 117274955Ssvnmir return tmp; 118274955Ssvnmir } 119274955Ssvnmir 120274955Ssvnmir DerivedT &operator++() { 121321369Sdim static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, 122321369Sdim "Must pass the derived type to this template!"); 123274955Ssvnmir return static_cast<DerivedT *>(this)->operator+=(1); 124274955Ssvnmir } 125274955Ssvnmir DerivedT operator++(int) { 126274955Ssvnmir DerivedT tmp = *static_cast<DerivedT *>(this); 127274955Ssvnmir ++*static_cast<DerivedT *>(this); 128274955Ssvnmir return tmp; 129274955Ssvnmir } 130274955Ssvnmir DerivedT &operator--() { 131274955Ssvnmir static_assert( 132274955Ssvnmir IsBidirectional, 133274955Ssvnmir "The decrement operator is only defined for bidirectional iterators."); 134274955Ssvnmir return static_cast<DerivedT *>(this)->operator-=(1); 135274955Ssvnmir } 136274955Ssvnmir DerivedT operator--(int) { 137274955Ssvnmir static_assert( 138274955Ssvnmir IsBidirectional, 139274955Ssvnmir "The decrement operator is only defined for bidirectional iterators."); 140274955Ssvnmir DerivedT tmp = *static_cast<DerivedT *>(this); 141274955Ssvnmir --*static_cast<DerivedT *>(this); 142274955Ssvnmir return tmp; 143274955Ssvnmir } 144274955Ssvnmir 145274955Ssvnmir bool operator!=(const DerivedT &RHS) const { 146274955Ssvnmir return !static_cast<const DerivedT *>(this)->operator==(RHS); 147274955Ssvnmir } 148274955Ssvnmir 149274955Ssvnmir bool operator>(const DerivedT &RHS) const { 150274955Ssvnmir static_assert( 151274955Ssvnmir IsRandomAccess, 152274955Ssvnmir "Relational operators are only defined for random access iterators."); 153274955Ssvnmir return !static_cast<const DerivedT *>(this)->operator<(RHS) && 154274955Ssvnmir !static_cast<const DerivedT *>(this)->operator==(RHS); 155274955Ssvnmir } 156274955Ssvnmir bool operator<=(const DerivedT &RHS) const { 157274955Ssvnmir static_assert( 158274955Ssvnmir IsRandomAccess, 159274955Ssvnmir "Relational operators are only defined for random access iterators."); 160274955Ssvnmir return !static_cast<const DerivedT *>(this)->operator>(RHS); 161274955Ssvnmir } 162274955Ssvnmir bool operator>=(const DerivedT &RHS) const { 163274955Ssvnmir static_assert( 164274955Ssvnmir IsRandomAccess, 165274955Ssvnmir "Relational operators are only defined for random access iterators."); 166274955Ssvnmir return !static_cast<const DerivedT *>(this)->operator<(RHS); 167274955Ssvnmir } 168274955Ssvnmir 169321369Sdim PointerT operator->() { return &static_cast<DerivedT *>(this)->operator*(); } 170274955Ssvnmir PointerT operator->() const { 171274955Ssvnmir return &static_cast<const DerivedT *>(this)->operator*(); 172274955Ssvnmir } 173321369Sdim ReferenceProxy operator[](DifferenceTypeT n) { 174321369Sdim static_assert(IsRandomAccess, 175321369Sdim "Subscripting is only defined for random access iterators."); 176321369Sdim return ReferenceProxy(static_cast<DerivedT *>(this)->operator+(n)); 177321369Sdim } 178309124Sdim ReferenceProxy operator[](DifferenceTypeT n) const { 179274955Ssvnmir static_assert(IsRandomAccess, 180274955Ssvnmir "Subscripting is only defined for random access iterators."); 181309124Sdim return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n)); 182274955Ssvnmir } 183274955Ssvnmir}; 184274955Ssvnmir 185341825Sdim/// CRTP base class for adapting an iterator to a different type. 186274955Ssvnmir/// 187274955Ssvnmir/// This class can be used through CRTP to adapt one iterator into another. 188274955Ssvnmir/// Typically this is done through providing in the derived class a custom \c 189274955Ssvnmir/// operator* implementation. Other methods can be overridden as well. 190274955Ssvnmirtemplate < 191274955Ssvnmir typename DerivedT, typename WrappedIteratorT, 192274955Ssvnmir typename IteratorCategoryT = 193274955Ssvnmir typename std::iterator_traits<WrappedIteratorT>::iterator_category, 194274955Ssvnmir typename T = typename std::iterator_traits<WrappedIteratorT>::value_type, 195274955Ssvnmir typename DifferenceTypeT = 196274955Ssvnmir typename std::iterator_traits<WrappedIteratorT>::difference_type, 197309124Sdim typename PointerT = typename std::conditional< 198309124Sdim std::is_same<T, typename std::iterator_traits< 199309124Sdim WrappedIteratorT>::value_type>::value, 200309124Sdim typename std::iterator_traits<WrappedIteratorT>::pointer, T *>::type, 201309124Sdim typename ReferenceT = typename std::conditional< 202309124Sdim std::is_same<T, typename std::iterator_traits< 203309124Sdim WrappedIteratorT>::value_type>::value, 204344779Sdim typename std::iterator_traits<WrappedIteratorT>::reference, T &>::type> 205274955Ssvnmirclass iterator_adaptor_base 206274955Ssvnmir : public iterator_facade_base<DerivedT, IteratorCategoryT, T, 207274955Ssvnmir DifferenceTypeT, PointerT, ReferenceT> { 208321369Sdim using BaseT = typename iterator_adaptor_base::iterator_facade_base; 209274955Ssvnmir 210274955Ssvnmirprotected: 211274955Ssvnmir WrappedIteratorT I; 212274955Ssvnmir 213288943Sdim iterator_adaptor_base() = default; 214274955Ssvnmir 215321369Sdim explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) { 216321369Sdim static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value, 217321369Sdim "Must pass the derived type to this template!"); 218321369Sdim } 219274955Ssvnmir 220288943Sdim const WrappedIteratorT &wrapped() const { return I; } 221288943Sdim 222274955Ssvnmirpublic: 223321369Sdim using difference_type = DifferenceTypeT; 224274955Ssvnmir 225274955Ssvnmir DerivedT &operator+=(difference_type n) { 226274955Ssvnmir static_assert( 227274955Ssvnmir BaseT::IsRandomAccess, 228274955Ssvnmir "The '+=' operator is only defined for random access iterators."); 229274955Ssvnmir I += n; 230274955Ssvnmir return *static_cast<DerivedT *>(this); 231274955Ssvnmir } 232274955Ssvnmir DerivedT &operator-=(difference_type n) { 233274955Ssvnmir static_assert( 234274955Ssvnmir BaseT::IsRandomAccess, 235274955Ssvnmir "The '-=' operator is only defined for random access iterators."); 236274955Ssvnmir I -= n; 237274955Ssvnmir return *static_cast<DerivedT *>(this); 238274955Ssvnmir } 239274955Ssvnmir using BaseT::operator-; 240274955Ssvnmir difference_type operator-(const DerivedT &RHS) const { 241274955Ssvnmir static_assert( 242274955Ssvnmir BaseT::IsRandomAccess, 243274955Ssvnmir "The '-' operator is only defined for random access iterators."); 244274955Ssvnmir return I - RHS.I; 245274955Ssvnmir } 246274955Ssvnmir 247274955Ssvnmir // We have to explicitly provide ++ and -- rather than letting the facade 248274955Ssvnmir // forward to += because WrappedIteratorT might not support +=. 249274955Ssvnmir using BaseT::operator++; 250274955Ssvnmir DerivedT &operator++() { 251274955Ssvnmir ++I; 252274955Ssvnmir return *static_cast<DerivedT *>(this); 253274955Ssvnmir } 254274955Ssvnmir using BaseT::operator--; 255274955Ssvnmir DerivedT &operator--() { 256274955Ssvnmir static_assert( 257274955Ssvnmir BaseT::IsBidirectional, 258274955Ssvnmir "The decrement operator is only defined for bidirectional iterators."); 259274955Ssvnmir --I; 260274955Ssvnmir return *static_cast<DerivedT *>(this); 261274955Ssvnmir } 262274955Ssvnmir 263274955Ssvnmir bool operator==(const DerivedT &RHS) const { return I == RHS.I; } 264274955Ssvnmir bool operator<(const DerivedT &RHS) const { 265274955Ssvnmir static_assert( 266274955Ssvnmir BaseT::IsRandomAccess, 267274955Ssvnmir "Relational operators are only defined for random access iterators."); 268274955Ssvnmir return I < RHS.I; 269274955Ssvnmir } 270274955Ssvnmir 271274955Ssvnmir ReferenceT operator*() const { return *I; } 272274955Ssvnmir}; 273274955Ssvnmir 274341825Sdim/// An iterator type that allows iterating over the pointees via some 275274955Ssvnmir/// other iterator. 276274955Ssvnmir/// 277274955Ssvnmir/// The typical usage of this is to expose a type that iterates over Ts, but 278274955Ssvnmir/// which is implemented with some iterator over T*s: 279274955Ssvnmir/// 280274955Ssvnmir/// \code 281321369Sdim/// using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>; 282274955Ssvnmir/// \endcode 283274955Ssvnmirtemplate <typename WrappedIteratorT, 284274955Ssvnmir typename T = typename std::remove_reference< 285274955Ssvnmir decltype(**std::declval<WrappedIteratorT>())>::type> 286274955Ssvnmirstruct pointee_iterator 287274955Ssvnmir : iterator_adaptor_base< 288341825Sdim pointee_iterator<WrappedIteratorT, T>, WrappedIteratorT, 289274955Ssvnmir typename std::iterator_traits<WrappedIteratorT>::iterator_category, 290274955Ssvnmir T> { 291288943Sdim pointee_iterator() = default; 292274955Ssvnmir template <typename U> 293274955Ssvnmir pointee_iterator(U &&u) 294274955Ssvnmir : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {} 295274955Ssvnmir 296274955Ssvnmir T &operator*() const { return **this->I; } 297274955Ssvnmir}; 298274955Ssvnmir 299321369Sdimtemplate <typename RangeT, typename WrappedIteratorT = 300321369Sdim decltype(std::begin(std::declval<RangeT>()))> 301321369Sdimiterator_range<pointee_iterator<WrappedIteratorT>> 302321369Sdimmake_pointee_range(RangeT &&Range) { 303321369Sdim using PointeeIteratorT = pointee_iterator<WrappedIteratorT>; 304321369Sdim return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))), 305321369Sdim PointeeIteratorT(std::end(std::forward<RangeT>(Range)))); 306321369Sdim} 307321369Sdim 308314564Sdimtemplate <typename WrappedIteratorT, 309314564Sdim typename T = decltype(&*std::declval<WrappedIteratorT>())> 310314564Sdimclass pointer_iterator 311344779Sdim : public iterator_adaptor_base< 312344779Sdim pointer_iterator<WrappedIteratorT, T>, WrappedIteratorT, 313344779Sdim typename std::iterator_traits<WrappedIteratorT>::iterator_category, 314344779Sdim T> { 315314564Sdim mutable T Ptr; 316274955Ssvnmir 317314564Sdimpublic: 318314564Sdim pointer_iterator() = default; 319314564Sdim 320314564Sdim explicit pointer_iterator(WrappedIteratorT u) 321314564Sdim : pointer_iterator::iterator_adaptor_base(std::move(u)) {} 322314564Sdim 323314564Sdim T &operator*() { return Ptr = &*this->I; } 324314564Sdim const T &operator*() const { return Ptr = &*this->I; } 325314564Sdim}; 326314564Sdim 327321369Sdimtemplate <typename RangeT, typename WrappedIteratorT = 328321369Sdim decltype(std::begin(std::declval<RangeT>()))> 329321369Sdimiterator_range<pointer_iterator<WrappedIteratorT>> 330321369Sdimmake_pointer_range(RangeT &&Range) { 331321369Sdim using PointerIteratorT = pointer_iterator<WrappedIteratorT>; 332321369Sdim return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))), 333321369Sdim PointerIteratorT(std::end(std::forward<RangeT>(Range)))); 334321369Sdim} 335321369Sdim 336360784Sdimtemplate <typename WrappedIteratorT, 337360784Sdim typename T1 = typename std::remove_reference<decltype(**std::declval<WrappedIteratorT>())>::type, 338360784Sdim typename T2 = typename std::add_pointer<T1>::type> 339360784Sdimusing raw_pointer_iterator = pointer_iterator<pointee_iterator<WrappedIteratorT, T1>, T2>; 340360784Sdim 341344779Sdim// Wrapper iterator over iterator ItType, adding DataRef to the type of ItType, 342344779Sdim// to create NodeRef = std::pair<InnerTypeOfItType, DataRef>. 343344779Sdimtemplate <typename ItType, typename NodeRef, typename DataRef> 344344779Sdimclass WrappedPairNodeDataIterator 345344779Sdim : public iterator_adaptor_base< 346344779Sdim WrappedPairNodeDataIterator<ItType, NodeRef, DataRef>, ItType, 347344779Sdim typename std::iterator_traits<ItType>::iterator_category, NodeRef, 348344779Sdim std::ptrdiff_t, NodeRef *, NodeRef &> { 349344779Sdim using BaseT = iterator_adaptor_base< 350344779Sdim WrappedPairNodeDataIterator, ItType, 351344779Sdim typename std::iterator_traits<ItType>::iterator_category, NodeRef, 352344779Sdim std::ptrdiff_t, NodeRef *, NodeRef &>; 353344779Sdim 354344779Sdim const DataRef DR; 355344779Sdim mutable NodeRef NR; 356344779Sdim 357344779Sdimpublic: 358344779Sdim WrappedPairNodeDataIterator(ItType Begin, const DataRef DR) 359344779Sdim : BaseT(Begin), DR(DR) { 360344779Sdim NR.first = DR; 361344779Sdim } 362344779Sdim 363344779Sdim NodeRef &operator*() const { 364344779Sdim NR.second = *this->I; 365344779Sdim return NR; 366344779Sdim } 367344779Sdim}; 368344779Sdim 369314564Sdim} // end namespace llvm 370314564Sdim 371314564Sdim#endif // LLVM_ADT_ITERATOR_H 372