20500: Unmetafy patterns where possible and other minor pattern fixes

1 files changed, 484 insertions, 189 deletions

diff --git a/Src/pattern.c b/Src/pattern.c
index 13e6ca250..04452187d 100644
--- a/Src/pattern.c
+++ b/Src/pattern.c
@@ -47,6 +47,26 @@
  *
  * Eagle-eyed readers will notice this is an altered version.  Incredibly
  * sharp-eyed readers might even find bits that weren't altered.
+ *
+ *
+ *      And I experienced a sense that, like certain regular
+ *      expressions, seemed to match the day from beginning to end, so
+ *      that I did not need to identify the parenthesised subexpression
+ *      that told of dawn, nor the group of characters that indicated
+ *      the moment when my grandfather returned home with news of
+ *      Swann's departure for Paris; and the whole length of the month
+ *      of May, as if matched by a closure, fitted into the buffer of my
+ *      life with no sign of overflowing, turning the days, like a
+ *      procession of insects that could consist of this or that
+ *      species, into a random and unstructured repetition of different
+ *      sequences, anchored from the first day of the month to the last
+ *      in the same fashion as the weeks when I knew I would not see
+ *      Gilberte and would search in vain for any occurrences of the
+ *      string in the avenue of hawthorns by Tansonville, without my
+ *      having to delimit explicitly the start or finish of the pattern.
+ *
+ *                                 M. Proust, "In Search of Lost Files",
+ *                                 bk I, "The Walk by Bourne's Place".
  */
 
 #include "zsh.mdh"
@@ -78,7 +98,7 @@ typedef union upat *Upat;
 #define P_EXCSYNC 0x01	/* no   Test if following exclude already failed */
 #define P_EXCEND  0x02	/* no   Test if exclude matched orig branch */
 #define	P_BACK	  0x03	/* no	Match "", "next" ptr points backward. */
-#define	P_EXACTLY 0x04	/* str	Match this string. */
+#define	P_EXACTLY 0x04	/* lstr	Match this string. */
 #define	P_NOTHING 0x05	/* no	Match empty string. */
 #define	P_ONEHASH 0x06	/* node	Match this (simple) thing 0 or more times. */
 #define	P_TWOHASH 0x07	/* node	Match this (simple) thing 1 or more times. */
@@ -103,10 +123,14 @@ typedef union upat *Upat;
 /* spaces left for P_OPEN+n,... for backreferences */
 #define	P_OPEN	  0x80	/* no	Mark this point in input as start of n. */
 #define	P_CLOSE	  0x90	/* no	Analogous to OPEN. */
-/* zl    is the range type zrange_t:  may be zlong or unsigned long
- * char is a single char
- * uc*   is a pointer to unsigned char, used at run time and initialised
+/*
+ * no    no argument
+ * zr    the range type zrange_t:  may be zlong or unsigned long
+ * char  a single char
+ * uc*   a pointer to unsigned char, used at run time and initialised
  *       to NULL.
+ * str   null-terminated, metafied string
+ * lstr  length as long then string, not null-terminated, unmetafied.
  */
 
 /*
@@ -179,16 +203,24 @@ typedef union upat *Upat;
 #define P_ISEXCLUDE(p)	(((p)->l & 0x30) == 0x30)
 #define P_NOTDOT(p)	((p)->l & 0x40)
 
+/* Specific to lstr type, i.e. P_EXACTLY. */
+#define P_LS_LEN(p)	((p)[1].l) /* can be used as lvalue */
+#define P_LS_STR(p)	((char *)((p) + 2))
+
 /* Flags needed when pattern is executed */
 #define P_SIMPLE        0x01	/* Simple enough to be #/## operand. */
 #define P_HSTART        0x02	/* Starts with # or ##'d pattern. */
 #define P_PURESTR	0x04	/* Can be matched with a strcmp */
 
-/* Next character after one which may be a Meta (x is any char *) */
-#define METANEXT(x)	(*(x) == Meta ? (x)+2 : (x)+1)
 /*
  * Increment pointer which may be on a Meta (x is a pointer variable),
  * returning the incremented value (i.e. like pre-increment).
+ *
+ * In future the following will need to refer to metafied multibyte
+ * characters.  References to invidual characters are not turned
+ * into a macro when the characters is metafied (c.f. CHARREF()
+ * below then the character is not metafied) and will need tracking
+ * down.
  */
 #define METAINC(x)	((x) += (*(x) == Meta) ? 2 : 1)
 /*
@@ -254,13 +286,18 @@ static int patglobflags;  /* globbing flags & approx */
 
 /* Add n more characters, ensuring there is enough space. */
 
+enum {
+    PA_NOALIGN = 1,
+    PA_UNMETA  = 2
+};
+
 /**/
 static void
-patadd(char *add, int ch, long n, int noalgn)
+patadd(char *add, int ch, long n, int paflags)
 {
-    /* Make sure everything gets aligned unless we get noalgn. */
+    /* Make sure everything gets aligned unless we get PA_NOALIGN. */
     long newpatsize = patsize + n;
-    if (!noalgn)
+    if (!(paflags & PA_NOALIGN))
 	newpatsize = (newpatsize + sizeof(union upat) - 1) &
 		      ~(sizeof(union upat) - 1);
     if (patalloc < newpatsize) {
@@ -272,8 +309,25 @@ patadd(char *add, int ch, long n, int noalgn)
     }
     patsize = newpatsize;
     if (add) {
-	while (n--)
-	    *patcode++ = *add++;
+	if (paflags & PA_UNMETA) {
+	    /*
+	     * Unmetafy and untokenize the string as we go.
+	     * The Meta characters in add aren't counted in n.
+	     */
+	    while (n--) {
+		if (itok(*add))
+		    *patcode++ = ztokens[*add++ - Pound];
+		else if (*add == Meta) {
+		    add++;
+		    *patcode++ = *add++ ^ 32;
+		} else {
+		    *patcode++ = *add++;
+		}
+	    }
+	} else {
+	    while (n--)
+		*patcode++ = *add++;
+	}
     } else
 	*patcode++ = ch;
     patcode = patout + patsize;
@@ -297,13 +351,22 @@ patcompstart(void)
 	patglobflags = GF_IGNCASE;
 }
 
