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
31 struct IntGen {
32 int operator()() const;
33 };
34
35 struct UncopyableGen {
36 UncopyableGen(const UncopyableGen&) = delete;
37 int operator()() const;
38 };
39 static_assert(!std::copy_constructible<UncopyableGen>);
40 static_assert(std::invocable<UncopyableGen>);
41
42 struct UninvocableGen {
43 };
44 static_assert(std::copy_constructible<UninvocableGen>);
45 static_assert(!std::invocable<UninvocableGen>);
46
47 struct IntPtrGen {
48 int* operator()() const;
49 };
50
51 // Test constraints of the (iterator, sentinel) overload.
52 // ======================================================
53
54 template <class Iter = int*, class Sent = int*, class Gen = IntGen>
55 concept 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
60 static_assert(HasGenerateIter<int*, int*, IntGen>);
61
62 // !input_or_output_iterator<O>
63 static_assert(!HasGenerateIter<InputIteratorNotInputOrOutputIterator>);
64
65 // !sentinel_for<S, O>
66 static_assert(!HasGenerateIter<int*, SentinelForNotSemiregular>);
67 static_assert(!HasGenerateIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
68
69 // !copy_constructible<F>
70 static_assert(!HasGenerateIter<int*, int*, UncopyableGen>);
71
72 // !invocable<F&>
73 static_assert(!HasGenerateIter<int*, int*, UninvocableGen>);
74
75 // !indirectly_writable<O, invoke_result_t<F&>>
76 static_assert(!HasGenerateIter<int*, int*, IntPtrGen>);
77
78 // Test constraints of the (range) overload.
79 // =========================================
80
81 template <class Range, class Gen = IntGen>
82 concept HasGenerateRange =
83 requires(Range&& range, Gen&& gen) {
84 std::ranges::generate(std::forward<Range>(range), std::forward<Gen>(gen));
85 };
86
87 template <class T>
88 using R = UncheckedRange<T>;
89
90 static_assert(HasGenerateRange<R<int*>, IntGen>);
91
92 // !copy_constructible<F>
93 static_assert(!HasGenerateRange<R<int*>, UncopyableGen>);
94
95 // !invocable<F&>
96 static_assert(!HasGenerateRange<R<int*>, UninvocableGen>);
97
98 // !output_range<R, invoke_result_t<F&>>
99 static_assert(!HasGenerateRange<InputRangeNotInputOrOutputIterator>);
100 static_assert(!HasGenerateRange<R<int*>, IntPtrGen>);
101
102 template <class Iter, class Sent, std::size_t N, class Gen>
test_one(const std::array<int,N> input,Gen gen,std::array<int,N> expected)103 constexpr 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
129 template <class Iter, class Sent>
test_iter_sent()130 constexpr 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
141 template <class Iter>
test_iter()142 constexpr 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
test_iterators()149 constexpr 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
test()161 constexpr 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
main(int,char **)200 int main(int, char**) {
201 test();
202 static_assert(test());
203
204 return 0;
205 }
206