3 ms·

> If your regex has backreferences, or look-ahead/look-behind assertions, or similar things, then your regex engine must support a backtracking strategy. There

> If your regex has backreferences, or look-ahead/look-behind assertions, or similar things, then your regex engine must support a backtracking strategy. There's a morphism that maps Phritzy's pattern to an equivalent pattern that can be matched with a Thompson NFA. (It's a similar strategy to the one that allows you to take an NFA and turn it into a DFA.) You can perform a sort of "static decomposition" on a subset of patterns containing backreferences, such that /(cat|dog)\1/ for example decomposes into /catcat|dogdog/. The caveat is that this isn't fully generalizable for all patterns containing backreferences. But saying that backreferences cannot be supported by a pattern matching engine that uses something other than backtracking is like saying that because there is no general algorithm no prove any given program P halts, then no program can be proven to halt. But that's trivially demonstrated to be untrue. ∃ ≠ ∀ RE2 chooses not to support any PCRE-style backreferences, because RE2 is a pattern matching engine meant to support patterns that are actually regular, and backreferences are not regular.

geofft 10y ago
> But saying that backreferences cannot be supported by a pattern matching engine that uses something other than backtracking is like saying that because there is no general algorithm no prove any given program P halts, then no program can be proven to halt. But that's trivially demonstrated to be untrue. ∃ ≠ ∀ Yeah, sorry, I mixed up the sense of the quantifiers a bit. More accurately: "If you are interested in regexes that use backreferences, or look-ahead/look-behind assertions, or similar things, then your regex engine must support a backtracking strategy, or you need to rewrite all the regexes you care about to not use any of these." Is it possible to automate that morphism, i.e., is it possible to build a wrapper around RE2 that converts (in suitably bounded time) a regex using backreferences to RE2 if the language described is in fact regular, and prints an error otherwise?
- wahern 10y ago
  I did something similar for word boundary zero-width assertions (i.e. \b and \B); that is, rewrite the PCRE by expanding permutations inline. The purpose was to compile as many PCREs as possible to DFAs using Ragel. Fortunately, Ragel supported a limited form of assertions called semantic conditions, which it implements by expanding the code space of each state and allows you to associate a C boolean expression as a predicate for entering that state. For various reasons the semantic condition needed to be attached to a terminal, not to subexpressions (i.e. groupings and alternations). Also, expressions like (cat?|dog?)\b needed to be permuted similar to the backreference problem, resulting in something that might look like (ca\b|cat\b|do\b|dog\b). This strategy didn't work for kleene stars (*), but usually a semantic condition could be attached to trailing terminals instead of leading terminals. The actual code to perform these AST transformations was surprisingly simple. Excluding parsing of PCREs into an annotated AST and generation of the code, less than 200 lines of Lua code, maybe. The PCREs weren't simple, but most were only moderately complex. For a corpus of about 10,000 PCREs about 1/2 used word boundary assertions. The vast majority of those (possibly even all of them... I can't remember) could be successfully transformed. With nested subexpressions (groups, alternations) the number of permutations rapidly grows, but I don't think our production corpus ever caused a problem in that regard, and only the most insane regular expressions nest subexpressions more than a few deep. Before we tackled back references and other gnarly PCRE features I think we managed to coax better than 90% of our PCRE corpus to transform into semantically equivalent Ragel-based DFAs. In other words, back references were rare. With 90%+ compiled completely to native machine code and the remainder simplified into prefilters we saw greater than 10x performance improvement (> 1000%) over libpcre in terms of production throughput, not just benchmarks. (Ragel is awesome!) RE2 was usually faster than libpcre, but RE2's performance wasn't even remotely in the same league as the native machine code DFA Ragel produced, so I quickly ditched the idea of using RE2 anywhere in the pipeline. That last 10% or so took much longer to tackle, and eventually most of my original code was dumped. But getting to about 90% was surprisingly easy. We did eventually get (and continue to maintain) 100% transformation to native machine code, but a small percentage still require backtracking. All-in-all I _think_ we're at 20x to 30x over baseline libpcre; that is, tacking the last 10% put us 2x or 3x atop the 10x. It wasn't a simple case of diminishing returns as the most difficult expressions to transform also tended to be the most costly at runtime, but if we had stopped early on at 90% it still would have been a resounding success. Regarding RE2, it's important to note once an expression was transformed into a proper regular expression, they could be easily joined into a single union. Setting aside the bytecode vs machine code differences, RE2 just isn't capable of compiling huge unions of expressions (on the order of 100s or 1000s), whereas for Ragel it was a relative breeze. Another team was using re2c (not RE2) for a project, and it turned out that what it literally took re2c DAYS to compile only took SECONDS for Ragel to compile. GCC and clang also became bottlenecks compiling the Ragel generated code. And interestingly they both, coincidentally, exhibited (and still exhibit, AFAIK) quadratic complexity when parsing certain C constructs, such as initializer lists. So that necessitated some workarounds.
  - carussell 10y ago
    Neat! What was the application? Or was it pure research?
    - wahern 10y ago
      For a content filtering/scanning service. By the time we wrapped up this project Intel finally released Hyperscan as Open Source. Hyperscan implements these and other transformation tricks, not to mention the SIMD optimizations. However, Hyperscan doesn't have as strong compatibility for PCRE as what we ended up with--100% effectively--and would have necessitated keeping libpcre as a failover. Hyperscan is substantially faster than Ragel for small-to-medium length expressions thanks to their SIMD optimizations, but with huge, unioned expressions (larger than what Hyperscan can handle) Ragel-generated code is on par. Starting from scratch today and presuming Hyperscan is still well-maintained, it would be most practical to build a solution around Hyperscan. Especially if you need capturing, as capturing expressions can't be unioned effectively. Ragel, however, makes a ton sense for many other tasks than merely speeding up PCRE matching. What makes Ragel unique is: 1) The way it integrates with the host language (C, C++, Java, etc). It allows executing host-language expressions at state machine transitions. It doesn't directly tie into the host language typing model (e.g. like Boost's template-based regular expressions), but for various reasons it's hardly a liability and often an asset. 2) It allows yielding and resumption of matching at any and all input stream boundaries, with runtime machine state being a simple integer. (Application keeps any additional state however it wants.) Most regular expression tools require a complete string to match against, while a Ragel machine can be iteratively applied to an infinite stream of data. That capability wasn't useful in this scenario, but it's extremely useful for concisely, performantly, and securely implementing network protocols, for example. In a low-level language like C, and especially with asynchronous I/O, this can drastically simplify the task of I/O and buffer management. You could parse (if you wanted) an entire HTTP stream in a single logical pass, without having to deal with line buffering, header continuations, etc as separate concerns in your code, greatly simplifying networking code. In a some sense it can be thought of as a complement if not an alternative to callback schemes, futures/promises, or green threading (a la Go).