-/* Top level pattern compilation subroutine */
+/*
+ * Top level pattern compilation subroutine
+ * exp is a null-terminated, metafied string.
+ * inflags is an or of some PAT_* flags.
+ * endexp, if non-null, is set to a pointer to the end of the
+ *   part of exp which was compiled.  This is used when
+ *   compiling patterns for directories which must be
+ *   matched recursively.
+ */
 
 /**/
 mod_export Patprog
 patcompile(char *exp, int inflags, char **endexp)
 {
-    int flags = 0, len = 0;
+    int flags = 0;
+    long len = 0;
     long startoff;
     Upat pscan;
     char *lng, *strp = NULL;
@@ -324,7 +387,7 @@ patcompile(char *exp, int inflags, char **endexp)
      * in struct is actual count of parentheses.
      */
     patnpar = 1;
-    patflags = inflags & ~PAT_PURES;
+    patflags = inflags & ~(PAT_PURES|PAT_HAS_EXCLUDP);
 
     patendseg = endseg;
     patendseglen = isset(EXTENDEDGLOB) ? PATENDSEGLEN_EXT : PATENDSEGLEN_NORM;
@@ -366,7 +429,12 @@ patcompile(char *exp, int inflags, char **endexp)
 	    if (patcompswitch(0, &flags) == 0)
 		return NULL;
 	} else {
-	    /* Yes, copy the string and skip compilation altogether */
+	    /*
+	     * Yes, copy the string, and skip compilation altogether.
+	     * Null terminate for the benefit of globbing.
+	     * Leave metafied both for globbing and for our own
+	     * efficiency.
+	     */
 	    patparse = strp;
 	    len = strp - exp;
 	    patadd(exp, 0, len + 1, 0);
@@ -404,19 +472,52 @@ patcompile(char *exp, int inflags, char **endexp)
 		for (; pscan; pscan = next) {
 		    next = PATNEXT(pscan);
 		    if (P_OP(pscan) == P_EXACTLY) {
-			char *opnd = (char *)P_OPERAND(pscan);
-			while ((*dst = *opnd++))
-			    dst++;
+			char *opnd = P_LS_STR(pscan), *mtest;
+			long oplen = P_LS_LEN(pscan), ilen;
+			int nmeta = 0;
+			/*
+			 * Unfortunately we unmetafied the string
+			 * and we need to put any metacharacters
+			 * back now we know it's a pure string.
+			 * This shouldn't happen too often, it's
+			 * just that there are some cases such
+			 * as . and .. in files where we really
+			 * need a pure string even if there are
+			 * pattern characters flying around.
+			 */
+			for (mtest = opnd, ilen = oplen; ilen;
+			     mtest++, ilen--)
+			    if (imeta(*mtest))
+				nmeta++;
+			if (nmeta) {
+			    char *oldpatout = patout;
+			    patadd(NULL, 0, nmeta, 0);
+			    /*
+			     * Yuk.
+			     */
+			    p = (Patprog)patout;
+			    opnd = patout + (opnd - oldpatout);
+			    dst = patout + startoff;
+			}
+
+			while (oplen--) {
+			    if (imeta(*opnd)) {
+				*dst++ = Meta;
+				*dst++ = *opnd ^ 32;
+			    } else {
+				*dst++ = *opnd++;
+			    }
+			}
 		    }
 		}
-		*dst++ = '\0';
 		p->size = dst - patout;
-		/* patmlen is really strlen, don't include null byte */
-		p->patmlen = p->size - startoff - 1;
+		/* patmlen is really strlen.  We don't need a null. */
+		p->patmlen = p->size - startoff;
 	    } else {
 		/* starting point info */
-		if (P_OP(pscan) == P_EXACTLY && !p->globflags)
-		    p->patstartch = *(char *)P_OPERAND(pscan);
+		if (P_OP(pscan) == P_EXACTLY && !p->globflags &&
+		    P_LS_LEN(pscan))
+		    p->patstartch = *P_LS_STR(pscan);
 		/*
 		 * Find the longest literal string in something expensive.
 		 * This is itself not all that cheap if we have
@@ -427,9 +528,9 @@ patcompile(char *exp, int inflags, char **endexp)
 		    len = 0;
 		    for (; pscan; pscan = PATNEXT(pscan))
 			if (P_OP(pscan) == P_EXACTLY &&
-			    (int)strlen((char *)P_OPERAND(pscan)) >= len) {
-			    lng = (char *)P_OPERAND(pscan);
-			    len = strlen(lng);
+			    P_LS_LEN(pscan) >= len) {
+			    lng = P_LS_STR(pscan);
+			    len = P_LS_LEN(pscan);
 			}
 		    if (lng) {
 			p->mustoff = lng - patout;
@@ -844,9 +945,9 @@ static long
 patcomppiece(int *flagp)
 {
     long starter = 0, next, pound, op;
-    int flags, flags2, kshchar, len, ch, patch;
+    int flags, flags2, kshchar, len, ch, patch, nmeta;
     union upat up;
-    char *nptr, *str0, cbuf[2];
+    char *nptr, *str0, *ptr, cbuf[2];
     zrange_t from, to;
 
     flags = 0;
@@ -881,6 +982,9 @@ patcomppiece(int *flagp)
     }
 
     if (patparse > str0) {
+	long slen = patparse - str0;
+	int morelen;
+
 	/* Ordinary string: cancel kshchar lookahead */
 	kshchar = '\0';
 	/*
@@ -889,25 +993,40 @@ patcomppiece(int *flagp)
 	flags |= P_PURESTR;
 	DPUTS(patparse == str0, "BUG: matched nothing in patcomppiece.");
 	/* more than one character matched? */
-	len = str0 + (*str0 == Meta ? 2 : 1) < patparse;
+	morelen = str0 + (*str0 == Meta ? 2 : 1) < patparse;
 	/*
 	 * If we have more than one character, a following hash only
 	 * applies to the last, so decrement.
 	 */
-	if (isset(EXTENDEDGLOB) && *patparse == Pound && len)
+	if (isset(EXTENDEDGLOB) && *patparse == Pound && morelen)
 	    patparse -= (patparse > str0 + 1 && patparse[-2] == Meta) ? 2 : 1;
 	/*
 	 * If len is 1, we can't have an active # following, so doesn't
 	 * matter that we don't make X in `XX#' simple.
 	 */
-	if (!len)
+	if (!morelen)
 	    flags |= P_SIMPLE;
 	starter = patnode(P_EXACTLY);
-	/* add enough space including null byte */
-	len = patparse - str0;
-	patadd(str0, 0, len + 1, 0);
-	nptr = (char *)P_OPERAND((Upat)patout + starter);
-	nptr[len] = '\0';
+
+	/* Get length of string without metafication. */
+	nmeta = 0;
+	for (ptr = str0; ptr < patparse; ptr++) {
+	    if (*ptr == Meta) {
+		nmeta++;
+		ptr++;
+	    }
+	}
+	slen = (patparse - str0) - nmeta;
+	/* First add length, which is a long */
+	patadd((char *)&slen, 0, sizeof(long), 0);
+	/*
+	 * Then the string, not null terminated.
+	 * Unmetafy and untokenize; pass the final length,
+	 * which is what we need to allocate, i.e. not including
+	 * a count for each Meta in the string.
+	 */
+	patadd(str0, 0, slen, PA_UNMETA);
+	nptr = P_LS_STR((Upat)patout + starter);
 	/*
 	 * It's much simpler to turn off pure string mode for
 	 * any case-insensitive or approximate matching; usually,
@@ -918,13 +1037,13 @@ patcomppiece(int *flagp)
 	 * ..(#a1).. (i.e. the (#a1) has no effect), but if you're
 	 * going to write funny patterns, you get no sympathy from me.
 	 */
-	if (patglobflags &&
-	    (!(patflags & PAT_FILE) || (strcmp(nptr, ".") &&
-					strcmp(nptr, ".."))))
-	    flags &= ~P_PURESTR;
-	for (; *nptr; METAINC(nptr))
-	    if (itok(*nptr))
-		*nptr = ztokens[*nptr - Pound];
+	if (patglobflags) {
+	    if (!(patflags & PAT_FILE))
+		flags &= ~P_PURESTR;
+	    else if (!(nptr[0] == '.' &&
+		       (slen == 1 || (nptr[1] == '.' && slen == 2))))
+		flags &= ~P_PURESTR;
+	}
     } else {
 	if (kshchar)
 	    patparse++;
@@ -950,7 +1069,7 @@ patcomppiece(int *flagp)
 		starter = patnode(P_ANYOF);
 	    if (*patparse == Outbrack) {
 		patparse++;
-		patadd(NULL, ']', 1, 1);
+		patadd(NULL, ']', 1, PA_NOALIGN);
 	    }
 	    while (*patparse && *patparse != Outbrack) {
 		/* Meta is not a token */
@@ -990,7 +1109,7 @@ patcomppiece(int *flagp)
 			    ch = PP_UNKWN;
 			patparse = nptr + 2;
 			if (ch != PP_UNKWN)
-			    patadd(NULL, STOUC(Meta+ch), 1, 1);
+			    patadd(NULL, STOUC(Meta+ch), 1, PA_NOALIGN);
 			continue;
 		}
 		if (itok(*patparse)) {
@@ -1003,15 +1122,17 @@ patcomppiece(int *flagp)
 		patparse++;
 
 		if (*patparse == '-' && patparse[1] != Outbrack) {
-		    patadd(NULL, STOUC(Meta+PP_RANGE), 1, 1);
-		    patadd(cbuf, 0, (cbuf[0] == Meta) ? 2 : 1, 1);
+		    patadd(NULL, STOUC(Meta+PP_RANGE), 1, PA_NOALIGN);
+		    patadd(cbuf, 0, (cbuf[0] == Meta) ? 2 : 1, PA_NOALIGN);
 		    if (itok(*++patparse)) {
-			patadd(0, STOUC(ztokens[*patparse - Pound]), 1, 1);
+			patadd(0, STOUC(ztokens[*patparse - Pound]), 1,
+			       PA_NOALIGN);
 		    } else
-			patadd(patparse, 0, (*patparse == Meta) ? 2 : 1, 1);
+			patadd(patparse, 0, (*patparse == Meta) ? 2 : 1,
+			       PA_NOALIGN);
 		    METAINC(patparse);
 		} else
-		    patadd(cbuf, 0, (cbuf[0] == Meta) ? 2 : 1, 1);
+		    patadd(cbuf, 0, (cbuf[0] == Meta) ? 2 : 1, PA_NOALIGN);
 	    }
 	    if (*patparse != Outbrack)
 		return 0;
@@ -1309,19 +1430,11 @@ static void patoptail(long p, long val)
  */
 static char *patinstart;	/* Start of input string */
 static char *patinend;		/* End of input string */
+static char *patinput;		/* String input pointer */
 static char *patinpath;		/* Full path for use with ~ exclusions */
-
-/**/
-char *patinput;		/* String input pointer */
-
-/*
- * Offset of string at which we are trying to match.
- * This is added in to the positions recorded in patbeginp and patendp
- * when we are looking for substrings.  Currently this only happens
- * in the parameter substitution code.
- */
-/**/
-int patoffset;
+static int   patinlen;		/* Length of last successful match.
+				 * Includes count of Meta characters.
+				 */
 
 static char *patbeginp[NSUBEXP];	/* Pointer to backref beginnings */
 static char *patendp[NSUBEXP];		/* Pointer to backref ends */
@@ -1330,8 +1443,23 @@ static int parsfound;			/* parentheses (with backrefs) found */
 static int globdots;			/* Glob initial dots? */
 
 /*
+ * Macros which are currently trivial but are likely to be less
+ * so when we handle multibyte characters.  They operate on
+ * umetafied strings.
+ */
+
+/* Get a character from the start point in a string */
+#define CHARREF(x)	(STOUC(*x))
+/* Get  a pointer to the next character */
+#define CHARNEXT(x)	(x+1)
+/* Increment a pointer past the current character. */
+#define CHARINC(x)	(x++)
+/* Counter the number of characters between two pointers, largest first */
+#define CHARSUB(x,y)	(x-y)
+
+/*
  * The following need to be accessed in the globbing scanner for
- * a multi-component file path.  See horror story there.
+ * a multi-component file path.  See horror story in glob.c.
  */
 /**/
 int errsfound;				/* Total error count so far */
@@ -1347,23 +1475,59 @@ pattrystart(void)
     errsfound = 0;
 }
 
