{"id":2226278,"url":"http://patchwork.ozlabs.org/api/1.1/patches/2226278/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhubic1gpg.gcc.gcc-TEST.redi.24.1.1@forge-stage.sourceware.org/","project":{"id":17,"url":"http://patchwork.ozlabs.org/api/1.1/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},"msgid":"","date":"2026-04-22T10:35:08","name":"[v1,1/1] libstdc++: Make equal and is_permutation short-circuit (LWG 3560)","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"b8663ab0da0ee1295632a6685626f5b7b5ea3db3","submitter":{"id":93210,"url":"http://patchwork.ozlabs.org/api/1.1/people/93210/?format=json","name":"Jonathan Wakely via Sourceware Forge","email":"forge-bot+redi@forge-stage.sourceware.org"},"delegate":null,"mbox":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhubic1gpg.gcc.gcc-TEST.redi.24.1.1@forge-stage.sourceware.org/mbox/","series":[{"id":500978,"url":"http://patchwork.ozlabs.org/api/1.1/series/500978/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/list/?series=500978","date":"2026-04-22T10:35:07","name":"libstdc++: Make equal and is_permutation short-circuit (LWG 3560)","version":1,"mbox":"http://patchwork.ozlabs.org/series/500978/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/patches/2226278/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/2226278/checks/","tags":{},"headers":{"Return-Path":"","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=38.145.34.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 [38.145.34.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 4g0xF06QPYz1y2d\n\tfor ; Wed, 22 Apr 2026 21:04:20 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id CA6DC427C740\n\tfor ; Wed, 22 Apr 2026 11:04:18 +0000 (GMT)","from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id C83A1436303B\n for ; Wed, 22 Apr 2026 10:36:00 +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 A402542B46\n for ; Wed, 22 Apr 2026 10:36:00 +0000 (UTC)"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org CA6DC427C740","OpenDKIM Filter v2.11.0 sourceware.org C83A1436303B"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org C83A1436303B","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org C83A1436303B","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776854160; cv=none;\n b=T3GyFU0j9QQhX1wdjkNUSlb3EWfOyIzhrKe5gO0wNfMleeKsQuxW8Up1e1EIzLBGTQhoTVL2LBORWq9I1CWzWe8XLZk9e+I03CfVOQVs3+T4BKt5HsAuhHWgW09NTNhIxYNOMsKohj22vbRXA03MfQ3dStkudvsY6PcP5Wj8jbk=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776854160; c=relaxed/simple;\n bh=1rVqcvt96o3uZDCyMPPhhDn/2BHxxU3DRT4bJuTcdYs=;\n h=From:Date:Subject:To:Message-ID;\n b=cOwAmBUf3krNgIbTXvC8zGZJwUk6+FdgdRaYB0to1pd+crFu31GywW3dW+B62jEpwHJ/Ra856Kxs9sY394E52DMWDVgDIXGnthmPgZwL9ACzCKLsyVyNal9b8fd1J7R5RaeFNlcIlTBhrfow6i5IXaIT6kML4U5iTWz4NdEcitI=","ARC-Authentication-Results":"i=1; server2.sourceware.org","From":"Jonathan Wakely via Sourceware Forge\n ","Date":"Wed, 22 Apr 2026 10:35:08 +0000","Subject":"[PATCH v1 1/1] libstdc++: Make equal and is_permutation short-circuit\n (LWG 3560)","To":"gcc-patches mailing list ","Message-ID":"\n ","X-Mailer":"batrachomyomachia","X-Requested-Reviewer":"ppalka","X-Pull-Request-Organization":"gcc","X-Pull-Request-Repository":"gcc-TEST","X-Pull-Request":"https://forge.sourceware.org/gcc/gcc-TEST/pulls/24","References":"\n ","In-Reply-To":"\n ","X-Patch-URL":"\n https://forge.sourceware.org/redi/gcc/commit/4116ef62cffdfd7b2e7b5868c2a5bd52addc8b92","X-BeenThere":"gcc-patches@gcc.gnu.org","X-Mailman-Version":"2.1.30","Precedence":"list","List-Id":"Gcc-patches mailing list ","List-Unsubscribe":",\n ","List-Archive":"","List-Post":"","List-Help":"","List-Subscribe":",\n ","Reply-To":"gcc-patches mailing list , redi@gcc.gnu.org","Errors-To":"gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org"},"content":"From: Jonathan Wakely \n\nWe already implement short-circuiting for random access iterators, but\nwe also need to do so for ranges::equal and ranges::is_permutation when\ngiven sized ranges that are not random access ranges (e.g. std::list).\n\nlibstdc++-v3/ChangeLog:\n\n\t* include/bits/ranges_algo.h (__is_permutation_fn::operator()):\n\tShort-circuit for sized ranges with different sizes, as per LWG\n\t3560.\n\t* include/bits/ranges_algobase.h (__equal_fn::operator()):\n\tLikewise.\n\t* include/bits/stl_algo.h (__is_permutation): Use if-constexpr\n\tfor random access iterator branches.\n\t* include/bits/stl_algobase.h (__equal4): Likewise.\n\t* testsuite/25_algorithms/equal/lwg3560.cc: New test.\n\t* testsuite/25_algorithms/is_permutation/lwg3560.cc: New test.\n---\n libstdc++-v3/include/bits/ranges_algo.h | 7 +++\n libstdc++-v3/include/bits/ranges_algobase.h | 7 +++\n libstdc++-v3/include/bits/stl_algo.h | 13 ++---\n libstdc++-v3/include/bits/stl_algobase.h | 44 ++++++++--------\n .../testsuite/25_algorithms/equal/lwg3560.cc | 49 ++++++++++++++++++\n .../25_algorithms/is_permutation/lwg3560.cc | 51 +++++++++++++++++++\n 6 files changed, 145 insertions(+), 26 deletions(-)\n create mode 100644 libstdc++-v3/testsuite/25_algorithms/equal/lwg3560.cc\n create mode 100644 libstdc++-v3/testsuite/25_algorithms/is_permutation/lwg3560.cc","diff":"diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h\nindex bae36637b3e3..80d4f5a0d574 100644\n--- a/libstdc++-v3/include/bits/ranges_algo.h\n+++ b/libstdc++-v3/include/bits/ranges_algo.h\n@@ -595,6 +595,13 @@ namespace ranges\n operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},\n \t\t _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const\n {\n+\t// _GLIBCXX_RESOLVE_LIB_DEFECTS\n+\t// 3560. ranges::is_permutation should short-circuit for sized_ranges\n+\tif constexpr (sized_range<_Range1>)\n+\t if constexpr (sized_range<_Range2>)\n+\t if (ranges::distance(__r1) != ranges::distance(__r2))\n+\t return false;\n+\n \treturn (*this)(ranges::begin(__r1), ranges::end(__r1),\n \t\t ranges::begin(__r2), ranges::end(__r2),\n \t\t std::move(__pred),\ndiff --git a/libstdc++-v3/include/bits/ranges_algobase.h b/libstdc++-v3/include/bits/ranges_algobase.h\nindex df4e770e7a65..150e990f9ae8 100644\n--- a/libstdc++-v3/include/bits/ranges_algobase.h\n+++ b/libstdc++-v3/include/bits/ranges_algobase.h\n@@ -172,6 +172,13 @@ namespace ranges\n operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},\n \t\t _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const\n {\n+\t// _GLIBCXX_RESOLVE_LIB_DEFECTS\n+\t// 3560. ranges::equal [...] should short-circuit for sized_ranges\n+\tif constexpr (sized_range<_Range1>)\n+\t if constexpr (sized_range<_Range2>)\n+\t if (ranges::distance(__r1) != ranges::distance(__r2))\n+\t return false;\n+\n \treturn (*this)(ranges::begin(__r1), ranges::end(__r1),\n \t\t ranges::begin(__r2), ranges::end(__r2),\n \t\t std::move(__pred),\ndiff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h\nindex 04bdaa669816..d8a7668ff831 100644\n--- a/libstdc++-v3/include/bits/stl_algo.h\n+++ b/libstdc++-v3/include/bits/stl_algo.h\n@@ -3471,6 +3471,8 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)\n }\n \n #if __cplusplus > 201103L\n+#pragma GCC diagnostic push\n+#pragma GCC diagnostic ignored \"-Wc++17-extensions\" // if constexpr\n template\n _GLIBCXX20_CONSTEXPR\n@@ -3485,12 +3487,10 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)\n \t= typename iterator_traits<_ForwardIterator2>::iterator_category;\n using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;\n using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;\n- constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();\n- if (__ra_iters)\n+ constexpr bool __ra_iters = __and_<_It1_is_RA, _It2_is_RA>::value;\n+ if constexpr (__ra_iters)\n \t{\n-\t auto __d1 = std::distance(__first1, __last1);\n-\t auto __d2 = std::distance(__first2, __last2);\n-\t if (__d1 != __d2)\n+\t if ((__last1 - __first1) != (__last2 - __first2))\n \t return false;\n \t}\n \n@@ -3501,7 +3501,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)\n \tif (!__pred(__first1, __first2))\n \t break;\n \n- if (__ra_iters)\n+ if constexpr (__ra_iters)\n \t{\n \t if (__first1 == __last1)\n \t return true;\n@@ -3532,6 +3532,7 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)\n \t}\n return true;\n }\n+#pragma GCC diagnostic pop\n \n /**\n * @brief Checks whether a permutaion of the second sequence is equal\ndiff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h\nindex 9ecd0b216c1a..d6f55dc575bc 100644\n--- a/libstdc++-v3/include/bits/stl_algobase.h\n+++ b/libstdc++-v3/include/bits/stl_algobase.h\n@@ -1640,6 +1640,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO\n }\n \n #if __cplusplus >= 201103L\n+#pragma GCC diagnostic push\n+#pragma GCC diagnostic ignored \"-Wc++17-extensions\" // if constexpr\n+\n // 4-iterator version of std::equal for use in C++11.\n template\n _GLIBCXX20_CONSTEXPR\n@@ -1650,20 +1653,20 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO\n using _Cat1 = typename iterator_traits<_II1>::iterator_category;\n using _Cat2 = typename iterator_traits<_II2>::iterator_category;\n using _RAIters = __and_, is_same<_Cat2, _RATag>>;\n- if (_RAIters())\n+ if constexpr (_RAIters::value)\n \t{\n-\t auto __d1 = std::distance(__first1, __last1);\n-\t auto __d2 = std::distance(__first2, __last2);\n-\t if (__d1 != __d2)\n+\t if ((__last1 - __first1) != (__last2 - __first2))\n \t return false;\n \t return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);\n \t}\n-\n- for (; __first1 != __last1 && __first2 != __last2;\n-\t ++__first1, (void)++__first2)\n-\tif (!(*__first1 == *__first2))\n-\t return false;\n- return __first1 == __last1 && __first2 == __last2;\n+ else\n+\t{\n+\t for (; __first1 != __last1 && __first2 != __last2;\n+\t ++__first1, (void)++__first2)\n+\t if (!(*__first1 == *__first2))\n+\t return false;\n+\t return __first1 == __last1 && __first2 == __last2;\n+\t}\n }\n \n // 4-iterator version of std::equal for use in C++11.\n@@ -1677,22 +1680,23 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO\n using _Cat1 = typename iterator_traits<_II1>::iterator_category;\n using _Cat2 = typename iterator_traits<_II2>::iterator_category;\n using _RAIters = __and_, is_same<_Cat2, _RATag>>;\n- if (_RAIters())\n+ if constexpr (_RAIters::value)\n \t{\n-\t auto __d1 = std::distance(__first1, __last1);\n-\t auto __d2 = std::distance(__first2, __last2);\n-\t if (__d1 != __d2)\n+\t if ((__last1 - __first1) != (__last2 - __first2))\n \t return false;\n \t return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,\n \t\t\t\t __binary_pred);\n \t}\n-\n- for (; __first1 != __last1 && __first2 != __last2;\n-\t ++__first1, (void)++__first2)\n-\tif (!bool(__binary_pred(*__first1, *__first2)))\n-\t return false;\n- return __first1 == __last1 && __first2 == __last2;\n+ else\n+\t{\n+\t for (; __first1 != __last1 && __first2 != __last2;\n+\t ++__first1, (void)++__first2)\n+\t if (!bool(__binary_pred(*__first1, *__first2)))\n+\t return false;\n+\t return __first1 == __last1 && __first2 == __last2;\n+\t}\n }\n+#pragma GCC diagnostic pop\n #endif // C++11\n \n #ifdef __glibcxx_robust_nonmodifying_seq_ops // C++ >= 14\ndiff --git a/libstdc++-v3/testsuite/25_algorithms/equal/lwg3560.cc b/libstdc++-v3/testsuite/25_algorithms/equal/lwg3560.cc\nnew file mode 100644\nindex 000000000000..7bf8486d1b36\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/25_algorithms/equal/lwg3560.cc\n@@ -0,0 +1,49 @@\n+// { dg-do run { target c++20 } }\n+\n+// LWG 3560. ranges::equal and ranges::is_permutation should short-circuit\n+// for sized_ranges\n+\n+#include \n+#include \n+#include \n+\n+struct X\n+{\n+ // Any equality comparison will cause the test to fail.\n+ bool operator==(const X&) const { VERIFY(false); }\n+};\n+\n+void\n+test_std_equal()\n+{\n+ X vals[3];\n+ __gnu_test::random_access_container r1(vals, vals+3);\n+ __gnu_test::random_access_container r2(vals, vals+2);\n+ VERIFY( ! std::equal(r1.begin(), r1.end(), r2.begin(), r2.end()) );\n+\n+ std::ranges::equal_to pred;\n+ VERIFY( ! std::equal(r1.begin(), r1.end(), r2.begin(), r2.end(), pred) );\n+}\n+\n+void\n+test_std_ranges_equal()\n+{\n+ X vals[3];\n+ __gnu_test::test_random_access_range r1(vals, vals+3);\n+ __gnu_test::test_random_access_range r2(vals, vals+2);\n+\n+ // Any application of the projection will cause the test to fail.\n+ auto proj = [](const X&) -> const X& { VERIFY(false); };\n+ VERIFY( ! std::ranges::equal(r1.begin(), r1.end(), r2.begin(), r2.end(), {},\n+\t\t\t proj, proj) );\n+\n+ __gnu_test::test_forward_sized_range r3(vals, vals+3);\n+ __gnu_test::test_forward_sized_range r4(vals, vals+2);\n+ VERIFY( ! std::ranges::equal(r3, r4, {}, proj, proj) );\n+}\n+\n+int main()\n+{\n+ test_std_equal();\n+ test_std_ranges_equal();\n+}\ndiff --git a/libstdc++-v3/testsuite/25_algorithms/is_permutation/lwg3560.cc b/libstdc++-v3/testsuite/25_algorithms/is_permutation/lwg3560.cc\nnew file mode 100644\nindex 000000000000..f9469b08a2f5\n--- /dev/null\n+++ b/libstdc++-v3/testsuite/25_algorithms/is_permutation/lwg3560.cc\n@@ -0,0 +1,51 @@\n+// { dg-do run { target c++20 } }\n+\n+// LWG 3560. ranges::equal and ranges::is_permutation should short-circuit\n+// for sized_ranges\n+\n+#include \n+#include \n+#include \n+\n+struct X\n+{\n+ // Any equality comparison will cause the test to fail.\n+ bool operator==(const X&) const { VERIFY(false); }\n+};\n+\n+void\n+test_std_is_permutation()\n+{\n+ X vals[3];\n+ __gnu_test::random_access_container r1(vals, vals+3);\n+ __gnu_test::random_access_container r2(vals, vals+2);\n+ VERIFY( ! std::is_permutation(r1.begin(), r1.end(), r2.begin(), r2.end()) );\n+\n+ std::ranges::equal_to pred;\n+ VERIFY( ! std::is_permutation(r1.begin(), r1.end(), r2.begin(), r2.end(),\n+\t\t\t\tpred) );\n+}\n+\n+void\n+test_std_ranges_is_permutation()\n+{\n+ X vals[3];\n+ __gnu_test::test_random_access_range r1(vals, vals+3);\n+ __gnu_test::test_random_access_range r2(vals, vals+2);\n+\n+ // Any application of the projection will cause the test to fail.\n+ auto proj = [](const X&) -> const X& { VERIFY(false); };\n+ VERIFY( ! std::ranges::is_permutation(r1.begin(), r1.end(),\n+\t\t\t\t\tr2.begin(), r2.end(),\n+\t\t\t\t\t{}, proj, proj) );\n+\n+ __gnu_test::test_forward_sized_range r3(vals, vals+3);\n+ __gnu_test::test_forward_sized_range r4(vals, vals+2);\n+ VERIFY( ! std::ranges::is_permutation(r3, r4, {}, proj, proj) );\n+}\n+\n+int main()\n+{\n+ test_std_is_permutation();\n+ test_std_ranges_is_permutation();\n+}\n","prefixes":["v1","1/1"]}