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