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_BEGIN_NAMESPACE_STD 24 25 #if _LIBCPP_STD_VER > 17 26 27 template <class _Tp> 28 using __with_reference = _Tp&; 29 30 template <class _Tp> 31 concept __can_reference = requires { 32 typename __with_reference<_Tp>; 33 }; 34 35 template <class _Tp> 36 concept __dereferenceable = requires(_Tp& __t) { 37 { *__t } -> __can_reference; // not required to be equality-preserving 38 }; 39 40 // [iterator.traits] 41 template<__dereferenceable _Tp> 42 using iter_reference_t = decltype(*declval<_Tp&>()); 43 44 #endif // _LIBCPP_STD_VER > 17 45 46 template <class _Iter> 47 struct _LIBCPP_TEMPLATE_VIS iterator_traits; 48 49 struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {}; 50 struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {}; 51 struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag {}; 52 struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {}; 53 struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {}; 54 #if _LIBCPP_STD_VER > 17 55 struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag : public random_access_iterator_tag {}; 56 #endif 57 58 template <class _Iter> 59 struct __iter_traits_cache { 60 using type = _If< 61 __is_primary_template<iterator_traits<_Iter> >::value, 62 _Iter, 63 iterator_traits<_Iter> 64 >; 65 }; 66 template <class _Iter> 67 using _ITER_TRAITS = typename __iter_traits_cache<_Iter>::type; 68 69 struct __iter_concept_concept_test { 70 template <class _Iter> 71 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_concept; 72 }; 73 struct __iter_concept_category_test { 74 template <class _Iter> 75 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_category; 76 }; 77 struct __iter_concept_random_fallback { 78 template <class _Iter> 79 using _Apply = __enable_if_t< 80 __is_primary_template<iterator_traits<_Iter> >::value, 81 random_access_iterator_tag 82 >; 83 }; 84 85 template <class _Iter, class _Tester> struct __test_iter_concept 86 : _IsValidExpansion<_Tester::template _Apply, _Iter>, 87 _Tester 88 { 89 }; 90 91 template <class _Iter> 92 struct __iter_concept_cache { 93 using type = _Or< 94 __test_iter_concept<_Iter, __iter_concept_concept_test>, 95 __test_iter_concept<_Iter, __iter_concept_category_test>, 96 __test_iter_concept<_Iter, __iter_concept_random_fallback> 97 >; 98 }; 99 100 template <class _Iter> 101 using _ITER_CONCEPT = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>; 102 103 104 template <class _Tp> 105 struct __has_iterator_typedefs 106 { 107 private: 108 struct __two {char __lx; char __lxx;}; 109 template <class _Up> static __two __test(...); 110 template <class _Up> static char __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 = sizeof(__test<_Tp>(0,0,0,0,0)) == 1; 117 }; 118 119 120 template <class _Tp> 121 struct __has_iterator_category 122 { 123 private: 124 struct __two {char __lx; char __lxx;}; 125 template <class _Up> static __two __test(...); 126 template <class _Up> static char __test(typename _Up::iterator_category* = nullptr); 127 public: 128 static const bool value = sizeof(__test<_Tp>(nullptr)) == 1; 129 }; 130 131 template <class _Tp> 132 struct __has_iterator_concept 133 { 134 private: 135 struct __two {char __lx; char __lxx;}; 136 template <class _Up> static __two __test(...); 137 template <class _Up> static char __test(typename _Up::iterator_concept* = nullptr); 138 public: 139 static const bool value = sizeof(__test<_Tp>(nullptr)) == 1; 140 }; 141 142 #if _LIBCPP_STD_VER > 17 143 144 // The `cpp17-*-iterator` exposition-only concepts have very similar names to the `Cpp17*Iterator` named requirements 145 // from `[iterator.cpp17]`. To avoid confusion between the two, the exposition-only concepts have been banished to 146 // a "detail" namespace indicating they have a niche use-case. 147 namespace __iterator_traits_detail { 148 template<class _Ip> 149 concept __cpp17_iterator = 150 requires(_Ip __i) { 151 { *__i } -> __can_reference; 152 { ++__i } -> same_as<_Ip&>; 153 { *__i++ } -> __can_reference; 154 } && 155 copyable<_Ip>; 156 157 template<class _Ip> 158 concept __cpp17_input_iterator = 159 __cpp17_iterator<_Ip> && 160 equality_comparable<_Ip> && 161 requires(_Ip __i) { 162 typename incrementable_traits<_Ip>::difference_type; 163 typename indirectly_readable_traits<_Ip>::value_type; 164 typename common_reference_t<iter_reference_t<_Ip>&&, 165 typename indirectly_readable_traits<_Ip>::value_type&>; 166 typename common_reference_t<decltype(*__i++)&&, 167 typename indirectly_readable_traits<_Ip>::value_type&>; 168 requires signed_integral<typename incrementable_traits<_Ip>::difference_type>; 169 }; 170 171 template<class _Ip> 172 concept __cpp17_forward_iterator = 173 __cpp17_input_iterator<_Ip> && 174 constructible_from<_Ip> && 175 is_lvalue_reference_v<iter_reference_t<_Ip>> && 176 same_as<remove_cvref_t<iter_reference_t<_Ip>>, 177 typename indirectly_readable_traits<_Ip>::value_type> && 178 requires(_Ip __i) { 179 { __i++ } -> convertible_to<_Ip const&>; 180 { *__i++ } -> same_as<iter_reference_t<_Ip>>; 181 }; 182 183 template<class _Ip> 184 concept __cpp17_bidirectional_iterator = 185 __cpp17_forward_iterator<_Ip> && 186 requires(_Ip __i) { 187 { --__i } -> same_as<_Ip&>; 188 { __i-- } -> convertible_to<_Ip const&>; 189 { *__i-- } -> same_as<iter_reference_t<_Ip>>; 190 }; 191 192 template<class _Ip> 193 concept __cpp17_random_access_iterator = 194 __cpp17_bidirectional_iterator<_Ip> && 195 totally_ordered<_Ip> && 196 requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) { 197 { __i += __n } -> same_as<_Ip&>; 198 { __i -= __n } -> same_as<_Ip&>; 199 { __i + __n } -> same_as<_Ip>; 200 { __n + __i } -> same_as<_Ip>; 201 { __i - __n } -> same_as<_Ip>; 202 { __i - __i } -> same_as<decltype(__n)>; // NOLINT(misc-redundant-expression) ; This is llvm.org/PR54114 203 { __i[__n] } -> convertible_to<iter_reference_t<_Ip>>; 204 }; 205 } // namespace __iterator_traits_detail 206 207 template<class _Ip> 208 concept __has_member_reference = requires { typename _Ip::reference; }; 209 210 template<class _Ip> 211 concept __has_member_pointer = requires { typename _Ip::pointer; }; 212 213 template<class _Ip> 214 concept __has_member_iterator_category = requires { typename _Ip::iterator_category; }; 215 216 template<class _Ip> 217 concept __specifies_members = requires { 218 typename _Ip::value_type; 219 typename _Ip::difference_type; 220 requires __has_member_reference<_Ip>; 221 requires __has_member_iterator_category<_Ip>; 222 }; 223 224 template<class> 225 struct __iterator_traits_member_pointer_or_void { 226 using type = void; 227 }; 228 229 template<__has_member_pointer _Tp> 230 struct __iterator_traits_member_pointer_or_void<_Tp> { 231 using type = typename _Tp::pointer; 232 }; 233 234 template<class _Tp> 235 concept __cpp17_iterator_missing_members = 236 !__specifies_members<_Tp> && 237 __iterator_traits_detail::__cpp17_iterator<_Tp>; 238 239 template<class _Tp> 240 concept __cpp17_input_iterator_missing_members = 241 __cpp17_iterator_missing_members<_Tp> && 242 __iterator_traits_detail::__cpp17_input_iterator<_Tp>; 243 244 // Otherwise, `pointer` names `void`. 245 template<class> 246 struct __iterator_traits_member_pointer_or_arrow_or_void { using type = void; }; 247 248 // [iterator.traits]/3.2.1 249 // If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type. 250 template<__has_member_pointer _Ip> 251 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { using type = typename _Ip::pointer; }; 252 253 // Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that 254 // type. 255 template<class _Ip> 256 requires requires(_Ip& __i) { __i.operator->(); } && (!__has_member_pointer<_Ip>) 257 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { 258 using type = decltype(declval<_Ip&>().operator->()); 259 }; 260 261 // Otherwise, `reference` names `iter-reference-t<I>`. 262 template<class _Ip> 263 struct __iterator_traits_member_reference { using type = iter_reference_t<_Ip>; }; 264 265 // [iterator.traits]/3.2.2 266 // If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type. 267 template<__has_member_reference _Ip> 268 struct __iterator_traits_member_reference<_Ip> { using type = typename _Ip::reference; }; 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 { using type = void; }; 312 313 // If the qualified-id `incrementable_traits<I>::difference_type` is valid and denotes a type, then 314 // `difference_type` names that type; 315 template<class _Ip> 316 requires requires { typename incrementable_traits<_Ip>::difference_type; } 317 struct __iterator_traits_difference_type<_Ip> { 318 using type = typename incrementable_traits<_Ip>::difference_type; 319 }; 320 321 // [iterator.traits]/3.4 322 // Otherwise, `iterator_traits<I>` has no members by any of the above names. 323 template<class> 324 struct __iterator_traits {}; 325 326 // [iterator.traits]/3.1 327 // If `I` has valid ([temp.deduct]) member types `difference-type`, `value-type`, `reference`, and 328 // `iterator-category`, then `iterator-traits<I>` has the following publicly accessible members: 329 template<__specifies_members _Ip> 330 struct __iterator_traits<_Ip> { 331 using iterator_category = typename _Ip::iterator_category; 332 using value_type = typename _Ip::value_type; 333 using difference_type = typename _Ip::difference_type; 334 using pointer = typename __iterator_traits_member_pointer_or_void<_Ip>::type; 335 using reference = typename _Ip::reference; 336 }; 337 338 // [iterator.traits]/3.2 339 // Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`, 340 // `iterator-traits<I>` has the following publicly accessible members: 341 template<__cpp17_input_iterator_missing_members _Ip> 342 struct __iterator_traits<_Ip> { 343 using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type; 344 using value_type = typename indirectly_readable_traits<_Ip>::value_type; 345 using difference_type = typename incrementable_traits<_Ip>::difference_type; 346 using pointer = typename __iterator_traits_member_pointer_or_arrow_or_void<_Ip>::type; 347 using reference = typename __iterator_traits_member_reference<_Ip>::type; 348 }; 349 350 // Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then 351 // `iterator_traits<I>` has the following publicly accessible members: 352 template<__cpp17_iterator_missing_members _Ip> 353 struct __iterator_traits<_Ip> { 354 using iterator_category = output_iterator_tag; 355 using value_type = void; 356 using difference_type = typename __iterator_traits_difference_type<_Ip>::type; 357 using pointer = void; 358 using reference = void; 359 }; 360 361 template<class _Ip> 362 struct iterator_traits : __iterator_traits<_Ip> { 363 using __primary_template = iterator_traits; 364 }; 365 366 #else // _LIBCPP_STD_VER > 17 367 368 template <class _Iter, bool> struct __iterator_traits {}; 369 370 template <class _Iter, bool> struct __iterator_traits_impl {}; 371 372 template <class _Iter> 373 struct __iterator_traits_impl<_Iter, true> 374 { 375 typedef typename _Iter::difference_type difference_type; 376 typedef typename _Iter::value_type value_type; 377 typedef typename _Iter::pointer pointer; 378 typedef typename _Iter::reference reference; 379 typedef typename _Iter::iterator_category iterator_category; 380 }; 381 382 template <class _Iter> 383 struct __iterator_traits<_Iter, true> 384 : __iterator_traits_impl 385 < 386 _Iter, 387 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value || 388 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value 389 > 390 {}; 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 399 : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> { 400 401 using __primary_template = iterator_traits; 402 }; 403 #endif // _LIBCPP_STD_VER > 17 404 405 template<class _Tp> 406 #if _LIBCPP_STD_VER > 17 407 requires is_object_v<_Tp> 408 #endif 409 struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*> 410 { 411 typedef ptrdiff_t difference_type; 412 typedef typename remove_cv<_Tp>::type value_type; 413 typedef _Tp* pointer; 414 typedef _Tp& reference; 415 typedef random_access_iterator_tag iterator_category; 416 #if _LIBCPP_STD_VER > 17 417 typedef contiguous_iterator_tag iterator_concept; 418 #endif 419 }; 420 421 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value> 422 struct __has_iterator_category_convertible_to 423 : is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up> 424 {}; 425 426 template <class _Tp, class _Up> 427 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {}; 428 429 template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value> 430 struct __has_iterator_concept_convertible_to 431 : is_convertible<typename _Tp::iterator_concept, _Up> 432 {}; 433 434 template <class _Tp, class _Up> 435 struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {}; 436 437 template <class _Tp> 438 struct __is_cpp17_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {}; 439 440 template <class _Tp> 441 struct __is_cpp17_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {}; 442 443 template <class _Tp> 444 struct __is_cpp17_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {}; 445 446 template <class _Tp> 447 struct __is_cpp17_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {}; 448 449 // __is_cpp17_contiguous_iterator determines if an iterator is known by 450 // libc++ to be contiguous, either because it advertises itself as such 451 // (in C++20) or because it is a pointer type or a known trivial wrapper 452 // around a (possibly fancy) pointer type, such as __wrap_iter<T*>. 453 // Such iterators receive special "contiguous" optimizations in 454 // std::copy and std::sort. 455 // 456 #if _LIBCPP_STD_VER > 17 457 template <class _Tp> 458 struct __is_cpp17_contiguous_iterator : _Or< 459 __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>, 460 __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag> 461 > {}; 462 #else 463 template <class _Tp> 464 struct __is_cpp17_contiguous_iterator : false_type {}; 465 #endif 466 467 // Any native pointer which is an iterator is also a contiguous iterator. 468 template <class _Up> 469 struct __is_cpp17_contiguous_iterator<_Up*> : true_type {}; 470 471 472 template <class _Tp> 473 struct __is_exactly_cpp17_input_iterator 474 : public 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 #if _LIBCPP_STD_VER >= 17 479 template<class _InputIterator> 480 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type; 481 482 template<class _InputIterator> 483 using __iter_key_type = remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>; 484 485 template<class _InputIterator> 486 using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type; 487 488 template<class _InputIterator> 489 using __iter_to_alloc_type = pair< 490 add_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>, 491 typename iterator_traits<_InputIterator>::value_type::second_type>; 492 #endif // _LIBCPP_STD_VER >= 17 493 494 _LIBCPP_END_NAMESPACE_STD 495 496 #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H 497