+/*
+ * Test prog against null-terminated, metafied string.
+ */
+
 /**/
 mod_export int
 pattry(Patprog prog, char *string)
 {
-    return pattryrefs(prog, string, NULL, NULL, NULL);
+    return pattryrefs(prog, string, -1, 0, NULL, NULL, NULL);
+}
+
+/*
+ * Test prog against string of given length, no null termination
+ * but still metafied at this point.  offset gives an offset
+ * to include in reported match indices
+ */
+
+/**/
+mod_export int
+pattrylen(Patprog prog, char *string, int len, int offset)
+{
+    return pattryrefs(prog, string, len, offset, NULL, NULL, NULL);
 }
 
-/* The last three arguments are used to report the positions for the
+/*
+ * Test prog against string with given length stringlen, which
+ * may be -1 to indicate a null-terminated string.  The input
+ * string is metafied; the length is the raw string length, not the
+ * number of possibly metafied characters.
+ *
+ * offset is the position in the original string (not seen by
+ * the patter module) at which we are trying to match.
+ * This is added in to the positions recorded in patbeginp and patendp
+ * when we are looking for substrings.  Currently this only happens
+ * in the parameter substitution code.
+ *
+ * Note this is a character offset, i.e. a metafied character
+ * counts as 1.
+ *
+ * The last three arguments are used to report the positions for the
  * backreferences. On entry, *nump should contain the maximum number
- * positions to report. */
+ * of positions to report.  In this case the match, mbegin, mend
+ * arrays are not altered.
+ */
 
 /**/
 mod_export int
