[cfe-dev] [llvm-dev] RFC: Extend UBSan with qsort checks

[Sean Parent via cfe-dev]

I don't have the full thread for context.

There is no practical way to test if a given comparison function satisfies
a strict-weak ordering or not. The issue is the requirement of transitivity:

a < b && b < c => a < c

Any test would have to ensure that this holds for all triplets in the
sequence being sorted (and you would have to verify the other axioms as
well).

The reason why sort can crash if this is violated is because it establishes
a sentinel at a partition point and assumes nothing will cross the sentinel
- you can bounds check with some additional cost but the ordering is still
going to be undefined if this axiom is violated and there is no guarantee a
bounds check will catch it.

There are some tests that can be done for common failures though - for
example a common failure of sort is trying to sort a floating point
sequence with float or doubles that contains NaNs. You can test for NaNs on
such a sequence with an additional linear pass. But it doesn't help if you
have a custom comparison that is passed in, that does something like
compare the first member of a struct that is of type double.

There are many pre-conditions in STL (and most any other library interface)
that cannot easily be validated.

Sean


On Thu, Jan 14, 2016 at 10:11 PM, Marshall Clow <mclow.lists at gmail.com>
wrote:

> On Tue, Jan 12, 2016 at 10:27 PM, Yury Gribov via cfe-dev <
> cfe-dev at lists.llvm.org> wrote:
>
>>
>> As for C++11, it has for e.g. srtd::sort:
>>
>> "Requires: operator< (for the version with no arguments) or comp (for the
>> version with a comparison argument) defines a strict weak ordering (25.4)."
>>
>> which also sounds like UB.
>
>
> Exactly correct.
> If your comparison operator does not define a SWO, then you have no
> guarantees of the results. Crashes are common.
>
> In principle, I am very much in favor of a checker like this.
> Passing an invalid comparison operator is one of the most common misuses
> of std::sort.
>
> I worry about the cost, though.
>
> -- Marshall
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20160115/40a1a4a7/attachment.html>