use crate::*;
#[derive(Debug, Clone, Eq, PartialEq)]
pub struct Diff {
pub from: Spanned<String>,
pub to: Spanned<String>,
}
impl Diff {
pub fn new(from: Spanned<String>, to: Spanned<String>) -> Self {
Self { from, to }
}
}
pub struct DiffIterator {
from_lines: Vec<Spanned<String>>,
to_lines: Vec<Spanned<String>>,
from_idx: usize,
to_idx: usize,
}
impl DiffIterator {
pub fn new(from: &str, to: &str) -> Self {
Self {
from_lines: Self::split_lines(from),
to_lines: Self::split_lines(to),
from_idx: 0,
to_idx: 0,
}
}
fn split_lines(text: &str) -> Vec<Spanned<String>> {
let mut lines = Vec::new();
let mut cursor = Cursor::start();
for line in text.lines() {
let line_start = cursor;
let line_with_newline = format!("{}\n", line);
let line_end = cursor.advance(&line_with_newline);
lines.push(
line.to_string()
.into_spanned(Span::new(line_start, cursor.advance(line))),
);
cursor = line_end;
}
if !text.is_empty() && !text.ends_with('\n') && !lines.is_empty() {
let last_idx = lines.len() - 1;
let line_start = lines[last_idx].span.start;
lines[last_idx].span = Span::new(line_start, cursor);
}
lines
}
fn merge_lines(lines: &[Spanned<String>]) -> Option<Spanned<String>> {
if lines.is_empty() {
return None;
}
let merged = lines
.iter()
.map(|line| line.as_str())
.collect::<Vec<_>>()
.join("\n");
let span = Span::new(lines[0].span.start, lines[lines.len() - 1].span.end);
Some(merged.into_spanned(span))
}
}
impl Iterator for DiffIterator {
type Item = Diff;
fn next(&mut self) -> Option<Self::Item> {
while self.from_idx < self.from_lines.len()
&& self.to_idx < self.to_lines.len()
&& self.from_lines[self.from_idx].as_str() == self.to_lines[self.to_idx].as_str()
{
self.from_idx += 1;
self.to_idx += 1;
}
if self.from_idx >= self.from_lines.len() && self.to_idx >= self.to_lines.len() {
return None;
}
if self.from_idx >= self.from_lines.len() {
let to_diff = &self.to_lines[self.to_idx..];
self.to_idx = self.to_lines.len();
let to_spanned = Self::merge_lines(to_diff).unwrap();
let from_spanned =
String::new().into_spanned(Span::new(Cursor::start(), Cursor::start()));
return Some(Diff::new(from_spanned, to_spanned));
}
if self.to_idx >= self.to_lines.len() {
let from_diff = &self.from_lines[self.from_idx..];
self.from_idx = self.from_lines.len();
let from_spanned = Self::merge_lines(from_diff).unwrap();
let to_spanned =
String::new().into_spanned(Span::new(Cursor::start(), Cursor::start()));
return Some(Diff::new(from_spanned, to_spanned));
}
let mut best_anchor = None;
let mut best_cost = usize::MAX;
for from_end in self.from_idx..self.from_lines.len() {
for to_end in self.to_idx..self.to_lines.len() {
if self.from_lines[from_end].as_str() == self.to_lines[to_end].as_str() {
let cost = (from_end - self.from_idx) + (to_end - self.to_idx);
if cost < best_cost {
best_cost = cost;
best_anchor = Some((from_end, to_end));
}
}
}
}
let (from_end, to_end) =
best_anchor.unwrap_or((self.from_lines.len(), self.to_lines.len()));
let from_diff = &self.from_lines[self.from_idx..from_end];
let to_diff = &self.to_lines[self.to_idx..to_end];
self.from_idx = from_end;
self.to_idx = to_end;
let from_spanned = if from_diff.is_empty() {
String::new().into_spanned(Span::new(Cursor::start(), Cursor::start()))
} else {
Self::merge_lines(from_diff).unwrap()
};
let to_spanned = if to_diff.is_empty() {
String::new().into_spanned(Span::new(Cursor::start(), Cursor::start()))
} else {
Self::merge_lines(to_diff).unwrap()
};
Some(Diff::new(from_spanned, to_spanned))
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_simple_diff() {
let from = "line1\nline2\nline3";
let to = "line1\nchanged\nline3";
let diffs: Vec<_> = DiffIterator::new(from, to).collect();
assert_eq!(diffs.len(), 1);
assert_eq!(*diffs[0].from, "line2");
assert_eq!(*diffs[0].to, "changed");
}
#[test]
fn test_multiple_line_diff() {
let from = "a\nb\nc\nd";
let to = "a\nx\ny\nz\nd";
let diffs: Vec<_> = DiffIterator::new(from, to).collect();
assert_eq!(diffs.len(), 1);
assert_eq!(*diffs[0].from, "b\nc");
assert_eq!(*diffs[0].to, "x\ny\nz");
}
#[test]
fn test_no_diff() {
let from = "line1\nline2\nline3";
let to = "line1\nline2\nline3";
let diffs: Vec<_> = DiffIterator::new(from, to).collect();
assert!(diffs.is_empty());
}
#[test]
fn test_added_lines() {
let from = "a\nd";
let to = "a\nb\nc\nd";
let diffs: Vec<_> = DiffIterator::new(from, to).collect();
assert_eq!(diffs.len(), 1);
assert_eq!(*diffs[0].from, "");
assert_eq!(*diffs[0].to, "b\nc");
}
#[test]
fn test_removed_lines() {
let from = "a\nb\nc\nd";
let to = "a\nd";
let diffs: Vec<_> = DiffIterator::new(from, to).collect();
assert_eq!(diffs.len(), 1);
assert_eq!(*diffs[0].from, "b\nc");
assert_eq!(*diffs[0].to, "");
}
#[test]
fn test_multiple_diffs() {
let from = "a\nb\nd\ne";
let to = "a\nx\nd\ny";
let diffs: Vec<_> = DiffIterator::new(from, to).collect();
assert_eq!(diffs.len(), 2);
assert_eq!(*diffs[0].from, "b");
assert_eq!(*diffs[0].to, "x");
assert_eq!(*diffs[1].from, "e");
assert_eq!(*diffs[1].to, "y");
}
#[test]
fn test_prefers_closest_anchor() {
let from = "header\nchanged_from\nfooter";
let to = "header\nchanged_to\nfooter";
let diffs: Vec<_> = DiffIterator::new(from, to).collect();
assert_eq!(diffs.len(), 1);
assert_eq!(*diffs[0].from, "changed_from");
assert_eq!(*diffs[0].to, "changed_to");
}
#[test]
fn test_prefers_closest_when_duplicates_exist() {
let from = "a\nb\nc\nd\nd\nd";
let to = "a\nx\nc\nd\nd\nd";
let diffs: Vec<_> = DiffIterator::new(from, to).collect();
assert_eq!(diffs.len(), 1);
assert_eq!(*diffs[0].from, "b");
assert_eq!(*diffs[0].to, "x");
}
#[test]
fn test_indentation_change_with_nearby_anchor() {
let from = " line1\n line2\n anchor";
let to = " line1\n line2\n anchor";
let diffs: Vec<_> = DiffIterator::new(from, to).collect();
assert_eq!(diffs.len(), 1);
assert_eq!(*diffs[0].from, " line1\n line2");
assert_eq!(*diffs[0].to, " line1\n line2");
}
}