Patches 10513, 10516 (Alexandre), 10519 (Oliver), 10524

8 files changed, 1174 insertions, 1307 deletions

diff --git a/.distfiles b/.distfiles
index 84316b5e9..b9ab9ae0c 100644
--- a/.distfiles
+++ b/.distfiles
@@ -1,6 +1,6 @@
 DISTFILES_SRC='
-    .cvsignore .distfiles Makefile.in
-    ChangeLog ChangeLog.3.0 INSTALL META-FAQ README
+    .cvsignore .distfiles .preconfig Makefile.in
+    ChangeLog ChangeLog.3.0 INSTALL LICENCE META-FAQ README
     acconfig.h aclocal.m4 aczsh.m4 configure.in
     configure config.h.in stamp-h.in
     config.guess config.sub install-sh mkinstalldirs
diff --git a/ChangeLog b/ChangeLog
index adcd2acf9..2f00a6676 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,16 @@
+2000-04-05  Peter Stephenson  <pws@pwstephenson.fsnet.co.uk>
+
+	* 10524: Util/mkdisttree.sh: always copy files to tarred tree;
+	chmod g-s.
+
+	* Oliver: 10519: Src/utils.c, Doc/Zsh/compsys.yo: AIX dependencies
+	and minor typo in docs.
+
+	* Alexandre: 10516: Completion/User/_prcs: diff options behaviour.
+	
+	* 10513: Src/glob.c, Doc/Zsh/expn.yo: glob order qualifier (od)
+	implements depth-first ordering.
+
 2000-04-05  Bart Schaefer  <schaefer@zsh.org>
 
 	* 10499: Makefile.in: Dependencies relative to $(sdir).
diff --git a/Completion/User/_prcs b/Completion/User/_prcs
index 30c76e791..5f964fbac 100644
--- a/Completion/User/_prcs
+++ b/Completion/User/_prcs
@@ -5,7 +5,7 @@
 
 (( $+functions[_prcs_projects] )) ||
 _prcs_projects() {
-  compadd $@ - ${opt_args[-R]:-${opt_args[--repository]:-${PRCS_REPOSITORY:-$HOME/PRCS}}}/*(/:t)
+  compadd $@ - ${~opt_args[-R]:-${opt_args[--repository]:-${PRCS_REPOSITORY:-$HOME/PRCS}}}/*(/:t)
 }	   
 
 # standard options for all subcommands 
@@ -65,6 +65,7 @@ else
 	  compress\:"instruct PRCS to save disk space for project"
 	  init\:"create a repository entry"
 	  pdelete\:"delete a repository entry"
+	  pinfo\:"list all projects in the repository"
 	  prename\:"rename a repository entry"
 	  rebuild\:"reconstruct PRCS data files in the repository"
 	  uncompress\:"instruct PRCS to save time in processing project"))'
@@ -75,11 +76,17 @@ else
       access|compress|init|pdelete|prename|rebuild)
         _prcs_arguments ':project name:_prcs_projects'
         ;;
+      pinfo)
+	_prcs_arguments
+	;;
       uncompress)
         _prcs_arguments \
 	  '-i[expand the entire project immediately]' \
           ':project name:_prcs_projects'
         ;;
+      *)
+	_message "unknown prcs administrative subfunction: $words[1]"
+	;;
       esac
     fi
     ;;
@@ -120,11 +127,6 @@ else
       '*:file or directory:_files'
     ;;
   diff)
-#
-# FIXME: when there will be a _diff completion function,
-#        we should complete with diff options after `--' :
-# prcs diff [OPTION ...] [PROJECT [FILE-OR-DIR ...]] [-- [DIFF-OPTION ...]]
-#
     _prcs_arguments \
       '*--revison=[version of the project]:revision:' \
       '*-r[version of the project]:revision:' \
@@ -134,6 +136,7 @@ else
       '(--new)-N[compare new files against empty files]' \
       "(-P)--exclude-project-file[don't diff the project file]" \
       "(--exclude-project-file)-P[don't diff the project file]" \
+      '--[introduce diff options]:*::diff options:=  _diff_options ${PRCS_DIFF_COMMAND:-diff}' \
       ':project name:_prcs_projects' \
       '*:file or directory:_files'
     ;;
@@ -197,7 +200,7 @@ else
       ':project name:_prcs_projects'
     ;;
   *)
-    _message "unknown prcs command: $words[2]"
+    _message "unknown prcs command: $words[1]"
   ;;
   esac
 fi
diff --git a/Doc/Zsh/compsys.yo b/Doc/Zsh/compsys.yo
index 035a98e0d..e8eada391 100644
--- a/Doc/Zsh/compsys.yo
+++ b/Doc/Zsh/compsys.yo
@@ -2794,7 +2794,7 @@ are taken from the array parameter tt(expl) which will be set up
 before executing the var(action) and hence may be used in it (normally 
 in an expansion like `tt($expl[@])').
 
-If the var(action) starts with `tt(= )' (a equal sign followed by a
+If the var(action) starts with `tt(= )' (an equals sign followed by a
 space), tt(_arguments) will insert the contents of the var(argument)
 field of the current context as the new first element in the tt(words) 
 special array and increments the value of the tt(CURRENT) special
diff --git a/Doc/Zsh/expn.yo b/Doc/Zsh/expn.yo
index 7198df703..9d2f035c8 100644
--- a/Doc/Zsh/expn.yo
+++ b/Doc/Zsh/expn.yo
@@ -1619,19 +1619,24 @@ pindex(NUMERIC_GLOB_SORT, setting in pattern)
 )
 item(tt(o)var(c))(
 specifies how the names of the files should be sorted. If var(c) is
-tt(n) they are sorted by name (the default), if it is tt(L) they
-are sorted depending on the size (length) of the files, if tt(l) 
-they are sorted by the number of links, and if tt(a), tt(m), and tt(c)
+tt(n) they are sorted by name (the default); if it is tt(L) they
+are sorted depending on the size (length) of the files; if tt(l) 
+they are sorted by the number of links; if tt(a), tt(m), or tt(c)
 they are sorted by the time of the last access, modification, or
-inode change respectively. Note that tt(a), tt(m), and tt(c) compare
-the age against the current time, hence the first name in the list is the 
-the youngest file. Also note that the modifiers tt(^) and tt(-) are 
-used, so `tt(*(^-oL))' gives a list of all files sorted by file size in 
-descending order, following any symbolic links.
+inode change respectively; if var(d), files in subdirectories appear before
+those in the current directory at each level of the search --- this is best
+combined with other criteria, for example `tt(odon)' to sort on names for
+files within the same directory.  Note that tt(a), tt(m), and tt(c) compare
+the age against the current time, hence the first name in the list is the
+the youngest file. Also note that the modifiers tt(^) and tt(-) are used,
+so `tt(*(^-oL))' gives a list of all files sorted by file size in descending
+order, following any symbolic links.
 )
 item(tt(O)var(c))(
 like `tt(o)', but sorts in descending order; i.e. `tt(*(^oc))' is the
-same as `tt(*(Oc))' and `tt(*(^Oc))' is the same as `tt(*(oc))'
+same as `tt(*(Oc))' and `tt(*(^Oc))' is the same as `tt(*(oc))'; `tt(OD)'
+puts files in the current directory before those in subdirectories at each
+level of the search.
 )
 item(tt([)var(beg)[tt(,)var(end)]tt(]))(
 specifies which of the matched filenames should be included in the
diff --git a/Src/glob.c b/Src/glob.c
index be7a04515..663e0167f 100644
--- a/Src/glob.c
+++ b/Src/glob.c
@@ -30,21 +30,58 @@
 #include "zsh.mdh"
 #include "glob.pro"
 
+#if defined(OFF_T_IS_64_BIT) && defined(__GNUC__)
+# define ALIGN64 __attribute__((aligned(8)))
+#else
+# define ALIGN64
+#endif
+
 /* flag for CSHNULLGLOB */
- 
+
+typedef struct gmatch *Gmatch; 
+
+struct gmatch {
+    char *name;
+    off_t size ALIGN64;
+    long atime;
+    long mtime;
+    long ctime;
+    long links;
+    off_t _size ALIGN64;
+    long _atime;
+    long _mtime;
+    long _ctime;
+    long _links;
+};
+
+#define GS_NAME   1
+#define GS_DEPTH  2
+#define GS_SIZE   4
+#define GS_ATIME  8
+#define GS_MTIME 16
+#define GS_CTIME 32
+#define GS_LINKS 64
+
+#define GS_SHIFT  5
+#define GS__SIZE  (GS_SIZE << GS_SHIFT)
+#define GS__ATIME (GS_ATIME << GS_SHIFT)
+#define GS__MTIME (GS_MTIME << GS_SHIFT)
+#define GS__CTIME (GS_CTIME << GS_SHIFT)
+#define GS__LINKS (GS_LINKS << GS_SHIFT)
+
+#define GS_DESC  4096
+
+#define GS_NORMAL (GS_SIZE | GS_ATIME | GS_MTIME | GS_CTIME | GS_LINKS)
+#define GS_LINKED (GS_NORMAL << GS_SHIFT)
+
 /**/
 int badcshglob;
  
-static int mode;		/* != 0 if we are parsing glob patterns */
-static int pathpos;		/* position in pathbuf                  */
-static int matchsz;		/* size of matchbuf                     */
-static int matchct;		/* number of matches found              */
-static char *pathbuf;		/* pathname buffer                      */
-static int pathbufsz;		/* size of pathbuf			*/
-static int pathbufcwd;		/* where did we chdir()'ed		*/
-static char **matchbuf;		/* array of matches                     */
-static char **matchptr;		/* &matchbuf[matchct]                   */
-static char *colonmod;		/* colon modifiers in qualifier list    */
+/**/
+int pathpos;		/* position in pathbuf (needed by pattern code) */
+
+/**/
+char *pathbuf;		/* pathname buffer (needed by pattern code) */
 
 typedef struct stat *Statptr;	 /* This makes the Ultrix compiler happy.  Go figure. */
 
@@ -55,78 +92,130 @@ typedef struct stat *Statptr;	 /* This makes the Ultrix compiler happy.  Go figu
 #define TT_MINS 2
 #define TT_WEEKS 3
 #define TT_MONTHS 4
+#define TT_SECONDS 5
 
 #define TT_BYTES 0
 #define TT_POSIX_BLOCKS 1
 #define TT_KILOBYTES 2
 #define TT_MEGABYTES 3
 
-typedef int (*TestMatchFunc) _((struct stat *, long));
+
+typedef int (*TestMatchFunc) _((char *, struct stat *, off_t, char *));
 
 struct qual {
     struct qual *next;		/* Next qualifier, must match                */
     struct qual *or;		/* Alternative set of qualifiers to match    */
     TestMatchFunc func;		/* Function to call to test match            */
-    long data;			/* Argument passed to function               */
+    off_t data ALIGN64;		/* Argument passed to function               */
     int sense;			/* Whether asserting or negating             */
     int amc;			/* Flag for which time to test (a, m, c)     */
     int range;			/* Whether to test <, > or = (as per signum) */
     int units;			/* Multiplier for time or size, respectively */
+    char *sdata;		/* currently only: expression to eval        */
 };
 
-/* Qualifiers pertaining to current pattern */
-static struct qual *quals;
-
-/* Other state values for current pattern */
-static int qualct, qualorct;
-static int range, amc, units;
-static int gf_nullglob, gf_markdirs, gf_noglobdots, gf_listtypes, gf_follow;
-
 /* Prefix, suffix for doing zle trickery */
 
 /**/
-char *glob_pre, *glob_suf;
+mod_export char *glob_pre, *glob_suf;
+
+/* struct to easily save/restore current state */
+
+struct globdata {
+    int gd_pathpos;
+    char *gd_pathbuf;
+
+    int gd_matchsz;		/* size of matchbuf                     */
+    int gd_matchct;		/* number of matches found              */
+    int gd_pathbufsz;		/* size of pathbuf			*/
+    int gd_pathbufcwd;		/* where did we chdir()'ed		*/
+    Gmatch gd_matchbuf;		/* array of matches                     */
+    Gmatch gd_matchptr;		/* &matchbuf[matchct]                   */
+    char *gd_colonmod;		/* colon modifiers in qualifier list    */
+
+    /* Qualifiers pertaining to current pattern */
+    struct qual *gd_quals;
+
+    /* Other state values for current pattern */
+    int gd_qualct, gd_qualorct;
+    int gd_range, gd_amc, gd_units;
+    int gd_gf_nullglob, gd_gf_markdirs, gd_gf_noglobdots, gd_gf_listtypes;
+    int gd_gf_numsort;
+    int gd_gf_follow, gd_gf_sorts, gd_gf_nsorts, gd_gf_sortlist[11];
+
+    char *gd_glob_pre, *gd_glob_suf;
+};
+
+/* The variable with the current globbing state and convenience macros */
+
+static struct globdata curglobdata;
+
+#define matchsz       (curglobdata.gd_matchsz)
+#define matchct       (curglobdata.gd_matchct)
+#define pathbufsz     (curglobdata.gd_pathbufsz)
+#define pathbufcwd    (curglobdata.gd_pathbufcwd)
+#define matchbuf      (curglobdata.gd_matchbuf)
+#define matchptr      (curglobdata.gd_matchptr)
+#define colonmod      (curglobdata.gd_colonmod)
+#define quals         (curglobdata.gd_quals)
+#define qualct        (curglobdata.gd_qualct)
+#define qualorct      (curglobdata.gd_qualorct)
+#define g_range       (curglobdata.gd_range)
+#define g_amc         (curglobdata.gd_amc)
+#define g_units       (curglobdata.gd_units)
+#define gf_nullglob   (curglobdata.gd_gf_nullglob)
+#define gf_markdirs   (curglobdata.gd_gf_markdirs)
+#define gf_noglobdots (curglobdata.gd_gf_noglobdots)
+#define gf_listtypes  (curglobdata.gd_gf_listtypes)
+#define gf_numsort    (curglobdata.gd_gf_numsort)
+#define gf_follow     (curglobdata.gd_gf_follow)
+#define gf_sorts      (curglobdata.gd_gf_sorts)
+#define gf_nsorts     (curglobdata.gd_gf_nsorts)
+#define gf_sortlist   (curglobdata.gd_gf_sortlist)
+
+/* and macros for save/restore */
+
+#define save_globstate(N) \
+  do { \
+    memcpy(&(N), &curglobdata, sizeof(struct globdata)); \
+    (N).gd_pathpos = pathpos; \
+    (N).gd_pathbuf = pathbuf; \
+    (N).gd_pathbufsz = 0; \
+    (N).gd_pathbuf = NULL; \
+    (N).gd_glob_pre = glob_pre; \
+    (N).gd_glob_suf = glob_suf; \
+  } while (0)
+
+#define restore_globstate(N) \
+  do { \
+    zfree(pathbuf, pathbufsz); \
+    memcpy(&curglobdata, &(N), sizeof(struct globdata)); \
+    pathpos = (N).gd_pathpos; \
+    pathbuf = (N).gd_pathbuf; \
+    glob_pre = (N).gd_glob_pre; \
+    glob_suf = (N).gd_glob_suf; \
+  } while (0)
 
 /* pathname component in filename patterns */
 
 struct complist {
     Complist next;
-    Comp comp;
+    Patprog pat;
     int closure;		/* 1 if this is a (foo/)# */
     int follow; 		/* 1 to go thru symlinks */
 };
