//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
// UNSUPPORTED: c++03, c++11, c++14, c++17
// <algorithm>
// template<input_or_output_iterator O, sentinel_for<O> S, copy_constructible F>
// requires invocable<F&> && indirectly_writable<O, invoke_result_t<F&>>
// constexpr O generate(O first, S last, F gen); // Since C++20
//
// template<class R, copy_constructible F>
// requires invocable<F&> && output_range<R, invoke_result_t<F&>>
// constexpr borrowed_iterator_t<R> generate(R&& r, F gen); // Since C++20
#include <algorithm>
#include <array>
#include <concepts>
#include <functional>
#include <ranges>
#include <utility>
#include "almost_satisfies_types.h"
#include "test_iterators.h"
struct IntGen {
int operator()() const;
};
struct UncopyableGen {
UncopyableGen(const UncopyableGen&) = delete;
int operator()() const;
};
static_assert(!std::copy_constructible<UncopyableGen>);
static_assert(std::invocable<UncopyableGen>);
struct UninvocableGen {
};
static_assert(std::copy_constructible<UninvocableGen>);
static_assert(!std::invocable<UninvocableGen>);
struct IntPtrGen {
int* operator()() const;
};
// Test constraints of the (iterator, sentinel) overload.
// ======================================================
template <class Iter = int*, class Sent = int*, class Gen = IntGen>
concept HasGenerateIter =
requires(Iter&& iter, Sent&& sent, Gen&& gen) {
std::ranges::generate(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Gen>(gen));
};
static_assert(HasGenerateIter<int*, int*, IntGen>);
// !input_or_output_iterator<O>
static_assert(!HasGenerateIter<InputIteratorNotInputOrOutputIterator>);
// !sentinel_for<S, O>
static_assert(!HasGenerateIter<int*, SentinelForNotSemiregular>);
static_assert(!HasGenerateIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
// !copy_constructible<F>
static_assert(!HasGenerateIter<int*, int*, UncopyableGen>);
// !invocable<F&>
static_assert(!HasGenerateIter<int*, int*, UninvocableGen>);
// !indirectly_writable<O, invoke_result_t<F&>>
static_assert(!HasGenerateIter<int*, int*, IntPtrGen>);
// Test constraints of the (range) overload.
// =========================================
template <class Range, class Gen = IntGen>
concept HasGenerateRange =
requires(Range&& range, Gen&& gen) {
std::ranges::generate(std::forward<Range>(range), std::forward<Gen>(gen));
};
template <class T>
using R = UncheckedRange<T>;
static_assert(HasGenerateRange<R<int*>, IntGen>);
// !copy_constructible<F>
static_assert(!HasGenerateRange<R<int*>, UncopyableGen>);
// !invocable<F&>
static_assert(!HasGenerateRange<R<int*>, UninvocableGen>);
// !output_range<R, invoke_result_t<F&>>
static_assert(!HasGenerateRange<InputRangeNotInputOrOutputIterator>);
static_assert(!HasGenerateRange<R<int*>, IntPtrGen>);
template <class Iter, class Sent, std::size_t N, class Gen>
constexpr void test_one(const std::array<int, N> input, Gen gen, std::array<int, N> expected) {
{ // (iterator, sentinel) overload.
auto in = input;
auto begin = Iter(in.data());
auto end = Sent(Iter(in.data() + in.size()));
std::same_as<Iter> decltype(auto) result = std::ranges::generate(std::move(begin), std::move(end), gen);
assert(base(result) == in.data() + in.size());
assert(in == expected);
}
{ // (range) overload.
auto in = input;
auto begin = Iter(in.data());
auto end = Sent(Iter(in.data() + in.size()));
auto range = std::ranges::subrange(std::move(begin), std::move(end));
// For some reason `ranges::generate` accepts both input and output iterators but only output (not input) ranges.
if constexpr (std::ranges::output_range<decltype(range), std::invoke_result_t<Gen&>>) {
std::same_as<Iter> decltype(auto) result = std::ranges::generate(std::move(range), gen);
assert(base(result) == in.data() + in.size());
assert(in == expected);
}
}
}
template <class Iter, class Sent>
constexpr void test_iter_sent() {
auto gen = [ctr = 1] () mutable { return ctr++; };
// Empty sequence.
test_one<Iter, Sent, 0>({}, gen, {});
// 1-element sequence.
test_one<Iter, Sent>(std::array{-10}, gen, {1});
// Longer sequence.
test_one<Iter, Sent>(std::array<int, 5>{}, gen, {1, 2, 3, 4, 5});
}
template <class Iter>
constexpr void test_iter() {
if constexpr (std::sentinel_for<Iter, Iter>) {
test_iter_sent<Iter, Iter>();
}
test_iter_sent<Iter, sentinel_wrapper<Iter>>();
}
constexpr void test_iterators() {
test_iter<cpp17_input_iterator<int*>>();
test_iter<cpp20_input_iterator<int*>>();
test_iter<cpp17_output_iterator<int*>>();
test_iter<cpp20_output_iterator<int*>>();
test_iter<forward_iterator<int*>>();
test_iter<bidirectional_iterator<int*>>();
test_iter<random_access_iterator<int*>>();
test_iter<contiguous_iterator<int*>>();
test_iter<int*>();
}
constexpr bool test() {
test_iterators();
{ // Complexity: exactly N evaluations of `gen()` and assignments.
struct AssignedOnce {
bool assigned = false;
constexpr AssignedOnce& operator=(const AssignedOnce&) {
assert(!assigned);
assigned = true;
return *this;
}
};
{ // (iterator, sentinel) overload.
int gen_invocations = 0;
auto gen = [&gen_invocations] { ++gen_invocations; return AssignedOnce(); };
constexpr std::size_t N = 10;
std::array<AssignedOnce, N> in;
std::ranges::generate(in.begin(), in.end(), gen);
assert(std::ranges::all_of(in, &AssignedOnce::assigned));
assert(gen_invocations == N);
}
{ // (range) overload.
int gen_invocations = 0;
auto gen = [&gen_invocations] { ++gen_invocations; return AssignedOnce(); };
constexpr std::size_t N = 10;
std::array<AssignedOnce, N> in;
std::ranges::generate(in, gen);
assert(std::ranges::all_of(in, &AssignedOnce::assigned));
assert(gen_invocations == N);
}
}
return true;
}
int main(int, char**) {
test();
static_assert(test());
return 0;
}
Codebase Browser
llvm