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