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