Re: bug in table.sort (lua 5.1.3)

[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: 2008年4月03日 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) {

---

• Follow-Ups:
  • Re: bug in table.sort (lua 5.1.3), Javier Guerra

• References:
  • bug in table.sort (lua 5.1.3), Tommy Pettersson

• Prev by Date: Re: LPEG code for JavaScript grammar?
• Next by Date: Re: LPEG code for JavaScript grammar?
• Previous by thread: bug in table.sort (lua 5.1.3)
• Next by thread: Re: bug in table.sort (lua 5.1.3)
• Index(es):
  • Date
  • Thread