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