Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:108853
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, 4 Mar 2020 21:13:07 +0100
Message-ID: <CAH0Uv3ECFfGKfbBmCXxegJ1em3vJ-gkRzFjzqHEPX7zSDTPVyg@mail.gmail.com>
To: Larry Garfield <larry@garfieldtech.com>
Cc: php internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary="00000000000019330605a00d0db7"
Subject: Re: [PHP-DEV] Make sorting stable
From: andreas@dqxtech.net (Andreas Hennings)

--00000000000019330605a00d0db7
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Note that a comparison callback can also be broken in other ways:
- It could contain a loop, e.g. 'a' < 'b', 'b' < 'c', 'c' < 'a'.
- It could have alternating return values in subsequent calls with the same
arguments.

This kind of misbehavior cannot be easily detected.
The best we can do is make sure these kinds of comparison functions do not
cause infinite loops.

This said: Yes, stable sort out of the box would be a welcome feature.

On Wed, 4 Mar 2020 at 20:49, 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?
>
> --Larry Garfield
>
> --
> PHP Internals - PHP Runtime Development Mailing List
> To unsubscribe, visit: http://www.php.net/unsub.php
>
>

--00000000000019330605a00d0db7--