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