News for hackers. Stuff that matters.
Re:Regex: badly needs fuzzing by flogic on Wednesday February 08, 2017 @01:47PM (#13600869)
In my experience, the exponential time thing isn't really a big deal. I've used Perl regular expressions on a very regular basis for about 16 years now. Exponential time has been an issue only once. Obviously if I were accepting regular expressions from random people, I'd use RE2. But for my day to day purposes, it's pretty much a complete non issue.
Re:Regex: badly needs fuzzing by kbenson on Wednesday February 08, 2017 @01:57PM (#13600956)
> Obviously if I were accepting regular expressions from random people, I'd use RE2.

And if you're using Perl, it's not hard to do so[1]. Pluggable regex engines FTW. :)

1: https://metacpan.org/pod/re::engine::RE2

Re:Regex: badly needs fuzzing by kmike84 on Wednesday February 08, 2017 @03:29PM (#13601735)
re2 is not only about exponential time: matching of regexes like a|b|c is O(N) in backtracking engines and O(1) in DFA-based engines like re2. It can make a big difference in practice for generated regexes - e.g. if you want to check if an URL has one of the thousand substrings in it (think adblock-like use cases). With backtracking regex or with a loop it'd be O(N) regarding the number of options, but with DFA it is O(1) regarding the number of options. I've seen 1000x speedups for similar use cases with re2 vs re from Python stdlib.
Re:Regex: badly needs fuzzing by adrianN on Thursday February 09, 2017 @12:24AM (#13604883)
How does the DFA engine match anything without looking at the whole input?
Re:Regex: badly needs fuzzing by haldean on Thursday February 09, 2017 @01:17AM (#13605078)
I think s/he meant to say O(nm) vs O(m), n being the number of branches in the regex and m being the length of the input.