[libc++][PSTL] Implement std::replace{,_if,_copy,_copy_if}

[philnik]

Try to fix CI

[ldionne]

libcxx/include/CMakeLists.txt

85

Can we remove any old PSTL code with this patch?

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

30

There needs to be a test with a non-empty range but no match. Here and everywhere.

31

Needs a test where you "match" more than one element in the range. For example

std::array a = {1, 2, 3, 4, 3, 3, 5, 6, 3};
// then replace 3 by 9, you need to end up with {1, 2, 9, 4, 9, 9, 5, 6, 9}

This comment applies to all the other algorithms as well.

[philnik]

Address comments

[philnik]

Try to fix CI

libcxx/include/CMakeLists.txt

set(files
   __algorithm/pstl_backends/cpu_backends/backend.h
   __algorithm/pstl_backends/cpu_backends/fill.h
   __algorithm/pstl_backends/cpu_backends/find_if.h
   __algorithm/pstl_backends/cpu_backends/for_each.h
   __algorithm/pstl_backends/cpu_backends/merge.h
   __algorithm/pstl_backends/cpu_backends/serial.h
   __algorithm/pstl_backends/cpu_backends/stable_sort.h
   __algorithm/pstl_backends/cpu_backends/thread.h
   __algorithm/pstl_backends/cpu_backends/transform.h
   __algorithm/pstl_backends/cpu_backends/transform_reduce.h
   __algorithm/pstl_copy.h
   __algorithm/pstl_count.h
   __algorithm/pstl_fill.h
   __algorithm/pstl_find.h
   __algorithm/pstl_for_each.h
   __algorithm/pstl_frontend_dispatch.h
   __algorithm/pstl_merge.h
+  __algorithm/pstl_replace.h
   __algorithm/pstl_stable_sort.h
   __algorithm/pstl_transform.h
   __algorithm/push_heap.h
   __algorithm/ranges_adjacent_find.h
   __algorithm/ranges_all_of.h
   __algorithm/ranges_any_of.h
   __algorithm/ranges_binary_search.h
   __algorithm/ranges_clamp.h

libcxx/include/__algorithm/pstl_backend.h

implemented, all the algorithms will eventually forward to the basis algorithms listed above:
   __iter_value_type<_Iterator> __pstl_reduce(_Backend, _Iterator __first, _Iterator __last);
 
   template <class _ExecuitonPolicy, class _Iterator, class _Tp>
   __iter_diff_t<_Iterator> __pstl_count(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value);
 
   template <class _ExecutionPolicy, class _Iterator, class _Predicate>
   __iter_diff_t<_Iterator> __pstl_count_if(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred);
 
+  template <class _ExecutionPolicy, class _Iterator, class _Tp>
+  void __pstl_replace(_Backend, _Iterator __first, _Iterator __last, const _Tp& __old_value, const _Tp& __new_value);
+
+  template <class _ExecutionPolicy, class _Iterator, class _Pred, class _Tp>
+  void __pstl_replace_if(_Backend, _Iterator __first, _Iterator __last, _Pred __pred, const _Tp& __new_value);
+
+  template <class _ExecutionPolicy, class _Iterator, class _OutIterator, class _Tp>
+  void __pstl_replace_copy(_Backend,
+                           _Iterator __first,
+                           _Iterator __last,
+                           _OutIterator __result,
+                           const _Tp& __old_value,
+                           const _Tp& __new_value);
+
+  template <class _ExecutionPolicy, class _Iterator, class _OutIterator, class _Pred, class _Tp>
+  void __pstl_replace_copy_if(_Backend,
+                              _Iterator __first,
+                              _Iterator __last,
+                              _OutIterator __result,
+                              _Pred __pred,
+                              const _Tp& __new_value);
+
 // TODO: Complete this list
 
 */
 
 template <class _ExecutionPolicy>
 struct __select_backend;
 
 template <>

libcxx/include/__algorithm/pstl_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_PSTL_REPLACE_H
+#define _LIBCPP___ALGORITHM_PSTL_REPLACE_H
+
+#include <__algorithm/pstl_backend.h>
+#include <__algorithm/pstl_for_each.h>
+#include <__algorithm/pstl_frontend_dispatch.h>
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class>
+void __pstl_replace_if();
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Pred,
+          class _Tp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void
+replace_if(_ExecutionPolicy&& __policy,
+           _ForwardIterator __first,
+           _ForwardIterator __last,
+           _Pred __pred,
+           const _Tp& __new_value) {
+  std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_replace_if),
+      [&__policy](_ForwardIterator __g_first, _ForwardIterator __g_last, _Pred __g_pred, const _Tp& __g_new_value) {
+        std::for_each(__policy, __g_first, __g_last, [&](__iter_reference<_ForwardIterator> __element) {
+          if (__g_pred(__element))
+            __element = __g_new_value;
+        });
+      },
+      std::move(__first),
+      std::move(__last),
+      std::move(__pred),
+      __new_value);
+}
+
+template <class>
+void __pstl_replace();
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Tp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void
+replace(_ExecutionPolicy&& __policy,
+        _ForwardIterator __first,
+        _ForwardIterator __last,
+        const _Tp& __old_value,
+        const _Tp& __new_value) {
+  std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_replace),
+      [&__policy](
+          _ForwardIterator __g_first, _ForwardIterator __g_last, const _Tp& __g_old_value, const _Tp& __g_new_value) {
+        std::replace_if(
+            __policy,
+            std::move(__g_first),
+            std::move(__g_last),
+            [&](__iter_reference<_ForwardIterator> __element) { return __element == __g_old_value; },
+            __g_new_value);
+      },
+      std::move(__first),
+      std::move(__last),
+      __old_value,
+      __new_value);
+}
+
+template <class>
+void __pstl_replace_copy_if();
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _ForwardOutIterator,
+          class _Pred,
+          class _Tp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void replace_copy_if(
+    _ExecutionPolicy&& __policy,
+    _ForwardIterator __first,
+    _ForwardIterator __last,
+    _ForwardOutIterator __result,
+    _Pred __pred,
+    const _Tp& __new_value) {
+  std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_replace_copy_if),
+      [&__policy](_ForwardIterator __g_first,
+                  _ForwardIterator __g_last,
+                  _ForwardOutIterator __g_result,
+                  _Pred __g_pred,
+                  const _Tp& __g_new_value) {
+        std::transform(__policy, __g_first, __g_last, __g_result, [&](__iter_reference<_ForwardIterator> __element) {
+          return __g_pred(__element) ? __g_new_value : __element;
+        });
+      },
+      std::move(__first),
+      std::move(__last),
+      std::move(__result),
+      std::move(__pred),
+      __new_value);
+}
+
+template <class>
+void __pstl_replace_copy();
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _ForwardOutIterator,
+          class _Tp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void replace_copy(
+    _ExecutionPolicy&& __policy,
+    _ForwardIterator __first,
+    _ForwardIterator __last,
+    _ForwardOutIterator __result,
+    const _Tp& __old_value,
+    const _Tp& __new_value) {
+  std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_replace_copy),
+      [&__policy](_ForwardIterator __g_first,
+                  _ForwardIterator __g_last,
+                  _ForwardOutIterator __g_result,
+                  const _Tp& __g_old_value,
+                  const _Tp& __g_new_value) {
+        return std::replace_copy_if(
+            __policy,
+            std::move(__g_first),
+            std::move(__g_last),
+            std::move(__g_result),
+            [&](__iter_reference<_ForwardIterator> __element) { return __element == __g_old_value; },
+            __g_new_value);
+      },
+      std::move(__first),
+      std::move(__last),
+      std::move(__result),
+      __old_value,
+      __new_value);
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_REPLACE_H

