vendor/regex-automata-0.4.3/tests/hybrid/suite.rs - toolchain/rustc - Git at Google

 use {
     anyhow::Result,
     regex_automata::{
         hybrid::{
             dfa::{OverlappingState, DFA},
             regex::{self, Regex},
         },
         nfa::thompson,
         util::{prefilter::Prefilter, syntax},
         Anchored, Input, PatternSet,
     },
     regex_test::{
         CompiledRegex, Match, RegexTest, SearchKind, Span, TestResult,
         TestRunner,
     },
 };

 use crate::{create_input, suite, untestify_kind};

 const EXPANSIONS: &[&str] = &["is_match", "find", "which"];

 /// Tests the default configuration of the hybrid NFA/DFA.
 #[test]
 fn default() -> Result<()> {
     let builder = Regex::builder();
     TestRunner::new()?
         .expand(EXPANSIONS, |t| t.compiles())
         // Without NFA shrinking, this test blows the default cache capacity.
         .blacklist("expensive/regression-many-repeat-no-stack-overflow")
         .test_iter(suite()?.iter(), compiler(builder))
         .assert();
     Ok(())
 }

 /// Tests the hybrid NFA/DFA 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 = Regex::builder();
         builder.dfa(DFA::config().prefilter(pre));
         compiler(builder)(test, regexes)
     };
     TestRunner::new()?
         .expand(EXPANSIONS, |t| t.compiles())
         // Without NFA shrinking, this test blows the default cache capacity.
         .blacklist("expensive/regression-many-repeat-no-stack-overflow")
         .test_iter(suite()?.iter(), my_compiler)
         .assert();
     Ok(())
 }

 /// Tests the hybrid NFA/DFA with NFA shrinking enabled.
 ///
 /// This is *usually* not the configuration one wants for a lazy DFA. NFA
 /// shrinking is mostly only advantageous when building a full DFA since it
 /// can sharply decrease the amount of time determinization takes. But NFA
 /// shrinking is itself otherwise fairly expensive currently. Since a lazy DFA
 /// has no compilation time (other than for building the NFA of course) before
 /// executing a search, it's usually worth it to forgo NFA shrinking.
 ///
 /// Nevertheless, we test to make sure everything is OK with NFA shrinking. As
 /// a bonus, there are some tests we don't need to skip because they now fit in
 /// the default cache capacity.
 #[test]
 fn nfa_shrink() -> Result<()> {
     let mut builder = Regex::builder();
     builder.thompson(thompson::Config::new().shrink(true));
     TestRunner::new()?
         .expand(EXPANSIONS, |t| t.compiles())
         .test_iter(suite()?.iter(), compiler(builder))
         .assert();
     Ok(())
 }

 /// Tests the hybrid NFA/DFA when 'starts_for_each_pattern' is enabled for all
 /// tests.
 #[test]
 fn starts_for_each_pattern() -> Result<()> {
     let mut builder = Regex::builder();
     builder.dfa(DFA::config().starts_for_each_pattern(true));
     TestRunner::new()?
         .expand(EXPANSIONS, |t| t.compiles())
         // Without NFA shrinking, this test blows the default cache capacity.
         .blacklist("expensive/regression-many-repeat-no-stack-overflow")
         .test_iter(suite()?.iter(), compiler(builder))
         .assert();
     Ok(())
 }

 /// Tests the hybrid NFA/DFA when 'specialize_start_states' is enabled.
 #[test]
 fn specialize_start_states() -> Result<()> {
     let mut builder = Regex::builder();
     builder.dfa(DFA::config().specialize_start_states(true));
     TestRunner::new()?
         .expand(EXPANSIONS, |t| t.compiles())
         // Without NFA shrinking, this test blows the default cache capacity.
         .blacklist("expensive/regression-many-repeat-no-stack-overflow")
         .test_iter(suite()?.iter(), compiler(builder))
         .assert();
     Ok(())
 }

 /// Tests the hybrid NFA/DFA when byte classes are disabled.
 ///
 /// N.B. Disabling byte classes doesn't avoid any indirection at search time.
 /// All it does is cause every byte value to be its own distinct equivalence
 /// class.
 #[test]
 fn no_byte_classes() -> Result<()> {
     let mut builder = Regex::builder();
     builder.dfa(DFA::config().byte_classes(false));
     TestRunner::new()?
         .expand(EXPANSIONS, |t| t.compiles())
         // Without NFA shrinking, this test blows the default cache capacity.
         .blacklist("expensive/regression-many-repeat-no-stack-overflow")
         .test_iter(suite()?.iter(), compiler(builder))
         .assert();
     Ok(())
 }

 /// Tests that hybrid NFA/DFA never clears its cache for any test with the
 /// default capacity.
 ///
 /// N.B. If a regex suite test is added that causes the cache to be cleared,
 /// then this should just skip that test. (Which can be done by calling the
 /// 'blacklist' method on 'TestRunner'.)
 #[test]
 fn no_cache_clearing() -> Result<()> {
     let mut builder = Regex::builder();
     builder.dfa(DFA::config().minimum_cache_clear_count(Some(0)));
     TestRunner::new()?
         .expand(EXPANSIONS, |t| t.compiles())
         // Without NFA shrinking, this test blows the default cache capacity.
         .blacklist("expensive/regression-many-repeat-no-stack-overflow")
         .test_iter(suite()?.iter(), compiler(builder))
         .assert();
     Ok(())
 }

 /// Tests the hybrid NFA/DFA when the minimum cache capacity is set.
 #[test]
 fn min_cache_capacity() -> Result<()> {
     let mut builder = Regex::builder();
     builder
         .dfa(DFA::config().cache_capacity(0).skip_cache_capacity_check(true));
     TestRunner::new()?
         .expand(EXPANSIONS, |t| t.compiles())
         .test_iter(suite()?.iter(), compiler(builder))
         .assert();
     Ok(())
 }

 fn compiler(
     mut builder: regex::Builder,
 ) -> impl FnMut(&RegexTest, &[String]) -> Result<CompiledRegex> {
     move |test, regexes| {
         // 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))?);
         }

         // Check if our regex contains things that aren't supported by DFAs.
         // That is, Unicode word boundaries when searching non-ASCII text.
         if !test.haystack().is_ascii() {
             for hir in hirs.iter() {
                 if hir.properties().look_set().contains_word_unicode() {
                     return Ok(CompiledRegex::skip());
                 }
             }
         }
         if !configure_regex_builder(test, &mut builder) {
             return Ok(CompiledRegex::skip());
         }
         let re = builder.build_many(&regexes)?;
         let mut cache = re.create_cache();
         Ok(CompiledRegex::compiled(move |test| -> TestResult {
             run_test(&re, &mut cache, test)
         }))
     }
 }

 fn run_test(
     re: &Regex,
     cache: &mut regex::Cache,
     test: &RegexTest,
 ) -> TestResult {
     let input = create_input(test);
     match test.additional_name() {
         "is_match" => {
             TestResult::matched(re.is_match(cache, 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(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() },
                         }),
                 )
             }
             SearchKind::Overlapping => {
                 try_search_overlapping(re, cache, &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 cache = cache.as_parts_mut().0;
                 let mut patset = PatternSet::new(dfa.pattern_len());
                 dfa.try_which_overlapping_matches(cache, &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
 /// regex test.
 ///
 /// If the regex test has a setting that is unsupported, then this returns
 /// false (implying the test should be skipped).
 fn configure_regex_builder(
     test: &RegexTest,
     builder: &mut regex::Builder,
 ) -> bool {
     let match_kind = match untestify_kind(test.match_kind()) {
         None => return false,
         Some(k) => k,
     };

     let mut dfa_config =
         DFA::config().match_kind(match_kind).unicode_word_boundary(true);
     // 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 {
         dfa_config = dfa_config.starts_for_each_pattern(true);
     }
     builder
         .syntax(config_syntax(test))
         .thompson(config_thompson(test))
         .dfa(dfa_config);
     true
 }

 /// Configuration of a Thompson NFA compiler from a regex test.
 fn config_thompson(test: &RegexTest) -> thompson::Config {
     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) -> 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(
     re: &Regex,
     cache: &mut regex::Cache,
     input: &Input<'_>,
 ) -> Result<TestResult> {
     let mut matches = vec![];
     let mut fwd_state = OverlappingState::start();
     let (fwd_dfa, rev_dfa) = (re.forward(), re.reverse());
     let (fwd_cache, rev_cache) = cache.as_parts_mut();
     while let Some(end) = {
         fwd_dfa.try_search_overlapping_fwd(
             fwd_cache,
             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(
                 rev_cache,
                 &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))
 }
	use {
	anyhow::Result,
	regex_automata::{
	hybrid::{
	dfa::{OverlappingState, DFA},
	regex::{self, Regex},
	},
	nfa::thompson,
	util::{prefilter::Prefilter, syntax},
	Anchored, Input, PatternSet,
	},
	regex_test::{
	CompiledRegex, Match, RegexTest, SearchKind, Span, TestResult,
	TestRunner,
	},
	};

	use crate::{create_input, suite, untestify_kind};

	const EXPANSIONS: &[&str] = &["is_match", "find", "which"];

	/// Tests the default configuration of the hybrid NFA/DFA.
	#[test]
	fn default() -> Result<()> {
	let builder = Regex::builder();
	TestRunner::new()?
	.expand(EXPANSIONS, \|t\| t.compiles())
	// Without NFA shrinking, this test blows the default cache capacity.
	.blacklist("expensive/regression-many-repeat-no-stack-overflow")
	.test_iter(suite()?.iter(), compiler(builder))
	.assert();
	Ok(())
	}

	/// Tests the hybrid NFA/DFA 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 = Regex::builder();
	builder.dfa(DFA::config().prefilter(pre));
	compiler(builder)(test, regexes)
	};
	TestRunner::new()?
	.expand(EXPANSIONS, \|t\| t.compiles())
	// Without NFA shrinking, this test blows the default cache capacity.
	.blacklist("expensive/regression-many-repeat-no-stack-overflow")
	.test_iter(suite()?.iter(), my_compiler)
	.assert();
	Ok(())
	}

	/// Tests the hybrid NFA/DFA with NFA shrinking enabled.
	///
	/// This is usually not the configuration one wants for a lazy DFA. NFA
	/// shrinking is mostly only advantageous when building a full DFA since it
	/// can sharply decrease the amount of time determinization takes. But NFA
	/// shrinking is itself otherwise fairly expensive currently. Since a lazy DFA
	/// has no compilation time (other than for building the NFA of course) before
	/// executing a search, it's usually worth it to forgo NFA shrinking.
	///
	/// Nevertheless, we test to make sure everything is OK with NFA shrinking. As
	/// a bonus, there are some tests we don't need to skip because they now fit in
	/// the default cache capacity.
	#[test]
	fn nfa_shrink() -> Result<()> {
	let mut builder = Regex::builder();
	builder.thompson(thompson::Config::new().shrink(true));
	TestRunner::new()?
	.expand(EXPANSIONS, \|t\| t.compiles())
	.test_iter(suite()?.iter(), compiler(builder))
	.assert();
	Ok(())
	}

	/// Tests the hybrid NFA/DFA when 'starts_for_each_pattern' is enabled for all
	/// tests.
	#[test]
	fn starts_for_each_pattern() -> Result<()> {
	let mut builder = Regex::builder();
	builder.dfa(DFA::config().starts_for_each_pattern(true));
	TestRunner::new()?
	.expand(EXPANSIONS, \|t\| t.compiles())
	// Without NFA shrinking, this test blows the default cache capacity.
	.blacklist("expensive/regression-many-repeat-no-stack-overflow")
	.test_iter(suite()?.iter(), compiler(builder))
	.assert();
	Ok(())
	}

	/// Tests the hybrid NFA/DFA when 'specialize_start_states' is enabled.
	#[test]
	fn specialize_start_states() -> Result<()> {
	let mut builder = Regex::builder();
	builder.dfa(DFA::config().specialize_start_states(true));
	TestRunner::new()?
	.expand(EXPANSIONS, \|t\| t.compiles())
	// Without NFA shrinking, this test blows the default cache capacity.
	.blacklist("expensive/regression-many-repeat-no-stack-overflow")
	.test_iter(suite()?.iter(), compiler(builder))
	.assert();
	Ok(())
	}

	/// Tests the hybrid NFA/DFA when byte classes are disabled.
	///
	/// N.B. Disabling byte classes doesn't avoid any indirection at search time.
	/// All it does is cause every byte value to be its own distinct equivalence
	/// class.
	#[test]
	fn no_byte_classes() -> Result<()> {
	let mut builder = Regex::builder();
	builder.dfa(DFA::config().byte_classes(false));
	TestRunner::new()?
	.expand(EXPANSIONS, \|t\| t.compiles())
	// Without NFA shrinking, this test blows the default cache capacity.
	.blacklist("expensive/regression-many-repeat-no-stack-overflow")
	.test_iter(suite()?.iter(), compiler(builder))
	.assert();
	Ok(())
	}

	/// Tests that hybrid NFA/DFA never clears its cache for any test with the
	/// default capacity.
	///
	/// N.B. If a regex suite test is added that causes the cache to be cleared,
	/// then this should just skip that test. (Which can be done by calling the
	/// 'blacklist' method on 'TestRunner'.)
	#[test]
	fn no_cache_clearing() -> Result<()> {
	let mut builder = Regex::builder();
	builder.dfa(DFA::config().minimum_cache_clear_count(Some(0)));
	TestRunner::new()?
	.expand(EXPANSIONS, \|t\| t.compiles())
	// Without NFA shrinking, this test blows the default cache capacity.
	.blacklist("expensive/regression-many-repeat-no-stack-overflow")
	.test_iter(suite()?.iter(), compiler(builder))
	.assert();
	Ok(())
	}

	/// Tests the hybrid NFA/DFA when the minimum cache capacity is set.
	#[test]
	fn min_cache_capacity() -> Result<()> {
	let mut builder = Regex::builder();
	builder
	.dfa(DFA::config().cache_capacity(0).skip_cache_capacity_check(true));
	TestRunner::new()?
	.expand(EXPANSIONS, \|t\| t.compiles())
	.test_iter(suite()?.iter(), compiler(builder))
	.assert();
	Ok(())
	}

	fn compiler(
	mut builder: regex::Builder,
	) -> impl FnMut(&RegexTest, &[String]) -> Result<CompiledRegex> {
	move \|test, regexes\| {
	// 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))?);
	}

	// Check if our regex contains things that aren't supported by DFAs.
	// That is, Unicode word boundaries when searching non-ASCII text.
	if !test.haystack().is_ascii() {
	for hir in hirs.iter() {
	if hir.properties().look_set().contains_word_unicode() {
	return Ok(CompiledRegex::skip());
	}
	}
	}
	if !configure_regex_builder(test, &mut builder) {
	return Ok(CompiledRegex::skip());
	}
	let re = builder.build_many(&regexes)?;
	let mut cache = re.create_cache();
	Ok(CompiledRegex::compiled(move \|test\| -> TestResult {
	run_test(&re, &mut cache, test)
	}))
	}
	}

	fn run_test(
	re: &Regex,
	cache: &mut regex::Cache,
	test: &RegexTest,
	) -> TestResult {
	let input = create_input(test);
	match test.additional_name() {
	"is_match" => {
	TestResult::matched(re.is_match(cache, 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(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() },
	}),
	)
	}
	SearchKind::Overlapping => {
	try_search_overlapping(re, cache, &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 cache = cache.as_parts_mut().0;
	let mut patset = PatternSet::new(dfa.pattern_len());
	dfa.try_which_overlapping_matches(cache, &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
	/// regex test.
	///
	/// If the regex test has a setting that is unsupported, then this returns
	/// false (implying the test should be skipped).
	fn configure_regex_builder(
	test: &RegexTest,
	builder: &mut regex::Builder,
	) -> bool {
	let match_kind = match untestify_kind(test.match_kind()) {
	None => return false,
	Some(k) => k,
	};

	let mut dfa_config =
	DFA::config().match_kind(match_kind).unicode_word_boundary(true);
	// 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 {
	dfa_config = dfa_config.starts_for_each_pattern(true);
	}
	builder
	.syntax(config_syntax(test))
	.thompson(config_thompson(test))
	.dfa(dfa_config);
	true
	}

	/// Configuration of a Thompson NFA compiler from a regex test.
	fn config_thompson(test: &RegexTest) -> thompson::Config {
	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) -> 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(
	re: &Regex,
	cache: &mut regex::Cache,
	input: &Input<'_>,
	) -> Result<TestResult> {
	let mut matches = vec![];
	let mut fwd_state = OverlappingState::start();
	let (fwd_dfa, rev_dfa) = (re.forward(), re.reverse());
	let (fwd_cache, rev_cache) = cache.as_parts_mut();
	while let Some(end) = {
	fwd_dfa.try_search_overlapping_fwd(
	fwd_cache,
	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(
	rev_cache,
	&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))
	}