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