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