State of the State::Dense/DenseTransition

[jorickert]

Hello,
I'm currently working on a new, NFA based regex engine and I'm using the excellent regex-syntax crate together with regex-automatas NFA to parse the regex into an NFA that is consumed by my engine.

Hereby I noticed that the NFA States can contain a DenseTransition, which is handled by the ThompsonVM.

But it is not possible to create such a DenseTransition and comments indicate that it is currently unused

This is IMO a bit unfortunate, as it makes it impossible to implement Sparse- to Dense-Transition transformations or to test the implementation and potential benefits of DenseTransition support in alternative VMs.

Do you think it could make sense to allow the construction of DenseTransitions, even if they are not used by the NFA compiler/builder right now?

Thank you for all the work with this library

[BurntSushi]

Unsure. Can you come up with a real benchmark where sparse vs dense matters? If so, then I would be more inclined to open it up.

[jorickert]

Okay, i will look if I can find a case where a dense transition has performance benefits