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