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

["Thiago L." <fakedme@...>]

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