nitely / nregex Goto Github PK

Find is always greedy even when non-greedy is specified i.e: a.*?b. This was fixed in nim-regex (nitely/nim-regex#62) which now shares a similar algorithm for the NFA. A very similar fix can be implemented for nregex.

Regex similar to ($|^)\w+ will always return false. Regex similar to ($*)*\w+ won't return an empty capture (or won't always return the right result, I don't remember anymore). This was fixed in nim-regex, see nitely/nim-regex#79 and nitely/nim-regex#84

nim-regex implements a literals optimization that puts it on par with PCRE performance. This is only because the nim-regex NFA engine is pretty slow, as it's is 35x times faster than PCRE in one of the benchmarks where the NFA is not hit much. I think, nregex would be consistently faster than PCRE once the optimization is in place.

However, both find/findAll APIs have quadratic time worst case complexity (linear time best case, though). Granted, PCRE has the same issue in the same situations (and many more). A linear time version would require to track all possible matching states in parallel (NFA style), and it would be slower. Another way may be to transform the expression into re".*regex" where "regex" is the expression, and "dot" matches new lines, that way the regex can start anywhere in the string.

That said, nregex is just a PoC to play around DFAs, so I doubt I'll ever implement this.