-pattryrefs(Patprog prog, char *string, int *nump, int *begp, int *endp)
+pattryrefs(Patprog prog, char *string, int stringlen, int patoffset,
+	   int *nump, int *begp, int *endp)
 {
-    int i, maxnpos = 0, ret;
-    char **sp, **ep;
+    int i, maxnpos = 0, ret, needfullpath, unmetalen, unmetalenp;
+    int origlen;
+    char **sp, **ep, *tryalloced, *ptr;
     char *progstr = (char *)prog + prog->startoff;
 
     if (nump) {
@@ -1374,12 +1538,87 @@ pattryrefs(Patprog prog, char *string, int *nump, int *begp, int *endp)
     if (*string == Nularg)
 	string++;
 
-    patinstart = patinput = string;
-    patinend = patinstart + strlen(patinstart);
+    if (stringlen < 0)
+	stringlen = strlen(string);
+    origlen = stringlen;
+
+    patflags = prog->flags;
+    /*
+     * For a top-level ~-exclusion, we will need the full
+     * path to exclude, so copy the path so far and append the
+     * current test string.
+     */
+    needfullpath = (patflags & PAT_HAS_EXCLUDP) && pathpos;
+
+    /* Get the length of the full string when unmetafied. */
+    unmetalen = ztrsub(string + stringlen, string);
+    if (needfullpath)
+	unmetalenp = ztrsub(pathbuf + pathpos, pathbuf);
+    else
+	unmetalenp = 0;
+
+    DPUTS(needfullpath && (patflags & (PAT_PURES|PAT_ANY)),
+	  "rum sort of file exclusion");
+    /*
+     * Partly for efficiency, and partly for the convenience of
+     * globbing, we don't unmetafy pure string patterns, and
+     * there's no reason to if the pattern is just a *.
+     */
+    if (!(patflags & (PAT_PURES|PAT_ANY))
+	&& (needfullpath || unmetalen != stringlen)) {
+	/*
+	 * We need to copy if we need to prepend the path so far
+	 * (in which case we copy both chunks), or if we have
+	 * Meta characters.
+	 */
+	char *dst;
+	int icopy, ncopy;
+
+	dst = tryalloced = zalloc(unmetalen + unmetalenp);
+
+	if (needfullpath) {
+	    /* loop twice, copy path buffer first time */
+	    ptr = pathbuf;
+	    ncopy = unmetalenp;
+	} else {
+	    /* just loop once, copy string with unmetafication */
+	    ptr = string;
+	    ncopy = unmetalen;
+	}
+	for (icopy = 0; icopy < 2; icopy++) {
+	    for (i = 0; i < ncopy; i++) {
+		if (*ptr == Meta) {
+		    ptr++;
+		    *dst++ = *ptr++ ^ 32;
+		} else {
+		    *dst++ = *ptr++;
+		}
+	    }
+	    if (!needfullpath)
+		break;
+	    /* next time append test string to path so far */
+	    ptr = string;
+	    ncopy = unmetalen;
+	}
+
+	if (needfullpath) {
+	    patinstart = tryalloced + unmetalenp;
+	    patinpath = tryalloced;
+	} else {
+	    patinstart = tryalloced;
+	    patinpath = NULL;
+	}
+	stringlen = unmetalen;
+    } else {
+	patinstart = string;
+	tryalloced = patinpath = NULL;
+    }
+
+    patinend = patinstart + stringlen;
     /*
      * From now on we do not require NULL termination of
-     * the test string.  It is still metafied, as is string
-     * data in the prog.
+     * the test string.  There should also be no more references
+     * to the variable string.
      */
 
     if (prog->flags & (PAT_PURES|PAT_ANY)) {
@@ -1399,11 +1638,11 @@ pattryrefs(Patprog prog, char *string, int *nump, int *begp, int *endp)
 	     * Testing a pure string.  See if initial
 	     * components match.
 	     */
-	    int lendiff = (patinend - patinstart) - prog->patmlen;
+	    int lendiff = stringlen - prog->patmlen;
 	    if (lendiff < 0) {
 		/* No, the pattern string is too long. */
 		ret = 0;
-	    } else if (!memcmp(progstr, string, prog->patmlen)) {
+	    } else if (!memcmp(progstr, patinstart, prog->patmlen)) {
 		/*
 		 * Initial component matches.  Matches either
 		 * if lengths are the same or we are not anchored
@@ -1420,47 +1659,61 @@ pattryrefs(Patprog prog, char *string, int *nump, int *begp, int *endp)
 	     * For files, we won't match initial "."s unless
 	     * glob_dots is set.
 	     */
-	    if ((prog->flags & PAT_NOGLD) && *string == '.')
-		return 0;
-	    /* in case used for ${..#..} etc. */
-	    patinput = string + prog->patmlen;
-	    /* if matching files, must update globbing flags */
-	    patglobflags = prog->globend;
-	    return 1;
-	} else
-	    return 0;
+	    if ((prog->flags & PAT_NOGLD) && *patinstart == '.') {
+		ret = 0;
+	    } else {
+		/*
+		 * Remember the length in case used for ${..#..} etc.
+		 * In this case, we didn't unmetafy the string.
+		 */
+		patinlen = (int)prog->patmlen;
+		/* if matching files, must update globbing flags */
+		patglobflags = prog->globend;
+	    }
+	}
+
+	if (tryalloced)
+	    zfree(tryalloced, unmetalen + unmetalenp);
+
+	return ret;
     } else {
 	/*
 	 * Test for a `must match' string, unless we're scanning for a match
 	 * in which case we don't need to do this each time.
 	 */
+	ret = 1;
 	if (!(prog->flags & PAT_SCAN) && prog->mustoff)
 	{
 	    char *testptr;	/* start pointer into test string */
 	    char *teststop;	/* last point from which we can match */
 	    char *patptr = (char *)prog + prog->mustoff;
-	    int patlen = strlen(patptr);
+	    int patlen = prog->patmlen;
 	    int found = 0;
 
-	    if (patlen > patinend - patinstart) {
+	    if (patlen > stringlen) {
 		/* Too long, can't match. */
-		return 0;
-	    }
-	    teststop = patinend - patlen;
+		ret = 0;
+	    } else {
+		teststop = patinend - patlen;
 
-	    for (testptr = patinstart; testptr <= teststop; testptr++)
-	    {
-		if (!memcmp(testptr, patptr, patlen)) {
-		    found = 1;
-		    break;
+		for (testptr = patinstart; testptr <= teststop; testptr++)
+		{
+		    if (!memcmp(testptr, patptr, patlen)) {
+			found = 1;
+			break;
+		    }
 		}
-	    }
 
-	    if (!found)
-		return 0;
+		if (!found)
+		    ret = 0;
+	    }
+	}
+	if (!ret) {
+	    if (tryalloced)
+		zfree(tryalloced, unmetalen + unmetalenp);
+	    return 0;
 	}
 
-	patflags = prog->flags;
 	patglobflags = prog->globflags;
 	if (!(patflags & PAT_FILE)) {
 	    forceerrs = -1;
@@ -1469,26 +1722,7 @@ pattryrefs(Patprog prog, char *string, int *nump, int *begp, int *endp)
 	globdots = !(patflags & PAT_NOGLD);
 	parsfound = 0;
 
-	if ((patflags & PAT_HAS_EXCLUDP) && pathpos) {
-	    /*
-	     * For a top-level ~-exclusion, we will need the full
-	     * path to exclude, so copy the path so far and append the
-	     * current test string.
-	     *
-	     * There are some advantages in making patinstart etc.
-	     * point into this new string; however, that gets confusing
-	     * if we need patinput outside this file.  That's
-	     * not likely for files but I don't think it's worth
-	     * the risk.
-	     */
-	    int len = patinend - patinstart;
-
-	    patinpath = (char *)zalloc(pathpos + len);
-	    memcpy(patinpath, pathbuf, pathpos);
-	    memcpy(patinpath + pathpos, patinstart, len);
-	} else {
-	    patinpath = NULL;
-	}
+	patinput = patinstart;
 
 	if (patmatch((Upat)progstr)) {
 	    /*
@@ -1496,6 +1730,23 @@ pattryrefs(Patprog prog, char *string, int *nump, int *begp, int *endp)
 	     * failed, so set it now
 	     */
 	    patglobflags = prog->globend;
+
+	    /*
+	     * Record length of successful match, including Meta
+	     * characters.  Do it here so that patmatchlen() can return
+	     * it even if we delete the pattern strings.
+	     */
+	    patinlen = patinput - patinstart;
+	    /*
+	     * Optimization: if we didn't find any Meta characters
+	     * to begin with, we don't need to look for them now.
+	     */
+	    if (unmetalen != origlen) {
+		for (ptr = patinstart; ptr < patinput; ptr++)
+		    if (imeta(*ptr))
+			patinlen++;
+	    }
+
 	    /*
 	     * Should we clear backreferences and matches on a failed
 	     * match?
@@ -1504,15 +1755,18 @@ pattryrefs(Patprog prog, char *string, int *nump, int *begp, int *endp)
 		/*
 		 * m flag: for global match.  This carries no overhead
 		 * in the pattern matching part.
+		 *
+		 * Remember the test pattern is already unmetafied.
 		 */
 		char *str;
-		int mlen = ztrsub(patinput, patinstart);
+		int mlen = CHARSUB(patinput, patinstart);
 
-		str = ztrduppfx(patinstart, patinput - patinstart);
+		str = metafy(patinstart, patinput - patinstart, META_DUP);
 		setsparam("MATCH", str);
 		setiparam("MBEGIN", (zlong)(patoffset + !isset(KSHARRAYS)));
 		setiparam("MEND",
-			  (zlong)(mlen + patoffset + !isset(KSHARRAYS) - 1));
+			  (zlong)(mlen + patoffset +
+				  !isset(KSHARRAYS) - 1));
 	    }
 	    if (prog->patnpar && nump) {
 		/*
@@ -1527,9 +1781,10 @@ pattryrefs(Patprog prog, char *string, int *nump, int *begp, int *endp)
 		for (i = 0; i < prog->patnpar && i < maxnpos; i++) {
 		    if (parsfound & (1 << i)) {
 			if (begp)
-			    *begp++ = ztrsub(*sp, patinstart) + patoffset;
+			    *begp++ = CHARSUB(*sp, patinstart) + patoffset;
 			if (endp)
-			    *endp++ = ztrsub(*ep, patinstart) + patoffset - 1;
+			    *endp++ = CHARSUB(*ep, patinstart) + patoffset
+				- 1;
 		    } else {
 			if (begp)
 			    *begp++ = -1;
@@ -1557,7 +1812,7 @@ pattryrefs(Patprog prog, char *string, int *nump, int *begp, int *endp)
 
 		for (i = 0; i < prog->patnpar; i++) {
 		    if (parsfound & (1 << i)) {
-			matcharr[i] = ztrduppfx(*sp, *ep - *sp);
+			matcharr[i] = metafy(*sp, *ep - *sp, META_DUP);
 			/*
 			 * mbegin and mend give indexes into the string
 			 * in the standard notation, i.e. respecting
@@ -1568,12 +1823,12 @@ pattryrefs(Patprog prog, char *string, int *nump, int *begp, int *endp)
 			 * corresponds to indexing as ${foo[1,1]}.
 			 */
 			sprintf(numbuf, "%ld",
-				(long)(ztrsub(*sp, patinstart) + 
+				(long)(CHARSUB(*sp, patinstart) +
 				       patoffset +
 				       !isset(KSHARRAYS)));
 			mbeginarr[i] = ztrdup(numbuf);
 			sprintf(numbuf, "%ld",
-				(long)(ztrsub(*ep, patinstart) + 
+				(long)(CHARSUB(*ep, patinstart) +
 				       patoffset +
 				       !isset(KSHARRAYS) - 1));
 			mendarr[i] = ztrdup(numbuf);
@@ -1593,20 +1848,32 @@ pattryrefs(Patprog prog, char *string, int *nump, int *begp, int *endp)
 		setaparam("mbegin", mbeginarr);
 		setaparam("mend", mendarr);
 	    }
+
 	    ret = 1;
 	} else
 	    ret = 0;
 
-	if (patinpath) {
-	    zfree(patinpath, pathpos + (patinend - patinstart));
-	    patinpath = NULL;
-	}
+	if (tryalloced)
+	    zfree(tryalloced, unmetalen + unmetalenp);
 
 	return ret;
     }
 }
 
 /*
+ * Return length of previous succesful match.  This is
+ * in metafied bytes, i.e. includes a count of Meta characters.
+ * Unusual and futile attempt at modular encapsulation.
+ */
+
+/**/
+int
+patmatchlen(void)
+{
+    return patinlen;
+}
+
+/*
  * Match literal characters with case insensitivity test:  the first
  * comes from the input string, the second the current pattern.
  */
@@ -1627,8 +1894,11 @@ pattryrefs(Patprog prog, char *string, int *nump, int *begp, int *endp)
  * exactpos is used to remember how far down an exact string we have
  * matched, if we are doing approximation and can therefore redo from
  * the same point; we never need to otherwise.
+ *
+ * exactend is a pointer to the end of the string, which isn't
+ * null-terminated.
  */
-static char *exactpos;
+static char *exactpos, *exactend;
 
 /*
  * Main matching routine.
@@ -1643,7 +1913,7 @@ patmatch(Upat prog)
 {
     /* Current and next nodes */
     Upat scan = prog, next, opnd;
-    char *start, *save, *chrop, *compend;
+    char *start, *save, *chrop, *chrend, *compend;
     int savglobflags, op, no, min, nextch, fail = 0, saverrsfound;
     zrange_t from, to, comp;
 
@@ -1659,45 +1929,52 @@ patmatch(Upat prog)
 	    if (patinput == patinend)
 		fail = 1;
 	    else
-		METAINC(patinput);
+		CHARINC(patinput);
 	    break;
 	case P_EXACTLY:
 	    /*
 	     * acts as nothing if *chrop is null:  this is used by
 	     * approx code.
 	     */
-	    chrop = exactpos ? exactpos : (char *)P_OPERAND(scan);
+	    if (exactpos) {
+		chrop = exactpos;
+		chrend = exactend;
+	    } else {
+		chrop = P_LS_STR(scan);
+		chrend = chrop + P_LS_LEN(scan);
+	    }
 	    exactpos = NULL;
-	    while (*chrop && patinput < patinend) {
-		int chin = STOUC(UNMETA(patinput));
-		int chpa = STOUC(UNMETA(chrop));
+	    while (chrop < chrend && patinput < patinend) {
+		int chin = CHARREF(patinput);
+		int chpa = CHARREF(chrop);
 		if (!CHARMATCH(chin, chpa)) {
 		    fail = 1;
 		    break;
 		}
-		METAINC(chrop);
-		METAINC(patinput);
+		CHARINC(chrop);
+		CHARINC(patinput);
 	    }
-	    if (*chrop) {
+	    if (chrop < chrend) {
 		exactpos = chrop;
+		exactend = chrend;
 		fail = 1;
 	    }
 	    break;
 	case P_ANYOF:
 	    if (patinput == patinend ||
 		!patmatchrange((char *)P_OPERAND(scan),
-			       STOUC(UNMETA(patinput))))
+			       CHARREF(patinput)))
 		fail = 1;
 	    else
-		METAINC(patinput);
+		CHARINC(patinput);
 	    break;
 	case P_ANYBUT:
 	    if (patinput == patinend ||
 		patmatchrange((char *)P_OPERAND(scan),
-			      STOUC(UNMETA(patinput))))
+			      CHARREF(patinput)))
 		fail = 1;
 	    else
