[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Soundness of table.sort
- From: takuya hashimoto <takuya.hashimoto@...>
- Date: Wed, 4 Nov 2015 15:17:46 +0900
function comp(l, r) return l <= r end
list = {1,3,2,4}
table.sort(list, comp)
`comp` is an invalid order function for sorting,
but no error occurs, and `list` become {1,2,4,3}.
I think this is not a sound algorithm.
By introducing the patch below, an error will occur as expected.
--- lua-5.3.1/src/ltablib.c 2015-11-04 02:44:14.099666336 +0000
+++ lua-5.3.1-mod/src/ltablib.c 2015-11-04 03:55:51.602169624 +0000
@@ -289,7 +289,7 @@
for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */
/* repeat ++i until a[i] >= P */
while ((*ta->geti)(L, 1, ++i), sort_comp(L, -1, -2)) {
- if (i>=u) luaL_error(L, "invalid order function for sorting");
+ if (i>=u-1) luaL_error(L, "invalid order function for sorting");
lua_pop(L, 1); /* remove a[i] */
}
/* repeat --j until a[j] <= P */