Treat space as a seperator instead of a character in fuzzy picker

4 files changed, 130 insertions, 8 deletions

diff --git a/helix-term/src/ui/fuzzy_match.rs b/helix-term/src/ui/fuzzy_match.rs
new file mode 100644
index 00000000..e25d7328
--- /dev/null
+++ b/helix-term/src/ui/fuzzy_match.rs
@@ -0,0 +1,74 @@
+use fuzzy_matcher::skim::SkimMatcherV2 as Matcher;
+use fuzzy_matcher::FuzzyMatcher;
+
+#[cfg(test)]
+mod test;
+
+pub struct FuzzyQuery {
+    queries: Vec<String>,
+}
+
+impl FuzzyQuery {
+    pub fn new(query: &str) -> FuzzyQuery {
+        let mut saw_backslash = false;
+        let queries = query
+            .split(|c| {
+                saw_backslash = match c {
+                    ' ' if !saw_backslash => return true,
+                    '\\' => true,
+                    _ => false,
+                };
+                false
+            })
+            .filter_map(|query| {
+                if query.is_empty() {
+                    None
+                } else {
+                    Some(query.replace("\\ ", " "))
+                }
+            })
+            .collect();
+        FuzzyQuery { queries }
+    }
+
+    pub fn fuzzy_match(&self, item: &str, matcher: &Matcher) -> Option<i64> {
+        // use the rank of the first query for the rank, because merging ranks is not really possible
+        // this behaviour matches fzf and skim
+        let score = matcher.fuzzy_match(item, self.queries.get(0)?)?;
+        if self
+            .queries
+            .iter()
+            .any(|query| matcher.fuzzy_match(item, query).is_none())
+        {
+            return None;
+        }
+        Some(score)
+    }
+
+    pub fn fuzzy_indicies(&self, item: &str, matcher: &Matcher) -> Option<(i64, Vec<usize>)> {
+        if self.queries.len() == 1 {
+            return matcher.fuzzy_indices(item, &self.queries[0]);
+        }
+
+        // use the rank of the first query for the rank, because merging ranks is not really possible
+        // this behaviour matches fzf and skim
+        let (score, mut indicies) = matcher.fuzzy_indices(item, self.queries.get(0)?)?;
+
+        // fast path for the common case of not using a space
+        // during matching this branch should be free thanks to branch prediction
+        if self.queries.len() == 1 {
+            return Some((score, indicies));
+        }
+
+        for query in &self.queries[1..] {
+            let (_, matched_indicies) = matcher.fuzzy_indices(item, query)?;
+            indicies.extend_from_slice(&matched_indicies);
+        }
+
+        // deadup and remove duplicate matches
+        indicies.sort_unstable();
+        indicies.dedup();
+
+        Some((score, indicies))
+    }
+}
diff --git a/helix-term/src/ui/fuzzy_match/test.rs b/helix-term/src/ui/fuzzy_match/test.rs
new file mode 100644
index 00000000..3f90ef68
--- /dev/null
+++ b/helix-term/src/ui/fuzzy_match/test.rs
@@ -0,0 +1,47 @@
+use crate::ui::fuzzy_match::FuzzyQuery;
+use crate::ui::fuzzy_match::Matcher;
+
+fn run_test<'a>(query: &str, items: &'a [&'a str]) -> Vec<String> {
+    let query = FuzzyQuery::new(query);
+    let matcher = Matcher::default();
+    items
+        .iter()
+        .filter_map(|item| {
+            let (_, indicies) = query.fuzzy_indicies(item, &matcher)?;
+            let matched_string = indicies
+                .iter()
+                .map(|&pos| item.chars().nth(pos).unwrap())
+                .collect();
+            Some(matched_string)
+        })
+        .collect()
+}
+
+#[test]
+fn match_single_value() {
+    let matches = run_test("foo", &["foobar", "foo", "bar"]);
+    assert_eq!(matches, &["foo", "foo"])
+}
+
+#[test]
+fn match_multiple_values() {
+    let matches = run_test(
+        "foo bar",
+        &["foo bar", "foo   bar", "bar foo", "bar", "foo"],
+    );
+    assert_eq!(matches, &["foobar", "foobar", "barfoo"])
+}
+
+#[test]
+fn space_escape() {
+    let matches = run_test(r"foo\ bar", &["bar foo", "foo bar", "foobar"]);
+    assert_eq!(matches, &["foo bar"])
+}
+
+#[test]
+fn trim() {
+    let matches = run_test(r" foo bar ", &["bar foo", "foo bar", "foobar"]);
+    assert_eq!(matches, &["barfoo", "foobar", "foobar"]);
+    let matches = run_test(r" foo bar\ ", &["bar foo", "foo bar", "foobar"]);
+    assert_eq!(matches, &["bar foo"])
+}
diff --git a/helix-term/src/ui/mod.rs b/helix-term/src/ui/mod.rs
index 8ab15bff..6ac4dbb7 100644
--- a/helix-term/src/ui/mod.rs
+++ b/helix-term/src/ui/mod.rs
@@ -1,5 +1,6 @@
 mod completion;
 pub(crate) mod editor;
