MatchKind::All matching any input

[chrisduerr]

Hello it's me again with some silly streaming parser question.

I just realized that after updating to the latest regex, parsing for "or" patterns like /github.com|https://github.com (on https://github.com) would no longer match the longest match. I've looked at the configuration options related to greed and similar and the only thing related to this I can find is the MatchKind. Using MatchKind::All fixes this issue and the documentation sounds like this is meant for this kind of issue.

However after switching to MatchKind::All, other searches are now failing. Most notably a search for [a-z]* will literally match everything no matter what you feed into it. I was going to report this as a bug, but I feel like I'm clearly just not understanding what MatchKind::All actuall does.

So is the Config::match_kind method the right solution for my problem, or am I way off?

Just in case this is actually a bug, here's a minimal repro for the odd [a-z]* behavior:

use regex_automata::hybrid::dfa::{Builder, Config};
use regex_automata::nfa::thompson::Config as ThompsonConfig;
use regex_automata::{Input, MatchKind};

fn main() {
    let thompson_config = ThompsonConfig::new();
    let config = Config::new().match_kind(MatchKind::All);
    let dfa = Builder::new().configure(config).thompson(thompson_config).build("[a-z]*").unwrap();
    let mut cache = dfa.create_cache();

    let mut state = dfa.start_state_forward(&mut cache, &Input::new(" abc")).unwrap();

    for c in " abc ".chars() {
        println!("PARSING {c:?}");
        let mut buf = [0; 4];
        let utf8_len = c.encode_utf8(&mut buf).len();
        for b in &buf[..utf8_len] {
            state = dfa.next_state(&mut cache, state, *b).unwrap();

            print!("NEW STATE: {state:?}");
            if state.is_match() {
                println!(" — MATCH");
            } else if state.is_dead() {
                println!(" — DEAD");
            } else {
                println!();
            }
        }
    }

    state = dfa.next_eoi_state(&mut cache, state).unwrap();
    print!("EOI STATE: {state:?}");
    if state.is_match() {
        println!(" — MATCH");
    } else if state.is_dead() {
        println!(" — DEAD");
    } else {
        println!();
    }
}

[chrisduerr]

I just compared my code to the code from 0.1.10 and there I used longest_match to search for the start of the match. This method's documentation also mentions "leftmost-first", so is match_kind its equivalent?

If this is the case, then the documentation of match_kind might be missing some caveats, like unanchored searches not working? This was documented in 0.1.10 at least:
https://docs.rs/regex-automata/0.1.10/regex_automata/dense/struct.Builder.html#method.longest_match

[BurntSushi]

Have you seen this? https://docs.rs/regex-automata/latest/regex_automata/enum.MatchKind.html#all-matches

Also, can you share your 0.1.10 program that got the longest match?

[chrisduerr]

I did not read this, I only read the method documentation. Sounds like I just need to match what I did before instead of using the same dfa (just in reverse) to look for the start.

I definitely do feel like the documentation of 0.1.10 was easier to understand here than the latest one though, since it was much more concise and I didn't have to go hunting in type docs to find important caveats. But docs are hard.

[BurntSushi]

Indeed. The 0.1.x release is also much much much smaller, perhaps by an order of magnitude. It also supports a lot less functionality. The latest release is sprawling, and I tried to make clear in the crate docs that it's an "expert" level crate. The API really doesn't try too hard to prevent you from doing something non-sensible because I'm not sure it's possible to do given the level of configuration I want to expose.

Consider, for example, the number of match_kind methods in 0.3 versus the number of longest_match methods in 0.1. Repeating the varied depth of what match semantics means on each of those methods is not really practical. So it gets moved to one spot.

But yeah, MatchKind::All is what longest_match was. longest_match was itself a very misleading name and it is not the same as leftmost-longest semantics (which aren't supported by regex-automata at all, although it is supported in aho-corasick).

One trick with or patterns, assuming they are all literals, is to use MatchKind::LeftmostFirst but sort the literals in order of descending length before joining them via a |. If you do this, then leftmost-first and leftmost-longest become equivalent. But it only applies to literals.

[chrisduerr]

The API really doesn't try too hard to prevent you from doing something non-sensible because I'm not sure it's possible to do given the level of configuration I want to expose.

As long as you don't mind having me create a new discussion every week that's fine. Though hopefully I've ironed out all the regressions now.

That said, for my usecase at least mentioning that this is useful for finding the start of a match while not useful for unanchored search would have been more useful in the method documentation than the example code (and I love example code).

[BurntSushi]

It does:

LeftmostFirst also supports non-greedy matches using this strategy where as All does not.

Although this requires knowing that unanchored searches rely on a non-greedy (?s-u:.)*? prefix. And there is also a fair bit of discussion about MatchKind::All not being right for leftmost searches and that it's typically for overlapping searches. And there's an example showing its use for start-of-match handling using a reverse DFA.

To be clear, I didn't write the docs this way so that people could ask me questions every week. :-) I wrote them this way because I didn't know how to do it any better in a feasible time frame. I spent three years on this project. Making the API even nicer likely requires more abstraction and I was already concerned about the problem of abstraction in the first place.

I am happy to field questions as time permits. And if you think there is a sentence or two that should go on every match_kind method docs, then a PR is welcome.