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_COMMON_ITERATOR_H 11 #define _LIBCPP___ITERATOR_COMMON_ITERATOR_H 12 13 #include <__assert> 14 #include <__concepts/assignable.h> 15 #include <__concepts/constructible.h> 16 #include <__concepts/convertible_to.h> 17 #include <__concepts/copyable.h> 18 #include <__concepts/derived_from.h> 19 #include <__concepts/equality_comparable.h> 20 #include <__concepts/same_as.h> 21 #include <__config> 22 #include <__iterator/concepts.h> 23 #include <__iterator/incrementable_traits.h> 24 #include <__iterator/iter_move.h> 25 #include <__iterator/iter_swap.h> 26 #include <__iterator/iterator_traits.h> 27 #include <__iterator/readable_traits.h> 28 #include <__memory/addressof.h> 29 #include <__type_traits/is_pointer.h> 30 #include <__utility/declval.h> 31 #include <variant> 32 33 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 34 # pragma GCC system_header 35 #endif 36 37 _LIBCPP_PUSH_MACROS 38 #include <__undef_macros> 39 40 _LIBCPP_BEGIN_NAMESPACE_STD 41 42 #if _LIBCPP_STD_VER >= 20 43 44 template <class _Iter> 45 concept __can_use_postfix_proxy = 46 constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>> && move_constructible<iter_value_t<_Iter>>; 47 48 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent> 49 requires(!same_as<_Iter, _Sent> && copyable<_Iter>) 50 class common_iterator { 51 struct __proxy { 52 _LIBCPP_HIDE_FROM_ABI constexpr const iter_value_t<_Iter>* operator->() const noexcept { 53 return std::addressof(__value_); 54 } 55 iter_value_t<_Iter> __value_; 56 }; 57 58 struct __postfix_proxy { 59 _LIBCPP_HIDE_FROM_ABI constexpr const iter_value_t<_Iter>& operator*() const noexcept { return __value_; } 60 iter_value_t<_Iter> __value_; 61 }; 62 63 variant<_Iter, _Sent> __hold_; 64 template <input_or_output_iterator _OtherIter, sentinel_for<_OtherIter> _OtherSent> 65 requires(!same_as<_OtherIter, _OtherSent> && copyable<_OtherIter>) 66 friend class common_iterator; 67 68 public: 69 _LIBCPP_HIDE_FROM_ABI common_iterator() 70 requires default_initializable<_Iter> 71 = default; 72 common_iterator(_Iter __i)73 _LIBCPP_HIDE_FROM_ABI constexpr common_iterator(_Iter __i) : __hold_(in_place_type<_Iter>, std::move(__i)) {} common_iterator(_Sent __s)74 _LIBCPP_HIDE_FROM_ABI constexpr common_iterator(_Sent __s) : __hold_(in_place_type<_Sent>, std::move(__s)) {} 75 76 template <class _I2, class _S2> 77 requires convertible_to<const _I2&, _Iter> && convertible_to<const _S2&, _Sent> common_iterator(const common_iterator<_I2,_S2> & __other)78 _LIBCPP_HIDE_FROM_ABI constexpr common_iterator(const common_iterator<_I2, _S2>& __other) 79 : __hold_([&]() -> variant<_Iter, _Sent> { 80 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 81 !__other.__hold_.valueless_by_exception(), "Attempted to construct from a valueless common_iterator"); 82 if (__other.__hold_.index() == 0) 83 return variant<_Iter, _Sent>{in_place_index<0>, std::__unchecked_get<0>(__other.__hold_)}; 84 return variant<_Iter, _Sent>{in_place_index<1>, std::__unchecked_get<1>(__other.__hold_)}; 85 }()) {} 86 87 template <class _I2, class _S2> 88 requires convertible_to<const _I2&, _Iter> && convertible_to<const _S2&, _Sent> && 89 assignable_from<_Iter&, const _I2&> && assignable_from<_Sent&, const _S2&> 90 _LIBCPP_HIDE_FROM_ABI common_iterator& operator=(const common_iterator<_I2, _S2>& __other) { 91 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 92 !__other.__hold_.valueless_by_exception(), "Attempted to assign from a valueless common_iterator"); 93 94 auto __idx = __hold_.index(); 95 auto __other_idx = __other.__hold_.index(); 96 97 // If they're the same index, just assign. 98 if (__idx == 0 && __other_idx == 0) 99 std::__unchecked_get<0>(__hold_) = std::__unchecked_get<0>(__other.__hold_); 100 else if (__idx == 1 && __other_idx == 1) 101 std::__unchecked_get<1>(__hold_) = std::__unchecked_get<1>(__other.__hold_); 102 103 // Otherwise replace with the oposite element. 104 else if (__other_idx == 1) 105 __hold_.template emplace<1>(std::__unchecked_get<1>(__other.__hold_)); 106 else if (__other_idx == 0) 107 __hold_.template emplace<0>(std::__unchecked_get<0>(__other.__hold_)); 108 109 return *this; 110 } 111 decltype(auto)112 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() { 113 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 114 std::holds_alternative<_Iter>(__hold_), "Attempted to dereference a non-dereferenceable common_iterator"); 115 return *std::__unchecked_get<_Iter>(__hold_); 116 } 117 decltype(auto)118 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const 119 requires __dereferenceable<const _Iter> 120 { 121 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 122 std::holds_alternative<_Iter>(__hold_), "Attempted to dereference a non-dereferenceable common_iterator"); 123 return *std::__unchecked_get<_Iter>(__hold_); 124 } 125 126 template <class _I2 = _Iter> 127 _LIBCPP_HIDE_FROM_ABI auto operator->() const 128 requires indirectly_readable<const _I2> && (requires(const _I2& __i) { 129 __i.operator->(); 130 } || is_reference_v<iter_reference_t<_I2>> || constructible_from<iter_value_t<_I2>, iter_reference_t<_I2>>) 131 { 132 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 133 std::holds_alternative<_Iter>(__hold_), "Attempted to dereference a non-dereferenceable common_iterator"); 134 if constexpr (is_pointer_v<_Iter> || requires(const _Iter& __i) { __i.operator->(); }) { 135 return std::__unchecked_get<_Iter>(__hold_); 136 } else if constexpr (is_reference_v<iter_reference_t<_Iter>>) { 137 auto&& __tmp = *std::__unchecked_get<_Iter>(__hold_); 138 return std::addressof(__tmp); 139 } else { 140 return __proxy{*std::__unchecked_get<_Iter>(__hold_)}; 141 } 142 } 143 144 _LIBCPP_HIDE_FROM_ABI common_iterator& operator++() { 145 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 146 std::holds_alternative<_Iter>(__hold_), "Attempted to increment a non-dereferenceable common_iterator"); 147 ++std::__unchecked_get<_Iter>(__hold_); 148 return *this; 149 } 150 151 _LIBCPP_HIDE_FROM_ABI decltype(auto) operator++(int) { 152 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 153 std::holds_alternative<_Iter>(__hold_), "Attempted to increment a non-dereferenceable common_iterator"); 154 if constexpr (forward_iterator<_Iter>) { 155 auto __tmp = *this; 156 ++*this; 157 return __tmp; 158 } else if constexpr (requires(_Iter& __i) { 159 { *__i++ } -> __can_reference; 160 } || !__can_use_postfix_proxy<_Iter>) { 161 return std::__unchecked_get<_Iter>(__hold_)++; 162 } else { 163 auto __p = __postfix_proxy{**this}; 164 ++*this; 165 return __p; 166 } 167 } 168 169 template <class _I2, sentinel_for<_Iter> _S2> 170 requires sentinel_for<_Sent, _I2> 171 _LIBCPP_HIDE_FROM_ABI friend constexpr bool 172 operator==(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) { 173 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 174 !__x.__hold_.valueless_by_exception(), "Attempted to compare a valueless common_iterator"); 175 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 176 !__y.__hold_.valueless_by_exception(), "Attempted to compare a valueless common_iterator"); 177 178 auto __x_index = __x.__hold_.index(); 179 auto __y_index = __y.__hold_.index(); 180 181 if (__x_index == __y_index) 182 return true; 183 184 if (__x_index == 0) 185 return std::__unchecked_get<_Iter>(__x.__hold_) == std::__unchecked_get<_S2>(__y.__hold_); 186 187 return std::__unchecked_get<_Sent>(__x.__hold_) == std::__unchecked_get<_I2>(__y.__hold_); 188 } 189 190 template <class _I2, sentinel_for<_Iter> _S2> 191 requires sentinel_for<_Sent, _I2> && equality_comparable_with<_Iter, _I2> 192 _LIBCPP_HIDE_FROM_ABI friend constexpr bool 193 operator==(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) { 194 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 195 !__x.__hold_.valueless_by_exception(), "Attempted to compare a valueless common_iterator"); 196 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 197 !__y.__hold_.valueless_by_exception(), "Attempted to compare a valueless common_iterator"); 198 199 auto __x_index = __x.__hold_.index(); 200 auto __y_index = __y.__hold_.index(); 201 202 if (__x_index == 1 && __y_index == 1) 203 return true; 204 205 if (__x_index == 0 && __y_index == 0) 206 return std::__unchecked_get<_Iter>(__x.__hold_) == std::__unchecked_get<_I2>(__y.__hold_); 207 208 if (__x_index == 0) 209 return std::__unchecked_get<_Iter>(__x.__hold_) == std::__unchecked_get<_S2>(__y.__hold_); 210 211 return std::__unchecked_get<_Sent>(__x.__hold_) == std::__unchecked_get<_I2>(__y.__hold_); 212 } 213 214 template <sized_sentinel_for<_Iter> _I2, sized_sentinel_for<_Iter> _S2> 215 requires sized_sentinel_for<_Sent, _I2> 216 _LIBCPP_HIDE_FROM_ABI friend constexpr iter_difference_t<_I2> 217 operator-(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) { 218 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 219 !__x.__hold_.valueless_by_exception(), "Attempted to subtract from a valueless common_iterator"); 220 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 221 !__y.__hold_.valueless_by_exception(), "Attempted to subtract a valueless common_iterator"); 222 223 auto __x_index = __x.__hold_.index(); 224 auto __y_index = __y.__hold_.index(); 225 226 if (__x_index == 1 && __y_index == 1) 227 return 0; 228 229 if (__x_index == 0 && __y_index == 0) 230 return std::__unchecked_get<_Iter>(__x.__hold_) - std::__unchecked_get<_I2>(__y.__hold_); 231 232 if (__x_index == 0) 233 return std::__unchecked_get<_Iter>(__x.__hold_) - std::__unchecked_get<_S2>(__y.__hold_); 234 235 return std::__unchecked_get<_Sent>(__x.__hold_) - std::__unchecked_get<_I2>(__y.__hold_); 236 } 237 238 _LIBCPP_HIDE_FROM_ABI friend constexpr iter_rvalue_reference_t<_Iter> iter_move(const common_iterator & __i)239 iter_move(const common_iterator& __i) noexcept(noexcept(ranges::iter_move(std::declval<const _Iter&>()))) 240 requires input_iterator<_Iter> 241 { 242 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 243 std::holds_alternative<_Iter>(__i.__hold_), "Attempted to iter_move a non-dereferenceable common_iterator"); 244 return ranges::iter_move(std::__unchecked_get<_Iter>(__i.__hold_)); 245 } 246 247 template <indirectly_swappable<_Iter> _I2, class _S2> 248 _LIBCPP_HIDE_FROM_ABI friend constexpr void iter_swap(const common_iterator & __x,const common_iterator<_I2,_S2> & __y)249 iter_swap(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) noexcept( 250 noexcept(ranges::iter_swap(std::declval<const _Iter&>(), std::declval<const _I2&>()))) { 251 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 252 std::holds_alternative<_Iter>(__x.__hold_), "Attempted to iter_swap a non-dereferenceable common_iterator"); 253 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 254 std::holds_alternative<_I2>(__y.__hold_), "Attempted to iter_swap a non-dereferenceable common_iterator"); 255 return ranges::iter_swap(std::__unchecked_get<_Iter>(__x.__hold_), std::__unchecked_get<_I2>(__y.__hold_)); 256 } 257 }; 258 259 template <class _Iter, class _Sent> 260 struct incrementable_traits<common_iterator<_Iter, _Sent>> { 261 using difference_type = iter_difference_t<_Iter>; 262 }; 263 264 template <class _Iter> 265 concept __denotes_forward_iter = requires { 266 typename iterator_traits<_Iter>::iterator_category; 267 } && derived_from<typename iterator_traits<_Iter>::iterator_category, forward_iterator_tag>; 268 269 template <class _Iter, class _Sent> 270 concept __common_iter_has_ptr_op = requires(const common_iterator<_Iter, _Sent>& __a) { __a.operator->(); }; 271 272 template <class, class> 273 struct __arrow_type_or_void { 274 using type = void; 275 }; 276 277 template <class _Iter, class _Sent> 278 requires __common_iter_has_ptr_op<_Iter, _Sent> 279 struct __arrow_type_or_void<_Iter, _Sent> { 280 using type = decltype(std::declval<const common_iterator<_Iter, _Sent>&>().operator->()); 281 }; 282 283 template <input_iterator _Iter, class _Sent> 284 struct iterator_traits<common_iterator<_Iter, _Sent>> { 285 using iterator_concept = _If<forward_iterator<_Iter>, forward_iterator_tag, input_iterator_tag>; 286 using iterator_category = _If<__denotes_forward_iter<_Iter>, forward_iterator_tag, input_iterator_tag>; 287 using pointer = typename __arrow_type_or_void<_Iter, _Sent>::type; 288 using value_type = iter_value_t<_Iter>; 289 using difference_type = iter_difference_t<_Iter>; 290 using reference = iter_reference_t<_Iter>; 291 }; 292 293 #endif // _LIBCPP_STD_VER >= 20 294 295 _LIBCPP_END_NAMESPACE_STD 296 297 _LIBCPP_POP_MACROS 298 299 #endif // _LIBCPP___ITERATOR_COMMON_ITERATOR_H 300