+mod fuzzy_match;
 mod info;
 pub mod lsp;
 mod markdown;
diff --git a/helix-term/src/ui/picker.rs b/helix-term/src/ui/picker.rs
index 49eb986b..ac97e3cc 100644
--- a/helix-term/src/ui/picker.rs
+++ b/helix-term/src/ui/picker.rs
@@ -1,7 +1,7 @@
 use crate::{
     compositor::{Component, Compositor, Context, Event, EventResult},
     ctrl, key, shift,
-    ui::{self, EditorView},
+    ui::{self, fuzzy_match::FuzzyQuery, EditorView},
 };
 use tui::{
     buffer::Buffer as Surface,
@@ -9,7 +9,6 @@ use tui::{
 };
 
 use fuzzy_matcher::skim::SkimMatcherV2 as Matcher;
-use fuzzy_matcher::FuzzyMatcher;
 use tui::widgets::Widget;
 
 use std::time::Instant;
@@ -389,13 +388,14 @@ impl<T: Item> Picker<T> {
                     .map(|(index, _option)| (index, 0)),
             );
         } else if pattern.starts_with(&self.previous_pattern) {
+            let query = FuzzyQuery::new(pattern);
             // optimization: if the pattern is a more specific version of the previous one
             // then we can score the filtered set.
             self.matches.retain_mut(|(index, score)| {
                 let option = &self.options[*index];
                 let text = option.sort_text(&self.editor_data);
 
-                match self.matcher.fuzzy_match(&text, pattern) {
+                match query.fuzzy_match(&text, &self.matcher) {
                     Some(s) => {
                         // Update the score
                         *score = s;
@@ -408,6 +408,7 @@ impl<T: Item> Picker<T> {
             self.matches
                 .sort_unstable_by_key(|(_, score)| Reverse(*score));
         } else {
+            let query = FuzzyQuery::new(pattern);
             self.matches.clear();
             self.matches.extend(
                 self.options
@@ -423,8 +424,8 @@ impl<T: Item> Picker<T> {
 
                         let text = option.filter_text(&self.editor_data);
 
-                        self.matcher
-                            .fuzzy_match(&text, pattern)
+                        query
+                            .fuzzy_match(&text, &self.matcher)
                             .map(|score| (index, score))
                     }),
             );
@@ -657,9 +658,8 @@ impl<T: Item + 'static> Component for Picker<T> {
             }
 
             let spans = option.label(&self.editor_data);
-            let (_score, highlights) = self
-                .matcher
-                .fuzzy_indices(&String::from(&spans), self.prompt.line())
+            let (_score, highlights) = FuzzyQuery::new(self.prompt.line())
+                .fuzzy_indicies(&String::from(&spans), &self.matcher)
                 .unwrap_or_default();
 
             spans.0.into_iter().fold(inner, |pos, span| {