Re: Soundness of table.sort

[Roberto Ierusalimschy <roberto@...>]

> (lua-5.3.1/src/ltablib.c line 287-)
>     /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
>     i = l; j = u-1;
>     for (;;) {  /* invariant: a[l..i] <= P <= a[j..u] */
> 
> a[i] and a[u-1] will be swapped after this loop.
> If `i` is equal to `u` after this loop, `i` overruns.
> My patch revises the range check so that `i` does not overrun.
> There is an increment after the range check,
> therefore it should be i>=u-1.

Right. I guess the corresponding test with 'j' also can be more tight:

-       if (j<=l) luaL_error(L, "invalid order function for sorting");
+       if (j<i) luaL_error(L, "invalid order function for sorting");

Thanks,

-- Roberto