https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78276
Tim Shen <timshen at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |timshen at gcc dot gnu.org
--- Comment #1 from Tim Shen <timshen at gcc dot gnu.org> ---
(In reply to idrazil from comment #0)
> Created attachment 40006 [details]
> Example with bug
>
> I tried match this string "<aaaaaaaaaaaaa>\r\n" with regexp
> "(?:[^\r\n]*)*<?(aaaaaaaaaaaaa)>?". GCC 4.9 can solve it almost instantly
> but at 6.2 (I've also tried 6.1) it takes on my computer more than 5 seconds.
>
> I've discovered increasing count of letter "a" also increase (probably
> exponentially) solving time of regexp. The problem goes away when I've
> alternated regexp to "[^\r\n]*<?(aaaaaaaaaaaaa)>?". (In this case the change
> is possible but my original code contains more complex regexp with the same
> problem)
>
> Full example is at the attachment.
We could have thrown error_complexity here, but I didn't implement that yet.
Alternatively, for this particular case, you can pass in
regex_constants::__polynomial. It's not in the standard; it's also slower for
normal cases, but it prevents pathological cases like this.
FYI, I have a talk about different algorithms and runtime efficiency at CppCon:
https://www.youtube.com/watch?v=N_rkHzhXueo
