[libc++] Implement ranges::replace{, _if}

[var-const]

The implementation looks great. Just need to add a few test cases and update the synopsis. Thanks!

libcxx/docs/Status/RangesAlgorithms.csv

51–53

Please don't forget to update this with an actual link.

libcxx/include/algorithm

1173

You probably need to update the synopsis as well.

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges.replace.pass.cpp

15

Can you also add the synopsis so that the algorithm signature is easy to look up when reading the test file?

21

Can you also test the requires clause and parameter constraints to check that SFINAE works correctly?

23

Nit: we normally use a trailing underscore for private variables. How about renaming it (maybe to something like original, original_input, etc.)?

23

In the signature, T1 and T2 can be different types, but the current tests only cover the case when they are the same type. Can you also test the conversion?

26

Nit: decltype(auto).

27

Nit: the formatting looks a little weird here, perhaps align oldval and newval with Iter on the line above?

44

Optional: consider adding comments to imitate named arguments, something like:

test<Iter, Sent, 4>(/*input=*/{1, 2, 3, 4}, /*old=*/2, /*new=*/23, /*expected=*/{1, 23, 3, 4});

46

Can this argument be deduced? (in all cases except for 0, I guess)

55

Can you also add a test for when the range overload returns dangling?

82

A couple more tests that I think should be added:

1. In the standard, the operator== (and the predicate for the _if version) isn't required to return a bool, just something convertible to a boolean. Can you check those cases?
2. There's a complexity requirement on the predicate and the projection. I know it's trivial, but perhaps test that as well to be exhaustive?

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges.replace_if.pass.cpp

23

I think all the same comments as in ranges.replace.pass.cpp apply here.

[var-const]

The implementation looks great. Just need to add a few test cases and update the synopsis. Thanks!

[var-const]

Also, can you check if you need to update niebloid.compile.pass.cpp?

[philnik]

• Rebased
• Address comments

[philnik]

• Add version guards

[philnik]

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges.replace.pass.cpp

44

I'm using a struct with designated initializers. WDYT?

46

I tried it and couldn't get it to work.

[var-const]

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges.replace.pass.cpp

44

It looks great, definitely better than comments.

46

Right -- looks like you would need to pass std::array{1, 2, 3, 4}. Let's leave as is.

libcxx/docs/Status/RangesAlgorithms.csv

 Write,move,Nikolas Klauser,`D126616 <https://llvm.org/D126616>`_,Under review
 Write,move_backward,Nikolas Klauser,`D126616 <https://llvm.org/D126616>`_,Under review
 Write,fill,Nikolas Klauser,`D123462 <https://reviews.llvm.org/D123462>`_,✅
 Write,fill_n,Nikolas Klauser,`D123462 <https://reviews.llvm.org/D123462>`_,✅
 Write,transform,Nikolas Klauser,`D122173 <https://llvm.org/D122173>`_,✅
 Write,generate,Not assigned,n/a,Not started
 Write,generate_n,Not assigned,n/a,Not started
 Write,remove_copy,Not assigned,n/a,Not started
 Write,remove_copy_if,Not assigned,n/a,Not started
-Write,replace,Nikolas Klauser,`D126283 <https://llvm.org/D126283>`_,Under review
-Write,replace_if,Nikolas Klauser,`D126283 <https://llvm.org/D126283>`_,Under review
+Write,replace,Nikolas Klauser,`D126283 <https://llvm.org/D126283>`_,✅
+Write,replace_if,Nikolas Klauser,`D126283 <https://llvm.org/D126283>`_,✅
 Write,replace_copy,Not assigned,n/a,Not started
 Write,replace_copy_if,Not assigned,n/a,Not started
 Write,swap_ranges,Nikolas Klauser,`D116303 <https://llvm.org/D116303>`_,✅
 Write,reverse_copy,Not assigned,n/a,Not started
 Write,rotate_copy,Not assigned,n/a,Not started
 Write,sample,Not assigned,n/a,Not started
 Write,unique_copy,Not assigned,n/a,Not started
 Write,partition_copy,Not assigned,n/a,Not started

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_max.h
   __algorithm/ranges_max_element.h
   __algorithm/ranges_min.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_minmax.h
   __algorithm/ranges_minmax_element.h
   __algorithm/ranges_mismatch.h
   __algorithm/ranges_none_of.h
