v3/iterator/common_iterator.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2014-present
0005 //  Copyright Casey Carter 2016
0006 //
0007 //  Use, modification and distribution is subject to the
0008 //  Boost Software License, Version 1.0. (See accompanying
0009 //  file LICENSE_1_0.txt or copy at
0010 //  http://www.boost.org/LICENSE_1_0.txt)
0011 //
0012 // Project home: https://github.com/ericniebler/range-v3
0013 //
0014 #ifndef RANGES_V3_ITERATOR_COMMON_ITERATOR_HPP
0015 #define RANGES_V3_ITERATOR_COMMON_ITERATOR_HPP
0016
0017 #include <cstdint>
0018 #include <iterator>
0019 #include <type_traits>
0020
0021 #include <meta/meta.hpp>
0022
0023 #include <concepts/concepts.hpp>
0024
0025 #include <range/v3/range_fwd.hpp>
0026
0027 #include <range/v3/detail/variant.hpp>
0028 #include <range/v3/iterator/basic_iterator.hpp>
0029 #include <range/v3/iterator/concepts.hpp>
0030 #include <range/v3/utility/common_tuple.hpp>
0031
0032 #include <range/v3/detail/prologue.hpp>
0033
0034 namespace ranges
0035 {
0036     /// \addtogroup group-iterator
0037     /// @{
0038
0039     /// \cond
0040     namespace detail
0041     {
0042         template<typename I, typename S>
0043         variant<I, S> & cidata(common_iterator<I, S> & that)
0044         {
0045             return that.data_;
0046         }
0047
0048         template<typename I, typename S>
0049         variant<I, S> const & cidata(common_iterator<I, S> const & that)
0050         {
0051             return that.data_;
0052         }
0053     } // namespace detail
0054
0055 #if RANGES_BROKEN_CPO_LOOKUP
0056     namespace _common_iterator_
0057     {
0058         struct adl_hook
0059         {};
0060     } // namespace _common_iterator_
0061 #endif
0062     /// \endcond
0063
0064     template<typename I, typename S>
0065     struct common_iterator
0066 #if RANGES_BROKEN_CPO_LOOKUP
0067       : private _common_iterator_::adl_hook
0068 #endif
0069     {
0070     private:
0071         CPP_assert(input_or_output_iterator<I>);
0072         CPP_assert(sentinel_for<S, I>);
0073         CPP_assert(!same_as<I, S>);
0074         variant<I, S> data_;
0075
0076         friend variant<I, S> & detail::cidata<>(common_iterator<I, S> &);
0077         friend variant<I, S> const & detail::cidata<>(common_iterator<I, S> const &);
0078         struct emplace_fn
0079         {
0080             variant<I, S> * data_;
0081             template<typename T, std::size_t N>
0082             void operator()(indexed_element<T, N> t) const
0083             {
0084                 ranges::emplace<N>(*data_, t.get());
0085             }
0086         };
0087         struct arrow_proxy_
0088         {
0089         private:
0090             friend common_iterator;
0091             iter_value_t<I> keep_;
0092             arrow_proxy_(iter_reference_t<I> && x)
0093               : keep_(std::move(x))
0094             {}
0095
0096         public:
0097             const iter_value_t<I> * operator->() const noexcept
0098             {
0099                 return std::addressof(keep_);
0100             }
0101         };
0102         template<typename T>
0103         static T * operator_arrow_(T * p, int) noexcept
0104         {
0105             return p;
0106         }
0107         template<typename J, typename = detail::iter_arrow_t<J const>>
0108         static J operator_arrow_(J const & j, int) noexcept(noexcept(J(j)))
0109         {
0110             return j;
0111         }
0112         template(typename J, typename R = iter_reference_t<J>)(
0113             requires std::is_reference<R>::value) //
0114         static meta::_t<std::add_pointer<R>> operator_arrow_(J const & j, long) noexcept
0115         {
0116             auto && r = *j;
0117             return std::addressof(r);
0118         }
0119         template(typename J, typename V = iter_value_t<J>)(
0120             requires constructible_from<V, iter_reference_t<J>>)
0121         static arrow_proxy_ operator_arrow_(J const & j, ...) noexcept(noexcept(V(V(*j))))
0122         {
0123             return arrow_proxy_(*j);
0124         }
0125
0126     public:
0127         using difference_type = iter_difference_t<I>;
0128
0129         common_iterator() = default;
0130         common_iterator(I i)
0131           : data_(emplaced_index<0>, std::move(i))
0132         {}
0133         common_iterator(S s)
0134           : data_(emplaced_index<1>, std::move(s))
0135         {}
0136         template(typename I2, typename S2)(
0137             requires convertible_to<I2, I> AND convertible_to<S2, S>)
0138         common_iterator(common_iterator<I2, S2> const & that)
0139           : data_(detail::variant_core_access::make_empty<I, S>())
0140         {
0141             detail::cidata(that).visit_i(emplace_fn{&data_});
0142         }
0143         template(typename I2, typename S2)(
0144             requires convertible_to<I2, I> AND convertible_to<S2, S>)
0145         common_iterator & operator=(common_iterator<I2, S2> const & that)
0146         {
0147             detail::cidata(that).visit_i(emplace_fn{&data_});
0148             return *this;
0149         }
0150         iter_reference_t<I> operator*() //
0151             noexcept(noexcept(iter_reference_t<I>(*std::declval<I &>())))
0152         {
0153             return *ranges::get<0>(data_);
0154         }
0155         CPP_member
0156         auto operator*() const //
0157             noexcept(noexcept(iter_reference_t<I>(*std::declval<I const &>())))
0158             -> CPP_ret(iter_reference_t<I>)(
0159                 requires indirectly_readable<I const>)
0160         {
0161             return *ranges::get<0>(data_);
0162         }
0163         template(typename J = I)(
0164             requires indirectly_readable<J>)
0165         auto operator->() const //
0166             noexcept(
0167                 noexcept(common_iterator::operator_arrow_(std::declval<I const &>(), 42)))
0168             -> decltype(common_iterator::operator_arrow_(std::declval<J const &>(), 42))
0169         {
0170             return common_iterator::operator_arrow_(ranges::get<0>(data_), 42);
0171         }
0172         common_iterator & operator++()
0173         {
0174             ++ranges::get<0>(data_);
0175             return *this;
0176         }
0177 #ifdef RANGES_WORKAROUND_MSVC_677925
0178         template(typename I2 = I)(
0179             requires (!forward_iterator<I2>)) //
0180         auto operator++(int) //
0181             -> decltype(std::declval<I2 &>()++)
0182         {
0183             return ranges::get<0>(data_)++;
0184         }
0185 #else  // ^^^ workaround ^^^ / vvv no workaround vvv
0186         CPP_member
0187         auto operator++(int) //
0188             -> CPP_ret(decltype(std::declval<I &>()++))(
0189                 requires (!forward_iterator<I>))
0190         {
0191             return ranges::get<0>(data_)++;
0192         }
0193 #endif // RANGES_WORKAROUND_MSVC_677925
0194         CPP_member
0195         auto operator++(int) //
0196             -> CPP_ret(common_iterator)(
0197                 requires forward_iterator<I>)
0198         {
0199             return common_iterator(ranges::get<0>(data_)++);
0200         }
0201
0202 #if !RANGES_BROKEN_CPO_LOOKUP
0203         template<typename I_ = I>
0204         friend constexpr auto iter_move(common_iterator const & i) //
0205             noexcept(detail::has_nothrow_iter_move_v<I>)
0206             -> CPP_broken_friend_ret(iter_rvalue_reference_t<I>)(
0207                 requires input_iterator<I_>)
0208         {
0209             return ranges::iter_move(ranges::get<0>(detail::cidata(i)));
0210         }
0211         template<typename I2, typename S2>
0212         friend auto iter_swap(
0213             common_iterator const & x,
0214             common_iterator<I2, S2> const &
0215                 y) noexcept(is_nothrow_indirectly_swappable<I, I2>::value)
0216             -> CPP_broken_friend_ret(void)(
0217                 requires indirectly_swappable<I2, I>)
0218         {
0219             return ranges::iter_swap(ranges::get<0>(detail::cidata(x)),
0220                                      ranges::get<0>(detail::cidata(y)));
0221         }
0222 #endif
0223     };
0224
0225     /// \cond
0226 #if RANGES_BROKEN_CPO_LOOKUP
0227     namespace _common_iterator_
0228     {
0229         template<typename I, typename S>
0230         constexpr auto iter_move(common_iterator<I, S> const & i) noexcept(
0231             detail::has_nothrow_iter_move_v<I>)
0232             -> CPP_broken_friend_ret(iter_rvalue_reference_t<I>)(
0233                 requires input_iterator<I>)
0234         {
0235             return ranges::iter_move(ranges::get<0>(detail::cidata(i)));
0236         }
0237         template<typename I1, typename S1, typename I2, typename S2>
0238         auto iter_swap(common_iterator<I1, S1> const & x,
0239                        common_iterator<I2, S2> const & y) //
0240             noexcept(is_nothrow_indirectly_swappable<I1, I2>::value)
0241                 -> CPP_broken_friend_ret(void)(
0242                     requires indirectly_swappable<I1, I2>)
0243         {
0244             return ranges::iter_swap(ranges::get<0>(detail::cidata(x)),
0245                                      ranges::get<0>(detail::cidata(y)));
0246         }
0247     } // namespace _common_iterator_
0248 #endif
0249     /// \endcond
0250
0251     template(typename I1, typename I2, typename S1, typename S2)(
0252         requires sentinel_for<S1, I2> AND sentinel_for<S2, I1> AND
0253         (!equality_comparable_with<I1, I2>)) //
0254     bool operator==(common_iterator<I1, S1> const & x, common_iterator<I2, S2> const & y)
0255     {
0256         return detail::cidata(x).index() == 1u ? (detail::cidata(y).index() == 1u ||
0257                                                   ranges::get<0>(detail::cidata(y)) ==
0258                                                       ranges::get<1>(detail::cidata(x)))
0259                                                : (detail::cidata(y).index() != 1u ||
0260                                                   ranges::get<0>(detail::cidata(x)) ==
0261                                                       ranges::get<1>(detail::cidata(y)));
0262     }
0263
0264     template(typename I1, typename I2, typename S1, typename S2)(
0265         requires sentinel_for<S1, I2> AND sentinel_for<S2, I1> AND
0266             equality_comparable_with<I1, I2>)
0267     bool operator==(common_iterator<I1, S1> const & x, common_iterator<I2, S2> const & y)
0268     {
0269         return detail::cidata(x).index() == 1u
0270                    ? (detail::cidata(y).index() == 1u ||
0271                       ranges::get<0>(detail::cidata(y)) ==
0272                           ranges::get<1>(detail::cidata(x)))
0273                    : (detail::cidata(y).index() == 1u
0274                           ? ranges::get<0>(detail::cidata(x)) ==
0275                                 ranges::get<1>(detail::cidata(y))
0276                           : ranges::get<0>(detail::cidata(x)) ==
0277                                 ranges::get<0>(detail::cidata(y)));
0278     }
0279
0280     template(typename I1, typename I2, typename S1, typename S2)(
0281         requires sentinel_for<S1, I2> AND sentinel_for<S2, I1>)
0282     bool operator!=(common_iterator<I1, S1> const & x, common_iterator<I2, S2> const & y)
0283     {
0284         return !(x == y);
0285     }
0286
0287     template(typename I1, typename I2, typename S1, typename S2)(
0288         requires sized_sentinel_for<I1, I2> AND sized_sentinel_for<S1, I2> AND
0289             sized_sentinel_for<S2, I1>)
0290     iter_difference_t<I2> operator-(common_iterator<I1, S1> const & x,
0291                                     common_iterator<I2, S2> const & y)
0292     {
0293         return detail::cidata(x).index() == 1u
0294                    ? (detail::cidata(y).index() == 1u
0295                           ? 0
0296                           : ranges::get<1>(detail::cidata(x)) -
0297                                 ranges::get<0>(detail::cidata(y)))
0298                    : (detail::cidata(y).index() == 1u
0299                           ? ranges::get<0>(detail::cidata(x)) -
0300                                 ranges::get<1>(detail::cidata(y))
0301                           : ranges::get<0>(detail::cidata(x)) -
0302                                 ranges::get<0>(detail::cidata(y)));
0303     }
0304
0305     template<typename I, typename S>
0306     struct indirectly_readable_traits<common_iterator<I, S>>
0307       : meta::if_c<
0308         (bool)indirectly_readable<I>,
0309         indirectly_readable_traits<I>,
0310         meta::nil_>
0311     {};
0312
0313     /// \cond
0314     namespace detail
0315     {
0316         template<typename I>
0317         auto demote_common_iter_cat(...) -> nil_;
0318         template<typename I>
0319         auto demote_common_iter_cat(long)
0320             -> with_iterator_category<std::input_iterator_tag>;
0321         template(typename I)(
0322             requires derived_from<typename std::iterator_traits<I>::iterator_category,
0323                                       std::forward_iterator_tag>)
0324         auto demote_common_iter_cat(int)
0325             -> with_iterator_category<std::forward_iterator_tag>;
0326
0327         template<typename I, bool = (bool)input_iterator<I>>
0328         struct common_iterator_std_traits : decltype(detail::demote_common_iter_cat<I>(0))
0329         {
0330             using difference_type = iter_difference_t<I>;
0331             using value_type = iter_value_t<I>;
0332             using reference = iter_reference_t<I>;
0333             using pointer = detail::iter_pointer_t<I>;
0334             using iterator_concept =
0335                 meta::conditional_t<(bool)forward_iterator<I>, std::forward_iterator_tag,
0336                           std::input_iterator_tag>;
0337         };
0338
0339         template<typename I>
0340         struct common_iterator_std_traits<I, false>
0341         {
0342             using difference_type = iter_difference_t<I>;
0343             using value_type = void;
0344             using reference = void;
0345             using pointer = void;
0346             using iterator_category = std::output_iterator_tag;
0347         };
0348
0349         // An iterator adaptor that demotes a user-defined difference_type to
0350         // std::intmax_t, for use when constructing containers from such
0351         // iterators.
0352         template<typename I>
0353         struct cpp17_iterator_cursor
0354         {
0355         private:
0356             friend range_access;
0357             I it_;
0358             struct mixin : basic_mixin<cpp17_iterator_cursor>
0359             {
0360                 mixin() = default;
0361                 #ifndef _MSC_VER
0362                 using basic_mixin<cpp17_iterator_cursor>::basic_mixin;
0363                 #else
0364                 constexpr explicit mixin(cpp17_iterator_cursor && cur)
0365                   : basic_mixin<cpp17_iterator_cursor>(
0366                         static_cast<cpp17_iterator_cursor &&>(cur))
0367                 {}
0368                 constexpr explicit mixin(cpp17_iterator_cursor const & cur)
0369                   : basic_mixin<cpp17_iterator_cursor>(cur)
0370                 {}
0371                 #endif
0372                 explicit mixin(I it)
0373                   : mixin{cpp17_iterator_cursor{std::move(it)}}
0374                 {}
0375                 I base() const
0376                 {
0377                     return this->get().it_;
0378                 }
0379             };
0380
0381         public:
0382             using single_pass = meta::bool_<!forward_iterator<I>>;
0383             using difference_type = std::ptrdiff_t;
0384             using value_type = iter_value_t<I>;
0385
0386             cpp17_iterator_cursor() = default;
0387             constexpr explicit cpp17_iterator_cursor(I i)
0388               : it_(static_cast<I &&>(i))
0389             {}
0390
0391             I arrow() const
0392             {
0393                 return it_;
0394             }
0395             decltype(auto) read()
0396             {
0397                 return *it_;
0398             }
0399             decltype(auto) read() const
0400             {
0401                 return *it_;
0402             }
0403             void next()
0404             {
0405                 ++it_;
0406             }
0407             bool equal(cpp17_iterator_cursor const & that) const
0408             {
0409                 return it_ == that.it_;
0410             }
0411             CPP_member
0412             auto prev() //
0413                 -> CPP_ret(void)(
0414                     requires bidirectional_iterator<I>)
0415             {
0416                 --it_;
0417             }
0418             CPP_member
0419             auto advance(std::ptrdiff_t n) //
0420                 -> CPP_ret(void)(
0421                     requires random_access_iterator<I>)
0422             {
0423                 it_ += static_cast<iter_difference_t<I>>(n);
0424             }
0425             CPP_member
0426             auto distance_to(cpp17_iterator_cursor const & that) //
0427                 -> CPP_ret(std::ptrdiff_t)(
0428                     requires random_access_iterator<I>)
0429             {
0430                 auto d = that.it_ - it_;
0431                 RANGES_EXPECT(d <= PTRDIFF_MAX);
0432                 return static_cast<std::ptrdiff_t>(d);
0433             }
0434         };
0435     } // namespace detail
0436     /// \endcond
0437
0438     namespace cpp20
0439     {
0440         using ranges::common_iterator;
0441     }
0442     /// @}
0443 } // namespace ranges
0444
0445 /// \cond
0446 RANGES_DIAGNOSTIC_PUSH
0447 RANGES_DIAGNOSTIC_IGNORE_MISMATCHED_TAGS
0448
0449 namespace std
0450 {
0451     template<typename I, typename S>
0452     struct iterator_traits<::ranges::common_iterator<I, S>>
0453       : ::ranges::detail::common_iterator_std_traits<I>
0454     {};
0455 } // namespace std
0456
0457 RANGES_DIAGNOSTIC_POP
0458 /// \endcond
0459
0460 #include <range/v3/detail/epilogue.hpp>
0461
0462 #endif