use super::counted;
const MAX_DIFF_CELLS: usize = 4_000_000;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DiffKind {
Same,
Added,
Removed,
Skipped,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DiffRow {
pub kind: DiffKind,
pub old_line: Option<usize>,
pub new_line: Option<usize>,
pub text: String,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct TextDiff {
pub rows: Vec<DiffRow>,
pub added: usize,
pub removed: usize,
pub same: usize,
}
impl TextDiff {
#[must_use]
pub const fn is_identical(&self) -> bool {
self.added == 0 && self.removed == 0
}
#[must_use]
pub fn summary(&self) -> String {
if self.is_identical() {
"The two texts are identical.".to_owned()
} else {
format!(
"{} added, {} removed, {} unchanged.",
counted(self.added, "line"),
counted(self.removed, "line"),
counted(self.same, "line"),
)
}
}
#[must_use]
pub fn collapsed(&self, context: usize) -> Vec<DiffRow> {
let mut keep = vec![false; self.rows.len()];
for (position, row) in self.rows.iter().enumerate() {
if row.kind == DiffKind::Same {
continue;
}
let from = position.saturating_sub(context);
let to = (position + context).min(self.rows.len() - 1);
keep[from..=to].fill(true);
}
let mut out = Vec::new();
let mut skipped = 0_usize;
let flush = |out: &mut Vec<DiffRow>, skipped: &mut usize| {
if *skipped > 0 {
out.push(DiffRow {
kind: DiffKind::Skipped,
old_line: None,
new_line: None,
text: counted(*skipped, "unchanged line"),
});
*skipped = 0;
}
};
for (row, kept) in self.rows.iter().zip(&keep) {
if *kept {
flush(&mut out, &mut skipped);
out.push(row.clone());
} else {
skipped += 1;
}
}
flush(&mut out, &mut skipped);
out
}
}
struct RowBuilder {
rows: Vec<DiffRow>,
old_next: usize,
new_next: usize,
}
impl RowBuilder {
fn same(&mut self, text: &str) {
self.rows.push(DiffRow {
kind: DiffKind::Same,
old_line: Some(self.old_next),
new_line: Some(self.new_next),
text: text.to_owned(),
});
self.old_next += 1;
self.new_next += 1;
}
fn removed(&mut self, text: &str) {
self.rows.push(DiffRow {
kind: DiffKind::Removed,
old_line: Some(self.old_next),
new_line: None,
text: text.to_owned(),
});
self.old_next += 1;
}
fn added(&mut self, text: &str) {
self.rows.push(DiffRow {
kind: DiffKind::Added,
old_line: None,
new_line: Some(self.new_next),
text: text.to_owned(),
});
self.new_next += 1;
}
}
fn diff_middle(old: &[&str], new: &[&str], rows: &mut RowBuilder) {
if (old.len() + 1).saturating_mul(new.len() + 1) > MAX_DIFF_CELLS {
for text in old {
rows.removed(text);
}
for text in new {
rows.added(text);
}
return;
}
let width = new.len() + 1;
let mut table = vec![0_u32; (old.len() + 1) * width];
for i in (0..old.len()).rev() {
for j in (0..new.len()).rev() {
table[i * width + j] = if old[i] == new[j] {
table[(i + 1) * width + j + 1] + 1
} else {
table[(i + 1) * width + j].max(table[i * width + j + 1])
};
}
}
let (mut i, mut j) = (0, 0);
while i < old.len() && j < new.len() {
if old[i] == new[j] {
rows.same(old[i]);
i += 1;
j += 1;
} else if table[(i + 1) * width + j] >= table[i * width + j + 1] {
rows.removed(old[i]);
i += 1;
} else {
rows.added(new[j]);
j += 1;
}
}
for text in &old[i..] {
rows.removed(text);
}
for text in &new[j..] {
rows.added(text);
}
}
#[must_use]
pub fn diff_lines(old: &str, new: &str) -> TextDiff {
let old_lines: Vec<&str> = old.lines().collect();
let new_lines: Vec<&str> = new.lines().collect();
let prefix = old_lines
.iter()
.zip(&new_lines)
.take_while(|(a, b)| a == b)
.count();
let room = old_lines.len().min(new_lines.len()) - prefix;
let suffix = old_lines
.iter()
.rev()
.zip(new_lines.iter().rev())
.take(room)
.take_while(|(a, b)| a == b)
.count();
let mut builder = RowBuilder {
rows: Vec::with_capacity(old_lines.len().max(new_lines.len())),
old_next: 1,
new_next: 1,
};
for text in &old_lines[..prefix] {
builder.same(text);
}
diff_middle(
&old_lines[prefix..old_lines.len() - suffix],
&new_lines[prefix..new_lines.len() - suffix],
&mut builder,
);
for text in &old_lines[old_lines.len() - suffix..] {
builder.same(text);
}
let count = |kind: DiffKind| builder.rows.iter().filter(|row| row.kind == kind).count();
TextDiff {
added: count(DiffKind::Added),
removed: count(DiffKind::Removed),
same: count(DiffKind::Same),
rows: builder.rows,
}
}