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