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))] |

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))] |

289 | 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))] |

297 | 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))] |

310 | 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 |