diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -42,8 +42,8 @@ Write,copy_backward,Nikolas Klauser,`D122982 `_,✅ Write,move,Not assigned,n/a,Not started Write,move_backward,Not assigned,n/a,Not started -Write,fill,Not assigned,n/a,Not started -Write,fill_n,Not assigned,n/a,Not started +Write,fill,Nikolas Klauser,`D123462 `_,✅ +Write,fill_n,Nikolas Klauser,`D123462 `_,✅ Write,transform,Nikolas Klauser,`D122173 `_,✅ Write,generate,Not assigned,n/a,Not started Write,generate_n,Not assigned,n/a,Not started diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -72,6 +72,8 @@ __algorithm/ranges_copy_n.h __algorithm/ranges_count.h __algorithm/ranges_count_if.h + __algorithm/ranges_fill.h + __algorithm/ranges_fill_n.h __algorithm/ranges_find.h __algorithm/ranges_find_if.h __algorithm/ranges_find_if_not.h diff --git a/libcxx/include/__algorithm/ranges_fill.h b/libcxx/include/__algorithm/ranges_fill.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_fill.h @@ -0,0 +1,59 @@ +//===----------------------------------------------------------------------===// +// +// 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___ALGORITHM_RANGES_FILL_H +#define _LIBCPP___ALGORITHM_RANGES_FILL_H + +#include <__algorithm/ranges_fill_n.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __fill { +struct __fn { + template _Iter, sentinel_for<_Iter> _Sent> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, const _Type& __value) const { + if constexpr(random_access_iterator<_Iter>) { + return ranges::fill_n(__first, __last - __first, __value); + } else { + for (; __first != __last; ++__first) + *__first = __value; + return __first; + } + } + + template _Range> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __range, const _Type& __value) const { + return (*this)(ranges::begin(__range), ranges::end(__range), __value); + } +}; +} // namespace __fill + +inline namespace __cpo { + inline constexpr auto fill = __fill::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FILL_H diff --git a/libcxx/include/__algorithm/ranges_fill_n.h b/libcxx/include/__algorithm/ranges_fill_n.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_fill_n.h @@ -0,0 +1,48 @@ +//===----------------------------------------------------------------------===// +// +// 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___ALGORITHM_RANGES_FILL_N_H +#define _LIBCPP___ALGORITHM_RANGES_FILL_N_H + +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __fill_n { +struct __fn { + template _Iter> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, iter_difference_t<_Iter> __n, const _Type& __value) const { + for (; __n != 0; --__n) { + *__first = __value; + ++__first; + } + return __first; + } +}; +} // namespace __fill_n + +inline namespace __cpo { + inline constexpr auto fill_n = __fill_n::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FILL_N_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -283,6 +283,14 @@ requires permutable> constexpr borrowed_iterator_t ranges::reverse(R&& r); // since C++20 + template O, sentinel_for S> + constexpr O ranges::fill(O first, S last, const T& value); // since C++20 + + template R> + constexpr borrowed_iterator_t ranges::fill(R&& r, const T& value); // since C++20 + + template O> + constexpr O ranges::fill_n(O first, iter_difference_t n, const T& value); // since C++20 } constexpr bool // constexpr in C++20 @@ -1005,6 +1013,8 @@ #include <__algorithm/ranges_copy_n.h> #include <__algorithm/ranges_count.h> #include <__algorithm/ranges_count_if.h> +#include <__algorithm/ranges_fill.h> +#include <__algorithm/ranges_fill_n.h> #include <__algorithm/ranges_find.h> #include <__algorithm/ranges_find_if.h> #include <__algorithm/ranges_find_if_not.h> diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -304,6 +304,8 @@ module ranges_copy_n { private header "__algorithm/ranges_copy_n.h" } module ranges_count { private header "__algorithm/ranges_count.h" } module ranges_count_if { private header "__algorithm/ranges_count_if.h" } + module ranges_fill { private header "__algorithm/ranges_fill.h" } + module ranges_fill_n { private header "__algorithm/ranges_fill_n.h" } module ranges_find { private header "__algorithm/ranges_find.h" } module ranges_find_if { private header "__algorithm/ranges_find_if.h" } module ranges_find_if_not { private header "__algorithm/ranges_find_if_not.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 @@ -109,6 +109,8 @@ #include <__algorithm/ranges_copy_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_n.h'}} #include <__algorithm/ranges_count.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count.h'}} #include <__algorithm/ranges_count_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count_if.h'}} +#include <__algorithm/ranges_fill.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill.h'}} +#include <__algorithm/ranges_fill_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill_n.h'}} #include <__algorithm/ranges_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find.h'}} #include <__algorithm/ranges_find_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if.h'}} #include <__algorithm/ranges_find_if_not.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if_not.h'}} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp @@ -0,0 +1,143 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// template O, sentinel_for S> +// constexpr O ranges::fill(O first, S last, const T& value); +// template R> +// constexpr borrowed_iterator_t ranges::fill(R&& r, const T& value); + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template > +concept HasFillIt = requires(Iter iter, Sent sent) { std::ranges::fill(iter, sent, int{}); }; + +static_assert(HasFillIt); +static_assert(!HasFillIt); +static_assert(!HasFillIt); +static_assert(!HasFillIt); +static_assert(!HasFillIt); + +template +concept HasFillR = requires(Range range) { std::ranges::fill(range, int{}); }; + +static_assert(HasFillR>); +static_assert(!HasFillR); +static_assert(!HasFillR); +static_assert(!HasFillR); +static_assert(!HasFillR); + +template +constexpr void test_iterators() { + { // simple test + { + int a[3]; + std::same_as auto ret = std::ranges::fill(It(a), Sent(It(a + 3)), 1); + assert(std::all_of(a, a + 3, [](int i) { return i == 1; })); + assert(base(ret) == a + 3); + } + { + int a[3]; + auto range = std::ranges::subrange(It(a), Sent(It(a + 3))); + std::same_as auto ret = std::ranges::fill(range, 1); + assert(std::all_of(a, a + 3, [](int i) { return i == 1; })); + assert(base(ret) == a + 3); + } + } + + { // check that an empty range works + { + std::array a; + auto ret = std::ranges::fill(It(a.data()), Sent(It(a.data())), 1); + assert(base(ret) == a.data()); + } + { + std::array a; + auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data()))); + auto ret = std::ranges::fill(range, 1); + assert(base(ret) == a.data()); + } + } +} + +constexpr bool test() { + test_iterators, sentinel_wrapper>>(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators(); + + { // check that every element is copied once + struct S { + bool copied = false; + constexpr S& operator=(const S&) { + copied = true; + return *this; + } + }; + { + S a[5]; + std::ranges::fill(a, a + 5, S {true}); + assert(std::all_of(a, a + 5, [](S& s) { return s.copied; })); + } + { + S a[5]; + std::ranges::fill(a, S {true}); + assert(std::all_of(a, a + 5, [](S& s) { return s.copied; })); + } + } + + { // check that std::ranges::dangling is returned + [[maybe_unused]] std::same_as decltype(auto) ret = + std::ranges::fill(std::array {}, 1); + } + + { // check that std::ranges::dangling isn't returned with a borrowing range + std::array a{}; + [[maybe_unused]] std::same_as::iterator> decltype(auto) ret = + std::ranges::fill(std::views::all(a), 1); + assert(std::all_of(a.begin(), a.end(), [](int i) { return i == 1; })); + } + + { // check that non-trivially copyable items are copied properly + { + std::array a; + auto ret = std::ranges::fill(a.begin(), a.end(), "long long string so no SSO"); + assert(ret == a.data() + a.size()); + assert(std::all_of(a.begin(), a.end(), [](auto& s) { return s == "long long string so no SSO"; })); + } + { + std::array a; + auto ret = std::ranges::fill(a, "long long string so no SSO"); + assert(ret == a.data() + a.size()); + assert(std::all_of(a.begin(), a.end(), [](auto& s) { return s == "long long string so no SSO"; })); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp @@ -0,0 +1,91 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// template O> +// constexpr O ranges::fill_n(O first, iter_difference_t n, const T& value); + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template +concept HasFillN = requires(Iter iter) { std::ranges::fill_n(iter, int{}, int{}); }; + +struct WrongType {}; + +static_assert(HasFillN); +static_assert(!HasFillN); +static_assert(!HasFillN); +static_assert(!HasFillN); + +template +constexpr void test_iterators() { + { // simple test + int a[3]; + std::same_as decltype(auto) ret = std::ranges::fill_n(It(a), 3, 1); + assert(std::all_of(a, a + 3, [](int i) { return i == 1; })); + assert(base(ret) == a + 3); + } + + { // check that an empty range works + std::array a; + auto ret = std::ranges::fill_n(It(a.data()), 0, 1); + assert(base(ret) == a.data()); + } +} + +constexpr bool test() { + test_iterators, sentinel_wrapper>>(); + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + test_iterators(); + + { // check that every element is copied once + struct S { + bool copied = false; + constexpr S& operator=(const S&) { + assert(!copied); + copied = true; + return *this; + } + }; + + S a[5]; + std::ranges::fill_n(a, 5, S {}); + assert(std::all_of(a, a + 5, [](S& s) { return s.copied; })); + } + + { // check that non-trivially copyable items are copied properly + std::array a; + auto ret = std::ranges::fill_n(a.data(), 10, "long long string so no SSO"); + assert(ret == a.data() + a.size()); + assert(std::all_of(a.begin(), a.end(), [](auto& s) { return s == "long long string so no SSO"; })); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/support/almost_satisfies_types.h b/libcxx/test/support/almost_satisfies_types.h --- a/libcxx/test/support/almost_satisfies_types.h +++ b/libcxx/test/support/almost_satisfies_types.h @@ -107,6 +107,7 @@ }; using InputRangeNotSentinelSemiregular = UncheckedRange, SentinelForNotSemiregular>; +using OutputRangeNotSentinelSemiregular = UncheckedRange, SentinelForNotSemiregular>; static_assert(std::input_or_output_iterator); static_assert(!std::semiregular); @@ -123,6 +124,8 @@ using InputRangeNotSentinelEqualityComparableWith = UncheckedRange, SentinelForNotWeaklyEqualityComparableWith>; +using OutputRangeNotSentinelEqualityComparableWith = + UncheckedRange, SentinelForNotWeaklyEqualityComparableWith>; static_assert(std::input_or_output_iterator); static_assert(std::semiregular); @@ -220,4 +223,39 @@ static_assert(!std::permutable); static_assert(!std::indirectly_swappable); +class OutputIteratorNotInputOrOutputIterator { +public: + using difference_type = long; + using value_type = int; + using iterator_category = std::input_iterator_tag; + + int& operator++(); + void operator++(int); + int& operator*(); +}; + +using OutputRangeNotInputOrOutputIterator = UncheckedRange; + +static_assert(!std::input_or_output_iterator); +static_assert(std::indirectly_writable); +static_assert(!std::output_iterator); +static_assert(!std::ranges::input_range); + +class OutputIteratorNotIndirectlyWritable { +public: + using difference_type = long; + using iterator_category = std::input_iterator_tag; + + OutputIteratorNotIndirectlyWritable& operator++(); + void operator++(int); + const int& operator*() const; +}; + +using OutputRangeNotIndirectlyWritable = UncheckedRange; + +static_assert(std::input_or_output_iterator); +static_assert(!std::indirectly_writable); +static_assert(!std::output_iterator); +static_assert(!std::ranges::output_range); + #endif // ALMOST_SATISFIES_TYPES_H