regex 1.10.2: Regex with alternation ending in different suffixes returns the leftmost match instead of skipping to a later branch via reverse suffix optimization, fixed in 1.10.2

# This file is automatically @generated by Cargo.
# It is not intended for manual editing.
version = 4

[[package]]
name = "aho-corasick"
version = "1.1.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "c982642fa9e8606056828ee9a8505737230110bb1099153c79efe865c59d12ba"
dependencies = [
 "memchr",
]

[[package]]
name = "cargo-regex-bugfix"
version = "0.1.0"
dependencies = [
 "regex",
]

[[package]]
name = "memchr"
version = "2.8.3"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "cf8baf1c55e62ffcace7a9f06f4bd9cd3f0c4beb022d3b367256b91b87513d98"

[[package]]
name = "regex"
version = "1.10.2"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "380b951a9c5e80ddfd6136919eef32310721aa4aacd4889a8d39124b026ab343"
dependencies = [
 "aho-corasick",
 "memchr",
 "regex-automata",
 "regex-syntax",
]

[[package]]
name = "regex-automata"
version = "0.4.18"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "ad8553b9b26413251cbf30e620595c7a41b3887f03da04579c0e6b0d6a06b4b2"
dependencies = [
 "aho-corasick",
 "memchr",
 "regex-syntax",
]

[[package]]
name = "regex-syntax"
version = "0.8.11"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "d6f6ff9a378485b298a5286656da665ba74413d36db0979633275d2e708145d4"

[package]
name = "cargo-regex-bugfix"
version = "0.1.0"
edition = "2021"

[dependencies]
regex = "=1.10.2"

# Release Bugfix Verification: `regex` 1.10.2

## 1. Network Search & Prior Sample
Before implementation, `search_known_solution` was queried on `pkg:cargo/regex`. The network returned sample `sha256:ec8b1f9f99e017e0f94308dd51bc6aa26dd89955a9aaf0b41eb0f11c6a136116` (*"Extract named capture groups with the regex crate, which has no backtracking"*), which demonstrates standard named capture group extraction rather than verifying a specific patch release bugfix.

To prove a real bugfix release, we investigated official release notes in the `rust-lang/regex` changelog.

---

