gistfile1.txt

--PLAIN_LUA
local function deepEquals(a, b, visited)
	-- If a and b are the same reference, they're equal
	if a == b then return true end

	-- If either a or b is not a table, they must be equal values
	if type(a) ~= "table" or type(b) ~= "table" then
		-- direct comparison
		if a ~= b then
			return false, string.format("Values differ: %s ~= %s", tostring(a), tostring(b))
		end

		return true
	end

	-- Generate a key for this pair in our visited table
	-- Check if we've seen this pair before
	visited = visited or {}
	visited[a] = visited[a] or {}

	if visited[a][b] ~= nil then
		-- If marked "pending", we're in a circular reference - assume equality
		if visited[a][b] == "pending" then return true end

		return unpack(visited[a][b])
	end

	-- Mark this pair as being visited with a pending result
	visited[a] = visited[a] or {}
	visited[a][b] = "pending"
	-- Separate tables and non-table keys for efficiency
	local a_normal_keys = {}
	local b_normal_keys = {}
	local a_table_pairs = {}
	local b_table_pairs = {}

	-- Collect key-value pairs
	for k, v in pairs(a) do
		if type(k) == "table" then
			table.insert(a_table_pairs, {key = k, value = v})
		else
			a_normal_keys[k] = v
		end
	end

	for k, v in pairs(b) do
		if type(k) == "table" then
			table.insert(b_table_pairs, {key = k, value = v})
		else
			b_normal_keys[k] = v
		end
	end

	-- Check non-table keys (O(n) operation)
	for k, v in pairs(a_normal_keys) do
		if b_normal_keys[k] == nil then
			visited[a][b] = {false, string.format("Key '%s' exists in a but not in b", tostring(k))}
			return unpack(visited[a][b])
		end

		local isEqual, reason = deepEquals(v, b_normal_keys[k], visited)

		if not isEqual then
			visited[a][b] = {
				false,
				string.format("Value for key '%s' differs: %s", tostring(k), reason or ""),
			}
			return unpack(visited[a][b])
		end

		-- Mark as checked
		b_normal_keys[k] = nil
	end

	-- If there are any keys left in b_normal_keys, they don't exist in a
	if next(b_normal_keys) ~= nil then
		local key = next(b_normal_keys)
		visited[a][b] = {false, string.format("Key '%s' exists in b but not in a", tostring(key))}
		return unpack(visited[a][b])
	end

	-- Check table keys (O(n²) but only for table keys)
	if #a_table_pairs ~= #b_table_pairs then
		visited[a][b] = {
			false,
			string.format("Different number of table keys: %d vs %d", #a_table_pairs, #b_table_pairs),
		}
		return unpack(visited[a][b])
	end

	for _, a_pair in ipairs(a_table_pairs) do
		local found = false
		local lastReason = "No matching key-value pair"

		for _, b_pair in ipairs(b_table_pairs) do
			local keyEqual, keyReason = deepEquals(a_pair.key, b_pair.key, visited)

			if keyEqual then
				local valueEqual, valueReason = deepEquals(a_pair.value, b_pair.value, visited)

				if valueEqual then
					found = true

					break
				else
					lastReason = valueReason or "Values don't match"
				end
			else

			-- Don't update lastReason for key mismatches - that's expected when searching
			end
		end

		if not found then
			visited[a][b] = {false, lastReason}
			return unpack(visited[a][b])
		end
	end

	-- Check metatables for equality
	local mt_a = getmetatable(a)
	local mt_b = getmetatable(b)
	local mtEqual, mtReason = deepEquals(mt_a, mt_b, visited)

	if not mtEqual then
		visited[a][b] = {false, "Metatables differ: " .. (mtReason or "")}
		return unpack(visited[a][b])
	end

	-- Tables are deeply equal
	visited[a][b] = {true}
	return true
end

-- Test cases covering all scenarios
do
	local i = 0

	local function run(func, desc)
		local success, reason = func()

		if not success then
			print("test " .. i .. ": " .. desc .. " failed")
			print("   reason: " .. (reason or "unknown"))
		end

		i = i + 1
	end

	-- Test 1: Basic table equality
	run(
		function()
			local a = {1, 2, 3}
			local b = {1, 2, 3}
			return deepEquals(a, b)
		end,
		"Basic table equality"
	)

	-- Test 2: Different table values
	run(
		function()
			local a = {1, 2, 3}
			local b = {1, 2, 4}
			local equal, reason = deepEquals(a, b)
			return not equal
		end,
		"Different table values"
	)

	-- Test 3: Nested tables
	run(
		function()
			local a = {1, 2, {3, 4}}
			local b = {1, 2, {3, 4}}
			return deepEquals(a, b)
		end,
		"Nested tables"
	)

	-- Test 4: Different nested values
	run(
		function()
			local a = {1, 2, {3, 4}}
			local b = {1, 2, {3, 5}}
			local equal, reason = deepEquals(a, b)
			return not equal
		end,
		"Different nested values"
	)

	-- Test 5: Self-references
	run(
		function()
			local a = {}
			a.test = a
			local b = {}
			b.test = b
			return deepEquals(a, b)
		end,
		"Self-references"
	)

	-- Test 6: Cross-references
	run(
		function()
			local a = {}
			local b = {}
			a.test = b
			b.test = a
			return deepEquals(a, b)
		end,
		"Cross-references"
	)

	-- Test 7: Simple metatables
	run(
		function()
			local mt = {
				__index = function()
					return 1
				end,
			}
			local a = {}
			local b = {}
			setmetatable(a, mt)
			setmetatable(b, mt)
			return deepEquals(a, b)
		end,
		"Simple metatables"
	)

	-- Test 8: Different metatables
	run(
		function()
			local mt_a = {
				__index = function()
					return 1
				end,
			}
			local mt_b = {
				__index = function()
					return 2
				end,
			}
			local a = {}
			local b = {}
			setmetatable(a, mt_a)
			setmetatable(b, mt_b)
			local equal, reason = deepEquals(a, b)
			return not equal
		end,
		"Different metatables"
	)

	-- Test 9: Metatable with self-reference
	run(
		function()
			local a = {}
			local mt_a = {__index = a}
			setmetatable(a, mt_a)
			local b = {}
			local mt_b = {__index = b}
			setmetatable(b, mt_b)
			return deepEquals(a, b)
		end,
		"Metatable with self-reference"
	)

	-- Test 10: Complex nested structure
	run(
		function()
			local a = {
				x = 1,
				y = {
					z = 3,
					w = {v = 5},
				},
			}
			local b = {
				x = 1,
				y = {
					z = 3,
					w = {v = 5},
				},
			}
			return deepEquals(a, b)
		end,
		"Complex nested structure"
	)

	-- Test 11: Mixed key types
	run(
		function()
			local a = {
				[1] = "one",
				["two"] = 2,
				[true] = false,
			}
			local b = {
				[1] = "one",
				["two"] = 2,
				[true] = false,
			}
			return deepEquals(a, b)
		end,
		"Mixed key types"
	)

	-- Test 12: Tables as keys
	run(
		function()
			local key1 = {x = 1, y = 2}
			local key2 = {x = 1, y = 2}
			local a = {}
			local b = {}
			a[key1] = "value"
			b[key2] = "value"
			return deepEquals(a, b)
		end,
		"Tables as keys"
	)

	-- Test 13: Complex self-references with shared tables
	run(
		function()
			local a = {x = 1}
			local b = {x = 1}
			a.self = a
			a.other = b
			b.self = b
			b.other = a
			return deepEquals(a, b)
		end,
		"Complex self-references"
	)

	-- Test 14: Array with nested table elements
	run(
		function()
			local a = {{1, 2}, {3, 4}}
			local b = {{1, 2}, {3, 4}}
			return deepEquals(a, b)
		end,
		"Array with table elements"
	)

	-- Test 15: Tables with different order but same content
	run(
		function()
			local a = {c = 3, b = 2, a = 1}
			local b = {a = 1, b = 2, c = 3}
			return deepEquals(a, b)
		end,
		"Different order"
	)

	-- Test 16: Circular references in metatables
	run(
		function()
			local a = {}
			local b = {}
			local mt_a = {parent = a}
			local mt_b = {parent = b}
			setmetatable(a, mt_a)
			setmetatable(b, mt_b)
			return deepEquals(a, b)
		end,
		"Circular metatables"
	)

	-- Test 17: Deep nested self-references
	run(
		function()
			local a = {level1 = {}}
			a.level1.back = a
			local b = {level1 = {}}
			b.level1.back = b
			return deepEquals(a, b)
		end,
		"Deep nested self-references"
	)

	-- Test 18: Complex metatable inheritance
	run(
		function()
			local base_mt = {
				__add = function(a, b)
					return a.value + b.value
				end,
			}
			local a_proto = {value = 0}
			setmetatable(a_proto, base_mt)
			local b_proto = {value = 0}
			setmetatable(b_proto, base_mt)
			local a = {value = 5}
			setmetatable(a, {__index = a_proto})
			local b = {value = 5}
			setmetatable(b, {__index = b_proto})
			return deepEquals(a, b)
		end,
		"Metatable inheritance"
	)

	-- Test 19: 3-way circular references
	run(
		function()
			-- First set
			local a1 = {name = "node1"}
			local a2 = {name = "node2"}
			local a3 = {name = "node3"}
			a1.next = a2
			a2.next = a3
			a3.next = a1
			-- Second set
			local b1 = {name = "node1"}
			local b2 = {name = "node2"}
			local b3 = {name = "node3"}
			b1.next = b2
			b2.next = b3
			b3.next = b1
			return deepEquals(a1, b1)
		end,
		"Three-way circular references"
	)

	-- Test 20: 4-way circular references
	run(
		function()
			-- First set
			local a1 = {name = "node1"}
			local a2 = {name = "node2"}
			local a3 = {name = "node3"}
			local a4 = {name = "node4"}
			a1.next = a2
			a2.next = a3
			a3.next = a4
			a4.next = a1
			-- Second set
			local b1 = {name = "node1"}
			local b2 = {name = "node2"}
			local b3 = {name = "node3"}
			local b4 = {name = "node4"}
			b1.next = b2
			b2.next = b3
			b3.next = b4
			b4.next = b1
			return deepEquals(a1, b1)
		end,
		"Four-way circular references"
	)

	-- Test 21: Diamond pattern references
	run(
		function()
			-- First diamond
			local a_top = {name = "top"}
			local a_left = {name = "left"}
			local a_right = {name = "right"}
			local a_bottom = {name = "bottom"}
			a_top.left = a_left
			a_top.right = a_right
			a_left.bottom = a_bottom
			a_right.bottom = a_bottom
			a_bottom.top = a_top
			-- Second diamond
			local b_top = {name = "top"}
			local b_left = {name = "left"}
			local b_right = {name = "right"}
			local b_bottom = {name = "bottom"}
			b_top.left = b_left
			b_top.right = b_right
			b_left.bottom = b_bottom
			b_right.bottom = b_bottom
			b_bottom.top = b_top
			return deepEquals(a_top, b_top)
		end,
		"Diamond pattern references"
	)

	-- Test 22: Complex graph with multiple cross-references
	run(
		function()
			-- First graph
			local a_nodes = {}

			for i = 1, 5 do
				a_nodes[i] = {id = i, connections = {}}
			end

			-- Create connections (edges)
			table.insert(a_nodes[1].connections, a_nodes[2])
			table.insert(a_nodes[1].connections, a_nodes[3])
			table.insert(a_nodes[2].connections, a_nodes[3])
			table.insert(a_nodes[2].connections, a_nodes[4])
			table.insert(a_nodes[3].connections, a_nodes[5])
			table.insert(a_nodes[4].connections, a_nodes[5])
			table.insert(a_nodes[5].connections, a_nodes[1]) -- Circular dependency
			-- Second graph
			local b_nodes = {}

			for i = 1, 5 do
				b_nodes[i] = {id = i, connections = {}}
			end

			-- Create identical connections
			table.insert(b_nodes[1].connections, b_nodes[2])
			table.insert(b_nodes[1].connections, b_nodes[3])
			table.insert(b_nodes[2].connections, b_nodes[3])
			table.insert(b_nodes[2].connections, b_nodes[4])
			table.insert(b_nodes[3].connections, b_nodes[5])
			table.insert(b_nodes[4].connections, b_nodes[5])
			table.insert(b_nodes[5].connections, b_nodes[1]) -- Circular dependency
			return deepEquals(a_nodes[1], b_nodes[1])
		end,
		"Complex graph with cross-references"
	)

	-- Test 23: Mixed self-references and cross-references
	run(
		function()
			-- First structure
			local a1 = {name = "node1"}
			local a2 = {name = "node2"}
			-- Self-references
			a1.self = a1
			a2.self = a2
			-- Cross-references
			a1.other = a2
			a2.other = a1
			-- Nested references
			a1.nested = {parent = a1, sibling = a2}
			a2.nested = {parent = a2, sibling = a1}
			-- Second structure
			local b1 = {name = "node1"}
			local b2 = {name = "node2"}
			-- Self-references
			b1.self = b1
			b2.self = b2
			-- Cross-references
			b1.other = b2
			b2.other = b1
			-- Nested references
			b1.nested = {parent = b1, sibling = b2}
			b2.nested = {parent = b2, sibling = b1}
			return deepEquals(a1, b1)
		end,
		"Mixed self and cross-references"
	)

	run(
		function()
			local log = {}
			local mt = {
				__index = function(t, k)
					table.insert(log, "accessed " .. tostring(k))
					t[k] = {}
					return t[k]
				end,
			}
			local a = setmetatable({}, mt)
			local b = setmetatable({}, mt)
			return deepEquals(a, b)
		end,
		"test side effect"
	)
end