Moduli:table/deepEquals

Udhëzuesi për këtë modul mund të krijohet te Moduli:table/deepEquals/doc.

local getmetatable = getmetatable
local next = next
local pairs = pairs
local type = type

local function is_eq(a, b, seen, include_mt)
	-- If `a` and `b` have been compared before, return the memoized result. This will usually be true, since failures normally fail the whole check outright, but match failures are tolerated during the laborious check without this happening, since it compares key/value pairs until it finds a match, so it could be false.
	local memo_a = seen[a]
	if memo_a then
		local result = memo_a[b]
		if result ~= nil then
			return result
		end
		-- To avoid recursive references causing infinite loops, assume the tables currently being compared are equivalent by memoizing the comparison as true; this will be corrected to false if there's a match failure.
		memo_a[b] = true
	else
		memo_a = {[b] = true}
		seen[a] = memo_a
	end
	-- Don't bother checking `memo_b` for `a`, since if `a` and `b` had been compared before then `b` would be in `memo_a`, but it isn't.
	local memo_b = seen[b]
	if memo_b then
		memo_b[a] = true
	else
		memo_b = {[a] = true}
		seen[b] = memo_b
	end
	-- If `include_mt` is set, check the metatables are equivalent.
	if include_mt then
		local mt_a, mt_b = getmetatable(a), getmetatable(b)
		if not (mt_a == mt_b or type(mt_a) == "table" and type(mt_b) == "table" and is_eq(mt_a, mt_b, seen, true)) then
			memo_a[b], memo_b[a] = false, false
			return false
		end
	end
	-- Copy all key/values pairs in `b` to `remaining_b`, and count the size: this uses `pairs`, which will also be used to iterate over `a`, ensuring that `a` and `b` are iterated over using the same iterator. This is necessary to ensure that `deepEquals(a, b)` and `deepEquals(b, a)` always give the same result. Simply iterating over `a` while accessing keys in `b` for comparison would ignore any `__pairs` metamethod that `b` has, which could cause asymmetrical outputs if `__pairs` returns more or less than the complete set of key/value pairs accessible via `__index`, so using `pairs` for both `a` and `b` prevents this.
	-- TODO: handle exotic `__pairs` methods which return the same key multiple times with different values.
	local remaining_b, size_b = {}, 0
	for k_b, v_b in pairs(b) do
		remaining_b[k_b], size_b = v_b, size_b + 1
	end
	-- Fast check: iterate over the keys in `a`, checking if an equivalent value exists at the same key in `remaining_b`. As matches are found, key/value pairs are removed from `remaining_b`. If any keys in `a` or `remaining_b` are tables, the fast check will only work if the exact same object exists as a key in the other table. Any others from `a` that don't match anything in `remaining_b` are added to `remaining_a`, while those in `remaining_b` that weren't found will still remain once the loop ends. `remaining_a` and `remaining_b` are then compared at the end with the laborious check.
	local size_a, remaining_a = 0
	for k, v_a in pairs(a) do
		local v_b = remaining_b[k]
		-- If `k` isn't in `remaining_b`, `a` and `b` can't be equivalent unless it's a table.
		if v_b == nil then
			if type(k) ~= "table" then
				memo_a[b], memo_b[a] = false, false
				return false
			-- Otherwise, add the `k`/`v_a` pair to `remaining_a` for the laborious check.
			elseif not remaining_a then
				remaining_a = {}
			end
			remaining_a[k], size_a = v_a, size_a + 1
		-- Otherwise, if `k` exists in `a` and `remaining_b`, `v_a` and `v_b` must be equivalent for there to be a match.
		elseif v_a == v_b or type(v_a) == "table" and type(v_b) == "table" and is_eq(v_a, v_b, seen, include_mt) then
			remaining_b[k], size_b = nil, size_b - 1
		else
			memo_a[b], memo_b[a] = false, false
			return false
		end
	end
	-- Must be the same number of remaining keys in each table.
	if size_a ~= size_b then
		memo_a[b], memo_b[a] = false, false
		return false
	-- If the size is 0, there's nothing left to check.
	elseif size_a == 0 then
		return true
	end
	-- Laborious check: since it's not possible to use table lookups to check if two keys are equivalent when they're tables, check each key/value pair in `remaining_a` against every key/value pair in `remaining_b` until a match is found, removing the matching key/value pair from `remaining_b` each time, to ensure one-to-one equivalence.
	for k_a, v_a in next, remaining_a do
		local success
		for k_b, v_b in next, remaining_b do
			-- Keys/value pairs must be equivalent in order to match.
			if ( -- More efficient to compare the values first, as they might not be tables.
				(v_a == v_b or type(v_a) == "table" and type(v_b) == "table" and is_eq(v_a, v_b, seen, include_mt)) and
				(k_a == k_b or type(k_a) == "table" and type(k_b) == "table" and is_eq(k_a, k_b, seen, include_mt))
			) then
				-- Remove matched key from `remaining_b`, and break the inner loop.
				success, remaining_b[k_b] = true, nil
				break
			end
		end
		-- Fail if `remaining_b` runs out of keys, as the `k_a`/`v_a` pair still hasn't matched.
		if not success then
			memo_a[b], memo_b[a] = false, false
			return false
		end
	end
	-- If every key/value pair in `remaining_a` matched with one in `remaining_b`, `a` and `b` must be equivalent. Note that `remaining_b` will now be empty, since the laborious check only starts if `remaining_a` and `remaining_b` are the same size.
	return true
end

--[==[
Recursively compare two values that may be tables, and returns true if all key-value pairs are structurally equivalent. Note that this handles arbitrary nesting of subtables (including recursive nesting) to any depth, for keys as well as values.

If `include_mt` is true, then metatables are also compared.]==]
return function(a, b, include_mt)
	-- Do simple checks before calling is_eq to avoid generating an unnecessary memo.
	-- Simple equality check and type check; if not a ~= b, a and b can only be equivalent if they're both tables.
	return a == b or type(a) == "table" and type(b) == "table" and is_eq(a, b, {}, include_mt)
end