[Bug libstdc++/113159] New: More robust std::sort for silly comparator functions

[Bug libstdc++/113159] New: More robust std::sort for silly comparator functions

[jengelh at inai dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113159

            Bug ID: 113159
           Summary: More robust std::sort for silly comparator functions
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jengelh at inai dot de
  Target Milestone: ---

Type: enhancement
Version: 13.2.1 20231130 [revision 741743c028dc00f27b9c8b1d5211c1f602f2fddd]
(SUSE Linux) x86_64

Input:

#include <algorithm>
#include <cstdlib>
#include <vector>
int main()
{
        std::vector<int> v(256);
        sort(v.begin(), v.end(), [](int a, int b) -> bool { return rand() & 1;
});
        // alternatively, { return true; }
        //
        // -D_GLIBCXX_DEBUG can diagnose obviously-broken cases like
        // {return true;}, but won't necessarily for
        // rand()&1 at all times.
}

Observed output:

<SIGSEGV>

Expected output:

Though I recognize this is undefined behavior, I would love to see the
implementation not run into an out-of-bounds access. glibc's qsort for example
stays within the array bounds even if given a buggy comparator like that.

[Bug libstdc++/113159] More robust std::sort for silly comparator functions

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113159

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

[Bug libstdc++/113159] More robust std::sort for silly comparator functions

[xry111 at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113159

Xi Ruoyao <xry111 at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |INVALID
             Status|UNCONFIRMED                 |RESOLVED
                 CC|                            |xry111 at gcc dot gnu.org

--- Comment #1 from Xi Ruoyao <xry111 at gcc dot gnu.org> ---
Glibc qsort had been slower than std::sort.

And in upcoming Glibc-2.39 there will be a major reimplementation of qsort, now
it's unclear if it will still keep the behavior you want.  Anyway this
shouldn't be something we should rely on.

Thus I don't think this is valid.

[Bug libstdc++/113159] More robust std::sort for silly comparator functions

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113159

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2023-12-28
     Ever confirmed|0                           |1
         Resolution|INVALID                     |---
             Status|RESOLVED                    |NEW

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I disagree, it's a perfectly valid wish. But somebody needs to work on it, or
nothing will happen and it will just stay open forever.

[Bug libstdc++/113159] More robust std::sort for silly comparator functions

[amonakov at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113159

Alexander Monakov <amonakov at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amonakov at gcc dot gnu.org

--- Comment #3 from Alexander Monakov <amonakov at gcc dot gnu.org> ---
Can you outline what would merge criteria for such an enhancement look like?

If it comes at a cost of increased code complexity and runtime overhead, what
sacrifice is acceptable in the name of increased robustness?

[Bug libstdc++/113159] More robust std::sort for silly comparator functions

[jengelh at inai dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113159

Jan Engelhardt <jengelh at inai dot de> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fweimer at redhat dot com

--- Comment #4 from Jan Engelhardt <jengelh at inai dot de> ---
>And in upcoming Glibc-2.39 there will be a major reimplementation of qsort

Even so, a recent commit strongly suggests that sticking to array bounds
remains important:

commit b9390ba93676c4b1e87e218af5e7e4bb596312ac
Author: Florian Weimer <fweimer@redhat.com>
Date:   Mon Dec 4 06:35:56 2023 +0100

    stdlib: Fix array bounds protection in insertion sort phase of qsort

[Bug libstdc++/113159] More robust std::sort for silly comparator functions

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113159

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Jan Engelhardt from comment #4)
> >And in upcoming Glibc-2.39 there will be a major reimplementation of qsort
> 
> Even so, a recent commit strongly suggests that sticking to array bounds
> remains important:

So IIRC the reasoning is because of bugs in older (current as of a month ago
even) versions of LLVM which crashes on a comparison with itself. Basically
broken comparison functions are forcing workarounds really.

Note GCC uses its own sort function due which is designed to detect the
brokeness of comparison functions even; see PR 109187, PR 90282, PR 87281, PR
84345, etc.

[Bug libstdc++/113159] More robust std::sort for silly comparator functions

[fw at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113159

Florian Weimer <fw at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fw at gcc dot gnu.org

--- Comment #6 from Florian Weimer <fw at gcc dot gnu.org> ---
We'll likely revert most of the qsort changes for glibc 2.39 because the new
implementation is both slower and has a significant backwards compatibility
impact.

[Bug libstdc++/113159] More robust std::sort for silly comparator functions

[xry111 at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113159

--- Comment #7 from Xi Ruoyao <xry111 at gcc dot gnu.org> ---
Generally I hate the idea to punish innocent programs (making them slower) just
to satisfy buggy programs.  If it's due to Hyrum's rule then fine, but here
Hyrum rule does not apply.

[Bug libstdc++/113159] More robust std::sort for silly comparator functions

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=113159

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I haven't seen a proof that libstdc++'s std::sort can't be made more robust
without losing performance. Maybe cheap range checks can be done conditionally
when _GLIBCXX_ASSERTIONS is defined, or maybe they'll be cheap enough to do
unconditionally. Some work is needed to see what's feasible, but there's no
reason to just close the request as INVALID.