Refactor table implementation

1 files changed, 137 insertions, 54 deletions

diff --git a/src/ltable.js b/src/ltable.js
index 432a91d..0d711b4 100644
--- a/src/ltable.js
+++ b/src/ltable.js
@@ -1,84 +1,167 @@
 /*jshint esversion: 6 */
 "use strict";
 
+const assert = require('assert');
+
 const defs    = require('./defs.js');
+const ldebug  = require('./ldebug.js');
 const lobject = require('./lobject.js');
 const CT      = defs.constant_types;
 
-
-const ordered_intindexes = function(table) {
-    return [...table.value.keys()]
-        .filter(e => typeof e === 'number' && e % 1 === 0 && e > 0)  // Only integer indexes
-        .sort(function (a, b) {
-            return a > b ? 1 : -1;
-        });
+/* converts strings (arrays) to a consistent map key */
+const hashstr = function(str) {
+    return str.map(e => `${e}|`).join('');
 };
 
-const ordered_indexes = function(table) {
-    return [...table.value.keys()]
-        .sort(function(a, b) {
-            if (typeof a !== "number" || a <= 0) return 1;
-            if (typeof b !== "number" || b <= 0) return -1;
-            return a > b ? 1 : -1;
-        });
+const table_hash = function(key) {
+    switch(key.type) {
+    case CT.LUA_TBOOLEAN:
+    case CT.LUA_TLIGHTUSERDATA: /* XXX: if user pushes conflicting lightuserdata then the table will do odd things */
+    case CT.LUA_TNUMFLT:
+    case CT.LUA_TNUMINT:
+    case CT.LUA_TTABLE:
+    case CT.LUA_TLCL:
+    case CT.LUA_TLCF:
+    case CT.LUA_TCCL:
+    case CT.LUA_TUSERDATA:
+    case CT.LUA_TTHREAD:
+        return key.value;
+    case CT.LUA_TSHRSTR:
+    case CT.LUA_TLNGSTR:
+        return hashstr(key.value);
+    default:
+        throw new Error("unknown key type: " + key.type);
+    }
 };
 
 const luaH_new = function(L) {
-    let t = new Map();
+    let t = {
+        strong: new Map(),
+        metatable: null
+    };
     return t;
 };
 
-/*
-** Try to find a boundary in table 't'. A 'boundary' is an integer index
-** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
-*/
-const luaH_getn = function(table) {
-    let indexes = ordered_intindexes(table);
-    let len = indexes.length;
+const getgeneric = function(t, hash) {
+    let v = t.strong.get(hash);
+    return v ? v.value : lobject.luaO_nilobject;
+};
 
-    // If first index != 1, length is 0
-    if (indexes[0] !== 1) return 0;
+const luaH_getint = function(t, key) {
+    assert(typeof key == "number");
+    return getgeneric(t, key);
+};
 
-    for (let i = 0; i < len; i++) {
-        let key = indexes[i];
+const luaH_getstr = function(t, key) {
+    assert(Array.isArray(key));
+    return getgeneric(t, hashstr(key));
+};
 
-        if (!lobject.table_index(table, key).ttisnil() // t[key] is non-nil
-            && (indexes[i + 1] - key > 1 || lobject.table_index(table, indexes[i + 1]).ttisnil())) { // gap with next key or next value is nil
-            return indexes[i];
-        }
-    }
+const luaH_get = function(t, key) {
+    assert(key instanceof lobject.TValue);
+    if (key.ttisnil())
+        return lobject.luaO_nilobject;
+    return getgeneric(t, table_hash(key));
+};
 
-    return 0;
+const setgeneric = function(t, hash, key) {
+    let v = t.strong.get(hash);
+    if (v)
+        return v.value;
+
+    let tv = new lobject.TValue(CT.LUA_TNIL, null);
+    t.strong.set(hash, {
+        key: key,
+        value: tv
+    });
+    return tv;
 };
 
-const luaH_next = function(L, table, keyI) {
-    let keyO = L.stack[keyI];
-    let key = lobject.table_keyValue(keyO);
-    let indexes = ordered_indexes(table);
+const luaH_setint = function(t, key, value) {
+    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) {
+        let tv = v.value;
+        tv.setfrom(value);
+    } else {
+        t.strong.set(hash, {
+            key: new lobject.TValue(CT.LUA_TNUMINT, key),
+            value: new lobject.TValue(value.type, value.value)
+        });
+    }
+};
 
-    if (indexes.length === 0) return 0;
+const luaH_set = function(t, key) {
+    assert(key instanceof lobject.TValue);
+    let hash = table_hash(key);
+    return setgeneric(t, hash, new lobject.TValue(key.type, key.value));
+};
 
-    let i = indexes.indexOf(key);
+const luaH_delete = function(t, key) {
+    assert(key instanceof lobject.TValue);
+    let hash = table_hash(key);
+    t.strong.delete(hash);
+};
 
-    if ((i >= 0 || key === null) && i < indexes.length - 1) {
-        if (key === null) i = -1;
-        let nidx = indexes[i+1];
-        let tnidx = typeof nidx;
+/*
+** Try to find a boundary in table 't'. A 'boundary' is an integer index
+** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
+*/
+const luaH_getn = function(t) {
+    let i = 0;
+    let j = t.strong.size + 1; /* use known size of Map to bound search */
+    /* now do a binary search between them */
+    while (j - i > 1) {
+        let m = Math.floor((i+j)/2);
+        if (luaH_getint(t, m).ttisnil()) j = m;
+        else i = m;
+    }
+    return i;
+};
 
-        if (tnidx === 'number' && nidx % 1 === 0)
-            L.stack[keyI] = new lobject.TValue(CT.LUA_TNUMINT, indexes[i + 1]);
-        else if (tnidx === 'string')
-            L.stack[keyI] = new lobject.TValue(CT.LUA_TLNGSTR, indexes[i + 1].split('|').map(e => Number.parseInt(e)).slice(0, -1));
-        else
-            L.stack[keyI] = indexes[i + 1];
+/*
+** Javascript tables don't have any next-like primitive.
+** For each call of `next` this does a full iteration up to the item
+*/
+const luaH_next = function(L, table, keyI) {
+    let keyO = L.stack[keyI];
 
-        L.stack[keyI + 1] = table.value.get(indexes[i + 1]);
-        return 1;
+    let iterresult;
+    if (keyO.type === CT.LUA_TNIL) {
+        iterresult = table.strong.keys().next();
+    } else {
+        let hash = table_hash(keyO);
+
+        if (!table.strong.has(hash))
+            /* item not in table */
+            return ldebug.luaG_runerror(L, "invalid key to 'next'");
+
+        let indexes = table.strong.keys();
+        while (1) {
+            let e = indexes.next();
+            if (e.done)
+                throw "unreachable";
+            else if (e.value == hash)
+                break;
+        }
+        iterresult = indexes.next();
     }
+    if (iterresult.done)
+        return false;
 
-    return 0;
+    let entry = table.strong.get(iterresult.value);
+    L.stack[keyI] = new lobject.TValue(entry.key.type, entry.key.value);
+    L.stack[keyI+1] = new lobject.TValue(entry.value.type, entry.value.value);
+    return true;
 };
 
-module.exports.luaH_new = luaH_new;
-module.exports.luaH_next = luaH_next;
-module.exports.luaH_getn = luaH_getn;
+module.exports.luaH_delete  = luaH_delete;
+module.exports.luaH_get     = luaH_get;
+module.exports.luaH_getint  = luaH_getint;
+module.exports.luaH_getn    = luaH_getn;
+module.exports.luaH_getstr  = luaH_getstr;
+module.exports.luaH_set     = luaH_set;
+module.exports.luaH_setint  = luaH_setint;
+module.exports.luaH_new     = luaH_new;
+module.exports.luaH_next    = luaH_next;