10 ms·

Note that when you use grep, awk, sed, libc regexec(), RE2 [1], or rust/regex, this isn't how your regexes are executed. They use automata-based engines wherea

by chubot 6y ago

Note that when you use grep, awk, sed, libc regexec(), RE2 [1], or rust/regex, this isn't how your regexes are executed. They use automata-based engines whereas this is a backtracking engine, which can blow up on small inputs. (Although I will say the C code here is cool, because it gives you a fork() bomb, so it might exhaust your operating system and not just your CPU!) Canonical reference: Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html Archive since it's down at the moment due to some App Engine stuff (!): https://web.archive.org/web/20200624195819/https://swtch.com/~rsc/regexp/regexp1.html https://web.archive.org/web/20200624195819/https://swtch.com... My blog post and sample code that verifies that GNU grep, awk, sed, and libc don't backtrack: Comments on Eggex and Regular Languages http://www.oilshell.org/blog/2020/07/eggex-theory.html http://www.oilshell.org/blog/2020/07/eggex-theory.html https://github.com/oilshell/blog-code/tree/master/regular-languages https://github.com/oilshell/blog-code/tree/master/regular-la... [1] https://github.com/google/re2 https://github.com/google/re2 ---- Also, the production quality way of compiling regular expressions to C code looks like this [2], which is completely different than what's shown in the article: https://www.oilshell.org/release/0.8.pre8/source-code.wwz/_devbuild/gen/osh-lex.h https://www.oilshell.org/release/0.8.pre8/source-code.wwz/_d... The regex is converted to an NFA, then a DFA, then a bunch of switch/goto statements in C that implement the DFA. This example is huge, but the switch/goto and lack of any notion of "threading" is the important point. Essentially, the instruction pointer is used as the DFA state. It's a very natural use of "goto" (where you don't write or debug them yourself) [2] via http://re2c.org/ http://re2c.org/ (not related to RE2)

robertelder 6y ago
It's worth pointing out that the resource https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html linked above is also by the same author, Russ Cox, as the reference I included at the end of the blog post: https://swtch.com/~rsc/regexp/regexp2.html https://swtch.com/~rsc/regexp/regexp2.html All of the insights that I presented through this visualization tool are based upon the knowledge found in Russ Cox's articles. Also, the link above on RE2: https://github.com/google/re2 https://github.com/google/re2 is a project that was was also (started by|heavily contributed to by) Russ Cox. His writings on the topic of regular expressions are absolutely world-class and I have never found any better resource for understanding the deep low-level theory on how they work in practice.
- chubot 6y ago
  But Cox would dislike this formulation of regular expressions. His whole point is that Perl-stye regexes are not regular languages, and RE2 goes to great lengths to work around this fact. I'm taking up his arguments with some more traditional terminology that I think may help: http://www.oilshell.org/blog/2020/07/eggex-theory.html http://www.oilshell.org/blog/2020/07/eggex-theory.html The entire O'Reilly book "Mastering Regular Expressions" by Friedl is based on the "debugging regexes by backtracking" approach you present here. It talks about "optimizing" regexes by reordering clauses and optimizing the backtracking. Russ Cox HATES THAT APPROACH and he wrote the entire RE2 project to advocate that it NOT be used! You do not need to optimize, reorder clauses, debug, or trace backtracking when you're using automata-based engines, because they run in guaranteed linear time and constant space (with respect to the length of the input). There is no backtracking. (I was at Google when he wrote RE2 and used it shortly afterward on big data, and regular languages are indeed better than regexes for such engineering. Also made clear by the HyperScan work.) Since his site is down I can't find the original comments, but here's a twitter exchange from 2018 that backs this up: https://twitter.com/geofflangdale/status/1060313603268501504 https://twitter.com/geofflangdale/status/1060313603268501504 https://twitter.com/_rsc/status/1060702201159565313 https://twitter.com/_rsc/status/1060702201159565313 Also, I believe your article would be improved if you simply take out this sentence: In computer science theory, this node type should remind you of the difference between DFAs and NFAs. It is treading close to the confusion that Cox is talking about. So I would just remove, add a proper explanation, or add a link to the authoritative source. ---- I would love to see a followup that goes through the rest of the article with the Thompson VM and Pike VM approaches! :) I think the whole point is that you don't have to backtrack to implement this VM, and this page confuses that issue.
  - robertelder 6y ago
    The goal with this article was never to show the best or most efficient way to match regular expressions, but rather to convey the correct interpretation of what a given regular expression will do when you try to use it. Even discussions of slow and simple backtracking regular expression matchers are a pretty niche topic and likely too much for casual users of regular expressions. Yes, I was thinking about also allowing it to optionally cross-compile to the more asymptotically efficient matching algorithm, also documented by Russ Cox. Everything takes time though, and I figured it would make to put this out there before investing too much time in something that possibly no one would use.
