diff --git a/libcxx/docs/ReleaseNotes.rst b/libcxx/docs/ReleaseNotes.rst --- a/libcxx/docs/ReleaseNotes.rst +++ b/libcxx/docs/ReleaseNotes.rst @@ -69,7 +69,8 @@ - P1035R7 - Input Range Adaptors - P2325R3 - Views should not be required to be default constructible - P2446R2 - ``views::as_rvalue`` -- P1020 - Smart pointer creation with default initialization +- P1020R1 - Smart pointer creation with default initialization +- P2210R2 - Superior String Splitting Improvements and New Features ----------------------------- diff --git a/libcxx/docs/Status/Cxx20Papers.csv b/libcxx/docs/Status/Cxx20Papers.csv --- a/libcxx/docs/Status/Cxx20Papers.csv +++ b/libcxx/docs/Status/Cxx20Papers.csv @@ -194,7 +194,7 @@ "","","","","","","" "`P2231R1 `__","LWG","Missing constexpr in std::optional and std::variant","June 2021","|Partial| [#note-P2231]_","13.0" "`P2325R3 `__","LWG","Views should not be required to be default constructible","June 2021","|Complete|","16.0","|ranges|" -"`P2210R2 `__","LWG","Superior String Splitting","June 2021","|In progress|","","|ranges|" +"`P2210R2 `__","LWG","Superior String Splitting","June 2021","|Complete|","16.0","|ranges|" "`P2216R3 `__","LWG","std::format improvements","June 2021","|Complete|","15.0" "`P2281R1 `__","LWG","Clarifying range adaptor objects","June 2021","|Complete|","14.0","|ranges|" "`P2328R1 `__","LWG","join_view should join all views of ranges","June 2021","|Complete|","15.0","|ranges|" diff --git a/libcxx/docs/Status/Cxx2bIssues.csv b/libcxx/docs/Status/Cxx2bIssues.csv --- a/libcxx/docs/Status/Cxx2bIssues.csv +++ b/libcxx/docs/Status/Cxx2bIssues.csv @@ -131,7 +131,7 @@ `3581 `__,"The range constructor makes ``basic_string_view`` not trivially move constructible","October 2021","|Complete|","14.0","|ranges|" `3585 `__,"``variant`` converting assignment with immovable alternative","October 2021","","" `3589 `__,"The ``const`` lvalue reference overload of ``get`` for ``subrange`` does not constrain ``I`` to be ``copyable`` when ``N == 0``","October 2021","|Complete|","14.0","|ranges|" -`3590 `__,"``split_view::base() const &`` is overconstrained","October 2021","","","|ranges|" +`3590 `__,"``split_view::base() const &`` is overconstrained","October 2021","|Complete|","16.0","|ranges|" `3591 `__,"``lazy_split_view::inner-iterator::base() &&`` invalidates outer iterators","October 2021","","","|ranges|" `3592 `__,"``lazy_split_view`` needs to check the simpleness of Pattern","October 2021","","","|ranges|" `3593 `__,"Several iterators' ``base() const &`` and ``lazy_split_view::outer-iterator::value_type::end()`` missing ``noexcept``","October 2021","","","|ranges|" diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -528,6 +528,7 @@ __ranges/reverse_view.h __ranges/single_view.h __ranges/size.h + __ranges/split_view.h __ranges/subrange.h __ranges/take_view.h __ranges/take_while_view.h diff --git a/libcxx/include/__ranges/split_view.h b/libcxx/include/__ranges/split_view.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__ranges/split_view.h @@ -0,0 +1,232 @@ +// -*- 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_SPLIT_VIEW_H +#define _LIBCPP___RANGES_SPLIT_VIEW_H + +#include <__algorithm/ranges_search.h> +#include <__concepts/constructible.h> +#include <__config> +#include <__functional/bind_back.h> +#include <__functional/ranges_operations.h> +#include <__iterator/indirectly_comparable.h> +#include <__iterator/iterator_traits.h> +#include <__memory/addressof.h> +#include <__ranges/access.h> +#include <__ranges/all.h> +#include <__ranges/concepts.h> +#include <__ranges/empty.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 <__type_traits/decay.h> +#include <__type_traits/is_nothrow_constructible.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 20 + +namespace ranges { + +template +struct __split_view_iterator; + +template +struct __split_view_sentinel; + +template + requires view<_View> && view<_Pattern> && + indirectly_comparable, iterator_t<_Pattern>, ranges::equal_to> +class split_view : public view_interface> { +private: + _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View(); + _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern(); + using _Cache = __non_propagating_cache>>; + _Cache __cached_begin_ = _Cache(); + + template + friend struct __split_view_iterator; + + template + friend struct __split_view_sentinel; + + using __iterator = __split_view_iterator<_View, _Pattern>; + using __sentinel = __split_view_sentinel<_View, _Pattern>; + + _LIBCPP_HIDE_FROM_ABI constexpr subrange> __find_next(iterator_t<_View> __it) { + auto [__begin, __end] = ranges::search(subrange(__it, ranges::end(__base_)), __pattern_); + if (__begin != ranges::end(__base_) && ranges::empty(__pattern_)) { + ++__begin; + ++__end; + } + return {__begin, __end}; + } + +public: + _LIBCPP_HIDE_FROM_ABI split_view() + requires default_initializable<_View> && default_initializable<_Pattern> + = default; + + _LIBCPP_HIDE_FROM_ABI constexpr split_view(_View __base, _Pattern __pattern) + : __base_(std::move(__base)), __pattern_(std::move((__pattern))) {} + + template + requires constructible_from<_View, views::all_t<_Range>> && + constructible_from<_Pattern, single_view>> + _LIBCPP_HIDE_FROM_ABI constexpr split_view(_Range&& __range, range_value_t<_Range> __elem) + : __base_(views::all(std::forward<_Range>(__range))), __pattern_(views::single(std::move(__elem))) {} + + _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 __iterator begin() { + if (!__cached_begin_.__has_value()) { + __cached_begin_.__emplace(__find_next(ranges::begin(__base_))); + } + return {*this, ranges::begin(__base_), *__cached_begin_}; + } + + _LIBCPP_HIDE_FROM_ABI constexpr auto end() { + if constexpr (common_range<_View>) { + return __iterator{*this, ranges::end(__base_), {}}; + } else { + return __sentinel{*this}; + } + } +}; + +template +split_view(_Range&&, _Pattern&&) -> split_view, views::all_t<_Pattern>>; + +template +split_view(_Range&&, range_value_t<_Range>) -> split_view, single_view>>; + +template +struct __split_view_iterator { +private: + split_view<_View, _Pattern>* __parent_ = nullptr; + _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __cur_ = iterator_t<_View>(); + _LIBCPP_NO_UNIQUE_ADDRESS subrange> __next_ = subrange>(); + bool __trailing_empty_ = false; + + template + friend struct __split_view_sentinel; + +public: + using iterator_concept = forward_iterator_tag; + using iterator_category = input_iterator_tag; + using value_type = subrange>; + using difference_type = range_difference_t<_View>; + + _LIBCPP_HIDE_FROM_ABI __split_view_iterator() = default; + + _LIBCPP_HIDE_FROM_ABI constexpr __split_view_iterator( + split_view<_View, _Pattern>& __parent, iterator_t<_View> __current, subrange> __next) + : __parent_(std::addressof(__parent)), __cur_(std::move(__current)), __next_(std::move(__next)) {} + + _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> base() const { return __cur_; } + + _LIBCPP_HIDE_FROM_ABI constexpr value_type operator*() const { return {__cur_, __next_.begin()}; } + + _LIBCPP_HIDE_FROM_ABI constexpr __split_view_iterator& operator++() { + __cur_ = __next_.begin(); + if (__cur_ != ranges::end(__parent_->__base_)) { + __cur_ = __next_.end(); + if (__cur_ == ranges::end(__parent_->__base_)) { + __trailing_empty_ = true; + __next_ = {__cur_, __cur_}; + } else { + __next_ = __parent_->__find_next(__cur_); + } + } else { + __trailing_empty_ = false; + } + return *this; + } + + _LIBCPP_HIDE_FROM_ABI constexpr __split_view_iterator operator++(int) { + auto __tmp = *this; + ++*this; + return __tmp; + } + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool + operator==(const __split_view_iterator& __x, const __split_view_iterator& __y) { + return __x.__cur_ == __y.__cur_ && __x.__trailing_empty_ == __y.__trailing_empty_; + } +}; + +template +struct __split_view_sentinel { +private: + _LIBCPP_NO_UNIQUE_ADDRESS sentinel_t<_View> __end_ = sentinel_t<_View>(); + + _LIBCPP_HIDE_FROM_ABI static constexpr bool + __equals(const __split_view_iterator<_View, _Pattern>& __x, const __split_view_sentinel& __y) { + return __x.__cur_ == __y.__end_ && !__x.__trailing_empty_; + } + +public: + _LIBCPP_HIDE_FROM_ABI __split_view_sentinel() = default; + + _LIBCPP_HIDE_FROM_ABI constexpr explicit __split_view_sentinel(split_view<_View, _Pattern>& __parent) + : __end_(ranges::end(__parent.__base_)) {} + + _LIBCPP_HIDE_FROM_ABI friend constexpr bool + operator==(const __split_view_iterator<_View, _Pattern>& __x, const __split_view_sentinel& __y) { + return __equals(__x, __y); + } +}; + +namespace views { +namespace __split_view { +struct __fn : __range_adaptor_closure<__fn> { + // clang-format off + template + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI + constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const + noexcept(noexcept(split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)))) + -> decltype( split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))) + { return split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)); } + // clang-format on + + template + requires constructible_from, _Pattern> + _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pattern&& __pattern) const + noexcept(is_nothrow_constructible_v, _Pattern>) { + return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pattern>(__pattern))); + } +}; +} // namespace __split_view + +inline namespace __cpo { +inline constexpr auto split = __split_view::__fn{}; +} // namespace __cpo +} // namespace views + +} // namespace ranges + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___RANGES_SPLIT_VIEW_H diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -1256,6 +1256,7 @@ module reverse_view { private header "__ranges/reverse_view.h" } module single_view { private header "__ranges/single_view.h" } module size { private header "__ranges/size.h" } + module split_view { private header "__ranges/split_view.h" } module subrange { private header "__ranges/subrange.h" diff --git a/libcxx/include/ranges b/libcxx/include/ranges --- a/libcxx/include/ranges +++ b/libcxx/include/ranges @@ -265,8 +265,15 @@ (forward_range || tiny-range) class lazy_split_view; + // [range.split], split view + template + requires view && view && + indirectly_comparable, iterator_t, ranges::equal_to> + class split_view; + namespace views { inline constexpr unspecified lazy_split = unspecified; + inline constexpr unspecified split = unspecified; } // [range.istream], istream view @@ -360,6 +367,7 @@ #include <__ranges/reverse_view.h> #include <__ranges/single_view.h> #include <__ranges/size.h> +#include <__ranges/split_view.h> #include <__ranges/subrange.h> #include <__ranges/take_view.h> #include <__ranges/take_while_view.h> diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -559,6 +559,7 @@ #include <__ranges/reverse_view.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/reverse_view.h'}} #include <__ranges/single_view.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/single_view.h'}} #include <__ranges/size.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/size.h'}} +#include <__ranges/split_view.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/split_view.h'}} #include <__ranges/subrange.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/subrange.h'}} #include <__ranges/take_view.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/take_view.h'}} #include <__ranges/take_while_view.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/take_while_view.h'}} diff --git a/libcxx/test/libcxx/ranges/range.adaptors/range.split/no_unique_address.compile.pass.cpp b/libcxx/test/libcxx/ranges/range.adaptors/range.split/no_unique_address.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/ranges/range.adaptors/range.split/no_unique_address.compile.pass.cpp @@ -0,0 +1,29 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 + +// clang-cl and cl currently don't support [[no_unique_address]] +// XFAIL: msvc + +// class split_view { +// _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View(); +// _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern(); +// }; + +#include + +#include "test_iterators.h" + +struct EmptyView : std::ranges::view_base { + int* begin() const; + int* end() const; +}; + +using SplitView = std::ranges::split_view; +static_assert(sizeof(SplitView) == sizeof(std::ranges::__non_propagating_cache>)); diff --git a/libcxx/test/std/ranges/range.adaptors/range.split/adaptor.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.split/adaptor.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.split/adaptor.pass.cpp @@ -0,0 +1,126 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 + +// std::views::split + +#include + +#include +#include +#include +#include +#include + +#include "test_iterators.h" + +template +concept CanBePiped = requires (View&& view, T&& t) { + { std::forward(view) | std::forward(t) }; +}; + +struct SomeView : std::ranges::view_base { + const std::string_view* v_; + constexpr SomeView(const std::string_view& v) : v_(&v) {} + constexpr auto begin() const { return v_->begin(); } + constexpr auto end() const { return v_->end(); } +}; + +struct NotAView { }; + +static_assert(!std::is_invocable_v); +static_assert(!std::is_invocable_v); +static_assert(!std::is_invocable_v); +static_assert( std::is_invocable_v); + +static_assert( CanBePiped); +static_assert( CanBePiped); +static_assert(!CanBePiped); +static_assert(!CanBePiped); + +static_assert(std::same_as); + +constexpr bool test() { + std::string_view input = "abc"; + std::string_view sep = "a"; + + // Test that `std::views::split` is a range adaptor. + + // Test `views::split(input, sep)`. + { + SomeView view(input); + + using Result = std::ranges::split_view; + std::same_as decltype(auto) result = std::views::split(view, sep); + assert(result.base().begin() == input.begin()); + assert(result.base().end() == input.end()); + } + + // Test `views::split(sep)(input)`. + { + SomeView view(input); + + using Result = std::ranges::split_view; + std::same_as decltype(auto) result = std::views::split(sep)(view); + assert(result.base().begin() == input.begin()); + assert(result.base().end() == input.end()); + } + + // Test `view | views::split`. + { + SomeView view(input); + + using Result = std::ranges::split_view; + std::same_as decltype(auto) result = view | std::views::split(sep); + assert(result.base().begin() == input.begin()); + assert(result.base().end() == input.end()); + } + + // Test `adaptor | views::split`. + { + SomeView view(input); + auto f = [](char c) { return c; }; + auto partial = std::views::transform(f) | std::views::split(sep); + + using Result = std::ranges::split_view, std::string_view>; + std::same_as decltype(auto) result = partial(view); + assert(result.base().base().begin() == input.begin()); + assert(result.base().base().end() == input.end()); + } + + // Test `views::split | adaptor`. + { + SomeView view(input); + auto f = [](auto v) { return v; }; + auto partial = std::views::split(sep) | std::views::transform(f); + + using Result = std::ranges::transform_view, decltype(f)>; + std::same_as decltype(auto) result = partial(view); + assert(result.base().base().begin() == input.begin()); + assert(result.base().base().end() == input.end()); + } + + // Test that one can call `std::views::split` with arbitrary stuff, as long as we + // don't try to actually complete the call by passing it a range. + // + // That makes no sense and we can't do anything with the result, but it's valid. + { + struct X { }; + [[maybe_unused]] auto partial = std::views::split(X{}); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.split/base.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.split/base.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.split/base.pass.cpp @@ -0,0 +1,103 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 + +// constexpr V base() const & requires copy_constructible { return base_; } +// constexpr V base() && { return std::move(base_); } + +#include +#include +#include +#include + +#include "MoveOnly.h" + +struct View : std::ranges::view_base { + int i; + int* begin() const; + int* end() const; +}; + +struct MoveOnlyView : View { + MoveOnly mo; +}; + +template +concept HasBase = requires(T&& t) { std::forward(t).base(); }; + +static_assert(HasBase const&>); +static_assert(HasBase&&>); + +static_assert(!HasBase const&>); +static_assert(HasBase&&>); + +constexpr bool test() { + // const & + { + const std::ranges::split_view sv{View{{}, 5}, View{{}, 0}}; + std::same_as decltype(auto) v = sv.base(); + assert(v.i == 5); + } + + // & + { + std::ranges::split_view sv{View{{}, 5}, View{{}, 0}}; + std::same_as decltype(auto) v = sv.base(); + assert(v.i == 5); + } + + // && + { + std::ranges::split_view sv{View{{}, 5}, View{{}, 0}}; + std::same_as decltype(auto) v = std::move(sv).base(); + assert(v.i == 5); + } + + // const && + { + std::ranges::split_view sv{View{{}, 5}, View{{}, 0}}; + std::same_as decltype(auto) v = std::move(sv).base(); + assert(v.i == 5); + } + + // move only + { + std::ranges::split_view sv{MoveOnlyView{{}, 5}, View{{}, 0}}; + std::same_as decltype(auto) v = std::move(sv).base(); + assert(v.mo.get() == 5); + } + + // LWG 3590 split_view::base() const & is overconstrained + { + struct CopyCtorButNotAssignable : std::ranges::view_base { + int i; + constexpr CopyCtorButNotAssignable(int ii) : i(ii) {} + constexpr CopyCtorButNotAssignable(const CopyCtorButNotAssignable&) = default; + constexpr CopyCtorButNotAssignable(CopyCtorButNotAssignable&&) = default; + constexpr CopyCtorButNotAssignable& operator=(CopyCtorButNotAssignable&&) = default; + constexpr CopyCtorButNotAssignable& operator=(const CopyCtorButNotAssignable&) = delete; + constexpr int* begin() const { return nullptr; } + constexpr int* end() const { return nullptr; } + }; + static_assert(std::copy_constructible); + static_assert(!std::copyable); + const std::ranges::split_view sv{ + CopyCtorButNotAssignable{5}, CopyCtorButNotAssignable{5}}; + std::same_as decltype(auto) v = sv.base(); + assert(v.i == 5); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + return 0; +} diff --git a/libcxx/test/std/ranges/range.adaptors/range.split/begin.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.split/begin.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.split/begin.pass.cpp @@ -0,0 +1,173 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 + +// constexpr auto begin(); + +#include +#include +#include +#include +#include + +#include "test_iterators.h" + +struct View : std::ranges::view_base { + int* begin() const; + int* end() const; +}; + +// Test that begin is not const +template +concept HasBegin = requires(T t) { t.begin(); }; + +static_assert(HasBegin>); +static_assert(!HasBegin>); + +template