Oh i didnt even know of this. But i got a lot of help from this one https://github.com/madler/infgen EDIT: Didnt notice that it’s even by the same person of course it’s very similar
> lazy quantifiers for inclusion into the next release of POSIX That is surprising! We've found that in certain simpler scenarios it's possible to use complement to express lazy quantifiers, but in the general case it…
I have not verified it but i assume matching the whole line grep-style would bypass this problem entirely Since a regex with ^<pattern>$ can not have overlapping matches it should guarantee linearity, given a linear…
It's still O(n * m). The matches are non-overlapping, even if you run a separate engine on the matches post-match it will at most traverse the full input once across all matches.
I don't agree that overlapping matches is the only interpretation of "all matches". it very clearly does return all matches and it removes overlap The post states clearly "finding all leftmost-longest non-overlapping…
I’m still open to it and thinking about it actually. I will explore if it’s possible to eliminate the large losses on common patterns and if it turns out it is then it’s a no brainer. Going forward this and the extended…
Oh that is interesting! I haven't even looked Nim regex until now, is it similar to the approach in Go?
> constraining oneself to fixed-upper-bound-length needles wait! you haven't reached the important part of the post yet
I have not heard of this before, i will have a look!
Haha, you're right about that. I was looking for another word for "default"
Good catch! I changed this to leftmost-longest nonoverlapping matches so it's not misleading
with all-matches semantics it returns a significantly higher number of matches than leftmost greedy. eg. /abc*/ and abccccc will return you matches at ab|c|c|c|c|c| I think it's very common and ok that people reason…
> I would say that regexes that matter in practice, e.g. when digging through logs, have clear boundaries that curb the pathological backtracking behavior I agree with you in the sense that most practical regexes do not…
It is human written and i've thoroughly went over every paragraph but i did use some help with wording. i suppose it does show now that you mention it
The part that makes it difficult is that it doesn't return the same matches, it returns almost the same matches but not exactly. But if PCRE semantics isn't set in stone then i hope leftmost longest could be the default…
Yes, this is entirely possible. you can even explore the automaton eagerly and detect if it's possible to loop from an accepting state to a nonaccepting one. Exciting stuff for future work
Sorry, finished the post just now with more comparisons on other inputs The reason is just that the normal mode is faster in average non pathological cases
Ah, sorry then i misunderstood the comment I'm not sure if it's with both RE2 or Rust, but some internal engines of Rust appear to allocate a fixed buffer that it constantly re-creates states into. I'm not really…
I have experienced this as well, the performance degradation of DFA to NFA is enormous and while not as bad as exponential backtracking, it's close to ReDoS territory. The rust version of the engine…
If you're interested, the rust version is open source now as well: https://github.com/ieviev/resharp
There is plenty still to do. One part of this is SIMD algorithms to better compete with Hyperscan/Rust, another is the decades of optimizations that backtracking engines have for short anchored matches for validation.…
In all honesty it's just never bothered me before and i've havent met many people bothered by it either It's the same thing with dark mode as default, i chose it because it's my own preference and i'd love it…
No, we do not lock reading the state, we only lock the creation side and the transition table reference stays valid during matching even if it is outdated. Only when a nonexistent state is encountered during matching it…
While i completely understand it, the lack of capitalization is just an indication that a human wrote this, it has to be imperfect i see enough slop and Look At Me on a daily basis. i don't want it to look like an ad or…
Yes, most (i think all) lazy DFA engines have a mutable DFA behind a lock internally that grows during matching. Multithreading is generally a non-issue, you just wrap the function that creates the state behind a…
Oh i didnt even know of this. But i got a lot of help from this one https://github.com/madler/infgen EDIT: Didnt notice that it’s even by the same person of course it’s very similar
> lazy quantifiers for inclusion into the next release of POSIX That is surprising! We've found that in certain simpler scenarios it's possible to use complement to express lazy quantifiers, but in the general case it…
I have not verified it but i assume matching the whole line grep-style would bypass this problem entirely Since a regex with ^<pattern>$ can not have overlapping matches it should guarantee linearity, given a linear…
It's still O(n * m). The matches are non-overlapping, even if you run a separate engine on the matches post-match it will at most traverse the full input once across all matches.
I don't agree that overlapping matches is the only interpretation of "all matches". it very clearly does return all matches and it removes overlap The post states clearly "finding all leftmost-longest non-overlapping…
I’m still open to it and thinking about it actually. I will explore if it’s possible to eliminate the large losses on common patterns and if it turns out it is then it’s a no brainer. Going forward this and the extended…
Oh that is interesting! I haven't even looked Nim regex until now, is it similar to the approach in Go?
> constraining oneself to fixed-upper-bound-length needles wait! you haven't reached the important part of the post yet
I have not heard of this before, i will have a look!
Haha, you're right about that. I was looking for another word for "default"
Good catch! I changed this to leftmost-longest nonoverlapping matches so it's not misleading
with all-matches semantics it returns a significantly higher number of matches than leftmost greedy. eg. /abc*/ and abccccc will return you matches at ab|c|c|c|c|c| I think it's very common and ok that people reason…
> I would say that regexes that matter in practice, e.g. when digging through logs, have clear boundaries that curb the pathological backtracking behavior I agree with you in the sense that most practical regexes do not…
It is human written and i've thoroughly went over every paragraph but i did use some help with wording. i suppose it does show now that you mention it
The part that makes it difficult is that it doesn't return the same matches, it returns almost the same matches but not exactly. But if PCRE semantics isn't set in stone then i hope leftmost longest could be the default…
Yes, this is entirely possible. you can even explore the automaton eagerly and detect if it's possible to loop from an accepting state to a nonaccepting one. Exciting stuff for future work
Sorry, finished the post just now with more comparisons on other inputs The reason is just that the normal mode is faster in average non pathological cases
Ah, sorry then i misunderstood the comment I'm not sure if it's with both RE2 or Rust, but some internal engines of Rust appear to allocate a fixed buffer that it constantly re-creates states into. I'm not really…
I have experienced this as well, the performance degradation of DFA to NFA is enormous and while not as bad as exponential backtracking, it's close to ReDoS territory. The rust version of the engine…
If you're interested, the rust version is open source now as well: https://github.com/ieviev/resharp
There is plenty still to do. One part of this is SIMD algorithms to better compete with Hyperscan/Rust, another is the decades of optimizations that backtracking engines have for short anchored matches for validation.…
In all honesty it's just never bothered me before and i've havent met many people bothered by it either It's the same thing with dark mode as default, i chose it because it's my own preference and i'd love it…
No, we do not lock reading the state, we only lock the creation side and the transition table reference stays valid during matching even if it is outdated. Only when a nonexistent state is encountered during matching it…
While i completely understand it, the lack of capitalization is just an indication that a human wrote this, it has to be imperfect i see enough slop and Look At Me on a daily basis. i don't want it to look like an ad or…
Yes, most (i think all) lazy DFA engines have a mutable DFA behind a lock internally that grows during matching. Multithreading is generally a non-issue, you just wrap the function that creates the state behind a…