Skip to main content

diff_modules

oxilean_parse::incremental::ast_diff

Function diff_modules 

Source 
pub fn diff_modules(
    old: &[Located<Decl>],
    new: &[Located<Decl>],
) -> Vec<DeclEdit>
Expand description

Compare two slices of located declarations and produce an edit script.

The algorithm is the classic Myers O(ND) diff over the fingerprint sequences. After computing the LCS, consecutive Deleted/Inserted pairs that share the same name and kind are folded into a single Modified edit.

§Complexity

Time: O(N·D) where N = max(|old|, |new|) and D = edit distance. Space: O(N + D²) for the DP frontier.

§Output invariants

  • Every old index appears in exactly one edit with old_idx = Some(_).
  • Every new index appears in exactly one edit with new_idx = Some(_).
  • Unchanged and Deleted counts sum to old.len().
  • Unchanged and Inserted counts sum to new.len().