libstdc++: add constexpr stable_partition

This completes the implementation of P2562R1 for C++26.

Unlike the other constexpr algorithms of the same family,
stable_partition does not have a constexpr-friendly version "ready to
use" during constant evaluation. In fact, it is not even available on
freestanding, because it always allocates a temporary memory buffer.

This commit implements the simplest possible strategy: during constant
evaluation allocate a buffer of length 1 on the stack, and use that as
a working area.

libstdc++-v3/ChangeLog:

	* include/bits/algorithmfwd.h (stable_partition): Mark it
	as constexpr for C++26.
	* include/bits/ranges_algo.h (__stable_partition_fn): Likewise.
	* include/bits/stl_algo.h (stable_partition): Mark it as
	constexpr for C++26; during constant evaluation use a new
	codepath where a temporary buffer of 1 element is used.
	* testsuite/25_algorithms/headers/algorithm/synopsis.cc
	(stable_partition): Add constexpr.
	* testsuite/25_algorithms/stable_partition/constexpr.cc: New test.

5 files changed, 67 insertions, 2 deletions

diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h
index 05894b5..a727b278 100644
--- a/libstdc++-v3/include/bits/algorithmfwd.h
+++ b/libstdc++-v3/include/bits/algorithmfwd.h
@@ -649,6 +649,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
 
 #if _GLIBCXX_HOSTED
   template<typename _BIter, typename _Predicate>
+    _GLIBCXX26_CONSTEXPR
     _BIter
     stable_partition(_BIter, _BIter, _Predicate);
 #endif
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 2814d90..f36e7dd 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -2389,6 +2389,7 @@ namespace ranges
 	     typename _Proj = identity,
 	     indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
       requires permutable<_Iter>
+      _GLIBCXX26_CONSTEXPR
       subrange<_Iter>
       operator()(_Iter __first, _Sent __last,
 		 _Pred __pred, _Proj __proj = {}) const
@@ -2404,6 +2405,7 @@ namespace ranges
 	     indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
 	       _Pred>
       requires permutable<iterator_t<_Range>>
+      _GLIBCXX26_CONSTEXPR
       borrowed_subrange_t<_Range>
       operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
       {
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index bb7dbfb..71ead10 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -1447,6 +1447,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
   /// move-assign an element onto itself.
   template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
 	   typename _Distance>
+    _GLIBCXX26_CONSTEXPR
     _ForwardIterator
     __stable_partition_adaptive(_ForwardIterator __first,
 				_ForwardIterator __last,
@@ -1507,6 +1508,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
     }
 
   template<typename _ForwardIterator, typename _Predicate>
+    _GLIBCXX26_CONSTEXPR
     _ForwardIterator
     __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
 		       _Predicate __pred)
@@ -1521,11 +1523,25 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
       typedef typename iterator_traits<_ForwardIterator>::difference_type
 	_DistanceType;
 
+      const _DistanceType __len = std::distance(__first, __last);
+
+#if __glibcxx_constexpr_algorithms >= 202306L // >= C++26
+      if consteval {
+	// Simulate a _Temporary_buffer of length 1:
+	_ValueType __buf = std::move(*__first);
+	*__first = std::move(__buf);
+	return std::__stable_partition_adaptive(__first, __last, __pred,
+						__len,
+						&__buf,
+						_DistanceType(1));
+      }
+#endif
+
       _Temporary_buffer<_ForwardIterator, _ValueType>
-	__buf(__first, std::distance(__first, __last));
+	__buf(__first, __len);
       return
 	std::__stable_partition_adaptive(__first, __last, __pred,
-					 _DistanceType(__buf.requested_size()),
+					 __len,
 					 __buf.begin(),
 					 _DistanceType(__buf.size()));
     }
@@ -1548,6 +1564,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
    *  relative ordering after calling @p stable_partition().
   */
   template<typename _ForwardIterator, typename _Predicate>
+    _GLIBCXX26_CONSTEXPR
     inline _ForwardIterator
     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
 		     _Predicate __pred)
diff --git a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
index 8d5c1fb..072dd07 100644
--- a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
@@ -349,6 +349,7 @@ namespace std
     partition(_BIter, _BIter, _Predicate);
 
   template<typename _BIter, typename _Predicate>
+    _GLIBCXX26_CONSTEXPR
     _BIter
     stable_partition(_BIter, _BIter, _Predicate);
 
diff --git a/libstdc++-v3/testsuite/25_algorithms/stable_partition/constexpr.cc b/libstdc++-v3/testsuite/25_algorithms/stable_partition/constexpr.cc
new file mode 100644
index 0000000..8decc93
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/stable_partition/constexpr.cc
@@ -0,0 +1,44 @@
+// { dg-do compile { target c++26 } }
+
+#include <algorithm>
+#include <array>
+
+constexpr auto
+create_array()
+{
+  return std::to_array({0, 10, 1, 2, 3, 3, 4, -1, -2, -4, 5, 6});
+}
+
+constexpr bool
+test01()
+{
+  auto ar = create_array();
+  auto pred = [](int i) { return i % 2 == 0; };
+  std::stable_partition(ar.begin(), ar.end(), pred);
+  return std::is_partitioned(ar.begin(), ar.end(), pred);
+}
+
+static_assert(test01());
+
+constexpr bool
+test02()
+{
+  auto ar = create_array();
+  auto pred = [](int i) { return i % 2 == 0; };
+  std::ranges::stable_partition(ar, pred);
+  return std::ranges::is_partitioned(ar, pred);
+}
+
+static_assert(test02());
+
+constexpr bool
+test03()
+{
+  auto ar = create_array();
+  auto pred = [](int i) { return i % 2 == 0; };
+  auto proj = [](int i) { return i + 1; };
+  std::ranges::stable_partition(ar, pred, proj);
+  return std::ranges::is_partitioned(ar, pred, proj);
+}
+
+static_assert(test03());