Picker performance improvements

4 files changed, 108 insertions, 52 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 1922960e..346fd7fd 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -449,6 +449,7 @@ dependencies = [
  "num_cpus",
  "once_cell",
  "pulldown-cmark",
+ "retain_mut",
  "serde",
  "serde_json",
  "signal-hook",
@@ -846,6 +847,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "f497285884f3fcff424ffc933e56d7cbca511def0c9831a7f9b5f6153e3cc89b"
 
 [[package]]
+name = "retain_mut"
+version = "0.1.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8c31b5c4033f8fdde8700e4657be2c497e7288f01515be52168c631e2e4d4086"
+
+[[package]]
 name = "ropey"
 version = "1.3.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/helix-term/Cargo.toml b/helix-term/Cargo.toml
index e62496f2..a1c096ee 100644
--- a/helix-term/Cargo.toml
+++ b/helix-term/Cargo.toml
@@ -61,5 +61,8 @@ serde = { version = "1.0", features = ["derive"] }
 grep-regex = "0.1.9"
 grep-searcher = "0.1.8"
 
+# Remove once retain_mut lands in stable rust
+retain_mut = "0.1.7"
+
 [target.'cfg(not(windows))'.dependencies]  # https://github.com/vorner/signal-hook/issues/100
 signal-hook-tokio = { version = "0.3", features = ["futures-v0_3"] }
diff --git a/helix-term/src/ui/mod.rs b/helix-term/src/ui/mod.rs
index 011ad9ba..d46de2d3 100644
--- a/helix-term/src/ui/mod.rs
+++ b/helix-term/src/ui/mod.rs
@@ -98,7 +98,9 @@ pub fn regex_prompt(
 
 pub fn file_picker(root: PathBuf, config: &helix_view::editor::Config) -> FilePicker<PathBuf> {
     use ignore::{types::TypesBuilder, WalkBuilder};
-    use std::time;
+    use std::time::Instant;
+
+    let now = Instant::now();
 
     let mut walk_builder = WalkBuilder::new(&root);
     walk_builder
@@ -116,56 +118,44 @@ pub fn file_picker(root: PathBuf, config: &helix_view::editor::Config) -> FilePi
 
     // We want to exclude files that the editor can't handle yet
     let mut type_builder = TypesBuilder::new();
-
     type_builder
         .add(
             "compressed",
             "*.{zip,gz,bz2,zst,lzo,sz,tgz,tbz2,lz,lz4,lzma,lzo,z,Z,xz,7z,rar,cab}",
         )
-        // This shouldn't panic as the above is static, but if it ever
-        // is changed and becomes invalid it will catch here rather than
-        // being unnoticed.
         .expect("Invalid type definition");
     type_builder.negate("all");
-
-    if let Ok(excluded_types) = type_builder.build() {
-        walk_builder.types(excluded_types);
-    }
+    let excluded_types = type_builder
+        .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()?;
-        // Path::is_dir() traverses symlinks, so we use it over DirEntry::is_dir
-        if entry.path().is_dir() {
+
+        // This is faster than entry.path().is_dir() since it uses cached fs::Metadata fetched by ignore/walkdir
+        let is_dir = entry.file_type().map(|ft| ft.is_dir()).unwrap_or(false);
+
+        if is_dir {
             // Will give a false positive if metadata cannot be read (eg. permission error)
             return None;
         }
 
-        let time = entry.metadata().map_or(time::UNIX_EPOCH, |metadata| {
-            metadata
-                .accessed()
-                .or_else(|_| metadata.modified())
-                .or_else(|_| metadata.created())
-                .unwrap_or(time::UNIX_EPOCH)
-        });
-
-        Some((entry.into_path(), time))
+        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<_> = if root.join(".git").is_dir() {
+    let files: Vec<_> = if root.join(".git").is_dir() {
         files.collect()
     } else {
-        const MAX: usize = 8192;
+        // const MAX: usize = 8192;
+        const MAX: usize = 100_000;
         files.take(MAX).collect()
     };
 
-    // Most recently modified first
-    files.sort_by_key(|file| std::cmp::Reverse(file.1));
-
-    // Strip the time data so we can send just the paths to the FilePicker
-    let files = files.into_iter().map(|(path, _)| path).collect();
+    log::debug!("file_picker init {:?}", Instant::now().duration_since(now));
 
     FilePicker::new(
         files,
diff --git a/helix-term/src/ui/picker.rs b/helix-term/src/ui/picker.rs
index 06e50f51..5d88622c 100644
--- a/helix-term/src/ui/picker.rs
+++ b/helix-term/src/ui/picker.rs
@@ -13,8 +13,10 @@ use fuzzy_matcher::skim::SkimMatcherV2 as Matcher;
 use fuzzy_matcher::FuzzyMatcher;
 use tui::widgets::Widget;
 
+use std::time::Instant;
 use std::{
     borrow::Cow,
+    cmp::Reverse,
     collections::HashMap,
     io::Read,
     path::{Path, PathBuf},
@@ -286,7 +288,8 @@ pub struct Picker<T> {
     cursor: usize,
     // pattern: String,
     prompt: Prompt,
-    /// Wheather to truncate the start (default true)
+    previous_pattern: String,
+    /// Whether to truncate the start (default true)
     pub truncate_start: bool,
 
     format_fn: Box<dyn Fn(&T) -> Cow<str>>,
@@ -303,9 +306,7 @@ impl<T> Picker<T> {
             "".into(),
             None,
             ui::completers::none,
-            |_editor: &mut Context, _pattern: &str, _event: PromptEvent| {
-                //
-            },
+            |_editor: &mut Context, _pattern: &str, _event: PromptEvent| {},
         );
 
         let mut picker = Self {
@@ -315,44 +316,99 @@ impl<T> Picker<T> {
             filters: Vec::new(),
             cursor: 0,
             prompt,
+            previous_pattern: String::new(),
             truncate_start: true,
             format_fn: Box::new(format_fn),
             callback_fn: Box::new(callback_fn),
             completion_height: 0,
         };
 
-        // TODO: scoring on empty input should just use a fastpath
-        picker.score();
+        // scoring on empty input:
+        // TODO: just reuse score()
+        picker.matches.extend(
+            picker
+                .options
+                .iter()
+                .enumerate()
+                .map(|(index, _option)| (index, 0)),
+        );
 
         picker
     }
 
     pub fn score(&mut self) {
+        let now = Instant::now();
+
         let pattern = &self.prompt.line;
 
-        // reuse the matches allocation
-        self.matches.clear();
-        self.matches.extend(
-            self.options
-                .iter()
-                .enumerate()
-                .filter_map(|(index, option)| {
-                    // filter options first before matching
-                    if !self.filters.is_empty() {
-                        self.filters.binary_search(&index).ok()?;
+        if pattern == &self.previous_pattern {
+            return;
+        }
+
+        if pattern.is_empty() {
+            // Fast path for no pattern.
+            self.matches.clear();
+            self.matches.extend(
+                self.options
+                    .iter()
+                    .enumerate()
+                    .map(|(index, _option)| (index, 0)),
+            );
+        } else if pattern.starts_with(&self.previous_pattern) {
+            // TODO: remove when retain_mut is in stable rust
+            use retain_mut::RetainMut;
+
+            // optimization: if the pattern is a more specific version of the previous one
+            // then we can score the filtered set.
+            #[allow(unstable_name_collisions)]
+            self.matches.retain_mut(|(index, score)| {
+                let option = &self.options[*index];
+                // TODO: maybe using format_fn isn't the best idea here
+                let text = (self.format_fn)(option);
+
+                match self.matcher.fuzzy_match(&text, pattern) {
+                    Some(s) => {
+                        // Update the score
+                        *score = s;
+                        true
                     }
-                    // TODO: maybe using format_fn isn't the best idea here
-                    let text = (self.format_fn)(option);
-                    // Highlight indices are computed lazily in the render function
-                    self.matcher
-                        .fuzzy_match(&text, pattern)
-                        .map(|score| (index, score))
-                }),
-        );
-        self.matches.sort_unstable_by_key(|(_, score)| -score);
+                    None => false,
+                }
+            });
+
+            self.matches
+                .sort_unstable_by_key(|(_, score)| Reverse(*score));
+        } else {
+            self.matches.clear();
+            self.matches.extend(
+                self.options
+                    .iter()
+                    .enumerate()
+                    .filter_map(|(index, option)| {
+                        // filter options first before matching
+                        if !self.filters.is_empty() {
+                            // TODO: this filters functionality seems inefficient,
+                            // instead store and operate on filters if any
+                            self.filters.binary_search(&index).ok()?;
+                        }
+
+                        // TODO: maybe using format_fn isn't the best idea here
+                        let text = (self.format_fn)(option);
+
+                        self.matcher
+                            .fuzzy_match(&text, pattern)
+                            .map(|score| (index, score))
+                    }),
+            );
+            self.matches
+                .sort_unstable_by_key(|(_, score)| Reverse(*score));
+        }
+
+        log::debug!("picker score {:?}", Instant::now().duration_since(now));
 
         // reset cursor position
         self.cursor = 0;
+        self.previous_pattern.clone_from(pattern);
     }
 
     /// Move the cursor by a number of lines, either down (`Forward`) or up (`Backward`)