Un-patch: new pattern matching code

Un-patch: new pattern matching code

[Peter Stephenson]

I'm just about to make 3.1.6-pws-1 available, and it will contain the new
pattern matching code (or a new pattern matching code, if it turns out to
be duff we can go back).  Since it's quite long I haven't posted it
separately, but here is a description.

The user-visible changes are supposed to be entirely minimal: the
precedence of operators should be more rational, backtracking will work in
numeric ranges, and that's pretty much it.  I intend to document a few more
of these in the manual; I don't think anything there at the moment has
become wrong.  One think works, which used to in the old days but I
inadvertently messed it up because I didn't know about it:  patterns like
foo~bar~rod are valid, and are equivalent to, but less cumbersome than,
foo~(bar|rod).

It's based on a real regular expression matcher, so it should be
significantly faster, although I haven't done any real testing of speed and
I would be glad to hear about any comparisons (or maybe I wouldn't).  In
particular, it should do much less memory management --- in some cases,
such as simple patterns in ${...#...} or [[ ... = ... ]], possibly even
none, as there is now a static buffer.  It is also possible to copy
compiled patterns; just use memcpy and the size member of the struct.
Note that the default is to duplicate the static buffer into a
heap-allocated chunk of the appropriate size; this is needed for file
paths.

It now lives in its own file, pattern.c.  Originally everything here was
going to use unsigned char * to avoid bad comparisons with integers, but
then I found that all the tokens are defined in zsh.h as ((char) 0x83) and
so on, so that went out of the window and I resorted to char * after
updating the whole of the shell to pass unsigned char * down.  As you can
imagine, that was great fun.  Anyway, it now uses the usual STOUC(...)
hack, so problems are quite possible if I've missed any.  However, it's now
been compiled and tested on one machine with unsigned and one with signed
characters, so the basics are probably right.

There are two cpp definitions available: one is ZSH_PAT_DEBUG, which
enables the `patdebug' builtin, which prints out a compiled pattern with
option -p and with more than one argument tests the pattern against the
strings; this was inherited from Henry Spencer's code, but I thought I
might as well leave it.  There's no configure code to enable
ZSH_PAT_DEBUG, just add it by hand.

The other cpp definition is BACKREFERENCES, which enables backreferencing
of parentheses in patterns like sed and perl do.  I haven't enabled it
because I don't know what, if anything, I'm going to do with it.  Matching
is a little more efficient without because the extra recursive call on open
and close parentheses isn't there.  (There's code not to use backreferences
even if they are compiled in, so that doesn't need to be a performance
issue for ordinary globbing.)

Anyone who knows any computer science will probably notice that, while it's
pretty much a finite state machine, some states are more finite than
others.  In particularly, backtracking on excluded matches, where in
(foo~bar)rod the `bar' only has to match the `foo' and the `rod' is
irrelevant, need some extra state recording, and I have retained the old
trick that eliminates infinite loops and prevents exponential behaviour
when failing to match against things like `(f#o#)#' (the version of perl
here goes into an infinite loop when given `(f*o*)*', so it isn't trivial).
This has meant leaving holes for pointers in the compiled expression, which
ought to work (I've tried to make sure everything is aligned to pointer
size anyway) but is probably the most dubious part of the proceedings.

Finally, the usual warning: in case you hadn't guessed, bugs here can cause
problems with pretty much any part of the shell.  Some of the tests to make
sure things like globbing flags are saved and restored are a bit complex.
Alignment problems should have been handled, but there could be some
remaining, particularly on 64-bit architectures which I haven't tried.  So
if you're planning on doing any real work while I'm away, you might want to
stick with 3.1.6.

-- 
Peter Stephenson <pws@ibmth.df.unipi.it>       Tel: +39 050 844536
WWW:  http://www.ifh.de/~pws/
Dipartimento di Fisica, Via Buonarroti 2, 56127 Pisa, Italy

RE: Un-patch: new pattern matching code

[Andrej Borsenkow]

>
> The other cpp definition is BACKREFERENCES, which enables backreferencing
> of parentheses in patterns like sed and perl do.  I haven't enabled it
> because I don't know what, if anything, I'm going to do with it.

This may prove useful for ${.../...} case at least. More general use depends on
scope of these references. If e.g. the result of last pattern mathing is
available (much like in Perl) as, say, ``pattern'' array, than it may be even
more useful in case like

if [[ ... == ... ]]
    foo="$pattern[1]-$pattern[3]"

that would completely eliminate need of expr. (I am not sure, that there is easy
way in Zsh to extract matched subpattern currently)

/andrej

Re: Un-patch: new pattern matching code

[Bart Schaefer]

On Aug 7,  1:02pm, Andrej Borsenkow wrote:
} Subject: RE: Un-patch: new pattern matching code
}
} >
} > The other cpp definition is BACKREFERENCES
} 
} If e.g. the result of last pattern mathing is
} available (much like in Perl) as, say, ``pattern'' array

I'd name it something other than `pattern' ... what's in the array is not
the patterns, it's the matched substring of the source string, right?

} I am not sure, that there is easy
} way in Zsh to extract matched subpattern currently)

