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 <__config> 14 #include <__iterator/incrementable_traits.h> 15 #include <__iterator/readable_traits.h> 16 #include <concepts> 17 #include <type_traits> 18 19 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 20 #pragma GCC system_header 21 #endif 22 23 _LIBCPP_PUSH_MACROS 24 #include <__undef_macros> 25 26 _LIBCPP_BEGIN_NAMESPACE_STD 27 28 #if !defined(_LIBCPP_HAS_NO_RANGES) 29 30 template <class _Tp> 31 using __with_reference = _Tp&; 32 33 template <class _Tp> 34 concept __referenceable = requires { 35 typename __with_reference<_Tp>; 36 }; 37 38 template <class _Tp> 39 concept __dereferenceable = requires(_Tp& __t) { 40 { *__t } -> __referenceable; // not required to be equality-preserving 41 }; 42 43 // [iterator.traits] 44 template<__dereferenceable _Tp> 45 using iter_reference_t = decltype(*declval<_Tp&>()); 46 47 #endif // !defined(_LIBCPP_HAS_NO_RANGES) 48 49 template <class _Iter> 50 struct _LIBCPP_TEMPLATE_VIS iterator_traits; 51 52 struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {}; 53 struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {}; 54 struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag {}; 55 struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {}; 56 struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {}; 57 #if _LIBCPP_STD_VER > 17 58 struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag : public random_access_iterator_tag {}; 59 #endif 60 61 template <class _Iter> 62 struct __iter_traits_cache { 63 using type = _If< 64 __is_primary_template<iterator_traits<_Iter> >::value, 65 _Iter, 66 iterator_traits<_Iter> 67 >; 68 }; 69 template <class _Iter> 70 using _ITER_TRAITS = typename __iter_traits_cache<_Iter>::type; 71 72 struct __iter_concept_concept_test { 73 template <class _Iter> 74 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_concept; 75 }; 76 struct __iter_concept_category_test { 77 template <class _Iter> 78 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_category; 79 }; 80 struct __iter_concept_random_fallback { 81 template <class _Iter> 82 using _Apply = _EnableIf< 83 __is_primary_template<iterator_traits<_Iter> >::value, 84 random_access_iterator_tag 85 >; 86 }; 87 88 template <class _Iter, class _Tester> struct __test_iter_concept 89 : _IsValidExpansion<_Tester::template _Apply, _Iter>, 90 _Tester 91 { 92 }; 93 94 template <class _Iter> 95 struct __iter_concept_cache { 96 using type = _Or< 97 __test_iter_concept<_Iter, __iter_concept_concept_test>, 98 __test_iter_concept<_Iter, __iter_concept_category_test>, 99 __test_iter_concept<_Iter, __iter_concept_random_fallback> 100 >; 101 }; 102 103 template <class _Iter> 104 using _ITER_CONCEPT = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>; 105 106 107 template <class _Tp> 108 struct __has_iterator_typedefs 109 { 110 private: 111 struct __two {char __lx; char __lxx;}; 112 template <class _Up> static __two __test(...); 113 template <class _Up> static char __test(typename __void_t<typename _Up::iterator_category>::type* = 0, 114 typename __void_t<typename _Up::difference_type>::type* = 0, 115 typename __void_t<typename _Up::value_type>::type* = 0, 116 typename __void_t<typename _Up::reference>::type* = 0, 117 typename __void_t<typename _Up::pointer>::type* = 0); 118 public: 119 static const bool value = sizeof(__test<_Tp>(0,0,0,0,0)) == 1; 120 }; 121 122 123 template <class _Tp> 124 struct __has_iterator_category 125 { 126 private: 127 struct __two {char __lx; char __lxx;}; 128 template <class _Up> static __two __test(...); 129 template <class _Up> static char __test(typename _Up::iterator_category* = nullptr); 130 public: 131 static const bool value = sizeof(__test<_Tp>(nullptr)) == 1; 132 }; 133 134 template <class _Tp> 135 struct __has_iterator_concept 136 { 137 private: 138 struct __two {char __lx; char __lxx;}; 139 template <class _Up> static __two __test(...); 140 template <class _Up> static char __test(typename _Up::iterator_concept* = nullptr); 141 public: 142 static const bool value = sizeof(__test<_Tp>(nullptr)) == 1; 143 }; 144 145 #if !defined(_LIBCPP_HAS_NO_RANGES) 146 147 // The `cpp17-*-iterator` exposition-only concepts are easily confused with the Cpp17*Iterator tables, 148 // so they've been banished to a namespace that makes it obvious they have a niche use-case. 149 namespace __iterator_traits_detail { 150 template<class _Ip> 151 concept __cpp17_iterator = 152 requires(_Ip __i) { 153 { *__i } -> __referenceable; 154 { ++__i } -> same_as<_Ip&>; 155 { *__i++ } -> __referenceable; 156 } && 157 copyable<_Ip>; 158 159 template<class _Ip> 160 concept __cpp17_input_iterator = 161 __cpp17_iterator<_Ip> && 162 equality_comparable<_Ip> && 163 requires(_Ip __i) { 164 typename incrementable_traits<_Ip>::difference_type; 165 typename indirectly_readable_traits<_Ip>::value_type; 166 typename common_reference_t<iter_reference_t<_Ip>&&, 167 typename indirectly_readable_traits<_Ip>::value_type&>; 168 typename common_reference_t<decltype(*__i++)&&, 169 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> && 176 constructible_from<_Ip> && 177 is_lvalue_reference_v<iter_reference_t<_Ip>> && 178 same_as<remove_cvref_t<iter_reference_t<_Ip>>, 179 typename indirectly_readable_traits<_Ip>::value_type> && 180 requires(_Ip __i) { 181 { __i++ } -> convertible_to<_Ip const&>; 182 { *__i++ } -> same_as<iter_reference_t<_Ip>>; 183 }; 184 185 template<class _Ip> 186 concept __cpp17_bidirectional_iterator = 187 __cpp17_forward_iterator<_Ip> && 188 requires(_Ip __i) { 189 { --__i } -> same_as<_Ip&>; 190 { __i-- } -> convertible_to<_Ip const&>; 191 { *__i-- } -> same_as<iter_reference_t<_Ip>>; 192 }; 193 194 template<class _Ip> 195 concept __cpp17_random_access_iterator = 196 __cpp17_bidirectional_iterator<_Ip> && 197 totally_ordered<_Ip> && 198 requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) { 199 { __i += __n } -> same_as<_Ip&>; 200 { __i -= __n } -> same_as<_Ip&>; 201 { __i + __n } -> same_as<_Ip>; 202 { __n + __i } -> same_as<_Ip>; 203 { __i - __n } -> same_as<_Ip>; 204 { __i - __i } -> same_as<decltype(__n)>; 205 { __i[__n] } -> convertible_to<iter_reference_t<_Ip>>; 206 }; 207 } // namespace __iterator_traits_detail 208 209 template<class _Ip> 210 concept __has_member_reference = requires { typename _Ip::reference; }; 211 212 template<class _Ip> 213 concept __has_member_pointer = requires { typename _Ip::pointer; }; 214 215 template<class _Ip> 216 concept __has_member_iterator_category = requires { typename _Ip::iterator_category; }; 217 218 template<class _Ip> 219 concept __specifies_members = requires { 220 typename _Ip::value_type; 221 typename _Ip::difference_type; 222 requires __has_member_reference<_Ip>; 223 requires __has_member_iterator_category<_Ip>; 224 }; 225 226 template<class> 227 struct __iterator_traits_member_pointer_or_void { 228 using type = void; 229 }; 230 231 template<__has_member_pointer _Tp> 232 struct __iterator_traits_member_pointer_or_void<_Tp> { 233 using type = typename _Tp::pointer; 234 }; 235 236 template<class _Tp> 237 concept __cpp17_iterator_missing_members = 238 !__specifies_members<_Tp> && 239 __iterator_traits_detail::__cpp17_iterator<_Tp>; 240 241 template<class _Tp> 242 concept __cpp17_input_iterator_missing_members = 243 __cpp17_iterator_missing_members<_Tp> && 244 __iterator_traits_detail::__cpp17_input_iterator<_Tp>; 245 246 // Otherwise, `pointer` names `void`. 247 template<class> 248 struct __iterator_traits_member_pointer_or_arrow_or_void { using type = void; }; 249 250 // [iterator.traits]/3.2.1 251 // If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type. 252 template<__has_member_pointer _Ip> 253 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { using type = typename _Ip::pointer; }; 254 255 // Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that 256 // type. 257 template<class _Ip> 258 requires requires(_Ip& __i) { __i.operator->(); } && (!__has_member_pointer<_Ip>) 259 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { 260 using type = decltype(declval<_Ip&>().operator->()); 261 }; 262 263 // Otherwise, `reference` names `iter-reference-t<I>`. 264 template<class _Ip> 265 struct __iterator_traits_member_reference { using type = iter_reference_t<_Ip>; }; 266 267 // [iterator.traits]/3.2.2 268 // If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type. 269 template<__has_member_reference _Ip> 270 struct __iterator_traits_member_reference<_Ip> { using type = typename _Ip::reference; }; 271 272 // [iterator.traits]/3.2.3.4 273 // input_iterator_tag 274 template<class _Ip> 275 struct __deduce_iterator_category { 276 using type = input_iterator_tag; 277 }; 278 279 // [iterator.traits]/3.2.3.1 280 // `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise 281 template<__iterator_traits_detail::__cpp17_random_access_iterator _Ip> 282 struct __deduce_iterator_category<_Ip> { 283 using type = random_access_iterator_tag; 284 }; 285 286 // [iterator.traits]/3.2.3.2 287 // `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise 288 template<__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip> 289 struct __deduce_iterator_category<_Ip> { 290 using type = bidirectional_iterator_tag; 291 }; 292 293 // [iterator.traits]/3.2.3.3 294 // `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise 295 template<__iterator_traits_detail::__cpp17_forward_iterator _Ip> 296 struct __deduce_iterator_category<_Ip> { 297 using type = forward_iterator_tag; 298 }; 299 300 template<class _Ip> 301 struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {}; 302 303 // [iterator.traits]/3.2.3 304 // If the qualified-id `I::iterator-category` is valid and denotes a type, `iterator-category` names 305 // that type. 306 template<__has_member_iterator_category _Ip> 307 struct __iterator_traits_iterator_category<_Ip> { 308 using type = typename _Ip::iterator_category; 309 }; 310 311 // otherwise, it names void. 312 template<class> 313 struct __iterator_traits_difference_type { using type = void; }; 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 // !defined(_LIBCPP_HAS_NO_RANGES) 369 370 template <class _Iter, bool> struct __iterator_traits {}; 371 372 template <class _Iter, bool> struct __iterator_traits_impl {}; 373 374 template <class _Iter> 375 struct __iterator_traits_impl<_Iter, true> 376 { 377 typedef typename _Iter::difference_type difference_type; 378 typedef typename _Iter::value_type value_type; 379 typedef typename _Iter::pointer pointer; 380 typedef typename _Iter::reference reference; 381 typedef typename _Iter::iterator_category iterator_category; 382 }; 383 384 template <class _Iter> 385 struct __iterator_traits<_Iter, true> 386 : __iterator_traits_impl 387 < 388 _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 {}; 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 401 : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> { 402 403 using __primary_template = iterator_traits; 404 }; 405 #endif // !defined(_LIBCPP_HAS_NO_RANGES) 406 407 template<class _Tp> 408 #if !defined(_LIBCPP_HAS_NO_RANGES) 409 requires is_object_v<_Tp> 410 #endif 411 struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*> 412 { 413 typedef ptrdiff_t difference_type; 414 typedef typename remove_cv<_Tp>::type value_type; 415 typedef _Tp* pointer; 416 typedef _Tp& reference; 417 typedef random_access_iterator_tag iterator_category; 418 #if _LIBCPP_STD_VER > 17 419 typedef contiguous_iterator_tag iterator_concept; 420 #endif 421 }; 422 423 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value> 424 struct __has_iterator_category_convertible_to 425 : is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up> 426 {}; 427 428 template <class _Tp, class _Up> 429 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {}; 430 431 template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value> 432 struct __has_iterator_concept_convertible_to 433 : is_convertible<typename _Tp::iterator_concept, _Up> 434 {}; 435 436 template <class _Tp, class _Up> 437 struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {}; 438 439 template <class _Tp> 440 struct __is_cpp17_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {}; 441 442 template <class _Tp> 443 struct __is_cpp17_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {}; 444 445 template <class _Tp> 446 struct __is_cpp17_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {}; 447 448 template <class _Tp> 449 struct __is_cpp17_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {}; 450 451 // __is_cpp17_contiguous_iterator determines if an iterator is known by 452 // libc++ to be contiguous, either because it advertises itself as such 453 // (in C++20) or because it is a pointer type or a known trivial wrapper 454 // around a (possibly fancy) pointer type, such as __wrap_iter<T*>. 455 // Such iterators receive special "contiguous" optimizations in 456 // std::copy and std::sort. 457 // 458 #if _LIBCPP_STD_VER > 17 459 template <class _Tp> 460 struct __is_cpp17_contiguous_iterator : _Or< 461 __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>, 462 __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag> 463 > {}; 464 #else 465 template <class _Tp> 466 struct __is_cpp17_contiguous_iterator : false_type {}; 467 #endif 468 469 // Any native pointer which is an iterator is also a contiguous iterator. 470 template <class _Up> 471 struct __is_cpp17_contiguous_iterator<_Up*> : true_type {}; 472 473 474 template <class _Tp> 475 struct __is_exactly_cpp17_input_iterator 476 : public integral_constant<bool, 477 __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value && 478 !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {}; 479 480 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 481 template<class _InputIterator> 482 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type; 483 484 template<class _InputIterator> 485 using __iter_key_type = remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>; 486 487 template<class _InputIterator> 488 using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type; 489 490 template<class _InputIterator> 491 using __iter_to_alloc_type = pair< 492 add_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>, 493 typename iterator_traits<_InputIterator>::value_type::second_type>; 494 #endif // _LIBCPP_HAS_NO_DEDUCTION_GUIDES 495 496 _LIBCPP_END_NAMESPACE_STD 497 498 _LIBCPP_POP_MACROS 499 500 #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H 501