Directed Graph Execution Order in Lua

dependecies.lua

local ____symbolMetatable = {__tostring = function(self)
    if self.description == nil then
        return "Symbol()"
    else
        return "Symbol(" .. tostring(self.description) .. ")"
    end
end}
function __TS__Symbol(description)
    return setmetatable({description = description}, ____symbolMetatable)
end
Symbol = {
    iterator = __TS__Symbol("Symbol.iterator"),
    hasInstance = __TS__Symbol("Symbol.hasInstance"),
    species = __TS__Symbol("Symbol.species"),
    toStringTag = __TS__Symbol("Symbol.toStringTag"),
}

function __TS__InstanceOf(obj, classTbl)
    if type(classTbl) ~= "table" then
        error("Right-hand side of \'instanceof\' is not an object")
    end
    if classTbl[Symbol.hasInstance] ~= nil then
        return not not classTbl[Symbol.hasInstance](classTbl, obj)
    end
    if obj ~= nil then
        local luaClass = obj.constructor
        while luaClass ~= nil do
            if luaClass == classTbl then
                return true
            end
            luaClass = luaClass.____super
        end
    end
    return false
end

function __TS__Iterator(iterable)
    if iterable[Symbol.iterator] then
        local iterator = iterable[Symbol.iterator](iterable)
        return function()
            local result = iterator:next()
            if not result.done then
                return result.value
            else
                return nil
            end
        end
    else
        local i = 0
        return function()
            i = i + 1
            return iterable[i]
        end
    end
end

Set = (function()
    Set = {}
    Set.name = "Set"
    Set.__index = Set
    Set.prototype = {}
    Set.prototype.__index = Set.prototype
    Set.prototype.constructor = Set
    function Set.new(...)
        local self = setmetatable({}, Set.prototype)
        self:____constructor(...)
        return self
    end
    function Set.prototype.____constructor(self, values)
        self[Symbol.toStringTag] = "Set"
        self.items = {}
        self.size = 0
        if values == nil then
            return
        end
        local iterable = values
        if iterable[Symbol.iterator] then
            local iterator = iterable[Symbol.iterator](iterable)
            while true do
                local result = iterator:next()
                if result.done then
                    break
                end
                self:add(result.value)
            end
        else
            local array = values
            self.size = #array
            for ____, value in ipairs(array) do
                self.items[value] = true
            end
        end
    end
    function Set.prototype.add(self, value)
        if not self:has(value) then
            self.size = self.size + 1
        end
        self.items[value] = true
        return self
    end
    function Set.prototype.clear(self)
        self.items = {}
        self.size = 0
        return
    end
    function Set.prototype.delete(self, value)
        local contains = self:has(value)
        if contains then
            self.size = self.size - 1
        end
        self.items[value] = nil
        return contains
    end
    function Set.prototype.forEach(self, callback)
        for key in pairs(self.items) do
            callback(_G, key, key, self)
        end
    end
    function Set.prototype.has(self, value)
        return self.items[value] == true
    end
    Set.prototype[Symbol.iterator] = function(self)
        return self:values()
    end
    function Set.prototype.entries(self)
        local items = self.items
        local key
        return {
            [Symbol.iterator] = function(self)
                return self
            end,
            next = function(self)
                key = next(items, key)
                return {
                    done = not key,
                    value = {
                        key,
                        key,
                    },
                }
            end,
        }
    end
    function Set.prototype.keys(self)
        local items = self.items
        local key
        return {
            [Symbol.iterator] = function(self)
                return self
            end,
            next = function(self)
                key = next(items, key)
                return {
                    done = not key,
                    value = key,
                }
            end,
        }
    end
    function Set.prototype.values(self)
        local items = self.items
        local key
        return {
            [Symbol.iterator] = function(self)
                return self
            end,
            next = function(self)
                key = next(items, key)
                return {
                    done = not key,
                    value = key,
                }
            end,
        }
    end
    Set[Symbol.species] = Set
    return Set
end)()

