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