Debian Codegraph @

.cargo/vendor/regex-automata/tests/nfa/thompson/backtrack/suite.rs

raw
1 use {
2 anyhow::Result,
3 regex_automata::{
4 nfa::thompson::{
5 self,
6 backtrack::{self, BoundedBacktracker},
7 NFA,
8 },
9 util::{prefilter::Prefilter, syntax},
10 Input,
11 },
12 regex_test::{
13 CompiledRegex, Match, MatchKind, RegexTest, SearchKind, Span,
14 TestResult, TestRunner,
15 },
16 };
17
18 use crate::{create_input, suite, testify_captures};
19
20 /// Tests the default configuration of the bounded backtracker.
21 #[test]
22 fn default() -> Result<()> {
23 let builder = BoundedBacktracker::builder();
24 let mut runner = TestRunner::new()?;
25 runner.expand(&["is_match", "find", "captures"], |test| test.compiles());
26 // At the time of writing, every regex search in the test suite fits
27 // into the backtracker's default visited capacity (except for the
28 // blacklisted tests below). If regexes are added that blow that capacity,
29 // then they should be blacklisted here. A tempting alternative is to
30 // automatically skip them by checking the haystack length against
31 // BoundedBacktracker::max_haystack_len, but that could wind up hiding
32 // interesting failure modes. e.g., If the visited capacity is somehow
33 // wrong or smaller than it should be.
34 runner.blacklist("expensive/backtrack-blow-visited-capacity");
35 runner.test_iter(suite()?.iter(), compiler(builder)).assert();
36 Ok(())
37 }
38
39 /// Tests the backtracker with prefilters enabled.
40 #[test]
41 fn prefilter() -> Result<()> {
42 let my_compiler = |test: &RegexTest, regexes: &[String]| {
43 // Parse regexes as HIRs so we can get literals to build a prefilter.
44 let mut hirs = vec![];
45 for pattern in regexes.iter() {
46 hirs.push(syntax::parse_with(pattern, &config_syntax(test))?);
47 }
48 // We can always select leftmost-first here because the backtracker
49 // only supports leftmost-first matching.
50 let pre = Prefilter::from_hirs_prefix(
51 regex_automata::MatchKind::LeftmostFirst,
52 &hirs,
53 );
54 let mut builder = BoundedBacktracker::builder();
55 builder.configure(BoundedBacktracker::config().prefilter(pre));
56 compiler(builder)(test, regexes)
57 };
58 let mut runner = TestRunner::new()?;
59 runner.expand(&["is_match", "find", "captures"], |test| test.compiles());
60 runner.blacklist("expensive/backtrack-blow-visited-capacity");
61 runner.test_iter(suite()?.iter(), my_compiler).assert();
62 Ok(())
63 }
64
65 /// Tests the bounded backtracker when its visited capacity is set to its
66 /// minimum amount.
67 #[test]
68 fn min_visited_capacity() -> Result<()> {
69 let mut runner = TestRunner::new()?;
70 runner.expand(&["is_match", "find", "captures"], |test| test.compiles());
71 runner
72 .test_iter(suite()?.iter(), move |test, regexes| {
73 let nfa = NFA::compiler()
74 .configure(config_thompson(test))
75 .syntax(config_syntax(test))
76 .build_many(&regexes)?;
77 let mut builder = BoundedBacktracker::builder();
78 if !configure_backtrack_builder(test, &mut builder) {
79 return Ok(CompiledRegex::skip());
80 }
81 // Setup the bounded backtracker so that its visited capacity is
82 // the absolute minimum required for the test's haystack.
83 builder.configure(BoundedBacktracker::config().visited_capacity(
84 backtrack::min_visited_capacity(
85 &nfa,
86 &Input::new(test.haystack()),
87 ),
88 ));
89
90 let re = builder.build_from_nfa(nfa)?;
91 let mut cache = re.create_cache();
92 Ok(CompiledRegex::compiled(move |test| -> TestResult {
93 run_test(&re, &mut cache, test)
94 }))
95 })
96 .assert();
97 Ok(())
98 }
99
100 fn compiler(
101 mut builder: backtrack::Builder,
102 ) -> impl FnMut(&RegexTest, &[String]) -> Result<CompiledRegex> {
103 move |test, regexes| {
104 if !configure_backtrack_builder(test, &mut builder) {
105 return Ok(CompiledRegex::skip());
106 }
107 let re = builder.build_many(&regexes)?;
108 let mut cache = re.create_cache();
109 Ok(CompiledRegex::compiled(move |test| -> TestResult {
110 run_test(&re, &mut cache, test)
111 }))
112 }
113 }
114
115 fn run_test(
116 re: &BoundedBacktracker,
117 cache: &mut backtrack::Cache,
118 test: &RegexTest,
119 ) -> TestResult {
120 let input = create_input(test);
121 match test.additional_name() {
122 "is_match" => match test.search_kind() {
123 SearchKind::Earliest | SearchKind::Overlapping => {
124 TestResult::skip()
125 }
126 SearchKind::Leftmost => {
127 let input = input.earliest(true);
128 TestResult::matched(re.try_is_match(cache, input).unwrap())
129 }
130 },
131 "find" => match test.search_kind() {
132 SearchKind::Earliest | SearchKind::Overlapping => {
133 TestResult::skip()
134 }
135 SearchKind::Leftmost => TestResult::matches(
136 re.try_find_iter(cache, input)
137 .take(test.match_limit().unwrap_or(std::usize::MAX))
138 .map(|result| result.unwrap())
139 .map(|m| Match {
140 id: m.pattern().as_usize(),
141 span: Span { start: m.start(), end: m.end() },
142 }),
143 ),
144 },
145 "captures" => match test.search_kind() {
146 SearchKind::Earliest | SearchKind::Overlapping => {
147 TestResult::skip()
148 }
149 SearchKind::Leftmost => TestResult::captures(
150 re.try_captures_iter(cache, input)
151 .take(test.match_limit().unwrap_or(std::usize::MAX))
152 .map(|result| result.unwrap())
153 .map(|caps| testify_captures(&caps)),
154 ),
155 },
156 name => TestResult::fail(&format!("unrecognized test name: {}", name)),
157 }
158 }
159
160 /// Configures the given regex builder with all relevant settings on the given
161 /// regex test.
162 ///
163 /// If the regex test has a setting that is unsupported, then this returns
164 /// false (implying the test should be skipped).
165 fn configure_backtrack_builder(
166 test: &RegexTest,
167 builder: &mut backtrack::Builder,
168 ) -> bool {
169 match (test.search_kind(), test.match_kind()) {
170 // For testing the standard search APIs. This is the only supported
171 // configuration for the backtracker.
172 (SearchKind::Leftmost, MatchKind::LeftmostFirst) => {}
173 // Overlapping APIs not supported at all for backtracker.
174 (SearchKind::Overlapping, _) => return false,
175 // Backtracking doesn't really support the notion of 'earliest'.
176 // Namely, backtracking already works by returning as soon as it knows
177 // it has found a match. It just so happens that this corresponds to
178 // the standard 'leftmost' formulation.
179 //
180 // The 'earliest' definition in this crate does indeed permit this
181 // behavior, so this is "fine," but our test suite specifically looks
182 // for the earliest position at which a match is known, which our
183 // finite automata based regex engines have no problem providing. So
184 // for backtracking, we just skip these tests.
185 (SearchKind::Earliest, _) => return false,
186 // For backtracking, 'all' semantics don't really make sense.
187 (_, MatchKind::All) => return false,
188 // Not supported at all in regex-automata.
189 (_, MatchKind::LeftmostLongest) => return false,
190 };
191 let backtrack_config = BoundedBacktracker::config();
192 builder
193 .configure(backtrack_config)
194 .syntax(config_syntax(test))
195 .thompson(config_thompson(test));
196 true
197 }
198
199 /// Configuration of a Thompson NFA compiler from a regex test.
200 fn config_thompson(test: &RegexTest) -> thompson::Config {
201 let mut lookm = regex_automata::util::look::LookMatcher::new();
202 lookm.set_line_terminator(test.line_terminator());
203 thompson::Config::new().utf8(test.utf8()).look_matcher(lookm)
204 }
205
206 /// Configuration of the regex parser from a regex test.
207 fn config_syntax(test: &RegexTest) -> syntax::Config {
208 syntax::Config::new()
209 .case_insensitive(test.case_insensitive())
210 .unicode(test.unicode())
211 .utf8(test.utf8())
212 .line_terminator(test.line_terminator())
213 }