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>,
class: Class,
text: &'a str,
}
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
struct Cell {
len: u32,
is_relevant: bool,
}
#[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
}
}
fn is_relevant(self) -> bool {
matches!(self, Self::Ident)
}
}
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,
class,
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;
}
if non_space_tokens_equal(&old, &new) {
return;
}
let rows = old.len() + 1;
let cols = new.len() + 1;
let mut table = vec![vec![Cell::default(); cols]; rows];
for i in 1..rows {
for j in 1..cols {
let prev = table[i - 1][j - 1];
let top = table[i - 1][j];
let left = table[i][j - 1];
table[i][j] = if old[i - 1].text == new[j - 1].text {
Cell {
len: prev.len + 1,
is_relevant: prev.is_relevant || old[i - 1].class.is_relevant(),
}
} else if top.len >= left.len {
top
} else {
left
};
}
}
let common = table[old.len()][new.len()];
let max_len = old.len().max(new.len());
if common.len as usize * SIMILARITY_DENOMINATOR < max_len * SIMILARITY_NUMERATOR
|| !common.is_relevant
{
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].len >= table[i][j - 1].len {
i -= 1;
push_changed_token(&old, i, changes);
} else {
j -= 1;
push_changed_token(&new, j, changes);
}
}
while i > 0 {
i -= 1;
push_changed_token(&old, i, changes);
}
while j > 0 {
j -= 1;
push_changed_token(&new, j, changes);
}
}
fn non_space_tokens_equal(old: &[Token<'_>], new: &[Token<'_>]) -> bool {
old.iter()
.filter(|token| token.class != Class::Space)
.map(|token| (token.class, token.text))
.eq(new
.iter()
.filter(|token| token.class != Class::Space)
.map(|token| (token.class, token.text)))
}
fn push_changed_token(tokens: &[Token<'_>], index: usize, changes: &mut WordChanges) {
let token = &tokens[index];
if token.class == Class::Space {
return;
}
let ranges = changes.entry(token.row).or_default();
if let Some(space) = tokens.get(index + 1)
&& let Some(next) = tokens.get(index + 2)
&& space.class == Class::Space
&& next.class != Class::Space
&& token.row == next.row
&& ranges.iter().any(|range| range == &next.range)
{
ranges.push(token.range.end..next.range.start);
}
ranges.push(token.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 spacing_changes_are_suppressed_except_word_splits() {
let doc = parse(
"\
diff --git a/a.rs b/a.rs
@@ -1 +1 @@
-let result = foo + bar;
+let result = foo+bar;
",
);
let hunk = &doc.files[0].hunks[0];
let changes = compute(hunk);
assert!(
changes.is_empty(),
"spacing-only edits should not produce a word-diff overlay, got {changes:?}"
);
let doc = parse(
"\
diff --git a/a.rs b/a.rs
@@ -1 +1 @@
-let word = foobar;
+let word = foo bar;
",
);
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();
let highlighted: String = new_ranges
.iter()
.map(|r| &new_row.text[r.clone()])
.collect();
assert_eq!(highlighted, "foo bar");
let doc = parse(
"\
diff --git a/a.rs b/a.rs
@@ -1 +1 @@
-let msg = old name;
+let msg = new value;
",
);
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();
let highlighted: String = new_ranges
.iter()
.map(|r| &new_row.text[r.clone()])
.collect();
assert_eq!(highlighted, "new value");
}
#[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 separator_only_matches_are_suppressed() {
let doc = parse(
"\
diff --git a/a.rs b/a.rs
@@ -1 +1 @@
-old + stale + gone
+new + fresh + kept
",
);
let hunk = &doc.files[0].hunks[0];
let changes = compute(hunk);
assert!(
changes.is_empty(),
"lines that share only separators should not produce word-diff overlay"
);
}
#[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));
}
}