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/get.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/pair_like.h>
33 #include <__tuple/tuple_element.h>
34 #include <__tuple/tuple_size.h>
35 #include <__type_traits/conditional.h>
36 #include <__type_traits/decay.h>
37 #include <__type_traits/is_pointer.h>
38 #include <__type_traits/is_reference.h>
39 #include <__type_traits/make_unsigned.h>
40 #include <__type_traits/remove_const.h>
41 #include <__type_traits/remove_pointer.h>
42 #include <__utility/move.h>
43 #include <cstddef>
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
56 namespace ranges {
57 template <class _From, class _To>
58 concept __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
62 template <class _From, class _To>
63 concept __convertible_to_non_slicing =
64 convertible_to<_From, _To> && !__uses_nonqualification_pointer_conversion<decay_t<_From>, decay_t<_To>>;
65
66 template <class _Pair, class _Iter, class _Sent>
67 concept __pair_like_convertible_from =
68 !range<_Pair> && __pair_like<_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
71 template <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>)
75 class _LIBCPP_TEMPLATE_VIS subrange : public view_interface<subrange<_Iter, _Sent, _Kind>> {
76 public:
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
80 private:
81 static constexpr bool _MustProvideSizeAtConstruction = !_StoreSize; // just to improve compiler diagnostics
82 struct _Empty {
_Empty_Empty83 _LIBCPP_HIDE_FROM_ABI constexpr _Empty(auto) noexcept {}
84 };
85 using _Size = 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
90 public:
91 _LIBCPP_HIDE_FROM_ABI subrange()
92 requires default_initializable<_Iter>
93 = default;
94
subrange(__convertible_to_non_slicing<_Iter> auto __iter,_Sent __sent)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
subrange(__convertible_to_non_slicing<_Iter> auto __iter,_Sent __sent,make_unsigned_t<iter_difference_t<_Iter>> __n)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>
subrange(_Range && __range)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>
subrange(_Range && __range)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>
subrange(_Range && __range,make_unsigned_t<iter_difference_t<_Iter>> __n)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 <__different_from<subrange> _Pair>
130 requires __pair_like_convertible_from<_Pair, const _Iter&, const _Sent&>
_Pair()131 _LIBCPP_HIDE_FROM_ABI constexpr operator _Pair() const {
132 return _Pair(__begin_, __end_);
133 }
134
begin()135 _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin() const
136 requires copyable<_Iter>
137 {
138 return __begin_;
139 }
140
begin()141 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin()
142 requires(!copyable<_Iter>)
143 {
144 return std::move(__begin_);
145 }
146
end()147 _LIBCPP_HIDE_FROM_ABI constexpr _Sent end() const { return __end_; }
148
empty()149 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool empty() const { return __begin_ == __end_; }
150
size()151 _LIBCPP_HIDE_FROM_ABI constexpr make_unsigned_t<iter_difference_t<_Iter>> size() const
152 requires(_Kind == subrange_kind::sized)
153 {
154 if constexpr (_StoreSize)
155 return __size_;
156 else
157 return std::__to_unsigned_like(__end_ - __begin_);
158 }
159
160 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) const&
161 requires forward_iterator<_Iter>
162 {
163 auto __tmp = *this;
164 __tmp.advance(__n);
165 return __tmp;
166 }
167
168 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) && {
169 advance(__n);
170 return std::move(*this);
171 }
172
173 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange prev(iter_difference_t<_Iter> __n = 1) const
174 requires bidirectional_iterator<_Iter>
175 {
176 auto __tmp = *this;
177 __tmp.advance(-__n);
178 return __tmp;
179 }
180
advance(iter_difference_t<_Iter> __n)181 _LIBCPP_HIDE_FROM_ABI constexpr subrange& advance(iter_difference_t<_Iter> __n) {
182 if constexpr (bidirectional_iterator<_Iter>) {
183 if (__n < 0) {
184 ranges::advance(__begin_, __n);
185 if constexpr (_StoreSize)
186 __size_ += std::__to_unsigned_like(-__n);
187 return *this;
188 }
189 }
190
191 auto __d = __n - ranges::advance(__begin_, __n, __end_);
192 if constexpr (_StoreSize)
193 __size_ -= std::__to_unsigned_like(__d);
194 return *this;
195 }
196 };
197
198 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
199 subrange(_Iter, _Sent) -> subrange<_Iter, _Sent>;
200
201 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
202 subrange(_Iter, _Sent, make_unsigned_t<iter_difference_t<_Iter>>) -> subrange<_Iter, _Sent, subrange_kind::sized>;
203
204 template <borrowed_range _Range>
205 subrange(_Range&&)
206 -> subrange<iterator_t<_Range>,
207 sentinel_t<_Range>,
208 (sized_range<_Range> || sized_sentinel_for<sentinel_t<_Range>, iterator_t<_Range>>)
209 ? subrange_kind::sized
210 : subrange_kind::unsized>;
211
212 template <borrowed_range _Range>
213 subrange(_Range&&, make_unsigned_t<range_difference_t<_Range>>)
214 -> subrange<iterator_t<_Range>, sentinel_t<_Range>, subrange_kind::sized>;
215
216 template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>
217 requires((_Index == 0 && copyable<_Iter>) || _Index == 1)
get(const subrange<_Iter,_Sent,_Kind> & __subrange)218 _LIBCPP_HIDE_FROM_ABI constexpr auto get(const subrange<_Iter, _Sent, _Kind>& __subrange) {
219 if constexpr (_Index == 0)
220 return __subrange.begin();
221 else
222 return __subrange.end();
223 }
224
225 template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>
226 requires(_Index < 2)
get(subrange<_Iter,_Sent,_Kind> && __subrange)227 _LIBCPP_HIDE_FROM_ABI constexpr auto get(subrange<_Iter, _Sent, _Kind>&& __subrange) {
228 if constexpr (_Index == 0)
229 return __subrange.begin();
230 else
231 return __subrange.end();
232 }
233
234 template <class _Ip, class _Sp, subrange_kind _Kp>
235 inline constexpr bool enable_borrowed_range<subrange<_Ip, _Sp, _Kp>> = true;
236
237 template <range _Rp>
238 using borrowed_subrange_t = _If<borrowed_range<_Rp>, subrange<iterator_t<_Rp>>, dangling>;
239 } // namespace ranges
240
241 // [range.subrange.general]
242
243 using ranges::get;
244
245 // [ranges.syn]
246
247 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
248 struct tuple_size<ranges::subrange<_Ip, _Sp, _Kp>> : integral_constant<size_t, 2> {};
249
250 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
251 struct tuple_element<0, ranges::subrange<_Ip, _Sp, _Kp>> {
252 using type = _Ip;
253 };
254
255 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
256 struct tuple_element<1, ranges::subrange<_Ip, _Sp, _Kp>> {
257 using type = _Sp;
258 };
259
260 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
261 struct tuple_element<0, const ranges::subrange<_Ip, _Sp, _Kp>> {
262 using type = _Ip;
263 };
264
265 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
266 struct tuple_element<1, const ranges::subrange<_Ip, _Sp, _Kp>> {
267 using type = _Sp;
268 };
269
270 #endif // _LIBCPP_STD_VER >= 20
271
272 _LIBCPP_END_NAMESPACE_STD
273
274 _LIBCPP_POP_MACROS
275
276 #endif // _LIBCPP___RANGES_SUBRANGE_H
277