+## 0.4.0

+

+Performance:

+

+ - Non-algorithmic improvements to `Diff` implementation resulting in `~41%` improvements over previous [benchmarks](). [Here's]() a writeup of the experiments.

+

+version = "0.4.0"

+description = "The fastest implementation of Myer's diff algorithm to perform the operations required for synchronizing plain text."

+**Fastest**, **accurate** and **wasm ready** implementation of [Diff Match Patch](https://github.com/dmsnell/diff-match-patch) in Rust based on [Myers' diff algorithm](https://neil.fraser.name/writing/diff/myers.pdf).

+## Benchmarks

+Benchmarks are maintained [diff-match-patch-bench repository](https://github.com/AnubhabB/diff-match-patch-rs-bench)

+

+| Lang. | Library | Diff Avg. | Patch Avg. | Bencher | Mode | Correct |

+|:-------:|:----------------------------------------------------------------------------------------:|:---------:|:----------:|:----------:|:-----------:|:-------:|

+| `rust` | [diff_match_patch v0.1.1](https://crates.io/crates/diff_match_patch)[^1] | 56.618 ms | 9.00 ms | Criterion | - | ✅ |

+| `rust` | [dmp v0.2.0](https://crates.io/crates/dmp) | 56.609 ms | 12.25 ms | Criterion | - | ✅ |

+| `rust` | [diff-match-patch-rs](https://github.com/AnubhabB/diff-match-patch-rs.git)^our | 32.795 ms | 533.17 µs | Criterion | `Efficient`| ✅ |

+| `rust` | [diff-match-patch-rs](https://github.com/AnubhabB/diff-match-patch-rs.git)^our | 33.222 ms | 993.90 µs | Criterion | `Compat` | ✅ |

+| `go` | [go-diff](https://github.com/sergi/go-diff)[^2] | 30.31 ms | 118.2 ms | go test | - | ❗ |

+| `node` | [diff-match-patch](https://www.npmjs.com/package/diff-match-patch)[^3] | 246.90 ms | 1.07 ms | tinybench | - | ❌ |

+| `python`| [diff-match-patch](https://pypi.org/project/diff-match-patch/) | 1.01 s | 0.25 ms | timeit | - | ✅ |

+

+

+[^1]: [diff_match_patch](https://crates.io/crates/diff_match_patch) Adds an extra clone to the iterator because the `patch_apply` method takes mutable refc. to `diffs`.

+[^2]: [go-diff](https://github.com/sergi/go-diff) is technically a correct implementation but it generates far more diffs than any other implementation I've tested. E.g. In our test data [here](https://github.com/AnubhabB/diff-match-patch-rs-bench/testdata) the go lib ends up generating `~3000` diffs while other implementations are generating `~2300` diffs. My guess is one of the cleanup passes are skipped by `go-diff`.

+[^3]: [diff-match-patch](https://www.npmjs.com/package/diff-match-patch) generated `patch text` and `delta` breaks on `unicode surrogates`.

+

+diff-match-patch-rs = "0.4.0"

+///

+///

+///

+///

+ /// helper functions to create op::Delete

+ /// helper functions to create op::Insert

+ /// helper functions to create op::Equal

+ /// returns the operation of the current diff

+ /// returns slice of the data

+ let (common_prefix, common_suffix) = Self::common_prefix_suffix(old_t, new_t);

+

+ let (old_uniq_end, new_uniq_end) =

+ (old_t.len() - common_suffix, new_t.len() - common_suffix);

+

+ // Some elaborate checks to avoid bound checks

+ // slice_start_index_len_fail

+ // slice_end_index_len_fail

+ // slice_index_order_fail

+ let mut diffs = if common_prefix <= old_t.len()

+ && common_prefix <= new_t.len()

+ && old_uniq_end <= old_t.len()

+ && new_uniq_end <= new_t.len()

+ && common_prefix <= old_uniq_end

+ && common_prefix <= new_uniq_end

+ {

+ self.compute(

+ &old_t[common_prefix..old_uniq_end],

+ &new_t[common_prefix..new_uniq_end],

+ linemode,

+ deadline,

+ )?

+ } else {

+ // This is part of the bound check optimization! Should never fail!

+ return Err(crate::errors::Error::InvalidInput);

+ };

+ if common_prefix > 0 && common_prefix <= old_t.len() {

+ if common_suffix > 0 && new_t.len() >= common_suffix && new_uniq_end < new_t.len() {

+ diffs.push(Diff::new(Ops::Equal, &new_t[new_uniq_end..]));

+ if let Some(idx) = long.windows(short.len()).position(|k| k == short) {

+ if long.len() < 4 || (short.len() << 1) < long.len() {

+ let hm1 = Self::half_match_i(long, short, (long.len() + 3) >> 2);

+ let hm2 = Self::half_match_i(long, short, (long.len() + 1) >> 1);

+

+ while pointer < diffs.len() {

+ if idxstart <= idxend {

+ diffs.drain(idxstart..idxend);

+ }

+ let (common_prefix, common_suffix) = Self::common_prefix_suffix(old, new);

+

+ let (old_uniq_end, new_uniq_end) = (old.len() - common_suffix, new.len() - common_suffix);

+ let mut diffs = if common_prefix <= old.len()

+ && common_prefix <= new.len()

+ && old_uniq_end <= old.len()

+ && new_uniq_end <= new.len()

+ && common_prefix <= old_uniq_end

+ && common_prefix <= new_uniq_end

+ {

+ self.compute_lines(

+ &old[common_prefix..old_uniq_end],

+ &new[common_prefix..new_uniq_end],

+ deadline,

+ )?

+ } else {

+ // This is part of the bound check optimization! Should never fail!

+ return Err(crate::errors::Error::InvalidInput);

+ };

+ if common_prefix > 0 && common_prefix <= old.len() {

+ if common_suffix > 0 && new.len() >= common_suffix && new_uniq_end < new.len() {

+ diffs.push(Diff::new(Ops::Equal, &new[new_uniq_end..]));

+ if let Some(idx) = long.windows(short.len()).position(|k| k == short) {

+ let v_offset = (old_len + new_len + 1) >> 1; // same as `max_d`, (/ 2)

+ let v_len = v_offset << 1; // (* 2)

+

+ let mut v = vec![-1_isize; (v_len << 1) as usize];

+ let (v1, v2) = v.split_at_mut(v_len as usize);

+ {

+ let v_trg = v_offset as usize + 1;

+ if v_trg < v1.len() {

+ v1[v_trg] = 0;

+ }

+ if v_trg < v2.len() {

+ v2[v_trg] = 0;

+ }

+ }

+ let front = (delta & 1) != 0;

+ let mut k1start = 0;

+ let mut k1end = 0;

+ let mut k2start = 0;

+ let mut k2end = 0;

+ for edit_dist in 0..v_offset {

+ let mut k1 = k1start - edit_dist;

+ while k1 < edit_dist + 1 - k1end {

+

+ let v1_prev = {

+ let prev_idx = (k1_offset - 1) as usize;

+ if prev_idx < v1.len() {

+ v1[prev_idx]

+ } else {

+ -1

+ }

+ };

+ let v1_next = {

+ let next_idx = (k1_offset + 1) as usize;

+ if next_idx < v1.len() {

+ v1[next_idx]

+ } else {

+ -1

+ }

+ };

+

+ let mut x1 = if k1 == -edit_dist || (k1 != edit_dist && v1_prev < v1_next) {

+ v1_next

+ v1_prev + 1

+ let (xi, yi) = Self::bisect_fwd_path_i(old, new, x1 as usize, y1 as usize);

+

+ y1 = yi as isize;

+ x1 = xi as isize;

+

+ if (0..v1.len() as isize).contains(&k1_offset) {

+ v1[k1_offset as usize] = x1;

+ let k2_offset = (v_offset + delta - k1) as usize;

+ if (0..v_len as usize).contains(&k2_offset)

+ && k2_offset < v2.len()

+ && v2[k2_offset] != -1

+ {

+ let x2 = old_len - v2[k2_offset];

+ let mut k2 = k2start - edit_dist;

+ while k2 < edit_dist + 1 - k2end {

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

+ let prev_idx = k2_offset - 1;

+ let next_idx = k2_offset + 1;

+ let v2_prev = if prev_idx < v2.len() {

+ v2[prev_idx]

+ } else {

+ -1

+ };

+ let v2_next = if next_idx < v2.len() {

+ v2[next_idx]

+ -1

+ };

+

+ let mut x2 = if k2 == -edit_dist || (k2 != edit_dist && v2_prev < v2_next) {

+ v2_next

+ } else {

+ v2_prev + 1

+ let (xi, yi) = Self::bisect_rev_path_i(old, new, x2 as usize, y2 as usize);

+ y2 = yi as isize;

+ x2 = xi as isize;

+

+ if k2_offset < v2.len() {

+ v2[k2_offset] = x2;

+ let k1_offset = (v_offset + delta - k2) as usize;

+ if k1_offset < v_len as usize && k1_offset < v1.len() && v1[k1_offset] != -1 {

+ // if (0..v_len).contains(&k1_offset) && k1_offset < v1.len() as isize && v1[k1_offset as usize] != -1 {

+ let x1 = v1[k1_offset];

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

+ fn bisect_fwd_path_i<'a, T: DType>(

+ old: &'a [T],

+ new: &'a [T],

+ x1: usize,

+ y1: usize,

+ ) -> (usize, usize) {

+ let mut x1 = x1;

+ let mut y1 = y1;

+

+ while x1 < old.len() && y1 < new.len() {

+ if old[x1] != new[y1] {

+ break;

+ }

+

+ x1 += 1;

+ y1 += 1;

+ }

+

+ (x1, y1)

+ }

+

+ fn bisect_rev_path_i<'a, T: DType>(

+ old: &'a [T],

+ new: &'a [T],

+ x2: usize,

+ y2: usize,

+ ) -> (usize, usize) {

+ let mut x2 = x2;

+ let mut y2 = y2;

+

+ while x2 < old.len() && y2 < new.len() {

+ let i1 = if old.len() - x2 > 0 {

+ old.len() - x2 - 1

+ } else {

+ x2 + 1

+ };

+ let i2 = if new.len() - y2 > 0 {

+ new.len() - y2 - 1

+ } else {

+ y2 + 1

+ };

+ if old[i1] != new[i2] {

+ break;

+ }

+ x2 += 1;

+ y2 += 1;

+ }

+

+ (x2, y2)

+ }

+

+ // idx Start index of quarter length substring within longtext.

+ let seed = {

+ let end = idx + (long.len() >> 2);

+ if idx < long.len() && end < long.len() {

+ &long[idx..end]

+ } else {

+ return None;

+ }

+ };

+ while j < short.len() {

+ if let Some(pos) = &short[j..].windows(seed.len()).position(|p| p == seed) {

+ j += *pos;

+

+ let (prefix_len, suffix_len) = if idx < long.len() && j < short.len() {

+ (

+ Self::common_prefix(&long[idx..], &short[j..], false),

+ Self::common_prefix(&long[..idx], &short[..j], true),

+ )

+ } else {

+ // this bound check shouldn't fail .. since it has, no point going further

+ return None;

+ };

+ if best_common.len() < suffix_len + prefix_len {

+ let j_min_suf = j - suffix_len;

+ let j_pls_prf = j + prefix_len;

+ let i_min_suf = idx - suffix_len;

+ let i_pls_prf = idx + prefix_len;

+

+ // Optimizing for bound checks

+ if j_min_suf < j_pls_prf

+ && j_min_suf <= short.len()

+ && j_pls_prf <= short.len()

+ && i_min_suf <= long.len()

+ && i_pls_prf <= long.len()

+ {

+ best_common = &short[j_min_suf..j_pls_prf];

+ best_long_a = &long[..i_min_suf];

+ best_long_b = &long[i_pls_prf..];

+ best_short_a = &short[..j_min_suf];

+ best_short_b = &short[j_pls_prf..];

+ }

+ }

+ j += 1;

+ } else {

+ break;

+ if (best_common.len() << 1) >= long.len() {

+ if lhsrange.end <= lhs.len()

+ && rhsrange.end <= rhs.len()

+ && lhs[lhsrange] == rhs[rhsrange]

+ {

+ pointmid = ((pointmax - pointmin) >> 1) + pointmin; // /2

+ fn common_prefix_suffix<T: DType>(lhs: &[T], rhs: &[T]) -> (usize, usize) {

+ let common_prefix = Self::common_prefix(lhs, rhs, false);

+ let common_suffix = {

+ if common_prefix < lhs.len() && common_prefix < rhs.len() {

+ Self::common_prefix(&lhs[common_prefix..], &rhs[common_prefix..], true)

+ } else {

+ 0

+ }

+ };

+

+ (common_prefix, common_suffix)

+ }

+

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

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

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

+ return l.len();

+ while let Some(found) = r.windows(len).position(|p| p == &l[l.len() - len..]) {

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

+

+ best

+ while pointer < diffs.len() {

+ while !diffs.is_empty() && pointer < diffs.len() {

+ let delete_thres = (delete.len() >> 1) + delete.len() % 2;

+ let insert_thres = (insert.len() >> 1) + insert.len() % 2;

+

+ while !diffs.is_empty() && (1..diffs.len() - 1).contains(&pointer) {

+ while !edit.is_empty() && edit.first() == equality_next.first() {

+ Self::cleanup_merge_first(diffs);

+

+ if Self::cleanup_merge_second(diffs) {

+ Self::cleanup_merge(diffs);

+ }

+ }

+

+ fn cleanup_merge_first<T: DType>(diffs: &mut Vec<Diff<T>>) {

+ // let mut difflen = diffs.len();

+ while pointer < diffs.len() {

+ Self::cleanup_merge_proc_equal(

+ diffs,

+ insert_n,

+ delete_n,

+ insert_data,

+ delete_data,

+ &mut pointer,

+ );

+ // println!("{pointer} {}", diffs.len());

+

+ }

+ // Second pass: look for single edits surrounded on both sides by equalities

+ // which can be shifted sideways to eliminate an equality.

+ // e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC

+ fn cleanup_merge_second<T: DType>(diffs: &mut Vec<Diff<T>>) -> bool {

+ let mut pointer = 1;

+ while !diffs.is_empty() && (1..diffs.len() - 1).contains(&pointer) {

+ let (diff_prev, diff, diff_next) =

+ (&diffs[pointer - 1], &diffs[pointer], &diffs[pointer + 1]);

+ // This is a single edit surrounded by equalities.

+ if diff_prev.op() == Ops::Equal && diff_next.op() == Ops::Equal {

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

+ diff.size() - diff_prev.size()

+ } else {

+ 0

+ };

+ if &diff.data()[substr_idx..] == diff_prev.data() {

+ // Shift the edit over the previous equality.

+ let new_current_data = [

+ diff_prev.data(),

+ &diff.data()[..diff.size() - diff_prev.size()],

+ ]

+ .concat();

+ let new_next_data = [diff_prev.data(), diff_next.data()].concat();

+ diffs[pointer].1 = new_current_data;

+ diffs[pointer + 1].1 = new_next_data;

+ diffs.remove(pointer - 1);

+

+ changes = true;

+ } else if &diff.data()[..if diff_next.size() <= diff.size() {

+ diff_next.size()

+ } else {

+ diff.size()

+ }] == diff_next.data()

+ {

+ // Shift the edit over the next equality.

+ diffs[pointer - 1].1 =

+ [&diffs[pointer - 1].1[..], diffs[pointer + 1].data()].concat();

+ diffs[pointer].1 = [

+ &diffs[pointer].data()[diffs[pointer + 1].size()..],

+ diffs[pointer + 1].data(),

+ ]

+ .concat();

+ diffs.remove(pointer + 1);

+

+ changes = true;

+ changes

+ }

+

+ // Handling `Equality` in the merge process

+ fn cleanup_merge_proc_equal<T: DType>(

+ diffs: &mut Vec<Diff<T>>,

+ insert_n: usize,

+ delete_n: usize,

+ insert_data: Vec<T>,

+ delete_data: Vec<T>,

+ pointer: &mut usize,

+ ) {

+ let mut insert_data = insert_data;

+ let mut delete_data = delete_data;

+

+ // Upon reaching an equality, check for prior redundancies.

+ if delete_n + insert_n > 1 {

+ if delete_n != 0 && insert_n != 0 && !insert_data.is_empty() && !delete_data.is_empty()

+ {

+ // Factor out any common prefixies.

+ let commonlen = Self::common_prefix(&insert_data[..], &delete_data[..], false);

+ if commonlen != 0 && commonlen < insert_data.len() && commonlen < delete_data.len()

+ {

+ let tmpidx = *pointer - delete_n - insert_n - 1;

+ if (0..diffs.len()).contains(&tmpidx) && diffs[tmpidx].op() == Ops::Equal {

+ diffs[tmpidx].1 =

+ [&diffs[tmpidx].1[..], &insert_data[..commonlen]].concat();

+ } else {

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

+ *pointer += 1;

+ }

+ insert_data = insert_data[commonlen..].to_vec();

+ delete_data = delete_data[commonlen..].to_vec();

+ }

+

+ // Factor out any common suffixies.

+ let commonlen = Self::common_prefix(&insert_data[..], &delete_data[..], true);

+ if commonlen > 0 {

+ diffs[*pointer].1 = [

+ &insert_data[insert_data.len() - commonlen..],

+ diffs[*pointer].data(),

+ ]

+ .concat();

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

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

+ }

+ }

+

+ // Delete the offending records and add the merged ones.

+ *pointer -= delete_n + insert_n;

+

+ // Reversing because index will not change

+ (*pointer..*pointer + delete_n + insert_n)

+ .rev()

+ .for_each(|i| {

+ diffs.remove(i);

+ });

+

+ if !delete_data.is_empty() {

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

+ *pointer += 1;

+ }

+

+ if !insert_data.is_empty() {

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

+ *pointer += 1;

+ }

+

+ *pointer += 1;

+ } else if pointer != &0 && diffs[*pointer - 1].op() == Ops::Equal {

+ // Merge this equality with the previous one.;

+ diffs[*pointer - 1].1 = [&diffs[*pointer - 1].1[..], diffs[*pointer].data()].concat();

+ diffs.remove(*pointer);

+ } else {

+ *pointer += 1;

+ || (le.len() < (edit_cost >> 1)

+ if let Some(item) = equalities.pop() {

+ if (0..diffs.len()).contains(&item) {

+ // change the second copy (after the insert in next line) to Insert

+ diffs[item].0 = Ops::Insert;

+ // add an item

+ diffs.insert(item, Diff::delete(le));

+ }

+ }

+

+ if broke && cursor <= text.len() {

+ let mut line = vec![];

+ d.data().iter().for_each(|d| {

+ if let Some(l) = lines.get(*d) {

+ line.append(&mut l.to_vec())

+ }

+ });

+ Diff::new(d.op(), &line)

+ && pattern.len() < self.match_max_bits() - (patch_margin << 1))

+//! **Fastest**, **accurate** and **wasm ready** implementation of [Diff Match Patch](https://github.com/dmsnell/diff-match-patch) in Rust based on [Myers' diff algorithm](https://neil.fraser.name/writing/diff/myers.pdf).

+//! ## Benchmarks

+//! Benchmarks are maintained [diff-match-patch-bench repository](https://github.com/AnubhabB/diff-match-patch-rs-bench)

+//!

+//! | Lang. | Library | Diff Avg. | Patch Avg. | Bencher | Mode | Correct |

+//! |:-------:|:----------------------------------------------------------------------------------------:|:---------:|:----------:|:----------:|:-----------:|:-------:|

+//! | `rust` | [diff_match_patch v0.1.1](https://crates.io/crates/diff_match_patch)[^1] | 56.618 ms | 9.00 ms | Criterion | - | ✅ |

+//! | `rust` | [dmp v0.2.0](https://crates.io/crates/dmp) | 56.609 ms | 12.25 ms | Criterion | - | ✅ |

+//! | `rust` | [diff-match-patch-rs](https://github.com/AnubhabB/diff-match-patch-rs.git)^our | 32.795 ms | 533.17 µs | Criterion | `Efficient`| ✅ |

+//! | `rust` | [diff-match-patch-rs](https://github.com/AnubhabB/diff-match-patch-rs.git)^our | 33.222 ms | 993.90 µs | Criterion | `Compat` | ✅ |

+//! | `go` | [go-diff](https://github.com/sergi/go-diff)[^2] | 30.31 ms | 118.2 ms | go test | - | ❗ |

+//! | `node` | [diff-match-patch](https://www.npmjs.com/package/diff-match-patch)[^3] | 246.90 ms | 1.07 ms | tinybench | - | ❌ |

+//! | `python`| [diff-match-patch](https://pypi.org/project/diff-match-patch/) | 1.01 s | 0.25 ms | timeit | - | ✅ |

+//!

+//! [^1]: [diff_match_patch](https://crates.io/crates/diff_match_patch) Adds an extra clone to the iterator because the `patch_apply` method takes mutable refc. to `diffs`.

+//! [^2]: [go-diff](https://github.com/sergi/go-diff) is technically a correct implementation but it generates far more diffs than any other implementation I've tested. E.g. In our test data [here](https://github.com/AnubhabB/diff-match-patch-rs-bench/testdata) the go lib ends up generating `~3000` diffs while other implementations are generating `~2300` diffs. My guess is one of the cleanup passes are skipped by `go-diff`.That's probably the reason behind unreasonably high `patch` timings.

+//! [^3]: [diff-match-patch](https://www.npmjs.com/package/diff-match-patch) generated `patch text` and `delta` breaks on `unicode surrogates`.

+//!

+//! diff-match-patch-rs = "0.4.0"