diffkit/
diff.rs

1use std::borrow::Cow;
2
3use crate::model::{CallLabel, CallNode, CallRelation, CallSiteId};
4
5#[derive(Clone, Copy, Debug, Eq, PartialEq)]
6pub enum DiffStatus {
7    Same,
8    Added,
9    Removed,
10    Modified,
11}
12
13#[derive(Clone, Debug, Eq, PartialEq)]
14pub struct DiffNode {
15    pub key: String,
16    pub callsite: Option<CallSiteId>,
17    pub label: CallLabel,
18    pub relation: CallRelation,
19    pub before_label: Option<CallLabel>,
20    pub before_relation: Option<CallRelation>,
21    pub status: DiffStatus,
22    pub children: Vec<DiffNode>,
23}
24
25pub fn diff_optional(before: Option<&CallNode>, after: Option<&CallNode>) -> Option<DiffNode> {
26    match (before, after) {
27        (Some(before), Some(after)) => Some(diff_node(Some(before), Some(after))),
28        (Some(before), None) => Some(diff_node(Some(before), None)),
29        (None, Some(after)) => Some(diff_node(None, Some(after))),
30        (None, None) => None,
31    }
32}
33
34fn diff_node(before: Option<&CallNode>, after: Option<&CallNode>) -> DiffNode {
35    match (before, after) {
36        (Some(before), Some(after)) => DiffNode {
37            key: after.key.clone(),
38            callsite: after.callsite.clone(),
39            label: after.label.clone(),
40            relation: after.relation,
41            before_label: (!labels_equivalent(&before.label.default, &after.label.default)
42                || before.relation != after.relation)
43                .then(|| before.label.clone()),
44            before_relation: (before.relation != after.relation).then_some(before.relation),
45            status: if labels_equivalent(&before.label.default, &after.label.default)
46                && before.relation == after.relation
47            {
48                DiffStatus::Same
49            } else {
50                DiffStatus::Modified
51            },
52            children: diff_children(&before.children, &after.children),
53        },
54        (None, Some(after)) => mark_tree(after, DiffStatus::Added),
55        (Some(before), None) => mark_tree(before, DiffStatus::Removed),
56        (None, None) => unreachable!("diff_node requires at least one node"),
57    }
58}
59
60fn mark_tree(node: &CallNode, status: DiffStatus) -> DiffNode {
61    DiffNode {
62        key: node.key.clone(),
63        callsite: node.callsite.clone(),
64        label: node.label.clone(),
65        relation: node.relation,
66        before_label: None,
67        before_relation: None,
68        status,
69        children: node
70            .children
71            .iter()
72            .map(|child| mark_tree(child, status))
73            .collect(),
74    }
75}
76
77fn diff_children(before: &[CallNode], after: &[CallNode]) -> Vec<DiffNode> {
78    let n = before.len();
79    let m = after.len();
80    if n == m
81        && before
82            .iter()
83            .zip(after)
84            .all(|(before, after)| nodes_equivalent(before, after))
85    {
86        return before
87            .iter()
88            .zip(after)
89            .map(|(before, after)| diff_node(Some(before), Some(after)))
90            .collect();
91    }
92    let before_alignment = before.iter().map(AlignmentNode::new).collect::<Vec<_>>();
93    let after_alignment = after.iter().map(AlignmentNode::new).collect::<Vec<_>>();
94    let width = m + 1;
95    let mut score = vec![0usize; (n + 1).saturating_mul(width)];
96
97    for i in (0..n).rev() {
98        for j in (0..m).rev() {
99            let matched = alignment_weight(&before_alignment[i], &after_alignment[j])
100                .map(|weight| score[(i + 1) * width + j + 1] + weight)
101                .unwrap_or_default();
102            score[i * width + j] = matched
103                .max(score[(i + 1) * width + j])
104                .max(score[i * width + j + 1]);
105        }
106    }
107
108    let mut result = Vec::new();
109    let (mut i, mut j) = (0, 0);
110    while i < n && j < m {
111        let matched = alignment_weight(&before_alignment[i], &after_alignment[j])
112            .map(|weight| score[(i + 1) * width + j + 1] + weight);
113        if matched == Some(score[i * width + j]) {
114            result.push(diff_node(Some(&before[i]), Some(&after[j])));
115            i += 1;
116            j += 1;
117        } else if score[(i + 1) * width + j] >= score[i * width + j + 1] {
118            result.push(diff_node(Some(&before[i]), None));
119            i += 1;
120        } else {
121            result.push(diff_node(None, Some(&after[j])));
122            j += 1;
123        }
124    }
125    while i < n {
126        result.push(diff_node(Some(&before[i]), None));
127        i += 1;
128    }
129    while j < m {
130        result.push(diff_node(None, Some(&after[j])));
131        j += 1;
132    }
133    result
134}
135
136struct AlignmentNode<'a> {
137    node: &'a CallNode,
138    key: Cow<'a, str>,
139    label: Cow<'a, str>,
140}
141
142impl<'a> AlignmentNode<'a> {
143    fn new(node: &'a CallNode) -> Self {
144        Self {
145            node,
146            key: normalize_anonymous_lambda_keys(&node.key),
147            label: normalize_anonymous_lambdas(&node.label.default),
148        }
149    }
150}
151
152pub(crate) fn nodes_equivalent(before: &CallNode, after: &CallNode) -> bool {
153    semantic_keys_equivalent(&before.key, &after.key)
154        && labels_equivalent(&before.label.default, &after.label.default)
155        && before.relation == after.relation
156        && before.children.len() == after.children.len()
157        && before
158            .children
159            .iter()
160            .zip(&after.children)
161            .all(|(before, after)| nodes_equivalent(before, after))
162}
163
164/// Prefer unchanged source labels and shallow call shape while still allowing
165/// a modified call to align by semantic target. `CallSiteId` currently embeds
166/// absolute source coordinates, so it must not influence cross-revision
167/// alignment: inserting a line can otherwise pair every repeated call with the
168/// following occurrence.
169fn alignment_weight(before: &AlignmentNode<'_>, after: &AlignmentNode<'_>) -> Option<usize> {
170    if before.key != after.key {
171        return None;
172    }
173    let mut weight = 10usize;
174    if before.node.label.default == after.node.label.default
175        && !before.node.label.default.contains("λ#")
176    {
177        weight += 100;
178    } else if before.label == after.label {
179        weight += 80;
180    }
181    if before.node.relation == after.node.relation {
182        weight += 5;
183    }
184    if same_shallow_children(before.node, after.node) {
185        weight += 25;
186    }
187    weight += matching_descendant_weight(before.node, after.node, 2).min(100);
188    Some(weight)
189}
190
191fn semantic_keys_equivalent(before: &str, after: &str) -> bool {
192    before == after
193        || normalize_anonymous_lambda_keys(before) == normalize_anonymous_lambda_keys(after)
194}
195
196fn normalize_anonymous_lambda_keys(key: &str) -> Cow<'_, str> {
197    if !key.contains("{lambda:") {
198        return Cow::Borrowed(key);
199    }
200    let mut normalized = String::with_capacity(key.len());
201    let mut remainder = key;
202    while let Some(start) = remainder.find("{lambda:") {
203        normalized.push_str(&remainder[..start]);
204        normalized.push_str("{lambda}");
205        let located = &remainder[start..];
206        let Some(end) = located.find('}') else {
207            normalized.push_str(located);
208            return Cow::Owned(normalized);
209        };
210        remainder = &located[end + 1..];
211    }
212    normalized.push_str(remainder);
213    Cow::Owned(normalized)
214}
215
216fn labels_equivalent(before: &str, after: &str) -> bool {
217    before == after || normalize_anonymous_lambdas(before) == normalize_anonymous_lambdas(after)
218}
219
220fn normalize_anonymous_lambdas(label: &str) -> Cow<'_, str> {
221    if !label.contains("λ#") {
222        return Cow::Borrowed(label);
223    }
224    let mut normalized = String::with_capacity(label.len());
225    let mut rest = label;
226    while let Some(index) = rest.find("λ#") {
227        normalized.push_str(&rest[..index + "λ#".len()]);
228        rest = &rest[index + "λ#".len()..];
229        let digits = rest.chars().take_while(char::is_ascii_digit).count();
230        rest = &rest[digits..];
231    }
232    normalized.push_str(rest);
233    Cow::Owned(normalized)
234}
235
236fn same_shallow_children(before: &CallNode, after: &CallNode) -> bool {
237    before.children.len() == after.children.len()
238        && before
239            .children
240            .iter()
241            .zip(&after.children)
242            .all(|(before, after)| {
243                semantic_keys_equivalent(&before.key, &after.key)
244                    && labels_equivalent(&before.label.default, &after.label.default)
245            })
246}
247
248fn matching_descendant_weight(before: &CallNode, after: &CallNode, depth: usize) -> usize {
249    if depth == 0 || before.children.len() != after.children.len() {
250        return 0;
251    }
252    before
253        .children
254        .iter()
255        .zip(&after.children)
256        .map(|(before, after)| {
257            if !semantic_keys_equivalent(&before.key, &after.key) {
258                return 0;
259            }
260            10 + usize::from(labels_equivalent(
261                &before.label.default,
262                &after.label.default,
263            )) * 10
264                + matching_descendant_weight(before, after, depth - 1)
265        })
266        .sum()
267}
268
269/// Apply the presentation depth after the complete trees have been compared.
270/// A hidden changed path is represented explicitly instead of being mistaken
271/// for "no call changes".
272pub fn truncate_diff_tree(node: &mut DiffNode, max_depth: usize) {
273    truncate_diff_tree_at(node, max_depth, 0);
274}
275
276fn truncate_diff_tree_at(node: &mut DiffNode, max_depth: usize, depth: usize) {
277    if depth >= max_depth {
278        if node.children.iter().any(tree_has_changes) {
279            node.children = vec![DiffNode {
280                key: format!("{}#depth-limit", node.key),
281                callsite: None,
282                label: CallLabel::new("… changed below max depth"),
283                relation: CallRelation::Call,
284                before_label: None,
285                before_relation: None,
286                status: DiffStatus::Added,
287                children: Vec::new(),
288            }];
289        } else {
290            node.children.clear();
291        }
292        return;
293    }
294    for child in &mut node.children {
295        truncate_diff_tree_at(child, max_depth, depth + 1);
296    }
297}
298
299pub fn tree_has_changes(node: &DiffNode) -> bool {
300    node.status != DiffStatus::Same || node.children.iter().any(tree_has_changes)
301}
302
303/// Keep unchanged siblings as one-line context while hiding their unchanged
304/// descendants. Paths that lead to a change and fully added/removed subtrees
305/// remain expanded.
306pub fn collapse_unchanged_subtrees(node: &mut DiffNode) -> bool {
307    let carries_dispatch_context = subtree_has_dispatch_context(node);
308    let mut descendants_changed = false;
309    for child in &mut node.children {
310        descendants_changed |= collapse_unchanged_subtrees(child);
311    }
312    let changed = node.status != DiffStatus::Same || descendants_changed;
313    if !changed && !carries_dispatch_context {
314        node.children.clear();
315    }
316    changed
317}
318
319fn subtree_has_dispatch_context(node: &DiffNode) -> bool {
320    node.relation == CallRelation::DispatchCandidate
321        || node.children.iter().any(subtree_has_dispatch_context)
322}
323
324#[cfg(test)]
325mod tests {
326    use super::*;
327    use crate::model::{CallLabel, CallSiteId};
328
329    fn node(key: &str, label: CallLabel, children: Vec<CallNode>) -> CallNode {
330        CallNode {
331            key: key.to_owned(),
332            callsite: None,
333            label,
334            relation: CallRelation::Call,
335            children,
336        }
337    }
338
339    fn call(key: &str, site: &str, label: &str) -> CallNode {
340        CallNode {
341            key: key.to_owned(),
342            callsite: Some(CallSiteId(site.to_owned())),
343            label: CallLabel::new(label),
344            relation: CallRelation::Call,
345            children: Vec::new(),
346        }
347    }
348
349    #[test]
350    fn aligns_by_semantic_key_and_records_a_display_change() {
351        let before = node("rust://save", CallLabel::new("save(order)"), Vec::new());
352        let after = node(
353            "rust://save",
354            CallLabel::new("save(next_order)"),
355            Vec::new(),
356        );
357
358        let diff = diff_optional(Some(&before), Some(&after)).unwrap();
359        assert_eq!(diff.key, "rust://save");
360        assert_eq!(diff.status, DiffStatus::Modified);
361        assert_eq!(
362            diff.before_label
363                .as_ref()
364                .map(|label| label.default.as_str()),
365            Some("save(order)")
366        );
367    }
368
369    #[test]
370    fn typed_labels_do_not_create_noise_in_the_default_call_diff() {
371        let before = node(
372            "rust://save",
373            CallLabel::with_types("save(order)", "save(order: OldOrder)"),
374            Vec::new(),
375        );
376        let after = node(
377            "rust://save",
378            CallLabel::with_types("save(order)", "save(order: NewOrder)"),
379            Vec::new(),
380        );
381
382        let diff = diff_optional(Some(&before), Some(&after)).unwrap();
383        assert_eq!(diff.status, DiffStatus::Same);
384        assert!(!tree_has_changes(&diff));
385    }
386
387    #[test]
388    fn collapses_unchanged_context_below_its_first_line() {
389        let stable = node(
390            "rust://stable",
391            CallLabel::new("stable()"),
392            vec![node("rust://deep", CallLabel::new("deep()"), Vec::new())],
393        );
394        let before = node(
395            "rust://root",
396            CallLabel::new("root()"),
397            vec![
398                stable.clone(),
399                node("rust://old", CallLabel::new("old()"), Vec::new()),
400            ],
401        );
402        let after = node(
403            "rust://root",
404            CallLabel::new("root()"),
405            vec![
406                stable,
407                node("rust://new", CallLabel::new("new()"), Vec::new()),
408            ],
409        );
410        let mut diff = diff_optional(Some(&before), Some(&after)).unwrap();
411
412        assert!(collapse_unchanged_subtrees(&mut diff));
413        assert_eq!(diff.children[0].label.default, "stable()");
414        assert!(diff.children[0].children.is_empty());
415    }
416
417    #[test]
418    fn aligns_repeated_callees_by_callsite_and_label_before_target_fallback() {
419        let before = node(
420            "rust://root",
421            CallLabel::new("root()"),
422            vec![
423                call("rust://save", "save@1", "save(first)"),
424                call("rust://save", "save@2", "save(second)"),
425            ],
426        );
427        let after = node(
428            "rust://root",
429            CallLabel::new("root()"),
430            vec![
431                call("rust://save", "save@0", "save(inserted)"),
432                call("rust://save", "save@1", "save(first)"),
433                call("rust://save", "save@2", "save(second)"),
434            ],
435        );
436
437        let diff = diff_optional(Some(&before), Some(&after)).unwrap();
438        assert_eq!(
439            diff.children
440                .iter()
441                .map(|node| (node.label.default.as_str(), node.status))
442                .collect::<Vec<_>>(),
443            vec![
444                ("save(inserted)", DiffStatus::Added),
445                ("save(first)", DiffStatus::Same),
446                ("save(second)", DiffStatus::Same),
447            ]
448        );
449    }
450
451    #[test]
452    fn absolute_source_line_shifts_do_not_corrupt_repeated_call_alignment() {
453        let before = node(
454            "rust://root",
455            CallLabel::new("root()"),
456            vec![
457                call("rust://touch", "touch@4", "touch(item)"),
458                call("rust://touch", "touch@5", "touch(item)"),
459                call("rust://touch", "touch@6", "touch(item)"),
460            ],
461        );
462        let after = node(
463            "rust://root",
464            CallLabel::new("root()"),
465            vec![
466                call("rust://touch", "touch@5", "touch(item)"),
467                call("rust://touch", "touch@6", "touch(item)"),
468                call("rust://touch", "touch@7", "touch(item)"),
469                call("rust://finish", "finish@8", "finish()"),
470            ],
471        );
472
473        let diff = diff_optional(Some(&before), Some(&after)).unwrap();
474        assert_eq!(diff.children.len(), 4);
475        assert!(
476            diff.children[..3]
477                .iter()
478                .all(|node| node.status == DiffStatus::Same)
479        );
480        assert_eq!(diff.children[3].label.default, "finish()");
481        assert_eq!(diff.children[3].status, DiffStatus::Added);
482    }
483
484    #[test]
485    fn preserves_a_deep_change_when_presentation_depth_is_small() {
486        let before = node(
487            "root",
488            CallLabel::new("root()"),
489            vec![node(
490                "a",
491                CallLabel::new("a()"),
492                vec![node("b", CallLabel::new("b()"), Vec::new())],
493            )],
494        );
495        let after = node(
496            "root",
497            CallLabel::new("root()"),
498            vec![node(
499                "a",
500                CallLabel::new("a()"),
501                vec![node(
502                    "b",
503                    CallLabel::new("b()"),
504                    vec![node("new", CallLabel::new("new()"), Vec::new())],
505                )],
506            )],
507        );
508        let mut diff = diff_optional(Some(&before), Some(&after)).unwrap();
509        assert!(tree_has_changes(&diff));
510        truncate_diff_tree(&mut diff, 1);
511        assert_eq!(
512            diff.children[0].children[0].label.default,
513            "… changed below max depth"
514        );
515    }
516}
diffkit/diff.rs

diffkit/
diff.rs
