+use std::{collections::HashMap, io::BufRead, time::{Duration, Instant}};

+ fn main_internal(&self, old_bytes: &[u8], new_bytes: &[u8]) -> Vec<Diff> {

+ let mut diffs = self.compute(&old_bytes[common_prefix .. old_bytes.len() - common_suffix], &new_bytes[common_prefix .. new_bytes.len() - common_suffix]);

+ fn compute(&self, old: &[u8], new: &[u8]) -> Vec<Diff> {

+ if let Some(half_match) = self.half_match(old, new) {

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

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

+ return self.line_mode(old, new);

+ fn half_match<'a>(&self, old: &'a [u8], new: &'a [u8]) -> Option<HalfMatch<'a>> {

+ let hm1 = Self::half_match_i(long, short, long.len() / 4 );

+ let hm2 = Self::half_match_i(long, short, long.len() / 2 );

+

+ // Quick line-level diff on both strings, then rediff the parts for greater accuracy

+ // This speedup can produce non-minimal diffs

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

+ let to_chars = Self::lines_to_chars(old, new);

+ let mut diffs = self.main_internal(

+ to_chars.chars_old.as_bytes(),

+ to_chars.chars_new.as_bytes()

+ );

+

+ Self::chars_to_lines(&mut diffs[..], &to_chars.lines[..]);

+ // anubhab

+ fn half_match_i<'a>(long: &'a[u8], short: &'a[u8], idx: usize) -> Option<HalfMatch<'a>> {

+#[derive(Debug, Eq, PartialEq)]

+struct LineToChars<'a> {

+ chars_old: String,

+ chars_new: String,

+ lines: Vec<&'a [u8]>

+}

+

+impl DiffMatchPatch {

+ fn lines_to_chars<'a>(old: &'a [u8], new: &'a [u8]) -> LineToChars<'a> {

+ let mut lines: Vec<&'a [u8]> = vec![];

+ let mut linehash: HashMap<&'a [u8], usize> = HashMap::new();

+

+ // Allocate 2/3rds of the space for text1, the rest for text2.

+ let mut maxlines = 5;

+ // let mut maxlines = 40000;

+ let chars_old = Self::lines_to_chars_internal(old, &mut lines, &mut linehash, maxlines);

+

+ // This basically represents the U16::MAX value

+ // maxlines = 65535;

+ maxlines = 7;

+ let chars_new = Self::lines_to_chars_internal(new, &mut lines, &mut linehash, maxlines);

+

+ LineToChars {

+ chars_old,

+ chars_new,

+ lines

+ }

+ }

+

+ fn lines_to_chars_internal<'a>(text: &'a [u8], array: &mut Vec<&'a [u8]>, hash: &mut HashMap<&'a [u8], usize>, maxlines: usize) -> String {

+ let take = maxlines - array.len();

+ println!("Take: {take}");

+

+ let lines = text.split_inclusive(|u| *u == b'\n').enumerate();

+ let mut charlist = Vec::with_capacity(take + 1);

+

+ let mut broke = None;

+

+ while let Some((idx, line)) = lines.next() {

+

+ let entry = hash.entry(line).or_insert(array.len());

+ // fresh insert

+ if entry == &array.len() {

+ array.push(line);

+ }

+

+ // We know the `maxlines = 65535`, this will never fail

+ charlist.push(char::from_u32(*entry as u32).unwrap())

+

+ if idx == take - 1 {

+ broke = Some(idx);

+ break;

+ }

+ }

+

+ let mut chars: String = charlist.join("");

+ if let Some(b) = broke {

+ let remainder = String::from_utf8(

+ lines.skip(b)

+ .map(|(_, l)| l)

+ .collect::<Vec<_>>()

+ .concat()

+ ).unwrap().as_str();

+

+

+ }

+ // let mut chars = lines.take(take)

+ // .map(|line| {

+ //

+

+ // // fresh insert

+ // if entry == &array.len() {

+ // array.push(line);

+ // }

+

+ // // We know the `maxlines = 65535`, this will never fail

+ // char::from_u32(*entry as u32).unwrap()

+ // }).collect::<String>();

+

+ // let t = ;

+ chars.push_str(String::from_utf8(lines.collect::<Vec<_>>().concat()).unwrap().as_str());

+

+ chars.to_owned()

+ }

+

+ fn chars_to_lines(diffs: &mut [Diff], lines: &[&[u8]]) {

+ diffs.iter_mut()

+ .for_each(|d| {

+ let chars = &d.1;

+ let t = chars.chars().map(|c| {

+ let idx: u32 = c.into();

+ *lines.get(idx as usize).unwrap()

+ }).collect::<Vec<_>>()

+ .concat();

+

+ d.1 = String::from_utf8(t).unwrap()

+ });

+ }

+}

+

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

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

+ assert!(dmp.half_match("1234567890".as_bytes(), "abcdef".as_bytes()).is_none());

+ assert!(dmp.half_match("12345".as_bytes(), "23".as_bytes()).is_none());

+ dmp.half_match("1234567890".as_bytes(), "a345678z".as_bytes())

+ dmp.half_match("a345678z".as_bytes(), "1234567890".as_bytes())

+ dmp.half_match("abc56789z".as_bytes(), "1234567890".as_bytes())

+ dmp.half_match("a23456xyz".as_bytes(), "1234567890".as_bytes())

+ dmp.half_match("121231234123451234123121".as_bytes(), "a1234123451234z".as_bytes())

+ dmp.half_match("x-=-=-=-=-=-=-=-=-=-=-=-=".as_bytes(), "xx-=-=-=-=-=-=-=".as_bytes())

+ dmp.half_match("-=-=-=-=-=-=-=-=-=-=-=-=y".as_bytes(), "-=-=-=-=-=-=-=yy".as_bytes())

+ dmp.half_match("qHilloHelloHew".as_bytes(), "xHelloHeHulloy".as_bytes())

+ assert!(dmp.half_match("qHilloHelloHew".as_bytes(), "xHelloHeHulloy".as_bytes()).is_none());

+

+ #[test]

+ fn test_diff_lines_to_chars() {

+ // Convert lines down to characters.

+ assert_eq!(

+ LineToChars { chars_old: [0_usize, 1, 0].iter().map(|i| char::from_u32(*i as u32).unwrap()).collect::<String>(), chars_new: [1_usize, 0, 1].iter().map(|i| char::from_u32(*i as u32).unwrap()).collect::<String>(), lines: vec![b"alpha\n", b"beta\n"] },

+ DiffMatchPatch::lines_to_chars(b"alpha\nbeta\nalpha\n", b"beta\nalpha\nbeta\n")

+ );

+ assert_eq!(

+ LineToChars { chars_old: String::new(), chars_new: [0_usize, 1, 2, 2].iter().map(|i| char::from_u32(*i as u32).unwrap()).collect::<String>(), lines: vec![b"alpha\r\n", b"beta\r\n", b"\r\n"] },

+ DiffMatchPatch::lines_to_chars(b"", b"alpha\r\nbeta\r\n\r\n\r\n")

+ );

+ assert_eq!(

+ LineToChars { chars_old: [0_usize].iter().map(|i| char::from_u32(*i as u32).unwrap()).collect::<String>(), chars_new: [1_usize].iter().map(|i| char::from_u32(*i as u32).unwrap()).collect::<String>(), lines: vec![b"a", b"b"] },

+ DiffMatchPatch::lines_to_chars(b"a", b"b")

+ );

+

+ // More than 256 to reveal any 8-bit limitations.

+ const TLIMIT: usize = 300;

+ let linestr = (0 .. TLIMIT).map(|i| format!("{i}\n")).collect::<Vec<_>>();

+ let linelist: Vec<&[u8]> = (0 .. TLIMIT).map(|i| linestr[i].as_bytes()).collect();

+ let charlist = (0 .. TLIMIT).map(|i| char::from_u32(i as u32).unwrap()).collect::<String>();

+

+ assert_eq!(

+ LineToChars { chars_old: charlist, chars_new: String::new(), lines: linelist },

+ DiffMatchPatch::lines_to_chars(linestr.join("").as_bytes(), b"")

+ );

+ }

+

+ #[test]

+ fn test_diff_chars_to_lines() {

+ // Convert chars up to lines.

+ let mut diffs = [

+ Diff::new(Ops::Equal, [0_usize, 1, 0].iter().map(|i| char::from_u32(*i as u32).unwrap()).collect::<String>().as_bytes()),

+ Diff::new(Ops::Insert, [1_usize, 0, 1].iter().map(|i| char::from_u32(*i as u32).unwrap()).collect::<String>().as_bytes())

+ ];

+

+ DiffMatchPatch::chars_to_lines(&mut diffs, &[b"alpha\n", b"beta\n"]);

+

+ assert_eq!([

+ Diff::new(Ops::Equal,b"alpha\nbeta\nalpha\n"),

+ Diff::new(Ops::Insert, b"beta\nalpha\nbeta\n")

+ ], diffs);

+

+

+ // More than 256 to reveal any 8-bit limitations.

+ const TLIMIT: usize = 300;

+

+ let charlist = (0 .. TLIMIT).map(|i| char::from_u32(i as u32).unwrap()).collect::<String>();

+ let linestr = (0 .. TLIMIT).map(|i| format!("{i}\n")).collect::<Vec<_>>();

+ let linelist: Vec<&[u8]> = (0 .. TLIMIT).map(|i| linestr[i].as_bytes()).collect();

+

+ let mut diffs = [Diff::new(Ops::Delete, charlist.as_bytes())];

+ DiffMatchPatch::chars_to_lines(&mut diffs, &linelist[..]);

+

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

+

+ // More than 65536 to verify any 16-bit limitation.

+ const ULIMIT: usize = 10;

+ let linestr = (0 .. ULIMIT).map(|i| format!("{i}\n")).collect::<Vec<_>>();

+ let lines = linestr.join("");

+ let l2c = DiffMatchPatch::lines_to_chars(lines.as_bytes(), b"");

+

+ let mut diffs = [Diff::new(Ops::Insert, l2c.chars_old.as_bytes())];

+ DiffMatchPatch::chars_to_lines(&mut diffs, &l2c.lines);

+

+ assert_eq!(lines, diffs[0].1);

+ // lineList = [];

+ // for (var i = 0; i < 66000; i++) {

+ // lineList[i] = i + '\n';

+ // }

+ // chars = lineList.join('');

+ // var results = dmp.diff_linesToChars_(chars, '');

+ // diffs = [[DIFF_INSERT, results.chars1]];

+ // dmp.diff_charsToLines_(diffs, results.lineArray);

+ // assertEquals(chars, diffs[0][1]);

+ }