Viewing profile — ieviev

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 simila…

> 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 qu…

I have not verified it but i assume matching the whole line grep-style would bypass this problem entirely Since a regex with ^ $ can not have overlapping matches it should guarante…

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 …

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 brain…

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 ve…

> 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 s…

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 hop…

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 fut…

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-cre…

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 ver…

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 s…

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 ow…

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 …

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…

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…