+ /// A default timeout in num milliseconda, defaults to 1000 (1 second)

+ timeout: Some(1000),

+ fn main_internal<'a>(

+ &self,

+ old_bytes: &'a [u8],

+ new_bytes: &'a [u8],

+ linemode: bool,

+ deadline: Instant,

+ ) -> Vec<Diff> {

+ return vec![Diff::equal(old_bytes)];

+ return vec![Diff::insert(new_bytes)];

+ return vec![Diff::delete(old_bytes)];

+ linemode,

+ deadline,

+ let mut d = vec![Diff::equal(&old_bytes[..common_prefix])];

+ Self::cleanup_merge(&mut diffs);

+

+ fn compute<'a>(&self, old: &'a [u8], new: &'a [u8], linemode: bool, deadline: Instant) -> Vec<Diff> {

+ return vec![Diff::insert(new)];

+ return vec![Diff::delete(old)];

+ Diff::equal(short),

+ return vec![Diff::delete(old), Diff::insert(new)];

+ let mut diffs_a = self.main_internal(old_a, new_a, linemode, deadline);

+ let mut diffs_b = self.main_internal(old_b, new_b, linemode, deadline);

+ diffs_a.push(Diff::equal(mid_common));

+ if linemode && old.len() > 100 && new.len() > 100 {

+ return self.line_mode(old, new, deadline);

+ fn line_mode<'a>(&self, old: &'a [u8], new: &'a [u8], deadline: Instant) -> Vec<Diff> {

+ let mut diffs = self.main_internal(&to_chars.chars_old, &to_chars.chars_new, false, deadline);

+

+ diffs.push(Diff::equal(b""));

+

+ let idxend = idxstart + delete_n + insert_n;

+

+ diffs.drain(idxstart .. idxend);

+ let mut subdiffs = self.main_internal(&delete_data, &insert_data, false, deadline);

+

+ }

+ // resetting counters

+ insert_n = 0;

+ delete_n = 0;

+ delete_data = Vec::new();

+ insert_data = Vec::new();

+ let v_len = 2 * max_d;

+

+ let mut v1 = vec![-1_i32; v_len as usize];

+ let mut v2 = vec![-1_i32; v_len as usize];

+ // println!("{v1:?}");

+ // println!("{v2:?}");

+ // println!("v_offset[{v_offset}] v_length[{v_len}] delta[{delta}] front[{front}]");

+

+

+ for d in 0..max_d {

+ // println!("For d: {d} --------------------");

+ for k1 in (k1start - d..d - k1end + 1).step_by(2) {

+ // println!("Loop 1 k1[{k1}] k1_offset[{k1_offset}]");

+ // println!("Loop 1 Check offset[if] {}", k1_offset + 1);

+ // println!("Loop 1 Check offset[else] {}", k1_offset - 1);

+

+

+ v1[k1_offset] = x1;

+

+ if x1 > old_len {

+ // ran off the right of the graph

+ k1end += 2;

+ } else if y1 > new_len {

+ // Ran of the bottom of the graph

+ k1start += 2;

+ } else if front {

+ let k2_offset = v_offset as i32 + delta - k1;

+ if k2_offset >= 0 && k2_offset < v_len && v2[k2_offset as usize] != -1 {

+ // Mirror x2 onto top-left coodinate system

+ let x2 = old_len - v2[k2_offset as usize];

+ if x1 >= x2 {

+ // Overlap detected

+ // println!("Loop 1 Overlap detected! {x1} {y1}");

+ return self.bisect_split(old, new, x1 as usize, y1 as usize, deadline);

+ }

+ }

+ }

+ }

+

+ // println!("After loop 1 k1start[{k1start}] k1end[{k1end}]");

+

+ // Walk the reverse path one step

+ for k2 in (k2start - d..d - k2end + 1).step_by(2) {

+ let k2_offset = (v_offset as i32 + k2) as usize;

+ // println!("Loop 2 k2: {k2} k2_offset: {k2_offset}");

+

+ let mut x2 = if k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1]) {

+ // println!("Loop 2 Check offset[if] {}", k2_offset + 1);

+ v2[k2_offset + 1]

+ } else {

+ // println!("Loop 2 Check offset[else] {}", k2_offset - 1);

+ v2[k2_offset - 1] + 1

+ };

+

+ let mut y2 = x2 - k2;

+ while x2 < old_len

+ && y2 < new_len

+ && old[(old_len - x2) as usize - 1] == new[(new_len - y2) as usize - 1]

+ {

+ x2 += 1;

+ y2 += 1;

+ }

+

+ v2[k2_offset] = x2;

+ if x2 > old_len {

+ // Ran off the left of the graph

+ k2end += 2;

+ } else if y2 > new_len {

+ // Ran off the top of the graph

+ k2start += 2;

+ } else if !front {

+ let k1_offset = v_offset as i32 + delta - k2;

+ // println!("Loop 2 not front! k1_offset[{k1_offset}] v_length[{v_len}]");

+ if k1_offset >= 0 && k1_offset < v_len && v1[k1_offset as usize] != -1 {

+ let x1 = v1[k1_offset as usize];

+ let y1 = v_offset as i32 + x1 - k1_offset;

+

+ // Mirror x2 onto top-left coordinate system

+ x2 = old_len - x2;

+ // println!("Loop 2 not front inner: x1[{x1}] y1[{y1}] x2[{x2}]");

+ if x1 >= x2 {

+ // Overlap

+ // println!("Loop 2 Overlap detected! {x1} {y1}");

+ return self.bisect_split(old, new, x1 as usize, y1 as usize, deadline);

+ }

+ }

+ }

+

+ vec![Diff::delete(old), Diff::insert(new)]

+ fn bisect_split(

+ &self,

+ old: &[u8],

+ new: &[u8],

+ x: usize,

+ y: usize,

+ deadline: Instant,

+ ) -> Vec<Diff> {

+ let new_a = &new[..y];

+ let mut diffs_a = self.main_internal(old_a, new_a, false, deadline);

+ let mut diffs_b = self.main_internal(old_b, new_b, false, deadline);

+

+

+ let l = if lhs.len() > rhs.len() {

+ &lhs[lhs.len() - rhs.len()..]

+ } else {

+ lhs

+ };

+ let r = if lhs.len() < rhs.len() {

+ &rhs[..lhs.len()]

+ } else {

+ rhs

+ };

+ let pattern = &l[minlen - len..];

+ let found = if let Some(found) = r

+ .windows(pattern.len())

+ .step_by(1)

+ .position(|p| p == pattern)

+ {

+ if found == 0 || l[minlen - len..] == r[..len] {

+

+ diffs.insert(last, Diff::delete(last_eq));

+

+

+ if overlap_1 >= overlap_2

+ && (overlap_1 >= delete_thres || overlap_1 >= insert_thres)

+ {

+ diffs[pointer - 1].1 = delete[..delete.len() - overlap_1].to_vec();

+ diffs[pointer + 1].1 = insert[overlap_1..].to_vec();

+ diffs.insert(pointer, Diff::equal(&delete[..overlap_2]));

+ diffs[pointer - 1] = Diff::insert(&insert[..insert.len() - overlap_2]);

+ diffs[pointer + 1] = Diff::delete(&delete[overlap_2..]);

+ // e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.

+ let mut common_prev = edit[edit.len() - commonlen..].to_vec();

+

+ equality_prev = equality_prev[..equality_prev.len() - commonlen].to_vec();

+ common_prev.append(&mut edit[..edit.len() - commonlen].to_vec());

+

+ let score = Self::cleanup_semantic_score(&equality_prev[..], &edit[..])

+ + Self::cleanup_semantic_score(&edit[..], &equality_next[..]);

+ let blankline_2 = linebreak_2

+ && (two.starts_with(b"\r\n\n")

+ || two.starts_with(b"\r\n\r\n")

+ || two.starts_with(b"\n\r\n")

+ || two.starts_with(b"\n\n"));

+

+ diffs.push(Diff::equal(b""));

+ diffs.insert(0, Diff::equal(&insert_data[..commonlen]));

+ diffs.insert(pointer, Diff::delete(&delete_data));

+ diffs.insert(pointer, Diff::insert(&insert_data));

+ let substr_idx = if diff.1.len() >= diff_prev.1.len() {

+ diff.1.len() - diff_prev.1.len()

+ } else {

+ 0

+ };

+ if diff.1[substr_idx..] == diff_prev.1 {

+ } else if diff.1[..if diff_next.1.len() <= diff.1.len() {

+ diff_next.1.len()

+ } else {

+ diff.1.len()

+ }] == diff_next.1

+ {

+ let deadline = Instant::now()

+ .checked_add(Duration::from_millis(self.timeout()))

+ .unwrap();

+

+ self.main_internal(old.as_bytes(), new.as_bytes(), self.checklines(), deadline)

+ use crate::dmp::{Diff, HalfMatch, LineToChars};

+ use super::{DiffMatchPatch, Ops};

+ let mut diffs = [Diff::equal(d1.as_bytes()), Diff::insert(d2.as_bytes())];

+ Diff::equal(b"alpha\nbeta\nalpha\n"),

+ Diff::insert(b"beta\nalpha\nbeta\n")

+ let mut diffs = [Diff::delete(charlist.as_bytes())];

+ assert_eq!([Diff::delete(linestr.join("").as_bytes())], diffs);

+ let mut diffs = [Diff::insert(&l2c.chars_old)];

+ let mut diffs = vec![Diff::equal(b"a"), Diff::delete(b"b"), Diff::insert(b"c")];

+ let test = vec![Diff::equal(b"a"), Diff::delete(b"b"), Diff::insert(b"c")];

+ let mut diffs = vec![Diff::equal(b"a"), Diff::equal(b"b"), Diff::equal(b"c")];

+ let test = vec![Diff::equal(b"abc")];

+ let mut diffs = vec![Diff::delete(b"a"), Diff::delete(b"b"), Diff::delete(b"c")];

+ let test = vec![Diff::delete(b"abc")];

+ let mut diffs = vec![Diff::insert(b"a"), Diff::insert(b"b"), Diff::insert(b"c")];

+ let test = vec![Diff::insert(b"abc")];

+ Diff::delete(b"a"),

+ Diff::insert(b"b"),

+ Diff::delete(b"c"),

+ Diff::insert(b"d"),

+ Diff::equal(b"e"),

+ Diff::equal(b"f"),

+ let test = vec![Diff::delete(b"ac"), Diff::insert(b"bd"), Diff::equal(b"ef")];

+ Diff::delete(b"a"),

+ Diff::insert(b"abc"),

+ Diff::delete(b"dc"),

+ Diff::equal(b"a"),

+ Diff::delete(b"d"),

+ Diff::insert(b"b"),

+ Diff::equal(b"c"),

+ Diff::equal(b"x"),

+ Diff::delete(b"a"),

+ Diff::insert(b"abc"),

+ Diff::delete(b"dc"),

+ Diff::equal(b"y"),

+ Diff::equal(b"xa"),

+ Diff::delete(b"d"),

+ Diff::insert(b"b"),

+ Diff::equal(b"cy"),

+ let mut diffs = vec![Diff::equal(b"a"), Diff::insert(b"ba"), Diff::equal(b"c")];

+ let test = vec![Diff::insert(b"ab"), Diff::equal(b"ac")];

+ let mut diffs = vec![Diff::equal(b"c"), Diff::insert(b"ab"), Diff::equal(b"a")];

+ let test = vec![Diff::equal(b"ca"), Diff::insert(b"ba")];

+ Diff::equal(b"a"),

+ Diff::delete(b"b"),

+ Diff::equal(b"c"),

+ Diff::delete(b"ac"),

+ Diff::equal(b"x"),

+ let test = vec![Diff::delete(b"abc"), Diff::equal(b"acx")];

+ Diff::equal(b"x"),

+ Diff::delete(b"ca"),

+ Diff::equal(b"c"),

+ Diff::delete(b"b"),

+ Diff::equal(b"a"),

+ let test = vec![Diff::equal(b"xca"), Diff::delete(b"cba")];

+ let mut diffs = vec![Diff::delete(b"b"), Diff::insert(b"ab"), Diff::equal(b"c")];

+ let test = vec![Diff::insert(b"a"), Diff::equal(b"bc")];

+ let mut diffs = vec![Diff::equal(b""), Diff::insert(b"a"), Diff::equal(b"b")];

+ let test = vec![Diff::insert(b"a"), Diff::equal(b"b")];

+ Diff::delete(b"e"),

+ Diff::delete(b"e"),

+ Diff::delete(b"wxyz"),

+ Diff::delete(b"wxyz"),

+ let mut diffs = vec![Diff::delete(b"a"), Diff::equal(b"b"), Diff::delete(b"c")];

+ let test: Vec<Diff> = vec![Diff::delete(b"abc"), Diff::insert(b"b")];

+ Diff::insert(b"g"),

+ let test: Vec<Diff> = vec![Diff::delete(b"abcdef"), Diff::insert(b"cdfg")];

+ let test: Vec<Diff> = vec![Diff::delete(b"AB_AB"), Diff::insert(b"1A2_1A2")];

+ let mut diffs = vec![Diff::delete(b"abcxx"), Diff::insert(b"xxdef")];

+ let test: Vec<Diff> = vec![Diff::delete(b"abcxx"), Diff::insert(b"xxdef")];

+ let mut diffs = vec![Diff::delete(b"abcxxx"), Diff::insert(b"xxxdef")];

+ Diff::insert(b"def"),

+ let mut diffs = vec![Diff::delete(b"xxxabc"), Diff::insert(b"defxxx")];

+ Diff::delete(b"abc"),

+ Diff::equal(b"\r\nEEE"),

+ Diff::equal(b"BBB\r\nEEE"),

+ Diff::equal(b" EEE"),

+ Diff::equal(b"BBB EEE"),

+ Diff::equal(b"at."),

+ Diff::equal(b"cat."),

+ Diff::equal(b"at."),

+ Diff::equal(b"cat."),

+ let mut diffs: Vec<Diff> = vec![Diff::equal(b"a"), Diff::delete(b"a"), Diff::equal(b"ax")];

+ let test: Vec<Diff> = vec![Diff::delete(b"a"), Diff::equal(b"aax")];

+ let mut diffs: Vec<Diff> = vec![Diff::equal(b"xa"), Diff::delete(b"a"), Diff::equal(b"a")];

+ let test: Vec<Diff> = vec![Diff::equal(b"xaa"), Diff::delete(b"a")];

+ Diff::equal(b"yyy."),

+ assert_eq!(

+ 0,

+ DiffMatchPatch::common_overlap(b"fi", "\u{7FFF}".as_bytes())

+ );

+ assert_eq!(

+ 6,

+ DiffMatchPatch::common_overlap("❤️".as_bytes(), "❤️".as_bytes())

+ );

+

+ assert_eq!(

+ 0,

+ DiffMatchPatch::common_overlap("ஆ".as_bytes(), "இ".as_bytes())

+ );

+ assert_eq!(

+ 3,

+ DiffMatchPatch::common_overlap("ஆஇ".as_bytes(), "இ".as_bytes())

+ );

+

+ let dmp = DiffMatchPatch::default();

+ assert_eq!(

+ vec![

+ Diff::delete(b"c"),

+ Diff::insert(b"m"),

+ Diff::equal(b"a"),

+ Diff::delete(b"t"),

+ Diff::insert(b"p")

+ ],

+ dmp.bisect(

+ b"cat",

+ b"map",

+ Instant::now()

+ .checked_add(Duration::from_secs(600))

+ .unwrap()

+ )

+ );

+ // Timeout.

+ assert_eq!(

+ vec![Diff::delete(b"cat"), Diff::insert(b"map"),],

+ dmp.bisect(

+ b"cat",

+ b"map",

+ Instant::now().checked_add(Duration::from_secs(0)).unwrap()

+ )

+ );

+

+ assert_eq!(vec![Diff::equal(b"abc")], dmp.diff_main("abc", "abc"));

+ vec![Diff::equal(b"ab"), Diff::insert(b"123"), Diff::equal(b"c")],

+ vec![Diff::equal(b"a"), Diff::delete(b"123"), Diff::equal(b"bc")],

+ Diff::equal(b"a"),

+ Diff::insert(b"123"),

+ Diff::equal(b"b"),

+ Diff::insert(b"456"),

+ Diff::equal(b"c"),

+ Diff::equal(b"a"),

+ Diff::delete(b"123"),

+ Diff::equal(b"b"),

+ Diff::delete(b"456"),

+ Diff::equal(b"c"),

+ vec![Diff::delete(b"a"), Diff::insert(b"b"),],

+ Diff::delete(b"Apple"),

+ Diff::insert(b"Banana"),

+ assert_eq!(

+ vec![

+ Diff::delete(b"a"),

+ Diff::insert("\u{0680}".as_bytes()),

+ Diff::equal(b"x"),

+ Diff::delete(b"\t"),

+ Diff::insert(b"\0")

+ ],

+ dmp.diff_main("ax\t", "\u{0680}x\0")

+ );

+ // Overlaps.

+ assert_eq!(

+ vec![

+ Diff::delete(b"1"),

+ Diff::equal(b"a"),

+ Diff::delete(b"y"),

+ Diff::equal(b"b"),

+ Diff::delete(b"2"),

+ Diff::insert(b"xab"),

+ ],

+ dmp.diff_main("1ayb2", "abxab")

+ );

+ assert_eq!(

+ vec![

+ Diff::insert(b"xaxcx"),

+ Diff::equal(b"abc"),

+ Diff::delete(b"y"),

+ ],

+ dmp.diff_main("abcy", "xaxcxabc")

+ );

+ assert_eq!(

+ vec![

+ Diff::delete(b"ABCD"),

+ Diff::equal(b"a"),

+ Diff::delete(b"="),

+ Diff::insert(b"-"),

+ Diff::equal(b"bcd"),

+ Diff::delete(b"="),

+ Diff::insert(b"-"),

+ Diff::equal(b"efghijklmnopqrs"),

+ Diff::delete(b"EFGHIJKLMNOefg"),

+ ],

+ dmp.diff_main("ABCDa=bcd=efghijklmnopqrsEFGHIJKLMNOefg", "a-bcd-efghijklmnopqrs")

+ );

+ // Large equality.

+ assert_eq!(

+ vec![

+ Diff::insert(b" "),

+ Diff::equal(b"a"),

+ Diff::insert(b"nd"),

+ Diff::equal(b" [[Hepatopancreatic]]"),

+ Diff::delete(b" and [[New"),

+ ],

+ dmp.diff_main("a [[Hepatopancreatic]] and [[New", " and [[Hepatopancreatic]]")

+ );

+ // Timeout.

+ const LOW_TIMEOUT: u64 = 100;

+ dmp.timeout = Some(LOW_TIMEOUT);

+ let a = vec!["`Twas brillig, and the slithy toves\nDid gyre and gimble in the wabe:\nAll mimsy were the borogoves,\nAnd the mome raths outgrabe.\n"; 2048].join("");

+ let b = vec!["I am the very model of a modern major general,\nI\'ve information vegetable, animal, and mineral,\nI know the kings of England, and I quote the fights historical,\nFrom Marathon to Waterloo, in order categorical.\n"; 2048].join("");

+

+ let start = Instant::now();

+ dmp.diff_main(&a, &b);

+ let end = Instant::now();

+ // Test that we took at least the timeout period (+ 5ms being generous).

+ assert!((end - start).as_millis() <= LOW_TIMEOUT as u128 + 5);

+

+ // Test the linemode speedup.

+ // Must be long to pass the 100 char cutoff.

+ // Simple line-mode.

+ let a = "12345678901234567890123456789 0123456 78901234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n";

+ let b = "abcdefghij abcdefghij abcdefghij abcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\n";

+ dmp.checklines = Some(false);

+ // let start = Instant::now();

+ let res_no_lm = dmp.diff_main(a, b);

+ // let no_lm = Instant::now() - start;

+ dmp.checklines = Some(true);

+ // let start = Instant::now();

+ let res_yes_lm = dmp.diff_main(a, b);

+ // let yes_lm = Instant::now() - start;

+

+ // Now, we'll run 2 checks - one for result equality, two for speedup

+ assert_eq!(res_no_lm, res_yes_lm);

+ // Fails, no-linemode takes less time than with linemode optimizations

+ // Off by a few 30μs

+ // assert!(no_lm > yes_lm);

+

+ // Single line-mode.

+ let a = "1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890";

+ let b = "abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghij";

+ dmp.checklines = Some(true);

+ let yes_lm = dmp.diff_main(a, b);

+ dmp.checklines = Some(false);

+ let no_lm = dmp.diff_main(a, b);

+ assert_eq!(no_lm, yes_lm);

+

+ // Overlap line-mode.

+ let a = "1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n";

+ let b = "abcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n";

+ dmp.checklines = Some(true);

+ let yes_lm = dmp.diff_main(a, b);

+ dmp.checklines = Some(false);

+ let no_lm = dmp.diff_main(a, b);

+ assert_eq!(rebuild_text(&yes_lm[..]), rebuild_text(&no_lm[..]));

+

+ // TODO

+

+ // Helper to construct the two texts which made up the diff originally.

+ fn rebuild_text(diffs: &[Diff]) -> (String, String) {

+ let mut txt1 = vec![];

+ let mut txt2 = vec![];

+

+ diffs.iter()

+ .for_each(|d| {

+ let mut txt = d.1.clone();

+ if d.0 != Ops::Insert {

+ txt1.append(&mut txt);

+ }

+

+ let mut txt = d.1.clone();

+ if d.0 != Ops::Delete {

+ txt2.append(&mut txt);

+ }

+ });

+

+ (String::from_utf8(txt1).unwrap(), String::from_utf8(txt2).unwrap())

+ }

+ // function diff_rebuildtexts(diffs) {

+ //

+ // var text1 = '';

+ // var text2 = '';

+ // for (var x = 0; x < diffs.length; x++) {

+ // if (diffs[x][0] != DIFF_INSERT) {

+ // text1 += diffs[x][1];

+ // }

+ // if (diffs[x][0] != DIFF_DELETE) {

+ // text2 += diffs[x][1];

+ // }

+ // }

+ // return [text1, text2];

+ // }