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___RANGES_SUBRANGE_H
11#define _LIBCPP___RANGES_SUBRANGE_H
12
13#include <__assert>
14#include <__concepts/constructible.h>
15#include <__concepts/convertible_to.h>
16#include <__concepts/copyable.h>
17#include <__concepts/derived_from.h>
18#include <__concepts/different_from.h>
19#include <__config>
20#include <__fwd/subrange.h>
21#include <__iterator/advance.h>
22#include <__iterator/concepts.h>
23#include <__iterator/incrementable_traits.h>
24#include <__iterator/iterator_traits.h>
25#include <__ranges/access.h>
26#include <__ranges/concepts.h>
27#include <__ranges/dangling.h>
28#include <__ranges/enable_borrowed_range.h>
29#include <__ranges/size.h>
30#include <__ranges/view_interface.h>
31#include <__tuple/tuple_element.h>
32#include <__tuple/tuple_like_no_subrange.h>
33#include <__tuple/tuple_size.h>
34#include <__type_traits/conditional.h>
35#include <__type_traits/decay.h>
36#include <__type_traits/is_pointer.h>
37#include <__type_traits/is_reference.h>
38#include <__type_traits/make_unsigned.h>
39#include <__type_traits/remove_const.h>
40#include <__type_traits/remove_pointer.h>
41#include <__utility/move.h>
42#include <cstddef>
43
44#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
45# pragma GCC system_header
46#endif
47
48_LIBCPP_PUSH_MACROS
49#include <__undef_macros>
50
51_LIBCPP_BEGIN_NAMESPACE_STD
52
53#if _LIBCPP_STD_VER >= 20
54
55namespace ranges {
56template <class _From, class _To>
57concept __uses_nonqualification_pointer_conversion =
58 is_pointer_v<_From> && is_pointer_v<_To> &&
59 !convertible_to<remove_pointer_t<_From> (*)[], remove_pointer_t<_To> (*)[]>;
60
61template <class _From, class _To>
62concept __convertible_to_non_slicing =
63 convertible_to<_From, _To> && !__uses_nonqualification_pointer_conversion<decay_t<_From>, decay_t<_To>>;
64
65template <class _Pair, class _Iter, class _Sent>
66concept __pair_like_convertible_from =
67 !range<_Pair> && __pair_like_no_subrange<_Pair> && constructible_from<_Pair, _Iter, _Sent> &&
68 __convertible_to_non_slicing<_Iter, tuple_element_t<0, _Pair>> && convertible_to<_Sent, tuple_element_t<1, _Pair>>;
69
70template <input_or_output_iterator _Iter,
71 sentinel_for<_Iter> _Sent = _Iter,
72 subrange_kind _Kind = sized_sentinel_for<_Sent, _Iter> ? subrange_kind::sized : subrange_kind::unsized>
73 requires(_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _Iter>)
74class _LIBCPP_TEMPLATE_VIS subrange : public view_interface<subrange<_Iter, _Sent, _Kind>> {
75public:
76 // Note: this is an internal implementation detail that is public only for internal usage.
77 static constexpr bool _StoreSize = (_Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _Iter>);
78
79private:
80 static constexpr bool _MustProvideSizeAtConstruction = !_StoreSize; // just to improve compiler diagnostics
81 struct _Empty {
82 _LIBCPP_HIDE_FROM_ABI constexpr _Empty(auto) noexcept {}
83 };
84 using _Size = conditional_t<_StoreSize, make_unsigned_t<iter_difference_t<_Iter>>, _Empty>;
85 _LIBCPP_NO_UNIQUE_ADDRESS _Iter __begin_ = _Iter();
86 _LIBCPP_NO_UNIQUE_ADDRESS _Sent __end_ = _Sent();
87 _LIBCPP_NO_UNIQUE_ADDRESS _Size __size_ = 0;
88
89public:
90 _LIBCPP_HIDE_FROM_ABI subrange()
91 requires default_initializable<_Iter>
92 = default;
93
94 _LIBCPP_HIDE_FROM_ABI constexpr subrange(__convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent)
95 requires _MustProvideSizeAtConstruction
96 : __begin_(std::move(__iter)), __end_(std::move(__sent)) {}
97
98 _LIBCPP_HIDE_FROM_ABI constexpr subrange(
99 __convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent, make_unsigned_t<iter_difference_t<_Iter>> __n)
100 requires(_Kind == subrange_kind::sized)
101 : __begin_(std::move(__iter)), __end_(std::move(__sent)), __size_(__n) {
102 if constexpr (sized_sentinel_for<_Sent, _Iter>)
103 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS((__end_ - __begin_) == static_cast<iter_difference_t<_Iter>>(__n),
104 "std::ranges::subrange was passed an invalid size hint");
105 }
106
107 template <__different_from<subrange> _Range>
108 requires borrowed_range<_Range> && __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&
109 convertible_to<sentinel_t<_Range>, _Sent>
110 _LIBCPP_HIDE_FROM_ABI constexpr subrange(_Range&& __range)
111 requires(!_StoreSize)
112 : subrange(ranges::begin(__range), ranges::end(__range)) {}
113
114 template <__different_from<subrange> _Range>
115 requires borrowed_range<_Range> && __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&
116 convertible_to<sentinel_t<_Range>, _Sent>
117 _LIBCPP_HIDE_FROM_ABI constexpr subrange(_Range&& __range)
118 requires _StoreSize && sized_range<_Range>
119 : subrange(__range, ranges::size(__range)) {}
120
121 template <borrowed_range _Range>
122 requires __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&
123 convertible_to<sentinel_t<_Range>, _Sent>
124 _LIBCPP_HIDE_FROM_ABI constexpr subrange(_Range&& __range, make_unsigned_t<iter_difference_t<_Iter>> __n)
125 requires(_Kind == subrange_kind::sized)
126 : subrange(ranges::begin(__range), ranges::end(__range), __n) {}
127
128 template <__pair_like_convertible_from<const _Iter&, const _Sent&> _Pair>
129 _LIBCPP_HIDE_FROM_ABI constexpr operator _Pair() const {
130 return _Pair(__begin_, __end_);
131 }
132
133 _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin() const
134 requires copyable<_Iter>
135 {
136 return __begin_;
137 }
138
139 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin()
140 requires(!copyable<_Iter>)
141 {
142 return std::move(__begin_);
143 }
144
145 _LIBCPP_HIDE_FROM_ABI constexpr _Sent end() const { return __end_; }
146
147 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool empty() const { return __begin_ == __end_; }
148
149 _LIBCPP_HIDE_FROM_ABI constexpr make_unsigned_t<iter_difference_t<_Iter>> size() const
150 requires(_Kind == subrange_kind::sized)
151 {
152 if constexpr (_StoreSize)
153 return __size_;
154 else
155 return std::__to_unsigned_like(__end_ - __begin_);
156 }
157
158 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) const&
159 requires forward_iterator<_Iter>
160 {
161 auto __tmp = *this;
162 __tmp.advance(__n);
163 return __tmp;
164 }
165
166 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) && {
167 advance(__n);
168 return std::move(*this);
169 }
170
171 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange prev(iter_difference_t<_Iter> __n = 1) const
172 requires bidirectional_iterator<_Iter>
173 {
174 auto __tmp = *this;
175 __tmp.advance(-__n);
176 return __tmp;
177 }
178
179 _LIBCPP_HIDE_FROM_ABI constexpr subrange& advance(iter_difference_t<_Iter> __n) {
180 if constexpr (bidirectional_iterator<_Iter>) {
181 if (__n < 0) {
182 ranges::advance(__begin_, __n);
183 if constexpr (_StoreSize)
184 __size_ += std::__to_unsigned_like(-__n);
185 return *this;
186 }
187 }
188
189 auto __d = __n - ranges::advance(__begin_, __n, __end_);
190 if constexpr (_StoreSize)
191 __size_ -= std::__to_unsigned_like(__d);
192 return *this;
193 }
194};
195
196template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
197subrange(_Iter, _Sent) -> subrange<_Iter, _Sent>;
198
199template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
200subrange(_Iter, _Sent, make_unsigned_t<iter_difference_t<_Iter>>) -> subrange<_Iter, _Sent, subrange_kind::sized>;
201
202template <borrowed_range _Range>
203subrange(_Range&&) -> subrange<iterator_t<_Range>,
204 sentinel_t<_Range>,
205 (sized_range<_Range> || sized_sentinel_for<sentinel_t<_Range>, iterator_t<_Range>>)
206 ? subrange_kind::sized
207 : subrange_kind::unsized>;
208
209template <borrowed_range _Range>
210subrange(_Range&&, make_unsigned_t<range_difference_t<_Range>>)
211 -> subrange<iterator_t<_Range>, sentinel_t<_Range>, subrange_kind::sized>;
212
213template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>
214 requires((_Index == 0 && copyable<_Iter>) || _Index == 1)
215_LIBCPP_HIDE_FROM_ABI constexpr auto get(const subrange<_Iter, _Sent, _Kind>& __subrange) {
216 if constexpr (_Index == 0)
217 return __subrange.begin();
218 else
219 return __subrange.end();
220}
221
222template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>
223 requires(_Index < 2)
224_LIBCPP_HIDE_FROM_ABI constexpr auto get(subrange<_Iter, _Sent, _Kind>&& __subrange) {
225 if constexpr (_Index == 0)
226 return __subrange.begin();
227 else
228 return __subrange.end();
229}
230
231template <class _Ip, class _Sp, subrange_kind _Kp>
232inline constexpr bool enable_borrowed_range<subrange<_Ip, _Sp, _Kp>> = true;
233
234template <range _Rp>
235using borrowed_subrange_t = _If<borrowed_range<_Rp>, subrange<iterator_t<_Rp>>, dangling>;
236} // namespace ranges
237
238// [range.subrange.general]
239
240using ranges::get;
241
242// [ranges.syn]
243
244template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
245struct tuple_size<ranges::subrange<_Ip, _Sp, _Kp>> : integral_constant<size_t, 2> {};
246
247template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
248struct tuple_element<0, ranges::subrange<_Ip, _Sp, _Kp>> {
249 using type = _Ip;
250};
251
252template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
253struct tuple_element<1, ranges::subrange<_Ip, _Sp, _Kp>> {
254 using type = _Sp;
255};
256
257template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
258struct tuple_element<0, const ranges::subrange<_Ip, _Sp, _Kp>> {
259 using type = _Ip;
260};
261
262template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
263struct tuple_element<1, const ranges::subrange<_Ip, _Sp, _Kp>> {
264 using type = _Sp;
265};
266
267#endif // _LIBCPP_STD_VER >= 20
268
269_LIBCPP_END_NAMESPACE_STD
270
271_LIBCPP_POP_MACROS
272
273#endif // _LIBCPP___RANGES_SUBRANGE_H
274