209 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// <algorithm>10 11// UNSUPPORTED: c++03, c++11, c++14, c++1712 13// template<class T, output_iterator<const T&> O>14// constexpr O ranges::fill_n(O first, iter_difference_t<O> n, const T& value);15 16#include <algorithm>17#include <array>18#include <cassert>19#include <deque>20#include <ranges>21#include <string>22#include <vector>23 24#include "sized_allocator.h"25#include "almost_satisfies_types.h"26#include "test_iterators.h"27#include "test_macros.h"28 29template <class Iter>30concept HasFillN = requires(Iter iter) { std::ranges::fill_n(iter, int{}, int{}); };31 32struct WrongType {};33 34static_assert(HasFillN<int*>);35static_assert(!HasFillN<WrongType*>);36static_assert(!HasFillN<OutputIteratorNotIndirectlyWritable>);37static_assert(!HasFillN<OutputIteratorNotInputOrOutputIterator>);38 39template <class It, class Sent = It>40constexpr void test_iterators() {41 { // simple test42 int a[3];43 std::same_as<It> decltype(auto) ret = std::ranges::fill_n(It(a), 3, 1);44 assert(std::all_of(a, a + 3, [](int i) { return i == 1; }));45 assert(base(ret) == a + 3);46 }47 48 { // check that an empty range works49 std::array<int, 0> a;50 auto ret = std::ranges::fill_n(It(a.data()), 0, 1);51 assert(base(ret) == a.data());52 }53}54 55// The `ranges::{fill, fill_n}` algorithms require `vector<bool, Alloc>::iterator` to satisfy56// the `std::indirectly_writable` concept when used with `vector<bool, Alloc>`, which is only57// satisfied since C++23.58#if TEST_STD_VER >= 2359constexpr bool test_vector_bool(std::size_t N) {60 { // Test cases validating leading/trailing bits unfilled remain unchanged61 { // Leading bits are not filled62 std::vector<bool> in(N, false);63 std::vector<bool> expected(N, true);64 expected[0] = expected[1] = false;65 std::ranges::fill_n(std::ranges::begin(in) + 2, N - 2, true);66 assert(in == expected);67 }68 { // Trailing bits are not filled69 std::vector<bool> in(N, false);70 std::vector<bool> expected(N, true);71 expected[N - 1] = expected[N - 2] = false;72 std::ranges::fill_n(std::ranges::begin(in), N - 2, true);73 assert(in == expected);74 }75 { // Leading and trailing bits are not filled76 std::vector<bool> in(N, false);77 std::vector<bool> expected(N, true);78 expected[0] = expected[1] = expected[N - 1] = expected[N - 2] = false;79 std::ranges::fill_n(std::ranges::begin(in) + 2, N - 4, true);80 assert(in == expected);81 }82 }83 84 { // Test cases with full or partial bytes filled85 { // Full bytes filled86 std::vector<bool> in(N, false);87 std::vector<bool> expected(N, true);88 std::ranges::fill_n(std::ranges::begin(in), N, true);89 assert(in == expected);90 }91 { // Partial bytes with offset filled92 std::vector<bool> in(N, false);93 std::vector<bool> expected(N, true);94 std::ranges::fill_n(std::ranges::begin(in) + 4, N - 8, true);95 std::ranges::fill_n(std::ranges::begin(expected), 4, false);96 std::ranges::fill_n(std::ranges::end(expected) - 4, 4, false);97 assert(in == expected);98 }99 }100 101 return true;102}103#endif104 105/*TEST_CONSTEXPR_CXX26*/ void test_deque() { // TODO: Mark as TEST_CONSTEXPR_CXX26 once std::deque is constexpr106 std::deque<int> in(20);107 std::deque<int> expected(in.size(), 42);108 std::ranges::fill_n(std::ranges::begin(in), std::ranges::size(in), 42);109 assert(in == expected);110}111 112constexpr bool test() {113 test_iterators<cpp17_output_iterator<int*>, sentinel_wrapper<cpp17_output_iterator<int*>>>();114 test_iterators<cpp20_output_iterator<int*>, sentinel_wrapper<cpp20_output_iterator<int*>>>();115 test_iterators<forward_iterator<int*>>();116 test_iterators<bidirectional_iterator<int*>>();117 test_iterators<random_access_iterator<int*>>();118 test_iterators<contiguous_iterator<int*>>();119 test_iterators<int*>();120 121 { // check that every element is copied once122 struct S {123 bool copied = false;124 constexpr S& operator=(const S&) {125 assert(!copied);126 copied = true;127 return *this;128 }129 };130 131 S a[5];132 std::ranges::fill_n(a, 5, S{});133 assert(std::all_of(a, a + 5, [](S& s) { return s.copied; }));134 }135 136 { // check that non-trivially copyable items are copied properly137 std::array<std::string, 10> a;138 auto ret = std::ranges::fill_n(a.data(), 10, "long long string so no SSO");139 assert(ret == a.data() + a.size());140 assert(std::all_of(a.begin(), a.end(), [](auto& s) { return s == "long long string so no SSO"; }));141 }142 143#if TEST_STD_VER >= 23144 { // Test vector<bool>::iterator optimization145 assert(test_vector_bool(8));146 assert(test_vector_bool(19));147 assert(test_vector_bool(32));148 assert(test_vector_bool(49));149 assert(test_vector_bool(64));150 assert(test_vector_bool(199));151 assert(test_vector_bool(256));152 153 // Make sure std::ranges::fill_n behaves properly with std::vector<bool> iterators with custom154 // size types. See https://github.com/llvm/llvm-project/pull/122410.155 {156 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;157 std::vector<bool, Alloc> in(100, false, Alloc(1));158 std::vector<bool, Alloc> expected(100, true, Alloc(1));159 std::ranges::fill_n(std::ranges::begin(in), in.size(), true);160 assert(in == expected);161 }162 {163 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;164 std::vector<bool, Alloc> in(200, false, Alloc(1));165 std::vector<bool, Alloc> expected(200, true, Alloc(1));166 std::ranges::fill_n(std::ranges::begin(in), in.size(), true);167 assert(in == expected);168 }169 {170 using Alloc = sized_allocator<bool, std::uint32_t, std::int32_t>;171 std::vector<bool, Alloc> in(200, false, Alloc(1));172 std::vector<bool, Alloc> expected(200, true, Alloc(1));173 std::ranges::fill_n(std::ranges::begin(in), in.size(), true);174 assert(in == expected);175 }176 {177 using Alloc = sized_allocator<bool, std::uint64_t, std::int64_t>;178 std::vector<bool, Alloc> in(200, false, Alloc(1));179 std::vector<bool, Alloc> expected(200, true, Alloc(1));180 std::ranges::fill_n(std::ranges::begin(in), in.size(), true);181 assert(in == expected);182 }183 }184#endif185 186 if (!TEST_IS_CONSTANT_EVALUATED) // TODO: Use TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED when std::deque is made constexpr187 test_deque();188 189#if TEST_STD_VER >= 20190 {191 std::vector<std::vector<int>> v{{1, 2}, {1, 2, 3}, {}, {3, 4, 5}, {6}, {7, 8, 9, 6}, {0, 1, 2, 3, 0, 1, 2}};192 auto jv = std::ranges::join_view(v);193 std::ranges::fill_n(std::ranges::begin(jv), std::ranges::distance(jv), 42);194 for (const auto& vec : v)195 for (auto n : vec)196 assert(n == 42);197 }198#endif199 200 return true;201}202 203int main(int, char**) {204 test();205 static_assert(test());206 207 return 0;208}209