commit 0d1bf8c9df4b48c50786c9849cad07cb66aab878
parent 5e087386088827aee5d4ec78fcc7fcd29bb3827d
Author: phoebos <ben@bvnf.space>
Date: Fri, 30 Jun 2023 01:24:18 +0100
Merge branch 'pkg_order'
Diffstat:
3 files changed, 159 insertions(+), 1 deletion(-)
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)
@@ -6,7 +7,9 @@ local function read_lines(file)
local f = io.open(file)
if not f then return {} end
for line in f:lines() do
- table.insert(t, utils.split(line, " "))
+ if #line ~= 0 and string.sub(line, 1, 1) ~= '#' then
+ table.insert(t, utils.split(line, " "))
+ end
end
f:close()
return t
@@ -37,6 +40,11 @@ local function find_checksums(pkg, repo_dir)
return read_lines(p)
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"
@@ -81,11 +89,53 @@ local function resolve(pkg, sources, env, repo_dir)
return caches
end
+local function recurse_all_deps(env, pkgs, deps)
+ for _, p in ipairs(pkgs) do
+ if not deps[p] then
+ local d = find_depends(p, env.PATH)
+ -- ignore make, just get pkg names
+ local d_ = {}
+ for _,v in ipairs(d) do
+ table.insert(d_, v[1])
+ end
+
+ -- recurse
+ deps = recurse_all_deps(env, d_, deps)
+
+ deps[p] = d_
+ end
+ end
+ return deps
+end
+
+local function order(env, pkgs)
+ local t = tsort.new()
+
+ local deps = recurse_all_deps(env, pkgs, {})
+ for k,v in pairs(deps) do
+ t:add(k, v)
+ 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_checksums = find_checksums,
+ 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
diff --git a/contrib/bliss-fulldepends b/contrib/bliss-fulldepends
@@ -0,0 +1,31 @@
+#!/usr/bin/env lua
+-- Display all dependencies of packages (recursively)
+local bliss = require "bliss"
+local dirent = require "posix.dirent"
+
+local function lists(env, arg)
+ if #arg == 0 then
+ for file in dirent.files(env.sys_db) do
+ if string.sub(file, 1, 1) ~= "." then
+ table.insert(arg, {file, #bliss.order(env, {file})})
+ end
+ end
+ table.sort(arg, function (a,b) return a[2]<b[2] end)
+ for _,v in ipairs(arg) do print(v[1],v[2]) end
+ else
+ local deps = bliss.order(env, {arg[1]})
+ for _,v in ipairs(deps) do print(v) end
+ end
+end
+
+if arg[1] == "-h" then
+ print("usage: "..arg[0].." [pkg]")
+ print(" With no args, list installed packages by total number of dependencies")
+ print(" With an arg, list full dependencies of pkg")
+ os.exit()
+end
+
+local env, atexit = bliss.setup()
+table.insert(env.PATH, 1, env.sys_db)
+
+lists(env, arg)
