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