Re: Soundness of table.sort

[Peter Cawley <lua@...>]

On Thu, Nov 5, 2015 at 5:47 PM, Roberto Ierusalimschy
<roberto@inf.puc-rio.br> wrote:
> This is a quite different beast.

Oh, for sure.

> If you allow the attacker to choose the comparison function, all bets are off.

Indeed, but that isn't the attack model I had in mind. The interesting
take-away from this comparison function is that it gives you back a
table of integers, and if your sorting algorithm is deterministic and
does pivot selection in O(1) time, then said table exhibits bad
behaviour when sorted using the default comparator. Whereas
worstcase.lua synthetically constructs a worst-case input for the
particular pivot selection algorithm currently employed by table.sort,
adversary.lua organically constructs a bad-case input with no a-priori
knowledge of the pivot selection algorithm. Given the two totally
different methods of construction, I find it very pleasing that the
constructed arrays come out almost identical.