Debian Codegraph @

.cargo/vendor/regex-automata/tests/dfa/suite.rs

raw
1 use {
2 anyhow::Result,
3 regex_automata::{
4 dfa::{
5 self, dense, regex::Regex, sparse, Automaton, OverlappingState,
6 StartKind,
7 },
8 nfa::thompson,
9 util::{prefilter::Prefilter, syntax},
10 Anchored, Input, PatternSet,
11 },
12 regex_test::{
13 CompiledRegex, Match, RegexTest, SearchKind, Span, TestResult,
14 TestRunner,
15 },
16 };
17
18 use crate::{create_input, suite, untestify_kind};
19
20 const EXPANSIONS: &[&str] = &["is_match", "find", "which"];
21
22 /// Runs the test suite with the default configuration.
23 #[test]
24 fn unminimized_default() -> Result<()> {
25 let builder = Regex::builder();
26 TestRunner::new()?
27 .expand(EXPANSIONS, |t| t.compiles())
28 .blacklist("expensive")
29 .test_iter(suite()?.iter(), dense_compiler(builder))
30 .assert();
31 Ok(())
32 }
33
34 /// Runs the test suite with the default configuration and a prefilter enabled,
35 /// if one can be built.
36 #[test]
37 fn unminimized_prefilter() -> Result<()> {
38 let my_compiler = |test: &RegexTest, regexes: &[String]| {
39 // Parse regexes as HIRs so we can get literals to build a prefilter.
40 let mut hirs = vec![];
41 for pattern in regexes.iter() {
42 hirs.push(syntax::parse_with(pattern, &config_syntax(test))?);
43 }
44 let kind = match untestify_kind(test.match_kind()) {
45 None => return Ok(CompiledRegex::skip()),
46 Some(kind) => kind,
47 };
48 let pre = Prefilter::from_hirs_prefix(kind, &hirs);
49 let mut builder = Regex::builder();
50 builder.dense(dense::DFA::config().prefilter(pre));
51 compiler(builder, |_, _, re| {
52 Ok(CompiledRegex::compiled(move |test| -> TestResult {
53 run_test(&re, test)
54 }))
55 })(test, regexes)
56 };
57 TestRunner::new()?
58 .expand(EXPANSIONS, |t| t.compiles())
59 .blacklist("expensive")
60 .test_iter(suite()?.iter(), my_compiler)
61 .assert();
62 Ok(())
63 }
64
65 /// Runs the test suite with start states specialized.
66 #[test]
67 fn unminimized_specialized_start_states() -> Result<()> {
68 let mut builder = Regex::builder();
69 builder.dense(dense::Config::new().specialize_start_states(true));
70
71 TestRunner::new()?
72 .expand(EXPANSIONS, |t| t.compiles())
73 .blacklist("expensive")
74 .test_iter(suite()?.iter(), dense_compiler(builder))
75 .assert();
76 Ok(())
77 }
78
79 /// Runs the test suite with byte classes disabled.
80 #[test]
81 fn unminimized_no_byte_class() -> Result<()> {
82 let mut builder = Regex::builder();
83 builder.dense(dense::Config::new().byte_classes(false));
84
85 TestRunner::new()?
86 .expand(EXPANSIONS, |t| t.compiles())
87 .blacklist("expensive")
88 .test_iter(suite()?.iter(), dense_compiler(builder))
89 .assert();
90 Ok(())
91 }
92
93 /// Runs the test suite with NFA shrinking enabled.
94 #[test]
95 fn unminimized_nfa_shrink() -> Result<()> {
96 let mut builder = Regex::builder();
97 builder.thompson(thompson::Config::new().shrink(true));
98
99 TestRunner::new()?
100 .expand(EXPANSIONS, |t| t.compiles())
101 .blacklist("expensive")
102 .test_iter(suite()?.iter(), dense_compiler(builder))
103 .assert();
104 Ok(())
105 }
106
107 /// Runs the test suite on a minimized DFA with an otherwise default
108 /// configuration.
109 #[test]
110 fn minimized_default() -> Result<()> {
111 let mut builder = Regex::builder();
112 builder.dense(dense::Config::new().minimize(true));
113 TestRunner::new()?
114 .expand(EXPANSIONS, |t| t.compiles())
115 .blacklist("expensive")
116 .test_iter(suite()?.iter(), dense_compiler(builder))
117 .assert();
118 Ok(())
119 }
120
121 /// Runs the test suite on a minimized DFA with byte classes disabled.
122 #[test]
123 fn minimized_no_byte_class() -> Result<()> {
124 let mut builder = Regex::builder();
125 builder.dense(dense::Config::new().minimize(true).byte_classes(false));
126
127 TestRunner::new()?
128 .expand(EXPANSIONS, |t| t.compiles())
129 .blacklist("expensive")
130 .test_iter(suite()?.iter(), dense_compiler(builder))
131 .assert();
132 Ok(())
133 }
134
135 /// Runs the test suite on a sparse unminimized DFA.
136 #[test]
137 fn sparse_unminimized_default() -> Result<()> {
138 let builder = Regex::builder();
139 TestRunner::new()?
140 .expand(EXPANSIONS, |t| t.compiles())
141 .blacklist("expensive")
142 .test_iter(suite()?.iter(), sparse_compiler(builder))
143 .assert();
144 Ok(())
145 }
146
147 /// Runs the test suite on a sparse unminimized DFA with prefilters enabled.
148 #[test]
149 fn sparse_unminimized_prefilter() -> Result<()> {
150 let my_compiler = |test: &RegexTest, regexes: &[String]| {
151 // Parse regexes as HIRs so we can get literals to build a prefilter.
152 let mut hirs = vec![];
153 for pattern in regexes.iter() {
154 hirs.push(syntax::parse_with(pattern, &config_syntax(test))?);
155 }
156 let kind = match untestify_kind(test.match_kind()) {
157 None => return Ok(CompiledRegex::skip()),
158 Some(kind) => kind,
159 };
160 let pre = Prefilter::from_hirs_prefix(kind, &hirs);
161 let mut builder = Regex::builder();
162 builder.dense(dense::DFA::config().prefilter(pre));
163 compiler(builder, |builder, _, re| {
164 let fwd = re.forward().to_sparse()?;
165 let rev = re.reverse().to_sparse()?;
166 let re = builder.build_from_dfas(fwd, rev);
167 Ok(CompiledRegex::compiled(move |test| -> TestResult {
168 run_test(&re, test)
169 }))
170 })(test, regexes)
171 };
172 TestRunner::new()?
173 .expand(EXPANSIONS, |t| t.compiles())
174 .blacklist("expensive")
175 .test_iter(suite()?.iter(), my_compiler)
176 .assert();
177 Ok(())
178 }
179
180 /// Another basic sanity test that checks we can serialize and then deserialize
181 /// a regex, and that the resulting regex can be used for searching correctly.
182 #[test]
183 fn serialization_unminimized_default() -> Result<()> {
184 let builder = Regex::builder();
185 let my_compiler = |builder| {
186 compiler(builder, |builder, _, re| {
187 let builder = builder.clone();
188 let (fwd_bytes, _) = re.forward().to_bytes_native_endian();
189 let (rev_bytes, _) = re.reverse().to_bytes_native_endian();
190 Ok(CompiledRegex::compiled(move |test| -> TestResult {
191 let fwd: dense::DFA<&[u32]> =
192 dense::DFA::from_bytes(&fwd_bytes).unwrap().0;
193 let rev: dense::DFA<&[u32]> =
194 dense::DFA::from_bytes(&rev_bytes).unwrap().0;
195 let re = builder.build_from_dfas(fwd, rev);
196
197 run_test(&re, test)
198 }))
199 })
200 };
201 TestRunner::new()?
202 .expand(EXPANSIONS, |t| t.compiles())
203 .blacklist("expensive")
204 .test_iter(suite()?.iter(), my_compiler(builder))
205 .assert();
206 Ok(())
207 }
208
209 /// A basic sanity test that checks we can serialize and then deserialize a
210 /// regex using sparse DFAs, and that the resulting regex can be used for
211 /// searching correctly.
212 #[test]
213 fn sparse_serialization_unminimized_default() -> Result<()> {
214 let builder = Regex::builder();
215 let my_compiler = |builder| {
216 compiler(builder, |builder, _, re| {
217 let builder = builder.clone();
218 let fwd_bytes = re.forward().to_sparse()?.to_bytes_native_endian();
219 let rev_bytes = re.reverse().to_sparse()?.to_bytes_native_endian();
220 Ok(CompiledRegex::compiled(move |test| -> TestResult {
221 let fwd: sparse::DFA<&[u8]> =
222 sparse::DFA::from_bytes(&fwd_bytes).unwrap().0;
223 let rev: sparse::DFA<&[u8]> =
224 sparse::DFA::from_bytes(&rev_bytes).unwrap().0;
225 let re = builder.build_from_dfas(fwd, rev);
226 run_test(&re, test)
227 }))
228 })
229 };
230 TestRunner::new()?
231 .expand(EXPANSIONS, |t| t.compiles())
232 .blacklist("expensive")
233 .test_iter(suite()?.iter(), my_compiler(builder))
234 .assert();
235 Ok(())
236 }
237
238 fn dense_compiler(
239 builder: dfa::regex::Builder,
240 ) -> impl FnMut(&RegexTest, &[String]) -> Result<CompiledRegex> {
241 compiler(builder, |_, _, re| {
242 Ok(CompiledRegex::compiled(move |test| -> TestResult {
243 run_test(&re, test)
244 }))
245 })
246 }
247
248 fn sparse_compiler(
249 builder: dfa::regex::Builder,
250 ) -> impl FnMut(&RegexTest, &[String]) -> Result<CompiledRegex> {
251 compiler(builder, |builder, _, re| {
252 let fwd = re.forward().to_sparse()?;
253 let rev = re.reverse().to_sparse()?;
254 let re = builder.build_from_dfas(fwd, rev);
255 Ok(CompiledRegex::compiled(move |test| -> TestResult {
256 run_test(&re, test)
257 }))
258 })
259 }
260
261 fn compiler(
262 mut builder: dfa::regex::Builder,
263 mut create_matcher: impl FnMut(
264 &dfa::regex::Builder,
265 Option<Prefilter>,
266 Regex,
267 ) -> Result<CompiledRegex>,
268 ) -> impl FnMut(&RegexTest, &[String]) -> Result<CompiledRegex> {
269 move |test, regexes| {
270 // Parse regexes as HIRs for some analysis below.
271 let mut hirs = vec![];
272 for pattern in regexes.iter() {
273 hirs.push(syntax::parse_with(pattern, &config_syntax(test))?);
274 }
275
276 // Get a prefilter in case the test wants it.
277 let kind = match untestify_kind(test.match_kind()) {
278 None => return Ok(CompiledRegex::skip()),
279 Some(kind) => kind,
280 };
281 let pre = Prefilter::from_hirs_prefix(kind, &hirs);
282
283 // Check if our regex contains things that aren't supported by DFAs.
284 // That is, Unicode word boundaries when searching non-ASCII text.
285 if !test.haystack().is_ascii() {
286 for hir in hirs.iter() {
287 if hir.properties().look_set().contains_word_unicode() {
288 return Ok(CompiledRegex::skip());
289 }
290 }
291 }
292 if !configure_regex_builder(test, &mut builder) {
293 return Ok(CompiledRegex::skip());
294 }
295 create_matcher(&builder, pre, builder.build_many(&regexes)?)
296 }
297 }
298
299 fn run_test<A: Automaton>(re: &Regex<A>, test: &RegexTest) -> TestResult {
300 let input = create_input(test);
301 match test.additional_name() {
302 "is_match" => TestResult::matched(re.is_match(input.earliest(true))),
303 "find" => match test.search_kind() {
304 SearchKind::Earliest | SearchKind::Leftmost => {
305 let input =
306 input.earliest(test.search_kind() == SearchKind::Earliest);
307 TestResult::matches(
308 re.find_iter(input)
309 .take(test.match_limit().unwrap_or(std::usize::MAX))
310 .map(|m| Match {
311 id: m.pattern().as_usize(),
312 span: Span { start: m.start(), end: m.end() },
313 }),
314 )
315 }
316 SearchKind::Overlapping => {
317 try_search_overlapping(re, &input).unwrap()
318 }
319 },
320 "which" => match test.search_kind() {
321 SearchKind::Earliest | SearchKind::Leftmost => {
322 // There are no "which" APIs for standard searches.
323 TestResult::skip()
324 }
325 SearchKind::Overlapping => {
326 let dfa = re.forward();
327 let mut patset = PatternSet::new(dfa.pattern_len());
328 dfa.try_which_overlapping_matches(&input, &mut patset)
329 .unwrap();
330 TestResult::which(patset.iter().map(|p| p.as_usize()))
331 }
332 },
333 name => TestResult::fail(&format!("unrecognized test name: {}", name)),
334 }
335 }
336
337 /// Configures the given regex builder with all relevant settings on the given
338 /// regex test.
339 ///
340 /// If the regex test has a setting that is unsupported, then this returns
341 /// false (implying the test should be skipped).
342 fn configure_regex_builder(
343 test: &RegexTest,
344 builder: &mut dfa::regex::Builder,
345 ) -> bool {
346 let match_kind = match untestify_kind(test.match_kind()) {
347 None => return false,
348 Some(k) => k,
349 };
350
351 let starts = if test.anchored() {
352 StartKind::Anchored
353 } else {
354 StartKind::Unanchored
355 };
356 let mut dense_config = dense::Config::new()
357 .start_kind(starts)
358 .match_kind(match_kind)
359 .unicode_word_boundary(true);
360 // When doing an overlapping search, we might try to find the start of each
361 // match with a custom search routine. In that case, we need to tell the
362 // reverse search (for the start offset) which pattern to look for. The
363 // only way that API works is when anchored starting states are compiled
364 // for each pattern. This does technically also enable it for the forward
365 // DFA, but we're okay with that.
366 if test.search_kind() == SearchKind::Overlapping {
367 dense_config = dense_config.starts_for_each_pattern(true);
368 }
369
370 builder
371 .syntax(config_syntax(test))
372 .thompson(config_thompson(test))
373 .dense(dense_config);
374 true
375 }
376
377 /// Configuration of a Thompson NFA compiler from a regex test.
378 fn config_thompson(test: &RegexTest) -> thompson::Config {
379 let mut lookm = regex_automata::util::look::LookMatcher::new();
380 lookm.set_line_terminator(test.line_terminator());
381 thompson::Config::new().utf8(test.utf8()).look_matcher(lookm)
382 }
383
384 /// Configuration of the regex syntax from a regex test.
385 fn config_syntax(test: &RegexTest) -> syntax::Config {
386 syntax::Config::new()
387 .case_insensitive(test.case_insensitive())
388 .unicode(test.unicode())
389 .utf8(test.utf8())
390 .line_terminator(test.line_terminator())
391 }
392
393 /// Execute an overlapping search, and for each match found, also find its
394 /// overlapping starting positions.
395 ///
396 /// N.B. This routine used to be part of the crate API, but 1) it wasn't clear
397 /// to me how useful it was and 2) it wasn't clear to me what its semantics
398 /// should be. In particular, a potentially surprising footgun of this routine
399 /// that it is worst case *quadratic* in the size of the haystack. Namely, it's
400 /// possible to report a match at every position, and for every such position,
401 /// scan all the way to the beginning of the haystack to find the starting
402 /// position. Typical leftmost non-overlapping searches don't suffer from this
403 /// because, well, matches can't overlap. So subsequent searches after a match
404 /// is found don't revisit previously scanned parts of the haystack.
405 ///
406 /// Its semantics can be strange for other reasons too. For example, given
407 /// the regex '.*' and the haystack 'zz', the full set of overlapping matches
408 /// is: [0, 0], [1, 1], [0, 1], [2, 2], [1, 2], [0, 2]. The ordering of
409 /// those matches is quite strange, but makes sense when you think about the
410 /// implementation: an end offset is found left-to-right, and then one or more
411 /// starting offsets are found right-to-left.
412 ///
413 /// Nevertheless, we provide this routine in our test suite because it's
414 /// useful to test the low level DFA overlapping search and our test suite
415 /// is written in a way that requires starting offsets.
416 fn try_search_overlapping<A: Automaton>(
417 re: &Regex<A>,
418 input: &Input<'_>,
419 ) -> Result<TestResult> {
420 let mut matches = vec![];
421 let mut fwd_state = OverlappingState::start();
422 let (fwd_dfa, rev_dfa) = (re.forward(), re.reverse());
423 while let Some(end) = {
424 fwd_dfa.try_search_overlapping_fwd(input, &mut fwd_state)?;
425 fwd_state.get_match()
426 } {
427 let revsearch = input
428 .clone()
429 .range(input.start()..end.offset())
430 .anchored(Anchored::Pattern(end.pattern()))
431 .earliest(false);
432 let mut rev_state = OverlappingState::start();
433 while let Some(start) = {
434 rev_dfa.try_search_overlapping_rev(&revsearch, &mut rev_state)?;
435 rev_state.get_match()
436 } {
437 let span = Span { start: start.offset(), end: end.offset() };
438 let mat = Match { id: end.pattern().as_usize(), span };
439 matches.push(mat);
440 }
441 }
442 Ok(TestResult::matches(matches))
443 }