onelf_sysroot/
closure.rs

1//! The set of packages an application reaches.
2
3use std::collections::{BTreeSet, VecDeque};
4
5use crate::db::Database;
6
7/// The packages reached from a root package, and the dependencies that
8/// nothing in the sysroot satisfies.
9#[derive(Debug, Default, PartialEq, Eq)]
10pub struct Closure {
11    /// Sorted package names, the root included.
12    pub packages: Vec<String>,
13    /// `(dependency, needed by)` for names no package provides. A
14    /// debloated sysroot drops metapackages on purpose, so this is
15    /// reported rather than fatal.
16    pub unsatisfied: Vec<(String, String)>,
17}
18
19impl Database {
20    /// The transitive `depends` closure of `root` and of every package
21    /// named in `optional`, plus every optional dependency so named,
22    /// resolved through `provides`. Naming a package nothing depends on,
23    /// a Vulkan driver say, is how it enters at all.
24    pub fn closure(&self, root: &str, optional: &[String]) -> Closure {
25        self.closure_excluding(root, optional, &BTreeSet::new())
26    }
27
28    /// As [`Self::closure`], with `excluded` packages treated as absent:
29    /// neither they nor what only they depend on enter.
30    pub fn closure_excluding(
31        &self,
32        root: &str,
33        optional: &[String],
34        excluded: &BTreeSet<String>,
35    ) -> Closure {
36        let mut seen: BTreeSet<String> = BTreeSet::new();
37        let mut unsatisfied = Vec::new();
38        let mut queue: VecDeque<String> = VecDeque::new();
39        queue.push_back(root.to_string());
40        queue.extend(
41            optional
42                .iter()
43                .filter_map(|name| self.satisfier(name))
44                .map(|p| p.name.clone()),
45        );
46        while let Some(name) = queue.pop_front() {
47            if !seen.insert(name.clone()) {
48                continue;
49            }
50            let Some(package) = self.package(&name) else {
51                continue;
52            };
53            if excluded.contains(&name) && name != root {
54                continue;
55            }
56            let wanted = package.depends.iter().chain(
57                package
58                    .optdepends
59                    .iter()
60                    .filter(|o| optional.iter().any(|w| w == *o)),
61            );
62            for dep in wanted {
63                match self.satisfier(dep) {
64                    Some(p) => {
65                        if !seen.contains(&p.name) {
66                            queue.push_back(p.name.clone());
67                        }
68                    }
69                    None => unsatisfied.push((dep.clone(), name.clone())),
70                }
71            }
72        }
73        unsatisfied.sort();
74        unsatisfied.dedup();
75        Closure {
76            packages: seen
77                .into_iter()
78                .filter(|n| n == root || !excluded.contains(n))
79                .collect(),
80            unsatisfied,
81        }
82    }
83
84    /// Every file owned by the packages in `closure`, sorted.
85    pub fn files_of(&self, closure: &Closure) -> Vec<String> {
86        let mut files: Vec<String> = closure
87            .packages
88            .iter()
89            .filter_map(|n| self.package(n))
90            .flat_map(|p| p.files.iter().cloned())
91            .collect();
92        files.sort();
93        files.dedup();
94        files
95    }
96}
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101    use crate::db::fixture::pkg;
102
103    fn db() -> Database {
104        let mut db = Database::default();
105        let mut app = pkg("app", &["usr/bin/app"]);
106        app.depends = vec!["libfixture".into(), "libvirtual.so".into()];
107        app.optdepends = vec!["extra".into(), "absent".into()];
108        db.insert(app);
109        let mut lib = pkg("libfixture", &["usr/lib/libfixture.so.1"]);
110        lib.depends = vec!["zlib".into()];
111        db.insert(lib);
112        db.insert(pkg("zlib", &["usr/lib/libz.so.1"]));
113        let mut provider = pkg("provider", &["usr/lib/libvirtual.so.1"]);
114        provider.provides = vec!["libvirtual.so".into()];
115        db.insert(provider);
116        db.insert(pkg("extra", &["usr/lib/plugins/extra.so"]));
117        db.insert(pkg("unrelated", &["usr/bin/other"]));
118        db
119    }
120
121    #[test]
122    fn reaches_transitive_and_provided_dependencies() {
123        let c = db().closure("app", &[]);
124        assert_eq!(c.packages, ["app", "libfixture", "provider", "zlib"]);
125        assert!(c.unsatisfied.is_empty());
126        assert_eq!(
127            db().files_of(&c),
128            [
129                "usr/bin/app",
130                "usr/lib/libfixture.so.1",
131                "usr/lib/libvirtual.so.1",
132                "usr/lib/libz.so.1"
133            ]
134        );
135    }
136
137    #[test]
138    fn optional_dependencies_enter_only_when_named() {
139        let c = db().closure("app", &["extra".to_string()]);
140        assert!(c.packages.contains(&"extra".to_string()));
141        assert!(c.unsatisfied.is_empty());
142
143        let c = db().closure("app", &["absent".to_string()]);
144        assert_eq!(c.unsatisfied, [("absent".to_string(), "app".to_string())]);
145    }
146
147    #[test]
148    fn a_missing_dependency_is_reported_not_fatal() {
149        let mut db = db();
150        let mut app = db.package("app").unwrap().clone();
151        app.depends.push("gone".into());
152        db.insert(app);
153        let c = db.closure("app", &[]);
154        assert!(c.packages.contains(&"zlib".to_string()));
155        assert_eq!(c.unsatisfied, [("gone".to_string(), "app".to_string())]);
156    }
157}
onelf_sysroot/closure.rs

onelf_sysroot/
closure.rs
