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