Subject: Re: [BUG] Long line makes pattern matching (by //) hog Zsh
From: Peter Stephenson <[email-masked]>
Cc: Zsh hackers list <[email-masked]>
Date: Sun, 5 Jun 2016 21:39:51 +0100
List-Id: Zsh Workers List <zsh-workers.zsh.org>

On Sun, 5 Jun 2016 20:37:08 +0100
Peter Stephenson <[email-masked]> 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);