1 use std::collections::HashMap;
2 use std::io;
3 use std::usize;
4
5 use {AhoCorasickBuilder, Match, MatchKind};
6
7 /// A description of a single test against an Aho-Corasick automaton.
8 ///
9 /// A single test may not necessarily pass on every configuration of an
10 /// Aho-Corasick automaton. The tests are categorized and grouped appropriately
11 /// below.
12 #[derive(Clone, Debug, Eq, PartialEq)]
13 struct SearchTest {
14 /// The name of this test, for debugging.
15 name: &'static str,
16 /// The patterns to search for.
17 patterns: &'static [&'static str],
18 /// The text to search.
19 haystack: &'static str,
20 /// Each match is a triple of (pattern_index, start, end), where
21 /// pattern_index is an index into `patterns` and `start`/`end` are indices
22 /// into `haystack`.
23 matches: &'static [(usize, usize, usize)],
24 }
25
26 /// Short-hand constructor for SearchTest. We use it a lot below.
27 macro_rules! t {
28 ($name:ident, $patterns:expr, $haystack:expr, $matches:expr) => {
29 SearchTest {
30 name: stringify!($name),
31 patterns: $patterns,
32 haystack: $haystack,
33 matches: $matches,
34 }
35 };
36 }
37
38 /// A collection of test groups.
39 type TestCollection = &'static [&'static [SearchTest]];
40
41 // Define several collections corresponding to the different type of match
42 // semantics supported by Aho-Corasick. These collections have some overlap,
43 // but each collection should have some tests that no other collection has.
44
45 /// Tests for Aho-Corasick's standard non-overlapping match semantics.
46 const AC_STANDARD_NON_OVERLAPPING: TestCollection =
47 &[BASICS, NON_OVERLAPPING, STANDARD, REGRESSION];
48
49 /// Tests for Aho-Corasick's anchored standard non-overlapping match semantics.
50 const AC_STANDARD_ANCHORED_NON_OVERLAPPING: TestCollection =
51 &[ANCHORED_BASICS, ANCHORED_NON_OVERLAPPING, STANDARD_ANCHORED];
52
53 /// Tests for Aho-Corasick's standard overlapping match semantics.
54 const AC_STANDARD_OVERLAPPING: TestCollection =
55 &[BASICS, OVERLAPPING, REGRESSION];
56
57 /// Tests for Aho-Corasick's anchored standard overlapping match semantics.
58 const AC_STANDARD_ANCHORED_OVERLAPPING: TestCollection =
59 &[ANCHORED_BASICS, ANCHORED_OVERLAPPING];
60
61 /// Tests for Aho-Corasick's leftmost-first match semantics.
62 const AC_LEFTMOST_FIRST: TestCollection =
63 &[BASICS, NON_OVERLAPPING, LEFTMOST, LEFTMOST_FIRST, REGRESSION];
64
65 /// Tests for Aho-Corasick's anchored leftmost-first match semantics.
66 const AC_LEFTMOST_FIRST_ANCHORED: TestCollection = &[
67 ANCHORED_BASICS,
68 ANCHORED_NON_OVERLAPPING,
69 ANCHORED_LEFTMOST,
70 ANCHORED_LEFTMOST_FIRST,
71 ];
72
73 /// Tests for Aho-Corasick's leftmost-longest match semantics.
74 const AC_LEFTMOST_LONGEST: TestCollection =
75 &[BASICS, NON_OVERLAPPING, LEFTMOST, LEFTMOST_LONGEST, REGRESSION];
76
77 /// Tests for Aho-Corasick's anchored leftmost-longest match semantics.
78 const AC_LEFTMOST_LONGEST_ANCHORED: TestCollection = &[
79 ANCHORED_BASICS,
80 ANCHORED_NON_OVERLAPPING,
81 ANCHORED_LEFTMOST,
82 ANCHORED_LEFTMOST_LONGEST,
83 ];
84
85 // Now define the individual tests that make up the collections above.
86
87 /// A collection of tests for the Aho-Corasick algorithm that should always be
88 /// true regardless of match semantics. That is, all combinations of
89 /// leftmost-{shortest, first, longest} x {overlapping, non-overlapping}
90 /// should produce the same answer.
91 const BASICS: &'static [SearchTest] = &[
92 t!(basic000, &[], "", &[]),
93 t!(basic001, &["a"], "", &[]),
94 t!(basic010, &["a"], "a", &[(0, 0, 1)]),
95 t!(basic020, &["a"], "aa", &[(0, 0, 1), (0, 1, 2)]),
96 t!(basic030, &["a"], "aaa", &[(0, 0, 1), (0, 1, 2), (0, 2, 3)]),
97 t!(basic040, &["a"], "aba", &[(0, 0, 1), (0, 2, 3)]),
98 t!(basic050, &["a"], "bba", &[(0, 2, 3)]),
99 t!(basic060, &["a"], "bbb", &[]),
100 t!(basic070, &["a"], "bababbbba", &[(0, 1, 2), (0, 3, 4), (0, 8, 9)]),
101 t!(basic100, &["aa"], "", &[]),
102 t!(basic110, &["aa"], "aa", &[(0, 0, 2)]),
103 t!(basic120, &["aa"], "aabbaa", &[(0, 0, 2), (0, 4, 6)]),
104 t!(basic130, &["aa"], "abbab", &[]),
105 t!(basic140, &["aa"], "abbabaa", &[(0, 5, 7)]),
106 t!(basic200, &["abc"], "abc", &[(0, 0, 3)]),
107 t!(basic210, &["abc"], "zazabzabcz", &[(0, 6, 9)]),
108 t!(basic220, &["abc"], "zazabczabcz", &[(0, 3, 6), (0, 7, 10)]),
109 t!(basic300, &["a", "b"], "", &[]),
110 t!(basic310, &["a", "b"], "z", &[]),
111 t!(basic320, &["a", "b"], "b", &[(1, 0, 1)]),
112 t!(basic330, &["a", "b"], "a", &[(0, 0, 1)]),
113 t!(
114 basic340,
115 &["a", "b"],
116 "abba",
117 &[(0, 0, 1), (1, 1, 2), (1, 2, 3), (0, 3, 4),]
118 ),
119 t!(
120 basic350,
121 &["b", "a"],
122 "abba",
123 &[(1, 0, 1), (0, 1, 2), (0, 2, 3), (1, 3, 4),]
124 ),
125 t!(basic360, &["abc", "bc"], "xbc", &[(1, 1, 3),]),
126 t!(basic400, &["foo", "bar"], "", &[]),
127 t!(basic410, &["foo", "bar"], "foobar", &[(0, 0, 3), (1, 3, 6),]),
128 t!(basic420, &["foo", "bar"], "barfoo", &[(1, 0, 3), (0, 3, 6),]),
129 t!(basic430, &["foo", "bar"], "foofoo", &[(0, 0, 3), (0, 3, 6),]),
130 t!(basic440, &["foo", "bar"], "barbar", &[(1, 0, 3), (1, 3, 6),]),
131 t!(basic450, &["foo", "bar"], "bafofoo", &[(0, 4, 7),]),
132 t!(basic460, &["bar", "foo"], "bafofoo", &[(1, 4, 7),]),
133 t!(basic470, &["foo", "bar"], "fobabar", &[(1, 4, 7),]),
134 t!(basic480, &["bar", "foo"], "fobabar", &[(0, 4, 7),]),
135 t!(basic600, &[""], "", &[(0, 0, 0)]),
136 t!(basic610, &[""], "a", &[(0, 0, 0), (0, 1, 1)]),
137 t!(basic620, &[""], "abc", &[(0, 0, 0), (0, 1, 1), (0, 2, 2), (0, 3, 3)]),
138 t!(basic700, &["yabcdef", "abcdezghi"], "yabcdefghi", &[(0, 0, 7),]),
139 t!(basic710, &["yabcdef", "abcdezghi"], "yabcdezghi", &[(1, 1, 10),]),
140 t!(
141 basic720,
142 &["yabcdef", "bcdeyabc", "abcdezghi"],
143 "yabcdezghi",
144 &[(2, 1, 10),]
145 ),
146 ];
147
148 /// A collection of *anchored* tests for the Aho-Corasick algorithm that should
149 /// always be true regardless of match semantics. That is, all combinations of
150 /// leftmost-{shortest, first, longest} x {overlapping, non-overlapping} should
151 /// produce the same answer.
152 const ANCHORED_BASICS: &'static [SearchTest] = &[
153 t!(abasic000, &[], "", &[]),
154 t!(abasic010, &[""], "", &[(0, 0, 0)]),
155 t!(abasic020, &[""], "a", &[(0, 0, 0)]),
156 t!(abasic030, &[""], "abc", &[(0, 0, 0)]),
157 t!(abasic100, &["a"], "a", &[(0, 0, 1)]),
158 t!(abasic110, &["a"], "aa", &[(0, 0, 1)]),
159 t!(abasic120, &["a", "b"], "ab", &[(0, 0, 1)]),
160 t!(abasic130, &["a", "b"], "ba", &[(1, 0, 1)]),
161 t!(abasic140, &["foo", "foofoo"], "foo", &[(0, 0, 3)]),
162 t!(abasic150, &["foofoo", "foo"], "foo", &[(1, 0, 3)]),
163 ];
164
165 /// Tests for non-overlapping standard match semantics.
166 ///
167 /// These tests generally shouldn't pass for leftmost-{first,longest}, although
168 /// some do in order to write clearer tests. For example, standard000 will
169 /// pass with leftmost-first semantics, but standard010 will not. We write
170 /// both to emphasize how the match semantics work.
171 const STANDARD: &'static [SearchTest] = &[
172 t!(standard000, &["ab", "abcd"], "abcd", &[(0, 0, 2)]),
173 t!(standard010, &["abcd", "ab"], "abcd", &[(1, 0, 2)]),
174 t!(standard020, &["abcd", "ab", "abc"], "abcd", &[(1, 0, 2)]),
175 t!(standard030, &["abcd", "abc", "ab"], "abcd", &[(2, 0, 2)]),
176 t!(standard040, &["a", ""], "a", &[(1, 0, 0), (1, 1, 1)]),
177 t!(
178 standard400,
179 &["abcd", "bcd", "cd", "b"],
180 "abcd",
181 &[(3, 1, 2), (2, 2, 4),]
182 ),
183 t!(standard410, &["", "a"], "a", &[(0, 0, 0), (0, 1, 1),]),
184 t!(standard420, &["", "a"], "aa", &[(0, 0, 0), (0, 1, 1), (0, 2, 2),]),
185 t!(standard430, &["", "a", ""], "a", &[(0, 0, 0), (0, 1, 1),]),
186 t!(standard440, &["a", "", ""], "a", &[(1, 0, 0), (1, 1, 1),]),
187 t!(standard450, &["", "", "a"], "a", &[(0, 0, 0), (0, 1, 1),]),
188 ];
189
190 /// Like STANDARD, but for anchored searches.
191 const STANDARD_ANCHORED: &'static [SearchTest] = &[
192 t!(astandard000, &["ab", "abcd"], "abcd", &[(0, 0, 2)]),
193 t!(astandard010, &["abcd", "ab"], "abcd", &[(1, 0, 2)]),
194 t!(astandard020, &["abcd", "ab", "abc"], "abcd", &[(1, 0, 2)]),
195 t!(astandard030, &["abcd", "abc", "ab"], "abcd", &[(2, 0, 2)]),
196 t!(astandard040, &["a", ""], "a", &[(1, 0, 0)]),
197 t!(astandard050, &["abcd", "bcd", "cd", "b"], "abcd", &[(0, 0, 4)]),
198 t!(astandard410, &["", "a"], "a", &[(0, 0, 0)]),
199 t!(astandard420, &["", "a"], "aa", &[(0, 0, 0)]),
200 t!(astandard430, &["", "a", ""], "a", &[(0, 0, 0)]),
201 t!(astandard440, &["a", "", ""], "a", &[(1, 0, 0)]),
202 t!(astandard450, &["", "", "a"], "a", &[(0, 0, 0)]),
203 ];
204
205 /// Tests for non-overlapping leftmost match semantics. These should pass for
206 /// both leftmost-first and leftmost-longest match kinds. Stated differently,
207 /// among ambiguous matches, the longest match and the match that appeared
208 /// first when constructing the automaton should always be the same.
209 const LEFTMOST: &'static [SearchTest] = &[
210 t!(leftmost000, &["ab", "ab"], "abcd", &[(0, 0, 2)]),
211 t!(leftmost010, &["a", ""], "a", &[(0, 0, 1), (1, 1, 1)]),
212 t!(leftmost020, &["", ""], "a", &[(0, 0, 0), (0, 1, 1)]),
213 t!(leftmost030, &["a", "ab"], "aa", &[(0, 0, 1), (0, 1, 2)]),
214 t!(leftmost031, &["ab", "a"], "aa", &[(1, 0, 1), (1, 1, 2)]),
215 t!(leftmost032, &["ab", "a"], "xayabbbz", &[(1, 1, 2), (0, 3, 5)]),
216 t!(leftmost300, &["abcd", "bce", "b"], "abce", &[(1, 1, 4)]),
217 t!(leftmost310, &["abcd", "ce", "bc"], "abce", &[(2, 1, 3)]),
218 t!(leftmost320, &["abcd", "bce", "ce", "b"], "abce", &[(1, 1, 4)]),
219 t!(leftmost330, &["abcd", "bce", "cz", "bc"], "abcz", &[(3, 1, 3)]),
220 t!(leftmost340, &["bce", "cz", "bc"], "bcz", &[(2, 0, 2)]),
221 t!(leftmost350, &["abc", "bd", "ab"], "abd", &[(2, 0, 2)]),
222 t!(
223 leftmost360,
224 &["abcdefghi", "hz", "abcdefgh"],
225 "abcdefghz",
226 &[(2, 0, 8),]
227 ),
228 t!(
229 leftmost370,
230 &["abcdefghi", "cde", "hz", "abcdefgh"],
231 "abcdefghz",
232 &[(3, 0, 8),]
233 ),
234 t!(
235 leftmost380,
236 &["abcdefghi", "hz", "abcdefgh", "a"],
237 "abcdefghz",
238 &[(2, 0, 8),]
239 ),
240 t!(
241 leftmost390,
242 &["b", "abcdefghi", "hz", "abcdefgh"],
243 "abcdefghz",
244 &[(3, 0, 8),]
245 ),
246 t!(
247 leftmost400,
248 &["h", "abcdefghi", "hz", "abcdefgh"],
249 "abcdefghz",
250 &[(3, 0, 8),]
251 ),
252 t!(
253 leftmost410,
254 &["z", "abcdefghi", "hz", "abcdefgh"],
255 "abcdefghz",
256 &[(3, 0, 8), (0, 8, 9),]
257 ),
258 ];
259
260 /// Like LEFTMOST, but for anchored searches.
261 const ANCHORED_LEFTMOST: &'static [SearchTest] = &[
262 t!(aleftmost000, &["ab", "ab"], "abcd", &[(0, 0, 2)]),
263 t!(aleftmost010, &["a", ""], "a", &[(0, 0, 1)]),
264 t!(aleftmost020, &["", ""], "a", &[(0, 0, 0)]),
265 t!(aleftmost030, &["a", "ab"], "aa", &[(0, 0, 1)]),
266 t!(aleftmost031, &["ab", "a"], "aa", &[(1, 0, 1)]),
267 t!(aleftmost032, &["ab", "a"], "xayabbbz", &[]),
268 t!(aleftmost300, &["abcd", "bce", "b"], "abce", &[]),
269 t!(aleftmost310, &["abcd", "ce", "bc"], "abce", &[]),
270 t!(aleftmost320, &["abcd", "bce", "ce", "b"], "abce", &[]),
271 t!(aleftmost330, &["abcd", "bce", "cz", "bc"], "abcz", &[]),
272 t!(aleftmost340, &["bce", "cz", "bc"], "bcz", &[(2, 0, 2)]),
273 t!(aleftmost350, &["abc", "bd", "ab"], "abd", &[(2, 0, 2)]),
274 t!(
275 aleftmost360,
276 &["abcdefghi", "hz", "abcdefgh"],
277 "abcdefghz",
278 &[(2, 0, 8),]
279 ),
280 t!(
281 aleftmost370,
282 &["abcdefghi", "cde", "hz", "abcdefgh"],
283 "abcdefghz",
284 &[(3, 0, 8),]
285 ),
286 t!(
287 aleftmost380,
288 &["abcdefghi", "hz", "abcdefgh", "a"],
289 "abcdefghz",
290 &[(2, 0, 8),]
291 ),
292 t!(
293 aleftmost390,
294 &["b", "abcdefghi", "hz", "abcdefgh"],
295 "abcdefghz",
296 &[(3, 0, 8),]
297 ),
298 t!(
299 aleftmost400,
300 &["h", "abcdefghi", "hz", "abcdefgh"],
301 "abcdefghz",
302 &[(3, 0, 8),]
303 ),
304 t!(
305 aleftmost410,
306 &["z", "abcdefghi", "hz", "abcdefgh"],
307 "abcdefghz",
308 &[(3, 0, 8)]
309 ),
310 ];
311
312 /// Tests for non-overlapping leftmost-first match semantics. These tests
313 /// should generally be specific to leftmost-first, which means they should
314 /// generally fail under leftmost-longest semantics.
315 const LEFTMOST_FIRST: &'static [SearchTest] = &[
316 t!(leftfirst000, &["ab", "abcd"], "abcd", &[(0, 0, 2)]),
317 t!(leftfirst010, &["", "a"], "a", &[(0, 0, 0), (0, 1, 1)]),
318 t!(leftfirst011, &["", "a", ""], "a", &[(0, 0, 0), (0, 1, 1),]),
319 t!(leftfirst012, &["a", "", ""], "a", &[(0, 0, 1), (1, 1, 1),]),
320 t!(leftfirst013, &["", "", "a"], "a", &[(0, 0, 0), (0, 1, 1),]),
321 t!(leftfirst020, &["abcd", "ab"], "abcd", &[(0, 0, 4)]),
322 t!(leftfirst030, &["ab", "ab"], "abcd", &[(0, 0, 2)]),
323 t!(leftfirst040, &["a", "ab"], "xayabbbz", &[(0, 1, 2), (0, 3, 4)]),
324 t!(leftfirst100, &["abcdefg", "bcde", "bcdef"], "abcdef", &[(1, 1, 5)]),
325 t!(leftfirst110, &["abcdefg", "bcdef", "bcde"], "abcdef", &[(1, 1, 6)]),
326 t!(leftfirst300, &["abcd", "b", "bce"], "abce", &[(1, 1, 2)]),
327 t!(
328 leftfirst310,
329 &["abcd", "b", "bce", "ce"],
330 "abce",
331 &[(1, 1, 2), (3, 2, 4),]
332 ),
333 t!(
334 leftfirst320,
335 &["a", "abcdefghi", "hz", "abcdefgh"],
336 "abcdefghz",
337 &[(0, 0, 1), (2, 7, 9),]
338 ),
339 t!(leftfirst330, &["a", "abab"], "abab", &[(0, 0, 1), (0, 2, 3)]),
340 ];
341
342 /// Like LEFTMOST_FIRST, but for anchored searches.
343 const ANCHORED_LEFTMOST_FIRST: &'static [SearchTest] = &[
344 t!(aleftfirst000, &["ab", "abcd"], "abcd", &[(0, 0, 2)]),
345 t!(aleftfirst010, &["", "a"], "a", &[(0, 0, 0)]),
346 t!(aleftfirst011, &["", "a", ""], "a", &[(0, 0, 0)]),
347 t!(aleftfirst012, &["a", "", ""], "a", &[(0, 0, 1)]),
348 t!(aleftfirst013, &["", "", "a"], "a", &[(0, 0, 0)]),
349 t!(aleftfirst020, &["abcd", "ab"], "abcd", &[(0, 0, 4)]),
350 t!(aleftfirst030, &["ab", "ab"], "abcd", &[(0, 0, 2)]),
351 t!(aleftfirst040, &["a", "ab"], "xayabbbz", &[]),
352 t!(aleftfirst100, &["abcdefg", "bcde", "bcdef"], "abcdef", &[]),
353 t!(aleftfirst110, &["abcdefg", "bcdef", "bcde"], "abcdef", &[]),
354 t!(aleftfirst300, &["abcd", "b", "bce"], "abce", &[]),
355 t!(aleftfirst310, &["abcd", "b", "bce", "ce"], "abce", &[]),
356 t!(
357 aleftfirst320,
358 &["a", "abcdefghi", "hz", "abcdefgh"],
359 "abcdefghz",
360 &[(0, 0, 1)]
361 ),
362 t!(aleftfirst330, &["a", "abab"], "abab", &[(0, 0, 1)]),
363 ];
364
365 /// Tests for non-overlapping leftmost-longest match semantics. These tests
366 /// should generally be specific to leftmost-longest, which means they should
367 /// generally fail under leftmost-first semantics.
368 const LEFTMOST_LONGEST: &'static [SearchTest] = &[
369 t!(leftlong000, &["ab", "abcd"], "abcd", &[(1, 0, 4)]),
370 t!(leftlong010, &["abcd", "bcd", "cd", "b"], "abcd", &[(0, 0, 4),]),
371 t!(leftlong020, &["", "a"], "a", &[(1, 0, 1), (0, 1, 1),]),
372 t!(leftlong021, &["", "a", ""], "a", &[(1, 0, 1), (0, 1, 1),]),
373 t!(leftlong022, &["a", "", ""], "a", &[(0, 0, 1), (1, 1, 1),]),
374 t!(leftlong023, &["", "", "a"], "a", &[(2, 0, 1), (0, 1, 1),]),
375 t!(leftlong030, &["", "a"], "aa", &[(1, 0, 1), (1, 1, 2), (0, 2, 2),]),
376 t!(leftlong040, &["a", "ab"], "a", &[(0, 0, 1)]),
377 t!(leftlong050, &["a", "ab"], "ab", &[(1, 0, 2)]),
378 t!(leftlong060, &["ab", "a"], "a", &[(1, 0, 1)]),
379 t!(leftlong070, &["ab", "a"], "ab", &[(0, 0, 2)]),
380 t!(leftlong100, &["abcdefg", "bcde", "bcdef"], "abcdef", &[(2, 1, 6)]),
381 t!(leftlong110, &["abcdefg", "bcdef", "bcde"], "abcdef", &[(1, 1, 6)]),
382 t!(leftlong300, &["abcd", "b", "bce"], "abce", &[(2, 1, 4)]),
383 t!(
384 leftlong310,
385 &["a", "abcdefghi", "hz", "abcdefgh"],
386 "abcdefghz",
387 &[(3, 0, 8),]
388 ),
389 t!(leftlong320, &["a", "abab"], "abab", &[(1, 0, 4)]),
390 t!(leftlong330, &["abcd", "b", "ce"], "abce", &[(1, 1, 2), (2, 2, 4),]),
391 t!(leftlong340, &["a", "ab"], "xayabbbz", &[(0, 1, 2), (1, 3, 5)]),
392 ];
393
394 /// Like LEFTMOST_LONGEST, but for anchored searches.
395 const ANCHORED_LEFTMOST_LONGEST: &'static [SearchTest] = &[
396 t!(aleftlong000, &["ab", "abcd"], "abcd", &[(1, 0, 4)]),
397 t!(aleftlong010, &["abcd", "bcd", "cd", "b"], "abcd", &[(0, 0, 4),]),
398 t!(aleftlong020, &["", "a"], "a", &[(1, 0, 1)]),
399 t!(aleftlong021, &["", "a", ""], "a", &[(1, 0, 1)]),
400 t!(aleftlong022, &["a", "", ""], "a", &[(0, 0, 1)]),
401 t!(aleftlong023, &["", "", "a"], "a", &[(2, 0, 1)]),
402 t!(aleftlong030, &["", "a"], "aa", &[(1, 0, 1)]),
403 t!(aleftlong040, &["a", "ab"], "a", &[(0, 0, 1)]),
404 t!(aleftlong050, &["a", "ab"], "ab", &[(1, 0, 2)]),
405 t!(aleftlong060, &["ab", "a"], "a", &[(1, 0, 1)]),
406 t!(aleftlong070, &["ab", "a"], "ab", &[(0, 0, 2)]),
407 t!(aleftlong100, &["abcdefg", "bcde", "bcdef"], "abcdef", &[]),
408 t!(aleftlong110, &["abcdefg", "bcdef", "bcde"], "abcdef", &[]),
409 t!(aleftlong300, &["abcd", "b", "bce"], "abce", &[]),
410 t!(
411 aleftlong310,
412 &["a", "abcdefghi", "hz", "abcdefgh"],
413 "abcdefghz",
414 &[(3, 0, 8),]
415 ),
416 t!(aleftlong320, &["a", "abab"], "abab", &[(1, 0, 4)]),
417 t!(aleftlong330, &["abcd", "b", "ce"], "abce", &[]),
418 t!(aleftlong340, &["a", "ab"], "xayabbbz", &[]),
419 ];
420
421 /// Tests for non-overlapping match semantics.
422 ///
423 /// Generally these tests shouldn't pass when using overlapping semantics.
424 /// These should pass for both standard and leftmost match semantics.
425 const NON_OVERLAPPING: &'static [SearchTest] = &[
426 t!(nover010, &["abcd", "bcd", "cd"], "abcd", &[(0, 0, 4),]),
427 t!(nover020, &["bcd", "cd", "abcd"], "abcd", &[(2, 0, 4),]),
428 t!(nover030, &["abc", "bc"], "zazabcz", &[(0, 3, 6),]),
429 t!(
430 nover100,
431 &["ab", "ba"],
432 "abababa",
433 &[(0, 0, 2), (0, 2, 4), (0, 4, 6),]
434 ),
435 t!(nover200, &["foo", "foo"], "foobarfoo", &[(0, 0, 3), (0, 6, 9),]),
436 t!(nover300, &["", ""], "", &[(0, 0, 0),]),
437 t!(nover310, &["", ""], "a", &[(0, 0, 0), (0, 1, 1),]),
438 ];
439
440 /// Like NON_OVERLAPPING, but for anchored searches.
441 const ANCHORED_NON_OVERLAPPING: &'static [SearchTest] = &[
442 t!(anover010, &["abcd", "bcd", "cd"], "abcd", &[(0, 0, 4),]),
443 t!(anover020, &["bcd", "cd", "abcd"], "abcd", &[(2, 0, 4),]),
444 t!(anover030, &["abc", "bc"], "zazabcz", &[]),
445 t!(anover100, &["ab", "ba"], "abababa", &[(0, 0, 2)]),
446 t!(anover200, &["foo", "foo"], "foobarfoo", &[(0, 0, 3)]),
447 t!(anover300, &["", ""], "", &[(0, 0, 0),]),
448 t!(anover310, &["", ""], "a", &[(0, 0, 0)]),
449 ];
450
451 /// Tests for overlapping match semantics.
452 ///
453 /// This only supports standard match semantics, since leftmost-{first,longest}
454 /// do not support overlapping matches.
455 const OVERLAPPING: &'static [SearchTest] = &[
456 t!(
457 over000,
458 &["abcd", "bcd", "cd", "b"],
459 "abcd",
460 &[(3, 1, 2), (0, 0, 4), (1, 1, 4), (2, 2, 4),]
461 ),
462 t!(
463 over010,
464 &["bcd", "cd", "b", "abcd"],
465 "abcd",
466 &[(2, 1, 2), (3, 0, 4), (0, 1, 4), (1, 2, 4),]
467 ),
468 t!(
469 over020,
470 &["abcd", "bcd", "cd"],
471 "abcd",
472 &[(0, 0, 4), (1, 1, 4), (2, 2, 4),]
473 ),
474 t!(
475 over030,
476 &["bcd", "abcd", "cd"],
477 "abcd",
478 &[(1, 0, 4), (0, 1, 4), (2, 2, 4),]
479 ),
480 t!(
481 over040,
482 &["bcd", "cd", "abcd"],
483 "abcd",
484 &[(2, 0, 4), (0, 1, 4), (1, 2, 4),]
485 ),
486 t!(over050, &["abc", "bc"], "zazabcz", &[(0, 3, 6), (1, 4, 6),]),
487 t!(
488 over100,
489 &["ab", "ba"],
490 "abababa",
491 &[(0, 0, 2), (1, 1, 3), (0, 2, 4), (1, 3, 5), (0, 4, 6), (1, 5, 7),]
492 ),
493 t!(
494 over200,
495 &["foo", "foo"],
496 "foobarfoo",
497 &[(0, 0, 3), (1, 0, 3), (0, 6, 9), (1, 6, 9),]
498 ),
499 t!(over300, &["", ""], "", &[(0, 0, 0), (1, 0, 0),]),
500 t!(
501 over310,
502 &["", ""],
503 "a",
504 &[(0, 0, 0), (1, 0, 0), (0, 1, 1), (1, 1, 1),]
505 ),
506 t!(over320, &["", "a"], "a", &[(0, 0, 0), (1, 0, 1), (0, 1, 1),]),
507 t!(
508 over330,
509 &["", "a", ""],
510 "a",
511 &[(0, 0, 0), (2, 0, 0), (1, 0, 1), (0, 1, 1), (2, 1, 1),]
512 ),
513 t!(
514 over340,
515 &["a", "", ""],
516 "a",
517 &[(1, 0, 0), (2, 0, 0), (0, 0, 1), (1, 1, 1), (2, 1, 1),]
518 ),
519 t!(
520 over350,
521 &["", "", "a"],
522 "a",
523 &[(0, 0, 0), (1, 0, 0), (2, 0, 1), (0, 1, 1), (1, 1, 1),]
524 ),
525 t!(
526 over360,
527 &["foo", "foofoo"],
528 "foofoo",
529 &[(0, 0, 3), (1, 0, 6), (0, 3, 6)]
530 ),
531 ];
532
533 /// Like OVERLAPPING, but for anchored searches.
534 const ANCHORED_OVERLAPPING: &'static [SearchTest] = &[
535 t!(aover000, &["abcd", "bcd", "cd", "b"], "abcd", &[(0, 0, 4)]),
536 t!(aover010, &["bcd", "cd", "b", "abcd"], "abcd", &[(3, 0, 4)]),
537 t!(aover020, &["abcd", "bcd", "cd"], "abcd", &[(0, 0, 4)]),
538 t!(aover030, &["bcd", "abcd", "cd"], "abcd", &[(1, 0, 4)]),
539 t!(aover040, &["bcd", "cd", "abcd"], "abcd", &[(2, 0, 4)]),
540 t!(aover050, &["abc", "bc"], "zazabcz", &[]),
541 t!(aover100, &["ab", "ba"], "abababa", &[(0, 0, 2)]),
542 t!(aover200, &["foo", "foo"], "foobarfoo", &[(0, 0, 3), (1, 0, 3)]),
543 t!(aover300, &["", ""], "", &[(0, 0, 0), (1, 0, 0),]),
544 t!(aover310, &["", ""], "a", &[(0, 0, 0), (1, 0, 0)]),
545 t!(aover320, &["", "a"], "a", &[(0, 0, 0), (1, 0, 1)]),
546 t!(aover330, &["", "a", ""], "a", &[(0, 0, 0), (2, 0, 0), (1, 0, 1)]),
547 t!(aover340, &["a", "", ""], "a", &[(1, 0, 0), (2, 0, 0), (0, 0, 1)]),
548 t!(aover350, &["", "", "a"], "a", &[(0, 0, 0), (1, 0, 0), (2, 0, 1)]),
549 t!(aover360, &["foo", "foofoo"], "foofoo", &[(0, 0, 3), (1, 0, 6)]),
550 ];
551
552 /// Tests for ASCII case insensitivity.
553 ///
554 /// These tests should all have the same behavior regardless of match semantics
555 /// or whether the search is overlapping.
556 const ASCII_CASE_INSENSITIVE: &'static [SearchTest] = &[
557 t!(acasei000, &["a"], "A", &[(0, 0, 1)]),
558 t!(acasei010, &["Samwise"], "SAMWISE", &[(0, 0, 7)]),
559 t!(acasei011, &["Samwise"], "SAMWISE.abcd", &[(0, 0, 7)]),
560 t!(acasei020, &["fOoBaR"], "quux foobar baz", &[(0, 5, 11)]),
561 ];
562
563 /// Like ASCII_CASE_INSENSITIVE, but specifically for non-overlapping tests.
564 const ASCII_CASE_INSENSITIVE_NON_OVERLAPPING: &'static [SearchTest] = &[
565 t!(acasei000, &["foo", "FOO"], "fOo", &[(0, 0, 3)]),
566 t!(acasei000, &["FOO", "foo"], "fOo", &[(0, 0, 3)]),
567 t!(acasei010, &["abc", "def"], "abcdef", &[(0, 0, 3), (1, 3, 6)]),
568 ];
569
570 /// Like ASCII_CASE_INSENSITIVE, but specifically for overlapping tests.
571 const ASCII_CASE_INSENSITIVE_OVERLAPPING: &'static [SearchTest] = &[
572 t!(acasei000, &["foo", "FOO"], "fOo", &[(0, 0, 3), (1, 0, 3)]),
573 t!(acasei001, &["FOO", "foo"], "fOo", &[(0, 0, 3), (1, 0, 3)]),
574 // This is a regression test from:
575 // https://github.com/BurntSushi/aho-corasick/issues/68
576 // Previously, it was reporting a duplicate (1, 3, 6) match.
577 t!(
578 acasei010,
579 &["abc", "def", "abcdef"],
580 "abcdef",
581 &[(0, 0, 3), (2, 0, 6), (1, 3, 6)]
582 ),
583 ];
584
585 /// Regression tests that are applied to all Aho-Corasick combinations.
586 ///
587 /// If regression tests are needed for specific match semantics, then add them
588 /// to the appropriate group above.
589 const REGRESSION: &'static [SearchTest] = &[
590 t!(regression010, &["inf", "ind"], "infind", &[(0, 0, 3), (1, 3, 6),]),
591 t!(regression020, &["ind", "inf"], "infind", &[(1, 0, 3), (0, 3, 6),]),
592 t!(
593 regression030,
594 &["libcore/", "libstd/"],
595 "libcore/char/methods.rs",
596 &[(0, 0, 8),]
597 ),
598 t!(
599 regression040,
600 &["libstd/", "libcore/"],
601 "libcore/char/methods.rs",
602 &[(1, 0, 8),]
603 ),
604 t!(
605 regression050,
606 &["\x00\x00\x01", "\x00\x00\x00"],
607 "\x00\x00\x00",
608 &[(1, 0, 3),]
609 ),
610 t!(
611 regression060,
612 &["\x00\x00\x00", "\x00\x00\x01"],
613 "\x00\x00\x00",
614 &[(0, 0, 3),]
615 ),
616 ];
617
618 // Now define a test for each combination of things above that we want to run.
619 // Since there are a few different combinations for each collection of tests,
620 // we define a couple of macros to avoid repetition drudgery. The testconfig
621 // macro constructs the automaton from a given match kind, and runs the search
622 // tests one-by-one over the given collection. The `with` parameter allows one
623 // to configure the builder with additional parameters. The testcombo macro
624 // invokes testconfig in precisely this way: it sets up several tests where
625 // each one turns a different knob on AhoCorasickBuilder.
626
627 macro_rules! testconfig {
628 (overlapping, $name:ident, $collection:expr, $kind:ident, $with:expr) => {
629 #[test]
630 fn $name() {
631 run_search_tests($collection, |test| {
632 let mut builder = AhoCorasickBuilder::new();
633 $with(&mut builder);
634 builder
635 .match_kind(MatchKind::$kind)
636 .build(test.patterns)
637 .find_overlapping_iter(test.haystack)
638 .collect()
639 });
640 }
641 };
642 (stream, $name:ident, $collection:expr, $kind:ident, $with:expr) => {
643 #[test]
644 fn $name() {
645 run_search_tests($collection, |test| {
646 let buf =
647 io::BufReader::with_capacity(1, test.haystack.as_bytes());
648 let mut builder = AhoCorasickBuilder::new();
649 $with(&mut builder);
650 builder
651 .match_kind(MatchKind::$kind)
652 .build(test.patterns)
653 .stream_find_iter(buf)
654 .map(|result| result.unwrap())
655 .collect()
656 });
657 }
658 };
659 ($name:ident, $collection:expr, $kind:ident, $with:expr) => {
660 #[test]
661 fn $name() {
662 run_search_tests($collection, |test| {
663 let mut builder = AhoCorasickBuilder::new();
664 $with(&mut builder);
665 builder
666 .match_kind(MatchKind::$kind)
667 .build(test.patterns)
668 .find_iter(test.haystack)
669 .collect()
670 });
671 }
672 };
673 }
674
675 macro_rules! testcombo {
676 ($name:ident, $collection:expr, $kind:ident) => {
677 mod $name {
678 use super::*;
679
680 testconfig!(nfa_default, $collection, $kind, |_| ());
681 testconfig!(
682 nfa_no_prefilter,
683 $collection,
684 $kind,
685 |b: &mut AhoCorasickBuilder| {
686 b.prefilter(false);
687 }
688 );
689 testconfig!(
690 nfa_all_sparse,
691 $collection,
692 $kind,
693 |b: &mut AhoCorasickBuilder| {
694 b.dense_depth(0);
695 }
696 );
697 testconfig!(
698 nfa_all_dense,
699 $collection,
700 $kind,
701 |b: &mut AhoCorasickBuilder| {
702 b.dense_depth(usize::MAX);
703 }
704 );
705 testconfig!(
706 dfa_default,
707 $collection,
708 $kind,
709 |b: &mut AhoCorasickBuilder| {
710 b.dfa(true);
711 }
712 );
713 testconfig!(
714 dfa_no_prefilter,
715 $collection,
716 $kind,
717 |b: &mut AhoCorasickBuilder| {
718 b.dfa(true).prefilter(false);
719 }
720 );
721 testconfig!(
722 dfa_all_sparse,
723 $collection,
724 $kind,
725 |b: &mut AhoCorasickBuilder| {
726 b.dfa(true).dense_depth(0);
727 }
728 );
729 testconfig!(
730 dfa_all_dense,
731 $collection,
732 $kind,
733 |b: &mut AhoCorasickBuilder| {
734 b.dfa(true).dense_depth(usize::MAX);
735 }
736 );
737 testconfig!(
738 dfa_no_byte_class,
739 $collection,
740 $kind,
741 |b: &mut AhoCorasickBuilder| {
742 b.dfa(true).byte_classes(false);
743 }
744 );
745 testconfig!(
746 dfa_no_premultiply,
747 $collection,
748 $kind,
749 |b: &mut AhoCorasickBuilder| {
750 b.dfa(true).premultiply(false);
751 }
752 );
753 testconfig!(
754 dfa_no_byte_class_no_premultiply,
755 $collection,
756 $kind,
757 |b: &mut AhoCorasickBuilder| {
758 b.dfa(true).byte_classes(false).premultiply(false);
759 }
760 );
761 }
762 };
763 }
764
765 // Write out the combinations.
766 testcombo!(search_leftmost_longest, AC_LEFTMOST_LONGEST, LeftmostLongest);
767 testcombo!(search_leftmost_first, AC_LEFTMOST_FIRST, LeftmostFirst);
768 testcombo!(
769 search_standard_nonoverlapping,
770 AC_STANDARD_NON_OVERLAPPING,
771 Standard
772 );
773
774 // Write out the overlapping combo by hand since there is only one of them.
775 testconfig!(
776 overlapping,
777 search_standard_overlapping_nfa_default,
778 AC_STANDARD_OVERLAPPING,
779 Standard,
780 |_| ()
781 );
782 testconfig!(
783 overlapping,
784 search_standard_overlapping_nfa_all_sparse,
785 AC_STANDARD_OVERLAPPING,
786 Standard,
787 |b: &mut AhoCorasickBuilder| {
788 b.dense_depth(0);
789 }
790 );
791 testconfig!(
792 overlapping,
793 search_standard_overlapping_nfa_all_dense,
794 AC_STANDARD_OVERLAPPING,
795 Standard,
796 |b: &mut AhoCorasickBuilder| {
797 b.dense_depth(usize::MAX);
798 }
799 );
800 testconfig!(
801 overlapping,
802 search_standard_overlapping_dfa_default,
803 AC_STANDARD_OVERLAPPING,
804 Standard,
805 |b: &mut AhoCorasickBuilder| {
806 b.dfa(true);
807 }
808 );
809 testconfig!(
810 overlapping,
811 search_standard_overlapping_dfa_all_sparse,
812 AC_STANDARD_OVERLAPPING,
813 Standard,
814 |b: &mut AhoCorasickBuilder| {
815 b.dfa(true).dense_depth(0);
816 }
817 );
818 testconfig!(
819 overlapping,
820 search_standard_overlapping_dfa_all_dense,
821 AC_STANDARD_OVERLAPPING,
822 Standard,
823 |b: &mut AhoCorasickBuilder| {
824 b.dfa(true).dense_depth(usize::MAX);
825 }
826 );
827 testconfig!(
828 overlapping,
829 search_standard_overlapping_dfa_no_byte_class,
830 AC_STANDARD_OVERLAPPING,
831 Standard,
832 |b: &mut AhoCorasickBuilder| {
833 b.dfa(true).byte_classes(false);
834 }
835 );
836 testconfig!(
837 overlapping,
838 search_standard_overlapping_dfa_no_premultiply,
839 AC_STANDARD_OVERLAPPING,
840 Standard,
841 |b: &mut AhoCorasickBuilder| {
842 b.dfa(true).premultiply(false);
843 }
844 );
845 testconfig!(
846 overlapping,
847 search_standard_overlapping_dfa_no_byte_class_no_premultiply,
848 AC_STANDARD_OVERLAPPING,
849 Standard,
850 |b: &mut AhoCorasickBuilder| {
851 b.dfa(true).byte_classes(false).premultiply(false);
852 }
853 );
854
855 // Also write out tests manually for streams, since we only test the standard
856 // match semantics. We also don't bother testing different automaton
857 // configurations, since those are well covered by tests above.
858 testconfig!(
859 stream,
860 search_standard_stream_nfa_default,
861 AC_STANDARD_NON_OVERLAPPING,
862 Standard,
863 |_| ()
864 );
865 testconfig!(
866 stream,
867 search_standard_stream_dfa_default,
868 AC_STANDARD_NON_OVERLAPPING,
869 Standard,
870 |b: &mut AhoCorasickBuilder| {
871 b.dfa(true);
872 }
873 );
874
875 // Same thing for anchored searches. Write them out manually.
876 testconfig!(
877 search_standard_anchored_nfa_default,
878 AC_STANDARD_ANCHORED_NON_OVERLAPPING,
879 Standard,
880 |b: &mut AhoCorasickBuilder| {
881 b.anchored(true);
882 }
883 );
884 testconfig!(
885 search_standard_anchored_dfa_default,
886 AC_STANDARD_ANCHORED_NON_OVERLAPPING,
887 Standard,
888 |b: &mut AhoCorasickBuilder| {
889 b.anchored(true).dfa(true);
890 }
891 );
892 testconfig!(
893 overlapping,
894 search_standard_anchored_overlapping_nfa_default,
895 AC_STANDARD_ANCHORED_OVERLAPPING,
896 Standard,
897 |b: &mut AhoCorasickBuilder| {
898 b.anchored(true);
899 }
900 );
901 testconfig!(
902 overlapping,
903 search_standard_anchored_overlapping_dfa_default,
904 AC_STANDARD_ANCHORED_OVERLAPPING,
905 Standard,
906 |b: &mut AhoCorasickBuilder| {
907 b.anchored(true).dfa(true);
908 }
909 );
910 testconfig!(
911 search_leftmost_first_anchored_nfa_default,
912 AC_LEFTMOST_FIRST_ANCHORED,
913 LeftmostFirst,
914 |b: &mut AhoCorasickBuilder| {
915 b.anchored(true);
916 }
917 );
918 testconfig!(
919 search_leftmost_first_anchored_dfa_default,
920 AC_LEFTMOST_FIRST_ANCHORED,
921 LeftmostFirst,
922 |b: &mut AhoCorasickBuilder| {
923 b.anchored(true).dfa(true);
924 }
925 );
926 testconfig!(
927 search_leftmost_longest_anchored_nfa_default,
928 AC_LEFTMOST_LONGEST_ANCHORED,
929 LeftmostLongest,
930 |b: &mut AhoCorasickBuilder| {
931 b.anchored(true);
932 }
933 );
934 testconfig!(
935 search_leftmost_longest_anchored_dfa_default,
936 AC_LEFTMOST_LONGEST_ANCHORED,
937 LeftmostLongest,
938 |b: &mut AhoCorasickBuilder| {
939 b.anchored(true).dfa(true);
940 }
941 );
942
943 // And also write out the test combinations for ASCII case insensitivity.
944 testconfig!(
945 acasei_standard_nfa_default,
946 &[ASCII_CASE_INSENSITIVE],
947 Standard,
948 |b: &mut AhoCorasickBuilder| {
949 b.prefilter(false).ascii_case_insensitive(true);
950 }
951 );
952 testconfig!(
953 acasei_standard_dfa_default,
954 &[ASCII_CASE_INSENSITIVE, ASCII_CASE_INSENSITIVE_NON_OVERLAPPING],
955 Standard,
956 |b: &mut AhoCorasickBuilder| {
957 b.ascii_case_insensitive(true).dfa(true);
958 }
959 );
960 testconfig!(
961 overlapping,
962 acasei_standard_overlapping_nfa_default,
963 &[ASCII_CASE_INSENSITIVE, ASCII_CASE_INSENSITIVE_OVERLAPPING],
964 Standard,
965 |b: &mut AhoCorasickBuilder| {
966 b.ascii_case_insensitive(true);
967 }
968 );
969 testconfig!(
970 overlapping,
971 acasei_standard_overlapping_dfa_default,
972 &[ASCII_CASE_INSENSITIVE, ASCII_CASE_INSENSITIVE_OVERLAPPING],
973 Standard,
974 |b: &mut AhoCorasickBuilder| {
975 b.ascii_case_insensitive(true).dfa(true);
976 }
977 );
978 testconfig!(
979 acasei_leftmost_first_nfa_default,
980 &[ASCII_CASE_INSENSITIVE, ASCII_CASE_INSENSITIVE_NON_OVERLAPPING],
981 LeftmostFirst,
982 |b: &mut AhoCorasickBuilder| {
983 b.ascii_case_insensitive(true);
984 }
985 );
986 testconfig!(
987 acasei_leftmost_first_dfa_default,
988 &[ASCII_CASE_INSENSITIVE, ASCII_CASE_INSENSITIVE_NON_OVERLAPPING],
989 LeftmostFirst,
990 |b: &mut AhoCorasickBuilder| {
991 b.ascii_case_insensitive(true).dfa(true);
992 }
993 );
994 testconfig!(
995 acasei_leftmost_longest_nfa_default,
996 &[ASCII_CASE_INSENSITIVE, ASCII_CASE_INSENSITIVE_NON_OVERLAPPING],
997 LeftmostLongest,
998 |b: &mut AhoCorasickBuilder| {
999 b.ascii_case_insensitive(true);
1000 }
1001 );
1002 testconfig!(
1003 acasei_leftmost_longest_dfa_default,
1004 &[ASCII_CASE_INSENSITIVE, ASCII_CASE_INSENSITIVE_NON_OVERLAPPING],
1005 LeftmostLongest,
1006 |b: &mut AhoCorasickBuilder| {
1007 b.ascii_case_insensitive(true).dfa(true);
1008 }
1009 );
1010
run_search_tests<F: FnMut(&SearchTest) -> Vec<Match>>( which: TestCollection, mut f: F, )1011 fn run_search_tests<F: FnMut(&SearchTest) -> Vec<Match>>(
1012 which: TestCollection,
1013 mut f: F,
1014 ) {
1015 let get_match_triples =
1016 |matches: Vec<Match>| -> Vec<(usize, usize, usize)> {
1017 matches
1018 .into_iter()
1019 .map(|m| (m.pattern(), m.start(), m.end()))
1020 .collect()
1021 };
1022 for &tests in which {
1023 for test in tests {
1024 assert_eq!(
1025 test.matches,
1026 get_match_triples(f(&test)).as_slice(),
1027 "test: {}, patterns: {:?}, haystack: {:?}",
1028 test.name,
1029 test.patterns,
1030 test.haystack
1031 );
1032 }
1033 }
1034 }
1035
1036 #[test]
search_tests_have_unique_names()1037 fn search_tests_have_unique_names() {
1038 let assert = |constname, tests: &[SearchTest]| {
1039 let mut seen = HashMap::new(); // map from test name to position
1040 for (i, test) in tests.iter().enumerate() {
1041 if !seen.contains_key(test.name) {
1042 seen.insert(test.name, i);
1043 } else {
1044 let last = seen[test.name];
1045 panic!(
1046 "{} tests have duplicate names at positions {} and {}",
1047 constname, last, i
1048 );
1049 }
1050 }
1051 };
1052 assert("BASICS", BASICS);
1053 assert("STANDARD", STANDARD);
1054 assert("LEFTMOST", LEFTMOST);
1055 assert("LEFTMOST_FIRST", LEFTMOST_FIRST);
1056 assert("LEFTMOST_LONGEST", LEFTMOST_LONGEST);
1057 assert("NON_OVERLAPPING", NON_OVERLAPPING);
1058 assert("OVERLAPPING", OVERLAPPING);
1059 assert("REGRESSION", REGRESSION);
1060 }
1061
1062 #[test]
1063 #[should_panic]
stream_not_allowed_leftmost_first()1064 fn stream_not_allowed_leftmost_first() {
1065 let fsm = AhoCorasickBuilder::new()
1066 .match_kind(MatchKind::LeftmostFirst)
1067 .build(None::<String>);
1068 assert_eq!(fsm.stream_find_iter(&b""[..]).count(), 0);
1069 }
1070
1071 #[test]
1072 #[should_panic]
stream_not_allowed_leftmost_longest()1073 fn stream_not_allowed_leftmost_longest() {
1074 let fsm = AhoCorasickBuilder::new()
1075 .match_kind(MatchKind::LeftmostLongest)
1076 .build(None::<String>);
1077 assert_eq!(fsm.stream_find_iter(&b""[..]).count(), 0);
1078 }
1079
1080 #[test]
1081 #[should_panic]
overlapping_not_allowed_leftmost_first()1082 fn overlapping_not_allowed_leftmost_first() {
1083 let fsm = AhoCorasickBuilder::new()
1084 .match_kind(MatchKind::LeftmostFirst)
1085 .build(None::<String>);
1086 assert_eq!(fsm.find_overlapping_iter("").count(), 0);
1087 }
1088
1089 #[test]
1090 #[should_panic]
overlapping_not_allowed_leftmost_longest()1091 fn overlapping_not_allowed_leftmost_longest() {
1092 let fsm = AhoCorasickBuilder::new()
1093 .match_kind(MatchKind::LeftmostLongest)
1094 .build(None::<String>);
1095 assert_eq!(fsm.find_overlapping_iter("").count(), 0);
1096 }
1097
1098 #[test]
state_id_too_small()1099 fn state_id_too_small() {
1100 let mut patterns = vec![];
1101 for c1 in (b'a'..b'z').map(|b| b as char) {
1102 for c2 in (b'a'..b'z').map(|b| b as char) {
1103 for c3 in (b'a'..b'z').map(|b| b as char) {
1104 patterns.push(format!("{}{}{}", c1, c2, c3));
1105 }
1106 }
1107 }
1108 let result =
1109 AhoCorasickBuilder::new().build_with_size::<u8, _, _>(&patterns);
1110 assert!(result.is_err());
1111 }
1112
1113 // See: https://github.com/BurntSushi/aho-corasick/issues/44
1114 //
1115 // In short, this test ensures that enabling ASCII case insensitivity does not
1116 // visit an exponential number of states when filling in failure transitions.
1117 #[test]
regression_ascii_case_insensitive_no_exponential()1118 fn regression_ascii_case_insensitive_no_exponential() {
1119 let ac = AhoCorasickBuilder::new()
1120 .ascii_case_insensitive(true)
1121 .build(&["Tsubaki House-Triple Shot Vol01校花三姐妹"]);
1122 assert!(ac.find("").is_none());
1123 }
1124
1125 // See: https://github.com/BurntSushi/aho-corasick/issues/53
1126 //
1127 // This test ensures that the rare byte prefilter works in a particular corner
1128 // case. In particular, the shift offset detected for '/' in the patterns below
1129 // was incorrect, leading to a false negative.
1130 #[test]
regression_rare_byte_prefilter()1131 fn regression_rare_byte_prefilter() {
1132 use AhoCorasick;
1133
1134 let ac = AhoCorasick::new_auto_configured(&["ab/j/", "x/"]);
1135 assert!(ac.is_match("ab/j/"));
1136 }
1137
1138 #[test]
regression_case_insensitive_prefilter()1139 fn regression_case_insensitive_prefilter() {
1140 use AhoCorasickBuilder;
1141
1142 for c in b'a'..b'z' {
1143 for c2 in b'a'..b'z' {
1144 let c = c as char;
1145 let c2 = c2 as char;
1146 let needle = format!("{}{}", c, c2).to_lowercase();
1147 let haystack = needle.to_uppercase();
1148 let ac = AhoCorasickBuilder::new()
1149 .ascii_case_insensitive(true)
1150 .prefilter(true)
1151 .build(&[&needle]);
1152 assert_eq!(
1153 1,
1154 ac.find_iter(&haystack).count(),
1155 "failed to find {:?} in {:?}\n\nautomaton:\n{:?}",
1156 needle,
1157 haystack,
1158 ac,
1159 );
1160 }
1161 }
1162 }
1163
1164 // See: https://github.com/BurntSushi/aho-corasick/issues/64
1165 //
1166 // This occurs when the rare byte prefilter is active.
1167 #[test]
regression_stream_rare_byte_prefilter()1168 fn regression_stream_rare_byte_prefilter() {
1169 use std::io::Read;
1170
1171 // NOTE: The test only fails if this ends with j.
1172 const MAGIC: [u8; 5] = *b"1234j";
1173
1174 // NOTE: The test fails for value in 8188..=8191 These value put the string
1175 // to search accross two call to read because the buffer size is 8192 by
1176 // default.
1177 const BEGIN: usize = 8191;
1178
1179 /// This is just a structure that implements Reader. The reader
1180 /// implementation will simulate a file filled with 0, except for the MAGIC
1181 /// string at offset BEGIN.
1182 #[derive(Default)]
1183 struct R {
1184 read: usize,
1185 }
1186
1187 impl Read for R {
1188 fn read(&mut self, buf: &mut [u8]) -> ::std::io::Result<usize> {
1189 //dbg!(buf.len());
1190 if self.read > 100000 {
1191 return Ok(0);
1192 }
1193 let mut from = 0;
1194 if self.read < BEGIN {
1195 from = buf.len().min(BEGIN - self.read);
1196 for x in 0..from {
1197 buf[x] = 0;
1198 }
1199 self.read += from;
1200 }
1201 if self.read >= BEGIN && self.read <= BEGIN + MAGIC.len() {
1202 let to = buf.len().min(BEGIN + MAGIC.len() - self.read + from);
1203 if to > from {
1204 buf[from..to].copy_from_slice(
1205 &MAGIC
1206 [self.read - BEGIN..self.read - BEGIN + to - from],
1207 );
1208 self.read += to - from;
1209 from = to;
1210 }
1211 }
1212 for x in from..buf.len() {
1213 buf[x] = 0;
1214 self.read += 1;
1215 }
1216 Ok(buf.len())
1217 }
1218 }
1219
1220 fn run() -> ::std::io::Result<()> {
1221 let aut = AhoCorasickBuilder::new().build(&[&MAGIC]);
1222
1223 // While reading from a vector, it works:
1224 let mut buf = vec![];
1225 R::default().read_to_end(&mut buf)?;
1226 let from_whole = aut.find_iter(&buf).next().unwrap().start();
1227
1228 //But using stream_find_iter fails!
1229 let mut file = R::default();
1230 let begin = aut
1231 .stream_find_iter(&mut file)
1232 .next()
1233 .expect("NOT FOUND!!!!")? // Panic here
1234 .start();
1235 assert_eq!(from_whole, begin);
1236 Ok(())
1237 }
1238
1239 run().unwrap()
1240 }
1241