• Subject: Re: weird behaviour of table.sort
• From: Henk Boom <henk@...>
• Date: Mon, 28 Jun 2010 14:53:31 -0400

```On 28 June 2010 14:11, Roberto Ierusalimschy <roberto@inf.puc-rio.br> wrote:
>> If Lua knows that my comparison function is flawed (and it most
>> obviously does), it should tell me just that, instead of pestering my
>> poor function with bogus arguments just to see what happens.
>
> Why "it most obviously does"? For Lua to know that the comparison
> function is flawed it needs extra checks in the code, so we must choose
> between performance and better error messages.

I agree that no defined behaviour should be expected when passing a
bad comparison function to table.sort, as it breaks the contract.

After hearing that table.sort attempts to detect bad comparison
functions, I got curious how. I took a look at the sort, and I wonder
if this would make the check catch the function a little earlier:

--- lua-5.1.4/src/ltablib.c	2008-02-14 11:46:58.000000000 -0500
+++ lua-5.1.4-mod/src/ltablib.c	2010-06-28 14:43:39.586617798 -0400
@@ -224,12 +224,12 @@
for (;;) {  /* invariant: a[l..i] <= P <= a[j..u] */
/* repeat ++i until a[i] >= P */
while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {
-        if (i>u) luaL_error(L, "invalid order function for sorting");
+        if (i==u) luaL_error(L, "invalid order function for sorting");
lua_pop(L, 1);  /* remove a[i] */
}
/* repeat --j until a[j] <= P */
while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {
-        if (j<l) luaL_error(L, "invalid order function for sorting");
+        if (j==l) luaL_error(L, "invalid order function for sorting");
lua_pop(L, 1);  /* remove a[j] */
}
if (j<i) {

Since the lower, upper, and pivot values are pre-sorted, if it's found
that (a[u] < pivot) or (pivot < a[l]), then is seems that there's a
problem with the comparison function.

Of course, maybe my logic's been hit by an off-by-one error and this
breaks the sort somehow :x

henk

```