* bug#31817: Possible bug in regex search
[not found] <1528899604.595409.22564.45300@mail.rambler.ru>
@ 2018-06-13 14:20 ` Michele Pes
2018-06-14 0:37 ` Noam Postavsky
0 siblings, 1 reply; 2+ messages in thread
From: Michele Pes @ 2018-06-13 14:20 UTC (permalink / raw)
To: 31817
[-- 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")))
^ permalink raw reply [flat|nested] 2+ messages in thread
* bug#31817: Possible bug in regex search
2018-06-13 14:20 ` bug#31817: Possible bug in regex search Michele Pes
@ 2018-06-14 0:37 ` Noam Postavsky
0 siblings, 0 replies; 2+ messages in thread
From: Noam Postavsky @ 2018-06-14 0:37 UTC (permalink / raw)
To: Michele Pes; +Cc: 31817
"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
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2018-06-14 0:37 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
[not found] <1528899604.595409.22564.45300@mail.rambler.ru>
2018-06-13 14:20 ` bug#31817: Possible bug in regex search Michele Pes
2018-06-14 0:37 ` Noam Postavsky
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).