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