Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/2226720/?format=api
{ "id": 2226720, "url": "http://patchwork.ozlabs.org/api/patches/2226720/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.2@forge-stage.sourceware.org/", "project": { "id": 17, "url": "http://patchwork.ozlabs.org/api/projects/17/?format=api", "name": "GNU Compiler Collection", "link_name": "gcc", "list_id": "gcc-patches.gcc.gnu.org", "list_email": "gcc-patches@gcc.gnu.org", "web_url": null, "scm_url": null, "webscm_url": null, "list_archive_url": "", "list_archive_url_format": "", "commit_url_format": "" }, "msgid": "<bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.2@forge-stage.sourceware.org>", "list_archive_url": null, "date": "2026-04-22T18:27:26", "name": "[v1,2/8] libstdc++: Directly implement ranges::sort [PR100795]", "commit_ref": null, "pull_url": null, "state": "new", "archived": false, "hash": "9f3810e5c124cc68462334a34bf59a907f2eafaf", "submitter": { "id": 93215, "url": "http://patchwork.ozlabs.org/api/people/93215/?format=api", "name": "ppalka via Sourceware Forge", "email": "forge-bot+ppalka@forge-stage.sourceware.org" }, "delegate": null, "mbox": "http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.2@forge-stage.sourceware.org/mbox/", "series": [ { "id": 501079, "url": "http://patchwork.ozlabs.org/api/series/501079/?format=api", "web_url": "http://patchwork.ozlabs.org/project/gcc/list/?series=501079", "date": "2026-04-22T18:27:24", "name": "libstdc++: C++20 iterator awareness fixes for various Ranges algorithms [PR100795]", "version": 1, "mbox": "http://patchwork.ozlabs.org/series/501079/mbox/" } ], "comments": "http://patchwork.ozlabs.org/api/patches/2226720/comments/", "check": "pending", "checks": "http://patchwork.ozlabs.org/api/patches/2226720/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org>", "X-Original-To": [ "incoming@patchwork.ozlabs.org", "gcc-patches@gcc.gnu.org" ], "Delivered-To": [ "patchwork-incoming@legolas.ozlabs.org", "gcc-patches@gcc.gnu.org" ], "Authentication-Results": [ "legolas.ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org\n (client-ip=2620:52:6:3111::32; helo=vm01.sourceware.org;\n envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org;\n receiver=patchwork.ozlabs.org)", "sourceware.org; dmarc=none (p=none dis=none)\n header.from=forge-stage.sourceware.org", "sourceware.org;\n spf=pass smtp.mailfrom=forge-stage.sourceware.org", "server2.sourceware.org;\n arc=none smtp.remote-ip=38.145.34.39" ], "Received": [ "from vm01.sourceware.org (vm01.sourceware.org\n [IPv6:2620:52:6:3111::32])\n\t(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n\t key-exchange x25519 server-signature ECDSA (secp384r1) server-digest SHA384)\n\t(No client certificate requested)\n\tby legolas.ozlabs.org (Postfix) with ESMTPS id 4g17Zv5HgPz1y2d\n\tfor <incoming@patchwork.ozlabs.org>; Thu, 23 Apr 2026 04:50:31 +1000 (AEST)", "from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id E9EDD40AAF2B\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 18:50:29 +0000 (GMT)", "from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id 2825548FEC17\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 18:28:35 +0000 (GMT)", "from forge-stage.sourceware.org (localhost [IPv6:::1])\n (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n key-exchange x25519 server-signature ECDSA (prime256v1) server-digest SHA256)\n (No client certificate requested)\n by forge-stage.sourceware.org (Postfix) with ESMTPS id 0456B4349C\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 18:28:35 +0000 (UTC)" ], "DKIM-Filter": [ "OpenDKIM Filter v2.11.0 sourceware.org E9EDD40AAF2B", "OpenDKIM Filter v2.11.0 sourceware.org 2825548FEC17" ], "DMARC-Filter": "OpenDMARC Filter v1.4.2 sourceware.org 2825548FEC17", "ARC-Filter": "OpenARC Filter v1.0.0 sourceware.org 2825548FEC17", "ARC-Seal": "i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776882515; cv=none;\n b=I3xu0v3hdsn+wVBK8J+ZY+GlQeTWWtDDp4CSwMdgmsrHyQHWTy9jemR2Lot4uX/r39uqlhwFeQ6CVVfsfoVYirRyCtwWgwv3dZh6I3A4C+vQUqF7jv6Jp7TcaONQZZ1BxlhgDentk55EwF25kpqZ7+MUOjPc69or5EJnTHJUqoU=", "ARC-Message-Signature": "i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776882515; c=relaxed/simple;\n bh=3lfR3IXKJlX9x/uDI77fmgEMTvKTiuKRSCfdEwQvcJk=;\n h=From:Date:Subject:MIME-Version:To:Message-ID;\n b=Q3396F9V0CXUZWfQ/C2Cam4mVa6kFqGTzgq59ciwvZdR5iJTMZGdjedsGYbC7EWJpKs0IMry6bKe+bcKxnMSmvT/kDxydd/ljSBG6a2BB8xPSMub1HCkcVcKSLVXmNbki7PP4t77u7ifxFlBhUVIe5x3of0BSnF4QGbNlOPM/GM=", "ARC-Authentication-Results": "i=1; server2.sourceware.org", "From": "ppalka via Sourceware Forge\n <forge-bot+ppalka@forge-stage.sourceware.org>", "Date": "Wed, 22 Apr 2026 18:27:26 +0000", "Subject": "[PATCH v1 2/8] libstdc++: Directly implement ranges::sort [PR100795]", "MIME-Version": "1.0", "Content-Type": "text/plain; charset=UTF-8", "Content-Transfer-Encoding": "8bit", "To": "gcc-patches mailing list <gcc-patches@gcc.gnu.org>", "Message-ID": "\n <bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.2@forge-stage.sourceware.org>", "X-Mailer": "batrachomyomachia", "X-Pull-Request-Organization": "gcc", "X-Pull-Request-Repository": "gcc-TEST", "X-Pull-Request": "https://forge.sourceware.org/gcc/gcc-TEST/pulls/57", "References": "\n <bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.0@forge-stage.sourceware.org>", "In-Reply-To": "\n <bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.0@forge-stage.sourceware.org>", "X-Patch-URL": "\n https://forge.sourceware.org/gcc/gcc-TEST/commit/61fabc90c7726b6d6d79fd61687207e841d96109", "X-BeenThere": "gcc-patches@gcc.gnu.org", "X-Mailman-Version": "2.1.30", "Precedence": "list", "List-Id": "Gcc-patches mailing list <gcc-patches.gcc.gnu.org>", "List-Unsubscribe": "<https://gcc.gnu.org/mailman/options/gcc-patches>,\n <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe>", "List-Archive": "<https://gcc.gnu.org/pipermail/gcc-patches/>", "List-Post": "<mailto:gcc-patches@gcc.gnu.org>", "List-Help": "<mailto:gcc-patches-request@gcc.gnu.org?subject=help>", "List-Subscribe": "<https://gcc.gnu.org/mailman/listinfo/gcc-patches>,\n <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe>", "Reply-To": "gcc-patches mailing list <gcc-patches@gcc.gnu.org>,\n ppalka@gcc.gnu.org", "Errors-To": "gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org" }, "content": "From: Patrick Palka <ppalka@redhat.com>\n\nAs with the previous patch, this patch reimplements ranges::sort\ndirectly instead of incorrectly forwarding to std::sort. In addition to\nthe compatibility changes listed in the previous patch we also:\n\n - use ranges::iter_swap instead of std::iter_swap\n - use ranges::move_backward instead of std::move_backward\n - use __bit_width and __to_unsigned_like instead of __lg\n\n\tPR libstdc++/100795\n\tPR libstdc++/118209\n\nlibstdc++-v3/ChangeLog:\n\n\t* include/bits/max_size_type.h (__bit_width): New explicit\n\tspecializatino for __max_size_type.\n\t* include/bits/ranges_algo.h (__detail::__move_median_to_first):\n\tNew, based on the stl_algo.h implementation.\n\t(__detail::__unguarded_liner_insert): Likewise.\n\t(__detail::__insertion_sort): Likewise.\n\t(__detail::__sort_threshold): Likewise.\n\t(__detail::__unguarded_insertion_sort): Likewise.\n\t(__detail::__final_insertion_sort): Likewise.\n\t(__detail::__unguarded_partition): Likewise.\n\t(__detail::__unguarded_partition_pivot): Likewise.\n\t(__detail::__heap_select): Likewise.\n\t(__detail::__partial_sort): Likewise.\n\t(__detail::__introsort_loop): Likewise.\n\t(__sort_fn::operator()): Reimplement in terms of the above.\n\t* libstdc++-v3/testsuite/25_algorithms/sort/118209.cc: New test.\n\t* libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc\n\t(test03): New test.\n\nReviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>\nReviewed-by: Jonathan Wakely <jwakely@redhat.com>\n---\n libstdc++-v3/include/bits/max_size_type.h | 11 ++\n libstdc++-v3/include/bits/ranges_algo.h | 168 +++++++++++++++++-\n .../testsuite/25_algorithms/sort/118209.cc | 23 +++\n .../25_algorithms/sort/constrained.cc | 31 ++++\n 4 files changed, 229 insertions(+), 4 deletions(-)\n create mode 100644 libstdc++-v3/testsuite/25_algorithms/sort/118209.cc", "diff": "diff --git a/libstdc++-v3/include/bits/max_size_type.h b/libstdc++-v3/include/bits/max_size_type.h\nindex e602b1b4bee5..73a6d141d5bc 100644\n--- a/libstdc++-v3/include/bits/max_size_type.h\n+++ b/libstdc++-v3/include/bits/max_size_type.h\n@@ -36,6 +36,7 @@\n \n #if __cplusplus > 201703L && __cpp_lib_concepts\n #include <ext/numeric_traits.h>\n+#include <bit> // __bit_width\n #include <numbers>\n \n // This header implements unsigned and signed integer-class types (as per\n@@ -818,6 +819,16 @@ namespace ranges\n { return min(); }\n };\n \n+ template<>\n+ inline constexpr int\n+ __bit_width(ranges::__detail::__max_size_type __x) noexcept\n+ {\n+ if (__x._M_msb)\n+ return numeric_limits<ranges::__detail::__max_size_type>::digits;\n+ else\n+ return std::__bit_width(__x._M_val);\n+ }\n+\n _GLIBCXX_END_NAMESPACE_VERSION\n } // namespace\n \ndiff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h\nindex d13729a83f72..de935dde4f70 100644\n--- a/libstdc++-v3/include/bits/ranges_algo.h\n+++ b/libstdc++-v3/include/bits/ranges_algo.h\n@@ -32,6 +32,7 @@\n \n #if __cplusplus > 201703L\n \n+#include <bit> // __bit_width\n #if __cplusplus > 202002L\n #include <optional>\n #endif\n@@ -2200,6 +2201,154 @@ namespace ranges\n \n inline constexpr __is_heap_fn is_heap{};\n \n+ namespace __detail\n+ {\n+ template<typename _Iter, typename _Comp>\n+ constexpr void\n+ __move_median_to_first(_Iter __result, _Iter __a, _Iter __b, _Iter __c,\n+\t\t\t _Comp __comp)\n+ {\n+\tif (__comp(*__a, *__b))\n+\t {\n+\t if (__comp(*__b, *__c))\n+\t ranges::iter_swap(__result, __b);\n+\t else if (__comp(*__a, *__c))\n+\t ranges::iter_swap(__result, __c);\n+\t else\n+\t ranges::iter_swap(__result, __a);\n+\t }\n+\telse if (__comp(*__a, *__c))\n+\t ranges::iter_swap(__result, __a);\n+\telse if (__comp(*__b, *__c))\n+\t ranges::iter_swap(__result, __c);\n+\telse\n+\t ranges::iter_swap(__result, __b);\n+ }\n+\n+ template<typename _Iter, typename _Comp>\n+ constexpr void\n+ __unguarded_linear_insert(_Iter __last, _Comp __comp)\n+ {\n+\titer_value_t<_Iter> __val = ranges::iter_move(__last);\n+\t_Iter __next = __last;\n+\t--__next;\n+\twhile (__comp(__val, *__next))\n+\t {\n+\t *__last = ranges::iter_move(__next);\n+\t __last = __next;\n+\t --__next;\n+\t }\n+\t*__last = std::move(__val);\n+ }\n+\n+ template<typename _Iter, typename _Comp>\n+ constexpr void\n+ __insertion_sort(_Iter __first, _Iter __last, _Comp __comp)\n+ {\n+\tif (__first == __last)\n+\t return;\n+\n+\tfor (_Iter __i = __first + 1; __i != __last; ++__i)\n+\t {\n+\t if (__comp(*__i, *__first))\n+\t {\n+\t\titer_value_t<_Iter> __val = ranges::iter_move(__i);\n+\t\tranges::move_backward(__first, __i, __i + 1);\n+\t\t*__first = std::move(__val);\n+\t }\n+\t else\n+\t __detail::__unguarded_linear_insert(__i, __comp);\n+\t }\n+ }\n+\n+ template<typename _Iter, typename _Comp>\n+ constexpr void\n+ __unguarded_insertion_sort(_Iter __first, _Iter __last, _Comp __comp)\n+ {\n+\tfor (_Iter __i = __first; __i != __last; ++__i)\n+\t __detail::__unguarded_linear_insert(__i, __comp);\n+ }\n+\n+ inline constexpr int __sort_threshold = 16;\n+\n+ template<typename _Iter, typename _Comp>\n+ constexpr void\n+ __final_insertion_sort(_Iter __first, _Iter __last, _Comp __comp)\n+ {\n+\tif (__last - __first > __sort_threshold)\n+\t {\n+\t __detail::__insertion_sort(__first, __first + __sort_threshold, __comp);\n+\t __detail::__unguarded_insertion_sort(__first + __sort_threshold, __last,\n+\t\t\t\t\t\t __comp);\n+\t }\n+\telse\n+\t __detail::__insertion_sort(__first, __last, __comp);\n+ }\n+\n+ template<typename _Iter, typename _Comp>\n+ constexpr _Iter\n+ __unguarded_partition(_Iter __first, _Iter __last, _Iter __pivot, _Comp __comp)\n+ {\n+\twhile (true)\n+\t {\n+\t while (__comp(*__first, *__pivot))\n+\t ++__first;\n+\t --__last;\n+\t while (__comp(*__pivot, *__last))\n+\t --__last;\n+\t if (!(__first < __last))\n+\t return __first;\n+\t ranges::iter_swap(__first, __last);\n+\t ++__first;\n+\t }\n+ }\n+\n+ template<typename _Iter, typename _Comp>\n+ constexpr _Iter\n+ __unguarded_partition_pivot(_Iter __first, _Iter __last, _Comp __comp)\n+ {\n+\t_Iter __mid = __first + (__last - __first) / 2;\n+\t__detail::__move_median_to_first(__first, __first + 1, __mid, __last - 1, __comp);\n+\treturn __detail::__unguarded_partition(__first + 1, __last, __first, __comp);\n+ }\n+\n+ template<typename _Iter, typename _Comp>\n+ constexpr void\n+ __heap_select(_Iter __first, _Iter __middle, _Iter __last, _Comp __comp)\n+ {\n+\tranges::make_heap(__first, __middle, __comp);\n+\tfor (_Iter __i = __middle; __i < __last; ++__i)\n+\t if (__comp(*__i, *__first))\n+\t __detail::__pop_heap(__first, __middle, __i, __comp);\n+ }\n+\n+ template<typename _Iter, typename _Comp>\n+ constexpr void\n+ __partial_sort(_Iter __first, _Iter __middle, _Iter __last, _Comp __comp)\n+ {\n+\t__detail::__heap_select(__first, __middle, __last, __comp);\n+\tranges::sort_heap(__first, __middle, __comp);\n+ }\n+\n+ template<typename _Iter, typename _Comp>\n+ constexpr void\n+ __introsort_loop(_Iter __first, _Iter __last, unsigned __depth_limit, _Comp __comp)\n+ {\n+\twhile (__last - __first > __sort_threshold)\n+\t {\n+\t if (__depth_limit == 0)\n+\t {\n+\t\t__detail::__partial_sort(__first, __last, __last, __comp);\n+\t\treturn;\n+\t }\n+\t --__depth_limit;\n+\t _Iter __cut = __detail::__unguarded_partition_pivot(__first, __last, __comp);\n+\t __detail::__introsort_loop(__cut, __last, __depth_limit, __comp);\n+\t __last = __cut;\n+\t }\n+ }\n+ } // namespace __detail\n+\n struct __sort_fn\n {\n template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,\n@@ -2209,10 +2358,21 @@ namespace ranges\n operator()(_Iter __first, _Sent __last,\n \t\t _Comp __comp = {}, _Proj __proj = {}) const\n {\n-\tauto __lasti = ranges::next(__first, __last);\n-\t_GLIBCXX_STD_A::sort(std::move(__first), __lasti,\n-\t\t\t __detail::__make_comp_proj(__comp, __proj));\n-\treturn __lasti;\n+\tif constexpr (!same_as<_Iter, _Sent>)\n+\t return (*this)(__first, ranges::next(__first, __last),\n+\t\t\t std::move(__comp), std::move(__proj));\n+\telse\n+\t {\n+\t if (__first != __last)\n+\t {\n+\t\tauto __comp_proj = __detail::__make_comp_proj(__comp, __proj);\n+\t\tauto __n = __detail::__to_unsigned_like(__last - __first);\n+\t\tunsigned __depth_limit = (std::__bit_width(__n) - 1) * 2;\n+\t\t__detail::__introsort_loop(__first, __last, __depth_limit, __comp_proj);\n+\t\t__detail::__final_insertion_sort(__first, __last, __comp_proj);\n+\t }\n+\t return __last;\n+\t }\n }\n \n template<random_access_range _Range,\ndiff --git a/libstdc++-v3/testsuite/25_algorithms/sort/118209.cc b/libstdc++-v3/testsuite/25_algorithms/sort/118209.cc\nnew file mode 100644\nindex 000000000000..6dedbde75173\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/25_algorithms/sort/118209.cc\n@@ -0,0 +1,23 @@\n+// PR libstdc++ - ranges::sort doesn't use iter_move, cannot sort zip of move-only type\n+// { dg-do compile { target c++23 } }\n+\n+#include <algorithm>\n+#include <ranges>\n+#include <vector>\n+\n+struct F {\n+ int a = -1;\n+ explicit F(int d) : a(d) { }\n+ F(const F&) = delete;\n+ F(F&& o) : a(o.a) { }\n+ void operator=(const F&) = delete;\n+ F& operator=(F&& o) { return *this; }\n+ auto operator<=>(const F&) const = default;\n+};\n+\n+int main () {\n+ int a[] = {3,2,1};\n+ std::vector<F> v(a, a+3);\n+ std::ranges::sort(v); // OK\n+ std::ranges::sort(std::views::zip(v)); // didn't compile\n+}\ndiff --git a/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc\nindex 82754af96430..930dbd77a376 100644\n--- a/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc\n+++ b/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc\n@@ -20,6 +20,7 @@\n \n #include <algorithm>\n #include <random>\n+#include <ranges>\n #include <vector>\n #include <testsuite_hooks.h>\n #include <testsuite_iterators.h>\n@@ -72,9 +73,39 @@ test02()\n \t && ranges::equal(x, y, {}, &X::i, &X::i));\n }\n \n+constexpr bool\n+test03()\n+{\n+ // PR libstdc++/100795 - ranges::sort should not use std::sort directly\n+#if __SIZEOF_INT128__\n+ auto v = std::views::iota(__int128(0), __int128(20));\n+#else\n+ auto v = std::views::iota(0ll, 20ll);\n+#endif\n+\n+ int storage[20] = {2,5,4,3,1,6,7,9,10,8,11,14,12,13,15,16,18,0,19,17};\n+ auto w = v | std::views::transform([&](auto i) -> int& { return storage[i]; });\n+ using type = decltype(w);\n+ using cat = std::iterator_traits<std::ranges::iterator_t<type>>::iterator_category;\n+ static_assert( std::same_as<cat, std::output_iterator_tag> );\n+ static_assert( std::ranges::random_access_range<type> );\n+\n+ ranges::sort(w);\n+ VERIFY( ranges::equal(w, v) );\n+\n+ ranges::sort(w, std::ranges::greater{});\n+ VERIFY( ranges::equal(w, v | std::views::reverse) );\n+\n+ ranges::sort(w, std::ranges::greater{}, std::negate{});\n+ VERIFY( ranges::equal(w, v) );\n+\n+ return true;\n+}\n+\n int\n main()\n {\n test01();\n static_assert(test02());\n+ static_assert(test03());\n }\n", "prefixes": [ "v1", "2/8" ] }