Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:108976
MIME-Version: 1.0
References: <CAF+90c9EAHbYQ+2iUA9vw13wMUevjXRMajYE9TLCoqf2YXCfBw@mail.gmail.com>
 <CAESVnVq4P67UBZBJ6LUFkzcF6TqudgSrCgeipE4HOUWFPYiC0g@mail.gmail.com>
 <CAF+90c_R0i5bBD7hsMwQ1ZHSujh5g5163V0krwJmpbwXJRV2zA@mail.gmail.com>
 <CAESVnVrsAbAgVBg80pCgt0S_exPMSg0HF22sQ2Of6xpDksaOKQ@mail.gmail.com> <9a590afe-8674-4d5c-b18f-2bc15786348c@www.fastmail.com>
In-Reply-To: <9a590afe-8674-4d5c-b18f-2bc15786348c@www.fastmail.com>
Date: Wed, 11 Mar 2020 12:41:46 +0100
Message-ID: <CAF+90c8A3i=-y73FrMki__F9eHPgqirEGq6U=tyLm1ic8wk+5g@mail.gmail.com>
To: Larry Garfield <larry@garfieldtech.com>
Cc: php internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary="000000000000a4602305a092b922"
Subject: Re: [PHP-DEV] Make sorting stable
From: nikita.ppv@gmail.com (Nikita Popov)

--000000000000a4602305a092b922
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Wed, Mar 4, 2020 at 8:49 PM Larry Garfield <larry@garfieldtech.com>
wrote:

> On Wed, Mar 4, 2020, at 12:35 PM, Sara Golemon wrote:
> > On Wed, Mar 4, 2020 at 12:12 PM Nikita Popov <nikita.ppv@gmail.com>
> wrote:
> >
> > > 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 th=
at
> > >> 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 coul=
d
> > > sort 5 before 3. The comparison function becomes completely
> ill-defined and
> > > you get Garbage-In-Garbage-Out.
> > >
> > > Roger that, thanks for explaining. =F0=9F=91=8D
> >
> >
> > > If we are concerned about this (I'm not sure we should be, but I've a=
t
> > > least seen people be interested about this peculiar behavior:
> > >
> https://stackoverflow.com/questions/59908195/how-come-usort-php-works-eve=
n-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 =3D $compare($a, $b);
> > > if ($result !=3D=3D false) {
> > >     return (int) $result; // Normal behavior
> > > }
> > >
> > > // Bad comparison function, try the reverse order as well
> > > return -$compare($b, $a);
> > >
> > >
> > =C2=BFPor que no los dos?
> >
> > Fixing broken stuff transparently for a smooth upgrade path PLUS lettin=
g
> > people know they're doing it wrong seems win-win and low cost.
> >
> > -Sara
>
>
> I concur.  If a comparison function returns a non-legal value:
>
> 1) Fold it to a legal value. if feasible.
> 2) Raise a notice/warning, maybe deprecated? that tells them they're Doin=
g
> It Wrong(tm)
> 3) Sometime in the future turn that notice/warning into a hard error.
>
> If I'm understanding the definition of stable here, it means that if two
> values evaluate to equal they will always end up in the same order in the
> output that they were in the input, yes?  So (trivial example):
>
> $a =3D ["3", 2, 3, 5];
>
> Sorts to:
>
> [2, "3", 3, 5];
>
> always, whereas right now it may sort to that or to [2, 3, "3", 5],
> somewhat randomly.  Am I understanding correctly?
>

That's right. Of course, this is not a particular useful case :) Typically,
stable sorting is useful if you are sorting only by some "part" of the
value. The most common case is sorting objects by one field:

usort($users, function($user1, $user2) {
    return $user1->age <=3D> $user2->age;
});

With stable sorting, this will sort users by age, but otherwise leave the
order of the objects alone. For example, if $users was originally sorted by
ID, then the objects will now be sorted by age first and ID second. With
unstable sorting, the order within one age bracket would be undefined.

Another example is asort(), which sorts by value but preserves keys.

$array =3D [
    'foo' =3D> 1,
    'bar' =3D> 1,
    'oof' =3D> 0,
    'rab' =3D> 0,
];
asort($array);

With stable sorting, this will always result in

$array =3D [
    'oof' =3D> 0,
    'rab' =3D> 0,
    'foo' =3D> 1,
    'bar' =3D> 1,
];

while with unstable sorting, the order of keys for a given value is
undefined.

Because stable sorting is the more useful default choice, most high-level
languages nowadays default to stable sorting (Java and Python have been
stable for a long time, JavaScript mandates stability since recently --
Ruby is a counter-example that uses unstable sorting.)  Low-level languages
tend to expose both stable and unstable sorts.

Regards,
Nikita

--000000000000a4602305a092b922--