use super::*; use once_cell::sync::OnceCell; macro_rules! range { ($text:expr) => {{ static CHARS: OnceCell> = OnceCell::new(); let chars = CHARS.get_or_init(|| $text.chars().collect()); Range::new(chars, ..) }}; } macro_rules! diff_list { () => { Solution { text1: Range::empty(), text2: Range::empty(), diffs: Vec::new(), } }; ($($kind:ident($text:literal)),+ $(,)?) => {{ #[allow(unused_macro_rules)] macro_rules! text1 { (Insert, $s:literal) => { "" }; (Delete, $s:literal) => { $s }; (Equal, $s:literal) => { $s }; } #[allow(unused_macro_rules)] macro_rules! text2 { (Insert, $s:literal) => { $s }; (Delete, $s:literal) => { "" }; (Equal, $s:literal) => { $s }; } let text1 = range!(concat!($(text1!($kind, $text)),*)); let text2 = range!(concat!($(text2!($kind, $text)),*)); let (_i, _j) = (&mut 0, &mut 0); #[allow(unused_macro_rules)] macro_rules! range { (Insert, $s:literal) => { Diff::Insert(range(text2.doc, _j, $s)) }; (Delete, $s:literal) => { Diff::Delete(range(text1.doc, _i, $s)) }; (Equal, $s:literal) => { Diff::Equal(range(text1.doc, _i, $s), range(text2.doc, _j, $s)) }; } Solution { text1, text2, diffs: vec![$(range!($kind, $text)),*], } }}; } fn range<'a>(doc: &'a [char], offset: &mut usize, text: &str) -> Range<'a> { let len = text.chars().count(); let range = Range { doc, offset: *offset, len, }; *offset += len; range } macro_rules! assert_diffs { ([$($kind:ident($text:literal)),* $(,)?], $solution:ident, $msg:expr $(,)?) => { let expected = &[$(Chunk::$kind($text)),*]; assert!( same_diffs(expected, &$solution.diffs), concat!($msg, "\nexpected={:#?}\nactual={:#?}"), expected, $solution.diffs, ); }; } fn same_diffs(expected: &[Chunk], actual: &[Diff]) -> bool { fn eq(expected: &str, actual: &Range) -> bool { expected.chars().eq(slice(*actual).iter().copied()) } expected.len() == actual.len() && expected.iter().zip(actual).all(|pair| match pair { (Chunk::Insert(expected), Diff::Insert(actual)) => eq(expected, actual), (Chunk::Delete(expected), Diff::Delete(actual)) => eq(expected, actual), (Chunk::Equal(expected), Diff::Equal(actual1, actual2)) => { eq(expected, actual1) && eq(expected, actual2) } (_, _) => false, }) } #[test] fn test_common_prefix() { let text1 = range!("abc"); let text2 = range!("xyz"); assert_eq!(0, common_prefix(text1, text2), "Null case"); let text1 = range!("1234abcdef"); let text2 = range!("1234xyz"); assert_eq!(4, common_prefix(text1, text2), "Non-null case"); let text1 = range!("1234"); let text2 = range!("1234xyz"); assert_eq!(4, common_prefix(text1, text2), "Whole case"); } #[test] fn test_common_suffix() { let text1 = range!("abc"); let text2 = range!("xyz"); assert_eq!(0, common_suffix(text1, text2), "Null case"); let text1 = range!("abcdef1234"); let text2 = range!("xyz1234"); assert_eq!(4, common_suffix(text1, text2), "Non-null case"); let text1 = range!("1234"); let text2 = range!("xyz1234"); assert_eq!(4, common_suffix(text1, text2), "Whole case"); } #[test] fn test_common_overlap() { let text1 = Range::empty(); let text2 = range!("abcd"); assert_eq!(0, common_overlap(text1, text2), "Null case"); let text1 = range!("abc"); let text2 = range!("abcd"); assert_eq!(3, common_overlap(text1, text2), "Whole case"); let text1 = range!("123456"); let text2 = range!("abcd"); assert_eq!(0, common_overlap(text1, text2), "No overlap"); let text1 = range!("123456xxx"); let text2 = range!("xxxabcd"); assert_eq!(3, common_overlap(text1, text2), "Overlap"); // Some overly clever languages (C#) may treat ligatures as equal to their // component letters. E.g. U+FB01 == 'fi' let text1 = range!("fi"); let text2 = range!("\u{fb01}i"); assert_eq!(0, common_overlap(text1, text2), "Unicode"); } #[test] fn test_cleanup_merge() { let mut solution = diff_list![]; cleanup_merge(&mut solution); assert_diffs!([], solution, "Null case"); let mut solution = diff_list![Equal("a"), Delete("b"), Insert("c")]; cleanup_merge(&mut solution); assert_diffs!( [Equal("a"), Delete("b"), Insert("c")], solution, "No change case", ); let mut solution = diff_list![Equal("a"), Equal("b"), Equal("c")]; cleanup_merge(&mut solution); assert_diffs!([Equal("abc")], solution, "Merge equalities"); let mut solution = diff_list![Delete("a"), Delete("b"), Delete("c")]; cleanup_merge(&mut solution); assert_diffs!([Delete("abc")], solution, "Merge deletions"); let mut solution = diff_list![Insert("a"), Insert("b"), Insert("c")]; cleanup_merge(&mut solution); assert_diffs!([Insert("abc")], solution, "Merge insertions"); let mut solution = diff_list![ Delete("a"), Insert("b"), Delete("c"), Insert("d"), Equal("e"), Equal("f"), ]; cleanup_merge(&mut solution); assert_diffs!( [Delete("ac"), Insert("bd"), Equal("ef")], solution, "Merge interweave", ); let mut solution = diff_list![Delete("a"), Insert("abc"), Delete("dc")]; cleanup_merge(&mut solution); assert_diffs!( [Equal("a"), Delete("d"), Insert("b"), Equal("c")], solution, "Prefix and suffix detection", ); let mut solution = diff_list![ Equal("x"), Delete("a"), Insert("abc"), Delete("dc"), Equal("y"), ]; cleanup_merge(&mut solution); assert_diffs!( [Equal("xa"), Delete("d"), Insert("b"), Equal("cy")], solution, "Prefix and suffix detection with equalities", ); let mut solution = diff_list![Equal("a"), Insert("ba"), Equal("c")]; cleanup_merge(&mut solution); assert_diffs!([Insert("ab"), Equal("ac")], solution, "Slide edit left"); let mut solution = diff_list![Equal("c"), Insert("ab"), Equal("a")]; cleanup_merge(&mut solution); assert_diffs!([Equal("ca"), Insert("ba")], solution, "Slide edit right"); let mut solution = diff_list![ Equal("a"), Delete("b"), Equal("c"), Delete("ac"), Equal("x"), ]; cleanup_merge(&mut solution); assert_diffs!( [Delete("abc"), Equal("acx")], solution, "Slide edit left recursive", ); let mut solution = diff_list![ Equal("x"), Delete("ca"), Equal("c"), Delete("b"), Equal("a"), ]; cleanup_merge(&mut solution); assert_diffs!( [Equal("xca"), Delete("cba")], solution, "Slide edit right recursive", ); let mut solution = diff_list![Delete("b"), Insert("ab"), Equal("c")]; cleanup_merge(&mut solution); assert_diffs!([Insert("a"), Equal("bc")], solution, "Empty range"); let mut solution = diff_list![Equal(""), Insert("a"), Equal("b")]; cleanup_merge(&mut solution); assert_diffs!([Insert("a"), Equal("b")], solution, "Empty equality"); } #[test] fn test_cleanup_semantic_lossless() { let mut solution = diff_list![]; cleanup_semantic_lossless(&mut solution); assert_diffs!([], solution, "Null case"); let mut solution = diff_list![ Equal("AAA\r\n\r\nBBB"), Insert("\r\nDDD\r\n\r\nBBB"), Equal("\r\nEEE"), ]; cleanup_semantic_lossless(&mut solution); assert_diffs!( [ Equal("AAA\r\n\r\n"), Insert("BBB\r\nDDD\r\n\r\n"), Equal("BBB\r\nEEE"), ], solution, "Blank lines", ); let mut solution = diff_list![Equal("AAA\r\nBBB"), Insert(" DDD\r\nBBB"), Equal(" EEE")]; cleanup_semantic_lossless(&mut solution); assert_diffs!( [Equal("AAA\r\n"), Insert("BBB DDD\r\n"), Equal("BBB EEE")], solution, "Line boundaries", ); let mut solution = diff_list![Equal("The c"), Insert("ow and the c"), Equal("at.")]; cleanup_semantic_lossless(&mut solution); assert_diffs!( [Equal("The "), Insert("cow and the "), Equal("cat.")], solution, "Word boundaries", ); let mut solution = diff_list![Equal("The-c"), Insert("ow-and-the-c"), Equal("at.")]; cleanup_semantic_lossless(&mut solution); assert_diffs!( [Equal("The-"), Insert("cow-and-the-"), Equal("cat.")], solution, "Alphanumeric boundaries", ); let mut solution = diff_list![Equal("a"), Delete("a"), Equal("ax")]; cleanup_semantic_lossless(&mut solution); assert_diffs!([Delete("a"), Equal("aax")], solution, "Hitting the start"); let mut solution = diff_list![Equal("xa"), Delete("a"), Equal("a")]; cleanup_semantic_lossless(&mut solution); assert_diffs!([Equal("xaa"), Delete("a")], solution, "Hitting the end"); let mut solution = diff_list![Equal("The xxx. The "), Insert("zzz. The "), Equal("yyy.")]; cleanup_semantic_lossless(&mut solution); assert_diffs!( [Equal("The xxx."), Insert(" The zzz."), Equal(" The yyy.")], solution, "Sentence boundaries", ); } #[test] fn test_cleanup_semantic() { let mut solution = diff_list![]; cleanup_semantic(&mut solution); assert_diffs!([], solution, "Null case"); let mut solution = diff_list![Delete("ab"), Insert("cd"), Equal("12"), Delete("e")]; cleanup_semantic(&mut solution); assert_diffs!( [Delete("ab"), Insert("cd"), Equal("12"), Delete("e")], solution, "No elimination #1", ); let mut solution = diff_list![Delete("abc"), Insert("ABC"), Equal("1234"), Delete("wxyz")]; cleanup_semantic(&mut solution); assert_diffs!( [Delete("abc"), Insert("ABC"), Equal("1234"), Delete("wxyz")], solution, "No elimination #2", ); let mut solution = diff_list![Delete("a"), Equal("b"), Delete("c")]; cleanup_semantic(&mut solution); assert_diffs!([Delete("abc"), Insert("b")], solution, "Simple elimination",); let mut solution = diff_list![ Delete("ab"), Equal("cd"), Delete("e"), Equal("f"), Insert("g"), ]; cleanup_semantic(&mut solution); assert_diffs!( [Delete("abcdef"), Insert("cdfg")], solution, "Backpass elimination", ); let mut solution = diff_list![ Insert("1"), Equal("A"), Delete("B"), Insert("2"), Equal("_"), Insert("1"), Equal("A"), Delete("B"), Insert("2"), ]; cleanup_semantic(&mut solution); assert_diffs!( [Delete("AB_AB"), Insert("1A2_1A2")], solution, "Multiple elimination", ); let mut solution = diff_list![Equal("The c"), Delete("ow and the c"), Equal("at.")]; cleanup_semantic(&mut solution); assert_diffs!( [Equal("The "), Delete("cow and the "), Equal("cat.")], solution, "Word boundaries", ); let mut solution = diff_list![Delete("abcxx"), Insert("xxdef")]; cleanup_semantic(&mut solution); assert_diffs!( [Delete("abcxx"), Insert("xxdef")], solution, "No overlap elimination", ); let mut solution = diff_list![Delete("abcxxx"), Insert("xxxdef")]; cleanup_semantic(&mut solution); assert_diffs!( [Delete("abc"), Equal("xxx"), Insert("def")], solution, "Overlap elimination", ); let mut solution = diff_list![Delete("xxxabc"), Insert("defxxx")]; cleanup_semantic(&mut solution); assert_diffs!( [Insert("def"), Equal("xxx"), Delete("abc")], solution, "Reverse overlap elimination", ); let mut solution = diff_list![ Delete("abcd1212"), Insert("1212efghi"), Equal("----"), Delete("A3"), Insert("3BC"), ]; cleanup_semantic(&mut solution); assert_diffs!( [ Delete("abcd"), Equal("1212"), Insert("efghi"), Equal("----"), Delete("A"), Equal("3"), Insert("BC"), ], solution, "Two overlap eliminations", ); } #[test] fn test_bisect() { let text1 = range!("cat"); let text2 = range!("map"); let solution = Solution { text1, text2, diffs: bisect(text1, text2), }; assert_diffs!( [ Delete("c"), Insert("m"), Equal("a"), Delete("t"), Insert("p"), ], solution, "Normal", ); } #[test] fn test_main() { let solution = main(Range::empty(), Range::empty()); assert_diffs!([], solution, "Null case"); let solution = main(range!("abc"), range!("abc")); assert_diffs!([Equal("abc")], solution, "Equality"); let solution = main(range!("abc"), range!("ab123c")); assert_diffs!( [Equal("ab"), Insert("123"), Equal("c")], solution, "Simple insertion", ); let solution = main(range!("a123bc"), range!("abc")); assert_diffs!( [Equal("a"), Delete("123"), Equal("bc")], solution, "Simple deletion", ); let solution = main(range!("abc"), range!("a123b456c")); assert_diffs!( [ Equal("a"), Insert("123"), Equal("b"), Insert("456"), Equal("c"), ], solution, "Two insertions", ); let solution = main(range!("a123b456c"), range!("abc")); assert_diffs!( [ Equal("a"), Delete("123"), Equal("b"), Delete("456"), Equal("c"), ], solution, "Two deletions", ); let solution = main(range!("a"), range!("b")); assert_diffs!([Delete("a"), Insert("b")], solution, "Simple case #1"); let solution = main( range!("Apples are a fruit."), range!("Bananas are also fruit."), ); assert_diffs!( [ Delete("Apple"), Insert("Banana"), Equal("s are a"), Insert("lso"), Equal(" fruit."), ], solution, "Simple case #2", ); let solution = main(range!("ax\t"), range!("\u{0680}x\000")); assert_diffs!( [ Delete("a"), Insert("\u{0680}"), Equal("x"), Delete("\t"), Insert("\000"), ], solution, "Simple case #3", ); let solution = main(range!("1ayb2"), range!("abxab")); assert_diffs!( [ Delete("1"), Equal("a"), Delete("y"), Equal("b"), Delete("2"), Insert("xab"), ], solution, "Overlap #1", ); let solution = main(range!("abcy"), range!("xaxcxabc")); assert_diffs!( [Insert("xaxcx"), Equal("abc"), Delete("y")], solution, "Overlap #2", ); let solution = main( range!("ABCDa=bcd=efghijklmnopqrsEFGHIJKLMNOefg"), range!("a-bcd-efghijklmnopqrs"), ); assert_diffs!( [ Delete("ABCD"), Equal("a"), Delete("="), Insert("-"), Equal("bcd"), Delete("="), Insert("-"), Equal("efghijklmnopqrs"), Delete("EFGHIJKLMNOefg"), ], solution, "Overlap #3", ); let solution = main( range!("a [[Pennsylvania]] and [[New"), range!(" and [[Pennsylvania]]"), ); assert_diffs!( [ Insert(" "), Equal("a"), Insert("nd"), Equal(" [[Pennsylvania]]"), Delete(" and [[New"), ], solution, "Large equality", ); }