Debian Codegraph @

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

raw
1 use {
2 anyhow::Result,
3 regex_automata::{
4 hybrid::{
5 dfa::{OverlappingState, DFA},
6 regex::{self, Regex},
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 /// Tests the default configuration of the hybrid NFA/DFA.
23 #[test]
24 fn default() -> Result<()> {
25 let builder = Regex::builder();
26 TestRunner::new()?
27 .expand(EXPANSIONS, |t| t.compiles())
28 // Without NFA shrinking, this test blows the default cache capacity.
29 .blacklist("expensive/regression-many-repeat-no-stack-overflow")
30 .test_iter(suite()?.iter(), compiler(builder))
31 .assert();
32 Ok(())
33 }
34
35 /// Tests the hybrid NFA/DFA with prefilters enabled.
36 #[test]
37 fn 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.dfa(DFA::config().prefilter(pre));
51 compiler(builder)(test, regexes)
52 };
53 TestRunner::new()?
54 .expand(EXPANSIONS, |t| t.compiles())
55 // Without NFA shrinking, this test blows the default cache capacity.
56 .blacklist("expensive/regression-many-repeat-no-stack-overflow")
57 .test_iter(suite()?.iter(), my_compiler)
58 .assert();
59 Ok(())
60 }
61
62 /// Tests the hybrid NFA/DFA with NFA shrinking enabled.
63 ///
64 /// This is *usually* not the configuration one wants for a lazy DFA. NFA
65 /// shrinking is mostly only advantageous when building a full DFA since it
66 /// can sharply decrease the amount of time determinization takes. But NFA
67 /// shrinking is itself otherwise fairly expensive currently. Since a lazy DFA
68 /// has no compilation time (other than for building the NFA of course) before
69 /// executing a search, it's usually worth it to forgo NFA shrinking.
70 ///
71 /// Nevertheless, we test to make sure everything is OK with NFA shrinking. As
72 /// a bonus, there are some tests we don't need to skip because they now fit in
73 /// the default cache capacity.
74 #[test]
75 fn nfa_shrink() -> Result<()> {
76 let mut builder = Regex::builder();
77 builder.thompson(thompson::Config::new().shrink(true));
78 TestRunner::new()?
79 .expand(EXPANSIONS, |t| t.compiles())
80 .test_iter(suite()?.iter(), compiler(builder))
81 .assert();
82 Ok(())
83 }
84
85 /// Tests the hybrid NFA/DFA when 'starts_for_each_pattern' is enabled for all
86 /// tests.
87 #[test]
88 fn starts_for_each_pattern() -> Result<()> {
89 let mut builder = Regex::builder();
90 builder.dfa(DFA::config().starts_for_each_pattern(true));
91 TestRunner::new()?
92 .expand(EXPANSIONS, |t| t.compiles())
93 // Without NFA shrinking, this test blows the default cache capacity.
94 .blacklist("expensive/regression-many-repeat-no-stack-overflow")
95 .test_iter(suite()?.iter(), compiler(builder))
96 .assert();
97 Ok(())
98 }
99
100 /// Tests the hybrid NFA/DFA when 'specialize_start_states' is enabled.
101 #[test]
102 fn specialize_start_states() -> Result<()> {
103 let mut builder = Regex::builder();
104 builder.dfa(DFA::config().specialize_start_states(true));
105 TestRunner::new()?
106 .expand(EXPANSIONS, |t| t.compiles())
107 // Without NFA shrinking, this test blows the default cache capacity.
108 .blacklist("expensive/regression-many-repeat-no-stack-overflow")
109 .test_iter(suite()?.iter(), compiler(builder))
110 .assert();
111 Ok(())
112 }
113
114 /// Tests the hybrid NFA/DFA when byte classes are disabled.
115 ///
116 /// N.B. Disabling byte classes doesn't avoid any indirection at search time.
117 /// All it does is cause every byte value to be its own distinct equivalence
118 /// class.
119 #[test]
120 fn no_byte_classes() -> Result<()> {
121 let mut builder = Regex::builder();
122 builder.dfa(DFA::config().byte_classes(false));
123 TestRunner::new()?
124 .expand(EXPANSIONS, |t| t.compiles())
125 // Without NFA shrinking, this test blows the default cache capacity.
126 .blacklist("expensive/regression-many-repeat-no-stack-overflow")
127 .test_iter(suite()?.iter(), compiler(builder))
128 .assert();
129 Ok(())
130 }
131
132 /// Tests that hybrid NFA/DFA never clears its cache for any test with the
133 /// default capacity.
134 ///
135 /// N.B. If a regex suite test is added that causes the cache to be cleared,
136 /// then this should just skip that test. (Which can be done by calling the
137 /// 'blacklist' method on 'TestRunner'.)
138 #[test]
139 fn no_cache_clearing() -> Result<()> {
140 let mut builder = Regex::builder();
141 builder.dfa(DFA::config().minimum_cache_clear_count(Some(0)));
142 TestRunner::new()?
143 .expand(EXPANSIONS, |t| t.compiles())
144 // Without NFA shrinking, this test blows the default cache capacity.
145 .blacklist("expensive/regression-many-repeat-no-stack-overflow")
146 .test_iter(suite()?.iter(), compiler(builder))
147 .assert();
148 Ok(())
149 }
150
151 /// Tests the hybrid NFA/DFA when the minimum cache capacity is set.
152 #[test]
153 fn min_cache_capacity() -> Result<()> {
154 let mut builder = Regex::builder();
155 builder
156 .dfa(DFA::config().cache_capacity(0).skip_cache_capacity_check(true));
157 TestRunner::new()?
158 .expand(EXPANSIONS, |t| t.compiles())
159 .test_iter(suite()?.iter(), compiler(builder))
160 .assert();
161 Ok(())
162 }
163
164 fn compiler(
165 mut builder: regex::Builder,
166 ) -> impl FnMut(&RegexTest, &[String]) -> Result<CompiledRegex> {
167 move |test, regexes| {
168 // Parse regexes as HIRs for some analysis below.
169 let mut hirs = vec![];
170 for pattern in regexes.iter() {
171 hirs.push(syntax::parse_with(pattern, &config_syntax(test))?);
172 }
173
174 // Check if our regex contains things that aren't supported by DFAs.
175 // That is, Unicode word boundaries when searching non-ASCII text.
176 if !test.haystack().is_ascii() {
177 for hir in hirs.iter() {
178 if hir.properties().look_set().contains_word_unicode() {
179 return Ok(CompiledRegex::skip());
180 }
181 }
182 }
183 if !configure_regex_builder(test, &mut builder) {
184 return Ok(CompiledRegex::skip());
185 }
186 let re = builder.build_many(&regexes)?;
187 let mut cache = re.create_cache();
188 Ok(CompiledRegex::compiled(move |test| -> TestResult {
189 run_test(&re, &mut cache, test)
190 }))
191 }
192 }
193
194 fn run_test(
195 re: &Regex,
196 cache: &mut regex::Cache,
197 test: &RegexTest,
198 ) -> TestResult {
199 let input = create_input(test);
200 match test.additional_name() {
201 "is_match" => {
202 TestResult::matched(re.is_match(cache, input.earliest(true)))
203 }
204 "find" => match test.search_kind() {
205 SearchKind::Earliest | SearchKind::Leftmost => {
206 let input =
207 input.earliest(test.search_kind() == SearchKind::Earliest);
208 TestResult::matches(
209 re.find_iter(cache, input)
210 .take(test.match_limit().unwrap_or(std::usize::MAX))
211 .map(|m| Match {
212 id: m.pattern().as_usize(),
213 span: Span { start: m.start(), end: m.end() },
214 }),
215 )
216 }
217 SearchKind::Overlapping => {
218 try_search_overlapping(re, cache, &input).unwrap()
219 }
220 },
221 "which" => match test.search_kind() {
222 SearchKind::Earliest | SearchKind::Leftmost => {
223 // There are no "which" APIs for standard searches.
224 TestResult::skip()
225 }
226 SearchKind::Overlapping => {
227 let dfa = re.forward();
228 let cache = cache.as_parts_mut().0;
229 let mut patset = PatternSet::new(dfa.pattern_len());
230 dfa.try_which_overlapping_matches(cache, &input, &mut patset)
231 .unwrap();
232 TestResult::which(patset.iter().map(|p| p.as_usize()))
233 }
234 },
235 name => TestResult::fail(&format!("unrecognized test name: {}", name)),
236 }
237 }
238
239 /// Configures the given regex builder with all relevant settings on the given
240 /// regex test.
241 ///
242 /// If the regex test has a setting that is unsupported, then this returns
243 /// false (implying the test should be skipped).
244 fn configure_regex_builder(
245 test: &RegexTest,
246 builder: &mut regex::Builder,
247 ) -> bool {
248 let match_kind = match untestify_kind(test.match_kind()) {
249 None => return false,
250 Some(k) => k,
251 };
252
253 let mut dfa_config =
254 DFA::config().match_kind(match_kind).unicode_word_boundary(true);
255 // When doing an overlapping search, we might try to find the start of each
256 // match with a custom search routine. In that case, we need to tell the
257 // reverse search (for the start offset) which pattern to look for. The
258 // only way that API works is when anchored starting states are compiled
259 // for each pattern. This does technically also enable it for the forward
260 // DFA, but we're okay with that.
261 if test.search_kind() == SearchKind::Overlapping {
262 dfa_config = dfa_config.starts_for_each_pattern(true);
263 }
264 builder
265 .syntax(config_syntax(test))
266 .thompson(config_thompson(test))
267 .dfa(dfa_config);
268 true
269 }
270
271 /// Configuration of a Thompson NFA compiler from a regex test.
272 fn config_thompson(test: &RegexTest) -> thompson::Config {
273 let mut lookm = regex_automata::util::look::LookMatcher::new();
274 lookm.set_line_terminator(test.line_terminator());
275 thompson::Config::new().utf8(test.utf8()).look_matcher(lookm)
276 }
277
278 /// Configuration of the regex parser from a regex test.
279 fn config_syntax(test: &RegexTest) -> syntax::Config {
280 syntax::Config::new()
281 .case_insensitive(test.case_insensitive())
282 .unicode(test.unicode())
283 .utf8(test.utf8())
284 .line_terminator(test.line_terminator())
285 }
286
287 /// Execute an overlapping search, and for each match found, also find its
288 /// overlapping starting positions.
289 ///
290 /// N.B. This routine used to be part of the crate API, but 1) it wasn't clear
291 /// to me how useful it was and 2) it wasn't clear to me what its semantics
292 /// should be. In particular, a potentially surprising footgun of this routine
293 /// that it is worst case *quadratic* in the size of the haystack. Namely, it's
294 /// possible to report a match at every position, and for every such position,
295 /// scan all the way to the beginning of the haystack to find the starting
296 /// position. Typical leftmost non-overlapping searches don't suffer from this
297 /// because, well, matches can't overlap. So subsequent searches after a match
298 /// is found don't revisit previously scanned parts of the haystack.
299 ///
300 /// Its semantics can be strange for other reasons too. For example, given
301 /// the regex '.*' and the haystack 'zz', the full set of overlapping matches
302 /// is: [0, 0], [1, 1], [0, 1], [2, 2], [1, 2], [0, 2]. The ordering of
303 /// those matches is quite strange, but makes sense when you think about the
304 /// implementation: an end offset is found left-to-right, and then one or more
305 /// starting offsets are found right-to-left.
306 ///
307 /// Nevertheless, we provide this routine in our test suite because it's
308 /// useful to test the low level DFA overlapping search and our test suite
309 /// is written in a way that requires starting offsets.
310 fn try_search_overlapping(
311 re: &Regex,
312 cache: &mut regex::Cache,
313 input: &Input<'_>,
314 ) -> Result<TestResult> {
315 let mut matches = vec![];
316 let mut fwd_state = OverlappingState::start();
317 let (fwd_dfa, rev_dfa) = (re.forward(), re.reverse());
318 let (fwd_cache, rev_cache) = cache.as_parts_mut();
319 while let Some(end) = {
320 fwd_dfa.try_search_overlapping_fwd(
321 fwd_cache,
322 input,
323 &mut fwd_state,
324 )?;
325 fwd_state.get_match()
326 } {
327 let revsearch = input
328 .clone()
329 .range(input.start()..end.offset())
330 .anchored(Anchored::Pattern(end.pattern()))
331 .earliest(false);
332 let mut rev_state = OverlappingState::start();
333 while let Some(start) = {
334 rev_dfa.try_search_overlapping_rev(
335 rev_cache,
336 &revsearch,
337 &mut rev_state,
338 )?;
339 rev_state.get_match()
340 } {
341 let span = Span { start: start.offset(), end: end.offset() };
342 let mat = Match { id: end.pattern().as_usize(), span };
343 matches.push(mat);
344 }
345 }
346 Ok(TestResult::matches(matches))
347 }