Mailing-List: contact zsh-workers-help@zsh.org; run by ezmlm Precedence: bulk X-No-Archive: yes List-Id: Zsh Workers List List-Post: List-Help: X-Spam-Checker-Version: SpamAssassin 3.4.1 (2015-04-28) on f.primenet.com.au X-Spam-Level: X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,MISSING_HEADERS autolearn=no autolearn_force=no version=3.4.1 X-Originating-IP: [86.21.161.213] X-Spam: 0 X-Authority: v=2.1 cv=GYXq5ljL c=1 sm=1 tr=0 a=oo3MgO7t/4XyXFuSzI3dDQ==:117 a=oo3MgO7t/4XyXFuSzI3dDQ==:17 a=L9H7d07YOLsA:10 a=9cW_t1CCXrUA:10 a=s5jvgZ67dGcA:10 a=kj9zAlcOel0A:10 a=NLZqzBF-AAAA:8 a=2BymRHSAaIIirApP2PEA:9 a=CjuIK1q_8ugA:10 a=wW_WBVUImv98JQXhvVPZ:22 Date: Sun, 5 Jun 2016 21:39:51 +0100 From: Peter Stephenson Cc: Zsh hackers list Subject: Re: [BUG] Long line makes pattern matching (by //) hog Zsh Message-ID: <20160605213951.4af7294a@ntlworld.com> In-Reply-To: <20160605203708.3701c7a2@ntlworld.com> References: <160605121020.ZM7727@torch.brasslantern.com> <20160605203708.3701c7a2@ntlworld.com> X-Mailer: Claws Mail 3.11.1 (GTK+ 2.24.28; x86_64-redhat-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Seq: zsh-workers 38619 On Sun, 5 Jun 2016 20:37:08 +0100 Peter Stephenson wrote: > The problem is the patterns are pathological. Each of them can match > the same characters. So it's spending a lot of time repartitioning the > mathches between the possibilities of 1. and 2. and 3. in the above. > That's not polynomially bounded. I'm not sure if it's even > exponentially bounded. > > What I'm not sure is if there's a way of improving this without some > special case or, obviously, making the patterns more specific. We are maybe being naive in treating [...] expressions as if they are "simple". I think we have better protection against pathological backtracking for more complicated patterns. Does the following help? pws diff --git a/Src/pattern.c b/Src/pattern.c index 4e2f236..bec980f 100644 --- a/Src/pattern.c +++ b/Src/pattern.c @@ -1425,7 +1425,7 @@ patcomppiece(int *flagp, int paren) case Inbrack: DPUTS(zpc_special[ZPC_INBRACK] == Marker, "Treating '[' as pattern character although disabled"); - flags |= P_SIMPLE; + /*flags |= P_SIMPLE;*/ if (*patparse == Hat || *patparse == Bang) { patparse++; starter = patnode(P_ANYBUT);