libcxx/include/__pstl/internal/glue_algorithm_impl.h

return __pstl::__internal::__pattern_walk2(
       __last1,
       __first2,
       [](_ReferenceType1 __x, _ReferenceType2 __y) {
         using std::swap;
         swap(__x, __y);
       });
 }
 
-// [alg.transform]
-
-template <class _ExecutionPolicy,
-          class _ForwardIterator1,
-          class _ForwardIterator2,
-          class _ForwardIterator,
-          class _BinaryOperation>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
-transform(_ExecutionPolicy&& __exec,
-          _ForwardIterator1 __first1,
-          _ForwardIterator1 __last1,
-          _ForwardIterator2 __first2,
-          _ForwardIterator __result,
-          _BinaryOperation __op) {
-  typedef typename iterator_traits<_ForwardIterator1>::reference _Input1Type;
-  typedef typename iterator_traits<_ForwardIterator2>::reference _Input2Type;
-  typedef typename iterator_traits<_ForwardIterator>::reference _OutputType;
-
-  auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2, __result);
-
-  return __pstl::__internal::__pattern_walk3(
-      __dispatch_tag,
-      std::forward<_ExecutionPolicy>(__exec),
-      __first1,
-      __last1,
-      __first2,
-      __result,
-      [__op](_Input1Type x, _Input2Type y, _OutputType z) mutable { z = __op(x, y); });
-}
-
-// [alg.replace]
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate, class _Tp>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
-replace_if(_ExecutionPolicy&& __exec,
-           _ForwardIterator __first,
-           _ForwardIterator __last,
-           _UnaryPredicate __pred,
-           const _Tp& __new_value) {
-  typedef typename iterator_traits<_ForwardIterator>::reference _ElementType;
-
-  auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
-
-  __pstl::__internal::__pattern_walk1(
-      __dispatch_tag,
-      std::forward<_ExecutionPolicy>(__exec),
-      __first,
-      __last,
-      [&__pred, &__new_value](_ElementType __elem) {
-        if (__pred(__elem)) {
-          __elem = __new_value;
-        }
-      });
-}
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
-replace(_ExecutionPolicy&& __exec,
-        _ForwardIterator __first,
-        _ForwardIterator __last,
-        const _Tp& __old_value,
-        const _Tp& __new_value) {
-  std::replace_if(
-      std::forward<_ExecutionPolicy>(__exec),
-      __first,
-      __last,
-      __pstl::__internal::__equal_value<_Tp>(__old_value),
-      __new_value);
-}
-
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _UnaryPredicate, class _Tp>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> replace_copy_if(
-    _ExecutionPolicy&& __exec,
-    _ForwardIterator1 __first,
-    _ForwardIterator1 __last,
-    _ForwardIterator2 __result,
-    _UnaryPredicate __pred,
-    const _Tp& __new_value) {
-  typedef typename iterator_traits<_ForwardIterator1>::reference _InputType;
-  typedef typename iterator_traits<_ForwardIterator2>::reference _OutputType;
-
-  auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
-
-  return __pstl::__internal::__pattern_walk2(
-      __dispatch_tag,
-      std::forward<_ExecutionPolicy>(__exec),
-      __first,
-      __last,
-      __result,
-      [__pred, &__new_value](_InputType __x, _OutputType __y) mutable { __y = __pred(__x) ? __new_value : __x; });
-}
-
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> replace_copy(
-    _ExecutionPolicy&& __exec,
-    _ForwardIterator1 __first,
-    _ForwardIterator1 __last,
-    _ForwardIterator2 __result,
-    const _Tp& __old_value,
-    const _Tp& __new_value) {
-  return std::replace_copy_if(
-      std::forward<_ExecutionPolicy>(__exec),
-      __first,
-      __last,
-      __result,
-      __pstl::__internal::__equal_value<_Tp>(__old_value),
-      __new_value);
-}
-
 // [alg.generate]
 template <class _ExecutionPolicy, class _ForwardIterator, class _Generator>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
 generate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Generator __g) {
   auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
 
   __pstl::__internal::__pattern_generate(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last, __g);
 }