There is ${(MSI:n:)...#...}, where n is a number.  BTW, it looks like (M)
doesn't work right with ${.../...}.  Am I missing something?

zagzig% x="abcdefghij"
zagzig% echo ${x/??}
cdefghij
zagzig% echo ${(M)x/??}
cdefghij
zagzig% echo ${(MS)x/??}
cdefghij
zagzig% echo ${(MSI:1:)x/??} 
cdefghij
zagzig% echo ${(MSI:2:)x/??} 
adefghij
zagzig% echo ${(RSI:2:)x/??} 
adefghij
echo ${(MSI:2:)x//??} 
ab
zagzig% echo ${(M)x#??}
ab
zagzig% echo ${(MSI:2:)x#??} 
bc


-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

Extended glob patterns in ${...#..} RE: Un-patch: new pattern matching code

[Andrej Borsenkow]

>
> } I am not sure, that there is easy
> } way in Zsh to extract matched subpattern currently)
>
> There is ${(MSI:n:)...#...}, where n is a number.

It looks, like this does not work with extended glob patterns (3.1.6 pure or
pws-1):

bor@itsrm2:~%> foo=ab12xy
bor@itsrm2:~%> print ${(SM)foo#[[:digit:]]}
1
bor@itsrm2:~%> print ${(SM)foo#([[:digit:]])#}

And some more considerations:

 there is subtle problem: searching for "...sub1 ...sub2..." may give different
results as searching for sub1 first and   then for sub2

 the exact order number of desired match is not always available.

So, the above example is not exact replacement for submatches reference.
Granted, Zsh lived without it for a long time - but, if we have this now, why
not use it?

/andrej

Re: Extended glob patterns in ${...#..} RE: Un-patch: new pattern matching code

[Bart Schaefer]

On Aug 8,  2:04pm, Andrej Borsenkow wrote:
} Subject: Extended glob patterns in ${...#..} RE: Un-patch: new pattern mat
}
} > There is ${(MSI:n:)...#...}, where n is a number.
} 
} It looks, like this does not work with extended glob patterns (3.1.6 pure or
} pws-1):
} 
} bor@itsrm2:~%> print ${(SM)foo#([[:digit:]])#}

This is at least partly consistent:

zagzig<7> foo=ab12xy
zagzig<8> print ${(SM)foo#*} 

zagzig<9>

Since a closure can match the empty string, the shortest matched portion
is nothing.  However, asking for the longest match definitely doesn't work:

zagzig<9> print ${(SM)foo##*}
ab12xy
zagzig<10> print ${(SM)foo##([[:digit:]])#} 

zagzig<11> 

} there is subtle problem: searching for "...sub1 ...sub2..." may give
} different results as searching for sub1 first and then for sub2

True.

-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

RE: Extended glob patterns in ${...#..} RE: Un-patch: new pattern matching code

[Andrej Borsenkow]

> Since a closure can match the empty string, the shortest matched portion
> is nothing.  However, asking for the longest match definitely doesn't work:
>
> zagzig<9> print ${(SM)foo##*}
> ab12xy
> zagzig<10> print ${(SM)foo##([[:digit:]])#}
>
> zagzig<11>
>


Believe it or not, it does work today. I have no idea, what went wrong yesterday
(I thought, it was the problem of flag order ...):

bor@itsrm2:~%> foo=ab12xy
bor@itsrm2:~%> print ${(SM)foo##[[:digit:]]#}
12
bor@itsrm2:~%> print ${(MS)foo##[[:digit:]]#}
12

But still, this one is probably unexpected:

bor@itsrm2:~%> print ${(MSI:1:)foo##[[:digit:]]#}
12
bor@itsrm2:~%> print ${(MSI:2:)foo##[[:digit:]]#}
2
bor@itsrm2:~%> print ${(MSI:3:)foo##[[:digit:]]#}

The first is O.K. ... and the third is O.K., but the second? I believe, this is
a clear bug. The ``S'' flag must consider only non-overlapped matches (the same
way, sed works).

/andrej

Bug? RE: Un-patch: new pattern matching code

[Andrej Borsenkow]

> Anyone who knows any computer science will probably notice that, while it's
> pretty much a finite state machine, some states are more finite than
> others.  In particularly, backtracking on excluded matches, where in
> (foo~bar)rod the `bar' only has to match the `foo' and the `rod' is
> irrelevant, need some extra state recording, and I have retained the old
> trick that eliminates infinite loops and prevents exponential behaviour
> when failing to match against things like `(f#o#)#' (the version of perl
> here goes into an infinite loop when given `(f*o*)*', so it isn't trivial).
> This has meant leaving holes for pointers in the compiled expression, which
> ought to work (I've tried to make sure everything is aligned to pointer
> size anyway) but is probably the most dubious part of the proceedings.
> 

bor@itsrm2:~%> foo=ab12xy
bor@itsrm2:~%> print ${foo/[[:digit:]]#}
abxy
bor@itsrm2:~%> print ${(S)foo/[[:digit:]]#}
ab12xy
bor@itsrm2:~%> print ${foo//[[:digit:]]#}  
abxy
bor@itsrm2:~%> print ${(S)foo//[[:digit:]]#}
here zsh hangs completely.

RE: Un-patch: new pattern matching code

[Andrej Borsenkow]

>
> There is ${(MSI:n:)...#...}, where n is a number.  BTW, it looks like (M)
> doesn't work right with ${.../...}.  Am I missing something?
>

At least, this is explicitly stated in the manual :-) What would you like to do
with (M) in this case?

/andrej

Re: Extended glob patterns in ${...#..} RE: Un-patch: new pattern matching code

[Bart Schaefer]

On Aug 9, 10:25am, Andrej Borsenkow wrote:
} Subject: RE: Extended glob patterns in ${...#..} RE: Un-patch: new pattern
}
} > Since a closure can match the empty string, the shortest matched portion
} > is nothing.  However, asking for the longest match definitely doesn't work:
} >
} > zagzig<9> print ${(SM)foo##*}
} > ab12xy
} > zagzig<10> print ${(SM)foo##([[:digit:]])#}
} >
} > zagzig<11>
} 
} Believe it or not, it does work today. I have no idea, what went wrong
} yesterday (I thought, it was the problem of flag order ...):

I think it's the difference between .6 and .6-pws-1 (I find myself wishing
Peter had chosen a different suffix this time; it's going to be confusing
especially during archive searches to decide which base version is meant
when someone refers to psw-N).

} But still, this one is probably unexpected:
} 
} bor@itsrm2:~%> print ${(MSI:2:)foo##[[:digit:]]#}
} 2
} 
} The first is O.K. ... and the third is O.K., but the second? I believe,
} this is a clear bug. The ``S'' flag must consider only non-overlapped
} matches (the same way, sed works).

