__cxx03/__iterator/bounded_iter.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___CXX03___ITERATOR_BOUNDED_ITER_H
0011 #define _LIBCPP___CXX03___ITERATOR_BOUNDED_ITER_H
0012
0013 #include <__cxx03/__assert>
0014 #include <__cxx03/__compare/ordering.h>
0015 #include <__cxx03/__compare/three_way_comparable.h>
0016 #include <__cxx03/__config>
0017 #include <__cxx03/__iterator/iterator_traits.h>
0018 #include <__cxx03/__memory/pointer_traits.h>
0019 #include <__cxx03/__type_traits/enable_if.h>
0020 #include <__cxx03/__type_traits/integral_constant.h>
0021 #include <__cxx03/__type_traits/is_convertible.h>
0022 #include <__cxx03/__utility/move.h>
0023
0024 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0025 #  pragma GCC system_header
0026 #endif
0027
0028 _LIBCPP_PUSH_MACROS
0029 #include <__cxx03/__undef_macros>
0030
0031 _LIBCPP_BEGIN_NAMESPACE_STD
0032
0033 // Iterator wrapper that carries the valid range it is allowed to access.
0034 //
0035 // This is a simple iterator wrapper for contiguous iterators that points
0036 // within a [begin, end] range and carries these bounds with it. The iterator
0037 // ensures that it is pointing within [begin, end) range when it is
0038 // dereferenced. It also ensures that it is never iterated outside of
0039 // [begin, end]. This is important for two reasons:
0040 //
0041 // 1. It allows `operator*` and `operator++` bounds checks to be `iter != end`.
0042 //    This is both less for the optimizer to prove, and aligns with how callers
0043 //    typically use iterators.
0044 //
0045 // 2. Advancing an iterator out of bounds is undefined behavior (see the table
0046 //    in [input.iterators]). In particular, when the underlying iterator is a
0047 //    pointer, it is undefined at the language level (see [expr.add]). If
0048 //    bounded iterators exhibited this undefined behavior, we risk compiler
0049 //    optimizations deleting non-redundant bounds checks.
0050 template <class _Iterator, class = __enable_if_t< __libcpp_is_contiguous_iterator<_Iterator>::value > >
0051 struct __bounded_iter {
0052   using value_type        = typename iterator_traits<_Iterator>::value_type;
0053   using difference_type   = typename iterator_traits<_Iterator>::difference_type;
0054   using pointer           = typename iterator_traits<_Iterator>::pointer;
0055   using reference         = typename iterator_traits<_Iterator>::reference;
0056   using iterator_category = typename iterator_traits<_Iterator>::iterator_category;
0057 #if _LIBCPP_STD_VER >= 20
0058   using iterator_concept = contiguous_iterator_tag;
0059 #endif
0060
0061   // Create a singular iterator.
0062   //
0063   // Such an iterator points past the end of an empty span, so it is not dereferenceable.
0064   // Observing operations like comparison and assignment are valid.
0065   _LIBCPP_HIDE_FROM_ABI __bounded_iter() = default;
0066
0067   _LIBCPP_HIDE_FROM_ABI __bounded_iter(__bounded_iter const&) = default;
0068   _LIBCPP_HIDE_FROM_ABI __bounded_iter(__bounded_iter&&)      = default;
0069
0070   template <class _OtherIterator, __enable_if_t< is_convertible<_OtherIterator, _Iterator>::value, int> = 0>
0071   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __bounded_iter(__bounded_iter<_OtherIterator> const& __other) _NOEXCEPT
0072       : __current_(__other.__current_),
0073         __begin_(__other.__begin_),
0074         __end_(__other.__end_) {}
0075
0076   // Assign a bounded iterator to another one, rebinding the bounds of the iterator as well.
0077   _LIBCPP_HIDE_FROM_ABI __bounded_iter& operator=(__bounded_iter const&) = default;
0078   _LIBCPP_HIDE_FROM_ABI __bounded_iter& operator=(__bounded_iter&&)      = default;
0079
0080 private:
0081   // Create an iterator wrapping the given iterator, and whose bounds are described
0082   // by the provided [begin, end] range.
0083   //
0084   // The constructor does not check whether the resulting iterator is within its bounds. It is a
0085   // responsibility of the container to ensure that the given bounds are valid.
0086   //
0087   // Since it is non-standard for iterators to have this constructor, __bounded_iter must
0088   // be created via `std::__make_bounded_iter`.
0089   _LIBCPP_HIDE_FROM_ABI
0090   _LIBCPP_CONSTEXPR_SINCE_CXX14 explicit __bounded_iter(_Iterator __current, _Iterator __begin, _Iterator __end)
0091       : __current_(__current), __begin_(__begin), __end_(__end) {
0092     _LIBCPP_ASSERT_INTERNAL(
0093         __begin <= __current, "__bounded_iter(current, begin, end): current and begin are inconsistent");
0094     _LIBCPP_ASSERT_INTERNAL(
0095         __current <= __end, "__bounded_iter(current, begin, end): current and end are inconsistent");
0096   }
0097
0098   template <class _It>
0099   friend _LIBCPP_CONSTEXPR __bounded_iter<_It> __make_bounded_iter(_It, _It, _It);
0100
0101 public:
0102   // Dereference and indexing operations.
0103   //
0104   // These operations check that the iterator is dereferenceable. Since the class invariant is
0105   // that the iterator is always within `[begin, end]`, we only need to check it's not pointing to
0106   // `end`. This is easier for the optimizer because it aligns with the `iter != container.end()`
0107   // checks that typical callers already use (see
0108   // https://github.com/llvm/llvm-project/issues/78829).
0109   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 reference operator*() const _NOEXCEPT {
0110     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0111         __current_ != __end_, "__bounded_iter::operator*: Attempt to dereference an iterator at the end");
0112     return *__current_;
0113   }
0114
0115   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pointer operator->() const _NOEXCEPT {
0116     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0117         __current_ != __end_, "__bounded_iter::operator->: Attempt to dereference an iterator at the end");
0118     return std::__to_address(__current_);
0119   }
0120
0121   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 reference operator[](difference_type __n) const _NOEXCEPT {
0122     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0123         __n >= __begin_ - __current_, "__bounded_iter::operator[]: Attempt to index an iterator past the start");
0124     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0125         __n < __end_ - __current_, "__bounded_iter::operator[]: Attempt to index an iterator at or past the end");
0126     return __current_[__n];
0127   }
0128
0129   // Arithmetic operations.
0130   //
0131   // These operations check that the iterator remains within `[begin, end]`.
0132   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator++() _NOEXCEPT {
0133     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0134         __current_ != __end_, "__bounded_iter::operator++: Attempt to advance an iterator past the end");
0135     ++__current_;
0136     return *this;
0137   }
0138   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter operator++(int) _NOEXCEPT {
0139     __bounded_iter __tmp(*this);
0140     ++*this;
0141     return __tmp;
0142   }
0143
0144   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator--() _NOEXCEPT {
0145     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0146         __current_ != __begin_, "__bounded_iter::operator--: Attempt to rewind an iterator past the start");
0147     --__current_;
0148     return *this;
0149   }
0150   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter operator--(int) _NOEXCEPT {
0151     __bounded_iter __tmp(*this);
0152     --*this;
0153     return __tmp;
0154   }
0155
0156   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator+=(difference_type __n) _NOEXCEPT {
0157     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0158         __n >= __begin_ - __current_, "__bounded_iter::operator+=: Attempt to rewind an iterator past the start");
0159     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0160         __n <= __end_ - __current_, "__bounded_iter::operator+=: Attempt to advance an iterator past the end");
0161     __current_ += __n;
0162     return *this;
0163   }
0164   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __bounded_iter
0165   operator+(__bounded_iter const& __self, difference_type __n) _NOEXCEPT {
0166     __bounded_iter __tmp(__self);
0167     __tmp += __n;
0168     return __tmp;
0169   }
0170   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __bounded_iter
0171   operator+(difference_type __n, __bounded_iter const& __self) _NOEXCEPT {
0172     __bounded_iter __tmp(__self);
0173     __tmp += __n;
0174     return __tmp;
0175   }
0176
0177   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator-=(difference_type __n) _NOEXCEPT {
0178     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0179         __n <= __current_ - __begin_, "__bounded_iter::operator-=: Attempt to rewind an iterator past the start");
0180     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
0181         __n >= __current_ - __end_, "__bounded_iter::operator-=: Attempt to advance an iterator past the end");
0182     __current_ -= __n;
0183     return *this;
0184   }
0185   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __bounded_iter
0186   operator-(__bounded_iter const& __self, difference_type __n) _NOEXCEPT {
0187     __bounded_iter __tmp(__self);
0188     __tmp -= __n;
0189     return __tmp;
0190   }
0191   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend difference_type
0192   operator-(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {
0193     return __x.__current_ - __y.__current_;
0194   }
0195
0196   // Comparison operations.
0197   //
0198   // These operations do not check whether the iterators are within their bounds.
0199   // The valid range for each iterator is also not considered as part of the comparison,
0200   // i.e. two iterators pointing to the same location will be considered equal even
0201   // if they have different validity ranges.
0202   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
0203   operator==(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {
0204     return __x.__current_ == __y.__current_;
0205   }
0206
0207 #if _LIBCPP_STD_VER <= 17
0208   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
0209   operator!=(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {
0210     return __x.__current_ != __y.__current_;
0211   }
0212 #endif
0213
0214   // TODO(mordante) disable these overloads in the LLVM 20 release.
0215   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
0216   operator<(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {
0217     return __x.__current_ < __y.__current_;
0218   }
0219   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
0220   operator>(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {
0221     return __x.__current_ > __y.__current_;
0222   }
0223   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
0224   operator<=(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {
0225     return __x.__current_ <= __y.__current_;
0226   }
0227   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool
0228   operator>=(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {
0229     return __x.__current_ >= __y.__current_;
0230   }
0231
0232 #if _LIBCPP_STD_VER >= 20
0233   _LIBCPP_HIDE_FROM_ABI constexpr friend strong_ordering
0234   operator<=>(__bounded_iter const& __x, __bounded_iter const& __y) noexcept {
0235     if constexpr (three_way_comparable<_Iterator, strong_ordering>) {
0236       return __x.__current_ <=> __y.__current_;
0237     } else {
0238       if (__x.__current_ < __y.__current_)
0239         return strong_ordering::less;
0240
0241       if (__x.__current_ == __y.__current_)
0242         return strong_ordering::equal;
0243
0244       return strong_ordering::greater;
0245     }
0246   }
0247 #endif // _LIBCPP_STD_VER >= 20
0248
0249 private:
0250   template <class>
0251   friend struct pointer_traits;
0252   template <class, class>
0253   friend struct __bounded_iter;
0254   _Iterator __current_;       // current iterator
0255   _Iterator __begin_, __end_; // valid range represented as [begin, end]
0256 };
0257
0258 template <class _It>
0259 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __bounded_iter<_It> __make_bounded_iter(_It __it, _It __begin, _It __end) {
0260   return __bounded_iter<_It>(std::move(__it), std::move(__begin), std::move(__end));
0261 }
0262
0263 #if _LIBCPP_STD_VER <= 17
0264 template <class _Iterator>
0265 struct __libcpp_is_contiguous_iterator<__bounded_iter<_Iterator> > : true_type {};
0266 #endif
0267
0268 template <class _Iterator>
0269 struct pointer_traits<__bounded_iter<_Iterator> > {
0270   using pointer         = __bounded_iter<_Iterator>;
0271   using element_type    = typename pointer_traits<_Iterator>::element_type;
0272   using difference_type = typename pointer_traits<_Iterator>::difference_type;
0273
0274   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static element_type* to_address(pointer __it) _NOEXCEPT {
0275     return std::__to_address(__it.__current_);
0276   }
0277 };
0278
0279 _LIBCPP_END_NAMESPACE_STD
0280
0281 _LIBCPP_POP_MACROS
0282
0283 #endif // _LIBCPP___CXX03___ITERATOR_BOUNDED_ITER_H