libcxx/include/algorithm

 #include <__algorithm/prev_permutation.h>
 #include <__algorithm/pstl_any_all_none_of.h>
 #include <__algorithm/pstl_copy.h>
 #include <__algorithm/pstl_count.h>
 #include <__algorithm/pstl_fill.h>
 #include <__algorithm/pstl_find.h>
 #include <__algorithm/pstl_for_each.h>
 #include <__algorithm/pstl_merge.h>
+#include <__algorithm/pstl_replace.h>
 #include <__algorithm/pstl_stable_sort.h>
 #include <__algorithm/pstl_transform.h>
 #include <__algorithm/push_heap.h>
 #include <__algorithm/ranges_adjacent_find.h>
 #include <__algorithm/ranges_all_of.h>
 #include <__algorithm/ranges_any_of.h>
 #include <__algorithm/ranges_binary_search.h>
 #include <__algorithm/ranges_clamp.h>

libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp

 bool pstl_fill_n_called = false;
 
 template <class, class ForwardIterator, class Size, class Func>
 void __pstl_fill_n(TestBackend, ForwardIterator, Size, Func) {
   assert(!pstl_fill_n_called);
   pstl_fill_n_called = true;
 }
 
+bool pstl_replace_called = false;
+
+template <class, class ForwardIterator, class T>
+void __pstl_replace(TestBackend, ForwardIterator, ForwardIterator, const T&, const T&) {
+  assert(!pstl_replace_called);
+  pstl_replace_called = true;
+}
+
+bool pstl_replace_if_called = false;
+
+template <class, class ForwardIterator, class T, class Func>
+void __pstl_replace_if(TestBackend, ForwardIterator, ForwardIterator, Func, const T&) {
+  assert(!pstl_replace_if_called);
+  pstl_replace_if_called = true;
+}
+
+bool pstl_replace_copy_called = false;
+
+template <class, class ForwardIterator, class ForwardOutIterator, class T>
+void __pstl_replace_copy(TestBackend, ForwardIterator, ForwardIterator, ForwardOutIterator, const T&, const T&) {
+  assert(!pstl_replace_copy_called);
+  pstl_replace_copy_called = true;
+}
+
+bool pstl_replace_copy_if_called = false;
+
+template <class, class ForwardIterator, class ForwardOutIterator, class T, class Func>
+void __pstl_replace_copy_if(TestBackend, ForwardIterator, ForwardIterator, ForwardOutIterator, Func, const T&) {
+  assert(!pstl_replace_copy_if_called);
+  pstl_replace_copy_if_called = true;
+}
+
 bool pstl_unary_transform_called = false;
 
 template <class, class ForwardIterator, class ForwardOutIterator, class UnaryOperation>
 ForwardOutIterator __pstl_transform(TestBackend, ForwardIterator, ForwardIterator, ForwardOutIterator, UnaryOperation) {
   assert(!pstl_unary_transform_called);
   pstl_unary_transform_called = true;
   return {};
 }
