Noam Postavsky <npostavs@HIDDEN>
to control <at> debbugs.gnu.org.
Full text available.Noam Postavsky <npostavs@HIDDEN>
to control <at> debbugs.gnu.org.
Full text available.
Received: (at 31817) by debbugs.gnu.org; 14 Jun 2018 00:38:01 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Wed Jun 13 20:38:01 2018
Received: from localhost ([127.0.0.1]:47082 helo=debbugs.gnu.org)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
id 1fTGH3-0005Wh-B8
for submit <at> debbugs.gnu.org; Wed, 13 Jun 2018 20:38:01 -0400
Received: from mail-io0-f173.google.com ([209.85.223.173]:39048)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <npostavs@HIDDEN>) id 1fTGH1-0005WV-K7
for 31817 <at> debbugs.gnu.org; Wed, 13 Jun 2018 20:38:00 -0400
Received: by mail-io0-f173.google.com with SMTP id f1-v6so5403815ioh.6
for <31817 <at> debbugs.gnu.org>; Wed, 13 Jun 2018 17:37:59 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=from:to:cc:subject:references:date:in-reply-to:message-id
:user-agent:mime-version;
bh=63IHoFuqT3BjLn1h99n8o01eLdjeZMcdedbJEthLe1Q=;
b=DtzoSL5UqOwEUt1KSHgiZiTdIOilWqKKmY/R5A9ZWm92HlXW6BDAHYpIsLQAeTNQFl
UeluJPZHDb5qK5EEF3fIqohmDwOPQCbhbdLREG6D8AX3ZE30+kov1y2DfOToGiAmXi7f
SReALHUm7W/3Zfz/1PRq2OdkaKNHgDi7pK4y37GVEM4+C8wZmnbaCoaJ3O2/ov61fyMf
l0hrHafO/aOXk5ZkRofTFxSrexji7ytZ6snKhOSGtszfKrp2HDIjmgbWWcUHv33PIu4r
6IYUYIq189GFwG5+y/G+5lyJg4TgkL3eHsrX8FkoZnotbXrsblGgwG+8dIq1i9yVsyNP
TXtQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to
:message-id:user-agent:mime-version;
bh=63IHoFuqT3BjLn1h99n8o01eLdjeZMcdedbJEthLe1Q=;
b=mNrr1q11SF/jIcAfpdpoac/oDdqbqC8fxUWQfOEDuwV/u0FXzdmv8TXwwlkXJEQxcf
mJpykuBM0Ft9bO8QhihF6FUJkEtfmhTP4mI3XmTAGGve/xKdrQieyjTnnlvywJVcvoq4
Bc7GvFfStzMLdT7n1hto+x9A1HMap4kspZjki9JsRFvalrm9rgsiMSbM3Jx26jJ2jxT5
0aGekbWj4jXdWVQwKhyWRoVmhkxM7FbpUrtJoBTiba+Yz7rBzXQbIACaa9UG6AyMxfO0
jXIBV73Z7v8hyOrN4ONyjRHv5gCqCmA39nly64vPX0zSQlFfmlGpg/3DwK3adBfg5GaA
FTAg==
X-Gm-Message-State: APt69E1qvov2csmaV6IVR+Wo5L9UiJtUFKF91KJ/DVkrAiQGiYsQDlsZ
PFehzrSIY6BoRlDBGb1HKc3Sqw==
X-Google-Smtp-Source: ADUXVKLlf0LOhJZZqAAH/aR2shRU4C44aQMDuP0Mbwjmr9/oNdSQJDaC6DiotViVbh+ZphNHNSGKmA==
X-Received: by 2002:a6b:2286:: with SMTP id
i128-v6mr349940ioi.289.1528936673972;
Wed, 13 Jun 2018 17:37:53 -0700 (PDT)
Received: from zebian (cbl-45-2-119-34.yyz.frontiernetworks.ca. [45.2.119.34])
by smtp.googlemail.com with ESMTPSA id
e6-v6sm1411324iog.7.2018.06.13.17.37.52
(version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256);
Wed, 13 Jun 2018 17:37:53 -0700 (PDT)
From: Noam Postavsky <npostavs@HIDDEN>
To: "Michele Pes" <mp81ss@HIDDEN>
Subject: Re: bug#31817: Possible bug in regex search
References: <1528899604.595409.22564.45300@HIDDEN>
<1528899618.415948.22587.31975@HIDDEN>
Date: Wed, 13 Jun 2018 20:37:51 -0400
In-Reply-To: <1528899618.415948.22587.31975@HIDDEN> (Michele Pes's
message of "Wed, 13 Jun 2018 17:20:18 +0300")
Message-ID: <87sh5qw6cg.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.1 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: 0.0 (/)
X-Debbugs-Envelope-To: 31817
Cc: 31817 <at> debbugs.gnu.org
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>,
<mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)
"Michele Pes" <mp81ss@HIDDEN> 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
bug-gnu-emacs@HIDDEN:bug#31817; Package emacs.
Full text available.Received: (at submit) by debbugs.gnu.org; 13 Jun 2018 17:53:31 +0000 From debbugs-submit-bounces <at> debbugs.gnu.org Wed Jun 13 13:53:31 2018 Received: from localhost ([127.0.0.1]:46881 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>) id 1fT9xa-0000fs-QZ for submit <at> debbugs.gnu.org; Wed, 13 Jun 2018 13:53:31 -0400 Received: from eggs.gnu.org ([208.118.235.92]:54457) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from <mp81ss@HIDDEN>) id 1fT6eo-0006lk-UJ for submit <at> debbugs.gnu.org; Wed, 13 Jun 2018 10:21:56 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from <mp81ss@HIDDEN>) id 1fT6ei-0000n7-M6 for submit <at> debbugs.gnu.org; Wed, 13 Jun 2018 10:21:49 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50,FREEMAIL_FROM, HTML_MESSAGE,T_DKIM_INVALID autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:41606) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from <mp81ss@HIDDEN>) id 1fT6ei-0000ms-HZ for submit <at> debbugs.gnu.org; Wed, 13 Jun 2018 10:21:48 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:45423) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from <mp81ss@HIDDEN>) id 1fT6eh-0003Gt-6x for bug-gnu-emacs@HIDDEN; Wed, 13 Jun 2018 10:21:48 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from <mp81ss@HIDDEN>) id 1fT6ec-0000Z2-VR for bug-gnu-emacs@HIDDEN; Wed, 13 Jun 2018 10:21:47 -0400 Received: from mxout3.rambler.ru ([81.19.78.102]:9329) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from <mp81ss@HIDDEN>) id 1fT6ec-0005Kl-CW for bug-gnu-emacs@HIDDEN; Wed, 13 Jun 2018 10:21:42 -0400 Received: from saddam1.rambler.ru (saddam1.rambler.ru [10.32.16.1]) by mxout3.rambler.ru (Postfix) with ESMTP id D48D37C0244 for <bug-gnu-emacs@HIDDEN>; Wed, 13 Jun 2018 17:20:18 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rambler.ru; s=mail; t=1528899619; bh=5A/q9hX/lZk1HGitxVcDAJGATxMFtTOjuqF8e0+xhr8=; h=From:To:Reply-To:Subject:Date:In-Reply-To:References; b=a5e94aHuOFnLb07nT2FTBDHcfGrdrYf/zsl4yA024Gf7VFjuJ/O+DZMNiqjmU4EA3 2xuCBNB6vQneygUBvvxRw2W1Xv0OQrugMB4cYg6i7NU7c/vk8sg+5UUm6/LYpfGEQf yHcWyFQHiLJ6pU7IAoCJLPr5/LSBmcnnPo5IwR2E= Received: from localhost.localdomain (localhost [127.0.0.1]) by saddam1.rambler.ru (Postfix) with ESMTP id C503D253B02 for <bug-gnu-emacs@HIDDEN>; Wed, 13 Jun 2018 17:20:18 +0300 (MSK) Received: from [79.8.93.92] by mail.rambler.ru with HTTP; Wed, 13 Jun 2018 17:20:18 +0300 From: "Michele Pes" <mp81ss@HIDDEN> To: bug-gnu-emacs@HIDDEN Subject: Possible bug in regex search Date: Wed, 13 Jun 2018 17:20:18 +0300 Content-Transfer-Encoding: 7bit Content-Type: multipart/mixed; boundary="_----------=_15288996182258762" In-Reply-To: <1528899604.595409.22564.45300@HIDDEN> Message-Id: <1528899618.415948.22587.31975@HIDDEN> MIME-Version: 1.0 References: <1528899604.595409.22564.45300@HIDDEN> X-Mailer: Rambler WebMail, http://mail.rambler.ru/ X-Rambler-User: mp81ss@HIDDEN/79.8.93.92 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.0 (----) X-Debbugs-Envelope-To: submit X-Mailman-Approved-At: Wed, 13 Jun 2018 13:53:29 -0400 X-BeenThere: debbugs-submit <at> debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: <debbugs-submit.debbugs.gnu.org> List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe> List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/> List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org> List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help> List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe> Reply-To: Michele Pes <mp81ss@HIDDEN> Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org> X-Spam-Score: -5.0 (-----) This is a multi-part message in MIME format. --_----------=_15288996182258762 Content-Type: multipart/alternative; boundary="_----------=_15288996182258763" This is a multi-part message in MIME format. --_----------=_15288996182258763 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8"; format="flowed" 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 stay= s 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-O= 2-with-modules.7z/download The variable case-fold-search is set to t. Can you help me? Thank you very much, Michele Pes --_----------=_15288996182258763 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset="utf-8" <div>Hi,</div><div>I'm working with regex, and I isolated an unexpected beh= aviour.</div><div>If I paste attached code code in scratch buffer and evalu= ate it, emacs hangs (cpu stays at 100% until I kill emacs)</div><div>Im run= ning emacs for windows x64, in particular this package:</div><div><br data-= mce-bogus=3D"1"></div><div>https://sourceforge.net/projects/emacsbinw64/fil= es/release/emacs-w64-25.3-O2-with-modules.7z/download</div><div><br data-mc= e-bogus=3D"1"></div><div>The variable case-fold-search is set to t.</d= iv><div><br data-mce-bogus=3D"1"></div><div>Can you help me?</div><div><br>= </div><div>Thank you very much,</div><div><br data-mce-bogus=3D"1"></div><d= iv>Michele Pes</div><div><br></div>= --_----------=_15288996182258763-- --_----------=_15288996182258762 Content-Disposition: attachment; filename="bug.el" Content-Transfer-Encoding: base64 Content-Type: application/octet-stream; name="bug.el" KGxldCAoDQogICAgICAocmVnZXgNCiAgICAgICAoY29uY2F0ICJbIFxmXHRc blxyXHZdIiAiKlxcKCIgIl8qW1s6YWxwaGE6XV0rW0EtWjAtOWEtel9dKiIN CiAgICAgICAgICAgICAgICJbIFxmXHRcblxyXHZcXCpdIg0KICAgICAgICAg ICAgICAgIipcXCkrKCIgIlsgXGZcdFxuXHJcdl0iDQogICAgICAgICAgICAg ICAiKlxcKiIgIlsgXGZcdFxuXHJcdl0iDQogICAgICAgICAgICAgICAiKlxc KCIgIl8qW1s6YWxwaGE6XV0rW0EtWjAtOWEtel9dKiIgIlxcKSINCiAgICAg ICAgICAgICAgICJbIFxmXHRcblxyXHZdIiAiKlsoKV0iKSkNCg0KICAgICAg KHggInZvaWQgVnNka19Jbml0KHZvaWQpIHsgICAgIC8qIE9wZW4gd2F0Y2hk b2cgaXdkdCBkcml2ZXIsIHdhdGNoZG9nIGlzIHJ1bm5pbmcgbm93ICovICAg ICBpd2R0LnBfYXBpLT5vcGVuIikpDQogIChpZiAoc3RyaW5nLW1hdGNoICIo IiB4KQ0KICAgICAgKHByb2cyDQogICAgICAgICAgKHN0cmluZy1tYXRjaCBy ZWdleCB4KQ0KICAgICAgICAgIChtYXRjaC1zdHJpbmcgMiB4KSkNCiAgICAo bWVzc2FnZSAiZGlkIG5vdCBtYXRjaCIpKSkNCg== --_----------=_15288996182258762--
Michele Pes <mp81ss@HIDDEN>:bug-gnu-emacs@HIDDEN.
Full text available.bug-gnu-emacs@HIDDEN:bug#31817; Package emacs.
Full text available.
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997 nCipher Corporation Ltd,
1994-97 Ian Jackson.