projects / thirdparty / gcc.git / blame
| Commit | Line | Data |
|---|---|---|
| 6d0dff49 JW |
1 | // Concepts and traits for use with iterators -*- C++ -*- |
| 2 | ||
| 8d9254fc | 3 | // Copyright (C) 2019-2020 Free Software Foundation, Inc. |
| 6d0dff49 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/iterator_concepts.h | |
| 26 | * This is an internal header file, included by other library headers. | |
| 27 | * Do not attempt to use it directly. @headername{iterator} | |
| 28 | */ | |
| 29 | ||
| 30 | #ifndef _ITERATOR_CONCEPTS_H | |
| 31 | #define _ITERATOR_CONCEPTS_H 1 | |
| 32 | ||
| 33 | #pragma GCC system_header | |
| 34 | ||
| 35 | #include <concepts> | |
| 36 | #include <bits/ptr_traits.h> // to_address | |
| 37 | #include <bits/range_cmp.h> // identity, ranges::less | |
| 38 | ||
| 39 | #if __cpp_lib_concepts | |
| 40 | namespace std _GLIBCXX_VISIBILITY(default) | |
| 41 | { | |
| 42 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
| 43 | ||
| 44 | struct input_iterator_tag; | |
| 45 | struct output_iterator_tag; | |
| 46 | struct forward_iterator_tag; | |
| 47 | struct bidirectional_iterator_tag; | |
| 48 | struct random_access_iterator_tag; | |
| 49 | struct contiguous_iterator_tag; | |
| 50 | ||
| 51 | template<typename _Iterator> | |
| 52 | struct iterator_traits; | |
| 53 | ||
| 54 | template<typename _Tp> requires is_object_v<_Tp> | |
| 55 | struct iterator_traits<_Tp*>; | |
| 56 | ||
| 57 | template<typename _Iterator, typename> | |
| 58 | struct __iterator_traits; | |
| 59 | ||
| 60 | namespace __detail | |
| 61 | { | |
| 62 | template<typename _Tp> | |
| 63 | using __with_ref = _Tp&; | |
| 64 | ||
| 65 | template<typename _Tp> | |
| 66 | concept __can_reference = requires { typename __with_ref<_Tp>; }; | |
| 67 | ||
| 68 | template<typename _Tp> | |
| 69 | concept __dereferenceable = requires(_Tp& __t) | |
| 70 | { | |
| 71 | { *__t } -> __can_reference; | |
| 72 | }; | |
| 73 | ||
| 74 | // FIXME: needed due to PR c++/67704 | |
| 75 | template<__detail::__dereferenceable _Tp> | |
| 76 | struct __iter_ref | |
| 77 | { | |
| 78 | using type = decltype(*std::declval<_Tp&>()); | |
| 79 | }; | |
| 80 | } // namespace __detail | |
| 81 | ||
| 82 | template<typename _Tp> | |
| 83 | using iter_reference_t = typename __detail::__iter_ref<_Tp>::type; | |
| 84 | ||
| 85 | namespace ranges | |
| 86 | { | |
| 87 | namespace __cust_imove | |
| 88 | { | |
| 89 | template<typename _Tp> | |
| 90 | concept __adl_imove | |
| 91 | = (std::__detail::__class_or_enum<remove_reference_t<_Tp>>) | |
| 92 | && requires(_Tp&& __t) { iter_move(static_cast<_Tp&&>(__t)); }; | |
| 93 | ||
| 94 | struct _IMove | |
| 95 | { | |
| 96 | private: | |
| 97 | template<typename _Tp> | |
| 98 | static constexpr bool | |
| 99 | _S_noexcept() | |
| 100 | { | |
| 101 | if constexpr (__adl_imove<_Tp>) | |
| 102 | return noexcept(iter_move(std::declval<_Tp>())); | |
| 103 | else | |
| 104 | return noexcept(*std::declval<_Tp>()); | |
| 105 | } | |
| 106 | ||
| 107 | public: | |
| 108 | template<typename _Tp> | |
| 109 | requires __adl_imove<_Tp> || requires(_Tp& __e) { *__e; } | |
| 110 | constexpr decltype(auto) | |
| 111 | operator()(_Tp&& __e) const | |
| 112 | noexcept(_S_noexcept<_Tp>()) | |
| 113 | { | |
| 114 | if constexpr (__adl_imove<_Tp>) | |
| 115 | return iter_move(static_cast<_Tp&&>(__e)); | |
| 116 | else if constexpr (is_reference_v<iter_reference_t<_Tp>>) | |
| 117 | return std::move(*__e); | |
| 118 | else | |
| 119 | return *__e; | |
| 120 | } | |
| 121 | }; | |
| 122 | } // namespace __cust_imove | |
| 123 | ||
| 124 | inline namespace __cust | |
| 125 | { | |
| 126 | inline constexpr __cust_imove::_IMove iter_move{}; | |
| 127 | } // inline namespace __cust | |
| 128 | } // namespace ranges | |
| 129 | ||
| 130 | namespace __detail | |
| 131 | { | |
| 132 | // FIXME: needed due to PR c++/67704 | |
| 133 | template<__detail::__dereferenceable _Tp> | |
| 134 | struct __iter_rvalue_ref | |
| 135 | { }; | |
| 136 | ||
| 137 | template<__detail::__dereferenceable _Tp> | |
| 138 | requires requires(_Tp& __t) | |
| 139 | { | |
| 140 | { ranges::iter_move(__t) } -> __detail::__can_reference; | |
| 141 | } | |
| 142 | struct __iter_rvalue_ref<_Tp> | |
| 143 | { using type = decltype(ranges::iter_move(std::declval<_Tp&>())); }; | |
| 144 | ||
| 145 | } // namespace __detail | |
| 146 | ||
| 147 | template<typename _Tp> | |
| 148 | using iter_rvalue_reference_t | |
| 149 | = typename __detail::__iter_rvalue_ref<_Tp>::type; | |
| 150 | ||
| 151 | template<typename> struct incrementable_traits { }; | |
| 152 | ||
| 153 | template<typename _Tp> requires is_object_v<_Tp> | |
| 154 | struct incrementable_traits<_Tp*> | |
| 155 | { using difference_type = ptrdiff_t; }; | |
| 156 | ||
| 157 | template<typename _Iter> | |
| 158 | struct incrementable_traits<const _Iter> | |
| 159 | : incrementable_traits<_Iter> { }; | |
| 160 | ||
| 161 | template<typename _Tp> requires requires { typename _Tp::difference_type; } | |
| 162 | struct incrementable_traits<_Tp> | |
| 163 | { using difference_type = typename _Tp::difference_type; }; | |
| 164 | ||
| 165 | template<typename _Tp> | |
| 166 | requires (!requires { typename _Tp::difference_type; } | |
| 167 | && requires(const _Tp& __a, const _Tp& __b) | |
| 168 | { | |
| 169 | requires (!is_void_v<remove_pointer_t<_Tp>>); // PR c++/78173 | |
| 170 | { __a - __b } -> integral; | |
| 171 | }) | |
| 172 | struct incrementable_traits<_Tp> | |
| 173 | { | |
| 174 | using difference_type | |
| 175 | = make_signed_t<decltype(std::declval<_Tp>() - std::declval<_Tp>())>; | |
| 176 | }; | |
| 177 | ||
| 178 | namespace __detail | |
| 179 | { | |
| 180 | // An iterator such that iterator_traits<_Iter> names a specialization | |
| 181 | // generated from the primary template. | |
| 182 | template<typename _Iter> | |
| 183 | concept __primary_traits_iter | |
| 184 | = __is_base_of(__iterator_traits<_Iter, void>, iterator_traits<_Iter>); | |
| 185 | ||
| 186 | template<typename _Iter, typename _Tp> | |
| 187 | struct __iter_traits_impl | |
| 188 | { using type = iterator_traits<_Iter>; }; | |
| 189 | ||
| 190 | template<typename _Iter, typename _Tp> | |
| 191 | requires __primary_traits_iter<_Iter> | |
| 192 | struct __iter_traits_impl<_Iter, _Tp> | |
| 193 | { using type = _Tp; }; | |
| 194 | ||
| 195 | // ITER_TRAITS | |
| 196 | template<typename _Iter, typename _Tp = _Iter> | |
| 197 | using __iter_traits = typename __iter_traits_impl<_Iter, _Tp>::type; | |
| 198 | } // namespace __detail | |
| 199 | ||
| 200 | template<typename _Tp> | |
| 201 | using iter_difference_t = typename | |
| 202 | __detail::__iter_traits<_Tp, incrementable_traits<_Tp>>::difference_type; | |
| 203 | ||
| 204 | namespace __detail | |
| 205 | { | |
| 206 | template<typename> struct __cond_value_type { }; | |
| 207 | ||
| 208 | template<typename _Tp> requires is_object_v<_Tp> | |
| 209 | struct __cond_value_type<_Tp> | |
| 210 | { using value_type = remove_cv_t<_Tp>; }; | |
| 211 | } // namespace __detail | |
| 212 | ||
| 213 | template<typename> struct readable_traits { }; | |
| 214 | ||
| 215 | template<typename _Tp> | |
| 216 | struct readable_traits<_Tp*> | |
| 217 | : __detail::__cond_value_type<_Tp> | |
| 218 | { }; | |
| 219 | ||
| 220 | template<typename _Iter> requires is_array_v<_Iter> | |
| 221 | struct readable_traits<_Iter> | |
| 222 | { using value_type = remove_cv_t<remove_extent_t<_Iter>>; }; | |
| 223 | ||
| 224 | template<typename _Iter> | |
| 225 | struct readable_traits<const _Iter> | |
| 226 | : readable_traits<_Iter> | |
| 227 | { }; | |
| 228 | ||
| 229 | template<typename _Tp> requires requires { typename _Tp::value_type; } | |
| 230 | struct readable_traits<_Tp> | |
| 231 | : __detail::__cond_value_type<typename _Tp::value_type> | |
| 232 | { }; | |
| 233 | ||
| 234 | template<typename _Tp> requires requires { typename _Tp::element_type; } | |
| 235 | struct readable_traits<_Tp> | |
| 236 | : __detail::__cond_value_type<typename _Tp::element_type> | |
| 237 | { }; | |
| 238 | ||
| 239 | template<typename _Tp> | |
| 240 | using iter_value_t = typename | |
| 241 | __detail::__iter_traits<_Tp, readable_traits<_Tp>>::value_type; | |
| 242 | ||
| 243 | namespace __detail | |
| 244 | { | |
| 245 | template<typename _Iter> | |
| 246 | concept __cpp17_iterator = copyable<_Iter> | |
| 247 | && requires(_Iter __it) | |
| 248 | { | |
| 249 | { *__it } -> __can_reference; | |
| 250 | { ++__it } -> same_as<_Iter&>; | |
| 251 | { *__it++ } -> __can_reference; | |
| 252 | }; | |
| 253 | ||
| 254 | template<typename _Iter> | |
| 255 | concept __cpp17_input_iterator = __cpp17_iterator<_Iter> | |
| 256 | && equality_comparable<_Iter> | |
| 257 | && requires(_Iter __it) | |
| 258 | { | |
| 259 | typename incrementable_traits<_Iter>::difference_type; | |
| 260 | typename readable_traits<_Iter>::value_type; | |
| 261 | typename common_reference_t<iter_reference_t<_Iter>&&, | |
| 262 | typename readable_traits<_Iter>::value_type&>; | |
| 263 | typename common_reference_t<decltype(*__it++)&&, | |
| 264 | typename readable_traits<_Iter>::value_type&>; | |
| 265 | requires signed_integral<typename incrementable_traits<_Iter>::difference_type>; | |
| 266 | }; | |
| 267 | ||
| 268 | template<typename _Iter> | |
| 269 | concept __cpp17_fwd_iterator = __cpp17_input_iterator<_Iter> | |
| 270 | && constructible_from<_Iter> | |
| 271 | && is_lvalue_reference_v<iter_reference_t<_Iter>> | |
| 272 | && same_as<remove_cvref_t<iter_reference_t<_Iter>>, | |
| 273 | typename readable_traits<_Iter>::value_type> | |
| 274 | && requires(_Iter __it) | |
| 275 | { | |
| 276 | { __it++ } -> convertible_to<const _Iter&>; | |
| 277 | { *__it++ } -> same_as<iter_reference_t<_Iter>>; | |
| 278 | }; | |
| 279 | ||
| 280 | template<typename _Iter> | |
| 281 | concept __cpp17_bidi_iterator = __cpp17_fwd_iterator<_Iter> | |
| 282 | && requires(_Iter __it) | |
| 283 | { | |
| 284 | { --__it } -> same_as<_Iter&>; | |
| 285 | { __it-- } -> convertible_to<const _Iter&>; | |
| 286 | { *__it-- } -> same_as<iter_reference_t<_Iter>>; | |
| 287 | }; | |
| 288 | ||
| 289 | template<typename _Iter> | |
| 290 | concept __cpp17_randacc_iterator = __cpp17_bidi_iterator<_Iter> | |
| 291 | && totally_ordered<_Iter> | |
| 292 | && requires(_Iter __it, | |
| 293 | typename incrementable_traits<_Iter>::difference_type __n) | |
| 294 | { | |
| 295 | { __it += __n } -> same_as<_Iter&>; | |
| 296 | { __it -= __n } -> same_as<_Iter&>; | |
| 297 | { __it + __n } -> same_as<_Iter>; | |
| 298 | { __n + __it } -> same_as<_Iter>; | |
| 299 | { __it - __n } -> same_as<_Iter>; | |
| 300 | { __it - __it } -> same_as<decltype(__n)>; | |
| 301 | { __it[__n] } -> convertible_to<iter_reference_t<_Iter>>; | |
| 302 | }; | |
| 303 | ||
| 304 | template<typename _Iter> | |
| 305 | concept __iter_with_nested_types = requires { | |
| 306 | typename _Iter::iterator_category; | |
| 307 | typename _Iter::value_type; | |
| 308 | typename _Iter::difference_type; | |
| 309 | typename _Iter::reference; | |
| 310 | }; | |
| 311 | ||
| 6d0dff49 JW |
312 | template<typename _Iter> |
| 313 | concept __iter_without_nested_types = !__iter_with_nested_types<_Iter>; | |
| 314 | ||
| 315 | template<typename _Iter, bool __use_arrow = false> | |
| 316 | struct __ptr | |
| 317 | { using type = void; }; | |
| 318 | ||
| 319 | template<typename _Iter> requires requires { typename _Iter::pointer; } | |
| 320 | struct __ptr<_Iter, true> | |
| 321 | { using type = typename _Iter::pointer; }; | |
| 322 | ||
| 323 | template<typename _Iter> requires requires { typename _Iter::pointer; } | |
| 324 | struct __ptr<_Iter, false> | |
| 325 | { using type = typename _Iter::pointer; }; | |
| 326 | ||
| 327 | template<typename _Iter> | |
| 328 | requires (!requires { typename _Iter::pointer; } | |
| 329 | && requires(_Iter& __it) { __it.operator->(); }) | |
| 330 | struct __ptr<_Iter, true> | |
| 331 | { using type = decltype(std::declval<_Iter&>().operator->()); }; | |
| 332 | ||
| 333 | template<typename _Iter> | |
| 334 | struct __ref | |
| 335 | { using type = iter_reference_t<_Iter>; }; | |
| 336 | ||
| 337 | template<typename _Iter> requires requires { typename _Iter::reference; } | |
| 338 | struct __ref<_Iter> | |
| 339 | { using type = typename _Iter::reference; }; | |
| 340 | ||
| 341 | template<typename _Iter> | |
| 342 | struct __cat | |
| 343 | { using type = input_iterator_tag; }; | |
| 344 | ||
| 345 | template<typename _Iter> | |
| 346 | requires requires { typename _Iter::iterator_category; } | |
| 347 | struct __cat<_Iter> | |
| 348 | { using type = typename _Iter::iterator_category; }; | |
| 349 | ||
| 350 | template<typename _Iter> | |
| 351 | requires (!requires { typename _Iter::iterator_category; } | |
| 352 | && __detail::__cpp17_randacc_iterator<_Iter>) | |
| 353 | struct __cat<_Iter> | |
| 354 | { using type = random_access_iterator_tag; }; | |
| 355 | ||
| 356 | template<typename _Iter> | |
| 357 | requires (!requires { typename _Iter::iterator_category; } | |
| 358 | && __detail::__cpp17_bidi_iterator<_Iter>) | |
| 359 | struct __cat<_Iter> | |
| 360 | { using type = bidirectional_iterator_tag; }; | |
| 361 | ||
| 362 | template<typename _Iter> | |
| 363 | requires (!requires { typename _Iter::iterator_category; } | |
| 364 | && __detail::__cpp17_fwd_iterator<_Iter>) | |
| 365 | struct __cat<_Iter> | |
| 366 | { using type = forward_iterator_tag; }; | |
| 367 | ||
| 368 | template<typename _Iter> | |
| 369 | struct __diff | |
| 370 | { using type = void; }; | |
| 371 | ||
| 372 | template<typename _Iter> | |
| 373 | requires requires { | |
| 374 | typename incrementable_traits<_Iter>::difference_type; | |
| 375 | } | |
| 376 | struct __diff<_Iter> | |
| 377 | { | |
| 378 | using type = typename incrementable_traits<_Iter>::difference_type; | |
| 379 | }; | |
| 380 | ||
| 381 | } // namespace __detail | |
| 382 | ||
| 383 | template<typename _Iterator> | |
| 384 | requires __detail::__iter_with_nested_types<_Iterator> | |
| 385 | struct __iterator_traits<_Iterator, void> | |
| 386 | { | |
| 387 | using iterator_category = typename _Iterator::iterator_category; | |
| 388 | using value_type = typename _Iterator::value_type; | |
| 389 | using difference_type = typename _Iterator::difference_type; | |
| 390 | using pointer = typename __detail::__ptr<_Iterator>::type; | |
| 391 | using reference = typename _Iterator::reference; | |
| 392 | }; | |
| 393 | ||
| 394 | template<typename _Iterator> | |
| 395 | requires __detail::__iter_without_nested_types<_Iterator> | |
| 396 | && __detail::__cpp17_input_iterator<_Iterator> | |
| 397 | struct __iterator_traits<_Iterator, void> | |
| 398 | { | |
| 399 | using iterator_category = typename __detail::__cat<_Iterator>::type; | |
| 400 | using value_type | |
| 401 | = typename readable_traits<_Iterator>::value_type; | |
| 402 | using difference_type | |
| 403 | = typename incrementable_traits<_Iterator>::difference_type; | |
| 404 | using pointer = typename __detail::__ptr<_Iterator, true>::type; | |
| 405 | using reference = typename __detail::__ref<_Iterator>::type; | |
| 406 | }; | |
| 407 | ||
| 408 | template<typename _Iterator> | |
| 409 | requires __detail::__iter_without_nested_types<_Iterator> | |
| 410 | && __detail::__cpp17_iterator<_Iterator> | |
| 411 | struct __iterator_traits<_Iterator, void> | |
| 412 | { | |
| 413 | using iterator_category = output_iterator_tag; | |
| 414 | using value_type = void; | |
| 415 | using difference_type = typename __detail::__diff<_Iterator>::type; | |
| 416 | using pointer = void; | |
| 417 | using reference = void; | |
| 418 | }; | |
| 419 | ||
| 420 | namespace __detail | |
| 421 | { | |
| 422 | template<typename _Iter> | |
| 270082a7 | 423 | struct __iter_concept_impl; |
| 6d0dff49 | 424 | |
| 270082a7 | 425 | // ITER_CONCEPT(I) is ITER_TRAITS(I)::iterator_concept if that is valid. |
| 6d0dff49 JW |
426 | template<typename _Iter> |
| 427 | requires requires { typename __iter_traits<_Iter>::iterator_concept; } | |
| 428 | struct __iter_concept_impl<_Iter> | |
| 429 | { using type = typename __iter_traits<_Iter>::iterator_concept; }; | |
| 430 | ||
| 270082a7 | 431 | // Otherwise, ITER_TRAITS(I)::iterator_category if that is valid. |
| 6d0dff49 JW |
432 | template<typename _Iter> |
| 433 | requires (!requires { typename __iter_traits<_Iter>::iterator_concept; } | |
| 434 | && requires { typename __iter_traits<_Iter>::iterator_category; }) | |
| 435 | struct __iter_concept_impl<_Iter> | |
| 436 | { using type = typename __iter_traits<_Iter>::iterator_category; }; | |
| 437 | ||
| 270082a7 | 438 | // Otherwise, random_access_tag if iterator_traits<I> is not specialized. |
| 6d0dff49 JW |
439 | template<typename _Iter> |
| 440 | requires (!requires { typename __iter_traits<_Iter>::iterator_concept; } | |
| 441 | && !requires { typename __iter_traits<_Iter>::iterator_category; } | |
| 442 | && __primary_traits_iter<_Iter>) | |
| 443 | struct __iter_concept_impl<_Iter> | |
| 444 | { using type = random_access_iterator_tag; }; | |
| 445 | ||
| 270082a7 JW |
446 | // Otherwise, there is no ITER_CONCEPT(I) type. |
| 447 | template<typename _Iter> | |
| 448 | struct __iter_concept_impl | |
| 449 | { }; | |
| 450 | ||
| 451 | // ITER_CONCEPT | |
| 6d0dff49 JW |
452 | template<typename _Iter> |
| 453 | using __iter_concept = typename __iter_concept_impl<_Iter>::type; | |
| 454 | } // namespace __detail | |
| 455 | ||
| 456 | /// Requirements for types that are readable by applying operator*. | |
| 457 | template<typename _In> | |
| 458 | concept readable = requires | |
| 459 | { | |
| 460 | typename iter_value_t<_In>; | |
| 461 | typename iter_reference_t<_In>; | |
| 462 | typename iter_rvalue_reference_t<_In>; | |
| 463 | } | |
| 464 | && common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&> | |
| 465 | && common_reference_with<iter_reference_t<_In>&&, | |
| 466 | iter_rvalue_reference_t<_In>&&> | |
| 467 | && common_reference_with<iter_rvalue_reference_t<_In>&&, | |
| 468 | const iter_value_t<_In>&>; | |
| 469 | ||
| 470 | namespace __detail | |
| 471 | { | |
| 472 | // FIXME: needed due to PR c++/67704 | |
| 473 | template<readable _Tp> | |
| 474 | struct __iter_common_ref | |
| 475 | : common_reference<iter_reference_t<_Tp>, iter_value_t<_Tp>&> | |
| 476 | { }; | |
| 6d0dff49 JW |
477 | } // namespace __detail |
| 478 | ||
| 479 | template<typename _Tp> | |
| 480 | using iter_common_reference_t | |
| 481 | = typename __detail::__iter_common_ref<_Tp>::type; | |
| 482 | ||
| 483 | /// Requirements for writing a value into an iterator's referenced object. | |
| 484 | template<typename _Out, typename _Tp> | |
| 485 | concept writable = requires(_Out&& __o, _Tp&& __t) | |
| 486 | { | |
| 487 | *__o = std::forward<_Tp>(__t); | |
| 488 | *std::forward<_Out>(__o) = std::forward<_Tp>(__t); | |
| 489 | const_cast<const iter_reference_t<_Out>&&>(*__o) | |
| 490 | = std::forward<_Tp>(__t); | |
| 491 | const_cast<const iter_reference_t<_Out>&&>(*std::forward<_Out>(__o)) | |
| 492 | = std::forward<_Tp>(__t); | |
| 493 | }; | |
| 494 | ||
| 495 | /// Requirements on types that can be incremented with ++. | |
| 496 | template<typename _Iter> | |
| a31517cb | 497 | concept weakly_incrementable = default_initializable<_Iter> |
| 6d0dff49 JW |
498 | && movable<_Iter> |
| 499 | && requires(_Iter __i) | |
| 500 | { | |
| 501 | typename iter_difference_t<_Iter>; | |
| 502 | requires signed_integral<iter_difference_t<_Iter>>; | |
| 503 | { ++__i } -> same_as<_Iter&>; | |
| 504 | __i++; | |
| 505 | }; | |
| 506 | ||
| 507 | template<typename _Iter> | |
| 508 | concept incrementable = regular<_Iter> && weakly_incrementable<_Iter> | |
| 509 | && requires(_Iter __i) { { __i++ } -> same_as<_Iter>; }; | |
| 510 | ||
| 511 | template<typename _Iter> | |
| 512 | concept input_or_output_iterator | |
| 513 | = requires(_Iter __i) { { *__i } -> __detail::__can_reference; } | |
| 514 | && weakly_incrementable<_Iter>; | |
| 515 | ||
| 516 | template<typename _Sent, typename _Iter> | |
| 517 | concept sentinel_for = semiregular<_Sent> | |
| 518 | && input_or_output_iterator<_Iter> | |
| 519 | && __detail::__weakly_eq_cmp_with<_Sent, _Iter>; | |
| 520 | ||
| 521 | template<typename _Sent, typename _Iter> | |
| d99828ee | 522 | inline constexpr bool disable_sized_sentinel_for = false; |
| 6d0dff49 JW |
523 | |
| 524 | template<typename _Sent, typename _Iter> | |
| 525 | concept sized_sentinel_for = sentinel_for<_Sent, _Iter> | |
| d99828ee | 526 | && !disable_sized_sentinel_for<remove_cv_t<_Sent>, remove_cv_t<_Iter>> |
| 6d0dff49 JW |
527 | && requires(const _Iter& __i, const _Sent& __s) |
| 528 | { | |
| 529 | { __s - __i } -> same_as<iter_difference_t<_Iter>>; | |
| 530 | { __i - __s } -> same_as<iter_difference_t<_Iter>>; | |
| 531 | }; | |
| 532 | ||
| 533 | template<typename _Iter> | |
| 534 | concept input_iterator = input_or_output_iterator<_Iter> | |
| 535 | && readable<_Iter> | |
| 536 | && requires { typename __detail::__iter_concept<_Iter>; } | |
| 537 | && derived_from<__detail::__iter_concept<_Iter>, input_iterator_tag>; | |
| 538 | ||
| 539 | template<typename _Iter, typename _Tp> | |
| 540 | concept output_iterator = input_or_output_iterator<_Iter> | |
| 541 | && writable<_Iter, _Tp> | |
| 542 | && requires(_Iter __i, _Tp&& __t) { *__i++ = std::forward<_Tp>(__t); }; | |
| 543 | ||
| 544 | template<typename _Iter> | |
| 545 | concept forward_iterator = input_iterator<_Iter> | |
| 546 | && derived_from<__detail::__iter_concept<_Iter>, forward_iterator_tag> | |
| 547 | && incrementable<_Iter> && sentinel_for<_Iter, _Iter>; | |
| 548 | ||
| 549 | template<typename _Iter> | |
| 550 | concept bidirectional_iterator = forward_iterator<_Iter> | |
| 551 | && derived_from<__detail::__iter_concept<_Iter>, | |
| 552 | bidirectional_iterator_tag> | |
| 553 | && requires(_Iter __i) | |
| 554 | { | |
| 555 | { --__i } -> same_as<_Iter&>; | |
| 556 | { __i-- } -> same_as<_Iter>; | |
| 557 | }; | |
| 558 | ||
| 559 | template<typename _Iter> | |
| 560 | concept random_access_iterator = bidirectional_iterator<_Iter> | |
| 561 | && derived_from<__detail::__iter_concept<_Iter>, | |
| 562 | random_access_iterator_tag> | |
| 563 | && totally_ordered<_Iter> && sized_sentinel_for<_Iter, _Iter> | |
| 564 | && requires(_Iter __i, const _Iter __j, | |
| 565 | const iter_difference_t<_Iter> __n) | |
| 566 | { | |
| 567 | { __i += __n } -> same_as<_Iter&>; | |
| 568 | { __j + __n } -> same_as<_Iter>; | |
| 569 | { __n + __j } -> same_as<_Iter>; | |
| 570 | { __i -= __n } -> same_as<_Iter&>; | |
| 571 | { __j - __n } -> same_as<_Iter>; | |
| 572 | { __j[__n] } -> same_as<iter_reference_t<_Iter>>; | |
| 573 | }; | |
| 574 | ||
| 575 | template<typename _Iter> | |
| 576 | concept contiguous_iterator = random_access_iterator<_Iter> | |
| 577 | && derived_from<__detail::__iter_concept<_Iter>, contiguous_iterator_tag> | |
| 578 | && is_lvalue_reference_v<iter_reference_t<_Iter>> | |
| 579 | && same_as<iter_value_t<_Iter>, remove_cvref_t<iter_reference_t<_Iter>>> | |
| 580 | && requires(const _Iter& __i) | |
| 581 | { | |
| 582 | { std::to_address(__i) } | |
| 583 | -> same_as<add_pointer_t<iter_reference_t<_Iter>>>; | |
| 584 | }; | |
| 585 | ||
| 586 | // [indirectcallable], indirect callable requirements | |
| 587 | ||
| 588 | // [indirectcallable.indirectinvocable], indirect callables | |
| 589 | ||
| 590 | template<typename _Fn, typename _Iter> | |
| 591 | concept indirectly_unary_invocable = readable<_Iter> | |
| 592 | && copy_constructible<_Fn> && invocable<_Fn&, iter_value_t<_Iter>&> | |
| 593 | && invocable<_Fn&, iter_reference_t<_Iter>> | |
| 594 | && invocable<_Fn&, iter_common_reference_t<_Iter>> | |
| 595 | && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>, | |
| 596 | invoke_result_t<_Fn&, iter_reference_t<_Iter>>>; | |
| 597 | ||
| 598 | template<typename _Fn, typename _Iter> | |
| 599 | concept indirectly_regular_unary_invocable = readable<_Iter> | |
| 600 | && copy_constructible<_Fn> | |
| 601 | && regular_invocable<_Fn&, iter_value_t<_Iter>&> | |
| 602 | && regular_invocable<_Fn&, iter_reference_t<_Iter>> | |
| 603 | && regular_invocable<_Fn&, iter_common_reference_t<_Iter>> | |
| 604 | && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>, | |
| 605 | invoke_result_t<_Fn&, iter_reference_t<_Iter>>>; | |
| 606 | ||
| 607 | template<typename _Fn, typename _Iter> | |
| 608 | concept indirect_unary_predicate = readable<_Iter> | |
| 609 | && copy_constructible<_Fn> && predicate<_Fn&, iter_value_t<_Iter>&> | |
| 610 | && predicate<_Fn&, iter_reference_t<_Iter>> | |
| 611 | && predicate<_Fn&, iter_common_reference_t<_Iter>>; | |
| 612 | ||
| 270082a7 JW |
613 | template<typename _Fn, typename _I1, typename _I2> |
| 614 | concept indirect_binary_predicate = readable<_I1> && readable<_I2> | |
| 615 | && copy_constructible<_Fn> | |
| 616 | && predicate<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&> | |
| 617 | && predicate<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>> | |
| 618 | && predicate<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&> | |
| 619 | && predicate<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>> | |
| 620 | && predicate<_Fn&, iter_common_reference_t<_I1>, | |
| 621 | iter_common_reference_t<_I2>>; | |
| 622 | ||
| 6d0dff49 | 623 | template<typename _Fn, typename _I1, typename _I2 = _I1> |
| 270082a7 | 624 | concept indirect_equivalence_relation = readable<_I1> && readable<_I2> |
| 6d0dff49 | 625 | && copy_constructible<_Fn> |
| 270082a7 JW |
626 | && equivalence_relation<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&> |
| 627 | && equivalence_relation<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>> | |
| 628 | && equivalence_relation<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&> | |
| 629 | && equivalence_relation<_Fn&, iter_reference_t<_I1>, | |
| 630 | iter_reference_t<_I2>> | |
| 631 | && equivalence_relation<_Fn&, iter_common_reference_t<_I1>, | |
| 632 | iter_common_reference_t<_I2>>; | |
| 6d0dff49 JW |
633 | |
| 634 | template<typename _Fn, typename _I1, typename _I2 = _I1> | |
| 635 | concept indirect_strict_weak_order = readable<_I1> && readable<_I2> | |
| 636 | && copy_constructible<_Fn> | |
| 637 | && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&> | |
| 638 | && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>> | |
| 639 | && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&> | |
| 640 | && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>> | |
| 641 | && strict_weak_order<_Fn&, iter_common_reference_t<_I1>, | |
| 642 | iter_common_reference_t<_I2>>; | |
| 643 | ||
| 990a09e4 JW |
644 | namespace __detail |
| 645 | { | |
| 646 | // FIXME: needed due to PR c++/67704 | |
| 647 | template<typename _Fn, typename... _Is> | |
| 648 | struct __indirect_result | |
| 649 | { }; | |
| 650 | ||
| 651 | template<typename _Fn, typename... _Is> | |
| 652 | requires (readable<_Is> && ...) | |
| 653 | && invocable<_Fn, iter_reference_t<_Is>...> | |
| 654 | struct __indirect_result<_Fn, _Is...> | |
| 655 | : invoke_result<_Fn, iter_reference_t<_Is>...> | |
| 656 | { }; | |
| 657 | } // namespace __detail | |
| 658 | ||
| 6d0dff49 JW |
659 | template<typename _Fn, typename... _Is> |
| 660 | using indirect_result_t = typename | |
| 990a09e4 | 661 | __detail::__indirect_result<_Fn, _Is...>::type; |
| 6d0dff49 JW |
662 | |
| 663 | /// [projected], projected | |
| 664 | template<readable _Iter, indirectly_regular_unary_invocable<_Iter> _Proj> | |
| 665 | struct projected | |
| 666 | { | |
| 667 | using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>; | |
| 990a09e4 | 668 | |
| 6d0dff49 JW |
669 | indirect_result_t<_Proj&, _Iter> operator*() const; // not defined |
| 670 | }; | |
| 671 | ||
| 672 | template<weakly_incrementable _Iter, typename _Proj> | |
| 673 | struct incrementable_traits<projected<_Iter, _Proj>> | |
| 674 | { using difference_type = iter_difference_t<_Iter>; }; | |
| 675 | ||
| 676 | // [alg.req], common algorithm requirements | |
| 677 | ||
| 678 | /// [alg.req.ind.move], concept `indirectly_movable` | |
| 679 | ||
| 680 | template<typename _In, typename _Out> | |
| 681 | concept indirectly_movable = readable<_In> | |
| 682 | && writable<_Out, iter_rvalue_reference_t<_In>>; | |
| 683 | ||
| 684 | template<typename _In, typename _Out> | |
| 685 | concept indirectly_movable_storable = indirectly_movable<_In, _Out> | |
| 686 | && writable<_Out, iter_value_t<_In>> && movable<iter_value_t<_In>> | |
| 687 | && constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>> | |
| 688 | && assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>; | |
| 689 | ||
| 690 | /// [alg.req.ind.copy], concept `indirectly_copyable` | |
| 691 | template<typename _In, typename _Out> | |
| 692 | concept indirectly_copyable = readable<_In> | |
| 693 | && writable<_Out, iter_reference_t<_In>>; | |
| 694 | ||
| 695 | template<typename _In, typename _Out> | |
| 696 | concept indirectly_copyable_storable = indirectly_copyable<_In, _Out> | |
| 697 | && writable<_Out, const iter_value_t<_In>&> | |
| 698 | && copyable<iter_value_t<_In>> | |
| 699 | && constructible_from<iter_value_t<_In>, iter_reference_t<_In>> | |
| 700 | && assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>; | |
| 701 | ||
| 702 | namespace ranges | |
| 703 | { | |
| 704 | namespace __cust_iswap | |
| 705 | { | |
| 706 | template<typename _It1, typename _It2> | |
| 7def9bd7 | 707 | void iter_swap(_It1, _It2) = delete; |
| 6d0dff49 JW |
708 | |
| 709 | template<typename _Tp, typename _Up> | |
| 710 | concept __adl_iswap | |
| 711 | = (std::__detail::__class_or_enum<remove_reference_t<_Tp>> | |
| 712 | || std::__detail::__class_or_enum<remove_reference_t<_Up>>) | |
| 713 | && requires(_Tp&& __t, _Up&& __u) { | |
| 714 | iter_swap(static_cast<_Tp&&>(__t), static_cast<_Up&&>(__u)); | |
| 715 | }; | |
| 716 | ||
| 717 | template<typename _Xp, typename _Yp> | |
| 718 | constexpr iter_value_t<remove_reference_t<_Xp>> | |
| 719 | __iter_exchange_move(_Xp&& __x, _Yp&& __y) | |
| 720 | noexcept(noexcept(iter_value_t<remove_reference_t<_Xp>>(iter_move(__x))) | |
| 721 | && noexcept(*__x = iter_move(__y))) | |
| 722 | { | |
| 723 | iter_value_t<remove_reference_t<_Xp>> __old_value(iter_move(__x)); | |
| 724 | *__x = iter_move(__y); | |
| 725 | return __old_value; | |
| 726 | } | |
| 727 | ||
| 728 | struct _IterSwap | |
| 729 | { | |
| 730 | private: | |
| 731 | template<typename _Tp, typename _Up> | |
| 732 | static constexpr bool | |
| 733 | _S_noexcept() | |
| 734 | { | |
| 735 | if constexpr (__adl_iswap<_Tp, _Up>) | |
| 736 | return noexcept(iter_swap(std::declval<_Tp>(), | |
| 737 | std::declval<_Up>())); | |
| 738 | else if constexpr (readable<_Tp> && readable<_Up> | |
| 739 | && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>) | |
| 740 | return noexcept(ranges::swap(*std::declval<_Tp>(), | |
| 741 | *std::declval<_Up>())); | |
| 742 | else | |
| 743 | return noexcept(*std::declval<_Tp>() | |
| 744 | = __iter_exchange_move(std::declval<_Up>(), | |
| 745 | std::declval<_Tp>())); | |
| 746 | } | |
| 747 | ||
| 748 | public: | |
| 749 | template<typename _Tp, typename _Up> | |
| 750 | requires __adl_iswap<_Tp, _Up> | |
| 7def9bd7 JW |
751 | || (readable<remove_reference_t<_Tp>> |
| 752 | && readable<remove_reference_t<_Up>> | |
| 6d0dff49 JW |
753 | && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>) |
| 754 | || (indirectly_movable_storable<_Tp, _Up> | |
| 755 | && indirectly_movable_storable<_Up, _Tp>) | |
| 756 | constexpr void | |
| 757 | operator()(_Tp&& __e1, _Up&& __e2) const | |
| 758 | noexcept(_S_noexcept<_Tp, _Up>()) | |
| 759 | { | |
| 760 | if constexpr (__adl_iswap<_Tp, _Up>) | |
| 761 | iter_swap(static_cast<_Tp&&>(__e1), static_cast<_Up&&>(__e2)); | |
| 762 | else if constexpr (readable<_Tp> && readable<_Up> | |
| 763 | && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>) | |
| 764 | ranges::swap(*__e1, *__e2); | |
| 765 | else | |
| 766 | *__e1 = __iter_exchange_move(__e2, __e1); | |
| 767 | } | |
| 768 | }; | |
| 769 | } // namespace __cust_iswap | |
| 770 | ||
| 771 | inline namespace __cust | |
| 772 | { | |
| 773 | inline constexpr __cust_iswap::_IterSwap iter_swap{}; | |
| 774 | } // inline namespace __cust | |
| 775 | ||
| 776 | } // namespace ranges | |
| 777 | ||
| 778 | /// [alg.req.ind.swap], concept `indirectly_swappable` | |
| 779 | template<typename _I1, typename _I2 = _I1> | |
| 780 | concept indirectly_swappable = readable<_I1> && readable<_I2> | |
| 781 | && requires(_I1& __i1, _I2& __i2) | |
| 782 | { | |
| 783 | ranges::iter_swap(__i1, __i1); | |
| 784 | ranges::iter_swap(__i2, __i2); | |
| 785 | ranges::iter_swap(__i1, __i2); | |
| 786 | ranges::iter_swap(__i2, __i1); | |
| 787 | }; | |
| 788 | ||
| 789 | /// [alg.req.ind.cmp], concept `indirectly_comparable` | |
| 790 | template<typename _I1, typename _I2, typename _Rel, typename _P1 = identity, | |
| 791 | typename _P2 = identity> | |
| 792 | concept indirectly_comparable | |
| 270082a7 JW |
793 | = indirect_binary_predicate<_Rel, projected<_I1, _P1>, |
| 794 | projected<_I2, _P2>>; | |
| 6d0dff49 JW |
795 | |
| 796 | /// [alg.req.permutable], concept `permutable` | |
| 797 | template<typename _Iter> | |
| 798 | concept permutable = forward_iterator<_Iter> | |
| 799 | && indirectly_movable_storable<_Iter, _Iter> | |
| 800 | && indirectly_swappable<_Iter, _Iter>; | |
| 801 | ||
| 802 | /// [alg.req.mergeable], concept `mergeable` | |
| 803 | template<typename _I1, typename _I2, typename _Out, | |
| 804 | typename _Rel = ranges::less, typename _P1 = identity, | |
| 805 | typename _P2 = identity> | |
| 806 | concept mergeable = input_iterator<_I1> && input_iterator<_I2> | |
| 807 | && weakly_incrementable<_Out> && indirectly_copyable<_I1, _Out> | |
| 808 | && indirectly_copyable<_I2, _Out> | |
| 809 | && indirect_strict_weak_order<_Rel, projected<_I1, _P1>, | |
| 810 | projected<_I2, _P2>>; | |
| 811 | ||
| 812 | /// [alg.req.sortable], concept `sortable` | |
| 813 | template<typename _Iter, typename _Rel = ranges::less, | |
| 814 | typename _Proj = identity> | |
| 815 | concept sortable = permutable<_Iter> | |
| 816 | && indirect_strict_weak_order<_Rel, projected<_Iter, _Proj>>; | |
| 817 | ||
| 818 | struct unreachable_sentinel_t | |
| 819 | { | |
| 820 | template<weakly_incrementable _It> | |
| 821 | friend constexpr bool | |
| 822 | operator==(unreachable_sentinel_t, const _It&) noexcept | |
| 823 | { return false; } | |
| 6d0dff49 JW |
824 | }; |
| 825 | ||
| 826 | inline constexpr unreachable_sentinel_t unreachable_sentinel{}; | |
| 827 | ||
| 828 | struct default_sentinel_t { }; | |
| 829 | inline constexpr default_sentinel_t default_sentinel{}; | |
| 830 | ||
| 831 | _GLIBCXX_END_NAMESPACE_VERSION | |
| 832 | } // namespace std | |
| 833 | #endif // C++20 library concepts | |
| 834 | #endif // _ITERATOR_CONCEPTS_H |