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