feat: highlight matches in interactive search (#2653)

* feat: highlight matches in interactive search

uses `norm` to do fzf-compatible matches when rendering history items
in the search panel to highlight the matching ranges of the item

this helps see _why_ certain history items have come up

note that this will never be 100% perfect as we search on a sqlite query
but it should be good enough in most cases

* fmt

* fix some clippy issues

* refactor to pass in a history_highlighter instead of search and engine

* improve the highlighting on the selected row

---------

Co-authored-by: Ellie Huxtable <ellie@atuin.sh>

6 files changed, 89 insertions, 14 deletions

diff --git a/crates/atuin/Cargo.toml b/crates/atuin/Cargo.toml
index 4ad6e058..1b33491f 100644
--- a/crates/atuin/Cargo.toml
+++ b/crates/atuin/Cargo.toml
@@ -89,6 +89,7 @@ tracing-subscriber = { workspace = true }
 uuid = { workspace = true }
 sysinfo = "0.30.7"
 regex = "1.10.5"
+norm = { version = "0.1.1", features = ["fzf-v2"] }
 tempfile = { workspace = true }
 shlex = "1.3.0"
 
diff --git a/crates/atuin/src/command/client/search/engines.rs b/crates/atuin/src/command/client/search/engines.rs
index 30a23cb2..95d6658b 100644
--- a/crates/atuin/src/command/client/search/engines.rs
+++ b/crates/atuin/src/command/client/search/engines.rs
@@ -69,4 +69,5 @@ pub trait SearchEngine: Send + Sync + 'static {
             self.full_query(state, db).await
         }
     }
+    fn get_highlight_indices(&self, command: &str, search_input: &str) -> Vec<usize>;
 }
diff --git a/crates/atuin/src/command/client/search/engines/db.rs b/crates/atuin/src/command/client/search/engines/db.rs
index e638f9d9..9358ee58 100644
--- a/crates/atuin/src/command/client/search/engines/db.rs
+++ b/crates/atuin/src/command/client/search/engines/db.rs
@@ -1,10 +1,12 @@
+use super::{SearchEngine, SearchState};
 use async_trait::async_trait;
 use atuin_client::{
     database::Database, database::OptFilters, history::History, settings::SearchMode,
 };
 use eyre::Result;
-
-use super::{SearchEngine, SearchState};
+use norm::Metric;
+use norm::fzf::{FzfParser, FzfV2};
+use std::ops::Range;
 
 pub struct Search(pub SearchMode);
 
@@ -30,4 +32,18 @@ impl SearchEngine for Search {
             // ignore errors as it may be caused by incomplete regex
             .map_or(Vec::new(), |r| r.into_iter().collect()))
     }
+
+    fn get_highlight_indices(&self, command: &str, search_input: &str) -> Vec<usize> {
+        if self.0 == SearchMode::Prefix {
+            return vec![];
+        }
+        let mut fzf = FzfV2::new();
+        let mut parser = FzfParser::new();
+        let query = parser.parse(search_input);
+        let mut ranges: Vec<Range<usize>> = Vec::new();
+        let _ = fzf.distance_and_ranges(query, command, &mut ranges);
+
+        // convert ranges to all indices
+        ranges.into_iter().flatten().collect()
+    }
 }
diff --git a/crates/atuin/src/command/client/search/engines/skim.rs b/crates/atuin/src/command/client/search/engines/skim.rs
index e87e06d1..e8aff7b4 100644
--- a/crates/atuin/src/command/client/search/engines/skim.rs
+++ b/crates/atuin/src/command/client/search/engines/skim.rs
@@ -37,6 +37,14 @@ impl SearchEngine for Search {
 
         Ok(fuzzy_search(&self.engine, state, &self.all_history).await)
     }
+
+    fn get_highlight_indices(&self, command: &str, search_input: &str) -> Vec<usize> {
+        let (_, indices) = self
+            .engine
+            .fuzzy_indices(command, search_input)
+            .unwrap_or_default();
+        indices
+    }
 }
 
 async fn fuzzy_search(
diff --git a/crates/atuin/src/command/client/search/history_list.rs b/crates/atuin/src/command/client/search/history_list.rs
index ccffc95c..bed883c7 100644
--- a/crates/atuin/src/command/client/search/history_list.rs
+++ b/crates/atuin/src/command/client/search/history_list.rs
@@ -1,10 +1,13 @@
 use std::time::Duration;
 
+use super::duration::format_duration;
+use super::engines::SearchEngine;
 use atuin_client::{
     history::History,
     theme::{Meaning, Theme},
 };
 use atuin_common::utils::Escapable as _;
+use itertools::Itertools;
 use ratatui::{
     buffer::Buffer,
     crossterm::style,
@@ -14,7 +17,17 @@ use ratatui::{
 };
 use time::OffsetDateTime;
 
-use super::duration::format_duration;
+pub struct HistoryHighlighter<'a> {
+    pub engine: &'a dyn SearchEngine,
+    pub search_input: &'a str,
+}
+
+impl HistoryHighlighter<'_> {
+    pub fn get_highlight_indices(&self, command: &str) -> Vec<usize> {
+        self.engine
+            .get_highlight_indices(command, self.search_input)
+    }
+}
 
 pub struct HistoryList<'a> {
     history: &'a [History],
