Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:108867
MIME-Version: 1.0
References: <CAF+90c9EAHbYQ+2iUA9vw13wMUevjXRMajYE9TLCoqf2YXCfBw@mail.gmail.com>
 <CAESVnVq4P67UBZBJ6LUFkzcF6TqudgSrCgeipE4HOUWFPYiC0g@mail.gmail.com>
 <CAF+90c_R0i5bBD7hsMwQ1ZHSujh5g5163V0krwJmpbwXJRV2zA@mail.gmail.com> <e9a5e9b4-3337-acc2-d915-c7bc538d078e@gmx.de>
In-Reply-To: <e9a5e9b4-3337-acc2-d915-c7bc538d078e@gmx.de>
Date: Thu, 5 Mar 2020 13:05:26 +0100
Message-ID: <CAF+90c8OOUJcOHEKh9EF+1bRMxZJty3ngidr3-EkaZvm9n82Bw@mail.gmail.com>
To: "Christoph M. Becker" <cmbecker69@gmx.de>
Cc: Sara Golemon <pollita@php.net>, PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary="00000000000031184b05a01a5b2d"
Subject: Re: [PHP-DEV] Make sorting stable
From: nikita.ppv@gmail.com (Nikita Popov)

--00000000000031184b05a01a5b2d
Content-Type: text/plain; charset="UTF-8"

On Wed, Mar 4, 2020 at 11:12 PM Christoph M. Becker <cmbecker69@gmx.de>
wrote:

> On 04.03.2020 at 19:11, Nikita Popov wrote:
>
> > 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.
>
> Given that we have internal classes which deliberately have such
> comparison behavior (i.e. returning 0 or 1, to signal that there is no
> order defined), e.g. Closures[1], I tend to prefer raising a warning
> instead of trying to recover.
>
> [1]
> <https://github.com/php/php-src/blob/php-7.4.3/Zend/zend_closures.c#L372>
>

This is a different case. The problem with my example is that it reports
equality where none exists, which is an issue if you try to change the
ordering of equal elements. Your case (which is indeed somewhat common in
extension code) always returns "greater-than" for non-equal elements. The
end result here is that the sort will not have any defined order regardless
of how we perform it. We can't really do anything about such cases.

I expect that a proposal for userland compare and equality overloading may
want to make the "not ordered" case more explicit, in which case we could
throw a warning when such comparisons are performed as part of sorting.

Nikita

--00000000000031184b05a01a5b2d--