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
55 namespace ranges {
56 template <class _From, class _To>
57 concept __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
61 template <class _From, class _To>
62 concept __convertible_to_non_slicing =
63 convertible_to<_From, _To> && !__uses_nonqualification_pointer_conversion<decay_t<_From>, decay_t<_To>>;
64
65 template <class _Pair, class _Iter, class _Sent>
66 concept __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
70 template <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>)
74 class _LIBCPP_TEMPLATE_VIS subrange : public view_interface<subrange<_Iter, _Sent, _Kind>> {
75 public:
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
79 private:
80 static constexpr bool _MustProvideSizeAtConstruction = !_StoreSize; // just to improve compiler diagnostics
81 struct _Empty {
_Empty_Empty82 _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
89 public:
90 _LIBCPP_HIDE_FROM_ABI subrange()
91 requires default_initializable<_Iter>
92 = default;
93
subrange(__convertible_to_non_slicing<_Iter> auto __iter,_Sent __sent)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
subrange(__convertible_to_non_slicing<_Iter> auto __iter,_Sent __sent,make_unsigned_t<iter_difference_t<_Iter>> __n)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>
subrange(_Range && __range)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>
subrange(_Range && __range)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>
subrange(_Range && __range,make_unsigned_t<iter_difference_t<_Iter>> __n)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>
_Pair()129 _LIBCPP_HIDE_FROM_ABI constexpr operator _Pair() const {
130 return _Pair(__begin_, __end_);
131 }
132
begin()133 _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin() const
134 requires copyable<_Iter>
135 {
136 return __begin_;
137 }
138
begin()139 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin()
140 requires(!copyable<_Iter>)
141 {
142 return std::move(__begin_);
143 }
144
end()145 _LIBCPP_HIDE_FROM_ABI constexpr _Sent end() const { return __end_; }
146
empty()147 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool empty() const { return __begin_ == __end_; }
148
size()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
advance(iter_difference_t<_Iter> __n)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
196 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
197 subrange(_Iter, _Sent) -> subrange<_Iter, _Sent>;
198
199 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
200 subrange(_Iter, _Sent, make_unsigned_t<iter_difference_t<_Iter>>) -> subrange<_Iter, _Sent, subrange_kind::sized>;
201
202 template <borrowed_range _Range>
203 subrange(_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
209 template <borrowed_range _Range>
210 subrange(_Range&&, make_unsigned_t<range_difference_t<_Range>>)
211 -> subrange<iterator_t<_Range>, sentinel_t<_Range>, subrange_kind::sized>;
212
213 template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>
214 requires((_Index == 0 && copyable<_Iter>) || _Index == 1)
get(const subrange<_Iter,_Sent,_Kind> & __subrange)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
222 template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>
223 requires(_Index < 2)
get(subrange<_Iter,_Sent,_Kind> && __subrange)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
231 template <class _Ip, class _Sp, subrange_kind _Kp>
232 inline constexpr bool enable_borrowed_range<subrange<_Ip, _Sp, _Kp>> = true;
233
234 template <range _Rp>
235 using borrowed_subrange_t = _If<borrowed_range<_Rp>, subrange<iterator_t<_Rp>>, dangling>;
236 } // namespace ranges
237
238 // [range.subrange.general]
239
240 using ranges::get;
241
242 // [ranges.syn]
243
244 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
245 struct tuple_size<ranges::subrange<_Ip, _Sp, _Kp>> : integral_constant<size_t, 2> {};
246
247 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
248 struct tuple_element<0, ranges::subrange<_Ip, _Sp, _Kp>> {
249 using type = _Ip;
250 };
251
252 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
253 struct tuple_element<1, ranges::subrange<_Ip, _Sp, _Kp>> {
254 using type = _Sp;
255 };
256
257 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
258 struct tuple_element<0, const ranges::subrange<_Ip, _Sp, _Kp>> {
259 using type = _Ip;
260 };
261
262 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
263 struct 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