sui_spec/
store_analyze.rs

1//! Typed analysis over an observed store.
2//!
3//! Consumes a [`StoreInventory`] + optional [`RefIndex`] and
4//! emits typed [`Finding`]s the operator can act on:
5//!
6//! - **Duplicate** — N entries share a NAR digest (waste).
7//! - **Orphan** — no referrers in the indexed set.
8//! - **HighFanout** — drv with > N input edges.
9//! - **VersionShadow** — older version superseded by newer.
10//!
11//! Plus typed [`UpgradePath`]s mined from the version-shadow
12//! relation — for every `pkg-1.0` shadowed by `pkg-1.1`, emit
13//! a recommended upgrade.
14
15use std::collections::{BTreeMap, BTreeSet};
16
17use crate::nar;
18use crate::store_inventory::{RefIndex, StoreInventory};
19
20/// One typed finding the analyzer surfaces.
21#[derive(Debug, Clone, PartialEq, Eq)]
22pub enum Finding {
23    /// Multiple store paths with the same NAR content hash.
24    /// `hash` is hex sha256; `paths` are the duplicates.
25    Duplicate {
26        hash: String,
27        paths: Vec<std::path::PathBuf>,
28        bytes_each: u64,
29    },
30    /// Path with zero referrers in the indexed set.
31    /// Candidate for GC (subject to root-set semantics).
32    Orphan {
33        path: std::path::PathBuf,
34        size: u64,
35    },
36    /// Drv with input-fan-out beyond the threshold.
37    HighFanout {
38        path: std::path::PathBuf,
39        fanout: usize,
40    },
41    /// Older version superseded by a newer one of the same name.
42    VersionShadow {
43        older: std::path::PathBuf,
44        newer: std::path::PathBuf,
45        name_root: String,
46        older_version: String,
47        newer_version: String,
48    },
49}
50
51/// Aggregated counts.
52#[derive(Debug, Default, Clone)]
53pub struct FindingsHistogram {
54    pub duplicates: usize,
55    pub orphans: usize,
56    pub high_fanout: usize,
57    pub version_shadows: usize,
58}
59
60/// Configuration knobs for [`analyze`].
61#[derive(Debug, Clone)]
62pub struct AnalyzeConfig {
63    /// Compute NAR sha256 for every entry to find duplicates.
64    /// Expensive on large stores — operator-driven opt-in.
65    pub detect_duplicates: bool,
66    /// Flag entries with no referrers in the inventory.  Requires
67    /// `idx` to be supplied to `analyze`.
68    pub detect_orphans: bool,
69    /// Flag drvs with input fan-out above this threshold.  0 disables.
70    pub high_fanout_threshold: usize,
71    /// Detect older/newer version shadow pairs.
72    pub detect_version_shadows: bool,
73}
74
75impl Default for AnalyzeConfig {
76    fn default() -> Self {
77        Self {
78            detect_duplicates: true,
79            detect_orphans: true,
80            high_fanout_threshold: 8,
81            detect_version_shadows: true,
82        }
83    }
84}
85
86/// Walk an inventory + (optional) ref index and emit findings.
87pub fn analyze(
88    inv: &StoreInventory,
89    idx: Option<&RefIndex>,
90    config: &AnalyzeConfig,
91) -> Vec<Finding> {
92    let mut findings: Vec<Finding> = Vec::new();
93
94    if config.detect_duplicates {
95        findings.extend(detect_duplicates(inv));
96    }
97    if config.detect_orphans {
98        if let Some(idx) = idx {
99            findings.extend(detect_orphans(inv, idx));
100        }
101    }
102    if config.high_fanout_threshold > 0 {
103        if let Some(idx) = idx {
104            findings.extend(detect_high_fanout(inv, idx, config.high_fanout_threshold));
105        }
106    }
107    if config.detect_version_shadows {
108        findings.extend(detect_version_shadows(inv));
109    }
110
111    findings
112}
113
114/// Convenience: bucket findings by kind.
115#[must_use]
116pub fn histogram(findings: &[Finding]) -> FindingsHistogram {
117    let mut h = FindingsHistogram::default();
118    for f in findings {
119        match f {
120            Finding::Duplicate { .. }     => h.duplicates += 1,
121            Finding::Orphan { .. }        => h.orphans += 1,
122            Finding::HighFanout { .. }    => h.high_fanout += 1,
123            Finding::VersionShadow { .. } => h.version_shadows += 1,
124        }
125    }
126    h
127}
128
129fn detect_duplicates(inv: &StoreInventory) -> Vec<Finding> {
130    use sha2::Digest;
131    let mut by_hash: BTreeMap<String, Vec<std::path::PathBuf>> = BTreeMap::new();
132    let mut size_of: BTreeMap<String, u64> = BTreeMap::new();
133    for entry in inv.entries.values() {
134        let Ok(bytes) = nar::encode(&entry.path) else { continue };
135        let digest = sha2::Sha256::digest(&bytes);
136        let hex: String = digest.iter().map(|b| format!("{b:02x}")).collect();
137        size_of.entry(hex.clone()).or_insert(entry.size);
138        by_hash.entry(hex).or_default().push(entry.path.clone());
139    }
140    by_hash.into_iter()
141        .filter(|(_, paths)| paths.len() > 1)
142        .map(|(hash, paths)| Finding::Duplicate {
143            bytes_each: *size_of.get(&hash).unwrap_or(&0),
144            hash,
145            paths,
146        })
147        .collect()
148}
149
150fn detect_orphans(inv: &StoreInventory, idx: &RefIndex) -> Vec<Finding> {
151    inv.entries.values()
152        .filter(|e| idx.referrers_of(&e.path).is_empty())
153        .map(|e| Finding::Orphan {
154            path: e.path.clone(),
155            size: e.size,
156        })
157        .collect()
158}
159
160fn detect_high_fanout(
161    inv: &StoreInventory,
162    idx: &RefIndex,
163    threshold: usize,
164) -> Vec<Finding> {
165    inv.entries.values()
166        .filter(|e| idx.refs_from(&e.path).len() >= threshold)
167        .map(|e| Finding::HighFanout {
168            path: e.path.clone(),
169            fanout: idx.refs_from(&e.path).len(),
170        })
171        .collect()
172}
173
174/// Mine version-shadow relations from an inventory.  Groups
175/// entries by `<name-without-version>`; within each group,
176/// detects pairs where one version is older than another via
177/// the [`split_name_version`] heuristic.
178fn detect_version_shadows(inv: &StoreInventory) -> Vec<Finding> {
179    // Bucket entries by name-root.
180    let mut by_root: BTreeMap<String, Vec<(&str, &std::path::Path, u64)>> = BTreeMap::new();
181    for entry in inv.entries.values() {
182        if let Some((name_root, version)) = split_name_version(&entry.parsed.name) {
183            by_root.entry(name_root.to_string())
184                .or_default()
185                .push((version, entry.path.as_path(), entry.size));
186        }
187    }
188
189    let mut findings: Vec<Finding> = Vec::new();
190    for (name_root, mut versions) in by_root {
191        if versions.len() < 2 { continue; }
192        // Sort by version (string-wise — coarse, good enough for
193        // the common semver-like case).
194        versions.sort_by(|a, b| version_cmp(a.0, b.0));
195        // Pairs of (older, newer).
196        for window in versions.windows(2) {
197            let (older_v, older_p, _) = window[0];
198            let (newer_v, newer_p, _) = window[1];
199            findings.push(Finding::VersionShadow {
200                older: older_p.to_path_buf(),
201                newer: newer_p.to_path_buf(),
202                name_root: name_root.clone(),
203                older_version: older_v.to_string(),
204                newer_version: newer_v.to_string(),
205            });
206        }
207    }
208    findings
209}
210
211/// Heuristic split of `name-1.2.3` into `("name", "1.2.3")`.
212/// Walks backwards from the end; the first `-` followed by a
213/// digit-leading suffix is the version separator.
214fn split_name_version(s: &str) -> Option<(&str, &str)> {
215    let bytes = s.as_bytes();
216    let mut i = 0usize;
217    while i < bytes.len() {
218        if bytes[i] == b'-' && i + 1 < bytes.len() && bytes[i + 1].is_ascii_digit() {
219            let name = &s[..i];
220            let version = &s[i + 1..];
221            if !name.is_empty() && !version.is_empty() {
222                return Some((name, version));
223            }
224        }
225        i += 1;
226    }
227    None
228}
229
230/// Coarse version comparator — splits on `.` / `-` and compares
231/// numeric components numerically, alphas lexically.  Good
232/// enough for typical semver-like nix names.
233fn version_cmp(a: &str, b: &str) -> std::cmp::Ordering {
234    let split = |s: &str| -> Vec<String> {
235        s.split(|c: char| c == '.' || c == '-' || c == '+')
236            .map(String::from)
237            .collect()
238    };
239    let av = split(a);
240    let bv = split(b);
241    let max = av.len().max(bv.len());
242    for i in 0..max {
243        let ai = av.get(i).map(String::as_str).unwrap_or("");
244        let bi = bv.get(i).map(String::as_str).unwrap_or("");
245        let ord = match (ai.parse::<u64>(), bi.parse::<u64>()) {
246            (Ok(x), Ok(y))   => x.cmp(&y),
247            (Ok(_), Err(_))  => std::cmp::Ordering::Greater,
248            (Err(_), Ok(_))  => std::cmp::Ordering::Less,
249            (Err(_), Err(_)) => ai.cmp(bi),
250        };
251        if ord != std::cmp::Ordering::Equal { return ord; }
252    }
253    std::cmp::Ordering::Equal
254}
255
256// ── UpgradePath miner ──────────────────────────────────────────────
257
258/// Recommended typed upgrade.
259#[derive(Debug, Clone, PartialEq, Eq)]
260pub struct UpgradePath {
261    pub from: std::path::PathBuf,
262    pub to: std::path::PathBuf,
263    pub name_root: String,
264    pub from_version: String,
265    pub to_version: String,
266    /// Number of paths that currently reference `from` — the
267    /// blast radius of applying this upgrade.
268    pub referrers_count: usize,
269}
270
271/// Extract `UpgradePath`s from `findings` plus a `RefIndex`.
272/// Every `VersionShadow` becomes an upgrade recommendation;
273/// the referrer count comes from the index.
274#[must_use]
275pub fn mine_upgrade_paths(
276    findings: &[Finding],
277    idx: &RefIndex,
278) -> Vec<UpgradePath> {
279    findings.iter().filter_map(|f| match f {
280        Finding::VersionShadow { older, newer, name_root, older_version, newer_version } => {
281            Some(UpgradePath {
282                from: older.clone(),
283                to: newer.clone(),
284                name_root: name_root.clone(),
285                from_version: older_version.clone(),
286                to_version: newer_version.clone(),
287                referrers_count: idx.referrers_of(older).len(),
288            })
289        }
290        _ => None,
291    }).collect()
292}
293
294/// Sort upgrade paths by descending blast radius (referrers).
295pub fn sort_upgrade_paths(paths: &mut [UpgradePath]) {
296    paths.sort_by_key(|p| std::cmp::Reverse(p.referrers_count));
297}
298
299#[cfg(test)]
300mod tests {
301    use super::*;
302
303    #[test]
304    fn split_name_version_handles_typical_shapes() {
305        assert_eq!(split_name_version("hello-2.12"), Some(("hello", "2.12")));
306        assert_eq!(split_name_version("rust_litrs-1.0.0-lib"), Some(("rust_litrs", "1.0.0-lib")));
307        assert_eq!(split_name_version("nodash"), None);
308        assert_eq!(split_name_version("dashed-but-no-version"), None);
309    }
310
311    #[test]
312    fn version_cmp_orders_typical_versions() {
313        use std::cmp::Ordering;
314        assert_eq!(version_cmp("1.0", "1.1"), Ordering::Less);
315        assert_eq!(version_cmp("1.10", "1.9"), Ordering::Greater);
316        assert_eq!(version_cmp("1.0.0", "1.0.0"), Ordering::Equal);
317        assert_eq!(version_cmp("2.0", "1.99"), Ordering::Greater);
318    }
319}
sui_spec/store_analyze.rs

sui_spec/
store_analyze.rs