- carussell 10y ago
  You can run into similar theoretical worst-case problems as what can happen when trying to conversion for arbitrary NFA -> DFA. See beeforpork's comment: https://news.ycombinator.com/item?id=13603461 https://news.ycombinator.com/item?id=13603461 You'd want to target a restricted subset containing patterns that use only certain "tractable", er... motifs.[1] It would make for an interesting project. Specifically, how much you have to restrict yourself in your focus while still aiming to produce something that's useful. I'm not going to pretend that I've got an up-to-date perspective that includes all available research in this area. Something like this may have already been done. 1. For lack of a better word. (I'm trying to avoid using the word "pattern" multiple times in the same sentence, where each has a different meaning.)
deleted 10y ago
[deleted]

geofft 10y ago

> But saying that backreferences cannot be supported by a pattern matching engine that uses something other than backtracking is like saying that because there is no general algorithm no prove any given program P halts, then no program can be proven to halt. But that's trivially demonstrated to be untrue. ∃ ≠ ∀ Yeah, sorry, I mixed up the sense of the quantifiers a bit. More accurately: "If you are interested in regexes that use backreferences, or look-ahead/look-behind assertions, or similar things, then your regex engine must support a backtracking strategy, or you need to rewrite all the regexes you care about to not use any of these." Is it possible to automate that morphism, i.e., is it possible to build a wrapper around RE2 that converts (in suitably bounded time) a regex using backreferences to RE2 if the language described is in fact regular, and prints an error otherwise?

