Sware: Created page with "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 = see..."

2025-11-25T17:11:26Z

Created page with "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 = see..."

New page

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

Module:table/deepEquals - Revision history