Show (git) diff signs in gutter (#3890)

* Show (git) diff signs in gutter (#3890)

Avoid string allocation when git diffing

Incrementally diff using changesets

refactor diffs to be provider indepndent and improve git implementation

remove dependency on zlib-ng

switch to asynchronus diffing with similar

Update helix-vcs/Cargo.toml

fix toml formatting

Co-authored-by: Ivan Tham <pickfire@riseup.net>

fix typo in documentation

use ropey reexpors from helix-core

fix crash when creating new file

remove useless use if io::Cursor

fix spelling mistakes

implement suggested improvement to repository loading

improve git test isolation

remove lefover comments

Co-authored-by: univerz <univerz@fu-solution.com>

fixed spelling mistake

minor cosmetic changes

fix: set self.differ to None if decoding the diff_base fails

fixup formatting

Co-authored-by: Ivan Tham <pickfire@riseup.net>

reload diff_base when file is reloaded from disk

switch to imara-diff

Fixup formatting

Co-authored-by: Blaž Hrastnik <blaz@mxxn.io>

Redraw buffer whenever a diff is updated.

Only store hunks instead of changes for individual lines to easily allow
jumping between them

Update to latest gitoxide version

Change default diff gutter position

Only update gutter after timeout

* update diff gutter synchronously, with a timeout

* Apply suggestions from code review

Co-authored-by: Blaž Hrastnik <blaz@mxxn.io>
Co-authored-by: Michael Davis <mcarsondavis@gmail.com>

* address review comments and ensure lock is always aquired

* remove configuration for redraw timeout

Co-authored-by: Blaž Hrastnik <blaz@mxxn.io>
Co-authored-by: Michael Davis <mcarsondavis@gmail.com>

5 files changed, 158 insertions, 41 deletions

diff --git a/helix-view/Cargo.toml b/helix-view/Cargo.toml
index a2a88001..13d5da0e 100644
--- a/helix-view/Cargo.toml
+++ b/helix-view/Cargo.toml
@@ -21,6 +21,7 @@ helix-loader = { version = "0.6", path = "../helix-loader" }
 helix-lsp = { version = "0.6", path = "../helix-lsp" }
 helix-dap = { version = "0.6", path = "../helix-dap" }
 crossterm = { version = "0.25", optional = true }
+helix-vcs = { version = "0.6", path = "../helix-vcs" }
 
 # Conversion traits
 once_cell = "1.16"
@@ -43,6 +44,7 @@ log = "~0.4"
 
 which = "4.2"
 
+
 [target.'cfg(windows)'.dependencies]
 clipboard-win = { version = "4.4", features = ["std"] }
 
diff --git a/helix-view/src/document.rs b/helix-view/src/document.rs
index ad47f838..856e5628 100644
--- a/helix-view/src/document.rs
+++ b/helix-view/src/document.rs
@@ -3,6 +3,8 @@ use futures_util::future::BoxFuture;
 use futures_util::FutureExt;
 use helix_core::auto_pairs::AutoPairs;
 use helix_core::Range;
+use helix_vcs::{DiffHandle, DiffProviderRegistry};
+
 use serde::de::{self, Deserialize, Deserializer};
 use serde::Serialize;
 use std::borrow::Cow;
@@ -24,6 +26,7 @@ use helix_core::{
     DEFAULT_LINE_ENDING,
 };
 
+use crate::editor::RedrawHandle;
 use crate::{apply_transaction, DocumentId, Editor, View, ViewId};
 
 /// 8kB of buffer space for encoding and decoding `Rope`s.
@@ -133,6 +136,8 @@ pub struct Document {
 
     diagnostics: Vec<Diagnostic>,
     language_server: Option<Arc<helix_lsp::Client>>,
+
+    diff_handle: Option<DiffHandle>,
 }
 
 use std::{fmt, mem};
@@ -371,6 +376,7 @@ impl Document {
             last_saved_revision: 0,
             modified_since_accessed: false,
             language_server: None,
+            diff_handle: None,
         }
     }
 
@@ -624,16 +630,20 @@ impl Document {
     }
 
     /// Reload the document from its path.
-    pub fn reload(&mut self, view: &mut View) -> Result<(), Error> {
+    pub fn reload(
+        &mut self,
+        view: &mut View,
+        provider_registry: &DiffProviderRegistry,
+        redraw_handle: RedrawHandle,
+    ) -> Result<(), Error> {
         let encoding = &self.encoding;
-        let path = self.path().filter(|path| path.exists());
-
-        // If there is no path or the path no longer exists.
-        if path.is_none() {
-            bail!("can't find file to reload from");
-        }
+        let path = self
+            .path()
+            .filter(|path| path.exists())
+            .ok_or_else(|| anyhow!("can't find file to reload from"))?
+            .to_owned();
 
-        let mut file = std::fs::File::open(path.unwrap())?;
+        let mut file = std::fs::File::open(&path)?;
         let (rope, ..) = from_reader(&mut file, Some(encoding))?;
 
         // Calculate the difference between the buffer and source text, and apply it.
@@ -646,6 +656,11 @@ impl Document {
 
         self.detect_indent_and_line_ending();
 
+        match provider_registry.get_diff_base(&path) {
+            Some(diff_base) => self.set_diff_base(diff_base, redraw_handle),
+            None => self.diff_handle = None,
+        }
+
         Ok(())
     }
 
@@ -787,6 +802,10 @@ impl Document {
 
         if !transaction.changes().is_empty() {
             self.version += 1;
+            // start computing the diff in parallel
+            if let Some(diff_handle) = &self.diff_handle {
+                diff_handle.update_document(self.text.clone(), false);
+            }
 
             // generate revert to savepoint
             if self.savepoint.is_some() {
@@ -1046,6 +1065,23 @@ impl Document {
         server.is_initialized().then(|| server)
     }
 
+    pub fn diff_handle(&self) -> Option<&DiffHandle> {
+        self.diff_handle.as_ref()
+    }
+
+    /// Intialize/updates the differ for this document with a new base.
+    pub fn set_diff_base(&mut self, diff_base: Vec<u8>, redraw_handle: RedrawHandle) {
+        if let Ok((diff_base, _)) = from_reader(&mut diff_base.as_slice(), Some(self.encoding)) {
+            if let Some(differ) = &self.diff_handle {
+                differ.update_diff_base(diff_base);
+                return;
+            }
+            self.diff_handle = Some(DiffHandle::new(diff_base, self.text.clone(), redraw_handle))
+        } else {
+            self.diff_handle = None;
+        }
+    }
+
     #[inline]
     /// Tree-sitter AST tree
     pub fn syntax(&self) -> Option<&Syntax> {
diff --git a/helix-view/src/editor.rs b/helix-view/src/editor.rs
index 5a1ac6b1..973cf82e 100644
--- a/helix-view/src/editor.rs
+++ b/helix-view/src/editor.rs
@@ -9,6 +9,7 @@ use crate::{
     tree::{self, Tree},
     Align, Document, DocumentId, View, ViewId,
 };
+use helix_vcs::DiffProviderRegistry;
 
 use futures_util::stream::select_all::SelectAll;
 use futures_util::{future, StreamExt};
@@ -26,7 +27,10 @@ use std::{
 };
 
 use tokio::{
-    sync::mpsc::{unbounded_channel, UnboundedReceiver, UnboundedSender},
+    sync::{
+        mpsc::{unbounded_channel, UnboundedReceiver, UnboundedSender},
+        Notify, RwLock,
+    },
     time::{sleep, Duration, Instant, Sleep},
 };
 
@@ -454,6 +458,8 @@ pub enum GutterType {
     LineNumbers,
     /// Show one blank space
     Spacer,
+    /// Highlight local changes
+    Diff,
 }
 
 impl std::str::FromStr for GutterType {
@@ -464,6 +470,7 @@ impl std::str::FromStr for GutterType {
             "diagnostics" => Ok(Self::Diagnostics),
             "spacer" => Ok(Self::Spacer),
             "line-numbers" => Ok(Self::LineNumbers),
+            "diff" => Ok(Self::Diff),
             _ => anyhow::bail!("Gutter type can only be `diagnostics` or `line-numbers`."),
         }
     }
@@ -600,6 +607,8 @@ impl Default for Config {
                 GutterType::Diagnostics,
                 GutterType::Spacer,
                 GutterType::LineNumbers,
+                GutterType::Spacer,
+                GutterType::Diff,
             ],
             middle_click_paste: true,
             auto_pairs: AutoPairConfig::default(),
@@ -681,6 +690,7 @@ pub struct Editor {
     pub macro_replaying: Vec<char>,
     pub language_servers: helix_lsp::Registry,
     pub diagnostics: BTreeMap<lsp::Url, Vec<lsp::Diagnostic>>,
+    pub diff_providers: DiffProviderRegistry,
 
     pub debugger: Option<dap::Client>,
     pub debugger_events: SelectAll<UnboundedReceiverStream<dap::Payload>>,
@@ -711,8 +721,15 @@ pub struct Editor {
     pub exit_code: i32,
 
     pub config_events: (UnboundedSender<ConfigEvent>, UnboundedReceiver<ConfigEvent>),
+    /// Allows asynchronous tasks to control the rendering
+    /// The `Notify` allows asynchronous tasks to request the editor to perform a redraw
+    /// The `RwLock` blocks the editor from performing the render until an exclusive lock can be aquired
+    pub redraw_handle: RedrawHandle,
+    pub needs_redraw: bool,
 }
 
+pub type RedrawHandle = (Arc<Notify>, Arc<RwLock<()>>);
+
 #[derive(Debug)]
 pub enum EditorEvent {
     DocumentSaved(DocumentSavedEventResult),
@@ -785,6 +802,7 @@ impl Editor {
             theme: theme_loader.default(),
             language_servers: helix_lsp::Registry::new(),
             diagnostics: BTreeMap::new(),
+            diff_providers: DiffProviderRegistry::default(),
             debugger: None,
             debugger_events: SelectAll::new(),
             breakpoints: HashMap::new(),
@@ -803,6 +821,8 @@ impl Editor {
             auto_pairs,
             exit_code: 0,
             config_events: unbounded_channel(),
+            redraw_handle: Default::default(),
+            needs_redraw: false,
         }
     }
 
@@ -1109,7 +1129,9 @@ impl Editor {
             let mut doc = Document::open(&path, None, Some(self.syn_loader.clone()))?;
 
             let _ = Self::launch_language_server(&mut self.language_servers, &mut doc);
-
+            if let Some(diff_base) = self.diff_providers.get_diff_base(&path) {
+                doc.set_diff_base(diff_base, self.redraw_handle.clone());
+            }
             self.new_document(doc)
         };
 
@@ -1348,24 +1370,39 @@ impl Editor {
     }
 
     pub async fn wait_event(&mut self) -> EditorEvent {
-        tokio::select! {
-            biased;
+        // the loop only runs once or twice and would be better implemented with a recursion + const generic
+        // however due to limitations with async functions that can not be implemented right now
+        loop {
+            tokio::select! {
+                biased;
+
+                Some(event) = self.save_queue.next() => {
+                    self.write_count -= 1;
+                    return EditorEvent::DocumentSaved(event)
+                }
+                Some(config_event) = self.config_events.1.recv() => {
+                    return EditorEvent::ConfigEvent(config_event)
+                }
+                Some(message) = self.language_servers.incoming.next() => {
+                    return EditorEvent::LanguageServerMessage(message)
+                }
+                Some(event) = self.debugger_events.next() => {
+                    return EditorEvent::DebuggerEvent(event)
+                }
 
-            Some(event) = self.save_queue.next() => {
-                self.write_count -= 1;
-                EditorEvent::DocumentSaved(event)
-            }
-            Some(config_event) = self.config_events.1.recv() => {
-                EditorEvent::ConfigEvent(config_event)
-            }
-            Some(message) = self.language_servers.incoming.next() => {
-                EditorEvent::LanguageServerMessage(message)
-            }
-            Some(event) = self.debugger_events.next() => {
-                EditorEvent::DebuggerEvent(event)
-            }
-            _ = &mut self.idle_timer => {
-                EditorEvent::IdleTimer
+                _ = self.redraw_handle.0.notified() => {
+                    if  !self.needs_redraw{
+                        self.needs_redraw = true;
+                        let timeout = Instant::now() + Duration::from_millis(96);
+                        if timeout < self.idle_timer.deadline(){
+                            self.idle_timer.as_mut().reset(timeout)
+                        }
+                    }
+                }
+
+                _ = &mut self.idle_timer  => {
+                    return EditorEvent::IdleTimer
+                }
             }
         }
     }
diff --git a/helix-view/src/gutter.rs b/helix-view/src/gutter.rs
index 61a17791..377518fb 100644
--- a/helix-view/src/gutter.rs
+++ b/helix-view/src/gutter.rs
@@ -12,7 +12,7 @@ fn count_digits(n: usize) -> usize {
     std::iter::successors(Some(n), |&n| (n >= 10).then(|| n / 10)).count()
 }
 
-pub type GutterFn<'doc> = Box<dyn Fn(usize, bool, &mut String) -> Option<Style> + 'doc>;
+pub type GutterFn<'doc> = Box<dyn FnMut(usize, bool, &mut String) -> Option<Style> + 'doc>;
 pub type Gutter =
     for<'doc> fn(&'doc Editor, &'doc Document, &View, &Theme, bool, usize) -> GutterFn<'doc>;
 
@@ -31,6 +31,7 @@ impl GutterType {
             }
             GutterType::LineNumbers => line_numbers(editor, doc, view, theme, is_focused),
             GutterType::Spacer => padding(editor, doc, view, theme, is_focused),
+            GutterType::Diff => diff(editor, doc, view, theme, is_focused),
         }
     }
 
@@ -39,6 +40,7 @@ impl GutterType {
             GutterType::Diagnostics => 1,
             GutterType::LineNumbers => line_numbers_width(_view, doc),
             GutterType::Spacer => 1,
+            GutterType::Diff => 1,
         }
     }
 }
@@ -83,6 +85,53 @@ pub fn diagnostic<'doc>(
     })
 }
 
+pub fn diff<'doc>(
+    _editor: &'doc Editor,
+    doc: &'doc Document,
+    _view: &View,
+    theme: &Theme,
+    _is_focused: bool,
+) -> GutterFn<'doc> {
+    let added = theme.get("diff.plus");
+    let deleted = theme.get("diff.minus");
+    let modified = theme.get("diff.delta");
+    if let Some(diff_handle) = doc.diff_handle() {
+        let hunks = diff_handle.hunks();
+        let mut hunk_i = 0;
+        let mut hunk = hunks.nth_hunk(hunk_i);
+        Box::new(move |line: usize, _selected: bool, out: &mut String| {
+            // truncating the line is fine here because we don't compute diffs
+            // for files with more lines than i32::MAX anyways
+            // we need to special case removals here
+            // these technically do not have a range of lines to highlight (`hunk.after.start == hunk.after.end`).
+            // However we still want to display these hunks correctly we must not yet skip to the next hunk here
+            while hunk.after.end < line as u32
+                || !hunk.is_pure_removal() && line as u32 == hunk.after.end
+            {
+                hunk_i += 1;
+                hunk = hunks.nth_hunk(hunk_i);
+            }
+
+            if hunk.after.start > line as u32 {
+                return None;
+            }
+
+            let (icon, style) = if hunk.is_pure_insertion() {
+                ("▍", added)
+            } else if hunk.is_pure_removal() {
+                ("▔", deleted)
+            } else {
+                ("▍", modified)
+            };
+
+            write!(out, "{}", icon).unwrap();
+            Some(style)
+        })
+    } else {
+        Box::new(move |_, _, _| None)
+    }
+}
+
 pub fn line_numbers<'doc>(
     editor: &'doc Editor,
     doc: &'doc Document,
@@ -226,8 +275,8 @@ pub fn diagnostics_or_breakpoints<'doc>(
     theme: &Theme,
     is_focused: bool,
 ) -> GutterFn<'doc> {
-    let diagnostics = diagnostic(editor, doc, view, theme, is_focused);
-    let breakpoints = breakpoints(editor, doc, view, theme, is_focused);
+    let mut diagnostics = diagnostic(editor, doc, view, theme, is_focused);
+    let mut breakpoints = breakpoints(editor, doc, view, theme, is_focused);
 
     Box::new(move |line, selected, out| {
         breakpoints(line, selected, out).or_else(|| diagnostics(line, selected, out))
diff --git a/helix-view/src/view.rs b/helix-view/src/view.rs
index 845a5458..ecc8e8be 100644
--- a/helix-view/src/view.rs
+++ b/helix-view/src/view.rs
@@ -158,17 +158,10 @@ impl View {
     }
 
     pub fn gutter_offset(&self, doc: &Document) -> u16 {
-        let mut offset = self
-            .gutters
+        self.gutters
             .iter()
             .map(|gutter| gutter.width(self, doc) as u16)
-            .sum();
-
-        if offset > 0 {
-            offset += 1
-        }
-
-        offset
+            .sum()
     }
 
     //
@@ -392,8 +385,8 @@ impl View {
 mod tests {
     use super::*;
     use helix_core::Rope;
-    const OFFSET: u16 = 4; // 1 diagnostic + 2 linenr (< 100 lines) + 1 gutter
-    const OFFSET_WITHOUT_LINE_NUMBERS: u16 = 2; // 1 diagnostic + 1 gutter
+    const OFFSET: u16 = 3; // 1 diagnostic + 2 linenr (< 100 lines)
+    const OFFSET_WITHOUT_LINE_NUMBERS: u16 = 1; // 1 diagnostic
                                                 // const OFFSET: u16 = GUTTERS.iter().map(|(_, width)| *width as u16).sum();
     use crate::document::Document;
     use crate::editor::GutterType;