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