-struct comp {
-    Comp left, right, next, exclude;
-    char *str;
-    int stat;
-};
 
-/* Type of Comp:  a closure with one or two #'s, the end of a *
- * pattern or path component, a piece of path to be added.    */
-#define C_ONEHASH	1
-#define C_TWOHASH	2
-#define C_OPTIONAL	4
-#define C_STAR		8    
-#define C_CLOSURE	(C_ONEHASH|C_TWOHASH|C_OPTIONAL|C_STAR)
-#define C_LAST		16
-#define C_PATHADD	32
-
-/* Test macros for the above */
-#define CLOSUREP(c)	(c->stat & C_CLOSURE)
-#define ONEHASHP(c)	(c->stat & (C_ONEHASH|C_STAR))
-#define TWOHASHP(c)	(c->stat & C_TWOHASH)
-#define OPTIONALP(c)	(c->stat & C_OPTIONAL)
-#define STARP(c)	(c->stat & C_STAR)
-#define LASTP(c)	(c->stat & C_LAST)
-#define PATHADDP(c)	(c->stat & C_PATHADD)
-
-/* Flags passed down to guts when compiling */
-#define GF_PATHADD	1	/* file glob, adding path components */
-#define GF_TOPLEV	2	/* outside (), so ~ ends main match */
-
-static char *pptr;		/* current place in string being matched */
-static Comp tail;
-static int first;		/* are leading dots special? */
+/* 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).
+ */
+#define METAINC(x)	((x) += (*(x) == Meta) ? 2 : 1)
+/*
+ * Return unmetafied char from string (x is any char *)
+ */
+#define UNMETA(x)	(*(x) == Meta ? (x)[1] ^ 32 : *(x))
 
 /* Add a component to pathbuf: This keeps track of how    *
  * far we are into a file name, since each path component *
@@ -160,7 +249,11 @@ statfullpath(const char *s, struct stat *st, int l)
 	  "BUG: statfullpath(): pathname too long");
     strcpy(buf, pathbuf + pathbufcwd);
     strcpy(buf + pathpos - pathbufcwd, s);
-    if (!*s) {
+    if (!*s && *buf) {
+	/*
+	 * Don't add the '.' if the path so far is empty, since
+	 * then we get bogus empty strings inserted as files.
+	 */
 	buf[pathpos - pathbufcwd] = '.';
 	buf[pathpos - pathbufcwd + 1] = '\0';
 	l = 0;
@@ -171,6 +264,11 @@ statfullpath(const char *s, struct stat *st, int l)
     return l ? lstat(buf, st) : stat(buf, st);
 }
 
+/* This may be set by qualifier functions to an array of strings to insert
+ * into the list instead of the original string. */
+
+char **inserts;
+
 /* add a match to the list */
 
 /**/
@@ -181,6 +279,8 @@ insert(char *s, int checked)
     char *news = s;
     int statted = 0;
 
