Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:129002
Precedence: list
MIME-Version: 1.0
References: <CAE1541uqb8qZa967UJNBXO2OkmM9VDbCJhZ+ruy=EyBP8+FfCQ@mail.gmail.com>
In-Reply-To: <CAE1541uqb8qZa967UJNBXO2OkmM9VDbCJhZ+ruy=EyBP8+FfCQ@mail.gmail.com>
Date: Wed, 29 Oct 2025 15:03:49 -0700
Message-ID: <CAE1541sJ7kQdhn==KSwQ0rPOCbTd+Y+tjMVoVFiDRT+2VmHPEA@mail.gmail.com>
Subject: [PHP-DEV] Re: Review request: Enabling `transitive_compare_mode` to fix SORT_REGULAR
To: PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary="000000000000563ff80642534f03"
From: jmarble@intuitivetechnology.com (Jason Marble)

--000000000000563ff80642534f03
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Quick update: The variation11 tests I mentioned are now passing after
fixing:

1. Empty string ordering - now sorts before numbers to match '' < 5
2. Windows ZTS - initialization in init_executor()

All CI tests pass. PR ready for review:
https://github.com/php/php-src/pull/20315

- Jason

On Wed, Oct 29, 2025 at 9:56=E2=80=AFAM Jason Marble <
jmarble@intuitivetechnology.com> wrote:

> Hello PHP Internals!
>
> I believe I've found an acceptable solution to the issue that's plagued
> SORT_REGULAR since the dawn of time.
>
> Fundamentally, all sorting algorithms require transitive comparisons (if =
A
> =E2=89=A4 B and B =E2=89=A4 C, then A =E2=89=A4 C). However, PHP's SORT_R=
EGULAR comparison function
> violates transitivity when mixing numeric strings, non-numeric strings, a=
nd
> numbers, leading to unpredictable and non-deterministic sort results.
>
> **The Solution:**
> Add a `transitive_compare_mode` flag to executor_globals (TLS) that
> signals zendi_smart_strcmp() to enforce consistent ordering during
> SORT_REGULAR operations:
> - Numeric strings are consistently ordered relative to non-numeric string=
s
> - Eliminates circular comparisons
> - Maintains PHP 8+ semantics (numeric-types < numeric-strings <
> non-numeric)
>
> **Implementation:**
> - PR: https://github.com/php/php-src/pull/20315
> - Uses save/restore pattern for reentrancy safety
> - New test coverage included
>
> **Historical Context:**
> Raghubansh Kumar documented this issue in 2007, creating tests with the
> note "(OK to fail as result is unpredectable)". Nikita Popov's 2019 RFC
> improved string-to-number comparison semantics but didn't eliminate the
> transitivity violation. This fix completes that work.
>
> **Test Results:**
> Four variation11 tests currently fail as expected, but their outputs are
> now deterministic and more "sane" than both the 2007 and 2019 versions im=
o:
> https://gist.github.com/jmarble/957a096cb2bf25b577de47449305723f
>
> **ABI Considerations:**
> This adds a field to _zend_executor_globals, which is technically an ABI
> break appropriate for PHP 8.6. However, practical impact is minimal, I
> think, since most extensions access executor_globals through the EG() mac=
ro
> (which abstracts the struct layout),
> not via direct struct manipulation.
>
> I'd appreciate review and feedback on this approach. This is a
> long-standing correctness issue.
>
> Thank you for your time and consideration!
>
> - Jason
>

--000000000000563ff80642534f03
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Quick update: The variation11 tests I mentioned are now pa=
ssing after fixing:<br><br>1. Empty string ordering - now sorts before numb=
ers to match &#39;&#39; &lt; 5<br>2. Windows ZTS - initialization in init_e=
xecutor()<br><br>All CI tests pass. PR ready for review: <a href=3D"https:/=
/github.com/php/php-src/pull/20315">https://github.com/php/php-src/pull/203=
15</a><br><br>- Jason</div><br><div class=3D"gmail_quote gmail_quote_contai=
ner"><div dir=3D"ltr" class=3D"gmail_attr">On Wed, Oct 29, 2025 at 9:56=E2=
=80=AFAM Jason Marble &lt;<a href=3D"mailto:jmarble@intuitivetechnology.com=
">jmarble@intuitivetechnology.com</a>&gt; wrote:<br></div><blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div>Hello PHP Internals!=
</div><div><br></div><div>I believe I&#39;ve found an acceptable solution t=
o the issue that&#39;s plagued SORT_REGULAR since the dawn of time.</div><d=
iv><br></div><div>Fundamentally, all sorting algorithms require transitive =
comparisons (if A =E2=89=A4 B and B =E2=89=A4 C, then A =E2=89=A4 C). Howev=
er, PHP&#39;s SORT_REGULAR comparison function violates transitivity when m=
ixing numeric strings, non-numeric strings, and numbers, leading to unpredi=
ctable and non-deterministic sort results.</div><div><br></div><div>**The S=
olution:**<br>Add a `transitive_compare_mode` flag to executor_globals (TLS=
) that signals zendi_smart_strcmp() to enforce consistent ordering during S=
ORT_REGULAR operations:<br>- Numeric strings are consistently ordered relat=
ive to non-numeric strings<br>- Eliminates circular comparisons<br>- Mainta=
ins PHP 8+ semantics (numeric-types &lt; numeric-strings &lt; non-numeric)<=
/div><div><br></div><div>**Implementation:**<br>- PR: <a href=3D"https://gi=
thub.com/php/php-src/pull/20315" target=3D"_blank">https://github.com/php/p=
hp-src/pull/20315</a><br>- Uses save/restore pattern for reentrancy safety<=
br>- New test coverage included</div><div><br></div><div>**Historical Conte=
xt:**<br>Raghubansh Kumar documented this issue in 2007, creating tests wit=
h the note &quot;(OK to fail as result is unpredectable)&quot;. Nikita Popo=
v&#39;s 2019 RFC improved string-to-number comparison semantics but didn=
9;t eliminate the transitivity violation. This fix completes that work.</di=
v><div><br></div><div>**Test Results:**<br>Four variation11 tests currently=
 fail as expected, but their outputs are now deterministic and more &quot;s=
ane&quot; than both the 2007 and 2019 versions imo:<br><a href=3D"https://g=
ist.github.com/jmarble/957a096cb2bf25b577de47449305723f" target=3D"_blank">=
https://gist.github.com/jmarble/957a096cb2bf25b577de47449305723f</a></div><=
div><br></div><div>**ABI Considerations:**<br>This adds a field to _zend_ex=
ecutor_globals, which is technically an ABI break appropriate for PHP 8.6. =
However, practical impact is minimal, I think, since most extensions access=
 executor_globals through the EG() macro (which abstracts the struct layout=
),<br>not via direct struct manipulation.</div><div><br></div><div>I&#39;d =
appreciate review and feedback on this approach. This is a long-standing co=
rrectness issue.<br><br>Thank you for your time and consideration!<br></div=
><div><br></div><div>- Jason</div><div dir=3D"ltr" class=3D"gmail_signature=
"><div dir=3D"ltr"><div></div></div></div></div>
</blockquote></div>

--000000000000563ff80642534f03--