diff options
| -rw-r--r-- | src/lapi.js | 11 | ||||
| -rw-r--r-- | src/lauxlib.js | 38 | ||||
| -rw-r--r-- | src/ldo.js | 2 | ||||
| -rw-r--r-- | src/loslib.js | 4 | ||||
| -rw-r--r-- | src/lstrlib.js | 2 | ||||
| -rw-r--r-- | src/ltable.js | 2 | ||||
| -rw-r--r-- | src/ltablib.js | 151 | ||||
| -rw-r--r-- | src/lua.js | 1 | ||||
| -rw-r--r-- | src/lutf8lib.js | 2 |
9 files changed, 140 insertions, 73 deletions
diff --git a/src/lapi.js b/src/lapi.js index 7123628..6ef5a9e 100644 --- a/src/lapi.js +++ b/src/lapi.js @@ -124,11 +124,6 @@ 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) { @@ -706,10 +701,6 @@ const lua_compare = function(L, index1, index2, op) { let o1 = index2addr(L, index1); let o2 = index2addr(L, index2); - return lua_compare_(L, o1, o2, op); -}; - -const lua_compare_ = function(L, o1, o2, op) { let i = 0; if (isvalid(o1) && isvalid(o2)) { @@ -1023,7 +1014,6 @@ 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; @@ -1075,7 +1065,6 @@ 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/lauxlib.js b/src/lauxlib.js index 0491de5..9c4b98d 100644 --- a/src/lauxlib.js +++ b/src/lauxlib.js @@ -10,9 +10,9 @@ const LUA_FILEHANDLE = lua.to_luastring("FILE*", true); class luaL_Buffer { - constructor(L) { - this.L = L; - this.b = ""; + constructor() { + this.b = null; + this.L = null; } } @@ -211,21 +211,27 @@ const luaL_fileresult = function(L, stat, fname, e) { }; /* Unlike normal lua, we pass in an error object */ -const luaL_execresult = function(L, stat, e) { - let what = lua.to_luastring("exit"); /* type of termination */ - if (e && e.status === -1) /* error? */ - return luaL_fileresult(L, 0, null, e); - else { - if (e && e.signal) { - lua.lua_pushnil(L); - lua.lua_pushliteral(L, "signal"); - } else { - lua.lua_pushboolean(L, 1); - lua.lua_pushliteral(L, "exit"); - } - lua.lua_pushinteger(L, e ? e.status : 0); +const luaL_execresult = function(L, e) { + let what, stat; + if (e === null) { + lua.lua_pushboolean(L, 1); + lua.lua_pushliteral(L, "exit"); + lua.lua_pushinteger(L, 0); return 3; + } else if (e.status) { + what = "exit"; + stat = e.status; + } else if (e.signal) { + what = "signal"; + stat = e.signal; + } else { + /* XXX: node seems to have e.errno as a string instead of a number */ + return luaL_fileresult(L, 0, null, e); } + lua.lua_pushnil(L); + lua.lua_pushliteral(L, what); + lua.lua_pushinteger(L, stat); + return 3; }; const luaL_getmetatable = function(L, n) { @@ -77,7 +77,7 @@ const luaD_precall = function(L, off, nresults) { luaD_hook(L, defs.LUA_HOOKCALL, -1); let n = f(L); /* do the actual call */ - assert(typeof n == "number" && n >= 0 && n==n|0, "invalid return value from JS function (expected integer)"); + assert(typeof n == "number" && n >= 0 && (n|0) === n, "invalid return value from JS function (expected integer)"); assert(n < L.top - L.ci.funcOff, "not enough elements in the stack"); luaD_poscall(L, ci, L.top - n, n); diff --git a/src/loslib.js b/src/loslib.js index 6fd5247..b93071b 100644 --- a/src/loslib.js +++ b/src/loslib.js @@ -247,10 +247,10 @@ if (typeof require === "function") { } ); } catch (e) { - return lauxlib.luaL_execresult(L, false, e); + return lauxlib.luaL_execresult(L, e); } - return lauxlib.luaL_execresult(L, true); + return lauxlib.luaL_execresult(L, null); } else { try { child_process.execSync( diff --git a/src/lstrlib.js b/src/lstrlib.js index 6121804..b5f235f 100644 --- a/src/lstrlib.js +++ b/src/lstrlib.js @@ -1333,7 +1333,7 @@ const str_gsub = function(L) { let anchor = p[0] === '^'.charCodeAt(0); let n = 0; /* replacement count */ let ms = new MatchState(L); - let b = new lauxlib.luaL_Buffer(L); + let b = new lauxlib.luaL_Buffer(); lauxlib.luaL_argcheck(L, tr === lua.LUA_TNUMBER || tr === lua.LUA_TSTRING || tr === lua.LUA_TFUNCTION || tr === lua.LUA_TTABLE, 3, lua.to_luastring("string/function/table expected", true)); lauxlib.luaL_buffinit(L, b); diff --git a/src/ltable.js b/src/ltable.js index 874a9f0..d6fffe9 100644 --- a/src/ltable.js +++ b/src/ltable.js @@ -79,7 +79,7 @@ const setgeneric = function(t, hash, key) { }; const luaH_setint = function(t, key, value) { - assert(typeof key == "number" && value instanceof lobject.TValue && key|0 === key); + assert(typeof key == "number" && value instanceof lobject.TValue && (key|0) === key); let hash = key; /* table_hash known result */ let v = t.strong.get(hash); if (v) { diff --git a/src/ltablib.js b/src/ltablib.js index 7d16b25..56ba2cd 100644 --- a/src/ltablib.js +++ b/src/ltablib.js @@ -1,7 +1,8 @@ "use strict"; +const assert = require('assert'); + const lua = require('./lua.js'); -const lapi = require('./lapi.js'); const lauxlib = require('./lauxlib.js'); const llimit = require('./llimit.js'); @@ -132,7 +133,7 @@ const tconcat = function(L) { let i = lauxlib.luaL_optinteger(L, 3, 1); last = lauxlib.luaL_optinteger(L, 4, last); - let b = new lauxlib.luaL_Buffer(L); + let b = new lauxlib.luaL_Buffer(); lauxlib.luaL_buffinit(L, b); for (; i < last; i++) { @@ -172,46 +173,118 @@ const unpack = function(L) { return n; }; +const l_randomizePivot = function() { + return Math.floor(Math.random()*1<<32); +}; -// TODO: Maybe do the quicksort after all -const auxsort = function(L) { - let a = []; - for (let i=1; ;i++) { - if(lua.lua_geti(L, 1, i) === lua.LUA_TNIL) { - lua.lua_pop(L, 1); - break; - } - let t = lapi.index2addr(L, -1); - a.push({ - oldkey: i, - value: t - }); - lua.lua_pop(L, 1); +const RANLIMIT = 100; + +const set2 = function(L, i, j) { + lua.lua_seti(L, 1, i); + lua.lua_seti(L, 1, j); +}; + +const sort_comp = function(L, a, b) { + if (lua.lua_isnil(L, 2)) /* no function? */ + return lua.lua_compare(L, a, b, lua.LUA_OPLT); /* a < b */ + else { /* function */ + lua.lua_pushvalue(L, 2); /* push function */ + lua.lua_pushvalue(L, a-1); /* -1 to compensate function */ + lua.lua_pushvalue(L, b-2); /* -2 to compensate function and 'a' */ + lua.lua_call(L, 2, 1); /* call function */ + let res = lua.lua_toboolean(L, -1); /* get result */ + lua.lua_pop(L, 1); /* pop result */ + return res; } +}; - let sort_function; - if (lua.lua_type(L, 2) !== lua.LUA_TFUNCTION) { /* no function? */ - sort_function = function (a, b) { - return lapi.lua_compare_(L, a.value, b.value, lua.LUA_OPLT) === 1 ? -1 : 1; /* a < b */ - }; - } else { - sort_function = function (a, b) { - lua.lua_pushvalue(L, 2); /* push function */ - lua.lua_pushtvalue(L, a.value); /* since we use Map.sort, a and b are not on the stack */ - lua.lua_pushtvalue(L, b.value); - lua.lua_call(L, 2, 1); /* call function */ - let res = lua.lua_toboolean(L, -1); /* get result */ - lua.lua_pop(L, 1); /* pop result */ - return res ? -1 : 1; - }; +const partition = function(L, lo, up) { + let i = lo; /* will be incremented before first use */ + let j = up - 1; /* will be decremented before first use */ + /* loop invariant: a[lo .. i] <= P <= a[j .. up] */ + for (;;) { + /* next loop: repeat ++i while a[i] < P */ + while (lua.lua_geti(L, 1, ++i), sort_comp(L, -1, -2)) { + if (i == up - 1) /* a[i] < P but a[up - 1] == P ?? */ + lauxlib.luaL_error(L, "invalid order function for sorting"); + lua.lua_pop(L, 1); /* remove a[i] */ + } + /* after the loop, a[i] >= P and a[lo .. i - 1] < P */ + /* next loop: repeat --j while P < a[j] */ + while (lua.lua_geti(L, 1, --j), sort_comp(L, -3, -1)) { + if (j < i) /* j < i but a[j] > P ?? */ + lauxlib.luaL_error(L, "invalid order function for sorting"); + lua.lua_pop(L, 1); /* remove a[j] */ + } + /* after the loop, a[j] <= P and a[j + 1 .. up] >= P */ + if (j < i) { /* no elements out of place? */ + /* a[lo .. i - 1] <= P <= a[j + 1 .. i .. up] */ + lua.lua_pop(L, 1); /* pop a[j] */ + /* swap pivot (a[up - 1]) with a[i] to satisfy pos-condition */ + set2(L, up - 1, i); + return i; + } + /* otherwise, swap a[i] - a[j] to restore invariant and repeat */ + set2(L, i, j); } - a.sort(sort_function) - .forEach(function(e, i) { - if (e.oldkey != i+1) { - lua.lua_pushtvalue(L, e.value); - lua.lua_seti(L, 1, i+1); - } - }); +}; + +const choosePivot = function(lo, up, rnd) { + let r4 = Math.floor((up - lo) / 4); /* range/4 */ + let p = rnd % (r4 * 2) + (lo + r4); + assert(lo + r4 <= p && p <= up - r4); + return p; +}; + +const auxsort = function(L, lo, up, rnd) { + while (lo < up) { /* loop for tail recursion */ + /* sort elements 'lo', 'p', and 'up' */ + lua.lua_geti(L, 1, lo); + lua.lua_geti(L, 1, up); + if (sort_comp(L, -1, -2)) /* a[up] < a[lo]? */ + set2(L, lo, up); /* swap a[lo] - a[up] */ + else + lua.lua_pop(L, 2); /* remove both values */ + if (up - lo == 1) /* only 2 elements? */ + return; /* already sorted */ + let p; /* Pivot index */ + if (up - lo < RANLIMIT || rnd === 0) /* small interval or no randomize? */ + p = Math.floor((lo + up)/2); /* middle element is a good pivot */ + else /* for larger intervals, it is worth a random pivot */ + p = choosePivot(lo, up, rnd); + lua.lua_geti(L, 1, p); + lua.lua_geti(L, 1, lo); + if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */ + set2(L, p, lo); /* swap a[p] - a[lo] */ + else { + lua.lua_pop(L, 1); /* remove a[lo] */ + lua.lua_geti(L, 1, up); + if (sort_comp(L, -1, -2)) /* a[up] < a[p]? */ + set2(L, p, up); /* swap a[up] - a[p] */ + else + lua.lua_pop(L, 2); + } + if (up - lo == 2) /* only 3 elements? */ + return; /* already sorted */ + lua.lua_geti(L, 1, p); /* get middle element (Pivot) */ + lua.lua_pushvalue(L, -1); /* push Pivot */ + lua.lua_geti(L, 1, up - 1); /* push a[up - 1] */ + set2(L, p, up - 1); /* swap Pivot (a[p]) with a[up - 1] */ + p = partition(L, lo, up); + let n; + /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */ + if (p - lo < up - p) { /* lower interval is smaller? */ + auxsort(L, lo, p - 1, rnd); /* call recursively for lower interval */ + n = p - lo; /* size of smaller interval */ + lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */ + } else { + auxsort(L, p + 1, up, rnd); /* call recursively for upper interval */ + n = up - p; /* size of smaller interval */ + up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ + } + if ((up - lo) / 128 > n) /* partition too imbalanced? */ + rnd = l_randomizePivot(); /* try a new randomization */ + } /* tail call auxsort(L, lo, up, rnd) */ }; const sort = function(L) { @@ -221,7 +294,7 @@ const sort = function(L) { if (!lua.lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ lauxlib.luaL_checktype(L, 2, lua.LUA_TFUNCTION); /* must be a function */ lua.lua_settop(L, 2); /* make sure there are two arguments */ - auxsort(L); + auxsort(L, 1, n, 0); } return 0; }; @@ -149,7 +149,6 @@ module.exports.lua_pushnil = lapi.lua_pushnil; module.exports.lua_pushnumber = lapi.lua_pushnumber; module.exports.lua_pushstring = lapi.lua_pushstring; module.exports.lua_pushthread = lapi.lua_pushthread; -module.exports.lua_pushtvalue = lapi.lua_pushtvalue; module.exports.lua_pushvalue = lapi.lua_pushvalue; module.exports.lua_rawequal = lapi.lua_rawequal; module.exports.lua_rawget = lapi.lua_rawget; diff --git a/src/lutf8lib.js b/src/lutf8lib.js index e78b8e8..9e0302f 100644 --- a/src/lutf8lib.js +++ b/src/lutf8lib.js @@ -96,7 +96,7 @@ const utfchar = function(L) { if (n === 1) /* optimize common case of single char */ pushutfchar(L, 1); else { - let b = new lauxlib.luaL_Buffer(L); + let b = new lauxlib.luaL_Buffer(); lauxlib.luaL_buffinit(L, b); for (let i = 1; i <= n; i++) { pushutfchar(L, i); |