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