]>
Commit | Line | Data |
---|---|---|
160061ac JW |
1 | // Core concepts and definitions for <ranges> -*- C++ -*- |
2 | ||
7adcbafe | 3 | // Copyright (C) 2019-2022 Free Software Foundation, Inc. |
160061ac JW |
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 | |
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; | |
cb326a64 | 92 | using std::__detail::__range_iter_t; |
160061ac | 93 | |
b9e35ee6 | 94 | struct _Begin |
160061ac JW |
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 | |
c8b024fa | 114 | operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>()) |
160061ac JW |
115 | { |
116 | if constexpr (is_array_v<remove_reference_t<_Tp>>) | |
117 | { | |
118 | static_assert(is_lvalue_reference_v<_Tp>); | |
160061ac JW |
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 | { | |
cb326a64 | 131 | { __decay_copy(__t.end()) } -> sentinel_for<__range_iter_t<_Tp>>; |
160061ac JW |
132 | }; |
133 | ||
ee9548b3 | 134 | // Poison pills so that unqualified lookup doesn't find std::end. |
160061ac JW |
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 | { | |
cb326a64 | 142 | { __decay_copy(end(__t)) } -> sentinel_for<__range_iter_t<_Tp>>; |
160061ac JW |
143 | }; |
144 | ||
b9e35ee6 | 145 | struct _End |
160061ac JW |
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> | |
ee9548b3 JW |
162 | requires is_bounded_array_v<remove_reference_t<_Tp>> |
163 | || __member_end<_Tp> || __adl_end<_Tp> | |
160061ac | 164 | constexpr auto |
c8b024fa | 165 | operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>()) |
160061ac JW |
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 | ||
ee9548b3 JW |
179 | // If _To is an lvalue-reference, return const _Tp&, otherwise const _Tp&&. |
180 | template<typename _To, typename _Tp> | |
160061ac | 181 | constexpr decltype(auto) |
ee9548b3 | 182 | __as_const(_Tp& __t) noexcept |
160061ac | 183 | { |
ee9548b3 JW |
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); | |
160061ac JW |
188 | else |
189 | return static_cast<const _Tp&&>(__t); | |
190 | } | |
191 | ||
b9e35ee6 | 192 | struct _CBegin |
160061ac JW |
193 | { |
194 | template<typename _Tp> | |
240b01b0 | 195 | [[nodiscard]] |
160061ac JW |
196 | constexpr auto |
197 | operator()(_Tp&& __e) const | |
ee9548b3 JW |
198 | noexcept(noexcept(_Begin{}(__cust_access::__as_const<_Tp>(__e)))) |
199 | requires requires { _Begin{}(__cust_access::__as_const<_Tp>(__e)); } | |
160061ac | 200 | { |
ee9548b3 | 201 | return _Begin{}(__cust_access::__as_const<_Tp>(__e)); |
160061ac JW |
202 | } |
203 | }; | |
204 | ||
8b935487 | 205 | struct _CEnd final |
160061ac JW |
206 | { |
207 | template<typename _Tp> | |
240b01b0 | 208 | [[nodiscard]] |
160061ac JW |
209 | constexpr auto |
210 | operator()(_Tp&& __e) const | |
ee9548b3 JW |
211 | noexcept(noexcept(_End{}(__cust_access::__as_const<_Tp>(__e)))) |
212 | requires requires { _End{}(__cust_access::__as_const<_Tp>(__e)); } | |
160061ac | 213 | { |
ee9548b3 | 214 | return _End{}(__cust_access::__as_const<_Tp>(__e)); |
160061ac JW |
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 | ||
b9e35ee6 | 241 | struct _RBegin |
160061ac JW |
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 | |
c8b024fa | 269 | operator()[[nodiscard]](_Tp&& __t) const |
ee9548b3 | 270 | noexcept(_S_noexcept<_Tp&>()) |
160061ac JW |
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()) } | |
cb326a64 | 285 | -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>; |
160061ac JW |
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 | ||
b9e35ee6 | 299 | struct _REnd |
160061ac JW |
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 | |
c8b024fa | 327 | operator()[[nodiscard]](_Tp&& __t) const |
ee9548b3 | 328 | noexcept(_S_noexcept<_Tp&>()) |
160061ac JW |
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 | ||
b9e35ee6 | 339 | struct _CRBegin |
160061ac JW |
340 | { |
341 | template<typename _Tp> | |
240b01b0 | 342 | [[nodiscard]] |
160061ac JW |
343 | constexpr auto |
344 | operator()(_Tp&& __e) const | |
ee9548b3 JW |
345 | noexcept(noexcept(_RBegin{}(__cust_access::__as_const<_Tp>(__e)))) |
346 | requires requires { _RBegin{}(__cust_access::__as_const<_Tp>(__e)); } | |
160061ac | 347 | { |
ee9548b3 | 348 | return _RBegin{}(__cust_access::__as_const<_Tp>(__e)); |
160061ac JW |
349 | } |
350 | }; | |
351 | ||
b9e35ee6 | 352 | struct _CREnd |
160061ac JW |
353 | { |
354 | template<typename _Tp> | |
240b01b0 | 355 | [[nodiscard]] |
160061ac JW |
356 | constexpr auto |
357 | operator()(_Tp&& __e) const | |
ee9548b3 JW |
358 | noexcept(noexcept(_REnd{}(__cust_access::__as_const<_Tp>(__e)))) |
359 | requires requires { _REnd{}(__cust_access::__as_const<_Tp>(__e)); } | |
160061ac | 360 | { |
ee9548b3 | 361 | return _REnd{}(__cust_access::__as_const<_Tp>(__e)); |
160061ac JW |
362 | } |
363 | }; | |
364 | ||
365 | template<typename _Tp> | |
366 | concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>> | |
ee9548b3 | 367 | && requires(_Tp& __t) |
160061ac | 368 | { |
ee9548b3 | 369 | { __decay_copy(__t.size()) } -> __detail::__is_integer_like; |
160061ac JW |
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>> | |
ee9548b3 | 378 | && requires(_Tp& __t) |
160061ac | 379 | { |
ee9548b3 | 380 | { __decay_copy(size(__t)) } -> __detail::__is_integer_like; |
160061ac JW |
381 | }; |
382 | ||
383 | template<typename _Tp> | |
ee9548b3 | 384 | concept __sentinel_size = requires(_Tp& __t) |
160061ac | 385 | { |
55823c5a JW |
386 | requires (!is_unbounded_array_v<remove_reference_t<_Tp>>); |
387 | ||
ee9548b3 | 388 | { _Begin{}(__t) } -> forward_iterator; |
160061ac | 389 | |
ee9548b3 JW |
390 | { _End{}(__t) } -> sized_sentinel_for<decltype(_Begin{}(__t))>; |
391 | ||
392 | __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t)); | |
160061ac JW |
393 | }; |
394 | ||
b9e35ee6 | 395 | struct _Size |
160061ac JW |
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>) | |
ee9548b3 | 405 | return noexcept(__decay_copy(std::declval<_Tp&>().size())); |
160061ac | 406 | else if constexpr (__adl_size<_Tp>) |
ee9548b3 | 407 | return noexcept(__decay_copy(size(std::declval<_Tp&>()))); |
160061ac | 408 | else if constexpr (__sentinel_size<_Tp>) |
ee9548b3 JW |
409 | return noexcept(_End{}(std::declval<_Tp&>()) |
410 | - _Begin{}(std::declval<_Tp&>())); | |
160061ac JW |
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 | |
c8b024fa | 418 | operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>()) |
160061ac JW |
419 | { |
420 | if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>) | |
ee9548b3 | 421 | return extent_v<remove_reference_t<_Tp>>; |
160061ac | 422 | else if constexpr (__member_size<_Tp>) |
ee9548b3 | 423 | return __t.size(); |
160061ac | 424 | else if constexpr (__adl_size<_Tp>) |
ee9548b3 | 425 | return size(__t); |
160061ac | 426 | else if constexpr (__sentinel_size<_Tp>) |
ee9548b3 | 427 | return __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t)); |
160061ac JW |
428 | } |
429 | }; | |
430 | ||
b9e35ee6 | 431 | struct _SSize |
160061ac | 432 | { |
621ea10c JW |
433 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
434 | // 3403. Domain of ranges::ssize(E) doesn't match ranges::size(E) | |
160061ac | 435 | template<typename _Tp> |
ee9548b3 | 436 | requires requires (_Tp& __t) { _Size{}(__t); } |
160061ac | 437 | constexpr auto |
c8b024fa | 438 | operator()[[nodiscard]](_Tp&& __t) const noexcept(noexcept(_Size{}(__t))) |
160061ac | 439 | { |
ee9548b3 | 440 | auto __size = _Size{}(__t); |
621ea10c JW |
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>) | |
160061ac | 444 | { |
621ea10c JW |
445 | using __gnu_cxx::__int_traits; |
446 | if constexpr (__int_traits<__size_type>::__digits | |
160061ac JW |
447 | < __int_traits<ptrdiff_t>::__digits) |
448 | return static_cast<ptrdiff_t>(__size); | |
621ea10c JW |
449 | else |
450 | return static_cast<make_signed_t<__size_type>>(__size); | |
160061ac | 451 | } |
621ea10c JW |
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>) | |
96963713 | 455 | return static_cast<__int128>(__size); |
621ea10c JW |
456 | #endif |
457 | else // Must be one of __max_diff_type or __max_size_type. | |
458 | return __detail::__max_diff_type(__size); | |
160061ac JW |
459 | } |
460 | }; | |
461 | ||
462 | template<typename _Tp> | |
ee9548b3 | 463 | concept __member_empty = requires(_Tp& __t) { bool(__t.empty()); }; |
160061ac JW |
464 | |
465 | template<typename _Tp> | |
ee9548b3 | 466 | concept __size0_empty = requires(_Tp& __t) { _Size{}(__t) == 0; }; |
160061ac JW |
467 | |
468 | template<typename _Tp> | |
ee9548b3 | 469 | concept __eq_iter_empty = requires(_Tp& __t) |
160061ac | 470 | { |
55823c5a JW |
471 | requires (!is_unbounded_array_v<remove_reference_t<_Tp>>); |
472 | ||
ee9548b3 JW |
473 | { _Begin{}(__t) } -> forward_iterator; |
474 | ||
475 | bool(_Begin{}(__t) == _End{}(__t)); | |
160061ac JW |
476 | }; |
477 | ||
b9e35ee6 | 478 | struct _Empty |
160061ac JW |
479 | { |
480 | private: | |
481 | template<typename _Tp> | |
482 | static constexpr bool | |
483 | _S_noexcept() | |
484 | { | |
485 | if constexpr (__member_empty<_Tp>) | |
f9598d89 | 486 | return noexcept(bool(std::declval<_Tp&>().empty())); |
160061ac | 487 | else if constexpr (__size0_empty<_Tp>) |
ee9548b3 | 488 | return noexcept(_Size{}(std::declval<_Tp&>()) == 0); |
160061ac | 489 | else |
ee9548b3 JW |
490 | return noexcept(bool(_Begin{}(std::declval<_Tp&>()) |
491 | == _End{}(std::declval<_Tp&>()))); | |
160061ac JW |
492 | } |
493 | ||
494 | public: | |
495 | template<typename _Tp> | |
496 | requires __member_empty<_Tp> || __size0_empty<_Tp> | |
ee9548b3 | 497 | || __eq_iter_empty<_Tp> |
160061ac | 498 | constexpr bool |
c8b024fa | 499 | operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>()) |
160061ac JW |
500 | { |
501 | if constexpr (__member_empty<_Tp>) | |
ee9548b3 | 502 | return bool(__t.empty()); |
160061ac | 503 | else if constexpr (__size0_empty<_Tp>) |
ee9548b3 | 504 | return _Size{}(__t) == 0; |
160061ac | 505 | else |
ee9548b3 | 506 | return bool(_Begin{}(__t) == _End{}(__t)); |
160061ac JW |
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> | |
3e5f2425 JW |
515 | concept __member_data = requires(_Tp& __t) |
516 | { | |
cb326a64 | 517 | { __decay_copy(__t.data()) } -> __pointer_to_object; |
3e5f2425 | 518 | }; |
160061ac JW |
519 | |
520 | template<typename _Tp> | |
cb326a64 | 521 | concept __begin_data = contiguous_iterator<__range_iter_t<_Tp>>; |
160061ac | 522 | |
b9e35ee6 | 523 | struct _Data |
160061ac JW |
524 | { |
525 | private: | |
526 | template<typename _Tp> | |
527 | static constexpr bool | |
528 | _S_noexcept() | |
529 | { | |
530 | if constexpr (__member_data<_Tp>) | |
ee9548b3 | 531 | return noexcept(__decay_copy(std::declval<_Tp&>().data())); |
160061ac | 532 | else |
ee9548b3 | 533 | return noexcept(_Begin{}(std::declval<_Tp&>())); |
160061ac JW |
534 | } |
535 | ||
536 | public: | |
537 | template<__maybe_borrowed_range _Tp> | |
538 | requires __member_data<_Tp> || __begin_data<_Tp> | |
539 | constexpr auto | |
c8b024fa | 540 | operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp>()) |
160061ac JW |
541 | { |
542 | if constexpr (__member_data<_Tp>) | |
ee9548b3 | 543 | return __t.data(); |
160061ac | 544 | else |
ee9548b3 | 545 | return std::to_address(_Begin{}(__t)); |
160061ac JW |
546 | } |
547 | }; | |
548 | ||
b9e35ee6 | 549 | struct _CData |
160061ac JW |
550 | { |
551 | template<typename _Tp> | |
240b01b0 | 552 | [[nodiscard]] |
160061ac JW |
553 | constexpr auto |
554 | operator()(_Tp&& __e) const | |
ee9548b3 JW |
555 | noexcept(noexcept(_Data{}(__cust_access::__as_const<_Tp>(__e)))) |
556 | requires requires { _Data{}(__cust_access::__as_const<_Tp>(__e)); } | |
160061ac | 557 | { |
ee9548b3 | 558 | return _Data{}(__cust_access::__as_const<_Tp>(__e)); |
160061ac JW |
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 | ||
53b1c382 PP |
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 | } | |
638 | ||
160061ac JW |
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> | |
53b1c382 PP |
644 | inline constexpr bool enable_view = derived_from<_Tp, view_base> |
645 | || __detail::__is_derived_from_view_interface<_Tp>; | |
160061ac JW |
646 | |
647 | /// [range.view] The ranges::view concept. | |
648 | template<typename _Tp> | |
649 | concept view | |
4b4f5666 | 650 | = range<_Tp> && movable<_Tp> && enable_view<_Tp>; |
160061ac JW |
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 | /// A range which can be safely converted to a view. | |
693 | template<typename _Tp> | |
694 | concept viewable_range = range<_Tp> | |
a2c2dcc6 PP |
695 | && ((view<remove_cvref_t<_Tp>> && constructible_from<remove_cvref_t<_Tp>, _Tp>) |
696 | || (!view<remove_cvref_t<_Tp>> && borrowed_range<_Tp>)); | |
160061ac JW |
697 | |
698 | // [range.iter.ops] range iterator operations | |
699 | ||
8b935487 | 700 | struct __advance_fn final |
a49a045b JW |
701 | { |
702 | template<input_or_output_iterator _It> | |
703 | constexpr void | |
704 | operator()(_It& __it, iter_difference_t<_It> __n) const | |
705 | { | |
706 | if constexpr (random_access_iterator<_It>) | |
707 | __it += __n; | |
708 | else if constexpr (bidirectional_iterator<_It>) | |
709 | { | |
710 | if (__n > 0) | |
711 | { | |
712 | do | |
713 | { | |
714 | ++__it; | |
715 | } | |
716 | while (--__n); | |
717 | } | |
718 | else if (__n < 0) | |
719 | { | |
720 | do | |
721 | { | |
722 | --__it; | |
723 | } | |
724 | while (++__n); | |
725 | } | |
726 | } | |
727 | else | |
728 | { | |
729 | // cannot decrement a non-bidirectional iterator | |
730 | __glibcxx_assert(__n >= 0); | |
731 | while (__n-- > 0) | |
732 | ++__it; | |
733 | } | |
734 | } | |
160061ac | 735 | |
a49a045b JW |
736 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> |
737 | constexpr void | |
738 | operator()(_It& __it, _Sent __bound) const | |
739 | { | |
740 | if constexpr (assignable_from<_It&, _Sent>) | |
741 | __it = std::move(__bound); | |
742 | else if constexpr (sized_sentinel_for<_Sent, _It>) | |
743 | (*this)(__it, __bound - __it); | |
744 | else | |
745 | { | |
746 | while (__it != __bound) | |
160061ac | 747 | ++__it; |
a49a045b JW |
748 | } |
749 | } | |
160061ac | 750 | |
a49a045b JW |
751 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> |
752 | constexpr iter_difference_t<_It> | |
753 | operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound) const | |
754 | { | |
755 | if constexpr (sized_sentinel_for<_Sent, _It>) | |
756 | { | |
757 | const auto __diff = __bound - __it; | |
758 | ||
759 | // n and bound must not lead in opposite directions: | |
760 | __glibcxx_assert(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0)); | |
761 | const auto __absdiff = __diff < 0 ? -__diff : __diff; | |
762 | const auto __absn = __n < 0 ? -__n : __n;; | |
763 | if (__absn >= __absdiff) | |
764 | { | |
765 | (*this)(__it, __bound); | |
766 | return __n - __diff; | |
767 | } | |
768 | else | |
769 | { | |
770 | (*this)(__it, __n); | |
771 | return 0; | |
772 | } | |
773 | } | |
774 | else if (__it == __bound || __n == 0) | |
d8326291 | 775 | return __n; |
a49a045b JW |
776 | else if (__n > 0) |
777 | { | |
778 | iter_difference_t<_It> __m = 0; | |
779 | do | |
780 | { | |
781 | ++__it; | |
782 | ++__m; | |
783 | } | |
784 | while (__m != __n && __it != __bound); | |
785 | return __n - __m; | |
786 | } | |
787 | else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>) | |
788 | { | |
789 | iter_difference_t<_It> __m = 0; | |
790 | do | |
791 | { | |
792 | --__it; | |
793 | --__m; | |
794 | } | |
795 | while (__m != __n && __it != __bound); | |
796 | return __n - __m; | |
797 | } | |
798 | else | |
799 | { | |
800 | // cannot decrement a non-bidirectional iterator | |
801 | __glibcxx_assert(__n >= 0); | |
802 | return __n; | |
803 | } | |
804 | } | |
8b935487 JW |
805 | |
806 | void operator&() const = delete; | |
a49a045b | 807 | }; |
160061ac | 808 | |
a49a045b | 809 | inline constexpr __advance_fn advance{}; |
160061ac | 810 | |
8b935487 | 811 | struct __distance_fn final |
a49a045b JW |
812 | { |
813 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> | |
20751fad | 814 | requires (!sized_sentinel_for<_Sent, _It>) |
a49a045b | 815 | constexpr iter_difference_t<_It> |
20751fad | 816 | operator()[[nodiscard]](_It __first, _Sent __last) const |
a49a045b | 817 | { |
20751fad JW |
818 | iter_difference_t<_It> __n = 0; |
819 | while (__first != __last) | |
a49a045b | 820 | { |
20751fad JW |
821 | ++__first; |
822 | ++__n; | |
a49a045b | 823 | } |
20751fad JW |
824 | return __n; |
825 | } | |
826 | ||
827 | template<input_or_output_iterator _It, sized_sentinel_for<_It> _Sent> | |
828 | [[nodiscard]] | |
829 | constexpr iter_difference_t<_It> | |
830 | operator()(const _It& __first, const _Sent& __last) const | |
831 | { | |
832 | return __last - __first; | |
a49a045b | 833 | } |
160061ac | 834 | |
a49a045b | 835 | template<range _Range> |
240b01b0 | 836 | [[nodiscard]] |
a49a045b JW |
837 | constexpr range_difference_t<_Range> |
838 | operator()(_Range&& __r) const | |
839 | { | |
840 | if constexpr (sized_range<_Range>) | |
841 | return static_cast<range_difference_t<_Range>>(ranges::size(__r)); | |
842 | else | |
843 | return (*this)(ranges::begin(__r), ranges::end(__r)); | |
844 | } | |
8b935487 JW |
845 | |
846 | void operator&() const = delete; | |
a49a045b | 847 | }; |
160061ac | 848 | |
a49a045b | 849 | inline constexpr __distance_fn distance{}; |
160061ac | 850 | |
8b935487 | 851 | struct __next_fn final |
a49a045b JW |
852 | { |
853 | template<input_or_output_iterator _It> | |
240b01b0 | 854 | [[nodiscard]] |
a49a045b JW |
855 | constexpr _It |
856 | operator()(_It __x) const | |
857 | { | |
858 | ++__x; | |
859 | return __x; | |
860 | } | |
160061ac | 861 | |
a49a045b | 862 | template<input_or_output_iterator _It> |
240b01b0 | 863 | [[nodiscard]] |
a49a045b JW |
864 | constexpr _It |
865 | operator()(_It __x, iter_difference_t<_It> __n) const | |
866 | { | |
867 | ranges::advance(__x, __n); | |
868 | return __x; | |
869 | } | |
160061ac | 870 | |
a49a045b | 871 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> |
240b01b0 | 872 | [[nodiscard]] |
a49a045b JW |
873 | constexpr _It |
874 | operator()(_It __x, _Sent __bound) const | |
875 | { | |
876 | ranges::advance(__x, __bound); | |
877 | return __x; | |
878 | } | |
879 | ||
880 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> | |
240b01b0 | 881 | [[nodiscard]] |
a49a045b JW |
882 | constexpr _It |
883 | operator()(_It __x, iter_difference_t<_It> __n, _Sent __bound) const | |
884 | { | |
885 | ranges::advance(__x, __n, __bound); | |
886 | return __x; | |
887 | } | |
8b935487 JW |
888 | |
889 | void operator&() const = delete; | |
a49a045b JW |
890 | }; |
891 | ||
892 | inline constexpr __next_fn next{}; | |
893 | ||
8b935487 | 894 | struct __prev_fn final |
a49a045b JW |
895 | { |
896 | template<bidirectional_iterator _It> | |
240b01b0 | 897 | [[nodiscard]] |
a49a045b JW |
898 | constexpr _It |
899 | operator()(_It __x) const | |
900 | { | |
901 | --__x; | |
902 | return __x; | |
903 | } | |
904 | ||
905 | template<bidirectional_iterator _It> | |
240b01b0 | 906 | [[nodiscard]] |
a49a045b JW |
907 | constexpr _It |
908 | operator()(_It __x, iter_difference_t<_It> __n) const | |
909 | { | |
910 | ranges::advance(__x, -__n); | |
911 | return __x; | |
912 | } | |
913 | ||
914 | template<bidirectional_iterator _It> | |
240b01b0 | 915 | [[nodiscard]] |
a49a045b JW |
916 | constexpr _It |
917 | operator()(_It __x, iter_difference_t<_It> __n, _It __bound) const | |
918 | { | |
919 | ranges::advance(__x, -__n, __bound); | |
920 | return __x; | |
921 | } | |
8b935487 JW |
922 | |
923 | void operator&() const = delete; | |
a49a045b JW |
924 | }; |
925 | ||
926 | inline constexpr __prev_fn prev{}; | |
160061ac JW |
927 | |
928 | /// Type returned by algorithms instead of a dangling iterator or subrange. | |
929 | struct dangling | |
930 | { | |
931 | constexpr dangling() noexcept = default; | |
932 | template<typename... _Args> | |
933 | constexpr dangling(_Args&&...) noexcept { } | |
934 | }; | |
935 | ||
936 | template<range _Range> | |
a09bb4a8 JW |
937 | using borrowed_iterator_t = __conditional_t<borrowed_range<_Range>, |
938 | iterator_t<_Range>, | |
939 | dangling>; | |
160061ac JW |
940 | |
941 | } // namespace ranges | |
942 | _GLIBCXX_END_NAMESPACE_VERSION | |
943 | } // namespace std | |
944 | #endif // library concepts | |
945 | #endif // C++20 | |
946 | #endif // _GLIBCXX_RANGES_BASE_H |