261 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, sentinel_for<O> S>14// constexpr O ranges::fill(O first, S last, const T& value);15// template<class T, output_range<const T&> R>16// constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value);17 18#include <algorithm>19#include <array>20#include <cassert>21#include <deque>22#include <ranges>23#include <string>24#include <vector>25 26#include "sized_allocator.h"27#include "almost_satisfies_types.h"28#include "test_iterators.h"29#include "test_macros.h"30 31template <class Iter, class Sent = sentinel_wrapper<Iter>>32concept HasFillIt = requires(Iter iter, Sent sent) { std::ranges::fill(iter, sent, int{}); };33 34static_assert(HasFillIt<int*>);35static_assert(!HasFillIt<OutputIteratorNotIndirectlyWritable>);36static_assert(!HasFillIt<OutputIteratorNotInputOrOutputIterator>);37static_assert(!HasFillIt<int*, SentinelForNotSemiregular>);38static_assert(!HasFillIt<int*, SentinelForNotWeaklyEqualityComparableWith>);39 40template <class Range>41concept HasFillR = requires(Range range) { std::ranges::fill(range, int{}); };42 43static_assert(HasFillR<UncheckedRange<int*>>);44static_assert(!HasFillR<OutputRangeNotIndirectlyWritable>);45static_assert(!HasFillR<OutputRangeNotInputOrOutputIterator>);46static_assert(!HasFillR<OutputRangeNotSentinelSemiregular>);47static_assert(!HasFillR<OutputRangeNotSentinelEqualityComparableWith>);48 49template <class It, class Sent = It>50constexpr void test_iterators() {51 { // simple test52 {53 int a[3];54 std::same_as<It> auto ret = std::ranges::fill(It(a), Sent(It(a + 3)), 1);55 assert(std::all_of(a, a + 3, [](int i) { return i == 1; }));56 assert(base(ret) == a + 3);57 }58 {59 int a[3];60 auto range = std::ranges::subrange(It(a), Sent(It(a + 3)));61 std::same_as<It> auto ret = std::ranges::fill(range, 1);62 assert(std::all_of(a, a + 3, [](int i) { return i == 1; }));63 assert(base(ret) == a + 3);64 }65 }66 67 { // check that an empty range works68 {69 std::array<int, 0> a;70 auto ret = std::ranges::fill(It(a.data()), Sent(It(a.data())), 1);71 assert(base(ret) == a.data());72 }73 {74 std::array<int, 0> a;75 auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data())));76 auto ret = std::ranges::fill(range, 1);77 assert(base(ret) == a.data());78 }79 }80}81 82// The `ranges::{fill, fill_n}` algorithms require `vector<bool, Alloc>::iterator` to satisfy83// the `std::indirectly_writable` concept when used with `vector<bool, Alloc>`, which is only84// satisfied since C++23.85#if TEST_STD_VER >= 2386constexpr bool test_vector_bool(std::size_t N) {87 { // Test cases validating leading/trailing bits unfilled remain unchanged88 { // Leading bits are not filled89 std::vector<bool> in(N, false);90 std::vector<bool> expected(N, true);91 expected[0] = expected[1] = false;92 std::ranges::fill(std::ranges::subrange(in.begin() + 2, in.end()), true);93 assert(in == expected);94 }95 { // Trailing bits are not filled96 std::vector<bool> in(N, false);97 std::vector<bool> expected(N, true);98 expected[N - 1] = expected[N - 2] = false;99 std::ranges::fill(std::ranges::subrange(in.begin(), in.end() - 2), true);100 assert(in == expected);101 }102 { // Leading and trailing bits are not filled103 std::vector<bool> in(N, false);104 std::vector<bool> expected(N, true);105 expected[0] = expected[1] = expected[N - 1] = expected[N - 2] = false;106 std::ranges::fill(std::ranges::subrange(in.begin() + 2, in.end() - 2), true);107 assert(in == expected);108 }109 }110 111 { // Test cases with full or partial bytes filled112 { // Full bytes filled113 std::vector<bool> in(N, false);114 std::vector<bool> expected(N, true);115 std::ranges::fill(in, true);116 assert(in == expected);117 }118 { // Partial bytes with offset filled119 std::vector<bool> in(N, false);120 std::vector<bool> expected(N, true);121 std::ranges::fill(std::ranges::subrange(std::ranges::begin(in) + 4, std::ranges::end(in) - 4), true);122 std::ranges::fill(std::ranges::subrange(std::ranges::begin(expected), std::ranges::begin(expected) + 4), false);123 std::ranges::fill(std::ranges::subrange(std::ranges::end(expected) - 4, std::ranges::end(expected)), false);124 assert(in == expected);125 }126 }127 128 return true;129}130#endif131 132/*TEST_CONSTEXPR_CXX26*/ void test_deque() { // TODO: Mark as TEST_CONSTEXPR_CXX26 once std::deque is constexpr133 std::deque<int> in(20);134 std::deque<int> expected(in.size(), 42);135 std::ranges::fill(in, 42);136 assert(in == expected);137}138 139constexpr bool test() {140 test_iterators<cpp17_output_iterator<int*>, sentinel_wrapper<cpp17_output_iterator<int*>>>();141 test_iterators<cpp20_output_iterator<int*>, sentinel_wrapper<cpp20_output_iterator<int*>>>();142 test_iterators<forward_iterator<int*>>();143 test_iterators<bidirectional_iterator<int*>>();144 test_iterators<random_access_iterator<int*>>();145 test_iterators<contiguous_iterator<int*>>();146 test_iterators<int*>();147 148 { // check that every element is copied once149 struct S {150 bool copied = false;151 constexpr S& operator=(const S&) {152 copied = true;153 return *this;154 }155 };156 {157 S a[5];158 std::ranges::fill(a, a + 5, S{true});159 assert(std::all_of(a, a + 5, [](S& s) { return s.copied; }));160 }161 {162 S a[5];163 std::ranges::fill(a, S{true});164 assert(std::all_of(a, a + 5, [](S& s) { return s.copied; }));165 }166 }167 168 { // check that std::ranges::dangling is returned169 [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =170 std::ranges::fill(std::array<int, 10>{}, 1);171 }172 173 { // check that std::ranges::dangling isn't returned with a borrowing range174 std::array<int, 10> a{};175 [[maybe_unused]] std::same_as<std::array<int, 10>::iterator> decltype(auto) ret =176 std::ranges::fill(std::views::all(a), 1);177 assert(std::all_of(a.begin(), a.end(), [](int i) { return i == 1; }));178 }179 180 { // check that non-trivially copyable items are copied properly181 {182 std::array<std::string, 10> a;183 auto ret = std::ranges::fill(a.begin(), a.end(), "long long string so no SSO");184 assert(ret == a.end());185 assert(std::all_of(a.begin(), a.end(), [](auto& s) { return s == "long long string so no SSO"; }));186 }187 {188 std::array<std::string, 10> a;189 auto ret = std::ranges::fill(a, "long long string so no SSO");190 assert(ret == a.end());191 assert(std::all_of(a.begin(), a.end(), [](auto& s) { return s == "long long string so no SSO"; }));192 }193 }194 195#if TEST_STD_VER >= 23196 { // Test vector<bool>::iterator optimization197 assert(test_vector_bool(8));198 assert(test_vector_bool(19));199 assert(test_vector_bool(32));200 assert(test_vector_bool(49));201 assert(test_vector_bool(64));202 assert(test_vector_bool(199));203 assert(test_vector_bool(256));204 205 // Make sure std::ranges::fill behaves properly with std::vector<bool> iterators with custom206 // size types. See https://github.com/llvm/llvm-project/pull/122410.207 {208 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;209 std::vector<bool, Alloc> in(100, false, Alloc(1));210 std::vector<bool, Alloc> expected(100, true, Alloc(1));211 std::ranges::fill(in, true);212 assert(in == expected);213 }214 {215 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;216 std::vector<bool, Alloc> in(200, false, Alloc(1));217 std::vector<bool, Alloc> expected(200, true, Alloc(1));218 std::ranges::fill(in, true);219 assert(in == expected);220 }221 {222 using Alloc = sized_allocator<bool, std::uint32_t, std::int32_t>;223 std::vector<bool, Alloc> in(200, false, Alloc(1));224 std::vector<bool, Alloc> expected(200, true, Alloc(1));225 std::ranges::fill(in, true);226 assert(in == expected);227 }228 {229 using Alloc = sized_allocator<bool, std::uint64_t, std::int64_t>;230 std::vector<bool, Alloc> in(200, false, Alloc(1));231 std::vector<bool, Alloc> expected(200, true, Alloc(1));232 std::ranges::fill(in, true);233 assert(in == expected);234 }235 }236#endif237 238 if (!TEST_IS_CONSTANT_EVALUATED) // TODO: Use TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED when std::deque is made constexpr239 test_deque();240 241#if TEST_STD_VER >= 20242 {243 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}};244 auto jv = std::ranges::join_view(v);245 std::ranges::fill(jv, 42);246 for (const auto& vec : v)247 for (auto n : vec)248 assert(n == 42);249 }250#endif251 252 return true;253}254 255int main(int, char**) {256 test();257 static_assert(test());258 259 return 0;260}261