libcxx/include/__iterator/iterator_traits.h

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