+  __algorithm/ranges_replace.h
+  __algorithm/ranges_replace_if.h
   __algorithm/ranges_reverse.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/ranges_transform.h
   __algorithm/ranges_upper_bound.h
   __algorithm/remove.h
   __algorithm/remove_copy.h
   __algorithm/remove_copy_if.h
   __algorithm/remove_if.h

libcxx/include/__algorithm/ranges_replace.h

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_REPLACE_H
+#define _LIBCPP___ALGORITHM_RANGES_REPLACE_H
+
+#include <__algorithm/ranges_replace_if.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined (_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __replace {
+struct __fn {
+
+  template <input_iterator _Iter, sentinel_for<_Iter> _Sent,
+            class _Type1,
+            class _Type2,
+            class _Proj = identity>
+    requires indirectly_writable<_Iter, const _Type2&>
+          && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type1*>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  _Iter operator()(_Iter __first, _Sent __last,
+                   const _Type1& __old_value,
+                   const _Type2& __new_value,
+                   _Proj __proj = {}) const {
+    auto __pred = [&](const auto& __val) { return __val == __old_value; };
+    return ranges::__replace_if_impl(std::move(__first), std::move(__last), __pred, __new_value, __proj);
+  }
+
+  template <input_range _Range,
+            class _Type1,
+            class _Type2,
+            class _Proj = identity>
+    requires indirectly_writable<iterator_t<_Range>, const _Type2&>
+          && indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type1*>
+  _LIBCPP_HIDE_FROM_ABI constexpr borrowed_iterator_t<_Range>
+  operator()(_Range&& __range, const _Type1& __old_value, const _Type2& __new_value, _Proj __proj = {}) const {
+    auto __pred = [&](auto&& __val) { return __val == __old_value; };
+    return ranges::__replace_if_impl(ranges::begin(__range), ranges::end(__range), __pred, __new_value, __proj);
+  }
+
+};
+} // namespace __replace
+
+inline namespace __cpo {
+  inline constexpr auto replace = __replace::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined (_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_REPLACE_H

libcxx/include/__algorithm/ranges_replace_if.h

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_REPLACE_IF_H
+#define _LIBCPP___ALGORITHM_RANGES_REPLACE_IF_H
+
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined (_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+
+template <class _Iter, class _Sent, class _Type, class _Proj, class _Pred>
+_LIBCPP_HIDE_FROM_ABI constexpr
+_Iter __replace_if_impl(_Iter __first, _Sent __last, _Pred& __pred, const _Type& __new_value, _Proj& __proj) {
+  for (; __first != __last; ++__first) {
+    if (std::invoke(__pred, std::invoke(__proj, *__first)))
+      *__first = __new_value;
+  }
+  return __first;
+}
+
+namespace __replace_if {
+struct __fn {
+
+  template <input_iterator _Iter, sentinel_for<_Iter> _Sent,
+            class _Type,
+            class _Proj = identity,
+            indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
+    requires indirectly_writable<_Iter, const _Type&>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  _Iter operator()(_Iter __first, _Sent __last, _Pred __pred, const _Type& __new_value, _Proj __proj = {}) const {
+    return ranges::__replace_if_impl(std::move(__first), std::move(__last), __pred, __new_value, __proj);
+  }
+
+  template <input_range _Range,
+            class _Type,
+            class _Proj = identity,
+            indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
+    requires indirectly_writable<iterator_t<_Range>, const _Type&>
+  _LIBCPP_HIDE_FROM_ABI constexpr borrowed_iterator_t<_Range>
+  operator()(_Range&& __range, _Pred __pred, const _Type& __new_value, _Proj __proj = {}) const {
+    return ranges::__replace_if_impl(ranges::begin(__range), ranges::end(__range), __pred, __new_value, __proj);
+  }
+
+};
+} // namespace __replace_if
+
+inline namespace __cpo {
+  inline constexpr auto replace_if = __replace_if::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined (_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_REPLACE_IF_H

libcxx/include/algorithm

template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
                                      projected<I, Proj>> Pred = ranges::equal_to>
     constexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {});     // since C+20
 
   template<forward_range R, class Proj = identity,
            indirect_binary_predicate<projected<iterator_t<R>, Proj>,
                                      projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
     constexpr borrowed_iterator_t<R> ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {});  // since C++20
 
+  template<input_iterator I, sentinel_for<I> S, class T1, class T2, class Proj = identity>
+    requires indirectly_writable<I, const T2&> &&
+             indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*>
+    constexpr I
+      ranges::replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = {});   // since C++20
+
+  template<input_range R, class T1, class T2, class Proj = identity>
+    requires indirectly_writable<iterator_t<R>, const T2&> &&
+             indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
+    constexpr borrowed_iterator_t<R>
+      ranges::replace(R&& r, const T1& old_value, const T2& new_value, Proj proj = {});             // since C++20
+
+  template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+           indirect_unary_predicate<projected<I, Proj>> Pred>
+    requires indirectly_writable<I, const T&>
+    constexpr I ranges::replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = {}); // since C++20
+
+  template<input_range R, class T, class Proj = identity,
+           indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+    requires indirectly_writable<iterator_t<R>, const T&>
+    constexpr borrowed_iterator_t<R>
+      ranges::replace_if(R&& r, Pred pred, const T& new_value, Proj proj = {});                     // since C++20
+
 }
 
     constexpr bool     // constexpr in C++20
     all_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     any_of(InputIterator first, InputIterator last, Predicate pred);

 #include <__algorithm/ranges_lower_bound.h>
 #include <__algorithm/ranges_max.h>
 #include <__algorithm/ranges_max_element.h>
 #include <__algorithm/ranges_min.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_minmax.h>
 #include <__algorithm/ranges_minmax_element.h>
 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_none_of.h>