int main(int, char**) {
   (void)std::find_if(TestPolicy{}, std::begin(a), std::end(a), pred);
   assert(std::pstl_find_if_called);
   (void)std::find_if_not(TestPolicy{}, std::begin(a), std::end(a), pred);
   assert(std::pstl_find_if_not_called);
   (void)std::for_each(TestPolicy{}, std::begin(a), std::end(a), pred);
   assert(std::pstl_for_each_called);
   (void)std::for_each_n(TestPolicy{}, std::begin(a), std::size(a), pred);
   assert(std::pstl_for_each_n_called);
+  (void)std::replace(TestPolicy{}, std::begin(a), std::end(a), 0, 0);
+  assert(std::pstl_replace_called);
+  (void)std::replace_if(TestPolicy{}, std::begin(a), std::end(a), pred, 0);
+  assert(std::pstl_replace_if_called);
+  (void)std::replace_copy(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), 0, 0);
+  assert(std::pstl_replace_copy_called);
+  (void)std::replace_copy_if(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), pred, 0);
+  assert(std::pstl_replace_copy_if_called);
   (void)std::transform(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), pred);
   assert(std::pstl_unary_transform_called);
   (void)std::transform(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), std::begin(a), pred);
   assert(std::pstl_unary_transform_called);
   (void)std::reduce(TestPolicy{}, std::begin(a), std::end(a), 0, pred);
   assert(std::pstl_reduce_with_init_called);
   (void)std::reduce(TestPolicy{}, std::begin(a), std::end(a));
   assert(std::pstl_reduce_without_init_called);
   (void)std::transform_reduce(TestPolicy{}, std::begin(a), std::end(a), 0, pred, pred);
   assert(std::pstl_unary_transform_reduce_called);
   (void)std::transform_reduce(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), 0, pred, pred);
   assert(std::pstl_binary_transform_reduce_called);
 
   return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// template<class ExecutionPolicy, class ForwardIterator, class T>
