Hacker News Reader

Comment by SonOfLilit | Hacker News Reader

Note that "minimal DFA" is not very relevant these days, with Google's `re2` being the only implementation I'm aware of that implements a DFA. All others sacrifice predictable performance for feature parity with Perl.

View on HN

It's certainly not the only one. Rust's regex crate (of which I'm the author) and Go's regexp package both use finite automata.

It should be noted that none of them build out complete DFAs in the general case. Building a DFA is worst case exponential time and space, and they can in practice be expensive even when not hitting the worst case.

Instead, they use different techniques. RE2 and the regex crate, for example, use a hybrid NFA/DFA that does subset construction at search time. Outside of pathological cases, it provides the speed of a DFA without needing to build the whole thing up front.

Hyperscan is also built on finite automata. GNU grep uses finite automata in many cases too.

Not a single other implementation has feature-parity with Perl. Perl regexes are not only Turing-complete, but can also execute arbitrary code¹ as part of the regex evaluation.

PCRE is the pinnacle of deceptive advertising. It is emphatically not Perl-Compatible.

Source: I used to write Perl for a living, and I have battle scars from (¹) above.

When Sun released Java and went on a marketing road show, I drove to Chicago to hear the presentation. Since Perl was my favorite language, I had to ask about regular expression support; the Sun engineer said there wasn’t any, but I could build the first library.

To me, it was inconceivable that you could release a major language and not only not have regular expressions built into the language like Perl, but not even have it in the standard library. Crazy.

We did the same thing for Rust. Regexes are neither in the language nor in the standard library. Go doesn't have them in the language either (although they're in the standard library).

Rust wasn’t trying to become the standard web programming language.

I didn't realize that was a necessary precondition in your evaluation of what makes something "crazy." Sorry.

Sorry, early morning. I should have been more verbose.

Rust has a different target problem space, a different standard library philosophy, a package management system, and exists in a world where adding external dependencies is trivial.

Java didn’t have any of those excuses.

Well, Java turned out quite all right on that front :-)

When I found out that Jonathan Locke had even a minimal Java implementation of a regex engine, I jumped on it and messaged him to open source it to the Jakarta project. Crazy that that was 20 years ago...

https://jakarta.apache.org/regexp/changes.html

It is incredibly relevant if you want to process uset-provided expressions. Otherwise you expose yourself to a DoS attack.

The Rust regex crate is also DFA based and safe for untrusted inputs.

Nice to know about Rust. From reading the docs the situation seems to be more complicated and more impressive: https://docs.rs/regex/latest/regex/#untrusted-input

.NET added timeouts to handle that. It’s a per-regex setting with a global default (https://docs.microsoft.com/en-us/dotnet/api/system.text.regu...).

I guess that adding timeouts can significantly decrease the run time efficiency?

It can, but this isn’t a hard timeout. From the description (“The MatchTimeout property defines the approximate maximum time interval for a Regex instance to execute”), it seems they have their regex engine periodically (say after handling every 10,000 instructions of the compiled regex) check whether they went over the limit.

Plus, as a general point, .NET has pretty decent performance. It's no C++, but at the same time substantial effort is put into optimisation.

In fact for both .NET v5 and v7, they specifically did work to improve the performance of regexes. For example there is a new non-backtracking option. https://devblogs.microsoft.com/dotnet/regular-expression-imp...

There’s also the postgres regex engine, I don’t know how it works under the hood but it’s very resistant to catastrophic backtracking despite features which normally translate to nfa (e.g. backrefs).

> features which normally translate to nfa (e.g. backrefs)

You're very wrong, backreferences in general can't be translated to finite automata (NFA is short for nondeterministic finite automaton). See these comments:

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

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

Maybe try to read my comment again because I don't think you understood what I wrote.

You say:

> resistant to catastrophic backtracking despite features which normally translate to nfa

I interpret this as you equating NFA with backtracking engines, which would be incorrect. Is my interpretation wrong?

https://devblogs.microsoft.com/dotnet/regular-expression-imp...

Stephen has put incredible work into having an alternative implementation in .net 7.

For anyone interested in regex engine inner workings and optimizations, including SIMD, the blog post is fantastic.

On a related note, if you have Python regex code that you want to make more stable/performant, https://pypi.org/project/pyre2/ is a drop-in replacement for `re` that (configurably) falls back to `re` if you use lookaheads, etc.

The design philosophy behind RE2 for those unfamiliar with the library: https://github.com/google/re2/wiki/WhyRE2

Various regexp implementation possibilities do exist, whether in software or in hardware. I think my general point stands independently of which regexp implementation is used (although the comparisons get hairy if you include the irregular expression "regexps").

Reply on news.ycombinator.com