[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#31817: Possible bug in regex search
From: |
Noam Postavsky |
Subject: |
bug#31817: Possible bug in regex search |
Date: |
Wed, 13 Jun 2018 20:37:51 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/26.1 (gnu/linux) |
"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