integer overflow in std.sort.block

[dylan-conway]

Zig Version

0.12.0-dev.1808+69195d0cd

Steps to Reproduce and Observed Behavior

repro:
block-sort-bug.zig.zip

Found in code using std.sort.block to sort a list of 1600 semver prerelease versions. To minify the repro, the order of true/false returned from lessThan is saved to an array and returned in the same order.

original code and data:
https://github.com/oven-sh/bun/blob/800fb12906c4b9e485c6d5a6611c9e470a2183f4/src/install/npm.zig#L1660
gatsby-manifest.json

Expected Behavior

Block sort should not integer overflow. sort.heap, sort.insertion, and sort.pdq do not have any problems with the original list of semver versions or the order of true/false in the minified repro.

[paperclover]

some discussion came up today about this, and it seems that our sort function doesn't always follow strict weak ordering (where if lessThan(a, b) and lessThan(b, c), then lessThan(a, c) is guaranteed). i might be misunderstanding it.

actually, i just read the doc comment on this function

NOTE: The algorithm only works when the comparison is less-than or greater-than.
(See #8289)

It seems this is related, but that issue was closed with a newly added assertion for debug mode that guards against that.

I wonder if we can add an assertion for this case, but not sure.

[dylan-conway]

With this bug fix std.sort.block no longer integer overflows 0cf405e32149f36bf85ec8fbd75020de5324d919. Like dave said, seems our lessThan function was inconsistent, potentially causing undefined behavior in wikisort