bug#6640: 23.2; Why is this regexp search taking so long? (and will it end?)

bug#6640: 23.2; Why is this regexp search taking so long? (and will it end?)

[Ryan Rix]

michael@cadilhac.name "(Michaël" Cadilhac) writes:
> - emacs -Q
> - Clear the scratch buffer, and paste:
>
[redact]
>
> (a small input would give quite the same result).
> - M-< C-- C-s ^\([^:]*:[^:]*\)\{9\}
>
>   (everything works fine till now)
>
> add an $ to the regexp.
>
> - FEAR the possible endless loop (and the actual unexpected result of
>   taking long time).
>
> With an 8 in place of the 9, it takes a long time, but not possibly
> endless.
>
> Thanks!

Hi Michael,

Thanks for reporting this. I can confirm this is still an issue in the
latest emacs-25, commit e51b27ec2ce214ef3d8377a27ee9d857bcc66afc

I will leave it to smarter minds than my own to debug the regex engine,
though.

bug#6640: 23.2; Why is this regexp search taking so long? (and will it end?)

[Noam Postavsky]

I haven't actually debugged the regexp engine, but I believe the
problem is that this regexp contains several repetitions of [^:]*[^:]*
(which becomes apparent if you expand the \{9\}). The regexp engine
isn't smart enough to coalesce them so when the match fails (due to
$), it has to go back and retry with all the possible different
matches to see if it will work that way. There are A^n possible
matches to try, where A is the length of non-colon string in the
buffer, and n is the number of [^:]*[^:]* sequences in the regexp
(which is 8 if \{9\} is used).

A regexp which should match the same thing is ^\([^:]*:\)\{9\}[^:]*
and ^\([^:]*:\)\{9\}[^:]*$ will fail to match anything much faster.