diff options
Diffstat (limited to 'vendor/regex-automata/tests/nfa/thompson/pikevm')
3 files changed, 108 insertions, 246 deletions
diff --git a/vendor/regex-automata/tests/nfa/thompson/pikevm/api.rs b/vendor/regex-automata/tests/nfa/thompson/pikevm/api.rs deleted file mode 100644 index c8199f709..000000000 --- a/vendor/regex-automata/tests/nfa/thompson/pikevm/api.rs +++ /dev/null @@ -1,191 +0,0 @@ -/* -use std::error::Error; - -use regex_automata::{ - hybrid::{ - dfa::{self, DFA}, - regex::Regex, - OverlappingState, - }, - nfa::thompson, - HalfMatch, MatchError, MatchKind, MultiMatch, -}; - -use crate::util::{BunkPrefilter, SubstringPrefilter}; - -// Tests that too many cache resets cause the lazy DFA to quit. -#[test] -fn too_many_cache_resets_cause_quit() -> Result<(), Box<dyn Error>> { - // This is a carefully chosen regex. The idea is to pick one that requires - // some decent number of states (hence the bounded repetition). But we - // specifically choose to create a class with an ASCII letter and a - // non-ASCII letter so that we can check that no new states are created - // once the cache is full. Namely, if we fill up the cache on a haystack - // of 'a's, then in order to match one 'β', a new state will need to be - // created since a 'β' is encoded with multiple bytes. Since there's no - // room for this state, the search should quit at the very first position. - let pattern = r"[aβ]{100}"; - let dfa = DFA::builder() - .configure( - // Configure it so that we have the minimum cache capacity - // possible. And that if any resets occur, the search quits. - DFA::config() - .skip_cache_capacity_check(true) - .cache_capacity(0) - .minimum_cache_clear_count(Some(0)), - ) - .build(pattern)?; - let mut cache = dfa.create_cache(); - - let haystack = "a".repeat(101).into_bytes(); - let err = MatchError::GaveUp { offset: 25 }; - assert_eq!(dfa.find_earliest_fwd(&mut cache, &haystack), Err(err.clone())); - assert_eq!(dfa.find_leftmost_fwd(&mut cache, &haystack), Err(err.clone())); - assert_eq!( - dfa.find_overlapping_fwd( - &mut cache, - &haystack, - &mut OverlappingState::start() - ), - Err(err.clone()) - ); - - let haystack = "β".repeat(101).into_bytes(); - let err = MatchError::GaveUp { offset: 0 }; - assert_eq!(dfa.find_earliest_fwd(&mut cache, &haystack), Err(err)); - // no need to test that other find routines quit, since we did that above - - // OK, if we reset the cache, then we should be able to create more states - // and make more progress with searching for betas. - cache.reset(&dfa); - let err = MatchError::GaveUp { offset: 26 }; - assert_eq!(dfa.find_earliest_fwd(&mut cache, &haystack), Err(err)); - - // ... switching back to ASCII still makes progress since it just needs to - // set transitions on existing states! - let haystack = "a".repeat(101).into_bytes(); - let err = MatchError::GaveUp { offset: 13 }; - assert_eq!(dfa.find_earliest_fwd(&mut cache, &haystack), Err(err)); - - Ok(()) -} - -// Tests that quit bytes in the forward direction work correctly. -#[test] -fn quit_fwd() -> Result<(), Box<dyn Error>> { - let dfa = DFA::builder() - .configure(DFA::config().quit(b'x', true)) - .build("[[:word:]]+$")?; - let mut cache = dfa.create_cache(); - - assert_eq!( - dfa.find_earliest_fwd(&mut cache, b"abcxyz"), - Err(MatchError::Quit { byte: b'x', offset: 3 }) - ); - assert_eq!( - dfa.find_leftmost_fwd(&mut cache, b"abcxyz"), - Err(MatchError::Quit { byte: b'x', offset: 3 }) - ); - assert_eq!( - dfa.find_overlapping_fwd( - &mut cache, - b"abcxyz", - &mut OverlappingState::start() - ), - Err(MatchError::Quit { byte: b'x', offset: 3 }) - ); - - Ok(()) -} - -// Tests that quit bytes in the reverse direction work correctly. -#[test] -fn quit_rev() -> Result<(), Box<dyn Error>> { - let dfa = DFA::builder() - .configure(DFA::config().quit(b'x', true)) - .thompson(thompson::Config::new().reverse(true)) - .build("^[[:word:]]+")?; - let mut cache = dfa.create_cache(); - - assert_eq!( - dfa.find_earliest_rev(&mut cache, b"abcxyz"), - Err(MatchError::Quit { byte: b'x', offset: 3 }) - ); - assert_eq!( - dfa.find_leftmost_rev(&mut cache, b"abcxyz"), - Err(MatchError::Quit { byte: b'x', offset: 3 }) - ); - - Ok(()) -} - -// Tests that if we heuristically enable Unicode word boundaries but then -// instruct that a non-ASCII byte should NOT be a quit byte, then the builder -// will panic. -#[test] -#[should_panic] -fn quit_panics() { - DFA::config().unicode_word_boundary(true).quit(b'\xFF', false); -} - -// This tests an intesting case where even if the Unicode word boundary option -// is disabled, setting all non-ASCII bytes to be quit bytes will cause Unicode -// word boundaries to be enabled. -#[test] -fn unicode_word_implicitly_works() -> Result<(), Box<dyn Error>> { - let mut config = DFA::config(); - for b in 0x80..=0xFF { - config = config.quit(b, true); - } - let dfa = DFA::builder().configure(config).build(r"\b")?; - let mut cache = dfa.create_cache(); - let expected = HalfMatch::must(0, 1); - assert_eq!(dfa.find_leftmost_fwd(&mut cache, b" a"), Ok(Some(expected))); - Ok(()) -} - -// Tests that we can provide a prefilter to a Regex, and the search reports -// correct results. -#[test] -fn prefilter_works() -> Result<(), Box<dyn Error>> { - let mut re = Regex::new(r"a[0-9]+").unwrap(); - re.set_prefilter(Some(Box::new(SubstringPrefilter::new("a")))); - let mut cache = re.create_cache(); - - let text = b"foo abc foo a1a2a3 foo a123 bar aa456"; - let matches: Vec<(usize, usize)> = re - .find_leftmost_iter(&mut cache, text) - .map(|m| (m.start(), m.end())) - .collect(); - assert_eq!( - matches, - vec![(12, 14), (14, 16), (16, 18), (23, 27), (33, 37),] - ); - Ok(()) -} - -// This test confirms that a prefilter is active by using a prefilter that -// reports false negatives. -#[test] -fn prefilter_is_active() -> Result<(), Box<dyn Error>> { - let text = b"za123"; - let mut re = Regex::new(r"a[0-9]+").unwrap(); - let mut cache = re.create_cache(); - - re.set_prefilter(Some(Box::new(SubstringPrefilter::new("a")))); - assert_eq!( - re.find_leftmost(&mut cache, b"za123"), - Some(MultiMatch::must(0, 1, 5)) - ); - assert_eq!( - re.find_leftmost(&mut cache, b"a123"), - Some(MultiMatch::must(0, 0, 4)) - ); - re.set_prefilter(Some(Box::new(BunkPrefilter::new()))); - assert_eq!(re.find_leftmost(&mut cache, b"za123"), None); - // This checks that the prefilter is used when first starting the search, - // instead of waiting until at least one transition has occurred. - assert_eq!(re.find_leftmost(&mut cache, b"a123"), None); - Ok(()) -} -*/ diff --git a/vendor/regex-automata/tests/nfa/thompson/pikevm/mod.rs b/vendor/regex-automata/tests/nfa/thompson/pikevm/mod.rs index f4299510c..9d6ab475e 100644 --- a/vendor/regex-automata/tests/nfa/thompson/pikevm/mod.rs +++ b/vendor/regex-automata/tests/nfa/thompson/pikevm/mod.rs @@ -1,2 +1,2 @@ -mod api; +#[cfg(not(miri))] mod suite; diff --git a/vendor/regex-automata/tests/nfa/thompson/pikevm/suite.rs b/vendor/regex-automata/tests/nfa/thompson/pikevm/suite.rs index e5505d59a..d32842a15 100644 --- a/vendor/regex-automata/tests/nfa/thompson/pikevm/suite.rs +++ b/vendor/regex-automata/tests/nfa/thompson/pikevm/suite.rs @@ -1,42 +1,65 @@ -use regex_automata::{ - nfa::thompson::{ - self, - pikevm::{self, PikeVM}, +use { + anyhow::Result, + regex_automata::{ + nfa::thompson::{ + self, + pikevm::{self, PikeVM}, + }, + util::{prefilter::Prefilter, syntax}, + PatternSet, + }, + regex_test::{ + CompiledRegex, Match, RegexTest, SearchKind, Span, TestResult, + TestRunner, }, - MatchKind, SyntaxConfig, -}; -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::{suite, Result}; +use crate::{create_input, suite, testify_captures, untestify_kind}; /// Tests the default configuration of the hybrid NFA/DFA. #[test] fn default() -> Result<()> { let builder = PikeVM::builder(); - TestRunner::new()?.test_iter(suite()?.iter(), compiler(builder)).assert(); + let mut runner = TestRunner::new()?; + runner.expand(&["is_match", "find", "captures"], |test| test.compiles()); + runner.test_iter(suite()?.iter(), compiler(builder)).assert(); + Ok(()) +} + +/// Tests the PikeVM with prefilters enabled. +#[test] +fn 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 = PikeVM::builder(); + builder.configure(PikeVM::config().prefilter(pre)); + compiler(builder)(test, regexes) + }; + let mut runner = TestRunner::new()?; + runner.expand(&["is_match", "find", "captures"], |test| test.compiles()); + runner.test_iter(suite()?.iter(), my_compiler).assert(); Ok(()) } fn compiler( mut builder: pikevm::Builder, -) -> 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>, _>>()?; if !configure_pikevm_builder(test, &mut builder) { return Ok(CompiledRegex::skip()); } let re = builder.build_many(®exes)?; let mut cache = re.create_cache(); - Ok(CompiledRegex::compiled(move |test| -> Vec<TestResult> { + Ok(CompiledRegex::compiled(move |test| -> TestResult { run_test(&re, &mut cache, test) })) } @@ -46,35 +69,59 @@ fn run_test( re: &PikeVM, cache: &mut pikevm::Cache, test: &RegexTest, -) -> Vec<TestResult> { - // let is_match = if re.is_match(cache, 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 => { - TestResult::skip().name("find_earliest_iter") - } - TestSearchKind::Leftmost => { - let it = re - .find_leftmost_iter(cache, 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 => { - TestResult::skip().name("find_overlapping_iter") - } - }; - // vec![is_match, find_matches] - vec![find_matches] +) -> TestResult { + let input = create_input(test); + match test.additional_name() { + "is_match" => TestResult::matched(re.is_match(cache, input)), + "find" => match test.search_kind() { + SearchKind::Earliest => { + let it = re + .find_iter(cache, input.earliest(true)) + .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() }, + }); + TestResult::matches(it) + } + SearchKind::Leftmost => { + let it = re + .find_iter(cache, 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() }, + }); + TestResult::matches(it) + } + SearchKind::Overlapping => { + let mut patset = PatternSet::new(re.get_nfa().pattern_len()); + re.which_overlapping_matches(cache, &input, &mut patset); + TestResult::which(patset.iter().map(|p| p.as_usize())) + } + }, + "captures" => match test.search_kind() { + SearchKind::Earliest => { + let it = re + .captures_iter(cache, input.earliest(true)) + .take(test.match_limit().unwrap_or(std::usize::MAX)) + .map(|caps| testify_captures(&caps)); + TestResult::captures(it) + } + SearchKind::Leftmost => { + let it = re + .captures_iter(cache, input) + .take(test.match_limit().unwrap_or(std::usize::MAX)) + .map(|caps| testify_captures(&caps)); + TestResult::captures(it) + } + SearchKind::Overlapping => { + // There is no overlapping PikeVM API that supports captures. + TestResult::skip() + } + }, + name => TestResult::fail(&format!("unrecognized test name: {}", name)), + } } /// Configures the given regex builder with all relevant settings on the given @@ -86,8 +133,11 @@ fn configure_pikevm_builder( test: &RegexTest, builder: &mut pikevm::Builder, ) -> bool { - let pikevm_config = - PikeVM::config().anchored(test.anchored()).utf8(test.utf8()); + let match_kind = match untestify_kind(test.match_kind()) { + None => return false, + Some(k) => k, + }; + let pikevm_config = PikeVM::config().match_kind(match_kind); builder .configure(pikevm_config) .syntax(config_syntax(test)) @@ -97,13 +147,16 @@ fn configure_pikevm_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 parser from a regex test. -fn config_syntax(test: &RegexTest) -> SyntaxConfig { - SyntaxConfig::new() +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()) } |