Re: bug in table.sort (lua 5.1.3)

[Tommy Pettersson <ptp@...>]

[Due to down time in a server room, starting earlier today and
continuing the entire weekend, I can only send emails, but not
receive any new ones, so apologies if this has already been
replied to.]

On Fri, Apr 04, 2008 at 11:25:25AM -0300, Roberto Ierusalimschy wrote:
> The first change is ok, but I am not sure about the second. The first
> part of the code arranges for a[l] and a[u] to act as sentinels. Because
> the pivot goes to a[u-1], it works as a sentinel too. So, i should never
> go up to u. But in the lower end the sentinel is still a[l]. So, when
> there are no elements left that are smaller than the pivot, it is ok
> for j to go down up to l (the sentinel). Of course, this stops the loop
> (because j<i), but it does not mean an error in the order function.

Well, yes and no.

The problem is the two for loops steps to the next index,
fetches the array value, and sends it to the cmp function, all
in one go. If the cmp function didn't return false we pop the
value, and we also get a chance to throw an error instead of
trying the next index. So when we check if j<=l (or even j==l)
we have already compared a[l] with P, and if we don't stop the
next turn we will compare a[l-1] with P, which is the bug. (Same
thing for i and u.)

The bug could be fixed by rewriting the for loops to do things
in another order.

Luckily we are guaranteed by code earlier in auxsort that
a[l]<=P, so when j==l a valid order function will always return
false for cmp(P,a[j]), and end the loop, i.e., no error thrown.
(Same thing for u and i.)


-- 
Tommy Pettersson <ptp@lysator.liu.se>