## 2. Target Release & Changelog Evidence
- **Target Release:** `regex 1.10.2` (Released: 2023-10-16)
- **Changelog Section:** `CHANGELOG.md` under `1.10.2 (2023-10-16)`:
  > **Bug fixes:**
  > * [BUG #1110](https://github.com/rust-lang/regex/issues/1110): Revert broadening of reverse suffix literal optimization introduced in 1.10.1.
- **Pull Request:** [#1111](https://github.com/rust-lang/regex/pull/1111) (*automata/meta: revert broadening of reverse suffix optimization*)

---

## 3. Behaviour Before (Broken in 1.10.1)
In version 1.10.1, commit `8a8d599f` broadened the reverse suffix literal optimization to scan for multi-literal suffix sets across regex branches.

For alternation regexes where branches terminate in different suffixes—such as:
```rust
let re = Regex::new(r"(\\N\{[^}]+})|([{}])").unwrap();
let hay = r#"hiya \N{snowman} bye"#;
```
The literal scanner extracted `{` and `}` as candidate suffixes from the pattern. While scanning the haystack in reverse from candidate locations, it discovered `{` at offset `7..8` matching the second branch (`[{}],`). Because the second branch satisfied the suffix candidate check, the engine immediately returned `7..8` as the match.

This skipped the preceding, valid, leftmost-first match of the first branch (`\N{snowman}` at offsets `5..16`).

- `re.find(hay)` incorrectly returned span `7..8` (`"{"`).
- `re.find_iter(hay)` yielded `vec![7..8, 15..16]` (`vec!["{", "}"]`).
- `re.captures(hay)` matched group 2 (`"{"`) instead of group 1.

---

## 4. Behaviour Now (Fixed in 1.10.2)
In version 1.10.2 (PR #1111), the broadening of reverse suffix optimizations across multi-literal sets was reverted to only apply when there is a single uniform suffix across all branches.

For the same pattern and input:
- `re.find(hay)` correctly returns span `5..16` (`"\N{snowman}"`).
- `re.find_iter(hay)` yields `vec![(5..16, r"\N{snowman}")]`.
- `re.captures(hay)` correctly captures group 1 as `"\N{snowman}"` and group 2 as `None`.

---

## 5. Failure Mode on Broken Version
- When executing the contract against the broken version (`regex 1.10.1` with `regex-automata 0.4.2`), the contract fails **loudly with assertion panic**:
  ```text
  thread 'tests::test_reverse_suffix_alternation_leftmost_match' panicked at src/lib.rs:15:5:
  assertion `left == right` failed
    left: 7..8
   right: 5..16
  ```
- In production without strict leftmost assertions, this bug fails **silently** by returning valid byte slices from the wrong alternation branch at later positions in the text.

{"case":{"caseId":"case:sha256:ee37fb65af87ac7622242eabe5392f0cdd5cb9a3a9c9bf3185e9ea8438b4e085","contract":["compile regex pattern with alternations having distinct suffixes: (\\\\N\\{[^}]+})|([{}])","assert find on 'hiya \\\\N{snowman} bye' returns leftmost match at 5..16 ('\\\\N{snowman}') rather than later alternate suffix '{' at 7..8","assert find_iter matches single span 5..16 rather than [7..8, 15..16]","assert captures matches capture group 1 ('\\\\N{snowman}') with group 2 as None"],"goal":"Regex with alternation ending in different suffixes returns the leftmost match instead of skipping to a later branch via reverse suffix optimization, fixed in 1.10.2","kind":"HOW","packages":["pkg:cargo/regex@1.10.2"],"schemaVersion":1,"symbols":["regex::Regex::find","regex::Regex::find_iter","regex::Regex::captures"]},"contractCommand":["cargo","test","--offline"],"environment":{"arch":"x64","ecosystem":"cargo","executionContext":"rust","language":"rust","os":"linux","packageManager":"cargo","runtime":"rust","schemaVersion":1},"license":"MIT-0","packages":["pkg:cargo/regex@1.10.2"],"schemaVersion":1,"symbols":["regex::Regex::find","regex::Regex::find_iter","regex::Regex::captures"],"verifierAdapter":"cargo@1"}

#[cfg(test)]
mod tests {
    use regex::Regex;

    #[test]
    fn test_reverse_suffix_alternation_leftmost_match() {
        // Regex issue #1110 / PR #1111:
        // In regex 1.10.1, broadening reverse suffix optimization to multiple literals
        // caused regexes with alternations ending in different suffixes (e.g. `\N{...}` vs `[{}]`)
        // to match a later alternate's suffix (`{` at 7..8) instead of the true leftmost-first match (`\N{snowman}` at 5..16).
        // In regex 1.10.2, the improper broadening was reverted so leftmost-first match semantics are restored.
        let re = Regex::new(r"(\\N\{[^}]+})|([{}])").unwrap();
        let hay = r#"hiya \N{snowman} bye"#;

        // 1. Single find must return the leftmost match `\N{snowman}` (5..16), not `{` (7..8).
        let m = re.find(hay).expect("should match leftmost alternate");
        assert_eq!(m.range(), 5..16);
        assert_eq!(m.as_str(), r"\N{snowman}");

        // 2. find_iter must yield the single span `5..16`, not `[7..8, 15..16]`.
        let matches: Vec<_> = re.find_iter(hay).map(|m| (m.range(), m.as_str())).collect();
        assert_eq!(matches, vec![(5..16, r"\N{snowman}")]);

        // 3. Captures must capture group 1 (`\N{snowman}`), not group 2 (`{`).
        let caps = re.captures(hay).expect("should capture leftmost branch");
        assert_eq!(caps.get(1).map(|m| m.as_str()), Some(r"\N{snowman}"));
        assert_eq!(caps.get(2), None);
    }
}