Initial vendor packages

Signed-off-by: Valentin Popov <valentin@popov.link>

3 files changed, 661 insertions, 0 deletions

diff --git a/vendor/memchr/src/tests/memchr/mod.rs b/vendor/memchr/src/tests/memchr/mod.rs
new file mode 100644
index 0000000..0564ad4
--- /dev/null
+++ b/vendor/memchr/src/tests/memchr/mod.rs
@@ -0,0 +1,307 @@
+use alloc::{
+    string::{String, ToString},
+    vec,
+    vec::Vec,
+};
+
+use crate::ext::Byte;
+
+pub(crate) mod naive;
+#[macro_use]
+pub(crate) mod prop;
+
+const SEEDS: &'static [Seed] = &[
+    Seed { haystack: "a", needles: &[b'a'], positions: &[0] },
+    Seed { haystack: "aa", needles: &[b'a'], positions: &[0, 1] },
+    Seed { haystack: "aaa", needles: &[b'a'], positions: &[0, 1, 2] },
+    Seed { haystack: "", needles: &[b'a'], positions: &[] },
+    Seed { haystack: "z", needles: &[b'a'], positions: &[] },
+    Seed { haystack: "zz", needles: &[b'a'], positions: &[] },
+    Seed { haystack: "zza", needles: &[b'a'], positions: &[2] },
+    Seed { haystack: "zaza", needles: &[b'a'], positions: &[1, 3] },
+    Seed { haystack: "zzza", needles: &[b'a'], positions: &[3] },
+    Seed { haystack: "\x00a", needles: &[b'a'], positions: &[1] },
+    Seed { haystack: "\x00", needles: &[b'\x00'], positions: &[0] },
+    Seed { haystack: "\x00\x00", needles: &[b'\x00'], positions: &[0, 1] },
+    Seed { haystack: "\x00a\x00", needles: &[b'\x00'], positions: &[0, 2] },
+    Seed { haystack: "zzzzzzzzzzzzzzzza", needles: &[b'a'], positions: &[16] },
+    Seed {
+        haystack: "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzza",
+        needles: &[b'a'],
+        positions: &[32],
+    },
+    // two needles (applied to memchr2 + memchr3)
+    Seed { haystack: "az", needles: &[b'a', b'z'], positions: &[0, 1] },
+    Seed { haystack: "az", needles: &[b'a', b'z'], positions: &[0, 1] },
+    Seed { haystack: "az", needles: &[b'x', b'y'], positions: &[] },
+    Seed { haystack: "az", needles: &[b'a', b'y'], positions: &[0] },
+    Seed { haystack: "az", needles: &[b'x', b'z'], positions: &[1] },
+    Seed { haystack: "yyyyaz", needles: &[b'a', b'z'], positions: &[4, 5] },
+    Seed { haystack: "yyyyaz", needles: &[b'z', b'a'], positions: &[4, 5] },
+    // three needles (applied to memchr3)
+    Seed {
+        haystack: "xyz",
+        needles: &[b'x', b'y', b'z'],
+        positions: &[0, 1, 2],
+    },
+    Seed {
+        haystack: "zxy",
+        needles: &[b'x', b'y', b'z'],
+        positions: &[0, 1, 2],
+    },
+    Seed { haystack: "zxy", needles: &[b'x', b'a', b'z'], positions: &[0, 1] },
+    Seed { haystack: "zxy", needles: &[b't', b'a', b'z'], positions: &[0] },
+    Seed { haystack: "yxz", needles: &[b't', b'a', b'z'], positions: &[2] },
+];
+
+/// Runs a host of substring search tests.
+///
+/// This has support for "partial" substring search implementations only work
+/// for a subset of needles/haystacks. For example, the "packed pair" substring
+/// search implementation only works for haystacks of some minimum length based
+/// of the pair of bytes selected and the size of the vector used.
+pub(crate) struct Runner {
+    needle_len: usize,
+}
+
+impl Runner {
+    /// Create a new test runner for forward and reverse byte search
+    /// implementations.
+    ///
+    /// The `needle_len` given must be at most `3` and at least `1`. It
+    /// corresponds to the number of needle bytes to search for.
+    pub(crate) fn new(needle_len: usize) -> Runner {
+        assert!(needle_len >= 1, "needle_len must be at least 1");
+        assert!(needle_len <= 3, "needle_len must be at most 3");
+        Runner { needle_len }
+    }
+
+    /// Run all tests. This panics on the first failure.
+    ///
+    /// If the implementation being tested returns `None` for a particular
+    /// haystack/needle combination, then that test is skipped.
+    pub(crate) fn forward_iter<F>(self, mut test: F)
+    where
+        F: FnMut(&[u8], &[u8]) -> Option<Vec<usize>> + 'static,
+    {
+        for seed in SEEDS.iter() {
+            if seed.needles.len() > self.needle_len {
+                continue;
+            }
+            for t in seed.generate() {
+                let results = match test(t.haystack.as_bytes(), &t.needles) {
+                    None => continue,
+                    Some(results) => results,
+                };
+                assert_eq!(
+                    t.expected,
+                    results,
+                    "needles: {:?}, haystack: {:?}",
+                    t.needles
+                        .iter()
+                        .map(|&b| b.to_char())
+                        .collect::<Vec<char>>(),
+                    t.haystack,
+                );
+            }
+        }
+    }
+
+    /// Run all tests in the reverse direction. This panics on the first
+    /// failure.
+    ///
+    /// If the implementation being tested returns `None` for a particular
+    /// haystack/needle combination, then that test is skipped.
+    pub(crate) fn reverse_iter<F>(self, mut test: F)
+    where
+        F: FnMut(&[u8], &[u8]) -> Option<Vec<usize>> + 'static,
+    {
+        for seed in SEEDS.iter() {
+            if seed.needles.len() > self.needle_len {
+                continue;
+            }
+            for t in seed.generate() {
+                let mut results = match test(t.haystack.as_bytes(), &t.needles)
+                {
+                    None => continue,
+                    Some(results) => results,
+                };
+                results.reverse();
+                assert_eq!(
+                    t.expected,
+                    results,
+                    "needles: {:?}, haystack: {:?}",
+                    t.needles
+                        .iter()
+                        .map(|&b| b.to_char())
+                        .collect::<Vec<char>>(),
+                    t.haystack,
+                );
+            }
+        }
+    }
+
+    /// Run all tests as counting tests. This panics on the first failure.
+    ///
+    /// That is, this only checks that the number of matches is correct and
+    /// not whether the offsets of each match are.
+    pub(crate) fn count_iter<F>(self, mut test: F)
+    where
+        F: FnMut(&[u8], &[u8]) -> Option<usize> + 'static,
+    {
+        for seed in SEEDS.iter() {
+            if seed.needles.len() > self.needle_len {
+                continue;
+            }
+            for t in seed.generate() {
+                let got = match test(t.haystack.as_bytes(), &t.needles) {
+                    None => continue,
+                    Some(got) => got,
+                };
+                assert_eq!(
+                    t.expected.len(),
+                    got,
+                    "needles: {:?}, haystack: {:?}",
+                    t.needles
+                        .iter()
+                        .map(|&b| b.to_char())
+                        .collect::<Vec<char>>(),
+                    t.haystack,
+                );
+            }
+        }
+    }
+
+    /// Like `Runner::forward`, but for a function that returns only the next
+    /// match and not all matches.
+    ///
+    /// If the function returns `None`, then it is skipped.
+    pub(crate) fn forward_oneshot<F>(self, mut test: F)
+    where
+        F: FnMut(&[u8], &[u8]) -> Option<Option<usize>> + 'static,
+    {
+        self.forward_iter(move |haystack, needles| {
+            let mut start = 0;
+            let mut results = vec![];
+            while let Some(i) = test(&haystack[start..], needles)? {
+                results.push(start + i);
+                start += i + 1;
+            }
+            Some(results)
+        })
+    }
+
+    /// Like `Runner::reverse`, but for a function that returns only the last
+    /// match and not all matches.
+    ///
+    /// If the function returns `None`, then it is skipped.
+    pub(crate) fn reverse_oneshot<F>(self, mut test: F)
+    where
+        F: FnMut(&[u8], &[u8]) -> Option<Option<usize>> + 'static,
+    {
+        self.reverse_iter(move |haystack, needles| {
+            let mut end = haystack.len();
+            let mut results = vec![];
+            while let Some(i) = test(&haystack[..end], needles)? {
+                results.push(i);
+                end = i;
+            }
+            Some(results)
+        })
+    }
+}
+
+/// A single test for memr?chr{,2,3}.
+#[derive(Clone, Debug)]
+struct Test {
+    /// The string to search in.
+    haystack: String,
+    /// The needles to look for.
+    needles: Vec<u8>,
+    /// The offsets that are expected to be found for all needles in the
+    /// forward direction.
+    expected: Vec<usize>,
+}
+
+impl Test {
+    fn new(seed: &Seed) -> Test {
+        Test {
+            haystack: seed.haystack.to_string(),
+            needles: seed.needles.to_vec(),
+            expected: seed.positions.to_vec(),
+        }
+    }
+}
+
+/// Data that can be expanded into many memchr tests by padding out the corpus.
+#[derive(Clone, Debug)]
+struct Seed {
+    /// The thing to search. We use `&str` instead of `&[u8]` because they
+    /// are nicer to write in tests, and we don't miss much since memchr
+    /// doesn't care about UTF-8.
+    ///
+    /// Corpora cannot contain either '%' or '#'. We use these bytes when
+    /// expanding test cases into many test cases, and we assume they are not
+    /// used. If they are used, `memchr_tests` will panic.
+    haystack: &'static str,
+    /// The needles to search for. This is intended to be an alternation of
+    /// needles. The number of needles may cause this test to be skipped for
+    /// some memchr variants. For example, a test with 2 needles cannot be used
+    /// to test `memchr`, but can be used to test `memchr2` and `memchr3`.
+    /// However, a test with only 1 needle can be used to test all of `memchr`,
+    /// `memchr2` and `memchr3`. We achieve this by filling in the needles with
+    /// bytes that we never used in the corpus (such as '#').
+    needles: &'static [u8],
+    /// The positions expected to match for all of the needles.
+    positions: &'static [usize],
+}
+
+impl Seed {
+    /// Controls how much we expand the haystack on either side for each test.
+    /// We lower this on Miri because otherwise running the tests would take
+    /// forever.
+    const EXPAND_LEN: usize = {
+        #[cfg(not(miri))]
+        {
+            515
+        }
+        #[cfg(miri)]
+        {
+            6
+        }
+    };
+
+    /// Expand this test into many variations of the same test.
+    ///
+    /// In particular, this will generate more tests with larger corpus sizes.
+    /// The expected positions are updated to maintain the integrity of the
+    /// test.
+    ///
+    /// This is important in testing a memchr implementation, because there are
+    /// often different cases depending on the length of the corpus.
+    ///
+    /// Note that we extend the corpus by adding `%` bytes, which we
+    /// don't otherwise use as a needle.
+    fn generate(&self) -> impl Iterator<Item = Test> {
+        let mut more = vec![];
+
+        // Add bytes to the start of the corpus.
+        for i in 0..Seed::EXPAND_LEN {
+            let mut t = Test::new(self);
+            let mut new: String = core::iter::repeat('%').take(i).collect();
+            new.push_str(&t.haystack);
+            t.haystack = new;
+            t.expected = t.expected.into_iter().map(|p| p + i).collect();
+            more.push(t);
+        }
+        // Add bytes to the end of the corpus.
+        for i in 1..Seed::EXPAND_LEN {
+            let mut t = Test::new(self);
+            let padding: String = core::iter::repeat('%').take(i).collect();
+            t.haystack.push_str(&padding);
+            more.push(t);
+        }
+
+        more.into_iter()
+    }
+}
diff --git a/vendor/memchr/src/tests/memchr/naive.rs b/vendor/memchr/src/tests/memchr/naive.rs
new file mode 100644
index 0000000..6ebcdae
--- /dev/null
+++ b/vendor/memchr/src/tests/memchr/naive.rs
@@ -0,0 +1,33 @@
+pub(crate) fn memchr(n1: u8, haystack: &[u8]) -> Option<usize> {
+    haystack.iter().position(|&b| b == n1)
+}
+
+pub(crate) fn memchr2(n1: u8, n2: u8, haystack: &[u8]) -> Option<usize> {
+    haystack.iter().position(|&b| b == n1 || b == n2)
+}
+
+pub(crate) fn memchr3(
+    n1: u8,
+    n2: u8,
+    n3: u8,
+    haystack: &[u8],
+) -> Option<usize> {
+    haystack.iter().position(|&b| b == n1 || b == n2 || b == n3)
+}
+
+pub(crate) fn memrchr(n1: u8, haystack: &[u8]) -> Option<usize> {
+    haystack.iter().rposition(|&b| b == n1)
+}
+
+pub(crate) fn memrchr2(n1: u8, n2: u8, haystack: &[u8]) -> Option<usize> {
+    haystack.iter().rposition(|&b| b == n1 || b == n2)
+}
+
+pub(crate) fn memrchr3(
+    n1: u8,
+    n2: u8,
+    n3: u8,
+    haystack: &[u8],
+) -> Option<usize> {
+    haystack.iter().rposition(|&b| b == n1 || b == n2 || b == n3)
+}
diff --git a/vendor/memchr/src/tests/memchr/prop.rs b/vendor/memchr/src/tests/memchr/prop.rs
new file mode 100644
index 0000000..b988260
--- /dev/null
+++ b/vendor/memchr/src/tests/memchr/prop.rs
@@ -0,0 +1,321 @@
+#[cfg(miri)]
+#[macro_export]
+macro_rules! define_memchr_quickcheck {
+    ($($tt:tt)*) => {};
+}
+
+#[cfg(not(miri))]
+#[macro_export]
+macro_rules! define_memchr_quickcheck {
+    ($mod:ident) => {
+        define_memchr_quickcheck!($mod, new);
+    };
+    ($mod:ident, $cons:ident) => {
+        use alloc::vec::Vec;
+
+        use quickcheck::TestResult;
+
+        use crate::tests::memchr::{
+            naive,
+            prop::{double_ended_take, naive1_iter, naive2_iter, naive3_iter},
+        };
+
+        quickcheck::quickcheck! {
+            fn qc_memchr_matches_naive(n1: u8, corpus: Vec<u8>) -> TestResult {
+                let expected = naive::memchr(n1, &corpus);
+                let got = match $mod::One::$cons(n1) {
+                    None => return TestResult::discard(),
+                    Some(f) => f.find(&corpus),
+                };
+                TestResult::from_bool(expected == got)
+            }
+
+            fn qc_memrchr_matches_naive(n1: u8, corpus: Vec<u8>) -> TestResult {
+                let expected = naive::memrchr(n1, &corpus);
+                let got = match $mod::One::$cons(n1) {
+                    None => return TestResult::discard(),
+                    Some(f) => f.rfind(&corpus),
+                };
+                TestResult::from_bool(expected == got)
+            }
+
+            fn qc_memchr2_matches_naive(n1: u8, n2: u8, corpus: Vec<u8>) -> TestResult {
+                let expected = naive::memchr2(n1, n2, &corpus);
+                let got = match $mod::Two::$cons(n1, n2) {
+                    None => return TestResult::discard(),
+                    Some(f) => f.find(&corpus),
+                };
+                TestResult::from_bool(expected == got)
+            }
+
+            fn qc_memrchr2_matches_naive(n1: u8, n2: u8, corpus: Vec<u8>) -> TestResult {
+                let expected = naive::memrchr2(n1, n2, &corpus);
+                let got = match $mod::Two::$cons(n1, n2) {
+                    None => return TestResult::discard(),
+                    Some(f) => f.rfind(&corpus),
+                };
+                TestResult::from_bool(expected == got)
+            }
+
+            fn qc_memchr3_matches_naive(
+                n1: u8, n2: u8, n3: u8,
+                corpus: Vec<u8>
+            ) -> TestResult {
+                let expected = naive::memchr3(n1, n2, n3, &corpus);
+                let got = match $mod::Three::$cons(n1, n2, n3) {
+                    None => return TestResult::discard(),
+                    Some(f) => f.find(&corpus),
+                };
+                TestResult::from_bool(expected == got)
+            }
+
+            fn qc_memrchr3_matches_naive(
+                n1: u8, n2: u8, n3: u8,
+                corpus: Vec<u8>
+            ) -> TestResult {
+                let expected = naive::memrchr3(n1, n2, n3, &corpus);
+                let got = match $mod::Three::$cons(n1, n2, n3) {
+                    None => return TestResult::discard(),
+                    Some(f) => f.rfind(&corpus),
+                };
+                TestResult::from_bool(expected == got)
+            }
+
+            fn qc_memchr_double_ended_iter(
+                needle: u8, data: Vec<u8>, take_side: Vec<bool>
+            ) -> TestResult {
+                // make nonempty
+                let mut take_side = take_side;
+                if take_side.is_empty() { take_side.push(true) };
+
+                let finder = match $mod::One::$cons(needle) {
+                    None => return TestResult::discard(),
+                    Some(finder) => finder,
+                };
+                let iter = finder.iter(&data);
+                let got = double_ended_take(
+                    iter,
+                    take_side.iter().cycle().cloned(),
+                );
+                let expected = naive1_iter(needle, &data);
+
+                TestResult::from_bool(got.iter().cloned().eq(expected))
+            }
+
+            fn qc_memchr2_double_ended_iter(
+                needle1: u8, needle2: u8, data: Vec<u8>, take_side: Vec<bool>
+            ) -> TestResult {
+                // make nonempty
+                let mut take_side = take_side;
+                if take_side.is_empty() { take_side.push(true) };
+
+                let finder = match $mod::Two::$cons(needle1, needle2) {
+                    None => return TestResult::discard(),
+                    Some(finder) => finder,
+                };
+                let iter = finder.iter(&data);
+                let got = double_ended_take(
+                    iter,
+                    take_side.iter().cycle().cloned(),
+                );
+                let expected = naive2_iter(needle1, needle2, &data);
+
+                TestResult::from_bool(got.iter().cloned().eq(expected))
+            }
+
+            fn qc_memchr3_double_ended_iter(
+                needle1: u8, needle2: u8, needle3: u8,
+                data: Vec<u8>, take_side: Vec<bool>
+            ) -> TestResult {
+                // make nonempty
+                let mut take_side = take_side;
+                if take_side.is_empty() { take_side.push(true) };
+
+                let finder = match $mod::Three::$cons(needle1, needle2, needle3) {
+                    None => return TestResult::discard(),
+                    Some(finder) => finder,
+                };
+                let iter = finder.iter(&data);
+                let got = double_ended_take(
+                    iter,
+                    take_side.iter().cycle().cloned(),
+                );
+                let expected = naive3_iter(needle1, needle2, needle3, &data);
+
+                TestResult::from_bool(got.iter().cloned().eq(expected))
+            }
+
+            fn qc_memchr1_iter(data: Vec<u8>) -> TestResult {
+                let needle = 0;
+                let finder = match $mod::One::$cons(needle) {
+                    None => return TestResult::discard(),
+                    Some(finder) => finder,
+                };
+                let got = finder.iter(&data);
+                let expected = naive1_iter(needle, &data);
+                TestResult::from_bool(got.eq(expected))
+            }
+
+            fn qc_memchr1_rev_iter(data: Vec<u8>) -> TestResult {
+                let needle = 0;
+
+                let finder = match $mod::One::$cons(needle) {
+                    None => return TestResult::discard(),
+                    Some(finder) => finder,
+                };
+                let got = finder.iter(&data).rev();
+                let expected = naive1_iter(needle, &data).rev();
+                TestResult::from_bool(got.eq(expected))
+            }
+
+            fn qc_memchr2_iter(data: Vec<u8>) -> TestResult {
+                let needle1 = 0;
+                let needle2 = 1;
+
+                let finder = match $mod::Two::$cons(needle1, needle2) {
+                    None => return TestResult::discard(),
+                    Some(finder) => finder,
+                };
+                let got = finder.iter(&data);
+                let expected = naive2_iter(needle1, needle2, &data);
+                TestResult::from_bool(got.eq(expected))
+            }
+
+            fn qc_memchr2_rev_iter(data: Vec<u8>) -> TestResult {
+                let needle1 = 0;
+                let needle2 = 1;
+
+                let finder = match $mod::Two::$cons(needle1, needle2) {
+                    None => return TestResult::discard(),
+                    Some(finder) => finder,
+                };
+                let got = finder.iter(&data).rev();
+                let expected = naive2_iter(needle1, needle2, &data).rev();
+                TestResult::from_bool(got.eq(expected))
+            }
+
+            fn qc_memchr3_iter(data: Vec<u8>) -> TestResult {
+                let needle1 = 0;
+                let needle2 = 1;
+                let needle3 = 2;
+
+                let finder = match $mod::Three::$cons(needle1, needle2, needle3) {
+                    None => return TestResult::discard(),
+                    Some(finder) => finder,
+                };
+                let got = finder.iter(&data);
+                let expected = naive3_iter(needle1, needle2, needle3, &data);
+                TestResult::from_bool(got.eq(expected))
+            }
+
+            fn qc_memchr3_rev_iter(data: Vec<u8>) -> TestResult {
+                let needle1 = 0;
+                let needle2 = 1;
+                let needle3 = 2;
+
+                let finder = match $mod::Three::$cons(needle1, needle2, needle3) {
+                    None => return TestResult::discard(),
+                    Some(finder) => finder,
+                };
+                let got = finder.iter(&data).rev();
+                let expected = naive3_iter(needle1, needle2, needle3, &data).rev();
+                TestResult::from_bool(got.eq(expected))
+            }
+
+            fn qc_memchr1_iter_size_hint(data: Vec<u8>) -> TestResult {
+                // test that the size hint is within reasonable bounds
+                let needle = 0;
+                let finder = match $mod::One::$cons(needle) {
+                    None => return TestResult::discard(),
+                    Some(finder) => finder,
+                };
+                let mut iter = finder.iter(&data);
+                let mut real_count = data
+                    .iter()
+                    .filter(|&&elt| elt == needle)
+                    .count();
+
+                while let Some(index) = iter.next() {
+                    real_count -= 1;
+                    let (lower, upper) = iter.size_hint();
+                    assert!(lower <= real_count);
+                    assert!(upper.unwrap() >= real_count);
+                    assert!(upper.unwrap() <= data.len() - index);
+                }
+                TestResult::passed()
+            }
+        }
+    };
+}
+
+// take items from a DEI, taking front for each true and back for each false.
+// Return a vector with the concatenation of the fronts and the reverse of the
+// backs.
+#[cfg(not(miri))]
+pub(crate) fn double_ended_take<I, J>(
+    mut iter: I,
+    take_side: J,
+) -> alloc::vec::Vec<I::Item>
+where
+    I: DoubleEndedIterator,
+    J: Iterator<Item = bool>,
+{
+    let mut found_front = alloc::vec![];
+    let mut found_back = alloc::vec![];
+
+    for take_front in take_side {
+        if take_front {
+            if let Some(pos) = iter.next() {
+                found_front.push(pos);
+            } else {
+                break;
+            }
+        } else {
+            if let Some(pos) = iter.next_back() {
+                found_back.push(pos);
+            } else {
+                break;
+            }
+        };
+    }
+
+    let mut all_found = found_front;
+    all_found.extend(found_back.into_iter().rev());
+    all_found
+}
+
+// return an iterator of the 0-based indices of haystack that match the needle
+#[cfg(not(miri))]
+pub(crate) fn naive1_iter<'a>(
+    n1: u8,
+    haystack: &'a [u8],
+) -> impl DoubleEndedIterator<Item = usize> + 'a {
+    haystack.iter().enumerate().filter(move |&(_, &b)| b == n1).map(|t| t.0)
+}
+
+#[cfg(not(miri))]
+pub(crate) fn naive2_iter<'a>(
+    n1: u8,
+    n2: u8,
+    haystack: &'a [u8],
+) -> impl DoubleEndedIterator<Item = usize> + 'a {
+    haystack
+        .iter()
+        .enumerate()
+        .filter(move |&(_, &b)| b == n1 || b == n2)
+        .map(|t| t.0)
+}
+
+#[cfg(not(miri))]
+pub(crate) fn naive3_iter<'a>(
+    n1: u8,
+    n2: u8,
+    n3: u8,
+    haystack: &'a [u8],
+) -> impl DoubleEndedIterator<Item = usize> + 'a {
+    haystack
+        .iter()
+        .enumerate()
+        .filter(move |&(_, &b)| b == n1 || b == n2 || b == n3)
+        .map(|t| t.0)
+}