Function diff_tokens

atomic-core/src/merge/three_way.rs:176–235

Compute an edit script transforming `old` into `new` at the token level. Returns a sequence of [`EditOp`]s. The algorithm uses dynamic-programming LCS to align the two sequences and then walks the DP table to emit keep / delete / insert / replace operations.

(old: &[MergeToken], new: &[MergeToken])

/// LCS to align the two sequences and then walks the DP table to emit
/// keep / delete / insert / replace operations.
fn diff_tokens(old: &[MergeToken], new: &[MergeToken]) -> Vec<EditOp> {
    let n = old.len();
    let m = new.len();

    if n == 0 && m == 0 {
        return Vec::new();
    }
    if n == 0 {
        // Everything in `new` is an insertion before the start.
        return new
            .iter()
            .map(|t| EditOp::Insert(usize::MAX, t.content.clone()))
            .collect();
    }
    if m == 0 {
        return (0..n).map(EditOp::Delete).collect();
    }

    // DP table for LCS lengths: dp[i][j] = LCS(old[0..i], new[0..j])
    let mut dp = vec![vec![0u32; m + 1]; n + 1];
    for i in 1..=n {
        for j in 1..=m {
            if old[i - 1] == new[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }

    // Back-track to produce edit operations.
    let mut ops = Vec::new();
    let mut i = n;
    let mut j = m;

    // We collect in reverse order, then reverse at the end.
    while i > 0 || j > 0 {
        if i > 0 && j > 0 && old[i - 1] == new[j - 1] {
            ops.push(EditOp::Keep(i - 1));
            i -= 1;
            j -= 1;
        } else if j > 0 && (i == 0 || dp[i][j - 1] >= dp[i - 1][j]) {
            // Insertion from `new` — record the base index *after which* it sits.
            let after = if i > 0 { i - 1 } else { usize::MAX };
            ops.push(EditOp::Insert(after, new[j - 1].content.clone()));
            j -= 1;
        } else {
            // Deletion from `old`.
            ops.push(EditOp::Delete(i - 1));
            i -= 1;
        }
    }

    ops.reverse();

    // Coalesce adjacent Delete(i) + Insert(i, _) into Replace(i, _).
    coalesce_replace(&mut ops);