__cxx03/__ranges/join_view.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___CXX03___RANGES_JOIN_VIEW_H
0011 #define _LIBCPP___CXX03___RANGES_JOIN_VIEW_H
0012
0013 #include <__cxx03/__concepts/constructible.h>
0014 #include <__cxx03/__concepts/convertible_to.h>
0015 #include <__cxx03/__concepts/copyable.h>
0016 #include <__cxx03/__concepts/derived_from.h>
0017 #include <__cxx03/__concepts/equality_comparable.h>
0018 #include <__cxx03/__config>
0019 #include <__cxx03/__iterator/concepts.h>
0020 #include <__cxx03/__iterator/iter_move.h>
0021 #include <__cxx03/__iterator/iter_swap.h>
0022 #include <__cxx03/__iterator/iterator_traits.h>
0023 #include <__cxx03/__iterator/iterator_with_data.h>
0024 #include <__cxx03/__iterator/segmented_iterator.h>
0025 #include <__cxx03/__memory/addressof.h>
0026 #include <__cxx03/__ranges/access.h>
0027 #include <__cxx03/__ranges/all.h>
0028 #include <__cxx03/__ranges/concepts.h>
0029 #include <__cxx03/__ranges/empty.h>
0030 #include <__cxx03/__ranges/non_propagating_cache.h>
0031 #include <__cxx03/__ranges/range_adaptor.h>
0032 #include <__cxx03/__ranges/view_interface.h>
0033 #include <__cxx03/__type_traits/common_type.h>
0034 #include <__cxx03/__type_traits/maybe_const.h>
0035 #include <__cxx03/__utility/as_lvalue.h>
0036 #include <__cxx03/__utility/empty.h>
0037 #include <__cxx03/__utility/forward.h>
0038 #include <__cxx03/optional>
0039
0040 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0041 #  pragma GCC system_header
0042 #endif
0043
0044 _LIBCPP_PUSH_MACROS
0045 #include <__cxx03/__undef_macros>
0046
0047 _LIBCPP_BEGIN_NAMESPACE_STD
0048
0049 #if _LIBCPP_STD_VER >= 20
0050
0051 namespace ranges {
0052 template <class>
0053 struct __join_view_iterator_category {};
0054
0055 template <class _View>
0056   requires is_reference_v<range_reference_t<_View>> && forward_range<_View> && forward_range<range_reference_t<_View>>
0057 struct __join_view_iterator_category<_View> {
0058   using _OuterC = typename iterator_traits<iterator_t<_View>>::iterator_category;
0059   using _InnerC = typename iterator_traits<iterator_t<range_reference_t<_View>>>::iterator_category;
0060
0061   using iterator_category =
0062       _If< derived_from<_OuterC, bidirectional_iterator_tag> && derived_from<_InnerC, bidirectional_iterator_tag> &&
0063                common_range<range_reference_t<_View>>,
0064            bidirectional_iterator_tag,
0065            _If< derived_from<_OuterC, forward_iterator_tag> && derived_from<_InnerC, forward_iterator_tag>,
0066                 forward_iterator_tag,
0067                 input_iterator_tag > >;
0068 };
0069
0070 template <input_range _View>
0071   requires view<_View> && input_range<range_reference_t<_View>>
0072 class join_view : public view_interface<join_view<_View>> {
0073 private:
0074   using _InnerRange = range_reference_t<_View>;
0075
0076   template <bool>
0077   struct __iterator;
0078
0079   template <bool>
0080   struct __sentinel;
0081
0082   template <class>
0083   friend struct std::__segmented_iterator_traits;
0084
0085   _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();
0086
0087   static constexpr bool _UseOuterCache = !forward_range<_View>;
0088   using _OuterCache                    = _If<_UseOuterCache, __non_propagating_cache<iterator_t<_View>>, __empty_cache>;
0089   _LIBCPP_NO_UNIQUE_ADDRESS _OuterCache __outer_;
0090
0091   static constexpr bool _UseInnerCache = !is_reference_v<_InnerRange>;
0092   using _InnerCache = _If<_UseInnerCache, __non_propagating_cache<remove_cvref_t<_InnerRange>>, __empty_cache>;
0093   _LIBCPP_NO_UNIQUE_ADDRESS _InnerCache __inner_;
0094
0095 public:
0096   _LIBCPP_HIDE_FROM_ABI join_view()
0097     requires default_initializable<_View>
0098   = default;
0099
0100   _LIBCPP_HIDE_FROM_ABI constexpr explicit join_view(_View __base) : __base_(std::move(__base)) {}
0101
0102   _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
0103     requires copy_constructible<_View>
0104   {
0105     return __base_;
0106   }
0107
0108   _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }
0109
0110   _LIBCPP_HIDE_FROM_ABI constexpr auto begin() {
0111     if constexpr (forward_range<_View>) {
0112       constexpr bool __use_const = __simple_view<_View> && is_reference_v<range_reference_t<_View>>;
0113       return __iterator<__use_const>{*this, ranges::begin(__base_)};
0114     } else {
0115       __outer_.__emplace(ranges::begin(__base_));
0116       return __iterator<false>{*this};
0117     }
0118   }
0119
0120   template <class _V2 = _View>
0121   _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const
0122     requires forward_range<const _V2> && is_reference_v<range_reference_t<const _V2>> &&
0123              input_range<range_reference_t<const _V2>>
0124   {
0125     return __iterator<true>{*this, ranges::begin(__base_)};
0126   }
0127
0128   _LIBCPP_HIDE_FROM_ABI constexpr auto end() {
0129     if constexpr (forward_range<_View> && is_reference_v<_InnerRange> && forward_range<_InnerRange> &&
0130                   common_range<_View> && common_range<_InnerRange>)
0131       return __iterator<__simple_view<_View>>{*this, ranges::end(__base_)};
0132     else
0133       return __sentinel<__simple_view<_View>>{*this};
0134   }
0135
0136   template <class _V2 = _View>
0137   _LIBCPP_HIDE_FROM_ABI constexpr auto end() const
0138     requires forward_range<const _V2> && is_reference_v<range_reference_t<const _V2>> &&
0139              input_range<range_reference_t<const _V2>>
0140   {
0141     using _ConstInnerRange = range_reference_t<const _View>;
0142     if constexpr (forward_range<_ConstInnerRange> && common_range<const _View> && common_range<_ConstInnerRange>) {
0143       return __iterator<true>{*this, ranges::end(__base_)};
0144     } else {
0145       return __sentinel<true>{*this};
0146     }
0147   }
0148 };
0149
0150 template <input_range _View>
0151   requires view<_View> && input_range<range_reference_t<_View>>
0152 template <bool _Const>
0153 struct join_view<_View>::__sentinel {
0154 private:
0155   template <bool>
0156   friend struct __sentinel;
0157
0158   using _Parent            = __maybe_const<_Const, join_view>;
0159   using _Base              = __maybe_const<_Const, _View>;
0160   sentinel_t<_Base> __end_ = sentinel_t<_Base>();
0161
0162 public:
0163   _LIBCPP_HIDE_FROM_ABI __sentinel() = default;
0164
0165   _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(_Parent& __parent) : __end_(ranges::end(__parent.__base_)) {}
0166
0167   _LIBCPP_HIDE_FROM_ABI constexpr __sentinel(__sentinel<!_Const> __s)
0168     requires _Const && convertible_to<sentinel_t<_View>, sentinel_t<_Base>>
0169       : __end_(std::move(__s.__end_)) {}
0170
0171   template <bool _OtherConst>
0172     requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>>
0173   _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
0174     return __x.__get_outer() == __y.__end_;
0175   }
0176 };
0177
0178 // https://reviews.llvm.org/D142811#inline-1383022
0179 // To simplify the segmented iterator traits specialization,
0180 // make the iterator `final`
0181 template <input_range _View>
0182   requires view<_View> && input_range<range_reference_t<_View>>
0183 template <bool _Const>
0184 struct join_view<_View>::__iterator final : public __join_view_iterator_category<__maybe_const<_Const, _View>> {
0185   friend join_view;
0186
0187   template <class>
0188   friend struct std::__segmented_iterator_traits;
0189
0190   static constexpr bool __is_join_view_iterator = true;
0191
0192 private:
0193   using _Parent     = __maybe_const<_Const, join_view<_View>>;
0194   using _Base       = __maybe_const<_Const, _View>;
0195   using _Outer      = iterator_t<_Base>;
0196   using _Inner      = iterator_t<range_reference_t<_Base>>;
0197   using _InnerRange = range_reference_t<_View>;
0198
0199   static_assert(!_Const || forward_range<_Base>, "Const can only be true when Base models forward_range.");
0200
0201   static constexpr bool __ref_is_glvalue = is_reference_v<range_reference_t<_Base>>;
0202
0203   static constexpr bool _OuterPresent           = forward_range<_Base>;
0204   using _OuterType                              = _If<_OuterPresent, _Outer, std::__empty>;
0205   _LIBCPP_NO_UNIQUE_ADDRESS _OuterType __outer_ = _OuterType();
0206
0207   optional<_Inner> __inner_;
0208   _Parent* __parent_ = nullptr;
0209
0210   _LIBCPP_HIDE_FROM_ABI constexpr void __satisfy() {
0211     for (; __get_outer() != ranges::end(__parent_->__base_); ++__get_outer()) {
0212       auto&& __inner = [this]() -> auto&& {
0213         if constexpr (__ref_is_glvalue)
0214           return *__get_outer();
0215         else
0216           return __parent_->__inner_.__emplace_from([&]() -> decltype(auto) { return *__get_outer(); });
0217       }();
0218       __inner_ = ranges::begin(__inner);
0219       if (*__inner_ != ranges::end(__inner))
0220         return;
0221     }
0222
0223     if constexpr (__ref_is_glvalue)
0224       __inner_.reset();
0225   }
0226
0227   _LIBCPP_HIDE_FROM_ABI constexpr _Outer& __get_outer() {
0228     if constexpr (forward_range<_Base>) {
0229       return __outer_;
0230     } else {
0231       return *__parent_->__outer_;
0232     }
0233   }
0234
0235   _LIBCPP_HIDE_FROM_ABI constexpr const _Outer& __get_outer() const {
0236     if constexpr (forward_range<_Base>) {
0237       return __outer_;
0238     } else {
0239       return *__parent_->__outer_;
0240     }
0241   }
0242
0243   _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent& __parent, _Outer __outer)
0244     requires forward_range<_Base>
0245       : __outer_(std::move(__outer)), __parent_(std::addressof(__parent)) {
0246     __satisfy();
0247   }
0248
0249   _LIBCPP_HIDE_FROM_ABI constexpr explicit __iterator(_Parent& __parent)
0250     requires(!forward_range<_Base>)
0251       : __parent_(std::addressof(__parent)) {
0252     __satisfy();
0253   }
0254
0255   _LIBCPP_HIDE_FROM_ABI constexpr __iterator(_Parent* __parent, _Outer __outer, _Inner __inner)
0256     requires forward_range<_Base>
0257       : __outer_(std::move(__outer)), __inner_(std::move(__inner)), __parent_(__parent) {}
0258
0259 public:
0260   using iterator_concept =
0261       _If< __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&
0262                common_range<range_reference_t<_Base>>,
0263            bidirectional_iterator_tag,
0264            _If< __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>,
0265                 forward_iterator_tag,
0266                 input_iterator_tag > >;
0267
0268   using value_type = range_value_t<range_reference_t<_Base>>;
0269
0270   using difference_type = common_type_t< range_difference_t<_Base>, range_difference_t<range_reference_t<_Base>>>;
0271
0272   _LIBCPP_HIDE_FROM_ABI __iterator() = default;
0273
0274   _LIBCPP_HIDE_FROM_ABI constexpr __iterator(__iterator<!_Const> __i)
0275     requires _Const && convertible_to<iterator_t<_View>, _Outer> && convertible_to<iterator_t<_InnerRange>, _Inner>
0276       : __outer_(std::move(__i.__outer_)), __inner_(std::move(__i.__inner_)), __parent_(__i.__parent_) {}
0277
0278   _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const { return **__inner_; }
0279
0280   _LIBCPP_HIDE_FROM_ABI constexpr _Inner operator->() const
0281     requires __has_arrow<_Inner> && copyable<_Inner>
0282   {
0283     return *__inner_;
0284   }
0285
0286   _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() {
0287     auto __get_inner_range = [&]() -> decltype(auto) {
0288       if constexpr (__ref_is_glvalue)
0289         return *__get_outer();
0290       else
0291         return *__parent_->__inner_;
0292     };
0293     if (++*__inner_ == ranges::end(std::__as_lvalue(__get_inner_range()))) {
0294       ++__get_outer();
0295       __satisfy();
0296     }
0297     return *this;
0298   }
0299
0300   _LIBCPP_HIDE_FROM_ABI constexpr void operator++(int) { ++*this; }
0301
0302   _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int)
0303     requires __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>
0304   {
0305     auto __tmp = *this;
0306     ++*this;
0307     return __tmp;
0308   }
0309
0310   _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--()
0311     requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&
0312              common_range<range_reference_t<_Base>>
0313   {
0314     if (__outer_ == ranges::end(__parent_->__base_))
0315       __inner_ = ranges::end(std::__as_lvalue(*--__outer_));
0316
0317     // Skip empty inner ranges when going backwards.
0318     while (*__inner_ == ranges::begin(std::__as_lvalue(*__outer_))) {
0319       __inner_ = ranges::end(std::__as_lvalue(*--__outer_));
0320     }
0321
0322     --*__inner_;
0323     return *this;
0324   }
0325
0326   _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int)
0327     requires __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&
0328              common_range<range_reference_t<_Base>>
0329   {
0330     auto __tmp = *this;
0331     --*this;
0332     return __tmp;
0333   }
0334
0335   _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y)
0336     requires __ref_is_glvalue && forward_range<_Base> && equality_comparable<iterator_t<range_reference_t<_Base>>>
0337   {
0338     return __x.__outer_ == __y.__outer_ && __x.__inner_ == __y.__inner_;
0339   }
0340
0341   _LIBCPP_HIDE_FROM_ABI friend constexpr decltype(auto)
0342   iter_move(const __iterator& __i) noexcept(noexcept(ranges::iter_move(*__i.__inner_))) {
0343     return ranges::iter_move(*__i.__inner_);
0344   }
0345
0346   _LIBCPP_HIDE_FROM_ABI friend constexpr void
0347   iter_swap(const __iterator& __x,
0348             const __iterator& __y) noexcept(noexcept(ranges::iter_swap(*__x.__inner_, *__y.__inner_)))
0349     requires indirectly_swappable<_Inner>
0350   {
0351     return ranges::iter_swap(*__x.__inner_, *__y.__inner_);
0352   }
0353 };
0354
0355 template <class _Range>
0356 explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>;
0357
0358 namespace views {
0359 namespace __join_view {
0360 struct __fn : __range_adaptor_closure<__fn> {
0361   template <class _Range>
0362   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range) const
0363       noexcept(noexcept(join_view<all_t<_Range&&>>(std::forward<_Range>(__range))))
0364           -> decltype(join_view<all_t<_Range&&>>(std::forward<_Range>(__range))) {
0365     return join_view<all_t<_Range&&>>(std::forward<_Range>(__range));
0366   }
0367 };
0368 } // namespace __join_view
0369 inline namespace __cpo {
0370 inline constexpr auto join = __join_view::__fn{};
0371 } // namespace __cpo
0372 } // namespace views
0373 } // namespace ranges
0374
0375 template <class _JoinViewIterator>
0376   requires(_JoinViewIterator::__is_join_view_iterator && ranges::common_range<typename _JoinViewIterator::_Parent> &&
0377            __has_random_access_iterator_category<typename _JoinViewIterator::_Outer>::value &&
0378            __has_random_access_iterator_category<typename _JoinViewIterator::_Inner>::value)
0379 struct __segmented_iterator_traits<_JoinViewIterator> {
0380   using __segment_iterator =
0381       _LIBCPP_NODEBUG __iterator_with_data<typename _JoinViewIterator::_Outer, typename _JoinViewIterator::_Parent*>;
0382   using __local_iterator = typename _JoinViewIterator::_Inner;
0383
0384   // TODO: Would it make sense to enable the optimization for other iterator types?
0385
0386   static constexpr _LIBCPP_HIDE_FROM_ABI __segment_iterator __segment(_JoinViewIterator __iter) {
0387     if (ranges::empty(__iter.__parent_->__base_))
0388       return {};
0389     if (!__iter.__inner_.has_value())
0390       return __segment_iterator(--__iter.__outer_, __iter.__parent_);
0391     return __segment_iterator(__iter.__outer_, __iter.__parent_);
0392   }
0393
0394   static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __local(_JoinViewIterator __iter) {
0395     if (ranges::empty(__iter.__parent_->__base_))
0396       return {};
0397     if (!__iter.__inner_.has_value())
0398       return ranges::end(*--__iter.__outer_);
0399     return *__iter.__inner_;
0400   }
0401
0402   static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __begin(__segment_iterator __iter) {
0403     return ranges::begin(*__iter.__get_iter());
0404   }
0405
0406   static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __end(__segment_iterator __iter) {
0407     return ranges::end(*__iter.__get_iter());
0408   }
0409
0410   static constexpr _LIBCPP_HIDE_FROM_ABI _JoinViewIterator
0411   __compose(__segment_iterator __seg_iter, __local_iterator __local_iter) {
0412     return _JoinViewIterator(
0413         std::move(__seg_iter).__get_data(), std::move(__seg_iter).__get_iter(), std::move(__local_iter));
0414   }
0415 };
0416
0417 #endif // #if _LIBCPP_STD_VER >= 20
0418
0419 _LIBCPP_END_NAMESPACE_STD
0420
0421 _LIBCPP_POP_MACROS
0422
0423 #endif // _LIBCPP___CXX03___RANGES_JOIN_VIEW_H