+#include <__algorithm/ranges_replace.h>
+#include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>
 #include <__algorithm/ranges_upper_bound.h>
 #include <__algorithm/remove.h>
 #include <__algorithm/remove_copy.h>
 #include <__algorithm/remove_copy_if.h>
 #include <__algorithm/remove_if.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module ranges_max               { private header "__algorithm/ranges_max.h" }
       module ranges_max_element       { private header "__algorithm/ranges_max_element.h" }
       module ranges_min               { private header "__algorithm/ranges_min.h" }
       module ranges_min_element       { private header "__algorithm/ranges_min_element.h" }
       module ranges_minmax            { private header "__algorithm/ranges_minmax.h" }
       module ranges_minmax_element    { private header "__algorithm/ranges_minmax_element.h" }
       module ranges_mismatch          { private header "__algorithm/ranges_mismatch.h" }
       module ranges_none_of           { private header "__algorithm/ranges_none_of.h" }
+      module ranges_replace           { private header "__algorithm/ranges_replace.h" }
+      module ranges_replace_if        { private header "__algorithm/ranges_replace_if.h" }
       module ranges_reverse           { private header "__algorithm/ranges_reverse.h" }
       module ranges_swap_ranges       { private header "__algorithm/ranges_swap_ranges.h" }
       module ranges_transform         { private header "__algorithm/ranges_transform.h" }
       module ranges_upper_bound       { private header "__algorithm/ranges_upper_bound.h" }
       module remove                   { private header "__algorithm/remove.h" }
       module remove_copy              { private header "__algorithm/remove_copy.h" }
       module remove_copy_if           { private header "__algorithm/remove_copy_if.h" }
       module remove_if                { private header "__algorithm/remove_if.h" }

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

