1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___ITERATOR_ITERATOR_TRAITS_H 11 #define _LIBCPP___ITERATOR_ITERATOR_TRAITS_H 12 13 #include <__concepts/arithmetic.h> 14 #include <__concepts/constructible.h> 15 #include <__concepts/convertible_to.h> 16 #include <__concepts/copyable.h> 17 #include <__concepts/equality_comparable.h> 18 #include <__concepts/same_as.h> 19 #include <__concepts/totally_ordered.h> 20 #include <__config> 21 #include <__fwd/pair.h> 22 #include <__iterator/incrementable_traits.h> 23 #include <__iterator/readable_traits.h> 24 #include <__type_traits/add_const.h> 25 #include <__type_traits/common_reference.h> 26 #include <__type_traits/conditional.h> 27 #include <__type_traits/disjunction.h> 28 #include <__type_traits/is_convertible.h> 29 #include <__type_traits/is_object.h> 30 #include <__type_traits/is_primary_template.h> 31 #include <__type_traits/is_reference.h> 32 #include <__type_traits/is_valid_expansion.h> 33 #include <__type_traits/remove_const.h> 34 #include <__type_traits/remove_cv.h> 35 #include <__type_traits/remove_cvref.h> 36 #include <__type_traits/void_t.h> 37 #include <__utility/declval.h> 38 #include <cstddef> 39 40 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 41 # pragma GCC system_header 42 #endif 43 44 _LIBCPP_BEGIN_NAMESPACE_STD 45 46 #if _LIBCPP_STD_VER >= 20 47 48 template <class _Tp> 49 using __with_reference = _Tp&; 50 51 template <class _Tp> 52 concept __can_reference = requires { 53 typename __with_reference<_Tp>; 54 }; 55 56 template <class _Tp> 57 concept __dereferenceable = requires(_Tp& __t) { 58 { *__t } -> __can_reference; // not required to be equality-preserving 59 }; 60 61 // [iterator.traits] 62 template<__dereferenceable _Tp> 63 using iter_reference_t = decltype(*std::declval<_Tp&>()); 64 65 #endif // _LIBCPP_STD_VER >= 20 66 67 template <class _Iter> 68 struct _LIBCPP_TEMPLATE_VIS iterator_traits; 69 70 struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {}; 71 struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {}; 72 struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag {}; 73 struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {}; 74 struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {}; 75 #if _LIBCPP_STD_VER >= 20 76 struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag : public random_access_iterator_tag {}; 77 #endif 78 79 template <class _Iter> 80 struct __iter_traits_cache { 81 using type = _If< 82 __is_primary_template<iterator_traits<_Iter> >::value, 83 _Iter, 84 iterator_traits<_Iter> 85 >; 86 }; 87 template <class _Iter> 88 using _ITER_TRAITS = typename __iter_traits_cache<_Iter>::type; 89 90 struct __iter_concept_concept_test { 91 template <class _Iter> 92 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_concept; 93 }; 94 struct __iter_concept_category_test { 95 template <class _Iter> 96 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_category; 97 }; 98 struct __iter_concept_random_fallback { 99 template <class _Iter> 100 using _Apply = __enable_if_t< 101 __is_primary_template<iterator_traits<_Iter> >::value, 102 random_access_iterator_tag 103 >; 104 }; 105 106 template <class _Iter, class _Tester> struct __test_iter_concept 107 : _IsValidExpansion<_Tester::template _Apply, _Iter>, 108 _Tester 109 { 110 }; 111 112 template <class _Iter> 113 struct __iter_concept_cache { 114 using type = _Or< 115 __test_iter_concept<_Iter, __iter_concept_concept_test>, 116 __test_iter_concept<_Iter, __iter_concept_category_test>, 117 __test_iter_concept<_Iter, __iter_concept_random_fallback> 118 >; 119 }; 120 121 template <class _Iter> 122 using _ITER_CONCEPT = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>; 123 124 125 template <class _Tp> 126 struct __has_iterator_typedefs 127 { 128 private: 129 template <class _Up> static false_type __test(...); 130 template <class _Up> static true_type __test(__void_t<typename _Up::iterator_category>* = nullptr, 131 __void_t<typename _Up::difference_type>* = nullptr, 132 __void_t<typename _Up::value_type>* = nullptr, 133 __void_t<typename _Up::reference>* = nullptr, 134 __void_t<typename _Up::pointer>* = nullptr); 135 public: 136 static const bool value = decltype(__test<_Tp>(0,0,0,0,0))::value; 137 }; 138 139 140 template <class _Tp> 141 struct __has_iterator_category 142 { 143 private: 144 template <class _Up> static false_type __test(...); 145 template <class _Up> static true_type __test(typename _Up::iterator_category* = nullptr); 146 public: 147 static const bool value = decltype(__test<_Tp>(nullptr))::value; 148 }; 149 150 template <class _Tp> 151 struct __has_iterator_concept 152 { 153 private: 154 template <class _Up> static false_type __test(...); 155 template <class _Up> static true_type __test(typename _Up::iterator_concept* = nullptr); 156 public: 157 static const bool value = decltype(__test<_Tp>(nullptr))::value; 158 }; 159 160 #if _LIBCPP_STD_VER >= 20 161 162 // The `cpp17-*-iterator` exposition-only concepts have very similar names to the `Cpp17*Iterator` named requirements 163 // from `[iterator.cpp17]`. To avoid confusion between the two, the exposition-only concepts have been banished to 164 // a "detail" namespace indicating they have a niche use-case. 165 namespace __iterator_traits_detail { 166 template<class _Ip> 167 concept __cpp17_iterator = 168 requires(_Ip __i) { 169 { *__i } -> __can_reference; 170 { ++__i } -> same_as<_Ip&>; 171 { *__i++ } -> __can_reference; 172 } && 173 copyable<_Ip>; 174 175 template<class _Ip> 176 concept __cpp17_input_iterator = 177 __cpp17_iterator<_Ip> && 178 equality_comparable<_Ip> && 179 requires(_Ip __i) { 180 typename incrementable_traits<_Ip>::difference_type; 181 typename indirectly_readable_traits<_Ip>::value_type; 182 typename common_reference_t<iter_reference_t<_Ip>&&, 183 typename indirectly_readable_traits<_Ip>::value_type&>; 184 typename common_reference_t<decltype(*__i++)&&, 185 typename indirectly_readable_traits<_Ip>::value_type&>; 186 requires signed_integral<typename incrementable_traits<_Ip>::difference_type>; 187 }; 188 189 template<class _Ip> 190 concept __cpp17_forward_iterator = 191 __cpp17_input_iterator<_Ip> && 192 constructible_from<_Ip> && 193 is_reference_v<iter_reference_t<_Ip>> && 194 same_as<remove_cvref_t<iter_reference_t<_Ip>>, 195 typename indirectly_readable_traits<_Ip>::value_type> && 196 requires(_Ip __i) { 197 { __i++ } -> convertible_to<_Ip const&>; 198 { *__i++ } -> same_as<iter_reference_t<_Ip>>; 199 }; 200 201 template<class _Ip> 202 concept __cpp17_bidirectional_iterator = 203 __cpp17_forward_iterator<_Ip> && 204 requires(_Ip __i) { 205 { --__i } -> same_as<_Ip&>; 206 { __i-- } -> convertible_to<_Ip const&>; 207 { *__i-- } -> same_as<iter_reference_t<_Ip>>; 208 }; 209 210 template<class _Ip> 211 concept __cpp17_random_access_iterator = 212 __cpp17_bidirectional_iterator<_Ip> && 213 totally_ordered<_Ip> && 214 requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) { 215 { __i += __n } -> same_as<_Ip&>; 216 { __i -= __n } -> same_as<_Ip&>; 217 { __i + __n } -> same_as<_Ip>; 218 { __n + __i } -> same_as<_Ip>; 219 { __i - __n } -> same_as<_Ip>; 220 { __i - __i } -> same_as<decltype(__n)>; // NOLINT(misc-redundant-expression) ; This is llvm.org/PR54114 221 { __i[__n] } -> convertible_to<iter_reference_t<_Ip>>; 222 }; 223 } // namespace __iterator_traits_detail 224 225 template<class _Ip> 226 concept __has_member_reference = requires { typename _Ip::reference; }; 227 228 template<class _Ip> 229 concept __has_member_pointer = requires { typename _Ip::pointer; }; 230 231 template<class _Ip> 232 concept __has_member_iterator_category = requires { typename _Ip::iterator_category; }; 233 234 template<class _Ip> 235 concept __specifies_members = requires { 236 typename _Ip::value_type; 237 typename _Ip::difference_type; 238 requires __has_member_reference<_Ip>; 239 requires __has_member_iterator_category<_Ip>; 240 }; 241 242 template<class> 243 struct __iterator_traits_member_pointer_or_void { 244 using type = void; 245 }; 246 247 template<__has_member_pointer _Tp> 248 struct __iterator_traits_member_pointer_or_void<_Tp> { 249 using type = typename _Tp::pointer; 250 }; 251 252 template<class _Tp> 253 concept __cpp17_iterator_missing_members = 254 !__specifies_members<_Tp> && 255 __iterator_traits_detail::__cpp17_iterator<_Tp>; 256 257 template<class _Tp> 258 concept __cpp17_input_iterator_missing_members = 259 __cpp17_iterator_missing_members<_Tp> && 260 __iterator_traits_detail::__cpp17_input_iterator<_Tp>; 261 262 // Otherwise, `pointer` names `void`. 263 template<class> 264 struct __iterator_traits_member_pointer_or_arrow_or_void { using type = void; }; 265 266 // [iterator.traits]/3.2.1 267 // If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type. 268 template<__has_member_pointer _Ip> 269 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { using type = typename _Ip::pointer; }; 270 271 // Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that 272 // type. 273 template<class _Ip> 274 requires requires(_Ip& __i) { __i.operator->(); } && (!__has_member_pointer<_Ip>) 275 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { 276 using type = decltype(std::declval<_Ip&>().operator->()); 277 }; 278 279 // Otherwise, `reference` names `iter-reference-t<I>`. 280 template<class _Ip> 281 struct __iterator_traits_member_reference { using type = iter_reference_t<_Ip>; }; 282 283 // [iterator.traits]/3.2.2 284 // If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type. 285 template<__has_member_reference _Ip> 286 struct __iterator_traits_member_reference<_Ip> { using type = typename _Ip::reference; }; 287 288 // [iterator.traits]/3.2.3.4 289 // input_iterator_tag 290 template<class _Ip> 291 struct __deduce_iterator_category { 292 using type = input_iterator_tag; 293 }; 294 295 // [iterator.traits]/3.2.3.1 296 // `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise 297 template<__iterator_traits_detail::__cpp17_random_access_iterator _Ip> 298 struct __deduce_iterator_category<_Ip> { 299 using type = random_access_iterator_tag; 300 }; 301 302 // [iterator.traits]/3.2.3.2 303 // `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise 304 template<__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip> 305 struct __deduce_iterator_category<_Ip> { 306 using type = bidirectional_iterator_tag; 307 }; 308 309 // [iterator.traits]/3.2.3.3 310 // `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise 311 template<__iterator_traits_detail::__cpp17_forward_iterator _Ip> 312 struct __deduce_iterator_category<_Ip> { 313 using type = forward_iterator_tag; 314 }; 315 316 template<class _Ip> 317 struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {}; 318 319 // [iterator.traits]/3.2.3 320 // If the qualified-id `I::iterator-category` is valid and denotes a type, `iterator-category` names 321 // that type. 322 template<__has_member_iterator_category _Ip> 323 struct __iterator_traits_iterator_category<_Ip> { 324 using type = typename _Ip::iterator_category; 325 }; 326 327 // otherwise, it names void. 328 template<class> 329 struct __iterator_traits_difference_type { using type = void; }; 330 331 // If the qualified-id `incrementable_traits<I>::difference_type` is valid and denotes a type, then 332 // `difference_type` names that type; 333 template<class _Ip> 334 requires requires { typename incrementable_traits<_Ip>::difference_type; } 335 struct __iterator_traits_difference_type<_Ip> { 336 using type = typename incrementable_traits<_Ip>::difference_type; 337 }; 338 339 // [iterator.traits]/3.4 340 // Otherwise, `iterator_traits<I>` has no members by any of the above names. 341 template<class> 342 struct __iterator_traits {}; 343 344 // [iterator.traits]/3.1 345 // If `I` has valid ([temp.deduct]) member types `difference-type`, `value-type`, `reference`, and 346 // `iterator-category`, then `iterator-traits<I>` has the following publicly accessible members: 347 template<__specifies_members _Ip> 348 struct __iterator_traits<_Ip> { 349 using iterator_category = typename _Ip::iterator_category; 350 using value_type = typename _Ip::value_type; 351 using difference_type = typename _Ip::difference_type; 352 using pointer = typename __iterator_traits_member_pointer_or_void<_Ip>::type; 353 using reference = typename _Ip::reference; 354 }; 355 356 // [iterator.traits]/3.2 357 // Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`, 358 // `iterator-traits<I>` has the following publicly accessible members: 359 template<__cpp17_input_iterator_missing_members _Ip> 360 struct __iterator_traits<_Ip> { 361 using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type; 362 using value_type = typename indirectly_readable_traits<_Ip>::value_type; 363 using difference_type = typename incrementable_traits<_Ip>::difference_type; 364 using pointer = typename __iterator_traits_member_pointer_or_arrow_or_void<_Ip>::type; 365 using reference = typename __iterator_traits_member_reference<_Ip>::type; 366 }; 367 368 // Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then 369 // `iterator_traits<I>` has the following publicly accessible members: 370 template<__cpp17_iterator_missing_members _Ip> 371 struct __iterator_traits<_Ip> { 372 using iterator_category = output_iterator_tag; 373 using value_type = void; 374 using difference_type = typename __iterator_traits_difference_type<_Ip>::type; 375 using pointer = void; 376 using reference = void; 377 }; 378 379 template<class _Ip> 380 struct iterator_traits : __iterator_traits<_Ip> { 381 using __primary_template = iterator_traits; 382 }; 383 384 #else // _LIBCPP_STD_VER >= 20 385 386 template <class _Iter, bool> struct __iterator_traits {}; 387 388 template <class _Iter, bool> struct __iterator_traits_impl {}; 389 390 template <class _Iter> 391 struct __iterator_traits_impl<_Iter, true> 392 { 393 typedef typename _Iter::difference_type difference_type; 394 typedef typename _Iter::value_type value_type; 395 typedef typename _Iter::pointer pointer; 396 typedef typename _Iter::reference reference; 397 typedef typename _Iter::iterator_category iterator_category; 398 }; 399 400 template <class _Iter> 401 struct __iterator_traits<_Iter, true> 402 : __iterator_traits_impl 403 < 404 _Iter, 405 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value || 406 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value 407 > 408 {}; 409 410 // iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category 411 // exists. Else iterator_traits<Iterator> will be an empty class. This is a 412 // conforming extension which allows some programs to compile and behave as 413 // the client expects instead of failing at compile time. 414 415 template <class _Iter> 416 struct _LIBCPP_TEMPLATE_VIS iterator_traits 417 : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> { 418 419 using __primary_template = iterator_traits; 420 }; 421 #endif // _LIBCPP_STD_VER >= 20 422 423 template<class _Tp> 424 #if _LIBCPP_STD_VER >= 20 425 requires is_object_v<_Tp> 426 #endif 427 struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*> 428 { 429 typedef ptrdiff_t difference_type; 430 typedef __remove_cv_t<_Tp> value_type; 431 typedef _Tp* pointer; 432 typedef _Tp& reference; 433 typedef random_access_iterator_tag iterator_category; 434 #if _LIBCPP_STD_VER >= 20 435 typedef contiguous_iterator_tag iterator_concept; 436 #endif 437 }; 438 439 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value> 440 struct __has_iterator_category_convertible_to 441 : is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up> 442 {}; 443 444 template <class _Tp, class _Up> 445 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {}; 446 447 template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value> 448 struct __has_iterator_concept_convertible_to 449 : is_convertible<typename _Tp::iterator_concept, _Up> 450 {}; 451 452 template <class _Tp, class _Up> 453 struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {}; 454 455 template <class _Tp> 456 using __has_input_iterator_category = __has_iterator_category_convertible_to<_Tp, input_iterator_tag>; 457 458 template <class _Tp> 459 using __has_forward_iterator_category = __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>; 460 461 template <class _Tp> 462 using __has_bidirectional_iterator_category = __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>; 463 464 template <class _Tp> 465 using __has_random_access_iterator_category = __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>; 466 467 // __libcpp_is_contiguous_iterator determines if an iterator is known by 468 // libc++ to be contiguous, either because it advertises itself as such 469 // (in C++20) or because it is a pointer type or a known trivial wrapper 470 // around a (possibly fancy) pointer type, such as __wrap_iter<T*>. 471 // Such iterators receive special "contiguous" optimizations in 472 // std::copy and std::sort. 473 // 474 #if _LIBCPP_STD_VER >= 20 475 template <class _Tp> 476 struct __libcpp_is_contiguous_iterator : _Or< 477 __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>, 478 __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag> 479 > {}; 480 #else 481 template <class _Tp> 482 struct __libcpp_is_contiguous_iterator : false_type {}; 483 #endif 484 485 // Any native pointer which is an iterator is also a contiguous iterator. 486 template <class _Up> 487 struct __libcpp_is_contiguous_iterator<_Up*> : true_type {}; 488 489 490 template <class _Iter> 491 class __wrap_iter; 492 493 template <class _Tp> 494 using __has_exactly_input_iterator_category 495 = integral_constant<bool, 496 __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value && 497 !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value>; 498 499 template <class _Tp> 500 using __has_exactly_forward_iterator_category 501 = integral_constant<bool, 502 __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value && 503 !__has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value>; 504 505 template <class _Tp> 506 using __has_exactly_bidirectional_iterator_category 507 = integral_constant<bool, 508 __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value && 509 !__has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>::value>; 510 511 template<class _InputIterator> 512 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type; 513 514 template<class _InputIterator> 515 using __iter_key_type = __remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>; 516 517 template<class _InputIterator> 518 using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type; 519 520 template<class _InputIterator> 521 using __iter_to_alloc_type = pair< 522 typename add_const<typename iterator_traits<_InputIterator>::value_type::first_type>::type, 523 typename iterator_traits<_InputIterator>::value_type::second_type>; 524 525 template <class _Iter> 526 using __iterator_category_type = typename iterator_traits<_Iter>::iterator_category; 527 528 template <class _Iter> 529 using __iterator_pointer_type = typename iterator_traits<_Iter>::pointer; 530 531 template <class _Iter> 532 using __iter_diff_t = typename iterator_traits<_Iter>::difference_type; 533 534 template <class _Iter> 535 using __iter_reference = typename iterator_traits<_Iter>::reference; 536 537 #if _LIBCPP_STD_VER >= 20 538 539 // [readable.traits] 540 541 // Let `RI` be `remove_cvref_t<I>`. The type `iter_value_t<I>` denotes 542 // `indirectly_readable_traits<RI>::value_type` if `iterator_traits<RI>` names a specialization 543 // generated from the primary template, and `iterator_traits<RI>::value_type` otherwise. 544 // This has to be in this file and not readable_traits.h to break the include cycle between the two. 545 template <class _Ip> 546 using iter_value_t = typename conditional_t<__is_primary_template<iterator_traits<remove_cvref_t<_Ip> > >::value, 547 indirectly_readable_traits<remove_cvref_t<_Ip> >, 548 iterator_traits<remove_cvref_t<_Ip> > >::value_type; 549 550 #endif // _LIBCPP_STD_VER >= 20 551 552 _LIBCPP_END_NAMESPACE_STD 553 554 #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H 555