On Tue, Jun 9, 2020 at 12:48 AM Kurtis Rader <kra...@skepticism.us> wrote:
> You're talking past each other. Robert is talking about limiting the > length of the regex, not the string(s) evaluated by the regex. > So am I. Note that e.g. a Code Search based on PCRE would break, even if you limit *both* (or rather, any limit causing it to not break would result in a completely useless piece of software). It should be possible to compile any regex of a reasonable length in a > matter of microseconds. Regardless of whether the application of the regex > to a given input is near linear (as in the case of the Go RE > implementation) or exponential (as in the case of PCRE). > This might be, where we talk past each other. I am using application as an example for concrete numbers on how quickly exponential growth can devolve. Of course, compilation of a regexp is fast - I am aware of that. As it turns out, so is application of a regexp, if you use RE2 (or Go's regexp package). What I take issue with are the statements that a) the question about the complexity of compiling a regexp is irrelevant, because b) limiting the algorithmic complexity of a function to counteract resource exhaustion attacks "never works". RE2 is an excellent example to show that it does work; it is carefully designed for linear complexity of the combined compilation+matching of a regular expression. I'm not saying compiling a regular expression is an exponential operation. I'm saying *if it was*, you could never reasonably build something like Code Search. And we can use the fact that *application* indeed is (in most engines) exponential in the combined input length of expression+search text as a good basis to make that case. Of course we don't even need this fantasy world to make the case - after all, saying "you can't build Code Search on PCRE, but you can on RE2" is just as effective to prove the effectiveness of lowering algorithmic complexity. It's just that OP's question was about compilation, so to talk about why OP's question *is* relevant, we need to talk about what would happen if the answer *wasn't* "it's linear". (I also genuinely don't understand the instinct to tell someone "why would you care?" instead of telling them the answer, FWIW. Especially in a case like this, where the answer is pretty simple) I'm pretty sure Robert is not arguing that the scaling problems of the > regex implementation used by Perl, and too many others, can be mitigated > simply by limiting the size of the string to be matched by the regex. If > compiling a regex of reasonable length takes a non-negligible amount of > time something is wrong. > > On Mon, Jun 8, 2020 at 3:22 PM Wojciech S. Czarnecki <o...@fairbe.org> > wrote: > >> Dnia 2020-06-08, o godz. 16:22:24 >> Robert Engels <reng...@ix.netcom.com> napisał(a): >> >> > it is trivial to limit the input size to something a user could input. >> >> With exponential complexity simple regex /(x+x+)+y/ blows up at input of >> 20 to 30 x-es. >> See: https://www.regular-expressions.info/catastrophic.html >> >> [Cut long explanations... Axel just posted most of what I was writing >> regarding trade-offs). >> >> Hope this helps, >> >> -- >> Wojciech S. Czarnecki >> << ^oo^ >> OHIR-RIPE >> >> -- >> You received this message because you are subscribed to the Google Groups >> "golang-nuts" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to golang-nuts+unsubscr...@googlegroups.com. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/golang-nuts/20200609002207.0a161adf%40xmint >> . >> > > > -- > Kurtis Rader > Caretaker of the exceptional canines Junior and Hank > > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/golang-nuts/CABx2%3DD9sKeHnqUAqB61y5Ts-U_f%2BctVAuS4BC0ae8phhhcp1iw%40mail.gmail.com > <https://groups.google.com/d/msgid/golang-nuts/CABx2%3DD9sKeHnqUAqB61y5Ts-U_f%2BctVAuS4BC0ae8phhhcp1iw%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfGnRrAt%3Dx3buNcfoOc9xGqVj_tfMEviU%3D7Amjw01e%3Df_w%40mail.gmail.com.
