cassaundra / wildflower

Efficient wildcard matching against strings
MIT License
13 stars 2 forks source link

Matching is incorrect because of lack of backtracking #14

Open orium opened 5 months ago

orium commented 5 months ago

Hi @cassaundra,

I've checked the implementation of the matching algorithm and I've noticed there is no backtracking. For instance, if the pattern is foo*bar and the input foobarbar wildflower will greedily match the bar in the pattern against the first bar of the input (with * matching the empty string), which fails the match. What should happen is that * should match the first bar and the bar in the pattern should match the second bar in the input.

Test reproducing the issue (currently failing):

#[test]
fn test_wildflower_match() {
    let pattern =  wildflower::Pattern::new("foo*bar");

    assert!(pattern.matches("foobarbar"));
}
cassaundra commented 5 months ago

Yeah, I'd be fine implementing backtracking. Will have to take a solid second pass at the algorithm, but there's some other stuff I've been wanting to rewrite anyway.