ceph/src/boost/boost/stl_interfaces/iterator_interface.hpp

   1 // Copyright (C) 2019 T. Zachary Laine
   2 //
   3 // Distributed under the Boost Software License, Version 1.0. (See
   4 // accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6 #ifndef BOOST_STL_INTERFACES_ITERATOR_INTERFACE_HPP
   7 #define BOOST_STL_INTERFACES_ITERATOR_INTERFACE_HPP
   8
   9 #include <boost/stl_interfaces/fwd.hpp>
  10
  11 #include <utility>
  12 #include <type_traits>
  13 #if defined(__cpp_lib_three_way_comparison)
  14 #include <compare>
  15 #endif
  16
  17
  18 namespace boost { namespace stl_interfaces {
  19
  20     /** A type for granting access to the private members of an iterator
  21         derived from `iterator_interface`. */
  22     struct access
  23     {
  24 #ifndef BOOST_STL_INTERFACES_DOXYGEN
  25
  26         template<typename D>
  27         static constexpr auto base(D & d) noexcept
  28             -> decltype(d.base_reference())
  29         {
  30             return d.base_reference();
  31         }
  32         template<typename D>
  33         static constexpr auto base(D const & d) noexcept
  34             -> decltype(d.base_reference())
  35         {
  36             return d.base_reference();
  37         }
  38
  39 #endif
  40     };
  41
  42     /** The return type of `operator->()` in a proxy iterator.
  43
  44         This template is used as the default `Pointer` template parameter in
  45         the `proxy_iterator_interface` template alias.  Note that the use of
  46         this template implies a copy or move of the underlying object of type
  47         `T`. */
  48     template<typename T>
  49     struct proxy_arrow_result
  50     {
  51         constexpr proxy_arrow_result(T const & value) noexcept(
  52             noexcept(T(value))) :
  53             value_(value)
  54         {}
  55         constexpr proxy_arrow_result(T && value) noexcept(
  56             noexcept(T(std::move(value)))) :
  57             value_(std::move(value))
  58         {}
  59
  60         constexpr T const * operator->() const noexcept { return &value_; }
  61         constexpr T * operator->() noexcept { return &value_; }
  62
  63     private:
  64         T value_;
  65     };
  66
  67     namespace detail {
  68         template<typename Pointer, typename T>
  69         auto make_pointer(
  70             T && value,
  71             std::enable_if_t<std::is_pointer<Pointer>::value, int> = 0)
  72             -> decltype(std::addressof(value))
  73         {
  74             return std::addressof(value);
  75         }
  76
  77         template<typename Pointer, typename T>
  78         auto make_pointer(
  79             T && value,
  80             std::enable_if_t<!std::is_pointer<Pointer>::value, int> = 0)
  81         {
  82             return Pointer(std::forward<T>(value));
  83         }
  84
  85         template<typename IteratorConcept>
  86         struct concept_category
  87         {
  88             using type = IteratorConcept;
  89         };
  90         template<typename IteratorConcept>
  91         using concept_category_t =
  92             typename concept_category<IteratorConcept>::type;
  93
  94         template<typename Pointer, typename IteratorConcept>
  95         struct pointer
  96         {
  97             using type = Pointer;
  98         };
  99         template<typename Pointer>
 100         struct pointer<Pointer, std::output_iterator_tag>
 101         {
 102             using type = void;
 103         };
 104         template<typename Pointer, typename IteratorConcept>
 105         using pointer_t = typename pointer<Pointer, IteratorConcept>::type;
 106
 107         template<typename T, typename U>
 108         using interoperable = std::integral_constant<
 109             bool,
 110             (std::is_convertible<T, U>::value ||
 111              std::is_convertible<U, T>::value)>;
 112
 113         template<typename T, typename U>
 114         using common_t =
 115             std::conditional_t<std::is_convertible<T, U>::value, U, T>;
 116
 117         template<typename T>
 118         using use_base = decltype(access::base(std::declval<T &>()));
 119
 120         template<typename... T>
 121         using void_t = void;
 122
 123         template<
 124             typename AlwaysVoid,
 125             template<class...> class Template,
 126             typename... Args>
 127         struct detector : std::false_type
 128         {
 129         };
 130
 131         template<template<class...> class Template, typename... Args>
 132         struct detector<void_t<Template<Args...>>, Template, Args...>
 133             : std::true_type
 134         {
 135         };
 136
 137         template<
 138             typename T,
 139             typename U,
 140             bool UseBase = detector<void, use_base, T>::value>
 141         struct common_eq
 142         {
 143             static constexpr auto call(T lhs, U rhs)
 144             {
 145                 return static_cast<common_t<T, U>>(lhs).derived() ==
 146                        static_cast<common_t<T, U>>(rhs).derived();
 147             }
 148         };
 149         template<typename T, typename U>
 150         struct common_eq<T, U, true>
 151         {
 152             static constexpr auto call(T lhs, U rhs)
 153             {
 154                 return access::base(lhs) == access::base(rhs);
 155             }
 156         };
 157
 158         template<typename T, typename U>
 159         constexpr auto common_diff(T lhs, U rhs) noexcept(noexcept(
 160             static_cast<common_t<T, U>>(lhs) -
 161             static_cast<common_t<T, U>>(rhs)))
 162             -> decltype(
 163                 static_cast<common_t<T, U>>(lhs) -
 164                 static_cast<common_t<T, U>>(rhs))
 165         {
 166             return static_cast<common_t<T, U>>(lhs) -
 167                    static_cast<common_t<T, U>>(rhs);
 168         }
 169     }
 170
 171 }}
 172
 173 namespace boost { namespace stl_interfaces { inline namespace v1 {
 174
 175     /** A CRTP template that one may derive from to make defining iterators
 176         easier.
 177
 178         The template parameter `D` for `iterator_interface` may be an
 179         incomplete type.  Before any member of the resulting specialization of
 180         `iterator_interface` other than special member functions is
 181         referenced, `D` shall be complete, and model
 182         `std::derived_from<iterator_interface<D>>`. */
 183     template<
 184         typename Derived,
 185         typename IteratorConcept,
 186         typename ValueType,
 187         typename Reference = ValueType &,
 188         typename Pointer = ValueType *,
 189         typename DifferenceType = std::ptrdiff_t
 190 #ifndef BOOST_STL_INTERFACES_DOXYGEN
 191         ,
 192         typename E = std::enable_if_t<
 193             std::is_class<Derived>::value &&
 194             std::is_same<Derived, std::remove_cv_t<Derived>>::value>
 195 #endif
 196         >
 197     struct iterator_interface;
 198
 199     namespace v1_dtl {
 200         template<typename Iterator, typename = void>
 201         struct ra_iter : std::false_type
 202         {
 203         };
 204         template<typename Iterator>
 205         struct ra_iter<Iterator, void_t<typename Iterator::iterator_concept>>
 206             : std::integral_constant<
 207                   bool,
 208                   std::is_base_of<
 209                       std::random_access_iterator_tag,
 210                       typename Iterator::iterator_concept>::value>
 211         {
 212         };
 213
 214         template<typename Iterator, typename DifferenceType, typename = void>
 215         struct plus_eq : std::false_type
 216         {
 217         };
 218         template<typename Iterator, typename DifferenceType>
 219         struct plus_eq<
 220             Iterator,
 221             DifferenceType,
 222             void_t<decltype(
 223                 std::declval<Iterator &>() += std::declval<DifferenceType>())>>
 224             : std::true_type
 225         {
 226         };
 227
 228         template<
 229             typename D,
 230             typename IteratorConcept,
 231             typename ValueType,
 232             typename Reference,
 233             typename Pointer,
 234             typename DifferenceType>
 235         void derived_iterator(iterator_interface<
 236                               D,
 237                               IteratorConcept,
 238                               ValueType,
 239                               Reference,
 240                               Pointer,
 241                               DifferenceType> const &);
 242     }
 243
 244     template<
 245         typename Derived,
 246         typename IteratorConcept,
 247         typename ValueType,
 248         typename Reference,
 249         typename Pointer,
 250         typename DifferenceType
 251 #ifndef BOOST_STL_INTERFACES_DOXYGEN
 252         ,
 253         typename E
 254 #endif
 255         >
 256     struct iterator_interface
 257     {
 258 #ifndef BOOST_STL_INTERFACES_DOXYGEN
 259     private:
 260         constexpr Derived & derived() noexcept
 261         {
 262             return static_cast<Derived &>(*this);
 263         }
 264         constexpr Derived const & derived() const noexcept
 265         {
 266             return static_cast<Derived const &>(*this);
 267         }
 268
 269         template<typename T, typename U, bool UseBase>
 270         friend struct detail::common_eq;
 271 #endif
 272
 273     public:
 274         using iterator_concept = IteratorConcept;
 275         using iterator_category = detail::concept_category_t<iterator_concept>;
 276         using value_type = std::remove_const_t<ValueType>;
 277         using reference = Reference;
 278         using pointer = detail::pointer_t<Pointer, iterator_concept>;
 279         using difference_type = DifferenceType;
 280
 281         template<typename D = Derived>
 282         constexpr auto operator*() const
 283             noexcept(noexcept(*access::base(std::declval<D const &>())))
 284                 -> decltype(*access::base(std::declval<D const &>()))
 285         {
 286             return *access::base(derived());
 287         }
 288
 289         template<typename D = Derived>
 290         constexpr auto operator-> () const noexcept(
 291             noexcept(detail::make_pointer<pointer>(*std::declval<D const &>())))
 292             -> decltype(
 293                 detail::make_pointer<pointer>(*std::declval<D const &>()))
 294         {
 295             return detail::make_pointer<pointer>(*derived());
 296         }
 297
 298         template<typename D = Derived>
 299         constexpr auto operator[](difference_type i) const noexcept(noexcept(
 300             D(std::declval<D const &>()),
 301             std::declval<D &>() += i,
 302             *std::declval<D &>()))
 303             -> decltype(std::declval<D &>() += i, *std::declval<D &>())
 304         {
 305             D retval = derived();
 306             retval += i;
 307             return *retval;
 308         }
 309
 310         template<
 311             typename D = Derived,
 312             typename Enable =
 313                 std::enable_if_t<!v1_dtl::plus_eq<D, difference_type>::value>>
 314         constexpr auto
 315         operator++() noexcept(noexcept(++access::base(std::declval<D &>())))
 316             -> decltype(++access::base(std::declval<D &>()))
 317         {
 318             return ++access::base(derived());
 319         }
 320
 321         template<typename D = Derived>
 322         constexpr auto operator++() noexcept(
 323             noexcept(std::declval<D &>() += difference_type(1)))
 324             -> decltype(
 325                 std::declval<D &>() += difference_type(1), std::declval<D &>())
 326         {
 327             derived() += difference_type(1);
 328             return derived();
 329         }
 330         template<typename D = Derived>
 331         constexpr auto operator++(int)noexcept(
 332             noexcept(D(std::declval<D &>()), ++std::declval<D &>()))
 333             -> std::remove_reference_t<decltype(
 334                 D(std::declval<D &>()),
 335                 ++std::declval<D &>(),
 336                 std::declval<D &>())>
 337         {
 338             D retval = derived();
 339             ++derived();
 340             return retval;
 341         }
 342
 343         template<typename D = Derived>
 344         constexpr auto operator+=(difference_type n) noexcept(
 345             noexcept(access::base(std::declval<D &>()) += n))
 346             -> decltype(access::base(std::declval<D &>()) += n)
 347         {
 348             return access::base(derived()) += n;
 349         }
 350
 351         template<typename D = Derived>
 352         constexpr auto operator+(difference_type i) const
 353             noexcept(noexcept(D(std::declval<D &>()), std::declval<D &>() += i))
 354                 -> std::remove_reference_t<decltype(
 355                     D(std::declval<D &>()),
 356                     std::declval<D &>() += i,
 357                     std::declval<D &>())>
 358         {
 359             D retval = derived();
 360             retval += i;
 361             return retval;
 362         }
 363         friend BOOST_STL_INTERFACES_HIDDEN_FRIEND_CONSTEXPR Derived
 364         operator+(difference_type i, Derived it) noexcept
 365         {
 366             return it + i;
 367         }
 368
 369         template<
 370             typename D = Derived,
 371             typename Enable =
 372                 std::enable_if_t<!v1_dtl::plus_eq<D, difference_type>::value>>
 373         constexpr auto
 374         operator--() noexcept(noexcept(--access::base(std::declval<D &>())))
 375             -> decltype(--access::base(std::declval<D &>()))
 376         {
 377             return --access::base(derived());
 378         }
 379
 380         template<typename D = Derived>
 381         constexpr auto operator--() noexcept(noexcept(
 382             D(std::declval<D &>()), std::declval<D &>() += -difference_type(1)))
 383             -> decltype(
 384                 std::declval<D &>() += -difference_type(1), std::declval<D &>())
 385         {
 386             derived() += -difference_type(1);
 387             return derived();
 388         }
 389         template<typename D = Derived>
 390         constexpr auto operator--(int)noexcept(
 391             noexcept(D(std::declval<D &>()), --std::declval<D &>()))
 392             -> std::remove_reference_t<decltype(
 393                 D(std::declval<D &>()),
 394                 --std::declval<D &>(),
 395                 std::declval<D &>())>
 396         {
 397             D retval = derived();
 398             --derived();
 399             return retval;
 400         }
 401
 402         template<typename D = Derived>
 403         constexpr D & operator-=(difference_type i) noexcept
 404         {
 405             derived() += -i;
 406             return derived();
 407         }
 408
 409         template<typename D = Derived>
 410         constexpr auto operator-(D other) const noexcept(noexcept(
 411             access::base(std::declval<D const &>()) - access::base(other)))
 412             -> decltype(
 413                 access::base(std::declval<D const &>()) - access::base(other))
 414         {
 415             return access::base(derived()) - access::base(other);
 416         }
 417
 418         friend BOOST_STL_INTERFACES_HIDDEN_FRIEND_CONSTEXPR Derived
 419         operator-(Derived it, difference_type i) noexcept
 420         {
 421             Derived retval = it;
 422             retval += -i;
 423             return retval;
 424         }
 425     };
 426
 427     /** Implementation of `operator==()`, implemented in terms of the iterator
 428         underlying IteratorInterface, for all iterators derived from
 429         `iterator_interface`, except those with an iterator category derived
 430         from `std::random_access_iterator_tag`.  */
 431     template<
 432         typename IteratorInterface1,
 433         typename IteratorInterface2,
 434         typename Enable =
 435             std::enable_if_t<!v1_dtl::ra_iter<IteratorInterface1>::value>>
 436     constexpr auto
 437     operator==(IteratorInterface1 lhs, IteratorInterface2 rhs) noexcept
 438         -> decltype(
 439             access::base(std::declval<IteratorInterface1 &>()) ==
 440             access::base(std::declval<IteratorInterface2 &>()))
 441     {
 442         return access::base(lhs) == access::base(rhs);
 443     }
 444
 445     /** Implementation of `operator==()` for all iterators derived from
 446         `iterator_interface` that have an iterator category derived from
 447         `std::random_access_iterator_tag`.  */
 448     template<
 449         typename IteratorInterface1,
 450         typename IteratorInterface2,
 451         typename Enable =
 452             std::enable_if_t<v1_dtl::ra_iter<IteratorInterface1>::value>>
 453     constexpr auto
 454     operator==(IteratorInterface1 lhs, IteratorInterface2 rhs) noexcept(
 455         noexcept(detail::common_diff(lhs, rhs)))
 456         -> decltype(
 457             v1_dtl::derived_iterator(lhs), detail::common_diff(lhs, rhs) == 0)
 458     {
 459         return detail::common_diff(lhs, rhs) == 0;
 460     }
 461
 462     /** Implementation of `operator!=()` for all iterators derived from
 463         `iterator_interface`.  */
 464     template<typename IteratorInterface1, typename IteratorInterface2>
 465     constexpr auto operator!=(
 466         IteratorInterface1 lhs,
 467         IteratorInterface2 rhs) noexcept(noexcept(!(lhs == rhs)))
 468         -> decltype(v1_dtl::derived_iterator(lhs), !(lhs == rhs))
 469     {
 470         return !(lhs == rhs);
 471     }
 472
 473     /** Implementation of `operator<()` for all iterators derived from
 474         `iterator_interface` that have an iterator category derived from
 475         `std::random_access_iterator_tag`.  */
 476     template<typename IteratorInterface1, typename IteratorInterface2>
 477     constexpr auto
 478     operator<(IteratorInterface1 lhs, IteratorInterface2 rhs) noexcept(
 479         noexcept(detail::common_diff(lhs, rhs)))
 480         -> decltype(
 481             v1_dtl::derived_iterator(lhs), detail::common_diff(lhs, rhs) < 0)
 482     {
 483         return detail::common_diff(lhs, rhs) < 0;
 484     }
 485
 486     /** Implementation of `operator<=()` for all iterators derived from
 487         `iterator_interface` that have an iterator category derived from
 488         `std::random_access_iterator_tag`.  */
 489     template<typename IteratorInterface1, typename IteratorInterface2>
 490     constexpr auto
 491     operator<=(IteratorInterface1 lhs, IteratorInterface2 rhs) noexcept(
 492         noexcept(detail::common_diff(lhs, rhs)))
 493         -> decltype(
 494             v1_dtl::derived_iterator(lhs), detail::common_diff(lhs, rhs) <= 0)
 495     {
 496         return detail::common_diff(lhs, rhs) <= 0;
 497     }
 498
 499     /** Implementation of `operator>()` for all iterators derived from
 500         `iterator_interface` that have an iterator category derived from
 501         `std::random_access_iterator_tag`.  */
 502     template<typename IteratorInterface1, typename IteratorInterface2>
 503     constexpr auto
 504     operator>(IteratorInterface1 lhs, IteratorInterface2 rhs) noexcept(
 505         noexcept(detail::common_diff(lhs, rhs)))
 506         -> decltype(
 507             v1_dtl::derived_iterator(lhs), detail::common_diff(lhs, rhs) > 0)
 508     {
 509         return detail::common_diff(lhs, rhs) > 0;
 510     }
 511
 512     /** Implementation of `operator>=()` for all iterators derived from
 513         `iterator_interface` that have an iterator category derived from
 514         `std::random_access_iterator_tag`.  */
 515     template<typename IteratorInterface1, typename IteratorInterface2>
 516     constexpr auto
 517     operator>=(IteratorInterface1 lhs, IteratorInterface2 rhs) noexcept(
 518         noexcept(detail::common_diff(lhs, rhs)))
 519         -> decltype(
 520             v1_dtl::derived_iterator(lhs), detail::common_diff(lhs, rhs) >= 0)
 521     {
 522         return detail::common_diff(lhs, rhs) >= 0;
 523     }
 524
 525
 526     /** A template alias useful for defining proxy iterators.  \see
 527         `iterator_interface`. */
 528     template<
 529         typename Derived,
 530         typename IteratorConcept,
 531         typename ValueType,
 532         typename Reference = ValueType,
 533         typename DifferenceType = std::ptrdiff_t>
 534     using proxy_iterator_interface = iterator_interface<
 535         Derived,
 536         IteratorConcept,
 537         ValueType,
 538         Reference,
 539         proxy_arrow_result<Reference>,
 540         DifferenceType>;
 541
 542 }}}
 543
 544 #if 201703L < __cplusplus && defined(__cpp_lib_ranges)
 545
 546 namespace boost { namespace stl_interfaces { namespace v2 { namespace detail {
 547
 548     template<typename Iterator>
 549     struct iter_concept;
 550
 551     template<typename Iterator>
 552     requires requires
 553     {
 554         typename std::iterator_traits<Iterator>::iterator_concept;
 555     }
 556     struct iter_concept<Iterator>
 557     {
 558         using type = typename std::iterator_traits<Iterator>::iterator_concept;
 559     };
 560
 561     template<typename Iterator>
 562     requires(
 563         !requires {
 564             typename std::iterator_traits<Iterator>::iterator_concept;
 565         } &&
 566         requires {
 567             typename std::iterator_traits<Iterator>::iterator_category;
 568         }) struct iter_concept<Iterator>
 569     {
 570         using type = typename std::iterator_traits<Iterator>::iterator_category;
 571     };
 572
 573     template<typename Iterator>
 574     requires(
 575         !requires {
 576             typename std::iterator_traits<Iterator>::iterator_concept;
 577         } &&
 578         !requires {
 579             typename std::iterator_traits<Iterator>::iterator_category;
 580         }) struct iter_concept<Iterator>
 581     {
 582         using type = std::random_access_iterator_tag;
 583     };
 584
 585     template<typename Iterator>
 586     struct iter_concept
 587     {};
 588
 589     template<typename Iterator>
 590     using iter_concept_t = typename iter_concept<Iterator>::type;
 591
 592 }}}}
 593
 594 #endif
 595
 596 #ifdef BOOST_STL_INTERFACES_DOXYGEN
 597
 598 /** `static_asserts` that type `type` models concept `concept_name`.  This is
 599     useful for checking that an iterator, view, etc. that you write using one
 600     of the *`_interface` templates models the right C++ concept.
 601
 602     For example: `BOOST_STL_INTERFACES_STATIC_ASSERT_CONCEPT(my_iter,
 603     std::input_iterator)`.
 604
 605     \note This macro expands to nothing when `__cpp_lib_concepts` is not
 606     defined. */
 607 #define BOOST_STL_INTERFACES_STATIC_ASSERT_CONCEPT(type, concept_name)
 608
 609 /** `static_asserts` that the types of all typedefs in
 610     `std::iterator_traits<iter>` match the remaining macro parameters.  This
 611     is useful for checking that an iterator you write using
 612     `iterator_interface` has the correct iterator traits.
 613
 614     For example: `BOOST_STL_INTERFACES_STATIC_ASSERT_ITERATOR_TRAITS(my_iter,
 615     std::input_iterator_tag, std::input_iterator_tag, int, int &, int *, std::ptrdiff_t)`.
 616
 617     \note This macro ignores the `concept` parameter when `__cpp_lib_concepts`
 618     is not defined. */
 619 #define BOOST_STL_INTERFACES_STATIC_ASSERT_ITERATOR_TRAITS(                    \
 620     iter, category, concept, value_type, reference, pointer, difference_type)
 621
 622 #else
 623
 624 #define BOOST_STL_INTERFACES_STATIC_ASSERT_ITERATOR_CONCEPT_IMPL(              \
 625     type, concept_name)                                                        \
 626     static_assert(concept_name<type>, "");
 627
 628 #define BOOST_STL_INTERFACES_STATIC_ASSERT_CONCEPT(iter, concept_name)
 629
 630 #define BOOST_STL_INTERFACES_STATIC_ASSERT_ITERATOR_TRAITS_IMPL(               \
 631     iter, category, value_t, ref, ptr, diff_t)                                 \
 632     static_assert(                                                             \
 633         std::is_same<                                                          \
 634             typename std::iterator_traits<iter>::iterator_category,            \
 635             category>::value,                                                  \
 636         "");                                                                   \
 637     static_assert(                                                             \
 638         std::is_same<                                                          \
 639             typename std::iterator_traits<iter>::value_type,                   \
 640             value_t>::value,                                                   \
 641         "");                                                                   \
 642     static_assert(                                                             \
 643         std::is_same<typename std::iterator_traits<iter>::reference, ref>::    \
 644             value,                                                             \
 645         "");                                                                   \
 646     static_assert(                                                             \
 647         std::is_same<typename std::iterator_traits<iter>::pointer, ptr>::      \
 648             value,                                                             \
 649         "");                                                                   \
 650     static_assert(                                                             \
 651         std::is_same<                                                          \
 652             typename std::iterator_traits<iter>::difference_type,              \
 653             diff_t>::value,                                                    \
 654         "");
 655
 656 #if 201703L < __cplusplus && defined(__cpp_lib_ranges)
 657 #define BOOST_STL_INTERFACES_STATIC_ASSERT_ITERATOR_TRAITS(                    \
 658     iter, category, concept, value_type, reference, pointer, difference_type)  \
 659     static_assert(                                                             \
 660         std::is_same_v<                                                        \
 661             boost::stl_interfaces::v2::detail::iter_concept_t<iter>,           \
 662             concept>,                                                          \
 663         "");                                                                   \
 664     BOOST_STL_INTERFACES_STATIC_ASSERT_ITERATOR_TRAITS_IMPL(                   \
 665         iter, category, value_type, reference, pointer, difference_type)
 666 #else
 667 #define BOOST_STL_INTERFACES_STATIC_ASSERT_ITERATOR_TRAITS(                    \
 668     iter, category, concept, value_type, reference, pointer, difference_type)  \
 669     BOOST_STL_INTERFACES_STATIC_ASSERT_ITERATOR_TRAITS_IMPL(                   \
 670         iter, category, value_type, reference, pointer, difference_type)
 671 #endif
 672
 673 #endif
 674
 675 #endif