Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:108849
MIME-Version: 1.0
References: <CAF+90c9EAHbYQ+2iUA9vw13wMUevjXRMajYE9TLCoqf2YXCfBw@mail.gmail.com>
 <CAESVnVq4P67UBZBJ6LUFkzcF6TqudgSrCgeipE4HOUWFPYiC0g@mail.gmail.com>
In-Reply-To: <CAESVnVq4P67UBZBJ6LUFkzcF6TqudgSrCgeipE4HOUWFPYiC0g@mail.gmail.com>
Date: Wed, 4 Mar 2020 19:11:56 +0100
Message-ID: <CAF+90c_R0i5bBD7hsMwQ1ZHSujh5g5163V0krwJmpbwXJRV2zA@mail.gmail.com>
To: Sara Golemon <pollita@php.net>
Cc: PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary="000000000000ff4c2505a00b5bc7"
Subject: Re: [PHP-DEV] Make sorting stable
From: nikita.ppv@gmail.com (Nikita Popov)

--000000000000ff4c2505a00b5bc7
Content-Type: text/plain; charset="UTF-8"

On Wed, Mar 4, 2020 at 6:17 PM Sara Golemon <pollita@php.net> wrote:

> On Wed, Mar 4, 2020 at 10:42 AM Nikita Popov <nikita.ppv@gmail.com> wrote:
>
>> The only issue I ran into is that this change has a negative impact on
>> code
>> using illegal comparison callbacks like this:
>>
>> usort($array, function($a, $b) {
>>     return $a > $b;
>> });
>>
>> Let's define what "negative impact" means in this regard.  Is it that one
> still winds up with an essentially sorted array, but hitherto "stable
> appering" output is now stable in a different way?  Or is the result
> actually just NOT sorted in a way that a reasonable user would consider
> correct (e.g. 5 sorted before "3")?
>

"Negative impact" is PR speak for "completely broken" ;) Yes, it could sort
5 before 3. The comparison function becomes completely ill-defined and you
get Garbage-In-Garbage-Out.

If we are concerned about this (I'm not sure we should be, but I've at
least seen people be interested about this peculiar behavior:
https://stackoverflow.com/questions/59908195/how-come-usort-php-works-even-when-not-returning-integers),
there's two things we can do:

1. As Tyson suggests, we can throw a warning if a boolean is returned from
the comparison callback (probably with a check to only throw it once per
sort), to make it obvious what the cause is.

2. We can fix this transparently by doing something like this internally:

$result = $compare($a, $b);
if ($result !== false) {
    return (int) $result; // Normal behavior
}

// Bad comparison function, try the reverse order as well
return -$compare($b, $a);

That is, we will recover the full three-way comparison result from the
"greater than" result, by checking for both $a > $b and $b > $a.


> If it's the former, then I'm generally disinclined to be concerned about
> the breakage.  We never made a promise about comparison equality
> resolution, so moving to making a promise about it isn't violating anything.
>
>
>
>> This kind of incorrect code will break under the proposed implementation,
>> because we will now compare by original position if the comparison
>> function
>> reports equality. Because the comparator reports equality inconsistently
>> (it says that $a == $b, but $b != $a), the sort results are also
>> inconsistent.
>>
>> I read this user-space comparator as saying that values are never equal.
> Sometimes $a > $b and $b > $a are both true, which is terrible.  But if
> they never report equality, then position sorting should never come into
> play.
>

That's not what this comparator does: The result gets interpreted as the
usual -1/0/1 three-way comparison result, so "return $a > $b" will report
true == 1 == greater-than if $a is greater than $b (this is correct!) and
will report false == 0 == equals if $a equals $b (this is also correct) or
if $a is smaller than $b (this is wrong).

This ends up working, because the sort implementation happened to never
make a distinction between 0 and -1 return value. Now it does, and thus
results in an incorrect result.

Nikita

--000000000000ff4c2505a00b5bc7--