summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/lapi.js11
-rw-r--r--src/lauxlib.js38
-rw-r--r--src/ldo.js2
-rw-r--r--src/loslib.js4
-rw-r--r--src/lstrlib.js2
-rw-r--r--src/ltable.js2
-rw-r--r--src/ltablib.js151
-rw-r--r--src/lua.js1
-rw-r--r--src/lutf8lib.js2
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) {
diff --git a/src/ldo.js b/src/ldo.js
index 1e9d355..c762798 100644
--- a/src/ldo.js
+++ b/src/ldo.js
@@ -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;
};
diff --git a/src/lua.js b/src/lua.js
index 09fb0e6..3954316 100644
--- a/src/lua.js
+++ b/src/lua.js
@@ -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);