[libc++][PSTL] Implement std::transform

[philnik]

Try to fix CI

[ldionne]

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

23

We should also include a SFINAE test that checks that we SFINAE-out whenever the first argument is not an execution policy. We could do that in a single big test file for all the algorithms, like we did for some ranges algorithms.

31

I think we're missing tests for constraints here and in the other test.

libcxx/test/support/type_algorithms.h

56–60

I would suggest this instead:

template <template <class...> class F, class ...T>
struct partial_instantiation {
  template <class ...Args>
  using apply = F<T..., Args...>;
};

This suggests that we're doing partial application of the template F. apply is often used in these cases so it's kind of idiomatic (e.g. the old MPL and derivatives of it).

[philnik]

Address comments

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

31

What kind of constraints do you mean?

libcxx/test/support/type_algorithms.h

56–60

template <class...> doesn't work when template <class> is expected. I first had it the way you have it right now.

[ldionne]

libcxx/include/__algorithm/pstl_transform.h

36–38

Per your suggestion, we could name those _ForwardIterator and _ForwardOutIterator. And for the binary version, _ForwardIterator1, _ForwardIterator2, and _ForwardOutIterator.

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

31

I meant the execution policy constraint that you added a test for, thanks! I don't know why I left two comments that were so similar, maybe I wanted to point out that it was missing from both the tests.

50

