Re: [PATCH 1/5] Fix asymmetric comparison functions

[Yury Gribov <y.gribov@samsung.com>]

On 12/17/2015 03:04 PM, Yury Gribov wrote:
> On 12/17/2015 02:39 PM, Jakub Jelinek wrote:
>> On Thu, Dec 17, 2015 at 11:58:30AM +0300, Yury Gribov wrote:
>>> 2015-12-17  Yury Gribov  <tetra2005@gmail.com>
>>>
>>>     * c-family/c-common.c (resort_field_decl_cmp):
>>>     Make symmteric.
>>>     * cp/class.c (method_name_cmp): Ditto.
>>>     (resort_method_name_cmp): Ditto.
>>>     * fortran/interface.c (pair_cmp): Ditto.
>>
>> Note, c-family, cp and fortran have their own ChangeLog files, so
>> the entries without those prefixes need to go into each one and can't
>> refer to other ChangeLog through Ditto/Likewise etc.
>> Typo in symmteric.
>
> Right, thanks.
>
>> That said, is this actually really a problem?  I mean, is qsort
>> allowed to call the comparison function with the same arguments?
>> I think lots of the comparison functions just assume that
>> for int cmpfn (const void *x, const void *y) x != y.
>> And if qsort can't call the comparison function with the same argument,
>> then perhaps the caller has some knowledge your checker does not, say
>> that the entries that would compare equal by the comparison function
>> simply can't appear in the array (so the caller knows that the comparison
>> function should never return 0).
>
> Self-comparisons are certainly less dangerous than transitive ones. I
> personally not aware about libc's which can compare element to itself.

Jakub,

So it seems most people generally agree that self-comparisons (cmp(x,x) 
== 0) are useless and don't need to be checked or fixed. What about 
ensuring symmetry i.e. that cmp(x, y) == -cmp(y, x) forall x, y?  One of 
the bugs (pair_cmp in fortran/interface.c) is exactly about this.

> However
> * comparing an element to itself still a valid thing for qsort to do
> * most other comparison functions in GCC support this
>
>>> --- a/gcc/tree-vrp.c
>>> +++ b/gcc/tree-vrp.c
>>> @@ -5882,7 +5882,9 @@ compare_case_labels (const void *p1, const void
>>> *p2)
>>>     else if (idx1 == idx2)
>>>       {
>>>         /* Make sure the default label is first in a group.  */
>>> -      if (!CASE_LOW (ci1->expr))
>>> +      if (!CASE_LOW (ci1->expr) && !CASE_LOW (ci2->expr))
>>> +    return 0;
>>> +      else if (!CASE_LOW (ci1->expr))
>>>       return -1;
>>>         else if (!CASE_LOW (ci2->expr))
>>>       return 1;
>>> --
>>> 1.9.1
>>
>> Say here, we know there is at most one default label in a switch, never
>> more.  So, unless qsort is allowed to call compare_case_labels
>> with p1 == p2 (which really doesn't make sense), this case just won't
>> happen.
>
>
>