diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -198,6 +198,7 @@ __ranges/enable_borrowed_range.h __ranges/enable_view.h __ranges/iota_view.h + __ranges/lazy_split_view.h __ranges/non_propagating_cache.h __ranges/ref_view.h __ranges/single_view.h diff --git a/libcxx/include/__ranges/lazy_split_view.h b/libcxx/include/__ranges/lazy_split_view.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__ranges/lazy_split_view.h @@ -0,0 +1,319 @@ +// -*- 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 <__config> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> +#include <__iterator/iterator_traits.h> +#include <__ranges/copyable_box.h> +#include <__ranges/single_view.h> +#include <__ranges/enable_borrowed_range.h> +#include <__ranges/view_interface.h> +#include +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if !defined(_LIBCPP_HAS_NO_RANGES) + +// REVIEW-NOTE: Will be its own patch. Not up for review. + +template +concept indirectly_comparable = + indirect_binary_predicate<_Range, projected<_I1, _P1>, projected<_I2, _P2>>; + +// END-REVIEW-NOTE + +namespace ranges { + template struct __require_constant; + + template + concept __tiny_range = + sized_range<_Range> && + requires { typename __require_constant::size()>; } && + (remove_reference_t<_Range>::size() <= 1); + + template + requires view<_View> && view<_Pattern> && + indirectly_comparable, iterator_t<_Pattern>, ranges::equal_to> && + (forward_range<_View> || __tiny_range<_Pattern>) + class lazy_split_view : public view_interface> { + template struct __inner_iterator; + + // TODO: LWG issue: if there's no current iterator this is unimplementable as far as I can tell. + template + struct __current_iter_base {}; + + template + struct __current_iter_base<_Iter> { + _Iter __current_ = _Iter(); + }; + + template + struct __outer_iterator + : public __current_iter_base>> { + + private: + using _Parent = __maybe_const<_Const, lazy_split_view>; + using _Base = __maybe_const<_Const, _View>; + + public: + _Parent *__parent_ = nullptr; + bool __trailing_empty_ = false; + + using iterator_concept = conditional_t, forward_iterator_tag, input_iterator_tag>; + using iterator_category = input_iterator_tag; + using difference_type = range_difference_t<_Base>; + struct value_type + : view_interface { + private: + __outer_iterator __i_ = __outer_iterator(); + public: + value_type() = default; + constexpr explicit value_type(__outer_iterator __i) + : __i_(_VSTD::move(__i)) {} + + constexpr __inner_iterator<_Const> begin() const { return __inner_iterator<_Const>{__i_}; } + constexpr default_sentinel_t end() const { return default_sentinel; } + }; + + __outer_iterator() = default; // TODO: shouldn't this require that base iterator is default ctorable? + + constexpr explicit __outer_iterator(_Parent& __parent) + requires (!forward_range<_Base>) + : __parent_(_VSTD::addressof(__parent)) {} + + constexpr __outer_iterator(_Parent& __parent, iterator_t<_Base> __current) + requires forward_range<_Base> + : __parent_(_VSTD::addressof(__parent)), __current_(_VSTD::move(__current)) {} + + constexpr __outer_iterator(__outer_iterator __i) + requires _Const && convertible_to, iterator_t<_Base>> + : __parent_(__i.__parent_), __current_(_VSTD::move(__i.__current_)) {} + + constexpr value_type operator*() const { return value_type{*this}; } + + constexpr __outer_iterator& operator++() { + const auto __end = ranges::end(__parent_->__base_); + // LWG editorial: this should have a trailing underscore. + if (__current_ == __end) { + __trailing_empty_ = false; + return *this; + } + + const auto __srange = ranges::subrange{__parent_->__pattern_}; + const auto __pbegin = __srange.begin(); + const auto __pend = __srange.end(); + + if (__pbegin == __pend) { + ++__current_; + } else if (__tiny_range<_Pattern>) { + __current_ = _VSTD::find(_VSTD::move(__current_), __end, *__pbegin); + if (__current_ != __end) { + ++__current_; + if (__current_ == __end) + __trailing_empty_ = true; + } + } else { + do { + const auto [__b, __p] = _VSTD::mismatch(__current_, __end, __pbegin, __pend); + if (__p == __pend) { + __current_ = __b; + if (__current_ == __end) + __trailing_empty_ = true; + break; + } + } while (++__current_ != __end); + } + return *this; + } + + constexpr decltype(auto) operator++(int) { + if constexpr (forward_range<_Base>) { + auto __tmp = *this; + ++*this; + return __tmp; + } + ++*this; + } + + 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_; + } + + friend constexpr bool operator==(const __outer_iterator& __x, default_sentinel_t) { + return __x.__current_ == ranges::end(__x.__parent_->__base_) && !__x.__trailing_empty_; + } + }; + + template struct __inner_iterator { + private: + using _Base = __maybe_const<_Const, _View>; + __outer_iterator<_Const> __i_ = __outer_iterator<_Const>(); + bool __incremented_ = false; + + public: + using iterator_Concept = typename __outer_iterator<_Const>::iterator_concept; + using iterator_category = _If< + derived_from>::iterator_category, forward_iterator_tag>, + forward_iterator_tag, + typename iterator_traits>::iterator_category + >; + + using value_type = range_value_t<_Base>; + using difference_type = range_difference_t<_Base>; + + __inner_iterator() = default; + + constexpr explicit __inner_iterator(__outer_iterator<_Const> __i) + : __i_(_VSTD::move(__i)) {} + + constexpr const iterator_t<_Base>& base() const& { return __i_.__current_; } + constexpr iterator_t<_Base> base() && { return _VSTD::move(__i_.__current_); } + + constexpr decltype(auto) operator*() const { return *__i_.__current_; } + + constexpr __inner_iterator& operator++() { + __incremented_ = true; + + if constexpr (!forward_range<_Base>) { + if constexpr (_Pattern::size() == 0) { + return *this; + } + } + + ++__i_.__current_; + return *this; + } + constexpr decltype(auto) operator++(int) { + if constexpr (forward_range<_Base>) { + auto __tmp = *this; + ++*this; + return __tmp; + } + + ++*this; + } + + friend constexpr bool operator==(const __inner_iterator& __x, const __inner_iterator& __y) + requires forward_range<_Base> + { + return __x.__i_.__current_ == __y.__i_.__current_; + } + + friend constexpr bool operator==(const __inner_iterator& __x, default_sentinel_t) { + const auto __srange = ranges::subrange{__x.__i_.__parent_->__pattern_}; + auto __pcur = __srange.begin(); + const auto __pend = __srange.end(); + const auto __end = ranges::end(__x.__i_.__parent_->__base_); + + auto __cur = __x.__i_.__current_; + if (__cur == __end) return true; + if (__pcur == __pend) return __x.__incremented_; + + if constexpr (__tiny_range<_Pattern>) { + return *__cur == *__pcur; + } + + do { + if (*__cur != *__pcur) return false; + if (++__pcur == __pend) return true; + } while (++__cur != __end); + + return false; // TODO: shouldn't this be true? + } + + friend constexpr decltype(auto) iter_move(const __inner_iterator& __i) + noexcept(noexcept(ranges::iter_move(__i.__i_.__current_))) + { + return ranges::iter_move(__i.__i_.__current_); + } + + friend constexpr void iter_swap(const __inner_iterator& __x, const __inner_iterator& __y) + noexcept(noexcept(ranges::iter_swap(__x.__i_.__current_, __y.__i_.__current_))) + requires indirectly_swappable> + { + ranges::iter_swap(__x.__i_.__current_, __y.__i_.__current_); + } + }; + + public: + _View __base_ = _View(); + _Pattern __pattern_ = _Pattern(); + __non_propagating_cache> __current_; // TODO: only if not forward_range. + + lazy_split_view() + requires default_initializable<_View> && default_initializable<_Pattern> = default; + + constexpr lazy_split_view(_View __base, _Pattern __pattern) + : __base_(_VSTD::move(__base)), __pattern_(_VSTD::move(__pattern)) {} + + template + requires constructible_from<_View, views::all_t<_Range>> && + constructible_from<_Pattern, single_view>> + constexpr lazy_split_view(_Range&& __r, range_value_t<_Range> __e) + : __base_(views::all(_VSTD::forward<_Range>(__r))) + , __pattern_(ranges::single_view(_VSTD::move(__e))) {} + + constexpr _View base() const& requires copy_constructible<_View> { return __base_; } + constexpr _View base() && { return _VSTD::move(__base_); } + + constexpr auto begin() { + if constexpr (forward_range<_View>) + return __outer_iterator<__simple_view<_View>>{*this, ranges::begin(__base_)}; + else { + __current_.__set(ranges::begin(__base_)); + return __outer_iterator{*this}; + } + } + + constexpr auto begin() const requires forward_range<_View> && forward_range { + return __outer_iterator{*this, ranges::begin(__base_)}; + } + + constexpr auto end() requires forward_range<_View> && common_range<_View> { + return __outer_iterator<__simple_view<_View>>{*this, ranges::end(__base_)}; + } + + constexpr auto end() const { + if constexpr (forward_range<_View> && forward_range && common_range) { + return __outer_iterator{*this, ranges::end(__base_)}; + } + return default_sentinel; + } + }; + + template + lazy_split_view(_Range&&, _Pattern&&) -> lazy_split_view, views::all_t<_Pattern>>; + + template + lazy_split_view(_Range&&, range_value_t<_Range>) + -> lazy_split_view, single_view>>; +} // namespace ranges + +#endif // !defined(_LIBCPP_HAS_NO_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___RANGES_LAZY_SPLIT_VIEW_H diff --git a/libcxx/include/ranges b/libcxx/include/ranges --- a/libcxx/include/ranges +++ b/libcxx/include/ranges @@ -195,6 +195,7 @@ #include <__ranges/enable_borrowed_range.h> #include <__ranges/enable_view.h> #include <__ranges/iota_view.h> +#include <__ranges/lazy_split_view.h> #include <__ranges/ref_view.h> #include <__ranges/single_view.h> #include <__ranges/size.h>