Squashed 'crates/atuin-nucleo/' content from commit 4253de9f

git-subtree-dir: crates/atuin-nucleo
git-subtree-split: 4253de9faabb4e5c6d81d946a5e35a90f87347ee

1 files changed, 51 insertions, 0 deletions

diff --git a/matcher/src/fuzzy_greedy.rs b/matcher/src/fuzzy_greedy.rs
new file mode 100644
index 00000000..8215bf31
--- /dev/null
+++ b/matcher/src/fuzzy_greedy.rs
@@ -0,0 +1,51 @@
+use crate::chars::Char;
+use crate::Matcher;
+
+impl Matcher {
+    /// greedy fallback algorithm, much faster (linear time) but reported scores/indicies
+    /// might not be the best match
+    pub(crate) fn fuzzy_match_greedy_<const INDICES: bool, H: Char + PartialEq<N>, N: Char>(
+        &mut self,
+        haystack: &[H],
+        needle: &[N],
+        mut start: usize,
+        mut end: usize,
+        indices: &mut Vec<u32>,
+    ) -> Option<u16> {
+        let first_char_end = if H::ASCII && N::ASCII { start + 1 } else { end };
+        'nonascii: {
+            if !H::ASCII || !N::ASCII {
+                let mut needle_iter = needle[1..].iter().copied();
+                if let Some(mut needle_char) = needle_iter.next() {
+                    for (i, &c) in haystack[first_char_end..].iter().enumerate() {
+                        if c.normalize(&self.config) == needle_char {
+                            let Some(next_needle_char) = needle_iter.next() else {
+                                // we found a match so we are now in the same state
+                                // as the prefilter would produce
+                                end = first_char_end + i + 1;
+                                break 'nonascii;
+                            };
+                            needle_char = next_needle_char;
+                        }
+                    }
+                    // some needle chars were not matched bail out
+                    return None;
+                }
+            }
+        } // minimize the greedly match by greedy matching in reverse
+
+        let mut needle_iter = needle.iter().rev().copied();
+        let mut needle_char = needle_iter.next().unwrap();
+        for (i, &c) in haystack[start..end].iter().enumerate().rev() {
+            let c = c.normalize(&self.config);
+            if c == needle_char {
+                let Some(next_needle_char) = needle_iter.next() else {
+                    start += i;
+                    break;
+                };
+                needle_char = next_needle_char;
+            }
+        }
+        Some(self.calculate_score::<INDICES, H, N>(haystack, needle, start, end, indices))
+    }
+}