-		METAINC(patinput);
+		CHARINC(patinput);
 	    break;
 	case P_NUMRNG:
 	case P_NUMFROM:
@@ -1771,7 +2048,8 @@ patmatch(Upat prog)
 		    return 1;
 		}
 		if (!no && P_OP(next) == P_EXACTLY &&
-		    !idigit(STOUC(*(char *)P_OPERAND(next))) &&
+		    (!P_LS_LEN(next) ||
+		     !idigit(STOUC(*P_LS_STR(next)))) &&
 		    !(patglobflags & 0xff))
 		    return 0;
 		patinput = --save;
@@ -1791,7 +2069,7 @@ patmatch(Upat prog)
 	case P_NUMANY:
 	    /* This is <->: any old set of digits, don't bother comparing */
 	    start = patinput;
-	    while (patinput < patinend && idigit(STOUC(*patinput)))
+	    while (patinput < patinend && idigit(CHARREF(patinput)))
 		patinput++;
 	    save = patinput;
 	    no = 0;
@@ -1799,7 +2077,8 @@ patmatch(Upat prog)
 		if (patmatch(next))
 		    return 1;
 		if (!no && P_OP(next) == P_EXACTLY &&
-		    !idigit(STOUC(*(char *)P_OPERAND(next))) &&
+		    (!P_LS_LEN(next) ||
+		     !idigit(CHARREF(P_LS_STR(next)))) &&
 		    !(patglobflags & 0xff))
 		    return 0;
 		patinput = --save;
