use std::collections::BTreeMap;
use std::ops::Range;
use crate::{DiffLine, DiffLineKind, Hunk, RowId};
const SIMILARITY_NUMERATOR: usize = 1;
const SIMILARITY_DENOMINATOR: usize = 2;
pub type WordChanges = BTreeMap<RowId, Vec<Range<usize>>>;
#[derive(Clone, Debug, Eq, PartialEq)]
struct Token<'a> {
row: RowId,
range: Range<usize>,
text: &'a str,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum Class {
Ident,
Space,
Other,
}
impl Class {
fn of(ch: char) -> Self {
if ch.is_ascii_alphanumeric() || ch == '_' {
Self::Ident
} else if ch == ' ' || ch == '\t' {
Self::Space
} else {
Self::Other
}
}
}
struct Tokens<'a> {
row: RowId,
text: &'a str,
cursor: usize,
}
impl<'a> Iterator for Tokens<'a> {
type Item = Token<'a>;
fn next(&mut self) -> Option<Self::Item> {
let rest = self.text.get(self.cursor..)?;
let mut chars = rest.char_indices();
let (_, first) = chars.next()?;
let class = Class::of(first);
let end_local = if matches!(class, Class::Ident | Class::Space) {
chars
.find(|(_, ch)| Class::of(*ch) != class)
.map_or(rest.len(), |(i, _)| i)
} else {
first.len_utf8()
};
let start = self.cursor;
let end = self.cursor + end_local;
self.cursor = end;
Some(Token {
row: self.row,
range: start..end,
text: &self.text[start..end],
})
}
}
impl Tokens<'_> {
fn new(line: &DiffLine) -> Tokens<'_> {
Tokens {
row: line.id,
text: line.text.as_str(),
cursor: 0,
}
}
}
pub fn compute(hunk: &Hunk) -> WordChanges {
let mut changes = WordChanges::new();
let mut dels: Vec<&DiffLine> = Vec::new();
let mut adds: Vec<&DiffLine> = Vec::new();
for line in &hunk.lines {
match line.kind {
DiffLineKind::Deletion => dels.push(line),
DiffLineKind::Addition => adds.push(line),
DiffLineKind::Context => {
flush_block(&mut dels, &mut adds, &mut changes);
}
DiffLineKind::NoNewline => {}
}
}
flush_block(&mut dels, &mut adds, &mut changes);
for ranges in changes.values_mut() {
ranges.sort_by_key(|range| range.start);
ranges.dedup_by(|next, prev| {
if prev.end >= next.start {
prev.end = prev.end.max(next.end);
true
} else {
false
}
});
}
changes
}
fn flush_block(dels: &mut Vec<&DiffLine>, adds: &mut Vec<&DiffLine>, changes: &mut WordChanges) {
let pairs = dels.len().min(adds.len());
for i in 0..pairs {
lcs(dels[i], adds[i], changes);
}
dels.clear();
adds.clear();
}
fn lcs(del: &DiffLine, add: &DiffLine, changes: &mut WordChanges) {
let old: Vec<Token<'_>> = Tokens::new(del).collect();
let new: Vec<Token<'_>> = Tokens::new(add).collect();
if old.is_empty() || new.is_empty() {
return;
}
let rows = old.len() + 1;
let cols = new.len() + 1;
let mut table = vec![vec![0_u32; cols]; rows];
for i in 1..rows {
for j in 1..cols {
table[i][j] = if old[i - 1].text == new[j - 1].text {
table[i - 1][j - 1] + 1
} else {
table[i - 1][j].max(table[i][j - 1])
};
}
}
let common = table[old.len()][new.len()] as usize;
let max_len = old.len().max(new.len());
if common * SIMILARITY_DENOMINATOR < max_len * SIMILARITY_NUMERATOR {
return;
}
let mut i = old.len();
let mut j = new.len();
while i > 0 && j > 0 {
if old[i - 1].text == new[j - 1].text {
i -= 1;
j -= 1;
} else if table[i - 1][j] >= table[i][j - 1] {
i -= 1;
changes
.entry(old[i].row)
.or_default()
.push(old[i].range.clone());
} else {
j -= 1;
changes
.entry(new[j].row)
.or_default()
.push(new[j].range.clone());
}
}
while i > 0 {
i -= 1;
changes
.entry(old[i].row)
.or_default()
.push(old[i].range.clone());
}
while j > 0 {
j -= 1;
changes
.entry(new[j].row)
.or_default()
.push(new[j].range.clone());
}
}
#[cfg(test)]
#[allow(clippy::unwrap_used)]
mod tests {
use super::*;
use crate::{Decode, DiffDocument};
fn parse(input: &str) -> DiffDocument {
DiffDocument::decode_str(input).unwrap()
}
fn tokens(line: &DiffLine) -> Vec<&str> {
Tokens::new(line).map(|t| t.text).collect()
}
#[test]
fn tokenizer_splits_idents_whitespace_and_punctuation() {
let line = DiffLine {
id: RowId::new(0),
kind: DiffLineKind::Context,
text: "foo bar+baz".to_owned(),
};
assert_eq!(tokens(&line), vec!["foo", " ", "bar", "+", "baz"]);
}
#[test]
fn tokenizer_records_byte_ranges() {
let line = DiffLine {
id: RowId::new(0),
kind: DiffLineKind::Context,
text: "ab cd".to_owned(),
};
let collected: Vec<_> = Tokens::new(&line).collect();
assert_eq!(collected[0].range, 0..2);
assert_eq!(collected[1].range, 2..3);
assert_eq!(collected[2].range, 3..5);
}
#[test]
fn similar_lines_get_word_diff() {
let doc = parse(
"\
diff --git a/a.rs b/a.rs
@@ -1 +1 @@
-fn render(view: &View) {
+fn render(view: &mut View, opts: Options) {
",
);
let hunk = &doc.files[0].hunks[0];
let changes = compute(hunk);
let new_row = hunk
.lines
.iter()
.find(|l| l.kind == DiffLineKind::Addition)
.unwrap();
let new_ranges = changes.get(&new_row.id).cloned().unwrap_or_default();
assert!(!new_ranges.is_empty(), "expected new-side changed ranges");
let new_text = new_row.text.as_str();
let highlighted: String = new_ranges
.iter()
.map(|r| &new_text[r.clone()])
.collect::<Vec<_>>()
.join("|");
assert!(highlighted.contains("mut"), "got {highlighted:?}");
assert!(highlighted.contains("opts"), "got {highlighted:?}");
assert!(highlighted.contains("Options"), "got {highlighted:?}");
}
#[test]
fn dissimilar_lines_are_suppressed() {
let doc = parse(
"\
diff --git a/a.rs b/a.rs
@@ -1 +1 @@
-x = something_complex();
+result.set(other_thing);
",
);
let hunk = &doc.files[0].hunks[0];
let changes = compute(hunk);
assert!(
changes.is_empty(),
"dissimilar lines should not produce a word-diff overlay, got {changes:?}"
);
}
#[test]
fn identical_lines_produce_no_changes() {
let doc = parse(
"\
diff --git a/a.rs b/a.rs
@@ -1,2 +1,2 @@
-same
+same
context
",
);
let hunk = &doc.files[0].hunks[0];
let changes = compute(hunk);
assert!(changes.values().all(Vec::is_empty) || changes.is_empty());
}
#[test]
fn pure_context_hunk_produces_no_changes() {
let doc = parse(
"\
diff --git a/a.rs b/a.rs
@@ -1,2 +1,2 @@
one
two
",
);
let hunk = &doc.files[0].hunks[0];
let changes = compute(hunk);
assert!(changes.is_empty() || changes.values().all(Vec::is_empty));
}
#[test]
fn pure_addition_hunk_produces_no_overlay() {
let doc = parse(
"\
diff --git a/a.rs b/a.rs
@@ -1,2 +1,4 @@
fn main() {
+ let foo = 42;
+ let bar = 43;
}
",
);
let hunk = &doc.files[0].hunks[0];
let changes = compute(hunk);
assert!(changes.is_empty(), "got {changes:?}");
}
#[test]
fn pure_deletion_hunk_produces_no_overlay() {
let doc = parse(
"\
diff --git a/a.rs b/a.rs
@@ -1,4 +1,2 @@
fn main() {
- let foo = 42;
- let bar = 43;
}
",
);
let hunk = &doc.files[0].hunks[0];
let changes = compute(hunk);
assert!(changes.is_empty());
}
#[test]
fn changed_ranges_per_row_are_merged_and_sorted() {
let doc = parse(
"\
diff --git a/a.rs b/a.rs
@@ -1 +1 @@
-a b c d e
+a x y z e
",
);
let hunk = &doc.files[0].hunks[0];
let changes = compute(hunk);
for ranges in changes.values() {
for pair in ranges.windows(2) {
assert!(
pair[0].end <= pair[1].start,
"ranges not disjoint: {pair:?}"
);
}
}
}
#[test]
fn pairing_is_one_to_one_within_a_change_block() {
let doc = parse(
"\
diff --git a/a.rs b/a.rs
@@ -1,3 +1,3 @@
-alpha
-beta
+alpha
+gamma
tail
",
);
let hunk = &doc.files[0].hunks[0];
let changes = compute(hunk);
assert!(changes.is_empty(), "got {changes:?}");
}
#[test]
fn unpaired_lines_in_a_block_get_no_overlay() {
let doc = parse(
"\
diff --git a/a.rs b/a.rs
@@ -1,3 +1,1 @@
-fn alpha() {}
-fn beta() {}
-fn gamma() {}
+fn alpha() {}
",
);
let hunk = &doc.files[0].hunks[0];
let changes = compute(hunk);
let beta = hunk
.lines
.iter()
.find(|l| l.kind == DiffLineKind::Deletion && l.text.contains("beta"))
.unwrap();
let gamma = hunk
.lines
.iter()
.find(|l| l.kind == DiffLineKind::Deletion && l.text.contains("gamma"))
.unwrap();
assert!(changes.get(&beta.id).is_none_or(Vec::is_empty));
assert!(changes.get(&gamma.id).is_none_or(Vec::is_empty));
}
}