transition to nucleo for fuzzy matching (#7814)

* transition to nucleo for fuzzy matching

* drop flakey test case

since the picker streams in results now any test that relies
on the picker containing results is potentially flakely

* use crates.io version of nucleo

* Fix typo in commands.rs

Co-authored-by: Skyler Hawthorne <skyler@dead10ck.com>

---------

Co-authored-by: Skyler Hawthorne <skyler@dead10ck.com>

1 files changed, 44 insertions, 140 deletions

diff --git a/helix-term/src/ui/mod.rs b/helix-term/src/ui/mod.rs
index 2d15fb32..3ca3d24d 100644
--- a/helix-term/src/ui/mod.rs
+++ b/helix-term/src/ui/mod.rs
@@ -1,7 +1,6 @@
 mod completion;
 mod document;
 pub(crate) mod editor;
-mod fuzzy_match;
 mod info;
 pub mod lsp;
 mod markdown;
@@ -64,7 +63,7 @@ pub fn regex_prompt(
     prompt: std::borrow::Cow<'static, str>,
     history_register: Option<char>,
     completion_fn: impl FnMut(&Editor, &str) -> Vec<prompt::Completion> + 'static,
-    fun: impl Fn(&mut Editor, Regex, PromptEvent) + 'static,
+    fun: impl Fn(&mut crate::compositor::Context, Regex, PromptEvent) + 'static,
 ) {
     let (view, doc) = current!(cx.editor);
     let doc_id = view.doc;
@@ -111,7 +110,7 @@ pub fn regex_prompt(
                                 view.jumps.push((doc_id, snapshot.clone()));
                             }
 
-                            fun(cx.editor, regex, event);
+                            fun(cx, regex, event);
 
                             let (view, doc) = current!(cx.editor);
                             view.ensure_cursor_in_view(doc, config.scrolloff);
@@ -174,6 +173,7 @@ pub fn file_picker(root: PathBuf, config: &helix_view::editor::Config) -> Picker
         .git_ignore(config.file_picker.git_ignore)
         .git_global(config.file_picker.git_global)
         .git_exclude(config.file_picker.git_exclude)
+        .sort_by_file_name(|name1, name2| name1.cmp(name2))
         .max_depth(config.file_picker.max_depth)
         .filter_entry(move |entry| filter_picker_entry(entry, &absolute_root, dedup_symlinks));
 
@@ -190,32 +190,16 @@ pub fn file_picker(root: PathBuf, config: &helix_view::editor::Config) -> Picker
         .build()
         .expect("failed to build excluded_types");
     walk_builder.types(excluded_types);
-
-    // We want files along with their modification date for sorting
     let files = walk_builder.build().filter_map(|entry| {
         let entry = entry.ok()?;
-        // This is faster than entry.path().is_dir() since it uses cached fs::Metadata fetched by ignore/walkdir
-        if entry.file_type()?.is_file() {
-            Some(entry.into_path())
-        } else {
-            None
+        if !entry.file_type()?.is_file() {
+            return None;
         }
+        Some(entry.into_path())
     });
-
-    // Cap the number of files if we aren't in a git project, preventing
-    // hangs when using the picker in your home directory
-    let mut files: Vec<PathBuf> = if root.join(".git").exists() {
-        files.collect()
-    } else {
-        // const MAX: usize = 8192;
-        const MAX: usize = 100_000;
-        files.take(MAX).collect()
-    };
-    files.sort();
-
     log::debug!("file_picker init {:?}", Instant::now().duration_since(now));
 
-    Picker::new(files, root, move |cx, path: &PathBuf, action| {
+    let picker = Picker::new(Vec::new(), root, move |cx, path: &PathBuf, action| {
         if let Err(e) = cx.editor.open(path, action) {
             let err = if let Some(err) = e.source() {
                 format!("{}", err)
@@ -225,20 +209,27 @@ pub fn file_picker(root: PathBuf, config: &helix_view::editor::Config) -> Picker
             cx.editor.set_error(err);
         }
     })
-    .with_preview(|_editor, path| Some((path.clone().into(), None)))
+    .with_preview(|_editor, path| Some((path.clone().into(), None)));
+    let injector = picker.injector();
+    std::thread::spawn(move || {
+        for file in files {
+            if injector.push(file).is_err() {
+                break;
+            }
+        }
+    });
+    picker
 }
 
 pub mod completers {
     use crate::ui::prompt::Completion;
-    use fuzzy_matcher::skim::SkimMatcherV2 as Matcher;
-    use fuzzy_matcher::FuzzyMatcher;
+    use helix_core::fuzzy::fuzzy_match;
     use helix_core::syntax::LanguageServerFeature;
     use helix_view::document::SCRATCH_BUFFER_NAME;
     use helix_view::theme;
     use helix_view::{editor::Config, Editor};
     use once_cell::sync::Lazy;
     use std::borrow::Cow;
-    use std::cmp::Reverse;
 
     pub type Completer = fn(&Editor, &str) -> Vec<Completion>;
 
@@ -247,31 +238,16 @@ pub mod completers {
     }
 
     pub fn buffer(editor: &Editor, input: &str) -> Vec<Completion> {
-        let mut names: Vec<_> = editor
-            .documents
-            .values()
-            .map(|doc| {
-                let name = doc
-                    .relative_path()
-                    .map(|p| p.display().to_string())
-                    .unwrap_or_else(|| String::from(SCRATCH_BUFFER_NAME));
-                ((0..), Cow::from(name))
-            })
-            .collect();
-
-        let matcher = Matcher::default();
-
-        let mut matches: Vec<_> = names
-            .into_iter()
-            .filter_map(|(_range, name)| {
-                matcher.fuzzy_match(&name, input).map(|score| (name, score))
-            })
-            .collect();
-
-        matches.sort_unstable_by_key(|(_file, score)| Reverse(*score));
-        names = matches.into_iter().map(|(name, _)| ((0..), name)).collect();
+        let names = editor.documents.values().map(|doc| {
+            doc.relative_path()
+                .map(|p| p.display().to_string().into())
+                .unwrap_or_else(|| Cow::from(SCRATCH_BUFFER_NAME))
+        });
 
-        names
+        fuzzy_match(input, names, true)
+            .into_iter()
+            .map(|(name, _)| ((0..), name))
+            .collect()
     }
 
     pub fn theme(_editor: &Editor, input: &str) -> Vec<Completion> {
@@ -284,26 +260,10 @@ pub mod completers {
         names.sort();
         names.dedup();
 
-        let mut names: Vec<_> = names
+        fuzzy_match(input, names, false)
             .into_iter()
-            .map(|name| ((0..), Cow::from(name)))
-            .collect();
-
-        let matcher = Matcher::default();
-
-        let mut matches: Vec<_> = names
-            .into_iter()
-            .filter_map(|(_range, name)| {
-                matcher.fuzzy_match(&name, input).map(|score| (name, score))
-            })
-            .collect();
-
-        matches.sort_unstable_by(|(name1, score1), (name2, score2)| {
-            (Reverse(*score1), name1).cmp(&(Reverse(*score2), name2))
-        });
-        names = matches.into_iter().map(|(name, _)| ((0..), name)).collect();
-
-        names
+            .map(|(name, _)| ((0..), name.into()))
+            .collect()
     }
 
     /// Recursive function to get all keys from this value and add them to vec
@@ -330,15 +290,7 @@ pub mod completers {
             keys
         });
 
-        let matcher = Matcher::default();
-
-        let mut matches: Vec<_> = KEYS
-            .iter()
-            .filter_map(|name| matcher.fuzzy_match(name, input).map(|score| (name, score)))
-            .collect();
-
-        matches.sort_unstable_by_key(|(_file, score)| Reverse(*score));
-        matches
+        fuzzy_match(input, &*KEYS, false)
             .into_iter()
             .map(|(name, _)| ((0..), name.into()))
             .collect()
@@ -365,8 +317,6 @@ pub mod completers {
     }
 
     pub fn language(editor: &Editor, input: &str) -> Vec<Completion> {
-        let matcher = Matcher::default();
-
         let text: String = "text".into();
 
         let language_ids = editor
@@ -375,27 +325,13 @@ pub mod completers {
             .map(|config| &config.language_id)
             .chain(std::iter::once(&text));
 
-        let mut matches: Vec<_> = language_ids
-            .filter_map(|language_id| {
-                matcher
-                    .fuzzy_match(language_id, input)
-                    .map(|score| (language_id, score))
-            })
-            .collect();
-
-        matches.sort_unstable_by(|(language1, score1), (language2, score2)| {
-            (Reverse(*score1), language1).cmp(&(Reverse(*score2), language2))
-        });
-
-        matches
+        fuzzy_match(input, language_ids, false)
             .into_iter()
-            .map(|(language, _score)| ((0..), language.clone().into()))
+            .map(|(name, _)| ((0..), name.to_owned().into()))
             .collect()
     }
 
     pub fn lsp_workspace_command(editor: &Editor, input: &str) -> Vec<Completion> {
-        let matcher = Matcher::default();
-
         let Some(options) = doc!(editor)
             .language_servers_with_feature(LanguageServerFeature::WorkspaceCommand)
             .find_map(|ls| ls.capabilities().execute_command_provider.as_ref())
@@ -403,23 +339,9 @@ pub mod completers {
             return vec![];
         };
 
-        let mut matches: Vec<_> = options
-            .commands
-            .iter()
-            .filter_map(|command| {
-                matcher
-                    .fuzzy_match(command, input)
-                    .map(|score| (command, score))
-            })
-            .collect();
-
-        matches.sort_unstable_by(|(command1, score1), (command2, score2)| {
-            (Reverse(*score1), command1).cmp(&(Reverse(*score2), command2))
-        });
-
-        matches
+        fuzzy_match(input, &options.commands, false)
             .into_iter()
-            .map(|(command, _score)| ((0..), command.clone().into()))
+            .map(|(name, _)| ((0..), name.to_owned().into()))
             .collect()
     }
 
@@ -500,7 +422,7 @@ pub mod completers {
 
         let end = input.len()..;
 
-        let mut files: Vec<_> = WalkBuilder::new(&dir)
+        let files = WalkBuilder::new(&dir)
             .hidden(false)
             .follow_links(false) // We're scanning over depth 1
             .git_ignore(git_ignore)
@@ -532,43 +454,25 @@ pub mod completers {
                         path.push("");
                     }
 
-                    let path = path.to_str()?.to_owned();
-                    Some((end.clone(), Cow::from(path)))
+                    let path = path.into_os_string().into_string().ok()?;
+                    Some(Cow::from(path))
                 })
             }) // TODO: unwrap or skip
-            .filter(|(_, path)| !path.is_empty()) // TODO
-            .collect();
+            .filter(|path| !path.is_empty());
 
         // if empty, return a list of dirs and files in current dir
         if let Some(file_name) = file_name {
-            let matcher = Matcher::default();
-
-            // inefficient, but we need to calculate the scores, filter out None, then sort.
-            let mut matches: Vec<_> = files
-                .into_iter()
-                .filter_map(|(_range, file)| {
-                    matcher
-                        .fuzzy_match(&file, &file_name)
-                        .map(|score| (file, score))
-                })
-                .collect();
-
             let range = (input.len().saturating_sub(file_name.len()))..;
-
-            matches.sort_unstable_by(|(file1, score1), (file2, score2)| {
-                (Reverse(*score1), file1).cmp(&(Reverse(*score2), file2))
-            });
-
-            files = matches
+            fuzzy_match(&file_name, files, true)
                 .into_iter()
-                .map(|(file, _)| (range.clone(), file))
-                .collect();
+                .map(|(name, _)| (range.clone(), name))
+                .collect()
 
             // TODO: complete to longest common match
         } else {
+            let mut files: Vec<_> = files.map(|file| (end.clone(), file)).collect();
             files.sort_unstable_by(|(_, path1), (_, path2)| path1.cmp(path2));
+            files
         }
-
-        files
     }
 }