Repository navigation
Commit 2a6d8f3
committed
nfa: massively simplify leftmost failure transitions
The key insight here is that all we need to do to support leftmost
semantics is to omit ALL failure transitions that appear after a match
state in the trie. (And to omit any entries in the trie that cross a
previously existing match state for leftmost-first semantics, and keep
them for leftmost-longest.)
Previously, I had somehow convinced myself that the subset was more
difficult to identify and required comparing depths. But this is just
not the case. Moreover, once you set the match state to have a failure
transition to the dead state, it automatically propagates to all
subsequent states.
This is such a huge simplification that I combined the 'standard' and
'leftmost' failure transition construction into a single method.
Fixes #921 parent 979cf73 commit 2a6d8f3
3 files changed
Lines changed: 86 additions & 247 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
68 | 68 | | |
69 | 69 | | |
70 | 70 | | |
71 | | - | |
72 | | - | |
73 | | - | |
74 | | - | |
75 | | - | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
76 | 76 | | |
77 | 77 | | |
78 | 78 | | |
| |||
340 | 340 | | |
341 | 341 | | |
342 | 342 | | |
343 | | - | |
| 343 | + | |
344 | 344 | | |
345 | 345 | | |
346 | 346 | | |
| |||
455 | 455 | | |
456 | 456 | | |
457 | 457 | | |
458 | | - | |
| 458 | + | |
459 | 459 | | |
460 | 460 | | |
461 | 461 | | |
| |||
0 commit comments