+//   void replace(ExecutionPolicy&& exec,
+//                ForwardIterator first, ForwardIterator last,
+//                const T& old_value, const T& new_value);
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <vector>
+
+#include "type_algorithms.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+template <class Iter>
+struct Test {
+  template <class ExecutionPolicy>
+  void operator()(ExecutionPolicy&& policy) {
+    { // simple test
+      std::array a = {1, 2, 3, 4, 5, 6, 7, 8};
+      std::replace(policy, Iter(std::begin(a)), Iter(std::end(a)), 3, 6);
+      assert((a == std::array{1, 2, 6, 4, 5, 6, 7, 8}));
+    }
+
+    { // empty range works
+      std::array<int, 0> a = {};
+      std::replace(policy, Iter(std::begin(a)), Iter(std::end(a)), 3, 6);
+    }
+
+    { // non-empty range without a match works
+      std::array a = {1, 2};
+      std::replace(policy, Iter(std::begin(a)), Iter(std::end(a)), 3, 6);
+    }
+
+    { // single element range works
+      std::array a = {3};
+      std::replace(policy, Iter(std::begin(a)), Iter(std::end(a)), 3, 6);
+      assert((a == std::array{6}));
+    }
+
+    { // two element range works
+      std::array a = {3, 4};
+      std::replace(policy, Iter(std::begin(a)), Iter(std::end(a)), 3, 6);
+      assert((a == std::array{6, 4}));
+    }
+
+    { // multiple matching elements work
+      std::array a = {1, 2, 3, 4, 3, 3, 5, 6, 3};
+      std::replace(policy, Iter(std::begin(a)), Iter(std::end(a)), 3, 9);
+      assert((a == std::array{1, 2, 9, 4, 9, 9, 5, 6, 9}));
+    }
+
+    { // large range works
+      std::vector<int> a(150, 3);
+      a[45] = 5;
+      std::replace(policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a)), 3, 6);
+
+      std::vector<int> comp(150, 6);
+      comp[45] = 5;
+      assert(std::equal(a.begin(), a.end(), comp.begin()));
+    }
+  }
+};
+
+struct ThrowOnCompare {};
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
+#endif
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+  std::set_terminate(terminate_successful);
+  ThrowOnCompare a[2];
+  try {
+    (void)std::replace(std::execution::par, std::begin(a), std::end(a), ThrowOnCompare{}, ThrowOnCompare{});
+  } catch (int) {
+    assert(false);
+  }
+#endif
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class T>
+//   ForwardIterator2
+//     replace_copy(ExecutionPolicy&& exec,
+//                  ForwardIterator1 first, ForwardIterator1 last,
+//                  ForwardIterator2 result,
+//                  const T& old_value, const T& new_value);
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <vector>
+
+#include "type_algorithms.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+template <class Iter>
+struct Test {
+  template <class ExecutionPolicy>
+  void operator()(ExecutionPolicy&& policy) {
+    { // simple test
+      std::array a = {1, 2, 3, 4, 5, 6, 7, 8};
+      std::array<int, a.size()> out;
+      std::replace_copy(policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), 3, 6);
+      assert((out == std::array{1, 2, 6, 4, 5, 6, 7, 8}));
+    }
+
+    { // empty range works
+      std::array<int, 0> a = {};
+      std::replace_copy(policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(a)), 3, 6);
+    }
+
+    { // non-empty range without a match works
+      std::array a = {1, 2};
+      std::array<int, a.size()> out;
+      std::replace_copy(policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(out.data()), 3, 6);
+      assert((out == std::array{1, 2}));
+    }
+
+    { // single element range works
+      std::array a = {3};
+      std::array<int, a.size()> out;
+      std::replace_copy(policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), 3, 6);
+      assert((out == std::array{6}));
+    }
+
+    { // two element range works
+      std::array a = {3, 4};
+      std::array<int, a.size()> out;
+      std::replace_copy(policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), 3, 6);
+      assert((out == std::array{6, 4}));
+    }
+
+    { // multiple matching elements work
+      std::array a = {1, 2, 3, 4, 3, 3, 5, 6, 3};
+      std::array<int, a.size()> out;
+      std::replace_copy(policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), 3, 9);
+      assert((out == std::array{1, 2, 9, 4, 9, 9, 5, 6, 9}));
+    }
+
+    { // large range works
+      std::vector<int> a(150, 3);
+      std::vector<int> out(a.size());
+      a[45] = 5;
+      std::replace_copy(policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a)), Iter(out.data()), 3, 6);
+
+      std::vector<int> comp(150, 6);
+      comp[45] = 5;
+      assert(std::equal(out.begin(), out.end(), comp.begin()));
+    }
+  }
+};
+
+struct ThrowOnCompare {};
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
+#endif
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+  std::set_terminate(terminate_successful);
+  ThrowOnCompare a[2];
+  try {
+    (void)std::replace_copy(
+        std::execution::par, std::begin(a), std::end(a), std::begin(a), ThrowOnCompare{}, ThrowOnCompare{});
+  } catch (int) {
+    assert(false);
+  }
+#endif
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy_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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+//          class Predicate, class T>
+//   ForwardIterator2
+//     replace_copy_if(ExecutionPolicy&& exec,
+//                     ForwardIterator1 first, ForwardIterator1 last,
+//                     ForwardIterator2 result,
+//                     Predicate pred, const T& new_value);
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <vector>
+
+#include "type_algorithms.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+template <class Iter>
+struct Test {
+  template <class ExecutionPolicy>
+  void operator()(ExecutionPolicy&& policy) {
+    { // simple test
+      std::array a = {1, 2, 3, 4, 5, 6, 7, 8};
+      std::array<int, a.size()> out;
+      std::replace_copy_if(
+          policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), [](int i) { return i == 3; }, 6);
+      assert((out == std::array{1, 2, 6, 4, 5, 6, 7, 8}));
+    }
+
+    { // empty range works
+      std::array<int, 0> a = {};
+      std::replace_copy_if(
+          policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(a)), [](int i) { return i == 3; }, 6);
+    }
+
+    { // non-empty range without a match works
+      std::array a = {1, 2};
+      std::array<int, a.size()> out;
+      std::replace_copy_if(
+          policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(out.data()), [](int i) { return i == 3; }, 6);
+      assert((out == std::array{1, 2}));
+    }
+
+    { // single element range works
+      std::array a = {3};
+      std::array<int, a.size()> out;
+      std::replace_copy_if(
+          policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), [](int i) { return i == 3; }, 6);
+      assert((out == std::array{6}));
+    }
+
+    { // two element range works
+      std::array a = {3, 4};
+      std::array<int, a.size()> out;
+      std::replace_copy_if(
+          policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), [](int i) { return i == 3; }, 6);
+      assert((out == std::array{6, 4}));
+    }
+
+    { // multiple matching elements work
+      std::array a = {1, 2, 3, 4, 3, 3, 5, 6, 3};
+      std::array<int, a.size()> out;
+      std::replace_copy_if(
+          policy, Iter(std::begin(a)), Iter(std::end(a)), Iter(std::begin(out)), [](int i) { return i == 3; }, 9);
+      assert((out == std::array{1, 2, 9, 4, 9, 9, 5, 6, 9}));
+    }
+
+    { // large range works
+      std::vector<int> a(150, 3);
+      std::vector<int> out(a.size());
+      a[45] = 5;
+      std::replace_copy_if(
+          policy,
+          Iter(std::data(a)),
+          Iter(std::data(a) + std::size(a)),
+          Iter(out.data()),
+          [](int i) { return i == 3; },
+          6);
+
+      std::vector<int> comp(150, 6);
+      comp[45] = 5;
+      assert(std::equal(out.begin(), out.end(), comp.begin()));
+    }
+  }
+};
+
+struct ThrowOnCompare {};
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
+#endif
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+  std::set_terminate(terminate_successful);
+  ThrowOnCompare a[2];
+  try {
+    (void)std::replace_copy_if(
+        std::execution::par,
+        std::begin(a),
+        std::end(a),
+        std::begin(a),
+        [](ThrowOnCompare& i) { return i == i; },
+        ThrowOnCompare{});
+  } catch (int) {
+    assert(false);
+  }
+#endif
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// template<class ExecutionPolicy, class ForwardIterator, class Predicate, class T>
+//   void replace_if(ExecutionPolicy&& exec,
+//                   ForwardIterator first, ForwardIterator last,
+//                   Predicate pred, const T& new_value);
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <vector>
+
+#include "type_algorithms.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+template <class Iter>
+struct Test {
+  template <class ExecutionPolicy>
+  void operator()(ExecutionPolicy&& policy) {
+    { // simple test
+      std::array a = {1, 2, 3, 4, 5, 6, 7, 8};
+      std::replace_if(
+          policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 3 || i == 7; }, 6);
+      assert((a == std::array{1, 2, 6, 4, 5, 6, 6, 8}));
+    }
+
+    { // empty range works
+      std::array<int, 0> a = {};
+      std::replace_if(
+          policy, Iter(std::begin(a)), Iter(std::end(a)), [](int) { return false; }, 6);
+    }
+
+    { // non-empty range without a match works
+      std::array a = {1, 2};
+      std::replace_if(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int) { return false; }, 6);
+    }
+
+    { // single element range works
+      std::array a = {3};
+      std::replace_if(
+          policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 3; }, 6);
+      assert((a == std::array{6}));
+    }
+
+    { // two element range works
+      std::array a = {3, 4};
+      std::replace_if(
+          policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 3; }, 6);
+      assert((a == std::array{6, 4}));
+    }
+
+    { // multiple matching elements work
+      std::array a = {1, 2, 3, 4, 3, 3, 5, 6, 3};
+      std::replace_if(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 3; }, 9);
+      assert((a == std::array{1, 2, 9, 4, 9, 9, 5, 6, 9}));
+    }
+
+    { // large range works
+      std::vector<int> a(150, 3);
+      a[45] = 5;
+      std::replace_if(
+          policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a)), [](int i) { return i == 3; }, 6);
+
+      std::vector<int> comp(150, 6);
+      comp[45] = 5;
+      assert(std::equal(a.begin(), a.end(), comp.begin()));
+    }
+  }
+};
+
+struct ThrowOnCompare {};
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
+#endif
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+  std::set_terminate(terminate_successful);
+  ThrowOnCompare a[2];
+  try {
+    (void)std::replace_if(
+        std::execution::par, std::begin(a), std::end(a), [](ThrowOnCompare&) { return false; }, ThrowOnCompare{});
+  } catch (int) {
+    assert(false);
+  }
+#endif
+
+  return 0;
+}