lua-users home
lua-l archive

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


On Thu, Sep 23, 2021 at 9:20 PM Marcus Mason <m4gicks@gmail.com> wrote:
Hi list, recently I discovered that it is not possible to yield from
within a table.sort sorting function. Is this intentional behaviour?
There doesn't seem to be a note in the manual saying this isn't
possible. You /can/ yield from c callbacks in places like xpcall.

To yield through C code, the C code must use lua_callk or lua_pcallk instead of lua_call or lua_pcall. The former two expect a continuation function, which is a C function, since yielding irreversibly destroys the C stack. The implementation of the xpcall() Lua function illustrates this [1]:

static int luaB_xpcall (lua_State *L) {
  /* snip */
  status = lua_pcallk(L, n - 2, LUA_MULTRET, 2, 2, finishpcall);
  return finishpcall(L, status, 2);
}

Since the C stack could be destroyed by a yield, everything after the function call has to be factored out into a continuation function that is either called by Lua after yielding and resuming, or called by you immediately after the call returns without a yield.

When we look at table.sort(), Lua 5.4 calls the sorting function from within sort_comp() [2], which is called from auxsort(), which calls itself recursively. Now ask yourself: if you allow a yield from the sorting function, then since that yield destroys the C stack which contains an unknown number of recursive calls to auxsort(), how do you factor everything after it into a continuation function?

The answer is: you can't, at least not without mountains of extra code, hours upon hours of work, and possibly a whole new non-recursive algorithm. And why go to all that trouble when, as Cloud Wu pointed out, it's a bad idea anyway? On top of that, a sorting function really should just be quickly comparing basic object elements and returning a boolean. A sorting function that needs to do advanced things like yielding is highly questionable to begin with.

[1]: https://www.lua.org/source/5.4/lbaselib.c.html#luaB_xpcall
[2]: https://www.lua.org/source/5.4/ltablib.c.html#sort_comp