From mboxrd@z Thu Jan  1 00:00:00 1970
Path: news.gmane.org!not-for-mail
From: Ilya Zakharevich <nospam-abuse@ilyaz.org>
Newsgroups: gmane.emacs.help
Subject: Re: Stack overflow in regexp matcher
Date: Thu, 17 Dec 2009 22:10:55 +0000 (UTC)
Organization: U.C. Berkeley Math. Department.
Message-ID: <slrnhilb3f.77e.nospam-abuse@powdermilk.math.berkeley.edu>
References: <8u-dncYjy6Q3iLTWnZ2dnUVZ8nKdnZ2d@posted.visi>
	<barmar-79113E.12011017122009@news.eternal-september.org>
NNTP-Posting-Host: lo.gmane.org
X-Trace: ger.gmane.org 1261089657 30898 80.91.229.12 (17 Dec 2009 22:40:57 GMT)
X-Complaints-To: usenet@ger.gmane.org
NNTP-Posting-Date: Thu, 17 Dec 2009 22:40:57 +0000 (UTC)
To: help-gnu-emacs@gnu.org
Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Thu Dec 17 23:40:51 2009
Return-path: <help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org>
Envelope-to: geh-help-gnu-emacs@m.gmane.org
Original-Received: from lists.gnu.org ([199.232.76.165])
	by lo.gmane.org with esmtp (Exim 4.50)
	id 1NLP1c-00085b-3L
	for geh-help-gnu-emacs@m.gmane.org; Thu, 17 Dec 2009 23:40:48 +0100
Original-Received: from localhost ([127.0.0.1]:54371 helo=lists.gnu.org)
	by lists.gnu.org with esmtp (Exim 4.43)
	id 1NLP1b-00042J-Uy
	for geh-help-gnu-emacs@m.gmane.org; Thu, 17 Dec 2009 17:40:48 -0500
Original-Path: news.stanford.edu!usenet.stanford.edu!goblin2!goblin.stu.neva.ru!feeder.erje.net!feeder.eternal-september.org!eternal-september.org!not-for-mail
Original-Newsgroups: gnu.emacs.help
Original-Lines: 18
Original-X-Trace: news.eternal-september.org
	U2FsdGVkX186fxi6RRJJ2Zw141RoCgrBaYEyQJs+R3ExBR8RKqwqQmD/cCb97XdFrWReJea7D7tY5XGHgH9O6WP1npF0nzkZ/MgY5+uljOinmPlsna9KgJNYXhP3WPlwqCgd4WsEFbAD2XiER7vpFg==
Original-X-Complaints-To: abuse@eternal-september.org
Original-NNTP-Posting-Date: Thu, 17 Dec 2009 22:10:55 +0000 (UTC)
User-Agent: slrn/0.9.8.1pl1 (Linux)
X-Auth-Sender: U2FsdGVkX19EHKEY3FxvOGNcG6BaaAfcU9Ul++duVDo=
Cancel-Lock: sha1:EgSSWar/BEg0HN0DdmTTDOCvpMY=
Original-Xref: news.stanford.edu gnu.emacs.help:175638
X-BeenThere: help-gnu-emacs@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Users list for the GNU Emacs text editor <help-gnu-emacs.gnu.org>
List-Unsubscribe: <http://lists.gnu.org/mailman/listinfo/help-gnu-emacs>,
	<mailto:help-gnu-emacs-request@gnu.org?subject=unsubscribe>
List-Archive: <http://lists.gnu.org/pipermail/help-gnu-emacs>
List-Post: <mailto:help-gnu-emacs@gnu.org>
List-Help: <mailto:help-gnu-emacs-request@gnu.org?subject=help>
List-Subscribe: <http://lists.gnu.org/mailman/listinfo/help-gnu-emacs>,
	<mailto:help-gnu-emacs-request@gnu.org?subject=subscribe>
Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org
Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org
Xref: news.gmane.org gmane.emacs.help:70712
Archived-At: <http://permalink.gmane.org/gmane.emacs.help/70712>

On 2009-12-17, Barry Margolin <barmar@alum.mit.edu> wrote:
>> A function of mine gets "Stack overflow in regexp matcher" on a certain 
>> file using the regexp
>> 
>>      "^< \\(.+].+=|\\)"

> The problem is that + is greedy, so this has to scan the entire line 
> looking for the last "]", then see if there's an "=" somewhere later.  
> If it can't find an "=" it has to back up to the previous "]" and search 
> again, and so on.  If there are lots of "]" characters, this has to save 
> the state of each of them in the matching stack.

What for?  There is no need to keep state of unsuccessful matches...

So the "next-]" state should replace the older one.

Yours,
Ilya