How to detect if the state is in a partial (prefix) match state?

[zzl0]

Hi,

Thanks for the awesome regex_automata crate, we've been using it to implement a match_prefix feature in Sapling.

For example, assuming we have a regex pattern r"a/t\d+/", it partially match a/ (i.e. a/ is a prefix of the pattern).

We were able to do that with the following logic in regex-automata = "0.1":

if self.dfa.is_dead_state(state) {
    return Some(false);  // dead state
} else if self.dfa.is_match_state(state) {
    return Some(true);  // match state
}
None  // partially match state (match the prefix)

In the new API of regex-automata = "0.3", it requires an explicit next_eoi_state transition. And after calling next_eoi_state, the state will be the dead state for haystack a/ (I tested with the following code). Is there a way to detect partial (prefix) match in the new version of regex-automata?

use anyhow::Result;

#[test]
fn test_dense_dfa() -> Result<()> {
    use regex_automata::{
        dfa::{dense, Automaton},
        Input,
    };

    let dfa = dense::DFA::new(r"a/t\d+/")?;
    let haystack = "a/";

    let mut state = dfa.start_state_forward(&Input::new(haystack))?;
    for &b in haystack.as_bytes().iter() {
        state = dfa.next_state(state, b);
    }

    state = dfa.next_eoi_state(state);
    assert!(dfa.is_dead_state(state));

    Ok(())
}

#[test]
fn test_lazy_dfa() -> Result<()> {
    use regex_automata::{hybrid::dfa::DFA, Input};

    let dfa = DFA::new(r"a/t\d+/")?;
    let mut cache = dfa.create_cache();
    let haystack = "a/".as_bytes();

    let mut sid = dfa.start_state_forward(&mut cache, &Input::new(haystack))?;
    for &b in haystack {
        sid = dfa.next_state(&mut cache, sid, b)?;
    }

    sid = dfa.next_eoi_state(&mut cache, sid)?;
    assert!(sid.is_dead());

    Ok(())
}

[BurntSushi]

Why do you think the EOI transition is necessary here? You should only call it if you know you've reached the end of input. If you're looking for partial matches, then how do you know when you've reached the end of input? The EOI transition will of course lead to a dead state if it wouldn't otherwise be a match because there is no other transition that can follow it. By invoking the EOI transition you are saying, "there is no more haystack to search." But that doesn't seem to be true.

[zzl0]

Thanks for the prompt reply.

Why do you think the EOI transition is necessary here? You should only call it if you know you've reached the end of input. If you're looking for partial matches, then how do you know when you've reached the end of input?

Sorry for the confusion, our use case is: in order to avoid unnecessary directory scans, we first check if a directory path is a potential match against the pattern, then decide if we need to look into (scan) that directory and do further checks (e.g. check inputs a/t123, a/b). So for the example above:

let dfa = dense::DFA::new(r"a/t\d+/")?;
let haystack = "a/";

In order to decide if we need to look into the directory path a/ (may contains a lot of files and sub directories), we use a/ as the whole input to check if it at least match the prefix of pattern a/t\d+/

By invoking the EOI transition you are saying, "there is no more haystack to search." But that doesn't seem to be true.

When checking directory path a/, it is the whole input and there is no more haystack to search. If a/ matches the prefix of a/t\d+/, we will scan directory a/ and do further checks from scratch, for example, check input a/t123 against the pattern from scratch.

match self.match_prefix("a/") {
    Some(true) => {
        // match state: DirectoryMatch::Everything
    }
    Some(false) => {
        // dead state: DirectoryMatch::Nothing,
    }
    None => {
        // match prefix: DirectoryMatch::ShouldTraverse,
        for path in fs::read_dir("a/").unwarp() {
            // do separate search against paths inside `a/`
            self.match_prefix(path)
        }
    }
};

[BurntSushi]

a/ isn't the whole input though. Because you're treating it conceptually as a prefix to some possibly longer haystack.

Have you tried just not using the eoi transition? The eoi transition exists because some matches can't be known until the end of input is seen.

[zzl0]

Yes, I tried it without using eoi transition. I also expect b/ will enter into a dead state, but it does not work if I don't have a eoi transition:

    fn match_prefix(dfa: &DFA<Vec<u32>>, haystack: &str) -> StateID {
        let mut state = dfa.start_state_forward(&Input::new(haystack)).unwrap();
        for &b in haystack.as_bytes().iter() {
            state = dfa.next_state(state, b);
        }
        state
    }

    let dfa = dense::DFA::new(r"a/t\d+/")?;

    assert!(!dfa.is_special_state(match_prefix(&dfa, "a/")));
    assert!(dfa.is_dead_state(match_prefix(&dfa, "b/"))); // assertion fails

[BurntSushi]

Yes, that's correct, because it looks like you're doing an unanchored search. So that a/t\d/ can match anywhere. Try Input::new(haystack).anchored(Anchored::Yes).

[BurntSushi]

And if you only need to do anchored searches, I would suggest setting dfa::dense::Config::start_kind to StartKind::Anchored, or else your DFA will be approximately twice as big as it needs to be.

[zzl0]

Thanks, I ended up have something like below

fn match_prefix(dfa: &DFA<Vec<u32>>, haystack: &str) -> Option<bool> {
    let mut state = dfa
        .start_state_forward(&Input::new(haystack).anchored(Anchored::Yes))
        .unwrap();
    for &b in haystack.as_bytes().iter() {
        state = dfa.next_state(state, b);
        if dfa.is_dead_state(state) {
            return Some(false);
        } else if dfa.is_match_state(state) {
            return Some(true);
        }
    }

    state = dfa.next_eoi_state(state);
    if dfa.is_match_state(state) {
        return Some(true);
    }
    None
}

let dfa = dense::DFA::builder()
    .configure(DFA::config().start_kind(StartKind::Anchored))
    .build(r"a/t\d+/")?;

assert_eq!(match_prefix(&dfa, "a/"), None);
assert_eq!(match_prefix(&dfa, "b/"), Some(false));
assert_eq!(match_prefix(&dfa, "a/t123/"), Some(true));
assert_eq!(match_prefix(&dfa, "a/t123/a"), Some(true));

In terms of why I thought explicit eoi is required, I misunderstood this comment:

regex/regex-automata/src/lib.rs

Lines 138 to 140 in 431c4e4

	// DFAs in this crate require an explicit
	// end-of-input transition if a search reaches
	// the end of a haystack.

[BurntSushi]

Yeah the key here is really what "haystack" means. In some sense, a/ is your entire haystack. But since you're trying to detect a partial match, it doesn't make sense to say that a/ is the entire haystack since you're explicitly treating it as a prefix to a logically longer haystack.

[BurntSushi]

I also fixed which comment is the answer. The key here is Input::anchored, not Config::start_kind. The former is what instructs the search to be anchored. The latter is "just" saving memory when compared with the default configuration.