@@ -25,6 +38,7 @@ pub struct HistoryList<'a> {
     now: &'a dyn Fn() -> OffsetDateTime,
     indicator: &'a str,
     theme: &'a Theme,
+    history_highlighter: HistoryHighlighter<'a>,
 }
 
 #[derive(Default)]
@@ -78,6 +92,7 @@ impl StatefulWidget for HistoryList<'_> {
             now: &self.now,
             indicator: self.indicator,
             theme: self.theme,
+            history_highlighter: self.history_highlighter,
         };
 
         for item in self.history.iter().skip(state.offset).take(end - start) {
@@ -101,6 +116,7 @@ impl<'a> HistoryList<'a> {
         now: &'a dyn Fn() -> OffsetDateTime,
         indicator: &'a str,
         theme: &'a Theme,
+        history_highlighter: HistoryHighlighter<'a>,
     ) -> Self {
         Self {
             history,
@@ -110,6 +126,7 @@ impl<'a> HistoryList<'a> {
             now,
             indicator,
             theme,
+            history_highlighter,
         }
     }
 
@@ -144,6 +161,7 @@ struct DrawState<'a> {
     now: &'a dyn Fn() -> OffsetDateTime,
     indicator: &'a str,
     theme: &'a Theme,
+    history_highlighter: HistoryHighlighter<'a>,
 }
 
 // longest line prefix I could come up with
@@ -203,21 +221,45 @@ impl DrawState<'_> {
 
     fn command(&mut self, h: &History) {
         let mut style = self.theme.as_style(Meaning::Base);
+        let mut row_highlighted = false;
         if !self.alternate_highlight && (self.y as usize + self.state.offset == self.state.selected)
         {
+            row_highlighted = true;
             // if not applying alternative highlighting to the whole row, color the command
             style = self.theme.as_style(Meaning::AlertError);
             style.attributes.set(style::Attribute::Bold);
         }
 
+        let highlight_indices = self.history_highlighter.get_highlight_indices(
+            h.command
+                .escape_control()
+                .split_ascii_whitespace()
+                .join(" ")
+                .as_str(),
+        );
+
+        let mut pos = 0;
         for section in h.command.escape_control().split_ascii_whitespace() {
             self.draw(" ", style.into());
-            if self.x > self.list_area.width {
-                // Avoid attempting to draw a command section beyond the width
-                // of the list
-                return;
+            for ch in section.chars() {
+                if self.x > self.list_area.width {
+                    // Avoid attempting to draw a command section beyond the width
+                    // of the list
+                    return;
+                }
+                let mut style = style;
+                if highlight_indices.contains(&pos) {
+                    if row_highlighted {
+                        // if the row is highlighted bold is not enough as the whole row is bold
+                        // change the color too
+                        style = self.theme.as_style(Meaning::AlertWarn);
+                    }
+                    style.attributes.set(style::Attribute::Bold);
+                }
+                self.draw(&ch.to_string(), style.into());
+                pos += 1;
             }
-            self.draw(section, style.into());
+            pos += 1;
         }
     }
 
diff --git a/crates/atuin/src/command/client/search/interactive.rs b/crates/atuin/src/command/client/search/interactive.rs
index d58052b1..cddd5b2b 100644
--- a/crates/atuin/src/command/client/search/interactive.rs
+++ b/crates/atuin/src/command/client/search/interactive.rs
@@ -10,6 +10,11 @@ use semver::Version;
 use time::OffsetDateTime;
 use unicode_width::UnicodeWidthStr;
 
+use super::{
+    cursor::Cursor,
+    engines::{SearchEngine, SearchState},
+    history_list::{HistoryList, ListState, PREFIX_LENGTH},
+};
 use atuin_client::{
     database::{Database, current_context},
     history::{History, HistoryStats, store::HistoryStore},
@@ -18,12 +23,7 @@ use atuin_client::{
     },
 };
 
-use super::{
-    cursor::Cursor,
-    engines::{SearchEngine, SearchState},
-    history_list::{HistoryList, ListState, PREFIX_LENGTH},
-};
-
+use crate::command::client::search::history_list::HistoryHighlighter;
 use crate::command::client::theme::{Meaning, Theme};
 use crate::{VERSION, command::client::search::engines};
 
@@ -732,6 +732,10 @@ impl State {
 
         match self.tab_index {
             0 => {
+                let history_highlighter = HistoryHighlighter {
+                    engine: self.engine.as_ref(),
+                    search_input: self.search.input.as_str(),
+                };
                 let results_list = Self::build_results_list(
                     style,
                     results,
@@ -739,6 +743,7 @@ impl State {
                     &self.now,
                     indicator.as_str(),
                     theme,
+                    history_highlighter,
                 );
                 f.render_stateful_widget(results_list, results_list_chunk, &mut self.results_state);
             }
@@ -882,6 +887,7 @@ impl State {
         now: &'a dyn Fn() -> OffsetDateTime,
         indicator: &'a str,
         theme: &'a Theme,
+        history_highlighter: HistoryHighlighter<'a>,
     ) -> HistoryList<'a> {
         let results_list = HistoryList::new(
             results,
@@ -890,6 +896,7 @@ impl State {
             now,
             indicator,
             theme,
+            history_highlighter,
         );
 
         if style.compact {