{"header":{"message":"Init with the new Pijul","description":null,"timestamp":"2021-02-01T09:49:13.042221182Z","authors":[{"full_name":"Pierre-Étienne Meunier","name":"pmeunier"}]},"hash":"XNQ4AFHIXFKIQECZRFK3NUVN5SZYLH2B5SG2GEYLQNIMDR3KHLFQC","authors":[],"deps":{"hashes":[["XNQ4AFHIXFKIQECZRFK3NUVN5SZYLH2B5SG2GEYLQNIMDR3KHLFQC","Init with the new Pijul"],["AA",null]],"deps":[],"known":[]},"hunks":[{"FileAdd":{"meta":{"basename":"src","metadata":1005},"context":[{"change":1,"pos":0}],"contents":[]}},{"FileAdd":{"meta":{"basename":"test.rs","metadata":420},"context":[{"change":0,"pos":6}],"contents":[{"Add":"use {myers, Diff, Replace};"},{"Add":""},{"Add":"#[test]"},{"Add":"fn test_diff() {"},{"Add":" let a: &[usize] = &[0, 1, 2, 3, 4];"},{"Add":" let b: &[usize] = &[0, 1, 2, 9, 4];"},{"Add":" struct D {}"},{"Add":" impl Diff for D {"},{"Add":" type Error = ();"},{"Add":" fn delete(&mut self, o: usize, len: usize, new: usize) -> Result<(), ()> {"},{"Add":" assert_eq!(o, 3);"},{"Add":" assert_eq!(len, 1);"},{"Add":" assert_eq!(new, 3);"},{"Add":" println!(\"delete\");"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" fn insert(&mut self, o: usize, n: usize, len: usize) -> Result<(), ()> {"},{"Add":" assert_eq!(o, 3);"},{"Add":" assert_eq!(n, 3);"},{"Add":" assert_eq!(len, 1);"},{"Add":" println!(\"insert\");"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" }"},{"Add":" let mut diff = Replace::new(D {});"},{"Add":" myers::diff(&mut diff, a, 0, a.len(), b, 0, b.len()).unwrap()"},{"Add":"}"},{"Add":""},{"Add":"#[test]"},{"Add":"fn test_contiguous() {"},{"Add":" let a: &[usize] = &[0, 1, 2, 3, 4, 4, 4, 5];"},{"Add":" let b: &[usize] = &[0, 1, 2, 8, 9, 4, 4, 7];"},{"Add":" struct D {}"},{"Add":" impl Diff for D {"},{"Add":" type Error = ();"},{"Add":" fn delete(&mut self, _o: usize, _len: usize, _new: usize) -> Result<(), ()> {"},{"Add":" panic!(\"Should not delete\")"},{"Add":" }"},{"Add":" fn insert(&mut self, _o: usize, _n: usize, _len: usize) -> Result<(), ()> {"},{"Add":" panic!(\"Should not insert\")"},{"Add":" }"},{"Add":" fn replace(&mut self, o: usize, l: usize, n: usize, nl: usize) -> Result<(), ()> {"},{"Add":" assert!(o != 3 || (l == 2 && nl == 2));"},{"Add":" assert!(o != 7 || (l == 1 && nl == 1));"},{"Add":" println!(\"replace {:?} {:?} {:?} {:?}\", o, l, n, nl);"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" }"},{"Add":" let mut diff = Replace::new(D {});"},{"Add":" myers::diff(&mut diff, a, 0, a.len(), b, 0, b.len()).unwrap();"},{"Add":"}"},{"Add":""},{"Add":"#[test]"},{"Add":"fn test_replace() {"},{"Add":" let a: &[usize] = &[0, 1, 2, 3, 4];"},{"Add":" let b: &[usize] = &[0, 1, 2, 7, 8, 9];"},{"Add":" struct D {}"},{"Add":" impl Diff for D {"},{"Add":" type Error = ();"},{"Add":" fn delete(&mut self, _o: usize, _len: usize, _new: usize) -> Result<(), ()> {"},{"Add":" panic!(\"should not delete\")"},{"Add":" }"},{"Add":" fn insert(&mut self, _o: usize, _n: usize, _len: usize) -> Result<(), ()> {"},{"Add":" panic!(\"should not insert\")"},{"Add":" }"},{"Add":" fn replace(&mut self, _o: usize, _l: usize, _n: usize, _nl: usize) -> Result<(), ()> {"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" }"},{"Add":" let mut diff = Replace::new(D {});"},{"Add":" myers::diff(&mut diff, a, 0, a.len(), b, 0, b.len()).unwrap();"},{"Add":"}"},{"Add":""},{"Add":"#[test]"},{"Add":"fn test_pat() {"},{"Add":" let a: &[usize] = &[0, 1, 3, 4, 5];"},{"Add":" let b: &[usize] = &[0, 1, 4, 5, 8, 9];"},{"Add":" struct D {}"},{"Add":" impl Diff for D {"},{"Add":" type Error = ();"},{"Add":" fn delete(&mut self, _o: usize, _len: usize, _new: usize) -> Result<(), ()> {"},{"Add":" println!(\"delete {:?} {:?} {:?}\", _o, _len, _new);"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" fn insert(&mut self, _o: usize, _n: usize, _len: usize) -> Result<(), ()> {"},{"Add":" println!(\"insert {:?} {:?} {:?}\", _o, _n, _len);"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" fn replace(&mut self, _o: usize, _l: usize, _n: usize, _nl: usize) -> Result<(), ()> {"},{"Add":" println!(\"replace {:?} {:?} {:?} {:?}\", _o, _l, _n, _nl);"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" }"},{"Add":" let mut diff = Replace::new(D {});"},{"Add":" myers::diff(&mut diff, a, 0, a.len(), b, 0, b.len()).unwrap();"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"replace.rs","metadata":420},"context":[{"change":0,"pos":6}],"contents":[{"Add":"use Diff;"},{"Add":""},{"Add":"/// A \"differ\" that combines deletions and insertions to give blocks"},{"Add":"/// of maximal length, and replacements when appropriate."},{"Add":"pub struct Replace {"},{"Add":" d: D,"},{"Add":" del: Option<(usize, usize, usize)>,"},{"Add":" ins: Option<(usize, usize, usize)>,"},{"Add":" eq: Option<(usize, usize, usize)>,"},{"Add":"}"},{"Add":""},{"Add":"impl Replace {"},{"Add":" pub fn new(d: D) -> Self {"},{"Add":" Replace {"},{"Add":" d,"},{"Add":" del: None,"},{"Add":" ins: None,"},{"Add":" eq: None,"},{"Add":" }"},{"Add":" }"},{"Add":" pub fn into_inner(self) -> D {"},{"Add":" self.d"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl AsRef for Replace {"},{"Add":" fn as_ref(&self) -> &D {"},{"Add":" &self.d"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl AsMut for Replace {"},{"Add":" fn as_mut(&mut self) -> &mut D {"},{"Add":" &mut self.d"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl Diff for Replace {"},{"Add":" type Error = D::Error;"},{"Add":" fn equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), D::Error> {"},{"Add":" if let Some((old0, len0, new0)) = self.del.take() {"},{"Add":" if let Some((_, new1, new_len1)) = self.ins.take() {"},{"Add":" self.d.replace(old0, len0, new1, new_len1)?"},{"Add":" } else {"},{"Add":" self.d.delete(old0, len0, new0)?"},{"Add":" }"},{"Add":" } else if let Some((old0, new0, new_len0)) = self.ins.take() {"},{"Add":" self.d.insert(old0, new0, new_len0)?"},{"Add":" }"},{"Add":""},{"Add":" if let Some((a, b, c)) = self.eq.take() {"},{"Add":" self.eq = Some((a, b, c + len))"},{"Add":" } else {"},{"Add":" self.eq = Some((old, new, len))"},{"Add":" }"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" fn delete(&mut self, old: usize, len: usize, new: usize) -> Result<(), D::Error> {"},{"Add":" if let Some((a, b, c)) = self.eq.take() {"},{"Add":" self.d.equal(a, b, c)?"},{"Add":" }"},{"Add":" if let Some((old0, len0, new0)) = self.del.take() {"},{"Add":" assert_eq!(old, old0 + len0);"},{"Add":" self.del = Some((old0, len0 + len, new0))"},{"Add":" } else {"},{"Add":" self.del = Some((old, len, new))"},{"Add":" }"},{"Add":" Ok(())"},{"Add":" }"},{"Add":""},{"Add":" fn insert(&mut self, old: usize, new: usize, new_len: usize) -> Result<(), D::Error> {"},{"Add":" if let Some((a, b, c)) = self.eq.take() {"},{"Add":" self.d.equal(a, b, c)?"},{"Add":" }"},{"Add":" if let Some((old1, new1, new_len1)) = self.ins.take() {"},{"Add":" assert_eq!(new1 + new_len1, new);"},{"Add":" self.ins = Some((old1, new1, new_len + new_len1))"},{"Add":" } else {"},{"Add":" self.ins = Some((old, new, new_len))"},{"Add":" }"},{"Add":" Ok(())"},{"Add":" }"},{"Add":""},{"Add":" fn replace("},{"Add":" &mut self,"},{"Add":" old: usize,"},{"Add":" old_len: usize,"},{"Add":" new: usize,"},{"Add":" new_len: usize,"},{"Add":" ) -> Result<(), D::Error> {"},{"Add":" if let Some((a, b, c)) = self.eq.take() {"},{"Add":" self.d.equal(a, b, c)?"},{"Add":" }"},{"Add":" self.d.replace(old, old_len, new, new_len)"},{"Add":" }"},{"Add":""},{"Add":" fn finish(&mut self) -> Result<(), D::Error> {"},{"Add":" if let Some((a, b, c)) = self.eq.take() {"},{"Add":" self.d.equal(a, b, c)?"},{"Add":" }"},{"Add":" if let Some((old0, len0, new0)) = self.del.take() {"},{"Add":" if let Some((_, new1, new_len1)) = self.ins.take() {"},{"Add":" self.d.replace(old0, len0, new1, new_len1)?"},{"Add":" } else {"},{"Add":" self.d.delete(old0, len0, new0)?"},{"Add":" }"},{"Add":" } else if let Some((old0, new0, new_len0)) = self.ins.take() {"},{"Add":" self.d.insert(old0, new0, new_len0)?"},{"Add":" }"},{"Add":" self.d.finish()"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"#[test]"},{"Add":"fn myers() {"},{"Add":" use myers;"},{"Add":" let a: &[&str] = &["},{"Add":" \">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\\n\","},{"Add":" \"a\\n\","},{"Add":" \"b\\n\","},{"Add":" \"c\\n\","},{"Add":" \"================================\\n\","},{"Add":" \"d\\n\","},{"Add":" \"e\\n\","},{"Add":" \"f\\n\","},{"Add":" \"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\\n\","},{"Add":" ];"},{"Add":" let b: &[&str] = &["},{"Add":" \">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\\n\","},{"Add":" \"x\\n\","},{"Add":" \"b\\n\","},{"Add":" \"c\\n\","},{"Add":" \"================================\\n\","},{"Add":" \"y\\n\","},{"Add":" \"e\\n\","},{"Add":" \"f\\n\","},{"Add":" \"<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\\n\","},{"Add":" ];"},{"Add":""},{"Add":" struct D {}"},{"Add":" impl Diff for D {"},{"Add":" type Error = ();"},{"Add":" fn equal(&mut self, o: usize, n: usize, len: usize) -> Result<(), ()> {"},{"Add":" println!(\"equal {:?} {:?} {:?}\", o, n, len);"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" fn delete(&mut self, o: usize, len: usize, new: usize) -> Result<(), ()> {"},{"Add":" println!(\"delete {:?} {:?} {:?}\", o, len, new);"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" fn insert(&mut self, o: usize, n: usize, len: usize) -> Result<(), ()> {"},{"Add":" println!(\"insert {:?} {:?} {:?}\", o, n, len);"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" fn replace(&mut self, o: usize, l: usize, n: usize, nl: usize) -> Result<(), ()> {"},{"Add":" println!(\"replace {:?} {:?} {:?} {:?}\", o, l, n, nl);"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" }"},{"Add":" let mut d = Replace::new(D {});"},{"Add":" myers::diff(&mut d, a, 0, a.len(), b, 0, b.len()).unwrap();"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"patience.rs","metadata":420},"context":[{"change":0,"pos":6}],"contents":[{"Add":"use std::collections::hash_map::Entry;"},{"Add":"use std::collections::HashMap;"},{"Add":"use std::hash::Hash;"},{"Add":"use std::ops::Index;"},{"Add":"use {myers, Diff, Replace};"},{"Add":""},{"Add":"struct I<'a, S: 'a + Index + ?Sized> {"},{"Add":" p: &'a S,"},{"Add":" i: usize,"},{"Add":"}"},{"Add":""},{"Add":"impl<'a, A: Index + 'a> std::fmt::Debug for I<'a, A>"},{"Add":"where"},{"Add":" A::Output: std::fmt::Debug,"},{"Add":"{"},{"Add":" fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {"},{"Add":" write!(fmt, \"{:?}\", &self.p[self.i])"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl<'a, 'b, A: Index + 'b + ?Sized, B: Index + 'b + ?Sized> PartialEq>"},{"Add":" for I<'b, B>"},{"Add":"where"},{"Add":" B::Output: PartialEq,"},{"Add":"{"},{"Add":" fn eq(&self, b: &I<'a, A>) -> bool {"},{"Add":" self.p[self.i] == b.p[b.i]"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"fn unique + ?Sized>("},{"Add":" p: &S,"},{"Add":" e0: usize,"},{"Add":" e1: usize,"},{"Add":") -> Vec> {"},{"Add":" let mut aa = HashMap::new();"},{"Add":" for i in e0..e1 {"},{"Add":" match aa.entry(&p[i]) {"},{"Add":" Entry::Vacant(e) => {"},{"Add":" e.insert(Some(i));"},{"Add":" }"},{"Add":" Entry::Occupied(mut e) => {"},{"Add":" let e = e.get_mut();"},{"Add":" if e.is_some() {"},{"Add":" *e = None"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" let mut v: Vec<_> = aa"},{"Add":" .into_iter()"},{"Add":" .filter_map(|(_, x)| x)"},{"Add":" .map(|i| I { p, i })"},{"Add":" .collect();"},{"Add":" v.sort_by(|a, b| a.i.cmp(&b.i));"},{"Add":" v"},{"Add":"}"},{"Add":""},{"Add":"/// Patience diff algorithm."},{"Add":"pub fn diff<"},{"Add":" A: Hash + Eq,"},{"Add":" B: Hash + Eq + PartialEq,"},{"Add":" S: Index + ?Sized,"},{"Add":" T: Index + ?Sized,"},{"Add":" D: Diff,"},{"Add":">("},{"Add":" d: &mut D,"},{"Add":" e: &S,"},{"Add":" e0: usize,"},{"Add":" e1: usize,"},{"Add":" f: &T,"},{"Add":" f0: usize,"},{"Add":" f1: usize,"},{"Add":") -> Result<(), D::Error> {"},{"Add":" let au = unique(e, e0, e1);"},{"Add":" let bu = unique(f, f0, f1);"},{"Add":""},{"Add":" struct Patience<"},{"Add":" 'a,"},{"Add":" 'b,"},{"Add":" 'd,"},{"Add":" S: 'a + Index + ?Sized,"},{"Add":" T: 'b + Index + ?Sized,"},{"Add":" D: Diff + 'd,"},{"Add":" > {"},{"Add":" current_a: usize,"},{"Add":" current_b: usize,"},{"Add":" a1: usize,"},{"Add":" b1: usize,"},{"Add":" a: &'a S,"},{"Add":" b: &'b T,"},{"Add":" d: &'d mut D,"},{"Add":" au: &'a [I<'a, S>],"},{"Add":" bu: &'b [I<'b, T>],"},{"Add":" }"},{"Add":" impl<"},{"Add":" 'a,"},{"Add":" 'b,"},{"Add":" 'd,"},{"Add":" S: 'a + Index + ?Sized,"},{"Add":" T: 'b + Index + ?Sized,"},{"Add":" D: Diff + 'd,"},{"Add":" > Diff for Patience<'a, 'b, 'd, S, T, D>"},{"Add":" where"},{"Add":" T::Output: PartialEq,"},{"Add":" {"},{"Add":" type Error = D::Error;"},{"Add":" fn equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), D::Error> {"},{"Add":" // eprintln!(\"equal {:?} {:?} {:?}\", old, new, len);"},{"Add":" for (old, new) in (old..old + len).zip(new..new + len) {"},{"Add":" let a0 = self.current_a;"},{"Add":" let b0 = self.current_b;"},{"Add":" while self.current_a < self.au[old].i"},{"Add":" && self.current_b < self.bu[new].i"},{"Add":" && self.b[self.current_b] == self.a[self.current_a]"},{"Add":" {"},{"Add":" self.current_a += 1;"},{"Add":" self.current_b += 1;"},{"Add":" }"},{"Add":" if self.current_a > a0 {"},{"Add":" self.d.equal(a0, b0, self.current_a - a0)?"},{"Add":" }"},{"Add":" // let a = &self.a[self.current_a..self.au[old].i];"},{"Add":" // let b = &self.b[self.current_b..self.bu[new].i];"},{"Add":" // eprintln!(\"matching a: {:?} {:?}\", self.current_a, self.au[old].i);"},{"Add":" // eprintln!(\"matching b: {:?} {:?}\", self.current_b, self.bu[new].i);"},{"Add":" myers::diff_offsets("},{"Add":" self.d,"},{"Add":" self.a,"},{"Add":" self.current_a,"},{"Add":" self.au[old].i,"},{"Add":" self.b,"},{"Add":" self.current_b,"},{"Add":" self.bu[new].i,"},{"Add":" )?;"},{"Add":" self.current_a = self.au[old].i;"},{"Add":" self.current_b = self.bu[new].i;"},{"Add":" }"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" /*"},{"Add":" fn insert(&mut self, old: usize, new: usize, len: usize) -> Result<(), D::Error> {"},{"Add":" eprintln!(\"insert {:?} {:?} {:?}\", old, new, len);"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" fn delete(&mut self, old: usize, len: usize) -> Result<(), D::Error> {"},{"Add":" eprintln!(\"delete {:?} {:?}\", old, len);"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" fn replace("},{"Add":" &mut self,"},{"Add":" old: usize,"},{"Add":" len: usize,"},{"Add":" new: usize,"},{"Add":" new_len: usize,"},{"Add":" ) -> Result<(), D::Error> {"},{"Add":" eprintln!(\"replace {:?} {:?} {:?} {:?}\", old, len, new, new_len);"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" */"},{"Add":" fn finish(&mut self) -> Result<(), D::Error> {"},{"Add":" myers::diff("},{"Add":" self.d,"},{"Add":" self.a,"},{"Add":" self.current_a,"},{"Add":" self.a1,"},{"Add":" self.b,"},{"Add":" self.current_b,"},{"Add":" self.b1,"},{"Add":" )"},{"Add":" }"},{"Add":" }"},{"Add":" let mut d = Replace::new(Patience {"},{"Add":" current_a: e0,"},{"Add":" current_b: f0,"},{"Add":" a: e,"},{"Add":" a1: e1,"},{"Add":" b: f,"},{"Add":" b1: f1,"},{"Add":" d,"},{"Add":" au: &au,"},{"Add":" bu: &bu,"},{"Add":" });"},{"Add":" myers::diff(&mut d, &au, 0, au.len(), &bu, 0, bu.len())?;"},{"Add":" Ok(())"},{"Add":"}"},{"Add":""},{"Add":"#[test]"},{"Add":"fn patience() {"},{"Add":" let a: &[usize] = &[11, 1, 2, 2, 3, 4, 4, 4, 5, 47, 19];"},{"Add":" let b: &[usize] = &[10, 1, 2, 2, 8, 9, 4, 4, 7, 47, 18];"},{"Add":" struct D(Vec<(usize, usize, usize, usize)>);"},{"Add":" impl Diff for D {"},{"Add":" type Error = ();"},{"Add":" fn delete(&mut self, o: usize, len: usize, new: usize) -> Result<(), ()> {"},{"Add":" self.0.push((o, len, new, 0));"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" fn insert(&mut self, o: usize, n: usize, len: usize) -> Result<(), ()> {"},{"Add":" self.0.push((o, 0, n, len));"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" fn replace(&mut self, o: usize, l: usize, n: usize, nl: usize) -> Result<(), ()> {"},{"Add":" self.0.push((o, l, n, nl));"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" }"},{"Add":" let mut d = Replace::new(D(Vec::new()));"},{"Add":" diff(&mut d, a, 0, a.len(), b, 0, b.len()).unwrap();"},{"Add":" let d: D = d.into_inner();"},{"Add":" assert_eq!("},{"Add":" d.0.as_slice(),"},{"Add":" &[(0, 1, 0, 1), (4, 2, 4, 2), (8, 1, 8, 1), (10, 1, 10, 1)]"},{"Add":" );"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"myers.rs","metadata":420},"context":[{"change":0,"pos":6}],"contents":[{"Add":"use std::cmp::{max, min};"},{"Add":"use std::ops::Index;"},{"Add":"use Diff;"},{"Add":""},{"Add":"fn modulo(a: isize, b: usize) -> usize {"},{"Add":" let b = b as isize;"},{"Add":" (((a % b) + b) % b) as usize"},{"Add":"}"},{"Add":""},{"Add":"#[test]"},{"Add":"fn test_modulo() {"},{"Add":" assert_eq!(modulo(-11, 10), 9);"},{"Add":" assert_eq!(modulo(23, 7), 2);"},{"Add":" assert_eq!(modulo(-12, 6), 0);"},{"Add":"}"},{"Add":""},{"Add":"/// Myers' diff algorithm. Diff `e`, between indices `e0` (included)"},{"Add":"/// and `e1` (excluded), on the one hand, and `f`, between indices"},{"Add":"/// `f0` (included)` and `f1` (excluded), on the other hand."},{"Add":"pub fn diff + ?Sized, T: Index + ?Sized, D: Diff>("},{"Add":" d: &mut D,"},{"Add":" e: &S,"},{"Add":" e0: usize,"},{"Add":" e1: usize,"},{"Add":" f: &T,"},{"Add":" f0: usize,"},{"Add":" f1: usize,"},{"Add":") -> Result<(), D::Error>"},{"Add":"where"},{"Add":" T::Output: PartialEq,"},{"Add":"{"},{"Add":" diff_offsets(d, e, e0, e1, f, f0, f1)?;"},{"Add":" d.finish()"},{"Add":"}"},{"Add":""},{"Add":"pub(crate) fn diff_offsets + ?Sized, T: Index + ?Sized>("},{"Add":" diff: &mut D,"},{"Add":" e: &S,"},{"Add":" i: usize,"},{"Add":" i_: usize,"},{"Add":" f: &T,"},{"Add":" j: usize,"},{"Add":" j_: usize,"},{"Add":") -> Result<(), D::Error>"},{"Add":"where"},{"Add":" T::Output: PartialEq,"},{"Add":"{"},{"Add":" if i_ > i && j_ > j {"},{"Add":" let n = i_ - i;"},{"Add":" let m = j_ - j;"},{"Add":" let l = (n + m) as isize;"},{"Add":" let z = (2 * min(n, m) + 2) as usize;"},{"Add":" let w = n as isize - m as isize;"},{"Add":" let mut g = vec![0; z as usize];"},{"Add":" let mut p = vec![0; z as usize];"},{"Add":" for h in 0..=(l / 2 + l % 2) {"},{"Add":" macro_rules! search {"},{"Add":" ($e: expr, $c: expr, $d: expr) => {"},{"Add":" let (k0, k1) = {"},{"Add":" let (m, n) = (m as isize, n as isize);"},{"Add":" (-(h - 2*max(0, h - m)), h-2*max(0, h-n)+1)"},{"Add":" };"},{"Add":" for k in (k0..k1).step_by(2) {"},{"Add":" let mut a: usize = if k == -h || k != h && $c[modulo(k-1, z)] < $c[modulo(k+1, z)] {"},{"Add":" $c[modulo(k+1, z)]"},{"Add":" } else {"},{"Add":" $c[modulo(k-1, z)] + 1"},{"Add":" };"},{"Add":" let mut b = (a as isize - k) as usize;"},{"Add":" let (s, t) = (a, b);"},{"Add":" while a < n && b < m && {"},{"Add":" let (e_i, f_i) = if $e { (a, b) } else { (n - a - 1, m - b - 1) };"},{"Add":" f[j + f_i] == e[i + e_i]"},{"Add":" } {"},{"Add":" a += 1;"},{"Add":" b += 1;"},{"Add":" }"},{"Add":" $c[modulo(k, z)] = a;"},{"Add":" let bound = if $e { h-1 } else { h };"},{"Add":" if (l%2 == 1) == $e"},{"Add":" && w-k >= -bound && w-k <= bound"},{"Add":" && $c[modulo(k, z)]+$d[modulo(w-k, z)] >= n"},{"Add":" {"},{"Add":" let (x, y, u, v) = if $e {"},{"Add":" (s, t, a, b)"},{"Add":" } else {"},{"Add":" (n-a, m-b, n-s, m-t)"},{"Add":" };"},{"Add":" if h + bound > 1 || (x != u && y != v) {"},{"Add":" diff_offsets(diff, e, i, i+x, f, j, j+y)?;"},{"Add":" if x != u {"},{"Add":" diff.equal(i + x, j + y, u-x)?;"},{"Add":" }"},{"Add":" diff_offsets(diff, e, i+u, i_, f, j+v, j_)?;"},{"Add":" return Ok(())"},{"Add":" } else if m > n {"},{"Add":" diff.equal(i, j, n)?;"},{"Add":" diff.insert(i+n, j+n, m-n)?;"},{"Add":" return Ok(())"},{"Add":" } else if m < n {"},{"Add":" diff.equal(i, j, m)?;"},{"Add":" diff.delete(i+m, n-m, j+m)?;"},{"Add":" return Ok(())"},{"Add":" } else {"},{"Add":" return Ok(())"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" search!(true, g, p);"},{"Add":" search!(false, p, g);"},{"Add":" }"},{"Add":" } else if i_ > i {"},{"Add":" diff.delete(i, i_ - i, j)?"},{"Add":" } else if j_ > j {"},{"Add":" diff.insert(i, j, j_ - j)?"},{"Add":" }"},{"Add":" Ok(())"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"lib.rs","metadata":420},"context":[{"change":0,"pos":6}],"contents":[{"Add":"//! Various diff (longest common subsequence) algorithms, used in"},{"Add":"//! practice:"},{"Add":"//!"},{"Add":"//! - Myers' diff, in time O((N+M)D) and space O(N+M), where N and M"},{"Add":"//! are the sizes of the old and new version, respectively. See [the"},{"Add":"//! original article by Eugene"},{"Add":"//! W. Myers](http://www.xmailserver.org/diff2.pdf)."},{"Add":"//!"},{"Add":"//! - Patience diff, in time O(N log N + M log M + (N+M)D), and space"},{"Add":"//! O(N+M), which tends to give more human-readable outputs. See [Bram"},{"Add":"//! Cohen's blog post describing"},{"Add":"//! it](https://bramcohen.livejournal.com/73318.html)."},{"Add":""},{"Add":"mod replace;"},{"Add":"pub use replace::*;"},{"Add":"/// Myers' diff algorithm"},{"Add":"pub mod myers;"},{"Add":"/// Patience diff algorithm"},{"Add":"pub mod patience;"},{"Add":""},{"Add":"pub use myers::diff;"},{"Add":""},{"Add":"#[cfg(test)]"},{"Add":"mod test;"},{"Add":""},{"Add":"#[allow(unused_variables)]"},{"Add":"/// A trait for reacting to an edit script from the \"old\" version to"},{"Add":"/// the \"new\" version."},{"Add":"pub trait Diff: Sized {"},{"Add":" type Error;"},{"Add":" /// Called when lines with indices `old` (in the old version) and"},{"Add":" /// `new` (in the new version) start an section equal in both"},{"Add":" /// versions, of length `len`."},{"Add":" fn equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), Self::Error> {"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" /// Called when a section of length `len`, starting at `old`,"},{"Add":" /// needs to be deleted from the old version."},{"Add":" fn delete(&mut self, old: usize, len: usize, new: usize) -> Result<(), Self::Error> {"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" /// Called when a section of the new version, of length `new_len`"},{"Add":" /// and starting at `new`, needs to be inserted at position `old'."},{"Add":" fn insert(&mut self, old: usize, new: usize, new_len: usize) -> Result<(), Self::Error> {"},{"Add":" Ok(())"},{"Add":" }"},{"Add":" /// Called when a section of the old version, starting at index"},{"Add":" /// `old` and of length `old_len`, needs to be replaced with a"},{"Add":" /// section of length `new_len`, starting at `new`, of the new"},{"Add":" /// version."},{"Add":" fn replace("},{"Add":" &mut self,"},{"Add":" old: usize,"},{"Add":" old_len: usize,"},{"Add":" new: usize,"},{"Add":" new_len: usize,"},{"Add":" ) -> Result<(), Self::Error> {"},{"Add":" self.delete(old, old_len, new)?;"},{"Add":" self.insert(old, new, new_len)"},{"Add":" }"},{"Add":" /// Always called at the end of the algorithm."},{"Add":" fn finish(&mut self) -> Result<(), Self::Error> {"},{"Add":" Ok(())"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"impl<'a, D: Diff + 'a> Diff for &'a mut D {"},{"Add":" type Error = D::Error;"},{"Add":" fn equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), Self::Error> {"},{"Add":" (*self).equal(old, new, len)"},{"Add":" }"},{"Add":" fn delete(&mut self, old: usize, len: usize, new: usize) -> Result<(), Self::Error> {"},{"Add":" (*self).delete(old, len, new)"},{"Add":" }"},{"Add":""},{"Add":" fn insert(&mut self, old: usize, new: usize, new_len: usize) -> Result<(), Self::Error> {"},{"Add":" (*self).insert(old, new, new_len)"},{"Add":" }"},{"Add":""},{"Add":" fn replace("},{"Add":" &mut self,"},{"Add":" old: usize,"},{"Add":" old_len: usize,"},{"Add":" new: usize,"},{"Add":" new_len: usize,"},{"Add":" ) -> Result<(), Self::Error> {"},{"Add":" (*self).replace(old, old_len, new, new_len)"},{"Add":" }"},{"Add":""},{"Add":" fn finish(&mut self) -> Result<(), Self::Error> {"},{"Add":" (*self).finish()"},{"Add":" }"},{"Add":"}"}]}},{"FileAdd":{"meta":{"basename":"Cargo.toml","metadata":420},"context":[{"change":1,"pos":0}],"contents":[{"Add":"[package]"},{"Add":"name = \"diffs\""},{"Add":"description = \"A number of diff algorithms, also called longest common subsequence.\""},{"Add":"documentation = \"https://docs.rs/diffs\""},{"Add":"homepage = \"https://nest.pijul.com/pijul_org/pijul\""},{"Add":"version = \"0.4.0\""},{"Add":"license = \"MIT/Apache-2.0\""},{"Add":"authors = [\"Pierre-Étienne Meunier \"]"},{"Add":"include = [\"Cargo.toml\", \"src/lib.rs\", \"src/replace.rs\", \"src/patience.rs\", \"src/myers.rs\", \"src/test.rs\"]"}]}}],"owner":"pijul","repo":"diffs","token":"TYjAF4HVJD7CKbyBp0oHoNznl7V8S+wNmUz8BsVT8J4=","login":null}

…

Dependencies

Change contents