bliss

commit 5b28d35e545b60453103e3acda32ac158af9e121
parent b2dc5a6e890d7d66a8b686a30250f2f0dcd24dea
Author: phoebos <ben@bvnf.space>
Date:   Fri, 16 Jun 2023 14:04:41 +0100

add pkg.order using a tsort

Diffstat:
M
bliss/pkg.lua
 | 
33
+++++++++++++++++++++++++++++++++
A
bliss/tsort.lua
 | 
77
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 110 insertions(+), 0 deletions(-)
diff --git a/bliss/pkg.lua b/bliss/pkg.lua
@@ -1,4 +1,5 @@
 local utils = require 'bliss.utils'
+local tsort = require 'bliss.tsort'
 local sys_stat = require 'posix.sys.stat'
 
 local function read_lines(file)
@@ -33,6 +34,11 @@ local function find_version(pkg, path)
     return ver[1]
 end
 
+local function find_depends(pkg, path)
+    local p = find(pkg, path) .. "/depends"
+    return read_lines(p)
+end
+
 local function find_sources(pkg, repo_dir)
     local p = repo_dir .. "/sources"
 
@@ -77,10 +83,37 @@ local function resolve(pkg, sources, env, repo_dir)
     return caches
 end
 
+local function order(env, pkgs)
+    local t = tsort.new()
+
+    for _,p in ipairs(pkgs) do
+        local deps = find_depends(p, env.PATH)
+        local deps_nomake = {}
+        for _,v in ipairs(deps) do
+            table.insert(deps_nomake, v[1])
+        end
+        t:add(p, deps_nomake)
+    end
+
+    local s, x,y = t:sort()
+    if not s then
+        utils.die("Circular dependency detected: " .. x .. " <> " .. y)
+    end
+
+    -- return s reversed (in order to be built)
+    local r = {}
+    for i = #s, 1, -1 do
+        r[i] = s[i]
+    end
+    return r
+end
+
 local M = {
     find = find,
     find_version = find_version,
+    find_depends = find_depends,
     find_sources = find_sources,
     resolve = resolve,
+    order = order,
 }
 return M
diff --git a/bliss/tsort.lua b/bliss/tsort.lua
@@ -0,0 +1,77 @@
+-- This module is not included in init.lua, but used locally by pkg.lua.
+local tsort = {}
+
+-- Returns a table of reverse deps
+local function reverse(input)
+    local reversed = {}
+    for k,v in pairs(input) do
+        for _,w in ipairs(v) do
+            reversed[w] = reversed[w] or {}
+            table.insert(reversed[w], k)
+        end
+    end
+    return reversed
+end
+
+local function find_cycle(revlinks, start)
+    local ret = {[start] = 1}
+    local old
+
+    local t = revlinks[start][1]
+    while t and not ret[t] do
+        ret[t] = 1
+        old = t
+        t = revlinks[t][1]
+    end
+    return t, old
+end
+
+function tsort.new()
+    return setmetatable({nodes={}}, {__index = tsort})
+end
+
+function tsort:add(node, deps)
+    self.nodes[node] = deps
+end
+
+function tsort:sort()
+    if not self.nodes then return nil end
+    local L = {}
+    local reversed = reverse(self.nodes)
+
+    -- find nodes with no incoming edges
+    local S = {}
+    for k in pairs(self.nodes) do
+        if not reversed[k] or #reversed[k] == 0 then
+            table.insert(S, k)
+        end
+    end
+
+    while #S ~= 0 do
+        local n = table.remove(S, 1)
+        table.insert(L, n)
+        for _,v in ipairs(self.nodes[n] or {}) do
+            -- remove edge n -> v
+            for i,j in ipairs(reversed[v]) do
+                if j == n then
+                    table.remove(reversed[v], i)
+                end
+            end
+            if not reversed[v] or #reversed[v] == 0 then
+                table.insert(S, v)
+                reversed[v] = nil
+            end
+        end
+    end
+
+    for k,v in pairs(reversed) do
+        if #v ~= 0 then
+            -- cycle detected
+            local x,y = find_cycle(reversed, k)
+            return nil, x, y
+        end
+    end
+    return L
+end
+
+return tsort