git.iko.soy/helix
on 376c19e help sign in
helix/helix-vcs/src/diff.rs
279 lines 9.3 kB history raw
1use std::ops::Range;
2use std::sync::Arc;
4use helix_core::Rope;
5use imara_diff::Algorithm;
6use parking_lot::{Mutex, MutexGuard};
7use tokio::sync::mpsc::{unbounded_channel, UnboundedSender};
8use tokio::sync::{Notify, OwnedRwLockReadGuard, RwLock};
9use tokio::task::JoinHandle;
10use tokio::time::Instant;
12use crate::diff::worker::DiffWorker;
14mod line_cache;
15mod worker;
17type RedrawHandle = (Arc<Notify>, Arc<RwLock<()>>);
19/// A rendering lock passed to the differ the prevents redraws from occurring
20struct RenderLock {
21 pub lock: OwnedRwLockReadGuard<()>,
22 pub timeout: Option<Instant>,
25struct Event {
26 text: Rope,
27 is_base: bool,
28 render_lock: Option<RenderLock>,
31#[derive(Clone, Debug)]
32pub struct DiffHandle {
33 channel: UnboundedSender<Event>,
34 render_lock: Arc<RwLock<()>>,
35 hunks: Arc<Mutex<Vec<Hunk>>>,
36 inverted: bool,
39impl DiffHandle {
40 pub fn new(diff_base: Rope, doc: Rope, redraw_handle: RedrawHandle) -> DiffHandle {
41 DiffHandle::new_with_handle(diff_base, doc, redraw_handle).0
42 }
44 fn new_with_handle(
45 diff_base: Rope,
46 doc: Rope,
47 redraw_handle: RedrawHandle,
48 ) -> (DiffHandle, JoinHandle<()>) {
49 let (sender, receiver) = unbounded_channel();
50 let hunks: Arc<Mutex<Vec<Hunk>>> = Arc::default();
51 let worker = DiffWorker {
52 channel: receiver,
53 hunks: hunks.clone(),
54 new_hunks: Vec::default(),
55 redraw_notify: redraw_handle.0,
56 diff_finished_notify: Arc::default(),
57 };
58 let handle = tokio::spawn(worker.run(diff_base, doc));
59 let differ = DiffHandle {
60 channel: sender,
61 hunks,
62 inverted: false,
63 render_lock: redraw_handle.1,
64 };
65 (differ, handle)
66 }
68 pub fn invert(&mut self) {
69 self.inverted = !self.inverted;
70 }
72 pub fn hunks(&self) -> FileHunks {
73 FileHunks {
74 hunks: self.hunks.lock(),
75 inverted: self.inverted,
76 }
77 }
79 /// Updates the document associated with this redraw handle
80 /// This function is only intended to be called from within the rendering loop
81 /// if called from elsewhere it may fail to acquire the render lock and panic
82 pub fn update_document(&self, doc: Rope, block: bool) -> bool {
83 // unwrap is ok here because the rendering lock is
84 // only exclusively locked during redraw.
85 // This function is only intended to be called
86 // from the core rendering loop where no redraw can happen in parallel
87 let lock = self.render_lock.clone().try_read_owned().unwrap();
88 let timeout = if block {
89 None
90 } else {
91 Some(Instant::now() + tokio::time::Duration::from_millis(SYNC_DIFF_TIMEOUT))
92 };
93 self.update_document_impl(doc, self.inverted, Some(RenderLock { lock, timeout }))
94 }
96 pub fn update_diff_base(&self, diff_base: Rope) -> bool {
97 self.update_document_impl(diff_base, !self.inverted, None)
98 }
100 fn update_document_impl(
101 &self,
102 text: Rope,
103 is_base: bool,
104 render_lock: Option<RenderLock>,
105 ) -> bool {
106 let event = Event {
107 text,
108 is_base,
109 render_lock,
110 };
111 self.channel.send(event).is_ok()
112 }
115/// synchronous debounce value should be low
116/// so we can update synchronously most of the time
117const DIFF_DEBOUNCE_TIME_SYNC: u64 = 1;
118/// maximum time that rendering should be blocked until the diff finishes
119const SYNC_DIFF_TIMEOUT: u64 = 12;
120const DIFF_DEBOUNCE_TIME_ASYNC: u64 = 96;
121const ALGORITHM: Algorithm = Algorithm::Histogram;
122const MAX_DIFF_LINES: usize = 64 * u16::MAX as usize;
123// cap average line length to 128 for files with MAX_DIFF_LINES
124const MAX_DIFF_BYTES: usize = MAX_DIFF_LINES * 128;
126/// A single change in a file potentially spanning multiple lines
127/// Hunks produced by the differs are always ordered by their position
128/// in the file and non-overlapping.
129/// Specifically for any two hunks `x` and `y` the following properties hold:
130///
131/// ``` no_compile
132/// assert!(x.before.end <= y.before.start);
133/// assert!(x.after.end <= y.after.start);
134/// ```
135#[derive(PartialEq, Eq, Clone, Debug)]
136pub struct Hunk {
137 pub before: Range<u32>,
138 pub after: Range<u32>,
141impl Hunk {
142 /// Can be used instead of `Option::None` for better performance
143 /// because lines larger then `i32::MAX` are not supported by `imara-diff` anyways.
144 /// Has some nice properties where it usually is not necessary to check for `None` separately:
145 /// Empty ranges fail contains checks and also fails smaller then checks.
146 pub const NONE: Hunk = Hunk {
147 before: u32::MAX..u32::MAX,
148 after: u32::MAX..u32::MAX,
149 };
151 /// Inverts a change so that `before`
152 pub fn invert(&self) -> Hunk {
153 Hunk {
154 before: self.after.clone(),
155 after: self.before.clone(),
156 }
157 }
159 pub fn is_pure_insertion(&self) -> bool {
160 self.before.is_empty()
161 }
163 pub fn is_pure_removal(&self) -> bool {
164 self.after.is_empty()
165 }
168/// A list of changes in a file sorted in ascending
169/// non-overlapping order
170#[derive(Debug)]
171pub struct FileHunks<'a> {
172 hunks: MutexGuard<'a, Vec<Hunk>>,
173 inverted: bool,
176impl FileHunks<'_> {
177 pub fn is_inverted(&self) -> bool {
178 self.inverted
179 }
181 /// Returns the `Hunk` for the `n`th change in this file.
182 /// if there is no `n`th change `Hunk::NONE` is returned instead.
183 pub fn nth_hunk(&self, n: u32) -> Hunk {
184 match self.hunks.get(n as usize) {
185 Some(hunk) if self.inverted => hunk.invert(),
186 Some(hunk) => hunk.clone(),
187 None => Hunk::NONE,
188 }
189 }
191 pub fn len(&self) -> u32 {
192 self.hunks.len() as u32
193 }
195 pub fn is_empty(&self) -> bool {
196 self.len() == 0
197 }
199 pub fn next_hunk(&self, line: u32) -> Option<u32> {
200 let hunk_range = if self.inverted {
201 |hunk: &Hunk| hunk.before.clone()
202 } else {
203 |hunk: &Hunk| hunk.after.clone()
204 };
206 let res = self
207 .hunks
208 .binary_search_by_key(&line, |hunk| hunk_range(hunk).start);
210 match res {
211 // Search found a hunk that starts exactly at this line, return the next hunk if it exists.
212 Ok(pos) if pos + 1 == self.hunks.len() => None,
213 Ok(pos) => Some(pos as u32 + 1),
215 // No hunk starts exactly at this line, so the search returns
216 // the position where a hunk starting at this line should be inserted.
217 // That position is exactly the position of the next hunk or the end
218 // of the list if no such hunk exists
219 Err(pos) if pos == self.hunks.len() => None,
220 Err(pos) => Some(pos as u32),
221 }
222 }
224 pub fn prev_hunk(&self, line: u32) -> Option<u32> {
225 let hunk_range = if self.inverted {
226 |hunk: &Hunk| hunk.before.clone()
227 } else {
228 |hunk: &Hunk| hunk.after.clone()
229 };
230 let res = self
231 .hunks
232 .binary_search_by_key(&line, |hunk| hunk_range(hunk).end);
234 match res {
235 // Search found a hunk that ends exactly at this line (so it does not include the current line).
236 // We can usually just return that hunk, however a special case for empty hunk is necessary
237 // which represents a pure removal.
238 // Removals are technically empty but are still shown as single line hunks
239 // and as such we must jump to the previous hunk (if it exists) if we are already inside the removal
240 Ok(pos) if !hunk_range(&self.hunks[pos]).is_empty() => Some(pos as u32),
242 // No hunk ends exactly at this line, so the search returns
243 // the position where a hunk ending at this line should be inserted.
244 // That position before this one is exactly the position of the previous hunk
245 Err(0) | Ok(0) => None,
246 Err(pos) | Ok(pos) => Some(pos as u32 - 1),
247 }
248 }
250 pub fn hunk_at(&self, line: u32, include_removal: bool) -> Option<u32> {
251 let hunk_range = if self.inverted {
252 |hunk: &Hunk| hunk.before.clone()
253 } else {
254 |hunk: &Hunk| hunk.after.clone()
255 };
257 let res = self
258 .hunks
259 .binary_search_by_key(&line, |hunk| hunk_range(hunk).start);
261 match res {
262 // Search found a hunk that starts exactly at this line, return it
263 Ok(pos) => Some(pos as u32),
265 // No hunk starts exactly at this line, so the search returns
266 // the position where a hunk starting at this line should be inserted.
267 // The previous hunk contains this hunk if it exists and doesn't end before this line
268 Err(0) => None,
269 Err(pos) => {
270 let hunk = hunk_range(&self.hunks[pos - 1]);
271 if hunk.end > line || include_removal && hunk.start == line && hunk.is_empty() {
272 Some(pos as u32 - 1)
273 } else {
274 None
275 }
276 }
277 }
278 }