title: How can I deep-compare 2 Lua tables, which may or may not have tables as keys?
body: <p>(Also posted on the Lua mailing list)</p>
  
  <p>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?).</p>
  
  <p>My deep-copy algorithm(s) are avaliable here: <a href="https://gist.github.com/SoniEx2/fc5d3614614e4e3fe131" rel="noreferrer">https://gist.github.com/SoniEx2/fc5d3614614e4e3fe131</a> (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))</p>
  
  <p>Recursive version:</p>
  
  <pre class="lang-lua prettyprint-override"><code>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
  </code></pre>
  
  <p><strong>Edit</strong>: I found things like this which don't really handle tables as keys: <a href="http://snippets.luacode.org/snippets/Deep_Comparison_of_Two_Values_3" rel="noreferrer">http://snippets.luacode.org/snippets/Deep_Comparison_of_Two_Values_3</a> (Copy of snippet below)</p>
  
  <pre class="lang-lua prettyprint-override"><code>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
  </code></pre>
  
  <p>Serializing is also not an option, as order of serialization is "random".</p>