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
43namespace std _GLIBCXX_VISIBILITY(default)
44{
45_GLIBCXX_BEGIN_NAMESPACE_VERSION
46namespace 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 // _GLIBCXX_RESOLVE_LIB_DEFECTS
934 // 3664. LWG 3392 broke std::ranges::distance(a, a+3)
935 template<typename _It, sentinel_for<_It> _Sent>
936 requires (!sized_sentinel_for<_Sent, _It>)
937 constexpr iter_difference_t<_It>
938 operator()[[nodiscard]](_It __first, _Sent __last) const
939 {
940 iter_difference_t<_It> __n = 0;
941 while (__first != __last)
942 {
943 ++__first;
944 ++__n;
945 }
946 return __n;
947 }
948
949 template<typename _It, sized_sentinel_for<decay_t<_It>> _Sent>
950 [[nodiscard]]
951 constexpr iter_difference_t<decay_t<_It>>
952 operator()(_It&& __first, _Sent __last) const
953 { return __last - static_cast<const decay_t<_It>&>(__first); }
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