libcxx/test/std/algorithms/alg.modifying.operations/alg.generate/ranges_generate.pass.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-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>
 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>
 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>
 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
 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
 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
 200 int main(int, char**) {
 201   test();
 202   static_assert(test());
 203
 204   return 0;
 205 }