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, 100 insertions, 0 deletions

diff --git a/crates/atuin-nucleo/src/pattern.rs b/crates/atuin-nucleo/src/pattern.rs
new file mode 100644
index 00000000..a9663274
--- /dev/null
+++ b/crates/atuin-nucleo/src/pattern.rs
@@ -0,0 +1,100 @@
+pub use atuin_nucleo_matcher::pattern::{Atom, AtomKind, CaseMatching, Normalization, Pattern};
+use atuin_nucleo_matcher::{Matcher, Utf32String};
+
+#[cfg(test)]
+mod tests;
+
+#[derive(Debug, PartialEq, Eq, Clone, Copy, PartialOrd, Ord, Default)]
+pub(crate) enum Status {
+    #[default]
+    Unchanged,
+    Update,
+    Rescore,
+}
+
+#[derive(Debug)]
+pub struct MultiPattern {
+    cols: Vec<(Pattern, Status)>,
+}
+
+impl Clone for MultiPattern {
+    fn clone(&self) -> Self {
+        Self {
+            cols: self.cols.clone(),
+        }
+    }
+
+    fn clone_from(&mut self, source: &Self) {
+        self.cols.clone_from(&source.cols)
+    }
+}
+
+impl MultiPattern {
+    /// Creates a multi pattern with `columns` empty column patterns.
+    pub fn new(columns: usize) -> Self {
+        Self {
+            cols: vec![Default::default(); columns],
+        }
+    }
+
+    /// Reparses a column. By specifying `append` the caller promises that text passed
+    /// to the previous `reparse` invocation is a prefix of `new_text`. This enables
+    /// additional optimizations but can lead to missing matches if an incorrect value
+    /// is passed.
+    pub fn reparse(
+        &mut self,
+        column: usize,
+        new_text: &str,
+        case_matching: CaseMatching,
+        normalization: Normalization,
+        append: bool,
+    ) {
+        let old_status = self.cols[column].1;
+        if append
+            && old_status != Status::Rescore
+            && self.cols[column]
+                .0
+                .atoms
+                .last()
+                .is_none_or(|last| !last.negative)
+        {
+            self.cols[column].1 = Status::Update;
+        } else {
+            self.cols[column].1 = Status::Rescore;
+        }
+        self.cols[column]
+            .0
+            .reparse(new_text, case_matching, normalization);
+    }
+
+    pub fn column_pattern(&self, column: usize) -> &Pattern {
+        &self.cols[column].0
+    }
+
+    pub(crate) fn status(&self) -> Status {
+        self.cols
+            .iter()
+            .map(|&(_, status)| status)
+            .max()
+            .unwrap_or(Status::Unchanged)
+    }
+
+    pub(crate) fn reset_status(&mut self) {
+        for (_, status) in &mut self.cols {
+            *status = Status::Unchanged
+        }
+    }
+
+    pub fn score(&self, haystack: &[Utf32String], matcher: &mut Matcher) -> Option<u32> {
+        // TODO: weight columns?
+        let mut score = 0;
+        for ((pattern, _), haystack) in self.cols.iter().zip(haystack) {
+            score += pattern.score(haystack.slice(..), matcher)?
+        }
+        Some(score)
+    }
+
+    pub fn is_empty(&self) -> bool {
+        self.cols.iter().all(|(pat, _)| pat.atoms.is_empty())
+    }
+}