#endif
     //(void)std::ranges::push_heap(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::push_heap(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(a, first2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_if(a, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(first, last, first2, UnaryTrue(&copies), value); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(a, first2, UnaryTrue(&copies), value); assert(copies == 0);
-    //(void)std::ranges::replace_if(first, last, UnaryTrue(&copies), value); assert(copies == 0);
-    //(void)std::ranges::replace_if(a, UnaryTrue(&copies), value); assert(copies == 0);
+    (void)std::ranges::replace_if(first, last, UnaryTrue(&copies), value); assert(copies == 0);
+    (void)std::ranges::replace_if(a, UnaryTrue(&copies), value); assert(copies == 0);
     //(void)std::ranges::search(first, last, first2, mid2, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::search(a, b, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(first, last, count, value, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(a, count, value, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::set_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_difference(a, b, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_intersection(a, b, first2, Less(&copies)); assert(copies == 0);

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp

#endif
     //(void)std::ranges::remove(first, last, value, Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove(a, value, Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_if(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::replace_copy(first, last, first2, value, T(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::replace_copy(a, first2, value, T(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(first, last, first2, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(a, first2, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::replace(first, last, value, T(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::replace(a, value, T(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::replace_if(first, last, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::replace_if(a, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::replace(first, last, value, T(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::replace(a, value, T(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::replace_if(first, last, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::replace_if(a, UnaryTrue(), T(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::search(first, last, first2, mid2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::search(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(first, last, count, value, Equal(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(a, count, value, Equal(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_difference(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_difference(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_intersection(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/ranges_max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max.h'}}
 #include <__algorithm/ranges_max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}}
 #include <__algorithm/ranges_min.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min.h'}}
 #include <__algorithm/ranges_min_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min_element.h'}}
 #include <__algorithm/ranges_minmax.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax.h'}}
 #include <__algorithm/ranges_minmax_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax_element.h'}}
 #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}}
 #include <__algorithm/ranges_none_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}}
