[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

• Subject: Re: bug in table.sort (lua 5.1.3)
• From: Daniel Stephens <daniel@...>
• Date: Thu, 03 Apr 2008 17:37:55 -0700

Actually, the problem is that your sort function is invalid, it doesn't follow the correct contract:
```
```
"Sorts table elements in a given order, /in-place/, from |table[1]| to |table[n]|, where |n| is the length of the table. If |comp| is given, then it must be a function that receives two table elements, and returns true when the first is less than the second (so that |not comp(a[i+1],a[i])| will be true after the sort). If |comp| is not given, then the standard Lua operator |<| is used instead."
```
func(a,b) implies not func(b, a);

```
With your function, for any pair of entries X and Y with the same value, you're saying X should come before Y AND that Y should come before X.
```
Change == to < in your function, and your problem will go away.

Daniel.

Tommy Pettersson wrote:
```
```Hi,

I'm not a list subscriber. Well, I am now, but I don't think
I'll have time to read it.

I just wanted to submit a bug fix. It is very minor, and only
concerns the error reporting from Lua. But it sent me on a long
bug hunt that could have been much shorter.

Here's how to reproduce the bug:

local t = { 1 }
table.sort( { t, t, t, t }, function (a,b) return a[1] == b[1] end )

gives:

lua: stdin:2: attempt to index local 'a' (a nil value)

but should give:

lua: stdin:2: invalid order function for sorting

It's auxsort that calls lua_rawgeti with an "out of bound" index
and thus passes a nil value to the comparison function.

The fix:

diff -rN -u old-lua-5.1.3/src/ltablib.c new-lua-5.1.3/src/ltablib.c
--- old-lua-5.1.3/src/ltablib.c	2008-04-04 00:51:38.375673575 +0200
+++ new-lua-5.1.3/src/ltablib.c	2008-04-04 00:51:38.407673452 +0200
@@ -216,12 +216,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) {

```
```

```