@@ -1963,7 +2242,7 @@ patmatch(Upat prog)
 			origpatinend = patinend;
 			while ((ret = patmatch(P_OPERAND(scan)))) {
 			    unsigned char *syncpt;
-			    char *savpatinstart, *savpatinend;
+			    char *savpatinstart;
 			    int savforce = forceerrs;
 			    int savpatflags = patflags, synclen;
 			    forceerrs = -1;
@@ -1998,7 +2277,6 @@ patmatch(Upat prog)
 				patflags |= PAT_NOTEND;
 			    }
 			    savpatinstart = patinstart;
-			    savpatinend = patinend;
 			    next = PATNEXT(scan);
 			    while (next && P_ISEXCLUDE(next)) {
 				patinput = save;
@@ -2013,14 +2291,15 @@ patmatch(Upat prog)
 				opnd = P_OPERAND(next) + 1;
 				if (P_OP(next) == P_EXCLUDP && patinpath) {
 				    /*
-				     * top level exclusion with a file,
+				     * Top level exclusion with a file,
 				     * applies to whole path so add the
-				     * segments already matched
+				     * segments already matched.
+				     * We copied these in front of the
+				     * test pattern, so patinend doesn't
+				     * need moving.
 				     */
 				    DPUTS(patinput != patinstart,
 					  "BUG: not at start excluding path");
-				    patinend = patinpath + pathpos +
-					(patinend - patinstart);
 				    patinput = patinstart = patinpath;
 				}
 				if (patmatch(opnd)) {
@@ -2036,7 +2315,6 @@ patmatch(Upat prog)
 				    patinput = savpatinstart +
 					(patinput - patinstart);
 				    patinstart = savpatinstart;
-				    patinend = savpatinend;
 				}
 				if (!ret)
 				    break;
@@ -2146,7 +2424,7 @@ patmatch(Upat prog)
 	    /* Note that no counts possibly metafied characters */
 	    start = patinput;
 	    if (op == P_STAR) {
-		for (no = 0; patinput < patinend; METAINC(patinput))
+		for (no = 0; patinput < patinend; CHARINC(patinput))
 		    no++;
 		/* simple optimization for reasonably common case */
 		if (P_OP(next) == P_END)
@@ -2156,7 +2434,7 @@ patmatch(Upat prog)
 		      "BUG: wrong backtracking with approximation.");
 		if (!globdots && P_NOTDOT(P_OPERAND(scan)) &&
 		    patinput == patinstart && patinput < patinend &&
-		    *patinput == '.')
+		    CHARREF(patinput) == '.')
 		    return 0;
 		no = patrepeat(P_OPERAND(scan));
 	    }
