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