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

[Hisham <h@...>]

On 22 September 2014 11:08, Hisham <h@hisham.hm> wrote:
> On 20 September 2014 09:05, 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.
>
> As others said, that depends a lot on your definition of equivalence.
> Let's take Paul's example from StackOverflow. Do you want this to
> return true?
>
> local t1 = {[{}] = {1}, [{}] = {2}}
> local t2 = {[{}] = {1}, [{}] = {2}}
> equiv(t1, t2)
>
> If you do, then each time the key in t1 is a table, you'll have to
> check its equivalence with every table key in t2 and try them one by
> one.

For the archives (and the sharp debugging eyes of lua-l), here's a
version that handles two different [{}] keys as equivalent, as
mentioned above:

function table_eq(table1, table2)
   local avoid_loops = {}
   function recurse(t1, t2)
      -- compare value types
      if type(t1) ~= type(t2) then return false end
      -- Base case: compare simple values
      if type(t1) ~= "table" then return t1 == t2 end
      -- Now, on to tables.
      -- First, let's avoid looping forever.
      if avoid_loops[t1] then return avoid_loops[t1] == t2 end
      avoid_loops[t1] = t2
      -- Copy keys from t2
      local t2keys = {}
      local t2tablekeys = {}
      for k, _ in pairs(t2) do
         if type(k) == "table" then table.insert(t2tablekeys, k) end
         t2keys[k] = true
      end
      -- Let's iterate keys from t1
      for k1, v1 in pairs(t1) do
         local v2 = t2[k1]
         if type(k1) == "table" then
            -- if key is a table, we need to find an equivalent one.
            local ok = false
            for i, tk in ipairs(t2tablekeys) do
               if table_eq(k1, tk) and recurse(v1, t2[tk]) then
                  table.remove(t2tablekeys, i)
                  t2keys[tk] = nil
                  ok = true
                  break
               end
            end
            if not ok then return false end
         else
            -- t1 has a key which t2 doesn't have, fail.
            if v2 == nil then return false end
            t2keys[k1] = nil
            if not recurse(v1, v2) then return false end
         end
      end
      -- if t2 has a key which t1 doesn't have, fail.
      if next(t2keys) then return false end
      return true
   end
   return recurse(table1, table2)
end

assert( table_eq({}, {}) )
assert( table_eq({1,2,3}, {1,2,3}) )
assert( table_eq({1,2,3, foo = "fighters"}, {["foo"] = "fighters", 1,2,3}) )
assert( table_eq({{{}}}, {{{}}}) )
assert( table_eq({[{}] = {1}, [{}] = {2}}, {[{}] = {1}, [{}] = {2}}) )
assert( table_eq({a = 1, [{}] = {}}, {[{}] = {}, a = 1}) )
assert( table_eq({a = 1, [{}] = {1}, [{}] = {2}}, {[{}] = {2}, a = 1,
[{}] = {1}}) )

assert( not table_eq({1,2,3,4}, {1,2,3}) )
assert( not table_eq({1,2,3, foo = "fighters"}, {["foo"] = "bar", 1,2,3}) )
assert( not table_eq({{{}}}, {{{{}}}}) )
assert( not table_eq({[{}] = {1}, [{}] = {2}}, {[{}] = {1}, [{}] =
{2}, [{}] = {3}}) )
assert( not table_eq({[{}] = {1}, [{}] = {2}}, {[{}] = {1}, [{}] = {3}}) )

-- Hisham