inflorescence_libpijul/diff/
diff.rs

1use super::Line;
2
3#[derive(Debug, Clone, Copy, PartialEq, Eq)]
4/// Algorithm used to compute the diff.
5pub enum Algorithm {
6    Myers,
7    Patience,
8    ImaraHistogram,
9}
10
11impl Default for Algorithm {
12    fn default() -> Self {
13        Algorithm::Myers
14    }
15}
16
17pub(super) fn diff(
18    lines_a: &[Line],
19    lines_b: &[Line],
20    algorithm: Algorithm,
21    stop_early: bool,
22) -> D {
23    let result = D {
24        r: Vec::with_capacity(lines_a.len() + lines_b.len()),
25        stop_early,
26    };
27    return match algorithm {
28        Algorithm::Patience => {
29            let mut dd = diffs::Replace::new(result);
30            diffs::patience::diff(
31                &mut dd,
32                lines_a,
33                0,
34                lines_a.len(),
35                lines_b,
36                0,
37                lines_b.len(),
38            )
39            .unwrap_or(());
40            dd.into_inner()
41        }
42        Algorithm::Myers => {
43            let mut dd = diffs::Replace::new(result);
44            diffs::myers::diff(
45                &mut dd,
46                lines_a,
47                0,
48                lines_a.len(),
49                lines_b,
50                0,
51                lines_b.len(),
52            )
53            .unwrap_or(());
54            dd.into_inner()
55        }
56        Algorithm::ImaraHistogram => {
57            let source = imara_diff::intern::InternedInput::new(&Lines(lines_a), &Lines(lines_b));
58            imara_diff::diff(imara_diff::Algorithm::Histogram, &source, result)
59        }
60    };
61}
62#[derive(Debug)]
63pub struct D {
64    pub r: Vec<Replacement>,
65    pub stop_early: bool,
66}
67
68impl D {
69    pub fn len(&self) -> usize {
70        self.r.len()
71    }
72}
73
74impl std::ops::Index<usize> for D {
75    type Output = Replacement;
76    fn index(&self, i: usize) -> &Replacement {
77        self.r.index(i)
78    }
79}
80
81impl std::ops::IndexMut<usize> for D {
82    fn index_mut(&mut self, i: usize) -> &mut Replacement {
83        self.r.index_mut(i)
84    }
85}
86
87#[derive(Debug)]
88pub struct Replacement {
89    pub old: usize,
90    pub old_len: usize,
91    pub new: usize,
92    pub new_len: usize,
93    // pub is_cyclic: bool,
94}
95
96impl diffs::Diff for D {
97    type Error = ();
98    fn delete(&mut self, old: usize, old_len: usize, new: usize) -> std::result::Result<(), ()> {
99        debug!("Diff::delete {:?} {:?} {:?}", old, old_len, new);
100        self.r.push(Replacement {
101            old,
102            old_len,
103            new,
104            new_len: 0,
105            // is_cyclic: false,
106        });
107        if self.stop_early {
108            Err(())
109        } else {
110            Ok(())
111        }
112    }
113    fn insert(&mut self, old: usize, new: usize, new_len: usize) -> std::result::Result<(), ()> {
114        debug!("Diff::insert {:?} {:?} {:?}", old, new, new_len);
115        self.r.push(Replacement {
116            old,
117            old_len: 0,
118            new,
119            new_len,
120            // is_cyclic: false,
121        });
122        if self.stop_early {
123            Err(())
124        } else {
125            Ok(())
126        }
127    }
128    fn replace(
129        &mut self,
130        old: usize,
131        old_len: usize,
132        new: usize,
133        new_len: usize,
134    ) -> std::result::Result<(), ()> {
135        debug!(
136            "Diff::replace {:?} {:?} {:?} {:?}",
137            old, old_len, new, new_len
138        );
139        self.r.push(Replacement {
140            old,
141            old_len,
142            new,
143            new_len,
144            // is_cyclic: false,
145        });
146        if self.stop_early {
147            Err(())
148        } else {
149            Ok(())
150        }
151    }
152}
153
154/// struct used for imara interning see InternedInput
155struct Lines<'a>(&'a [Line<'a>]);
156
157impl<'a> imara_diff::intern::TokenSource for &Lines<'a> {
158    type Token = &'a Line<'a>;
159    type Tokenizer = core::slice::Iter<'a, Line<'a>>;
160
161    fn tokenize(&self) -> Self::Tokenizer {
162        self.0.iter()
163    }
164    fn estimate_tokens(&self) -> u32 {
165        self.0.len() as u32
166    }
167}
168
169impl imara_diff::Sink for D {
170    type Out = D;
171
172    fn process_change(&mut self, before: std::ops::Range<u32>, after: std::ops::Range<u32>) {
173        debug!(
174            "Process change: old:{:?}-{:?} new:{:?}-{:?}",
175            before.start, before.end, after.start, after.end
176        );
177        self.r.push(Replacement {
178            old: before.start as usize,
179            old_len: before.len(),
180            new: after.start as usize,
181            new_len: after.len(),
182            // is_cyclic: false,
183        });
184    }
185
186    fn finish(self) -> Self::Out {
187        self
188    }
189}
190
191fn line_index(lines_a: &[Line], pos_bytes: usize) -> usize {
192    lines_a
193        .binary_search_by(|line| {
194            (line.l.as_ptr() as usize - lines_a[0].l.as_ptr() as usize).cmp(&pos_bytes)
195        })
196        .unwrap()
197}
198
199pub struct Deleted {
200    pub replaced: bool,
201    pub next: usize,
202}
203
204impl D {
205    pub(super) fn is_deleted(&self, lines_a: &[Line], pos: usize) -> Option<Deleted> {
206        let line = line_index(lines_a, pos);
207        match self.r.binary_search_by(|repl| repl.old.cmp(&line)) {
208            Ok(i) if self.r[i].old_len > 0 => Some(Deleted {
209                replaced: self.r[i].new_len > 0,
210                next: pos + lines_a[line].l.len(),
211            }),
212            Err(i) if i == 0 => None,
213            Err(i) if line < self.r[i - 1].old + self.r[i - 1].old_len => Some(Deleted {
214                replaced: self.r[i - 1].new_len > 0,
215                next: pos + lines_a[line].l.len(),
216            }),
217            _ => None,
218        }
219    }
220}
inflorescence_libpijul/diff/diff.rs

inflorescence_libpijul/diff/
diff.rs
