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