//===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_ITERATOR_H #define LLVM_ADT_ITERATOR_H #include "llvm/ADT/iterator_range.h" #include #include #include #include #include namespace llvm { /// CRTP base class which implements the entire standard iterator facade /// in terms of a minimal subset of the interface. /// /// Use this when it is reasonable to implement most of the iterator /// functionality in terms of a core subset. If you need special behavior or /// there are performance implications for this, you may want to override the /// relevant members instead. /// /// Note, one abstraction that this does *not* provide is implementing /// subtraction in terms of addition by negating the difference. Negation isn't /// always information preserving, and I can see very reasonable iterator /// designs where this doesn't work well. It doesn't really force much added /// boilerplate anyways. /// /// Another abstraction that this doesn't provide is implementing increment in /// terms of addition of one. These aren't equivalent for all iterator /// categories, and respecting that adds a lot of complexity for little gain. /// /// Classes wishing to use `iterator_facade_base` should implement the following /// methods: /// /// Forward Iterators: /// (All of the following methods) /// - DerivedT &operator=(const DerivedT &R); /// - bool operator==(const DerivedT &R) const; /// - const T &operator*() const; /// - T &operator*(); /// - DerivedT &operator++(); /// /// Bidirectional Iterators: /// (All methods of forward iterators, plus the following) /// - DerivedT &operator--(); /// /// Random-access Iterators: /// (All methods of bidirectional iterators excluding the following) /// - DerivedT &operator++(); /// - DerivedT &operator--(); /// (and plus the following) /// - bool operator<(const DerivedT &RHS) const; /// - DifferenceTypeT operator-(const DerivedT &R) const; /// - DerivedT &operator+=(DifferenceTypeT N); /// - DerivedT &operator-=(DifferenceTypeT N); /// template class iterator_facade_base : public std::iterator { protected: enum { IsRandomAccess = std::is_base_of::value, IsBidirectional = std::is_base_of::value, }; /// A proxy object for computing a reference via indirecting a copy of an /// iterator. This is used in APIs which need to produce a reference via /// indirection but for which the iterator object might be a temporary. The /// proxy preserves the iterator internally and exposes the indirected /// reference via a conversion operator. class ReferenceProxy { friend iterator_facade_base; DerivedT I; ReferenceProxy(DerivedT I) : I(std::move(I)) {} public: operator ReferenceT() const { return *I; } }; public: DerivedT operator+(DifferenceTypeT n) const { static_assert(std::is_base_of::value, "Must pass the derived type to this template!"); static_assert( IsRandomAccess, "The '+' operator is only defined for random access iterators."); DerivedT tmp = *static_cast(this); tmp += n; return tmp; } friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) { static_assert( IsRandomAccess, "The '+' operator is only defined for random access iterators."); return i + n; } DerivedT operator-(DifferenceTypeT n) const { static_assert( IsRandomAccess, "The '-' operator is only defined for random access iterators."); DerivedT tmp = *static_cast(this); tmp -= n; return tmp; } DerivedT &operator++() { static_assert(std::is_base_of::value, "Must pass the derived type to this template!"); return static_cast(this)->operator+=(1); } DerivedT operator++(int) { DerivedT tmp = *static_cast(this); ++*static_cast(this); return tmp; } DerivedT &operator--() { static_assert( IsBidirectional, "The decrement operator is only defined for bidirectional iterators."); return static_cast(this)->operator-=(1); } DerivedT operator--(int) { static_assert( IsBidirectional, "The decrement operator is only defined for bidirectional iterators."); DerivedT tmp = *static_cast(this); --*static_cast(this); return tmp; } bool operator!=(const DerivedT &RHS) const { return !static_cast(this)->operator==(RHS); } bool operator>(const DerivedT &RHS) const { static_assert( IsRandomAccess, "Relational operators are only defined for random access iterators."); return !static_cast(this)->operator<(RHS) && !static_cast(this)->operator==(RHS); } bool operator<=(const DerivedT &RHS) const { static_assert( IsRandomAccess, "Relational operators are only defined for random access iterators."); return !static_cast(this)->operator>(RHS); } bool operator>=(const DerivedT &RHS) const { static_assert( IsRandomAccess, "Relational operators are only defined for random access iterators."); return !static_cast(this)->operator<(RHS); } PointerT operator->() { return &static_cast(this)->operator*(); } PointerT operator->() const { return &static_cast(this)->operator*(); } ReferenceProxy operator[](DifferenceTypeT n) { static_assert(IsRandomAccess, "Subscripting is only defined for random access iterators."); return ReferenceProxy(static_cast(this)->operator+(n)); } ReferenceProxy operator[](DifferenceTypeT n) const { static_assert(IsRandomAccess, "Subscripting is only defined for random access iterators."); return ReferenceProxy(static_cast(this)->operator+(n)); } }; /// CRTP base class for adapting an iterator to a different type. /// /// This class can be used through CRTP to adapt one iterator into another. /// Typically this is done through providing in the derived class a custom \c /// operator* implementation. Other methods can be overridden as well. template < typename DerivedT, typename WrappedIteratorT, typename IteratorCategoryT = typename std::iterator_traits::iterator_category, typename T = typename std::iterator_traits::value_type, typename DifferenceTypeT = typename std::iterator_traits::difference_type, typename PointerT = typename std::conditional< std::is_same::value_type>::value, typename std::iterator_traits::pointer, T *>::type, typename ReferenceT = typename std::conditional< std::is_same::value_type>::value, typename std::iterator_traits::reference, T &>::type> class iterator_adaptor_base : public iterator_facade_base { using BaseT = typename iterator_adaptor_base::iterator_facade_base; protected: WrappedIteratorT I; iterator_adaptor_base() = default; explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) { static_assert(std::is_base_of::value, "Must pass the derived type to this template!"); } const WrappedIteratorT &wrapped() const { return I; } public: using difference_type = DifferenceTypeT; DerivedT &operator+=(difference_type n) { static_assert( BaseT::IsRandomAccess, "The '+=' operator is only defined for random access iterators."); I += n; return *static_cast(this); } DerivedT &operator-=(difference_type n) { static_assert( BaseT::IsRandomAccess, "The '-=' operator is only defined for random access iterators."); I -= n; return *static_cast(this); } using BaseT::operator-; difference_type operator-(const DerivedT &RHS) const { static_assert( BaseT::IsRandomAccess, "The '-' operator is only defined for random access iterators."); return I - RHS.I; } // We have to explicitly provide ++ and -- rather than letting the facade // forward to += because WrappedIteratorT might not support +=. using BaseT::operator++; DerivedT &operator++() { ++I; return *static_cast(this); } using BaseT::operator--; DerivedT &operator--() { static_assert( BaseT::IsBidirectional, "The decrement operator is only defined for bidirectional iterators."); --I; return *static_cast(this); } bool operator==(const DerivedT &RHS) const { return I == RHS.I; } bool operator<(const DerivedT &RHS) const { static_assert( BaseT::IsRandomAccess, "Relational operators are only defined for random access iterators."); return I < RHS.I; } ReferenceT operator*() const { return *I; } }; /// An iterator type that allows iterating over the pointees via some /// other iterator. /// /// The typical usage of this is to expose a type that iterates over Ts, but /// which is implemented with some iterator over T*s: /// /// \code /// using iterator = pointee_iterator::iterator>; /// \endcode template ())>::type> struct pointee_iterator : iterator_adaptor_base< pointee_iterator, WrappedIteratorT, typename std::iterator_traits::iterator_category, T> { pointee_iterator() = default; template pointee_iterator(U &&u) : pointee_iterator::iterator_adaptor_base(std::forward(u)) {} T &operator*() const { return **this->I; } }; template ()))> iterator_range> make_pointee_range(RangeT &&Range) { using PointeeIteratorT = pointee_iterator; return make_range(PointeeIteratorT(std::begin(std::forward(Range))), PointeeIteratorT(std::end(std::forward(Range)))); } template ())> class pointer_iterator : public iterator_adaptor_base< pointer_iterator, WrappedIteratorT, typename std::iterator_traits::iterator_category, T> { mutable T Ptr; public: pointer_iterator() = default; explicit pointer_iterator(WrappedIteratorT u) : pointer_iterator::iterator_adaptor_base(std::move(u)) {} T &operator*() { return Ptr = &*this->I; } const T &operator*() const { return Ptr = &*this->I; } }; template ()))> iterator_range> make_pointer_range(RangeT &&Range) { using PointerIteratorT = pointer_iterator; return make_range(PointerIteratorT(std::begin(std::forward(Range))), PointerIteratorT(std::end(std::forward(Range)))); } // Wrapper iterator over iterator ItType, adding DataRef to the type of ItType, // to create NodeRef = std::pair. template class WrappedPairNodeDataIterator : public iterator_adaptor_base< WrappedPairNodeDataIterator, ItType, typename std::iterator_traits::iterator_category, NodeRef, std::ptrdiff_t, NodeRef *, NodeRef &> { using BaseT = iterator_adaptor_base< WrappedPairNodeDataIterator, ItType, typename std::iterator_traits::iterator_category, NodeRef, std::ptrdiff_t, NodeRef *, NodeRef &>; const DataRef DR; mutable NodeRef NR; public: WrappedPairNodeDataIterator(ItType Begin, const DataRef DR) : BaseT(Begin), DR(DR) { NR.first = DR; } NodeRef &operator*() const { NR.second = *this->I; return NR; } }; } // end namespace llvm #endif // LLVM_ADT_ITERATOR_H