Fast table deep compare algorithm (Lua)

fast_deep_compare.lua

local function deep_compare(tbl1, tbl2)
	if tbl1 == tbl2 then
		return true
	elseif type(tbl1) == "table" and type(tbl2) == "table" then
		for key1, value1 in pairs(tbl1) do
			local value2 = tbl2[key1]

			if value2 == nil then
				-- avoid the type call for missing keys in tbl2 by directly comparing with nil
				return false
			elseif value1 ~= value2 then
				if type(value1) == "table" and type(value2) == "table" then
					if not deep_compare(value1, value2) then
						return false
					end
				else
					return false
				end
			end
		end

		-- check for missing keys in tbl1
		for key2, _ in pairs(tbl2) do
			if tbl1[key2] == nil then
				return false
			end
		end

		return true
	end

	return false
end

LICENSE

MIT License

Copyright (c) 2022 sapphyrus

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

Refer to https://stackoverflow.com/a/32660766/2336707 that can deeply compare any two values.

--- deeply compare two objects
local function deep_equals(o1, o2, ignore_mt)
    -- same object
    if o1 == o2 then return true end

    local o1Type = type(o1)
    local o2Type = type(o2)
    --- different type
    if o1Type ~= o2Type then return false end
    --- same type but not table, already compared above
    if o1Type ~= 'table' then return false end

    -- use metatable method
    if not ignore_mt then
        local mt1 = getmetatable(o1)
        if mt1 and mt1.__eq then
            --compare using built in method
            return o1 == o2
        end
    end

    -- iterate over o1
    for key1, value1 in pairs(o1) do
        local value2 = o2[key1]
        if value2 == nil or equals(value1, value2, ignore_mt) == false then
            return false
        end
    end

    --- check keys in o2 but missing from o1
    for key2, _ in pairs(o2) do
        if o1[key2] == nil then return false end
    end
    return true
end

Refer to https://stackoverflow.com/a/32660766/2336707 that can deeply compare any two values.

--- deeply compare two objects
local function deep_equals(o1, o2, ignore_mt)
    -- same object
    if o1 == o2 then return true end

    local o1Type = type(o1)
    local o2Type = type(o2)
    --- different type
    if o1Type ~= o2Type then return false end
    --- same type but not table, already compared above
    if o1Type ~= 'table' then return false end

    -- use metatable method
    if not ignore_mt then
        local mt1 = getmetatable(o1)
        if mt1 and mt1.__eq then
            --compare using built in method
            return o1 == o2
        end
    end

    -- iterate over o1
    for key1, value1 in pairs(o1) do
        local value2 = o2[key1]
        if value2 == nil or equals(value1, value2, ignore_mt) == false then
            return false
        end
    end

    --- check keys in o2 but missing from o1
    for key2, _ in pairs(o2) do
        if o1[key2] == nil then return false end
    end
    return true
end

Hi! Thank you for sharing this, but it doesn't work because there is a typo in it that should be "deep_equals" instead of "equals".

Correct version:

--- deeply compare two objects
local function deep_equals(o1, o2, ignore_mt)
    -- same object
    if o1 == o2 then return true end

    local o1Type = type(o1)
    local o2Type = type(o2)
    --- different type
    if o1Type ~= o2Type then return false end
    --- same type but not table, already compared above
    if o1Type ~= 'table' then return false end

    -- use metatable method
    if not ignore_mt then
        local mt1 = getmetatable(o1)
        if mt1 and mt1.__eq then
            --compare using built in method
            return o1 == o2
        end
    end

    -- iterate over o1
    for key1, value1 in pairs(o1) do
        local value2 = o2[key1]
        if value2 == nil or deep_equals(value1, value2, ignore_mt) == false then
            return false
        end
    end

    --- check keys in o2 but missing from o1
    for key2, _ in pairs(o2) do
        if o1[key2] == nil then return false end
    end
    return true
end

Just for anyone wanting to see the differences, I made a slight modification to return the diff table:

--- deeply compare two objects and return the diff
local function deep_cmp(o1, o2)
	-- same object
	if o1 == o2 then return nil end

	local o1Type = type(o1)
	local o2Type = type(o2)
	--- different type
	if o1Type ~= o2Type then -- don't expand tables to make it more readable
		return { _1 = o1Type == 'table' and o1Type or o1, _2 = o2Type == 'table' and o2Type or o2 }
	end
	--- same type but not table, already compared above
	if o1Type ~= 'table' then return nil end

	local diff = {}

	-- iterate over o1
	for key1, value1 in pairs(o1) do
		local value2 = o2[key1]
		diff[key1] = deep_cmp(value1, value2)
	end

	--- check keys in o2 but missing from o1
	for key2, value2 in pairs(o2) do
		diff[key2] = deep_cmp(nil, value2)
	end
	local gen, param, state = pairs(diff)
	if gen(param, state) ~= nil then
		return diff
	else
		return nil
	end
end