master
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
46template <class _Iter>
47concept __can_use_postfix_proxy =
48 constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>> && move_constructible<iter_value_t<_Iter>>;
49
50template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
51 requires(!same_as<_Iter, _Sent> && copyable<_Iter>)
52class 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
70public:
71 _LIBCPP_HIDE_FROM_ABI common_iterator()
72 requires default_initializable<_Iter>
73 = default;
74
75 _LIBCPP_HIDE_FROM_ABI constexpr common_iterator(_Iter __i) : __hold_(in_place_type<_Iter>, std::move(__i)) {}
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>
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
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
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
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
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
261template <class _Iter, class _Sent>
262struct incrementable_traits<common_iterator<_Iter, _Sent>> {
263 using difference_type = iter_difference_t<_Iter>;
264};
265
266template <class _Iter>
267concept __denotes_forward_iter = requires {
268 typename iterator_traits<_Iter>::iterator_category;
269} && derived_from<typename iterator_traits<_Iter>::iterator_category, forward_iterator_tag>;
270
271template <class _Iter, class _Sent>
272concept __common_iter_has_ptr_op = requires(const common_iterator<_Iter, _Sent>& __a) { __a.operator->(); };
273
274template <class, class>
275struct __arrow_type_or_void {
276 using type _LIBCPP_NODEBUG = void;
277};
278
279template <class _Iter, class _Sent>
280 requires __common_iter_has_ptr_op<_Iter, _Sent>
281struct __arrow_type_or_void<_Iter, _Sent> {
282 using type _LIBCPP_NODEBUG = decltype(std::declval<const common_iterator<_Iter, _Sent>&>().operator->());
283};
284
285template <input_iterator _Iter, class _Sent>
286struct 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