ES2019 stable Array.sort()

[gbrail]

The greater JavaScript community got excited a while back because "all major JavaScript implementations" have implemented a stable sort for Array.sort().

Rhino, however, has its own sorting implementation in the "Sorting" class that's not stable, as it uses a hybrid quicksort / insertion sort. I realize that this is no longer the state of the art.

(Rhino cannot use the "Collections.sort()" functionality in Java because it does not handle misbehaved comparators in a way that is compatible with the JavaScript specs.)

A great project for an eager computer scientist would be to improve this sorting algorithm.

[angelinakap2]

Hello @gbrail, I have some experience in coding in JavaScript and am interested in open-source contribution for my Intro to Software Engineering class. Could I possibly be assigned to this code?

[tuchida]

@angelinakap2 Thank you for your interest.
Rhino is open source, so anyone can create a Pull Request. If you create a Pull Request for this issue, I will review it.

[gbrail]

Absolutely -- if you have the time to create a GitHub PR with a new implementation of sort (which has to be in Java due to the nature of Rhino) then we'd be happy to look at it! We're trying to increase the quality of Rhino in general, so a change in this part of the code would require a very bulletproof implementation, complete with a comprehensive test suite with (for this very critical thing) 100% test coverage. That's a great thing to aim for in any CS curriculum I think!

…

On Fri, Jan 21, 2022 at 4:44 PM tuchida ***@***.***> wrote: @angelinakap2 <https://github.com/angelinakap2> Thank you for your interest. Rhino is open source, so anyone can create a Pull Request. If you create a Pull Request for this issue, I will review it. — Reply to this email directly, view it on GitHub <#1151 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAD7I2ZHZLRNKTZJWNDJQ7LUXH4WPANCNFSM5LPME3OA> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you were mentioned.Message ID: ***@***.***>

[p-bakker]

Some links that might contain interesting/relevant info:

• [Normative] Make Array.prototype.sort stable tc39/ecma262#1340: ES2019 stable array sort
• [Normative] Make %TypedArray%.prototype.sort stable tc39/ecma262#1433: ES20219 stable Typed Array sort
• Normative: A more precise Array.prototype.sort tc39/ecma262#1585: ES2021 further refinements to the sorting algorithm
• https://mobile.twitter.com/mathias/status/1036626116654637057
• https://esdiscuss.org/topic/stable-sort-proposal

As for testing: as stable sorting was introduced in ES20219 and we're running agfainst a version of the test262 suite authored in 2020, the functional tests of the stable sorting algorithm ought to be covered by the version of the test262 suite we're running against (assuming such tests are included in the test262 suite). Any tests for the refinements to the algorithm in ES2021 wont be in the version of the test262 suite we're running against (and while we cant upgrade the version of the test262 suite we run against in our CI, you can try to locally run the tests related to the (stable) sorting algorithm from test262 master)

[DanielRosenwasser]

Hey all, I have a PR over at #1494; however, I might have jumped the gun a bit and done a quick implementation using Arrays.sort, not having read this line:

Rhino cannot use the "Collections.sort()" functionality in Java because it does not handle misbehaved comparators in a way that is compatible with the JavaScript specs

Can you give some specifics on what sort of misbehavior can occur there? Because as far as I can tell, the current implementation already performs a copy and ignores external mutations.

[DanielRosenwasser]

Also - the context is that we'd eventually like to merge in microsoft/TypeScript#55728, and while we generally expect a Node.js runtime, we don't want to break anyone building anything custom with Rhino. 😄

[gbrail]

There were a bunch of bugs in Rhino about this years ago. I believe that we addressed those in some tests that are now built in to the project, such as this one: rhino/tests/testsrc/jstests/sorting-comparators.js at master · mozilla/rhino (github.com) <https://github.com/mozilla/rhino/blob/master/tests/testsrc/jstests/sorting-comparators.js> So if your patch passes all the tests, then we SHOULD be covered on what the old problem was. (As I recall, whatever Java sorting code we used to use -- maybe it was "Collections.sort", would freak out and eventually throw an exception if the comparator didn't have consistent behavior, such as always returning the same result...)

…

On Mon, Jun 17, 2024 at 5:38 PM Daniel Rosenwasser ***@***.***> wrote: Also - the context is that we'd eventually like to merge in microsoft/TypeScript#55728 <microsoft/TypeScript#55728>, and while we generally expect a Node.js runtime, we don't want to break anyone building anything custom with Rhino. 😄 — Reply to this email directly, view it on GitHub <#1151 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAD7I25GH4WFUIMQWR3WZWDZH56QTAVCNFSM6AAAAABJO7DZU2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDCNZUGY4DSOJWG4> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[gbrail]

Here's the original issue. It's possible that Arrays.sort is a lot more flexible in more recent versions of Java:

#255

[DanielRosenwasser]

Well let me know if you feel like the current approach is fine - I'm okay with implementing a separate merge sort or something if you'd like.