1 | // Core concepts and definitions for <ranges> -*- C++ -*- |
2 | |
3 | // Copyright (C) 2019-2024 Free Software Foundation, Inc. |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free |
6 | // software; you can redistribute it and/or modify it under the |
7 | // terms of the GNU General Public License as published by the |
8 | // Free Software Foundation; either version 3, or (at your option) |
9 | // any later version. |
10 | |
11 | // This library is distributed in the hope that it will be useful, |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 | // GNU General Public License for more details. |
15 | |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version |
18 | // 3.1, as published by the Free Software Foundation. |
19 | |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
23 | // <http://www.gnu.org/licenses/>. |
24 | |
25 | /** @file bits/ranges_base.h |
26 | * This is an internal header file, included by other library headers. |
27 | * Do not attempt to use it directly. @headername{ranges} |
28 | */ |
29 | |
30 | #ifndef _GLIBCXX_RANGES_BASE_H |
31 | #define _GLIBCXX_RANGES_BASE_H 1 |
32 | |
33 | #pragma GCC system_header |
34 | |
35 | #if __cplusplus > 201703L |
36 | #include <initializer_list> |
37 | #include <bits/stl_iterator.h> |
38 | #include <ext/numeric_traits.h> |
39 | #include <bits/max_size_type.h> |
40 | #include <bits/version.h> |
41 | |
42 | #ifdef __cpp_lib_concepts |
43 | namespace std _GLIBCXX_VISIBILITY(default) |
44 | { |
45 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
46 | namespace ranges |
47 | { |
48 | template<typename> |
49 | inline constexpr bool disable_sized_range = false; |
50 | |
51 | template<typename _Tp> |
52 | inline constexpr bool enable_borrowed_range = false; |
53 | |
54 | namespace __detail |
55 | { |
56 | constexpr __max_size_type |
57 | __to_unsigned_like(__max_size_type __t) noexcept |
58 | { return __t; } |
59 | |
60 | constexpr __max_size_type |
61 | __to_unsigned_like(__max_diff_type __t) noexcept |
62 | { return __max_size_type(__t); } |
63 | |
64 | template<integral _Tp> |
65 | constexpr auto |
66 | __to_unsigned_like(_Tp __t) noexcept |
67 | { return static_cast<make_unsigned_t<_Tp>>(__t); } |
68 | |
69 | #if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__ |
70 | constexpr unsigned __int128 |
71 | __to_unsigned_like(__int128 __t) noexcept |
72 | { return __t; } |
73 | |
74 | constexpr unsigned __int128 |
75 | __to_unsigned_like(unsigned __int128 __t) noexcept |
76 | { return __t; } |
77 | #endif |
78 | |
79 | template<typename _Tp> |
80 | using __make_unsigned_like_t |
81 | = decltype(__detail::__to_unsigned_like(std::declval<_Tp>())); |
82 | |
83 | // Part of the constraints of ranges::borrowed_range |
84 | template<typename _Tp> |
85 | concept __maybe_borrowed_range |
86 | = is_lvalue_reference_v<_Tp> |
87 | || enable_borrowed_range<remove_cvref_t<_Tp>>; |
88 | |
89 | } // namespace __detail |
90 | |
91 | // Namespace for helpers for the <ranges> customization points. |
92 | namespace __access |
93 | { |
94 | using std::ranges::__detail::__maybe_borrowed_range; |
95 | using std::__detail::__range_iter_t; |
96 | |
97 | struct _Begin |
98 | { |
99 | private: |
100 | template<typename _Tp> |
101 | static constexpr bool |
102 | _S_noexcept() |
103 | { |
104 | if constexpr (is_array_v<remove_reference_t<_Tp>>) |
105 | return true; |
106 | else if constexpr (__member_begin<_Tp>) |
107 | return noexcept(__decay_copy(std::declval<_Tp&>().begin())); |
108 | else |
109 | return noexcept(__decay_copy(begin(std::declval<_Tp&>()))); |
110 | } |
111 | |
112 | public: |
113 | template<__maybe_borrowed_range _Tp> |
114 | requires is_array_v<remove_reference_t<_Tp>> || __member_begin<_Tp> |
115 | || __adl_begin<_Tp> |
116 | constexpr auto |
117 | operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>()) |
118 | { |
119 | if constexpr (is_array_v<remove_reference_t<_Tp>>) |
120 | { |
121 | static_assert(is_lvalue_reference_v<_Tp>); |
122 | return __t + 0; |
123 | } |
124 | else if constexpr (__member_begin<_Tp>) |
125 | return __t.begin(); |
126 | else |
127 | return begin(__t); |
128 | } |
129 | }; |
130 | |
131 | template<typename _Tp> |
132 | concept __member_end = requires(_Tp& __t) |
133 | { |
134 | { __decay_copy(__t.end()) } -> sentinel_for<__range_iter_t<_Tp>>; |
135 | }; |
136 | |
137 | // Poison pill so that unqualified lookup doesn't find std::end. |
138 | void end() = delete; |
139 | |
140 | template<typename _Tp> |
141 | concept __adl_end = __class_or_enum<remove_reference_t<_Tp>> |
142 | && requires(_Tp& __t) |
143 | { |
144 | { __decay_copy(end(__t)) } -> sentinel_for<__range_iter_t<_Tp>>; |
145 | }; |
146 | |
147 | struct _End |
148 | { |
149 | private: |
150 | template<typename _Tp> |
151 | static constexpr bool |
152 | _S_noexcept() |
153 | { |
154 | if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>) |
155 | return true; |
156 | else if constexpr (__member_end<_Tp>) |
157 | return noexcept(__decay_copy(std::declval<_Tp&>().end())); |
158 | else |
159 | return noexcept(__decay_copy(end(std::declval<_Tp&>()))); |
160 | } |
161 | |
162 | public: |
163 | template<__maybe_borrowed_range _Tp> |
164 | requires is_bounded_array_v<remove_reference_t<_Tp>> |
165 | || __member_end<_Tp> || __adl_end<_Tp> |
166 | constexpr auto |
167 | operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>()) |
168 | { |
169 | if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>) |
170 | { |
171 | static_assert(is_lvalue_reference_v<_Tp>); |
172 | return __t + extent_v<remove_reference_t<_Tp>>; |
173 | } |
174 | else if constexpr (__member_end<_Tp>) |
175 | return __t.end(); |
176 | else |
177 | return end(__t); |
178 | } |
179 | }; |
180 | |
181 | template<typename _Tp> |
182 | concept __member_rbegin = requires(_Tp& __t) |
183 | { |
184 | { __decay_copy(__t.rbegin()) } -> input_or_output_iterator; |
185 | }; |
186 | |
187 | void rbegin() = delete; |
188 | |
189 | template<typename _Tp> |
190 | concept __adl_rbegin = __class_or_enum<remove_reference_t<_Tp>> |
191 | && requires(_Tp& __t) |
192 | { |
193 | { __decay_copy(rbegin(__t)) } -> input_or_output_iterator; |
194 | }; |
195 | |
196 | template<typename _Tp> |
197 | concept __reversable = requires(_Tp& __t) |
198 | { |
199 | { _Begin{}(__t) } -> bidirectional_iterator; |
200 | { _End{}(__t) } -> same_as<decltype(_Begin{}(__t))>; |
201 | }; |
202 | |
203 | struct _RBegin |
204 | { |
205 | private: |
206 | template<typename _Tp> |
207 | static constexpr bool |
208 | _S_noexcept() |
209 | { |
210 | if constexpr (__member_rbegin<_Tp>) |
211 | return noexcept(__decay_copy(std::declval<_Tp&>().rbegin())); |
212 | else if constexpr (__adl_rbegin<_Tp>) |
213 | return noexcept(__decay_copy(rbegin(std::declval<_Tp&>()))); |
214 | else |
215 | { |
216 | if constexpr (noexcept(_End{}(std::declval<_Tp&>()))) |
217 | { |
218 | using _It = decltype(_End{}(std::declval<_Tp&>())); |
219 | // std::reverse_iterator copy-initializes its member. |
220 | return is_nothrow_copy_constructible_v<_It>; |
221 | } |
222 | else |
223 | return false; |
224 | } |
225 | } |
226 | |
227 | public: |
228 | template<__maybe_borrowed_range _Tp> |
229 | requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp> |
230 | constexpr auto |
231 | operator()[[nodiscard]](_Tp&& __t) const |
232 | noexcept(_S_noexcept<_Tp&>()) |
233 | { |
234 | if constexpr (__member_rbegin<_Tp>) |
235 | return __t.rbegin(); |
236 | else if constexpr (__adl_rbegin<_Tp>) |
237 | return rbegin(__t); |
238 | else |
239 | return std::make_reverse_iterator(_End{}(__t)); |
240 | } |
241 | }; |
242 | |
243 | template<typename _Tp> |
244 | concept __member_rend = requires(_Tp& __t) |
245 | { |
246 | { __decay_copy(__t.rend()) } |
247 | -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>; |
248 | }; |
249 | |
250 | void rend() = delete; |
251 | |
252 | template<typename _Tp> |
253 | concept __adl_rend = __class_or_enum<remove_reference_t<_Tp>> |
254 | && requires(_Tp& __t) |
255 | { |
256 | { __decay_copy(rend(__t)) } |
257 | -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>; |
258 | }; |
259 | |
260 | struct _REnd |
261 | { |
262 | private: |
263 | template<typename _Tp> |
264 | static constexpr bool |
265 | _S_noexcept() |
266 | { |
267 | if constexpr (__member_rend<_Tp>) |
268 | return noexcept(__decay_copy(std::declval<_Tp&>().rend())); |
269 | else if constexpr (__adl_rend<_Tp>) |
270 | return noexcept(__decay_copy(rend(std::declval<_Tp&>()))); |
271 | else |
272 | { |
273 | if constexpr (noexcept(_Begin{}(std::declval<_Tp&>()))) |
274 | { |
275 | using _It = decltype(_Begin{}(std::declval<_Tp&>())); |
276 | // std::reverse_iterator copy-initializes its member. |
277 | return is_nothrow_copy_constructible_v<_It>; |
278 | } |
279 | else |
280 | return false; |
281 | } |
282 | } |
283 | |
284 | public: |
285 | template<__maybe_borrowed_range _Tp> |
286 | requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp> |
287 | constexpr auto |
288 | operator()[[nodiscard]](_Tp&& __t) const |
289 | noexcept(_S_noexcept<_Tp&>()) |
290 | { |
291 | if constexpr (__member_rend<_Tp>) |
292 | return __t.rend(); |
293 | else if constexpr (__adl_rend<_Tp>) |
294 | return rend(__t); |
295 | else |
296 | return std::make_reverse_iterator(_Begin{}(__t)); |
297 | } |
298 | }; |
299 | |
300 | template<typename _Tp> |
301 | concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>> |
302 | && requires(_Tp& __t) |
303 | { |
304 | { __decay_copy(__t.size()) } -> __detail::__is_integer_like; |
305 | }; |
306 | |
307 | void size() = delete; |
308 | |
309 | template<typename _Tp> |
310 | concept __adl_size = __class_or_enum<remove_reference_t<_Tp>> |
311 | && !disable_sized_range<remove_cvref_t<_Tp>> |
312 | && requires(_Tp& __t) |
313 | { |
314 | { __decay_copy(size(__t)) } -> __detail::__is_integer_like; |
315 | }; |
316 | |
317 | template<typename _Tp> |
318 | concept __sentinel_size = requires(_Tp& __t) |
319 | { |
320 | requires (!is_unbounded_array_v<remove_reference_t<_Tp>>); |
321 | |
322 | { _Begin{}(__t) } -> forward_iterator; |
323 | |
324 | { _End{}(__t) } -> sized_sentinel_for<decltype(_Begin{}(__t))>; |
325 | |
326 | __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t)); |
327 | }; |
328 | |
329 | struct _Size |
330 | { |
331 | private: |
332 | template<typename _Tp> |
333 | static constexpr bool |
334 | _S_noexcept() |
335 | { |
336 | if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>) |
337 | return true; |
338 | else if constexpr (__member_size<_Tp>) |
339 | return noexcept(__decay_copy(std::declval<_Tp&>().size())); |
340 | else if constexpr (__adl_size<_Tp>) |
341 | return noexcept(__decay_copy(size(std::declval<_Tp&>()))); |
342 | else if constexpr (__sentinel_size<_Tp>) |
343 | return noexcept(_End{}(std::declval<_Tp&>()) |
344 | - _Begin{}(std::declval<_Tp&>())); |
345 | } |
346 | |
347 | public: |
348 | template<typename _Tp> |
349 | requires is_bounded_array_v<remove_reference_t<_Tp>> |
350 | || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp> |
351 | constexpr auto |
352 | operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>()) |
353 | { |
354 | if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>) |
355 | return extent_v<remove_reference_t<_Tp>>; |
356 | else if constexpr (__member_size<_Tp>) |
357 | return __t.size(); |
358 | else if constexpr (__adl_size<_Tp>) |
359 | return size(__t); |
360 | else if constexpr (__sentinel_size<_Tp>) |
361 | return __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t)); |
362 | } |
363 | }; |
364 | |
365 | struct _SSize |
366 | { |
367 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
368 | // 3403. Domain of ranges::ssize(E) doesn't match ranges::size(E) |
369 | template<typename _Tp> |
370 | requires requires (_Tp& __t) { _Size{}(__t); } |
371 | constexpr auto |
372 | operator()[[nodiscard]](_Tp&& __t) const noexcept(noexcept(_Size{}(__t))) |
373 | { |
374 | auto __size = _Size{}(__t); |
375 | using __size_type = decltype(__size); |
376 | // Return the wider of ptrdiff_t and make-signed-like-t<__size_type>. |
377 | if constexpr (integral<__size_type>) |
378 | { |
379 | using __gnu_cxx::__int_traits; |
380 | if constexpr (__int_traits<__size_type>::__digits |
381 | < __int_traits<ptrdiff_t>::__digits) |
382 | return static_cast<ptrdiff_t>(__size); |
383 | else |
384 | return static_cast<make_signed_t<__size_type>>(__size); |
385 | } |
386 | #if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__ |
387 | // For strict-ansi modes integral<__int128> is false |
388 | else if constexpr (__detail::__is_int128<__size_type>) |
389 | return static_cast<__int128>(__size); |
390 | #endif |
391 | else // Must be one of __max_diff_type or __max_size_type. |
392 | return __detail::__max_diff_type(__size); |
393 | } |
394 | }; |
395 | |
396 | template<typename _Tp> |
397 | concept __member_empty = requires(_Tp& __t) { bool(__t.empty()); }; |
398 | |
399 | template<typename _Tp> |
400 | concept __size0_empty = requires(_Tp& __t) { _Size{}(__t) == 0; }; |
401 | |
402 | template<typename _Tp> |
403 | concept __eq_iter_empty = requires(_Tp& __t) |
404 | { |
405 | requires (!is_unbounded_array_v<remove_reference_t<_Tp>>); |
406 | |
407 | { _Begin{}(__t) } -> forward_iterator; |
408 | |
409 | bool(_Begin{}(__t) == _End{}(__t)); |
410 | }; |
411 | |
412 | struct _Empty |
413 | { |
414 | private: |
415 | template<typename _Tp> |
416 | static constexpr bool |
417 | _S_noexcept() |
418 | { |
419 | if constexpr (__member_empty<_Tp>) |
420 | return noexcept(bool(std::declval<_Tp&>().empty())); |
421 | else if constexpr (__size0_empty<_Tp>) |
422 | return noexcept(_Size{}(std::declval<_Tp&>()) == 0); |
423 | else |
424 | return noexcept(bool(_Begin{}(std::declval<_Tp&>()) |
425 | == _End{}(std::declval<_Tp&>()))); |
426 | } |
427 | |
428 | public: |
429 | template<typename _Tp> |
430 | requires __member_empty<_Tp> || __size0_empty<_Tp> |
431 | || __eq_iter_empty<_Tp> |
432 | constexpr bool |
433 | operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>()) |
434 | { |
435 | if constexpr (__member_empty<_Tp>) |
436 | return bool(__t.empty()); |
437 | else if constexpr (__size0_empty<_Tp>) |
438 | return _Size{}(__t) == 0; |
439 | else |
440 | return bool(_Begin{}(__t) == _End{}(__t)); |
441 | } |
442 | }; |
443 | |
444 | template<typename _Tp> |
445 | concept __pointer_to_object = is_pointer_v<_Tp> |
446 | && is_object_v<remove_pointer_t<_Tp>>; |
447 | |
448 | template<typename _Tp> |
449 | concept __member_data = requires(_Tp& __t) |
450 | { |
451 | { __decay_copy(__t.data()) } -> __pointer_to_object; |
452 | }; |
453 | |
454 | template<typename _Tp> |
455 | concept __begin_data = contiguous_iterator<__range_iter_t<_Tp>>; |
456 | |
457 | struct _Data |
458 | { |
459 | private: |
460 | template<typename _Tp> |
461 | static constexpr bool |
462 | _S_noexcept() |
463 | { |
464 | if constexpr (__member_data<_Tp>) |
465 | return noexcept(__decay_copy(std::declval<_Tp&>().data())); |
466 | else |
467 | return noexcept(_Begin{}(std::declval<_Tp&>())); |
468 | } |
469 | |
470 | public: |
471 | template<__maybe_borrowed_range _Tp> |
472 | requires __member_data<_Tp> || __begin_data<_Tp> |
473 | constexpr auto |
474 | operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp>()) |
475 | { |
476 | if constexpr (__member_data<_Tp>) |
477 | return __t.data(); |
478 | else |
479 | return std::to_address(_Begin{}(__t)); |
480 | } |
481 | }; |
482 | |
483 | } // namespace __access |
484 | |
485 | inline namespace _Cpo |
486 | { |
487 | inline constexpr ranges::__access::_Begin begin{}; |
488 | inline constexpr ranges::__access::_End end{}; |
489 | inline constexpr ranges::__access::_RBegin rbegin{}; |
490 | inline constexpr ranges::__access::_REnd rend{}; |
491 | inline constexpr ranges::__access::_Size size{}; |
492 | inline constexpr ranges::__access::_SSize ssize{}; |
493 | inline constexpr ranges::__access::_Empty empty{}; |
494 | inline constexpr ranges::__access::_Data data{}; |
495 | } |
496 | |
497 | /// [range.range] The range concept. |
498 | template<typename _Tp> |
499 | concept range = requires(_Tp& __t) |
500 | { |
501 | ranges::begin(__t); |
502 | ranges::end(__t); |
503 | }; |
504 | |
505 | /// [range.range] The borrowed_range concept. |
506 | template<typename _Tp> |
507 | concept borrowed_range |
508 | = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>; |
509 | |
510 | template<typename _Tp> |
511 | using iterator_t = std::__detail::__range_iter_t<_Tp>; |
512 | |
513 | template<range _Range> |
514 | using sentinel_t = decltype(ranges::end(std::declval<_Range&>())); |
515 | |
516 | #if __glibcxx_ranges_as_const // >= C++23 |
517 | template<range _Range> |
518 | using const_iterator_t = const_iterator<iterator_t<_Range>>; |
519 | |
520 | template<range _Range> |
521 | using const_sentinel_t = const_sentinel<sentinel_t<_Range>>; |
522 | |
523 | template<range _Range> |
524 | using range_const_reference_t = iter_const_reference_t<iterator_t<_Range>>; |
525 | #endif |
526 | |
527 | template<range _Range> |
528 | using range_difference_t = iter_difference_t<iterator_t<_Range>>; |
529 | |
530 | template<range _Range> |
531 | using range_value_t = iter_value_t<iterator_t<_Range>>; |
532 | |
533 | template<range _Range> |
534 | using range_reference_t = iter_reference_t<iterator_t<_Range>>; |
535 | |
536 | template<range _Range> |
537 | using range_rvalue_reference_t |
538 | = iter_rvalue_reference_t<iterator_t<_Range>>; |
539 | |
540 | /// [range.sized] The sized_range concept. |
541 | template<typename _Tp> |
542 | concept sized_range = range<_Tp> |
543 | && requires(_Tp& __t) { ranges::size(__t); }; |
544 | |
545 | template<sized_range _Range> |
546 | using range_size_t = decltype(ranges::size(std::declval<_Range&>())); |
547 | |
548 | template<typename _Derived> |
549 | requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>> |
550 | class view_interface; // defined in <bits/ranges_util.h> |
551 | |
552 | namespace __detail |
553 | { |
554 | template<typename _Tp, typename _Up> |
555 | requires (!same_as<_Tp, view_interface<_Up>>) |
556 | void __is_derived_from_view_interface_fn(const _Tp&, |
557 | const view_interface<_Up>&); // not defined |
558 | |
559 | // Returns true iff _Tp has exactly one public base class that's a |
560 | // specialization of view_interface. |
561 | template<typename _Tp> |
562 | concept __is_derived_from_view_interface |
563 | = requires (_Tp __t) { __is_derived_from_view_interface_fn(__t, __t); }; |
564 | } // namespace __detail |
565 | |
566 | /// [range.view] The ranges::view_base type. |
567 | struct view_base { }; |
568 | |
569 | /// [range.view] The ranges::enable_view boolean. |
570 | template<typename _Tp> |
571 | inline constexpr bool enable_view = derived_from<_Tp, view_base> |
572 | || __detail::__is_derived_from_view_interface<_Tp>; |
573 | |
574 | /// [range.view] The ranges::view concept. |
575 | template<typename _Tp> |
576 | concept view |
577 | = range<_Tp> && movable<_Tp> && enable_view<_Tp>; |
578 | |
579 | // [range.refinements] |
580 | |
581 | /// A range for which ranges::begin returns an output iterator. |
582 | template<typename _Range, typename _Tp> |
583 | concept output_range |
584 | = range<_Range> && output_iterator<iterator_t<_Range>, _Tp>; |
585 | |
586 | /// A range for which ranges::begin returns an input iterator. |
587 | template<typename _Tp> |
588 | concept input_range = range<_Tp> && input_iterator<iterator_t<_Tp>>; |
589 | |
590 | /// A range for which ranges::begin returns a forward iterator. |
591 | template<typename _Tp> |
592 | concept forward_range |
593 | = input_range<_Tp> && forward_iterator<iterator_t<_Tp>>; |
594 | |
595 | /// A range for which ranges::begin returns a bidirectional iterator. |
596 | template<typename _Tp> |
597 | concept bidirectional_range |
598 | = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp>>; |
599 | |
600 | /// A range for which ranges::begin returns a random access iterator. |
601 | template<typename _Tp> |
602 | concept random_access_range |
603 | = bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp>>; |
604 | |
605 | /// A range for which ranges::begin returns a contiguous iterator. |
606 | template<typename _Tp> |
607 | concept contiguous_range |
608 | = random_access_range<_Tp> && contiguous_iterator<iterator_t<_Tp>> |
609 | && requires(_Tp& __t) |
610 | { |
611 | { ranges::data(__t) } -> same_as<add_pointer_t<range_reference_t<_Tp>>>; |
612 | }; |
613 | |
614 | /// A range for which ranges::begin and ranges::end return the same type. |
615 | template<typename _Tp> |
616 | concept common_range |
617 | = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp>>; |
618 | |
619 | #if __glibcxx_ranges_as_const // >= C++23 |
620 | template<typename _Tp> |
621 | concept constant_range |
622 | = input_range<_Tp> && std::__detail::__constant_iterator<iterator_t<_Tp>>; |
623 | #endif |
624 | |
625 | namespace __access |
626 | { |
627 | #if __glibcxx_ranges_as_const // >= C++23 |
628 | template<typename _Range> |
629 | constexpr auto& |
630 | __possibly_const_range(_Range& __r) noexcept |
631 | { |
632 | if constexpr (constant_range<const _Range> && !constant_range<_Range>) |
633 | return const_cast<const _Range&>(__r); |
634 | else |
635 | return __r; |
636 | } |
637 | #else |
638 | // If _To is an lvalue-reference, return const _Tp&, otherwise const _Tp&&. |
639 | template<typename _To, typename _Tp> |
640 | constexpr decltype(auto) |
641 | __as_const(_Tp& __t) noexcept |
642 | { |
643 | static_assert(std::is_same_v<_To&, _Tp&>); |
644 | |
645 | if constexpr (is_lvalue_reference_v<_To>) |
646 | return const_cast<const _Tp&>(__t); |
647 | else |
648 | return static_cast<const _Tp&&>(__t); |
649 | } |
650 | #endif |
651 | |
652 | struct _CBegin |
653 | { |
654 | #if __glibcxx_ranges_as_const // >= C++23 |
655 | template<__maybe_borrowed_range _Tp> |
656 | [[nodiscard]] |
657 | constexpr auto |
658 | operator()(_Tp&& __t) const |
659 | noexcept(noexcept(std::make_const_iterator |
660 | (ranges::begin(__access::__possibly_const_range(__t))))) |
661 | requires requires { std::make_const_iterator |
662 | (ranges::begin(__access::__possibly_const_range(__t))); } |
663 | { |
664 | auto& __r = __access::__possibly_const_range(__t); |
665 | return const_iterator_t<decltype(__r)>(ranges::begin(__r)); |
666 | } |
667 | #else |
668 | template<typename _Tp> |
669 | [[nodiscard]] |
670 | constexpr auto |
671 | operator()(_Tp&& __e) const |
672 | noexcept(noexcept(_Begin{}(__access::__as_const<_Tp>(__e)))) |
673 | requires requires { _Begin{}(__access::__as_const<_Tp>(__e)); } |
674 | { |
675 | return _Begin{}(__access::__as_const<_Tp>(__e)); |
676 | } |
677 | #endif |
678 | }; |
679 | |
680 | struct _CEnd final |
681 | { |
682 | #if __glibcxx_ranges_as_const // >= C++23 |
683 | template<__maybe_borrowed_range _Tp> |
684 | [[nodiscard]] |
685 | constexpr auto |
686 | operator()(_Tp&& __t) const |
687 | noexcept(noexcept(std::make_const_sentinel |
688 | (ranges::end(__access::__possibly_const_range(__t))))) |
689 | requires requires { std::make_const_sentinel |
690 | (ranges::end(__access::__possibly_const_range(__t))); } |
691 | { |
692 | auto& __r = __access::__possibly_const_range(__t); |
693 | return const_sentinel_t<decltype(__r)>(ranges::end(__r)); |
694 | } |
695 | #else |
696 | template<typename _Tp> |
697 | [[nodiscard]] |
698 | constexpr auto |
699 | operator()(_Tp&& __e) const |
700 | noexcept(noexcept(_End{}(__access::__as_const<_Tp>(__e)))) |
701 | requires requires { _End{}(__access::__as_const<_Tp>(__e)); } |
702 | { |
703 | return _End{}(__access::__as_const<_Tp>(__e)); |
704 | } |
705 | #endif |
706 | }; |
707 | |
708 | struct _CRBegin |
709 | { |
710 | #if __glibcxx_ranges_as_const // >= C++23 |
711 | template<__maybe_borrowed_range _Tp> |
712 | [[nodiscard]] |
713 | constexpr auto |
714 | operator()(_Tp&& __t) const |
715 | noexcept(noexcept(std::make_const_iterator |
716 | (ranges::rbegin(__access::__possibly_const_range(__t))))) |
717 | requires requires { std::make_const_iterator |
718 | (ranges::rbegin(__access::__possibly_const_range(__t))); } |
719 | { |
720 | auto& __r = __access::__possibly_const_range(__t); |
721 | return const_iterator<decltype(ranges::rbegin(__r))>(ranges::rbegin(__r)); |
722 | } |
723 | #else |
724 | template<typename _Tp> |
725 | [[nodiscard]] |
726 | constexpr auto |
727 | operator()(_Tp&& __e) const |
728 | noexcept(noexcept(_RBegin{}(__access::__as_const<_Tp>(__e)))) |
729 | requires requires { _RBegin{}(__access::__as_const<_Tp>(__e)); } |
730 | { |
731 | return _RBegin{}(__access::__as_const<_Tp>(__e)); |
732 | } |
733 | #endif |
734 | }; |
735 | |
736 | struct _CREnd |
737 | { |
738 | #if __glibcxx_ranges_as_const // >= C++23 |
739 | template<__maybe_borrowed_range _Tp> |
740 | [[nodiscard]] |
741 | constexpr auto |
742 | operator()(_Tp&& __t) const |
743 | noexcept(noexcept(std::make_const_sentinel |
744 | (ranges::rend(__access::__possibly_const_range(__t))))) |
745 | requires requires { std::make_const_sentinel |
746 | (ranges::rend(__access::__possibly_const_range(__t))); } |
747 | { |
748 | auto& __r = __access::__possibly_const_range(__t); |
749 | return const_sentinel<decltype(ranges::rend(__r))>(ranges::rend(__r)); |
750 | } |
751 | #else |
752 | template<typename _Tp> |
753 | [[nodiscard]] |
754 | constexpr auto |
755 | operator()(_Tp&& __e) const |
756 | noexcept(noexcept(_REnd{}(__access::__as_const<_Tp>(__e)))) |
757 | requires requires { _REnd{}(__access::__as_const<_Tp>(__e)); } |
758 | { |
759 | return _REnd{}(__access::__as_const<_Tp>(__e)); |
760 | } |
761 | #endif |
762 | }; |
763 | |
764 | struct _CData |
765 | { |
766 | #if __glibcxx_ranges_as_const // >= C++23 |
767 | template<__maybe_borrowed_range _Tp> |
768 | [[nodiscard]] |
769 | constexpr const auto* |
770 | operator()(_Tp&& __t) const |
771 | noexcept(noexcept(ranges::data(__access::__possibly_const_range(__t)))) |
772 | requires requires { ranges::data(__access::__possibly_const_range(__t)); } |
773 | { return ranges::data(__access::__possibly_const_range(__t)); } |
774 | #else |
775 | template<typename _Tp> |
776 | [[nodiscard]] |
777 | constexpr auto |
778 | operator()(_Tp&& __e) const |
779 | noexcept(noexcept(_Data{}(__access::__as_const<_Tp>(__e)))) |
780 | requires requires { _Data{}(__access::__as_const<_Tp>(__e)); } |
781 | { |
782 | return _Data{}(__access::__as_const<_Tp>(__e)); |
783 | } |
784 | #endif |
785 | }; |
786 | } // namespace __access |
787 | |
788 | inline namespace _Cpo |
789 | { |
790 | inline constexpr ranges::__access::_CBegin cbegin{}; |
791 | inline constexpr ranges::__access::_CEnd cend{}; |
792 | inline constexpr ranges::__access::_CRBegin crbegin{}; |
793 | inline constexpr ranges::__access::_CREnd crend{}; |
794 | inline constexpr ranges::__access::_CData cdata{}; |
795 | } |
796 | |
797 | namespace __detail |
798 | { |
799 | template<typename _Tp> |
800 | inline constexpr bool __is_initializer_list = false; |
801 | |
802 | template<typename _Tp> |
803 | inline constexpr bool __is_initializer_list<initializer_list<_Tp>> = true; |
804 | } // namespace __detail |
805 | |
806 | /// A range which can be safely converted to a view. |
807 | template<typename _Tp> |
808 | concept viewable_range = range<_Tp> |
809 | && ((view<remove_cvref_t<_Tp>> && constructible_from<remove_cvref_t<_Tp>, _Tp>) |
810 | || (!view<remove_cvref_t<_Tp>> |
811 | && (is_lvalue_reference_v<_Tp> |
812 | || (movable<remove_reference_t<_Tp>> |
813 | && !__detail::__is_initializer_list<remove_cvref_t<_Tp>>)))); |
814 | |
815 | // [range.iter.ops] range iterator operations |
816 | |
817 | struct __advance_fn final |
818 | { |
819 | template<input_or_output_iterator _It> |
820 | constexpr void |
821 | operator()(_It& __it, iter_difference_t<_It> __n) const |
822 | { |
823 | if constexpr (random_access_iterator<_It>) |
824 | __it += __n; |
825 | else if constexpr (bidirectional_iterator<_It>) |
826 | { |
827 | if (__n > 0) |
828 | { |
829 | do |
830 | { |
831 | ++__it; |
832 | } |
833 | while (--__n); |
834 | } |
835 | else if (__n < 0) |
836 | { |
837 | do |
838 | { |
839 | --__it; |
840 | } |
841 | while (++__n); |
842 | } |
843 | } |
844 | else |
845 | { |
846 | // cannot decrement a non-bidirectional iterator |
847 | __glibcxx_assert(__n >= 0); |
848 | while (__n-- > 0) |
849 | ++__it; |
850 | } |
851 | } |
852 | |
853 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> |
854 | constexpr void |
855 | operator()(_It& __it, _Sent __bound) const |
856 | { |
857 | if constexpr (assignable_from<_It&, _Sent>) |
858 | __it = std::move(__bound); |
859 | else if constexpr (sized_sentinel_for<_Sent, _It>) |
860 | (*this)(__it, __bound - __it); |
861 | else |
862 | { |
863 | while (__it != __bound) |
864 | ++__it; |
865 | } |
866 | } |
867 | |
868 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> |
869 | constexpr iter_difference_t<_It> |
870 | operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound) const |
871 | { |
872 | if constexpr (sized_sentinel_for<_Sent, _It>) |
873 | { |
874 | const auto __diff = __bound - __it; |
875 | |
876 | if (__diff == 0) |
877 | return __n; |
878 | else if (__diff > 0 ? __n >= __diff : __n <= __diff) |
879 | { |
880 | (*this)(__it, __bound); |
881 | return __n - __diff; |
882 | } |
883 | else if (__n != 0) [[likely]] |
884 | { |
885 | // n and bound must not lead in opposite directions: |
886 | __glibcxx_assert((__n < 0) == (__diff < 0)); |
887 | |
888 | (*this)(__it, __n); |
889 | return 0; |
890 | } |
891 | else |
892 | return 0; |
893 | } |
894 | else if (__it == __bound || __n == 0) |
895 | return __n; |
896 | else if (__n > 0) |
897 | { |
898 | iter_difference_t<_It> __m = 0; |
899 | do |
900 | { |
901 | ++__it; |
902 | ++__m; |
903 | } |
904 | while (__m != __n && __it != __bound); |
905 | return __n - __m; |
906 | } |
907 | else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>) |
908 | { |
909 | iter_difference_t<_It> __m = 0; |
910 | do |
911 | { |
912 | --__it; |
913 | --__m; |
914 | } |
915 | while (__m != __n && __it != __bound); |
916 | return __n - __m; |
917 | } |
918 | else |
919 | { |
920 | // cannot decrement a non-bidirectional iterator |
921 | __glibcxx_assert(__n >= 0); |
922 | return __n; |
923 | } |
924 | } |
925 | |
926 | void operator&() const = delete; |
927 | }; |
928 | |
929 | inline constexpr __advance_fn advance{}; |
930 | |
931 | struct __distance_fn final |
932 | { |
933 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> |
934 | requires (!sized_sentinel_for<_Sent, _It>) |
935 | constexpr iter_difference_t<_It> |
936 | operator()[[nodiscard]](_It __first, _Sent __last) const |
937 | { |
938 | iter_difference_t<_It> __n = 0; |
939 | while (__first != __last) |
940 | { |
941 | ++__first; |
942 | ++__n; |
943 | } |
944 | return __n; |
945 | } |
946 | |
947 | template<input_or_output_iterator _It, sized_sentinel_for<_It> _Sent> |
948 | [[nodiscard]] |
949 | constexpr iter_difference_t<_It> |
950 | operator()(const _It& __first, const _Sent& __last) const |
951 | { |
952 | return __last - __first; |
953 | } |
954 | |
955 | template<range _Range> |
956 | [[nodiscard]] |
957 | constexpr range_difference_t<_Range> |
958 | operator()(_Range&& __r) const |
959 | { |
960 | if constexpr (sized_range<_Range>) |
961 | return static_cast<range_difference_t<_Range>>(ranges::size(__r)); |
962 | else |
963 | return (*this)(ranges::begin(__r), ranges::end(__r)); |
964 | } |
965 | |
966 | void operator&() const = delete; |
967 | }; |
968 | |
969 | inline constexpr __distance_fn distance{}; |
970 | |
971 | struct __next_fn final |
972 | { |
973 | template<input_or_output_iterator _It> |
974 | [[nodiscard]] |
975 | constexpr _It |
976 | operator()(_It __x) const |
977 | { |
978 | ++__x; |
979 | return __x; |
980 | } |
981 | |
982 | template<input_or_output_iterator _It> |
983 | [[nodiscard]] |
984 | constexpr _It |
985 | operator()(_It __x, iter_difference_t<_It> __n) const |
986 | { |
987 | ranges::advance(__x, __n); |
988 | return __x; |
989 | } |
990 | |
991 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> |
992 | [[nodiscard]] |
993 | constexpr _It |
994 | operator()(_It __x, _Sent __bound) const |
995 | { |
996 | ranges::advance(__x, __bound); |
997 | return __x; |
998 | } |
999 | |
1000 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> |
1001 | [[nodiscard]] |
1002 | constexpr _It |
1003 | operator()(_It __x, iter_difference_t<_It> __n, _Sent __bound) const |
1004 | { |
1005 | ranges::advance(__x, __n, __bound); |
1006 | return __x; |
1007 | } |
1008 | |
1009 | void operator&() const = delete; |
1010 | }; |
1011 | |
1012 | inline constexpr __next_fn next{}; |
1013 | |
1014 | struct __prev_fn final |
1015 | { |
1016 | template<bidirectional_iterator _It> |
1017 | [[nodiscard]] |
1018 | constexpr _It |
1019 | operator()(_It __x) const |
1020 | { |
1021 | --__x; |
1022 | return __x; |
1023 | } |
1024 | |
1025 | template<bidirectional_iterator _It> |
1026 | [[nodiscard]] |
1027 | constexpr _It |
1028 | operator()(_It __x, iter_difference_t<_It> __n) const |
1029 | { |
1030 | ranges::advance(__x, -__n); |
1031 | return __x; |
1032 | } |
1033 | |
1034 | template<bidirectional_iterator _It> |
1035 | [[nodiscard]] |
1036 | constexpr _It |
1037 | operator()(_It __x, iter_difference_t<_It> __n, _It __bound) const |
1038 | { |
1039 | ranges::advance(__x, -__n, __bound); |
1040 | return __x; |
1041 | } |
1042 | |
1043 | void operator&() const = delete; |
1044 | }; |
1045 | |
1046 | inline constexpr __prev_fn prev{}; |
1047 | |
1048 | /// Type returned by algorithms instead of a dangling iterator or subrange. |
1049 | struct dangling |
1050 | { |
1051 | constexpr dangling() noexcept = default; |
1052 | template<typename... _Args> |
1053 | constexpr dangling(_Args&&...) noexcept { } |
1054 | }; |
1055 | |
1056 | template<range _Range> |
1057 | using borrowed_iterator_t = __conditional_t<borrowed_range<_Range>, |
1058 | iterator_t<_Range>, |
1059 | dangling>; |
1060 | } // namespace ranges |
1061 | |
1062 | #if __glibcxx_ranges_to_container // C++ >= 23 |
1063 | struct from_range_t { explicit from_range_t() = default; }; |
1064 | inline constexpr from_range_t from_range{}; |
1065 | #endif |
1066 | |
1067 | _GLIBCXX_END_NAMESPACE_VERSION |
1068 | } // namespace std |
1069 | #endif // library concepts |
1070 | #endif // C++20 |
1071 | #endif // _GLIBCXX_RANGES_BASE_H |
1072 | |