libstdc++: Make PSTL algorithms accept C++20 iterators [PR110512]

This is a step towards implementing the C++23 change P2408R5, "Ranges
iterators as inputs to non-Ranges algorithms". C++20 random access
iterators which do not meet the Cpp17RandomAccessIterator requirements
will now be recognized by the PSTL algorithms.

As noted by Patrick, P2408R5 only relaxes the requirements for
non-mutating algorithms, but this relaxes them for all parallel
algorithms. I believe that's OK. A call with a type which previously
didn't compile at all was undefined, so we're allowed to start accepting
those calls if the type satisfies std::random_access_iterator. However,
this also causes a change in behaviour for calls with arguments which
satisfy std::random_access_iterator and meet the Cpp17ForwardIterator
requirements but not the Cpp17RandomAccessIterator requirements. The
algorithms will dispatch to a different implementation now. I believe
that's also OK. The algorithms should give the same results whether
acting on forward iterators or random access iterators, just more
efficiently for the latter.

Additionally, we can optimize the C++17 implementation by using
std::__and_, and use std::__remove_cvref_t and std::__iter_category_t
for readability.  This diverges from the upstream PSTL, but since libc++
is no longer using that upstream (so we're the only consumer of this
code) I think it's reasonable to use libstdc++ extensions in localized
places like this. Rebasing this small header on upstream should not be
difficult.

libstdc++-v3/ChangeLog:

	PR libstdc++/110512
	* include/pstl/execution_impl.h (__are_random_access_iterators):
	Recognize C++20 random access iterators, and use more efficient
	implementations.
	* testsuite/25_algorithms/pstl/110512.cc: New test.

2 files changed, 47 insertions, 5 deletions

diff --git a/libstdc++-v3/include/pstl/execution_impl.h b/libstdc++-v3/include/pstl/execution_impl.h
index 64f6cc4..c840618 100644
--- a/libstdc++-v3/include/pstl/execution_impl.h
+++ b/libstdc++-v3/include/pstl/execution_impl.h
@@ -19,13 +19,24 @@ namespace __pstl
 {
 namespace __internal
 {
+#if __glibcxx_concepts
+template<typename _Iter>
+  concept __is_random_access_iter
+    = std::is_base_of_v<std::random_access_iterator_tag,
+			std::__iter_category_t<_Iter>>
+      || std::random_access_iterator<_Iter>;
 
-template <typename _IteratorTag, typename... _IteratorTypes>
-using __are_iterators_of = std::conjunction<
-    std::is_base_of<_IteratorTag, typename std::iterator_traits<std::decay_t<_IteratorTypes>>::iterator_category>...>;
-
 template <typename... _IteratorTypes>
-using __are_random_access_iterators = __are_iterators_of<std::random_access_iterator_tag, _IteratorTypes...>;
+  using __are_random_access_iterators
+    = std::bool_constant<(__is_random_access_iter<std::remove_cvref_t<_IteratorTypes>> && ...)>;
+#else
+template <typename... _IteratorTypes>
+using __are_random_access_iterators
+    = std::__and_<
+	std::is_base_of<std::random_access_iterator_tag,
+			std::__iter_category_t<std::__remove_cvref_t<_IteratorTypes>>>...
+      >;
+#endif
 
 struct __serial_backend_tag
 {
diff --git a/libstdc++-v3/testsuite/25_algorithms/pstl/110512.cc b/libstdc++-v3/testsuite/25_algorithms/pstl/110512.cc
new file mode 100644
index 0000000..188c7c9
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/pstl/110512.cc
@@ -0,0 +1,31 @@
+// { dg-do compile { target c++17 } }
+
+// Bug 110512 - C++20 random access iterators run sequentially with PSTL
+
+#include <algorithm>
+#include <execution>
+#include <ranges>
+#include <testsuite_iterators.h>
+
+using InputIter = __gnu_test::input_iterator_wrapper<int>;
+using FwdIter = __gnu_test::forward_iterator_wrapper<long>;
+using RAIter = __gnu_test::random_access_iterator_wrapper<float>;
+
+template<typename... Iter>
+constexpr bool all_random_access
+  = __pstl::__internal::__are_random_access_iterators<Iter...>::value;
+
+using __pstl::__internal::__are_random_access_iterators;
+static_assert( all_random_access<RAIter> );
+static_assert( all_random_access<int*, RAIter, const long*> );
+static_assert( ! all_random_access<RAIter, FwdIter> );
+static_assert( ! all_random_access<FwdIter, InputIter, RAIter> );
+
+#if __cpp_lib_ranges
+using IotaIter = std::ranges::iterator_t<std::ranges::iota_view<int, int>>;
+static_assert( std::random_access_iterator<IotaIter> );
+static_assert( all_random_access<IotaIter> );
+static_assert( all_random_access<IotaIter, RAIter> );
+static_assert( all_random_access<RAIter, IotaIter> );
+static_assert( ! all_random_access<RAIter, IotaIter, FwdIter> );
+#endif