regex with loop in loop incorrecly matches when it shouldn't

[lukas-code]

Repro

I tried this code:

use logos::Logos;

#[derive(Debug, Logos)]
enum Token {
    #[regex(r"(a*b)*")]
    Foo,
}

fn main() {
    let input = "a";
    for token in Token::lexer(input) {
        println!("{token:?}");
    }
}

The regex (a*b)* should not match the string a, so this program should print Err(()). But Logos incorrectly thinks the regex matches and the program actually prints Ok(Foo).

Analysis

The problem appears to be in the construction of the NFA. For the program above, Logos will currently construct this NFA, which allows a single a to match:

flowchart LR
    s[start]-->2
    2((2))--a-->2((2))
    2((2))--_-->4((4))
    4((4))--b-->2((2))
    4((4))--_-->1((1))
    1((1))-->e[::Foo]

Loading

A possible solution would be to construct an NFA with separate paths for the first and the remaining iterations of the inner loop, such as the following. This way, every a must be eventually followed by a b to match.

flowchart LR
    s[start]-->2
    2((2))--a-->4((4))
    2((2))--_-->5((5))
    4((4))--a-->4((4))
    4((4))--_-->3((3))
    3((3))--b-->2((2))
    5((5))--b-->2((2))
    5((5))--_-->1((1))
    1((1))-->e[::Foo]

Loading

I will submit a PR implementing this approach shortly.