From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.bugs Subject: bug#18577: Regexp I-search: [(error Stack overflow in regexp matcher)] Date: Sun, 28 Sep 2014 13:35:30 -0400 Message-ID: References: <20140928085554.GA3157@acm.acm> <87mw9kt3m7.fsf@igel.home> <20140928123717.GC3157@acm.acm> <87d2afud0p.fsf@igel.home> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1411925796 13522 80.91.229.3 (28 Sep 2014 17:36:36 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 28 Sep 2014 17:36:36 +0000 (UTC) Cc: Alan Mackenzie , 18577@debbugs.gnu.org To: Andreas Schwab Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sun Sep 28 19:36:29 2014 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XYIOY-0007dh-KH for geb-bug-gnu-emacs@m.gmane.org; Sun, 28 Sep 2014 19:36:26 +0200 Original-Received: from localhost ([::1]:60475 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XYIOY-0000JO-9R for geb-bug-gnu-emacs@m.gmane.org; Sun, 28 Sep 2014 13:36:26 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:47286) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XYION-0000BR-WE for bug-gnu-emacs@gnu.org; Sun, 28 Sep 2014 13:36:23 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1XYIOG-0008ON-H1 for bug-gnu-emacs@gnu.org; Sun, 28 Sep 2014 13:36:15 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:34727) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1XYIOG-0008Mz-DQ for bug-gnu-emacs@gnu.org; Sun, 28 Sep 2014 13:36:08 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1XYIOA-00011D-Iq for bug-gnu-emacs@gnu.org; Sun, 28 Sep 2014 13:36:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Stefan Monnier Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 28 Sep 2014 17:36:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 18577 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: Original-Received: via spool by 18577-submit@debbugs.gnu.org id=B18577.14119257353870 (code B ref 18577); Sun, 28 Sep 2014 17:36:02 +0000 Original-Received: (at 18577) by debbugs.gnu.org; 28 Sep 2014 17:35:35 +0000 Original-Received: from localhost ([127.0.0.1]:54521 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XYINi-00010M-KV for submit@debbugs.gnu.org; Sun, 28 Sep 2014 13:35:34 -0400 Original-Received: from pruche.dit.umontreal.ca ([132.204.246.22]:41203) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1XYINf-00010B-En for 18577@debbugs.gnu.org; Sun, 28 Sep 2014 13:35:32 -0400 Original-Received: from fmsmemgm.homelinux.net (lechon.iro.umontreal.ca [132.204.27.242]) by pruche.dit.umontreal.ca (8.14.1/8.14.1) with ESMTP id s8SHZSZa025181; Sun, 28 Sep 2014 13:35:28 -0400 Original-Received: by fmsmemgm.homelinux.net (Postfix, from userid 20848) id 7457AAE80E; Sun, 28 Sep 2014 13:35:30 -0400 (EDT) In-Reply-To: <87d2afud0p.fsf@igel.home> (Andreas Schwab's message of "Sun, 28 Sep 2014 14:48:22 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (gnu/linux) X-NAI-Spam-Flag: NO X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0 X-NAI-Spam-Rules: 1 Rules triggered RV5078=0 X-NAI-Spam-Version: 2.3.0.9378 : core <5078> : inlines <1340> : streams <1302333> : uri <1819223> X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:93832 Archived-At: >> Is this a defect in my regexp or in the regexp engine? > It is fundamental to the way regexp matching works. To clarify: it is fundamental to the way *our* regexp engine works. As long as the regexp doesn't use backrefs, it can be matched efficiently, without backtracking. Of course using \(..\) (as opposed to using \(?:..\)) can also make the problem harder since the various different (but largely equivalent) ways to match might need to be distinguishable via match-data. But even tho your regexp doesn't use backrefs, and even if you replace all \(..\) with \(?:..\), your regexp will still cause problems because our regexp engine does not try to optimize these kinds of cases. So you have to do it by hand. >> If the former, how could I rewrite the regexp so that it would not hit >> these problems? Maybe something like: /\*\(\)*\*+/ where is something like [^'*]\|\*+\([^/'*]\|'\)\|' where is something like \([^'*]\|\*+[^/'*]\)*' Tho this will still push a backtrack point for every character. Maybe better would be something like /\*[^'*]*\(\)*\*+/ where is something like \(\*+[^/'*]\|\**'\)[^'*]* where is still something like \([^'*]\|\*+[^/'*]\)*' so that we should only push a backtrace point when we see a * or a ' in the comment. Stefan