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 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 appears very fragile.

a simple example: a.*?b can be rewritten to something like (a.*b&~(a.*b_+)) in RE# syntax, which effectively means "there is a match, but must not contain a shorter match"

1998 TOPLAS

I will read through it properly, but i can already see from page 8 that it requires a table of (DFA size x input length) which makes me very suspicious that it is more of a thought exercise than a real world solution.

It is true that you can’t stream the haystack in the general case, but to what precise extent you can is an interesting question with a known algorithmic answer[3].

Thank you for this, this is an interesting paper

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 case of preprocessing lines first and then running is_match it's also 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 matches without quadratic blowup"

The engines mentioned at the beginning all return nonoverlapping matches. Basic document search returns nonoverlapping matches.

Finding overlapping matches is exotic and rarely ever used in practice outside of network security. It does solve a different problem

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 pattern perf will hopefully be a strong selling point to gain more traction

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 about other engines in terms of backtracking but it works very differently. And fixed length lookbehinds are more of a Java/Python thing, other engines support all lookbehinds.

The main idea of linear regex and intuitive semantics is that it should be declarative and the engine does whatever is the fastest without you having to worry about it. Instead of describing character by character how to perform the search and where it can blow up, think of it as just a specification. Then you can truly express whatever is the shortest/most convenient to explain.

Something i'm still trying to figure out and perhaps failing to understand is what are the killer features of backtracking regex that you would really miss if you were to use linear regex? It would help me a lot to know, i'm trying to convince others to make the switch

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 quadratic blowup (from all matches) but i do not think the same about backtracking. The effect of backtracking is immediately clear when you're searching inside text without a clear anchor like \A or ^ or a very rare string prefix. It is much more visible with either larger patterns or larger character classes like unicode

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 some day. There's a lot of nice things you get for free with the two pass approach

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 familiar with the eviction technique of RE2 but I've done a lot of benchmark comparisons. A good way to really stress test RE2 is large Unicode classes, \w and \d in RE2 are ascii-only, i've noticed Unicode (\p{class}) classes very drastically change the throughput of the engine.

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/ieviev/resharp) just returns an Error instead of falling back to NFA, I think that should be a reasonable approach, but the library is still new so i'm still waiting to see how it turns out and whether i had any oversights on this.

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.

There's analysis to do for specific patterns so we can opt for specialized algorithms, eg. for fixed length patterns we skip the left-to-right pass entirely since we already know the match start + match length.

Lots of opportunistic things like this which we haven't done. Also there are no statistical optimizations in the engine right now. Most engines will immediately start looking for a 'z' if there is one in the pattern since it is rare.

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 everywhere, but i'm constantly being flashbanged by phone apps because someone decided #FFFFFF is a good background color while the app is loading.

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 region.

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 in 2026.

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 usually the default.

The subtle denial of service part is interesting, i haven't thought of it before. Yes this is possible. For security-critical uses i would compile the full DFA ahead of time - the memory cost may be painful but this completely removes the chance of anything going wrong.

There are valid arguments to switch from DFA to NFA with large state spaces, but RE# intentionally does not switch to a NFA and capitalizes on reducing the DFA memory costs instead (eg. minterm compression in the post, algebraic simplifications in the paper).

The problem with going from DFA to NFA for large state spaces is that this makes the match time performance fall off a cliff - something like going from 1GB/s to 1KB/s as we also show in the benchmarks in the paper.

As for eviction techniques i have not researched this, the simplest thing to do is just completely reset the instance and rebuild past a certain size, but likely there is a better way.

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 cannot avoid enormous DFA sizes, a simple case would be (.*a.*)&(.*b.*)&(.*c.*)&(.*d.*)... which has 2^4 states and every intersection adds +1 to the exponent.

How we get around this in the real world is that we create at most one state per input character, so even if the full DFA size is 1 million, you need an input that is at least 1 million characters long to reach it.

The real argument to complexity is how expensive can the cost of taking a lazy derivative get? The first time you use the engine with a unique input and states, it is not linear - the worst case is creating a new state for each character. The second time the same (or similar) input is used these states are already created and it is linear. So as said in the article it is a bit foggy - Lazy DFAs are not linear but appear as such for practical cases

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 keep the lookaround internal states smaller in the engine.

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 does Harry (https://ieeexplore.ieee.org/document/10229022) compare to the Teddy algorithm, it's written by some of the same authors - i wonder if it's used in any engines outside of Hyperscan today.

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 since it doesn't expose which branch matched so we would be taking unnecessary steps.

Also .NET implementation of Hyperscan's Teddy algorithm only goes left to right.. if it went right to left it would make RE# much faster for these cases.

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 been a long tangent so i didn't want to get into it.

so given input 'aabbcc' and pattern `b+`,

first reverse pass (using `.*b+`) marks 'aa|b|bcc'<-

the forward pass starts from the first match:

'aa->b|b|cc' marking 2 ends

then enters a dead state after the first 'c' and returns the longest end: aa|bb|cc

i hope this explains it better