tuning and perf improvements regarding search

6 files changed, 50 insertions, 30 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 4840020..df622a7 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -102,11 +102,11 @@ dependencies = [
  "lazy-regex 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.8 (registry+https://github.com/rust-lang/crates.io-index)",
- "minimad 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "minimad 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "opener 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "regex 1.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "simplelog 0.7.4 (registry+https://github.com/rust-lang/crates.io-index)",
- "termimad 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "termimad 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "toml 0.5.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "umask 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "users 0.9.1 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -394,7 +394,7 @@ dependencies = [
 
 [[package]]
 name = "minimad"
-version = "0.5.0"
+version = "0.5.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -648,13 +648,13 @@ dependencies = [
 
 [[package]]
 name = "termimad"
-version = "0.8.0"
+version = "0.8.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "crossbeam 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "crossterm 0.13.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
- "minimad 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "minimad 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "thiserror 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
@@ -823,7 +823,7 @@ dependencies = [
 "checksum log 0.4.8 (registry+https://github.com/rust-lang/crates.io-index)" = "14b6052be84e6b71ab17edffc2eeabf5c2c3ae1fdb464aae35ac50c67a44e1f7"
 "checksum memchr 2.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "88579771288728879b57485cc7d6b07d648c9f0141eb955f8ab7f9d45394468e"
 "checksum memoffset 0.5.2 (registry+https://github.com/rust-lang/crates.io-index)" = "4a85c1a8c329f11437034d7313dca647c79096523533a1c79e86f1d0f657c7cc"
-"checksum minimad 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)" = "cfbb3ddc590c274f60f2f31c523a812b7f224c76f2debb6bd1da125f9c7809e8"
+"checksum minimad 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "239a9899175151e1ac2d5a99c42848001998ef46ff3bb46236b9173c4e8f65d3"
 "checksum mio 0.6.19 (registry+https://github.com/rust-lang/crates.io-index)" = "83f51996a3ed004ef184e16818edc51fadffe8e7ca68be67f9dee67d84d0ff23"
 "checksum miow 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "8c1f2f3b1cf331de6896aabf6e9d55dca90356cc9960cca7eaaf408a355ae919"
 "checksum net2 0.2.33 (registry+https://github.com/rust-lang/crates.io-index)" = "42550d9fb7b6684a6d404d9fa7250c2eb2646df731d1c06afc06dcee9e1bcf88"
@@ -854,7 +854,7 @@ dependencies = [
 "checksum syn 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)" = "0e7bedb3320d0f3035594b0b723c8a28d7d336a3eda3881db79e61d676fb644c"
 "checksum synstructure 0.12.1 (registry+https://github.com/rust-lang/crates.io-index)" = "3f085a5855930c0441ca1288cf044ea4aecf4f43a91668abdb870b4ba546a203"
 "checksum term 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)" = "c0863a3345e70f61d613eab32ee046ccd1bcc5f9105fe402c61fcd0c13eeb8b5"
-"checksum termimad 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)" = "6413a6129d509b86617526ecfc72a4c67b178e4f78cda3d1b49d3c6c64877eff"
+"checksum termimad 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)" = "fcd4e6aad24b4c35155627906ed29f9279d1cdb165f825f81bca43a710657860"
 "checksum textwrap 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "d326610f408c7a4eb6f51c37c330e496b08506c9457c9d34287ecc38809fb060"
 "checksum thiserror 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "9fe148fa0fc3363a27092d48f7787363ded15bb8623c5d5dd4e2e9f23e4b21bc"
 "checksum thiserror-impl 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "258da67e99e590650fa541ac6be764313d23e80cefb6846b516deb8de6b6d921"
diff --git a/Cargo.toml b/Cargo.toml
index 98c7fe6..cd57c9b 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -26,8 +26,8 @@ crossbeam = "0.7"
 opener = "0.4"
 crossterm = "0.13.2"
 umask = "0.1.7"
-minimad = "0.5.0"
-termimad = "0.8.0"
+minimad = "0.5.1"
+termimad = "0.8.1"
 id-arena = "2.2.1"
 lazy-regex = "0.1"
 
diff --git a/README.md b/README.md
index 1b0f885..3f1e592 100644
--- a/README.md
+++ b/README.md
@@ -60,11 +60,11 @@ Once the file you want is selected you can
 
 ![mv](img/20191112-mv.png)
 
-Most often you move your files in the blind. You do a few `ls` before, then your manipulation, and maybe you check after.
+Without broot you move your files in the blind. You do a few `ls` before, then your manipulation, and maybe you check after.
 
 You can instead do it without losing the view of the file hierarchy.
 
-Move, copy, rm, mkdir, are built in and you can add your own shortcuts.
+`mv`, `cp`, `rm`, `mkdir`, are built in and you can add your own shortcuts.
 
 ### Apply a standard or personal shortcut to a file
 
diff --git a/src/fuzzy_patterns.rs b/src/fuzzy_patterns.rs
index 8a741fd..47333d6 100644
--- a/src/fuzzy_patterns.rs
+++ b/src/fuzzy_patterns.rs
@@ -30,6 +30,12 @@ impl fmt::Display for FuzzyPattern {
     }
 }
 
+enum MatchSearchResult {
+    Perfect(Match), // no need to test other positions
+    Some(Match),
+    None,
+}
+
 impl FuzzyPattern {
     pub fn from(pat: &str) -> FuzzyPattern {
         let lc_chars: Vec<char> = pat.chars().map(|c| c.to_ascii_lowercase()).collect();
@@ -50,13 +56,14 @@ impl FuzzyPattern {
             max_nb_holes,
         }
     }
+
     fn match_starting_at_index(
         &self,
         cand_chars: &[char],
         start_idx: usize, // start index in candidate
-    ) -> Option<Match> {
+    ) -> MatchSearchResult {
         if cand_chars[start_idx] != self.lc_chars[0] {
-            return None;
+            return MatchSearchResult::None;
         }
         let mut pos: Vec<usize> = vec![]; // positions of matching chars in candidate
         pos.push(start_idx);
@@ -67,7 +74,7 @@ impl FuzzyPattern {
             loop {
                 let cand_idx = start_idx + d;
                 if cand_idx == cand_chars.len() {
-                    return None;
+                    return MatchSearchResult::None;
                 }
                 d += 1;
                 if cand_chars[cand_idx] == self.lc_chars[pat_idx] {
@@ -79,7 +86,7 @@ impl FuzzyPattern {
                 // note that there's no absolute guarantee we found the minimal
                 // number of holes. The algorithm isn't perfect
                 if nb_holes >= self.max_nb_holes {
-                    return None;
+                    return MatchSearchResult::None;
                 }
                 nb_holes += 1;
             }
@@ -93,32 +100,43 @@ impl FuzzyPattern {
             score += BONUS_START;
             if cand_chars.len() == self.lc_chars.len() {
                 score += BONUS_EXACT;
+                return MatchSearchResult::Perfect(Match { score, pos });
             }
         } else {
             let previous = cand_chars[start_idx - 1];
             if previous == '_' || previous == ' ' || previous == '-' {
                 score += BONUS_START_WORD;
+                if cand_chars.len() == self.lc_chars.len() {
+                    return MatchSearchResult::Perfect(Match { score, pos });
+                }
             }
         }
-        Some(Match { score, pos })
+        MatchSearchResult::Some(Match { score, pos })
     }
     // return a match if the pattern can be found in the candidate string.
     // The algorithm tries to return the best one. For example if you search
-    // "abc" in "ababaca-abc", the returned match would be at the end.
+    // "abc" in "ababca-abc", the returned match would be at the end.
     pub fn find(&self, candidate: &str) -> Option<Match> {
-        let cand_chars: Vec<char> = candidate.chars().map(|c| c.to_ascii_lowercase()).collect();
+        let mut cand_chars: Vec<char> = Vec::with_capacity(candidate.len());
+        cand_chars.extend(candidate.chars().map(|c| c.to_ascii_lowercase()));
         if cand_chars.len() < self.lc_chars.len() {
             return None;
         }
         let mut best_score = 0;
         let mut best_match: Option<Match> = None;
-        for start_idx in 0..=cand_chars.len() - self.lc_chars.len() {
-            let sm = self.match_starting_at_index(&cand_chars, start_idx);
-            if let Some(m) = sm {
-                if m.score > best_score {
-                    best_score = m.score;
-                    best_match = Some(m);
+        let n = cand_chars.len() - self.lc_chars.len();
+        for start_idx in 0..=n {
+            match self.match_starting_at_index(&cand_chars, start_idx) {
+                MatchSearchResult::Perfect(m) => {
+                    return Some(m);
+                }
+                MatchSearchResult::Some(m) => {
+                    if m.score > best_score {
+                        best_score = m.score;
+                        best_match = Some(m);
+                    }
                 }
+                _ => {}
             }
         }
         best_match
@@ -126,6 +144,6 @@ impl FuzzyPattern {
     // return the number of results we should find before starting to
     //  sort them (unless time is runing out).
     pub const fn optimal_result_number(&self, targeted_size: usize) -> usize {
-        20 * targeted_size
+        40 * targeted_size
     }
 }
diff --git a/src/tree_build.rs b/src/tree_build.rs
index 8655c06..57ce3e1 100644
--- a/src/tree_build.rs
+++ b/src/tree_build.rs
@@ -19,6 +19,11 @@ use crate::{
 
 type BId = Id<BLine>;
 
+/// If a search found enough results to fill the screen but didn't scan
+/// everything, we search a little more in case we find better matches
+/// but not after the NOT_LONG duration.
+static NOT_LONG: Duration = Duration::from_millis(1300);
+
 /// like a tree line, but with the info needed during the build
 /// This structure isn't usable independantly from the tree builder
 struct BLine {
@@ -325,7 +330,6 @@ impl TreeBuilder {
     fn gather_lines(&mut self, task_lifetime: &TaskLifetime) -> Option<Vec<BId>> {
         let start = Instant::now();
         let mut out_blines: Vec<BId> = Vec::new(); // the blines we want to display
-        let not_long = Duration::from_millis(600);
         let optimal_size = self
             .options
             .pattern
@@ -338,7 +342,7 @@ impl TreeBuilder {
         open_dirs.push_back(self.root_id);
         loop {
             if (nb_lines_ok > optimal_size)
-                || (nb_lines_ok >= self.targeted_size && start.elapsed() > not_long)
+                || (nb_lines_ok >= self.targeted_size && start.elapsed() > NOT_LONG)
             {
                 break;
             }
diff --git a/website/docs/documentation/installation.md b/website/docs/documentation/installation.md
index 744a463..a3f74b9 100644
--- a/website/docs/documentation/installation.md
+++ b/website/docs/documentation/installation.md
@@ -30,9 +30,7 @@ You'll need to have the [Rust development environment](https://www.rust-lang.org
 
 Fetch the Canop/broot repository, move to the broot directory, then run
 
-    cargo build --release
-
-The executable is written in the `target/release` directory (you might want to move it to your `/usr/bin`, or to add the release directory to your path).
+    cargo install --path .
 
 # Installation Completion : the `br` shell function