[libc++][ranges] Implement `lazy_split_view`.
Note that this class was called just `split_view` in the original One
Ranges Proposal and was renamed to `lazy_split_view` by
[P2210](https://wg21.link/p2210).
Co-authored-by: zoecarver <z.zoelec2@gmail.com>
Differential Revision: https://reviews.llvm.org/D107500
NOKEYCHECK=True
GitOrigin-RevId: e53c461bf3f0feebb4fd6b43e05a0047f8edb945
diff --git a/include/CMakeLists.txt b/include/CMakeLists.txt
index 615c0ab..cf73417 100644
--- a/include/CMakeLists.txt
+++ b/include/CMakeLists.txt
@@ -373,6 +373,7 @@
__ranges/enable_view.h
__ranges/iota_view.h
__ranges/join_view.h
+ __ranges/lazy_split_view.h
__ranges/non_propagating_cache.h
__ranges/owning_view.h
__ranges/range_adaptor.h
diff --git a/include/__ranges/lazy_split_view.h b/include/__ranges/lazy_split_view.h
new file mode 100644
index 0000000..68617c4
--- /dev/null
+++ b/include/__ranges/lazy_split_view.h
@@ -0,0 +1,466 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___RANGES_LAZY_SPLIT_VIEW_H
+#define _LIBCPP___RANGES_LAZY_SPLIT_VIEW_H
+
+#include <__algorithm/in_in_result.h>
+#include <__algorithm/ranges_find.h>
+#include <__algorithm/ranges_mismatch.h>
+#include <__concepts/constructible.h>
+#include <__concepts/convertible_to.h>
+#include <__concepts/derived_from.h>
+#include <__config>
+#include <__functional/bind_back.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/default_sentinel.h>
+#include <__iterator/incrementable_traits.h>
+#include <__iterator/indirectly_comparable.h>
+#include <__iterator/iter_move.h>
+#include <__iterator/iter_swap.h>
+#include <__iterator/iterator_traits.h>
+#include <__memory/addressof.h>
+#include <__ranges/access.h>
+#include <__ranges/all.h>
+#include <__ranges/concepts.h>
+#include <__ranges/non_propagating_cache.h>
+#include <__ranges/range_adaptor.h>
+#include <__ranges/single_view.h>
+#include <__ranges/subrange.h>
+#include <__ranges/view_interface.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+# pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+namespace ranges {
+
+template <auto> struct __require_constant;
+
+template <class _Range>
+concept __tiny_range =
+ sized_range<_Range> &&
+ requires { typename __require_constant<remove_reference_t<_Range>::size()>; } &&
+ (remove_reference_t<_Range>::size() <= 1);
+
+template <input_range _View, forward_range _Pattern>
+ requires view<_View> && view<_Pattern> &&
+ indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to> &&
+ (forward_range<_View> || __tiny_range<_Pattern>)
+class lazy_split_view : public view_interface<lazy_split_view<_View, _Pattern>> {
+
+ _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();
+ _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern();
+
+ using _MaybeCurrent = _If<!forward_range<_View>, __non_propagating_cache<iterator_t<_View>>, __empty_cache>;
+ _LIBCPP_NO_UNIQUE_ADDRESS _MaybeCurrent __current_ = _MaybeCurrent();
+
+ template <bool> struct __outer_iterator;
+ template <bool> struct __inner_iterator;
+
+public:
+ _LIBCPP_HIDE_FROM_ABI
+ lazy_split_view()
+ requires default_initializable<_View> && default_initializable<_Pattern> = default;
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr lazy_split_view(_View __base, _Pattern __pattern)
+ : __base_(std::move(__base)), __pattern_(std::move(__pattern)) {}
+
+ template <input_range _Range>
+ requires constructible_from<_View, views::all_t<_Range>> &&
+ constructible_from<_Pattern, single_view<range_value_t<_Range>>>
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr lazy_split_view(_Range&& __r, range_value_t<_Range> __e)
+ : __base_(views::all(std::forward<_Range>(__r)))
+ // TODO(varconst): use `views::single` once it's implemented.
+ , __pattern_(ranges::single_view(std::move(__e))) {}
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr _View base() const& requires copy_constructible<_View> { return __base_; }
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr _View base() && { return std::move(__base_); }
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr auto begin() {
+ if constexpr (forward_range<_View>) {
+ return __outer_iterator<__simple_view<_View> && __simple_view<_Pattern>>{*this, ranges::begin(__base_)};
+ } else {
+ __current_.__emplace(ranges::begin(__base_));
+ return __outer_iterator<false>{*this};
+ }
+ }
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr auto begin() const requires forward_range<_View> && forward_range<const _View> {
+ return __outer_iterator<true>{*this, ranges::begin(__base_)};
+ }
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr auto end() requires forward_range<_View> && common_range<_View> {
+ return __outer_iterator<__simple_view<_View> && __simple_view<_Pattern>>{*this, ranges::end(__base_)};
+ }
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr auto end() const {
+ if constexpr (forward_range<_View> && forward_range<const _View> && common_range<const _View>) {
+ return __outer_iterator<true>{*this, ranges::end(__base_)};
+ } else {
+ return default_sentinel;
+ }
+ }
+
+private:
+
+ template <class>
+ struct __outer_iterator_category {};
+
+ template <forward_range _Tp>
+ struct __outer_iterator_category<_Tp> {
+ using iterator_category = input_iterator_tag;
+ };
+
+ template <bool _Const>
+ struct __outer_iterator : __outer_iterator_category<__maybe_const<_Const, _View>> {
+ private:
+ template <bool>
+ friend struct __inner_iterator;
+ friend __outer_iterator<true>;
+
+ using _Parent = __maybe_const<_Const, lazy_split_view>;
+ using _Base = __maybe_const<_Const, _View>;
+
+ _Parent* __parent_ = nullptr;
+ using _MaybeCurrent = _If<forward_range<_View>, iterator_t<_Base>, __empty_cache>;
+ _LIBCPP_NO_UNIQUE_ADDRESS _MaybeCurrent __current_ = _MaybeCurrent();
+ bool __trailing_empty_ = false;
+
+ [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+ constexpr auto& __current() noexcept {
+ if constexpr (forward_range<_View>) {
+ return __current_;
+ } else {
+ return *__parent_->__current_;
+ }
+ }
+
+ [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+ constexpr const auto& __current() const noexcept {
+ if constexpr (forward_range<_View>) {
+ return __current_;
+ } else {
+ return *__parent_->__current_;
+ }
+ }
+
+ // Workaround for the GCC issue that doesn't allow calling `__parent_->__base_` from friend functions (because
+ // `__base_` is private).
+ [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+ constexpr auto& __parent_base() const noexcept {
+ return __parent_->__base_;
+ }
+
+ public:
+ // using iterator_category = inherited;
+ using iterator_concept = conditional_t<forward_range<_Base>, forward_iterator_tag, input_iterator_tag>;
+ using difference_type = range_difference_t<_Base>;
+
+ struct value_type : view_interface<value_type> {
+ private:
+ __outer_iterator __i_ = __outer_iterator();
+
+ public:
+ _LIBCPP_HIDE_FROM_ABI
+ value_type() = default;
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr explicit value_type(__outer_iterator __i)
+ : __i_(std::move(__i)) {}
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr __inner_iterator<_Const> begin() const { return __inner_iterator<_Const>{__i_}; }
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr default_sentinel_t end() const noexcept { return default_sentinel; }
+ };
+
+ _LIBCPP_HIDE_FROM_ABI
+ __outer_iterator() = default;
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr explicit __outer_iterator(_Parent& __parent)
+ requires (!forward_range<_Base>)
+ : __parent_(std::addressof(__parent)) {}
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr __outer_iterator(_Parent& __parent, iterator_t<_Base> __current)
+ requires forward_range<_Base>
+ : __parent_(std::addressof(__parent)), __current_(std::move(__current)) {}
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr __outer_iterator(__outer_iterator<!_Const> __i)
+ requires _Const && convertible_to<iterator_t<_View>, iterator_t<_Base>>
+ : __parent_(__i.__parent_), __current_(std::move(__i.__current_)) {}
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr value_type operator*() const { return value_type{*this}; }
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr __outer_iterator& operator++() {
+ const auto __end = ranges::end(__parent_->__base_);
+ if (__current() == __end) {
+ __trailing_empty_ = false;
+ return *this;
+ }
+
+ const auto [__pbegin, __pend] = ranges::subrange{__parent_->__pattern_};
+ if (__pbegin == __pend) {
+ // Empty pattern: split on every element in the input range
+ ++__current();
+
+ } else if constexpr (__tiny_range<_Pattern>) {
+ // One-element pattern: we can use `ranges::find`.
+ __current() = ranges::find(std::move(__current()), __end, *__pbegin);
+ if (__current() != __end) {
+ // Make sure we point to after the separator we just found.
+ ++__current();
+ if (__current() == __end)
+ __trailing_empty_ = true;
+ }
+
+ } else {
+ // General case for n-element pattern.
+ do {
+ const auto [__b, __p] = ranges::mismatch(__current(), __end, __pbegin, __pend);
+ if (__p == __pend) {
+ __current() = __b;
+ if (__current() == __end) {
+ __trailing_empty_ = true;
+ }
+ break; // The pattern matched; skip it.
+ }
+ } while (++__current() != __end);
+ }
+
+ return *this;
+ }
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr decltype(auto) operator++(int) {
+ if constexpr (forward_range<_Base>) {
+ auto __tmp = *this;
+ ++*this;
+ return __tmp;
+
+ } else {
+ ++*this;
+ }
+ }
+
+ _LIBCPP_HIDE_FROM_ABI
+ friend constexpr bool operator==(const __outer_iterator& __x, const __outer_iterator& __y)
+ requires forward_range<_Base> {
+ return __x.__current_ == __y.__current_ && __x.__trailing_empty_ == __y.__trailing_empty_;
+ }
+
+ _LIBCPP_HIDE_FROM_ABI
+ friend constexpr bool operator==(const __outer_iterator& __x, default_sentinel_t) {
+ _LIBCPP_ASSERT(__x.__parent_, "Cannot call comparison on a default-constructed iterator.");
+ return __x.__current() == ranges::end(__x.__parent_base()) && !__x.__trailing_empty_;
+ }
+ };
+
+ template <class>
+ struct __inner_iterator_category {};
+
+ template <forward_range _Tp>
+ struct __inner_iterator_category<_Tp> {
+ using iterator_category = _If<
+ derived_from<typename iterator_traits<iterator_t<_Tp>>::iterator_category, forward_iterator_tag>,
+ forward_iterator_tag,
+ typename iterator_traits<iterator_t<_Tp>>::iterator_category
+ >;
+ };
+
+ template <bool _Const>
+ struct __inner_iterator : __inner_iterator_category<__maybe_const<_Const, _View>> {
+ private:
+ using _Base = __maybe_const<_Const, _View>;
+ // Workaround for a GCC issue.
+ static constexpr bool _OuterConst = _Const;
+ __outer_iterator<_Const> __i_ = __outer_iterator<_OuterConst>();
+ bool __incremented_ = false;
+
+ // Note: these private functions are necessary because GCC doesn't allow calls to private members of `__i_` from
+ // free functions that are friends of `inner-iterator`.
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr bool __is_done() const {
+ _LIBCPP_ASSERT(__i_.__parent_, "Cannot call comparison on a default-constructed iterator.");
+
+ auto [__pcur, __pend] = ranges::subrange{__i_.__parent_->__pattern_};
+ auto __end = ranges::end(__i_.__parent_->__base_);
+
+ if constexpr (__tiny_range<_Pattern>) {
+ const auto& __cur = __i_.__current();
+ if (__cur == __end)
+ return true;
+ if (__pcur == __pend)
+ return __incremented_;
+
+ return *__cur == *__pcur;
+
+ } else {
+ auto __cur = __i_.__current();
+ if (__cur == __end)
+ return true;
+ if (__pcur == __pend)
+ return __incremented_;
+
+ do {
+ if (*__cur != *__pcur)
+ return false;
+ if (++__pcur == __pend)
+ return true;
+ } while (++__cur != __end);
+
+ return false;
+ }
+ }
+
+ [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+ constexpr auto& __outer_current() noexcept {
+ return __i_.__current();
+ }
+
+ [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+ constexpr const auto& __outer_current() const noexcept {
+ return __i_.__current();
+ }
+
+ public:
+ // using iterator_category = inherited;
+ using iterator_concept = typename __outer_iterator<_Const>::iterator_concept;
+ using value_type = range_value_t<_Base>;
+ using difference_type = range_difference_t<_Base>;
+
+ _LIBCPP_HIDE_FROM_ABI
+ __inner_iterator() = default;
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr explicit __inner_iterator(__outer_iterator<_Const> __i)
+ : __i_(std::move(__i)) {}
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr const iterator_t<_Base>& base() const& noexcept { return __i_.__current(); }
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr iterator_t<_Base> base() &&
+ requires forward_range<_View> { return std::move(__i_.__current()); }
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr decltype(auto) operator*() const { return *__i_.__current(); }
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr __inner_iterator& operator++() {
+ __incremented_ = true;
+
+ if constexpr (!forward_range<_Base>) {
+ if constexpr (_Pattern::size() == 0) {
+ return *this;
+ }
+ }
+
+ ++__i_.__current();
+ return *this;
+ }
+
+ _LIBCPP_HIDE_FROM_ABI
+ constexpr decltype(auto) operator++(int) {
+ if constexpr (forward_range<_Base>) {
+ auto __tmp = *this;
+ ++*this;
+ return __tmp;
+
+ } else {
+ ++*this;
+ }
+ }
+
+ _LIBCPP_HIDE_FROM_ABI
+ friend constexpr bool operator==(const __inner_iterator& __x, const __inner_iterator& __y)
+ requires forward_range<_Base> {
+ return __x.__outer_current() == __y.__outer_current();
+ }
+
+ _LIBCPP_HIDE_FROM_ABI
+ friend constexpr bool operator==(const __inner_iterator& __x, default_sentinel_t) {
+ return __x.__is_done();
+ }
+
+ _LIBCPP_HIDE_FROM_ABI
+ friend constexpr decltype(auto) iter_move(const __inner_iterator& __i)
+ noexcept(noexcept(ranges::iter_move(__i.__outer_current()))) {
+ return ranges::iter_move(__i.__outer_current());
+ }
+
+ _LIBCPP_HIDE_FROM_ABI
+ friend constexpr void iter_swap(const __inner_iterator& __x, const __inner_iterator& __y)
+ noexcept(noexcept(ranges::iter_swap(__x.__outer_current(), __y.__outer_current())))
+ requires indirectly_swappable<iterator_t<_Base>> {
+ ranges::iter_swap(__x.__outer_current(), __y.__outer_current());
+ }
+ };
+
+};
+
+template <class _Range, class _Pattern>
+lazy_split_view(_Range&&, _Pattern&&) -> lazy_split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
+
+template <input_range _Range>
+lazy_split_view(_Range&&, range_value_t<_Range>)
+ -> lazy_split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
+
+namespace views {
+namespace __lazy_split_view {
+struct __fn : __range_adaptor_closure<__fn> {
+ template <class _Range, class _Pattern>
+ [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+ constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const
+ noexcept(noexcept(lazy_split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))))
+ -> decltype( lazy_split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)))
+ { return lazy_split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)); }
+
+ template <class _Pattern>
+ requires constructible_from<decay_t<_Pattern>, _Pattern>
+ [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+ constexpr auto operator()(_Pattern&& __pattern) const
+ noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) {
+ return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pattern>(__pattern)));
+ }
+};
+} // namespace __lazy_split_view
+
+inline namespace __cpo {
+ inline constexpr auto lazy_split = __lazy_split_view::__fn{};
+} // namespace __cpo
+} // namespace views
+
+} // namespace ranges
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___RANGES_LAZY_SPLIT_VIEW_H
diff --git a/include/module.modulemap b/include/module.modulemap
index 80ebbaf..6a20165 100644
--- a/include/module.modulemap
+++ b/include/module.modulemap
@@ -851,6 +851,7 @@
module enable_view { private header "__ranges/enable_view.h" }
module iota_view { private header "__ranges/iota_view.h" }
module join_view { private header "__ranges/join_view.h" }
+ module lazy_split_view { private header "__ranges/lazy_split_view.h" }
module non_propagating_cache { private header "__ranges/non_propagating_cache.h" }
module owning_view { private header "__ranges/owning_view.h" }
module range_adaptor { private header "__ranges/range_adaptor.h" }
diff --git a/include/ranges b/include/ranges
index 67a688b..3e843fc 100644
--- a/include/ranges
+++ b/include/ranges
@@ -204,6 +204,20 @@
template<input_range V>
requires view<V> && input_range<range_reference_t<V>>
class join_view;
+
+ // [range.lazy.split], lazy split view
+ template<class R>
+ concept tiny-range = see below; // exposition only
+
+ template<input_range V, forward_range Pattern>
+ requires view<V> && view<Pattern> &&
+ indirectly_comparable<iterator_t<V>, iterator_t<Pattern>, ranges::equal_to> &&
+ (forward_range<V> || tiny-range<Pattern>)
+ class lazy_split_view;
+
+ namespace views {
+ inline constexpr unspecified lazy_split = unspecified;
+ }
}
namespace std {
@@ -254,6 +268,7 @@
#include <__ranges/enable_view.h>
#include <__ranges/iota_view.h>
#include <__ranges/join_view.h>
+#include <__ranges/lazy_split_view.h>
#include <__ranges/rbegin.h>
#include <__ranges/ref_view.h>
#include <__ranges/rend.h>