| 1 |
/*! |
| 2 |
This module defines a few quickcheck properties for substring search. |
| 3 |
|
| 4 |
It also provides a forward and reverse macro for conveniently defining |
| 5 |
quickcheck tests that run these properties over any substring search |
| 6 |
implementation. |
| 7 |
*/ |
| 8 |
|
| 9 |
use crate::tests::substring::naive; |
| 10 |
|
| 11 |
/// $fwd is a `impl FnMut(haystack, needle) -> Option<Option<usize>>`. When the |
| 12 |
/// routine returns `None`, then it's skipped, which is useful for substring |
| 13 |
/// implementations that don't work for all inputs. |
| 14 |
#[macro_export] |
| 15 |
macro_rules! define_substring_forward_quickcheck { |
| 16 |
($fwd:expr) => { |
| 17 |
#[cfg(not(miri))] |
| 18 |
quickcheck::quickcheck! { |
| 19 |
fn qc_fwd_prefix_is_substring(bs: alloc::vec::Vec<u8>) -> bool { |
| 20 |
crate::tests::substring::prop::prefix_is_substring(&bs, $fwd) |
| 21 |
} |
| 22 |
|
| 23 |
fn qc_fwd_suffix_is_substring(bs: alloc::vec::Vec<u8>) -> bool { |
| 24 |
crate::tests::substring::prop::suffix_is_substring(&bs, $fwd) |
| 25 |
} |
| 26 |
|
| 27 |
fn qc_fwd_matches_naive( |
| 28 |
haystack: alloc::vec::Vec<u8>, |
| 29 |
needle: alloc::vec::Vec<u8> |
| 30 |
) -> bool { |
| 31 |
crate::tests::substring::prop::same_as_naive( |
| 32 |
false, |
| 33 |
&haystack, |
| 34 |
&needle, |
| 35 |
$fwd, |
| 36 |
) |
| 37 |
} |
| 38 |
} |
| 39 |
}; |
| 40 |
} |
| 41 |
|
| 42 |
/// $rev is a `impl FnMut(haystack, needle) -> Option<Option<usize>>`. When the |
| 43 |
/// routine returns `None`, then it's skipped, which is useful for substring |
| 44 |
/// implementations that don't work for all inputs. |
| 45 |
#[macro_export] |
| 46 |
macro_rules! define_substring_reverse_quickcheck { |
| 47 |
($rev:expr) => { |
| 48 |
#[cfg(not(miri))] |
| 49 |
quickcheck::quickcheck! { |
| 50 |
fn qc_rev_prefix_is_substring(bs: alloc::vec::Vec<u8>) -> bool { |
| 51 |
crate::tests::substring::prop::prefix_is_substring(&bs, $rev) |
| 52 |
} |
| 53 |
|
| 54 |
fn qc_rev_suffix_is_substring(bs: alloc::vec::Vec<u8>) -> bool { |
| 55 |
crate::tests::substring::prop::suffix_is_substring(&bs, $rev) |
| 56 |
} |
| 57 |
|
| 58 |
fn qc_rev_matches_naive( |
| 59 |
haystack: alloc::vec::Vec<u8>, |
| 60 |
needle: alloc::vec::Vec<u8> |
| 61 |
) -> bool { |
| 62 |
crate::tests::substring::prop::same_as_naive( |
| 63 |
true, |
| 64 |
&haystack, |
| 65 |
&needle, |
| 66 |
$rev, |
| 67 |
) |
| 68 |
} |
| 69 |
} |
| 70 |
}; |
| 71 |
} |
| 72 |
|
| 73 |
/// Check that every prefix of the given byte string is a substring. |
| 74 |
pub(crate) fn prefix_is_substring( |
| 75 |
bs: &[u8], |
| 76 |
mut search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>>, |
| 77 |
) -> bool { |
| 78 |
for i in 0..bs.len().saturating_sub(1) { |
| 79 |
let prefix = &bs[..i]; |
| 80 |
let result = match search(bs, prefix) { |
| 81 |
None => continue, |
| 82 |
Some(result) => result, |
| 83 |
}; |
| 84 |
if !result.is_some() { |
| 85 |
return false; |
| 86 |
} |
| 87 |
} |
| 88 |
true |
| 89 |
} |
| 90 |
|
| 91 |
/// Check that every suffix of the given byte string is a substring. |
| 92 |
pub(crate) fn suffix_is_substring( |
| 93 |
bs: &[u8], |
| 94 |
mut search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>>, |
| 95 |
) -> bool { |
| 96 |
for i in 0..bs.len().saturating_sub(1) { |
| 97 |
let suffix = &bs[i..]; |
| 98 |
let result = match search(bs, suffix) { |
| 99 |
None => continue, |
| 100 |
Some(result) => result, |
| 101 |
}; |
| 102 |
if !result.is_some() { |
| 103 |
return false; |
| 104 |
} |
| 105 |
} |
| 106 |
true |
| 107 |
} |
| 108 |
|
| 109 |
/// Check that naive substring search matches the result of the given search |
| 110 |
/// algorithm. |
| 111 |
pub(crate) fn same_as_naive( |
| 112 |
reverse: bool, |
| 113 |
haystack: &[u8], |
| 114 |
needle: &[u8], |
| 115 |
mut search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>>, |
| 116 |
) -> bool { |
| 117 |
let result = match search(haystack, needle) { |
| 118 |
None => return true, |
| 119 |
Some(result) => result, |
| 120 |
}; |
| 121 |
if reverse { |
| 122 |
result == naive::rfind(haystack, needle) |
| 123 |
} else { |
| 124 |
result == naive::find(haystack, needle) |
| 125 |
} |
| 126 |
} |