diff options
Diffstat (limited to 'vendor/memchr/src/tests/substring')
| -rw-r--r-- | vendor/memchr/src/tests/substring/mod.rs | 232 | ||||
| -rw-r--r-- | vendor/memchr/src/tests/substring/naive.rs | 45 | ||||
| -rw-r--r-- | vendor/memchr/src/tests/substring/prop.rs | 126 |
3 files changed, 0 insertions, 403 deletions
diff --git a/vendor/memchr/src/tests/substring/mod.rs b/vendor/memchr/src/tests/substring/mod.rs deleted file mode 100644 index dd10cbd..0000000 --- a/vendor/memchr/src/tests/substring/mod.rs +++ /dev/null @@ -1,232 +0,0 @@ -/*! -This module defines tests and test helpers for substring implementations. -*/ - -use alloc::{ - boxed::Box, - format, - string::{String, ToString}, -}; - -pub(crate) mod naive; -#[macro_use] -pub(crate) mod prop; - -const SEEDS: &'static [Seed] = &[ - Seed::new("", "", Some(0), Some(0)), - Seed::new("", "a", Some(0), Some(1)), - Seed::new("", "ab", Some(0), Some(2)), - Seed::new("", "abc", Some(0), Some(3)), - Seed::new("a", "", None, None), - Seed::new("a", "a", Some(0), Some(0)), - Seed::new("a", "aa", Some(0), Some(1)), - Seed::new("a", "ba", Some(1), Some(1)), - Seed::new("a", "bba", Some(2), Some(2)), - Seed::new("a", "bbba", Some(3), Some(3)), - Seed::new("a", "bbbab", Some(3), Some(3)), - Seed::new("a", "bbbabb", Some(3), Some(3)), - Seed::new("a", "bbbabbb", Some(3), Some(3)), - Seed::new("a", "bbbbbb", None, None), - Seed::new("ab", "", None, None), - Seed::new("ab", "a", None, None), - Seed::new("ab", "b", None, None), - Seed::new("ab", "ab", Some(0), Some(0)), - Seed::new("ab", "aab", Some(1), Some(1)), - Seed::new("ab", "aaab", Some(2), Some(2)), - Seed::new("ab", "abaab", Some(0), Some(3)), - Seed::new("ab", "baaab", Some(3), Some(3)), - Seed::new("ab", "acb", None, None), - Seed::new("ab", "abba", Some(0), Some(0)), - Seed::new("abc", "ab", None, None), - Seed::new("abc", "abc", Some(0), Some(0)), - Seed::new("abc", "abcz", Some(0), Some(0)), - Seed::new("abc", "abczz", Some(0), Some(0)), - Seed::new("abc", "zabc", Some(1), Some(1)), - Seed::new("abc", "zzabc", Some(2), Some(2)), - Seed::new("abc", "azbc", None, None), - Seed::new("abc", "abzc", None, None), - Seed::new("abczdef", "abczdefzzzzzzzzzzzzzzzzzzzz", Some(0), Some(0)), - Seed::new("abczdef", "zzzzzzzzzzzzzzzzzzzzabczdef", Some(20), Some(20)), - Seed::new( - "xyz", - "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaxyz", - Some(32), - Some(32), - ), - Seed::new("\u{0}\u{15}", "\u{0}\u{15}\u{15}\u{0}", Some(0), Some(0)), - Seed::new("\u{0}\u{1e}", "\u{1e}\u{0}", None, None), -]; - -/// 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 { - fwd: Option< - Box<dyn FnMut(&[u8], &[u8]) -> Option<Option<usize>> + 'static>, - >, - rev: Option< - Box<dyn FnMut(&[u8], &[u8]) -> Option<Option<usize>> + 'static>, - >, -} - -impl Runner { - /// Create a new test runner for forward and reverse substring search - /// implementations. - pub(crate) fn new() -> Runner { - Runner { fwd: None, rev: None } - } - - /// 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. - /// - /// This runs tests on both the forward and reverse implementations given. - /// If either (or both) are missing, then tests for that implementation are - /// skipped. - pub(crate) fn run(self) { - if let Some(mut fwd) = self.fwd { - for seed in SEEDS.iter() { - for t in seed.generate() { - match fwd(t.haystack.as_bytes(), t.needle.as_bytes()) { - None => continue, - Some(result) => { - assert_eq!( - t.fwd, result, - "FORWARD, needle: {:?}, haystack: {:?}", - t.needle, t.haystack, - ); - } - } - } - } - } - if let Some(mut rev) = self.rev { - for seed in SEEDS.iter() { - for t in seed.generate() { - match rev(t.haystack.as_bytes(), t.needle.as_bytes()) { - None => continue, - Some(result) => { - assert_eq!( - t.rev, result, - "REVERSE, needle: {:?}, haystack: {:?}", - t.needle, t.haystack, - ); - } - } - } - } - } - } - - /// Set the implementation for forward substring search. - /// - /// If the closure returns `None`, then it is assumed that the given - /// test cannot be applied to the particular implementation and it is - /// skipped. For example, if a particular implementation only supports - /// needles or haystacks for some minimum length. - /// - /// If this is not set, then forward substring search is not tested. - pub(crate) fn fwd( - mut self, - search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>> + 'static, - ) -> Runner { - self.fwd = Some(Box::new(search)); - self - } - - /// Set the implementation for reverse substring search. - /// - /// If the closure returns `None`, then it is assumed that the given - /// test cannot be applied to the particular implementation and it is - /// skipped. For example, if a particular implementation only supports - /// needles or haystacks for some minimum length. - /// - /// If this is not set, then reverse substring search is not tested. - pub(crate) fn rev( - mut self, - search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>> + 'static, - ) -> Runner { - self.rev = Some(Box::new(search)); - self - } -} - -/// A single substring test for forward and reverse searches. -#[derive(Clone, Debug)] -struct Test { - needle: String, - haystack: String, - fwd: Option<usize>, - rev: Option<usize>, -} - -/// A single substring test for forward and reverse searches. -/// -/// Each seed is valid on its own, but it also serves as a starting point -/// to generate more tests. Namely, we pad out the haystacks with other -/// characters so that we get more complete coverage. This is especially useful -/// for testing vector algorithms that tend to have weird special cases for -/// alignment and loop unrolling. -/// -/// Padding works by assuming certain characters never otherwise appear in a -/// needle or a haystack. Neither should contain a `#` character. -#[derive(Clone, Copy, Debug)] -struct Seed { - needle: &'static str, - haystack: &'static str, - fwd: Option<usize>, - rev: Option<usize>, -} - -impl Seed { - const MAX_PAD: usize = 34; - - const fn new( - needle: &'static str, - haystack: &'static str, - fwd: Option<usize>, - rev: Option<usize>, - ) -> Seed { - Seed { needle, haystack, fwd, rev } - } - - fn generate(self) -> impl Iterator<Item = Test> { - assert!(!self.needle.contains('#'), "needle must not contain '#'"); - assert!(!self.haystack.contains('#'), "haystack must not contain '#'"); - (0..=Seed::MAX_PAD) - // Generate tests for padding at the beginning of haystack. - .map(move |pad| { - let needle = self.needle.to_string(); - let prefix = "#".repeat(pad); - let haystack = format!("{}{}", prefix, self.haystack); - let fwd = if needle.is_empty() { - Some(0) - } else { - self.fwd.map(|i| pad + i) - }; - let rev = if needle.is_empty() { - Some(haystack.len()) - } else { - self.rev.map(|i| pad + i) - }; - Test { needle, haystack, fwd, rev } - }) - // Generate tests for padding at the end of haystack. - .chain((1..=Seed::MAX_PAD).map(move |pad| { - let needle = self.needle.to_string(); - let suffix = "#".repeat(pad); - let haystack = format!("{}{}", self.haystack, suffix); - let fwd = if needle.is_empty() { Some(0) } else { self.fwd }; - let rev = if needle.is_empty() { - Some(haystack.len()) - } else { - self.rev - }; - Test { needle, haystack, fwd, rev } - })) - } -} diff --git a/vendor/memchr/src/tests/substring/naive.rs b/vendor/memchr/src/tests/substring/naive.rs deleted file mode 100644 index 1bc6009..0000000 --- a/vendor/memchr/src/tests/substring/naive.rs +++ /dev/null @@ -1,45 +0,0 @@ -/*! -This module defines "naive" implementations of substring search. - -These are sometimes useful to compare with "real" substring implementations. -The idea is that they are so simple that they are unlikely to be incorrect. -*/ - -/// Naively search forwards for the given needle in the given haystack. -pub(crate) fn find(haystack: &[u8], needle: &[u8]) -> Option<usize> { - let end = haystack.len().checked_sub(needle.len()).map_or(0, |i| i + 1); - for i in 0..end { - if needle == &haystack[i..i + needle.len()] { - return Some(i); - } - } - None -} - -/// Naively search in reverse for the given needle in the given haystack. -pub(crate) fn rfind(haystack: &[u8], needle: &[u8]) -> Option<usize> { - let end = haystack.len().checked_sub(needle.len()).map_or(0, |i| i + 1); - for i in (0..end).rev() { - if needle == &haystack[i..i + needle.len()] { - return Some(i); - } - } - None -} - -#[cfg(test)] -mod tests { - use crate::tests::substring; - - use super::*; - - #[test] - fn forward() { - substring::Runner::new().fwd(|h, n| Some(find(h, n))).run() - } - - #[test] - fn reverse() { - substring::Runner::new().rev(|h, n| Some(rfind(h, n))).run() - } -} diff --git a/vendor/memchr/src/tests/substring/prop.rs b/vendor/memchr/src/tests/substring/prop.rs deleted file mode 100644 index a8352ec..0000000 --- a/vendor/memchr/src/tests/substring/prop.rs +++ /dev/null @@ -1,126 +0,0 @@ -/*! -This module defines a few quickcheck properties for substring search. - -It also provides a forward and reverse macro for conveniently defining -quickcheck tests that run these properties over any substring search -implementation. -*/ - -use crate::tests::substring::naive; - -/// $fwd is a `impl FnMut(haystack, needle) -> Option<Option<usize>>`. When the -/// routine returns `None`, then it's skipped, which is useful for substring -/// implementations that don't work for all inputs. -#[macro_export] -macro_rules! define_substring_forward_quickcheck { - ($fwd:expr) => { - #[cfg(not(miri))] - quickcheck::quickcheck! { - fn qc_fwd_prefix_is_substring(bs: alloc::vec::Vec<u8>) -> bool { - crate::tests::substring::prop::prefix_is_substring(&bs, $fwd) - } - - fn qc_fwd_suffix_is_substring(bs: alloc::vec::Vec<u8>) -> bool { - crate::tests::substring::prop::suffix_is_substring(&bs, $fwd) - } - - fn qc_fwd_matches_naive( - haystack: alloc::vec::Vec<u8>, - needle: alloc::vec::Vec<u8> - ) -> bool { - crate::tests::substring::prop::same_as_naive( - false, - &haystack, - &needle, - $fwd, - ) - } - } - }; -} - -/// $rev is a `impl FnMut(haystack, needle) -> Option<Option<usize>>`. When the -/// routine returns `None`, then it's skipped, which is useful for substring -/// implementations that don't work for all inputs. -#[macro_export] -macro_rules! define_substring_reverse_quickcheck { - ($rev:expr) => { - #[cfg(not(miri))] - quickcheck::quickcheck! { - fn qc_rev_prefix_is_substring(bs: alloc::vec::Vec<u8>) -> bool { - crate::tests::substring::prop::prefix_is_substring(&bs, $rev) - } - - fn qc_rev_suffix_is_substring(bs: alloc::vec::Vec<u8>) -> bool { - crate::tests::substring::prop::suffix_is_substring(&bs, $rev) - } - - fn qc_rev_matches_naive( - haystack: alloc::vec::Vec<u8>, - needle: alloc::vec::Vec<u8> - ) -> bool { - crate::tests::substring::prop::same_as_naive( - true, - &haystack, - &needle, - $rev, - ) - } - } - }; -} - -/// Check that every prefix of the given byte string is a substring. -pub(crate) fn prefix_is_substring( - bs: &[u8], - mut search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>>, -) -> bool { - for i in 0..bs.len().saturating_sub(1) { - let prefix = &bs[..i]; - let result = match search(bs, prefix) { - None => continue, - Some(result) => result, - }; - if !result.is_some() { - return false; - } - } - true -} - -/// Check that every suffix of the given byte string is a substring. -pub(crate) fn suffix_is_substring( - bs: &[u8], - mut search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>>, -) -> bool { - for i in 0..bs.len().saturating_sub(1) { - let suffix = &bs[i..]; - let result = match search(bs, suffix) { - None => continue, - Some(result) => result, - }; - if !result.is_some() { - return false; - } - } - true -} - -/// Check that naive substring search matches the result of the given search -/// algorithm. -pub(crate) fn same_as_naive( - reverse: bool, - haystack: &[u8], - needle: &[u8], - mut search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>>, -) -> bool { - let result = match search(haystack, needle) { - None => return true, - Some(result) => result, - }; - if reverse { - result == naive::rfind(haystack, needle) - } else { - result == naive::find(haystack, needle) - } -} |