diff options
Diffstat (limited to 'vendor/regex-automata/tests/dfa/suite.rs')
| -rw-r--r-- | vendor/regex-automata/tests/dfa/suite.rs | 365 |
1 files changed, 266 insertions, 99 deletions
diff --git a/vendor/regex-automata/tests/dfa/suite.rs b/vendor/regex-automata/tests/dfa/suite.rs index 426ae346d..f3445e02a 100644 --- a/vendor/regex-automata/tests/dfa/suite.rs +++ b/vendor/regex-automata/tests/dfa/suite.rs @@ -1,23 +1,77 @@ -use regex_automata::{ - dfa::{self, dense, regex::Regex, sparse, Automaton}, - nfa::thompson, - MatchKind, SyntaxConfig, +use { + anyhow::Result, + regex_automata::{ + dfa::{ + self, dense, regex::Regex, sparse, Automaton, OverlappingState, + StartKind, + }, + nfa::thompson, + util::{prefilter::Prefilter, syntax}, + Anchored, Input, PatternSet, + }, + regex_syntax::hir, + regex_test::{ + CompiledRegex, Match, RegexTest, SearchKind, Span, TestResult, + TestRunner, + }, }; -use regex_syntax as syntax; -use regex_test::{ - bstr::{BString, ByteSlice}, - CompiledRegex, Match, MatchKind as TestMatchKind, RegexTest, RegexTests, - SearchKind as TestSearchKind, TestResult, TestRunner, -}; +use crate::{create_input, suite, untestify_kind}; -use crate::{suite, Result}; +const EXPANSIONS: &[&str] = &["is_match", "find", "which"]; /// Runs the test suite with the default configuration. #[test] fn unminimized_default() -> Result<()> { let builder = Regex::builder(); TestRunner::new()? + .expand(EXPANSIONS, |t| t.compiles()) + .blacklist("expensive") + .test_iter(suite()?.iter(), dense_compiler(builder)) + .assert(); + Ok(()) +} + +/// Runs the test suite with the default configuration and a prefilter enabled, +/// if one can be built. +#[test] +fn unminimized_prefilter() -> Result<()> { + let my_compiler = |test: &RegexTest, regexes: &[String]| { + // Parse regexes as HIRs so we can get literals to build a prefilter. + let mut hirs = vec![]; + for pattern in regexes.iter() { + hirs.push(syntax::parse_with(pattern, &config_syntax(test))?); + } + let kind = match untestify_kind(test.match_kind()) { + None => return Ok(CompiledRegex::skip()), + Some(kind) => kind, + }; + let pre = Prefilter::from_hirs_prefix(kind, &hirs); + let mut builder = Regex::builder(); + builder.dense(dense::DFA::config().prefilter(pre)); + compiler(builder, |_, _, re| { + Ok(CompiledRegex::compiled(move |test| -> TestResult { + run_test(&re, test) + })) + })(test, regexes) + }; + TestRunner::new()? + .expand(EXPANSIONS, |t| t.compiles()) + .blacklist("expensive") + .test_iter(suite()?.iter(), my_compiler) + .assert(); + Ok(()) +} + +/// Runs the test suite with start states specialized. +#[test] +fn unminimized_specialized_start_states() -> Result<()> { + let mut builder = Regex::builder(); + builder.dense(dense::Config::new().specialize_start_states(true)); + + TestRunner::new()? + .expand(EXPANSIONS, |t| t.compiles()) + .blacklist("expensive") .test_iter(suite()?.iter(), dense_compiler(builder)) .assert(); Ok(()) @@ -30,18 +84,22 @@ fn unminimized_no_byte_class() -> Result<()> { builder.dense(dense::Config::new().byte_classes(false)); TestRunner::new()? + .expand(EXPANSIONS, |t| t.compiles()) + .blacklist("expensive") .test_iter(suite()?.iter(), dense_compiler(builder)) .assert(); Ok(()) } -/// Runs the test suite with NFA shrinking disabled. +/// Runs the test suite with NFA shrinking enabled. #[test] -fn unminimized_no_nfa_shrink() -> Result<()> { +fn unminimized_nfa_shrink() -> Result<()> { let mut builder = Regex::builder(); - builder.thompson(thompson::Config::new().shrink(false)); + builder.thompson(thompson::Config::new().shrink(true)); TestRunner::new()? + .expand(EXPANSIONS, |t| t.compiles()) + .blacklist("expensive") .test_iter(suite()?.iter(), dense_compiler(builder)) .assert(); Ok(()) @@ -54,7 +112,7 @@ fn minimized_default() -> Result<()> { let mut builder = Regex::builder(); builder.dense(dense::Config::new().minimize(true)); TestRunner::new()? - // These regexes tend to be too big. Minimization takes... forever. + .expand(EXPANSIONS, |t| t.compiles()) .blacklist("expensive") .test_iter(suite()?.iter(), dense_compiler(builder)) .assert(); @@ -68,7 +126,7 @@ fn minimized_no_byte_class() -> Result<()> { builder.dense(dense::Config::new().minimize(true).byte_classes(false)); TestRunner::new()? - // These regexes tend to be too big. Minimization takes... forever. + .expand(EXPANSIONS, |t| t.compiles()) .blacklist("expensive") .test_iter(suite()?.iter(), dense_compiler(builder)) .assert(); @@ -80,22 +138,57 @@ fn minimized_no_byte_class() -> Result<()> { fn sparse_unminimized_default() -> Result<()> { let builder = Regex::builder(); TestRunner::new()? + .expand(EXPANSIONS, |t| t.compiles()) + .blacklist("expensive") .test_iter(suite()?.iter(), sparse_compiler(builder)) .assert(); Ok(()) } +/// Runs the test suite on a sparse unminimized DFA with prefilters enabled. +#[test] +fn sparse_unminimized_prefilter() -> Result<()> { + let my_compiler = |test: &RegexTest, regexes: &[String]| { + // Parse regexes as HIRs so we can get literals to build a prefilter. + let mut hirs = vec![]; + for pattern in regexes.iter() { + hirs.push(syntax::parse_with(pattern, &config_syntax(test))?); + } + let kind = match untestify_kind(test.match_kind()) { + None => return Ok(CompiledRegex::skip()), + Some(kind) => kind, + }; + let pre = Prefilter::from_hirs_prefix(kind, &hirs); + let mut builder = Regex::builder(); + builder.dense(dense::DFA::config().prefilter(pre)); + compiler(builder, |builder, _, re| { + let fwd = re.forward().to_sparse()?; + let rev = re.reverse().to_sparse()?; + let re = builder.build_from_dfas(fwd, rev); + Ok(CompiledRegex::compiled(move |test| -> TestResult { + run_test(&re, test) + })) + })(test, regexes) + }; + TestRunner::new()? + .expand(EXPANSIONS, |t| t.compiles()) + .blacklist("expensive") + .test_iter(suite()?.iter(), my_compiler) + .assert(); + Ok(()) +} + /// Another basic sanity test that checks we can serialize and then deserialize /// a regex, and that the resulting regex can be used for searching correctly. #[test] fn serialization_unminimized_default() -> Result<()> { let builder = Regex::builder(); let my_compiler = |builder| { - compiler(builder, |builder, re| { + compiler(builder, |builder, _, re| { let builder = builder.clone(); let (fwd_bytes, _) = re.forward().to_bytes_native_endian(); let (rev_bytes, _) = re.reverse().to_bytes_native_endian(); - Ok(CompiledRegex::compiled(move |test| -> Vec<TestResult> { + Ok(CompiledRegex::compiled(move |test| -> TestResult { let fwd: dense::DFA<&[u32]> = dense::DFA::from_bytes(&fwd_bytes).unwrap().0; let rev: dense::DFA<&[u32]> = @@ -107,6 +200,8 @@ fn serialization_unminimized_default() -> Result<()> { }) }; TestRunner::new()? + .expand(EXPANSIONS, |t| t.compiles()) + .blacklist("expensive") .test_iter(suite()?.iter(), my_compiler(builder)) .assert(); Ok(()) @@ -119,11 +214,11 @@ fn serialization_unminimized_default() -> Result<()> { fn sparse_serialization_unminimized_default() -> Result<()> { let builder = Regex::builder(); let my_compiler = |builder| { - compiler(builder, |builder, re| { + compiler(builder, |builder, _, re| { let builder = builder.clone(); let fwd_bytes = re.forward().to_sparse()?.to_bytes_native_endian(); let rev_bytes = re.reverse().to_sparse()?.to_bytes_native_endian(); - Ok(CompiledRegex::compiled(move |test| -> Vec<TestResult> { + Ok(CompiledRegex::compiled(move |test| -> TestResult { let fwd: sparse::DFA<&[u8]> = sparse::DFA::from_bytes(&fwd_bytes).unwrap().0; let rev: sparse::DFA<&[u8]> = @@ -134,6 +229,8 @@ fn sparse_serialization_unminimized_default() -> Result<()> { }) }; TestRunner::new()? + .expand(EXPANSIONS, |t| t.compiles()) + .blacklist("expensive") .test_iter(suite()?.iter(), my_compiler(builder)) .assert(); Ok(()) @@ -141,9 +238,9 @@ fn sparse_serialization_unminimized_default() -> Result<()> { fn dense_compiler( builder: dfa::regex::Builder, -) -> impl FnMut(&RegexTest, &[BString]) -> Result<CompiledRegex> { - compiler(builder, |_, re| { - Ok(CompiledRegex::compiled(move |test| -> Vec<TestResult> { +) -> impl FnMut(&RegexTest, &[String]) -> Result<CompiledRegex> { + compiler(builder, |_, _, re| { + Ok(CompiledRegex::compiled(move |test| -> TestResult { run_test(&re, test) })) }) @@ -151,12 +248,12 @@ fn dense_compiler( fn sparse_compiler( builder: dfa::regex::Builder, -) -> impl FnMut(&RegexTest, &[BString]) -> Result<CompiledRegex> { - compiler(builder, |builder, re| { +) -> impl FnMut(&RegexTest, &[String]) -> Result<CompiledRegex> { + compiler(builder, |builder, _, re| { let fwd = re.forward().to_sparse()?; let rev = re.reverse().to_sparse()?; let re = builder.build_from_dfas(fwd, rev); - Ok(CompiledRegex::compiled(move |test| -> Vec<TestResult> { + Ok(CompiledRegex::compiled(move |test| -> TestResult { run_test(&re, test) })) }) @@ -166,79 +263,79 @@ fn compiler( mut builder: dfa::regex::Builder, mut create_matcher: impl FnMut( &dfa::regex::Builder, + Option<Prefilter>, Regex, ) -> Result<CompiledRegex>, -) -> impl FnMut(&RegexTest, &[BString]) -> Result<CompiledRegex> { +) -> impl FnMut(&RegexTest, &[String]) -> Result<CompiledRegex> { move |test, regexes| { - let regexes = regexes - .iter() - .map(|r| r.to_str().map(|s| s.to_string())) - .collect::<std::result::Result<Vec<String>, _>>()?; + // Parse regexes as HIRs for some analysis below. + let mut hirs = vec![]; + for pattern in regexes.iter() { + hirs.push(syntax::parse_with(pattern, &config_syntax(test))?); + } + + // Get a prefilter in case the test wants it. + let kind = match untestify_kind(test.match_kind()) { + None => return Ok(CompiledRegex::skip()), + Some(kind) => kind, + }; + let pre = Prefilter::from_hirs_prefix(kind, &hirs); // Check if our regex contains things that aren't supported by DFAs. // That is, Unicode word boundaries when searching non-ASCII text. - let mut thompson = thompson::Builder::new(); - thompson.configure(config_thompson(test)); - // TODO: Modify Hir to report facts like this, instead of needing to - // build an NFA to do it. - if let Ok(nfa) = thompson.build_many(®exes) { - let non_ascii = test.input().iter().any(|&b| !b.is_ascii()); - if nfa.has_word_boundary_unicode() && non_ascii { - return Ok(CompiledRegex::skip()); + if !test.haystack().is_ascii() { + for hir in hirs.iter() { + let looks = hir.properties().look_set(); + if looks.contains(hir::Look::WordUnicode) + || looks.contains(hir::Look::WordUnicodeNegate) + { + return Ok(CompiledRegex::skip()); + } } } if !configure_regex_builder(test, &mut builder) { return Ok(CompiledRegex::skip()); } - create_matcher(&builder, builder.build_many(®exes)?) + create_matcher(&builder, pre, builder.build_many(®exes)?) } } -fn run_test<A: Automaton>(re: &Regex<A>, test: &RegexTest) -> Vec<TestResult> { - let is_match = if re.is_match(test.input()) { - TestResult::matched() - } else { - TestResult::no_match() - }; - let is_match = is_match.name("is_match"); - - let find_matches = match test.search_kind() { - TestSearchKind::Earliest => { - let it = re - .find_earliest_iter(test.input()) - .take(test.match_limit().unwrap_or(std::usize::MAX)) - .map(|m| Match { - id: m.pattern().as_usize(), - start: m.start(), - end: m.end(), - }); - TestResult::matches(it).name("find_earliest_iter") - } - TestSearchKind::Leftmost => { - let it = re - .find_leftmost_iter(test.input()) - .take(test.match_limit().unwrap_or(std::usize::MAX)) - .map(|m| Match { - id: m.pattern().as_usize(), - start: m.start(), - end: m.end(), - }); - TestResult::matches(it).name("find_leftmost_iter") - } - TestSearchKind::Overlapping => { - let it = re - .find_overlapping_iter(test.input()) - .take(test.match_limit().unwrap_or(std::usize::MAX)) - .map(|m| Match { - id: m.pattern().as_usize(), - start: m.start(), - end: m.end(), - }); - TestResult::matches(it).name("find_overlapping_iter") - } - }; - - vec![is_match, find_matches] +fn run_test<A: Automaton>(re: &Regex<A>, test: &RegexTest) -> TestResult { + let input = create_input(test); + match test.additional_name() { + "is_match" => TestResult::matched(re.is_match(input.earliest(true))), + "find" => match test.search_kind() { + SearchKind::Earliest | SearchKind::Leftmost => { + let input = + input.earliest(test.search_kind() == SearchKind::Earliest); + TestResult::matches( + re.find_iter(input) + .take(test.match_limit().unwrap_or(std::usize::MAX)) + .map(|m| Match { + id: m.pattern().as_usize(), + span: Span { start: m.start(), end: m.end() }, + }), + ) + } + SearchKind::Overlapping => { + try_search_overlapping(re, &input).unwrap() + } + }, + "which" => match test.search_kind() { + SearchKind::Earliest | SearchKind::Leftmost => { + // There are no "which" APIs for standard searches. + TestResult::skip() + } + SearchKind::Overlapping => { + let dfa = re.forward(); + let mut patset = PatternSet::new(dfa.pattern_len()); + dfa.try_which_overlapping_matches(&input, &mut patset) + .unwrap(); + TestResult::which(patset.iter().map(|p| p.as_usize())) + } + }, + name => TestResult::fail(&format!("unrecognized test name: {}", name)), + } } /// Configures the given regex builder with all relevant settings on the given @@ -250,25 +347,32 @@ fn configure_regex_builder( test: &RegexTest, builder: &mut dfa::regex::Builder, ) -> bool { - let match_kind = match test.match_kind() { - TestMatchKind::All => MatchKind::All, - TestMatchKind::LeftmostFirst => MatchKind::LeftmostFirst, - TestMatchKind::LeftmostLongest => return false, + let match_kind = match untestify_kind(test.match_kind()) { + None => return false, + Some(k) => k, }; - let syntax_config = SyntaxConfig::new() - .case_insensitive(test.case_insensitive()) - .unicode(test.unicode()) - .utf8(test.utf8()); - let dense_config = dense::Config::new() - .anchored(test.anchored()) + let starts = if test.anchored() { + StartKind::Anchored + } else { + StartKind::Unanchored + }; + let mut dense_config = dense::Config::new() + .start_kind(starts) .match_kind(match_kind) .unicode_word_boundary(true); - let regex_config = Regex::config().utf8(test.utf8()); + // When doing an overlapping search, we might try to find the start of each + // match with a custom search routine. In that case, we need to tell the + // reverse search (for the start offset) which pattern to look for. The + // only way that API works is when anchored starting states are compiled + // for each pattern. This does technically also enable it for the forward + // DFA, but we're okay with that. + if test.search_kind() == SearchKind::Overlapping { + dense_config = dense_config.starts_for_each_pattern(true); + } builder - .configure(regex_config) - .syntax(syntax_config) + .syntax(config_syntax(test)) .thompson(config_thompson(test)) .dense(dense_config); true @@ -276,5 +380,68 @@ fn configure_regex_builder( /// Configuration of a Thompson NFA compiler from a regex test. fn config_thompson(test: &RegexTest) -> thompson::Config { - thompson::Config::new().utf8(test.utf8()) + let mut lookm = regex_automata::util::look::LookMatcher::new(); + lookm.set_line_terminator(test.line_terminator()); + thompson::Config::new().utf8(test.utf8()).look_matcher(lookm) +} + +/// Configuration of the regex syntax from a regex test. +fn config_syntax(test: &RegexTest) -> syntax::Config { + syntax::Config::new() + .case_insensitive(test.case_insensitive()) + .unicode(test.unicode()) + .utf8(test.utf8()) + .line_terminator(test.line_terminator()) +} + +/// Execute an overlapping search, and for each match found, also find its +/// overlapping starting positions. +/// +/// N.B. This routine used to be part of the crate API, but 1) it wasn't clear +/// to me how useful it was and 2) it wasn't clear to me what its semantics +/// should be. In particular, a potentially surprising footgun of this routine +/// that it is worst case *quadratic* in the size of the haystack. Namely, it's +/// possible to report a match at every position, and for every such position, +/// scan all the way to the beginning of the haystack to find the starting +/// position. Typical leftmost non-overlapping searches don't suffer from this +/// because, well, matches can't overlap. So subsequent searches after a match +/// is found don't revisit previously scanned parts of the haystack. +/// +/// Its semantics can be strange for other reasons too. For example, given +/// the regex '.*' and the haystack 'zz', the full set of overlapping matches +/// is: [0, 0], [1, 1], [0, 1], [2, 2], [1, 2], [0, 2]. The ordering of +/// those matches is quite strange, but makes sense when you think about the +/// implementation: an end offset is found left-to-right, and then one or more +/// starting offsets are found right-to-left. +/// +/// Nevertheless, we provide this routine in our test suite because it's +/// useful to test the low level DFA overlapping search and our test suite +/// is written in a way that requires starting offsets. +fn try_search_overlapping<A: Automaton>( + re: &Regex<A>, + input: &Input<'_>, +) -> Result<TestResult> { + let mut matches = vec![]; + let mut fwd_state = OverlappingState::start(); + let (fwd_dfa, rev_dfa) = (re.forward(), re.reverse()); + while let Some(end) = { + fwd_dfa.try_search_overlapping_fwd(input, &mut fwd_state)?; + fwd_state.get_match() + } { + let revsearch = input + .clone() + .range(input.start()..end.offset()) + .anchored(Anchored::Pattern(end.pattern())) + .earliest(false); + let mut rev_state = OverlappingState::start(); + while let Some(start) = { + rev_dfa.try_search_overlapping_rev(&revsearch, &mut rev_state)?; + rev_state.get_match() + } { + let span = Span { start: start.offset(), end: end.offset() }; + let mat = Match { id: end.pattern().as_usize(), span }; + matches.push(mat); + } + } + Ok(TestResult::matches(matches)) } |