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>
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>
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>
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 
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 
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 
201 int main(int, char**) {
202   test();
203   static_assert(test());
204 
205   return 0;
206 }
207