GNU logs - #31817, boring messages

Message sent to bug-gnu-emacs@HIDDEN:

Subject: bug#31817: Possible bug in regex search
Resent-From: "Michele Pes" <mp81ss@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Wed, 13 Jun 2018 17:54:03 +0000
Resent-Message-ID: <handler.31817.B.15289124112601 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: 31817 <at> debbugs.gnu.org
Reply-To: Michele Pes <mp81ss@HIDDEN>
From: "Michele Pes" <mp81ss@HIDDEN>
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>
Precedence: list
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>


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&nbsp;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--

Message sent:

Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-Mailer: MIME-tools 5.505 (Entity 5.505)
Content-Type: text/plain; charset=utf-8
X-Loop: help-debbugs@HIDDEN
From: help-debbugs@HIDDEN (GNU bug Tracking System)
To: Michele Pes <mp81ss@HIDDEN>
Subject: bug#31817: Acknowledgement (Possible bug in regex search)
Message-ID: <handler.31817.B.15289124112601.ack <at> debbugs.gnu.org>
References: <1528899618.415948.22587.31975@HIDDEN>
X-Gnu-PR-Message: ack 31817
X-Gnu-PR-Package: emacs
Reply-To: 31817 <at> debbugs.gnu.org
Date: Wed, 13 Jun 2018 17:54:03 +0000

Thank you for filing a new bug report with debbugs.gnu.org.

This is an automatically generated reply to let you know your message
has been received.

Your message is being forwarded to the package maintainers and other
interested parties for their attention; they will reply in due course.

Your message has been sent to the package maintainer(s):
 bug-gnu-emacs@HIDDEN

If you wish to submit further information on this problem, please
send it to 31817 <at> debbugs.gnu.org.

Please do not send mail to help-debbugs@HIDDEN unless you wish
to report a problem with the Bug-tracking system.

--=20
31817: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D31817
GNU Bug Tracking System
Contact help-debbugs@HIDDEN with problems

Message sent to bug-gnu-emacs@HIDDEN:

Subject: bug#31817: Possible bug in regex search
Resent-From: Noam Postavsky <npostavs@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Thu, 14 Jun 2018 00:38:02 +0000
Resent-Message-ID: <handler.31817.B31817.152893668121256 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: "Michele Pes" <mp81ss@HIDDEN>
Cc: 31817 <at> debbugs.gnu.org
From: Noam Postavsky <npostavs@HIDDEN>
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
Precedence: list
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>

"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

Message received at control <at> debbugs.gnu.org:

Received: (at control) by debbugs.gnu.org; 16 Jun 2018 13:55:29 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Sat Jun 16 09:55:29 2018
Received: from localhost ([127.0.0.1]:51738 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1fUBft-0000XA-9g
	for submit <at> debbugs.gnu.org; Sat, 16 Jun 2018 09:55:29 -0400
Received: from mail-io0-f179.google.com ([209.85.223.179]:37270)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <npostavs@HIDDEN>) id 1fUBfs-0000X4-C6
 for control <at> debbugs.gnu.org; Sat, 16 Jun 2018 09:55:28 -0400
Received: by mail-io0-f179.google.com with SMTP id s26-v6so13141421ioj.4
 for <control <at> debbugs.gnu.org>; Sat, 16 Jun 2018 06:55:28 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=from:to:subject:date:message-id:mime-version;
 bh=1aPqTYuBnF+jwc/oCE3TfLU9OokMPaGyn3OVbvycqCE=;
 b=dX+OikGxo5f6iRyZCdPOZAzfw6F/BXH30sT+i9phL1mi4gZeNwVnDSWCtQLhvandub
 H/a8RV8wTiwjTyY0mBy3hFI5qE38R0JxpVqmhgfteYq9XL61YuWr+GzFlaTIGaOxWyZI
 o5mDzDKX5wwfR86cdR6yIhy6i3xgrNfGrAeHPFMkqQ6GQ2zhTn1S47JoisXckigyIBi6
 pRSX9wYhCJ0UyhKuv2JBuuwwkdaJu0SV6zN7nHDyZeNKbpQ5v9GOoTHGQXtV6puDSZ4N
 XYED5rIWaoIaUixa3LjdRTRi5HVwLOuln47+1yUSOY46PNtarBU1kX/4Rd5P0ScXWvO1
 ai7g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:from:to:subject:date:message-id:mime-version;
 bh=1aPqTYuBnF+jwc/oCE3TfLU9OokMPaGyn3OVbvycqCE=;
 b=RYJSCHOucOeVF+qlDiYfbejHoS/frKtzgWKYsNu5tYpuswRqlf8pr3cJupb44Xn+fh
 AFdC8FCb2TO9zUO+Xf8vY/PBrEtin5EOc35LhI5RH1BgKmfsx4Y6syURRe1ANO5em9f4
 FHlJwbHzgN0J2QCStJ/w7t/Qr2Lyopy61qhwOKotpX0vOEaSFEQScsL6y3x5v9a1YmeT
 3uIGPglodJ8wzFb+lYtT3niiA6w0HZEOW/JeHIwuSWvDFnZFh9YxvhRchh5WUJAGZkOR
 pGbA7gail21WrcsjpRgGlYqpqbOp/DbLtR8XV6bhmrIxek2KCD+yiYjzOdwJ0a5CCkfd
 DG1A==
X-Gm-Message-State: APt69E3oJMu1rOgKlqzcer/JnSbsrQ7SSnDCdWy45SEjCnAij+eLqSWU
 8CsE5D1my4CWRijayI+f6NJ0yg==
