From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <zsh-workers-return-43849-ml=inbox.vuxu.org@zsh.org>
X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on inbox.vuxu.org
X-Spam-Level: 
X-Spam-Status: No, score=-1.0 required=5.0 tests=MAILING_LIST_MULTI,
	RCVD_IN_DNSWL_NONE autolearn=ham autolearn_force=no version=3.4.2
Received: from primenet.com.au (ns1.primenet.com.au [203.24.36.2])
	by inbox.vuxu.org (OpenSMTPD) with ESMTP id 852993d0
	for <ml@inbox.vuxu.org>;
	Tue, 27 Nov 2018 12:51:29 +0000 (UTC)
Received: (qmail 21418 invoked by alias); 27 Nov 2018 12:51:16 -0000
Mailing-List: contact zsh-workers-help@zsh.org; run by ezmlm
Precedence: bulk
X-No-Archive: yes
List-Id: Zsh Workers List <zsh-workers.zsh.org>
List-Post: <mailto:zsh-workers@zsh.org>
List-Help: <mailto:zsh-workers-help@zsh.org>
List-Unsubscribe: <mailto:zsh-workers-unsubscribe@zsh.org>
X-Seq: 43849
Received: (qmail 2823 invoked by uid 1010); 27 Nov 2018 12:51:16 -0000
X-Qmail-Scanner-Diagnostics: from rcpt-mqugw.biglobe.ne.jp by f.primenet.com.au (envelope-from <takimoto-j@kba.biglobe.ne.jp>, uid 7791) with qmail-scanner-2.11 
 (clamdscan: 0.100.2/25112. spamassassin: 3.4.2.  
 Clear:RC:0(133.208.100.4):SA:0(-2.6/5.0):. 
 Processed in 3.879815 secs); 27 Nov 2018 12:51:16 -0000
X-Envelope-From: takimoto-j@kba.biglobe.ne.jp
X-Qmail-Scanner-Mime-Attachments: |
X-Qmail-Scanner-Zip-Files: |
X-Biglobe-Sender: <takimoto-j@kba.biglobe.ne.jp>
From: Jun T <takimoto-j@kba.biglobe.ne.jp>
Content-Type: text/plain;
	charset=us-ascii
Content-Transfer-Encoding: 7bit
Mime-Version: 1.0 (Mac OS X Mail 12.1 \(3445.101.1\))
Subject: Re: [BUG] Glob handling is brittle
Date: Tue, 27 Nov 2018 21:14:20 +0900
References: <4a07ef77-de18-8966-5f3e-bd544aaaae3f@inlv.org>
To: zsh-workers@zsh.org
In-Reply-To: <4a07ef77-de18-8966-5f3e-bd544aaaae3f@inlv.org>
Message-Id: <942D7657-1371-4A04-B2E7-1CBFE9DC0966@kba.biglobe.ne.jp>
X-Mailer: Apple Mail (2.3445.101.1)
X-Biglobe-Spnum: 60494


> 2018/11/26 14:38, Martijn Dekker <martijn@inlv.org> wrote:
> 
> The script below reliably makes zsh hang.
(snip)
> case '\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\' in
> ( *\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\\
> *\\*\\*\\*\\*\\*\\*\\*\\*\\*\\* )
> 	echo ok ;;
> esac

zsh is not hanging; it is just very slow.
On my Mac it takes about 130 sec to print 'ok', and it uses up almost
all the memory (16GB) in my Mac (so macOS starts the memory compression.
If one more \\ were added swap would start, I guess).

We can use any other character than '\' to reproduce the problem. In the
script below, str='aaa...a' is compared with pat='a*a*a*...*a*' while
increasing the number of 'a's in str:

zmodload zsh/datetime
str=''
pat='*'
repeat 30; do
    str=$str'a'
    pat=$pat'a*'
    t0=$EPOCHREALTIME
    [[ $str = ${~pat} ]] && \
        printf '%2d: %9.4f\n' ${#str} $(( $EPOCHREALTIME - $t0 ))
done


The output looks like:
 1:    0.0000
(snip)
11:    0.0001
12:    0.0001
13:    0.0002
14:    0.0005
15:    0.0010
16:    0.0019
17:    0.0039
18:    0.0078
19:    0.0155
20:    0.0306
21:    0.0621
22:    0.1219
23:    0.2459
24:    0.4879
25:    0.9834
26:    1.9586
27:    3.9203
28:    7.8332
29:   15.6636
30:   31.3442

So the cpu time is proportional to 2**${#str}.
I don't know whether this can be 'fixed' easily.