We need to test the result type of this algorithm (and all the other PSTL algorithms we have so far, where I think we've neglected that).

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

29

Here, let's add a comment explaining "we can't test the constraint on the execution policy, because that would conflict with the binary transform algorithm that doesn't take an execution policy, which is not constrained at all".

[philnik]

Address comments

[ldionne]

libcxx/test/support/type_algorithms.h

56–60

Ahhhh yeah I remember that issue. I still think apply would be a naming improvement though.

[philnik]

Address comments

[philnik]

Rebased

[philnik]

Try to fix CI

[philnik]

• Rebased
• Try to fix CI

[philnik]

Try to fix CI

[philnik]

Rebased on top of new dispatching scheme

[philnik]

Rebased

[philnik]

Fix formatting

[philnik]

Generate files

[philnik]

Rebased

[philnik]

Rebased

[ldionne]

LGTM w/ comments and CI. Thanks!!!

libcxx/include/__algorithm/pstl_transform.h

51

We need to reject the case where a non-forward iterator is provided as the output (and also for the input I guess). Otherwise, folks could try to pass something like back_inserter which is not only invalid but also potentially dangerous (race conditions).

We don't have to do this in this patch, but let's add appropriate static asserts pretty aggressively in the frontend "layer" of all the parallel algorithms in another patch. And from then on let's do it for all the algos.

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

78

I think we can do the lambda trick here. And in all the other patches you have open too, I guess.

[philnik]

Address comments

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Fix diff

libcxx/include/CMakeLists.txt

set(files
   __algorithm/pstl_backend.h
   __algorithm/pstl_backends/cpu_backend.h
   __algorithm/pstl_backends/cpu_backends/any_of.h
   __algorithm/pstl_backends/cpu_backends/backend.h
   __algorithm/pstl_backends/cpu_backends/find_if.h
   __algorithm/pstl_backends/cpu_backends/fill.h
   __algorithm/pstl_backends/cpu_backends/for_each.h
   __algorithm/pstl_backends/cpu_backends/serial.h
+  __algorithm/pstl_backends/cpu_backends/transform.h
   __algorithm/pstl_fill.h
   __algorithm/pstl_find.h
   __algorithm/pstl_for_each.h
   __algorithm/pstl_frontend_dispatch.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
   __algorithm/ranges_copy.h
   __algorithm/ranges_copy_backward.h

libcxx/include/__algorithm/pstl_backend.h

 A PSTL parallel backend is a tag type to which the following functions are associated, at minimum:
 
   template <class _ExecutionPolicy, class _Iterator, class _Func>
   void __pstl_for_each(_Backend, _ExecutionPolicy&&, _Iterator __first, _Iterator __last, _Func __f);
 
   template <class _ExecutionPolicy, class _Iterator, class _Predicate>
   _Iterator __pstl_find_if(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred);
 
+  template <class _ExecutionPolicy, class _InIterator, class _OutIterator, class _UnaryOperation>
+  _OutIterator __pstl_transform(_InIterator __first, _InIterator __last, _OutIterator __result, _UnaryOperation __op);
+
+  template <class _ExecutionPolicy, class _InIterator1, class _InIterator2, class _OutIterator, class _BinaryOperation>
+  _OutIterator __pstl_transform(_InIterator1 __first1,
+                                _InIterator1 __last1,
+                                _InIterator2 __first2,
+                                _OutIterator __result,
+                                _BinaryOperation __op);
+
 // TODO: Complete this list
 
 The following functions are optional but can be provided. If provided, they are used by the corresponding
 algorithms, otherwise they are implemented in terms of other algorithms. If none of the optional algorithms are
 implemented, all the algorithms will eventually forward to the basis algorithms listed above:
 
   template <class _ExecutionPolicy, class _Iterator, class _Size, class _Func>
   void __pstl_for_each_n(_Backend, _ExecutionPolicy&&, _Iterator __first, _Size __n, _Func __f);

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

/*
 
   TODO: Document the parallel backend
 */
 
 #include <__algorithm/pstl_backends/cpu_backends/any_of.h>
 #include <__algorithm/pstl_backends/cpu_backends/fill.h>
 #include <__algorithm/pstl_backends/cpu_backends/find_if.h>
 #include <__algorithm/pstl_backends/cpu_backends/for_each.h>
+#include <__algorithm/pstl_backends/cpu_backends/transform.h>
+
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/transform.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_BACKENDS_CPU_BACKENDS_TRANSFORM_H
+#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_TRANSFORM_H
+
+#include <__algorithm/pstl_backends/cpu_backends/backend.h>
+#include <__algorithm/transform.h>
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__type_traits/enable_if.h>
+#include <__type_traits/is_execution_policy.h>
+#include <__type_traits/remove_cvref.h>
+#include <__utility/terminate_on_exception.h>
+
+#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 _Iterator1, class _DifferenceType, class _Iterator2, class _Function>
+_LIBCPP_HIDE_FROM_ABI _Iterator2
+__simd_walk_2(_Iterator1 __first1, _DifferenceType __n, _Iterator2 __first2, _Function __f) noexcept {
+  _PSTL_PRAGMA_SIMD
+  for (_DifferenceType __i = 0; __i < __n; ++__i)
+    __f(__first1[__i], __first2[__i]);
+  return __first2 + __n;
+}
+
+template <class _ExecutionPolicy, class _ForwardIterator, class _ForwardOutIterator, class _UnaryOperation>
+_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator __pstl_transform(
+    __cpu_backend_tag,
+    _ForwardIterator __first,
+    _ForwardIterator __last,
+    _ForwardOutIterator __result,
+    _UnaryOperation __op) {
+  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
+                __is_cpp17_random_access_iterator<_ForwardIterator>::value &&
+                __is_cpp17_random_access_iterator<_ForwardOutIterator>::value) {
+    std::__terminate_on_exception([&] {
+      std::__par_backend::__parallel_for(
+          __first, __last, [__op, __first, __result](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
+            return std::__pstl_transform<__remove_parallel_policy_t<_ExecutionPolicy>>(
+                __cpu_backend_tag{}, __brick_first, __brick_last, __result + (__brick_first - __first), __op);
+          });
+    });
+    return __result + (__last - __first);
+  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
+                       __is_cpp17_random_access_iterator<_ForwardIterator>::value &&
+                       __is_cpp17_random_access_iterator<_ForwardOutIterator>::value) {
+    return std::__simd_walk_2(
+        __first,
+        __last - __first,
+        __result,
+        [&](__iter_reference<_ForwardIterator> __in_value, __iter_reference<_ForwardOutIterator> __out_value) {
+          __out_value = __op(__in_value);
+        });
+  } else {
+    return std::transform(__first, __last, __result, __op);
+  }
+}
+
+template <class _Iterator1, class _DifferenceType, class _Iterator2, class _Iterator3, class _Function>
+_LIBCPP_HIDE_FROM_ABI _Iterator3 __simd_walk_3(
+    _Iterator1 __first1, _DifferenceType __n, _Iterator2 __first2, _Iterator3 __first3, _Function __f) noexcept {
+  _PSTL_PRAGMA_SIMD
+  for (_DifferenceType __i = 0; __i < __n; ++__i)
+    __f(__first1[__i], __first2[__i], __first3[__i]);
+  return __first3 + __n;
+}
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _ForwardOutIterator,
+          class _BinaryOperation,
+          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator __pstl_transform(
+    __cpu_backend_tag,
+    _ForwardIterator1 __first1,
+    _ForwardIterator1 __last1,
+    _ForwardIterator2 __first2,
+    _ForwardOutIterator __result,
+    _BinaryOperation __op) {
+  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
+                __is_cpp17_random_access_iterator<_ForwardIterator1>::value &&
+                __is_cpp17_random_access_iterator<_ForwardIterator2>::value &&
+                __is_cpp17_random_access_iterator<_ForwardOutIterator>::value) {
+    std::__terminate_on_exception([&] {
+      std::__par_backend::__parallel_for(
+          __first1,
+          __last1,
+          [__op, __first1, __first2, __result](_ForwardIterator1 __brick_first, _ForwardIterator1 __brick_last) {
+            return std::__pstl_transform<__remove_parallel_policy_t<_ExecutionPolicy>>(
+                __cpu_backend_tag{},
+                __brick_first,
+                __brick_last,
+                __first2 + (__brick_first - __first1),
+                __result + (__brick_first - __first1),
+                __op);
+          });
+    });
+    return __result + (__last1 - __first1);
+  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
+                       __is_cpp17_random_access_iterator<_ForwardIterator1>::value &&
+                       __is_cpp17_random_access_iterator<_ForwardIterator2>::value &&
+                       __is_cpp17_random_access_iterator<_ForwardOutIterator>::value) {
+    return std::__simd_walk_3(
+        __first1,
+        __last1 - __first1,
+        __first2,
+        __result,
+        [&](__iter_reference<_ForwardIterator1> __in1,
+            __iter_reference<_ForwardIterator2> __in2,
+            __iter_reference<_ForwardOutIterator> __out_value) { __out_value = __op(__in1, __in2); });
+  } else {
+    return std::transform(__first1, __last1, __first2, __result, __op);
+  }
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_TRANSFORM_H

libcxx/include/__algorithm/pstl_transform.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_TRANSFORM_H
+#define _LIBCPP___ALGORITHM_PSTL_TRANSFORM_H
+
+#include <__algorithm/pstl_backend.h>
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__type_traits/is_execution_policy.h>
+#include <__utility/terminate_on_exception.h>
+
+#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 _ExecutionPolicy,
+          class _ForwardIterator,
+          class _ForwardOutIterator,
+          class _UnaryOperation,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator transform(
+    _ExecutionPolicy&& __policy,
+    _ForwardIterator __first,
+    _ForwardIterator __last,
+    _ForwardOutIterator __result,
+    _UnaryOperation __op) {
+  using _Backend = typename __select_backend<_RawPolicy>::type;
+  return std::__pstl_transform<_RawPolicy>(
+      _Backend{}, std::move(__first), std::move(__last), std::move(__result), std::move(__op));
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _ForwardOutIterator,
+          class _BinaryOperation,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator transform(
+    _ExecutionPolicy&& __policy,
+    _ForwardIterator1 __first1,
+    _ForwardIterator1 __last1,
+    _ForwardIterator2 __first2,
+    _ForwardOutIterator __result,
+    _BinaryOperation __op) {
+  using _Backend = typename __select_backend<_RawPolicy>::type;
+  return std::__pstl_transform<_RawPolicy>(
+      _Backend{}, std::move(__first1), std::move(__last1), std::move(__first2), std::move(__result), std::move(__op));
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_TRANSFORM_H

libcxx/include/__pstl/internal/glue_algorithm_defs.h

copy_if(_ExecutionPolicy&& __exec,
         _Predicate __pred);
 
 // [alg.swap]
 
 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> swap_ranges(
     _ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2);
 
-// [alg.transform]
-
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _UnaryOperation>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
-transform(_ExecutionPolicy&& __exec,
-          _ForwardIterator1 __first,
-          _ForwardIterator1 __last,
-          _ForwardIterator2 __result,
-          _UnaryOperation __op);
-
-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);
-
 // [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,

libcxx/include/__pstl/internal/glue_algorithm_impl.h

return __pstl::__internal::__pattern_walk2(
       [](_ReferenceType1 __x, _ReferenceType2 __y) {
         using std::swap;
         swap(__x, __y);
       });
 }
 
 // [alg.transform]
 
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _UnaryOperation>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
-transform(_ExecutionPolicy&& __exec,
-          _ForwardIterator1 __first,
-          _ForwardIterator1 __last,
-          _ForwardIterator2 __result,
-          _UnaryOperation __op) {
-  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,
-      [__op](_InputType __x, _OutputType __y) mutable { __y = __op(__x); });
-}
-
 template <class _ExecutionPolicy,
           class _ForwardIterator1,
           class _ForwardIterator2,
           class _ForwardIterator,
           class _BinaryOperation>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
 transform(_ExecutionPolicy&& __exec,
           _ForwardIterator1 __first1,

libcxx/include/algorithm

 #include <__algorithm/partition_copy.h>
 #include <__algorithm/partition_point.h>
 #include <__algorithm/pop_heap.h>
 #include <__algorithm/prev_permutation.h>
 #include <__algorithm/pstl_any_all_none_of.h>
 #include <__algorithm/pstl_fill.h>
 #include <__algorithm/pstl_find.h>
 #include <__algorithm/pstl_for_each.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>
 #include <__algorithm/ranges_copy.h>
 #include <__algorithm/ranges_copy_backward.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module pstl {
         private header "__algorithm/pstl_backends/cpu_backend.h"
         private header "__algorithm/pstl_backends/cpu_backends/any_of.h"
         private header "__algorithm/pstl_backends/cpu_backends/backend.h"
         private header "__algorithm/pstl_backends/cpu_backends/fill.h"
         private header "__algorithm/pstl_backends/cpu_backends/find_if.h"
         private header "__algorithm/pstl_backends/cpu_backends/for_each.h"
         private header "__algorithm/pstl_backends/cpu_backends/serial.h"
+        private header "__algorithm/pstl_backends/cpu_backends/transform.h"
       }
       module push_heap                       { private header "__algorithm/push_heap.h" }
       module ranges_adjacent_find            { private header "__algorithm/ranges_adjacent_find.h" }
       module ranges_all_of                   { private header "__algorithm/ranges_all_of.h" }
       module ranges_any_of                   { private header "__algorithm/ranges_any_of.h" }
       module ranges_binary_search {
         private header "__algorithm/ranges_binary_search.h"
         export functional.__functional.ranges_operations

libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/pstl.transform.binary.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
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+//          class ForwardIterator, class BinaryOperation>
+//   ForwardIterator
+//     transform(ExecutionPolicy&& exec,
+//               ForwardIterator1 first1, ForwardIterator1 last1,
+//               ForwardIterator2 first2, ForwardIterator result,
+//               BinaryOperation binary_op);
+
+#include <algorithm>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+EXECUTION_POLICY_SFINAE_TEST(transform);
+
+static_assert(sfinae_test_transform<int, int*, int*, int*, int*, bool (*)(int)>);
+static_assert(!sfinae_test_transform<std::execution::parallel_policy, int*, int*, int*, int*, int (*)(int, int)>);
+
+template <class Iter1, class Iter2, class Iter3>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    // simple test
+    for (const int size : {0, 1, 2, 100, 350}) {
+      std::vector<int> a(size);
+      std::vector<int> b(size);
+      for (int i = 0; i != size; ++i) {
+        a[i] = i + 1;
+        b[i] = i - 3;
+      }
+
+      std::vector<int> out(std::size(a));
+      decltype(auto) ret = std::transform(
+          policy,
+          Iter1(std::data(a)),
+          Iter1(std::data(a) + std::size(a)),
+          Iter2(std::data(b)),
+          Iter3(std::data(out)),
+          [](int i, int j) { return i + j + 3; });
+      static_assert(std::is_same_v<decltype(ret), Iter3>);
+      assert(base(ret) == std::data(out) + std::size(out));
+      for (int i = 0; i != size; ++i) {
+        assert(out[i] == i * 2 + 1);
+      }
+    }
+  }
+};
+
+template <class Iter3>
+struct TestIterators2 {
+  template <class Iter2>
+  void operator()() {
+    types::for_each(types::forward_iterator_list<int*>{},
+                    TestIteratorWithPolicies<types::partial_instantiation<Test, Iter2, Iter3>::template apply>{});
+  }
+};
+
+struct TestIterators1 {
+  template <class Iter3>
+  void operator()() {
+    types::for_each(types::forward_iterator_list<int*>{}, TestIterators2<Iter3>{});
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIterators1{});
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/pstl.transform.unary.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
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+//          class UnaryOperation>
+//   ForwardIterator2
+//     transform(ExecutionPolicy&& exec,
+//               ForwardIterator1 first1, ForwardIterator1 last1,
+//               ForwardIterator2 result, UnaryOperation op);
+
+#include <algorithm>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+// We can't test the constraint on the execution policy, because that would conflict with the binary
+// transform algorithm that doesn't take an execution policy, which is not constrained at all.
+
+template <class Iter1, class Iter2>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    // simple test
+    for (const int size : {0, 1, 2, 100, 350}) {
+      std::vector<int> a(size);
+      for (int i = 0; i != size; ++i)
+        a[i] = i + 1;
+
+      std::vector<int> out(std::size(a));
+      decltype(auto) ret = std::transform(
+          policy, Iter1(std::data(a)), Iter1(std::data(a) + std::size(a)), Iter2(std::data(out)), [](int i) {
+            return i + 3;
+          });
+      static_assert(std::is_same_v<decltype(ret), Iter2>);
+      assert(base(ret) == std::data(out) + std::size(out));
+      for (int i = 0; i != size; ++i)
+        assert(out[i] == i + 4);
+    }
+  }
+};
+
+struct TestIterators {
+  template <class Iter2>
+  void operator()() {
+    types::for_each(types::forward_iterator_list<int*>{},
+                    TestIteratorWithPolicies<types::partial_instantiation<Test, Iter2>::template apply>{});
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIterators{});
+
+  return 0;
+}

libcxx/test/support/type_algorithms.h

 template <class... Types>
 TEST_CONSTEXPR_CXX14 void swallow(Types...) {}
 
 template <class... Types, class Functor>
 TEST_CONSTEXPR_CXX14 void for_each(type_list<Types...>, Functor f) {
   swallow((f.template operator()<Types>(), 0)...);
 }
 
+
+template <template <class...> class T, class... Args>
+struct partial_instantiation {
+  template <class Other>
+  using apply = T<Args..., Other>;
+};
+
 // type categories defined in [basic.fundamental] plus extensions (without CV-qualifiers)
 
 using character_types =
     type_list<char
 #ifndef TEST_HAS_NO_WIDE_CHARACTERS
               ,
               wchar_t
 #endif