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.
diff --git a/lgc.c b/lgc.c
index 03326df..5dba56f 100644
--- a/lgc.c
+++ b/lgc.c
@@ -161,18 +161,17 @@
/*
-** 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 a9d4578..1cc8e75 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 @@
/*
** {==================================================================
-** Closures
+** Functions
** ===================================================================
*/
@@ -743,13 +745,13 @@
/*
-** 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 5a0d066..38bee1d 100644
--- a/ltable.c
+++ b/ltable.c
@@ -172,11 +172,17 @@
** be equal to floats. It is assumed that 'eqshrstr' is simply
** pointer equality, so that short strings are handled in the
** default case.
+** 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) {
- if (rawtt(k1) != keytt(n2)) /* not the same variants? */
+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 @@
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 @@
/*
** "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 @@
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 @@
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 @@
/* else... */
} /* FALLTHROUGH */
default:
- return getgeneric(t, key);
+ return getgeneric(t, key, 0);
}
}
diff --git a/testes/nextvar.lua b/testes/nextvar.lua
index a16d557..29cb05d 100644
--- a/testes/nextvar.lua
+++ b/testes/nextvar.lua
@@ -359,6 +359,38 @@
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);