+    inserts = NULL;
+
     if (gf_listtypes || gf_markdirs) {
 	/* Add the type marker to the end of the filename */
 	mode_t mode;
@@ -191,13 +291,13 @@ insert(char *s, int checked)
 	if (gf_follow) {
 	    if (!S_ISLNK(mode) || statfullpath(s, &buf2, 0))
 		memcpy(&buf2, &buf, sizeof(buf));
-	    statted = 2;
+	    statted |= 2;
 	    mode = buf2.st_mode;
 	}
 	if (gf_listtypes || S_ISDIR(mode)) {
 	    int ll = strlen(s);
 
-	    news = (char *)ncalloc(ll + 2);
+	    news = (char *) hcalloc(ll + 2);
 	    strcpy(news, s);
 	    news[ll] = file_type(mode);
 	    news[ll + 1] = '\0';
@@ -209,22 +309,26 @@ insert(char *s, int checked)
 
 	if (!statted && statfullpath(s, &buf, 1))
 	    return;
+
+	news = dyncat(pathbuf, news);
+
+	statted = 1;
 	qo = quals;
 	for (qn = qo; qn && qn->func;) {
-	    range = qn->range;
-	    amc = qn->amc;
-	    units = qn->units;
-	    if ((qn->sense & 2) && statted != 2) {
+	    g_range = qn->range;
+	    g_amc = qn->amc;
+	    g_units = qn->units;
+	    if ((qn->sense & 2) && !(statted & 2)) {
 		/* If (sense & 2), we're following links */
 		if (!S_ISLNK(buf.st_mode) || statfullpath(s, &buf2, 0))
 		    memcpy(&buf2, &buf, sizeof(buf));
-		statted = 2;
+		statted |= 2;
 	    }
 	    bp = (qn->sense & 2) ? &buf2 : &buf;
 	    /* Reject the file if the function returned zero *
 	     * and the sense was positive (sense&1 == 0), or *
 	     * vice versa.                                   */
-	    if ((!((qn->func) (bp, qn->data)) ^ qn->sense) & 1) {
+	    if ((!((qn->func) (news, bp, qn->data, qn->sdata)) ^ qn->sense) & 1) {
 		/* Try next alternative, or return if there are no more */
 		if (!(qo = qo->or))
 		    return;
@@ -233,28 +337,64 @@ insert(char *s, int checked)
 	    }
 	    qn = qn->next;
 	}
-    } else if (!checked && statfullpath(s, NULL, 1))
-	return;
+    } else if (!checked) {
+	if (statfullpath(s, NULL, 1))
+	    return;
+	statted = 1;
+	news = dyncat(pathbuf, news);
+    } else
+	news = dyncat(pathbuf, news);
 
-    news = dyncat(pathbuf, news);
-    if (colonmod) {
-	/* Handle the remainder of the qualifer:  e.g. (:r:s/foo/bar/). */
-	s = colonmod;
-	modify(&news, &s);
-    }
-    *matchptr++ = news;
-    if (++matchct == matchsz) {
-	matchbuf = (char **)realloc((char *)matchbuf,
-				    sizeof(char **) * (matchsz *= 2));
+    while (!inserts || (news = dupstring(*inserts++))) {
+	if (colonmod) {
+	    /* Handle the remainder of the qualifer:  e.g. (:r:s/foo/bar/). */
+	    s = colonmod;
+	    modify(&news, &s);
+	}
+	if (!statted && (gf_sorts & GS_NORMAL)) {
+	    statfullpath(s, &buf, 1);
+	    statted = 1;
+	}
+	if (!(statted & 2) && (gf_sorts & GS_LINKED)) {
+	    if (statted) {
+		if (!S_ISLNK(buf.st_mode) || statfullpath(s, &buf2, 0))
+		    memcpy(&buf2, &buf, sizeof(buf));
+	    } else if (statfullpath(s, &buf2, 0))
+		statfullpath(s, &buf2, 1);
+	    statted |= 2;
+	}
+	matchptr->name = news;
+	if (statted & 1) {
+	    matchptr->size = buf.st_size;
+	    matchptr->atime = buf.st_atime;
+	    matchptr->mtime = buf.st_mtime;
+	    matchptr->ctime = buf.st_ctime;
+	    matchptr->links = buf.st_nlink;
+	}
+	if (statted & 2) {
+	    matchptr->_size = buf2.st_size;
+	    matchptr->_atime = buf2.st_atime;
+	    matchptr->_mtime = buf2.st_mtime;
+	    matchptr->_ctime = buf2.st_ctime;
+	    matchptr->_links = buf2.st_nlink;
+	}
+	matchptr++;
 
-	matchptr = matchbuf + matchct;
+	if (++matchct == matchsz) {
+	    matchbuf = (Gmatch )realloc((char *)matchbuf,
+					sizeof(struct gmatch) * (matchsz *= 2));
+
+	    matchptr = matchbuf + matchct;
+	}
+	if (!inserts)
+	    break;
     }
 }
 
 /* Check to see if str is eligible for filename generation. */
 
 /**/
-int
+mod_export int
 haswilds(char *str)
 {
     /* `[' and `]' are legal even if bad patterns are usually not. */
@@ -294,9 +434,10 @@ haswilds(char *str)
 static void
 scanner(Complist q)
 {
-    Comp c;
+    Patprog p;
     int closure;
     int pbcwdsav = pathbufcwd;
+    int errssofar = errsfound;
     struct dirsav ds;
 
     ds.ino = ds.dev = 0;
@@ -305,16 +446,21 @@ scanner(Complist q)
     if (!q)
 	return;
 
-    if ((closure = q->closure))	/* (foo/)# - match zero or more dirs */
+    if ((closure = q->closure)) {
+	/* (foo/)# - match zero or more dirs */
 	if (q->closure == 2)	/* (foo/)## - match one or more dirs */
 	    q->closure = 1;
 	else
 	    scanner(q->next);
-    c = q->comp;
+    }
+    p = q->pat;
     /* Now the actual matching for the current path section. */
-    if (!(c->next || c->left) && !haswilds(c->str)) {
-	/* It's a straight string to the end of the path section. */
-	int l = strlen(c->str);
+    if (p->flags & PAT_PURES) {
+	/*
+	 * It's a straight string to the end of the path section.
+	 */
+	char *str = (char *)p + p->startoff;
+	int l = p->patmlen;
 
 	if (l + !l + pathpos - pathbufcwd >= PATH_MAX) {
 	    int err;
@@ -334,31 +480,37 @@ scanner(Complist q)
 	    /* Not the last path section. Just add it to the path. */
 	    int oppos = pathpos;
 
-	    if (!errflag && !(q->closure && !strcmp(c->str, "."))) {
-		addpath(c->str);
-		if (!closure || statfullpath("", NULL, 1))
-		    scanner((q->closure) ? q : q->next);
-		pathbuf[pathpos = oppos] = '\0';
+	    if (!errflag) {
+		int add = 1;
+
+		if (q->closure && *pathbuf) {
+		    if (!strcmp(str, "."))
+			add = 0;
+		    else if (!strcmp(str, "..")) {
+			struct stat sc, sr;
+
+			add = (stat("/", &sr) || stat(pathbuf, &sc) ||
+			       sr.st_ino != sc.st_ino ||
+			       sr.st_dev != sc.st_dev);
+		    }
+		}
+		if (add) {
+		    addpath(str);
+		    if (!closure || !statfullpath("", NULL, 1))
+			scanner((q->closure) ? q : q->next);
+		    pathbuf[pathpos = oppos] = '\0';
+		}
 	    }
 	} else
-	    insert(c->str, 0);
+	    insert(str, 0);
     } else {
 	/* Do pattern matching on current path section. */
-	char *fn;
+	char *fn = pathbuf[pathbufcwd] ? unmeta(pathbuf + pathbufcwd) : ".";
 	int dirs = !!q->next;
-	DIR *lock;
+	DIR *lock = opendir(fn);
 	char *subdirs = NULL;
 	int subdirlen = 0;
 
-	fn = pathbuf[pathbufcwd] ? unmeta(pathbuf + pathbufcwd) : ".";
-	if (dirs) {
-	    struct stat st;
-	    stat(fn, &st);
-	    /* a directory with subdirectories has link count greater than 2 */
-	    if (!S_ISDIR(st.st_mode) || st.st_nlink == 2)
-		return;
-	}
-	lock = opendir(fn);
 	if (lock == NULL)
 	    return;
 	while ((fn = zreaddir(lock, 1)) && !errflag) {
@@ -367,7 +519,8 @@ scanner(Complist q)
 		((glob_pre && !strpfx(glob_pre, fn))
 		 || (glob_suf && !strsfx(glob_suf, fn))))
 		continue;
-	    if (domatch(fn, c, gf_noglobdots)) {
+	    errsfound = errssofar;
+	    if (pattry(p, fn)) {
 		/* if this name matchs the pattern... */
 		if (pbcwdsav == pathbufcwd &&
 		    strlen(fn) + pathpos - pathbufcwd >= PATH_MAX) {
@@ -387,7 +540,32 @@ scanner(Complist q)
 		if (dirs) {
 		    int l;
 
-		    /* if not the last component in the path */
+		    /*
+		     * If not the last component in the path:
+		     *
+		     * If we made an approximation in the new path segment,
+		     * then it is possible we made too many errors.  For
+		     * example, (ab)#(cb)# will match the directory abcb
+		     * with one error if allowed to, even though it can
+		     * match with none.  This will stop later parts of the
+		     * path matching, so we need to check by reducing the
+		     * maximum number of errors and seeing if the directory
+		     * still matches.  Luckily, this is not a terribly
+		     * common case, since complex patterns typically occur
+		     * in the last part of the path which is not affected
+		     * by this problem.
+		     */
+		    if (errsfound > errssofar) {
+			forceerrs = errsfound - 1;
+			while (forceerrs >= errssofar) {
+			    errsfound = errssofar;
+			    if (!pattry(p, fn))
+				break;
+			    forceerrs = errsfound - 1;
+			}
+			errsfound = forceerrs + 1;
+			forceerrs = -1;
+		    }
 		    if (closure) {
 			/* if matching multiple directories */
 			struct stat buf;
@@ -404,9 +582,14 @@ scanner(Complist q)
 			    continue;
 		    }
 		    l = strlen(fn) + 1;
-		    subdirs = hrealloc(subdirs, subdirlen, subdirlen + l);
+		    subdirs = hrealloc(subdirs, subdirlen, subdirlen + l
+				       + sizeof(int));
 		    strcpy(subdirs + subdirlen, fn);
 		    subdirlen += l;
+		    /* store the count of errors made so far, too */
+		    memcpy(subdirs + subdirlen, (char *)&errsfound,
+			   sizeof(int));
+		    subdirlen += sizeof(int);
 		} else
 		    /* if the last filename component, just add it */
 		    insert(fn, 1);
@@ -416,8 +599,11 @@ scanner(Complist q)
 	if (subdirs) {
 	    int oppos = pathpos;
 
-	    for (fn = subdirs; fn < subdirs+subdirlen; fn += strlen(fn) + 1) {
+	    for (fn = subdirs; fn < subdirs+subdirlen; ) {
 		addpath(fn);
+		fn += strlen(fn) + 1;
+		memcpy((char *)&errsfound, fn, sizeof(int));
+		fn += sizeof(int);
 		scanner((q->closure) ? q : q->next);  /* scan next level */
 		pathbuf[pathpos = oppos] = '\0';
 	    }
@@ -434,373 +620,72 @@ scanner(Complist q)
     }
 }
 
-/* Parse a series of path components pointed to by pptr */
-
-/* enum used with ksh-like patterns, @(...) etc. */
-
-enum { KF_NONE, KF_AT, KF_QUEST, KF_STAR, KF_PLUS, KF_NOT };
-
-/* parse lowest level pattern */
-
-/**/
-static Comp
-parsecomp(int gflag)
-{
-    int kshfunc;
-    Comp c = (Comp) alloc(sizeof *c), c1, c2;
-    char *cstr, *ls = NULL;
-
-    /* In case of alternatives, code coming up is stored in tail. */
-    c->next = tail;
-    cstr = pptr;
-
-    while (*pptr && (mode || *pptr != '/') && *pptr != Bar &&
-	   (unset(EXTENDEDGLOB) || *pptr != Tilde ||
-	    !pptr[1] || pptr[1] == Outpar || pptr[1] == Bar) &&
-	   *pptr != Outpar) {
-	/* Go through code until we find something separating alternatives,
-	 * or path components if relevant.
-	 */
-	if (*pptr == Hat && isset(EXTENDEDGLOB)) {
-	    /* negate remaining pattern */
-	    Comp stail = tail;
-	    tail = NULL;
-	    c->str = dupstrpfx(cstr, pptr - cstr);
-	    pptr++;
-
-	    c1 = (Comp) alloc(sizeof *c1);
-	    c1->stat |= C_STAR;
-
-	    c2 = (Comp) alloc(sizeof *c2);
-	    if (!(c2->exclude = parsecomp(gflag)))
-		return NULL;
-	    if (!*pptr || *pptr == '/')
-		c2->stat |= C_LAST;
-	    c2->left = c1;
-	    c2->next = stail;
-	    c->next = c2;
-	    tail = stail;
-	    return c;
-	}
-
-	/* Ksh-type globs */
-	kshfunc = KF_NONE;
-	if (isset(KSHGLOB) && *pptr && pptr[1] == Inpar) {
-	    switch (*pptr) {
-	    case '@':		/* just do paren as usual */
-		kshfunc = KF_AT;
-		break;
-
-	    case Quest:
-	    case '?':		/* matched optionally, treat as (...|) */
-		kshfunc = KF_QUEST;
-		break;
-
-	    case Star:
-	    case '*':		/* treat as (...)# */
-		kshfunc = KF_STAR;
-		break;
-
-	    case '+':		/* treat as (...)## */
-		kshfunc = KF_PLUS;
-		break;
-
-	    case '!':		/* treat as (*~...) */
-		kshfunc = KF_NOT;
-		break;
-	    }
-	    if (kshfunc != KF_NONE)
-		pptr++;
-	}
-
-	if (*pptr == Inpar) {
-	    /* Found a group (...) */
-	    char *startp = pptr, *endp;
-	    Comp stail = tail;
-	    int dpnd = 0;
-
-	    /* Need matching close parenthesis */
-	    if (skipparens(Inpar, Outpar, &pptr)) {
-		errflag = 1;
-		return NULL;
-	    }
-	    if (kshfunc == KF_STAR)
-		dpnd = 1;
-	    else if (kshfunc == KF_PLUS)
-		dpnd = 2;
-	    else if (kshfunc == KF_QUEST)
-		dpnd = 3;
-	    if (*pptr == Pound && isset(EXTENDEDGLOB)) {
-		/* Zero (or one) or more repetitions of group */
-		pptr++;
-		if(*pptr == Pound) {
-		    pptr++;
-		    if(dpnd == 0)
-			dpnd = 2;
-		    else if(dpnd == 3)
-			dpnd = 1;
-		} else
-		    dpnd = 1;
-	    }
-	    /* Parse the remaining pattern following the group... */
-	    if (!(c1 = parsecomp(gflag)))
-		return NULL;
-	    /* ...remembering what comes after it... */
-	    tail = (dpnd || kshfunc == KF_NOT) ? NULL : c1;
-	    /* ...before going back and parsing inside the group. */
-	    endp = pptr;
-	    pptr = startp;
-	    c->str = dupstrpfx(cstr, (pptr - cstr) - (kshfunc != KF_NONE));
-	    pptr++;
-	    c2 = (Comp) alloc(sizeof *c);
-	    c->next = c2;
-	    c2->next = (dpnd || kshfunc == KF_NOT) ?
-		c1 : (Comp) alloc(sizeof *c);
-	    if (!(c2->left = parsecompsw(0)))
-		return NULL;
-	    if (kshfunc == KF_NOT) {
-		/* we'd actually rather it didn't match.  Instead, match *
-		 * a star and put the parsed pattern into exclude.       */
-		Comp c3 = (Comp) alloc(sizeof *c3);
-		c3->stat |= C_STAR;
-
-		c2->exclude = c2->left;
-		c2->left = c3;
-	    }
-	    /* Remember closures for group. */
-	    if (dpnd)
-		c2->stat |= (dpnd == 3) ? C_OPTIONAL
-		    : (dpnd == 2) ? C_TWOHASH : C_ONEHASH;
-	    pptr = endp;
-	    tail = stail;
-	    return c;
-	}
-	if (*pptr == Star && pptr[1] &&
-	    (unset(EXTENDEDGLOB) || !(gflag & GF_TOPLEV) ||
-	     pptr[1] != Tilde || !pptr[2] || pptr[2] == Bar ||
-	     pptr[2] == Outpar) && (mode || pptr[1] != '/')) {
-	    /* Star followed by other patterns is now treated as a special
-	     * type of closure in doesmatch().
-	     */
-	    c->str = dupstrpfx(cstr, pptr - cstr);
-	    pptr++;
-	    c1 = (Comp) alloc(sizeof *c1);
-	    c1->stat |= C_STAR;
-	    if (!(c2 = parsecomp(gflag)))
-		return NULL;
-	    c1->next = c2;
-	    c->next = c1;
-	    return c;
-	}
-	if (*pptr == Pound && isset(EXTENDEDGLOB)) {
-	    /* repeat whatever we've just had (ls) zero or more times */
-	    if (!ls)
-		return NULL;
-	    c2 = (Comp) alloc(sizeof *c);
-	    c2->str = dupstrpfx(ls, pptr - ls);
-	    pptr++;
-	    if (*pptr == Pound) {
-		/* need one or more matches: cheat by copying previous char */
-		pptr++;
-		c->next = c1 = (Comp) alloc(sizeof *c);
-		c1->str = c2->str;
-	    } else
-		c1 = c;
-	    c1->next = c2;
-	    c2->stat |= C_ONEHASH;
-	    /* parse the rest of the pattern and return. */
-	    c2->next = parsecomp(gflag);
-	    if (!c2->next)
-		return NULL;
-	    c->str = dupstrpfx(cstr, ls - cstr);
-	    return c;
-	}
-	ls = pptr;		/* whatever we just parsed */
-	if (*pptr == Inang) {
-	    /* Numeric glob */
-	    int dshct;
-
-	    dshct = (pptr[1] == Outang);
-	    while (*++pptr && *pptr != Outang)
-		if (*pptr == '-' && !dshct)
-		    dshct = 1;
-		else if (!idigit(*pptr))
-		    break;
-	    if (*pptr != Outang)
-		return NULL;
-	} else if (*pptr == Inbrack) {
-	    /* Character set: brackets had better match */
-	    if (pptr[1] == Outbrack)
-		*++pptr = ']';
-	    else if ((pptr[1] == Hat || pptr[1] == '^' || pptr[1] == '!') &&
-		     pptr[2] == Outbrack)
-		*(pptr += 2) = ']';
-	    while (*++pptr && *pptr != Outbrack) {
-		if (itok(*pptr)) {
-		    /* POSIX classes: make sure it's a real one, *
-		     * leave the Inbrack tokenised if so.        */
-		    char *nptr;
-		    if (*pptr == Inbrack && pptr[1] == ':'
-			&& (nptr = strchr(pptr+2, ':')) && 
-			*++nptr == Outbrack)
-			pptr = nptr;
-		    *pptr = ztokens[*pptr - Pound];
-		}
-	    }
-	    if (*pptr != Outbrack)
-		return NULL;
-	} else if (itok(*pptr) && *pptr != Star && *pptr != Quest)
-	    /* something that can be tokenised which isn't otherwise special */
-	    *pptr = ztokens[*pptr - Pound];
-	pptr++;
-    }
-    /* mark if last pattern component in path component or pattern */
-    if (*pptr == '/' || !*pptr ||
-	(isset(EXTENDEDGLOB) && *pptr == Tilde && (gflag & GF_TOPLEV)))
-	c->stat |= C_LAST;
-    c->str = dupstrpfx(cstr, pptr - cstr);
-    return c;
-}
-
-/* Parse pattern possibly with different alternatives (|) */
-
-/**/
-static Comp
-parsecompsw(int gflag)
-{
-    Comp c1, c2, c3, excl = NULL, stail = tail;
-    char *sptr;
-
-    /*
-     * Check for a tilde in the expression.  We need to know this in 
-     * advance so as to be able to treat the whole a~b expression by
-     * backtracking:  see exclusion code in doesmatch().
-     */
-    if (isset(EXTENDEDGLOB)) {
-	int pct = 0;
-	for (sptr = pptr; *sptr; sptr++) {
-	    if (*sptr == Inpar)
-		pct++;
-	    else if (*sptr == Outpar && --pct < 0)
-		break;
-	    else if (*sptr == Bar && !pct)
-		break;
-	    else if (*sptr == Tilde && !pct) {
-		tail = NULL;
-		break;
-	    }
-	}
-    }
-
-    c1 = parsecomp(gflag);
-    if (!c1)
-	return NULL;
-    if (isset(EXTENDEDGLOB) && *pptr == Tilde) {
-	/* Matching remainder of pattern excludes the pattern from matching */
-	int oldmode = mode;
-
-	mode = 1;
-	pptr++;
-	excl = parsecomp(gflag);
-	mode = oldmode;
-	if (!excl)
-	    return NULL;
-    }
-    tail = stail;
-    if (*pptr == Bar || excl) {
-	/* found an alternative or something to exclude */
-	c2 = (Comp) alloc(sizeof *c2);
-	if (*pptr == Bar) {
-	    /* get the next alternative after the | */
-	    pptr++;
-	    c3 = parsecompsw(gflag);
-	    if (!c3)
-		return NULL;
-	} else
-	    c3 = NULL;
-	/* mark if end of pattern or path component */
-	if (!*pptr || *pptr == '/')
-	    c1->stat |= c2->stat = C_LAST;
-	c2->str = dupstring("");
-	c2->left = c1;
-	c2->right = c3;
-	if ((c2->exclude = excl))
-	    c2->next = stail;
-	if (gflag & GF_PATHADD)
-	    c2->stat |= C_PATHADD;
-	return c2;
-    }
-    return c1;
-}
-
 /* This function tokenizes a zsh glob pattern */
 
 /**/
 static Complist
-parsecomplist(void)
+parsecomplist(char *instr)
 {
-    Comp c1;
-    Complist p1;
+    Patprog p1;
+    Complist l1;
     char *str;
+    int compflags = gf_noglobdots ? (PAT_FILE|PAT_NOGLD) : PAT_FILE;
 
-    if (pptr[0] == Star && pptr[1] == Star &&
-        (pptr[2] == '/' || (pptr[2] == Star && pptr[3] == '/'))) {
+    if (instr[0] == Star && instr[1] == Star &&
+        (instr[2] == '/' || (instr[2] == Star && instr[3] == '/'))) {
 	/* Match any number of directories. */
 	int follow;
 
 	/* with three stars, follow symbolic links */
-	follow = (pptr[2] == Star);
-	pptr += (3 + follow);
+	follow = (instr[2] == Star);
+	instr += (3 + follow);
 
 	/* Now get the next path component if there is one. */
-	p1 = (Complist) alloc(sizeof *p1);
-	if ((p1->next = parsecomplist()) == NULL) {
+	l1 = (Complist) zhalloc(sizeof *l1);
+	if ((l1->next = parsecomplist(instr)) == NULL) {
 	    errflag = 1;
 	    return NULL;
 	}
-	p1->comp = (Comp) alloc(sizeof *p1->comp);
-	p1->comp->stat |= C_LAST;	/* end of path component  */
-	p1->comp->str = dupstring("*");
-	*p1->comp->str = Star;		/* match anything...      */
-	p1->closure = 1;		/* ...zero or more times. */
-	p1->follow = follow;
-	return p1;
+	l1->pat = patcompile(NULL, compflags | PAT_ANY, NULL);
+	l1->closure = 1;		/* ...zero or more times. */
+	l1->follow = follow;
+	return l1;
     }
 
     /* Parse repeated directories such as (dir/)# and (dir/)## */
-    if (*(str = pptr) == Inpar && !skipparens(Inpar, Outpar, &str) &&
+    if (*(str = instr) == Inpar && !skipparens(Inpar, Outpar, (char **)&str) &&
         *str == Pound && isset(EXTENDEDGLOB) && str[-2] == '/') {
-	pptr++;
-	if (!(c1 = parsecompsw(0)))
+	instr++;
+	if (!(p1 = patcompile(instr, compflags, &instr)))
 	    return NULL;
-	if (pptr[0] == '/' && pptr[1] == Outpar && pptr[2] == Pound) {
+	if (instr[0] == '/' && instr[1] == Outpar && instr[2] == Pound) {
 	    int pdflag = 0;
 
-	    pptr += 3;
-	    if (*pptr == Pound) {
+	    instr += 3;
+	    if (*instr == Pound) {
 		pdflag = 1;
-		pptr++;
+		instr++;
 	    }
-	    p1 = (Complist) alloc(sizeof *p1);
-	    p1->comp = c1;
-	    p1->closure = 1 + pdflag;
-	    p1->follow = 0;
-	    p1->next = parsecomplist();
-	    return (p1->comp) ? p1 : NULL;
+	    l1 = (Complist) zhalloc(sizeof *l1);
+	    l1->pat = p1;
+	    l1->closure = 1 + pdflag;
+	    l1->follow = 0;
+	    l1->next = parsecomplist(instr);
+	    return (l1->pat) ? l1 : NULL;
 	}
     } else {
 	/* parse single path component */
-	if (!(c1 = parsecompsw(GF_PATHADD|GF_TOPLEV)))
+	if (!(p1 = patcompile(instr, compflags|PAT_FILET, &instr)))
 	    return NULL;
 	/* then do the remaining path compoents */
-	if (*pptr == '/' || !*pptr) {
-	    int ef = *pptr == '/';
-
-	    p1 = (Complist) alloc(sizeof *p1);
-	    p1->comp = c1;
-	    p1->closure = 0;
-	    p1->next = ef ? (pptr++, parsecomplist()) : NULL;
-	    return (ef && !p1->next) ? NULL : p1;
+	if (*instr == '/' || !*instr) {
+	    int ef = *instr == '/';
+
+	    l1 = (Complist) zhalloc(sizeof *l1);
+	    l1->pat = p1;
+	    l1->closure = 0;
+	    l1->next = ef ? parsecomplist(instr+1) : NULL;
+	    return (ef && !l1->next) ? NULL : l1;
 	}
     }
     errflag = 1;
@@ -813,19 +698,40 @@ parsecomplist(void)
 static Complist
 parsepat(char *str)
 {
-    mode = 0;			/* path components present */
-    pptr = str;
-    tail = NULL;
-    return parsecomplist();
+    patcompstart();
+    /*
+     * Check for initial globbing flags, so that they don't form
+     * a bogus path component.
+     */
+    if ((*str == Inpar && str[1] == Pound && isset(EXTENDEDGLOB)) ||
+	(isset(KSHGLOB) && *str == '@' && str[1] == Inpar &&
+	 str[2] == Pound)) {
+	str += (*str == Inpar) ? 2 : 3;
+	if (!patgetglobflags(&str))
+	    return NULL;
+    }
+
+    /* Now there is no (#X) in front, we can check the path. */
+    if (!pathbuf)
+	pathbuf = zalloc(pathbufsz = PATH_MAX);
+    DPUTS(pathbufcwd, "BUG: glob changed directory");
+    if (*str == '/') {		/* pattern has absolute path */
+	str++;
+	pathbuf[0] = '/';
+	pathbuf[pathpos = 1] = '\0';
+    } else			/* pattern is relative to pwd */
+	pathbuf[pathpos = 0] = '\0';
+
+    return parsecomplist(str);
 }
 
 /* get number after qualifier */
 
 /**/
-static long
+static off_t
 qgetnum(char **s)
 {
-    long v = 0;
+    off_t v = 0;
 
     if (!idigit(**s)) {
 	zerr("number expected", NULL, 0);
@@ -836,21 +742,166 @@ qgetnum(char **s)
     return v;
 }
 
-/* get octal number after qualifier */
+/* get mode spec after qualifier */
 
 /**/
-static long
-qgetoctnum(char **s)
+static zlong
+qgetmodespec(char **s)
 {
-    long v = 0;
+    zlong yes = 0, no = 0, val, mask, t;
+    char *p = *s, c, how, end;
 
-    if (!idigit(**s)) {
-	zerr("octal number expected", NULL, 0);
-	return 0;
+    if ((c = *p) == '=' || c == Equals || c == '+' || c == '-' ||
+	c == '?' || c == Quest || (c >= '0' && c <= '7')) {
+	end = 0;
+	c = 0;
+    } else {
+	end = (c == '<' ? '>' :
+	       (c == '[' ? ']' :
+		(c == '{' ? '}' :
+		 (c == Inang ? Outang :
+		  (c == Inbrack ? Outbrack :
+		   (c == Inbrace ? Outbrace : c))))));
+	p++;
     }
-    while (**s >= '0' && **s <= '7')
-	v = v * 010 + *(*s)++ - '0';
-    return v;
+    do {
+	mask = 0;
+	while (((c = *p) == 'u' || c == 'g' || c == 'o' || c == 'a') && end) {
+	    switch (c) {
+	    case 'o': mask |= 01007; break;
+	    case 'g': mask |= 02070; break;
+	    case 'u': mask |= 04700; break;
+	    case 'a': mask |= 07777; break;
+	    }
+	    p++;
+	}
+	how = ((c == '+' || c == '-') ? c : '=');
+	if (c == '+' || c == '-' || c == '=' || c == Equals)
+	    p++;
+	val = 0;
+	if (mask) {
+	    while ((c = *p++) != ',' && c != end) {
+		switch (c) {
+		case 'x': val |= 00111; break;
+		case 'w': val |= 00222; break;
+		case 'r': val |= 00444; break;
+		case 's': val |= 06000; break;
+		case 't': val |= 01000; break;
+		case '0': case '1': case '2': case '3':
+		case '4': case '5': case '6': case '7':
+		    t = ((zlong) c - '0');
+		    val |= t | (t << 3) | (t << 6);
+		    break;
+		default:
+		    zerr("invalid mode specification", NULL, 0);
+		    return 0;
+		}
+	    }
+	    if (how == '=' || how == '+') {
+		yes |= val & mask;
+		val = ~val;
+	    }
+	    if (how == '=' || how == '-')
+		no |= val & mask;
+	} else {
+	    t = 07777;
+	    while ((c = *p) == '?' || c == Quest ||
+		   (c >= '0' && c <= '7')) {
+		if (c == '?' || c == Quest) {
+		    t = (t << 3) | 7;
+		    val <<= 3;
+		} else {
+		    t <<= 3;
+		    val = (val << 3) | ((zlong) c - '0');
+		}
+		p++;
+	    }
+	    if (end && c != end && c != ',') {
+		zerr("invalid mode specification", NULL, 0);
+		return 0;
+	    }
+	    if (how == '=') {
+		yes = (yes & ~t) | val;
+		no = (no & ~t) | (~val & ~t);
+	    } else if (how == '+')
+		yes |= val;
+	    else
+		no |= val;
+	}
+    } while (end && c != end);
+
+    *s = p;
+    return ((yes & 07777) | ((no & 07777) << 12));
+}
+
+static int
+gmatchcmp(Gmatch a, Gmatch b)
+{
+    int i, *s;
+    off_t r = 0L;
+
+    for (i = gf_nsorts, s = gf_sortlist; i; i--, s++) {
+	switch (*s & ~GS_DESC) {
+	case GS_NAME:
+	    r = notstrcmp(&a->name, &b->name);
+	    break;
+	case GS_DEPTH:
+	    {
+		char *aptr = a->name, *bptr = b->name;
+		int slasha = 0, slashb = 0;
+		/* Count slashes.  Trailing slashes don't count. */
+		while (*aptr && *aptr == *bptr)
+		    aptr++, bptr++;
+		if (*aptr)
+		    for (; aptr[1]; aptr++)
+			if (*aptr == '/') {
+			    slasha = 1;
+			    break;
+			}
+		if (*bptr)
+		    for (; bptr[1]; bptr++)
+			if (*bptr == '/') {
+			    slashb = 1;
+			    break;
+			}
+		r = slasha - slashb;
+	    }
+	    break;
+	case GS_SIZE:
+	    r = b->size - a->size;
+	    break;
+	case GS_ATIME:
+	    r = a->atime - b->atime;
+	    break;
+	case GS_MTIME:
+	    r = a->mtime - b->mtime;
+	    break;
+	case GS_CTIME:
+	    r = a->ctime - b->ctime;
+	    break;
+	case GS_LINKS:
+	    r = b->links - a->links;
+	    break;
+	case GS__SIZE:
+	    r = b->_size - a->_size;
+	    break;
+	case GS__ATIME:
+	    r = a->_atime - b->_atime;
+	    break;
+	case GS__MTIME:
+	    r = a->_mtime - b->_mtime;
+	    break;
+	case GS__CTIME:
+	    r = a->_ctime - b->_ctime;
+	    break;
+	case GS__LINKS:
+	    r = b->_links - a->_links;
+	    break;
+	}
+	if (r)
+	    return (int) ((*s & GS_DESC) ? -r : r);
+    }
+    return 0;
 }
 
 /* Main entry point to the globbing code for filename globbing. *
@@ -859,7 +910,7 @@ qgetoctnum(char **s)
 
 /**/
 void
-glob(LinkList list, LinkNode np)
+glob(LinkList list, LinkNode np, int nountok)
 {
     struct qual *qo, *qn, *ql;
     LinkNode node = prevnode(np);
@@ -868,12 +919,17 @@ glob(LinkList list, LinkNode np)
     Complist q;				/* pattern after parsing         */
     char *ostr = (char *)getdata(np);	/* the pattern before the parser */
 					/* chops it up                   */
+    int first = 0, last = -1;		/* index of first/last match to  */
+				        /* return */
+    struct globdata saved;		/* saved glob state              */
 
-    MUSTUSEHEAP("glob");
     if (unset(GLOBOPT) || !haswilds(ostr)) {
-	untokenize(ostr);
+	if (!nountok)
+	    untokenize(ostr);
 	return;
     }
+    save_globstate(saved);
+
     str = dupstring(ostr);
     sl = strlen(str);
     uremnode(list, np);
@@ -886,6 +942,8 @@ glob(LinkList list, LinkNode np)
     gf_markdirs = isset(MARKDIRS);
     gf_listtypes = gf_follow = 0;
     gf_noglobdots = unset(GLOBDOTS);
+    gf_numsort = isset(NUMERICGLOBSORT);
+    gf_sorts = gf_nsorts = 0;
 
     /* Check for qualifiers */
     if (isset(BAREGLOBQUAL) && str[sl - 1] == Outpar) {
@@ -897,21 +955,23 @@ glob(LinkList list, LinkNode np)
 	    if (*s == Bar || *s == Outpar ||
 		(isset(EXTENDEDGLOB) && *s == Tilde))
 		break;
-	if (*s == Inpar) {
+	if (*s == Inpar && (!isset(EXTENDEDGLOB) || s[1] != Pound)) {
 	    /* Real qualifiers found. */
-	    int sense = 0;	/* bit 0 for match (0)/don't match (1)   */
-				/* bit 1 for follow links (2), don't (0) */
-	    long data = 0;	/* Any numerical argument required       */
-	    int (*func) _((Statptr, long));
+	    int sense = 0;	   /* bit 0 for match (0)/don't match (1)   */
+				   /* bit 1 for follow links (2), don't (0) */
+	    off_t data = 0;	   /* Any numerical argument required       */
+	    char *sdata = NULL; /* Any list argument required            */
+	    int (*func) _((char *, Statptr, off_t, char *));
 
 	    str[sl-1] = 0;
 	    *s++ = 0;
 	    while (*s && !colonmod) {
-		func = (int (*) _((Statptr, long)))0;
+		func = (int (*) _((char *, Statptr, off_t, char *)))0;
 		if (idigit(*s)) {
 		    /* Store numeric argument for qualifier */
 		    func = qualflags;
 		    data = 0;
+		    sdata = NULL;
 		    while (idigit(*s))
 			data = data * 010 + (*s++ - '0');
 		} else if (*s == ',') {
@@ -1044,7 +1104,7 @@ glob(LinkList list, LinkNode np)
 		    case 'l':
 			/* Match files with the given no. of hard links */
 			func = qualnlink;
-			amc = -1;
+			g_amc = -1;
 			goto getrange;
 		    case 'U':
 			/* Match files owned by effective user ID */
@@ -1137,11 +1197,10 @@ glob(LinkList list, LinkNode np)
 			    }
 			}
 			break;
-		    case 'o':
-			/* Match octal mode of file exactly. *
-			 * Currently undocumented.           */
-			func = qualeqflags;
-			data = qgetoctnum(&s);
+		    case 'f':
+			/* Match modes with chmod-spec. */
+			func = qualmodeflags;
+			data = qgetmodespec(&s);
 			break;
 		    case 'M':
 			/* Mark directories with a / */
@@ -1161,54 +1220,132 @@ glob(LinkList list, LinkNode np)
 			/* Glob dots: match leading dots implicitly */
 			gf_noglobdots = sense & 1;
 			break;
+		    case 'n':
+			/* Numeric glob sort */
+			gf_numsort = !(sense & 1);
+			break;
 		    case 'a':
 			/* Access time in given range */
-			amc = 0;
+			g_amc = 0;
 			func = qualtime;
 			goto getrange;
 		    case 'm':
 			/* Modification time in given range */
-			amc = 1;
+			g_amc = 1;
 			func = qualtime;
 			goto getrange;
 		    case 'c':
 			/* Inode creation time in given range */
-			amc = 2;
+			g_amc = 2;
 			func = qualtime;
 			goto getrange;
 		    case 'L':
 			/* File size (Length) in given range */
 			func = qualsize;
-			amc = -1;
+			g_amc = -1;
 			/* Get size multiplier */
-			units = TT_BYTES;
+			g_units = TT_BYTES;
 			if (*s == 'p' || *s == 'P')
-			    units = TT_POSIX_BLOCKS, ++s;
+			    g_units = TT_POSIX_BLOCKS, ++s;
 			else if (*s == 'k' || *s == 'K')
-			    units = TT_KILOBYTES, ++s;
+			    g_units = TT_KILOBYTES, ++s;
 			else if (*s == 'm' || *s == 'M')
-			    units = TT_MEGABYTES, ++s;
+			    g_units = TT_MEGABYTES, ++s;
 		      getrange:
 			/* Get time multiplier */
-			if (amc >= 0) {
-			    units = TT_DAYS;
+			if (g_amc >= 0) {
+			    g_units = TT_DAYS;
 			    if (*s == 'h')
-				units = TT_HOURS, ++s;
+				g_units = TT_HOURS, ++s;
 			    else if (*s == 'm')
-				units = TT_MINS, ++s;
+				g_units = TT_MINS, ++s;
 			    else if (*s == 'w')
-				units = TT_WEEKS, ++s;
+				g_units = TT_WEEKS, ++s;
 			    else if (*s == 'M')
-				units = TT_MONTHS, ++s;
+				g_units = TT_MONTHS, ++s;
+			    else if (*s == 's')
+				g_units = TT_SECONDS, ++s;
 			}
 			/* See if it's greater than, equal to, or less than */
-			if ((range = *s == '+' ? 1 : *s == '-' ? -1 : 0))
+			if ((g_range = *s == '+' ? 1 : *s == '-' ? -1 : 0))
 			    ++s;
 			data = qgetnum(&s);
 			break;
 
+		    case 'o':
+		    case 'O':
+			{
+			    int t;
+
+			    switch (*s) {
+			    case 'n': t = GS_NAME; break;
+			    case 'L': t = GS_SIZE; break;
+			    case 'l': t = GS_LINKS; break;
+			    case 'a': t = GS_ATIME; break;
+			    case 'm': t = GS_MTIME; break;
+			    case 'c': t = GS_CTIME; break;
+			    case 'd': t = GS_DEPTH; break;
+			    default:
+				zerr("unknown sort specifier", NULL, 0);
+				restore_globstate(saved);
+				return;
+			    }
+			    if ((sense & 2) && !(t & (GS_NAME|GS_DEPTH)))
+				t <<= GS_SHIFT;
+			    if (gf_sorts & t) {
+				zerr("doubled sort specifier", NULL, 0);
+				restore_globstate(saved);
+				return;
+			    }
+			    gf_sorts |= t;
+			    gf_sortlist[gf_nsorts++] = t |
+				(((sense & 1) ^ (s[-1] == 'O')) ? GS_DESC : 0);
+			    s++;
+			    break;
+			}
+		    case 'e':
+			{
+			    char sav, *tt = get_strarg(s);
+
+			    if (!*tt) {
+				zerr("missing end of string", NULL, 0);
+				data = 0;
+			    } else {
+				sav = *tt;
+				*tt = '\0';
+				func = qualsheval;
+				sdata = dupstring(s + 1);
+				untokenize(sdata);
+				*tt = sav;
+				if (sav)
+				    s = tt + 1;
+				else
+				    s = tt;
+			    }
+			    break;
+			}
+		    case '[':
+		    case Inbrack:
+			{
+			    char *os = --s;
+			    struct value v;
+
+			    v.isarr = SCANPM_WANTVALS;
+			    v.pm = NULL;
+			    v.b = -1;
+			    v.inv = 0;
+			    if (getindex(&s, &v) || s == os) {
+				zerr("invalid subscript", NULL, 0);
+				restore_globstate(saved);
+				return;
+			    }
+			    first = v.a;
+			    last = v.b;
+			    break;
+			}
 		    default:
 			zerr("unknown file attribute", NULL, 0);
+			restore_globstate(saved);
 			return;
 		    }
 		if (func) {
@@ -1223,30 +1360,26 @@ glob(LinkList list, LinkNode np)
 		    qn->func = func;
 		    qn->sense = sense;
 		    qn->data = data;
-		    qn->range = range;
-		    qn->units = units;
-		    qn->amc = amc;
+		    qn->sdata = sdata;
+		    qn->range = g_range;
+		    qn->units = g_units;
+		    qn->amc = g_amc;
 		    qn = NULL;
 		    qualct++;
 		}
-		if (errflag)
+		if (errflag) {
+		    restore_globstate(saved);
 		    return;
+		}
 	    }
 	}
     }
-    if (!pathbuf)
-	pathbuf = zalloc(pathbufsz = PATH_MAX);
-    DPUTS(pathbufcwd, "BUG: glob changed directory");
-    if (*str == '/') {		/* pattern has absolute path */
-	str++;
-	pathbuf[0] = '/';
-	pathbuf[pathpos = 1] = '\0';
-    } else			/* pattern is relative to pwd */
-	pathbuf[pathpos = 0] = '\0';
     q = parsepat(str);
     if (!q || errflag) {	/* if parsing failed */
+	restore_globstate(saved);
 	if (unset(BADPATTERN)) {
-	    untokenize(ostr);
+	    if (!nountok)
+		untokenize(ostr);
 	    insertlinknode(list, node, ostr);
 	    return;
 	}
@@ -1254,11 +1387,16 @@ glob(LinkList list, LinkNode np)
 	zerr("bad pattern: %s", ostr, 0);
 	return;
     }
-
+    if (!gf_nsorts) {
+	gf_sortlist[0] = gf_sorts = GS_NAME;
+	gf_nsorts = 1;
+    }
     /* Initialise receptacle for matched files, *
      * expanded by insert() where necessary.    */
-    matchptr = matchbuf = (char **)zalloc((matchsz = 16) * sizeof(char *));
+    matchptr = matchbuf = (Gmatch)zalloc((matchsz = 16) *
+					 sizeof(struct gmatch));
     matchct = 0;
+    pattrystart();
 
     /* The actual processing takes place here: matches go into  *
      * matchbuf.  This is the only top-level call to scanner(). */
@@ -1267,7 +1405,7 @@ glob(LinkList list, LinkNode np)
     /* Deal with failures to match depending on options */
     if (matchct)
 	badcshglob |= 2;	/* at least one cmd. line expansion O.K. */
-    else if (!gf_nullglob)
+    else if (!gf_nullglob) {
 	if (isset(CSHNULLGLOB)) {
 	    badcshglob |= 1;	/* at least one cmd. line expansion failed */
 	} else if (isset(NOMATCH)) {
@@ -1276,18 +1414,35 @@ glob(LinkList list, LinkNode np)
 	    return;
 	} else {
 	    /* treat as an ordinary string */
-	    untokenize(*matchptr++ = dupstring(ostr));
+	    untokenize(matchptr->name = dupstring(ostr));
+	    matchptr++;
 	    matchct = 1;
 	}
+    }
     /* Sort arguments in to lexical (and possibly numeric) order. *
      * This is reversed to facilitate insertion into the list.    */
-    qsort((void *) & matchbuf[0], matchct, sizeof(char *),
-	       (int (*) _((const void *, const void *)))notstrcmp);
-
-    matchptr = matchbuf;
-    while (matchct--)		/* insert matches in the arg list */
-	insertlinknode(list, node, *matchptr++);
+    qsort((void *) & matchbuf[0], matchct, sizeof(struct gmatch),
+	       (int (*) _((const void *, const void *)))gmatchcmp);
+
+    if (first < 0)
+	first += matchct;
+    if (last < 0)
+	last += matchct;
+    if (first < 0)
+	first = 0;
+    if (last >= matchct)
+	last = matchct - 1;
+    if (first <= last) {
+	matchptr = matchbuf + matchct - 1 - last;
+	last -= first;
+	while (last-- >= 0) {		/* insert matches in the arg list */
+	    insertlinknode(list, node, matchptr->name);
+	    matchptr++;
+	}
+    }
     free(matchbuf);
+
+    restore_globstate(saved);
 }
 
 /* Return the order of two strings, taking into account *
@@ -1308,7 +1463,7 @@ notstrcmp(char **a, char **b)
 #ifndef HAVE_STRCOLL
     cmp = (int)STOUC(*c) - (int)STOUC(*d);
 #endif
-    if (isset(NUMERICGLOBSORT) && (idigit(*c) || idigit(*d))) {
+    if (gf_numsort && (idigit(*c) || idigit(*d))) {
 	for (; c > *b && idigit(c[-1]); c--, d--);
 	if (idigit(*c) && idigit(*d)) {
 	    while (*c == '0')
@@ -1333,7 +1488,7 @@ notstrcmp(char **a, char **b)
 /* Return the trailing character for marking file types */
 
 /**/
-char
+mod_export char
 file_type(mode_t filemode)
 {
     if(S_ISBLK(filemode))
@@ -1365,19 +1520,20 @@ hasbraces(char *str)
     if (isset(BRACECCL)) {
 	/* In this case, any properly formed brace expression  *
 	 * will match and expand to the characters in between. */
-	int bc;
+	int bc, c;
 
-	for (bc = 0; *str; ++str)
-	    if (*str == Inbrace) {
+	for (bc = 0; (c = *str); ++str)
+	    if (c == Inbrace) {
 		if (!bc && str[1] == Outbrace)
 		    *str++ = '{', *str = '}';
 		else
 		    bc++;
-	    } else if (*str == Outbrace)
+	    } else if (c == Outbrace) {
 		if (!bc)
 		    *str = '}';
 		else if (!--bc)
 		    return 1;
+	    }
 	return 0;
     }
     /* Otherwise we need to look for... */
@@ -1450,31 +1606,30 @@ hasbraces(char *str)
 int
 xpandredir(struct redir *fn, LinkList tab)
 {
-    LinkList fake;
     char *nam;
     struct redir *ff;
     int ret = 0;
+    local_list1(fake);
 
     /* Stick the name in a list... */
-    fake = newlinklist();
-    addlinknode(fake, fn->name);
+    init_list1(fake, fn->name);
     /* ...which undergoes all the usual shell expansions */
-    prefork(fake, isset(MULTIOS) ? 0 : 4);
+    prefork(&fake, isset(MULTIOS) ? 0 : PF_SINGLE);
     /* Globbing is only done for multios. */
     if (!errflag && isset(MULTIOS))
-	globlist(fake);
+	globlist(&fake, 0);
     if (errflag)
 	return 0;
-    if (nonempty(fake) && !nextnode(firstnode(fake))) {
+    if (nonempty(&fake) && !nextnode(firstnode(&fake))) {
 	/* Just one match, the usual case. */
-	char *s = peekfirst(fake);
+	char *s = peekfirst(&fake);
 	fn->name = s;
 	untokenize(s);
 	if (fn->type == MERGEIN || fn->type == MERGEOUT) {
 	    if (s[0] == '-' && !s[1])
 		fn->type = CLOSE;
 	    else if (s[0] == 'p' && !s[1]) 
-		fn->fd2 = (fn->type == MERGEOUT) ? coprocout : coprocin;
+		fn->fd2 = -2;
 	    else {
 		while (idigit(*s))
 		    s++;
@@ -1491,10 +1646,10 @@ xpandredir(struct redir *fn, LinkList tab)
     else {
 	if (fn->type == MERGEOUT)
 	    fn->type = ERRWRITE;
-	while ((nam = (char *)ugetnode(fake))) {
+	while ((nam = (char *)ugetnode(&fake))) {
 	    /* Loop over matches, duplicating the *
 	     * redirection for each file found.   */
-	    ff = (struct redir *)alloc(sizeof *ff);
+	    ff = (struct redir *) zhalloc(sizeof *ff);
 	    *ff = *fn;
 	    ff->name = nam;
 	    addlinknode(tab, ff);
@@ -1507,14 +1662,14 @@ xpandredir(struct redir *fn, LinkList tab)
 /* concatenate s1 and s2 in dynamically allocated buffer */
 
 /**/
-char *
+mod_export char *
 dyncat(char *s1, char *s2)
 {
     /* This version always uses space from the current heap. */
     char *ptr;
     int l1 = strlen(s1);
 
-    ptr = (char *)ncalloc(l1 + strlen(s2) + 1);
+    ptr = (char *)zhalloc(l1 + strlen(s2) + 1);
     strcpy(ptr, s1);
     strcpy(ptr + l1, s2);
     return ptr;
@@ -1523,7 +1678,7 @@ dyncat(char *s1, char *s2)
 /* concatenate s1, s2, and s3 in dynamically allocated buffer */
 
 /**/
-char *
+mod_export char *
 tricat(char const *s1, char const *s2, char const *s3)
 {
     /* This version always uses permanently-allocated space. */
@@ -1554,11 +1709,12 @@ xpandbraces(LinkList list, LinkNode *np)
 	else if (*str2 == Outbrace) {
 	    if (--bc == 0)
 		break;
-	} else if (bc == 1)
+	} else if (bc == 1) {
 	    if (*str2 == Comma)
 		++comma;	/* we have {foo,bar} */
 	    else if (*str2 == '.' && str2[1] == '.')
 		dotdot++;	/* we have {num1..num2} */
+	}
     DPUTS(bc, "BUG: unmatched brace in xpandbraces()");
     if (!comma && dotdot) {
 	/* Expand range like 0..10 numerically: comma or recursive
@@ -1637,12 +1793,12 @@ xpandbraces(LinkList list, LinkNode *np)
 	    if (*p) {
 		c1 = p - ccl;
 		if (imeta(c1)) {
-		    str = ncalloc(len + 1);
+		    str = hcalloc(len + 1);
 		    str[pl] = Meta;
 		    str[pl+1] = c1 ^ 32;
 		    strcpy(str + pl + 2, str2);
 		} else {
-		    str = ncalloc(len);
+		    str = hcalloc(len);
 		    str[pl] = c1;
 		    strcpy(str + pl + 1, str2);
 		}
@@ -1673,7 +1829,7 @@ xpandbraces(LinkList list, LinkNode *np)
 	}
 	/* Concatenate the string before the braces (str3), the section *
 	 * just found (str4) and the text after the braces (str2)       */
-	zz = (char *)ncalloc(prev + (str - str4) + strlen(str2) + 1);
+	zz = (char *) hcalloc(prev + (str - str4) + strlen(str2) + 1);
 	ztrncpy(zz, str3, prev);
 	strncat(zz, str4, str - str4);
 	strcat(zz, str2);
@@ -1694,53 +1850,81 @@ xpandbraces(LinkList list, LinkNode *np)
 int
 matchpat(char *a, char *b)
 {
-    Comp c = parsereg(b);
+    Patprog p = patcompile(b, PAT_STATIC, NULL);
 
-    if (!c) {
+    if (!p) {
 	zerr("bad pattern: %s", b, 0);
 	return 0;
     }
-    return domatch(a, c, 0);
+    return pattry(p, a);
 }
 
 /* do the ${foo%%bar}, ${foo#bar} stuff */
 /* please do not laugh at this code. */
 
+struct repldata {
+    int b, e;			/* beginning and end of chunk to replace */
+    char *replstr;		/* replacement string to use */
+};
+typedef struct repldata *Repldata;
+
+/* 
+ * List of bits of matches to concatenate with replacement string.
+ * The data is a struct repldata.  It is not used in cases like
+ * ${...//#foo/bar} even though SUB_GLOBAL is set, since the match
+ * is anchored.  It goes on the heap.
+ */
+
+static LinkList repllist;
+
 /* Having found a match in getmatch, decide what part of string
  * to return.  The matched part starts b characters into string s
  * and finishes e characters in: 0 <= b <= e <= strlen(s)
  * (yes, empty matches should work).
- * Bits 3 and higher in fl are used: the flags are
- *   8:		Result is matched portion.
- *  16:		Result is unmatched portion.
- *		(N.B. this should be set for standard ${foo#bar} etc. matches.)
- *  32:		Result is numeric position of start of matched portion.
- *  64:		Result is numeric position of end of matched portion.
- * 128:		Result is length of matched portion.
+ * fl is a set of the SUB_* matches defined in zsh.h from SUB_MATCH onwards;
+ * the lower parts are ignored.
+ * replstr is the replacement string for a substitution
  */
 
 /**/
 static char *
-get_match_ret(char *s, int b, int e, int fl)
+get_match_ret(char *s, int b, int e, int fl, char *replstr)
 {
     char buf[80], *r, *p, *rr;
     int ll = 0, l = strlen(s), bl = 0, t = 0, i;
 
-    if (fl & 8)			/* matched portion */
+    if (replstr) {
+	if (fl & SUB_DOSUBST) {
+	    replstr = dupstring(replstr);
+	    singsub(&replstr);
+	    untokenize(replstr);
+	}
+	if ((fl & SUB_GLOBAL) && repllist) {
+	    /* We are replacing the chunk, just add this to the list */
+	    Repldata rd = (Repldata) zhalloc(sizeof(*rd));
+	    rd->b = b;
+	    rd->e = e;
+	    rd->replstr = replstr;
+	    addlinknode(repllist, rd);
+	    return s;
+	}
+	ll += strlen(replstr);
+    }
+    if (fl & SUB_MATCH)			/* matched portion */
 	ll += 1 + (e - b);
-    if (fl & 16)		/* unmatched portion */
+    if (fl & SUB_REST)		/* unmatched portion */
 	ll += 1 + (l - (e - b));
-    if (fl & 32) {
+    if (fl & SUB_BIND) {
 	/* position of start of matched portion */
 	sprintf(buf, "%d ", b + 1);
 	ll += (bl = strlen(buf));
     }
-    if (fl & 64) {
+    if (fl & SUB_EIND) {
 	/* position of end of matched portion */
 	sprintf(buf + bl, "%d ", e + 1);
 	ll += (bl = strlen(buf));
     }
-    if (fl & 128) {
+    if (fl & SUB_LEN) {
 	/* length of matched portion */
 	sprintf(buf + bl, "%d ", e - b);
 	ll += (bl = strlen(buf));
@@ -1748,15 +1932,15 @@ get_match_ret(char *s, int b, int e, int fl)
     if (bl)
 	buf[bl - 1] = '\0';
 
-    rr = r = (char *)ncalloc(ll);
+    rr = r = (char *) hcalloc(ll);
 
-    if (fl & 8) {
+    if (fl & SUB_MATCH) {
 	/* copy matched portion to new buffer */
 	for (i = b, p = s + b; i < e; i++)
 	    *rr++ = *p++;
 	t = 1;
     }
-    if (fl & 16) {
+    if (fl & SUB_REST) {
 	/* Copy unmatched portion to buffer.  If both portions *
 	 * requested, put a space in between (why?)            */
 	if (t)
@@ -1764,6 +1948,9 @@ get_match_ret(char *s, int b, int e, int fl)
 	/* there may be unmatched bits at both beginning and end of string */
 	for (i = 0, p = s; i < b; i++)
 	    *rr++ = *p++;
+	if (replstr)
+	    for (p = replstr; *p; )
+		*rr++ = *p++;
 	for (i = e, p = s + e; i < l; i++)
 	    *rr++ = *p++;
 	t = 1;
@@ -1779,744 +1966,341 @@ get_match_ret(char *s, int b, int e, int fl)
     return r;
 }
 
-/* It is called from paramsubst to get the match for ${foo#bar} etc.
- * Bits of fl determines the required action:
- *   bit 0: match the end instead of the beginning (% or %%)
- *   bit 1: % or # was doubled so get the longest match
- *   bit 2: substring match
- *   bit 3: include the matched portion
- *   bit 4: include the unmatched portion
- *   bit 5: the index of the beginning
- *   bit 6: the index of the end
- *   bit 7: the length of the match
- *   bit 8: match the complete string
- * *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.
- */
-
-/**/
-int
-getmatch(char **sp, char *pat, int fl, int n)
+static Patprog
+compgetmatch(char *pat, int *flp, char **replstrp)
 {
-    Comp c;
-    char *s = *sp, *t, sav;
-    int i, j, l = strlen(*sp);
-
-    c = parsereg(pat);
-    if (!c) {
-	zerr("bad pattern: %s", pat, 0);
-	return 1;
-    }
-    if (fl & 256) {
-	i = domatch(s, c, 0);
-	*sp = get_match_ret(*sp, 0, domatch(s, c, 0) ? l : 0, fl);
-	if (! **sp && (((fl & 8) && !i) || ((fl & 16) && i)))
-	    return 0;
-	return 1;
-    }
-    switch (fl & 7) {
-    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);
-		return 1;
-	    }
-	    if ((*t = sav) == Meta)
-		i++, t++;
-	}
-	break;
-
-    case 1:
-	/* 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);
-		return 1;
-	    }
-	    if (t > s+1 && t[-2] == Meta)
-		t--;
-	}
-	break;
-
-    case 2:
-	/* 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);
-		return 1;
-	    }
-	    *t = sav;
-	    if (t >= s+2 && t[-2] == Meta)
-		t--;
-	}
-	break;
+    Patprog p;
+    /*
+     * Flags to pattern compiler:  use static buffer since we only
+     * have one pattern at a time; we will try the must-match test ourselves,
+     * so tell the pattern compiler we are scanning.
+     */
 
-    case 3:
-	/* 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);
-		return 1;
-	    }
-	    if (*t == Meta)
-		i++, t++;
-	}
-	break;
+    /* int patflags = PAT_STATIC|PAT_SCAN|PAT_NOANCH;*/
 
-    case 4:
-	/* Smallest at start, but matching substrings. */
-	if (domatch(s + l, c, 0) && !--n) {
-	    *sp = get_match_ret(*sp, 0, 0, fl);
-	    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);
-		    return 1;
-		}
-		if ((s[j] = sav) == Meta)
-		    j++;
-		if (*t == Meta)
-		    t++;
-	    }
-	    if (s[i] == Meta)
-		i++;
-	}
-	break;
+    /* Unfortunately, PAT_STATIC doesn't work if we have a replstr with
+     * something like ${x#...} in it which will be singsub()ed below because
+     * that would overwrite the pattern buffer. */
 
-    case 5:
-	/* Smallest at end, matching substrings */
-	if (domatch(s + l, c, 0) && !--n) {
-	    *sp = get_match_ret(*sp, l, l, fl);
-	    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);
-		    return 1;
-		}
-		*t = sav;
-		if (t >= s+2 && t[-2] == Meta)
-		    t--;
-		if (j >= 2 && s[j-2] == Meta)
-		    j--;
-	    }
-	}
-	break;
+    int patflags = PAT_SCAN|PAT_NOANCH | (*replstrp ? 0 : PAT_STATIC);
 
-    case 6:
-	/* Largest at start, matching substrings. */
-	for (i = l; i; 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);
-		    return 1;
-		}
-		if ((s[j] = sav) == Meta)
-		    j++;
-		if (*t == Meta)
-		    t++;
-	    }
-	    if (i >= 2 && s[i-2] == Meta)
-		i--;
-	}
-	if (domatch(s + l, c, 0) && !--n) {
-	    *sp = get_match_ret(*sp, 0, 0, fl);
-	    return 1;
-	}
-	break;
-
-    case 7:
-	/* 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);
-		    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);
-	    return 1;
+    /*
+     * Search is anchored to the end of the string if we want to match
+     * it all, or if we are matching at the end of the string and not
+     * using substrings.
+     */
+    if ((*flp & SUB_ALL) || ((*flp & SUB_END) && !(*flp & SUB_SUBSTR)))
+	patflags &= ~PAT_NOANCH;
+    p = patcompile(pat, patflags, NULL);
+    if (!p) {
+	zerr("bad pattern: %s", pat, 0);
+	return NULL;
+    }
+    if (*replstrp) {
+	if (p->patnpar || (p->globend & GF_MATCHREF)) {
+	    /*
+	     * Either backreferences or match references, so we
+	     * need to re-substitute replstr each time round.
+	     */
+	    *flp |= SUB_DOSUBST;
+	} else {
+	    singsub(replstrp);
+	    untokenize(*replstrp);
 	}
-	break;
     }
-    /* munge the whole string */
-    *sp = get_match_ret(*sp, 0, 0, fl);
-    return 1;
+
+    return p;
 }
 
-/* The main entry point for matching a string str against  *
- * a compiled pattern c.  `fist' indicates whether leading *
- * dots are special.                                       */
+/*
+ * 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. The heap 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.
+ */
 
 /**/
 int
-domatch(char *str, Comp c, int fist)
+getmatch(char **sp, char *pat, int fl, int n, char *replstr)
 {
-    int ret;
-    pptr = str;
-    first = fist;
-    if (*pptr == Nularg)
-	pptr++;
-    PERMALLOC {
-	ret = doesmatch(c);
-    } LASTALLOC;
-    return ret;
-}
+    Patprog p;
 
-#define untok(C)  (itok(C) ? ztokens[(C) - Pound] : (C))
+    if (!(p = compgetmatch(pat, &fl, &replstr)))
+	return 1;
 
-/* See if pattern has a matching exclusion (~...) part */
+    return igetmatch(sp, p, fl, n, replstr);
+}
 
 /**/
-static int
-excluded(Comp c, char *eptr)
+void
+getmatcharr(char ***ap, char *pat, int fl, int n, char *replstr)
 {
-    char *saves = pptr;
-    int savei = first, ret;
-
-    first = 0;
-    if (PATHADDP(c) && pathpos) {
-	VARARR(char, buf, pathpos + strlen(eptr) + 1);
-
-	strcpy(buf, pathbuf);
-	strcpy(buf + pathpos, eptr);
-	pptr = buf;
-	ret = doesmatch(c->exclude);
-    } else {
-	pptr = eptr;
-	ret = doesmatch(c->exclude);
-    }
-    if (*pptr)
-	ret = 0;
+    char **arr = *ap, **pp;
+    Patprog p;
 
-    pptr = saves;
-    first = savei;
+    if (!(p = compgetmatch(pat, &fl, &replstr)))
+	return;
 
-    return ret;
+    *ap = pp = hcalloc(sizeof(char *) * (arrlen(arr) + 1));
+    while ((*pp = *arr++))
+	if (igetmatch(pp, p, fl, n, replstr))
+	    pp++;
 }
 
-struct gclose {
-    char *start;
-    char *end;
-};
-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
- * the closure (c->next) at that point and failed.  This means that not
- * only should we not bother using the corresponding match, we should
- * also not bother going any further, since the first time we got to
- * that position (when it was marked), we must already have failed on
- * and backtracked over any further closure matches beyond that point.
- */
-
 /**/
-static void
-addclosures(Comp c, LinkList closlist, int *pdone, char *trystring)
+static int
+igetmatch(char **sp, Patprog p, int fl, int n, char *replstr)
 {
-    Gclose gcnode;
-    char *opptr = pptr;
-
-    while (*pptr) {
-	if (STARP(c)) {
-	    if (trystring[(pptr+1)-opptr])
-		break;
-	    gcnode = (Gclose)zalloc(sizeof(struct gclose));
-	    gcnode->start = pptr;
-	    gcnode->end = ++pptr;
-	} else {
-	    char *saves = pptr;
-	    if (OPTIONALP(c) && *pdone >= 1)
-		return;
-	    if (!matchonce(c) || saves == pptr ||
-		trystring[pptr-opptr]) {
-		pptr = saves;
-		break;
-	    }
-	    gcnode = (Gclose)zalloc(sizeof(struct gclose));
-	    gcnode->start = saves;
-	    gcnode->end = pptr;
-	}
-	pushnode(closlist, gcnode);
-	(*pdone)++;
-    }
-}
+    char *s = *sp, *t, sav;
+    int i, l = strlen(*sp), ml = ztrlen(*sp), matched = 1;
 
-/* see if current string in pptr matches c */
+    repllist = NULL;
 
-/**/
-static int
-doesmatch(Comp c)
-{
-    if (CLOSUREP(c)) {
-	int done, retflag = 0;
-	char *saves, *trystring, *opptr;
-	LinkList closlist;
-	Gclose gcnode;
+    /* perform must-match test for complex closures */
+    if (p->mustoff && !strstr((char *)s, (char *)p + p->mustoff))
+	matched = 0;
 
-	if (first && *pptr == '.')
+    if (fl & SUB_ALL) {
+	i = matched && pattry(p, s);
+	*sp = get_match_ret(*sp, 0, i ? l : 0, fl, i ? replstr : 0);
+	if (! **sp && (((fl & SUB_MATCH) && !i) || ((fl & SUB_REST) && i)))
 	    return 0;
-
-	if (!inclosure && !c->left) {
-	    /* We are not inside another closure, and the current
-	     * pattern is a simple string.  We handle this very common
-	     * case specially: otherwise, matches like *foo* are
-	     * extremely slow.  Here, instead of backtracking, we track
-	     * forward until we get a match.  At top level, we are bound
-	     * to get there eventually, so this is OK.
+	return 1;
+    }
+    if (matched) {
+	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...
 	     */
-	    char looka;
-
-	    if (STARP(c) && c->next &&
-		!c->next->left && (looka = *c->next->str) &&
-		!itok(looka)) {
-		/* Another simple optimisation for a very common case:
-		 * we are processing a * and there is
-		 * an ordinary character match next.  We look ahead for
-		 * that character, taking care of Meta bytes.
-		 */
-		while (*pptr) {
-		    for (; *pptr; pptr++) {
-			if (*pptr == Meta)
-			    pptr++;
-			else if (*pptr == looka)
+	    if (pattry(p, s)) {
+		char *mpos = patinput;
+		if (!(fl & SUB_LONG) && !(p->flags & PAT_PURES)) {
+		    /*
+		     * ... now we know whether it's worth looking for the
+		     * shortest, which we do by brute force.
+		     */
+		    for (t = s; t < mpos; METAINC(t)) {
+			sav = *t;
+			*t = '\0';
+			if (pattry(p, s)) {
+			    mpos = patinput;
+			    *t = sav;
 			    break;
+			}
+			*t = sav;
 		    }
-		    if (!*(saves = pptr))
-			break;
-		    if (doesmatch(c->next))
-			return 1;
-		    pptr = saves+1;
 		}
-	    } else {
-		/* Standard track-forward code */
-		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))
-			return 0;
-		    pptr = saves;
-		    first = 0;
-		    if (STARP(c)) {
-			if (!*pptr)
-			    return 0;
-			pptr++;
-		    } else if (!matchonce(c) || pptr == saves)
-			return 0;
-		}
-	    }
-	    return 0;
-	}
-	/* The full, gory backtracking code is now necessary. */
-	inclosure++;
-	closlist = newlinklist();
-	trystring = zcalloc(strlen(pptr)+1);
-	opptr = pptr;
-
-	/* Start by making a list where each match is as long
-	 * as possible.  We later have to take account of the
-	 * fact that earlier matches may be too long.
-	 */
-	done = 0;
-	addclosures(c, closlist, &done, trystring);
-	for (;;) {
-	    if (TWOHASHP(c) && !done)
-		break;
-	    saves = pptr;
-	    /* do we really want this LASTP here?? */
-	    if ((!c->next && (!LASTP(c) || !*pptr)) ||
-		(c->next && doesmatch(c->next))) {
-		retflag = 1;
-		break;
+		*sp = get_match_ret(*sp, 0, mpos-s, fl, replstr);
+		return 1;
 	    }
-	    trystring[saves-opptr] = 1;
-	    /*
-	     * If we failed, the first thing to try is whether we can
-	     * shorten the match using the last pattern in the closure.
-	     */
-	    gcnode = firstnode(closlist) ? peekfirst(closlist) : NULL;
-	    if (gcnode && --gcnode->end > gcnode->start
-		&& (gcnode->end[-1] != Meta ||
-		    --gcnode->end > gcnode->start)) {
-		char savec = *gcnode->end;
-		*gcnode->end = '\0';
-		pptr = gcnode->start;
-		if (matchonce(c) && pptr != gcnode->start
-		    && !trystring[pptr-opptr]) {
-		    *gcnode->end = savec;
-		    gcnode->end = pptr;
-		    /* Try again to construct a list based on
-		     * this new position
-		     */
-		    addclosures(c, closlist, &done, trystring+(pptr-opptr));
-		    continue;
+	    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.               */
+	    patoffset = ml;
+	    for (t = s + l; t >= s; t--, patoffset--) {
+		if (pattry(p, t)) {
+		    *sp = get_match_ret(*sp, t - s, l, fl, replstr);
+		    patoffset = 0;
+		    return 1;
 		}
-		*gcnode->end = savec;
+		if (t > s+1 && t[-2] == Meta)
+		    t--;
 	    }
-	    /* We've now exhausted the possibilities with that match,
-	     * backtrack to the previous.
-	     */
-	    if ((gcnode = (Gclose)getlinknode(closlist))) {
-		pptr = gcnode->start;
-		zfree(gcnode, sizeof(struct gclose));
-		done--;
-	    } else
-		break;
-	}
-	freelinklist(closlist, free);
-	zfree(trystring, strlen(opptr)+1);
-	inclosure--;
-
-	return retflag;
-    } else
-	return matchonce(c);
-}
-
-/**/
-static int
-posix_range(char **patptr, int ch)
-{
-    /* Match POSIX ranges, which correspond to ctype macros,  *
-     * e.g. [:alpha:] -> isalpha.  It just doesn't seem worth * 
-     * the palaver of creating a hash table for this.         */
-    char *start = *patptr;
-    int len;
-
-    /* we made sure in parsecomp() there was a ':' to search for */
-    *patptr = strchr(start, ':');
-    len = (*patptr)++ - start;
-
-    if (!strncmp(start, "alpha", len))
-	return isalpha(ch);
-    if (!strncmp(start, "alnum", len))
-	return isalnum(ch);
-    if (!strncmp(start, "blank", len))
-	return ch == ' ' || ch == '\t';
-    if (!strncmp(start, "cntrl", len))
-	return iscntrl(ch);
-    if (!strncmp(start, "digit", len))
-	return isdigit(ch);
-    if (!strncmp(start, "graph", len))
-	return isgraph(ch);
-    if (!strncmp(start, "lower", len))
-	return islower(ch);
-    if (!strncmp(start, "print", len))
-	return isprint(ch);
-    if (!strncmp(start, "punct", len))
-	return ispunct(ch);
-    if (!strncmp(start, "space", len))
-	return isspace(ch);
-    if (!strncmp(start, "upper", len))
-	return isupper(ch);
-    if (!strncmp(start, "xdigit", len))
-	return isxdigit(ch);
-    return 0;
-}
-
-/**/
-static void
-rangematch(char **patptr, int ch, int rchar)
-{
-    /* Check for a character in a [...] or [^...].  The [ *
-     * and optional ^ have already been skipped.          */
-
-    char *pat = *patptr;
-#ifdef HAVE_STRCOLL
-    char l_buf[2], r_buf[2], ch_buf[2];
-
-    ch_buf[0] = ch;
-    l_buf[1] = r_buf[1] = ch_buf[1] = '\0';
-#endif
-
-#define PAT(X) (pat[X] == Meta ? pat[(X)+1] ^ 32 : untok(pat[X]))
-#define PPAT(X) (pat[(X)-1] == Meta ? pat[X] ^ 32 : untok(pat[X]))
-
-    for (pat++; *pat != Outbrack && *pat;
-	 *pat == Meta ? pat += 2 : pat++) {
-	if (*pat == Inbrack) {
-	    /* Inbrack can only occur inside a range if we found [:...:]. */
-	    pat += 2;
-	    if (posix_range(&pat, ch))
-		break;
-	} else if (*pat == '-' && pat[-1] != rchar &&
-		   pat[1] != Outbrack) {
-#ifdef HAVE_STRCOLL
-	    l_buf[0] = PPAT(-1);
-	    r_buf[0] = PAT(1);
-	    if (strcoll(l_buf, ch_buf) <= 0 &&
-		strcoll(ch_buf, r_buf) <= 0)
-#else
-		if (PPAT(-1) <= ch && PAT(1) >= ch)
-#endif
-		    break;
-	} else if (ch == PAT(0))
+	    patoffset = 0;
 	    break;
-    }
-
-    *patptr = pat;
-}
 
-/**/
-static int
-matchonce(Comp c)
-{
-    char *pat = c->str;
-    for (;;) {
-	/* loop until success or failure of pattern */
-	if (!pat || !*pat) {
-	    /* No current pattern (c->str). */
-	    char *saves;
-	    int savei;
+	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++, patoffset++) {
+		if (pattry(p, t)) {
+		    *sp = get_match_ret(*sp, i, l, fl, replstr);
+		    patoffset = 0;
+		    return 1;
+		}
+		if (*t == Meta)
+		    i++, t++;
+	    }
+	    patoffset = 0;
+	    break;
 
-	    if (errflag)
-		return 0;
-	    /* Remember state in case we need to go back and   *
-	     * check for exclusion of pattern or alternatives. */
-	    saves = pptr;
-	    savei = first;
-	    /* Loop over alternatives with exclusions: (foo~bar|...). *
-	     * Exclusions apply to the pattern in c->left.            */
-	    if (c->left || c->right) {
-		int ret = 0, ret2 = 0;
-		if (c->exclude) {
-		    char *exclend = 0;
-
-		    /* We may need to back up on things like `(*~foo)'
-		     * if the `*' matched `foo' but needs to match `fo'.
-		     * exclend marks the end of the shortened text.  We
-		     * need to restore it to match the tail.
-		     * We set `inclosure' because we need the more
-		     * sophisticated code in doesmatch() for any nested
-		     * closures.
-		     */
-		    inclosure++;
-
-		    while (!exclend || exclend >= pptr) {
-			char exclsav = 0;
-			if (exclend) {
-			     exclsav = *exclend;
-			    *exclend = '\0';
-			 }
-			if ((ret = doesmatch(c->left))) {
-			    if (exclend)
-				*exclend = exclsav;
-			    exclsav = *(exclend = pptr);
-			    *exclend = '\0';
-			    ret2 = !excluded(c, saves);
+	case SUB_SUBSTR:
+	    /* Smallest at start, but matching substrings. */
+	    if (!(fl & SUB_GLOBAL) && pattry(p, s + l) && !--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 */
+	    t = s;
+	    if (fl & SUB_GLOBAL)
+		repllist = newlinklist();
+	    do {
+		/* loop over all matches for global substitution */
+		matched = 0;
+		for (; t < s + l; t++, patoffset++) {
+		    /* Find the longest match from this position. */
+		    if (pattry(p, t) && patinput > t) {
+			char *mpos = patinput;
+			if (!(fl & SUB_LONG) && !(p->flags & PAT_PURES)) {
+			    char *ptr;
+			    for (ptr = t; ptr < mpos; METAINC(ptr)) {
+				sav = *ptr;
+				*ptr = '\0';
+				if (pattry(p, t)) {
+				    mpos = patinput;
+				    *ptr = sav;
+				    break;
+				}
+				*ptr = sav;
+			    }
 			}
-			if (exclend)
-			    *exclend = exclsav;
-
-			if (!ret)
-			    break;
-			if ((ret = ret2 &&
-			     ((!c->next && (!LASTP(c) || !*pptr))
-			      || (c->next && doesmatch(c->next)))) ||
-			    (!c->next && LASTP(c)))
-			    break;
-			/* Back up if necessary: exclend gives the position
-			 * of the end of the match we are excluding,
-			 * so only try to match to there.
+			if (!--n || (n <= 0 && (fl & SUB_GLOBAL))) {
+			    *sp = get_match_ret(*sp, t-s, mpos-s, fl, replstr);
+			    if (mpos == t)
+				METAINC(mpos);
+			}
+			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 {
+				patoffset = 0;
+				return 1;
+			    }
+			}
+			/*
+			 * For a global match, we need to skip the stuff
+			 * which is already marked for replacement.
 			 */
-			exclend--;
-			pptr = saves;
+			matched = 1;
+			for ( ; t < mpos; t++, patoffset++)
+			    if (*t == Meta)
+				t++;
+			break;
 		    }
-		    inclosure--;
-		    if (ret)
-			return 1;
-		} else
-		    ret = doesmatch(c->left);
-		ret2 = 0;
-		if (c->right && (!ret || inclosure)) {
-		    /* If in a closure, we always want the longest match. */
-		    char *newpptr = pptr;
-		    pptr = saves;
-		    first = savei;
-		    ret2 = doesmatch(c->right);
-		    if (ret && (!ret2 || pptr < newpptr))
-			pptr = newpptr;
+		    if (*t == Meta)
+			t++;
 		}
-		if (!ret && !ret2)
-		    return 0;
-	    }
-	    if (CLOSUREP(c))
+	    } while (matched);
+	    patoffset = 0;
+	    /*
+	     * check if we can match a blank string, if so do it
+	     * 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 &&
+		pattry(p, s + l) && !--n) {
+		*sp = get_match_ret(*sp, 0, 0, fl, replstr);
 		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;
-		pat = c->str;
-		continue;
 	    }
-	    return doesmatch(c->next);
-	}
-	/* Don't match leading dot if first is set */
-	if (first && *pptr == '.' && *pat != '.')
-	    return 0;
-	if (*pat == Star) {	/* final * is not expanded to ?#; returns success */
-	    while (*pptr)
-		pptr++;
-	    return 1;
-	}
-	first = 0;		/* finished checking start of pattern */
-	if (*pat == Quest && *pptr) {
-	    /* match exactly one character */
-	    if (*pptr == Meta)
-		pptr++;
-	    pptr++;
-	    pat++;
-	    continue;
-	}
-	if (*pat == Inbrack) {
-	    /* Match groups of characters */
-	    char ch;
+	    break;
 
-	    if (!*pptr)
-		break;
-	    ch = *pptr == Meta ? pptr[1] ^ 32 : *pptr;
-	    if (pat[1] == Hat || pat[1] == '^' || pat[1] == '!') {
-		/* group is negated */
-		*++pat = Hat;
-		rangematch(&pat, ch, Hat);
-		DPUTS(!*pat, "BUG: something is very wrong in doesmatch()");
-		if (*pat != Outbrack)
-		    break;
-		pat++;
-		*pptr == Meta ? pptr += 2 : pptr++;
-		continue;
-	    } else {
-		/* pattern is not negated (affirmed? asserted?) */
-		rangematch(&pat, ch, Inbrack);
-		DPUTS(!pat || !*pat, "BUG: something is very wrong in doesmatch()");
-		if (*pat == Outbrack)
-		    break;
-		for (*pptr == Meta ? pptr += 2 : pptr++;
-		     *pat != Outbrack; pat++);
-		pat++;
-		continue;
+	case (SUB_END|SUB_SUBSTR):
+	    /* Shortest at end with substrings */
+	    patoffset = ml;
+	    if (pattry(p, s + l) && !--n) {
+		*sp = get_match_ret(*sp, l, l, fl, replstr);
+		patoffset = 0;
+		return 1;
+	    } /* fall through */
+	case (SUB_END|SUB_LONG|SUB_SUBSTR):
+	    /* Longest/shortest at end, matching substrings.       */
+	    patoffset--;
+	    for (t = s + l - 1; t >= s; t--, patoffset--) {
+		if (t > s && t[-1] == Meta)
+		    t--;
+		if (pattry(p, t) && patinput > t && !--n) {
+		    /* Found the longest match */
+		    char *mpos = patinput;
+		    if (!(fl & SUB_LONG) && !(p->flags & PAT_PURES)) {
+			char *ptr;
+			for (ptr = t; ptr < mpos; METAINC(ptr)) {
+			    sav = *ptr;
+			    *ptr = '\0';
+			    if (pattry(p, t)) {
+				mpos = patinput;
+				*ptr = sav;
+				break;
+			    }
+			    *ptr = sav;
+			}
+		    }
+		    *sp = get_match_ret(*sp, t-s, mpos-s, fl, replstr);
+		    patoffset = 0;
+		    return 1;
+		}
+	    }
+	    patoffset = ml;
+	    if ((fl & SUB_LONG) && pattry(p, s + l) && !--n) {
+		*sp = get_match_ret(*sp, l, l, fl, replstr);
+		patoffset = 0;
+		return 1;
 	    }
+	    patoffset = 0;
+	    break;
 	}
-	if (*pat == Inang) {
-	    /* Numeric globbing. */
-	    unsigned long t1, t2, t3;
-	    char *ptr;
+    }
 
-	    if (!idigit(*pptr))
-		break;
-	    if (*++pat == Outang || 
-		(*pat == '-' && pat[1] == Outang && ++pat)) {
-		/* <> or <->:  any number matches */
-		while (idigit(*++pptr));
-		pat++;
-	    } else {
-		/* Flag that there is no upper limit */
-		int not3 = 0;
-		char *opptr = pptr;
-		/*
-		 * Form is <a-b>, where a or b are numbers or blank.
-		 * t1 = number supplied:  must be positive, so use
-		 * unsigned arithmetic.
-		 */
-		t1 = (unsigned long)zstrtol(pptr, &ptr, 10);
-		pptr = ptr;
-		/* t2 = lower limit */
-		if (idigit(*pat))
-		    t2 = (unsigned long)zstrtol(pat, &ptr, 10);
-		else
-		    t2 = 0, ptr = pat;
-		if (*ptr != '-' || (not3 = (ptr[1] == Outang)))
-				/* exact match or no upper limit */
-		    t3 = t2, pat = ptr + not3;
-		else		/* t3 = upper limit */
-		    t3 = (unsigned long)zstrtol(ptr + 1, &pat, 10);
-		DPUTS(*pat != Outang, "BUG: wrong internal range pattern");
-		pat++;
-		/*
-		 * If the number found is too large for the pattern,
-		 * try matching just the first part.  This way
-		 * we always get the longest possible match.
-		 */
-		while (!not3 && t1 > t3 && pptr > opptr+1) {
-		  pptr--;
-		  t1 /= 10;
-		}
-		if (t1 < t2 || (!not3 && t1 > t3))
-		    break;
-	    }
-	    continue;
+    if (repllist && nonempty(repllist)) {
+	/* Put all the bits of a global search and replace together. */
+	LinkNode nd;
+	Repldata rd;
+	int lleft = 0;		/* size of returned string */
+	char *ptr, *start;
+
+	i = 0;			/* start of last chunk we got from *sp */
+	for (nd = firstnode(repllist); nd; incnode(nd)) {
+	    rd = (Repldata) getdata(nd);
+	    lleft += rd->b - i; /* previous chunk of *sp */
+	    lleft += strlen(rd->replstr);	/* the replaced bit */
+	    i = rd->e;		/* start of next chunk of *sp */
 	}
-	if (*pptr == *pat) {
-	    /* just plain old characters */
-	    pptr++;
-	    pat++;
-	    continue;
+	lleft += l - i;	/* final chunk from *sp */
+	start = t = zhalloc(lleft+1);
+	i = 0;
+	for (nd = firstnode(repllist); nd; incnode(nd)) {
+	    rd = (Repldata) getdata(nd);
+	    memcpy(t, s + i, rd->b - i);
+	    t += rd->b - i;
+	    ptr = rd->replstr;
+	    while (*ptr)
+		*t++ = *ptr++;
+	    i = rd->e;
 	}
-	break;
+	memcpy(t, s + i, l - i);
+	start[lleft] = '\0';
+	*sp = (char *)start;
+	return 1;
     }
-    return 0;
-}
-
-/* turn a string into a Comp struct:  this doesn't treat / specially */
 
-/**/
-Comp
-parsereg(char *str)
-{
-    remnulargs(str);
-    mode = 1;			/* no path components */
-    pptr = str;
-    tail = NULL;
-    return parsecompsw(GF_TOPLEV);
+    /* munge the whole string: no match, so no replstr */
+    *sp = get_match_ret(*sp, 0, 0, fl, 0);
+    return 1;
 }
 
 /* blindly turn a string into a tokenised expression without lexing */
 
 /**/
-void
+mod_export void
 tokenize(char *s)
 {
     char *t;
@@ -2550,16 +2334,14 @@ tokenize(char *s)
 	    *t = Inang;
 	    *s = Outang;
 	    break;
-	case '^':
-	case '#':
-	case '~':
-	    if (unset(EXTENDEDGLOB))
-		break;
 	case '(':
 	case '|':
 	case ')':
 	    if (isset(SHGLOB))
 		break;
+	case '^':
+	case '#':
+	case '~':
 	case '[':
 	case ']':
 	case '*':
@@ -2580,20 +2362,26 @@ tokenize(char *s)
 /* remove unnecessary Nulargs */
 
 /**/
-void
+mod_export void
 remnulargs(char *s)
 {
-    int nl = *s;
-    char *t = s;
+    if (*s) {
+	char *o = s, c;
 
-    while (*s)
-	if (INULL(*s))
-	    chuck(s);
-	else
-	    s++;
-    if (!*t && nl) {
-	t[0] = Nularg;
-	t[1] = '\0';
+	while ((c = *s++))
+	    if (INULL(c)) {
+		char *t = s - 1;
+
+		while ((c = *s++))
+		    if (!INULL(c))
+			*t++ = c;
+		*t = '\0';
+		if (!*o) {
+		    o[0] = Nularg;
+		    o[1] = '\0';
+		}
+		break;
+	    }
     }
 }
 
@@ -2603,7 +2391,7 @@ remnulargs(char *s)
 
 /**/
 static int
-qualdev(struct stat *buf, long dv)
+qualdev(char *name, struct stat *buf, off_t dv, char *dummy)
 {
     return buf->st_dev == dv;
 }
@@ -2612,10 +2400,10 @@ qualdev(struct stat *buf, long dv)
 
 /**/
 static int
-qualnlink(struct stat *buf, long ct)
+qualnlink(char *name, struct stat *buf, off_t ct, char *dummy)
 {
-    return (range < 0 ? buf->st_nlink < ct :
-	    range > 0 ? buf->st_nlink > ct :
+    return (g_range < 0 ? buf->st_nlink < ct :
+	    g_range > 0 ? buf->st_nlink > ct :
 	    buf->st_nlink == ct);
 }
 
@@ -2623,7 +2411,7 @@ qualnlink(struct stat *buf, long ct)
 
 /**/
 static int
-qualuid(struct stat *buf, long uid)
+qualuid(char *name, struct stat *buf, off_t uid, char *dummy)
 {
     return buf->st_uid == uid;
 }
@@ -2632,7 +2420,7 @@ qualuid(struct stat *buf, long uid)
 
 /**/
 static int
-qualgid(struct stat *buf, long gid)
+qualgid(char *name, struct stat *buf, off_t gid, char *dummy)
 {
     return buf->st_gid == gid;
 }
@@ -2641,7 +2429,7 @@ qualgid(struct stat *buf, long gid)
 
 /**/
 static int
-qualisdev(struct stat *buf, long junk)
+qualisdev(char *name, struct stat *buf, off_t junk, char *dummy)
 {
     return S_ISBLK(buf->st_mode) || S_ISCHR(buf->st_mode);
 }
@@ -2650,7 +2438,7 @@ qualisdev(struct stat *buf, long junk)
 
 /**/
 static int
-qualisblk(struct stat *buf, long junk)
+qualisblk(char *name, struct stat *buf, off_t junk, char *dummy)
 {
     return S_ISBLK(buf->st_mode);
 }
@@ -2659,7 +2447,7 @@ qualisblk(struct stat *buf, long junk)
 
 /**/
 static int
-qualischr(struct stat *buf, long junk)
+qualischr(char *name, struct stat *buf, off_t junk, char *dummy)
 {
     return S_ISCHR(buf->st_mode);
 }
@@ -2668,7 +2456,7 @@ qualischr(struct stat *buf, long junk)
 
 /**/
 static int
-qualisdir(struct stat *buf, long junk)
+qualisdir(char *name, struct stat *buf, off_t junk, char *dummy)
 {
     return S_ISDIR(buf->st_mode);
 }
@@ -2677,7 +2465,7 @@ qualisdir(struct stat *buf, long junk)
 
 /**/
 static int
-qualisfifo(struct stat *buf, long junk)
+qualisfifo(char *name, struct stat *buf, off_t junk, char *dummy)
 {
     return S_ISFIFO(buf->st_mode);
 }
@@ -2686,7 +2474,7 @@ qualisfifo(struct stat *buf, long junk)
 
 /**/
 static int
-qualislnk(struct stat *buf, long junk)
+qualislnk(char *name, struct stat *buf, off_t junk, char *dummy)
 {
     return S_ISLNK(buf->st_mode);
 }
@@ -2695,7 +2483,7 @@ qualislnk(struct stat *buf, long junk)
 
 /**/
 static int
-qualisreg(struct stat *buf, long junk)
+qualisreg(char *name, struct stat *buf, off_t junk, char *dummy)
 {
     return S_ISREG(buf->st_mode);
 }
@@ -2704,7 +2492,7 @@ qualisreg(struct stat *buf, long junk)
 
 /**/
 static int
-qualissock(struct stat *buf, long junk)
+qualissock(char *name, struct stat *buf, off_t junk, char *dummy)
 {
     return S_ISSOCK(buf->st_mode);
 }
@@ -2713,25 +2501,27 @@ qualissock(struct stat *buf, long junk)
 
 /**/
 static int
-qualflags(struct stat *buf, long mod)
+qualflags(char *name, struct stat *buf, off_t mod, char *dummy)
 {
     return mode_to_octal(buf->st_mode) & mod;
 }
 
-/* mode matches number supplied exactly  */
+/* mode matches specification */
 
 /**/
 static int
-qualeqflags(struct stat *buf, long mod)
+qualmodeflags(char *name, struct stat *buf, off_t mod, char *dummy)
 {
-    return mode_to_octal(buf->st_mode) == mod;
+    long v = mode_to_octal(buf->st_mode), y = mod & 07777, n = mod >> 12;
+
+    return ((v & y) == y && !(v & n));
 }
 
 /* regular executable file? */
 
 /**/
 static int
-qualiscom(struct stat *buf, long mod)
+qualiscom(char *name, struct stat *buf, off_t mod, char *dummy)
 {
     return S_ISREG(buf->st_mode) && (buf->st_mode & S_IXUGO);
 }
@@ -2740,11 +2530,17 @@ qualiscom(struct stat *buf, long mod)
 
 /**/
 static int
-qualsize(struct stat *buf, long size)
+qualsize(char *name, struct stat *buf, off_t size, char *dummy)
 {
-    unsigned long scaled = buf->st_size;
+#if defined(LONG_IS_64_BIT) || defined(OFF_T_IS_64_BIT)
+# define QS_CAST_SIZE()
+    off_t scaled = buf->st_size;
+#else
+# define QS_CAST_SIZE() (unsigned long)
+    unsigned long scaled = (unsigned long)buf->st_size;
+#endif
 
-    switch (units) {
+    switch (g_units) {
     case TT_POSIX_BLOCKS:
 	scaled += 511l;
 	scaled /= 512l;
@@ -2759,24 +2555,25 @@ qualsize(struct stat *buf, long size)
 	break;
     }
 
-    return (range < 0 ? scaled < (unsigned long) size :
-	    range > 0 ? scaled > (unsigned long) size :
-	    scaled == (unsigned long) size);
+    return (g_range < 0 ? scaled < QS_CAST_SIZE() size :
+	    g_range > 0 ? scaled > QS_CAST_SIZE() size :
+	    scaled == QS_CAST_SIZE() size);
+#undef QS_CAST_SIZE
 }
 
 /* time in required range? */
 
 /**/
 static int
-qualtime(struct stat *buf, long days)
+qualtime(char *name, struct stat *buf, off_t days, char *dummy)
 {
     time_t now, diff;
 
     time(&now);
-    diff = now - (amc == 0 ? buf->st_atime : amc == 1 ? buf->st_mtime :
+    diff = now - (g_amc == 0 ? buf->st_atime : g_amc == 1 ? buf->st_mtime :
 		  buf->st_ctime);
     /* handle multipliers indicating units */
-    switch (units) {
+    switch (g_units) {
     case TT_DAYS:
 	diff /= 86400l;
 	break;
@@ -2794,7 +2591,45 @@ qualtime(struct stat *buf, long days)
 	break;
     }
 
-    return (range < 0 ? diff < days :
-	    range > 0 ? diff > days :
+    return (g_range < 0 ? diff < days :
+	    g_range > 0 ? diff > days :
 	    diff == days);
 }
+
+/* evaluate a string */
+
+/**/
+static int
+qualsheval(char *name, struct stat *buf, off_t days, char *str)
+{
+    Eprog prog;
+
+    if ((prog = parse_string(str, 0))) {
+	int ef = errflag, lv = lastval, ret;
+
+	unsetparam("reply");
+	setsparam("REPLY", ztrdup(name));
+
+	execode(prog, 1, 0);
+
+	ret = lastval;
+	errflag = ef;
+	lastval = lv;
+
+	if (!(inserts = getaparam("reply")) &&
+	    !(inserts = gethparam("reply"))) {
+	    char *tmp;
+
+	    if ((tmp = getsparam("reply")) || (tmp = getsparam("REPLY"))) {
+		static char *tmparr[2];
+
+		tmparr[0] = tmp;
+		tmparr[1] = NULL;
+
+		inserts = tmparr;
+	    }
+	}
+	return !ret;
+    }
+    return 0;
+}
diff --git a/Src/utils.c b/Src/utils.c
index 8dbad00e9..416d0aeaf 100644
--- a/Src/utils.c
+++ b/Src/utils.c
@@ -2681,7 +2681,7 @@ niceztrdup(char const *s)
 }
 
 /**/
-char *
+mod_export char *
 nicedupstring(char const *s)
 {
     return nicedup(s, 1);
diff --git a/Util/mkdisttree.sh b/Util/mkdisttree.sh
index 837ebbcc2..80139c716 100755
--- a/Util/mkdisttree.sh
+++ b/Util/mkdisttree.sh
@@ -42,10 +42,13 @@ sed_separate='
     s/;;*/;/g
 '
 
+filelist=filelist$$
+trap 'rm -f $filelist; rm -rf $disttree; exit 1' 1 2 15
 (
     cd $sdir_top
-    find . \( -name '*.*' -prune -false \) -o \( -name .distfiles -print \)
-) | while read dfn; do
+    find . -name '*.*' -prune -o -name .distfiles -print
+) > $filelist
+( while read dfn; do
     subdir=`echo $dfn | sed 's,/\.distfiles$,,'`
     echo >&2 "Processing directory $subdir..."
     eval "DISTFILES_$type="
@@ -55,15 +58,15 @@ sed_separate='
 	cmds=`echo "$distfiles" | sed -e "$sed_separate"`
 	eval "$cmds"
 	if test -n "$deplist" && test -f $dir_top/$subdir/Makefile; then
-	    ( cd $dir_top/$subdir && "$@" $deplist ) || exit 1
+	    ( trap '' 1 2 15; cd $dir_top/$subdir && "$@" $deplist ) || exit 1
 	fi
 	$sdir_top/mkinstalldirs $disttree/$subdir || exit 1
 	for f in $deplist `test -z "$globlist" || ( cd $dir_top/$subdir && eval "echo $globlist")`; do
 	    if test -f $dir_top/$subdir/$f; then
-		ln $dir_top/$subdir/$f $disttree/$subdir/$f || \
+#		ln $dir_top/$subdir/$f $disttree/$subdir/$f || \
 		    cp -p $dir_top/$subdir/$f $disttree/$subdir/$f || exit 1
 	    elif test -f $sdir_top/$subdir/$f; then
-		ln $sdir_top/$subdir/$f $disttree/$subdir/$f || \
+#		ln $sdir_top/$subdir/$f $disttree/$subdir/$f || \
 		    cp -p $sdir_top/$subdir/$f $disttree/$subdir/$f || exit 1
 	    else
 		echo >&2 "$0: can't find file $subdir/$f"
@@ -71,6 +74,14 @@ sed_separate='
 	    fi
 	done
     fi
-done
+done ) < $filelist
 
-exec chmod -R a+rX,u+w,go-w $disttree
+status=$?
+rm -f $filelist
+trap '' 1 2 15
+if test $status -ne 0; then
+    rm -rf $disttree
+    exit $status
+fi
+
+exec chmod -R a+rX,u+w,g-s,go-w $disttree