Fix deep compare for recursive tables

[o-lim]

This fixes comparison of recursive tables The following should now pass:

local luassert = require "luassert"
local t1 = {}
local t2 = {}
local a = {}
local b = {}
local c = {}
local d = {}
t1.k1 = a
t2.k1 = b
a.k1 = c
b.k1 = d
c.k2 = a
d.k2 = d
luassert.is_table(t1.k1.k1.k2.k1)
luassert.is_nil(t2.k1.k1.k2.k1)
luassert.are_not_same(t1, t2)

Thanks @mpeterv for pointing out the failure case. I think this should cover all cases, but do you think there are any other failure cases?

[mpeterv]

@o-lim it seems raising the threshold won't help, here is a failure case:

local luassert = require "luassert"

local cycle_root = {}
local cycle_1 = {}
local cycle_2 = {}
cycle_root.k1 = cycle_1
cycle_1.k2 = cycle_2
cycle_2.k2 = cycle_root

local mimic_root = {}
local mimic_1 = {}
local mimic_2 = {}
local mimic_3 = {}
local self_ref = {}
mimic_root.k1 = mimic_1
mimic_1.k2 = mimic_2
mimic_2.k2 = mimic_3
mimic_3.k1 = self_ref
self_ref.k2 = self_ref

luassert.is_table(cycle_root.k1.k2.k2.k1.k2.k2.k1)
luassert.is_nil(mimic_root.k1.k2.k2.k1.k2.k2.k1)
luassert.are_same(cycle_root, mimic_root)

I think caching pairs of compared tables is necessary. E.g. if cache[t1][t2] or cache[t2][t1] is true, consider t1 and t2 same, else set cache[t1] = cache[t1] or {} and cache[t1][t2] = true and continue as usual. Cleaning up the cache after iterating through keys should not be necessary, if only to save memory.

[o-lim]

@mpeterv it turns out that doesn't work either. Caching pairs of tables, like you suggested, was actually what I started out with in the beginning. So I tried going back to that, but it doesn't work for this failure case.

I think the threshold is dependent on where the recursion starts. The threshold needs to be 1 or 2 more than the number of cycles once recursion is detected for both tables. What do you think? Am I still missing a failure condition?

[o-lim]

@mpeterv can you find any fault with the latest changes?

[mpeterv]

@o-lim sorry for the delay. It is strange that caching pairs of tables does not work for you, because for me it passes this second failure case. https://github.com/mpeterv/luassert/commit/22239342c24f9ce6d48596c61965cb9d9f2e0aff

I think there is still an issue, albeit fixable, let me make a failure case...

[mpeterv]

There it is:

local luassert = require "luassert"

local c1, c2, c3, c4 = {}, {}, {}, {}
local m1, m2, m3, m4, m5, m6, m7, m8, m9 = {}, {}, {}, {}, {}, {}, {}, {}, {}
local r1, r2, r3 = {}, {}, {}

r1[1] = r3
r2[1] = r2
r3[1] = r3
c2[1] = r2
c3[1] = r2
c4[1] = r2
m2[1] = r3
m3[1] = r3
m4[1] = r3
m6[1] = r3
m7[1] = r3
m8[1] = r3

c1[2] = c2
c2[3] = c3
c3[3] = c4
c4[3] = c1

m1[2] = m2
m2[3] = m3
m3[3] = m4
m4[3] = m5
m5[2] = m6
m6[3] = m7
m7[3] = m8
m8[3] = m9
m9[2] = r1
r1[3] = r1

luassert.is_table(c1[2][3][3][3][2][3][3][3][2][3][3][3][2])
luassert.is_nil(m1[2][3][3][3][2][3][3][3][2][3][3][3][2])
luassert.are_same(c1, m1)

Chances that something like this happens are not very big, but just for the sake of correctness. The issue is that threshold counts must be reset after recursively checking nested tables, otherwise thresholds can be reset to low numbers in one recursion path and then incorrectly used in another.

[o-lim]

@mpeterv I tried your changes for caching pairs, and it stack overflows for the above failure case as well as the following simple case:

  it("Checks same() assertion to handle recursive tables", function()
    local t1 = { k1 = 1, k2 = 2 }
    local t2 = { k1 = 1, k2 = 2 }
    local t3 = { k1 = 1, k2 = 2, k3 = { k1 = 1, k2 = 2, k3 = t2 } }
    t1.k3 = t1
    t2.k3 = t2

    assert.same(t1, t2)
    assert.same(t1, t3)
    assert.same(t1, t3)
  end)

I managed to fix your last failure case by passing thresholds down the stack. This way the thresholds are never overwritten, and so are always accurate relative to the current nested table. Can you give this a try?

[o-lim]

@mpeterv any other thoughts?

[o-lim]

@mpeterv do you think this is ready for a merge? My latest changes fixes all of your failure cases. Are there any other failure cases you can think of?

[mpeterv]

@o-lim I think this is ready for a merge, thanks for your work! I can't reproduce stack overflows when using pair caching solution though, but that's a separate issue.