[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

22

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.

30

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

30

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

30

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/partition_copy.h
   __algorithm/partition_point.h
   __algorithm/pop_heap.h
   __algorithm/prev_permutation.h
   __algorithm/pstl_any_all_none_of.h
   __algorithm/pstl_fill.h
   __algorithm/pstl_find.h
   __algorithm/pstl_for_each.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_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/transform.h>
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__pstl/internal/parallel_backend.h>
+#include <__pstl/internal/unseq_backend_simd.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_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _UnaryOperation,
+          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _ForwardIterator2 transform(
+    _ExecutionPolicy&& __policy,
+    _ForwardIterator1 __first,
+    _ForwardIterator1 __last,
+    _ForwardIterator2 __result,
+    _UnaryOperation __op) {
+  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
+                __is_cpp17_random_access_iterator<_ForwardIterator1>::value &&
+                __is_cpp17_random_access_iterator<_ForwardIterator2>::value) {
+    std::__terminate_on_exception([&] {
+      __pstl::__par_backend::__parallel_for(
+          __pstl::__internal::__par_backend_tag{},
+          __policy,
+          __first,
+          __last,
+          [&__policy, __op, __first, __result](_ForwardIterator1 __brick_first, _ForwardIterator1 __brick_last) {
+            return std::transform(
+                std::__remove_parallel_policy(__policy),
+                __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<_ForwardIterator1>::value &&
+                       __is_cpp17_random_access_iterator<_ForwardIterator2>::value) {
+    return __pstl::__unseq_backend::__simd_walk_2(
+        __first,
+        __last - __first,
+        __result,
+        [&](__iter_reference<_ForwardIterator1> __in, __iter_reference<_ForwardIterator2> __out) {
+          __out = __op(__in);
+        });
+  } else {
+    return std::transform(__first, __last, __result, __op);
+  }
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _ForwardIterator3,
+          class _BinaryOperation,
+          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _ForwardIterator3 transform(
+    _ExecutionPolicy&& __policy,
+    _ForwardIterator1 __first1,
+    _ForwardIterator1 __last1,
+    _ForwardIterator2 __first2,
+    _ForwardIterator3 __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<_ForwardIterator3>::value) {
+    std::__terminate_on_exception([&] {
+      __pstl::__par_backend::__parallel_for(
+          __pstl::__internal::__par_backend_tag{},
+          __policy,
+          __first1,
+          __last1,
+          [&__policy, __op, __first1, __first2, __result](
+              _ForwardIterator1 __brick_first, _ForwardIterator1 __brick_last) {
+            return std::transform(
+                std::__remove_parallel_policy(__policy),
+                __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<_ForwardIterator3>::value) {
+    return __pstl::__unseq_backend::__simd_walk_3(
+        __first1,
+        __last1 - __first1,
+        __first2,
+        __result,
+        [&](__iter_reference<_ForwardIterator1> __in1,
+            __iter_reference<_ForwardIterator2> __in2,
+            __iter_reference<_ForwardIterator3> __out) { __out = __op(__in1, __in2); });
+  } else {
+    return std::transform(__first1, __last1, __first2, __result, __op);
+  }
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_TRANSFORM_H

libcxx/include/__iterator/iterator_traits.h

 using __iterator_pointer_type = typename iterator_traits<_Iter>::pointer;
 
 template <class _Iter>
 using __iter_diff_t = typename iterator_traits<_Iter>::difference_type;
 
 template<class _InputIterator>
 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;
 
+template <class _Iter>
+using __iter_reference = typename iterator_traits<_Iter>::reference;
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_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/unwrap_iter.h>
 #include <__algorithm/upper_bound.h>
 
 #ifdef _LIBCPP_HAS_PARALLEL_ALGORITHMS
 #  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>
 #endif
 
 // standard-mandated includes
 
 // [algorithm.syn]
 #include <initializer_list>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

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
+
+// REQUIRES: with-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"
+
+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));
+      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; });
+      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 type>{});
+  }
+};
+
+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
+
+// REQUIRES: with-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"
+
+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));
+      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;
+          });
+      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 type>{});
+  }
+};
+
+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 type = 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