293 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___ITERATOR_BOUNDED_ITER_H11#define _LIBCPP___ITERATOR_BOUNDED_ITER_H12 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_header30#endif31 32_LIBCPP_PUSH_MACROS33#include <__undef_macros>34 35_LIBCPP_BEGIN_NAMESPACE_STD36 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 points40// within a [begin, end] range and carries these bounds with it. The iterator41// ensures that it is pointing within [begin, end) range when it is42// dereferenced. It also ensures that it is never iterated outside of43// [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 callers47// typically use iterators.48//49// 2. Advancing an iterator out of bounds is undefined behavior (see the table50// in [input.iterators]). In particular, when the underlying iterator is a51// pointer, it is undefined at the language level (see [expr.add]). If52// bounded iterators exhibited this undefined behavior, we risk compiler53// optimizations deleting non-redundant bounds checks.54template <class _Iterator>55struct __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 >= 2065 using iterator_concept = contiguous_iterator_tag;66#endif67 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, __iterator_reference<_OtherIterator> >,81 is_same<reference, __make_const_lvalue_ref<__iterator_reference<_OtherIterator> > > > >::value,82 int> = 0>83 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __bounded_iter(__bounded_iter<_OtherIterator> const& __other) _NOEXCEPT84 : __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 92private:93 // Create an iterator wrapping the given iterator, and whose bounds are described94 // by the provided [begin, end] range.95 //96 // The constructor does not check whether the resulting iterator is within its bounds. It is a97 // 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 must100 // be created via `std::__make_bounded_iter`.101 _LIBCPP_HIDE_FROM_ABI102 _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 113public:114 // Dereference and indexing operations.115 //116 // These operations check that the iterator is dereferenceable. Since the class invariant is117 // that the iterator is always within `[begin, end]`, we only need to check it's not pointing to118 // `end`. This is easier for the optimizer because it aligns with the `iter != container.end()`119 // checks that typical callers already use (see https://llvm.org/PR78829).120 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 reference operator*() const _NOEXCEPT {121 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(122 __current_ != __end_, "__bounded_iter::operator*: Attempt to dereference an iterator at the end");123 return *__current_;124 }125 126 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pointer operator->() const _NOEXCEPT {127 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(128 __current_ != __end_, "__bounded_iter::operator->: Attempt to dereference an iterator at the end");129 return std::__to_address(__current_);130 }131 132 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 reference operator[](difference_type __n) const _NOEXCEPT {133 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(134 __n >= __begin_ - __current_, "__bounded_iter::operator[]: Attempt to index an iterator past the start");135 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(136 __n < __end_ - __current_, "__bounded_iter::operator[]: Attempt to index an iterator at or past the end");137 return __current_[__n];138 }139 140 // Arithmetic operations.141 //142 // These operations check that the iterator remains within `[begin, end]`.143 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator++() _NOEXCEPT {144 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(145 __current_ != __end_, "__bounded_iter::operator++: Attempt to advance an iterator past the end");146 ++__current_;147 return *this;148 }149 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter operator++(int) _NOEXCEPT {150 __bounded_iter __tmp(*this);151 ++*this;152 return __tmp;153 }154 155 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator--() _NOEXCEPT {156 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(157 __current_ != __begin_, "__bounded_iter::operator--: Attempt to rewind an iterator past the start");158 --__current_;159 return *this;160 }161 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter operator--(int) _NOEXCEPT {162 __bounded_iter __tmp(*this);163 --*this;164 return __tmp;165 }166 167 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator+=(difference_type __n) _NOEXCEPT {168 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(169 __n >= __begin_ - __current_, "__bounded_iter::operator+=: Attempt to rewind an iterator past the start");170 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(171 __n <= __end_ - __current_, "__bounded_iter::operator+=: Attempt to advance an iterator past the end");172 __current_ += __n;173 return *this;174 }175 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __bounded_iter176 operator+(__bounded_iter const& __self, difference_type __n) _NOEXCEPT {177 __bounded_iter __tmp(__self);178 __tmp += __n;179 return __tmp;180 }181 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __bounded_iter182 operator+(difference_type __n, __bounded_iter const& __self) _NOEXCEPT {183 __bounded_iter __tmp(__self);184 __tmp += __n;185 return __tmp;186 }187 188 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 __bounded_iter& operator-=(difference_type __n) _NOEXCEPT {189 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(190 __n <= __current_ - __begin_, "__bounded_iter::operator-=: Attempt to rewind an iterator past the start");191 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(192 __n >= __current_ - __end_, "__bounded_iter::operator-=: Attempt to advance an iterator past the end");193 __current_ -= __n;194 return *this;195 }196 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend __bounded_iter197 operator-(__bounded_iter const& __self, difference_type __n) _NOEXCEPT {198 __bounded_iter __tmp(__self);199 __tmp -= __n;200 return __tmp;201 }202 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 friend difference_type203 operator-(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {204 return __x.__current_ - __y.__current_;205 }206 207 // Comparison operations.208 //209 // These operations do not check whether the iterators are within their bounds.210 // The valid range for each iterator is also not considered as part of the comparison,211 // i.e. two iterators pointing to the same location will be considered equal even212 // if they have different validity ranges.213 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool214 operator==(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {215 return __x.__current_ == __y.__current_;216 }217 218#if _LIBCPP_STD_VER <= 17219 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool220 operator!=(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {221 return __x.__current_ != __y.__current_;222 }223 224 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool225 operator<(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {226 return __x.__current_ < __y.__current_;227 }228 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool229 operator>(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {230 return __x.__current_ > __y.__current_;231 }232 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool233 operator<=(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {234 return __x.__current_ <= __y.__current_;235 }236 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR friend bool237 operator>=(__bounded_iter const& __x, __bounded_iter const& __y) _NOEXCEPT {238 return __x.__current_ >= __y.__current_;239 }240 241#else242 _LIBCPP_HIDE_FROM_ABI constexpr friend strong_ordering243 operator<=>(__bounded_iter const& __x, __bounded_iter const& __y) noexcept {244 if constexpr (three_way_comparable<_Iterator, strong_ordering>) {245 return __x.__current_ <=> __y.__current_;246 } else {247 if (__x.__current_ < __y.__current_)248 return strong_ordering::less;249 250 if (__x.__current_ == __y.__current_)251 return strong_ordering::equal;252 253 return strong_ordering::greater;254 }255 }256#endif // _LIBCPP_STD_VER >= 20257 258private:259 template <class>260 friend struct pointer_traits;261 template <class>262 friend struct __bounded_iter;263 _Iterator __current_; // current iterator264 _Iterator __begin_, __end_; // valid range represented as [begin, end]265};266 267template <class _It>268_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR __bounded_iter<_It> __make_bounded_iter(_It __it, _It __begin, _It __end) {269 return __bounded_iter<_It>(std::move(__it), std::move(__begin), std::move(__end));270}271 272#if _LIBCPP_STD_VER <= 17273template <class _Iterator>274struct __libcpp_is_contiguous_iterator<__bounded_iter<_Iterator> > : true_type {};275#endif276 277template <class _Iterator>278struct pointer_traits<__bounded_iter<_Iterator> > {279 using pointer = __bounded_iter<_Iterator>;280 using element_type = typename pointer_traits<_Iterator>::element_type;281 using difference_type = typename pointer_traits<_Iterator>::difference_type;282 283 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static element_type* to_address(pointer __it) _NOEXCEPT {284 return std::__to_address(__it.__current_);285 }286};287 288_LIBCPP_END_NAMESPACE_STD289 290_LIBCPP_POP_MACROS291 292#endif // _LIBCPP___ITERATOR_BOUNDED_ITER_H293