lex_vcs/
compute_diff.rs

1//! AST-level structural diff between two sets of `FnDecl`s.
2//!
3//! Moved from `lex-cli/src/diff.rs` so both the CLI (`lex diff`
4//! command) and the HTTP API (`lex serve`) can compute a [`DiffReport`]
5//! without introducing a circular dependency. `lex-vcs` is the right
6//! home because it already owns `DiffReport` and `diff_to_ops`.
7
8use crate::diff_report::{
9    AddRemove, BodyPatch, DiffReport, EffectChanges, Modified, Renamed,
10};
11use lex_ast::{stage_canonical_hash_hex, CExpr, Effect, EffectArg, FnDecl, Stage, TypeDecl, TypeExpr};
12use std::collections::{BTreeMap, BTreeSet, HashMap};
13
14/// Compute a structural diff between two named fn-decl maps.
15///
16/// `body_patches` controls whether body-level expression diffs are
17/// emitted inside each `Modified` entry. Pass `true` for rich output
18/// (CLI / review); `false` for a signature-only diff (faster).
19///
20/// Function-only: type declarations are not considered. Use
21/// [`compute_diff_with_types`] on the publish path, where the op log
22/// must capture `type` declarations too (else `export-git` cannot
23/// reproduce a compilable module — see alpibrusl/lex-lang#895).
24pub fn compute_diff(
25    a: &BTreeMap<String, FnDecl>,
26    b: &BTreeMap<String, FnDecl>,
27    body_patches: bool,
28) -> DiffReport {
29    compute_diff_with_types(a, b, &BTreeMap::new(), &BTreeMap::new(), body_patches)
30}
31
32/// Like [`compute_diff`], but also diffs top-level `type` declarations,
33/// emitting added / removed / modified entries for them so `diff_to_ops`
34/// produces `AddType` / `RemoveType` / `ModifyType` ops. A type's
35/// `signature` is rendered `type Name = …` (the `"type "` prefix is how
36/// `diff_to_ops` tells a type removal from a function removal), and its
37/// `old_sig_id` is the `SigId` of the old `TypeDecl` stage. Rename
38/// detection is intentionally function-only; a renamed type reads as a
39/// remove + add, which reproduces it correctly.
40pub fn compute_diff_with_types(
41    a: &BTreeMap<String, FnDecl>,
42    b: &BTreeMap<String, FnDecl>,
43    a_types: &BTreeMap<String, TypeDecl>,
44    b_types: &BTreeMap<String, TypeDecl>,
45    body_patches: bool,
46) -> DiffReport {
47    let mut report = DiffReport::default();
48    let names_a: BTreeSet<&String> = a.keys().collect();
49    let names_b: BTreeSet<&String> = b.keys().collect();
50
51    let only_a: Vec<&String> = names_a.difference(&names_b).copied().collect();
52    let only_b: Vec<&String> = names_b.difference(&names_a).copied().collect();
53
54    // Detect renames: for each name only-in-A, check if any only-in-B
55    // has a body whose canonical-AST hash matches (modulo the fn
56    // name itself). sig_id over the FnDecl with name normalized
57    // serves as the structural-identity key.
58    //
59    // `body_hash` clones the FnDecl and does a full canonical
60    // serialize + SHA-256 — not O(1). The naive nested loop below
61    // used to recompute `body_hash(fb)` on every outer (`only_a`)
62    // iteration even though `fb` never changes, making this
63    // O(|only_a| * |only_b|) hashes instead of O(|only_a| + |only_b|).
64    // Harmless at the tiny scale these sets used to have, but
65    // `pkg_publish_handler` calls this once per uploaded file with
66    // `only_a` sized to the *entire* tenant's historical function
67    // set — that combination hung the server for 38+ minutes on a
68    // real publish (alpibrusl/lex-lang#813). Precomputing each
69    // `only_b` hash once turns the nested loop into O(1) lookups.
70    let mut hash_to_bs: HashMap<String, Vec<&String>> = HashMap::new();
71    for &bn in &only_b {
72        hash_to_bs.entry(body_hash(&b[bn])).or_default().push(bn);
73    }
74    let mut renamed_pairs: Vec<(String, String)> = Vec::new();
75    let mut consumed_a: BTreeSet<String> = BTreeSet::new();
76    let mut consumed_b: BTreeSet<String> = BTreeSet::new();
77    for &an in &only_a {
78        let fa = &a[an];
79        let fa_norm_id = body_hash(fa);
80        let Some(candidates) = hash_to_bs.get(&fa_norm_id) else { continue };
81        let Some(&bn) = candidates.iter().find(|bn| !consumed_b.contains(**bn)) else { continue };
82        renamed_pairs.push((an.clone(), bn.clone()));
83        consumed_a.insert(an.clone());
84        consumed_b.insert(bn.clone());
85    }
86
87    for &n in &only_a {
88        if consumed_a.contains(n) { continue; }
89        let fd = &a[n];
90        report.removed.push(AddRemove {
91            name: n.clone(),
92            signature: render_signature(fd),
93            old_sig_id: lex_ast::sig_id(&Stage::FnDecl(fd.clone())),
94        });
95    }
96    for &n in &only_b {
97        if consumed_b.contains(n) { continue; }
98        let fd = &b[n];
99        report.added.push(AddRemove {
100            name: n.clone(),
101            signature: render_signature(fd),
102            old_sig_id: None,
103        });
104    }
105    for (an, bn) in &renamed_pairs {
106        let fa = &a[an];
107        let fd = &b[bn];
108        report.renamed.push(Renamed {
109            from: an.clone(),
110            to: bn.clone(),
111            signature: render_signature(fd),
112            old_sig_id: lex_ast::sig_id(&Stage::FnDecl(fa.clone())).unwrap_or_default(),
113        });
114    }
115
116    // Modified: same name on both sides; compare bodies.
117    for n in names_a.intersection(&names_b) {
118        let fa = &a[*n];
119        let fb = &b[*n];
120        let sig_a = render_signature(fa);
121        let sig_b = render_signature(fb);
122        if body_hash(fa) == body_hash(fb) && sig_a == sig_b { continue; }
123
124        let patches = if body_patches {
125            let mut patches = Vec::new();
126            diff_expr(&fa.body, &fb.body, "body", &mut patches, 4);
127            patches
128        } else { Vec::new() };
129
130        let effect_changes = effect_diff(&fa.effects, &fb.effects);
131        report.modified.push(Modified {
132            name: (*n).clone(),
133            signature_before: sig_a.clone(),
134            signature_after: sig_b.clone(),
135            signature_changed: sig_a != sig_b,
136            effect_changes,
137            body_patches: patches,
138            old_sig_id: lex_ast::sig_id(&Stage::FnDecl(fa.clone())).unwrap_or_default(),
139        });
140    }
141
142    // Types. Added / removed by name; a same-name pair whose canonical
143    // hash differs is a modification (its `SigId` — name + type params,
144    // not the definition — stays put across a body change). A pair whose
145    // `SigId` differs too (e.g. gained a type parameter) reads as a
146    // remove + add, since the old sig can't be `ModifyType`d into the new
147    // one. No rename detection for types (rare; remove + add reproduces).
148    let tnames_a: BTreeSet<&String> = a_types.keys().collect();
149    let tnames_b: BTreeSet<&String> = b_types.keys().collect();
150    for n in tnames_a.difference(&tnames_b) {
151        let td = &a_types[*n];
152        report.removed.push(AddRemove {
153            name: (*n).clone(),
154            signature: render_type_signature(td),
155            old_sig_id: lex_ast::sig_id(&Stage::TypeDecl(td.clone())),
156        });
157    }
158    for n in tnames_b.difference(&tnames_a) {
159        let td = &b_types[*n];
160        report.added.push(AddRemove {
161            name: (*n).clone(),
162            signature: render_type_signature(td),
163            old_sig_id: None,
164        });
165    }
166    for n in tnames_a.intersection(&tnames_b) {
167        let ta = &a_types[*n];
168        let tb = &b_types[*n];
169        let hash_a = stage_canonical_hash_hex(&Stage::TypeDecl(ta.clone()));
170        let hash_b = stage_canonical_hash_hex(&Stage::TypeDecl(tb.clone()));
171        if hash_a == hash_b { continue; }
172        let sig_a = lex_ast::sig_id(&Stage::TypeDecl(ta.clone()));
173        let sig_b = lex_ast::sig_id(&Stage::TypeDecl(tb.clone()));
174        if sig_a != sig_b {
175            // Structural identity changed (type params): can't modify in
176            // place — drop the old, introduce the new.
177            report.removed.push(AddRemove {
178                name: (*n).clone(),
179                signature: render_type_signature(ta),
180                old_sig_id: sig_a,
181            });
182            report.added.push(AddRemove {
183                name: (*n).clone(),
184                signature: render_type_signature(tb),
185                old_sig_id: None,
186            });
187        } else {
188            report.modified.push(Modified {
189                name: (*n).clone(),
190                signature_before: render_type_signature(ta),
191                signature_after: render_type_signature(tb),
192                signature_changed: true,
193                effect_changes: EffectChanges::default(),
194                body_patches: Vec::new(),
195                old_sig_id: sig_a.unwrap_or_default(),
196            });
197        }
198    }
199    report
200}
201
202/// Hash of the function's structural identity, used for rename
203/// detection. Excludes the function's name (so `fn foo -> Int { 1 }`
204/// and `fn bar -> Int { 1 }` share a hash) but includes everything
205/// else: params, effects, return type, body.
206fn body_hash(fd: &FnDecl) -> String {
207    let mut anon = fd.clone();
208    anon.name = String::new();
209    let stage = Stage::FnDecl(anon);
210    stage_canonical_hash_hex(&stage)
211}
212
213/// Walk two CExprs in parallel; record the first divergence at each
214/// child position. `depth` caps recursion so a tiny per-fn diff
215/// doesn't degenerate into hundreds of micro-changes.
216fn diff_expr(a: &CExpr, b: &CExpr, path: &str, out: &mut Vec<BodyPatch>, depth: u32) {
217    if depth == 0 { return; }
218    let kind_a = node_kind(a);
219    let kind_b = node_kind(b);
220    if kind_a != kind_b {
221        out.push(BodyPatch {
222            op: "Replace".into(), node_path: path.into(),
223            from_kind: kind_a.into(), to_kind: kind_b.into(),
224        });
225        return;
226    }
227    // Same kind: recurse into structurally-equivalent children.
228    match (a, b) {
229        (CExpr::Literal { value: la }, CExpr::Literal { value: lb }) => {
230            if la != lb {
231                out.push(BodyPatch {
232                    op: "Replace".into(), node_path: path.into(),
233                    from_kind: "Literal".into(), to_kind: "Literal".into(),
234                });
235            }
236        }
237        (CExpr::Var { name: na }, CExpr::Var { name: nb }) => {
238            if na != nb {
239                out.push(BodyPatch {
240                    op: "Replace".into(), node_path: path.into(),
241                    from_kind: format!("Var({na})"), to_kind: format!("Var({nb})"),
242                });
243            }
244        }
245        (CExpr::Call { callee: ca, args: aa },
246         CExpr::Call { callee: cb, args: ab }) => {
247            diff_expr(ca, cb, &format!("{path}.callee"), out, depth - 1);
248            diff_args(aa, ab, &format!("{path}.args"), out, depth);
249        }
250        (CExpr::Let { name: na, value: va, body: ba, .. },
251         CExpr::Let { name: nb, value: vb, body: bb, .. }) => {
252            if na != nb {
253                out.push(BodyPatch {
254                    op: "Replace".into(),
255                    node_path: format!("{path}.name"),
256                    from_kind: format!("Let({na})"),
257                    to_kind:   format!("Let({nb})"),
258                });
259            }
260            diff_expr(va, vb, &format!("{path}.value"), out, depth - 1);
261            diff_expr(ba, bb, &format!("{path}.body"),  out, depth - 1);
262        }
263        (CExpr::Match { scrutinee: sa, arms: ams },
264         CExpr::Match { scrutinee: sb, arms: bms }) => {
265            diff_expr(sa, sb, &format!("{path}.scrutinee"), out, depth - 1);
266            let n = ams.len().max(bms.len());
267            for i in 0..n {
268                let p = format!("{path}.arms[{i}]");
269                match (ams.get(i), bms.get(i)) {
270                    (Some(a), Some(b)) =>
271                        diff_expr(&a.body, &b.body, &p, out, depth - 1),
272                    (Some(_), None) => out.push(BodyPatch {
273                        op: "Deleted".into(), node_path: p,
274                        from_kind: "MatchArm".into(), to_kind: "(removed)".into(),
275                    }),
276                    (None, Some(_)) => out.push(BodyPatch {
277                        op: "Inserted".into(), node_path: p,
278                        from_kind: "(none)".into(), to_kind: "MatchArm".into(),
279                    }),
280                    (None, None) => break,
281                }
282            }
283        }
284        (CExpr::Block { statements: sa, result: ra },
285         CExpr::Block { statements: sb, result: rb }) => {
286            diff_args(sa, sb, &format!("{path}.statements"), out, depth);
287            diff_expr(ra, rb, &format!("{path}.result"), out, depth - 1);
288        }
289        (CExpr::FieldAccess { value: va, field: fa },
290         CExpr::FieldAccess { value: vb, field: fb }) => {
291            diff_expr(va, vb, &format!("{path}.value"), out, depth - 1);
292            if fa != fb {
293                out.push(BodyPatch {
294                    op: "Replace".into(), node_path: format!("{path}.field"),
295                    from_kind: format!("Field({fa})"), to_kind: format!("Field({fb})"),
296                });
297            }
298        }
299        (CExpr::Lambda { body: ba, .. }, CExpr::Lambda { body: bb, .. }) => {
300            diff_expr(ba, bb, &format!("{path}.body"), out, depth - 1);
301        }
302        // For shapes we don't unfold further, mark the node itself
303        // as edited (same kind, content differs) — finer detail can
304        // come in a follow-up.
305        _ => {
306            out.push(BodyPatch {
307                op: "Replace".into(), node_path: path.into(),
308                from_kind: kind_a.into(), to_kind: kind_b.into(),
309            });
310        }
311    }
312}
313
314fn diff_args(a: &[CExpr], b: &[CExpr], path: &str, out: &mut Vec<BodyPatch>, depth: u32) {
315    let n = a.len().max(b.len());
316    for i in 0..n {
317        let p = format!("{path}[{i}]");
318        match (a.get(i), b.get(i)) {
319            (Some(x), Some(y)) => diff_expr(x, y, &p, out, depth - 1),
320            (Some(x), None) => out.push(BodyPatch {
321                op: "Deleted".into(), node_path: p,
322                from_kind: node_kind(x).into(), to_kind: "(removed)".into(),
323            }),
324            (None, Some(y)) => out.push(BodyPatch {
325                op: "Inserted".into(), node_path: p,
326                from_kind: "(none)".into(), to_kind: node_kind(y).into(),
327            }),
328            (None, None) => break,
329        }
330    }
331}
332
333fn node_kind(e: &CExpr) -> &'static str {
334    match e {
335        CExpr::Literal { .. }     => "Literal",
336        CExpr::Var { .. }         => "Var",
337        CExpr::Call { .. }        => "Call",
338        CExpr::Let { .. }         => "Let",
339        CExpr::Match { .. }       => "Match",
340        CExpr::Block { .. }       => "Block",
341        CExpr::Constructor { .. } => "Constructor",
342        CExpr::RecordLit { .. }   => "RecordLit",
343        CExpr::TupleLit { .. }    => "TupleLit",
344        CExpr::ListLit { .. }     => "ListLit",
345        CExpr::FieldAccess { .. } => "FieldAccess",
346        CExpr::Lambda { .. }      => "Lambda",
347        CExpr::BinOp { .. }       => "BinOp",
348        CExpr::UnaryOp { .. }     => "UnaryOp",
349        CExpr::Return { .. }      => "Return",
350    }
351}
352
353pub fn render_signature(fd: &FnDecl) -> String {
354    let params: Vec<String> = fd.params.iter()
355        .map(|p| format!("{} :: {}", p.name, render_type(&p.ty))).collect();
356    let eff = if fd.effects.is_empty() { String::new() } else {
357        let labels: Vec<String> = fd.effects.iter().map(effect_label).collect();
358        format!("[{}] ", labels.join(", "))
359    };
360    format!("fn {}({}) -> {}{}", fd.name, params.join(", "),
361        eff, render_type(&fd.return_type))
362}
363
364/// Render a type declaration's signature. The leading `type ` is
365/// load-bearing: `diff_to_ops` classifies a removal as `RemoveType`
366/// vs `RemoveFunction` by testing `signature.starts_with("type ")`.
367pub fn render_type_signature(td: &TypeDecl) -> String {
368    let params = if td.params.is_empty() {
369        String::new()
370    } else {
371        format!("[{}]", td.params.join(", "))
372    };
373    format!("type {}{} = {}", td.name, params, render_type(&td.definition))
374}
375
376/// Render an effect with its arg if present: `fs_read("/tmp")`,
377/// `net("api.example.com")`, or just `io`. Used by both signature
378/// rendering and effect-diff so the same string identifies the
379/// same effect in either context.
380pub fn effect_label(e: &Effect) -> String {
381    match &e.arg {
382        Some(EffectArg::Str { value })   => format!("{}({:?})", e.name, value),
383        Some(EffectArg::Int { value })   => format!("{}({})",   e.name, value),
384        Some(EffectArg::Ident { value }) => format!("{}({})",   e.name, value),
385        None => e.name.clone(),
386    }
387}
388
389/// Set-style diff over two effect lists. Order-insensitive within
390/// the lists; ordering of the output is sorted-by-label so the
391/// JSON is stable.
392fn effect_diff(a: &[Effect], b: &[Effect]) -> EffectChanges {
393    let labels_a: BTreeSet<String> = a.iter().map(effect_label).collect();
394    let labels_b: BTreeSet<String> = b.iter().map(effect_label).collect();
395    let added:   Vec<String> = labels_b.difference(&labels_a).cloned().collect();
396    let removed: Vec<String> = labels_a.difference(&labels_b).cloned().collect();
397    EffectChanges {
398        before:  labels_a.into_iter().collect(),
399        after:   labels_b.into_iter().collect(),
400        added,
401        removed,
402    }
403}
404
405fn render_type(t: &TypeExpr) -> String {
406    match t {
407        TypeExpr::Named { name, args } => {
408            if args.is_empty() { name.clone() }
409            else {
410                let parts: Vec<String> = args.iter().map(render_type).collect();
411                format!("{name}[{}]", parts.join(", "))
412            }
413        }
414        TypeExpr::Tuple { items } => {
415            let parts: Vec<String> = items.iter().map(render_type).collect();
416            format!("({})", parts.join(", "))
417        }
418        TypeExpr::Record { fields } => {
419            let parts: Vec<String> = fields.iter()
420                .map(|f| format!("{} :: {}", f.name, render_type(&f.ty))).collect();
421            format!("{{ {} }}", parts.join(", "))
422        }
423        TypeExpr::RecordWithSpreads { spreads, fields } => {
424            let mut parts: Vec<String> = spreads.iter().map(|s| format!("...{}", s)).collect();
425            parts.extend(fields.iter().map(|f| format!("{} :: {}", f.name, render_type(&f.ty))));
426            format!("{{ {} }}", parts.join(", "))
427        }
428        TypeExpr::Function { params, effects, effect_row_var, ret } => {
429            let parts: Vec<String> = params.iter().map(render_type).collect();
430            let eff = if effects.is_empty() && effect_row_var.is_none() { String::new() } else {
431                let mut names: Vec<String> = effects.iter().map(|e| e.name.clone()).collect();
432                if let Some(v) = effect_row_var { names.push(format!("| {}", v)); }
433                format!("[{}] ", names.join(", "))
434            };
435            format!("({}) -> {}{}", parts.join(", "), eff, render_type(ret))
436        }
437        TypeExpr::Union { variants } => variants.iter().map(|v| match &v.payload {
438            Some(p) => format!("{}({})", v.name, render_type(p)),
439            None => v.name.clone(),
440        }).collect::<Vec<_>>().join(" | "),
441        TypeExpr::Refined { base, binding, .. } => {
442            // Render compactly: `Base{x | …}`. The full predicate is
443            // captured in the canonical AST and contributes to
444            // OpId hashing via lex-vcs's content-addressing — this
445            // string is for diagnostics only. (#209 slice 1)
446            format!("{}{{{} | …}}", render_type(base), binding)
447        }
448    }
449}
lex_vcs/compute_diff.rs

lex_vcs/
compute_diff.rs
