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