1 #[cfg(miri)]
2 #[macro_export]
3 macro_rules! define_memchr_quickcheck {
4 ($($tt:tt)*) => {};
5 }
6
7 #[cfg(not(miri))]
8 #[macro_export]
9 macro_rules! define_memchr_quickcheck {
10 ($mod:ident) => {
11 define_memchr_quickcheck!($mod, new);
12 };
13 ($mod:ident, $cons:ident) => {
14 use alloc::vec::Vec;
15
16 use quickcheck::TestResult;
17
18 use crate::tests::memchr::{
19 naive,
20 prop::{double_ended_take, naive1_iter, naive2_iter, naive3_iter},
21 };
22
23 quickcheck::quickcheck! {
24 fn qc_memchr_matches_naive(n1: u8, corpus: Vec<u8>) -> TestResult {
25 let expected = naive::memchr(n1, &corpus);
26 let got = match $mod::One::$cons(n1) {
27 None => return TestResult::discard(),
28 Some(f) => f.find(&corpus),
29 };
30 TestResult::from_bool(expected == got)
31 }
32
33 fn qc_memrchr_matches_naive(n1: u8, corpus: Vec<u8>) -> TestResult {
34 let expected = naive::memrchr(n1, &corpus);
35 let got = match $mod::One::$cons(n1) {
36 None => return TestResult::discard(),
37 Some(f) => f.rfind(&corpus),
38 };
39 TestResult::from_bool(expected == got)
40 }
41
42 fn qc_memchr2_matches_naive(n1: u8, n2: u8, corpus: Vec<u8>) -> TestResult {
43 let expected = naive::memchr2(n1, n2, &corpus);
44 let got = match $mod::Two::$cons(n1, n2) {
45 None => return TestResult::discard(),
46 Some(f) => f.find(&corpus),
47 };
48 TestResult::from_bool(expected == got)
49 }
50
51 fn qc_memrchr2_matches_naive(n1: u8, n2: u8, corpus: Vec<u8>) -> TestResult {
52 let expected = naive::memrchr2(n1, n2, &corpus);
53 let got = match $mod::Two::$cons(n1, n2) {
54 None => return TestResult::discard(),
55 Some(f) => f.rfind(&corpus),
56 };
57 TestResult::from_bool(expected == got)
58 }
59
60 fn qc_memchr3_matches_naive(
61 n1: u8, n2: u8, n3: u8,
62 corpus: Vec<u8>
63 ) -> TestResult {
64 let expected = naive::memchr3(n1, n2, n3, &corpus);
65 let got = match $mod::Three::$cons(n1, n2, n3) {
66 None => return TestResult::discard(),
67 Some(f) => f.find(&corpus),
68 };
69 TestResult::from_bool(expected == got)
70 }
71
72 fn qc_memrchr3_matches_naive(
73 n1: u8, n2: u8, n3: u8,
74 corpus: Vec<u8>
75 ) -> TestResult {
76 let expected = naive::memrchr3(n1, n2, n3, &corpus);
77 let got = match $mod::Three::$cons(n1, n2, n3) {
78 None => return TestResult::discard(),
79 Some(f) => f.rfind(&corpus),
80 };
81 TestResult::from_bool(expected == got)
82 }
83
84 fn qc_memchr_double_ended_iter(
85 needle: u8, data: Vec<u8>, take_side: Vec<bool>
86 ) -> TestResult {
87 // make nonempty
88 let mut take_side = take_side;
89 if take_side.is_empty() { take_side.push(true) };
90
91 let finder = match $mod::One::$cons(needle) {
92 None => return TestResult::discard(),
93 Some(finder) => finder,
94 };
95 let iter = finder.iter(&data);
96 let got = double_ended_take(
97 iter,
98 take_side.iter().cycle().cloned(),
99 );
100 let expected = naive1_iter(needle, &data);
101
102 TestResult::from_bool(got.iter().cloned().eq(expected))
103 }
104
105 fn qc_memchr2_double_ended_iter(
106 needle1: u8, needle2: u8, data: Vec<u8>, take_side: Vec<bool>
107 ) -> TestResult {
108 // make nonempty
109 let mut take_side = take_side;
110 if take_side.is_empty() { take_side.push(true) };
111
112 let finder = match $mod::Two::$cons(needle1, needle2) {
113 None => return TestResult::discard(),
114 Some(finder) => finder,
115 };
116 let iter = finder.iter(&data);
117 let got = double_ended_take(
118 iter,
119 take_side.iter().cycle().cloned(),
120 );
121 let expected = naive2_iter(needle1, needle2, &data);
122
123 TestResult::from_bool(got.iter().cloned().eq(expected))
124 }
125
126 fn qc_memchr3_double_ended_iter(
127 needle1: u8, needle2: u8, needle3: u8,
128 data: Vec<u8>, take_side: Vec<bool>
129 ) -> TestResult {
130 // make nonempty
131 let mut take_side = take_side;
132 if take_side.is_empty() { take_side.push(true) };
133
134 let finder = match $mod::Three::$cons(needle1, needle2, needle3) {
135 None => return TestResult::discard(),
136 Some(finder) => finder,
137 };
138 let iter = finder.iter(&data);
139 let got = double_ended_take(
140 iter,
141 take_side.iter().cycle().cloned(),
142 );
143 let expected = naive3_iter(needle1, needle2, needle3, &data);
144
145 TestResult::from_bool(got.iter().cloned().eq(expected))
146 }
147
148 fn qc_memchr1_iter(data: Vec<u8>) -> TestResult {
149 let needle = 0;
150 let finder = match $mod::One::$cons(needle) {
151 None => return TestResult::discard(),
152 Some(finder) => finder,
153 };
154 let got = finder.iter(&data);
155 let expected = naive1_iter(needle, &data);
156 TestResult::from_bool(got.eq(expected))
157 }
158
159 fn qc_memchr1_rev_iter(data: Vec<u8>) -> TestResult {
160 let needle = 0;
161
162 let finder = match $mod::One::$cons(needle) {
163 None => return TestResult::discard(),
164 Some(finder) => finder,
165 };
166 let got = finder.iter(&data).rev();
167 let expected = naive1_iter(needle, &data).rev();
168 TestResult::from_bool(got.eq(expected))
169 }
170
171 fn qc_memchr2_iter(data: Vec<u8>) -> TestResult {
172 let needle1 = 0;
173 let needle2 = 1;
174
175 let finder = match $mod::Two::$cons(needle1, needle2) {
176 None => return TestResult::discard(),
177 Some(finder) => finder,
178 };
179 let got = finder.iter(&data);
180 let expected = naive2_iter(needle1, needle2, &data);
181 TestResult::from_bool(got.eq(expected))
182 }
183
184 fn qc_memchr2_rev_iter(data: Vec<u8>) -> TestResult {
185 let needle1 = 0;
186 let needle2 = 1;
187
188 let finder = match $mod::Two::$cons(needle1, needle2) {
189 None => return TestResult::discard(),
190 Some(finder) => finder,
191 };
192 let got = finder.iter(&data).rev();
193 let expected = naive2_iter(needle1, needle2, &data).rev();
194 TestResult::from_bool(got.eq(expected))
195 }
196
197 fn qc_memchr3_iter(data: Vec<u8>) -> TestResult {
198 let needle1 = 0;
199 let needle2 = 1;
200 let needle3 = 2;
201
202 let finder = match $mod::Three::$cons(needle1, needle2, needle3) {
203 None => return TestResult::discard(),
204 Some(finder) => finder,
205 };
206 let got = finder.iter(&data);
207 let expected = naive3_iter(needle1, needle2, needle3, &data);
208 TestResult::from_bool(got.eq(expected))
209 }
210
211 fn qc_memchr3_rev_iter(data: Vec<u8>) -> TestResult {
212 let needle1 = 0;
213 let needle2 = 1;
214 let needle3 = 2;
215
216 let finder = match $mod::Three::$cons(needle1, needle2, needle3) {
217 None => return TestResult::discard(),
218 Some(finder) => finder,
219 };
220 let got = finder.iter(&data).rev();
221 let expected = naive3_iter(needle1, needle2, needle3, &data).rev();
222 TestResult::from_bool(got.eq(expected))
223 }
224
225 fn qc_memchr1_iter_size_hint(data: Vec<u8>) -> TestResult {
226 // test that the size hint is within reasonable bounds
227 let needle = 0;
228 let finder = match $mod::One::$cons(needle) {
229 None => return TestResult::discard(),
230 Some(finder) => finder,
231 };
232 let mut iter = finder.iter(&data);
233 let mut real_count = data
234 .iter()
235 .filter(|&&elt| elt == needle)
236 .count();
237
238 while let Some(index) = iter.next() {
239 real_count -= 1;
240 let (lower, upper) = iter.size_hint();
241 assert!(lower <= real_count);
242 assert!(upper.unwrap() >= real_count);
243 assert!(upper.unwrap() <= data.len() - index);
244 }
245 TestResult::passed()
246 }
247 }
248 };
249 }
250
251 // take items from a DEI, taking front for each true and back for each false.
252 // Return a vector with the concatenation of the fronts and the reverse of the
253 // backs.
254 #[cfg(not(miri))]
double_ended_take<I, J>( mut iter: I, take_side: J, ) -> alloc::vec::Vec<I::Item> where I: DoubleEndedIterator, J: Iterator<Item = bool>,255 pub(crate) fn double_ended_take<I, J>(
256 mut iter: I,
257 take_side: J,
258 ) -> alloc::vec::Vec<I::Item>
259 where
260 I: DoubleEndedIterator,
261 J: Iterator<Item = bool>,
262 {
263 let mut found_front = alloc::vec![];
264 let mut found_back = alloc::vec![];
265
266 for take_front in take_side {
267 if take_front {
268 if let Some(pos) = iter.next() {
269 found_front.push(pos);
270 } else {
271 break;
272 }
273 } else {
274 if let Some(pos) = iter.next_back() {
275 found_back.push(pos);
276 } else {
277 break;
278 }
279 };
280 }
281
282 let mut all_found = found_front;
283 all_found.extend(found_back.into_iter().rev());
284 all_found
285 }
286
287 // return an iterator of the 0-based indices of haystack that match the needle
288 #[cfg(not(miri))]
naive1_iter<'a>( n1: u8, haystack: &'a [u8], ) -> impl DoubleEndedIterator<Item = usize> + 'a289 pub(crate) fn naive1_iter<'a>(
290 n1: u8,
291 haystack: &'a [u8],
292 ) -> impl DoubleEndedIterator<Item = usize> + 'a {
293 haystack.iter().enumerate().filter(move |&(_, &b)| b == n1).map(|t| t.0)
294 }
295
296 #[cfg(not(miri))]
naive2_iter<'a>( n1: u8, n2: u8, haystack: &'a [u8], ) -> impl DoubleEndedIterator<Item = usize> + 'a297 pub(crate) fn naive2_iter<'a>(
298 n1: u8,
299 n2: u8,
300 haystack: &'a [u8],
301 ) -> impl DoubleEndedIterator<Item = usize> + 'a {
302 haystack
303 .iter()
304 .enumerate()
305 .filter(move |&(_, &b)| b == n1 || b == n2)
306 .map(|t| t.0)
307 }
308
309 #[cfg(not(miri))]
naive3_iter<'a>( n1: u8, n2: u8, n3: u8, haystack: &'a [u8], ) -> impl DoubleEndedIterator<Item = usize> + 'a310 pub(crate) fn naive3_iter<'a>(
311 n1: u8,
312 n2: u8,
313 n3: u8,
314 haystack: &'a [u8],
315 ) -> impl DoubleEndedIterator<Item = usize> + 'a {
316 haystack
317 .iter()
318 .enumerate()
319 .filter(move |&(_, &b)| b == n1 || b == n2 || b == n3)
320 .map(|t| t.0)
321 }
322