@@ -2165,8 +2443,9 @@ patmatch(Upat prog)
 	     * Lookahead to avoid useless matches. This is not possible
 	     * with approximation.
 	     */
-	    if (P_OP(next) == P_EXACTLY && !(patglobflags & 0xff)) {
-		char *nextop = (char *)P_OPERAND(next);
+	    if (P_OP(next) == P_EXACTLY && P_LS_LEN(next) &&
+		!(patglobflags & 0xff)) {
+		char *nextop = P_LS_STR(next);
 		/*
 		 * If that P_EXACTLY is last (common in simple patterns,
 		 * such as *.c), then it can be only be matched at one
@@ -2175,21 +2454,20 @@ patmatch(Upat prog)
 		if (P_OP(PATNEXT(next)) == P_END &&
 		    !(patflags & PAT_NOANCH)) {
 		    int ptlen = patinend - patinput;
-		    int oplen = strlen(nextop);
-		    int lenmatch = patinend - (min ? METANEXT(start) : start);
+		    int lenmatch = patinend - (min ? CHARNEXT(start) : start);
 		    /* Are we in the right range? */
-		    if (oplen > lenmatch || oplen < ptlen)
+		    if (P_LS_LEN(next) > lenmatch || P_LS_LEN(next) < ptlen)
 			return 0;
 		    /* Yes, just position appropriately and test. */
-		    patinput += ptlen - oplen;
-		    if (patinput > start && patinput[-1] == Meta) {
-			/* doesn't align properly, no go */
-			return 0;
-		    }
+		    patinput += ptlen - P_LS_LEN(next);
+		    /*
+		     * Here we will need to be careful that patinput is not
+		     * in the middle of a multibyte character.
+		     */
 		    /* Continue loop with P_EXACTLY test. */
 		    break;
 		}
-		nextch = STOUC(UNMETA(nextop));
+		nextch = CHARREF(nextop);
 	    } else
 		nextch = -1;
 	    save = patinput;
