1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___ITERATOR_BOUNDED_ITER_H 11 #define _LIBCPP___ITERATOR_BOUNDED_ITER_H 12 13 #include <__assert> 14 #include <__compare/ordering.h> 15 #include <__compare/three_way_comparable.h> 16 #include <__config> 17 #include <__iterator/iterator_traits.h> 18 #include <__memory/pointer_traits.h> 19 #include <__type_traits/enable_if.h> 20 #include <__type_traits/integral_constant.h> 21 #include <__type_traits/is_convertible.h> 22 #include <__utility/move.h> 23 24 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 25 # pragma GCC system_header 26 #endif 27 28 _LIBCPP_PUSH_MACROS 29 #include <__undef_macros> 30 31 _LIBCPP_BEGIN_NAMESPACE_STD 32 33 // Iterator wrapper that carries the valid range it is allowed to access. 34 // 35 // This is a simple iterator wrapper for contiguous iterators that points 36 // within a [begin, end] range and carries these bounds with it. The iterator 37 // ensures that it is pointing within [begin, end) range when it is 38 // dereferenced. It also ensures that it is never iterated outside of 39 // [begin, end]. This is important for two reasons: 40 // 41 // 1. It allows `operator*` and `operator++` bounds checks to be `iter != end`. 42 // This is both less for the optimizer to prove, and aligns with how callers 43 // typically use iterators. 44 // 45 // 2. Advancing an iterator out of bounds is undefined behavior (see the table 46 // in [input.iterators]). In particular, when the underlying iterator is a 47 // pointer, it is undefined at the language level (see [expr.add]). If 48 // bounded iterators exhibited this undefined behavior, we risk compiler 49 // optimizations deleting non-redundant bounds checks. 50 template <class _Iterator, class = __enable_if_t< __libcpp_is_contiguous_iterator<_Iterator>::value > > 51 struct __bounded_iter { 52 using value_type = typename iterator_traits<_Iterator>::value_type; 53 using difference_type = typename iterator_traits<_Iterator>::difference_type; 54 using pointer = typename iterator_traits<_Iterator>::pointer; 55 using reference = typename iterator_traits<_Iterator>::reference; 56 using iterator_category = typename iterator_traits<_Iterator>::iterator_category; 57 #if _LIBCPP_STD_VER >= 20 58 using iterator_concept = contiguous_iterator_tag; 59 #endif 60 61 // Create a singular iterator. 62 // 63 // Such an iterator points past the end of an empty span, so it is not dereferenceable. 64 // Observing operations like comparison and assignment are valid. 65 _LIBCPP_HIDE_FROM_ABI __bounded_iter() = default; 66 67 _LIBCPP_HIDE_FROM_ABI __bounded_iter(__bounded_iter const&) = default; 68 _LIBCPP_HIDE_FROM_ABI __bounded_iter(__bounded_iter&&) = default; 69 70 template <class _OtherIterator, __enable_if_t< is_convertible<_OtherIterator, _Iterator>::value, int> = 0> 71 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __bounded_iter(__bounded_iter<_OtherIterator> const& __other) _NOEXCEPT 72 : __current_(__other.__current_), 73 __begin_(__other.__begin_), 74 __end_(__other.__end_) {} 75 76 // Assign a bounded iterator to another one, rebinding the bounds of the iterator as well. 77 _LIBCPP_HIDE_FROM_ABI __bounded_iter& operator=(__bounded_iter const&) = default; 78 _LIBCPP_HIDE_FROM_ABI __bounded_iter& operator=(__bounded_iter&&) = default; 79 80 private: 81 // Create an iterator wrapping the given iterator, and whose bounds are described 82 // by the provided [begin, end] range. 83 // 84 // The constructor does not check whether the resulting iterator is within its bounds. It is a 85 // responsibility of the container to ensure that the given bounds are valid. 86 // 87 // Since it is non-standard for iterators to have this constructor, __bounded_iter must 88 // be created via `std::__make_bounded_iter`. 89 _LIBCPP_HIDE_FROM_ABI 90 _LIBCPP_CONSTEXPR_SINCE_CXX14 explicit __bounded_iter(_Iterator __current, _Iterator __begin, _Iterator __end) 91 : __current_(__current), __begin_(__begin), __end_(__end) { 92 _LIBCPP_ASSERT_INTERNAL( 93 __begin <= __current, "__bounded_iter(current, begin, end): current and begin are inconsistent"); 94 _LIBCPP_ASSERT_INTERNAL( 95 __current <= __end, "__bounded_iter(current, begin, end): current and end are inconsistent"); 96 } 97 98 template <class _It> 99 friend _LIBCPP_CONSTEXPR __bounded_iter<_It> __make_bounded_iter(_It, _It, _It); 100 101 public: 102 // Dereference and indexing operations. 103 // 104 // These operations check that the iterator is dereferenceable. Since the class invariant is 105 // that the iterator is always within `[begin, end]`, we only need to check it's not pointing to 106 // `end`. This is easier for the optimizer because it aligns with the `iter != container.end()` 107 // checks that typical callers already use (see 108 // https://github.com/llvm/llvm-project/issues/78829). 109 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 reference operator*() const _NOEXCEPT { 110 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 111 __current_ != __end_, "__bounded_iter::operator*: Attempt to dereference an iterator at the end"); 112 return *__current_; 113 } 114 115 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pointer operator->() const _NOEXCEPT { 116 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 117 __current_ != __end_, "__bounded_iter::operator->: Attempt to dereference an iterator at the end"); 118 return std::__to_address(__current_); 119 } 120 121 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 reference operator[](difference_type __n) const _NOEXCEPT { 122 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 123 __n >= __begin_ - __current_, "__bounded_iter::operator[]: Attempt to index an iterator past the start"); 124 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 125 __n < __end_ - __current_, "__bounded_iter::operator[]: Attempt to index an iterator at or past the end"); 126 return __current_[__n]; 127 } 128 129 // Arithmetic operations. 130 // 131 // These operations check that the iterator remains within `[begin, end]`. 132 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator++() _NOEXCEPT { 133 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 134 __current_ != __end_, "__bounded_iter::operator++: Attempt to advance an iterator past the end"); 135 ++__current_; 136 return *this; 137 } 138 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter operator++(int) _NOEXCEPT { 139 __bounded_iter __tmp(*this); 140 ++*this; 141 return __tmp; 142 } 143 144 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator--() _NOEXCEPT { 145 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 146 __current_ != __begin_, "__bounded_iter::operator--: Attempt to rewind an iterator past the start"); 147 --__current_; 148 return *this; 149 } 150 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter operator--(int) _NOEXCEPT { 151 __bounded_iter __tmp(*this); 152 --*this; 153 return __tmp; 154 } 155 156 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator+=(difference_type __n) _NOEXCEPT { 157 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 158 __n >= __begin_ - __current_, "__bounded_iter::operator+=: Attempt to rewind an iterator past the start"); 159 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 160 __n <= __end_ - __current_, "__bounded_iter::operator+=: Attempt to advance an iterator past the end"); 161 __current_ += __n; 162 return *this; 163 } 164 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __bounded_iter 165 operator+(__bounded_iter const& __self, difference_type __n) _NOEXCEPT { 166 __bounded_iter __tmp(__self); 167 __tmp += __n; 168 return __tmp; 169 } 170 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __bounded_iter 171 operator+(difference_type __n, __bounded_iter const& __self) _NOEXCEPT { 172 __bounded_iter __tmp(__self); 173 __tmp += __n; 174 return __tmp; 175 } 176 177 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator-=(difference_type __n) _NOEXCEPT { 178 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 179 __n <= __current_ - __begin_, "__bounded_iter::operator-=: Attempt to rewind an iterator past the start"); 180 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 181 __n >= __current_ - __end_, "__bounded_iter::operator-=: Attempt to advance an iterator past the end"); 182 __current_ -= __n; 183 return *this; 184 } 185 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __bounded_iter 186 operator-(__bounded_iter const& __self, difference_type __n) _NOEXCEPT { 187 __bounded_iter __tmp(__self); 188 __tmp -= __n; 189 return __tmp; 190 } 191 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend difference_type 192 operator-(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 193 return __x.__current_ - __y.__current_; 194 } 195 196 // Comparison operations. 197 // 198 // These operations do not check whether the iterators are within their bounds. 199 // The valid range for each iterator is also not considered as part of the comparison, 200 // i.e. two iterators pointing to the same location will be considered equal even 201 // if they have different validity ranges. 202 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool 203 operator==(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 204 return __x.__current_ == __y.__current_; 205 } 206 207 #if _LIBCPP_STD_VER <= 17 208 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool 209 operator!=(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 210 return __x.__current_ != __y.__current_; 211 } 212 #endif 213 214 // TODO(mordante) disable these overloads in the LLVM 20 release. 215 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool 216 operator<(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 217 return __x.__current_ < __y.__current_; 218 } 219 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool 220 operator>(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 221 return __x.__current_ > __y.__current_; 222 } 223 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool 224 operator<=(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 225 return __x.__current_ <= __y.__current_; 226 } 227 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool 228 operator>=(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 229 return __x.__current_ >= __y.__current_; 230 } 231 232 #if _LIBCPP_STD_VER >= 20 233 _LIBCPP_HIDE_FROM_ABI constexpr friend strong_ordering 234 operator<=>(__bounded_iter const& __x, __bounded_iter const& __y) noexcept { 235 if constexpr (three_way_comparable<_Iterator, strong_ordering>) { 236 return __x.__current_ <=> __y.__current_; 237 } else { 238 if (__x.__current_ < __y.__current_) 239 return strong_ordering::less; 240 241 if (__x.__current_ == __y.__current_) 242 return strong_ordering::equal; 243 244 return strong_ordering::greater; 245 } 246 } 247 #endif // _LIBCPP_STD_VER >= 20 248 249 private: 250 template <class> 251 friend struct pointer_traits; 252 template <class, class> 253 friend struct __bounded_iter; 254 _Iterator __current_; // current iterator 255 _Iterator __begin_, __end_; // valid range represented as [begin, end] 256 }; 257 258 template <class _It> 259 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __bounded_iter<_It> __make_bounded_iter(_It __it, _It __begin, _It __end) { 260 return __bounded_iter<_It>(std::move(__it), std::move(__begin), std::move(__end)); 261 } 262 263 #if _LIBCPP_STD_VER <= 17 264 template <class _Iterator> 265 struct __libcpp_is_contiguous_iterator<__bounded_iter<_Iterator> > : true_type {}; 266 #endif 267 268 template <class _Iterator> 269 struct pointer_traits<__bounded_iter<_Iterator> > { 270 using pointer = __bounded_iter<_Iterator>; 271 using element_type = typename pointer_traits<_Iterator>::element_type; 272 using difference_type = typename pointer_traits<_Iterator>::difference_type; 273 274 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static element_type* to_address(pointer __it) _NOEXCEPT { 275 return std::__to_address(__it.__current_); 276 } 277 }; 278 279 _LIBCPP_END_NAMESPACE_STD 280 281 _LIBCPP_POP_MACROS 282 283 #endif // _LIBCPP___ITERATOR_BOUNDED_ITER_H 284