imadr 6y ago
RE2 source code is interesting, it seems to switch between simulating an NFA or a DFA depending on which is faster. However to my understanding, don't you first need to make an NFA and use subset construction to convert it to a DFA?
- burntsushi 6y ago
  With RE2 in particular, the DFA is almost always faster. The most common cases where an NFA is used is when the DFA can't handle the request. Typically, that occurs when you need the offsets of submatches. But in some circumstances, if the regex would cause the DFA to grow exponentially, then RE2 will dynamically fall back to the NFA, since it's slightly faster. Keep in mind that RE2 doesn't really have a true DFA. It has a hybrid NFA/DFA or a "lazy DFA." Namely, the DFA is computed at match time through incremental subset construction. The DFA states are cached in memory, so most bytes that are processed are processed as if it were a bog-standard table based DFA.
  - ridiculous_fish 6y ago
    How do DFAs handle zero-width anchors? For example \b, or ^ and $ in multiline mode?
    - burntsushi 6y ago
      Not easily. In the special case of one byte look around (which works for the ASCII interpretations of \b, ^ and $), the DFA can be massaged to make it work by doing two things. First is by embedding some look-around state into each DFA state, when appropriate. For example, in the case of \b, a DFA state is marked as "coming from a word byte" if its incoming transition is a word byte and not marked otherwise. Then, when computing the epsilon closure during subset construction, you use the look-around state to compute whether an epsilon transition is something you're allowed to take or not. e.g., a \b is an epsilon transition since it doesn't consume any input, so you only take it if the state you're in and the byte currently under inspection satisfy the \b criteria. The second aspect of this is that you have to delay your match by one byte, in order to account for \b and $ at the end of the input. This actually requires adding a special "end of text" sentinel to your DFA's alphabet, but is otherwise pretty easy to handle. Look-around can actually be supported in the general case using finite automata, although I believe it requires something more powerful than a bare DFA. This paper has the details on that, although it is a difficult read: https://re2c.org/2017_trofimovich_tagged_deterministic_finite_automata_with_lookahead.pdf https://re2c.org/2017_trofimovich_tagged_deterministic_finit... Of course, these techniques can greatly balloon the size of the DFA. The special case of one-byte look-ahead is generally tolerable, but anything more than that can get pretty bad. A further pain point is that in Rust's regex engine, \b is Unicode aware by default, and the DFA doesn't support that. The tagged DFA paper makes it clear that such things are possible, but it's complex and it's not clear how effective it would be. Especially since a Unicode aware \w is quite large. So Rust's regex crate has a special optimization where it treats a Unicode aware \b as an ASCII \b if and only if all of its input is ASCII. (Of course, it doesn't scan the input ahead of time to determine this. Instead, it constructs the DFA to quit if it observes any non-ASCII byte. Then it falls back to the slower PikeVM or bounded backtracking engines.) Apologies for the late reply. :-( I wish HN sent email notifications for replies.

by chubot 6y ago

robertelder 6y ago

It's worth pointing out that the resource https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html linked above is also by the same author, Russ Cox, as the reference I included at the end of the blog post: https://swtch.com/~rsc/regexp/regexp2.html https://swtch.com/~rsc/regexp/regexp2.html All of the insights that I presented through this visualization tool are based upon the knowledge found in Russ Cox's articles. Also, the link above on RE2: https://github.com/google/re2 https://github.com/google/re2 is a project that was was also (started by|heavily contributed to by) Russ Cox. His writings on the topic of regular expressions are absolutely world-class and I have never found any better resource for understanding the deep low-level theory on how they work in practice.

