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