Pythons MRO implemented in Lua

gistfile1.lua

merge = function(seqs)
	local res = {}
	while true do
		--filter out empty sequences
		local nonemptyseqs = {}
		for _, seq in ipairs(seqs) do
			if #seq > 0 then table.insert(nonemptyseqs, seq) end
		end
		--all sequences empty? we're done!
		if #nonemptyseqs == 0 then return res end

		-- find merge candidates among seq heads
		local cand
		for _, seq in ipairs(nonemptyseqs) do
			cand = seq[1]

			--check if the candidate is in the tail of any sequence
			intail = (function()
				for _, nonemptyseq in ipairs(nonemptyseqs) do
					for j, cls in ipairs(nonemptyseq) do
						if j > 1 and cls == cand then
							return true
						end
					end
				end
				return false
			end)()
			if intail then
				break
			else
				cand = nil --reject candidate
			end
		end

		--add new entry
		if not cand then
			error("Inconsistent hierarchy", 2)
		else
			table.insert(res, cand)
			for _, seq in ipairs(nonemptyseqs) do -- remove cand
				if seq[1] == cand then
					table.remove(seq, 1)
				end
			end
		end
	end
end

mro = function(C)
	-- Compute the class precedence list (mro) according to C3
	local mros = {}
	local basesCopy = {} -- we need to copy C.__bases__ so that it isn't modified
	table.insert(mros, {C})
	for _, base in ipairs(C.__bases__) do
		table.insert(mros, mro(base))
		table.insert(basesCopy, base)
	end
	table.insert(mros, basesCopy)
	return merge(mros)
end

--Shell "class" for testing with
class = function(n, ...)
    return setmetatable({__bases__ = {...}}, {__tostring = function() return n end});
end

---------------------------------------------

O = class("O")
X = class("X", O)
Y = class("Y",O)
A = class("A",X, Y)
B = class("B",Y, X)

mA = mro(A)
mB = mro(B)

s = "A:\n"
for _, v in ipairs(mA) do s =s .. tostring(v) end
print(s) --AXYO

s = "B:\n"
for _, v in ipairs(mB) do s = s .. tostring(v) end
print(s) --BYXO

I will use this code for https://github.com/EcmaXp/PyCraft :D