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 41namespace std _GLIBCXX_VISIBILITY(default) 42{ 43_GLIBCXX_BEGIN_NAMESPACE_VERSION 44namespace 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