1/*!
2This module defines a few quickcheck properties for substring search.
3
4It also provides a forward and reverse macro for conveniently defining
5quickcheck tests that run these properties over any substring search
6implementation.
7*/
8
9use 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]
15macro_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]
46macro_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.
74pub(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.
92pub(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.
111pub(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