An error in the logic of util.deepcompare?

[telemachus]

The current implementation of util.deepcompare has a result that is counter-intuitive (to me) in the following case:

    local foo = {4}
    local bar = {4}
    local mt = {}
    local function always_true()
        return true
    end
    mt.__eq = always_true
    setmetatable(foo, mt)

According to util.deepcompare, foo and bar are the same, but that seems wrong. (They don't both have the same metatable. bar has no metatable at all.) The problem comes in the fourth line here in util.deepcompare:

  local mt1 = debug.getmetatable(t1)
  local mt2 = debug.getmetatable(t2)
  -- would equality be determined by metatable __eq?
  if mt1 and mt1 == mt2 and mt1.__eq then
    -- then use that unless asked not to
    if not ignore_mt then return t1 == t2 end
  else -- we can skip the deep comparison below if t1 and t2 share identity
    if t1 == t2 then return true end
  end

Because the two tables do not have equal metatables, they are not compared using ==. Instead, they are handed off to the key, value checking further down. Since they both have the same single item—4—they appear the same by those sorts of checks.

This may be a judgment call, but util.deepcompare seems to me to give the wrong result. If two tables are being compared, and one has a metatable and the other doesn't, then that very fact means they are not (at a deep level) the same. underscore and cwtest would consider foo and bar different because they handle the metatable branch the following way:

    -- cwtest
    local mt = getmetatable(t1)
    if mt and mt.__eq then return t1 == t2 end

    -- underscore
    local mt = getmetatable(o1)
    if not ignore_mt and mt and mt.__eq then return o1 == o2 end

Sorry for the novel, but I wanted to see if the result was expected by you before making a PR to change anything. Thanks.

Edit: After thinking this over, I now think it's even more complicated. util.deepcompare is wrong to consider foo and bar the same table, but underscore and cwtest have a parallel problem. In their case, the problem is about order: what if the second (but not the first) table has a metatable with .__eq? Their way of handling things won't detect this, and they will wrongly call two subtly different tables the same.

So the full logic should be this:

    local mt1 = getmetatable(t1)
    local mt2 = getmetatable(t2)
    if (mt1 and mt1.__eq) or (mt2 and mt2.__eq) then
        return t1 == t2
    end

/ping @catwell and @mirven

[catwell]

As written in the source, I took the logic from Penlight.

Comparison of tables with different metatables in Lua is complicated. For instance:

local mt = function(x) return { __eq = function() return x end } end
local foo, bar = {4}, {4}

print(foo == bar, bar == foo) -- false, false

setmetatable(foo, mt(true))
print(foo == bar, bar == foo) -- true, true

setmetatable(bar, mt(false))
print(foo == bar, bar == foo) -- true, false

As you can see, when both members have an __eq metamethod, comparison is no longer symmetric. Mix that with deep comparison and it can quickly become a nightmare.

I think what Penlight is doing for deep comparison (only take the first parameter into account to check if a metatable should be used, i.e. "cast the second parameter to the type of the first one") is a good trade-off.

[telemachus]

@catwell I agree that comparison once metatables are involved gets very complicated. However, that last result really bothers me. That said, I'm not sure of the right alternative. Here's one thought. Change my last attempt above into this:

local mt1 = getmetatable(t1)
local mt2 = getmetatable(t2)
if (mt1 and mt1.__eq) or (mt2 and mt2.__eq) then
  return t1 == t2 and t2 == t1
end

I'm aksing for my parallel method in tapered. At the moment, I'm trying something much more complicated than I like, but I'm trying to catch all possible cases.

[catwell]

@telemachus Yes, that makes sense. It can be inefficient, but does it really matter in test helpers?

[telemachus]

@catwell To me that (tiny?) inefficiency is less important than a wrong result. But I can imagine cases where people would vote the other way.

[catwell]

Inefficiency is not always that tiny. Think about what happens if you are comparing trees and __eq itself is implemented with deep comparison :)

[catwell]

Regarding the luassert code: the real bug IMO is that the code does not do what the comment says. If mt1 exists and has an __eq methamethod but mt1 is not the same as mt2, the two members are compared using mt1.__eq. It can be fixed by calling rawequal() instead of ==.

[o-lim]

I agree with @catwell's last comment, util.deepcompare should be using rawequal() instead of ==.

[telemachus]

@catwell @o-lim I think that there is an important difference here between Lua 5.3 and earlier versions.

In Lua 5.2, a call to == will only use .__eq only if both mt1 and mt2 share the same .__eq function. (Reference: http://www.lua.org/manual/5.2/manual.html#2.4.)

In Lua 5.3, a call to == will only use .__eq if either mt1 or mt2 have a .__eq function. (And apparently without regard to whether these are the same methods. Calls to x == y become order dependent. See @catwell's code in [his earlier comment](a day ago).) (Reference: http://www.lua.org/manual/5.3/manual.html#2.4.)

$ ./lua-5.3.1/lua-5.3.1 catwell.lua 
false   false
true    true
true    false
$ lua-5.2 catwell.lua 
false   false
false   false
false   false
false

So perhaps luassert is relying on t1 == t2 to do the right thing (and skip .__eq) because that's the default behavior on Lua before 5.3?

[catwell]

Right. To be honest I had to check with an interpreter, and I had not realized this had changed in 5.3. I almost never overload operators in my own code.

[telemachus]

A reason given on the lua mailing list for not required equality of metatables is that it rules out (some kinds of) inheritance. I'm not sure how relevant that is to anyone's choices in this thread, but it makes sense to me as one concern that some people may have.

Reference: http://listmaster.pepperfish.net/cgi-bin/mailman/private/lua-l-lists.lua.org/2015-July/049132.html

[o-lim]

In either case, I think be using rawequal instead of == is the right thing to do here. However, in the case of using .__eq, maybe the right thing to do is to check that mt1 and mt2 share the same .__eq function, instead of checking mt1 == mt2, before using .__eq to evaluate equality? And maybe assert.is_equal should also do the same to maintain consistency between different versions of Lua?

[telemachus]

In either case, I think be using rawequal instead of == is the right thing to do here.

I agree with you about the change you've proposed as a PR.

However, in the case of using .eq, maybe the right thing to do is to check that mt1 and mt2 share the same .eq function, instead of checking mt1 == mt2, before using .__eq to evaluate equality? And maybe assert.is_equal should also do the same to maintain consistency between different versions of Lua?

I had written a version of tapered (my little testing library) that did this, but now I'm thinking of going back to the way that penlight, underscore and cwtest handle things. In other words:

if mt and mt.__eq then return t1 == t2 end

On the lua mailing list, Roberto's attitude to my worries about noncommutative __eq methods was basically, "If someone writes such methods, they get what they deserve." As a language designer, I think he wanted to change away from testing that both __eq methods are identical (in order to make a certain form of inheritance possible and avoid a certain kind of indeterminate behavior). If that's the case, I'm thinking I may just follow the language's lead.