chubot 6y ago
But Cox would dislike this formulation of regular expressions. His whole point is that Perl-stye regexes are not regular languages, and RE2 goes to great lengths to work around this fact. I'm taking up his arguments with some more traditional terminology that I think may help: http://www.oilshell.org/blog/2020/07/eggex-theory.html http://www.oilshell.org/blog/2020/07/eggex-theory.html The entire O'Reilly book "Mastering Regular Expressions" by Friedl is based on the "debugging regexes by backtracking" approach you present here. It talks about "optimizing" regexes by reordering clauses and optimizing the backtracking. Russ Cox HATES THAT APPROACH and he wrote the entire RE2 project to advocate that it NOT be used! You do not need to optimize, reorder clauses, debug, or trace backtracking when you're using automata-based engines, because they run in guaranteed linear time and constant space (with respect to the length of the input). There is no backtracking. (I was at Google when he wrote RE2 and used it shortly afterward on big data, and regular languages are indeed better than regexes for such engineering. Also made clear by the HyperScan work.) Since his site is down I can't find the original comments, but here's a twitter exchange from 2018 that backs this up: https://twitter.com/geofflangdale/status/1060313603268501504 https://twitter.com/geofflangdale/status/1060313603268501504 https://twitter.com/_rsc/status/1060702201159565313 https://twitter.com/_rsc/status/1060702201159565313 Also, I believe your article would be improved if you simply take out this sentence: In computer science theory, this node type should remind you of the difference between DFAs and NFAs. It is treading close to the confusion that Cox is talking about. So I would just remove, add a proper explanation, or add a link to the authoritative source. ---- I would love to see a followup that goes through the rest of the article with the Thompson VM and Pike VM approaches! :) I think the whole point is that you don't have to backtrack to implement this VM, and this page confuses that issue.
- robertelder 6y ago
  The goal with this article was never to show the best or most efficient way to match regular expressions, but rather to convey the correct interpretation of what a given regular expression will do when you try to use it. Even discussions of slow and simple backtracking regular expression matchers are a pretty niche topic and likely too much for casual users of regular expressions. Yes, I was thinking about also allowing it to optionally cross-compile to the more asymptotically efficient matching algorithm, also documented by Russ Cox. Everything takes time though, and I figured it would make to put this out there before investing too much time in something that possibly no one would use.

imadr 6y ago

RE2 source code is interesting, it seems to switch between simulating an NFA or a DFA depending on which is faster. However to my understanding, don't you first need to make an NFA and use subset construction to convert it to a DFA?

burntsushi 6y ago
With RE2 in particular, the DFA is almost always faster. The most common cases where an NFA is used is when the DFA can't handle the request. Typically, that occurs when you need the offsets of submatches. But in some circumstances, if the regex would cause the DFA to grow exponentially, then RE2 will dynamically fall back to the NFA, since it's slightly faster. Keep in mind that RE2 doesn't really have a true DFA. It has a hybrid NFA/DFA or a "lazy DFA." Namely, the DFA is computed at match time through incremental subset construction. The DFA states are cached in memory, so most bytes that are processed are processed as if it were a bog-standard table based DFA.
- ridiculous_fish 6y ago
  How do DFAs handle zero-width anchors? For example \b, or ^ and $ in multiline mode?
  - burntsushi 6y ago
    Not easily. In the special case of one byte look around (which works for the ASCII interpretations of \b, ^ and $), the DFA can be massaged to make it work by doing two things. First is by embedding some look-around state into each DFA state, when appropriate. For example, in the case of \b, a DFA state is marked as "coming from a word byte" if its incoming transition is a word byte and not marked otherwise. Then, when computing the epsilon closure during subset construction, you use the look-around state to compute whether an epsilon transition is something you're allowed to take or not. e.g., a \b is an epsilon transition since it doesn't consume any input, so you only take it if the state you're in and the byte currently under inspection satisfy the \b criteria. The second aspect of this is that you have to delay your match by one byte, in order to account for \b and $ at the end of the input. This actually requires adding a special "end of text" sentinel to your DFA's alphabet, but is otherwise pretty easy to handle. Look-around can actually be supported in the general case using finite automata, although I believe it requires something more powerful than a bare DFA. This paper has the details on that, although it is a difficult read: https://re2c.org/2017_trofimovich_tagged_deterministic_finite_automata_with_lookahead.pdf https://re2c.org/2017_trofimovich_tagged_deterministic_finit... Of course, these techniques can greatly balloon the size of the DFA. The special case of one-byte look-ahead is generally tolerable, but anything more than that can get pretty bad. A further pain point is that in Rust's regex engine, \b is Unicode aware by default, and the DFA doesn't support that. The tagged DFA paper makes it clear that such things are possible, but it's complex and it's not clear how effective it would be. Especially since a Unicode aware \w is quite large. So Rust's regex crate has a special optimization where it treats a Unicode aware \b as an ASCII \b if and only if all of its input is ASCII. (Of course, it doesn't scan the input ahead of time to determine this. Instead, it constructs the DFA to quit if it observes any non-ASCII byte. Then it falls back to the slower PikeVM or bounded backtracking engines.) Apologies for the late reply. :-( I wish HN sent email notifications for replies.