use std::ops::Range;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Edit {
pub range: Range<usize>,
pub insert: String,
}
impl Edit {
pub fn delta(&self) -> isize {
self.insert.len() as isize - (self.range.end - self.range.start) as isize
}
pub fn apply(&self, old: &str) -> String {
let mut out =
String::with_capacity(old.len().saturating_sub(self.range.len()) + self.insert.len());
out.push_str(&old[..self.range.start]);
out.push_str(&self.insert);
out.push_str(&old[self.range.end..]);
out
}
}
pub fn apply_edits(old: &str, edits: &[Edit]) -> String {
try_apply_edits(old, edits).expect("apply_edits: edit slice does not fit the text")
}
pub fn try_apply_edits(old: &str, edits: &[Edit]) -> Option<String> {
let mut text = old.to_string();
for e in edits {
if e.range.start > e.range.end
|| e.range.end > text.len()
|| !text.is_char_boundary(e.range.start)
|| !text.is_char_boundary(e.range.end)
{
return None;
}
text.replace_range(e.range.clone(), &e.insert);
}
Some(text)
}
pub fn diff_edit(old: &str, new: &str) -> Edit {
let ob = old.as_bytes();
let nb = new.as_bytes();
let mut prefix = 0;
let max_prefix = ob.len().min(nb.len());
while prefix < max_prefix && ob[prefix] == nb[prefix] {
prefix += 1;
}
while prefix > 0 && !old.is_char_boundary(prefix) {
prefix -= 1;
}
let mut suffix = 0;
let max_suffix = (ob.len() - prefix).min(nb.len() - prefix);
while suffix < max_suffix && ob[ob.len() - 1 - suffix] == nb[nb.len() - 1 - suffix] {
suffix += 1;
}
while suffix > 0
&& (!old.is_char_boundary(old.len() - suffix) || !new.is_char_boundary(new.len() - suffix))
{
suffix -= 1;
}
Edit {
range: prefix..(old.len() - suffix),
insert: new[prefix..(new.len() - suffix)].to_string(),
}
}
#[cfg(test)]
mod tests {
use super::*;
fn edit(range: std::ops::Range<usize>, insert: &str) -> Edit {
Edit {
range,
insert: insert.to_string(),
}
}
#[test]
fn diff_edit_recovers_a_noop() {
assert_eq!(diff_edit("x = 1\n", "x = 1\n"), edit(6..6, ""));
}
#[test]
fn diff_edit_recovers_an_insertion() {
let e = diff_edit("x = 1\n", "x = 12\n");
assert_eq!(e, edit(5..5, "2"));
assert_eq!(e.apply("x = 1\n"), "x = 12\n");
assert_eq!(e.delta(), 1);
}
#[test]
fn diff_edit_recovers_a_deletion() {
let e = diff_edit("x = 12\n", "x = 1\n");
assert_eq!(e, edit(5..6, ""));
assert_eq!(e.apply("x = 12\n"), "x = 1\n");
assert_eq!(e.delta(), -1);
}
#[test]
fn diff_edit_recovers_a_replacement() {
let e = diff_edit("f(a, b)\n", "f(a, c)\n");
assert_eq!(e, edit(5..6, "c"));
assert_eq!(e.apply("f(a, b)\n"), "f(a, c)\n");
assert_eq!(e.delta(), 0);
}
#[test]
fn diff_edit_collapses_disjoint_edits_into_one_span() {
let e = diff_edit("a b c\n", "z b z\n");
assert_eq!(e, edit(0..5, "z b z"));
assert_eq!(e.apply("a b c\n"), "z b z\n");
}
#[test]
fn diff_edit_handles_whole_replacement_and_empty_texts() {
assert_eq!(diff_edit("", "x = 1\n"), edit(0..0, "x = 1\n"));
assert_eq!(diff_edit("x = 1\n", ""), edit(0..6, ""));
assert_eq!(diff_edit("abc", "xyz"), edit(0..3, "xyz"));
}
#[test]
fn diff_edit_clamps_to_char_boundaries() {
let e = diff_edit("α = 1\n", "β = 1\n");
assert_eq!(e, edit(0..2, "β"));
assert_eq!(e.apply("α = 1\n"), "β = 1\n");
let old = "x\u{3AC}";
let new = "x\u{1FB6}";
let e = diff_edit(old, new);
assert!(old.is_char_boundary(e.range.start));
assert!(old.is_char_boundary(e.range.end));
assert_eq!(e.apply(old), new);
}
#[test]
fn apply_edits_chains_left_to_right() {
let edits = vec![edit(0..1, "y"), edit(4..5, "2")];
assert_eq!(apply_edits("x = 1\n", &edits), "y = 2\n");
assert_eq!(apply_edits("x = 1\n", &[]), "x = 1\n");
}
#[test]
fn try_apply_edits_rejects_a_slice_that_does_not_fit() {
assert_eq!(try_apply_edits("x = 1\n", &[edit(9..9, "!")]), None);
let inverted = Edit {
range: std::ops::Range { start: 4, end: 2 },
insert: "!".to_string(),
};
assert_eq!(try_apply_edits("x = 1\n", &[inverted]), None);
assert_eq!(try_apply_edits("α", &[edit(1..1, "!")]), None);
let edits = vec![edit(0..6, ""), edit(3..3, "!")];
assert_eq!(try_apply_edits("x = 1\n", &edits), None);
}
}