5 ms·

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 sacrif

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.

kevincox 4y ago
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.
- SonOfLilit 4y ago
  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 https://docs.rs/regex/latest/regex/#untrusted-input
- Someone 4y ago
  .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.regularexpressions.regex.matchtimeout?view=net-6.0 https://docs.microsoft.com/en-us/dotnet/api/system.text.regu...).
  - nsajko 4y ago
    I guess that adding timeouts can significantly decrease the run time efficiency?
    - Someone 4y ago
      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.
      - orra 4y ago
        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-improvements-in-dotnet-7/ https://devblogs.microsoft.com/dotnet/regular-expression-imp...
- masklinn 4y ago
  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).
  - nsajko 4y ago
    > 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=18431610 https://news.ycombinator.com/item?id=27877743 https://news.ycombinator.com/item?id=27877743
    - masklinn 4y ago
      Maybe try to read my comment again because I don't think you understood what I wrote.
      - nsajko 4y ago
        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?
nsajko 4y ago
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").
ankitpati 4y ago
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.
- macintux 4y ago
  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.
  - burntsushi 4y ago
    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).
    - macintux 4y ago
      Rust wasn’t trying to become the standard web programming language.
      - burntsushi 4y ago
        I didn't realize that was a necessary precondition in your evaluation of what makes something "crazy." Sorry.
        macintux 4y ago
        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.
burntsushi 4y ago
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.
btown 4y ago
On a related note, if you have Python regex code that you want to make more stable/performant, https://pypi.org/project/pyre2/ 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 https://github.com/google/re2/wiki/WhyRE2
joe_guy 4y ago
https://devblogs.microsoft.com/dotnet/regular-expression-improvements-in-dotnet-7/ 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.

kevincox 4y ago

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.

SonOfLilit 4y ago
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 https://docs.rs/regex/latest/regex/#untrusted-input
Someone 4y ago
.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.regularexpressions.regex.matchtimeout?view=net-6.0 https://docs.microsoft.com/en-us/dotnet/api/system.text.regu...).
- nsajko 4y ago
  I guess that adding timeouts can significantly decrease the run time efficiency?
  - Someone 4y ago
    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.
    - orra 4y ago
      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-improvements-in-dotnet-7/ https://devblogs.microsoft.com/dotnet/regular-expression-imp...
masklinn 4y ago
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).
- nsajko 4y ago
  > 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=18431610 https://news.ycombinator.com/item?id=27877743 https://news.ycombinator.com/item?id=27877743
  - masklinn 4y ago
    Maybe try to read my comment again because I don't think you understood what I wrote.
    - nsajko 4y ago
      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?

nsajko 4y ago

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").

ankitpati 4y ago

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.

macintux 4y ago
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.
- burntsushi 4y ago
  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).
  - macintux 4y ago
    Rust wasn’t trying to become the standard web programming language.
    - burntsushi 4y ago
      I didn't realize that was a necessary precondition in your evaluation of what makes something "crazy." Sorry.
      - macintux 4y ago
        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.

burntsushi 4y ago

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.

btown 4y ago

On a related note, if you have Python regex code that you want to make more stable/performant, https://pypi.org/project/pyre2/ 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 https://github.com/google/re2/wiki/WhyRE2

joe_guy 4y ago

https://devblogs.microsoft.com/dotnet/regular-expression-improvements-in-dotnet-7/ 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.