1 //glob.c - filename generation

     2 //

     3 // © Portions Copyright (c) Symbian Software Ltd 2007. All rights reserved.

     4 //

     5 /*

     6  * This file is part of zsh, the Z shell.

     7  *

     8  * Copyright (c) 1992-1997 Paul Falstad

     9  * All rights reserved.

    10  *

    11  * Permission is hereby granted, without written agreement and without

    12  * license or royalty fees, to use, copy, modify, and distribute this

    13  * software and to distribute modified versions of this software for any

    14  * purpose, provided that the above copyright notice and the following

    15  * two paragraphs appear in all copies of this software.

    16  *

    17  * In no event shall Paul Falstad or the Zsh Development Group be liable

    18  * to any party for direct, indirect, special, incidental, or consequential

    19  * damages arising out of the use of this software and its documentation,

    20  * even if Paul Falstad and the Zsh Development Group have been advised of

    21  * the possibility of such damage.

    22  *

    23  * Paul Falstad and the Zsh Development Group specifically disclaim any

    24  * warranties, including, but not limited to, the implied warranties of

    25  * merchantability and fitness for a particular purpose.  The software

    26  * provided hereunder is on an "as is" basis, and Paul Falstad and the

    27  * Zsh Development Group have no obligation to provide maintenance,

    28  * support, updates, enhancements, or modifications.

    29  *

    30  */

    31 

    32 #include "zsh.mdh"

    33 #include "glob.pro"

    34 

    35 #ifdef __SYMBIAN32__

    36 #ifdef __WINSCW__

    37 #pragma warn_unusedarg off

    38 #pragma warn_possunwant off

    39 #endif//__WINSCW__

    40 #endif//__SYMBIAN32__

    41 

    42 

    43 #if defined(OFF_T_IS_64_BIT) && defined(__GNUC__)

    44 # define ALIGN64 __attribute__((aligned(8)))

    45 #else

    46 # define ALIGN64

    47 #endif

    48 

    49 /* flag for CSHNULLGLOB */

    50 

    51 typedef struct gmatch *Gmatch;

    52 

    53 struct gmatch {

    54     char *name;

    55     off_t size ALIGN64;

    56     long atime;

    57     long mtime;

    58     long ctime;

    59     long links;

    60     off_t _size ALIGN64;

    61     long _atime;

    62     long _mtime;

    63     long _ctime;

    64     long _links;

    65 };

    66 

    67 #define GS_NAME   1

    68 #define GS_DEPTH  2

    69 #define GS_SIZE   4

    70 #define GS_ATIME  8

    71 #define GS_MTIME 16

    72 #define GS_CTIME 32

    73 #define GS_LINKS 64

    74 

    75 #define GS_SHIFT  5

    76 #define GS__SIZE  (GS_SIZE << GS_SHIFT)

    77 #define GS__ATIME (GS_ATIME << GS_SHIFT)

    78 #define GS__MTIME (GS_MTIME << GS_SHIFT)

    79 #define GS__CTIME (GS_CTIME << GS_SHIFT)

    80 #define GS__LINKS (GS_LINKS << GS_SHIFT)

    81 

    82 #define GS_DESC  4096

    83 

    84 #define GS_NORMAL (GS_SIZE | GS_ATIME | GS_MTIME | GS_CTIME | GS_LINKS)

    85 #define GS_LINKED (GS_NORMAL << GS_SHIFT)

    86 

    87 /**/

    88 int badcshglob;

    89 

    90 /**/

    91 int pathpos;		/* position in pathbuf (needed by pattern code) */

    92 

    93 /**/

    94 char *pathbuf;		/* pathname buffer (needed by pattern code) */

    95 

    96 typedef struct stat *Statptr;	 /* This makes the Ultrix compiler happy.  Go figure. */

    97 

    98 /* modifier for unit conversions */

    99 

   100 #define TT_DAYS 0

   101 #define TT_HOURS 1

   102 #define TT_MINS 2

   103 #define TT_WEEKS 3

   104 #define TT_MONTHS 4

   105 #define TT_SECONDS 5

   106 

   107 #define TT_BYTES 0

   108 #define TT_POSIX_BLOCKS 1

   109 #define TT_KILOBYTES 2

   110 #define TT_MEGABYTES 3

   111 

   112 

   113 typedef int (*TestMatchFunc) _((char *, struct stat *, off_t, char *));

   114 

   115 struct qual {

   116     struct qual *next;		/* Next qualifier, must match                */

   117     struct qual *or;		/* Alternative set of qualifiers to match    */

   118     TestMatchFunc func;		/* Function to call to test match            */

   119     off_t data ALIGN64;		/* Argument passed to function               */

   120     int sense;			/* Whether asserting or negating             */

   121     int amc;			/* Flag for which time to test (a, m, c)     */

   122     int range;			/* Whether to test <, > or = (as per signum) */

   123     int units;			/* Multiplier for time or size, respectively */

   124     char *sdata;		/* currently only: expression to eval        */

   125 };

   126 

   127 /* Prefix, suffix for doing zle trickery */

   128 

   129 /**/

   130 mod_export char *glob_pre, *glob_suf;

   131 

   132 /* struct to easily save/restore current state */

   133 

   134 struct globdata {

   135     int gd_pathpos;

   136     char *gd_pathbuf;

   137 

   138     int gd_matchsz;		/* size of matchbuf                     */

   139     int gd_matchct;		/* number of matches found              */

   140     int gd_pathbufsz;		/* size of pathbuf			*/

   141     int gd_pathbufcwd;		/* where did we chdir()'ed		*/

   142     Gmatch gd_matchbuf;		/* array of matches                     */

   143     Gmatch gd_matchptr;		/* &matchbuf[matchct]                   */

   144     char *gd_colonmod;		/* colon modifiers in qualifier list    */

   145 

   146     /* Qualifiers pertaining to current pattern */

   147     struct qual *gd_quals;

   148 

   149     /* Other state values for current pattern */

   150     int gd_qualct, gd_qualorct;

   151     int gd_range, gd_amc, gd_units;

   152     int gd_gf_nullglob, gd_gf_markdirs, gd_gf_noglobdots, gd_gf_listtypes;

   153     int gd_gf_numsort;

   154     int gd_gf_follow, gd_gf_sorts, gd_gf_nsorts, gd_gf_sortlist[11];

   155 

   156     char *gd_glob_pre, *gd_glob_suf;

   157 };

   158 

   159 /* The variable with the current globbing state and convenience macros */

   160 

   161 static struct globdata curglobdata;

   162 

   163 #define matchsz       (curglobdata.gd_matchsz)

   164 #define matchct       (curglobdata.gd_matchct)

   165 #define pathbufsz     (curglobdata.gd_pathbufsz)

   166 #define pathbufcwd    (curglobdata.gd_pathbufcwd)

   167 #define matchbuf      (curglobdata.gd_matchbuf)

   168 #define matchptr      (curglobdata.gd_matchptr)

   169 #define colonmod      (curglobdata.gd_colonmod)

   170 #define quals         (curglobdata.gd_quals)

   171 #define qualct        (curglobdata.gd_qualct)

   172 #define qualorct      (curglobdata.gd_qualorct)

   173 #define g_range       (curglobdata.gd_range)

   174 #define g_amc         (curglobdata.gd_amc)

   175 #define g_units       (curglobdata.gd_units)

   176 #define gf_nullglob   (curglobdata.gd_gf_nullglob)

   177 #define gf_markdirs   (curglobdata.gd_gf_markdirs)

   178 #define gf_noglobdots (curglobdata.gd_gf_noglobdots)

   179 #define gf_listtypes  (curglobdata.gd_gf_listtypes)

   180 #define gf_numsort    (curglobdata.gd_gf_numsort)

   181 #define gf_follow     (curglobdata.gd_gf_follow)

   182 #define gf_sorts      (curglobdata.gd_gf_sorts)

   183 #define gf_nsorts     (curglobdata.gd_gf_nsorts)

   184 #define gf_sortlist   (curglobdata.gd_gf_sortlist)

   185 

   186 /* and macros for save/restore */

   187 

   188 #define save_globstate(N) \

   189   do { \

   190     memcpy(&(N), &curglobdata, sizeof(struct globdata)); \

   191     (N).gd_pathpos = pathpos; \

   192     (N).gd_pathbuf = pathbuf; \

   193     (N).gd_pathbufsz = 0; \

   194     (N).gd_glob_pre = glob_pre; \

   195     (N).gd_glob_suf = glob_suf; \

   196     pathbuf = NULL; \

   197   } while (0)

   198 

   199 #define restore_globstate(N) \

   200   do { \

   201     zfree(pathbuf, pathbufsz); \

   202     memcpy(&curglobdata, &(N), sizeof(struct globdata)); \

   203     pathpos = (N).gd_pathpos; \

   204     pathbuf = (N).gd_pathbuf; \

   205     glob_pre = (N).gd_glob_pre; \

   206     glob_suf = (N).gd_glob_suf; \

   207   } while (0)

   208 

   209 /* pathname component in filename patterns */

   210 

   211 struct complist {

   212     Complist next;

   213     Patprog pat;

   214     int closure;		/* 1 if this is a (foo/)# */

   215     int follow; 		/* 1 to go thru symlinks */

   216 };

   217 

   218 /* Next character after one which may be a Meta (x is any char *) */

   219 #define METANEXT(x)	(*(x) == Meta ? (x)+2 : (x)+1)

   220 /*

   221  * Increment pointer which may be on a Meta (x is a pointer variable),

   222  * returning the incremented value (i.e. like pre-increment).

   223  */

   224 #define METAINC(x)	((x) += (*(x) == Meta) ? 2 : 1)

   225 /*

   226  * Return unmetafied char from string (x is any char *)

   227  */

   228 #define UNMETA(x)	(*(x) == Meta ? (x)[1] ^ 32 : *(x))

   229 

   230 /* Add a component to pathbuf: This keeps track of how    *

   231  * far we are into a file name, since each path component *

   232  * must be matched separately.                            */

   233 

   234 /**/

   235 static void

   236 addpath(char *s, int l)

   237 {

   238     DPUTS(!pathbuf, "BUG: pathbuf not initialised");

   239     while (pathpos + l + 1 >= pathbufsz)

   240 	pathbuf = realloc(pathbuf, pathbufsz *= 2);

   241     while (l--)

   242 	pathbuf[pathpos++] = *s++;

   243     pathbuf[pathpos++] = '/';

   244     pathbuf[pathpos] = '\0';

   245 }

   246 

   247 /* stat the filename s appended to pathbuf.  l should be true for lstat,    *

   248  * false for stat.  If st is NULL, the file is only checked for existance.  *

   249  * s == "" is treated as s == ".".  This is necessary since on most systems *

   250  * foo/ can be used to reference a non-directory foo.  Returns nonzero if   *

   251  * the file does not exists.                                                */

   252 

   253 /**/

   254 static int

   255 statfullpath(const char *s, struct stat *st, int l)

   256 {

   257     char buf[PATH_MAX];

   258 

   259     DPUTS(strlen(s) + !*s + pathpos - pathbufcwd >= PATH_MAX,

   260 	  "BUG: statfullpath(): pathname too long");

   261     strcpy(buf, pathbuf + pathbufcwd);

   262     strcpy(buf + pathpos - pathbufcwd, s);

   263     if (!*s && *buf) {

   264 	/*

   265 	 * Don't add the '.' if the path so far is empty, since

   266 	 * then we get bogus empty strings inserted as files.

   267 	 */

   268 	buf[pathpos - pathbufcwd] = '.';

   269 	buf[pathpos - pathbufcwd + 1] = '\0';

   270 	l = 0;

   271     }

   272     unmetafy(buf, NULL);

   273     if (!st)

   274 	return access(buf, F_OK) && (!l || readlink(buf, NULL, 0));

   275     return l ? lstat(buf, st) : stat(buf, st);

   276 }

   277 

   278 /* This may be set by qualifier functions to an array of strings to insert

   279  * into the list instead of the original string. */

   280 

   281 char **inserts;

   282 

   283 /* add a match to the list */

   284 

   285 /**/

   286 static void

   287 insert(char *s, int checked)

   288 {

   289     struct stat buf, buf2, *bp;

   290     char *news = s;

   291     int statted = 0;

   292 

   293     queue_signals();

   294     inserts = NULL;

   295 

   296     if (gf_listtypes || gf_markdirs) {

   297 	/* Add the type marker to the end of the filename */

   298 	mode_t mode;

   299 	checked = statted = 1;

   300 	if (statfullpath(s, &buf, 1)) {

   301 	    unqueue_signals();

   302 	    return;

   303 	}

   304 	mode = buf.st_mode;

   305 	if (gf_follow) {

   306 	    if (!S_ISLNK(mode) || statfullpath(s, &buf2, 0))

   307 		memcpy(&buf2, &buf, sizeof(buf));

   308 	    statted |= 2;

   309 	    mode = buf2.st_mode;

   310 	}

   311 	if (gf_listtypes || S_ISDIR(mode)) {

   312 	    int ll = strlen(s);

   313 

   314 	    news = (char *) hcalloc(ll + 2);

   315 	    strcpy(news, s);

   316 	    news[ll] = file_type(mode);

   317 	    news[ll + 1] = '\0';

   318 	}

   319     }

   320     if (qualct || qualorct) {

   321 	/* Go through the qualifiers, rejecting the file if appropriate */

   322 	struct qual *qo, *qn;

   323 

   324 	if (!statted && statfullpath(s, &buf, 1)) {

   325 	    unqueue_signals();

   326 	    return;

   327 	}

   328 	news = dyncat(pathbuf, news);

   329 

   330 	statted = 1;

   331 	qo = quals;

   332 	for (qn = qo; qn && qn->func;) {

   333 	    g_range = qn->range;

   334 	    g_amc = qn->amc;

   335 	    g_units = qn->units;

   336 	    if ((qn->sense & 2) && !(statted & 2)) {

   337 		/* If (sense & 2), we're following links */

   338 		if (!S_ISLNK(buf.st_mode) || statfullpath(s, &buf2, 0))

   339 		    memcpy(&buf2, &buf, sizeof(buf));

   340 		statted |= 2;

   341 	    }

   342 	    bp = (qn->sense & 2) ? &buf2 : &buf;

   343 	    /* Reject the file if the function returned zero *

   344 	     * and the sense was positive (sense&1 == 0), or *

   345 	     * vice versa.                                   */

   346 	    if ((!((qn->func) (news, bp, qn->data, qn->sdata)) ^ qn->sense) & 1) {

   347 		/* Try next alternative, or return if there are no more */

   348 		if (!(qo = qo->or)) {

   349 		    unqueue_signals();

   350 		    return;

   351 		}

   352 		qn = qo;

   353 		continue;

   354 	    }

   355 	    qn = qn->next;

   356 	}

   357     } else if (!checked) {

   358 	if (statfullpath(s, NULL, 1)) {

   359 	    unqueue_signals();

   360 	    return;

   361 	}

   362 	statted = 1;

   363 	news = dyncat(pathbuf, news);

   364     } else

   365 	news = dyncat(pathbuf, news);

   366 

   367     while (!inserts || (news = dupstring(*inserts++))) {

   368 	if (colonmod) {

   369 	    /* Handle the remainder of the qualifier:  e.g. (:r:s/foo/bar/). */

   370 	    s = colonmod;

   371 	    modify(&news, &s);

   372 	}

   373 	if (!statted && (gf_sorts & GS_NORMAL)) {

   374 	    statfullpath(s, &buf, 1);

   375 	    statted = 1;

   376 	}

   377 	if (!(statted & 2) && (gf_sorts & GS_LINKED)) {

   378 	    if (statted) {

   379 		if (!S_ISLNK(buf.st_mode) || statfullpath(s, &buf2, 0))

   380 		    memcpy(&buf2, &buf, sizeof(buf));

   381 	    } else if (statfullpath(s, &buf2, 0))

   382 		statfullpath(s, &buf2, 1);

   383 	    statted |= 2;

   384 	}

   385 	matchptr->name = news;

   386 	if (statted & 1) {

   387 	    matchptr->size = buf.st_size;

   388 	    matchptr->atime = buf.st_atime;

   389 	    matchptr->mtime = buf.st_mtime;

   390 	    matchptr->ctime = buf.st_ctime;

   391 	    matchptr->links = buf.st_nlink;

   392 	}

   393 	if (statted & 2) {

   394 	    matchptr->_size = buf2.st_size;

   395 	    matchptr->_atime = buf2.st_atime;

   396 	    matchptr->_mtime = buf2.st_mtime;

   397 	    matchptr->_ctime = buf2.st_ctime;

   398 	    matchptr->_links = buf2.st_nlink;

   399 	}

   400 	matchptr++;

   401 

   402 	if (++matchct == matchsz) {

   403 	    matchbuf = (Gmatch )realloc((char *)matchbuf,

   404 					sizeof(struct gmatch) * (matchsz *= 2));

   405 

   406 	    matchptr = matchbuf + matchct;

   407 	}

   408 	if (!inserts)

   409 	    break;

   410     }

   411     unqueue_signals();

   412 }

   413 

   414 /* Check to see if str is eligible for filename generation. */

   415 

   416 /**/

   417 mod_export int

   418 haswilds(char *str)

   419 {

   420     /* `[' and `]' are legal even if bad patterns are usually not. */

   421     if ((*str == Inbrack || *str == Outbrack) && !str[1])

   422 	return 0;

   423 

   424     /* If % is immediately followed by ?, then that ? is     *

   425      * not treated as a wildcard.  This is so you don't have *

   426      * to escape job references such as %?foo.               */

   427     if (str[0] == '%' && str[1] == Quest)

   428 	str[1] = '?';

   429 

   430     for (; *str; str++) {

   431 	switch (*str) {

   432 	    case Inpar:

   433 	    case Bar:

   434 	    case Star:

   435 	    case Inbrack:

   436 	    case Inang:

   437 	    case Quest:

   438 		return 1;

   439 	    case Pound:

   440 	    case Hat:

   441 		if (isset(EXTENDEDGLOB))

   442 		    return 1;

   443 		break;

   444 	}

   445     }

   446     return 0;

   447 }

   448 

   449 /* Do the globbing:  scanner is called recursively *

   450  * with successive bits of the path until we've    *

   451  * tried all of it.                                */

   452 

   453 /**/

   454 static void

   455 scanner(Complist q)

   456 {

   457     Patprog p;

   458     int closure;

   459     int pbcwdsav = pathbufcwd;

   460     int errssofar = errsfound;

   461     struct dirsav ds;

   462 

   463     ds.ino = ds.dev = 0;

   464     ds.dirname = NULL;

   465     ds.dirfd = ds.level = -1;

   466     if (!q)

   467 	return;

   468 

   469     if ((closure = q->closure)) {

   470 	/* (foo/)# - match zero or more dirs */

   471 	if (q->closure == 2)	/* (foo/)## - match one or more dirs */

   472 	    q->closure = 1;

   473 	else

   474 	    scanner(q->next);

   475     }

   476     p = q->pat;

   477     /* Now the actual matching for the current path section. */

   478     if (p->flags & PAT_PURES) {

   479 	/*

   480 	 * It's a straight string to the end of the path section.

   481 	 */

   482 	char *str = (char *)p + p->startoff;

   483 	int l = p->patmlen;

   484 

   485 	if (l + !l + pathpos - pathbufcwd >= PATH_MAX) {

   486 	    int err;

   487 

   488 	    if (l >= PATH_MAX)

   489 		return;

   490 	    err = lchdir(pathbuf + pathbufcwd, &ds, 0);

   491 	    if (err == -1)

   492 		return;

   493 	    if (err) {

   494 		zerr("current directory lost during glob", NULL, 0);

   495 		return;

   496 	    }

   497 	    pathbufcwd = pathpos;

   498 	}

   499 	if (q->next) {

   500 	    /* Not the last path section. Just add it to the path. */

   501 	    int oppos = pathpos;

   502 

   503 	    if (!errflag) {

   504 		int add = 1;

   505 

   506 		if (q->closure && *pathbuf) {

   507 		    if (!strcmp(str, "."))

   508 			add = 0;

   509 		    else if (!strcmp(str, "..")) {

   510 			struct stat sc, sr;

   511 

   512 			add = (stat("/", &sr) || stat(pathbuf, &sc) ||

   513 			       sr.st_ino != sc.st_ino ||

   514 			       sr.st_dev != sc.st_dev);

   515 		    }

   516 		}

   517 		if (add) {

   518 		    addpath(str, l);

   519 		    if (!closure || !statfullpath("", NULL, 1))

   520 			scanner((q->closure) ? q : q->next);

   521 		    pathbuf[pathpos = oppos] = '\0';

   522 		}

   523 	    }

   524 	} else {

   525 	    if (str[l])

   526 		str = dupstrpfx(str, l);

   527 	    insert(str, 0);

   528 	}

   529     } else {

   530 	/* Do pattern matching on current path section. */

   531 	char *fn = pathbuf[pathbufcwd] ? unmeta(pathbuf + pathbufcwd) : ".";

   532 	int dirs = !!q->next;

   533 	DIR *lock = opendir(fn);

   534 	char *subdirs = NULL;

   535 	int subdirlen = 0;

   536 

   537 	if (lock == NULL)

   538 	    return;

   539 	while ((fn = zreaddir(lock, 1)) && !errflag) {

   540 	    /* prefix and suffix are zle trickery */

   541 	    if (!dirs && !colonmod &&

   542 		((glob_pre && !strpfx(glob_pre, fn))

   543 		 || (glob_suf && !strsfx(glob_suf, fn))))

   544 		continue;

   545 	    errsfound = errssofar;

   546 	    if (pattry(p, fn)) {

   547 		/* if this name matchs the pattern... */

   548 		if (pbcwdsav == pathbufcwd &&

   549 		    strlen(fn) + pathpos - pathbufcwd >= PATH_MAX) {

   550 		    int err;

   551 

   552 		    DPUTS(pathpos == pathbufcwd,

   553 			  "BUG: filename longer than PATH_MAX");

   554 		    err = lchdir(pathbuf + pathbufcwd, &ds, 0);

   555 		    if (err == -1)

   556 			break;

   557 		    if (err) {

   558 			zerr("current directory lost during glob", NULL, 0);

   559 			break;

   560 		    }

   561 		    pathbufcwd = pathpos;

   562 		}

   563 		if (dirs) {

   564 		    int l;

   565 

   566 		    /*

   567 		     * If not the last component in the path:

   568 		     *

   569 		     * If we made an approximation in the new path segment,

   570 		     * then it is possible we made too many errors.  For

   571 		     * example, (ab)#(cb)# will match the directory abcb

   572 		     * with one error if allowed to, even though it can

   573 		     * match with none.  This will stop later parts of the

   574 		     * path matching, so we need to check by reducing the

   575 		     * maximum number of errors and seeing if the directory

   576 		     * still matches.  Luckily, this is not a terribly

   577 		     * common case, since complex patterns typically occur

   578 		     * in the last part of the path which is not affected

   579 		     * by this problem.

   580 		     */

   581 		    if (errsfound > errssofar) {

   582 			forceerrs = errsfound - 1;

   583 			while (forceerrs >= errssofar) {

   584 			    errsfound = errssofar;

   585 			    if (!pattry(p, fn))

   586 				break;

   587 			    forceerrs = errsfound - 1;

   588 			}

   589 			errsfound = forceerrs + 1;

   590 			forceerrs = -1;

   591 		    }

   592 		    if (closure) {

   593 			/* if matching multiple directories */

   594 			struct stat buf;

   595 

   596 			if (statfullpath(fn, &buf, !q->follow)) {

   597 			    if (errno != ENOENT && errno != EINTR &&

   598 				errno != ENOTDIR && !errflag) {

   599 				zwarn("%e: %s", fn, errno);

   600 			    }

   601 			    continue;

   602 			}

   603 			if (!S_ISDIR(buf.st_mode))

   604 			    continue;

   605 		    }

   606 		    l = strlen(fn) + 1;

   607 		    subdirs = hrealloc(subdirs, subdirlen, subdirlen + l

   608 				       + sizeof(int));

   609 		    strcpy(subdirs + subdirlen, fn);

   610 		    subdirlen += l;

   611 		    /* store the count of errors made so far, too */

   612 		    memcpy(subdirs + subdirlen, (char *)&errsfound,

   613 			   sizeof(int));

   614 		    subdirlen += sizeof(int);

   615 		} else

   616 		    /* if the last filename component, just add it */

   617 		    insert(fn, 1);

   618 	    }

   619 	}

   620 	closedir(lock);

   621 	if (subdirs) {

   622 	    int oppos = pathpos;

   623 

   624 	    for (fn = subdirs; fn < subdirs+subdirlen; ) {

   625 		int l = strlen(fn);

   626 		addpath(fn, l);

   627 		fn += l + 1;

   628 		memcpy((char *)&errsfound, fn, sizeof(int));

   629 		fn += sizeof(int);

   630 		scanner((q->closure) ? q : q->next);  /* scan next level */

   631 		pathbuf[pathpos = oppos] = '\0';

   632 	    }

   633 	    hrealloc(subdirs, subdirlen, 0);

   634 	}

   635     }

   636     if (pbcwdsav < pathbufcwd) {

   637 	if (restoredir(&ds))

   638 	    zerr("current directory lost during glob", NULL, 0);

   639 	zsfree(ds.dirname);

   640 	if (ds.dirfd >= 0)

   641 	    close(ds.dirfd);

   642 	pathbufcwd = pbcwdsav;

   643     }

   644 }

   645 

   646 /* This function tokenizes a zsh glob pattern */

   647 

   648 /**/

   649 static Complist

   650 parsecomplist(char *instr)

   651 {

   652     Patprog p1;

   653     Complist l1;

   654     char *str;

   655     int compflags = gf_noglobdots ? (PAT_FILE|PAT_NOGLD) : PAT_FILE;

   656 

   657     if (instr[0] == Star && instr[1] == Star &&

   658         (instr[2] == '/' || (instr[2] == Star && instr[3] == '/'))) {

   659 	/* Match any number of directories. */

   660 	int follow;

   661 

   662 	/* with three stars, follow symbolic links */

   663 	follow = (instr[2] == Star);

   664 	instr += (3 + follow);

   665 

   666 	/* Now get the next path component if there is one. */

   667 	l1 = (Complist) zhalloc(sizeof *l1);

   668 	if ((l1->next = parsecomplist(instr)) == NULL) {

   669 	    errflag = 1;

   670 	    return NULL;

   671 	}

   672 	l1->pat = patcompile(NULL, compflags | PAT_ANY, NULL);

   673 	l1->closure = 1;		/* ...zero or more times. */

   674 	l1->follow = follow;

   675 	return l1;

   676     }

   677 

   678     /* Parse repeated directories such as (dir/)# and (dir/)## */

   679     if (*(str = instr) == Inpar && !skipparens(Inpar, Outpar, (char **)&str) &&

   680         *str == Pound && isset(EXTENDEDGLOB) && str[-2] == '/') {

   681 	instr++;

   682 	if (!(p1 = patcompile(instr, compflags, &instr)))

   683 	    return NULL;

   684 	if (instr[0] == '/' && instr[1] == Outpar && instr[2] == Pound) {

   685 	    int pdflag = 0;

   686 

   687 	    instr += 3;

   688 	    if (*instr == Pound) {

   689 		pdflag = 1;

   690 		instr++;

   691 	    }

   692 	    l1 = (Complist) zhalloc(sizeof *l1);

   693 	    l1->pat = p1;

   694 	    l1->closure = 1 + pdflag;

   695 	    l1->follow = 0;

   696 	    l1->next = parsecomplist(instr);

   697 	    return (l1->pat) ? l1 : NULL;

   698 	}

   699     } else {

   700 	/* parse single path component */

   701 	if (!(p1 = patcompile(instr, compflags|PAT_FILET, &instr)))

   702 	    return NULL;

   703 	/* then do the remaining path components */

   704 	if (*instr == '/' || !*instr) {

   705 	    int ef = *instr == '/';

   706 

   707 	    l1 = (Complist) zhalloc(sizeof *l1);

   708 	    l1->pat = p1;

   709 	    l1->closure = 0;

   710 	    l1->next = ef ? parsecomplist(instr+1) : NULL;

   711 	    return (ef && !l1->next) ? NULL : l1;

   712 	}

   713     }

   714     errflag = 1;

   715     return NULL;

   716 }

   717 

   718 /* turn a string into a Complist struct:  this has path components */

   719 

   720 /**/

   721 static Complist

   722 parsepat(char *str)

   723 {

   724     long assert;

   725     int ignore;

   726 

   727     patcompstart();

   728     /*

   729      * Check for initial globbing flags, so that they don't form

   730      * a bogus path component.

   731      */

   732     if ((*str == Inpar && str[1] == Pound && isset(EXTENDEDGLOB)) ||

   733 	(isset(KSHGLOB) && *str == '@' && str[1] == Inpar &&

   734 	 str[2] == Pound)) {

   735 	str += (*str == Inpar) ? 2 : 3;

   736 	if (!patgetglobflags(&str, &assert, &ignore))

   737 	    return NULL;

   738     }

   739 

   740     /* Now there is no (#X) in front, we can check the path. */

   741     if (!pathbuf)

   742 	pathbuf = zalloc(pathbufsz = PATH_MAX);

   743     DPUTS(pathbufcwd, "BUG: glob changed directory");

   744     if (*str == '/') {		/* pattern has absolute path */

   745 	str++;

   746 	pathbuf[0] = '/';

   747 	pathbuf[pathpos = 1] = '\0';

   748     } else			/* pattern is relative to pwd */

   749 	pathbuf[pathpos = 0] = '\0';

   750 

   751     return parsecomplist(str);

   752 }

   753 

   754 /* get number after qualifier */

   755 

   756 /**/

   757 static off_t

   758 qgetnum(char **s)

   759 {

   760     off_t v = 0;

   761 

   762     if (!idigit(**s)) {

   763 	zerr("number expected", NULL, 0);

   764 	return 0;

   765     }

   766     while (idigit(**s))

   767 	v = v * 10 + *(*s)++ - '0';

   768     return v;

   769 }

   770 

   771 /* get mode spec after qualifier */

   772 

   773 /**/

   774 static zlong

   775 qgetmodespec(char **s)

   776 {

   777     zlong yes = 0, no = 0, val, mask, t;

   778     char *p = *s, c, how, end;

   779 

   780     if ((c = *p) == '=' || c == Equals || c == '+' || c == '-' ||

   781 	c == '?' || c == Quest || (c >= '0' && c <= '7')) {

   782 	end = 0;

   783 	c = 0;

   784     } else {

   785 	end = (c == '<' ? '>' :

   786 	       (c == '[' ? ']' :

   787 		(c == '{' ? '}' :

   788 		 (c == Inang ? Outang :

   789 		  (c == Inbrack ? Outbrack :

   790 		   (c == Inbrace ? Outbrace : c))))));

   791 	p++;

   792     }

   793     do {

   794 	mask = 0;

   795 	while (((c = *p) == 'u' || c == 'g' || c == 'o' || c == 'a') && end) {

   796 	    switch (c) {

   797 	    case 'o': mask |= 01007; break;

   798 	    case 'g': mask |= 02070; break;

   799 	    case 'u': mask |= 04700; break;

   800 	    case 'a': mask |= 07777; break;

   801 	    }

   802 	    p++;

   803 	}

   804 	how = ((c == '+' || c == '-') ? c : '=');

   805 	if (c == '+' || c == '-' || c == '=' || c == Equals)

   806 	    p++;

   807 	val = 0;

   808 	if (mask) {

   809 	    while ((c = *p++) != ',' && c != end) {

   810 		switch (c) {

   811 		case 'x': val |= 00111; break;

   812 		case 'w': val |= 00222; break;

   813 		case 'r': val |= 00444; break;

   814 		case 's': val |= 06000; break;

   815 		case 't': val |= 01000; break;

   816 		case '0': case '1': case '2': case '3':

   817 		case '4': case '5': case '6': case '7':

   818 		    t = ((zlong) c - '0');

   819 		    val |= t | (t << 3) | (t << 6);

   820 		    break;

   821 		default:

   822 		    zerr("invalid mode specification", NULL, 0);

   823 		    return 0;

   824 		}

   825 	    }

   826 	    if (how == '=' || how == '+') {

   827 		yes |= val & mask;

   828 		val = ~val;

   829 	    }

   830 	    if (how == '=' || how == '-')

   831 		no |= val & mask;

   832 	} else if (!(end && c == end) && c != ',' && c) {

   833 	    t = 07777;

   834 	    while ((c = *p) == '?' || c == Quest ||

   835 		   (c >= '0' && c <= '7')) {

   836 		if (c == '?' || c == Quest) {

   837 		    t = (t << 3) | 7;

   838 		    val <<= 3;

   839 		} else {

   840 		    t <<= 3;

   841 		    val = (val << 3) | ((zlong) c - '0');

   842 		}

   843 		p++;

   844 	    }

   845 	    if (end && c != end && c != ',') {

   846 		zerr("invalid mode specification", NULL, 0);

   847 		return 0;

   848 	    }

   849 	    if (how == '=') {

   850 		yes = (yes & ~t) | val;

   851 		no = (no & ~t) | (~val & ~t);

   852 	    } else if (how == '+')

   853 		yes |= val;

   854 	    else

   855 		no |= val;

   856 	} else {

   857 	    zerr("invalid mode specification", NULL, 0);

   858 	    return 0;

   859         }

   860     } while (end && c != end);

   861 

   862     *s = p;

   863     return ((yes & 07777) | ((no & 07777) << 12));

   864 }

   865 

   866 static int

   867 gmatchcmp(Gmatch a, Gmatch b)

   868 {

   869     int i, *s;

   870     off_t r = 0L;

   871 

   872     for (i = gf_nsorts, s = gf_sortlist; i; i--, s++) {

   873 	switch (*s & ~GS_DESC) {

   874 	case GS_NAME:

   875 	    if (gf_numsort)

   876 	    	r = nstrpcmp(&b->name, &a->name);

   877 	    else

   878 	    	r = strpcmp(&b->name, &a->name);

   879 	    break;

   880 	case GS_DEPTH:

   881 	    {

   882 		char *aptr = a->name, *bptr = b->name;

   883 		int slasha = 0, slashb = 0;

   884 		/* Count slashes.  Trailing slashes don't count. */

   885 		while (*aptr && *aptr == *bptr)

   886 		    aptr++, bptr++;

   887 		if (*aptr)

   888 		    for (; aptr[1]; aptr++)

   889 			if (*aptr == '/') {

   890 			    slasha = 1;

   891 			    break;

   892 			}

   893 		if (*bptr)

   894 		    for (; bptr[1]; bptr++)

   895 			if (*bptr == '/') {

   896 			    slashb = 1;

   897 			    break;

   898 			}

   899 		r = slasha - slashb;

   900 	    }

   901 	    break;

   902 	case GS_SIZE:

   903 	    r = b->size - a->size;

   904 	    break;

   905 	case GS_ATIME:

   906 	    r = a->atime - b->atime;

   907 	    break;

   908 	case GS_MTIME:

   909 	    r = a->mtime - b->mtime;

   910 	    break;

   911 	case GS_CTIME:

   912 	    r = a->ctime - b->ctime;

   913 	    break;

   914 	case GS_LINKS:

   915 	    r = b->links - a->links;

   916 	    break;

   917 	case GS__SIZE:

   918 	    r = b->_size - a->_size;

   919 	    break;

   920 	case GS__ATIME:

   921 	    r = a->_atime - b->_atime;

   922 	    break;

   923 	case GS__MTIME:

   924 	    r = a->_mtime - b->_mtime;

   925 	    break;

   926 	case GS__CTIME:

   927 	    r = a->_ctime - b->_ctime;

   928 	    break;

   929 	case GS__LINKS:

   930 	    r = b->_links - a->_links;

   931 	    break;

   932 	}

   933 	if (r)

   934 	    return (int) ((*s & GS_DESC) ? -r : r);

   935     }

   936     return 0;

   937 }

   938 

   939 /*

   940  * Duplicate a list of qualifiers using the `next' linkage (not the

   941  * `or' linkage).  Return the head element and set *last (if last non-NULL)

   942  * to point to the last element of the new list.  All allocation is on the

   943  * heap (or off the heap?)

   944  */

   945 static struct qual *dup_qual_list(struct qual *orig, struct qual **lastp)

   946 {

   947     struct qual *qfirst = NULL, *qlast = NULL;

   948 

   949     while (orig) {

   950 	struct qual *qnew = (struct qual *)zhalloc(sizeof(struct qual));

   951 	*qnew = *orig;

   952 	qnew->next = qnew->or = NULL;

   953 

   954 	if (!qfirst)

   955 	    qfirst = qnew;

   956 	if (qlast)

   957 	    qlast->next = qnew;

   958 	qlast = qnew;

   959 

   960 	orig = orig->next;

   961     }

   962 

   963     if (lastp)

   964 	*lastp = qlast;

   965     return qfirst;

   966 }

   967 

   968 /* Main entry point to the globbing code for filename globbing. *

   969  * np points to a node in the list list which will be expanded  *

   970  * into a series of nodes.                                      */

   971 

   972 /**/

   973 void

   974 zglob(LinkList list, LinkNode np, int nountok)

   975 {

   976     struct qual *qo, *qn, *ql;

   977     LinkNode node = prevnode(np);

   978     char *str;				/* the pattern                   */

   979     int sl;				/* length of the pattern         */

   980     Complist q;				/* pattern after parsing         */

   981     char *ostr = (char *)getdata(np);	/* the pattern before the parser */

   982 					/* chops it up                   */

   983     int first = 0, end = -1;		/* index of first match to return */

   984 					/* and index+1 of the last match */

   985     struct globdata saved;		/* saved glob state              */

   986     int nobareglob = !isset(BAREGLOBQUAL);

   987 

   988     if (unset(GLOBOPT) || !haswilds(ostr)) {

   989 	if (!nountok)

   990 	    untokenize(ostr);

   991 	return;

   992     }

   993     save_globstate(saved);

   994 

   995     str = dupstring(ostr);

   996     uremnode(list, np);

   997 

   998     /* quals will hold the complete list of qualifiers (file static). */

   999     quals = NULL;

  1000     /*

  1001      * qualct and qualorct indicate we have qualifiers in the last

  1002      * alternative, or a set of alternatives, respectively.  They

  1003      * are not necessarily an accurate count, however.

  1004      */

  1005     qualct = qualorct = 0;

  1006     /*

  1007      * colonmod is a concatenated list of all colon modifiers found in

  1008      * all sets of qualifiers.

  1009      */

  1010     colonmod = NULL;

  1011     /* The gf_* flags are qualifiers which are applied globally. */

  1012     gf_nullglob = isset(NULLGLOB);

  1013     gf_markdirs = isset(MARKDIRS);

  1014     gf_listtypes = gf_follow = 0;

  1015     gf_noglobdots = unset(GLOBDOTS);

  1016     gf_numsort = isset(NUMERICGLOBSORT);

  1017     gf_sorts = gf_nsorts = 0;

  1018 

  1019     /* Check for qualifiers */

  1020     while (!nobareglob || isset(EXTENDEDGLOB)) {

  1021 	struct qual *newquals;

  1022 	char *s;

  1023 	int sense, paren;

  1024 	off_t data;

  1025 	char *sdata, *newcolonmod;

  1026 	int (*func) _((char *, Statptr, off_t, char *));

  1027 

  1028 	/*

  1029 	 * Initialise state variables for current file pattern.

  1030 	 * newquals is the root for the linked list of all qualifiers.

  1031 	 * qo is the root of the current list of alternatives.

  1032 	 * ql is the end of the current alternative where the `next' will go.

  1033 	 * qn is the current qualifier node to be added.

  1034 	 *

  1035 	 * Here is an attempt at a diagram.  An `or' is added horizontally

  1036 	 * to the top line, a `next' at the bottom of the right hand line.

  1037 	 * `qn' is usually NULL unless a new `or' has just been added.

  1038 	 *

  1039 	 * quals -> x  -> x -> qo

  1040 	 *          |     |    |

  1041 	 *          x     x    x

  1042 	 *          |          |

  1043 	 *          x          ql

  1044 	 *

  1045 	 * In fact, after each loop the complete set is in the file static

  1046 	 * `quals'.  Then, if we have a second set of qualifiers, we merge

  1047 	 * the lists together.  This is only tricky if one or both have an

  1048 	 * `or' in them; then we need to distribute over all alternatives.

  1049 	 */

  1050 	newquals = qo = qn = ql = NULL;

  1051 

  1052 	sl = strlen(str);

  1053 	if (str[sl - 1] != Outpar)

  1054 	    break;

  1055 

  1056 	/* Check these are really qualifiers, not a set of *

  1057 	 * alternatives or exclusions.  We can be more     *

  1058 	 * lenient with an explicit (#q) than with a bare  *

  1059 	 * set of qualifiers.                              */

  1060 	paren = 0;

  1061 	for (s = str + sl - 2; *s && (*s != Inpar || paren); s--) {

  1062 	    switch (*s) {

  1063 	    case Outpar:

  1064 		paren++; /*FALLTHROUGH*/

  1065 	    case Bar:

  1066 		nobareglob = 1;

  1067 		break;

  1068 	    case Tilde:

  1069 		if (isset(EXTENDEDGLOB))

  1070 		    nobareglob = 1;

  1071 		break;

  1072 	    case Inpar:

  1073 		paren--;

  1074 		break;

  1075 	    }

  1076 	}

  1077 	if (*s != Inpar)

  1078 	    break;

  1079 	if (isset(EXTENDEDGLOB) && s[1] == Pound) {

  1080 	    if (s[2] == 'q') {

  1081 		*s = 0;

  1082 		s += 2;

  1083 	    } else

  1084 		break;

  1085 	} else if (nobareglob)

  1086 	    break;

  1087 

  1088 	/* Real qualifiers found. */

  1089 	nobareglob = 1;

  1090 	sense = 0;	   /* bit 0 for match (0)/don't match (1)   */

  1091 			   /* bit 1 for follow links (2), don't (0) */

  1092 	data = 0;	   /* Any numerical argument required       */

  1093 	sdata = NULL;	   /* Any list argument required            */

  1094 	newcolonmod = NULL; /* Contains trailing colon modifiers    */

  1095 

  1096 	str[sl-1] = 0;

  1097 	*s++ = 0;

  1098 	while (*s && !newcolonmod) {

  1099 	    func = (int (*) _((char *, Statptr, off_t, char *)))0;

  1100 	    if (idigit(*s)) {

  1101 		/* Store numeric argument for qualifier */

  1102 		func = qualflags;

  1103 		data = 0;

  1104 		sdata = NULL;

  1105 		while (idigit(*s))

  1106 		    data = data * 010 + (*s++ - '0');

  1107 	    } else if (*s == ',') {

  1108 		/* A comma separates alternative sets of qualifiers */

  1109 		s++;

  1110 		sense = 0;

  1111 		if (qualct) {

  1112 		    qn = (struct qual *)hcalloc(sizeof *qn);

  1113 		    qo->or = qn;

  1114 		    qo = qn;

  1115 		    qualorct++;

  1116 		    qualct = 0;

  1117 		    ql = NULL;

  1118 		}

  1119 	    } else {

  1120 		switch (*s++) {

  1121 		case ':':

  1122 		    /* Remaining arguments are history-type     *

  1123 		     * colon substitutions, handled separately. */

  1124 		    newcolonmod = s - 1;

  1125 		    untokenize(newcolonmod);

  1126 		    if (colonmod) {

  1127 			/* remember we're searching backwards */

  1128 			colonmod = dyncat(newcolonmod, colonmod);

  1129 		    } else

  1130 			colonmod = newcolonmod;

  1131 		    break;

  1132 		case Hat:

  1133 		case '^':

  1134 		    /* Toggle sense:  go from positive to *