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