BioJulia / Automa.jl

A julia code generator for regular expressions
Other
188 stars 15 forks source link

Optimisation: Only check disambiguating preconditions once #123

Open jakobnissen opened 1 year ago

jakobnissen commented 1 year ago

In Automa v1, the following code:

machine = let
    a = precond!(onenter!(re"XY", :a), :c)
    b = precond!(onenter!(re"XZ", :b), :c; bool=false)
    compile(a | b)
end;

Does not create an ambiguous NFA and thus compiles perfectly fine. However, the precondition :c is needlessly checked twice: First to check if it's true when entering a, then to check if it's false when entering b.

This needs to be optimised: When Automa detects that there are two edges which are only disambiguated by a precondition, emit code along the lines of this pseudocode

if byte in $(intersection(edge1, edge2))
    if $(precond)
        @goto a
    else
        @goto a
    end
else if byte in [ other edges... ]
[ ... ]