2

This question is similar to a previously posted question, How can I deep-compare 2 Lua tables, which may or may not have tables as keys?

The thing is, the solution there works great for simple deep-compares. It doesn't handle cyclic references properly, however. More specifically, the following:

function table_eq(table1, table2)
   local avoid_loops = {}
   local 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


local t1 = {}

t1[t1]=t1
t1.x = {[t1] = {1, 2, 3}}

local t2 = {}
local t3 = {}

t2[t3]=t2
t3[t2]=t3
t2.x = {[t3] = {1, 2, 3}}
t3.x = {[t2] = {1, 2, 3}}

print(table_eq(t1, t2))
--[[>
lua: deeptest.lua:15: stack overflow
stack traceback:
    deeptest.lua:15: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    ...
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:26: in function <deeptest.lua:3>
    (...tail calls...)
    deeptest.lua:62: in main chunk
    [C]: in ?
--]]

produces a stack overflow. And if it wasn't for the stack overflow, it'd probably produce a false positive instead (not that I can test that).

How can I handle this case? (Can it even be handled? It sounds like an unresolved problem in computer science when I think about it... but I don't know much about that)

When I say "structural equality", I mean that the following table:

local t = {}
t[{}] = 1
t["1"] = {}

is structurally different from the following table:

local t = {}
local t2 = {}
t[t2] = 1
t["1"] = t2

Whereas in "content equality" they'd be equal.

Test cases:

local t1 = {}

t1[t1]=t1
t1.x = {[t1] = {1, 2, 3}}

local t2 = {}
local t3 = {}

t2[t3]=t2
t3[t2]=t3
t2.x = {[t3] = {1, 2, 3}}
t3.x = {[t2] = {1, 2, 3}}

assert(table_eq(t1, t2) == false)
assert(table_eq(t2, t3) == true)

local t4 = {}
t4[{}] = 1
t4["1"] = {}

local t5 = {}
local t6 = {}
t5[t6] = 1
t5["1"] = t6

assert(table_eq(t4, t5) == false)
Machavity
  • 30,841
  • 27
  • 92
  • 100
SoniEx2
  • 1,864
  • 3
  • 27
  • 40
  • 3
    Could you please give your definition of equality? I can't understand what should be the correct answer for `table_eq(t2, t3)` from your example. – Egor Skriptunoff Aug 29 '16 at 17:34
  • Perhaps an option would be to shove all objects into a table, then assert that they're all shallow-equal (to eliminate false positives), then do a deep-compare? There might still be false positives with that solution, but it's easy to bolt onto the current algorithm. – SoniEx2 Aug 29 '16 at 17:46
  • @EgorSkriptunoff `table_eq(t2, t3)` should be... undefined. t2 and t3 point to different parts of the same object (i.e. they reference eachother). It's only `table_eq(t1, t2)` (i.e. `table_eq` with completely isolated tables) that matters/should be deterministic. – SoniEx2 Aug 29 '16 at 17:54
  • 2
    Still trying to understand the intended comparison… A shallow comparison would be sufficient to establish that two tables have the same key-value pairs. It seems you want some sort of structural comparison; including, perhaps that all empty tables are equivalent? – Tom Blodget Aug 29 '16 at 21:41
  • @TomBlodget No. Empty table is equivalent to empty table only if it's the same reference *within the system*. That is, given two empty tables t1 and t2, `table_eq(t1, t2)` should be true, but `table_eq({a=t1, b=t2}, {a=t2, b=t2})` should be false. – SoniEx2 Aug 29 '16 at 22:09

1 Answers1

1

The stack overflow is easy to fix in this example by changing this:

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

to: 

-- if key is a table, we need to find an equivalent one.
        local ok = false
        for i, tk in ipairs(t2tablekeys) do
           if recurse(k1, tk) and recurse(v1, t2[tk]) then

The first 2 testcases return true, but the 3rd fails because the table as key is compared content to content. If you want key's to be tested if they are the same actual table you will need to change it to:

-- if key is a table, we need to find an equivalent one.
        local ok = false
        for i, tk in ipairs(t2tablekeys) do
           if k1 == tk and recurse(v1, t2[tk]) then

But then keep in mind the 2nd test case will fail, because their you expect the table as key to be compared content to content and not actual table.

Your testcases contradict each other about what you consider "equal" so there is no real answer.

P.s.

This function ignores metadata, which could also make the comparison with the __eq metamethod. So it's still not a complete compare anyway.

Jorith
  • 11
  • 1
  • They don't contradict eachother. It's just that you're looking at only "contents" vs "instances". But what I'm looking for is in fact neither, but instead "structure". – SoniEx2 Sep 17 '16 at 15:50
  • Lua tables have no structure whatsoever, and its meant to be that way actually. So this would be impossible. You could use something to "sort" the tables and try a compare that way for structure. – Jorith Sep 18 '16 at 23:28
  • What do you mean Lua tables have no structure? They're a *set* of *key-value pairs*. They're called a data structure for a reason. – SoniEx2 Sep 18 '16 at 23:50
  • If you dont want help thats fine, dont be a smartass. You can only compare tables in 2 ways, content or adress. If you want to compare the variable names you used to create the tables, you should read up about what they are. Cause you give them diff names, but they represent the EXACT same thing. – Jorith Sep 20 '16 at 11:31
  • You can also compare structure, which is a mixture of content and address in a very specific way. Within the same table, you compare addresses, but across tables you compare contents. As I said, look here: http://sprunge.us/QFeM it shows the **structures** of some of the tables in the unit tests. – SoniEx2 Sep 20 '16 at 15:32
  • Unfortunately that example is unreadable. But as you seem to have figured out it can be done and even how, ill consider this done now. p.s. seeing as every response you got is along the lines of "what do you consider equal" and that is still not clear to me, i wish you good luck. – Jorith Sep 22 '16 at 23:48
  • I don't know how! Those examples were too simple. Yes, for simple examples I can just use that, but that's a whole pretty printer I need to include - and they were just that, examples. For huge tables, key order is undefined, so structurally equal tables could pretty print differently. – SoniEx2 Sep 23 '16 at 00:19