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.
prefix_is_substring( bs: &[u8], mut search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>>, ) -> bool74 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.
suffix_is_substring( bs: &[u8], mut search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>>, ) -> bool92 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.
same_as_naive( reverse: bool, haystack: &[u8], needle: &[u8], mut search: impl FnMut(&[u8], &[u8]) -> Option<Option<usize>>, ) -> bool111 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 }
127