Module:table/compare

local string_linesub_module = "Module:string/linesub"
local table_get_metamethod_module = "Module:table/getMetamethod"

local error = error
local rawequal = rawequal
local require = require
local sub = string.sub
local traceback = debug.traceback
local xpcall = xpcall

local function get_metamethod(...)
	get_metamethod = require(table_get_metamethod_module)
	return get_metamethod(...)
end

local function linesub(...)
	linesub = require(string_linesub_module)
	return linesub(...)
end

local _a, _b -- used to pass arguments to compare_for_xpcall()
local NOT_COMPARABLE = {} -- sentinel

local function compare_for_xpcall()
	local a, b = _a, _b
	_a, _b = nil
	return a < b
end

local function err_handler(err)
	-- Error message relate to comparing two table values, but the trace at the
	-- start of the message needs to be trimmed. Traceback will only refer to
	-- xpcall() on line 5 if the error occured in compare_for_xpcall(); if it
	-- originated further up the stack (i.e. in a metamethod), xpcall() will
	-- only be mentioned on a later line.
	if (
		sub(err, -35) == "attempt to compare two table values" and
		linesub(traceback(), 5, 5) == "\t: in function 'xpcall'"
	) then
		return NOT_COMPARABLE
	end
	return err
end

--[==[
A comparison function for tables, which returns {true} if {a} sorts before {b}, or otherwise {false}; it can be used as the sort function with {table.sort}.

By default, attempting to compare two tables will result in an error, unless both tables have the same {__lt} metamethod. This function will also use the {__lt} metamethod under the same circumstances, but will return {false} instead of throwing an error if the two tables are not comparable.]==]
return function(a, b)
	-- If `a` and `b` are tables, they are only comparable if they both have the
	-- same __lt metamethod. get_unprotected_metatable() returns nil if there is
	-- no metatable, and false if the metatable is protected.
	local success_a, __lt_a = get_metamethod(a, "__lt")
	-- Not comparable if `a` has no __lt metamethod.
	if success_a and __lt_a == nil then
		return false
	end
	local success_b, __lt_b = get_metamethod(b, "__lt")
	if success_b then
		-- Not comparable if `b` has no __lt metamethod.
		if __lt_b == nil then
			return false
		-- If `a` and `b` have known __lt metamethods, they are only comparable
		-- if the two metamethods are primitively equal.
		elseif __lt_a ~= nil then
			return rawequal(__lt_a, __lt_b) and a < b
		end
	end
	-- Not possible to know if `a` and `b` are comparable if either or both have
	-- protected metatables, and neither are confirmed to have no __lt
	-- metamethod. Use xpcall() when comparing them, with an error handler that
	-- determines if the error was due to `a` and `b` not being comparable.
	-- Unlike pcall(), xpcall() can't pass on arguments to the called function,
	-- so use upvalues in the top-level of the module to circumvent this.
	_a, _b = a, b
	local success, result = xpcall(compare_for_xpcall, err_handler)
	if success then
		return result
	elseif result == NOT_COMPARABLE then
		return false
	end
	-- If the error wasn't due to the comparison, rethrow it.
	error(result)
end