libstdc++: add constexpr inplace_merge

This commit adds support for constexpr inplace_merge, added by P2562R1
for C++26. The implementation strategy is the same as for constexpr
stable_sort: use if consteval to detect if we're in constant evaluation,
and dispatch to a suitable path (same one as freestanding).

libstdc++-v3/ChangeLog:

	* include/bits/algorithmfwd.h (inplace_merge): Mark it as
	constexpr for C++26.
	* include/bits/ranges_algo.h (__inplace_merge_fn): Likewise.
	* include/bits/stl_algo.h (inplace_merge): Mark it as constexpr;
	during constant evaluation, dispatch to the non-allocating
	codepath.
	* testsuite/25_algorithms/headers/algorithm/synopsis.cc
	(inplace_merge): Add constexpr.
	* testsuite/25_algorithms/inplace_merge/constexpr.cc: New test.

5 files changed, 87 insertions, 0 deletions

diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h
index 3e81bca..05894b5 100644
--- a/libstdc++-v3/include/bits/algorithmfwd.h
+++ b/libstdc++-v3/include/bits/algorithmfwd.h
@@ -315,10 +315,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     includes(_IIter1, _IIter1, _IIter2, _IIter2, _Compare);
 
   template<typename _BIter>
+    _GLIBCXX26_CONSTEXPR
     void
     inplace_merge(_BIter, _BIter, _BIter);
 
   template<typename _BIter, typename _Compare>
+    _GLIBCXX26_CONSTEXPR
     void
     inplace_merge(_BIter, _BIter, _BIter, _Compare);
 
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index d3644a8..2814d90 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -2598,6 +2598,7 @@ namespace ranges
 	     typename _Comp = ranges::less,
 	     typename _Proj = identity>
       requires sortable<_Iter, _Comp, _Proj>
+      _GLIBCXX26_CONSTEXPR
       _Iter
       operator()(_Iter __first, _Iter __middle, _Sent __last,
 		 _Comp __comp = {}, _Proj __proj = {}) const
@@ -2611,6 +2612,7 @@ namespace ranges
     template<bidirectional_range _Range,
 	     typename _Comp = ranges::less, typename _Proj = identity>
       requires sortable<iterator_t<_Range>, _Comp, _Proj>
+      _GLIBCXX26_CONSTEXPR
       borrowed_iterator_t<_Range>
       operator()(_Range&& __r, iterator_t<_Range> __middle,
 		 _Comp __comp = {}, _Proj __proj = {}) const
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index c3fea76..bb7dbfb 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2465,6 +2465,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
     }
 
   template<typename _BidirectionalIterator, typename _Compare>
+    _GLIBCXX26_CONSTEXPR
     void
     __inplace_merge(_BidirectionalIterator __first,
 		    _BidirectionalIterator __middle,
@@ -2483,6 +2484,12 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
       const _DistanceType __len2 = std::distance(__middle, __last);
 
 #if _GLIBCXX_HOSTED
+# if __glibcxx_constexpr_algorithms >= 202306L // >= C++26
+      if consteval {
+	return std::__merge_without_buffer
+	  (__first, __middle, __last, __len1, __len2, __comp);
+      }
+# endif
       typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
       // __merge_adaptive will use a buffer for the smaller of
       // [first,middle) and [middle,last).
@@ -2523,6 +2530,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
    *  distance(__first,__last).
   */
   template<typename _BidirectionalIterator>
+    _GLIBCXX26_CONSTEXPR
     inline void
     inplace_merge(_BidirectionalIterator __first,
 		  _BidirectionalIterator __middle,
@@ -2564,6 +2572,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
    *  the function used for the initial sort.
   */
   template<typename _BidirectionalIterator, typename _Compare>
+    _GLIBCXX26_CONSTEXPR
     inline void
     inplace_merge(_BidirectionalIterator __first,
 		  _BidirectionalIterator __middle,
diff --git a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
index 5000b18..8d5c1fb 100644
--- a/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/headers/algorithm/synopsis.cc
@@ -458,10 +458,12 @@ namespace std
     merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
 
   template<typename _BIter>
+    _GLIBCXX26_CONSTEXPR
     void
     inplace_merge(_BIter, _BIter, _BIter);
 
   template<typename _BIter, typename _Compare>
+    _GLIBCXX26_CONSTEXPR
     void
     inplace_merge(_BIter, _BIter, _BIter, _Compare);
 
diff --git a/libstdc++-v3/testsuite/25_algorithms/inplace_merge/constexpr.cc b/libstdc++-v3/testsuite/25_algorithms/inplace_merge/constexpr.cc
new file mode 100644
index 0000000..0bc4ed4
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/inplace_merge/constexpr.cc
@@ -0,0 +1,72 @@
+// { dg-do compile { target c++26 } }
+
+#include <algorithm>
+#include <array>
+#include <functional>
+#include <utility>
+
+// returns a pair [array, index of partitioning point]
+constexpr auto
+create_array()
+{
+  return std::make_pair(
+    std::to_array({0, 2, 2, 2, 4, 6, 1, 2, 3, 3, 4, 4, 5}),
+    6);
+}
+
+constexpr bool
+test01()
+{
+  auto [ar, index] = create_array();
+  std::inplace_merge(ar.begin(), ar.begin() + index, ar.end());
+  return std::is_sorted(ar.begin(), ar.end());
+}
+
+static_assert(test01());
+
+constexpr bool
+test02()
+{
+  auto [ar, index] = create_array();
+  auto index_it = ar.begin() + index;
+  std::reverse(ar.begin(), index_it);
+  std::reverse(index_it, ar.end());
+  std::inplace_merge(ar.begin(), index_it, ar.end(), std::greater<>());
+  return std::is_sorted(ar.begin(), ar.end(), std::greater<>());
+}
+
+static_assert(test02());
+
+constexpr bool
+test03()
+{
+  auto [ar, index] = create_array();
+  std::ranges::inplace_merge(ar, ar.begin() + index);
+  return std::ranges::is_sorted(ar);
+}
+
+static_assert(test03());
+
+constexpr bool
+test04()
+{
+  auto [ar, index] = create_array();
+  auto index_it = ar.begin() + index;
+  std::ranges::reverse(ar.begin(), index_it);
+  std::ranges::reverse(index_it, ar.end());
+  std::ranges::inplace_merge(ar, index_it, std::ranges::greater());
+  return std::ranges::is_sorted(ar, std::ranges::greater());
+}
+
+static_assert(test04());
+
+constexpr bool
+test05()
+{
+  auto [ar, index] = create_array();
+  auto proj = [](int i) { return -i; };
+  std::ranges::inplace_merge(ar, ar.begin() + index, std::ranges::greater(), proj);
+  return std::ranges::is_sorted(ar, std::ranges::greater(), proj);
+}
+
+static_assert(test05());