Stable sort crash

[dlangBugzillaToGithub]

john.loughran.colvin (@John-Colvin) reported this on 2023-11-02T16:32:53Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=24221

Description

Created attachment 1898
the code to trigger the crash

I know this predicate is weird and almost certainly isn't what the user wanted. I am reporting the crash & wondering if the predicate is "allowed".

predicate:

(x, y) => x.a < y.a && x.b < y.b;

data type:

Tuple!(string, "a", string, "b")[];

data length:

129

I reduced it from a longer array, but any smaller and the problem stops.

Please find code attached.

Error output:

core.exception.ArrayIndexError@/home/john/dlang/dmd-2.105.2/linux/bin64/../../src/phobos/std/algorithm/sorting.d(2755): index [18446744073709551615] is out of bounds for array of length 1
----------------
??:? onArrayIndexError [0x55b9bdd1bc26]
??:? _d_arraybounds_indexp [0x55b9bdd1bbe3]
??:? pure @safe ulong std.algorithm.sorting.TimSortImpl!(crash.main().__lambda1, immutable(char)[][][]).mergeHi!().mergeHi(immutable(char)[][][], immutable(ulong), ulong, immutable(char)[][][]) [0x55b9bdcfd051]
??:? pure @safe void std.algorithm.sorting.TimSortImpl!(crash.main().__lambda1, immutable(char)[][][]).merge!().merge(immutable(char)[][][], ulong, ref ulong, ref immutable(char)[][][]) [0x55b9bdcfbeb9]
??:? pure @safe void std.algorithm.sorting.TimSortImpl!(crash.main().__lambda1, immutable(char)[][][]).mergeAt!().mergeAt(immutable(char)[][][], std.algorithm.sorting.TimSortImpl!(crash.main().__lambda1, immutable(char)[][][]).Slice[], immutable(ulong), ref ulong, ref immutable(char)[][][]) [0x55b9bdcfbb24]
??:? pure @safe void std.algorithm.sorting.TimSortImpl!(crash.main().__lambda1, immutable(char)[][][]).sort!().sort(immutable(char)[][][], immutable(char)[][][]) [0x55b9bdcfab62]
??:? pure @safe std.range.SortedRange!(immutable(char)[][][], crash.main().__lambda1, 0).SortedRange std.algorithm.sorting.sort!(crash.main().__lambda1, 2, immutable(char)[][][]).sort(immutable(char)[][][]) [0x55b9bdcfa11e]
??:? _Dmain [0x55b9bdcf9f01]

!!!There are attachements in the bugzilla issue that have not been copied over!!!

[dlangBugzillaToGithub]

john.loughran.colvin commented on 2023-11-02T17:23:05Z

It seems that the timsort implementation is using some inverted predicates (e.g. greaterEqual), perhaps it is assuming antisymmetry of the inverse? That does not follow from antisymmetry of the original predicate, which I show below. Of course maybe it doesn't assume it, idk :shrug:

Having finished writing the following I realise it was probably a waste of time and not a great explanation, but I'll leave it here in case it's useful:

assuming `<` on the underlying types in antisymmetric (if, for any x != y, f(x, y) is true, then f(y, x) will be false), then any && combination will also be.
 
f = (x, y) => x.a < y.a && x.b < y.b

the only way f(y, x) and f(x, y) could be true - breaking antisymmetry - would be if both x.a < y.a && y.a < x.a && x.b < y.b && y.b < x.b, which we have already assumed is not the case ("assuming `<` on the underlying types in antisymmetric").

BUT, quoting phobos:

bool greaterEqual()(auto ref T a, auto ref T b) { return !less(a, b); }

so this is

(x, y) => !(x.a < y.a && x.b < y.b)

which can be rewritten as

!(x.a < y.a) || !(x.b < y.b)

and we can see that both q(x, y) and q(y, x) CAN be true, expanded it is

(!(x.a < y.a) || !(x.b < y.b)) && (!(y.a < x.a) || !(y.b < x.b))

which can be satisfied if only one || clause is true in each side of the &&, so we can choose a clause only impacting .a for one of them and .b for the other, avoiding contradicting the reflexivity of `<` for the underlying type.