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 // MSVC warning C4244: 'argument': conversion from 'const _Ty2' to 'T', possible loss of data
10 // ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4244
11 
12 // <algorithm>
13 
14 // UNSUPPORTED: c++03, c++11, c++14, c++17
15 
16 // template<input_iterator I, sentinel_for<I> S, class T1, class T2, class Proj = identity>
17 //   requires indirectly_writable<I, const T2&> &&
18 //            indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*>
19 //   constexpr I
20 //     ranges::replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = {});
21 // template<input_range R, class T1, class T2, class Proj = identity>
22 //   requires indirectly_writable<iterator_t<R>, const T2&> &&
23 //            indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
24 //   constexpr borrowed_iterator_t<R>
25 //     ranges::replace(R&& r, const T1& old_value, const T2& new_value, Proj proj = {});
26 
27 #include <algorithm>
28 #include <array>
29 #include <cassert>
30 #include <ranges>
31 
32 #include "almost_satisfies_types.h"
33 #include "boolean_testable.h"
34 #include "test_iterators.h"
35 
36 template <class Iter, class Sent = sentinel_wrapper<Iter>>
37 concept HasReplaceIt = requires(Iter iter, Sent sent) { std::ranges::replace(iter, sent, 0, 0); };
38 
39 static_assert(HasReplaceIt<int*>);
40 static_assert(!HasReplaceIt<InputIteratorNotDerivedFrom>);
41 static_assert(!HasReplaceIt<InputIteratorNotIndirectlyReadable>);
42 static_assert(!HasReplaceIt<InputIteratorNotInputOrOutputIterator>);
43 static_assert(!HasReplaceIt<int*, SentinelForNotSemiregular>);
44 static_assert(!HasReplaceIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
45 static_assert(!HasReplaceIt<int**>); // not indirectly_writable
46 static_assert(!HasReplaceIt<IndirectBinaryPredicateNotIndirectlyReadable>);
47 
48 template <class Range>
49 concept HasReplaceR = requires(Range range) { std::ranges::replace(range, 0, 0); };
50 
51 static_assert(HasReplaceR<UncheckedRange<int*>>);
52 static_assert(!HasReplaceR<InputRangeNotDerivedFrom>);
53 static_assert(!HasReplaceR<InputRangeNotIndirectlyReadable>);
54 static_assert(!HasReplaceR<InputRangeNotInputOrOutputIterator>);
55 static_assert(!HasReplaceR<InputRangeNotSentinelSemiregular>);
56 static_assert(!HasReplaceR<InputRangeNotSentinelEqualityComparableWith>);
57 static_assert(!HasReplaceR<UncheckedRange<int**>>); // not indirectly_writable
58 static_assert(!HasReplaceR<InputRangeIndirectBinaryPredicateNotIndirectlyReadable>);
59 
60 template <int N>
61 struct Data {
62   std::array<int, N> input;
63   int oldval;
64   int newval;
65   std::array<int, N> expected;
66 };
67 
68 template <class Iter, class Sent, int N>
test(Data<N> d)69 constexpr void test(Data<N> d) {
70   {
71     auto a = d.input;
72     std::same_as<Iter> decltype(auto) ret = std::ranges::replace(Iter(a.data()), Sent(Iter(a.data() + N)),
73                                                                  d.oldval,
74                                                                  d.newval);
75     assert(base(ret) == a.data() + N);
76     assert(a == d.expected);
77   }
78   {
79     auto a = d.input;
80     auto range = std::ranges::subrange(Iter(a.data()), Sent(Iter(a.data() + N)));
81     std::same_as<Iter> decltype(auto) ret = std::ranges::replace(range, d.oldval, d.newval);
82     assert(base(ret) == a.data() + N);
83     assert(a == d.expected);
84   }
85 }
86 
87 template <class Iter, class Sent = Iter>
test_iterators()88 constexpr void test_iterators() {
89   // simple test
90   test<Iter, Sent, 4>({.input = {1, 2, 3, 4}, .oldval = 2, .newval = 23, .expected = {1, 23, 3, 4}});
91   // no match
92   test<Iter, Sent, 4>({.input = {1, 2, 3, 4}, .oldval = 5, .newval = 23, .expected = {1, 2, 3, 4}});
93   // all match
94   test<Iter, Sent, 4>({.input = {1, 1, 1, 1}, .oldval = 1, .newval = 23, .expected = {23, 23, 23, 23}});
95   // empty range
96   test<Iter, Sent, 0>({.input = {}, .oldval = 1, .newval = 23, .expected = {}});
97   // single element range
98   test<Iter, Sent, 1>({.input = {1}, .oldval = 1, .newval = 2, .expected = {2}});
99 }
100 
test()101 constexpr bool test() {
102   test_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
103   test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
104   test_iterators<forward_iterator<int*>>();
105   test_iterators<bidirectional_iterator<int*>>();
106   test_iterators<random_access_iterator<int*>>();
107   test_iterators<contiguous_iterator<int*>>();
108   test_iterators<int*>();
109 
110   { // check that the projection is used
111     struct S {
112       constexpr S(int i_) : i(i_) {}
113       int i;
114     };
115     {
116       S a[] = {1, 2, 3, 4};
117       std::ranges::replace(a, a + 4, 3, S{0}, &S::i);
118     }
119     {
120       S a[] = {1, 2, 3, 4};
121       std::ranges::replace(a, 3, S{0}, &S::i);
122     }
123   }
124 
125   { // check that std::invoke is used
126     struct S {
127       constexpr S(int i_) : i(i_) {}
128       constexpr bool operator==(const S&) const = default;
129       constexpr const S& identity() const { return *this; }
130       int i;
131     };
132     {
133       S a[] = {1, 2, 3, 4};
134       auto ret = std::ranges::replace(std::begin(a), std::end(a), S{1}, S{2}, &S::identity);
135       assert(ret == a + 4);
136     }
137     {
138       S a[] = {1, 2, 3, 4};
139       auto ret = std::ranges::replace(a, S{1}, S{2}, &S::identity);
140       assert(ret == a + 4);
141     }
142   }
143 
144   { // check that T1 and T2 can be different types
145     {
146       StrictComparable<int> a[] = {1, 2, 2, 4};
147       auto ret = std::ranges::replace(std::begin(a), std::end(a), '\0', 2ull);
148       assert(ret == std::end(a));
149     }
150     {
151       StrictComparable<int> a[] = {1, 2, 2, 4};
152       auto ret = std::ranges::replace(a, '\0', 2ull);
153       assert(ret == std::end(a));
154     }
155   }
156 
157   { // check that std::ranges::dangling is returned
158     [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
159         std::ranges::replace(std::array {1, 2, 3, 4}, 1, 1);
160   }
161 
162   { // check that the complexity requirements are met
163     {
164       auto projectionCount = 0;
165       auto proj = [&](int i) { ++projectionCount; return i; };
166       int a[] = {1, 2, 3, 4, 5};
167       auto ret = std::ranges::replace(std::begin(a), std::end(a), 1, 2, proj);
168       assert(ret == a + 5);
169       assert(projectionCount == 5);
170     }
171     {
172       auto projectionCount = 0;
173       auto proj = [&](int i) { ++projectionCount; return i; };
174       int a[] = {1, 2, 3, 4, 5};
175       auto ret = std::ranges::replace(a, 1, 2, proj);
176       assert(ret == a + 5);
177       assert(projectionCount == 5);
178     }
179   }
180 
181   return true;
182 }
183 
main(int,char **)184 int main(int, char**) {
185   test();
186   static_assert(test());
187 
188   return 0;
189 }
190