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 <concepts> 15 #include <__iterator/incrementable_traits.h> 16 #include <__iterator/readable_traits.h> 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 // [iterator.traits] 31 template<__dereferenceable _Tp> 32 using iter_reference_t = decltype(*declval<_Tp&>()); 33 #endif // !defined(_LIBCPP_HAS_NO_RANGES) 34 35 template <class _Iter> 36 struct _LIBCPP_TEMPLATE_VIS iterator_traits; 37 38 struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {}; 39 struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {}; 40 struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag {}; 41 struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {}; 42 struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {}; 43 #if _LIBCPP_STD_VER > 17 44 struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag : public random_access_iterator_tag {}; 45 #endif 46 47 template <class _Iter> 48 struct __iter_traits_cache { 49 using type = _If< 50 __is_primary_template<iterator_traits<_Iter> >::value, 51 _Iter, 52 iterator_traits<_Iter> 53 >; 54 }; 55 template <class _Iter> 56 using _ITER_TRAITS = typename __iter_traits_cache<_Iter>::type; 57 58 struct __iter_concept_concept_test { 59 template <class _Iter> 60 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_concept; 61 }; 62 struct __iter_concept_category_test { 63 template <class _Iter> 64 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_category; 65 }; 66 struct __iter_concept_random_fallback { 67 template <class _Iter> 68 using _Apply = _EnableIf< 69 __is_primary_template<iterator_traits<_Iter> >::value, 70 random_access_iterator_tag 71 >; 72 }; 73 74 template <class _Iter, class _Tester> struct __test_iter_concept 75 : _IsValidExpansion<_Tester::template _Apply, _Iter>, 76 _Tester 77 { 78 }; 79 80 template <class _Iter> 81 struct __iter_concept_cache { 82 using type = _Or< 83 __test_iter_concept<_Iter, __iter_concept_concept_test>, 84 __test_iter_concept<_Iter, __iter_concept_category_test>, 85 __test_iter_concept<_Iter, __iter_concept_random_fallback> 86 >; 87 }; 88 89 template <class _Iter> 90 using _ITER_CONCEPT = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>; 91 92 93 template <class _Tp> 94 struct __has_iterator_typedefs 95 { 96 private: 97 struct __two {char __lx; char __lxx;}; 98 template <class _Up> static __two __test(...); 99 template <class _Up> static char __test(typename __void_t<typename _Up::iterator_category>::type* = 0, 100 typename __void_t<typename _Up::difference_type>::type* = 0, 101 typename __void_t<typename _Up::value_type>::type* = 0, 102 typename __void_t<typename _Up::reference>::type* = 0, 103 typename __void_t<typename _Up::pointer>::type* = 0); 104 public: 105 static const bool value = sizeof(__test<_Tp>(0,0,0,0,0)) == 1; 106 }; 107 108 109 template <class _Tp> 110 struct __has_iterator_category 111 { 112 private: 113 struct __two {char __lx; char __lxx;}; 114 template <class _Up> static __two __test(...); 115 template <class _Up> static char __test(typename _Up::iterator_category* = nullptr); 116 public: 117 static const bool value = sizeof(__test<_Tp>(nullptr)) == 1; 118 }; 119 120 template <class _Tp> 121 struct __has_iterator_concept 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_concept* = nullptr); 127 public: 128 static const bool value = sizeof(__test<_Tp>(nullptr)) == 1; 129 }; 130 131 #if !defined(_LIBCPP_HAS_NO_RANGES) 132 133 // The `cpp17-*-iterator` exposition-only concepts are easily confused with the Cpp17*Iterator tables, 134 // so they've been banished to a namespace that makes it obvious they have a niche use-case. 135 namespace __iterator_traits_detail { 136 template<class _Ip> 137 concept __cpp17_iterator = 138 requires(_Ip __i) { 139 { *__i } -> __referenceable; 140 { ++__i } -> same_as<_Ip&>; 141 { *__i++ } -> __referenceable; 142 } && 143 copyable<_Ip>; 144 145 template<class _Ip> 146 concept __cpp17_input_iterator = 147 __cpp17_iterator<_Ip> && 148 equality_comparable<_Ip> && 149 requires(_Ip __i) { 150 typename incrementable_traits<_Ip>::difference_type; 151 typename indirectly_readable_traits<_Ip>::value_type; 152 typename common_reference_t<iter_reference_t<_Ip>&&, 153 typename indirectly_readable_traits<_Ip>::value_type&>; 154 typename common_reference_t<decltype(*__i++)&&, 155 typename indirectly_readable_traits<_Ip>::value_type&>; 156 requires signed_integral<typename incrementable_traits<_Ip>::difference_type>; 157 }; 158 159 template<class _Ip> 160 concept __cpp17_forward_iterator = 161 __cpp17_input_iterator<_Ip> && 162 constructible_from<_Ip> && 163 is_lvalue_reference_v<iter_reference_t<_Ip>> && 164 same_as<remove_cvref_t<iter_reference_t<_Ip>>, 165 typename indirectly_readable_traits<_Ip>::value_type> && 166 requires(_Ip __i) { 167 { __i++ } -> convertible_to<_Ip const&>; 168 { *__i++ } -> same_as<iter_reference_t<_Ip>>; 169 }; 170 171 template<class _Ip> 172 concept __cpp17_bidirectional_iterator = 173 __cpp17_forward_iterator<_Ip> && 174 requires(_Ip __i) { 175 { --__i } -> same_as<_Ip&>; 176 { __i-- } -> convertible_to<_Ip const&>; 177 { *__i-- } -> same_as<iter_reference_t<_Ip>>; 178 }; 179 180 template<class _Ip> 181 concept __cpp17_random_access_iterator = 182 __cpp17_bidirectional_iterator<_Ip> and 183 totally_ordered<_Ip> and 184 requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) { 185 { __i += __n } -> same_as<_Ip&>; 186 { __i -= __n } -> same_as<_Ip&>; 187 { __i + __n } -> same_as<_Ip>; 188 { __n + __i } -> same_as<_Ip>; 189 { __i - __n } -> same_as<_Ip>; 190 { __i - __i } -> same_as<decltype(__n)>; 191 { __i[__n] } -> convertible_to<iter_reference_t<_Ip>>; 192 }; 193 } // namespace __iterator_traits_detail 194 195 template<class _Ip> 196 concept __has_member_reference = requires { typename _Ip::reference; }; 197 198 template<class _Ip> 199 concept __has_member_pointer = requires { typename _Ip::pointer; }; 200 201 template<class _Ip> 202 concept __has_member_iterator_category = requires { typename _Ip::iterator_category; }; 203 204 template<class _Ip> 205 concept __specifies_members = requires { 206 typename _Ip::value_type; 207 typename _Ip::difference_type; 208 requires __has_member_reference<_Ip>; 209 requires __has_member_iterator_category<_Ip>; 210 }; 211 212 template<class> 213 struct __iterator_traits_member_pointer_or_void { 214 using type = void; 215 }; 216 217 template<__has_member_pointer _Tp> 218 struct __iterator_traits_member_pointer_or_void<_Tp> { 219 using type = typename _Tp::pointer; 220 }; 221 222 template<class _Tp> 223 concept __cpp17_iterator_missing_members = 224 !__specifies_members<_Tp> && 225 __iterator_traits_detail::__cpp17_iterator<_Tp>; 226 227 template<class _Tp> 228 concept __cpp17_input_iterator_missing_members = 229 __cpp17_iterator_missing_members<_Tp> && 230 __iterator_traits_detail::__cpp17_input_iterator<_Tp>; 231 232 // Otherwise, `pointer` names `void`. 233 template<class> 234 struct __iterator_traits_member_pointer_or_arrow_or_void { using type = void; }; 235 236 // [iterator.traits]/3.2.1 237 // If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type. 238 template<__has_member_pointer _Ip> 239 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { using type = typename _Ip::pointer; }; 240 241 // Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that 242 // type. 243 template<class _Ip> 244 concept __has_arrow = 245 requires(_Ip& __i) { 246 __i.operator->(); 247 }; 248 249 template<class _Ip> 250 requires __has_arrow<_Ip> && (!__has_member_pointer<_Ip>) 251 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { 252 using type = decltype(declval<_Ip&>().operator->()); 253 }; 254 255 // Otherwise, `reference` names `iter-reference-t<I>`. 256 template<class _Ip> 257 struct __iterator_traits_member_reference { using type = iter_reference_t<_Ip>; }; 258 259 // [iterator.traits]/3.2.2 260 // If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type. 261 template<__has_member_reference _Ip> 262 struct __iterator_traits_member_reference<_Ip> { using type = typename _Ip::reference; }; 263 264 // [iterator.traits]/3.2.3.4 265 // input_iterator_tag 266 template<class _Ip> 267 struct __deduce_iterator_category { 268 using type = input_iterator_tag; 269 }; 270 271 // [iterator.traits]/3.2.3.1 272 // `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise 273 template<__iterator_traits_detail::__cpp17_random_access_iterator _Ip> 274 struct __deduce_iterator_category<_Ip> { 275 using type = random_access_iterator_tag; 276 }; 277 278 // [iterator.traits]/3.2.3.2 279 // `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise 280 template<__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip> 281 struct __deduce_iterator_category<_Ip> { 282 using type = bidirectional_iterator_tag; 283 }; 284 285 // [iterator.traits]/3.2.3.3 286 // `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise 287 template<__iterator_traits_detail::__cpp17_forward_iterator _Ip> 288 struct __deduce_iterator_category<_Ip> { 289 using type = forward_iterator_tag; 290 }; 291 292 template<class _Ip> 293 struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {}; 294 295 // [iterator.traits]/3.2.3 296 // If the qualified-id `I::iterator-category` is valid and denotes a type, `iterator-category` names 297 // that type. 298 template<__has_member_iterator_category _Ip> 299 struct __iterator_traits_iterator_category<_Ip> { 300 using type = typename _Ip::iterator_category; 301 }; 302 303 // otherwise, it names void. 304 template<class> 305 struct __iterator_traits_difference_type { using type = void; }; 306 307 // If the qualified-id `incrementable_traits<I>::difference_type` is valid and denotes a type, then 308 // `difference_type` names that type; 309 template<class _Ip> 310 requires requires { typename incrementable_traits<_Ip>::difference_type; } 311 struct __iterator_traits_difference_type<_Ip> { 312 using type = typename incrementable_traits<_Ip>::difference_type; 313 }; 314 315 // [iterator.traits]/3.4 316 // Otherwise, `iterator_traits<I>` has no members by any of the above names. 317 template<class> 318 struct __iterator_traits {}; 319 320 // [iterator.traits]/3.1 321 // If `I` has valid ([temp.deduct]) member types `difference-type`, `value-type`, `reference`, and 322 // `iterator-category`, then `iterator-traits<I>` has the following publicly accessible members: 323 template<__specifies_members _Ip> 324 struct __iterator_traits<_Ip> { 325 using iterator_category = typename _Ip::iterator_category; 326 using value_type = typename _Ip::value_type; 327 using difference_type = typename _Ip::difference_type; 328 using pointer = typename __iterator_traits_member_pointer_or_void<_Ip>::type; 329 using reference = typename _Ip::reference; 330 }; 331 332 // [iterator.traits]/3.2 333 // Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`, 334 // `iterator-traits<I>` has the following publicly accessible members: 335 template<__cpp17_input_iterator_missing_members _Ip> 336 struct __iterator_traits<_Ip> { 337 using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type; 338 using value_type = typename indirectly_readable_traits<_Ip>::value_type; 339 using difference_type = typename incrementable_traits<_Ip>::difference_type; 340 using pointer = typename __iterator_traits_member_pointer_or_arrow_or_void<_Ip>::type; 341 using reference = typename __iterator_traits_member_reference<_Ip>::type; 342 }; 343 344 // Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then 345 // `iterator_traits<I>` has the following publicly accessible members: 346 template<__cpp17_iterator_missing_members _Ip> 347 struct __iterator_traits<_Ip> { 348 using iterator_category = output_iterator_tag; 349 using value_type = void; 350 using difference_type = typename __iterator_traits_difference_type<_Ip>::type; 351 using pointer = void; 352 using reference = void; 353 }; 354 355 template<class _Ip> 356 struct iterator_traits : __iterator_traits<_Ip> { 357 using __primary_template = iterator_traits; 358 }; 359 360 #else // !defined(_LIBCPP_HAS_NO_RANGES) 361 362 template <class _Iter, bool> struct __iterator_traits {}; 363 364 template <class _Iter, bool> struct __iterator_traits_impl {}; 365 366 template <class _Iter> 367 struct __iterator_traits_impl<_Iter, true> 368 { 369 typedef typename _Iter::difference_type difference_type; 370 typedef typename _Iter::value_type value_type; 371 typedef typename _Iter::pointer pointer; 372 typedef typename _Iter::reference reference; 373 typedef typename _Iter::iterator_category iterator_category; 374 }; 375 376 template <class _Iter> 377 struct __iterator_traits<_Iter, true> 378 : __iterator_traits_impl 379 < 380 _Iter, 381 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value || 382 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value 383 > 384 {}; 385 386 // iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category 387 // exists. Else iterator_traits<Iterator> will be an empty class. This is a 388 // conforming extension which allows some programs to compile and behave as 389 // the client expects instead of failing at compile time. 390 391 template <class _Iter> 392 struct _LIBCPP_TEMPLATE_VIS iterator_traits 393 : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> { 394 395 using __primary_template = iterator_traits; 396 }; 397 #endif // !defined(_LIBCPP_HAS_NO_RANGES) 398 399 template<class _Tp> 400 #if !defined(_LIBCPP_HAS_NO_RANGES) 401 requires is_object_v<_Tp> 402 #endif 403 struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*> 404 { 405 typedef ptrdiff_t difference_type; 406 typedef typename remove_cv<_Tp>::type value_type; 407 typedef _Tp* pointer; 408 typedef _Tp& reference; 409 typedef random_access_iterator_tag iterator_category; 410 #if _LIBCPP_STD_VER > 17 411 typedef contiguous_iterator_tag iterator_concept; 412 #endif 413 }; 414 415 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value> 416 struct __has_iterator_category_convertible_to 417 : _BoolConstant<is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value> 418 {}; 419 420 template <class _Tp, class _Up> 421 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {}; 422 423 template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value> 424 struct __has_iterator_concept_convertible_to 425 : _BoolConstant<is_convertible<typename _Tp::iterator_concept, _Up>::value> 426 {}; 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 struct __is_cpp17_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {}; 433 434 template <class _Tp> 435 struct __is_cpp17_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {}; 436 437 template <class _Tp> 438 struct __is_cpp17_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {}; 439 440 template <class _Tp> 441 struct __is_cpp17_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {}; 442 443 // __is_cpp17_contiguous_iterator determines if an iterator is contiguous, 444 // either because it advertises itself as such (in C++20) or because it 445 // is a pointer type or a known trivial wrapper around a pointer type, 446 // such as __wrap_iter<T*>. 447 // 448 #if _LIBCPP_STD_VER > 17 449 template <class _Tp> 450 struct __is_cpp17_contiguous_iterator : _Or< 451 __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>, 452 __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag> 453 > {}; 454 #else 455 template <class _Tp> 456 struct __is_cpp17_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 __is_cpp17_contiguous_iterator<_Up*> : true_type {}; 462 463 464 template <class _Tp> 465 struct __is_exactly_cpp17_input_iterator 466 : public integral_constant<bool, 467 __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value && 468 !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {}; 469 470 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 471 template<class _InputIterator> 472 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type; 473 474 template<class _InputIterator> 475 using __iter_key_type = remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>; 476 477 template<class _InputIterator> 478 using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type; 479 480 template<class _InputIterator> 481 using __iter_to_alloc_type = pair< 482 add_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>, 483 typename iterator_traits<_InputIterator>::value_type::second_type>; 484 #endif // _LIBCPP_HAS_NO_DEDUCTION_GUIDES 485 486 _LIBCPP_END_NAMESPACE_STD 487 488 _LIBCPP_POP_MACROS 489 490 #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H 491