wahern 10y ago
I did something similar for word boundary zero-width assertions (i.e. \b and \B); that is, rewrite the PCRE by expanding permutations inline. The purpose was to compile as many PCREs as possible to DFAs using Ragel. Fortunately, Ragel supported a limited form of assertions called semantic conditions, which it implements by expanding the code space of each state and allows you to associate a C boolean expression as a predicate for entering that state. For various reasons the semantic condition needed to be attached to a terminal, not to subexpressions (i.e. groupings and alternations). Also, expressions like (cat?|dog?)\b needed to be permuted similar to the backreference problem, resulting in something that might look like (ca\b|cat\b|do\b|dog\b). This strategy didn't work for kleene stars (*), but usually a semantic condition could be attached to trailing terminals instead of leading terminals. The actual code to perform these AST transformations was surprisingly simple. Excluding parsing of PCREs into an annotated AST and generation of the code, less than 200 lines of Lua code, maybe. The PCREs weren't simple, but most were only moderately complex. For a corpus of about 10,000 PCREs about 1/2 used word boundary assertions. The vast majority of those (possibly even all of them... I can't remember) could be successfully transformed. With nested subexpressions (groups, alternations) the number of permutations rapidly grows, but I don't think our production corpus ever caused a problem in that regard, and only the most insane regular expressions nest subexpressions more than a few deep. Before we tackled back references and other gnarly PCRE features I think we managed to coax better than 90% of our PCRE corpus to transform into semantically equivalent Ragel-based DFAs. In other words, back references were rare. With 90%+ compiled completely to native machine code and the remainder simplified into prefilters we saw greater than 10x performance improvement (> 1000%) over libpcre in terms of production throughput, not just benchmarks. (Ragel is awesome!) RE2 was usually faster than libpcre, but RE2's performance wasn't even remotely in the same league as the native machine code DFA Ragel produced, so I quickly ditched the idea of using RE2 anywhere in the pipeline. That last 10% or so took much longer to tackle, and eventually most of my original code was dumped. But getting to about 90% was surprisingly easy. We did eventually get (and continue to maintain) 100% transformation to native machine code, but a small percentage still require backtracking. All-in-all I _think_ we're at 20x to 30x over baseline libpcre; that is, tacking the last 10% put us 2x or 3x atop the 10x. It wasn't a simple case of diminishing returns as the most difficult expressions to transform also tended to be the most costly at runtime, but if we had stopped early on at 90% it still would have been a resounding success. Regarding RE2, it's important to note once an expression was transformed into a proper regular expression, they could be easily joined into a single union. Setting aside the bytecode vs machine code differences, RE2 just isn't capable of compiling huge unions of expressions (on the order of 100s or 1000s), whereas for Ragel it was a relative breeze. Another team was using re2c (not RE2) for a project, and it turned out that what it literally took re2c DAYS to compile only took SECONDS for Ragel to compile. GCC and clang also became bottlenecks compiling the Ragel generated code. And interestingly they both, coincidentally, exhibited (and still exhibit, AFAIK) quadratic complexity when parsing certain C constructs, such as initializer lists. So that necessitated some workarounds.
- carussell 10y ago
  Neat! What was the application? Or was it pure research?
  - wahern 10y ago
    For a content filtering/scanning service. By the time we wrapped up this project Intel finally released Hyperscan as Open Source. Hyperscan implements these and other transformation tricks, not to mention the SIMD optimizations. However, Hyperscan doesn't have as strong compatibility for PCRE as what we ended up with--100% effectively--and would have necessitated keeping libpcre as a failover. Hyperscan is substantially faster than Ragel for small-to-medium length expressions thanks to their SIMD optimizations, but with huge, unioned expressions (larger than what Hyperscan can handle) Ragel-generated code is on par. Starting from scratch today and presuming Hyperscan is still well-maintained, it would be most practical to build a solution around Hyperscan. Especially if you need capturing, as capturing expressions can't be unioned effectively. Ragel, however, makes a ton sense for many other tasks than merely speeding up PCRE matching. What makes Ragel unique is: 1) The way it integrates with the host language (C, C++, Java, etc). It allows executing host-language expressions at state machine transitions. It doesn't directly tie into the host language typing model (e.g. like Boost's template-based regular expressions), but for various reasons it's hardly a liability and often an asset. 2) It allows yielding and resumption of matching at any and all input stream boundaries, with runtime machine state being a simple integer. (Application keeps any additional state however it wants.) Most regular expression tools require a complete string to match against, while a Ragel machine can be iteratively applied to an infinite stream of data. That capability wasn't useful in this scenario, but it's extremely useful for concisely, performantly, and securely implementing network protocols, for example. In a low-level language like C, and especially with asynchronous I/O, this can drastically simplify the task of I/O and buffer management. You could parse (if you wanted) an entire HTTP stream in a single logical pass, without having to deal with line buffering, header continuations, etc as separate concerns in your code, greatly simplifying networking code. In a some sense it can be thought of as a complement if not an alternative to callback schemes, futures/promises, or green threading (a la Go).
carussell 10y ago
You can run into similar theoretical worst-case problems as what can happen when trying to conversion for arbitrary NFA -> DFA. See beeforpork's comment: https://news.ycombinator.com/item?id=13603461 https://news.ycombinator.com/item?id=13603461 You'd want to target a restricted subset containing patterns that use only certain "tractable", er... motifs.[1] It would make for an interesting project. Specifically, how much you have to restrict yourself in your focus while still aiming to produce something that's useful. I'm not going to pretend that I've got an up-to-date perspective that includes all available research in this area. Something like this may have already been done. 1. For lack of a better word. (I'm trying to avoid using the word "pattern" multiple times in the same sentence, where each has a different meaning.)

deleted 10y ago

[deleted]