[BUG] Glob handling is brittle

[BUG] Glob handling is brittle

[Martijn Dekker]

The script below reliably makes zsh hang.

(ksh93 hangs, too. mksh, bash, yash, and ash variants execute it in no 
time at all.)

- M.

case '\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\' in
( *\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\\
*\\*\\*\\*\\*\\*\\*\\*\\*\\*\\* )
	echo ok ;;
esac

Re: [BUG] Glob handling is brittle

[Jun T]

> 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.

Re: [BUG] Glob handling is brittle

[Peter Stephenson]

On Tue, 2018-11-27 at 21:14 +0900, Jun T wrote:
> > 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.

Yes, you can see that by gradually increasing the length of the
pattern.  Depending on the machine, it starts to get really slow after
about half a dozen or so \\* groups.

> I don't know whether this can be 'fixed' easily.

There's something a bit similar that does improve the case of excluded
matches, ~ and ^ --- where you hit pathological cases quite quickly, and
which aren't so commonly used in patterns.  That's not nice.  It's
almost certainly not a good idea to do it that way here, as * is very
widely used indeed.  I can't offhand think of a good way of fixing up
pathological cases without having a much more noticeable effect on more
typical cases.  But I don't think offhand thinking is what's required
here.

Really, this is at the point where you need an algorithm expert rather
than a bunch of hackers.

pws