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 @@ -168,7 +168,7 @@ "`P1115R3 `__","LWG","Improving the Return Value of Erase-Like Algorithms II: Free erase/erase if","Prague","|Complete|","11.0" "`P1243R4 `__","LWG","Rangify New Algorithms","Prague","* *","" "`P1460R1 `__","LWG","Mandating the Standard Library: Clause 20 - Utilities library","Prague","* *","" -"`P1739R4 `__","LWG","Avoid template bloat for safe_ranges in combination with ""subrange-y"" view adaptors","Prague","* *","" +"`P1739R4 `__","LWG","Avoid template bloat for safe_ranges in combination with ""subrange-y"" view adaptors","Prague","|Complete|","15.0" "`P1831R1 `__","LWG","Deprecating volatile: library","Prague","* *","" "`P1868R2 `__","LWG","width: clarifying units of width and precision in std::format","Prague","|Complete|","14.0" "`P1908R1 `__","CWG","Reserving Attribute Namespaces for Future Use","Prague","* *","" 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 @@ -107,7 +107,7 @@ `3293 `__,"``move_iterator operator+()`` has incorrect constraints","October 2021","|Complete|","15.0","|ranges|" `3361 `__,"``safe_range`` case","October 2021","|Nothing To Do|","","|ranges|" `3392 `__,"``ranges::distance()`` cannot be used on a move-only iterator with a sized sentinel","October 2021","|Complete|","14.0","|ranges|" -`3407 `__,"Some problems with the wording changes of P1739R4","October 2021","","","|ranges|" +`3407 `__,"Some problems with the wording changes of P1739R4","October 2021","|Complete|","15.0","|ranges|" `3422 `__,"Issues of ``seed_seq``'s constructors","October 2021","|Complete|","14.0" `3470 `__,"``convertible-to-non-slicing`` seems to reject valid case","October 2021","|Complete|","14.0","|ranges|" `3480 `__,"``directory_iterator`` and ``recursive_directory_iterator`` are not C++20 ranges","October 2021","|Complete|","14.0","|ranges|" diff --git a/libcxx/docs/Status/RangesIssues.csv b/libcxx/docs/Status/RangesIssues.csv --- a/libcxx/docs/Status/RangesIssues.csv +++ b/libcxx/docs/Status/RangesIssues.csv @@ -12,7 +12,7 @@ `P1523R1 `__,Views And Size Types,, `P1638R1 `__,basic_istream_view::iterator Should Not Be Copyable,, `P1716R3 `__,Range Comparison Algorithms Are Over-Constrained,, -`P1739R4 `__,Avoiding Template Bloat For Ranges,, +`P1739R4 `__,Avoiding Template Bloat For Ranges,|Complete|,15.0 `P1862R1 `__,Range Adaptors For Non-Copyable Iterators,, `P1870R1 `__,safe_range,, `P1871R1 `__,disable_sized_sentinel_for,|Complete|,14.0 diff --git a/libcxx/include/__ranges/drop_view.h b/libcxx/include/__ranges/drop_view.h --- a/libcxx/include/__ranges/drop_view.h +++ b/libcxx/include/__ranges/drop_view.h @@ -9,18 +9,29 @@ #ifndef _LIBCPP___RANGES_DROP_VIEW_H #define _LIBCPP___RANGES_DROP_VIEW_H +#include <__algorithm/min.h> #include <__assert> #include <__config> +#include <__functional/bind_back.h> +#include <__fwd/span.h> +#include <__fwd/string_view.h> #include <__iterator/concepts.h> +#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__iterator/next.h> #include <__ranges/access.h> #include <__ranges/all.h> #include <__ranges/concepts.h> +#include <__ranges/empty_view.h> #include <__ranges/enable_borrowed_range.h> +#include <__ranges/iota_view.h> #include <__ranges/non_propagating_cache.h> +#include <__ranges/range_adaptor.h> #include <__ranges/size.h> +#include <__ranges/subrange.h> #include <__ranges/view_interface.h> +#include <__utility/auto_cast.h> +#include <__utility/forward.h> #include <__utility/move.h> #include #include @@ -113,13 +124,182 @@ { return __size(*this); } }; - template - drop_view(_Range&&, range_difference_t<_Range>) -> drop_view>; +template +drop_view(_Range&&, range_difference_t<_Range>) -> drop_view>; + +template +inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; + +namespace views { +namespace __drop { + +template +inline constexpr bool __is_empty_view = false; + +template +inline constexpr bool __is_empty_view> = true; + +template +inline constexpr bool __is_passthrough_specialization = false; + +template +inline constexpr bool __is_passthrough_specialization> = true; + +template +inline constexpr bool __is_passthrough_specialization> = true; + +template +inline constexpr bool __is_passthrough_specialization> = true; + +template +inline constexpr bool __store_size = false; + +template +inline constexpr bool __store_size> = + // The definition of `subrange::StoreSize` (which is exposition-only and private). + _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _Iter>; + +template +inline constexpr bool __is_passthrough_specialization> = + !__store_size>; + +template +inline constexpr bool __is_subrange_specialization_with_store_size = false; + +template +inline constexpr bool __is_subrange_specialization_with_store_size> = + __store_size>; + +template +struct __passthrough_type; + +template +struct __passthrough_type> { + using type = span<_Tp>; +}; + +template +struct __passthrough_type> { + using type = basic_string_view<_CharT, _Traits>; +}; + +template +struct __passthrough_type> { + using type = iota_view<_Np, _Bound>; +}; + +template +struct __passthrough_type> { + using type = subrange<_Iter, _Sent, _Kind>; +}; + +template +using __passthrough_type_t = typename __passthrough_type<_Tp>::type; + +struct __fn { + // [range.drop.overview]: the `empty_view` case. + template > _Np> + requires __is_empty_view> + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI + constexpr auto operator()(_Range&& __range, _Np&&) const + noexcept(noexcept(_LIBCPP_AUTO_CAST(std::forward<_Range>(__range)))) + -> decltype( _LIBCPP_AUTO_CAST(std::forward<_Range>(__range))) + { return _LIBCPP_AUTO_CAST(std::forward<_Range>(__range)); } + + // [range.drop.overview]: the `span | basic_string_view | iota_view | subrange (StoreSize == false)` case. + template > _Np, + class _RawRange = remove_cvref_t<_Range>, + class _Dist = range_difference_t<_Range>> + requires (!__is_empty_view<_RawRange> && + random_access_range<_RawRange> && + sized_range<_RawRange> && + __is_passthrough_specialization<_RawRange>) + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI + constexpr auto operator()(_Range&& __rng, _Np&& __n) const + noexcept(noexcept(__passthrough_type_t<_RawRange>( + ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)), + ranges::end(__rng) + ))) + -> decltype( __passthrough_type_t<_RawRange>( + // Note: deliberately not forwarding `__rng` to guard against double moves. + ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)), + ranges::end(__rng) + )) + { return __passthrough_type_t<_RawRange>( + ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)), + ranges::end(__rng) + ); } + + // [range.drop.overview]: the `subrange (StoreSize == true)` case. + template > _Np, + class _RawRange = remove_cvref_t<_Range>, + class _Dist = range_difference_t<_Range>> + requires (!__is_empty_view<_RawRange> && + random_access_range<_RawRange> && + sized_range<_RawRange> && + __is_subrange_specialization_with_store_size<_RawRange>) + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI + constexpr auto operator()(_Range&& __rng, _Np&& __n) const + noexcept(noexcept(_RawRange( + ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)), + ranges::end(__rng), + std::__to_unsigned_like(ranges::distance(__rng) - + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n))) + ))) + -> decltype( _RawRange( + // Note: deliberately not forwarding `__rng` to guard against double moves. + ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)), + ranges::end(__rng), + std::__to_unsigned_like(ranges::distance(__rng) - + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n))) + )) + { + auto clamped = std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)); + return _RawRange( + ranges::begin(__rng) + clamped, + ranges::end(__rng), + std::__to_unsigned_like(ranges::distance(__rng) - clamped) + );} + + // [range.drop.overview]: the "otherwise" case. + template > _Np, + class _RawRange = remove_cvref_t<_Range>> + // Note: without specifically excluding the other cases, GCC sees this overload as ambiguous with the other + // overloads. + requires (!(__is_empty_view<_RawRange> || + (__is_subrange_specialization_with_store_size<_RawRange> && + sized_range<_RawRange> && + random_access_range<_RawRange>) || + (__is_passthrough_specialization<_RawRange> && + sized_range<_RawRange> && + random_access_range<_RawRange>) + )) + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI + constexpr auto operator()(_Range&& __range, _Np&& __n) const + noexcept(noexcept(drop_view(std::forward<_Range>(__range), std::forward<_Np>(__n)))) + -> decltype( drop_view(std::forward<_Range>(__range), std::forward<_Np>(__n))) + { return drop_view(std::forward<_Range>(__range), std::forward<_Np>(__n)); } + + template + requires constructible_from, _Np> + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI + constexpr auto operator()(_Np&& __n) const + noexcept(is_nothrow_constructible_v, _Np>) + { return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Np>(__n))); } +}; + +} // namespace __drop + +inline namespace __cpo { + inline constexpr auto drop = __drop::__fn{}; +} // namespace __cpo +} // namespace views - template - inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; } // namespace ranges + #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/test/std/ranges/range.adaptors/range.take/adaptor.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.drop/adaptor.pass.cpp copy from libcxx/test/std/ranges/range.adaptors/range.take/adaptor.pass.cpp copy to libcxx/test/std/ranges/range.adaptors/range.drop/adaptor.pass.cpp --- a/libcxx/test/std/ranges/range.adaptors/range.take/adaptor.pass.cpp +++ b/libcxx/test/std/ranges/range.adaptors/range.drop/adaptor.pass.cpp @@ -9,17 +9,17 @@ // UNSUPPORTED: c++03, c++11, c++14, c++17 // UNSUPPORTED: libcpp-has-no-incomplete-ranges -// std::views::take +// std::views::drop #include #include #include #include +#include #include #include #include "test_iterators.h" -#include "types.h" template concept CanBePiped = requires (View&& view, T&& t) { @@ -38,150 +38,182 @@ static_assert(std::ranges::sized_range); static_assert(std::ranges::view); +struct SizedViewWithUnsizedSentinel : std::ranges::view_base { + using iterator = random_access_iterator; + using sentinel = sentinel_wrapper>; + + int* begin_ = nullptr; + int* end_ = nullptr; + constexpr SizedViewWithUnsizedSentinel(int* begin, int* end) : begin_(begin), end_(end) {} + + constexpr auto begin() const { return iterator(begin_); } + constexpr auto end() const { return sentinel(iterator(end_)); } + constexpr size_t size() const { return end_ - begin_; } +}; +static_assert(std::ranges::random_access_range); +static_assert(std::ranges::sized_range); +static_assert(!std::sized_sentinel_for); +static_assert(std::ranges::view); + template constexpr void test_small_range(const T& input) { constexpr int N = 100; auto size = std::ranges::size(input); - - auto result = input | std::views::take(N); assert(size < N); - assert(result.size() == size); + + auto result = input | std::views::drop(N); + assert(result.empty()); } constexpr bool test() { constexpr int N = 8; int buf[N] = {1, 2, 3, 4, 5, 6, 7, 8}; - // Test that `std::views::take` is a range adaptor. + // Test that `std::views::drop` is a range adaptor. { using SomeView = SizedView; - // Test `view | views::take` + // Test `view | views::drop` { SomeView view(buf, buf + N); - std::same_as> decltype(auto) result = view | std::views::take(3); + std::same_as> decltype(auto) result = view | std::views::drop(3); assert(result.base().begin_ == buf); assert(result.base().end_ == buf + N); - assert(result.size() == 3); + assert(base(result.begin()) == buf + 3); + assert(base(base(result.end())) == buf + N); + assert(result.size() == 5); } - // Test `adaptor | views::take` + // Test `adaptor | views::drop` { SomeView view(buf, buf + N); auto f = [](int i) { return i; }; - auto const partial = std::views::transform(f) | std::views::take(3); + auto const partial = std::views::transform(f) | std::views::drop(3); - using Result = std::ranges::take_view>; + using Result = std::ranges::drop_view>; std::same_as decltype(auto) result = partial(view); assert(result.base().base().begin_ == buf); assert(result.base().base().end_ == buf + N); - assert(result.size() == 3); + assert(base(result.begin().base()) == buf + 3); + assert(base(base(result.end().base())) == buf + N); + assert(result.size() == 5); } - // Test `views::take | adaptor` + // Test `views::drop | adaptor` { SomeView view(buf, buf + N); auto f = [](int i) { return i; }; - auto const partial = std::views::take(3) | std::views::transform(f); + auto const partial = std::views::drop(3) | std::views::transform(f); - using Result = std::ranges::transform_view, decltype(f)>; + using Result = std::ranges::transform_view, decltype(f)>; std::same_as decltype(auto) result = partial(view); assert(result.base().base().begin_ == buf); assert(result.base().base().end_ == buf + N); - assert(result.size() == 3); + assert(base(result.begin().base()) == buf + 3); + assert(base(base(result.end().base())) == buf + N); + assert(result.size() == 5); } // Check SFINAE friendliness { struct NotAView { }; - 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(!CanBePiped); + 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(!CanBePiped); } } { - static_assert(std::same_as); + static_assert(std::same_as); } - // `views::take(empty_view, n)` returns an `empty_view`. + // `views::drop(empty_view, n)` returns an `empty_view`. { using Result = std::ranges::empty_view; - [[maybe_unused]] std::same_as decltype(auto) result = std::views::empty | std::views::take(3); + [[maybe_unused]] std::same_as decltype(auto) result = std::views::empty | std::views::drop(3); } - // `views::take(span, n)` returns a `span`. + // `views::drop(span, n)` returns a `span`. { std::span s(buf); - std::same_as decltype(auto) result = s | std::views::take(3); + std::same_as decltype(auto) result = s | std::views::drop(5); assert(result.size() == 3); } - // `views::take(span, n)` returns a `span` with a dynamic extent, regardless of the input `span`. + // `views::drop(span, n)` returns a `span` with a dynamic extent, regardless of the input `span`. { std::span s(buf); - std::same_as> decltype(auto) result = s | std::views::take(3); - assert(result.size() == 3); + std::same_as> decltype(auto) result = s | std::views::drop(3); + assert(result.size() == 5); } - // `views::take(string_view, n)` returns a `string_view`. + // `views::drop(string_view, n)` returns a `string_view`. { { std::string_view sv = "abcdef"; - std::same_as decltype(auto) result = sv | std::views::take(3); - assert(result.size() == 3); + std::same_as decltype(auto) result = sv | std::views::drop(2); + assert(result.size() == 4); } { std::u32string_view sv = U"abcdef"; - std::same_as decltype(auto) result = sv | std::views::take(3); - assert(result.size() == 3); + std::same_as decltype(auto) result = sv | std::views::drop(2); + assert(result.size() == 4); } } - // `views::take(subrange, n)` returns a `subrange`. + // `views::drop(iota_view, n)` returns an `iota_view`. { - auto subrange = std::ranges::subrange(buf, buf + N); - using Result = std::ranges::subrange; - std::same_as decltype(auto) result = subrange | std::views::take(3); - assert(result.size() == 3); + auto iota = std::views::iota(1, 8); + // The second template argument of the resulting `iota_view` is different because it has to be able to hold + // the `range_difference_t` of the input `iota_view`. + using Result = std::ranges::iota_view; + std::same_as decltype(auto) result = iota | std::views::drop(3); + assert(result.size() == 4); + assert(*result.begin() == 4); + assert(*std::ranges::next(result.begin(), 3) == 7); } - // `views::take(subrange, n)` doesn't return a `subrange` if it's not a random access range. + // `views::drop(subrange, n)` returns a `subrange` when `subrange::StoreSize == false`. { - SizedView v(buf, buf + N); - auto subrange = std::ranges::subrange(v.begin(), v.end()); + auto subrange = std::ranges::subrange(buf, buf + N); + LIBCPP_STATIC_ASSERT(!std::ranges::views::__drop::__store_size); - using Result = std::ranges::take_view, - sized_sentinel>>>; - std::same_as decltype(auto) result = subrange | std::views::take(3); - assert(result.size() == 3); + using Result = std::ranges::subrange; + std::same_as decltype(auto) result = subrange | std::views::drop(3); + assert(result.size() == 5); } - // `views::take(subrange, n)` returns a `subrange` with all default template arguments. + // `views::drop(subrange, n)` returns a `subrange` when `subrange::StoreSize == true`. { - std::ranges::subrange, std::ranges::subrange_kind::sized> subrange; + using View = SizedViewWithUnsizedSentinel; + View view(buf, buf + N); - using Result = std::ranges::subrange; - [[maybe_unused]] std::same_as decltype(auto) result = subrange | std::views::take(3); + using Subrange = std::ranges::subrange; + auto subrange = Subrange(view.begin(), view.end(), std::ranges::distance(view.begin(), view.end())); + LIBCPP_STATIC_ASSERT(std::ranges::views::__drop::__store_size); + + std::same_as decltype(auto) result = subrange | std::views::drop(3); + assert(result.size() == 5); } - // `views::take(iota_view, n)` returns an `iota_view`. + // `views::drop(subrange, n)` doesn't return a `subrange` if it's not a random access range. { - auto iota = std::views::iota(1, 8); - // The second template argument of the resulting `iota_view` is different because it has to be able to hold - // the `range_difference_t` of the input `iota_view`. - using Result = std::ranges::iota_view>; - std::same_as decltype(auto) result = iota | std::views::take(3); - assert(result.size() == 3); + SizedView v(buf, buf + N); + auto subrange = std::ranges::subrange(v.begin(), v.end()); + + using Result = std::ranges::drop_view, + sized_sentinel>>>; + std::same_as decltype(auto) result = subrange | std::views::drop(3); + assert(result.size() == 5); } - // When the size of the input range `s` is shorter than `n`, only `s` elements are taken. + // When the size of the input range `s` is shorter than `n`, an `empty_view` is returned. { test_small_range(std::span(buf)); test_small_range(std::string_view("abcdef")); @@ -189,11 +221,11 @@ test_small_range(std::views::iota(1, 8)); } - // Test that it's possible to call `std::views::take` with any single argument as long as the resulting closure is + // Test that it's possible to call `std::views::drop` with any single argument as long as the resulting closure is // never invoked. There is no good use case for it, but it's valid. { struct X { }; - [[maybe_unused]] auto partial = std::views::take(X{}); + [[maybe_unused]] auto partial = std::views::drop(X{}); } return true; diff --git a/libcxx/test/std/ranges/range.adaptors/range.take/adaptor.pass.cpp b/libcxx/test/std/ranges/range.adaptors/range.take/adaptor.pass.cpp --- a/libcxx/test/std/ranges/range.adaptors/range.take/adaptor.pass.cpp +++ b/libcxx/test/std/ranges/range.adaptors/range.take/adaptor.pass.cpp @@ -13,13 +13,12 @@ #include -#include #include #include +#include #include #include #include "test_iterators.h" -#include "types.h" template concept CanBePiped = requires (View&& view, T&& t) {