feat(ui): highlight fulltext search as fulltext search instead of fuzzy search (#3098)

also parse query in one place.

This supersedes #3097 and can highlight regex matches as well.

<!-- Thank you for making a PR! Bug fixes are always welcome, but if
you're adding a new feature or changing an existing one, we'd really
appreciate if you open an issue, post on the forum, or drop in on
Discord -->

## Checks
- [x] I am happy for maintainers to push small adjustments to this PR,
to speed up the review cycle
- [x] I have checked that there are no existing pull requests for the
same thing

2 files changed, 177 insertions, 61 deletions

diff --git a/crates/atuin-client/src/database.rs b/crates/atuin-client/src/database.rs
index 82644182..408e8e52 100644
--- a/crates/atuin-client/src/database.rs
+++ b/crates/atuin-client/src/database.rs
@@ -1,5 +1,4 @@
 use std::{
-    borrow::Cow,
     env,
     path::{Path, PathBuf},
     str::FromStr,
@@ -483,76 +482,47 @@ impl Database for Sqlite {
             SearchMode::Prefix => sql.and_where_like_left("command", query.replace('*', "%")),
             _ => {
                 let mut is_or = false;
-                let mut regex = None;
-                for part in query.split_inclusive(' ') {
-                    let query_part: Cow<str> = match (&mut regex, part.starts_with("r/")) {
-                        (None, false) => {
-                            if part.trim_end().is_empty() {
-                                continue;
-                            }
-                            Cow::Owned(part.trim_end().replace('*', "%")) // allow wildcard char
-                        }
-                        (None, true) => {
-                            if part[2..].trim_end().ends_with('/') {
-                                let end_pos = part.trim_end().len() - 1;
-                                regexes.push(String::from(&part[2..end_pos]));
-                            } else {
-                                regex = Some(String::from(&part[2..]));
-                            }
-                            continue;
-                        }
-                        (Some(r), _) => {
-                            if part.trim_end().ends_with('/') {
-                                let end_pos = part.trim_end().len() - 1;
-                                r.push_str(&part.trim_end()[..end_pos]);
-                                regexes.push(regex.take().unwrap());
-                            } else {
-                                r.push_str(part);
-                            }
-                            continue;
-                        }
-                    };
-
+                for token in QueryTokenizer::new(query) {
                     // TODO smart case mode could be made configurable like in fzf
-                    let (is_glob, glob) = if query_part.contains(char::is_uppercase) {
+                    let (is_glob, glob) = if token.has_uppercase() {
                         (true, "*")
                     } else {
                         (false, "%")
                     };
-
-                    let (is_inverse, query_part) = match query_part.strip_prefix('!') {
-                        Some(stripped) => (true, Cow::Borrowed(stripped)),
-                        None => (false, query_part),
-                    };
-
-                    #[allow(clippy::if_same_then_else)]
-                    let param = if query_part == "|" {
-                        if !is_or {
-                            is_or = true;
+                    let param = match token {
+                        QueryToken::Regex(r) => {
+                            regexes.push(String::from(r));
                             continue;
-                        } else {
-                            format!("{glob}|{glob}")
                         }
-                    } else if let Some(term) = query_part.strip_prefix('^') {
-                        format!("{term}{glob}")
-                    } else if let Some(term) = query_part.strip_suffix('$') {
-                        format!("{glob}{term}")
-                    } else if let Some(term) = query_part.strip_prefix('\'') {
-                        format!("{glob}{term}{glob}")
-                    } else if is_inverse {
-                        format!("{glob}{query_part}{glob}")
-                    } else if search_mode == SearchMode::FullText {
-                        format!("{glob}{query_part}{glob}")
-                    } else {
-                        query_part.split("").join(glob)
+                        QueryToken::Or => {
+                            if !is_or {
+                                is_or = true;
+                                continue;
+                            } else {
+                                format!("{glob}|{glob}")
+                            }
+                        }
+                        QueryToken::MatchStart(term, _) => {
+                            format!("{term}{glob}")
+                        }
+                        QueryToken::MatchEnd(term, _) => {
+                            format!("{glob}{term}")
+                        }
+                        QueryToken::MatchFull(term, _) => {
+                            format!("{glob}{term}{glob}")
+                        }
+                        QueryToken::Match(term, _) => {
+                            if search_mode == SearchMode::FullText {
+                                format!("{glob}{term}{glob}")
+                            } else {
+                                term.split("").join(glob)
+                            }
+                        }
                     };
 
-                    sql.fuzzy_condition("command", param, is_inverse, is_glob, is_or);
+                    sql.fuzzy_condition("command", param, token.is_inverse(), is_glob, is_or);
                     is_or = false;
                 }
-                if let Some(r) = regex {
-                    regexes.push(r);
-                }
 
                 &mut sql
             }
@@ -1206,3 +1176,94 @@ mod test {
         assert!(duration < Duration::from_secs(15));
     }
 }
+
+pub struct QueryTokenizer<'a> {
+    query: &'a str,
+    last_pos: usize,
+}
+
+pub enum QueryToken<'a> {
+    Match(&'a str, bool),
+    MatchStart(&'a str, bool),
+    MatchEnd(&'a str, bool),
+    MatchFull(&'a str, bool),
+    Or,
+    Regex(&'a str),
+}
+
+impl<'a> QueryToken<'a> {
+    pub fn has_uppercase(&self) -> bool {
+        match self {
+            Self::Match(term, _)
+            | Self::MatchStart(term, _)
+            | Self::MatchEnd(term, _)
+            | Self::MatchFull(term, _) => term.contains(char::is_uppercase),
+            _ => false,
+        }
+    }
+
+    pub fn is_inverse(&self) -> bool {
+        match self {
+            Self::Match(_, inv)
+            | Self::MatchStart(_, inv)
+            | Self::MatchEnd(_, inv)
+            | Self::MatchFull(_, inv) => *inv,
+            _ => false,
+        }
+    }
+}
+
+impl<'a> QueryTokenizer<'a> {
+    pub fn new(query: &'a str) -> Self {
+        Self { query, last_pos: 0 }
+    }
+}
+
+impl<'a> Iterator for QueryTokenizer<'a> {
+    type Item = QueryToken<'a>;
+    fn next(&mut self) -> Option<Self::Item> {
+        let remaining = &self.query[self.last_pos..];
+        if remaining.is_empty() {
+            return None;
+        }
+
+        if let Some(remaining) = remaining.strip_prefix("r/") {
+            let (regex, next_pos) = if let Some(end) = remaining.find("/ ") {
+                (&remaining[..end], self.last_pos + 2 + end + 2)
+            } else if let Some(remaining) = remaining.strip_suffix('/') {
+                (remaining, self.query.len())
+            } else {
+                (remaining, self.query.len())
+            };
+            self.last_pos = next_pos;
+            Some(QueryToken::Regex(regex))
+        } else {
+            let (mut part, next_pos) = if let Some(sp) = remaining.find(' ') {
+                (&remaining[..sp], self.last_pos + sp + 1)
+            } else {
+                (remaining, self.query.len())
+            };
+            self.last_pos = next_pos;
+
+            if part == "|" {
+                return Some(QueryToken::Or);
+            }
+
+            let mut is_inverse = false;
+            if let Some(s) = part.strip_prefix('!') {
+                part = s;
+                is_inverse = true;
+            }
+            let token = if let Some(s) = part.strip_prefix('^') {
+                QueryToken::MatchStart(s, is_inverse)
+            } else if let Some(s) = part.strip_suffix('$') {
+                QueryToken::MatchEnd(s, is_inverse)
+            } else if let Some(s) = part.strip_prefix('\'') {
+                QueryToken::MatchFull(s, is_inverse)
+            } else {
+                QueryToken::Match(part, is_inverse)
+            };
+            Some(token)
+        }
+    }
+}
diff --git a/crates/atuin/src/command/client/search/engines/db.rs b/crates/atuin/src/command/client/search/engines/db.rs
index 9358ee58..f0ed424e 100644
--- a/crates/atuin/src/command/client/search/engines/db.rs
+++ b/crates/atuin/src/command/client/search/engines/db.rs
@@ -1,7 +1,11 @@
 use super::{SearchEngine, SearchState};
 use async_trait::async_trait;
 use atuin_client::{
-    database::Database, database::OptFilters, history::History, settings::SearchMode,
+    database::Database,
+    database::OptFilters,
+    database::{QueryToken, QueryTokenizer},
+    history::History,
+    settings::SearchMode,
 };
 use eyre::Result;
 use norm::Metric;
@@ -36,6 +40,8 @@ impl SearchEngine for Search {
     fn get_highlight_indices(&self, command: &str, search_input: &str) -> Vec<usize> {
         if self.0 == SearchMode::Prefix {
             return vec![];
+        } else if self.0 == SearchMode::FullText {
+            return get_highlight_indices_fulltext(command, search_input);
         }
         let mut fzf = FzfV2::new();
         let mut parser = FzfParser::new();
@@ -47,3 +53,52 @@ impl SearchEngine for Search {
         ranges.into_iter().flatten().collect()
     }
 }
+
+fn get_highlight_indices_fulltext(command: &str, search_input: &str) -> Vec<usize> {
+    let mut ranges = vec![];
+    let lower_command = command.to_ascii_lowercase();
+
+    for token in QueryTokenizer::new(search_input) {
+        let matchee = if token.has_uppercase() {
+            command
+        } else {
+            &lower_command
+        };
+
+        if token.is_inverse() {
+            continue;
+        }
+
+        match token {
+            QueryToken::Or => {}
+            QueryToken::Regex(r) => {
+                if let Ok(re) = regex::Regex::new(r) {
+                    for m in re.find_iter(command) {
+                        ranges.push(m.range());
+                    }
+                }
+            }
+            QueryToken::MatchStart(term, _) => {
+                if matchee.starts_with(term) {
+                    ranges.push(0..term.len());
+                }
+            }
+            QueryToken::MatchEnd(term, _) => {
+                if matchee.ends_with(term) {
+                    let l = matchee.len();
+                    ranges.push((l - term.len())..l);
+                }
+            }
+            QueryToken::Match(term, _) | QueryToken::MatchFull(term, _) => {
+                for (idx, m) in matchee.match_indices(term) {
+                    ranges.push(idx..(idx + m.len()));
+                }
+            }
+        }
+    }
+
+    let mut ret: Vec<_> = ranges.into_iter().flatten().collect();
+    ret.sort_unstable();
+    ret.dedup();
+    ret
+}