• Subject: How can I deep-compare 2 Lua tables, which may or may not have tables as keys?
• From: "Thiago L." <fakedme@...>
• Date: Sat, 20 Sep 2014 09:05:15 -0300

```Also posted on http://stackoverflow.com/q/25922437/3691554

```
So I've been writing deep-copy algorithms, and I wanna test them to see if they work the way I want them to. While I do have access to the original->copy map, I want a general-purpose deep-compare algorithm that must be able to compare table keys (tables as keys?). The #Lua channel on Freenode thinks it's impossible, I just think it's really hard.
```
```
My deep-copy algorithm(s) are avaliable here: https://gist.github.com/SoniEx2/fc5d3614614e4e3fe131 (it's not very organized, but there are 3 of them, one uses recursive calls, the other uses a todo table, and the other simulates a call stack (in a very ugly but 5.1-compatible way))
```
Recursive version:

local function deep(inp,copies)
if type(inp) ~= "table" then
return inp
end
local out = {}
copies = (type(copies) == "table") and copies or {}
```
copies[inp] = out -- use normal assignment so we use copies' metatable (if any) for key,value in next,inp do -- skip metatables by using next directly
```        -- we want a copy of the key and the value
-- if one is not available on the copies table, we have to make one
```
-- we can't do normal assignment here because metatabled copies tables might set metatables
```
```
-- out[copies[key] or deep(key,copies)]=copies[value] or deep(value,copies) rawset(out,copies[key] or deep(key,copies),copies[value] or deep(value,copies))
```      end
return out
end

Simulated stack version:

local function deep(inp,copies)
-- push
```
local stack = {{inp = inp, key = nil, value = nil, next = false, skipNext = false, out = nil}}
```      local currentResult

copies = (type(copies) == "table") and copies or {}

-- I run ZBS from stock Lua (5.1), it's not label-friendly
while true do
--::Return::

if #stack == 0 then
return currentResult
end
local entry = stack[#stack]

if not entry.next then
entry.out = {}
copies[entry.inp] = entry.out
end
--::Next::
local rep = false
local ret = false
while true do
repeat
local key,value = entry.key, entry.value
if not entry.skipNext then
key,value = next(entry.inp, entry.key)
if not key then
--goto Out
break
end
entry.key = key
end
entry.skipNext = false
entry.next = true
print(key, value)
```
if (type(key) ~= "table" or copies[key]) and (type(value) ~= "table" or copies[value]) then
```              rawset(entry.out,copies[key] or key,copies[value] or value)
entry.key,entry.value = key,value
--goto Next
rep = true
break
end
if not (type(key) ~= "table" or copies[key]) then
-- push
entry.skipNext = true
```
stack[#stack+1] = {inp = key, key = nil, value = nil, next = false, skipNext = false, out = nil}
```            elseif not (type(value) ~= "table" or copies[value]) then
-- push
entry.skipNext = true
```
stack[#stack+1] = {inp = value, key = nil, value = nil, next = false, skipNext = false, out = nil}
```            end
--goto Return
ret = true
break
until true
if not rep then break end
rep = false
end
if not ret then
--::Out::
currentResult = entry.out
-- pop
stack[#stack] = nil
end
--goto Return
end
end

"Todo table" (not sure what to call it) version:

local function deep(inp,copies)
local todo = {[inp] = {}}
copies = type(copies) == "table" and copies or {}
copies[inp] = todo[inp]

-- we can't use pairs or for here because we modify todo
while next(todo) do
local i,o = next(todo)
todo[i] = nil
for k,v in next,i do
if copies[k] ~= nil then
k = copies[k]
elseif type(k) == "table" then
local t = {}
todo[k] = t
copies[k] = t
k = t
end
if copies[v] ~= nil then
v = copies[v]
elseif type(v) == "table" then
local t = {}
todo[v] = t
copies[v] = t
v = t
end
rawset(o,k,v)
end
end
return copies[inp] -- heh :P
end

```
I found things like this which don't really handle tables as keys: http://snippets.luacode.org/snippets/Deep_Comparison_of_Two_Values_3 (Copy of snippet below)
```
function deepcompare(t1,t2,ignore_mt)
local ty1 = type(t1)
local ty2 = type(t2)
if ty1 ~= ty2 then return false end
-- non-table types can be directly compared
if ty1 ~= 'table' and ty2 ~= 'table' then return t1 == t2 end
-- as well as tables which have the metamethod __eq
local mt = getmetatable(t1)
if not ignore_mt and mt and mt.__eq then return t1 == t2 end
for k1,v1 in pairs(t1) do
local v2 = t2[k1]
if v2 == nil or not deepcompare(v1,v2) then return false end
end
for k2,v2 in pairs(t2) do
local v1 = t1[k2]
if v1 == nil or not deepcompare(v1,v2) then return false end
end
return true
end

Serializing is also not an option, as order of serialization is "random".

```

• Follow-Ups: