Zsh Mailing List Archive
Messages sorted by:
Reverse Date,
Date,
Thread,
Author
PATCH: 3.1.5: parameter substitution: another thing
- X-seq: zsh-workers 4754
- From: Peter Stephenson <pws@xxxxxxxxxxxxxxxxx>
- To: zsh-workers@xxxxxxxxxxxxxxx (Zsh hackers list)
- Subject: PATCH: 3.1.5: parameter substitution: another thing
- Date: Fri, 11 Dec 1998 15:28:48 +0100
This adds on to the previous patch which implemented ${.../../..}. It
does various things.
1. The main change is an optimization of all forms of pattern
matching inside parameter strings. The code in the matcher has
already been upgraded so it can reliably (don't say I used that word)
match the longest substring with the start position anchored. Thus
it's possible to remove a whole load of loops in getmatch() where
complete strings were searched for. For example, ${foo##bar} used to
sweep back through substrings $foo[1,$i] for $i in {$#foo..1} to get a
match; now it can do it in one call to the matcher. That's the
simplest case, but other optimizations for most of the other cases
were possible. Maybe it's now even possible to remove pfalstad's
comment `please do not laugh at this code', but that would be inviting
disaster.
2. Use of the I flag has been rationalized. It is now only useful for
substrings (I would guess nobody ever used it for anything else) and
matches the nth match along from the start (or, with %, the end), at
each position picking either the shortest (# and %) or longest (## and
%%) match, i.e. what you probably always thought it did. I have tried
to make the documentation more explicit on the flags.
3. As I said yesterday, the replacement string in ${foo/orig/repl} is
now subject to $-expansion, like the original pattern always was.
I've also mentioned both in the manual for the first time.
4. Finally, I implemented ${(S)foo/orig/repl} to replace the shortest
match of orig in foo with repl instead of the longest. This more or
less falls out immediately with the optimizations.
*** Doc/Zsh/expn.yo.pmfl2 Wed Dec 9 17:27:02 1998
--- Doc/Zsh/expn.yo Fri Dec 11 15:04:42 1998
***************
*** 312,319 ****
for a description of parameters.
In the expansions discussed below that require a pattern, the form of
the pattern is the same as that used for filename generation;
! see noderef(Filename Generation). In addition to the following
! operations, the file modifiers described in
noderef(Modifiers) in noderef(History Expansion) can be
applied: for example, tt(${i:s/foo/bar/}) performs string
substitution on the value of parameter tt($i).
--- 312,321 ----
for a description of parameters.
In the expansions discussed below that require a pattern, the form of
the pattern is the same as that used for filename generation;
! see noderef(Filename Generation). Note that this pattern, along with
! the replacement text of a substitution, is itself subject to
! parameter, command and arithmetic substitution. In addition to the
! following operations, the file modifiers described in
noderef(Modifiers) in noderef(History Expansion) can be
applied: for example, tt(${i:s/foo/bar/}) performs string
substitution on the value of parameter tt($i).
***************
*** 408,420 ****
which case it must match at the end of the string. The var(repl) may
be an empty string, in which case the final tt(/) may also be omitted.
To quote the final tt(/) in other cases it should be preceded by two
! backslashes (i.e., a quoted backslash). Substitution of an array is as
! described for tt(#) and tt(%) above.
The first tt(/) may be preceded by a tt(:), in which case the match
will only succeed if it matches the entire word. Note also the
! effect of the tt(I) parameter expansion flag below: the flags tt(S),
! tt(M), tt(R), tt(B), tt(E) and tt(N) are not useful, however.
)
item(tt(${#)var(spec)tt(}))(
If var(spec) is one of the above substitutions, substitute
--- 410,435 ----
which case it must match at the end of the string. The var(repl) may
be an empty string, in which case the final tt(/) may also be omitted.
To quote the final tt(/) in other cases it should be preceded by two
! backslashes (i.e., a quoted backslash); this is not necessary if the
! tt(/) occurs inside a substituted paramter. Substitution of an array
! is as described for tt(#) and tt(%) above.
The first tt(/) may be preceded by a tt(:), in which case the match
will only succeed if it matches the entire word. Note also the
! effect of the tt(I) and tt(S) parameter expansion flags below: the
! flags tt(M), tt(R), tt(B), tt(E) and tt(N) are not useful, however.
!
! For example,
!
! nofill(tt(foo="twinkle twinkle little star" sub="t*e" rep="spy"))
! nofill(tt(print ${foo//${~sub}/$rep}))
! nofill(tt(print ${(S)foo//${~sub}/$rep}))
!
! Here, the tt(~) ensures that the text of tt($sub) is treated as a
! pattern rather than a plain string. In the first case, the longest
! match for tt(t*e) is substituted and the result is `tt(spy star)',
! while in the second case, the shortest matches are taken and the
! result is `tt(spy spy lispy star)'.
)
item(tt(${#)var(spec)tt(}))(
If var(spec) is one of the above substitutions, substitute
***************
*** 567,580 ****
item(tt(S))(
(This and all remaining flags are used with the tt(${)...tt(#)...tt(}) or
tt(${)...tt(%)...tt(}) forms.)
! Search substrings as well as beginnings or ends.
)
item(tt(I:)var(expr)tt(:))(
Search the var(expr)th match (where var(expr) evaluates to a number).
! This may be used with tt(${)...tt(/)...tt(}) or
! tt(${)...tt(//)...tt(}) substitution: in the first case, only the
! var(expr)th match is substituted, while in the second case, all
! matches from the var(expr)th on are substituted.
)
item(tt(M))(
Include the matched portion in the result.
--- 582,602 ----
item(tt(S))(
(This and all remaining flags are used with the tt(${)...tt(#)...tt(}) or
tt(${)...tt(%)...tt(}) forms.)
! Search substrings as well as beginnings or ends; with tt(#) start
! from the beginning and with tt(%) start from the end of the string.
! With substitution via tt(${)...tt(/)...tt(}) or
! tt(${)...tt(//)...tt(}), specifies that the shortest instead of the
! longest match should be replaced.
)
item(tt(I:)var(expr)tt(:))(
Search the var(expr)th match (where var(expr) evaluates to a number).
! This only applies when searching for substrings, either with the tt(S)
! flag, or with tt(${)...tt(/)...tt(}) (only the var(expr)th match is
! substituted) or tt(${)...tt(//)...tt(}) (all matches from the
! var(expr)th on are substituted). The var(expr)th match is counted
! such that there is either one or zero matches from each starting
! position in the string, although for global subsitution matches
! overlapping previous replacements are ignored.
)
item(tt(M))(
Include the matched portion in the result.
*** Src/glob.c.pmfl2 Thu Dec 10 15:45:42 1998
--- Src/glob.c Fri Dec 11 14:52:10 1998
***************
*** 129,134 ****
--- 129,136 ----
static char *pptr; /* current place in string being matched */
static Comp tail;
static int first; /* are leading dots special? */
+ static int longest; /* always match longest piece of path. */
+ static int inclosure; /* see comment in doesmatch() */
/* Add a component to pathbuf: This keeps track of how *
* far we are into a file name, since each path component *
***************
*** 1904,1915 ****
--- 1906,1944 ----
}
/*
+ * Run the pattern so that we always get the longest possible match.
+ * This eliminates a loop where we gradually shorten the target string
+ * to find same. We also need to check pptr (the point successfully
+ * reached along the target string) explicitly.
+ *
+ * For this to work, we need the full hairy closure code, so
+ * set inclosure.
+ */
+
+ /**/
+ static int
+ dolongestmatch(char *str, Comp c, int fist)
+ {
+ int ret;
+ longest = 1;
+ inclosure++;
+ ret = domatch(str, c, fist);
+ inclosure--;
+ longest = 0;
+ return ret;
+ }
+
+ /*
* This is called from paramsubst to get the match for ${foo#bar} etc.
* fl is a set of the SUB_* flags defined in zsh.h
* *sp points to the string we have to modify. The n'th match will be
* returned in *sp. ncalloc is used to get memory for the result string.
* replstr is the replacement string from a ${.../orig/repl}, in
* which case pat is the original.
+ *
+ * n is now ignored unless we are looking for a substring, in
+ * which case the n'th match from the start is counted such that
+ * there is no more than one match from each position.
*/
/**/
***************
*** 1918,1924 ****
{
Comp c;
char *s = *sp, *t, *start, sav;
! int i, j, l = strlen(*sp), lleft, matched;
MUSTUSEHEAP("getmatch"); /* presumably covered by prefork() test */
repllist = NULL;
--- 1947,1953 ----
{
Comp c;
char *s = *sp, *t, *start, sav;
! int i, j, l = strlen(*sp), matched;
MUSTUSEHEAP("getmatch"); /* presumably covered by prefork() test */
repllist = NULL;
***************
*** 1936,1961 ****
}
switch (fl & (SUB_END|SUB_LONG|SUB_SUBSTR)) {
case 0:
! /* Smallest possible match at head of string: *
! * start adding characters until we get a match. */
! for (i = 0, t = s; i <= l; i++, t++) {
! sav = *t;
! *t = '\0';
! if (domatch(s, c, 0) && !--n) {
*t = sav;
- *sp = get_match_ret(*sp, 0, i, fl, replstr);
- return 1;
}
! if ((*t = sav) == Meta)
! i++, t++;
}
break;
case SUB_END:
/* Smallest possible match at tail of string: *
! * move back down string until we get a match. */
for (t = s + l; t >= s; t--) {
! if (domatch(t, c, 0) && !--n) {
*sp = get_match_ret(*sp, t - s, l, fl, replstr);
return 1;
}
--- 1965,2005 ----
}
switch (fl & (SUB_END|SUB_LONG|SUB_SUBSTR)) {
case 0:
! case SUB_LONG:
! /*
! * Largest/smallest possible match at head of string.
! * First get the longest match.
! */
! if (dolongestmatch(s, c, 0)) {
! char *mpos = pptr;
! while (!(fl & SUB_LONG) && pptr > s) {
! /*
! * If we want the shortest, keep backing up to the
! * previous character and find the longest up to there.
! * That way we can usually reach the shortest in only
! * a few attempts.
! */
! t = (pptr > s + 1 && pptr[-2] == Meta) ? pptr - 2 : pptr -1;
! sav = *t;
! *t = '\0';
! if (!dolongestmatch(s, c, 0)) {
! *t = sav;
! break;
! }
! mpos = pptr;
*t = sav;
}
! *sp = get_match_ret(*sp, 0, mpos-s, fl, replstr);
! return 1;
}
break;
case SUB_END:
/* Smallest possible match at tail of string: *
! * move back down string until we get a match. *
! * There's no optimization here. */
for (t = s + l; t >= s; t--) {
! if (domatch(t, c, 0)) {
*sp = get_match_ret(*sp, t - s, l, fl, replstr);
return 1;
}
***************
*** 1964,1991 ****
}
break;
- case SUB_LONG:
- /* Largest possible match at head of string: *
- * delete characters from end until we get a match. */
- for (t = s + l; t > s; t--) {
- sav = *t;
- *t = '\0';
- if (domatch(s, c, 0) && !--n) {
- *t = sav;
- *sp = get_match_ret(*sp, 0, t - s, fl, replstr);
- return 1;
- }
- *t = sav;
- if (t >= s+2 && t[-2] == Meta)
- t--;
- }
- break;
-
case (SUB_END|SUB_LONG):
/* Largest possible match at tail of string: *
! * move forward along string until we get a match. */
for (i = 0, t = s; i < l; i++, t++) {
! if (domatch(t, c, 0) && !--n) {
*sp = get_match_ret(*sp, i, l, fl, replstr);
return 1;
}
--- 2008,2019 ----
}
break;
case (SUB_END|SUB_LONG):
/* Largest possible match at tail of string: *
! * move forward along string until we get a match. *
! * Again there's no optimisation. */
for (i = 0, t = s; i < l; i++, t++) {
! if (domatch(t, c, 0)) {
*sp = get_match_ret(*sp, i, l, fl, replstr);
return 1;
}
***************
*** 1996,2084 ****
case SUB_SUBSTR:
/* Smallest at start, but matching substrings. */
! if (domatch(s + l, c, 0) && !--n) {
*sp = get_match_ret(*sp, 0, 0, fl, replstr);
return 1;
! }
! for (i = 1; i <= l; i++) {
! for (t = s, j = i; j <= l; j++, t++) {
! sav = s[j];
! s[j] = '\0';
! if (domatch(t, c, 0) && !--n) {
! s[j] = sav;
! *sp = get_match_ret(*sp, t - s, j, fl, replstr);
! return 1;
! }
! if ((s[j] = sav) == Meta)
! j++;
! if (*t == Meta)
! t++;
! }
! if (s[i] == Meta)
! i++;
! }
! break;
!
! case (SUB_END|SUB_SUBSTR):
! /* Smallest at end, matching substrings */
! if (domatch(s + l, c, 0) && !--n) {
! *sp = get_match_ret(*sp, l, l, fl, replstr);
! return 1;
! }
! for (i = l; i--;) {
! if (i && s[i-1] == Meta)
! i--;
! for (t = s + l, j = i; j >= 0; j--, t--) {
! sav = *t;
! *t = '\0';
! if (domatch(s + j, c, 0) && !--n) {
! *t = sav;
! *sp = get_match_ret(*sp, j, t - s, fl, replstr);
! return 1;
! }
! *t = sav;
! if (t >= s+2 && t[-2] == Meta)
! t--;
! if (j >= 2 && s[j-2] == Meta)
! j--;
! }
! }
! break;
!
! case (SUB_LONG|SUB_SUBSTR):
! /* Largest at start, matching substrings. */
start = s;
- lleft = l;
if (fl & SUB_GLOBAL)
repllist = newlinklist();
do {
/* loop over all matches for global substitution */
matched = 0;
! for (i = lleft; i; i--) {
! for (t = start, j = i; j <= lleft; j++, t++) {
! sav = start[j];
! start[j] = '\0';
! if (domatch(t, c, 0) &&
! (!--n || ((fl & SUB_GLOBAL) && n <= 0))) {
! start[j] = sav;
! *sp = get_match_ret(*sp, t - s, j + (start-s), fl,
! replstr);
! if (!(fl & SUB_GLOBAL))
return 1;
- matched = j;
- start += j;
- lleft -= j;
- break;
}
! if ((start[j] = sav) == Meta)
! j++;
! if (*t == Meta)
! t++;
! }
! if (matched)
break;
! if (i >= 2 && s[i-2] == Meta)
! i--;
}
} while (matched);
/*
--- 2024,2082 ----
case SUB_SUBSTR:
/* Smallest at start, but matching substrings. */
! if (!(fl & SUB_GLOBAL) && domatch(s + l, c, 0) && !--n) {
*sp = get_match_ret(*sp, 0, 0, fl, replstr);
return 1;
! } /* fall through */
! case (SUB_SUBSTR|SUB_LONG):
! /* longest or smallest at start with substrings */
start = s;
if (fl & SUB_GLOBAL)
repllist = newlinklist();
do {
/* loop over all matches for global substitution */
matched = 0;
! for (t = start; t < s + l; t++) {
! /* Find the longest match from this position. */
! if (dolongestmatch(t, c, 0) && pptr > t) {
! char *mpos = pptr;
! while (!(fl & SUB_LONG) && pptr > t) {
! /* Now reduce to find the smallest match */
! char *p = (pptr > t + 1 && pptr[-2] == Meta) ?
! pptr - 2 : pptr - 1;
! sav = *p;
! *p = '\0';
! if (!dolongestmatch(t, c, 0)) {
! *p = sav;
! break;
! }
! mpos = pptr;
! *p = sav;
! }
! if (!--n || (n <= 0 && (fl & SUB_GLOBAL)))
! *sp = get_match_ret(*sp, t-s, mpos-s, fl, replstr);
! if (!(fl & SUB_GLOBAL)) {
! if (n) {
! /*
! * Looking for a later match: in this case,
! * we can continue looking for matches from
! * the next character, even if it overlaps
! * with what we just found.
! */
! continue;
! } else
return 1;
}
! /*
! * For a global match, we need to skip the stuff
! * which is already marked for replacement.
! */
! matched = 1;
! start = mpos;
break;
! }
! if (*t == Meta)
! t++;
}
} while (matched);
/*
***************
*** 2086,2118 ****
* at the start. Goodness knows if this is a good idea
* with global substitution, so it doesn't happen.
*/
! if (!(fl & SUB_GLOBAL) && domatch(s + l, c, 0) && !--n) {
*sp = get_match_ret(*sp, 0, 0, fl, replstr);
return 1;
}
break;
case (SUB_END|SUB_LONG|SUB_SUBSTR):
! /* Largest at end, matching substrings. */
! for (i = 0; i < l; i++) {
! for (t = s + l, j = i; j >= 0; j--, t--) {
! sav = *t;
! *t = '\0';
! if (domatch(s + j, c, 0) && !--n) {
! *t = sav;
! *sp = get_match_ret(*sp, j, t - s, fl, replstr);
! return 1;
}
! *t = sav;
! if (t >= s+2 && t[-2] == Meta)
! t--;
! if (j >= 2 && s[j-2] == Meta)
! j--;
}
- if (s[i] == Meta)
- i++;
}
! if (domatch(s + l, c, 0) && !--n) {
*sp = get_match_ret(*sp, l, l, fl, replstr);
return 1;
}
--- 2084,2128 ----
* at the start. Goodness knows if this is a good idea
* with global substitution, so it doesn't happen.
*/
! if ((fl & (SUB_LONG|SUB_GLOBAL)) == SUB_LONG &&
! domatch(s + l, c, 0) && !--n) {
*sp = get_match_ret(*sp, 0, 0, fl, replstr);
return 1;
}
break;
+ case (SUB_END|SUB_SUBSTR):
+ /* Shortest at end with substrings */
+ if (domatch(s + l, c, 0) && !--n) {
+ *sp = get_match_ret(*sp, l, l, fl, replstr);
+ return 1;
+ } /* fall through */
case (SUB_END|SUB_LONG|SUB_SUBSTR):
! /* Longest/shortest at end, matching substrings. */
! for (t = s + l - 1; t >= s; t--) {
! if (t > s && t[-1] == Meta)
! t--;
! if (dolongestmatch(t, c, 0) && pptr > t && !--n) {
! /* Found the longest match */
! char *mpos = pptr;
! while (!(fl & SUB_LONG) && pptr > t) {
! /* Look for the shortest match */
! char *p = (pptr > t+1 && pptr[-2] == Meta) ?
! pptr-2 : pptr-1;
! sav = *p;
! *p = '\0';
! if (!dolongestmatch(t, c, 0) || pptr == t) {
! *p = sav;
! break;
! }
! *p = sav;
! mpos = pptr;
}
! *sp = get_match_ret(*sp, t-s, mpos-s, fl, replstr);
! return 1;
}
}
! if ((fl & SUB_LONG) && domatch(s + l, c, 0) && !--n) {
*sp = get_match_ret(*sp, l, l, fl, replstr);
return 1;
}
***************
*** 2124,2131 ****
LinkNode nd;
Repldata rd;
int rlen;
- lleft = 0; /* size of returned string */
i = 0; /* start of last chunk we got from *sp */
rlen = strlen(replstr);
for (nd = firstnode(repllist); nd; incnode(nd)) {
--- 2134,2141 ----
LinkNode nd;
Repldata rd;
int rlen;
+ int lleft = 0; /* size of returned string */
i = 0; /* start of last chunk we got from *sp */
rlen = strlen(replstr);
for (nd = firstnode(repllist); nd; incnode(nd)) {
***************
*** 2184,2192 ****
excluded(Comp c, char *eptr)
{
char *saves = pptr;
! int savei = first, ret;
first = 0;
if (PATHADDP(c) && pathpos) {
VARARR(char, buf, pathpos + strlen(eptr) + 1);
--- 2194,2208 ----
excluded(Comp c, char *eptr)
{
char *saves = pptr;
! int savei = first, savel = longest, ret;
first = 0;
+ /*
+ * Even if we've been told always to match the longest string,
+ * i.e. not anchored to the end, we want to match the full string
+ * we've already matched when we're trying to exclude it.
+ */
+ longest = 0;
if (PATHADDP(c) && pathpos) {
VARARR(char, buf, pathpos + strlen(eptr) + 1);
***************
*** 2203,2208 ****
--- 2219,2225 ----
pptr = saves;
first = savei;
+ longest = savel;
return ret;
}
***************
*** 2213,2220 ****
};
typedef struct gclose *Gclose;
- static int inclosure; /* see comment in doesmatch() */
-
/* Add a list of matches that fit the closure. trystring is a string of
* the same length as the target string; a non-zero in that string
* indicates that we have already tried to match the patterns following
--- 2230,2235 ----
***************
*** 2317,2323 ****
for (done = 0; ; done++) {
saves = pptr;
if ((done || ONEHASHP(c) || OPTIONALP(c)) &&
! ((!c->next && (!LASTP(c) || !*pptr)) ||
(c->next && doesmatch(c->next))))
return 1;
if (done && OPTIONALP(c))
--- 2332,2338 ----
for (done = 0; ; done++) {
saves = pptr;
if ((done || ONEHASHP(c) || OPTIONALP(c)) &&
! ((!c->next && (!LASTP(c) || !*pptr || longest)) ||
(c->next && doesmatch(c->next))))
return 1;
if (done && OPTIONALP(c))
***************
*** 2351,2357 ****
break;
saves = pptr;
/* do we really want this LASTP here?? */
! if ((!c->next && (!LASTP(c) || !*pptr)) ||
(c->next && doesmatch(c->next))) {
retflag = 1;
break;
--- 2366,2372 ----
break;
saves = pptr;
/* do we really want this LASTP here?? */
! if ((!c->next && (!LASTP(c) || !*pptr || longest)) ||
(c->next && doesmatch(c->next))) {
retflag = 1;
break;
***************
*** 2537,2543 ****
if (!ret)
break;
if ((ret = ret2 &&
! ((!c->next && (!LASTP(c) || !*pptr))
|| (c->next && doesmatch(c->next)))) ||
(!c->next && LASTP(c)))
break;
--- 2552,2558 ----
if (!ret)
break;
if ((ret = ret2 &&
! ((!c->next && (!LASTP(c) || !*pptr || longest))
|| (c->next && doesmatch(c->next)))) ||
(!c->next && LASTP(c)))
break;
***************
*** 2569,2575 ****
if (CLOSUREP(c))
return 1;
if (!c->next) /* no more patterns left */
! return (!LASTP(c) || !*pptr);
/* optimisation when next pattern is not a closure */
if (!CLOSUREP(c->next)) {
c = c->next;
--- 2584,2590 ----
if (CLOSUREP(c))
return 1;
if (!c->next) /* no more patterns left */
! return (!LASTP(c) || !*pptr || longest);
/* optimisation when next pattern is not a closure */
if (!CLOSUREP(c->next)) {
c = c->next;
*** Src/subst.c.pmfl2 Thu Dec 10 15:45:22 1998
--- Src/subst.c Thu Dec 10 15:51:28 1998
***************
*** 1145,1152 ****
s++;
if (s[-1] == '/') {
char *ptr;
! /* previous flags are irrelevant: we always want longest match */
! flags = SUB_LONG;
if (*s == '/') {
/* doubled, so replace all occurrences */
flags |= SUB_GLOBAL;
--- 1145,1155 ----
s++;
if (s[-1] == '/') {
char *ptr;
! /*
! * previous flags are irrelevant, except for (S) which
! * indicates shortest substring; else look for longest.
! */
! flags = (flags & SUB_SUBSTR) ? 0 : SUB_LONG;
if (*s == '/') {
/* doubled, so replace all occurrences */
flags |= SUB_GLOBAL;
***************
*** 1177,1182 ****
--- 1180,1186 ----
if (*ptr == '\\' && ptr[1] == '/')
chuck(ptr);
replstr = (*ptr && ptr[1]) ? ptr+1 : "";
+ singsub(&replstr);
untokenize(replstr);
*ptr = '\0';
}
--
Peter Stephenson <pws@xxxxxxxxxxxxxxxxx> Tel: +39 050 844536
WWW: http://www.ifh.de/~pws/
Dipartimento di Fisica, Via Buonarroti 2, 56127 Pisa, Italy
Messages sorted by:
Reverse Date,
Date,
Thread,
Author