chore: vendor nucleo-ext + fork, so we can depend on our changes properly (#3284)

We cannot publish to crates.io without specifying a version, and we
cannot do that without properly forking nucleo. We're shipping
atuin-nucleo, but will likely drop this if we can get our changes
upstream. This is highlighted in the README + manifest, and the original
author is still included.

Originally forked here: https://github.com/atuinsh/nucleo-ext

cc @BinaryMuse - this should just be a vendor + restructure, but would
appreciate the sanity check

## Checks
- [ ] I am happy for maintainers to push small adjustments to this PR,
to speed up the review cycle
- [ ] I have checked that there are no existing pull requests for the
same thing

1 files changed, 51 insertions, 0 deletions

diff --git a/crates/atuin-nucleo/matcher/src/fuzzy_greedy.rs b/crates/atuin-nucleo/matcher/src/fuzzy_greedy.rs
new file mode 100644
index 00000000..386d289c
--- /dev/null
+++ b/crates/atuin-nucleo/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/indices
+    /// 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))
+    }
+}