Repository: rust-lang/regex
Pull request #1038 (2023-07-12 13:56:35)

{pikevm,meta}: fix anchored searches
This PR fixes two distinct bugs discovered by #1036. First, it fixes a bug where the PikeVM did not correctly handle anchored searches in all cases. (It did handle probably most cases, although it is difficult to precisely quantify.) Secondly, it fixes bugs in all three of the "reverse" optimizations in the meta engine. Namely, none of them are active when the regex is anchored. That is, all three assume that they are running unanchored searches. But of course, the API permits the caller to run an anchored search even when the regex itself isn't anchored. We fix that by detecting that case and falling back to the "core" engine which handles it correctly.

We add the case from #1036 as a regression test and also a few other test cases based on it in order to target each of the three reverse optimization code paths.

None of the other engines (backtracker, one-pass DFA, full DFA and lazy DFA) had this problem.


Patch:
diff --git a/regex-automata/src/meta/strategy.rs b/regex-automata/src/meta/strategy.rs
index 2de2c38..aa1d61e 100644
--- a/regex-automata/src/meta/strategy.rs
+++ b/regex-automata/src/meta/strategy.rs
@@ -845,6 +845,14 @@ impl ReverseAnchored {
             );
             return Err(core);
         }
+        // Note that the caller can still request an anchored search even when
+        // the regex isn't anchored at the start. We detect that case in the
+        // search routines below and just fallback to the core engine. This
+        // is fine because both searches are anchored. It's just a matter of
+        // picking one. Falling back to the core engine is a little simpler,
+        // since if we used the reverse anchored approach, we'd have to add an
+        // extra check to ensure the match reported starts at the place where
+        // the caller requested the search to start.
         if core.info.is_always_anchored_start() {
             debug!(
                 "skipping reverse anchored optimization because \
@@ -930,6 +938,9 @@ impl Strategy for ReverseAnchored {
 
     #[cfg_attr(feature = "perf-inline", inline(always))]
     fn search(&self, cache: &mut Cache, input: &Input<'_>) -> Option<Match> {
+        if input.get_anchored().is_anchored() {
+            return self.core.search(cache, input);
+        }
         match self.try_search_half_anchored_rev(cache, input) {
             Err(_err) => {
                 trace!("fast reverse anchored search failed: {}", _err);
@@ -948,6 +959,9 @@ impl Strategy for ReverseAnchored {
         cache: &mut Cache,
         input: &Input<'_>,
     ) -> Option<HalfMatch> {
+        if input.get_anchored().is_anchored() {
+            return self.core.search_half(cache, input);
+        }
         match self.try_search_half_anchored_rev(cache, input) {
             Err(_err) => {
                 trace!("fast reverse anchored search failed: {}", _err);
@@ -973,6 +987,9 @@ impl Strategy for ReverseAnchored {
         input: &Input<'_>,
         slots: &mut [Option<NonMaxUsize>],
     ) -> Option<PatternID> {
+        if input.get_anchored().is_anchored() {
+            return self.core.search_slots(cache, input, slots);
+        }
         match self.try_search_half_anchored_rev(cache, input) {
             Err(_err) => {
                 trace!("fast reverse anchored search failed: {}", _err);
@@ -1034,6 +1051,13 @@ impl ReverseSuffix {
         // requires a reverse scan after a literal match to confirm or reject
         // the match. (Although, in the case of confirmation, it then needs to
         // do another forward scan to find the end position.)
+        //
+        // Note that the caller can still request an anchored search even
+        // when the regex isn't anchored. We detect that case in the search
+        // routines below and just fallback to the core engine. Currently this
+        // optimization assumes all searches are unanchored, so if we do want
+        // to enable this optimization for anchored searches, it will need a
+        // little work to support it.
         if core.info.is_always_anchored_start() {
             debug!(
                 "skipping reverse suffix optimization because \
@@ -1211,6 +1235,9 @@ impl Strategy for ReverseSuffix {
 
     #[cfg_attr(feature = "perf-inline", inline(always))]
     fn search(&self, cache: &mut Cache, input: &Input<'_>) -> Option<Match> {
+        if input.get_anchored().is_anchored() {
+            return self.core.search(cache, input);
+        }
         match self.try_search_half_start(cache, input) {
             Err(RetryError::Quadratic(_err)) => {
                 trace!("reverse suffix optimization failed: {}", _err);
@@ -1255,6 +1282,9 @@ impl Strategy for ReverseSuffix {
         cache: &mut Cache,
         input: &Input<'_>,
     ) -> Option<HalfMatch> {
+        if input.get_anchored().is_anchored() {
+            return self.core.search_half(cache, input);
+        }
         match self.try_search_half_start(cache, input) {
             Err(RetryError::Quadratic(_err)) => {
                 trace!("reverse suffix half optimization failed: {}", _err);
@@ -1309,6 +1339,9 @@ impl Strategy for ReverseSuffix {
         input: &Input<'_>,
         slots: &mut [Option<NonMaxUsize>],
     ) -> Option<PatternID> {
+        if input.get_anchored().is_anchored() {
+            return self.core.search_slots(cache, input, slots);
+        }
         if !self.core.is_capture_search_needed(slots.len()) {
             trace!("asked for slots unnecessarily, trying fast path");
             let m = self.search(cache, input)?;
@@ -1396,6 +1429,13 @@ impl ReverseInner {
         // or when the literal scan matches. If it matches, then confirming the
         // match requires a reverse scan followed by a forward scan to confirm
         // or reject, which is a fair bit of work.
+        //
+        // Note that the caller can still request an anchored search even
+        // when the regex isn't anchored. We detect that case in the search
+        // routines below and just fallback to the core engine. Currently this
+        // optimization assumes all searches are unanchored, so if we do want
+        // to enable this optimization for anchored searches, it will need a
+        // little work to support it.
         if core.info.is_always_anchored_start() {
             debug!(
                 "skipping reverse inner optimization because \
@@ -1635,6 +1675,9 @@ impl Strategy for ReverseInner {
 
     #[cfg_attr(feature = "perf-inline", inline(always))]
     fn search(&self, cache: &mut Cache, input: &Input<'_>) -> Option<Match> {
+        if input.get_anchored().is_anchored() {
+            return self.core.search(cache, input);
+        }
         match self.try_search_full(cache, input) {
             Err(RetryError::Quadratic(_err)) => {
                 trace!("reverse inner optimization failed: {}", _err);
@@ -1654,6 +1697,9 @@ impl Strategy for ReverseInner {
         cache: &mut Cache,
         input: &Input<'_>,
     ) -> Option<HalfMatch> {
+        if input.get_anchored().is_anchored() {
+            return self.core.search_half(cache, input);
+        }
         match self.try_search_full(cache, input) {
             Err(RetryError::Quadratic(_err)) => {
                 trace!("reverse inner half optimization failed: {}", _err);
@@ -1675,6 +1721,9 @@ impl Strategy for ReverseInner {
         input: &Input<'_>,
         slots: &mut [Option<NonMaxUsize>],
     ) -> Option<PatternID> {
+        if input.get_anchored().is_anchored() {
+            return self.core.search_slots(cache, input, slots);
+        }
         if !self.core.is_capture_search_needed(slots.len()) {
             trace!("asked for slots unnecessarily, trying fast path");
             let m = self.search(cache, input)?;
diff --git a/regex-automata/src/nfa/thompson/pikevm.rs b/regex-automata/src/nfa/thompson/pikevm.rs
index d737fb7..79ce3c6 100644
--- a/regex-automata/src/nfa/thompson/pikevm.rs
+++ b/regex-automata/src/nfa/thompson/pikevm.rs
@@ -1356,7 +1356,15 @@ impl PikeVM {
             // matches their behavior. (Generally, 'allmatches' is useful for
             // overlapping searches or leftmost anchored searches to find the
             // longest possible match by ignoring match priority.)
-            if !pid.is_some() || allmatches {
+            //
+            // Additionally, when we're running an anchored search, this
+            // epsilon closure should only be computed at the beginning of the
+            // search. If we re-computed it at every position, we would be
+            // simulating an unanchored search when we were tasked to perform
+            // an anchored search.
+            if (!pid.is_some() || allmatches)
+                && (!anchored || at == input.start())
+            {
                 // Since we are adding to the 'curr' active states and since
                 // this is for the start ID, we use a slots slice that is
                 // guaranteed to have the right length but where every element


Test patch:
diff --git a/testdata/anchored.toml b/testdata/anchored.toml
index cca561d..0f2248d 100644
--- a/testdata/anchored.toml
+++ b/testdata/anchored.toml
@@ -69,3 +69,59 @@ haystack = 'abcβ'
 matches = [[0, 3]]
 anchored = true
 unicode = false
+
+# Tests that '.c' doesn't match 'abc' when performing an anchored search from
+# the beginning of the haystack. This test found two different bugs in the
+# PikeVM and the meta engine.
+[[test]]
+name = "no-match-at-start"
+regex = '.c'
+haystack = 'abc'
+matches = []
+anchored = true
+
+# Like above, but at a non-zero start offset.
+[[test]]
+name = "no-match-at-start-bounds"
+regex = '.c'
+haystack = 'aabc'
+bounds = [1, 4]
+matches = []
+anchored = true
+
+# This is like no-match-at-start, but hits the "reverse inner" optimization
+# inside the meta engine. (no-match-at-start hits the "reverse suffix"
+# optimization.)
+[[test]]
+name = "no-match-at-start-reverse-inner"
+regex = '.c[a-z]'
+haystack = 'abcz'
+matches = []
+anchored = true
+
+# Like above, but at a non-zero start offset.
+[[test]]
+name = "no-match-at-start-reverse-inner-bounds"
+regex = '.c[a-z]'
+haystack = 'aabcz'
+bounds = [1, 5]
+matches = []
+anchored = true
+
+# Same as no-match-at-start, but applies to the meta engine's "reverse
+# anchored" optimization.
+[[test]]
+name = "no-match-at-start-reverse-anchored"
+regex = '.c[a-z]$'
+haystack = 'abcz'
+matches = []
+anchored = true
+
+# Like above, but at a non-zero start offset.
+[[test]]
+name = "no-match-at-start-reverse-anchored-bounds"
+regex = '.c[a-z]$'
+haystack = 'aabcz'
+bounds = [1, 5]
+matches = []
+anchored = true