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 @@ -45,8 +45,8 @@ Write,fill,Nikolas Klauser,`D123462 `_,✅ Write,fill_n,Nikolas Klauser,`D123462 `_,✅ Write,transform,Nikolas Klauser,`D122173 `_,✅ -Write,generate,Nikolas Klauser,n/a,Not started -Write,generate_n,Nikolas Klauser,n/a,Not started +Write,generate,Konstantin Varlamov,`D130552 `_,✅ +Write,generate_n,Konstantin Varlamov,`D130552 `_,✅ Write,remove_copy,Nikolas Klauser,n/a,Not started Write,remove_copy_if,Nikolas Klauser,n/a,Not started Write,replace,Nikolas Klauser,`D126283 `_,✅ diff --git a/libcxx/include/__algorithm/ranges_generate.h b/libcxx/include/__algorithm/ranges_generate.h --- a/libcxx/include/__algorithm/ranges_generate.h +++ b/libcxx/include/__algorithm/ranges_generate.h @@ -9,21 +9,15 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_GENERATE_H #define _LIBCPP___ALGORITHM_RANGES_GENERATE_H -#include <__algorithm/generate.h> -#include <__algorithm/make_projected.h> #include <__concepts/constructible.h> #include <__concepts/invocable.h> #include <__config> -#include <__functional/identity.h> #include <__functional/invoke.h> -#include <__functional/ranges_operations.h> #include <__iterator/concepts.h> #include <__iterator/iterator_traits.h> -#include <__iterator/projected.h> #include <__ranges/access.h> #include <__ranges/concepts.h> #include <__ranges/dangling.h> -#include <__utility/forward.h> #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -39,22 +33,28 @@ struct __fn { + template + _LIBCPP_HIDE_FROM_ABI constexpr + static _OutIter __generate_fn_impl(_OutIter __first, _Sent __last, _Func& __gen) { + for (; __first != __last; ++__first) { + *__first = __gen(); + } + + return __first; + } + template _Sent, copy_constructible _Func> requires invocable<_Func&> && indirectly_writable<_OutIter, invoke_result_t<_Func&>> _LIBCPP_HIDE_FROM_ABI constexpr _OutIter operator()(_OutIter __first, _Sent __last, _Func __gen) const { - // TODO: implement - (void)__first; (void)__last; (void)__gen; - return {}; + return __generate_fn_impl(std::move(__first), std::move(__last), __gen); } template requires invocable<_Func&> && output_range<_Range, invoke_result_t<_Func&>> _LIBCPP_HIDE_FROM_ABI constexpr borrowed_iterator_t<_Range> operator()(_Range&& __range, _Func __gen) const { - // TODO: implement - (void)__range; (void)__gen; - return {}; + return __generate_fn_impl(ranges::begin(__range), ranges::end(__range), __gen); } }; diff --git a/libcxx/include/__algorithm/ranges_generate_n.h b/libcxx/include/__algorithm/ranges_generate_n.h --- a/libcxx/include/__algorithm/ranges_generate_n.h +++ b/libcxx/include/__algorithm/ranges_generate_n.h @@ -9,21 +9,16 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_GENERATE_N_H #define _LIBCPP___ALGORITHM_RANGES_GENERATE_N_H -#include <__algorithm/generate_n.h> -#include <__algorithm/make_projected.h> #include <__concepts/constructible.h> #include <__concepts/invocable.h> #include <__config> #include <__functional/identity.h> #include <__functional/invoke.h> -#include <__functional/ranges_operations.h> #include <__iterator/concepts.h> #include <__iterator/incrementable_traits.h> #include <__iterator/iterator_traits.h> -#include <__iterator/projected.h> #include <__ranges/access.h> #include <__ranges/concepts.h> -#include <__utility/forward.h> #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -43,9 +38,12 @@ requires invocable<_Func&> && indirectly_writable<_OutIter, invoke_result_t<_Func&>> _LIBCPP_HIDE_FROM_ABI constexpr _OutIter operator()(_OutIter __first, iter_difference_t<_OutIter> __n, _Func __gen) const { - // TODO: implement - (void)__first; (void)__n; (void)__gen; - return {}; + for (; __n > 0; --__n) { + *__first = __gen(); + ++__first; + } + + return __first; } }; diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -380,6 +380,18 @@ template O> constexpr O ranges::fill_n(O first, iter_difference_t n, const T& value); // since C++20 + template S, copy_constructible F> + requires invocable && indirectly_writable> + constexpr O generate(O first, S last, F gen); // Since C++20 + + template + requires invocable && output_range> + constexpr borrowed_iterator_t generate(R&& r, F gen); // Since C++20 + + template + requires invocable && indirectly_writable> + constexpr O generate_n(O first, iter_difference_t n, F gen); // Since C++20 + template S1, input_iterator I2, sentinel_for S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> requires indirectly_comparable @@ -1575,6 +1587,8 @@ #include <__algorithm/ranges_find_if_not.h> #include <__algorithm/ranges_for_each.h> #include <__algorithm/ranges_for_each_n.h> +#include <__algorithm/ranges_generate.h> +#include <__algorithm/ranges_generate_n.h> #include <__algorithm/ranges_includes.h> #include <__algorithm/ranges_is_partitioned.h> #include <__algorithm/ranges_is_sorted.h> diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/ranges_generate.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/ranges_generate.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/ranges_generate.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/ranges_generate.pass.cpp @@ -24,16 +24,176 @@ #include #include #include +#include #include "almost_satisfies_types.h" #include "test_iterators.h" -// TODO: SFINAE tests. +struct IntGen { + int operator()() const; +}; + +struct UncopyableGen { + UncopyableGen(const UncopyableGen&) = delete; + int operator()() const; +}; +static_assert(!std::copy_constructible); +static_assert(std::invocable); + +struct UninvocableGen { +}; +static_assert(std::copy_constructible); +static_assert(!std::invocable); + +struct IntPtrGen { + int* operator()() const; +}; + +// Test constraints of the (iterator, sentinel) overload. +// ====================================================== + +template +concept HasGenerateIter = + requires(Iter&& iter, Sent&& sent, Gen&& gen) { + std::ranges::generate(std::forward(iter), std::forward(sent), std::forward(gen)); + }; + +static_assert(HasGenerateIter); + +// !input_or_output_iterator +static_assert(!HasGenerateIter); + +// !sentinel_for +static_assert(!HasGenerateIter); +static_assert(!HasGenerateIter); + +// !copy_constructible +static_assert(!HasGenerateIter); + +// !invocable +static_assert(!HasGenerateIter); + +// !indirectly_writable> +static_assert(!HasGenerateIter); + +// Test constraints of the (range) overload. +// ========================================= + +template +concept HasGenerateRange = + requires(Range&& range, Gen&& gen) { + std::ranges::generate(std::forward(range), std::forward(gen)); + }; + +template +using R = UncheckedRange; + +static_assert(HasGenerateRange, IntGen>); + +// !copy_constructible +static_assert(!HasGenerateRange, UncopyableGen>); + +// !invocable +static_assert(!HasGenerateRange, UninvocableGen>); + +// !output_range> +static_assert(!HasGenerateRange); +static_assert(!HasGenerateRange, IntPtrGen>); + +template +constexpr void test_one(const std::array input, Gen gen, std::array expected) { + { // (iterator, sentinel) overload. + auto in = input; + auto begin = Iter(in.data()); + auto end = Sent(Iter(in.data() + in.size())); + + std::same_as decltype(auto) result = std::ranges::generate(std::move(begin), std::move(end), gen); + assert(base(result) == in.data() + in.size()); + assert(in == expected); + } + + { // (range) overload. + auto in = input; + auto begin = Iter(in.data()); + auto end = Sent(Iter(in.data() + in.size())); + auto range = std::ranges::subrange(std::move(begin), std::move(end)); + + // For some reason `ranges::generate` accepts both input and output iterators but only output (not input) ranges. + if constexpr (std::ranges::output_range>) { + std::same_as decltype(auto) result = std::ranges::generate(std::move(range), gen); + assert(base(result) == in.data() + in.size()); + assert(in == expected); + } + } +} + +template +constexpr void test_iter_sent() { + auto gen = [ctr = 1] () mutable { return ctr++; }; + + // Empty sequence. + test_one({}, gen, {}); + // 1-element sequence. + test_one(std::array{-10}, gen, {1}); + // Longer sequence. + test_one(std::array{}, gen, {1, 2, 3, 4, 5}); +} + +template +constexpr void test_iter() { + if constexpr (std::sentinel_for) { + test_iter_sent(); + } + test_iter_sent>(); +} + +constexpr void test_iterators() { + test_iter>(); + test_iter>(); + test_iter>(); + test_iter>(); + test_iter>(); + test_iter>(); + test_iter>(); + test_iter>(); + test_iter(); +} constexpr bool test() { - // TODO: main tests. - // TODO: A custom comparator works. - // TODO: A custom projection works. + test_iterators(); + + { // Complexity: exactly N evaluations of `gen()` and assignments. + struct AssignedOnce { + bool assigned = false; + constexpr AssignedOnce& operator=(const AssignedOnce&) { + assert(!assigned); + assigned = true; + return *this; + } + }; + + { // (iterator, sentinel) overload. + int gen_invocations = 0; + auto gen = [&gen_invocations] { ++gen_invocations; return AssignedOnce(); }; + constexpr size_t N = 10; + std::array in; + + std::ranges::generate(in.begin(), in.end(), gen); + assert(std::ranges::all_of(in, &AssignedOnce::assigned)); + assert(gen_invocations == N); + } + + { // (range) overload. + int gen_invocations = 0; + auto gen = [&gen_invocations] { ++gen_invocations; return AssignedOnce(); }; + constexpr size_t N = 10; + std::array in; + + std::ranges::generate(in, gen); + assert(std::ranges::all_of(in, &AssignedOnce::assigned)); + assert(gen_invocations == N); + } + } return true; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/ranges_generate_n.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/ranges_generate_n.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/ranges_generate_n.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/ranges_generate_n.pass.cpp @@ -24,12 +24,113 @@ #include "almost_satisfies_types.h" #include "test_iterators.h" -// TODO: SFINAE tests. +struct IntGen { + int operator()() const; +}; + +struct UncopyableGen { + UncopyableGen(const UncopyableGen&) = delete; + int operator()() const; +}; +static_assert(!std::copy_constructible); +static_assert(std::invocable); + +struct UninvocableGen { +}; +static_assert(std::copy_constructible); +static_assert(!std::invocable); + +struct IntPtrGen { + int* operator()() const; +}; + +// Test type constraints. +// ====================================================== + +template +concept HasGenerateNIter = + requires(Iter&& iter, Gen&& gen) { + std::ranges::generate_n(std::forward(iter), 0, std::forward(gen)); + }; + +static_assert(HasGenerateNIter); + +// !input_or_output_iterator +static_assert(!HasGenerateNIter); + +// !copy_constructible +static_assert(!HasGenerateNIter); + +// !invocable +static_assert(!HasGenerateNIter); + +// !indirectly_writable> +static_assert(!HasGenerateNIter); + +template +constexpr void test_one(std::array in, size_t n, Gen gen, std::array expected) { + assert(n <= N); + + auto begin = Iter(in.data()); + + std::same_as decltype(auto) result = std::ranges::generate_n(std::move(begin), n, gen); + assert(base(result) == in.data() + n); + assert(in == expected); +} + +template +constexpr void test_iter() { + auto gen = [ctr = 1] () mutable { return ctr++; }; + + // Empty sequence. + test_one({}, 0, gen, {}); + // 1-element sequence, n = 0. + test_one(std::array{-10}, 0, gen, {-10}); + // 1-element sequence, n = 1. + test_one(std::array{-10}, 1, gen, {1}); + // Longer sequence, n = 3. + test_one(std::array{-10, -20, -30, -40, -50}, 3, gen, {1, 2, 3, -40, -50}); + // Longer sequence, n = 5. + test_one(std::array{}, 5, gen, {1, 2, 3, 4, 5}); +} + +constexpr void test_iterators() { + test_iter>(); + test_iter>(); + test_iter>(); + test_iter>(); + test_iter>(); + test_iter>(); + test_iter>(); + test_iter>(); + test_iter(); +} constexpr bool test() { - // TODO: main tests. - // TODO: A custom comparator works. - // TODO: A custom projection works. + test_iterators(); + + { // Complexity: exactly N evaluations of `gen()` and assignments. + struct AssignedOnce { + bool assigned = false; + constexpr AssignedOnce& operator=(const AssignedOnce&) { + assert(!assigned); + assigned = true; + return *this; + } + }; + + int gen_invocations = 0; + auto gen = [&gen_invocations] { ++gen_invocations; return AssignedOnce(); }; + constexpr size_t N1 = 10; + constexpr size_t N2 = N1 / 2; + std::array in; + + auto result = std::ranges::generate_n(in.begin(), N2, gen); + assert(std::ranges::all_of(std::ranges::subrange(in.begin(), result), &AssignedOnce::assigned)); + assert(std::ranges::none_of(std::ranges::subrange(result, in.end()), &AssignedOnce::assigned)); + assert(gen_invocations == N2); + } + return true; } diff --git a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp @@ -92,7 +92,7 @@ auto unary_pred = [](int i) { return i > 0; }; auto binary_pred = [](int i, int j) { return i < j; }; - //auto gen = [] { return 42; }; + auto gen = [] { return 42; }; std::array in = {1, 2, 3}; std::array in2 = {4, 5, 6}; @@ -145,7 +145,7 @@ dangling_both>( std::ranges::transform, in, in2, out_transform.begin(), binary_pred); } - //dangling_1st(std::ranges::generate, in, gen); + dangling_1st(std::ranges::generate, in, gen); //dangling_1st>(std::ranges::remove_copy, in, out, x); //dangling_1st>(std::ranges::remove_copy_if, in, out, unary_pred); dangling_1st(std::ranges::replace, in, x, x); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp @@ -128,8 +128,7 @@ std::array out_transform = {false, true, true}; test(std::ranges::transform, in, out_transform.begin(), &Foo::unary_pred, &Bar::val); } - //test(std::ranges::generate, in, &Bar::create); - //std::ranges::generate_n(in.begin(), count, &Bar::create); + // Whether `ranges::generate{,_n}` invokes `gen` via `std::invoke` is not observable. //test(std::ranges::remove_copy, in, out, x, &Bar::val); //test(std::ranges::remove_copy_if, in, out, &Foo::unary_pred, &Bar::val); // `replace*` algorithms only use the projection to compare the elements, not to write them. diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp @@ -70,7 +70,7 @@ auto unary_pred = [](const Proxy&) { return true; }; //auto binary_pred = [](const Proxy&, const Proxy&) { return return false; }; auto binary_func = [](const Proxy&, const Proxy&) -> Proxy { return Proxy(T()); }; - //auto gen = [] { return Proxy(T{42}); }; + auto gen = [] { return Proxy(T{42}); }; test(std::ranges::any_of, in, unary_pred); test(std::ranges::all_of, in, unary_pred); @@ -122,8 +122,8 @@ test(std::ranges::transform, in, out, std::identity{}); test(std::ranges::transform, in, in2, out, binary_func); } - //test(std::ranges::generate, in, gen); - //std::ranges::generate_n(in.begin(), count, gen); + test(std::ranges::generate, in, gen); + std::ranges::generate_n(in.begin(), count, gen); if constexpr (std::copyable) { //test(std::ranges::remove_copy, in, out, x); //test(std::ranges::remove_copy_if, in, out, unary_pred); diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -55,7 +55,7 @@ int a[10]; auto odd = [](int x) { return x % 2 != 0; }; auto triple = [](int x) { return 3*x; }; -//auto gen = [] { return 42; }; +auto gen = [] { return 42; }; //auto plus = [](int x, int y) { return x == y; }; std::mt19937 g; @@ -84,8 +84,8 @@ static_assert(test(std::ranges::find_if_not, a, odd)); static_assert(test(std::ranges::for_each, a, odd)); static_assert(test(std::ranges::for_each_n, a, 10, odd)); -//static_assert(test(std::ranges::generate, a, gen)); -//static_assert(test(std::ranges::generate_n, a, 10, gen)); +static_assert(test(std::ranges::generate, a, gen)); +static_assert(test(std::ranges::generate_n, a, 10, gen)); static_assert(test(std::ranges::includes, a, a)); //static_assert(test(std::ranges::inplace_merge, a, a+5)); //static_assert(test(std::ranges::is_heap, a));