How can I structurally deep-compare 2 lua tables which may contain cyclic references, where keys of a table may themselves be tables?

Question

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)

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