From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Stack overflow in regexp matcher Date: 16 Oct 2003 14:56:52 -0400 Sender: emacs-devel-bounces+emacs-devel=quimby.gnus.org@gnu.org Message-ID: References: NNTP-Posting-Host: deer.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1066331137 5934 80.91.224.253 (16 Oct 2003 19:05:37 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Thu, 16 Oct 2003 19:05:37 +0000 (UTC) Original-X-From: emacs-devel-bounces+emacs-devel=quimby.gnus.org@gnu.org Thu Oct 16 21:05:35 2003 Return-path: Original-Received: from quimby.gnus.org ([80.91.224.244]) by deer.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 1AADRH-0008Pm-00 for ; Thu, 16 Oct 2003 21:05:35 +0200 Original-Received: from monty-python.gnu.org ([199.232.76.173]) by quimby.gnus.org with esmtp (Exim 3.35 #1 (Debian)) id 1AADRH-0006my-00 for ; Thu, 16 Oct 2003 21:05:35 +0200 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.24) id 1AADNN-0006er-CP for emacs-devel@quimby.gnus.org; Thu, 16 Oct 2003 15:01:33 -0400 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.24) id 1AADLd-0006Ke-Tb for emacs-devel@gnu.org; Thu, 16 Oct 2003 14:59:45 -0400 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.24) id 1AADIv-0005o4-Vr for emacs-devel@gnu.org; Thu, 16 Oct 2003 14:57:29 -0400 Original-Received: from [132.204.24.67] (helo=mercure.iro.umontreal.ca) by monty-python.gnu.org with esmtp (Exim 4.24) id 1AADIt-0005md-Oe for emacs-devel@gnu.org; Thu, 16 Oct 2003 14:56:55 -0400 Original-Received: from vor.iro.umontreal.ca (vor.iro.umontreal.ca [132.204.24.42]) by mercure.iro.umontreal.ca (8.12.9/8.12.9) with ESMTP id h9GIurUN025656 for ; Thu, 16 Oct 2003 14:56:53 -0400 Original-Received: by vor.iro.umontreal.ca (Postfix, from userid 20848) id ED2843C63E; Thu, 16 Oct 2003 14:56:52 -0400 (EDT) Original-To: emacs-devel@gnu.org In-Reply-To: Original-Lines: 19 User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.3.50 X-DIRO-MailScanner: Found to be clean X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.2 Precedence: list List-Id: Emacs development discussions. List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+emacs-devel=quimby.gnus.org@gnu.org Xref: main.gmane.org gmane.emacs.devel:17170 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:17170 > what this might mean? Although, strictly speaking, regular expressions can be matched using a finite-state machine, Emacs's regexp-matcher uses a backtracking matcher and if the backtracking stack is too large you get a stack overflow. In your case "nnfolder.*?sent" might work better. Stefan PS: As for why not use a finite-state machine... well one of the reasons is that it's extra work, another is that Emacs's regexps aren't pure regular expressions (most obviously because of backrefs). Supposedly the latest glibc regexp code uses an FSM, and hopefully someone will hack on it at some point to make it useable for Emacs. In the mean time, you'll have to be careful with regexps to try and avoid excessive stack use.