Repository: rust-lang/regex (rust)

Issue:
broadening of reverse suffix optimization has led to incorrect matches
Specifically, this program succeeds in `regex 1.9.x` but fails in `regex 1.10.1`:

```rust
fn main() -> anyhow::Result<()> {
    let re = regex::Regex::new(r"(\\N\{[^}]+})|([{}])").unwrap();
    let hay = r#"hiya \N{snowman} bye"#;
    let matches = re.find_iter(hay).map(|m| m.range()).collect::<Vec<_>>();
    assert_eq!(matches, vec![5..16]);
    Ok(())
}
```

Its output with `1.10.1`:

```
$ cargo run -q
thread 'main' panicked at main.rs:7:5:
assertion `left == right` failed
  left: [7..8, 15..16]
 right: [5..16]
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
```

I believe the issue here was my change to broaden the reverse suffix optimization to use one of many possible literals. But this turns out to be not be quite correct since the rules that govern prefixes don't apply to suffixes. In this case, the literal optimization extracts `{` and `}` as suffixes. It looks for a `{` first and finds a match at that position via the second alternate in the regex. But this winds up missing the match that came before it with the first alternate since the `{` isn't a suffix of the first alternate.

This is why we should, at least at present, only use this optimization when there is a non-empty longest common suffix. In that case, and only that case, we know that it is a suffix of every possible path through the regex.

Thank you to @charliermarsh for finding this! See: https://github.com/astral-sh/ruff/pull/7980

Pull request description:
automata/meta: revert broadening of reverse suffix optimization
This reverts commit 8a8d599f9d2f2d78e9ad84e4084788c2d563afa5 and includes a regression test, as well as a tweak to a log message.

Essentially, the broadening was improper. We have to be careful when dealing with suffixes as opposed to prefixes. Namely, my logic previously was that the broadening was okay because we were already doing it for the reverse inner optimization. But the reverse inner optimization works with prefixes, not suffixes. So the comparison wasn't quite correct.

This goes back to only applying the reverse suffix optimization when there is a non-empty single common suffix.

Fixes #1110, Ref https://github.com/astral-sh/ruff/pull/7980

Patch:
diff --git a/regex-automata/src/meta/strategy.rs b/regex-automata/src/meta/strategy.rs
index 4cb3b29..04f2ba3 100644
--- a/regex-automata/src/meta/strategy.rs
+++ b/regex-automata/src/meta/strategy.rs
@@ -1167,21 +1167,34 @@ impl ReverseSuffix {
             return Err(core);
         }
         let kind = core.info.config().get_match_kind();
-        let suffixseq = crate::util::prefilter::suffixes(kind, hirs);
-        let Some(suffixes) = suffixseq.literals() else {
-            debug!(
-                "skipping reverse suffix optimization because \
-                 the extract suffix sequence is not finite",
-            );
-            return Err(core);
+        let suffixes = crate::util::prefilter::suffixes(kind, hirs);
+        let lcs = match suffixes.longest_common_suffix() {
+            None => {
+                debug!(
+                    "skipping reverse suffix optimization because \
+                     a longest common suffix could not be found",
+                );
+                return Err(core);
+            }
+            Some(lcs) if lcs.is_empty() => {
+                debug!(
+                    "skipping reverse suffix optimization because \
+                     the longest common suffix is the empty string",
+                );
+                return Err(core);
+            }
+            Some(lcs) => lcs,
         };
-        let Some(pre) = Prefilter::new(kind, suffixes) else {
-            debug!(
-                "skipping reverse suffix optimization because \
+        let pre = match Prefilter::new(kind, &[lcs]) {
+            Some(pre) => pre,
+            None => {
+                debug!(
+                    "skipping reverse suffix optimization because \
                      a prefilter could not be constructed from the \
                      longest common suffix",
-            );
-            return Err(core);
+                );
+                return Err(core);
+            }
         };
         if !pre.is_fast() {
             debug!(
@@ -1268,7 +1281,7 @@ impl ReverseSuffix {
             e.try_search_half_rev_limited(&input, min_start)
         } else if let Some(e) = self.core.hybrid.get(&input) {
             trace!(
-                "using lazy DFA for reverse inner search at {:?}, \
+                "using lazy DFA for reverse suffix search at {:?}, \
                  but will be stopped at {} to avoid quadratic behavior",
                 input.get_span(),
                 min_start,


Test patch:
diff --git a/testdata/regression.toml b/testdata/regression.toml
index 2954c91..53b0701 100644
--- a/testdata/regression.toml
+++ b/testdata/regression.toml
@@ -813,3 +813,18 @@ name = "hir-optimization-out-of-order-class"
 regex = '^[[:alnum:]./-]+$'
 haystack = "a-b"
 matches = [[0, 3]]
+
+# This is a regression test for an improper reverse suffix optimization. This
+# occurred when I "broadened" the applicability of the optimization to include
+# multiple possible literal suffixes instead of only sticking to a non-empty
+# longest common suffix. It turns out that, at least given how the reverse
+# suffix optimization works, we need to stick to the longest common suffix for
+# now.
+#
+# See: https://github.com/rust-lang/regex/issues/1110
+# See also: https://github.com/astral-sh/ruff/pull/7980
+[[test]]
+name = 'improper-reverse-suffix-optimization'
+regex = '(\\N\{[^}]+})|([{}])'
+haystack = 'hiya \N{snowman} bye'
+matches = [[[5, 16], [5, 16], []]]