Unexpected behavior of ungreedy ?? operator

[vthib]

What version of regex are you using?

1.5.5

Describe the bug at a high level.

Running the regex ab?? on the input ab returns the match ab instead of a.

What are the steps to reproduce the behavior?

fn main() {
    let rx = regex::Regex::new("ab??").unwrap();
    let input = "ab";
    let mat = rx.find(input).unwrap();
    println!("match: {}", &input[mat.range()]);
}

What is the actual behavior?

This program returns: ab

What is the expected behavior?

I expect the output to be a, since ?? is non greedy, it should favor not matching the second letter in the input.

All other implementations i could find matches on a only.

[BurntSushi]

Wow. Yes, this is a bug. I am amazed that this isn't captured by the test suite. Non-greediness itself works (both ab*? and ab+? work as expected), but it looks like ab?? doesn't specifically:

fn main() {
    let rx = regex::Regex::new("ab??").unwrap();
    let input = "abb";
    let mat = rx.find(input).unwrap();
    println!("match: {}", &input[mat.range()]);
    
    let rx = regex::Regex::new("ab+?").unwrap();
    let input = "abb";
    let mat = rx.find(input).unwrap();
    println!("match: {}", &input[mat.range()]);
    
    let rx = regex::Regex::new("ab*?").unwrap();
    let input = "abb";
    let mat = rx.find(input).unwrap();
    println!("match: {}", &input[mat.range()]);
}

Outputs:

match: ab
match: ab
match: a

Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=da2560ea6ce7655338ef34101cf5eab3

[BurntSushi]

Gah. This is another literal optimization bug. They are going to be the death of me. The regex \wab?? correctly reports [0, 2) as a match against Zab. That \w defeats literal optimizations and just runs the regex engine.

[BurntSushi]

This actually a regression that was introduced in regex 1.1.8 in f43beb3. regex 1.1.7 handles this case correctly.

[BurntSushi]

OK, so I at least understand the root cause. The root issue seems to be the order of literals extracted from the regex. For example:

$ regex-debug prefixes -a 'ab??'
Complete(ab)
Complete(a)

Since both literals are marked as "complete" (which means that if a match is found we can report a match for the overall regex and avoid using the regex engine to confirm the match), which is correct in this case, the regex crate will divert to using Aho-Corasick for this. It correctly uses "leftmost first" match semantics, which matches how the regex crate does things. But since ab comes before a, it means that a match of ab will take priority over a. That's correct for the regex ab? but wrong for ab??.

So why does ab*? and ab+? work as expected? Well, let's take a look at the prefix literals extracted for them:

$ regex-debug prefixes -a 'ab*?'
Cut(ab)
Complete(a)

$ regex-debug prefixes -a 'ab+?'
Cut(ab)

The latter is correct. The former generates literals in the wrong order, but since once of them is Cut (meaning we need the regex engine to confirm the match), we can't just divert to Aho-Corasick complete. Aho-Corasick will still prefer ab matches, but then it will ask the regex engine to confirm the match which will correctly report a, thus masking the bug.

Interestingly, despite the regex ab{0,1}? being equivalent to ab??, it does not exhibit this bug and correctly matches a in ab. The key is that the prefixes extracted from it actually appear to be different than what is extracted from ab??:

$ regex-debug prefixes -a 'ab{0,1}?'
Cut(ab)
Complete(a)

This is actually because in the code, the literal extraction isn't perfect and we treat bounded repetitions slightly differently. In this case, any bounded repetition e{minimum,maximum} with minimum == 0 is interpreted as e*:

fn repeat_range_literals<F: FnMut(&Hir, &mut Literals)>(
    e: &Hir,
    min: u32,
    max: Option<u32>,
    greedy: bool,
    lits: &mut Literals,
    mut f: F,
) {
    if min == 0 {
        // This is a bit conservative. If `max` is set, then we could
        // treat this as a finite set of alternations. For now, we
        // just treat it as `e*`.
        f(
            &Hir::repetition(hir::Repetition {
                kind: hir::RepetitionKind::ZeroOrMore,
                greedy: greedy,
                hir: Box::new(e.clone()),
            }),
            lits,
        );
    } else {

Since literal extraction is on my list of things to rewrite (the current implementation is quite bad and inscrutable), I'm going to just make an easy fix: treat e?? as e{0,n}, which in turn means we treat e?? as e*? or just e*. This will result in a list of literals where at least one is cut, and thus inhibit the Aho-Corasick optimization (sadly).

[BurntSushi]

This bug is fixed in regex 1.5.6 and regex-syntax 0.6.26.

[vthib]

That was fast! Thanks for the fix and the very detailed explanation!