harn_hostlib/code_index/
graph.rs

1//! Forward + reverse dependency graph over project files.
2//!
3//! Edges are "file A imports file B", built from the import strings the
4//! `imports` module surfaces. Forward answers "what does A depend on?";
5//! reverse answers "who depends on A?". Mirrors the Swift `DepGraph`,
6//! including the `unresolved_imports` side-table for raw strings the
7//! resolver could not map back to a known file.
8
9use std::collections::{HashMap, HashSet};
10
11use super::file_table::FileId;
12
13/// Forward + reverse import graph plus the side-table of unresolved
14/// import strings (raw text we couldn't map back to a known file).
15#[derive(Debug, Default, Clone)]
16pub struct DepGraph {
17    forward: HashMap<FileId, HashSet<FileId>>,
18    reverse: HashMap<FileId, HashSet<FileId>>,
19    unresolved: HashMap<FileId, Vec<String>>,
20}
21
22impl DepGraph {
23    /// Construct an empty graph.
24    pub fn new() -> Self {
25        Self::default()
26    }
27
28    /// Replace the outgoing edges for `file` with the resolved set.
29    /// Re-keys reverse edges atomically so `imports`/`importers` stay in
30    /// sync after every call.
31    pub fn set_edges(&mut self, file: FileId, resolved: HashSet<FileId>, unresolved: Vec<String>) {
32        if let Some(old) = self.forward.remove(&file) {
33            for target in &old {
34                if *target == file {
35                    continue;
36                }
37                if let Some(set) = self.reverse.get_mut(target) {
38                    set.remove(&file);
39                    if set.is_empty() {
40                        self.reverse.remove(target);
41                    }
42                }
43            }
44        }
45        for target in &resolved {
46            if *target == file {
47                continue;
48            }
49            self.reverse.entry(*target).or_default().insert(file);
50        }
51        self.forward.insert(file, resolved);
52        if unresolved.is_empty() {
53            self.unresolved.remove(&file);
54        } else {
55            self.unresolved.insert(file, unresolved);
56        }
57    }
58
59    /// Drop every edge touching `file` from both directions. Importers
60    /// of `file` keep their forward entry but lose the dangling target.
61    pub fn remove_file(&mut self, file: FileId) {
62        if let Some(old) = self.forward.remove(&file) {
63            for target in old {
64                if target == file {
65                    continue;
66                }
67                if let Some(set) = self.reverse.get_mut(&target) {
68                    set.remove(&file);
69                    if set.is_empty() {
70                        self.reverse.remove(&target);
71                    }
72                }
73            }
74        }
75        self.unresolved.remove(&file);
76        // Anyone who imported us keeps their forward edge but it now
77        // dangles. They'll re-resolve on their next reindex.
78        if let Some(rev) = self.reverse.remove(&file) {
79            for importer in rev {
80                if let Some(forward) = self.forward.get_mut(&importer) {
81                    forward.remove(&file);
82                }
83            }
84        }
85    }
86
87    /// Forward edges: every file `file` imports.
88    pub fn imports_of(&self, file: FileId) -> Vec<FileId> {
89        self.forward
90            .get(&file)
91            .map(|set| set.iter().copied().collect())
92            .unwrap_or_default()
93    }
94
95    /// Reverse edges: every file that imports `file`.
96    pub fn importers_of(&self, file: FileId) -> Vec<FileId> {
97        self.reverse
98            .get(&file)
99            .map(|set| set.iter().copied().collect())
100            .unwrap_or_default()
101    }
102
103    /// Raw import strings the resolver couldn't map back to a known file.
104    pub fn unresolved_imports(&self, file: FileId) -> &[String] {
105        self.unresolved.get(&file).map(Vec::as_slice).unwrap_or(&[])
106    }
107}
108
109#[cfg(test)]
110mod tests {
111    use super::*;
112
113    fn set_of(ids: &[FileId]) -> HashSet<FileId> {
114        ids.iter().copied().collect()
115    }
116
117    #[test]
118    fn set_edges_populates_both_sides() {
119        let mut g = DepGraph::new();
120        g.set_edges(1, set_of(&[2, 3]), vec![]);
121        let mut imports = g.imports_of(1);
122        imports.sort();
123        assert_eq!(imports, vec![2, 3]);
124        assert_eq!(g.importers_of(2), vec![1]);
125        assert_eq!(g.importers_of(3), vec![1]);
126    }
127
128    #[test]
129    fn re_setting_edges_drops_stale_reverse_edges() {
130        let mut g = DepGraph::new();
131        g.set_edges(1, set_of(&[2]), vec![]);
132        g.set_edges(1, set_of(&[3]), vec![]);
133        assert!(g.importers_of(2).is_empty());
134        assert_eq!(g.importers_of(3), vec![1]);
135    }
136
137    #[test]
138    fn remove_file_cleans_up_both_directions() {
139        let mut g = DepGraph::new();
140        g.set_edges(1, set_of(&[2]), vec!["unmatched".into()]);
141        g.set_edges(3, set_of(&[1]), vec![]);
142        g.remove_file(1);
143        assert!(g.imports_of(1).is_empty());
144        assert!(g.importers_of(2).is_empty());
145        // 3 still imports... nothing now (its forward edge dangling-cleared).
146        assert!(g.imports_of(3).is_empty());
147    }
148
149    #[test]
150    fn unresolved_imports_round_trip() {
151        let mut g = DepGraph::new();
152        g.set_edges(1, HashSet::new(), vec!["weird::path".into()]);
153        assert_eq!(g.unresolved_imports(1), &["weird::path".to_string()]);
154        g.set_edges(1, HashSet::new(), vec![]);
155        assert!(g.unresolved_imports(1).is_empty());
156    }
157}
harn_hostlib/code_index/graph.rs

harn_hostlib/code_index/
graph.rs
