__cxx03/__ranges/lazy_split_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_LAZY_SPLIT_VIEW_H
0011 #define _LIBCPP___CXX03___RANGES_LAZY_SPLIT_VIEW_H
0012
0013 #include <__cxx03/__algorithm/ranges_find.h>
0014 #include <__cxx03/__algorithm/ranges_mismatch.h>
0015 #include <__cxx03/__assert>
0016 #include <__cxx03/__concepts/constructible.h>
0017 #include <__cxx03/__concepts/convertible_to.h>
0018 #include <__cxx03/__concepts/derived_from.h>
0019 #include <__cxx03/__config>
0020 #include <__cxx03/__functional/bind_back.h>
0021 #include <__cxx03/__functional/ranges_operations.h>
0022 #include <__cxx03/__iterator/concepts.h>
0023 #include <__cxx03/__iterator/default_sentinel.h>
0024 #include <__cxx03/__iterator/incrementable_traits.h>
0025 #include <__cxx03/__iterator/indirectly_comparable.h>
0026 #include <__cxx03/__iterator/iter_move.h>
0027 #include <__cxx03/__iterator/iter_swap.h>
0028 #include <__cxx03/__iterator/iterator_traits.h>
0029 #include <__cxx03/__memory/addressof.h>
0030 #include <__cxx03/__ranges/access.h>
0031 #include <__cxx03/__ranges/all.h>
0032 #include <__cxx03/__ranges/concepts.h>
0033 #include <__cxx03/__ranges/non_propagating_cache.h>
0034 #include <__cxx03/__ranges/range_adaptor.h>
0035 #include <__cxx03/__ranges/single_view.h>
0036 #include <__cxx03/__ranges/subrange.h>
0037 #include <__cxx03/__ranges/view_interface.h>
0038 #include <__cxx03/__type_traits/conditional.h>
0039 #include <__cxx03/__type_traits/decay.h>
0040 #include <__cxx03/__type_traits/is_nothrow_constructible.h>
0041 #include <__cxx03/__type_traits/maybe_const.h>
0042 #include <__cxx03/__type_traits/remove_reference.h>
0043 #include <__cxx03/__utility/forward.h>
0044 #include <__cxx03/__utility/move.h>
0045
0046 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0047 #  pragma GCC system_header
0048 #endif
0049
0050 _LIBCPP_PUSH_MACROS
0051 #include <__cxx03/__undef_macros>
0052
0053 _LIBCPP_BEGIN_NAMESPACE_STD
0054
0055 #if _LIBCPP_STD_VER >= 20
0056
0057 namespace ranges {
0058
0059 template <auto>
0060 struct __require_constant;
0061
0062 template <class _Range>
0063 concept __tiny_range = sized_range<_Range> && requires {
0064   typename __require_constant<remove_reference_t<_Range>::size()>;
0065 } && (remove_reference_t<_Range>::size() <= 1);
0066
0067 template <input_range _View, forward_range _Pattern>
0068   requires view<_View> && view<_Pattern> &&
0069            indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to> &&
0070            (forward_range<_View> || __tiny_range<_Pattern>)
0071 class lazy_split_view : public view_interface<lazy_split_view<_View, _Pattern>> {
0072   _LIBCPP_NO_UNIQUE_ADDRESS _View __base_       = _View();
0073   _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern();
0074
0075   using _MaybeCurrent = _If<!forward_range<_View>, __non_propagating_cache<iterator_t<_View>>, __empty_cache>;
0076   _LIBCPP_NO_UNIQUE_ADDRESS _MaybeCurrent __current_ = _MaybeCurrent();
0077
0078   template <bool>
0079   struct __outer_iterator;
0080   template <bool>
0081   struct __inner_iterator;
0082
0083 public:
0084   _LIBCPP_HIDE_FROM_ABI lazy_split_view()
0085     requires default_initializable<_View> && default_initializable<_Pattern>
0086   = default;
0087
0088   _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 lazy_split_view(_View __base, _Pattern __pattern)
0089       : __base_(std::move(__base)), __pattern_(std::move(__pattern)) {}
0090
0091   template <input_range _Range>
0092     requires constructible_from<_View, views::all_t<_Range>> &&
0093                  constructible_from<_Pattern, single_view<range_value_t<_Range>>>
0094   _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 lazy_split_view(_Range&& __r, range_value_t<_Range> __e)
0095       : __base_(views::all(std::forward<_Range>(__r))), __pattern_(views::single(std::move(__e))) {}
0096
0097   _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
0098     requires copy_constructible<_View>
0099   {
0100     return __base_;
0101   }
0102   _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }
0103
0104   _LIBCPP_HIDE_FROM_ABI constexpr auto begin() {
0105     if constexpr (forward_range<_View>) {
0106       return __outer_iterator < __simple_view<_View> && __simple_view < _Pattern >> {*this, ranges::begin(__base_)};
0107     } else {
0108       __current_.__emplace(ranges::begin(__base_));
0109       return __outer_iterator<false>{*this};
0110     }
0111   }
0112
0113   _LIBCPP_HIDE_FROM_ABI constexpr auto begin() const
0114     requires forward_range<_View> && forward_range<const _View>
0115   {
0116     return __outer_iterator<true>{*this, ranges::begin(__base_)};
0117   }
0118
0119   _LIBCPP_HIDE_FROM_ABI constexpr auto end()
0120     requires forward_range<_View> && common_range<_View>
0121   {
0122     return __outer_iterator < __simple_view<_View> && __simple_view < _Pattern >> {*this, ranges::end(__base_)};
0123   }
0124
0125   _LIBCPP_HIDE_FROM_ABI constexpr auto end() const {
0126     if constexpr (forward_range<_View> && forward_range<const _View> && common_range<const _View>) {
0127       return __outer_iterator<true>{*this, ranges::end(__base_)};
0128     } else {
0129       return default_sentinel;
0130     }
0131   }
0132
0133 private:
0134   template <class>
0135   struct __outer_iterator_category {};
0136
0137   template <forward_range _Tp>
0138   struct __outer_iterator_category<_Tp> {
0139     using iterator_category = input_iterator_tag;
0140   };
0141
0142   template <bool _Const>
0143   struct __outer_iterator : __outer_iterator_category<__maybe_const<_Const, _View>> {
0144   private:
0145     template <bool>
0146     friend struct __inner_iterator;
0147     friend __outer_iterator<true>;
0148
0149     using _Parent = __maybe_const<_Const, lazy_split_view>;
0150     using _Base   = __maybe_const<_Const, _View>;
0151
0152     _Parent* __parent_                                 = nullptr;
0153     using _MaybeCurrent                                = _If<forward_range<_View>, iterator_t<_Base>, __empty_cache>;
0154     _LIBCPP_NO_UNIQUE_ADDRESS _MaybeCurrent __current_ = _MaybeCurrent();
0155     bool __trailing_empty_                             = false;
0156
0157     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto& __current() noexcept {
0158       if constexpr (forward_range<_View>) {
0159         return __current_;
0160       } else {
0161         return *__parent_->__current_;
0162       }
0163     }
0164
0165     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr const auto& __current() const noexcept {
0166       if constexpr (forward_range<_View>) {
0167         return __current_;
0168       } else {
0169         return *__parent_->__current_;
0170       }
0171     }
0172
0173     // Workaround for the GCC issue that doesn't allow calling `__parent_->__base_` from friend functions (because
0174     // `__base_` is private).
0175     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto& __parent_base() const noexcept { return __parent_->__base_; }
0176
0177   public:
0178     // using iterator_category = inherited;
0179     using iterator_concept = conditional_t<forward_range<_Base>, forward_iterator_tag, input_iterator_tag>;
0180     using difference_type  = range_difference_t<_Base>;
0181
0182     struct value_type : view_interface<value_type> {
0183     private:
0184       __outer_iterator __i_ = __outer_iterator();
0185
0186     public:
0187       _LIBCPP_HIDE_FROM_ABI value_type() = default;
0188       _LIBCPP_HIDE_FROM_ABI constexpr explicit value_type(__outer_iterator __i) : __i_(std::move(__i)) {}
0189
0190       _LIBCPP_HIDE_FROM_ABI constexpr __inner_iterator<_Const> begin() const { return __inner_iterator<_Const>{__i_}; }
0191       _LIBCPP_HIDE_FROM_ABI constexpr default_sentinel_t end() const noexcept { return default_sentinel; }
0192     };
0193
0194     _LIBCPP_HIDE_FROM_ABI __outer_iterator() = default;
0195
0196     _LIBCPP_HIDE_FROM_ABI constexpr explicit __outer_iterator(_Parent& __parent)
0197       requires(!forward_range<_Base>)
0198         : __parent_(std::addressof(__parent)) {}
0199
0200     _LIBCPP_HIDE_FROM_ABI constexpr __outer_iterator(_Parent& __parent, iterator_t<_Base> __current)
0201       requires forward_range<_Base>
0202         : __parent_(std::addressof(__parent)), __current_(std::move(__current)) {}
0203
0204     _LIBCPP_HIDE_FROM_ABI constexpr __outer_iterator(__outer_iterator<!_Const> __i)
0205       requires _Const && convertible_to<iterator_t<_View>, iterator_t<_Base>>
0206         : __parent_(__i.__parent_), __current_(std::move(__i.__current_)) {}
0207
0208     _LIBCPP_HIDE_FROM_ABI constexpr value_type operator*() const { return value_type{*this}; }
0209
0210     _LIBCPP_HIDE_FROM_ABI constexpr __outer_iterator& operator++() {
0211       const auto __end = ranges::end(__parent_->__base_);
0212       if (__current() == __end) {
0213         __trailing_empty_ = false;
0214         return *this;
0215       }
0216
0217       const auto [__pbegin, __pend] = ranges::subrange{__parent_->__pattern_};
0218       if (__pbegin == __pend) {
0219         // Empty pattern: split on every element in the input range
0220         ++__current();
0221
0222       } else if constexpr (__tiny_range<_Pattern>) {
0223         // One-element pattern: we can use `ranges::find`.
0224         __current() = ranges::find(std::move(__current()), __end, *__pbegin);
0225         if (__current() != __end) {
0226           // Make sure we point to after the separator we just found.
0227           ++__current();
0228           if (__current() == __end)
0229             __trailing_empty_ = true;
0230         }
0231
0232       } else {
0233         // General case for n-element pattern.
0234         do {
0235           const auto [__b, __p] = ranges::mismatch(__current(), __end, __pbegin, __pend);
0236           if (__p == __pend) {
0237             __current() = __b;
0238             if (__current() == __end) {
0239               __trailing_empty_ = true;
0240             }
0241             break; // The pattern matched; skip it.
0242           }
0243         } while (++__current() != __end);
0244       }
0245
0246       return *this;
0247     }
0248
0249     _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator++(int) {
0250       if constexpr (forward_range<_Base>) {
0251         auto __tmp = *this;
0252         ++*this;
0253         return __tmp;
0254
0255       } else {
0256         ++*this;
0257       }
0258     }
0259
0260     _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __outer_iterator& __x, const __outer_iterator& __y)
0261       requires forward_range<_Base>
0262     {
0263       return __x.__current_ == __y.__current_ && __x.__trailing_empty_ == __y.__trailing_empty_;
0264     }
0265
0266     _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __outer_iterator& __x, default_sentinel_t) {
0267       _LIBCPP_ASSERT_NON_NULL(__x.__parent_ != nullptr, "Cannot call comparison on a default-constructed iterator.");
0268       return __x.__current() == ranges::end(__x.__parent_base()) && !__x.__trailing_empty_;
0269     }
0270   };
0271
0272   template <class>
0273   struct __inner_iterator_category {};
0274
0275   template <forward_range _Tp>
0276   struct __inner_iterator_category<_Tp> {
0277     using iterator_category =
0278         _If< derived_from<typename iterator_traits<iterator_t<_Tp>>::iterator_category, forward_iterator_tag>,
0279              forward_iterator_tag,
0280              typename iterator_traits<iterator_t<_Tp>>::iterator_category >;
0281   };
0282
0283   template <bool _Const>
0284   struct __inner_iterator : __inner_iterator_category<__maybe_const<_Const, _View>> {
0285   private:
0286     using _Base = __maybe_const<_Const, _View>;
0287     // Workaround for a GCC issue.
0288     static constexpr bool _OuterConst = _Const;
0289     __outer_iterator<_Const> __i_     = __outer_iterator<_OuterConst>();
0290     bool __incremented_               = false;
0291
0292     // Note: these private functions are necessary because GCC doesn't allow calls to private members of `__i_` from
0293     // free functions that are friends of `inner-iterator`.
0294
0295     _LIBCPP_HIDE_FROM_ABI constexpr bool __is_done() const {
0296       _LIBCPP_ASSERT_NON_NULL(__i_.__parent_ != nullptr, "Cannot call comparison on a default-constructed iterator.");
0297
0298       auto [__pcur, __pend] = ranges::subrange{__i_.__parent_->__pattern_};
0299       auto __end            = ranges::end(__i_.__parent_->__base_);
0300
0301       if constexpr (__tiny_range<_Pattern>) {
0302         const auto& __cur = __i_.__current();
0303         if (__cur == __end)
0304           return true;
0305         if (__pcur == __pend)
0306           return __incremented_;
0307
0308         return *__cur == *__pcur;
0309
0310       } else {
0311         auto __cur = __i_.__current();
0312         if (__cur == __end)
0313           return true;
0314         if (__pcur == __pend)
0315           return __incremented_;
0316
0317         do {
0318           if (*__cur != *__pcur)
0319             return false;
0320           if (++__pcur == __pend)
0321             return true;
0322         } while (++__cur != __end);
0323
0324         return false;
0325       }
0326     }
0327
0328     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto& __outer_current() noexcept { return __i_.__current(); }
0329
0330     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr const auto& __outer_current() const noexcept {
0331       return __i_.__current();
0332     }
0333
0334   public:
0335     // using iterator_category = inherited;
0336     using iterator_concept = typename __outer_iterator<_Const>::iterator_concept;
0337     using value_type       = range_value_t<_Base>;
0338     using difference_type  = range_difference_t<_Base>;
0339
0340     _LIBCPP_HIDE_FROM_ABI __inner_iterator() = default;
0341
0342     _LIBCPP_HIDE_FROM_ABI constexpr explicit __inner_iterator(__outer_iterator<_Const> __i) : __i_(std::move(__i)) {}
0343
0344     _LIBCPP_HIDE_FROM_ABI constexpr const iterator_t<_Base>& base() const& noexcept { return __i_.__current(); }
0345     _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_Base> base() &&
0346       requires forward_range<_View>
0347     {
0348       return std::move(__i_.__current());
0349     }
0350
0351     _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator*() const { return *__i_.__current(); }
0352
0353     _LIBCPP_HIDE_FROM_ABI constexpr __inner_iterator& operator++() {
0354       __incremented_ = true;
0355
0356       if constexpr (!forward_range<_Base>) {
0357         if constexpr (_Pattern::size() == 0) {
0358           return *this;
0359         }
0360       }
0361
0362       ++__i_.__current();
0363       return *this;
0364     }
0365
0366     _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator++(int) {
0367       if constexpr (forward_range<_Base>) {
0368         auto __tmp = *this;
0369         ++*this;
0370         return __tmp;
0371
0372       } else {
0373         ++*this;
0374       }
0375     }
0376
0377     _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __inner_iterator& __x, const __inner_iterator& __y)
0378       requires forward_range<_Base>
0379     {
0380       return __x.__outer_current() == __y.__outer_current();
0381     }
0382
0383     _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __inner_iterator& __x, default_sentinel_t) {
0384       return __x.__is_done();
0385     }
0386
0387     _LIBCPP_HIDE_FROM_ABI friend constexpr decltype(auto)
0388     iter_move(const __inner_iterator& __i) noexcept(noexcept(ranges::iter_move(__i.__outer_current()))) {
0389       return ranges::iter_move(__i.__outer_current());
0390     }
0391
0392     _LIBCPP_HIDE_FROM_ABI friend constexpr void iter_swap(
0393         const __inner_iterator& __x,
0394         const __inner_iterator& __y) noexcept(noexcept(ranges::iter_swap(__x.__outer_current(), __y.__outer_current())))
0395       requires indirectly_swappable<iterator_t<_Base>>
0396     {
0397       ranges::iter_swap(__x.__outer_current(), __y.__outer_current());
0398     }
0399   };
0400 };
0401
0402 template <class _Range, class _Pattern>
0403 lazy_split_view(_Range&&, _Pattern&&) -> lazy_split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
0404
0405 template <input_range _Range>
0406 lazy_split_view(_Range&&,
0407                 range_value_t<_Range>) -> lazy_split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
0408
0409 namespace views {
0410 namespace __lazy_split_view {
0411 struct __fn {
0412   template <class _Range, class _Pattern>
0413   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const
0414       noexcept(noexcept(lazy_split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))))
0415           -> decltype(lazy_split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))) {
0416     return lazy_split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern));
0417   }
0418
0419   template <class _Pattern>
0420     requires constructible_from<decay_t<_Pattern>, _Pattern>
0421   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pattern&& __pattern) const
0422       noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) {
0423     return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pattern>(__pattern)));
0424   }
0425 };
0426 } // namespace __lazy_split_view
0427
0428 inline namespace __cpo {
0429 inline constexpr auto lazy_split = __lazy_split_view::__fn{};
0430 } // namespace __cpo
0431 } // namespace views
0432
0433 } // namespace ranges
0434
0435 #endif // _LIBCPP_STD_VER >= 20
0436
0437 _LIBCPP_END_NAMESPACE_STD
0438
0439 _LIBCPP_POP_MACROS
0440
0441 #endif // _LIBCPP___CXX03___RANGES_LAZY_SPLIT_VIEW_H