Re: How can I deep-compare 2 Lua tables, which may or may not have tables as keys?

If you do a lot of deep copying / deep comparing you should consider if you wouldn't be better of using (pseudo*) immutable tables the first place.

I know I keep menitoning this, a naive assumption is that copying a table just to alter one key/value pair seems wasteful in many more complex systems the results often can end up in higher efficiency, since you do not have to deep copy ever.

* @pseudo: Lua doesn't natively support (deep) frozen tables. Nor can it thus natively use optimizations due to knowing a table is deeply frozen. Nevertheless even without it can pay off. You can use a metatable which forbids any write access. I don't know of an effective way to intern pseudo immutables tough.

I switched a project doing a lot of logic on a 2d euclidian plane from mutables to immutables and it saved a ton of headaches (e.g. do i have to copy that point or line if I give it that subroutine, since it might alter it?) and also deep copying of data representing 2d stuff.

On Sat, Sep 20, 2014 at 2:05 PM, Thiago L. <fakedme@gmail.com> wrote:

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".