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 <__config> 15 #include <__iterator/iterator_traits.h> 16 #include <__memory/pointer_traits.h> 17 #include <__type_traits/enable_if.h> 18 #include <__type_traits/integral_constant.h> 19 #include <__type_traits/is_convertible.h> 20 #include <__utility/move.h> 21 22 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 23 # pragma GCC system_header 24 #endif 25 26 _LIBCPP_BEGIN_NAMESPACE_STD 27 28 // Iterator wrapper that carries the valid range it is allowed to access. 29 // 30 // This is a simple iterator wrapper for contiguous iterators that points 31 // within a [begin, end) range and carries these bounds with it. The iterator 32 // ensures that it is pointing within that [begin, end) range when it is 33 // dereferenced. 34 // 35 // Arithmetic operations are allowed and the bounds of the resulting iterator 36 // are not checked. Hence, it is possible to create an iterator pointing outside 37 // its range, but it is not possible to dereference it. 38 template <class _Iterator, class = __enable_if_t< __is_cpp17_contiguous_iterator<_Iterator>::value > > 39 struct __bounded_iter { 40 using value_type = typename iterator_traits<_Iterator>::value_type; 41 using difference_type = typename iterator_traits<_Iterator>::difference_type; 42 using pointer = typename iterator_traits<_Iterator>::pointer; 43 using reference = typename iterator_traits<_Iterator>::reference; 44 using iterator_category = typename iterator_traits<_Iterator>::iterator_category; 45 #if _LIBCPP_STD_VER > 17 46 using iterator_concept = contiguous_iterator_tag; 47 #endif 48 49 // Create a singular iterator. 50 // 51 // Such an iterator does not point to any object and is conceptually out of bounds, so it is 52 // not dereferenceable. Observing operations like comparison and assignment are valid. 53 _LIBCPP_HIDE_FROM_ABI __bounded_iter() = default; 54 55 _LIBCPP_HIDE_FROM_ABI __bounded_iter(__bounded_iter const&) = default; 56 _LIBCPP_HIDE_FROM_ABI __bounded_iter(__bounded_iter&&) = default; 57 58 template <class _OtherIterator, class = __enable_if_t< is_convertible<_OtherIterator, _Iterator>::value > > 59 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __bounded_iter(__bounded_iter<_OtherIterator> const& __other) _NOEXCEPT 60 : __current_(__other.__current_), 61 __begin_(__other.__begin_), 62 __end_(__other.__end_) {} 63 64 // Assign a bounded iterator to another one, rebinding the bounds of the iterator as well. 65 _LIBCPP_HIDE_FROM_ABI __bounded_iter& operator=(__bounded_iter const&) = default; 66 _LIBCPP_HIDE_FROM_ABI __bounded_iter& operator=(__bounded_iter&&) = default; 67 68 private: 69 // Create an iterator wrapping the given iterator, and whose bounds are described 70 // by the provided [begin, end) range. 71 // 72 // This constructor does not check whether the resulting iterator is within its bounds. 73 // However, it does check that the provided [begin, end) range is a valid range (that 74 // is, begin <= end). 75 // 76 // Since it is non-standard for iterators to have this constructor, __bounded_iter must 77 // be created via `std::__make_bounded_iter`. 78 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 explicit __bounded_iter( 79 _Iterator __current, _Iterator __begin, _Iterator __end) 80 : __current_(__current), __begin_(__begin), __end_(__end) { 81 _LIBCPP_ASSERT(__begin <= __end, "__bounded_iter(current, begin, end): [begin, end) is not a valid range"); 82 } 83 84 template <class _It> 85 friend _LIBCPP_CONSTEXPR __bounded_iter<_It> __make_bounded_iter(_It, _It, _It); 86 87 public: 88 // Dereference and indexing operations. 89 // 90 // These operations check that the iterator is dereferenceable, that is within [begin, end). 91 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 reference operator*() const _NOEXCEPT { 92 _LIBCPP_ASSERT( 93 __in_bounds(__current_), "__bounded_iter::operator*: Attempt to dereference an out-of-range iterator"); 94 return *__current_; 95 } 96 97 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pointer operator->() const _NOEXCEPT { 98 _LIBCPP_ASSERT( 99 __in_bounds(__current_), "__bounded_iter::operator->: Attempt to dereference an out-of-range iterator"); 100 return std::__to_address(__current_); 101 } 102 103 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 reference operator[](difference_type __n) const _NOEXCEPT { 104 _LIBCPP_ASSERT( 105 __in_bounds(__current_ + __n), "__bounded_iter::operator[]: Attempt to index an iterator out-of-range"); 106 return __current_[__n]; 107 } 108 109 // Arithmetic operations. 110 // 111 // These operations do not check that the resulting iterator is within the bounds, since that 112 // would make it impossible to create a past-the-end iterator. 113 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator++() _NOEXCEPT { 114 ++__current_; 115 return *this; 116 } 117 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter operator++(int) _NOEXCEPT { 118 __bounded_iter __tmp(*this); 119 ++*this; 120 return __tmp; 121 } 122 123 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator--() _NOEXCEPT { 124 --__current_; 125 return *this; 126 } 127 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter operator--(int) _NOEXCEPT { 128 __bounded_iter __tmp(*this); 129 --*this; 130 return __tmp; 131 } 132 133 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator+=(difference_type __n) _NOEXCEPT { 134 __current_ += __n; 135 return *this; 136 } 137 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __bounded_iter 138 operator+(__bounded_iter const& __self, difference_type __n) _NOEXCEPT { 139 __bounded_iter __tmp(__self); 140 __tmp += __n; 141 return __tmp; 142 } 143 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __bounded_iter 144 operator+(difference_type __n, __bounded_iter const& __self) _NOEXCEPT { 145 __bounded_iter __tmp(__self); 146 __tmp += __n; 147 return __tmp; 148 } 149 150 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator-=(difference_type __n) _NOEXCEPT { 151 __current_ -= __n; 152 return *this; 153 } 154 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __bounded_iter 155 operator-(__bounded_iter const& __self, difference_type __n) _NOEXCEPT { 156 __bounded_iter __tmp(__self); 157 __tmp -= __n; 158 return __tmp; 159 } 160 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend difference_type 161 operator-(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 162 return __x.__current_ - __y.__current_; 163 } 164 165 // Comparison operations. 166 // 167 // These operations do not check whether the iterators are within their bounds. 168 // The valid range for each iterator is also not considered as part of the comparison, 169 // i.e. two iterators pointing to the same location will be considered equal even 170 // if they have different validity ranges. 171 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool 172 operator==(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 173 return __x.__current_ == __y.__current_; 174 } 175 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool 176 operator!=(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 177 return __x.__current_ != __y.__current_; 178 } 179 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool 180 operator<(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 181 return __x.__current_ < __y.__current_; 182 } 183 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool 184 operator>(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 185 return __x.__current_ > __y.__current_; 186 } 187 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool 188 operator<=(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 189 return __x.__current_ <= __y.__current_; 190 } 191 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool 192 operator>=(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT { 193 return __x.__current_ >= __y.__current_; 194 } 195 196 private: 197 // Return whether the given iterator is in the bounds of this __bounded_iter. 198 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool __in_bounds(_Iterator const& __iter) const { 199 return __iter >= __begin_ && __iter < __end_; 200 } 201 202 template <class> 203 friend struct pointer_traits; 204 _Iterator __current_; // current iterator 205 _Iterator __begin_, __end_; // valid range represented as [begin, end) 206 }; 207 208 template <class _It> 209 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __bounded_iter<_It> __make_bounded_iter(_It __it, _It __begin, _It __end) { 210 return __bounded_iter<_It>(std::move(__it), std::move(__begin), std::move(__end)); 211 } 212 213 #if _LIBCPP_STD_VER <= 17 214 template <class _Iterator> 215 struct __is_cpp17_contiguous_iterator<__bounded_iter<_Iterator> > : true_type {}; 216 #endif 217 218 template <class _Iterator> 219 struct pointer_traits<__bounded_iter<_Iterator> > { 220 using pointer = __bounded_iter<_Iterator>; 221 using element_type = typename pointer_traits<_Iterator>::element_type; 222 using difference_type = typename pointer_traits<_Iterator>::difference_type; 223 224 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static element_type* to_address(pointer __it) _NOEXCEPT { 225 return std::__to_address(__it.__current_); 226 } 227 }; 228 229 _LIBCPP_END_NAMESPACE_STD 230 231 #endif // _LIBCPP___ITERATOR_BOUNDED_ITER_H 232