From: Noam Postavsky <npostavs@gmail.com>
To: "Michele Pes" <mp81ss@rambler.ru>
Cc: 31817@debbugs.gnu.org
Subject: bug#31817: Possible bug in regex search
Date: Wed, 13 Jun 2018 20:37:51 -0400 [thread overview]
Message-ID: <87sh5qw6cg.fsf@gmail.com> (raw)
In-Reply-To: <1528899618.415948.22587.31975@mail.rambler.ru> (Michele Pes's message of "Wed, 13 Jun 2018 17:20:18 +0300")
"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
prev parent reply other threads:[~2018-06-14 0:37 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
[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 [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87sh5qw6cg.fsf@gmail.com \
--to=npostavs@gmail.com \
--cc=31817@debbugs.gnu.org \
--cc=mp81ss@rambler.ru \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.