bug#31817: Possible bug in regex search

bug#31817: Possible bug in regex search

[Michele Pes]

[-- Attachment #1.1: Type: text/plain, Size: 447 bytes --]

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)Im running emacs for windows x64, in particular this
package:
https://sourceforge.net/projects/emacsbinw64/files/release/emacs-w64-25.3-O2-with-modules.7z/download
The variable case-fold-search is set to t.
Can you help me?
Thank you very much,
Michele Pes

[-- Attachment #1.2: Type: text/html, Size: 702 bytes --]

[-- Attachment #2: bug.el --]
[-- Type: application/octet-stream, Size: 568 bytes --]

(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 (string-match "(" x)
      (prog2
          (string-match regex x)
          (match-string 2 x))
    (message "did not match")))

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