search

timbray / quamina

Home of Quamina, a fast pattern-matching library in Go
Apache License 2.0
373 stars 18 forks source link

kaizen: clean up state finite automata #308

Closed timbray closed 1 month ago

timbray commented 2 months ago

addresses #197

This gets rid of the DFA/NFA distinction, everything is now an NFA. The stretch goal is to fix #188, but the messy sprawl of DFA-and-NFA was getting in the way of understanding.

This includes a bunch of commented-out code for pretty-printing state machines, which I found totally essential in migrating to all-NFA. I'm going to create an issue to bring this code out of comments and make it possible to switch it off/on to facilitate the creating and merging different kinds of patterns.

timbray commented 2 months ago

I see that I accidentally lost a couple of unit tests, although the coverage didn't go down. Will clean this up subsequently. There's a huge amount of quite difficult work here that I want to get checked in so I have a stable base to continue work on #188 and then some new features.

codecov-commenter commented 1 month ago

Codecov Report

Attention: Patch coverage is 97.80220% with 4 lines in your changes are missing coverage. Please review.

Project coverage is 96.32%. Comparing base (a716bc1) to head (8351137). Report is 68 commits behind head on main.

Files Patch % Lines
nfa.go 94.82% 1 Missing and 2 partials :warning:
shell_style.go 95.45% 1 Missing :warning:

:exclamation: Your organization needs to install the Codecov GitHub app to enable full functionality.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #308 +/- ## ========================================== + Coverage 96.19% 96.32% +0.13% ========================================== Files 17 17 Lines 2129 1634 -495 ========================================== - Hits 2048 1574 -474 + Misses 54 34 -20 + Partials 27 26 -1 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

timbray commented 1 month ago

Having thought about it, I can see why this is a difficult PR to review. It's all down in the finite-automaton weeds and not that many people care about this stuff or have exposure to it. Having said that, a bunch of ugly code was removed and the tests all still pass and I see no performance regression. So I will probably break the rules and go ahead and merge if nobody is up to doing a real review in the next day or so.

embano1 commented 1 month ago

+1