diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -254,6 +254,8 @@ __functional/unary_negate.h __functional/unwrap_ref.h __functional/weak_result_type.h + __fwd/span.h + __fwd/string_view.h __hash_table __ios/fpos.h __iterator/access.h diff --git a/libcxx/include/__fwd/span.h b/libcxx/include/__fwd/span.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__fwd/span.h @@ -0,0 +1,37 @@ +// -*- 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_FWD_SPAN_H +#define _LIBCPP_FWD_SPAN_H + +#include <__config> +#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 _LIBCPP_STD_VER > 17 + +inline constexpr size_t dynamic_extent = numeric_limits::max(); +template class span; + +#endif + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP_FWD_SPAN_H diff --git a/libcxx/include/__fwd/string_view.h b/libcxx/include/__fwd/string_view.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__fwd/string_view.h @@ -0,0 +1,37 @@ +// -*- 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_FWD_STRING_VIEW_H +#define _LIBCPP_FWD_STRING_VIEW_H + +#include <__config> +#include // char_traits + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template > +class _LIBCPP_TEMPLATE_VIS basic_string_view; + +typedef basic_string_view string_view; +#ifndef _LIBCPP_HAS_NO_CHAR8_T +typedef basic_string_view u8string_view; +#endif +typedef basic_string_view u16string_view; +typedef basic_string_view u32string_view; +#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS +typedef basic_string_view wstring_view; +#endif + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_FWD_STRING_VIEW_H diff --git a/libcxx/include/__ranges/take_view.h b/libcxx/include/__ranges/take_view.h --- a/libcxx/include/__ranges/take_view.h +++ b/libcxx/include/__ranges/take_view.h @@ -9,18 +9,29 @@ #ifndef _LIBCPP___RANGES_TAKE_VIEW_H #define _LIBCPP___RANGES_TAKE_VIEW_H +#include <__algorithm/min.h> #include <__algorithm/ranges_min.h> #include <__config> +#include <__functional/bind_back.h> +#include <__fwd/span.h> +#include <__fwd/string_view.h> #include <__iterator/concepts.h> #include <__iterator/counted_iterator.h> #include <__iterator/default_sentinel.h> +#include <__iterator/distance.h> #include <__iterator/iterator_traits.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/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 @@ -115,7 +126,6 @@ } } - _LIBCPP_HIDE_FROM_ABI constexpr auto size() requires sized_range<_View> { auto __n = ranges::size(__base_); @@ -174,6 +184,148 @@ template inline constexpr bool enable_borrowed_range> = enable_borrowed_range<_Tp>; +namespace views { +namespace __take { + +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 __is_iota_specialization = false; + +template +inline constexpr bool __is_iota_specialization> = true; + +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 = subrange<_Iter>; +}; + +template +using __passthrough_type_t = typename __passthrough_type<_Tp>::type; + +struct __fn { + // [range.take.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.take.overview]: the `span | basic_string_view | subrange` 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), + ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)) + ))) + -> decltype( __passthrough_type_t<_RawRange>( + // Note: deliberately not forwarding `__rng` to guard against double moves. + ranges::begin(__rng), + ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)) + )) + { return __passthrough_type_t<_RawRange>( + ranges::begin(__rng), + ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)) + ); } + + // [range.take.overview]: the `iota_view` 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_iota_specialization<_RawRange>) + [[nodiscard]] _LIBCPP_HIDE_FROM_ABI + constexpr auto operator()(_Range&& __rng, _Np&& __n) const + noexcept(noexcept(ranges::iota_view( + *ranges::begin(__rng), + *ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)) + ))) + -> decltype( ranges::iota_view( + // Note: deliberately not forwarding `__rng` to guard against double moves. + *ranges::begin(__rng), + *ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)) + )) + { return ranges::iota_view( + *ranges::begin(__rng), + *ranges::begin(__rng) + std::min<_Dist>(ranges::distance(__rng), std::forward<_Np>(__n)) + ); } + + // [range.take.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_iota_specialization<_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(take_view(std::forward<_Range>(__range), std::forward<_Np>(__n)))) + -> decltype( take_view(std::forward<_Range>(__range), std::forward<_Np>(__n))) + { return take_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 __take + +inline namespace __cpo { + inline constexpr auto take = __take::__fn{}; +} // namespace __cpo +} // namespace views + } // namespace ranges #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -919,6 +919,7 @@ header "span" export ranges.__ranges.enable_borrowed_range export version + module span_fwd { private header "__fwd/span.h" } } module sstream { header "sstream" @@ -950,6 +951,7 @@ export initializer_list export __string export * + module string_view_fwd { private header "__fwd/string_view.h" } } module strstream { header "strstream" diff --git a/libcxx/include/span b/libcxx/include/span --- a/libcxx/include/span +++ b/libcxx/include/span @@ -130,6 +130,7 @@ #include <__assert> // all public C++ headers provide the assertion handler #include <__config> #include <__debug> +#include <__fwd/span.h> #include <__iterator/concepts.h> #include <__iterator/wrap_iter.h> #include <__ranges/concepts.h> @@ -155,9 +156,6 @@ #if _LIBCPP_STD_VER > 17 -inline constexpr size_t dynamic_extent = numeric_limits::max(); -template class span; - template struct __is_std_array : false_type {}; diff --git a/libcxx/include/string_view b/libcxx/include/string_view --- a/libcxx/include/string_view +++ b/libcxx/include/string_view @@ -199,6 +199,7 @@ #include <__algorithm/min.h> #include <__assert> // all public C++ headers provide the assertion handler #include <__config> +#include <__fwd/string_view.h> #include <__ranges/concepts.h> #include <__ranges/data.h> #include <__ranges/enable_borrowed_range.h> @@ -223,19 +224,6 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template > - class _LIBCPP_TEMPLATE_VIS basic_string_view; - -typedef basic_string_view string_view; -#ifndef _LIBCPP_HAS_NO_CHAR8_T -typedef basic_string_view u8string_view; -#endif -typedef basic_string_view u16string_view; -typedef basic_string_view u32string_view; -#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS -typedef basic_string_view wstring_view; -#endif - // TODO: This is a workaround for some vendors to carry a downstream diff to accept `nullptr` in // string_view constructors. This can be refactored when this exact form isn't needed anymore. template diff --git a/libcxx/test/libcxx/lint/lint_modulemap.sh.py b/libcxx/test/libcxx/lint/lint_modulemap.sh.py old mode 100644 new mode 100755 --- a/libcxx/test/libcxx/lint/lint_modulemap.sh.py +++ b/libcxx/test/libcxx/lint/lint_modulemap.sh.py @@ -26,6 +26,9 @@ elif re.match(r'^\s*module (\w+)\s+[{] private header "__\w+/\1[.]h" [}]', line): # It's a private submodule, such as <__utility/swap.h>. pass + elif re.match(r'^\s*module (\w+)_fwd\s+[{] private header "__fwd/\1[.]h" [}]', line): + # It's a private submodule with forward declarations, such as <__fwd/span.h>. + pass else: okay = False print("LINE DOESN'T MATCH REGEX in libcxx/include/module.modulemap!") 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 @@ -286,6 +286,8 @@ #include <__functional/unary_negate.h> // expected-error@*:* {{use of private header from outside its module: '__functional/unary_negate.h'}} #include <__functional/unwrap_ref.h> // expected-error@*:* {{use of private header from outside its module: '__functional/unwrap_ref.h'}} #include <__functional/weak_result_type.h> // expected-error@*:* {{use of private header from outside its module: '__functional/weak_result_type.h'}} +#include <__fwd/span.h> // expected-error@*:* {{use of private header from outside its module: '__fwd/span.h'}} +#include <__fwd/string_view.h> // expected-error@*:* {{use of private header from outside its module: '__fwd/string_view.h'}} #include <__ios/fpos.h> // expected-error@*:* {{use of private header from outside its module: '__ios/fpos.h'}} #include <__iterator/access.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/access.h'}} #include <__iterator/advance.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/advance.h'}} diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/cpo.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/cpo.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/cpo.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/cpo.compile.pass.cpp @@ -91,8 +91,9 @@ //static_assert(test(std::views::elements<0>, pairs)); static_assert(test(std::views::filter, a, [](int x){ return x < 10; })); //static_assert(test(std::views::join, arrays)); +//static_assert(test(std::views::split, a, 4)); static_assert(test(std::views::lazy_split, a, 4)); static_assert(test(std::views::reverse, a)); -//static_assert(test(std::views::take, a, 10)); +static_assert(test(std::views::take, a, 10)); //static_assert(test(std::views::take_while, a, [](int x){ return x < 10; })); static_assert(test(std::views::transform, a, [](int x){ return x + 1; })); 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 new file mode 100644 --- /dev/null +++ b/libcxx/test/std/ranges/range.adaptors/range.take/adaptor.pass.cpp @@ -0,0 +1,207 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// std::views::take + +#include + +#include +#include +#include +#include +#include +#include "test_iterators.h" +#include "types.h" + +template +concept CanBePiped = requires (View&& view, T&& t) { + { std::forward(view) | std::forward(t) }; +}; + +struct SizedView : std::ranges::view_base { + int* begin_ = nullptr; + int* end_ = nullptr; + constexpr SizedView(int* begin, int* end) : begin_(begin), end_(end) {} + + constexpr auto begin() const { return forward_iterator(begin_); } + constexpr auto end() const { return sized_sentinel>(forward_iterator(end_)); } +}; +static_assert(std::ranges::forward_range); +static_assert(std::ranges::sized_range); +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); +} + +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. + { + using SomeView = SizedView; + + // Test `view | views::take` + { + SomeView view(buf, buf + N); + std::same_as> decltype(auto) result = view | std::views::take(3); + assert(result.base().begin_ == buf); + assert(result.base().end_ == buf + N); + assert(result.size() == 3); + } + + // Test `adaptor | views::take` + { + SomeView view(buf, buf + N); + auto f = [](int i) { return i; }; + auto const partial = std::views::transform(f) | std::views::take(3); + + using Result = std::ranges::take_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); + } + + // Test `views::take | adaptor` + { + SomeView view(buf, buf + N); + auto f = [](int i) { return i; }; + auto const partial = std::views::take(3) | 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_ == buf); + assert(result.base().base().end_ == buf + N); + assert(result.size() == 3); + } + + // 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::same_as); + } + + // `views::take(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); + } + + // `views::take(span, n)` returns a `span`. + { + std::span s(buf); + std::same_as decltype(auto) result = s | std::views::take(3); + assert(result.size() == 3); + } + + // `views::take(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); + } + + // `views::take(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::u32string_view sv = U"abcdef"; + std::same_as decltype(auto) result = sv | std::views::take(3); + assert(result.size() == 3); + } + } + + // `views::take(subrange, n)` returns a `subrange`. + { + 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); + } + + // `views::take(subrange, n)` doesn't return a `subrange` if it's not a random access range. + { + SizedView v(buf, buf + N); + auto subrange = std::ranges::subrange(v.begin(), v.end()); + + using Result = std::ranges::take_view, + sized_sentinel>>>; + std::same_as decltype(auto) result = subrange | std::views::take(3); + assert(result.size() == 3); + } + + // `views::take(subrange, n)` returns a `subrange` with all default template arguments. + { + std::ranges::subrange, std::ranges::subrange_kind::sized> subrange; + + using Result = std::ranges::subrange; + [[maybe_unused]] std::same_as decltype(auto) result = subrange | std::views::take(3); + } + + // `views::take(iota_view, n)` returns an `iota_view`. + { + 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); + } + + // When the size of the input range `s` is shorter than `n`, only `s` elements are taken. + { + test_small_range(std::span(buf)); + test_small_range(std::string_view("abcdef")); + test_small_range(std::ranges::subrange(buf, buf + N)); + 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 + // never invoked. There is no good use case for it, but it's valid. + { + struct X { }; + [[maybe_unused]] auto partial = std::views::take(X{}); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +}