reverse inner literal optimization results in incorrect match offsets in some cases

[Theta-Dev]

What version of regex are you using?

The bug is present in version 1.9.0 and 1.9.1.
1.8.4 was the last working version.

Describe the bug at a high level.

I am using the regex crate for parsing textual video durations and getting the duration in seconds.
After updating the regex crate to version 1.9.0, my regex fails to parse durations with more than 2 hour digits.

The + operator I use for matching an arbitrary amount of hour digits now only matches 1 or 2 digits.

What are the steps to reproduce the behavior?

Regex: (?:(\d+)[:.])?(\d{1,2})[:.](\d{2})

Here is my parsing function.

/// Parse textual video length (e.g. `0:49`, `2:02` or `1:48:18`)
/// and return the duration in seconds.
pub fn parse_video_length(text: &str) -> Option<u32> {
    static VIDEO_LENGTH_REGEX: Lazy<Regex> =
        Lazy::new(|| Regex::new(r#"(?:(\d+)[:.])?(\d{1,2})[:.](\d{2})"#).unwrap());
    VIDEO_LENGTH_REGEX.captures(text).map(|cap| {
        let hrs = cap
            .get(1)
            .and_then(|x| x.as_str().parse::<u32>().ok())
            .unwrap_or_default();
        let min = cap
            .get(2)
            .and_then(|x| x.as_str().parse::<u32>().ok())
            .unwrap_or_default();
        let sec = cap
            .get(3)
            .and_then(|x| x.as_str().parse::<u32>().ok())
            .unwrap_or_default();

        hrs * 3600 + min * 60 + sec
    })
}

What is the actual behavior?

The hour group only matches the number 2, so the parsed duration is 2:12:39 or 7959 seconds

parse_video_length("102:12:39") == Some(7959)

What is the expected behavior?

parse_video_length("102:12:39") == Some(367959)

[BurntSushi]

CLI reproduction:

$ regex-cli find match meta -p '(?:(\d+)[:.])?(\d{1,2})[:.](\d{2})' -y '888:77:66'
     parse time:  27.056µs
 translate time:  9.404µs
build meta time:  263.862µs
    search time:  28.082µs
  total matches:  1
0:1:9:88:77:66

The match should be 0:9 but 1:9 is reported.

This isn't really about + but about a literal optimization. The regex is conceptually broken into three pieces: (?:(\d+)[:.])?(\d{1,2}), [:.] and (\d{2}). The search looks for matches of the [:.] first, which is very quick by virtue of using SIMD acceleration. That first match occurs at &haystack[3]. Then it tries to run a reverse search for (?:(\d+)[:.])?(\d{1,2}). This is where things go wrong. It finds a reverse match at &haystack[1] because the \d{1,2} matches two digits and since the (?:(\d+)[:.])? is overall optional and the [:.] doesn't match at this point, the match is reported at offset 1. Then a forward search is run from that point to find the real end of the match, which finds 9 because a match at &haystack[1..9] exists, but the correct leftmost match is &haystack[0..9].

I'm going to need to think a little bit about how to fix this. It might be something about characterizing regexes that can't be used with the inner literal optimization. Which is unfortunate, but much better than removing the inner literal optimization altogether... Yikes.

[BurntSushi]

This is fixed in regex 1.9.3 and regex-automata 0.3.6 on crates.io.