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