Re: [PATCH 0/2] Introduce gcc_qsort

[Alexander Monakov <amonakov@ispras.ru>]

On Fri, 11 May 2018, Segher Boessenkool wrote:
> > In general such address-based comparisons steps are invalid; they lack
> > anti-reflexivity. So comparators are not actually allowed to do that.
> 
> I don't know what you mean here?  Every comparator is required to be
> *reflexive*!  Subtracting two pointers to elements of the same array gives
> a perfectly fine total order as far as I see (it is the same as the
> difference between the array indices of those elements).

I meant "anti-commutativity"; sorry about the mixup. Such strategy does not
give a valid total order because the order changes while in-progress sorting
reorders elements:

suppose you have elements A and B such that A precedes B and compare A < B
via address test. At some point, the sort routine may swap A with some
unrelated element C, moving A past B. Now B < A. This is a contradiction.

> In any case, every qsort call that is converted to one with this weaker
> contract will need to be checked.  Or we can wait for bug reports ;-)

I think such comparators have a good chance of failing existing qsort_chk
validation.

Alexander