Erroneous failure to match in simple regex

[ConnorGray]

The simple regexes ((IMG|MVI|MGG)|DS)X and (((IMG|MVI)|MG)|DS)X both ought to match the string "MVIX, but only the second one does.

extern crate regex;

use regex::{Regex};

fn main() {
    simple_match_1();
    simple_match_2();
}

/// This example working on regex101: https://regex101.com/r/WJgwJ5/1
#[test]
fn simple_match_1() {
    let regex_str = "((IMG|MVI|MG)|DS)X";
    let text = "MVIX";

    let regex: Regex = Regex::new(regex_str).unwrap();

    // These both panic when they shouldn't
    assert!(regex.is_match(text));
    assert!(regex.find(text) != None);
}

/// This example *does not* panic
#[test]
fn simple_match_2() {
    let regex_str = "(((IMG|MVI)|MG)|DS)X";
    let text = "MVIX";

    let regex: Regex = Regex::new(regex_str).unwrap();

    // These both *work* (no panic)
    assert!(regex.is_match(text));
    assert!(regex.find(text) != None);
}

[mbrubeck]

git bisect shows that this is a regression from 55a1fc9.

[mbrubeck]

The minimal test case I've found for this bug is:

assert!(Regex::new("(ABC|CDA|BC)X").unwrap().is_match("CDAX"));

[BurntSushi]

Gah. Probably a bug in the literal optimizations (again).

[BurntSushi]

The problem here is that the literals returned by regex_syntax::Literals::unambiguous_prefixes for (ABC|CDA|BC)X are [Cut(A), Cut(BCX), Complete(CDAX)], which is wrong. Namely, it doesn't satisfy the documented contract of the function:

    /// Any substring match with a member of the set is returned is guaranteed
    /// to never overlap with a substring match of another member of the set
    /// at the same starting position.
    ///
    /// Given any two members of the returned set, neither is a substring of
    /// the other.

... because A is a substring of CDAX.

[BurntSushi]

OK, 0.1.78 should be on crates.io with this fix. @ConnorGray Thanks so much for reporting this! @mbrubeck Thanks so much for minimizing the example. :-)

[ConnorGray]

No problem! :) Thanks for the quick fix!

[ConnorGray]

I'm new to this so maybe I made a mistake, but this seems to still not be working in the original simple_match_1() case after updating to regex 0.1.78 on my machine.

[BurntSushi]

@ConnorGray Wow. Serves me right for trusting the minimal example. Dammit. Your original example does indeed fail. sigh Working on it...

[BurntSushi]

@ConnorGray Derp. The minimal example was good. I just messed up the release. 0.1.79 incoming...

[BurntSushi]

@ConnorGray All right, 0.1.79 is out. Try again? :-)

[ConnorGray]

@BurntSushi Looks good :)

[BurntSushi]

Phew. Thanks for your patience!

[ConnorGray]

Haha no problem, I was surprised it got fixed this quickly!