bug#31817: Possible bug in regex search

[Noam Postavsky]

"Michele Pes" <mp81ss@rambler.ru> writes:

> Hi,I'm working with regex, and I isolated an unexpected behaviour.If I paste
> attached code code in scratch buffer and evaluate it, emacs hangs (cpu stays 
> at
> 100% until I kill emacs)

This is because the current regexp engine is implemented with
backtracking, so certain patterns trigger an exponential amount of
searching.

> (let (
>       (regex
>        (concat "[ \f\t\n\r\v]" "*\\(" "_*[[:alpha:]]+[A-Z0-9a-z_]*"

So here, [[:alpha:]]+ and [A-Z0-9a-z_]* have a lot of overlap, so when
matching against "void", for example, the matcher could match
[[:alpha:]]+ with "v", "vo", "voi", or "void".  And for each of these it
goes and matches the rest of the pattern (with additional backtracking)
all of which takes a long time.

It's better to use non-overlapping matches, like

(let ((regex
       (concat "[ \f\t\n\r\v]*"
               "\\(" "[_[:alpha:]][A-Z0-9a-z_]*" "[ \f\t\n\r\v\\*]*" "\\)+"
               "(" "[ \f\t\n\r\v]*" "\\*?" "[ \f\t\n\r\v]*"
               "\\(" "[_[:alpha:]][A-Z0-9a-z_]*" "\\)"
               "[ \f\t\n\r\v]*" "[()]"))
      (x "void Vsdk_Init(void) {     /* Open watchdog iwdt driver, watchdog is 
running now */     iwdt.p_api->open"))
  (if (and (string-match "(" x)
           (string-match regex x))
      (match-string 2 x)
    (message "did not match")))

Also note, if you meant the regex to match starting from the beginning
of the string, you should prefix it with "\\`", so that the string-match
won't try other positions.

Further reading:

https://en.wikipedia.org/wiki/ReDoS
https://swtch.com/~rsc/regexp/regexp1.html