Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

kaizen: Cleanup DFA/NFA #197

Closed
timbray opened this issue Feb 18, 2023 · 1 comment
Closed

kaizen: Cleanup DFA/NFA #197

timbray opened this issue Feb 18, 2023 · 1 comment

Comments

@timbray
Copy link
Owner

timbray commented Feb 18, 2023

I am starting to implement the "suffix" pattern which obviously requires an NFA to implement (as does "shellstyle" and anything slightly regexp-ish). At the moment, Quamina reduces all NFAs to DFAs, which is well-known to be prone to producing O(2**N) explosions of the kind we're seeing in some tests (although it's not obvious this is the source of that problem). Anyhow, the DFA/NFA confusion is adding lots of complexity. We should throw away DFAs and do everything in NFAs. This would have a few benefits, including:

  • lose a lot of code
  • simplify the addPattern code path
  • de-genericize the SmallTable structure - this doesn't seem to be a good use of generics, lots of things are made harder to read and write.
timbray added a commit that referenced this issue May 25, 2024
addresses #197

Signed-off-by: Tim Bray <tbray@textuality.com>
timbray added a commit that referenced this issue May 31, 2024
* kaizen: clean up state finite automata

addresses #197

Signed-off-by: Tim Bray <tbray@textuality.com>

* patch codecov workflow

Signed-off-by: Tim Bray <tbray@textuality.com>

---------

Signed-off-by: Tim Bray <tbray@textuality.com>
@timbray
Copy link
Owner Author

timbray commented May 31, 2024

Fixed in 8833629

@timbray timbray closed this as completed May 31, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant