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