An additional non-backtracking RegExp engine | Hacker News Reader

An additional non-backtracking RegExp engine

v8.dev

46 points0xedb19 comments

> For now it remains experimental because Irregexp is orders of magnitude faster than the new engine on most common patterns

I'm sure that an important reason for this is that thousands of man-hours have been invested optimizing Irregexp. However, is that the only explanation?

In my experience, while an NFA-based engine has better asymptotic complexity, a backtracking-based engine can be hard to beat for patterns that don't do much backtracking. In a textbook NFA automaton, the time spent maintaining a set of parallel states may be "wasted" if it turns out that the first state in the list is already going to succeed anyway.

Regex experts of Hacker News, do you know if there are any engines and/or algorithms that try to get the best of both worlds? Fast execution for patterns that don't need much backtracking, but avoiding exponential run time in the worst case?

Not an expert but fancy regex is a Rust library that uses a hybrid approach to detect whether a sub expression contains backtracking and delegates to the appropriate engine.

https://github.com/fancy-regex/fancy-regex

It looks like the current implementation [1] just always compiles to Bytecode which is then interpreted [2]. The usual one is more like PCRE JIT in that it defaults to using a macro assembler to generate machine code and execute it.

So I wouldn't draw too much from the current performance difference, it's primarily "simple interpreter vs machine code". IIUC, the plan from that blog post is to default to the backtracking mode (depth first) for a small-ish number of backtracks at which point you switch strategies to get that best of both worlds-ish behavior.

[1] https://github.com/v8/v8/blob/dc712da548c7fb433caed56af9a021...

[2] https://github.com/v8/v8/blob/dc712da548c7fb433caed56af9a021...

That caught my eye too. I looked for benchmarks of re2, but couldn't find anything more recent than this:

https://rust-leipzig.github.io/regex/2017/03/28/comparison-o...

burntsushi criticized it at the time as being unfair to DFA engines.

Incidentally, I also discovered that Firefox now uses Chrome's Irregexp engine:

https://hacks.mozilla.org/2020/06/a-new-regexp-engine-in-spi...

HN discussion:

https://news.ycombinator.com/item?id=23487960

Thanks for the references. The academic paper about Hyperscan is very interesting: https://www.usenix.org/system/files/nsdi19-wang-xiang.pdf

My impression is that they break the regex into components and use choose different algorithms for each component:

1. String search (for fixed strings)

2. DFA (if the number of states is small enough)

3. NFA (if the numer of states is too large)

But one important detail is that Hyperscan doesn't do capture groups and IIRC, capture groups are hard to do using a DFA representation. So going back to my original question, I now wonder if there are other ways to run an NFA (for regexes with capture groups) other than the traditional method of updating all the states in parallel, one character at a time.

> Unfortunately, backreferences, lookahead and lookbehind cannot be supported without major changes that alter asymptotic worst-case complexity.

I live and die by regexes, and regexes without backreferences and lookahead would be pretty useless to me.

I guess such regexes are useful for _something_, but I am not sure what it would be.

Ripgrep (and by extension, vscode) does not have these features for the same reasons. It turns out you can usually find a way of doing what you need without using these features. People got by without them for a long time.

Note that the default regex engine does not. But ripgrep (including the version of ripgrep bundled with VS Code) does permit being built with PCRE2, which allows one to use the -P/--pcre2 flag to switch regex engines. You can even use '--engine auto' to have ripgrep automatically select the regex engine.

With that said, I of course agree with your broader point. To say that regexes are "useless" without look-around/backreferences is absolutely ridiculous.

If you're using references a lot, you're probably using regexes for something where a parser would be a better fit.

You say you live and die by regexes, but most people don't. Most people use regexes for simple validation, and text field extraction from static text patterns; e.g. extracting metrics from log lines. You don't need fancy features to pattern-match a number.

> You don't need fancy features to pattern-match a number.

You would be surprised.

If by a number you don't mean just a sequence of digits, and includes say floating point numbers, a regex to match it surprisingly complex.

Most of what I do with regexes (or similar constructs) is processing text. Extracting information from human-produced text, mostly. No, a parsed won't help me.

And, contrary to common belief, even processing XML (more precisely, XML fragments) sometimes makes more sense to do with regexes than with a parser. Specifically, when dealing with so-called "mixed contents", which is basically is just text with XML elements used for face markup.

For example, suppose you need to find in a text an ordinal number, that can look like "5th". Of course it can be at the top level, as in "My 5th text", or within other face markup, as in "My 2nd italic text", perhaps nested, as in "My 2nd italic text".

Matching it using a parser while handling all these possibilities is hellishly difficult and verbose. With regexes it's straightforward and compact.

Parser is great what what you dealing is true hierarchical, or when you don't care much about what's marked up (e.g. transforms). When dealing with what's essentially is just rich text, it's much less helpful.

Now I'm genuinely curious: I want to see the fancy features used when writing a regex for floating point numbers :)

I regularly write trival regexes like /\d+/ to grab integers out of unstructured text.

> For the fallback mechanism to kick in, the RegExp must: > * ... > * not have the u (Unicode) or i (case insensitive) flags set.

I wonder why these flags are significant. Case-insensitivity and unicode support don't seem like they should really affect whatever algorithm they're using.

Am I underthinking this, or can you convert /abc/i into /[aA][bB][cC]/ ?

I think for the ASCII/Latin characters you selected you’re probably right, but the moment you’re matching Unicode explicitly or characters in the Unicode range implicitly (JS strings are always Unicode), those substitutions may become more complex and deoptimize (or just require additional engineering effort).

Just seems like implementation work. See the various TODOs from mbid like https://github.com/v8/v8/blob/dc712da548c7fb433caed56af9a021...

Current locale determines what the case equivalence rules are for many characters.

It seems more developer-friendly to me to, at Regex construction, try to parse as linear, and fallback to a backtracking regex if not. The engine is an implementation detail that programmers probably care very little about; a linear engine being default but not raising errors would be the best-of-all-worlds scenario.

(It’s a little weird to see the i flag not working with linear regexes, mind. Surely that’s easily implemented when the regex is compiled?)

The problem is that it’s hard to know when you’re triggering backtracking or potentially creating a DoS vector. Having these explicit rules helps other tooling.

Aside: fun fact, I recently worked on a validation library[1] where input was reasonably expected to come from a web browser. So validating email and URL strings was something I delegated to the HTML spec, rather than finding or developing a validator of my liking. Turns out the URL validation regex in the living HTML spec has pathological backtracking. In my case, I disabled linting on that line because if it’s good enough for Chrome it’s good enough for the users who could make it through that series of client requests. But fair warning!

[1]: It’s proprietary so I can’t divulge much, it did much more but that’s the relevant detail I can include.

I'm guessing that if they can get the non-backtracking algorithm to perform at least as fast, then they'll consider switching the default

Reply on news.ycombinator.com