{"id":2226711,"url":"http://patchwork.ozlabs.org/api/patches/2226711/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.1@forge-stage.sourceware.org/","project":{"id":17,"url":"http://patchwork.ozlabs.org/api/projects/17/?format=json","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.1@forge-stage.sourceware.org>","list_archive_url":null,"date":"2026-04-22T18:27:25","name":"[v1,1/8] libstdc++: Directly implement ranges::heap algos [PR100795]","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"af620647456646094db754fdfb2cb2cfbb0fb087","submitter":{"id":93215,"url":"http://patchwork.ozlabs.org/api/people/93215/?format=json","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.1@forge-stage.sourceware.org/mbox/","series":[{"id":501079,"url":"http://patchwork.ozlabs.org/api/series/501079/?format=json","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/2226711/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/2226711/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 4g17TZ3qVkz1yD5\n\tfor <incoming@patchwork.ozlabs.org>; Thu, 23 Apr 2026 04:45:54 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id AD742409F62C\n\tfor <incoming@patchwork.ozlabs.org>; Wed, 22 Apr 2026 18:45:52 +0000 (GMT)","from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id 1981F48FEDA0\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 EA7084349B\n for <gcc-patches@gcc.gnu.org>; Wed, 22 Apr 2026 18:28:34 +0000 (UTC)"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org AD742409F62C","OpenDKIM Filter v2.11.0 sourceware.org 1981F48FEDA0"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org 1981F48FEDA0","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org 1981F48FEDA0","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776882515; cv=none;\n b=jEutIVV8dfnALXl471si6aRHNJ0ftr6jNcQBAwem6x1NwqL6r0/VCWuksxhvvgRXI4KxJlnwBMY2aIPseYPrSSiLCJDHHJhDWNQrwUOGbK8MZ0k6Ayfgkc1ebENiDcqJx4y54+EdgwVvOpM3H+PUd4OAnHQTm4JcBBN4d7d9QdA=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776882515; c=relaxed/simple;\n bh=RmKcyG0UJydE3dmCKhBz6HYZPLMXw+TVDWaF5HodpOo=;\n h=From:Date:Subject:MIME-Version:To:Message-ID;\n b=Xezef+yxyDvy+EE0+dFKXfY88BkvLIaUJb0F/w2ydAikImdKMlYfOmObO12nS/PH2zNk4N8Pg2hY5I5+ZL6PEJirjA+RlipJ9OTfj4eQFu2uZUm8k5zpiezlgDI+NFxeekHM8Fc9ZEZ7wgQsshqvCQtWBlYU89Q8Ej5WxcV+xhQ=","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:25 +0000","Subject":"[PATCH v1 1/8] libstdc++: Directly implement ranges::heap algos\n [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.1@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/a36e939a6a159d13cf052971275f6ef3c3d00052","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\nranges::push_heap, ranges::pop_heap, ranges::make_heap and\nranges::sort_heap are currently defined in terms of the corresponding\nSTL-style algorithms, but this is incorrect because the STL-style\nalgorithms rely on the legacy iterator system, and so misbehave when\npassed a narrowly C++20 random access iterator.  The other ranges heap\nalgos, ranges::is_heap and ranges::is_heap_until, are implemented\ndirectly already and have no known issues.\n\nThis patch reimplements these ranges:: algos directly instead, based\nclosely on the legacy stl_heap.h implementation, with the following\nchanges for compatibility with the C++20 iterator system:\n\n  - handle non-common ranges by computing the corresponding end iterator\n  - use ranges::iter_move instead of std::move(*iter)\n  - use iter_value_t / iter_difference_t instead of iterator_traits\n\nBesides these changes, the implementation of these algorithms is\nintended to mirror the stl_heap.h implementations, for ease of\nmaintenance and review.\n\nNote that we don't explicitly pass the projection function throughout,\ninstead we just create and pass a composite predicate via __make_comp_proj.\n\n\tPR libstdc++/100795\n\nlibstdc++-v3/ChangeLog:\n\n\t* include/bits/ranges_algo.h (__detail::__push_heap): New,\n\tbased on the stl_heap.h implementation.\n\t(__push_heap_fn::operator()): Reimplement in terms of the above.\n\t(__detail::__adjust_heap): New, based on the stl_heap.h\n\timplementation.\n\t(__deatil::__pop_heap): Likewise.\n\t(__pop_heap_fn::operator()): Reimplement in terms of the above.\n\t(__make_heap_fn::operator()): Likewise.\n\t(__sort_heap_fn::operator()): Likewise.\n\t* testsuite/25_algorithms/heap/constrained.cc (test03): New\n\ttest.\n\nReviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>\nReviewed-by: Jonathan Wakely <jwakely@redhat.com>\n---\n libstdc++-v3/include/bits/ranges_algo.h       | 140 ++++++++++++++++--\n .../25_algorithms/heap/constrained.cc         |  46 ++++++\n 2 files changed, 170 insertions(+), 16 deletions(-)","diff":"diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h\nindex 5aca6e8d864d..d13729a83f72 100644\n--- a/libstdc++-v3/include/bits/ranges_algo.h\n+++ b/libstdc++-v3/include/bits/ranges_algo.h\n@@ -1913,6 +1913,28 @@ namespace ranges\n \n   inline constexpr __shuffle_fn shuffle{};\n \n+  namespace __detail\n+  {\n+    template<typename _Iter, typename _Comp>\n+      constexpr void\n+      __push_heap(_Iter __first,\n+\t\t  iter_difference_t<_Iter> __holeIndex,\n+\t\t  iter_difference_t<_Iter> __topIndex,\n+\t\t  iter_value_t<_Iter> __value,\n+\t\t  _Comp __comp)\n+      {\n+\tauto __parent = (__holeIndex - 1) / 2;\n+\twhile (__holeIndex > __topIndex\n+\t       && __comp(*(__first + __parent), __value))\n+\t  {\n+\t    *(__first + __holeIndex) = ranges::iter_move(__first + __parent);\n+\t    __holeIndex = __parent;\n+\t    __parent = (__holeIndex - 1) / 2;\n+\t  }\n+\t*(__first + __holeIndex) = std::move(__value);\n+      }\n+  } // namespace __detail\n+\n   struct __push_heap_fn\n   {\n     template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,\n@@ -1922,10 +1944,17 @@ 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-\tstd::push_heap(__first, __lasti,\n-\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    auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);\n+\t    __detail::__push_heap(__first, (__last - __first) - 1,\n+\t\t\t\t  0, ranges::iter_move(__last - 1),\n+\t\t\t\t  __comp_proj);\n+\t    return __last;\n+\t  }\n       }\n \n     template<random_access_range _Range,\n@@ -1941,6 +1970,48 @@ namespace ranges\n \n   inline constexpr __push_heap_fn push_heap{};\n \n+  namespace __detail\n+  {\n+    template<typename _Iter, typename _Comp>\n+      constexpr void\n+      __adjust_heap(_Iter __first,\n+\t\t    iter_difference_t<_Iter> __holeIndex,\n+\t\t    iter_difference_t<_Iter> __len,\n+\t\t    iter_value_t<_Iter> __value,\n+\t\t    _Comp __comp)\n+      {\n+\tauto __topIndex = __holeIndex;\n+\tauto __secondChild = __holeIndex;\n+\twhile (__secondChild < (__len - 1) / 2)\n+\t  {\n+\t    __secondChild = 2 * (__secondChild + 1);\n+\t    if (__comp(*(__first + __secondChild),\n+\t\t       *(__first + (__secondChild - 1))))\n+\t      __secondChild--;\n+\t    *(__first + __holeIndex) = ranges::iter_move(__first + __secondChild);\n+\t    __holeIndex = __secondChild;\n+\t  }\n+\tif ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)\n+\t  {\n+\t    __secondChild = 2 * (__secondChild + 1);\n+\t    *(__first + __holeIndex) = ranges::iter_move(__first + (__secondChild - 1));\n+\t    __holeIndex = __secondChild - 1;\n+\t  }\n+\t__detail::__push_heap(__first, __holeIndex, __topIndex,\n+\t\t\t      std::move(__value), __comp);\n+      }\n+\n+    template<typename _Iter, typename _Comp>\n+      constexpr void\n+      __pop_heap(_Iter __first, _Iter __last, _Iter __result, _Comp __comp)\n+      {\n+\titer_value_t<_Iter> __value = ranges::iter_move(__result);\n+\t*__result = ranges::iter_move(__first);\n+\t__detail::__adjust_heap(__first, 0, __last - __first,\n+\t\t\t\tstd::move(__value), __comp);\n+      }\n+  } // namespace __detail\n+\n   struct __pop_heap_fn\n   {\n     template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,\n@@ -1950,10 +2021,18 @@ 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-\tstd::pop_heap(__first, __lasti,\n-\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 (__last - __first > 1)\n+\t      {\n+\t\tauto __comp_proj = __detail::__make_comp_proj(__comp, __proj);\n+\t\t__detail::__pop_heap(__first, __last - 1, __last - 1, __comp_proj);\n+\t      }\n+\t    return __last;\n+\t  }\n       }\n \n     template<random_access_range _Range,\n@@ -1978,10 +2057,29 @@ 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-\tstd::make_heap(__first, __lasti,\n-\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    const auto __len = __last - __first;\n+\t    if (__len < 2)\n+\t      return __last;\n+\n+\t    auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);\n+\t    auto __parent = (__len - 2) / 2;\n+\t    while (true)\n+\t      {\n+\t\titer_value_t<_Iter> __value = ranges::iter_move(__first + __parent);\n+\t\t__detail::__adjust_heap(__first, __parent, __len,\n+\t\t\t\t\tstd::move(__value),\n+\t\t\t\t\t__comp_proj);\n+\t\tif (__parent == 0)\n+\t\t  break;\n+\t\t__parent--;\n+\t      }\n+\t    return __last;\n+\t  }\n       }\n \n     template<random_access_range _Range,\n@@ -2006,10 +2104,20 @@ 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-\tstd::sort_heap(__first, __lasti,\n-\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    auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);\n+\t    _Iter __ret = __last;\n+\t    while (__last - __first > 1)\n+\t      {\n+\t\t--__last;\n+\t\t__detail::__pop_heap(__first, __last, __last, __comp_proj);\n+\t      }\n+\t    return __ret;\n+\t  }\n       }\n \n     template<random_access_range _Range,\ndiff --git a/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc\nindex 8037a2db6b80..5486c8552d03 100644\n--- a/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc\n+++ b/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc\n@@ -20,6 +20,7 @@\n \n #include <algorithm>\n #include <random>\n+#include <ranges>\n #include <testsuite_hooks.h>\n #include <testsuite_iterators.h>\n \n@@ -97,10 +98,55 @@ test02()\n   return ok;\n }\n \n+constexpr bool\n+test03()\n+{\n+  // PR libstdc++/100795 - ranges::heap algos should not use std::heap 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+  for (int i = 1; i < 20; i++)\n+    ranges::push_heap(w.begin(), w.begin() + i);\n+  ranges::sort_heap(w);\n+  VERIFY( ranges::equal(w, v) );\n+  ranges::make_heap(w);\n+  auto it = ranges::pop_heap(w);\n+  VERIFY( it[-1] == 19 );\n+\n+  for (int i = 1; i < 20; i++)\n+    ranges::push_heap(w.begin(), w.begin() + i, std::ranges::greater{});\n+  ranges::sort_heap(w, std::ranges::greater{});\n+  VERIFY( ranges::equal(w, v | std::views::reverse) );\n+  ranges::make_heap(w, std::ranges::greater{});\n+  it = ranges::pop_heap(w, std::ranges::greater{});\n+  VERIFY( it[-1] == 0 );\n+\n+  for (int i = 1; i < 20; i++)\n+    ranges::push_heap(w.begin(), w.begin() + i, std::ranges::greater{}, std::negate{});\n+  ranges::sort_heap(w, std::ranges::greater{}, std::negate{});\n+  VERIFY( ranges::equal(w, v) );\n+  ranges::make_heap(w, std::ranges::greater{}, std::negate{});\n+  it = ranges::pop_heap(w, std::ranges::greater{}, std::negate{});\n+  VERIFY( it[-1] == 19 );\n+\n+  return true;\n+}\n+\n int\n main()\n {\n   test01<test_range>();\n   test01<test_container>();\n   static_assert(test02());\n+  static_assert(test03());\n }\n","prefixes":["v1","1/8"]}