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

[Jonathan Wakely]

Tested x86_64-linux and aarch64-linux, with TBB 2020.3 only.

Reviews requested.

-- >8 --

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 C==17RandomAccessIterator requirements
will now be recognized by the PSTL algorithms.

We can also optimize the C++17 implementation by using std::__or_, 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.
---
 libstdc++-v3/include/pstl/execution_impl.h    | 21 ++++++++++---
 .../testsuite/25_algorithms/pstl/110512.cc    | 31 +++++++++++++++++++
 2 files changed, 47 insertions(+), 5 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/25_algorithms/pstl/110512.cc

diff --git a/libstdc++-v3/include/pstl/execution_impl.h b/libstdc++-v3/include/pstl/execution_impl.h
index 64f6cc4357a..c84061848b9 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
 {
-
-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>...>;
+#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... _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 00000000000..188c7c915e5
--- /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
-- 
2.43.0