gonzalo_graph/
diff.rs

1//! Structural diff between two assembled views (ticket K).
2//!
3//! Given two [`GraphStore`]s — e.g. two competing worktrees over the same slice
4//! store — [`diff`] reports which symbols and references were **added** (in `b`,
5//! not `a`) or **removed** (in `a`, not `b`). Identity is structural, not
6//! positional: a symbol is `(path, name, kind)` and a reference is
7//! `(path, from, name)`, so line shifts do not register as changes.
8
9use crate::{GraphStore, Located, Reference, Symbol, SymbolKind};
10use serde::{Deserialize, Serialize};
11use std::collections::HashSet;
12
13/// The structural difference between two views (`a` → `b`).
14#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
15pub struct GraphDiff {
16    /// Symbols in `b` but not `a`.
17    pub added_symbols: Vec<Located<Symbol>>,
18    /// Symbols in `a` but not `b`.
19    pub removed_symbols: Vec<Located<Symbol>>,
20    /// References in `b` but not `a`.
21    pub added_references: Vec<Located<Reference>>,
22    /// References in `a` but not `b`.
23    pub removed_references: Vec<Located<Reference>>,
24}
25
26impl GraphDiff {
27    /// Whether the two views are structurally identical.
28    pub fn is_empty(&self) -> bool {
29        self.added_symbols.is_empty()
30            && self.removed_symbols.is_empty()
31            && self.added_references.is_empty()
32            && self.removed_references.is_empty()
33    }
34}
35
36type SymbolKey = (String, String, SymbolKind);
37type ReferenceKey = (String, Option<String>, String);
38
39fn symbol_key(l: &Located<Symbol>) -> SymbolKey {
40    (l.path.clone(), l.item.name.clone(), l.item.kind)
41}
42
43fn reference_key(l: &Located<Reference>) -> ReferenceKey {
44    (l.path.clone(), l.item.from.clone(), l.item.name.clone())
45}
46
47/// Diff view `a` against view `b`: what `b` adds and what it removes.
48pub fn diff(a: &dyn GraphStore, b: &dyn GraphStore) -> GraphDiff {
49    let (a_syms, b_syms) = (a.all_symbols(), b.all_symbols());
50    let (a_refs, b_refs) = (a.all_references(), b.all_references());
51
52    let a_sym_keys: HashSet<SymbolKey> = a_syms.iter().map(symbol_key).collect();
53    let b_sym_keys: HashSet<SymbolKey> = b_syms.iter().map(symbol_key).collect();
54    let a_ref_keys: HashSet<ReferenceKey> = a_refs.iter().map(reference_key).collect();
55    let b_ref_keys: HashSet<ReferenceKey> = b_refs.iter().map(reference_key).collect();
56
57    GraphDiff {
58        added_symbols: dedup_by_key(b_syms, |l| !a_sym_keys.contains(&symbol_key(l)), symbol_key),
59        removed_symbols: dedup_by_key(a_syms, |l| !b_sym_keys.contains(&symbol_key(l)), symbol_key),
60        added_references: dedup_by_key(
61            b_refs,
62            |l| !a_ref_keys.contains(&reference_key(l)),
63            reference_key,
64        ),
65        removed_references: dedup_by_key(
66            a_refs,
67            |l| !b_ref_keys.contains(&reference_key(l)),
68            reference_key,
69        ),
70    }
71}
72
73/// Keep items matching `keep`, deduplicated by `key` (first occurrence wins).
74fn dedup_by_key<T, K: std::hash::Hash + Eq>(
75    items: Vec<T>,
76    keep: impl Fn(&T) -> bool,
77    key: impl Fn(&T) -> K,
78) -> Vec<T> {
79    let mut seen = HashSet::new();
80    items
81        .into_iter()
82        .filter(|it| keep(it) && seen.insert(key(it)))
83        .collect()
84}
85
86#[cfg(test)]
87mod tests {
88    use super::*;
89    use crate::{InMemoryGraphStore, build_rust};
90
91    fn store(files: &[(&str, &str)]) -> InMemoryGraphStore {
92        let mut s = InMemoryGraphStore::new();
93        for (path, src) in files {
94            s.insert(path, build_rust(src));
95        }
96        s
97    }
98
99    #[test]
100    fn identical_views_have_no_diff() {
101        let a = store(&[("lib.rs", "fn a() {}\nfn b() { a(); }")]);
102        let b = store(&[("lib.rs", "fn a() {}\nfn b() { a(); }")]);
103        assert!(diff(&a, &b).is_empty());
104    }
105
106    #[test]
107    fn reports_added_and_removed_symbols() {
108        let a = store(&[("lib.rs", "fn keep() {}\nfn gone() {}")]);
109        let b = store(&[("lib.rs", "fn keep() {}\nfn fresh() {}")]);
110        let d = diff(&a, &b);
111
112        let added: Vec<&str> = d
113            .added_symbols
114            .iter()
115            .map(|l| l.item.name.as_str())
116            .collect();
117        let removed: Vec<&str> = d
118            .removed_symbols
119            .iter()
120            .map(|l| l.item.name.as_str())
121            .collect();
122        assert_eq!(added, vec!["fresh"]);
123        assert_eq!(removed, vec!["gone"]);
124    }
125
126    #[test]
127    fn reports_added_and_removed_references() {
128        let a = store(&[("lib.rs", "fn f() {}\nfn caller() { f(); }")]);
129        // caller now calls g() instead of f().
130        let b = store(&[("lib.rs", "fn f() {}\nfn g() {}\nfn caller() { g(); }")]);
131        let d = diff(&a, &b);
132
133        assert!(d.added_references.iter().any(|l| l.item.name == "g"));
134        assert!(d.removed_references.iter().any(|l| l.item.name == "f"));
135        // `g` is an added symbol; `f` still exists (not removed).
136        assert!(d.added_symbols.iter().any(|l| l.item.name == "g"));
137        assert!(!d.removed_symbols.iter().any(|l| l.item.name == "f"));
138    }
139
140    #[test]
141    fn moving_a_symbol_across_files_is_add_plus_remove() {
142        let a = store(&[("a.rs", "fn moved() {}"), ("b.rs", "")]);
143        let b = store(&[("a.rs", ""), ("b.rs", "fn moved() {}")]);
144        let d = diff(&a, &b);
145        assert_eq!(d.added_symbols.len(), 1);
146        assert_eq!(d.added_symbols[0].path, "b.rs");
147        assert_eq!(d.removed_symbols.len(), 1);
148        assert_eq!(d.removed_symbols[0].path, "a.rs");
149    }
150
151    #[test]
152    fn line_shift_is_not_a_change() {
153        let a = store(&[("lib.rs", "fn a() {}")]);
154        // Same symbol, different line.
155        let b = store(&[("lib.rs", "\n\nfn a() {}")]);
156        assert!(diff(&a, &b).is_empty());
157    }
158}
gonzalo_graph/diff.rs

gonzalo_graph/
diff.rs
