1 use search::twoway::TwoWay;
2
3 /// Each test is a (needle, haystack, expected_fwd, expected_rev) tuple.
4 type SearchTest = (&'static str, &'static str, Option<usize>, Option<usize>);
5
6 const SEARCH_TESTS: &'static [SearchTest] = &[
7 ("", "", Some(0), Some(0)),
8 ("", "a", Some(0), Some(1)),
9 ("", "ab", Some(0), Some(2)),
10 ("", "abc", Some(0), Some(3)),
11 ("a", "", None, None),
12 ("a", "a", Some(0), Some(0)),
13 ("a", "aa", Some(0), Some(1)),
14 ("a", "ba", Some(1), Some(1)),
15 ("a", "bba", Some(2), Some(2)),
16 ("a", "bbba", Some(3), Some(3)),
17 ("a", "bbbab", Some(3), Some(3)),
18 ("a", "bbbabb", Some(3), Some(3)),
19 ("a", "bbbabbb", Some(3), Some(3)),
20 ("a", "bbbbbb", None, None),
21 ("ab", "", None, None),
22 ("ab", "a", None, None),
23 ("ab", "b", None, None),
24 ("ab", "ab", Some(0), Some(0)),
25 ("ab", "aab", Some(1), Some(1)),
26 ("ab", "aaab", Some(2), Some(2)),
27 ("ab", "abaab", Some(0), Some(3)),
28 ("ab", "baaab", Some(3), Some(3)),
29 ("ab", "acb", None, None),
30 ("ab", "abba", Some(0), Some(0)),
31 ("abc", "ab", None, None),
32 ("abc", "abc", Some(0), Some(0)),
33 ("abc", "abcz", Some(0), Some(0)),
34 ("abc", "abczz", Some(0), Some(0)),
35 ("abc", "zabc", Some(1), Some(1)),
36 ("abc", "zzabc", Some(2), Some(2)),
37 ("abc", "azbc", None, None),
38 ("abc", "abzc", None, None),
39 ("abczdef", "abczdefzzzzzzzzzzzzzzzzzzzz", Some(0), Some(0)),
40 ("abczdef", "zzzzzzzzzzzzzzzzzzzzabczdef", Some(20), Some(20)),
41 // Failures caught by quickcheck.
42 ("\u{0}\u{15}", "\u{0}\u{15}\u{15}\u{0}", Some(0), Some(0)),
43 ("\u{0}\u{1e}", "\u{1e}\u{0}", None, None),
44 ];
45
46 #[test]
unit_twoway_fwd()47 fn unit_twoway_fwd() {
48 run_search_tests_fwd("TwoWay", |n, h| TwoWay::forward(n).find(h));
49 }
50
51 #[test]
unit_twoway_rev()52 fn unit_twoway_rev() {
53 run_search_tests_rev("TwoWay", |n, h| TwoWay::reverse(n).rfind(h));
54 }
55
56 /// Run the substring search tests. `name` should be the type of searcher used,
57 /// for diagnostics. `search` should be a closure that accepts a needle and a
58 /// haystack and returns the starting position of the first occurrence of
59 /// needle in the haystack, or `None` if one doesn't exist.
run_search_tests_fwd( name: &str, mut search: impl FnMut(&[u8], &[u8]) -> Option<usize>, )60 fn run_search_tests_fwd(
61 name: &str,
62 mut search: impl FnMut(&[u8], &[u8]) -> Option<usize>,
63 ) {
64 for &(needle, haystack, expected_fwd, _) in SEARCH_TESTS {
65 let (n, h) = (needle.as_bytes(), haystack.as_bytes());
66 assert_eq!(
67 expected_fwd,
68 search(n, h),
69 "{}: needle: {:?}, haystack: {:?}, expected: {:?}",
70 name,
71 n,
72 h,
73 expected_fwd
74 );
75 }
76 }
77
78 /// Run the substring search tests. `name` should be the type of searcher used,
79 /// for diagnostics. `search` should be a closure that accepts a needle and a
80 /// haystack and returns the starting position of the last occurrence of
81 /// needle in the haystack, or `None` if one doesn't exist.
run_search_tests_rev( name: &str, mut search: impl FnMut(&[u8], &[u8]) -> Option<usize>, )82 fn run_search_tests_rev(
83 name: &str,
84 mut search: impl FnMut(&[u8], &[u8]) -> Option<usize>,
85 ) {
86 for &(needle, haystack, _, expected_rev) in SEARCH_TESTS {
87 let (n, h) = (needle.as_bytes(), haystack.as_bytes());
88 assert_eq!(
89 expected_rev,
90 search(n, h),
91 "{}: needle: {:?}, haystack: {:?}, expected: {:?}",
92 name,
93 n,
94 h,
95 expected_rev
96 );
97 }
98 }
99
100 quickcheck! {
101 fn qc_twoway_fwd_prefix_is_substring(bs: Vec<u8>) -> bool {
102 prop_prefix_is_substring(false, &bs, |n, h| TwoWay::forward(n).find(h))
103 }
104
105 fn qc_twoway_fwd_suffix_is_substring(bs: Vec<u8>) -> bool {
106 prop_suffix_is_substring(false, &bs, |n, h| TwoWay::forward(n).find(h))
107 }
108
109 fn qc_twoway_rev_prefix_is_substring(bs: Vec<u8>) -> bool {
110 prop_prefix_is_substring(true, &bs, |n, h| TwoWay::reverse(n).rfind(h))
111 }
112
113 fn qc_twoway_rev_suffix_is_substring(bs: Vec<u8>) -> bool {
114 prop_suffix_is_substring(true, &bs, |n, h| TwoWay::reverse(n).rfind(h))
115 }
116
117 fn qc_twoway_fwd_matches_naive(
118 needle: Vec<u8>,
119 haystack: Vec<u8>
120 ) -> bool {
121 prop_matches_naive(
122 false,
123 &needle,
124 &haystack,
125 |n, h| TwoWay::forward(n).find(h),
126 )
127 }
128
129 fn qc_twoway_rev_matches_naive(
130 needle: Vec<u8>,
131 haystack: Vec<u8>
132 ) -> bool {
133 prop_matches_naive(
134 true,
135 &needle,
136 &haystack,
137 |n, h| TwoWay::reverse(n).rfind(h),
138 )
139 }
140 }
141
142 /// Check that every prefix of the given byte string is a substring.
prop_prefix_is_substring( reverse: bool, bs: &[u8], mut search: impl FnMut(&[u8], &[u8]) -> Option<usize>, ) -> bool143 fn prop_prefix_is_substring(
144 reverse: bool,
145 bs: &[u8],
146 mut search: impl FnMut(&[u8], &[u8]) -> Option<usize>,
147 ) -> bool {
148 if bs.is_empty() {
149 return true;
150 }
151 for i in 0..(bs.len() - 1) {
152 let prefix = &bs[..i];
153 if reverse {
154 assert_eq!(naive_rfind(prefix, bs), search(prefix, bs));
155 } else {
156 assert_eq!(naive_find(prefix, bs), search(prefix, bs));
157 }
158 }
159 true
160 }
161
162 /// Check that every suffix of the given byte string is a substring.
prop_suffix_is_substring( reverse: bool, bs: &[u8], mut search: impl FnMut(&[u8], &[u8]) -> Option<usize>, ) -> bool163 fn prop_suffix_is_substring(
164 reverse: bool,
165 bs: &[u8],
166 mut search: impl FnMut(&[u8], &[u8]) -> Option<usize>,
167 ) -> bool {
168 if bs.is_empty() {
169 return true;
170 }
171 for i in 0..(bs.len() - 1) {
172 let suffix = &bs[i..];
173 if reverse {
174 assert_eq!(naive_rfind(suffix, bs), search(suffix, bs));
175 } else {
176 assert_eq!(naive_find(suffix, bs), search(suffix, bs));
177 }
178 }
179 true
180 }
181
182 /// Check that naive substring search matches the result of the given search
183 /// algorithm.
prop_matches_naive( reverse: bool, needle: &[u8], haystack: &[u8], mut search: impl FnMut(&[u8], &[u8]) -> Option<usize>, ) -> bool184 fn prop_matches_naive(
185 reverse: bool,
186 needle: &[u8],
187 haystack: &[u8],
188 mut search: impl FnMut(&[u8], &[u8]) -> Option<usize>,
189 ) -> bool {
190 if reverse {
191 naive_rfind(needle, haystack) == search(needle, haystack)
192 } else {
193 naive_find(needle, haystack) == search(needle, haystack)
194 }
195 }
196
197 /// Naively search forwards for the given needle in the given haystack.
naive_find(needle: &[u8], haystack: &[u8]) -> Option<usize>198 fn naive_find(needle: &[u8], haystack: &[u8]) -> Option<usize> {
199 if needle.is_empty() {
200 return Some(0);
201 } else if haystack.len() < needle.len() {
202 return None;
203 }
204 for i in 0..(haystack.len() - needle.len() + 1) {
205 if needle == &haystack[i..i + needle.len()] {
206 return Some(i);
207 }
208 }
209 None
210 }
211
212 /// Naively search in reverse for the given needle in the given haystack.
naive_rfind(needle: &[u8], haystack: &[u8]) -> Option<usize>213 fn naive_rfind(needle: &[u8], haystack: &[u8]) -> Option<usize> {
214 if needle.is_empty() {
215 return Some(haystack.len());
216 } else if haystack.len() < needle.len() {
217 return None;
218 }
219 for i in (0..(haystack.len() - needle.len() + 1)).rev() {
220 if needle == &haystack[i..i + needle.len()] {
221 return Some(i);
222 }
223 }
224 None
225 }
226