The (S) flag has recognized overlapping matches for as long as it exsisted.
Remember, it means on "match within a substring" (it effectively turns
off the implicit start-anchor of # or end-anchor of %).

I think what you mean is that the (I::) flag should skip the overlapping
matches.  I suppose it could be proclaimed a bug fix, but consider the
example below -- don't you WANT overlapping matches in that instance?

I don't know how heavily the (I::) flag is employed by 3.0.x users, but
some differences have already been introduced; with x="a1_b_a2_c_a3_d" the
two look like:
====================================+========================================
zsh-3.0.6: print ${(MS)x##a*}       | zsh-3.1.6-pws-1: print ${(MS)x##a*}
a1_b_a2_c_a3_d                      | a1_b_a2_c_a3_d
zsh-3.0.6: print ${(MSI:2:)x##a*}   | zsh-3.1.6-pws-1: print ${(MSI:2:)x##a*}
a1_b_a2_c_a3_                       | a2_c_a3_d
zsh-3.0.6: print ${(MSI:3:)x##a*}   | zsh-3.1.6-pws-1: print ${(MSI:3:)x##a*}
a1_b_a2_c_a3                        | a3_d
zsh-3.0.6: print ${(MSI:4:)x##a*}   | zsh-3.1.6-pws-1: print ${(MSI:4:)x##a*}
a1_b_a2_c_a                         | 
zsh-3.0.6: print ${(SMI:5:)x##a*}   | zsh-3.1.6-pws-1: print ${(SMI:5:)x##a*}
a1_b_a2_c                           | 
====================================+========================================

Note that 3.0.6 is using overlapping matches and counting from the longest
to the shortest starting at the right, whereas 3.1.6-pws-1 is counting from
the left (which I admit is more intuitive, but it is skipping a lot of
possible matches that way without skipping all of them).  3.0.6 rambles on:

1 = a1_b_a2_c_a3_d
2 = a1_b_a2_c_a3_
3 = a1_b_a2_c_a3
4 = a1_b_a2_c_a
5 = a1_b_a2_c_
6 = a1_b_a2_c
7 = a2_c_a3_d
8 = a1_b_a2_
9 = a2_c_a3_
10 = a1_b_a2
11 = a2_c_a3
12 = a1_b_a
13 = a2_c_a
14 = a1_b_
15 = a2_c_
16 = a1_b
17 = a2_c
18 = a3_d
19 = a1_
20 = a2_
21 = a3_
22 = a1
23 = a2
24 = a3
25 = a
26 = a
27 = a

This is a pretty significant difference in behavior.

-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

Re: Un-patch: new pattern matching code

[Bart Schaefer]

On Aug 9, 12:21pm, Andrej Borsenkow wrote:
} Subject: RE: Un-patch: new pattern matching code
}
} >
} > There is ${(MSI:n:)...#...}, where n is a number.  BTW, it looks like (M)
} > doesn't work right with ${.../...}.  Am I missing something?
} 
} At least, this is explicitly stated in the manual :-)

