Compute the word diff using LCS algorithm.
(
old_tokens: Vec<Token<'a>>,
new_tokens: Vec<Token<'a>>,
)
| 644 | |
| 645 | /// Compute the word diff using LCS algorithm. |
| 646 | fn compute_word_diff<'a>( |
| 647 | old_tokens: Vec<Token<'a>>, |
| 648 | new_tokens: Vec<Token<'a>>, |
| 649 | ) -> WordDiffResult<'a> { |
| 650 | let n = old_tokens.len(); |
| 651 | let m = new_tokens.len(); |
| 652 | |
| 653 | // Build LCS table |
| 654 | let mut dp = vec![vec![0usize; m + 1]; n + 1]; |
| 655 | |
| 656 | for i in 1..=n { |
| 657 | for j in 1..=m { |
| 658 | if old_tokens[i - 1] == new_tokens[j - 1] { |
| 659 | dp[i][j] = dp[i - 1][j - 1] + 1; |
| 660 | } else { |
| 661 | dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]); |
| 662 | } |
| 663 | } |
| 664 | } |
| 665 | |
| 666 | // Backtrack to find operations |
| 667 | let mut ops = Vec::new(); |
| 668 | let mut i = n; |
| 669 | let mut j = m; |
| 670 | |
| 671 | // We build ops in reverse, then reverse at the end |
| 672 | while i > 0 || j > 0 { |
| 673 | if i > 0 && j > 0 && old_tokens[i - 1] == new_tokens[j - 1] { |
| 674 | // Equal |
| 675 | ops.push(WordDiffOp::Equal { |
| 676 | old_range: (i - 1)..i, |
| 677 | new_range: (j - 1)..j, |
| 678 | }); |
| 679 | i -= 1; |
| 680 | j -= 1; |
| 681 | } else if j > 0 && (i == 0 || dp[i][j - 1] >= dp[i - 1][j]) { |
| 682 | // Insert |
| 683 | ops.push(WordDiffOp::Insert { |
| 684 | old_pos: i, |
| 685 | new_range: (j - 1)..j, |
| 686 | }); |
| 687 | j -= 1; |
| 688 | } else { |
| 689 | // Delete |
| 690 | ops.push(WordDiffOp::Delete { |
| 691 | old_range: (i - 1)..i, |
| 692 | new_pos: j, |
| 693 | }); |
| 694 | i -= 1; |
| 695 | } |
| 696 | } |
| 697 | |
| 698 | ops.reverse(); |
| 699 | |
| 700 | // Merge adjacent operations of the same type and convert delete+insert pairs to replace |
| 701 | let merged_ops = merge_operations(ops); |
| 702 | |
| 703 | WordDiffResult { |
no test coverage detected