From fc79b2ae7a85af1b892a103340b9465274153c60 Mon Sep 17 00:00:00 2001 From: Benoit Giannangeli Date: Fri, 24 Feb 2017 14:01:02 +0100 Subject: table.sort Using Array.prototype.sort for now --- README.md | 9 +------ src/lapi.js | 15 ++++++++++- src/ltablib.js | 44 ++++++++++++++++++++++++++++++++ tests/ltablib.js | 78 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-- 4 files changed, 135 insertions(+), 11 deletions(-) diff --git a/README.md b/README.md index 41ae840..d0bbae9 100644 --- a/README.md +++ b/README.md @@ -205,14 +205,7 @@ - [ ] loadfile - [ ] load - [x] Coroutine - - [ ] Table - - [x] table.concat - - [x] table.insert - - [x] table.move - - [x] table.pack - - [x] table.remove - - [x] table.unpack - - [ ] table.sort + - [x] Table - [ ] Run [Lua test suite](https://github.com/lua/tests) - [ ] DOM API binding - [ ] Parse Lua diff --git a/src/lapi.js b/src/lapi.js index 488fb58..b39046b 100644 --- a/src/lapi.js +++ b/src/lapi.js @@ -119,6 +119,11 @@ const lua_pushvalue = function(L, idx) { assert(L.top <= L.ci.top, "stack overflow"); }; +const lua_pushtvalue = function(L, tvalue) { + L.stack[L.top++] = tvalue; + assert(L.top <= L.ci.top, "stack overflow"); +}; + const lua_settop = function(L, idx) { let func = L.ci.funcOff; if (idx >= 0) { @@ -539,10 +544,15 @@ const lua_topointer = function(L, idx) { }; const lua_compare = function(L, index1, index2, op) { - let i = 0; let o1 = index2addr(L, index1); let o2 = index2addr(L, index1); + return lua_compare_(L, o1, o2, op); +}; + +const lua_compare_ = function(L, o1, o2, op) { + let i = 0; + if (!o1.ttisnil() && !o2.ttisnil()) { switch (op) { case lua.LUA_OPEQ: i = lvm.luaV_equalobj(L, o1, o2); break; @@ -757,12 +767,14 @@ const lua_getextraspace = function () { }; module.exports.index2addr = index2addr; +module.exports.index2addr_ = index2addr_; module.exports.lua_absindex = lua_absindex; module.exports.lua_atpanic = lua_atpanic; module.exports.lua_call = lua_call; module.exports.lua_callk = lua_callk; module.exports.lua_checkstack = lua_checkstack; module.exports.lua_compare = lua_compare; +module.exports.lua_compare_ = lua_compare_; module.exports.lua_concat = lua_concat; module.exports.lua_copy = lua_copy; module.exports.lua_createtable = lua_createtable; @@ -800,6 +812,7 @@ module.exports.lua_pushnil = lua_pushnil; module.exports.lua_pushnumber = lua_pushnumber; module.exports.lua_pushstring = lua_pushstring; module.exports.lua_pushthread = lua_pushthread; +module.exports.lua_pushtvalue = lua_pushtvalue; module.exports.lua_pushvalue = lua_pushvalue; module.exports.lua_rawequal = lua_rawequal; module.exports.lua_rawget = lua_rawget; diff --git a/src/ltablib.js b/src/ltablib.js index 97ecd65..fa43523 100644 --- a/src/ltablib.js +++ b/src/ltablib.js @@ -180,12 +180,56 @@ const unpack = function(L) { return n; }; + +// TODO: Maybe do the quicksort after all +const auxsort = function(L) { + let t = lapi.index2addr(L, 1); + + if (lapi.lua_type(L, 2) !== CT.LUA_TFUNCTION) { /* no function? */ + [...t.value.entries()] + .sort(function (a, b) { + if (typeof a[0] !== 'number') return 1; + else if (typeof b[0] !== 'number') return -1; + return lapi.lua_compare_(L, a[1], b[1], lua.LUA_OPLT) === 1 ? -1 : 1; /* a < b */ + }) + .forEach((e, i) => typeof e[0] === 'number' ? t.value.set(i, e[1]) : true); + } else { + [...t.value.entries()] + .sort(function (a, b) { + if (typeof a[0] !== 'number') return 1; + else if (typeof b[0] !== 'number') return -1; + + lapi.lua_pushvalue(L, 2); /* push function */ + lapi.lua_pushtvalue(L, a[1]); /* since we use Map.sort, a and b are not on the stack */ + lapi.lua_pushtvalue(L, b[1]); + lapi.lua_call(L, 2, 1); /* call function */ + let res = lapi.lua_toboolean(L, -1); /* get result */ + lapi.lua_pop(L, 1); /* pop result */ + return res ? -1 : 1; + }) + .forEach((e, i) => typeof e[0] === 'number' ? t.value.set(i, e[1]) : true); + } +}; + +const sort = function(L) { + let n = aux_getn(L, 1, TAB_RW); + if (n > 1) { /* non-trivial interval? */ + lauxlib.luaL_argcheck(L, n < Number.MAX_SAFE_INTEGER, 1, "array too big"); + if (!lapi.lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ + lauxlib.luaL_checktype(L, 2, CT.LUA_TFUNCTION); /* must be a function */ + lapi.lua_settop(L, 2); /* make sure there are two arguments */ + auxsort(L); + } + return 0; +}; + const tab_funcs = { "concat": tconcat, "insert": tinsert, "move": tmove, "pack": pack, "remove": tremove, + "sort": sort, "unpack": unpack }; diff --git a/tests/ltablib.js b/tests/ltablib.js index 990b1f8..fa15d6a 100644 --- a/tests/ltablib.js +++ b/tests/ltablib.js @@ -17,6 +17,16 @@ const linit = require('../src/linit.js'); const lstate = require('../src/lstate.js'); const CT = lua.constant_types; +const inttable2array = function(t) { + let a = []; + + t.forEach(function (v, k) { + if (typeof k === 'number') + a[k] = v; + }); + + return a.map(e => e.value); +}; test('table.concat', function (t) { let luaCode = ` @@ -171,7 +181,7 @@ test('table.remove', function (t) { linit.luaL_openlibs(L); - lapi.lua_load(L, bc, "test-table.insert"); + lapi.lua_load(L, bc, "test-table.remove"); lapi.lua_call(L, 0, -1); @@ -204,7 +214,7 @@ test('table.move', function (t) { linit.luaL_openlibs(L); - lapi.lua_load(L, bc, "test-table.insert"); + lapi.lua_load(L, bc, "test-table.move"); lapi.lua_call(L, 0, -1); @@ -217,4 +227,68 @@ test('table.move', function (t) { [1, 2, 3, 4, 5, 6], "Correct element(s) on the stack" ); +}); + + +test('table.sort (<)', function (t) { + let luaCode = ` + local t = {3, 1, 5, ['just'] = 'tofuckitup', 2, 4} + table.sort(t) + return t + `, L; + + t.plan(2); + + t.doesNotThrow(function () { + + let bc = toByteCode(luaCode).dataView; + + L = lauxlib.luaL_newstate(); + + linit.luaL_openlibs(L); + + lapi.lua_load(L, bc, "test-table.sort"); + + lapi.lua_call(L, 0, -1); + + }, "JS Lua program ran without error"); + + t.deepEqual( + inttable2array(lapi.lua_topointer(L, -1)), + [1, 2, 3, 4, 5], + "Correct element(s) on the stack" + ); +}); + + +test('table.sort with cmp function', function (t) { + let luaCode = ` + local t = {3, 1, 5, ['just'] = 'tofuckitup', 2, 4} + table.sort(t, function (a, b) + return a > b + end) + return t + `, L; + + t.plan(2); + + t.doesNotThrow(function () { + + let bc = toByteCode(luaCode).dataView; + + L = lauxlib.luaL_newstate(); + + linit.luaL_openlibs(L); + + lapi.lua_load(L, bc, "test-table.sort"); + + lapi.lua_call(L, 0, -1); + + }, "JS Lua program ran without error"); + + t.deepEqual( + inttable2array(lapi.lua_topointer(L, -1)), + [5, 4, 3, 2, 1], + "Correct element(s) on the stack" + ); }); \ No newline at end of file -- cgit v1.2.3-70-g09d2