Determining dead state without using next_eoi_state() for streaming

[mehdi-pplx]

I am trying to handle the case of matching regexes while streaming text input, and outputting matches as early as possible, with the possibility that more input might be added. To accomplish this, I am using regex-automata and iterating through my input character-by-character. However because of the one-byte-behind nature of the DFA I cannot easily distinguish determine if the DFA is in a terminal state after running through all currently available input.

For instance, suppose I have a DFA based on r"\n---\n+" and I feed it "\n---\na". In this case, I am in a terminal state and know that the match I have found is the longest possible but with the current API it seems not easily possible to do this? I am able to workaround this by running through all possible transitions from the current state and checking that they are all dead. So I guess my question is, is this workaround valid/correct? And if so, is there an easy way to read this from the state table or should I just precompute it?

I created a playground/test case to illustrate what I mean: https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=5e109d8c06def6f4403a573cb184d5fc

Hoping this was clear enough, I've only been using this crate for a couple days so apologies if I misunderstood how to use the API.

[BurntSushi]

The delay just means the match can't be reported until the next byte is fed to it. I don't understand the problem you're having? The program you submitted seems to be working as intended. Please consider providing a program that doesn't work as intended. Perhaps with a failing assertion or a clear explanation of expected output vs actual output.

To be clear, the EOI transition should only be followed when the input is finished and no more bytes will be fed to the state machine.

[mehdi-pplx]

ah sorry, yea the problem I am trying to solve is determining if a DFA is still alive, in the sense that it is meaningful to feed any input to it.

In the example above, after processing "a", I would expect the DFA to be in a dead state but this is not the case, even though all possible transitions from the current state would result in a dead state. Only after sending another character does the DFA enter a dead state, which seems like a bug to me but would be handled correctly in the non-streaming case. Here is a less spammy example that illustrates it: https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=53ba49b064a7a8e071bf8e47cb34ed5a
What is unclear to me is how is_dead_state() is false even though every possible transition from the current state results in a dead state.

[BurntSushi]

It is 100% not a bug. I'm confused as to where you are confused. You already mentioned the 1 byte delay, so you know about that. And that is why there is a delay here. If you extend the input by one more byte, you can see it enter a dead state: https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=5a35c4fd4a94eb64799d392d1cadbac2

Maybe the thing you are confused by is that you as a human can see that the regex can never match. But the engine itself cannot because the 1 byte delay is built into the finite state machine, even when a pattern doesn't have any look around assertions.

[BurntSushi]

For your streaming use case, you just don't report a match until that once extra byte is seen.

[mehdi-pplx]

For your streaming use case, you just don't report a match until that once extra byte is seen.

yeah that makes sense but I also want to know if the dfa should still be considered running (because if it is still running, there could be a longer match with more input).

given that, would this be a good way to check if the dfa cannot match more (in which case, the match we have found is the longest possible)? and then, is there a faster, more supported way by the API (rather than checking all bytes)?

    let mut cannot_match_more = true;
    for byte in 0u8..=255 {
        let next_state = dfa.next_state(state, byte);
        if !dfa.is_dead_state(next_state) {
            cannot_match_more = false;
        }
    }

[BurntSushi]

I believe that will work. You may also need to check the EOI transition to account for the case that the input ends. There is no easier way because everything in this crate operates on a 1 byte delay.

I don't understand why you would want to do this though.

[mehdi-pplx]

The high level problem I'm trying to solve is handle regexes with streaming input, and outputting match success/fail without waiting for more input (if possible).

You may also need to check the EOI transition to account for the case that the input ends.

ahh good point, forgot about that! given that I built a way to support the 3 simple cases of

1. the regex matches, and is maximally satisfied (regex r"abc" and input abc)
2. the regex has already matched on the input and will never again (regex r"abc" and input abcd)
3. the regex has matched and may match again (regex r"\d+" and input 123`)

(playground here: https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=19ea7090da3d8d7372c59b07d616fd38)

one thing that does feel like a bug to me is that after running abcd through the r"abc" regex in anchored mode, it does not enter the dead state after processing d even though it does enter the dead state with the input abd. It feels like the two inputs should do the same thing?