206 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// UNSUPPORTED: c++03, c++11, c++14, c++1710 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++2016//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++2020 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