heddle_object_model/object/
semantic_reverse_deps.rs

1// SPDX-License-Identifier: Apache-2.0
2//! File → importers reverse-dependency index for incremental re-resolution.
3
4use std::collections::{BTreeMap, BTreeSet};
5
6use serde::{Deserialize, Serialize};
7
8use super::SemanticIndexError;
9
10/// Content-addressed file → importers map for one state.
11///
12/// `importers[target]` lists every source file whose resolved dependencies
13/// include `target`. Capture walks this map from changed files to obtain the
14/// invalidation frontier without re-resolving the rest of the repository.
15#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
16pub struct ReverseDependencyIndex {
17    pub format_version: u8,
18    /// Imported file → sorted importer paths.
19    pub importers: BTreeMap<String, Vec<String>>,
20}
21
22impl ReverseDependencyIndex {
23    pub const FORMAT_VERSION: u8 = 1;
24
25    /// Construct a canonical index from an importer map.
26    pub fn new(importers: BTreeMap<String, BTreeSet<String>>) -> Self {
27        let importers = importers
28            .into_iter()
29            .filter_map(|(target, sources)| {
30                if sources.is_empty() {
31                    None
32                } else {
33                    Some((target, sources.into_iter().collect()))
34                }
35            })
36            .collect();
37        Self {
38            format_version: Self::FORMAT_VERSION,
39            importers,
40        }
41    }
42
43    /// Invert source → dependencies into a file → importers index.
44    pub fn from_dependencies(dependencies: &BTreeMap<String, BTreeSet<String>>) -> Self {
45        let mut importers = BTreeMap::<String, BTreeSet<String>>::new();
46        for (source, deps) in dependencies {
47            for dep in deps {
48                importers
49                    .entry(dep.clone())
50                    .or_default()
51                    .insert(source.clone());
52            }
53        }
54        Self::new(importers)
55    }
56
57    /// Look up the files that import `path`.
58    pub fn importers_of(&self, path: &str) -> &[String] {
59        self.importers
60            .get(path)
61            .map(Vec::as_slice)
62            .unwrap_or_default()
63    }
64
65    /// Encode this index as named MessagePack.
66    pub fn encode(&self) -> Result<Vec<u8>, SemanticIndexError> {
67        rmp_serde::to_vec_named(self).map_err(|err| SemanticIndexError::Encoding(err.to_string()))
68    }
69
70    /// Decode and version-check a reverse-dependency index.
71    pub fn decode(bytes: &[u8]) -> Result<Self, SemanticIndexError> {
72        let index: Self = rmp_serde::from_slice(bytes)
73            .map_err(|err| SemanticIndexError::Encoding(err.to_string()))?;
74        if index.format_version != Self::FORMAT_VERSION {
75            return Err(SemanticIndexError::UnsupportedVersion(index.format_version));
76        }
77        Ok(index)
78    }
79}
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84
85    #[test]
86    fn index_roundtrips_and_drops_empty_importer_sets() {
87        let index = ReverseDependencyIndex::from_dependencies(&BTreeMap::from([
88            (
89                "b.rs".to_string(),
90                BTreeSet::from(["a.rs".to_string(), "a.rs".to_string()]),
91            ),
92            ("c.rs".to_string(), BTreeSet::from(["b.rs".to_string()])),
93            ("d.rs".to_string(), BTreeSet::new()),
94        ]));
95
96        assert_eq!(index.importers_of("a.rs"), ["b.rs"]);
97        assert_eq!(index.importers_of("b.rs"), ["c.rs"]);
98        assert!(index.importers_of("d.rs").is_empty());
99        assert_eq!(
100            ReverseDependencyIndex::decode(&index.encode().unwrap()).unwrap(),
101            index
102        );
103    }
104}
heddle_object_model/object/semantic_reverse_deps.rs

heddle_object_model/object/
semantic_reverse_deps.rs