+#include <__algorithm/ranges_replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace.h'}}
+#include <__algorithm/ranges_replace_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}}
 #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}}
 #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}}
 #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}}
 #include <__algorithm/ranges_upper_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_upper_bound.h'}}
 #include <__algorithm/remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove.h'}}
 #include <__algorithm/remove_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy.h'}}
 #include <__algorithm/remove_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy_if.h'}}
 #include <__algorithm/remove_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_if.h'}}

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges.replace.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<input_iterator I, sentinel_for<I> S, class T1, class T2, class Proj = identity>
+//   requires indirectly_writable<I, const T2&> &&
+//            indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*>
+//   constexpr I
+//     ranges::replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = {});
+// template<input_range R, class T1, class T2, class Proj = identity>
+//   requires indirectly_writable<iterator_t<R>, const T2&> &&
+//            indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
+//   constexpr borrowed_iterator_t<R>
+//     ranges::replace(R&& r, const T1& old_value, const T2& new_value, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "boolean_testable.h"
+#include "test_iterators.h"
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>>
+concept HasReplaceIt = requires(Iter iter, Sent sent) { std::ranges::replace(iter, sent, 0, 0); };
+
+static_assert(HasReplaceIt<int*>);
+static_assert(!HasReplaceIt<InputIteratorNotDerivedFrom>);
+static_assert(!HasReplaceIt<InputIteratorNotIndirectlyReadable>);
+static_assert(!HasReplaceIt<InputIteratorNotInputOrOutputIterator>);
+static_assert(!HasReplaceIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasReplaceIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasReplaceIt<int**>); // not indirectly_writable
+static_assert(!HasReplaceIt<IndirectBinaryPredicateNotIndirectlyReadable>);
+
+template <class Range>
+concept HasReplaceR = requires(Range range) { std::ranges::replace(range, 0, 0); };
+
+static_assert(HasReplaceR<UncheckedRange<int*>>);
+static_assert(!HasReplaceR<InputRangeNotDerivedFrom>);
+static_assert(!HasReplaceR<InputRangeNotIndirectlyReadable>);
+static_assert(!HasReplaceR<InputRangeNotInputOrOutputIterator>);
+static_assert(!HasReplaceR<InputRangeNotSentinelSemiregular>);
+static_assert(!HasReplaceR<InputRangeNotSentinelEqualityComparableWith>);
+static_assert(!HasReplaceR<UncheckedRange<int**>>); // not indirectly_writable
+static_assert(!HasReplaceR<InputRangeIndirectBinaryPredicateNotIndirectlyReadable>);
+
+template <int N>
+struct Data {
+  std::array<int, N> input;
+  int oldval;
+  int newval;
+  std::array<int, N> expected;
+};
+
+template <class Iter, class Sent, int N>
+constexpr void test(Data<N> d) {
+  {
+    auto a = d.input;
+    std::same_as<Iter> decltype(auto) ret = std::ranges::replace(Iter(a.data()), Sent(Iter(a.data() + N)),
+                                                                 d.oldval,
+                                                                 d.newval);
+    assert(base(ret) == a.data() + N);
+    assert(a == d.expected);
+  }
+  {
+    auto a = d.input;
+    auto range = std::ranges::subrange(Iter(a.data()), Sent(Iter(a.data() + N)));
+    std::same_as<Iter> decltype(auto) ret = std::ranges::replace(range, d.oldval, d.newval);
+    assert(base(ret) == a.data() + N);
+    assert(a == d.expected);
+  }
+}
+
+template <class Iter, class Sent = Iter>
+constexpr void test_iterators() {
+  // simple test
+  test<Iter, Sent, 4>({.input = {1, 2, 3, 4}, .oldval = 2, .newval = 23, .expected = {1, 23, 3, 4}});
+  // no match
+  test<Iter, Sent, 4>({.input = {1, 2, 3, 4}, .oldval = 5, .newval = 23, .expected = {1, 2, 3, 4}});
+  // all match
+  test<Iter, Sent, 4>({.input = {1, 1, 1, 1}, .oldval = 1, .newval = 23, .expected = {23, 23, 23, 23}});
+  // empty range
+  test<Iter, Sent, 0>({.input = {}, .oldval = 1, .newval = 23, .expected = {}});
+  // single element range
+  test<Iter, Sent, 1>({.input = {1}, .oldval = 1, .newval = 2, .expected = {2}});
+}
+
+constexpr bool test() {
+  test_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
+  test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
+  test_iterators<forward_iterator<int*>>();
+  test_iterators<bidirectional_iterator<int*>>();
+  test_iterators<random_access_iterator<int*>>();
+  test_iterators<contiguous_iterator<int*>>();
+  test_iterators<int*>();
+
+  { // check that the projection is used
+    struct S {
+      constexpr S(int i_) : i(i_) {}
+      int i;
+    };
+    {
+      S a[] = {1, 2, 3, 4};
+      std::ranges::replace(a, a + 4, 3, S{0}, &S::i);
+    }
+    {
+      S a[] = {1, 2, 3, 4};
+      std::ranges::replace(a, 3, S{0}, &S::i);
+    }
+  }
+
+  { // check that std::invoke is used
+    struct S {
+      constexpr S(int i_) : i(i_) {}
+      constexpr bool operator==(const S&) const = default;
+      constexpr const S& identity() const { return *this; }
+      int i;
+    };
+    {
+      S a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::replace(std::begin(a), std::end(a), S{1}, S{2}, &S::identity);
+      assert(ret == a + 4);
+    }
+    {
+      S a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::replace(a, S{1}, S{2}, &S::identity);
+      assert(ret == a + 4);
+    }
+  }
+
+  { // check that the implicit conversion to bool works
+    {
+      StrictComparable<int> a[] = {1, 2, 2, 4};
+      auto ret = std::ranges::replace(std::begin(a), std::end(a), 1, 2);
+      assert(ret == std::end(a));
+    }
+    {
+      StrictComparable<int> a[] = {1, 2, 2, 4};
+      auto ret = std::ranges::replace(a, 1, 2);
+      assert(ret == std::end(a));
+    }
+  }
+
+  { // check that T1 and T2 can be different types
+    {
+      StrictComparable<int> a[] = {1, 2, 2, 4};
+      auto ret = std::ranges::replace(std::begin(a), std::end(a), '\0', 2ull);
+      assert(ret == std::end(a));
+    }
+    {
+      StrictComparable<int> a[] = {1, 2, 2, 4};
+      auto ret = std::ranges::replace(a, '\0', 2ull);
+      assert(ret == std::end(a));
+    }
+  }
+
+  { // check that std::ranges::dangling is returned
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
+        std::ranges::replace(std::array {1, 2, 3, 4}, 1, 1);
+  }
+
+  { // check that the complexity requirements are met
+    {
+      auto projectionCount = 0;
+      auto proj = [&](int i) { ++projectionCount; return i; };
+      int a[] = {1, 2, 3, 4, 5};
+      auto ret = std::ranges::replace(std::begin(a), std::end(a), 1, 2, proj);
+      assert(ret == a + 5);
+      assert(projectionCount == 5);
+    }
+    {
+      auto projectionCount = 0;
+      auto proj = [&](int i) { ++projectionCount; return i; };
+      int a[] = {1, 2, 3, 4, 5};
+      auto ret = std::ranges::replace(a, 1, 2, proj);
+      assert(ret == a + 5);
+      assert(projectionCount == 5);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/ranges.replace_if.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+//          indirect_unary_predicate<projected<I, Proj>> Pred>
+//   requires indirectly_writable<I, const T&>
+//   constexpr I ranges::replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = {});
+// template<input_range R, class T, class Proj = identity,
+//          indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+//   requires indirectly_writable<iterator_t<R>, const T&>
+//   constexpr borrowed_iterator_t<R>
+//     ranges::replace_if(R&& r, Pred pred, const T& new_value, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "boolean_testable.h"
+#include "test_iterators.h"
+
+struct FalsePredicate {
+  bool operator()(auto&&) { return false; }
+};
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>>
+concept HasReplaceIt = requires(Iter iter, Sent sent) { std::ranges::replace_if(iter, sent, FalsePredicate{}, 0); };
+
+static_assert(HasReplaceIt<int*>);
+static_assert(!HasReplaceIt<InputIteratorNotDerivedFrom>);
+static_assert(!HasReplaceIt<InputIteratorNotIndirectlyReadable>);
+static_assert(!HasReplaceIt<InputIteratorNotInputOrOutputIterator>);
+static_assert(!HasReplaceIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasReplaceIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasReplaceIt<int**>); // not indirectly_writable
+static_assert(!HasReplaceIt<IndirectBinaryPredicateNotIndirectlyReadable>);
+
+template <class Range>
+concept HasReplaceR = requires(Range range) { std::ranges::replace_if(range, FalsePredicate{}, 0); };
+
+static_assert(HasReplaceR<UncheckedRange<int*>>);
+static_assert(!HasReplaceR<InputRangeNotDerivedFrom>);
+static_assert(!HasReplaceR<InputRangeNotIndirectlyReadable>);
+static_assert(!HasReplaceR<InputRangeNotInputOrOutputIterator>);
+static_assert(!HasReplaceR<InputRangeNotSentinelSemiregular>);
+static_assert(!HasReplaceR<InputRangeNotSentinelEqualityComparableWith>);
+static_assert(!HasReplaceR<UncheckedRange<int**>>); // not indirectly_writable
+static_assert(!HasReplaceR<InputRangeIndirectBinaryPredicateNotIndirectlyReadable>);
+
+template <class Iter, class Sent, int N, class Pred>
+constexpr void test(std::array<int, N> a_, Pred pred, int val, std::array<int, N> expected) {
+  {
+    auto a = a_;
+    std::same_as<Iter> auto ret = std::ranges::replace_if(Iter(a.data()), Sent(Iter(a.data() + N)),
+                                                          pred,
+                                                          val);
+    assert(base(ret) == a.data() + N);
+    assert(a == expected);
+  }
+  {
+    auto a = a_;
+    auto range = std::ranges::subrange(Iter(a.data()), Sent(Iter(a.data() + N)));
+    std::same_as<Iter> auto ret = std::ranges::replace_if(range, pred, val);
+    assert(base(ret) == a.data() + N);
+    assert(a == expected);
+  }
+}
+
+template <class Iter, class Sent = Iter>
+constexpr void test_iterators() {
+  // simple test
+  test<Iter, Sent, 4>({1, 2, 3, 4}, [](int i) { return i < 3; }, 23, {23, 23, 3, 4});
+  // no match
+  test<Iter, Sent, 4>({1, 2, 3, 4}, [](int i) { return i < 0; }, 23, {1, 2, 3, 4});
+  // all match
+  test<Iter, Sent, 4>({1, 2, 3, 4}, [](int i) { return i > 0; }, 23, {23, 23, 23, 23});
+  // empty range
+  test<Iter, Sent, 0>({}, [](int i) { return i > 0; }, 23, {});
+  // single element range
+  test<Iter, Sent, 1>({1}, [](int i) { return i > 0; }, 2, {2});
+}
+
+constexpr bool test() {
+  test_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
+  test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
+  test_iterators<forward_iterator<int*>>();
+  test_iterators<bidirectional_iterator<int*>>();
+  test_iterators<random_access_iterator<int*>>();
+  test_iterators<contiguous_iterator<int*>>();
+  test_iterators<int*>();
+
+  { // check that the projection is used
+    struct S {
+      constexpr S(int i_) : i(i_) {}
+      int i;
+    };
+    {
+      S a[] = {1, 2, 3, 4};
+      std::ranges::replace_if(a, a + 4, [](int i) { return i == 3; }, S{0}, &S::i);
+    }
+    {
+      S a[] = {1, 2, 3, 4};
+      std::ranges::replace_if(a, [](int i) { return i == 3; }, S{0}, &S::i);
+    }
+  }
+
+  { // check that std::invoke is used
+    struct S {
+      constexpr S(int i_) : i(i_) {}
+      constexpr bool check() const { return false; }
+      constexpr const S& identity() const { return *this; }
+      int i;
+    };
+    {
+      S a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::replace_if(std::begin(a), std::end(a), &S::check, S{2}, &S::identity);
+      assert(ret == std::end(a));
+    }
+    {
+      S a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::replace_if(a, &S::check, S{2}, &S::identity);
+      assert(ret == std::end(a));
+    }
+  }
+
+  { // check that the implicit conversion to bool works
+    {
+      int a[] = {1, 2, 2, 4};
+      auto ret = std::ranges::replace_if(std::begin(a), std::end(a), [](int) { return BooleanTestable{false}; }, 2);
+      assert(ret == std::end(a));
+    }
+    {
+      int a[] = {1, 2, 2, 4};
+      auto ret = std::ranges::replace_if(a, [](int) { return BooleanTestable{false}; }, 2);
+      assert(ret == std::end(a));
+    }
+  }
+
+  { // check that std::ranges::dangling is returned
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
+        std::ranges::replace_if(std::array {1, 2, 3, 4}, [](int) { return false; }, 1);
+  }
+
+  { // check that the complexity requirements are met
+    {
+      int predicateCount = 0;
+      auto pred = [&](int) { ++predicateCount; return false; };
+      auto projectionCount = 0;
+      auto proj = [&](int i) { ++projectionCount; return i; };
+      int a[] = {1, 2, 3, 4, 5};
+      auto ret = std::ranges::replace_if(a, a + 5, pred, 1, proj);
+      assert(ret == a + 5);
+      assert(predicateCount == 5);
+      assert(projectionCount == 5);
+    }
+    {
+      int predicateCount = 0;
+      auto pred = [&](int) { ++predicateCount; return false; };
+      auto projectionCount = 0;
+      auto proj = [&](int i) { ++projectionCount; return i; };
+      int a[] = {1, 2, 3, 4, 5};
+      auto ret = std::ranges::replace_if(a, pred, 1, proj);
+      assert(ret == a + 5);
+      assert(predicateCount == 5);
+      assert(projectionCount == 5);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 //static_assert(test(std::ranges::partition_point, a, odd));
 //static_assert(test(std::ranges::pop_heap, a));
 //static_assert(test(std::ranges::prev_permutation, a));
 //static_assert(test(std::ranges::push_heap, a));
 //static_assert(test(std::ranges::remove, a, 42));
 //static_assert(test(std::ranges::remove_copy, a, a, 42));
 //static_assert(test(std::ranges::remove_copy_if, a, a, odd));
 //static_assert(test(std::ranges::remove_if, a, odd));
-//static_assert(test(std::ranges::replace, a, 42, 43));
+static_assert(test(std::ranges::replace, a, 42, 43));
 //static_assert(test(std::ranges::replace_copy, a, a, 42, 43));
 //static_assert(test(std::ranges::replace_copy_if, a, a, odd, 43));
-//static_assert(test(std::ranges::replace_if, a, odd, 43));
+static_assert(test(std::ranges::replace_if, a, odd, 43));
 static_assert(test(std::ranges::reverse, a));
 //static_assert(test(std::ranges::reverse_copy, a, a));
 //static_assert(test(std::ranges::rotate, a, a+5));
 //static_assert(test(std::ranges::rotate_copy, a, a+5, a));
 //static_assert(test(std::ranges::sample, a, a, 5));
 //static_assert(test(std::ranges::search, a, a));
 //static_assert(test(std::ranges::search_n, a, 10, 42));
 //static_assert(test(std::ranges::set_difference, a, a, a));

libcxx/test/support/almost_satisfies_types.h

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef ALMOST_SATISFIES_TYPES_H
 #define ALMOST_SATISFIES_TYPES_H
 
+#include <functional>
 #include <iterator>
 #include <ranges>
 
 #include "test_iterators.h"
 
 template <class T, class U = sentinel_wrapper<T>>
 class UncheckedRange {
 public:

 
 using OutputRangeNotIndirectlyWritable = UncheckedRange<OutputIteratorNotIndirectlyWritable>;
 
 static_assert(std::input_or_output_iterator<OutputIteratorNotIndirectlyWritable>);
 static_assert(!std::indirectly_writable<OutputIteratorNotIndirectlyWritable, int>);
 static_assert(!std::output_iterator<OutputIteratorNotIndirectlyWritable, int>);
 static_assert(!std::ranges::output_range<OutputIteratorNotIndirectlyWritable, int>);
 
+class IndirectBinaryPredicateNotIndirectlyReadable {
+public:
+  using difference_type = long;
+  using iterator_category = std::input_iterator_tag;
+
+  int& operator++();
+  void operator++(int);
+  const int& operator*() const;
+};
+
+using InputRangeIndirectBinaryPredicateNotIndirectlyReadable
+     = UncheckedRange<cpp20_input_iterator<int*>, IndirectBinaryPredicateNotIndirectlyReadable>;
+
+static_assert(!std::indirect_binary_predicate<std::ranges::equal_to, IndirectBinaryPredicateNotIndirectlyReadable, int*>);
+
 #endif // ALMOST_SATISFIES_TYPES_H