X-Google-Smtp-Source: ADUXVKJ5SC6QEcr3OS24YcBMQsrs8jkke1h2cSpa9UU9cMIMuU4JBXfdynl2dpQNm/KqZGdnsJUS8A==
X-Received: by 2002:a5e:860f:: with SMTP id
 z15-v6mr4992689ioj.73.1529157322602; 
 Sat, 16 Jun 2018 06:55:22 -0700 (PDT)
Received: from zebian (cbl-45-2-119-34.yyz.frontiernetworks.ca. [45.2.119.34])
 by smtp.googlemail.com with ESMTPSA id
 i10-v6sm2237165itb.38.2018.06.16.06.55.21
 for <control <at> debbugs.gnu.org>
 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256);
 Sat, 16 Jun 2018 06:55:22 -0700 (PDT)
From: Noam Postavsky <npostavs@HIDDEN>
To: control <at> debbugs.gnu.org
Subject: control message for bug #6640
Date: Sat, 16 Jun 2018 09:55:21 -0400
Message-ID: <878t7evnsm.fsf@HIDDEN>
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: 0.0 (/)
X-Debbugs-Envelope-To: control
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 (-)

merge 6640 31817 
quit

Message received at control <at> debbugs.gnu.org:

Received: (at control) by debbugs.gnu.org; 2 Apr 2019 01:20:12 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Mon Apr 01 21:20:12 2019
Received: from localhost ([127.0.0.1]:40190 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1hB860-0001pp-De
	for submit <at> debbugs.gnu.org; Mon, 01 Apr 2019 21:20:12 -0400
Received: from mail-qt1-f170.google.com ([209.85.160.170]:44638)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <npostavs@HIDDEN>) id 1hB85y-0001pV-Bn
 for control <at> debbugs.gnu.org; Mon, 01 Apr 2019 21:20:10 -0400
Received: by mail-qt1-f170.google.com with SMTP id w5so13077948qtb.11
 for <control <at> debbugs.gnu.org>; Mon, 01 Apr 2019 18:20:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=from:to:subject:date:message-id:mime-version;
 bh=cIYmh7bmSfa0zBRukzUDekfEHPMVEIOthQJnM+Q4wlI=;
 b=L0BuubmCGbhWg41QDDmfSKBVRD9B7Vpgx6yRThTPpY3eospnOJFAlppelM3fPZyqVH
 9bc8CWUupx8/LhNvRztlD+LAPkieNYa9reBZvMJYoKyuYr+fmO8AGZs/082nLKT5CfEU
 axpGdIC9hcMQjhemKw6X+06deO0ob150EGTDk5SX9cRJ9iEQj/s+ab00qndZPvM1u4By
 1luCITAt+1CLFtvV4Z1X5Yh3FEyXNQ4v92PuW9KT0w8tko+OM7t0poHIRqn5mddZhhit
 /o5MfGyP05tCdEm1+OenECj0LwmABMb2/nae6Ja7ayaMSgRMN5wJ789GkqU692p3zZqe
 ZblQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:from:to:subject:date:message-id:mime-version;
 bh=cIYmh7bmSfa0zBRukzUDekfEHPMVEIOthQJnM+Q4wlI=;
 b=ryNY/Kx1rTOZ6gxPKoYMKW73OYEYBwtdTf4suu4Qdz5aV9Qy8omAWP4qL1StEWQ++x
 w/30chKALIg8a1vuNKElkbbBOFe9DjpRr7eUrbaYK61SIMbTC7K8xRNP8o+JyKiXubmQ
 FRIGUHq2XbY0Jh90zfOnCNAAO4H2MDSjzGFLJK+3v+m7n5zgwyKrVgePdHyuCuvW8ds8
 gKkgPqq9EP1/hrL82dsH9bodGANiWzUppV2nUZ9AGYhBN9tjC6JYuDk5wRYR6Uvi+vMi
 TMFxGpQm9frC+XMu+KrNgeHnTMuSL18T+GYsM43gAf/B3T+UtUYzWc8096D4BSF5HuMr
 9Z/w==
X-Gm-Message-State: APjAAAXkt1ssSpZBBoNRPrTeBMT2jOuZ0fItimsJmwNFQFj1PyignlDY
 PJfGvq/OUKrfpY/qURW6ATRj4q2i
X-Google-Smtp-Source: APXvYqygCJ74fvxh5pD0xw9uqkBTD1f2Oxnq4AaeE86G3+H4cdNR8dTFGruxfKEvQ7H1WCE3faRacw==
X-Received: by 2002:ac8:2df8:: with SMTP id q53mr56290591qta.132.1554168004572; 
 Mon, 01 Apr 2019 18:20:04 -0700 (PDT)
Received: from minid (cbl-45-2-119-34.yyz.frontiernetworks.ca. [45.2.119.34])
 by smtp.googlemail.com with ESMTPSA id
 z8sm7466736qth.62.2019.04.01.18.20.03 for <control <at> debbugs.gnu.org>
 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256);
 Mon, 01 Apr 2019 18:20:03 -0700 (PDT)
From: Noam Postavsky <npostavs@HIDDEN>
To: control <at> debbugs.gnu.org
Subject: control message for bug #6640
Date: Mon, 01 Apr 2019 21:20:03 -0400
Message-ID: <878swtgq4c.fsf@HIDDEN>
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: 0.0 (/)
X-Debbugs-Envelope-To: control
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 (-)

merge 6640 34823
quit

Last modified: Mon, 25 Nov 2019 12:00:02 UTC

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997 nCipher Corporation Ltd, 1994-97 Ian Jackson.