libcxx/include/__iterator/bounded_iter.h

   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