invalid key to 'next'

Hi,

I guess most people around here know this error:
invalid key to 'next'

It occurs when you add or remove a key from a table while iterating on it using next (e.g. in pairs()). I'd like to know whether there exists some kind of way to prevent this error during the current loop (without using a second loop for clean up). Here is an example:

local tbl = {1,2,3,4}

for k, v in pairs(tbl) do
  print(v)
  if (v == 3) then
    tbl[k] = nil
  end
end

The error is being thrown when next() is called to get the element next to 3, the 4.

Cyclonit

In this case, you can do

table.remove(tbl, k)

but that doesn't really work if you have a table with string indices.

This solution sadly does not work because table.remove shifts all numerical indices thus causing the element right next to the deleted one to be skipped (because it gets the index of the deleted entry).

pairs uses next(tab, index), which will return the next index it finds after the one you gave it as a parameter.
If you delete the current index the next function cannot return the next index, because the current one doesn't exist anymore…:(/>

Yes I know that (I wrote it in the first post). I guess a custom next function is the best idea I have so far…

If you only want to remove one key/value from the table, you can put a break after removing it, so it won't keep looping (wich would cause the error).

I want to keep looping.

After some investigation I think I was able to find the source of the error. Imagine the table as a list of elements. Next uses an element's next-pointer to get to the next element. The issue is the following:

If I provide a table

tbl = {[1]="a", [2]="b", [3]="c"}

, the pointers look something like this: 1.next = 2, 2.next = 3.
Deleting the second entry by doing

tbl[2] = nil

will change the pointers and result in: 1.next = 3.

It appears as if the next() implementation is working on a different table, than I edit during the loop itself. On the Lua side, I successfully removed the 2. element. The LuaJ side however tries accessing tbl[2], because it did not update the pointers and is thus using 1.next = 2.

Hint: You can iterate a numerically-indexed table backwards when you want to remove entries with table.remove().

Okay I came up with a small work around function:

local a, b
function safeNext(tbl, k)

  local succ, k, v = {pcall(next, tbl, k)}
	   
  if (not succ) then
    k = a
    v = b
  end
	
  a, b = next(tbl, val[2]
	
  return select(2, unpack(val))

end

It saves the key and value after the next element and uses those, if the actual successor is being deleted.

Cyclonit, on 11 March 2013 - 09:53 AM said:

I want to keep looping.

After some investigation I think I was able to find the source of the error. Imagine the table as a list of elements. Next uses an element's next-pointer to get to the next element. The issue is the following:

If I provide a table

tbl = {[1]="a", [2]="b", [3]="c"}

, the pointers look something like this: 1.next = 2, 2.next = 3.
Deleting the second entry by doing

tbl[2] = nil

will change the pointers and result in: 1.next = 3.

It appears as if the next() implementation is working on a different table, than I edit during the loop itself. On the Lua side, I successfully removed the 2. element. The LuaJ side however tries accessing tbl[2], because it did not update the pointers and is thus using 1.next = 2.

Actually, what happens is that pairs calls next with the last key it returned, so if you delete the entry for that key from the table it won't find it when calling next.
Using your example:

tbl = {[1]="a", [2]="b", [3]="c"}

pairs initially calls next with no key, and returns the first key and its value. You check for the value and it's not the one to delete, so it keeps looping. Then pairs calls next with 1 (the first key) as the key, and return the second key and its value. You remove that entry. pairs calls next with that key, but there's no such key in the table, so it errors.

Another solution (instead of writing your own next function) would be to use a while loop like this:

local key = next(tbl) -- get the first key
while key do
  if tbl[key] == valueToDelete then -- check if it's the value to delete
    local k = key -- store the key
    key = next(tbl, key) -- get the next key first
    tbl[k] = nil -- and then delete the value
  else
    key = next(tbl, key) -- get the next key
  end
end

(Not tested, but it should work)

For the purposes specified (a sequential numeric table) Lyqyd's suggested approach is better. Of course, the table will end up non-sequential unless you use table.remove rather than just setting to nil.

If you want, you can build a sequential table of the indexes you'll want to delete, then go back and delete those indexes once you've iterated through the whole table. That feels faster to me than the above approach, but I could be wrong.

MysticT, on 11 March 2013 - 11:34 AM said:

pairs initially calls next with no key, and returns the first key and its value. You check for the value and it's not the one to delete, so it keeps looping. Then pairs calls next with 1 (the first key) as the key, and return the second key and its value. You remove that entry. pairs calls next with that key, but there's no such key in the table, so it errors.

That is what I tried to explain.

tbl = {1,2,3}
for k, v in pairs(tbl) do
  ...
end

Should execute next(tbl, k) in every iteration. If this were the case, setting tbl[2]=nil, should not break anything. {[1]=1,[3]=3} is a valid table and next({[1]=1,[3]=3},1) will return 3 as next index.


I guess I will use your solution instead of my safeNext function, because it does not need to save potentially non-used variables. Thank you so far.

You are allowed to change existing values, including setting them to nil, but not to add new ones. Are you sure you're not adding new ones?

immibis, on 11 March 2013 - 12:23 PM said:

You are allowed to change existing values, including setting them to nil, but not to add new ones. Are you sure you're not adding new ones?

I thought that too. I had this same problem some time ago and I didn't understand why it happened, when the lua manual clearly states that you can modify existing values and even delete them, but not add new ones. But it does cause an error when you try to delete values from the table.
For example, to clear a table:

for k in pairs(tbl) do
  tbl[k] = nil
end

it will error, but:

local k = next(tbl)
while k do
  tbl[k] = nil
  k = next(tbl)
end

won't, since it doesn't require the previous key.
It might be another bug in LuaJ, or maybe that's the behavior of the C version too…

codepad.org (Lua 5.1 too) does not have this error. (One of the reasons why I think the problem is in LuaJ.)