search

nitely / nim-regex

Pure Nim regex engine. Guarantees linear time matching
https://nitely.github.io/nim-regex/
MIT License
228 stars 21 forks source link

Reorder epsilon transitions #145

Closed nitely closed 5 days ago

nitely commented 6 days ago

Follow up #129

Reorder the epsilon transitions to be evaluated after the matchable node: @[matchable_node_idx, epsilon_transition_idx].

It helps avoiding pointless capts evaluation on regex with alternations: (foo|bar|...). Currently capts are evaluated for all alternations, even if only one matches. Note (foo|bar|...) translates to (foo)|(bar)|... internally to remove epsilon transition states, although all capts refer to the same capt node.

This improves #138 somewhat when using findAll (contains uses the no-capts optimization so no changes there).

This branch:

time nim c -r --threads:off -d:danger tests/test_bug/testbug.nim
compiled
2000
ok

real    0m7.232s
user    0m7.194s
sys     0m0.037s

Master:

time nim c -r --threads:off -d:danger tests/test_bug/testbug.nim
compiled
2000
ok

real    0m19.415s
user    0m20.467s
sys     0m0.270s