Re: [BUG] Glob handling is brittle

[Jun T <takimoto-j@xxxxxxxxxxxxxxxxx>]

> 2018/11/26 14:38, Martijn Dekker <martijn@xxxxxxxx> 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.