git.iko.soy/helix
on 376c19e help sign in
helix/helix-core/src/diff.rs
221 lines 7.2 kB history raw
1use std::ops::Range;
2use std::time::Instant;
4use imara_diff::intern::InternedInput;
5use imara_diff::Algorithm;
6use ropey::RopeSlice;
8use crate::{ChangeSet, Rope, Tendril, Transaction};
10/// A `imara_diff::Sink` that builds a `ChangeSet` for a character diff of a hunk
11struct CharChangeSetBuilder<'a> {
12 res: &'a mut ChangeSet,
13 hunk: &'a InternedInput<char>,
14 pos: u32,
17impl imara_diff::Sink for CharChangeSetBuilder<'_> {
18 type Out = ();
19 fn process_change(&mut self, before: Range<u32>, after: Range<u32>) {
20 self.res.retain((before.start - self.pos) as usize);
21 self.res.delete(before.len());
22 self.pos = before.end;
24 let res = self.hunk.after[after.start as usize..after.end as usize]
25 .iter()
26 .map(|&token| self.hunk.interner[token])
27 .collect();
29 self.res.insert(res);
30 }
32 fn finish(self) -> Self::Out {
33 self.res.retain(self.hunk.before.len() - self.pos as usize);
34 }
37struct LineChangeSetBuilder<'a> {
38 res: ChangeSet,
39 after: RopeSlice<'a>,
40 file: &'a InternedInput<RopeSlice<'a>>,
41 current_hunk: InternedInput<char>,
42 pos: u32,
45impl imara_diff::Sink for LineChangeSetBuilder<'_> {
46 type Out = ChangeSet;
48 fn process_change(&mut self, before: Range<u32>, after: Range<u32>) {
49 let len = self.file.before[self.pos as usize..before.start as usize]
50 .iter()
51 .map(|&it| self.file.interner[it].len_chars())
52 .sum();
53 self.res.retain(len);
54 self.pos = before.end;
56 // do not perform diffs on large hunks
57 let len_before = before.end - before.start;
58 let len_after = after.end - after.start;
60 // Pure insertions/removals do not require a character diff.
61 // Very large changes are ignored because their character diff is expensive to compute
62 // TODO adjust heuristic to detect large changes?
63 if len_before == 0
64 || len_after == 0
65 || len_after > 5 * len_before
66 || 5 * len_after < len_before && len_before > 10
67 || len_before + len_after > 200
68 {
69 let remove = self.file.before[before.start as usize..before.end as usize]
70 .iter()
71 .map(|&it| self.file.interner[it].len_chars())
72 .sum();
73 self.res.delete(remove);
74 let mut fragment = Tendril::new();
75 if len_after > 500 {
76 // copying a rope line by line is slower then copying the entire
77 // rope. Use to_string for very large changes instead..
78 if self.file.after.len() == after.end as usize {
79 if after.start == 0 {
80 fragment = self.after.to_string().into();
81 } else {
82 let start = self.after.line_to_char(after.start as usize);
83 fragment = self.after.slice(start..).to_string().into();
84 }
85 } else if after.start == 0 {
86 let end = self.after.line_to_char(after.end as usize);
87 fragment = self.after.slice(..end).to_string().into();
88 } else {
89 let start = self.after.line_to_char(after.start as usize);
90 let end = self.after.line_to_char(after.end as usize);
91 fragment = self.after.slice(start..end).to_string().into();
92 }
93 } else {
94 for &line in &self.file.after[after.start as usize..after.end as usize] {
95 for chunk in self.file.interner[line].chunks() {
96 fragment.push_str(chunk)
97 }
98 }
99 };
100 self.res.insert(fragment);
101 } else {
102 // for reasonably small hunks, generating a ChangeSet from char diff can save memory
103 // TODO use a tokenizer (word diff?) for improved performance
104 let hunk_before = self.file.before[before.start as usize..before.end as usize]
105 .iter()
106 .flat_map(|&it| self.file.interner[it].chars());
107 let hunk_after = self.file.after[after.start as usize..after.end as usize]
108 .iter()
109 .flat_map(|&it| self.file.interner[it].chars());
110 self.current_hunk.update_before(hunk_before);
111 self.current_hunk.update_after(hunk_after);
113 // the histogram heuristic does not work as well
114 // for characters because the same characters often reoccur
115 // use myer diff instead
116 imara_diff::diff(
117 Algorithm::Myers,
118 &self.current_hunk,
119 CharChangeSetBuilder {
120 res: &mut self.res,
121 hunk: &self.current_hunk,
122 pos: 0,
123 },
124 );
126 self.current_hunk.clear();
127 }
128 }
130 fn finish(mut self) -> Self::Out {
131 let len = self.file.before[self.pos as usize..]
132 .iter()
133 .map(|&it| self.file.interner[it].len_chars())
134 .sum();
136 self.res.retain(len);
137 self.res
138 }
141struct RopeLines<'a>(RopeSlice<'a>);
143impl<'a> imara_diff::intern::TokenSource for RopeLines<'a> {
144 type Token = RopeSlice<'a>;
145 type Tokenizer = ropey::iter::Lines<'a>;
147 fn tokenize(&self) -> Self::Tokenizer {
148 self.0.lines()
149 }
151 fn estimate_tokens(&self) -> u32 {
152 // we can provide a perfect estimate which is very nice for performance
153 self.0.len_lines() as u32
154 }
157/// Compares `old` and `new` to generate a [`Transaction`] describing
158/// the steps required to get from `old` to `new`.
159pub fn compare_ropes(before: &Rope, after: &Rope) -> Transaction {
160 let start = Instant::now();
161 let res = ChangeSet::with_capacity(32);
162 let after = after.slice(..);
163 let file = InternedInput::new(RopeLines(before.slice(..)), RopeLines(after));
164 let builder = LineChangeSetBuilder {
165 res,
166 file: &file,
167 after,
168 pos: 0,
169 current_hunk: InternedInput::default(),
170 };
172 let res = imara_diff::diff(Algorithm::Histogram, &file, builder).into();
174 log::debug!(
175 "rope diff took {}s",
176 Instant::now().duration_since(start).as_secs_f64()
177 );
178 res
181#[cfg(test)]
182mod tests {
183 use super::*;
185 fn test_identity(a: &str, b: &str) {
186 let mut old = Rope::from(a);
187 let new = Rope::from(b);
188 compare_ropes(&old, &new).apply(&mut old);
189 assert_eq!(old, new);
190 }
192 quickcheck::quickcheck! {
193 fn test_compare_ropes(a: String, b: String) -> bool {
194 let mut old = Rope::from(a);
195 let new = Rope::from(b);
196 compare_ropes(&old, &new).apply(&mut old);
197 old == new
198 }
199 }
201 #[test]
202 fn equal_files() {
203 test_identity("foo", "foo");
204 }
206 #[test]
207 fn trailing_newline() {
208 test_identity("foo\n", "foo");
209 test_identity("foo", "foo\n");
210 }
212 #[test]
213 fn new_file() {
214 test_identity("", "foo");
215 }
217 #[test]
218 fn deleted_file() {
219 test_identity("foo", "");
220 }