[libc++][PSTL] Parallelize random_access_iterator

[gonzalobg]

Summary

P2408 requires this for C++23, but implementing it in C++20 is safe
because the only code impacted would be code that violated a
precondition of the parallel algorithm. It was P2408 intent to
enable implementations to backport this to C++20.

Closes #63447 .

[philnik]

Could you upload the patch with context (i.e. use arc or add -U9999 when generating the patch)?

It feels a bit wrong to me that we check for random_access_iterator in a classic algorithm, but I guess that is fine. Do all Cpp17RandomAccessIterators meet the random_access_iterator requirements? If yes, I'd just go with using either __has_random_access_iterator or random_access_iterator. We'd probably want to diagnose iterators which advertise themselves as such while not actually being random_access_iterators if we go that route.

libcxx/include/__algorithm/pstl_traits.h

26 ↗

(On Diff #536608)

This isn't actually pstl-specific, so IMO this should live in iterator_traits or something like that.

[gonzalobg]

• Generated with -U9999
• Moved utility to __iterator/concepts.h (requires random_access_iterator concept)
• Removed pstl_traits.h file

[philnik]

Thanks for the patch! LGTM.

[philnik]

Please make sure the CI is run and green before landing.

[ldionne]

libcxx/include/__algorithm/pstl_any_all_none_of.h

16

Why is this include changed, since we didn't touch the contents of the file? Was the include unnecessary in the first place?

libcxx/include/__algorithm/pstl_find.h

18

Same comment.

libcxx/include/__algorithm/pstl_transform.h

15

Same comment.

libcxx/include/__iterator/concepts.h

290

(not attached to the diff) Can you folks think of a way to test this? I can't, but asking just in case.

[philnik]

libcxx/include/__iterator/concepts.h

290

We already test with C++20 iterators, which should be good enough I think. Performance can only be tested through benchmarks anyways, so I think that's out of scope for this, since we don't have any PSTL benchmarks yet. (Reminds me that we should log the result of our benchmarks...)

[gonzalobg]

libcxx/include/__iterator/concepts.h

290

(not attached to the diff) Can you folks think of a way to test this? I can't, but asking just in case.

I don't know how to test this (I thought quite a bit about it, but benchmarks are the only way I have to test this right now).

If someone figures out a way to test this without requiring benchmarks, that would be helpful for libstdc++ as well (I've sent a similar patch there).

[gonzalobg]

Remove unnecessary iterator/iterator_traits.h and iterator/concepts.h includes.

[gonzalobg]

Forgot to remove header from one file.

[ldionne]

Can you rebase this onto main? The diff fails to apply in the CI.

[gonzalobg]

Rebased on top of main.

[gonzalobg]

Fix fmt.

[gonzalobg]

Re-add iterator_traits to some files (required for modules).

[gonzalobg]

Re-add missing module files.

[gonzalobg]

@ldionne @philnik I've fixed all failures except for the current three. Can it be that they are caused by something that's not in my PR ?

[Mordante]

In D154305#4532745, @gonzalobg wrote:

@ldionne @philnik I've fixed all failures except for the current three. Can it be that they are caused by something that's not in my PR ?

It looks like the last build is green. Can you rebase before landing to make sure the CI is really green?

[gonzalobg]

Rebased on main.

[gonzalobg]

Name: Gonzalo Brito Gadeschi
Email: [e-mail]

[gonzalobg]

Rebased one last time.

[gonzalobg]

Fix tests after rebase.

libcxx/include/__algorithm/pstl_any_all_none_of.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_ANY_ALL_NONE_OF_H
 #define _LIBCPP___ALGORITHM_PSTL_ANY_ALL_NONE_OF_H
 
 #include <__algorithm/pstl_find.h>
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__iterator/cpp17_iterator_concepts.h>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.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

libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h

 
 #include <__algorithm/any_of.h>
 #include <__algorithm/find_if.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__atomic/atomic.h>
 #include <__atomic/memory_order.h>
 #include <__config>
 #include <__functional/operations.h>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/pair.h>
 #include <__utility/terminate_on_exception.h>
 #include <cstdint>
 
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _LIBCPP_BEGIN_NAMESPACE_STD
_LIBCPP_HIDE_FROM_ABI bool __simd_or(_Index __first, _DifferenceType __n, _Pred __pred) noexcept {
   }
   return false;
 }
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
 _LIBCPP_HIDE_FROM_ABI bool
 __pstl_any_of(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__terminate_on_exception([&] {
       return std::__parallel_or(
           __first, __last, [&__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
             return std::__pstl_any_of<__remove_parallel_policy_t<_ExecutionPolicy>>(
                 __cpu_backend_tag{}, __brick_first, __brick_last, __pred);
           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__simd_or(__first, __last - __first, __pred);
   } else {
     return std::any_of(__first, __last, __pred);
   }
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_ANY_OF_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/fill.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_FILL_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_FILL_H
 
 #include <__algorithm/fill.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.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 _Index, class _DifferenceType, class _Tp>
 _LIBCPP_HIDE_FROM_ABI _Index __simd_fill_n(_Index __first, _DifferenceType __n, const _Tp& __value) noexcept {
   _PSTL_USE_NONTEMPORAL_STORES_IF_ALLOWED
   _PSTL_PRAGMA_SIMD
   for (_DifferenceType __i = 0; __i < __n; ++__i)
     __first[__i] = __value;
   return __first + __n;
 }
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
 _LIBCPP_HIDE_FROM_ABI void
 __pstl_fill(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__terminate_on_exception([&] {
       __par_backend::__parallel_for(
           __first, __last, [&__value](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
             std::__pstl_fill<__remove_parallel_policy_t<_ExecutionPolicy>>(
                 __cpu_backend_tag{}, __brick_first, __brick_last, __value);
           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__simd_fill_n(__first, __last - __first, __value);
   } else {
     std::fill(__first, __last, __value);
   }
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_FILL_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/find_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_PSTL_BACKENDS_CPU_BACKENDS_FIND_IF_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_FIND_IF_H
 
 #include <__algorithm/find_if.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__atomic/atomic.h>
 #include <__config>
 #include <__functional/operations.h>
+#include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/pair.h>
 #include <__utility/terminate_on_exception.h>
 #include <cstddef>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
__simd_first(_Index __first, _DifferenceType __begin, _DifferenceType __end, _Compare __comp) noexcept {
   }
   return __first + __end;
 }
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
 _LIBCPP_HIDE_FROM_ABI _ForwardIterator
 __pstl_find_if(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__terminate_on_exception([&] {
       return std::__parallel_find(
           __first,
           __last,
           [&__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
             return std::__pstl_find_if<__remove_parallel_policy_t<_ExecutionPolicy>>(
                 __cpu_backend_tag{}, __brick_first, __brick_last, __pred);
           },
           less<>{},
           true);
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     using __diff_t = __iter_diff_t<_ForwardIterator>;
     return std::__simd_first(__first, __diff_t(0), __last - __first, [&__pred](_ForwardIterator __iter, __diff_t __i) {
       return __pred(__iter[__i]);
     });
   } else {
     return std::find_if(__first, __last, __pred);
   }
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_FIND_IF_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/for_each.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_BACKNEDS_FOR_EACH_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKNEDS_FOR_EACH_H
 
 #include <__algorithm/for_each.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.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 _Iterator, class _DifferenceType, class _Function>
 _LIBCPP_HIDE_FROM_ABI _Iterator __simd_walk_1(_Iterator __first, _DifferenceType __n, _Function __f) noexcept {
   _PSTL_PRAGMA_SIMD
   for (_DifferenceType __i = 0; __i < __n; ++__i)
     __f(__first[__i]);
 
   return __first + __n;
 }
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Functor>
 _LIBCPP_HIDE_FROM_ABI void
 __pstl_for_each(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Functor __func) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__terminate_on_exception([&] {
       std::__par_backend::__parallel_for(
           __first, __last, [__func](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
             std::__pstl_for_each<__remove_parallel_policy_t<_ExecutionPolicy>>(
                 __cpu_backend_tag{}, __brick_first, __brick_last, __func);
           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__simd_walk_1(__first, __last - __first, __func);
   } else {
     std::for_each(__first, __last, __func);
   }
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKNEDS_FOR_EACH_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/merge.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_MERGE_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_MERGE_H
 
 #include <__algorithm/merge.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/move.h>
 #include <__utility/terminate_on_exception.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator __pstl_merge(
     __cpu_backend_tag,
     _ForwardIterator1 __first1,
     _ForwardIterator1 __last1,
     _ForwardIterator2 __first2,
     _ForwardIterator2 __last2,
     _ForwardOutIterator __result,
     _Comp __comp) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                __has_random_access_iterator_category<_ForwardIterator2>::value &&
-                __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
     return std::__terminate_on_exception([&] {
       __par_backend::__parallel_merge(
           __first1,
           __last1,
           __first2,
           __last2,
           __result,
           __comp,

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/concepts.h>
 #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

 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> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value &&
-                __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value &&
+                __has_random_access_iterator_category_or_concept<_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> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value &&
-                       __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value &&
+                       __has_random_access_iterator_category_or_concept<_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 {

 _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> &&
-                __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                __has_random_access_iterator_category<_ForwardIterator2>::value &&
-                __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value &&
+                __has_random_access_iterator_category_or_concept<_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> &&
-                       __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                       __has_random_access_iterator_category<_ForwardIterator2>::value &&
-                       __has_random_access_iterator_category<_ForwardOutIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value &&
+                       __has_random_access_iterator_category_or_concept<_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); });

libcxx/include/__algorithm/pstl_backends/cpu_backends/transform_reduce.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_REDUCE_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_TRANSFORM_REDUCE_H
 
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
+#include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__numeric/transform_reduce.h>
 #include <__type_traits/is_arithmetic.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/operation_traits.h>
 #include <__utility/move.h>
 #include <__utility/terminate_on_exception.h>
 #include <new>
_LIBCPP_HIDE_FROM_ABI _Tp __pstl_transform_reduce(
     __cpu_backend_tag,
     _ForwardIterator1 __first1,
     _ForwardIterator1 __last1,
     _ForwardIterator2 __first2,
     _Tp __init,
     _BinaryOperation1 __reduce,
     _BinaryOperation2 __transform) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                __has_random_access_iterator_category<_ForwardIterator2>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
     return std::__terminate_on_exception([&] {
       return __par_backend::__parallel_transform_reduce(
           __first1,
           std::move(__last1),
           [__first1, __first2, __transform](_ForwardIterator1 __iter) {
             return __transform(*__iter, *(__first2 + (__iter - __first1)));
           },
           std::move(__init),
           std::move(__reduce),
           [__first1, __first2, __reduce, __transform](
               _ForwardIterator1 __brick_first, _ForwardIterator1 __brick_last, _Tp __brick_init) {
             return std::__pstl_transform_reduce<__remove_parallel_policy_t<_ExecutionPolicy>>(
                 __cpu_backend_tag{},
                 __brick_first,
                 std::move(__brick_last),
                 __first2 + (__brick_first - __first1),
                 std::move(__brick_init),
                 std::move(__reduce),
                 std::move(__transform));
           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator1>::value &&
-                       __has_random_access_iterator_category<_ForwardIterator2>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
     return std::__simd_transform_reduce(
         __last1 - __first1, std::move(__init), std::move(__reduce), [&](__iter_diff_t<_ForwardIterator1> __i) {
           return __transform(__first1[__i], __first2[__i]);
         });
   } else {
     return std::transform_reduce(
         std::move(__first1),
         std::move(__last1),
         std::move(__first2),
         std::move(__init),
         std::move(__reduce),
         std::move(__transform));
   }
 }
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
 _LIBCPP_HIDE_FROM_ABI _Tp __pstl_transform_reduce(
     __cpu_backend_tag,
     _ForwardIterator __first,
     _ForwardIterator __last,
     _Tp __init,
     _BinaryOperation __reduce,
     _UnaryOperation __transform) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __has_random_access_iterator_category<_ForwardIterator>::value) {
+                __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__terminate_on_exception([&] {
       return __par_backend::__parallel_transform_reduce(
           std::move(__first),
           std::move(__last),
           [__transform](_ForwardIterator __iter) { return __transform(*__iter); },
           std::move(__init),
           std::move(__reduce),
           [=](_ForwardIterator __brick_first, _ForwardIterator __brick_last, _Tp __brick_init) {
             return std::__pstl_transform_reduce<__remove_parallel_policy_t<_ExecutionPolicy>>(
                 __cpu_backend_tag{},
                 std::move(__brick_first),
                 std::move(__brick_last),
                 std::move(__brick_init),
                 std::move(__reduce),
                 std::move(__transform));
           });
     });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+                       __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__simd_transform_reduce(
         __last - __first,
         std::move(__init),
         std::move(__reduce),
         [=, &__transform](__iter_diff_t<_ForwardIterator> __i) { return __transform(__first[__i]); });
   } else {
     return std::transform_reduce(
         std::move(__first), std::move(__last), std::move(__init), std::move(__reduce), std::move(__transform));
   }
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_TRANSFORM_REDUCE_H

libcxx/include/__algorithm/pstl_copy.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_COPY_H
 #define _LIBCPP___ALGORITHM_PSTL_COPY_H
 
 #include <__algorithm/copy_n.h>
 #include <__algorithm/pstl_transform.h>
 #include <__config>
 #include <__functional/identity.h>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
 #include <__type_traits/is_constant_evaluated.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/is_trivially_copyable.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 

 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _ForwardOutIterator,
           class _Size,
           enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI _ForwardOutIterator
 copy_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __result) {
-  if constexpr (__has_random_access_iterator_category<_ForwardIterator>::value)
+  if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value)
     return std::copy(__policy, __first, __first + __n, __result);
   else
     return std::copy_n(__first, __n, __result);
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_COPY_H

libcxx/include/__algorithm/pstl_fill.h

template <class _ExecutionPolicy,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI void
 fill_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _SizeT __n, const _Tp& __value) {
   _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
   std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_fill_n),
       [&](_ForwardIterator __g_first, _SizeT __g_n, const _Tp& __g_value) {
-        if constexpr (__has_random_access_iterator_category<_ForwardIterator>::value)
+        if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value)
           std::fill(__policy, __g_first, __g_first + __g_n, __g_value);
         else
           std::fill_n(__g_first, __g_n, __g_value);
       },
       std::move(__first),
       __n,
       __value);
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_FILL_H

libcxx/include/__algorithm/pstl_find.h

 #define _LIBCPP___ALGORITHM_PSTL_FIND_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/find.h>
 #include <__algorithm/pstl_backend.h>
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__iterator/cpp17_iterator_concepts.h>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.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
 

libcxx/include/__algorithm/pstl_for_each.h

 #define _LIBCPP___ALGORITHM_PSTL_FOR_EACH_H
 
 #include <__algorithm/for_each.h>
 #include <__algorithm/for_each_n.h>
 #include <__algorithm/pstl_backend.h>
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__iterator/cpp17_iterator_concepts.h>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__type_traits/void_t.h>
 #include <__utility/terminate_on_exception.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
template <class _ExecutionPolicy,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI void
 for_each_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) {
   _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_for_each_n),
       [&](_ForwardIterator __g_first, _Size __g_size, _Function __g_func) {
-        if constexpr (__has_random_access_iterator_category<_ForwardIterator>::value) {
+        if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
           std::for_each(__policy, std::move(__g_first), __g_first + __g_size, std::move(__g_func));
         } else {
           std::for_each_n(std::move(__g_first), __g_size, std::move(__g_func));
         }
       },
       __first,
       __size,
       std::move(__func));
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_FOR_EACH_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/cpp17_iterator_concepts.h>
-#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.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

libcxx/include/__iterator/concepts.h

 template<class _In, class _Out>
 concept indirectly_copyable_storable =
   indirectly_copyable<_In, _Out> &&
   indirectly_writable<_Out, iter_value_t<_In>&> &&
   indirectly_writable<_Out, const iter_value_t<_In>&> &&
   indirectly_writable<_Out, iter_value_t<_In>&&> &&
   indirectly_writable<_Out, const iter_value_t<_In>&&> &&
   copyable<iter_value_t<_In>> &&
   constructible_from<iter_value_t<_In>, iter_reference_t<_In>> &&
   assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>;
 
 // Note: indirectly_swappable is located in iter_swap.h to prevent a dependency cycle
 // (both iter_swap and indirectly_swappable require indirectly_readable).
 
 #endif // _LIBCPP_STD_VER >= 20
 
+template <class _Tp>
+using __has_random_access_iterator_category_or_concept
+#if _LIBCPP_STD_VER >= 20
+  = integral_constant<bool, random_access_iterator<_Tp>>;
+#else   // _LIBCPP_STD_VER < 20
+  = __has_random_access_iterator_category<_Tp>;
+#endif  // _LIBCPP_STD_VER
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_CONCEPTS_H