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

[Yury Gribov via llvm-dev]

On 01/15/2016 11:47 AM, Sean Parent wrote:
> I don't have the full thread for context.

There you go: 
http://lists.llvm.org/pipermail/llvm-dev/2016-January/093835.html

> 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).

Right, that's why I have to intercept qsort to check transitivity.

> 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.

Ah, good to know, thanks.

> 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
>>
>>
>