1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// UNSUPPORTED: c++03, c++11, c++14, c++17
10
11// <algorithm>
12
13// template<input_or_output_iterator O, sentinel_for<O> S, copy_constructible F>
14// requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>>
15// constexpr O generate(O first, S last, F gen); // Since C++20
16//
17// template<class R, copy_constructible F>
18// requires invocable<F&> && output_range<R, invoke_result_t<F&>>
19// constexpr borrowed_iterator_t<R> generate(R&& r, F gen); // Since C++20
20
21#include <algorithm>
22#include <array>
23#include <concepts>
24#include <functional>
25#include <ranges>
26#include <utility>
27
28#include "almost_satisfies_types.h"
29#include "test_iterators.h"
30
31struct IntGen {
32 int operator()() const;
33};
34
35struct UncopyableGen {
36 UncopyableGen(const UncopyableGen&) = delete;
37 int operator()() const;
38};
39static_assert(!std::copy_constructible<UncopyableGen>);
40static_assert(std::invocable<UncopyableGen>);
41
42struct UninvocableGen {
43};
44static_assert(std::copy_constructible<UninvocableGen>);
45static_assert(!std::invocable<UninvocableGen>);
46
47struct IntPtrGen {
48 int* operator()() const;
49};
50
51// Test constraints of the (iterator, sentinel) overload.
52// ======================================================
53
54template <class Iter = int*, class Sent = int*, class Gen = IntGen>
55concept HasGenerateIter =
56 requires(Iter&& iter, Sent&& sent, Gen&& gen) {
57 std::ranges::generate(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Gen>(gen));
58 };
59
60static_assert(HasGenerateIter<int*, int*, IntGen>);
61
62// !input_or_output_iterator<O>
63static_assert(!HasGenerateIter<InputIteratorNotInputOrOutputIterator>);
64
65// !sentinel_for<S, O>
66static_assert(!HasGenerateIter<int*, SentinelForNotSemiregular>);
67static_assert(!HasGenerateIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
68
69// !copy_constructible<F>
70static_assert(!HasGenerateIter<int*, int*, UncopyableGen>);
71
72// !invocable<F&>
73static_assert(!HasGenerateIter<int*, int*, UninvocableGen>);
74
75// !indirectly_writable<O, invoke_result_t<F&>>
76static_assert(!HasGenerateIter<int*, int*, IntPtrGen>);
77
78// Test constraints of the (range) overload.
79// =========================================
80
81template <class Range, class Gen = IntGen>
82concept HasGenerateRange =
83 requires(Range&& range, Gen&& gen) {
84 std::ranges::generate(std::forward<Range>(range), std::forward<Gen>(gen));
85 };
86
87template <class T>
88using R = UncheckedRange<T>;
89
90static_assert(HasGenerateRange<R<int*>, IntGen>);
91
92// !copy_constructible<F>
93static_assert(!HasGenerateRange<R<int*>, UncopyableGen>);
94
95// !invocable<F&>
96static_assert(!HasGenerateRange<R<int*>, UninvocableGen>);
97
98// !output_range<R, invoke_result_t<F&>>
99static_assert(!HasGenerateRange<InputRangeNotInputOrOutputIterator>);
100static_assert(!HasGenerateRange<R<int*>, IntPtrGen>);
101
102template <class Iter, class Sent, std::size_t N, class Gen>
103constexpr void test_one(const std::array<int, N> input, Gen gen, std::array<int, N> expected) {
104 { // (iterator, sentinel) overload.
105 auto in = input;
106 auto begin = Iter(in.data());
107 auto end = Sent(Iter(in.data() + in.size()));
108
109 std::same_as<Iter> decltype(auto) result = std::ranges::generate(std::move(begin), std::move(end), gen);
110 assert(base(result) == in.data() + in.size());
111 assert(in == expected);
112 }
113
114 { // (range) overload.
115 auto in = input;
116 auto begin = Iter(in.data());
117 auto end = Sent(Iter(in.data() + in.size()));
118 auto range = std::ranges::subrange(std::move(begin), std::move(end));
119
120 // For some reason `ranges::generate` accepts both input and output iterators but only output (not input) ranges.
121 if constexpr (std::ranges::output_range<decltype(range), std::invoke_result_t<Gen&>>) {
122 std::same_as<Iter> decltype(auto) result = std::ranges::generate(std::move(range), gen);
123 assert(base(result) == in.data() + in.size());
124 assert(in == expected);
125 }
126 }
127}
128
129template <class Iter, class Sent>
130constexpr void test_iter_sent() {
131 auto gen = [ctr = 1] () mutable { return ctr++; };
132
133 // Empty sequence.
134 test_one<Iter, Sent, 0>({}, gen, {});
135 // 1-element sequence.
136 test_one<Iter, Sent>(std::array{-10}, gen, {1});
137 // Longer sequence.
138 test_one<Iter, Sent>(std::array<int, 5>{}, gen, {1, 2, 3, 4, 5});
139}
140
141template <class Iter>
142constexpr void test_iter() {
143 if constexpr (std::sentinel_for<Iter, Iter>) {
144 test_iter_sent<Iter, Iter>();
145 }
146 test_iter_sent<Iter, sentinel_wrapper<Iter>>();
147}
148
149constexpr void test_iterators() {
150 test_iter<cpp17_input_iterator<int*>>();
151 test_iter<cpp20_input_iterator<int*>>();
152 test_iter<cpp17_output_iterator<int*>>();
153 test_iter<cpp20_output_iterator<int*>>();
154 test_iter<forward_iterator<int*>>();
155 test_iter<bidirectional_iterator<int*>>();
156 test_iter<random_access_iterator<int*>>();
157 test_iter<contiguous_iterator<int*>>();
158 test_iter<int*>();
159}
160
161constexpr bool test() {
162 test_iterators();
163
164 { // Complexity: exactly N evaluations of `gen()` and assignments.
165 struct AssignedOnce {
166 bool assigned = false;
167 constexpr AssignedOnce& operator=(const AssignedOnce&) {
168 assert(!assigned);
169 assigned = true;
170 return *this;
171 }
172 };
173
174 { // (iterator, sentinel) overload.
175 int gen_invocations = 0;
176 auto gen = [&gen_invocations] { ++gen_invocations; return AssignedOnce(); };
177 constexpr std::size_t N = 10;
178 std::array<AssignedOnce, N> in;
179
180 std::ranges::generate(in.begin(), in.end(), gen);
181 assert(std::ranges::all_of(in, &AssignedOnce::assigned));
182 assert(gen_invocations == N);
183 }
184
185 { // (range) overload.
186 int gen_invocations = 0;
187 auto gen = [&gen_invocations] { ++gen_invocations; return AssignedOnce(); };
188 constexpr std::size_t N = 10;
189 std::array<AssignedOnce, N> in;
190
191 std::ranges::generate(in, gen);
192 assert(std::ranges::all_of(in, &AssignedOnce::assigned));
193 assert(gen_invocations == N);
194 }
195 }
196
197 return true;
198}
199
200int main(int, char**) {
201 test();
202 static_assert(test());
203
204 return 0;
205}
206

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/ranges_generate.pass.cpp