Ray, only the discussion is exponential. On Mon, Jun 8, 2020 at 4:23 PM 'Axel Wagner' via golang-nuts < golang-nuts@googlegroups.com> wrote:
> 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 > <https://groups.google.com/d/msgid/golang-nuts/CAEkBMfGnRrAt%3Dx3buNcfoOc9xGqVj_tfMEviU%3D7Amjw01e%3Df_w%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- *Michael T. jonesmichael.jo...@gmail.com <michael.jo...@gmail.com>* -- 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/CALoEmQwXi99-PCpfrwzgfBkk5H6-u82ROYeNG9%2B-0yeNirDx-g%40mail.gmail.com.