D'oh!  I even edited that text when it appeared.  But clearly it ought to be
repeated in the "Parameter Flags" subsection.

Index: Doc/Zsh/expn.yo
===================================================================
@@ -697,8 +697,9 @@
 )
 enditem()
 
-The following flags are meaningful with the tt(${)...tt(#)...tt(}),
-tt(${)...tt(%)...tt(}), or tt(${)...tt(/)...tt(}) forms.
+The following flags are meaningful with the tt(${)...tt(#)...tt(}) or
+tt(${)...tt(%)...tt(}) forms.  The tt(S) and tt(I) flags may also be
+used with the tt(${)...tt(/)...tt(}) forms.
 
 startitem()
 item(tt(S))(

} What would you like to do with (M) in this case?

I was expecting it to reverse the sense of the pattern match, and thus
substitute the NON-matching substrings by the replacement string.  However,
it's probably more sensible the way it is.

-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

Re: Bug? RE: Un-patch: new pattern matching code

[Bart Schaefer]

On Aug 9, 10:42am, Sven Wischnowsky wrote:
} Subject: Re: Bug? RE: Un-patch: new pattern matching code
}
} P.S.: At least simple things like ${a#*/}, ${a%/*}, ${a##*/}, and
}       ${a%%/*} seem to be circa three times slower than before for me.

(I saw the followup about -O2 eliminating this.)  It does appear that a
shell compiled for debugging starts up noticably slower with the new
code (and using my init files).  I use a LOT of "case ... exac" tests in
my init files with fairly simple patterns in the labels (often with no
wildcards, occasionally with only (|) alternation).

-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

Re: Bug? RE: Un-patch: new pattern matching code

[Sven Wischnowsky]

I wrote:

> P.S.: At least simple things like ${a#*/}, ${a%/*}, ${a##*/}, and
>       ${a%%/*} seem to be circa three times slower than before for me.

Sorry for the false alarm. With -O2 they have approximately the same
speed.

Bye
 Sven


--
Sven Wischnowsky                         wischnow@informatik.hu-berlin.de

Re: Bug? RE: Un-patch: new pattern matching code

[Sven Wischnowsky]

Andrej Borsenkow wrote:

> > Anyone who knows any computer science will probably notice that, while it's
> > pretty much a finite state machine, some states are more finite than
> > others.  In particularly, backtracking on excluded matches, where in
> > (foo~bar)rod the `bar' only has to match the `foo' and the `rod' is
> > irrelevant, need some extra state recording, and I have retained the old
> > trick that eliminates infinite loops and prevents exponential behaviour
> > when failing to match against things like `(f#o#)#' (the version of perl
> > here goes into an infinite loop when given `(f*o*)*', so it isn't trivial).
> > This has meant leaving holes for pointers in the compiled expression, which
> > ought to work (I've tried to make sure everything is aligned to pointer
> > size anyway) but is probably the most dubious part of the proceedings.
> > 
> 
> bor@itsrm2:~%> foo=ab12xy
> bor@itsrm2:~%> print ${foo/[[:digit:]]#}
> abxy
> bor@itsrm2:~%> print ${(S)foo/[[:digit:]]#}
> ab12xy
> bor@itsrm2:~%> print ${foo//[[:digit:]]#}  
> abxy
> bor@itsrm2:~%> print ${(S)foo//[[:digit:]]#}
> here zsh hangs completely.

It was repeatedly matching the empty string, of course. This makes
that be handled as a special case, stepping one character forward even 
if zero characters were matched.
Maybe Peter will have to decide if this is the right thing to do here.

Bye
 Sven

P.S.: At least simple things like ${a#*/}, ${a%/*}, ${a##*/}, and
      ${a%%/*} seem to be circa three times slower than before for me.

--- os/glob.c	Mon Aug  9 10:40:41 1999
+++ Src/glob.c	Mon Aug  9 10:33:49 1999
@@ -1971,8 +1971,11 @@
 				*ptr = sav;
 			    }
 			}
-			if (!--n || (n <= 0 && (fl & SUB_GLOBAL)))
+			if (!--n || (n <= 0 && (fl & SUB_GLOBAL))) {
 			    *sp = get_match_ret(*sp, t-s, mpos-s, fl, replstr);
+			    if (mpos == start)
+				mpos++;
+			}
 			if (!(fl & SUB_GLOBAL)) {
 			    if (n) {
 				/*

--
Sven Wischnowsky                         wischnow@informatik.hu-berlin.de