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

3 files changed, 111 insertions, 0 deletions

diff --git a/crates/atuin-nucleo/matcher/fuzz/.gitignore b/crates/atuin-nucleo/matcher/fuzz/.gitignore
new file mode 100644
index 00000000..1a45eee7
--- /dev/null
+++ b/crates/atuin-nucleo/matcher/fuzz/.gitignore
@@ -0,0 +1,4 @@
+target
+corpus
+artifacts
+coverage
diff --git a/crates/atuin-nucleo/matcher/fuzz/Cargo.toml b/crates/atuin-nucleo/matcher/fuzz/Cargo.toml
new file mode 100644
index 00000000..1b9d8a7f
--- /dev/null
+++ b/crates/atuin-nucleo/matcher/fuzz/Cargo.toml
@@ -0,0 +1,29 @@
+[package]
+name = "fzf_oxide-fuzz"
+version = "0.0.0"
+publish = false
+edition = "2021"
+
+[package.metadata]
+cargo-fuzz = true
+
+[dependencies]
+libfuzzer-sys = "0.4"
+arbitrary = { version = "1", features = ["derive"] }
+
+[dependencies.fzf_oxide]
+path = ".."
+
+# Prevent this from interfering with workspaces
+[workspace]
+members = ["."]
+
+[profile.release]
+debug = 1
+
+[[bin]]
+name = "fuzz_target_1"
+path = "fuzz_targets/fuzz_target_1.rs"
+test = false
+doc = false
+
diff --git a/crates/atuin-nucleo/matcher/fuzz/fuzz_targets/fuzz_target_1.rs b/crates/atuin-nucleo/matcher/fuzz/fuzz_targets/fuzz_target_1.rs
new file mode 100644
index 00000000..00940d58
--- /dev/null
+++ b/crates/atuin-nucleo/matcher/fuzz/fuzz_targets/fuzz_target_1.rs
@@ -0,0 +1,78 @@
+#![no_main]
+
+use fzf_oxide::{chars, Matcher, MatcherConfig, Utf32Str};
+use libfuzzer_sys::arbitrary::Arbitrary;
+use libfuzzer_sys::fuzz_target;
+
+#[derive(Arbitrary, Debug)]
+pub struct Input<'a> {
+    haystack: &'a str,
+    needle: &'a str,
+    ignore_case: bool,
+    normalize: bool,
+}
+
+fuzz_target!(|data: Input<'_>| {
+    let mut data = data;
+    let mut config = MatcherConfig::DEFAULT;
+    config.ignore_case = data.ignore_case;
+    config.normalize = data.normalize;
+    let mut matcher = Matcher::new(config);
+    let mut indices_optimal = Vec::new();
+    let mut indices_greedy = Vec::new();
+    let mut needle_buf = Vec::new();
+    let mut haystack_buf = Vec::new();
+    let normalize = |mut c: char| {
+        if config.normalize {
+            c = chars::normalize(c);
+        }
+        if config.ignore_case {
+            c = chars::to_lower_case(c);
+        }
+        c
+    };
+    let needle: String = data.needle.chars().map(normalize).collect();
+    let needle_chars: Vec<_> = needle.chars().collect();
+    let needle = Utf32Str::new(&needle, &mut needle_buf);
+    let haystack = Utf32Str::new(data.haystack, &mut haystack_buf);
+
+    let greedy_score = matcher.fuzzy_indices_greedy(haystack, needle, &mut indices_greedy);
+    if greedy_score.is_some() {
+        let match_chars: Vec<_> = indices_greedy
+            .iter()
+            .map(|&i| normalize(haystack.get(i)))
+            .collect();
+        assert_eq!(
+            match_chars, needle_chars,
+            "failed match, found {indices_greedy:?} {match_chars:?} (greedy)"
+        );
+    }
+    let optimal_score = matcher.fuzzy_indices(haystack, needle, &mut indices_optimal);
+    if optimal_score.is_some() {
+        let match_chars: Vec<_> = indices_optimal
+            .iter()
+            .map(|&i| normalize(haystack.get(i)))
+            .collect();
+        assert_eq!(
+            match_chars, needle_chars,
+            "failed match, found {indices_optimal:?} {match_chars:?}"
+        );
+    }
+    match (greedy_score, optimal_score) {
+        (None, Some(score)) => unreachable!("optimal matched {score} but greedy did not match"),
+        (Some(score), None) => unreachable!("greedy matched {score} but optimal did not match"),
+        (Some(greedy), Some(optimal)) => {
+            assert!(
+                greedy <= optimal,
+                "optimal score must be at least the same as greedy score {greedy} {optimal}"
+            );
+            if indices_greedy == indices_optimal {
+                assert_eq!(
+                    greedy, optimal,
+                    "if matching same char greedy and optimal score should be identical"
+                )
+            }
+        }
+        (None, None) => (),
+    }
+});