function __TS__ArrayPush(arr, ...)
    local items = ({...})
    for ____, item in ipairs(items) do
        arr[#arr + 1] = item
    end
    return #arr
end

function __TS__ObjectKeys(obj)
    local result = {}
    for key in pairs(obj) do
        result[#result + 1] = key
    end
    return result
end

function __TS__ArrayForEach(arr, callbackFn)
    do
        local i = 0
        while i < #arr do
            callbackFn(_G, arr[i + 1], i, arr)
            i = i + 1
        end
    end
end

function __TS__ArrayIndexOf(arr, searchElement, fromIndex)
    local len = #arr
    if len == 0 then
        return -1
    end
    local n = 0
    if fromIndex then
        n = fromIndex
    end
    if n >= len then
        return -1
    end
    local k
    if n >= 0 then
        k = n
    else
        k = len + n
        if k < 0 then
            k = 0
        end
    end
    do
        local i = k
        while i < len do
            if arr[i + 1] == searchElement then
                return i
            end
            i = i + 1
        end
    end
    return -1
end

function __TS__ArrayFilter(arr, callbackfn)
    local result = {}
    do
        local i = 0
        while i < #arr do
            if callbackfn(_G, arr[i + 1], i, arr) then
                result[#result + 1] = arr[i + 1]
            end
            i = i + 1
        end
    end
    return result
end

function __TS__ArrayUnshift(arr, ...)
    local items = ({...})
    do
        local i = #items - 1
        while i >= 0 do
            table.insert(arr, 1, items[i + 1])
            i = i - 1
        end
    end
    return #arr
end

Vertex = {}
Vertex.name = "Vertex"
Vertex.__index = Vertex
Vertex.prototype = {}
Vertex.prototype.__index = Vertex.prototype
Vertex.prototype.constructor = Vertex
function Vertex.new(...)
    local self = setmetatable({}, Vertex.prototype)
    self:____constructor(...)
    return self
end
function Vertex.prototype.____constructor(self, graph)
    self.name = nil
    self.graph = graph
    self.edges = {
        from = Set.new(),
        to = Set.new(),
    }
end
function Vertex.prototype.edge(self, node)
    local ____ = self.edges
    local from = ____.from
    local ____ = node.edges
    local to = ____.to
    for edge in __TS__Iterator(to:values()) do
        if edge.to == self then
            return edge
        end
    end
    local edge = Edge.new(self, node)
    to:add(edge)
    from:add(edge)
    self.graph.edges:add(edge)
    return edge
end
Edge = {}
Edge.name = "Edge"
Edge.__index = Edge
Edge.prototype = {}
Edge.prototype.__index = Edge.prototype
Edge.prototype.constructor = Edge
function Edge.new(...)
    local self = setmetatable({}, Edge.prototype)
    self:____constructor(...)
    return self
end
function Edge.prototype.____constructor(self, from, to)
    self.from = from
    self.to = to
    self.graph = from.graph or to.graph
end
function Edge.prototype.remove(self)
    self.graph.edges:delete(self)
    self.to.edges.to:delete(self)
    self.from.edges.from:delete(self)
end
Digraph = {}
Digraph.name = "Digraph"
Digraph.__index = Digraph
Digraph.prototype = {}
Digraph.prototype.__index = Digraph.prototype
Digraph.prototype.constructor = Digraph
function Digraph.new(...)
    local self = setmetatable({}, Digraph.prototype)
    self:____constructor(...)
    return self
end
function Digraph.prototype.____constructor(self)
    self.nodes = {}
    self.edges = Set.new()
    self.cache = {}
end
function Digraph.prototype.node(self, node)
    if type(node) == "string" then
        local cached = self.cache[node]
        if not cached then
            local created = Vertex.new(self)
            created.name = node
            self.cache[node] = created
            __TS__ArrayPush(self.nodes, created)
        end
        return self.cache[node]
    end
    if node.name ~= nil then
        local cached = self.cache[node.name]
        if cached then
            __TS__ArrayForEach(__TS__ObjectKeys(node), function(____, key) return (function(o, i, v)
                o[i] = v
                return v
            end)(cached, key, node[key]) end)
        else
            self.cache[node.name] = node
            __TS__ArrayPush(self.nodes, node)
        end
        return self.cache[node.name]
    else
        local index = __TS__ArrayIndexOf(self.nodes, node)
        if index == -1 then
            __TS__ArrayPush(self.nodes, node)
            return node
        else
            return self.nodes[index + 1]
        end
    end
end
function Digraph.prototype.sort(self)
    local L = {}
    local S = __TS__ArrayFilter(self.nodes, function(____, n) return n.edges.to.size == 0 end)
    while #S > 0 do
        local n = table.remove(S)
        __TS__ArrayPush(L, n)
        for e in __TS__Iterator(n.edges.from) do
            local m = e.to
            e:remove()
            if m.edges.to.size == 0 then
                __TS__ArrayUnshift(S, m)
            end
        end
    end
    if self.edges.size > 0 then
        error("Could not create topological sort due to circular dependecies!")
    else
        return L
    end
end

example.lua

local a = {
    name = "a",
    dependecies = {},
}
local b = {
    name = "b",
    dependecies = {"a"},
}
local c = {
    name = "c",
    dependecies = {
        "a",
        "b",
    },
}
local packages = {
    b,
    c,
    a,
}
local G = Digraph.new()
for ____, pkg in ipairs(packages) do
    local node = G:node(pkg.name)
    for ____, dependecy in ipairs(pkg.dependecies) do
        G:node(dependecy):edge(node)
    end
end
for ____, pkg in ipairs(G:sort()) do
    print(pkg.name)
end