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