ieviev

24 ms·

1.
by ieviev 6mo ago
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
2.
by ieviev 6mo ago
> 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 appears v
3.
by ieviev 6mo ago
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 engine. Or in the
4.
by ieviev 6mo ago
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.
5.
by ieviev 6mo ago
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 mat
6.
by ieviev 6mo ago
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 operators + large pa
7.
by ieviev 6mo ago
Oh that is interesting! I haven't even looked Nim regex until now, is it similar to the approach in Go?
8.
by ieviev 6mo ago
> constraining oneself to fixed-upper-bound-length needles wait! you haven't reached the important part of the post yet
9.
by ieviev 6mo ago
I have not heard of this before, i will have a look!
10.
by ieviev 6mo ago
Haha, you're right about that. I was looking for another word for "default"
11.
by ieviev 6mo ago
Good catch! I changed this to leftmost-longest nonoverlapping matches so it's not misleading
12.
by ieviev 6mo ago
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 about oth
13.
by ieviev 6mo ago
> 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 expose this quadr
14.
by ieviev 6mo ago
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
15.
by ieviev 6mo ago
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 some day.
16.
by ieviev 6mo ago
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
17.
by ieviev 6mo ago
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
18.
by ieviev 6mo ago
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 familiar wit
19.
by ieviev 6mo ago
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 ( https://github.com/
20.
by ieviev 6mo ago
If you're interested, the rust version is open source now as well: https://github.com/ieviev/resharp
21.
by ieviev 7mo ago
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. There's anal
22.
by ieviev 7mo ago
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 everyw
23.
by ieviev 7mo ago
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 enters the locked re
24.
by ieviev 7mo ago
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 a LinkedIn post
25.
by ieviev 7mo ago
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 lock/mutex, this is us
26.
by ieviev 7mo ago
We refer to this in the paper as well, The standard way to do intersection / complementation of regexes with NFAs requires determinization, which causes a huge blowup, whereas for us this is the cost of a derivative. It is true that we
27.
by ieviev 7mo ago
Yes, exactly correct It's also beneficial to merge some of the matching locations into ranges where possible, so when `a*` matches a long sequence of '|a|a|a|a|a|', it can be represented as a range of (0,5), we do this to kee
28.
by ieviev 7mo ago
yes, that is correct. also Rust's engine matches the full unicode spec as individual characters, whereas .NET's will chop emojis into two sometimes, so Rust at a disadvantage here. something i've been also wondering is how do
29.
by ieviev 7mo ago
Yes, that's exactly what we did to be competitive in the benchmarks. There's a lot of simple cases where you don't really need a regex engine at all. integrating SearchValues as a multi-string prefix search is a bit harder si
30.
by ieviev 7mo ago
It goes from start of the first match to the longest "alive" end, in practice it will go to a dead state and return after finding the match end. there's an implicit `.*` in front of the first pass but i felt it would've

More ›