@@ -2199,14 +2477,17 @@ patmatch(Upat prog)
 		int charmatch_cache;
 		if (nextch < 0 ||
 		    (patinput < patinend &&
-		     CHARMATCH_EXPR(STOUC(UNMETA(patinput)), nextch))) {
+		     CHARMATCH_EXPR(CHARREF(patinput), nextch))) {
 		    if (patmatch(next))
 			return 1;
 		}
 		no--;
 		save--;
-		if (save > start && save[-1] == Meta)
-		    save--;
+		/*
+		 * Here we will need to make sure save is
+		 * decremented properly to the start of
+		 * the preceeding multibyte character.
+		 */
 		patinput = save;
 		patglobflags = savglobflags;
 		errsfound = saverrsfound;
@@ -2270,7 +2551,7 @@ patmatch(Upat prog)
 
 		/* Try omitting a character from the input string */
 		if (patinput < patinend) {
-		    METAINC(patinput);
+		    CHARINC(patinput);
 		    /* If we are not on an exact match, then this is
 		     * our last gasp effort, so we can optimize out
 		     * the recursive call.
@@ -2285,11 +2566,11 @@ patmatch(Upat prog)
 		    char *nextexact = savexact;
 		    DPUTS(!savexact || !*savexact,
 			  "BUG: exact match has not set exactpos");
-		    METAINC(nextexact);
+		    CHARINC(nextexact);
 
 		    if (save < patinend) {
 			char *nextin = save;
-			METAINC(nextin);
+			CHARINC(nextin);
 			patglobflags = savglobflags;
 			errsfound = saverrsfound;
 			exactpos = savexact;
@@ -2299,18 +2580,18 @@ patmatch(Upat prog)
 			 * exactpos
 			 */
 			if (save < patinend && nextin < patinend &&
-			    *nextexact) {
-			    int cin0 = UNMETA(save);
-			    int cpa0 = UNMETA(exactpos);
-			    int cin1 = UNMETA(nextin);
-			    int cpa1 = UNMETA(nextexact);
+			    nextexact < exactend) {
+			    int cin0 = CHARREF(save);
+			    int cpa0 = CHARREF(exactpos);
+			    int cin1 = CHARREF(nextin);
+			    int cpa1 = CHARREF(nextexact);
 
 			    if (CHARMATCH(cin0, cpa1) &&
 				CHARMATCH(cin1, cpa0)) {
 				patinput = nextin;
-				METAINC(patinput);
+				CHARINC(patinput);
 				exactpos = nextexact;
-				METAINC(exactpos);
+				CHARINC(exactpos);
 				if (patmatch(scan))
 				    return 1;
 
@@ -2333,12 +2614,13 @@ patmatch(Upat prog)
 			exactpos = savexact;
 		    }
 
+		    DPUTS(exactpos == exactend, "approximating too far");
 		    /*
 		     * Try moving up the exact match pattern.
 		     * This must be the last attempt, so just loop
 		     * instead of calling recursively.
 		     */
-		    METAINC(exactpos);
+		    CHARINC(exactpos);
 		    continue;
 		}
 	    }
@@ -2358,6 +2640,11 @@ patmatchrange(char *range, int ch)
 {
     int r1, r2;
 
+    /*
+     * Careful here: unlike other strings, range is a NULL-terminated,
+     * metafied string, because we need to treat the Posix and hyphenated
+     * ranges specially.
+     */
     for (; *range; range++) {
 	if (imeta(STOUC(*range))) {
 	    switch (STOUC(*range)-STOUC(Meta)) {
@@ -2459,23 +2746,24 @@ static int patrepeat(Upat p)
 	break;
 #endif
     case P_EXACTLY:
-	tch = STOUC(UNMETA(opnd));
+	DPUTS(P_LS_LEN(p) != 1, "closure following more than one character");
+	tch = CHARREF(P_LS_STR(p));
 	while (scan < patinend &&
-	       CHARMATCH_EXPR(STOUC(UNMETA(scan)), tch)) {
+	       CHARMATCH_EXPR(CHARREF(scan), tch)) {
 	    count++;
-	    METAINC(scan);
+	    CHARINC(scan);
 	}
 	break;
     case P_ANYOF:
-	while (scan < patinend && patmatchrange(opnd, STOUC(UNMETA(scan)))) {
+	while (scan < patinend && patmatchrange(opnd, CHARREF(scan))) {
 	    count++;
-	    METAINC(scan);
+	    CHARINC(scan);
     	}
 	break;
     case P_ANYBUT:
-	while (scan < patinend && !patmatchrange(opnd, STOUC(UNMETA(scan)))) {
+	while (scan < patinend && !patmatchrange(opnd, CHARREF(scan))) {
 	    count++;
-	    METAINC(scan);
+	    CHARINC(scan);
     	}
 	break;
 #ifdef DEBUG
@@ -2528,7 +2816,14 @@ patdump(Patprog r)
 	    next = PATNEXT(up);
 	    printf("(%d)", next ? next-codestart : 0);
 	    s += sizeof(union upat);
-	    if (op == P_ANYOF || op == P_ANYBUT || op == P_EXACTLY) {
+	    if (op == P_EXACTLY) {
+		long llen = *(long *)s;
+		s += sizeof(long);
+		while (llen--) {
+		    putchar(CHARREF(s));
+		    CHARINC(s);
+		}
+	    } else if (op == P_ANYOF || op == P_ANYBUT) {
 		while (*s != '\0') {
 		    if (itok(*s)) {
 			if (*s == Meta + PP_RANGE) {