From 52c86797608f1bf927be5bab1e9b97b7d35bdf2c Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Wed, 14 Oct 2020 15:46:58 -0300 Subject: Fixed bug of keys removed from tables vs 'next' Fixed the bug that a key removed from a table might not be found again by 'next'. (This is needed to allow keys to be removed during a traversal.) This bug was introduced in commit 73ec04fc. --- lgc.c | 17 ++++++++--------- lobject.h | 18 ++++++++++-------- ltable.c | 27 +++++++++++++++++---------- testes/nextvar.lua | 32 ++++++++++++++++++++++++++++++++ 4 files changed, 67 insertions(+), 27 deletions(-) diff --git a/lgc.c b/lgc.c index 03326df3..5dba56fc 100644 --- a/lgc.c +++ b/lgc.c @@ -161,18 +161,17 @@ static void linkgclist_ (GCObject *o, GCObject **pnext, GCObject **list) { /* -** Clear keys for empty entries in tables. If entry is empty -** and its key is not marked, mark its entry as dead. This allows the -** collection of the key, but keeps its entry in the table (its removal -** could break a chain). The main feature of a dead key is that it must -** be different from any other value, to do not disturb searches. -** Other places never manipulate dead keys, because its associated empty -** value is enough to signal that the entry is logically empty. +** Clear keys for empty entries in tables. If entry is empty, mark its +** entry as dead. This allows the collection of the key, but keeps its +** entry in the table: its removal could break a chain and could break +** a table traversal. Other places never manipulate dead keys, because +** its associated empty value is enough to signal that the entry is +** logically empty. */ static void clearkey (Node *n) { lua_assert(isempty(gval(n))); - if (keyiswhite(n)) - setdeadkey(n); /* unused and unmarked key; remove it */ + if (keyiscollectable(n)) + setdeadkey(n); /* unused key; remove it */ } diff --git a/lobject.h b/lobject.h index a9d45785..1cc8e757 100644 --- a/lobject.h +++ b/lobject.h @@ -21,10 +21,12 @@ */ #define LUA_TUPVAL LUA_NUMTYPES /* upvalues */ #define LUA_TPROTO (LUA_NUMTYPES+1) /* function prototypes */ +#define LUA_TDEADKEY (LUA_NUMTYPES+2) /* removed keys in tables */ + /* -** number of all possible types (including LUA_TNONE) +** number of all possible types (including LUA_TNONE but excluding DEADKEY) */ #define LUA_TOTALTYPES (LUA_TPROTO + 2) @@ -555,7 +557,7 @@ typedef struct Proto { /* ** {================================================================== -** Closures +** Functions ** =================================================================== */ @@ -743,13 +745,13 @@ typedef struct Table { /* -** Use a "nil table" to mark dead keys in a table. Those keys serve -** to keep space for removed entries, which may still be part of -** chains. Note that the 'keytt' does not have the BIT_ISCOLLECTABLE -** set, so these values are considered not collectable and are different -** from any valid value. +** Dead keys in tables have the tag DEADKEY but keep their original +** gcvalue. This distinguishes them from regular keys but allows them to +** be found when searched in a special way. ('next' needs that to find +** keys removed from a table during a traversal.) */ -#define setdeadkey(n) (keytt(n) = LUA_TTABLE, gckey(n) = NULL) +#define setdeadkey(node) (keytt(node) = LUA_TDEADKEY) +#define keyisdead(node) (keytt(node) == LUA_TDEADKEY) /* }================================================================== */ diff --git a/ltable.c b/ltable.c index 5a0d066f..38bee1dc 100644 --- a/ltable.c +++ b/ltable.c @@ -172,11 +172,17 @@ static Node *mainpositionTV (const Table *t, const TValue *key) { ** be equal to floats. It is assumed that 'eqshrstr' is simply ** pointer equality, so that short strings are handled in the ** default case. -*/ -static int equalkey (const TValue *k1, const Node *n2) { - if (rawtt(k1) != keytt(n2)) /* not the same variants? */ +** A true 'deadok' means to accept dead keys as equal to their original +** values, which can only happen if the original key was collectable. +** All dead values are compared in the default case, by pointer +** identity. (Note that dead long strings are also compared by +** identity). +*/ +static int equalkey (const TValue *k1, const Node *n2, int deadok) { + if ((rawtt(k1) != keytt(n2)) && /* not the same variants? */ + !(deadok && keyisdead(n2) && iscollectable(k1))) return 0; /* cannot be same key */ - switch (ttypetag(k1)) { + switch (keytt(n2)) { case LUA_VNIL: case LUA_VFALSE: case LUA_VTRUE: return 1; case LUA_VNUMINT: @@ -187,7 +193,7 @@ static int equalkey (const TValue *k1, const Node *n2) { return pvalue(k1) == pvalueraw(keyval(n2)); case LUA_VLCF: return fvalue(k1) == fvalueraw(keyval(n2)); - case LUA_VLNGSTR: + case ctb(LUA_VLNGSTR): return luaS_eqlngstr(tsvalue(k1), keystrval(n2)); default: return gcvalue(k1) == gcvalueraw(keyval(n2)); @@ -251,11 +257,12 @@ static unsigned int setlimittosize (Table *t) { /* ** "Generic" get version. (Not that generic: not valid for integers, ** which may be in array part, nor for floats with integral values.) +** See explanation about 'deadok' in function 'equalkey'. */ -static const TValue *getgeneric (Table *t, const TValue *key) { +static const TValue *getgeneric (Table *t, const TValue *key, int deadok) { Node *n = mainpositionTV(t, key); for (;;) { /* check whether 'key' is somewhere in the chain */ - if (equalkey(key, n)) + if (equalkey(key, n, deadok)) return gval(n); /* that's it */ else { int nx = gnext(n); @@ -292,7 +299,7 @@ static unsigned int findindex (lua_State *L, Table *t, TValue *key, if (i - 1u < asize) /* is 'key' inside array part? */ return i; /* yes; that's the index */ else { - const TValue *n = getgeneric(t, key); + const TValue *n = getgeneric(t, key, 1); if (unlikely(isabstkey(n))) luaG_runerror(L, "invalid key to 'next'"); /* key not found */ i = cast_int(nodefromval(n) - gnode(t, 0)); /* key index in hash table */ @@ -730,7 +737,7 @@ const TValue *luaH_getstr (Table *t, TString *key) { else { /* for long strings, use generic case */ TValue ko; setsvalue(cast(lua_State *, NULL), &ko, key); - return getgeneric(t, &ko); + return getgeneric(t, &ko, 0); } } @@ -750,7 +757,7 @@ const TValue *luaH_get (Table *t, const TValue *key) { /* else... */ } /* FALLTHROUGH */ default: - return getgeneric(t, key); + return getgeneric(t, key, 0); } } diff --git a/testes/nextvar.lua b/testes/nextvar.lua index a16d557b..29cb05d5 100644 --- a/testes/nextvar.lua +++ b/testes/nextvar.lua @@ -359,6 +359,38 @@ end assert(n == 5) +do + print("testing next x GC of deleted keys") + -- bug in 5.4.1 + local co = coroutine.wrap(function (t) + for k, v in pairs(t) do + local k1 = next(t) -- all previous keys were deleted + assert(k == k1) -- current key is the first in the table + t[k] = nil + local expected = (type(k) == "table" and k[1] or + type(k) == "function" and k() or + string.sub(k, 1, 1)) + assert(expected == v) + coroutine.yield(v) + end + end) + local t = {} + t[{1}] = 1 -- add several unanchored, collectable keys + t[{2}] = 2 + t[string.rep("a", 50)] = "a" -- long string + t[string.rep("b", 50)] = "b" + t[{3}] = 3 + t[string.rep("c", 10)] = "c" -- short string + t[function () return 10 end] = 10 + local count = 7 + while co(t) do + collectgarbage("collect") -- collect dead keys + count = count - 1 + end + assert(count == 0 and next(t) == nil) -- traversed the whole table +end + + local function test (a) assert(not pcall(table.insert, a, 2, 20)); table.insert(a, 10); table.insert(a, 2, 20); -- cgit v1.2.3-55-g6feb