From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.emacs.gnus.general/22203 Path: main.gmane.org!not-for-mail From: Dale Hagglund Newsgroups: gmane.emacs.gnus.general Subject: Re: nnmail-split-header-length-limit is EVIL! Date: 31 Mar 1999 23:02:31 -0800 Sender: owner-ding@hpc.uh.edu Message-ID: <86aewsu8l4.fsf@ponoka.battleriver.com> References: <87sobotazh.fsf@pc-hrvoje.srce.hr> <87u2vxfn00.fsf@pc-hrvoje.srce.hr> <87k8whq4kx.fsf@pc-hrvoje.srce.hr> <863e2nikbe.fsf@ponoka.battleriver.com> <87u2v24b07.fsf@x2-150.mtl.Generation.NET> <86bthaf7rg.fsf@ponoka.battleriver.com> NNTP-Posting-Host: coloc-standby.netfonds.no Mime-Version: 1.0 X-Trace: main.gmane.org 1035160166 26917 80.91.224.250 (21 Oct 2002 00:29:26 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Mon, 21 Oct 2002 00:29:26 +0000 (UTC) Return-Path: Original-Received: from farabi.math.uh.edu (farabi.math.uh.edu [129.7.128.57]) by sclp3.sclp.com (8.8.5/8.8.5) with ESMTP id CAA11350 for ; Thu, 1 Apr 1999 02:04:49 -0500 (EST) Original-Received: from sina.hpc.uh.edu (lists@Sina.HPC.UH.EDU [129.7.3.5]) by farabi.math.uh.edu (8.9.1/8.9.1) with ESMTP id BAB16331; Thu, 1 Apr 1999 01:04:04 -0600 (CST) Original-Received: by sina.hpc.uh.edu (TLB v0.09a (1.20 tibbs 1996/10/09 22:03:07)); Thu, 01 Apr 1999 01:04:13 -0600 (CST) Original-Received: from sclp3.sclp.com (root@sclp3.sclp.com [204.252.123.139]) by sina.hpc.uh.edu (8.7.3/8.7.3) with ESMTP id BAA08769 for ; Thu, 1 Apr 1999 01:04:05 -0600 (CST) Original-Received: from proxy3.ba.best.com (root@proxy3.ba.best.com [206.184.139.14]) by sclp3.sclp.com (8.8.5/8.8.5) with ESMTP id CAA11335 for ; Thu, 1 Apr 1999 02:03:57 -0500 (EST) Original-Received: from best.com (dynamic24.pm01.pleasanton.best.com [204.156.131.24]) by proxy3.ba.best.com (8.9.3/8.9.2/best.out) with ESMTP id XAA08468 for ; Wed, 31 Mar 1999 23:02:35 -0800 (PST) Original-Received: (from rdh@localhost) by best.com (8.8.5/8.8.5) id XAA15770; Wed, 31 Mar 1999 23:02:32 -0800 (PST) Original-To: ding@gnus.org In-Reply-To: Peter Seibel's message of "31 Mar 1999 18:54:48 -0800" Original-Lines: 35 User-Agent: Gnus/5.070066 (Pterodactyl Gnus v0.66) Emacs/20.3 Precedence: list X-Majordomo: 1.94.jlt7 Xref: main.gmane.org gmane.emacs.gnus.general:22203 X-Report-Spam: http://spam.gmane.org/gmane.emacs.gnus.general:22203 Peter Seibel writes: > >>>>> "Dale" == Dale Hagglund writes: > > Dale> I haven't seen any examples of complete regular > Dale> expressions that cause the problems we're talking about > Dale> here . . . . Do we have any known regexp/string pairs > Dale> that deonstrate the problem? > > Try eval'ing the expression below with the data line below it. It'll > run quickly as is. Then add a's on the end of one or two at a time and > watch it slow down. > (search-forward-regexp "\\(.*\\)*x") > > xaaaaaa > > [A good description of the exponential backracking in the previous > regexp and a pointer to Friedl's _Mastering Regular Expressions_ > deleted. --rdh] Umm, I've read Friedl's book (I agree it's excellent), and I already understand the basic reason regexps show exponential time behaviour. I guess I wasn't precise enough. I was asking for known regexps from gnus split processing and corresponding header lines that show exponential behaviour, not a generic example that demonstrates how it can happen on contrived input. (I have no problems with your example as such; it nicely demonstrates how easily exponential matching time can arise. But, I'd like to see a regexp/string pair with this problem that shows up in real use of gnus.) Dale.