home *** CD-ROM | disk | FTP | other *** search
/ Big Green CD 8 / BGCD_8_Dev.iso / NEXTSTEP / UNIX / Shells / zsh-3.0.5-MIHS / src / Src / glob.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-09-25  |  55.1 KB  |  2,400 lines
  1. /*
  2.  * $Id: glob.c,v 2.35 1996/10/15 20:16:35 hzoli Exp $
  3.  *
  4.  * glob.c - filename generation
  5.  *
  6.  * This file is part of zsh, the Z shell.
  7.  *
  8.  * Copyright (c) 1992-1996 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.h"
  33.  
  34. static int
  35. exists(char *s)
  36. {
  37.     char *us = unmeta(s);
  38.  
  39.     return access(us,0) == 0 || readlink(us,NULL,0) == 0;
  40. }
  41.  
  42. static int mode;        /* != 0 if we are parsing glob patterns */
  43. static int pathpos;        /* position in pathbuf                  */
  44. static int matchsz;        /* size of matchbuf                     */
  45. static int matchct;        /* number of matches found              */
  46. static char pathbuf[PATH_MAX];    /* pathname buffer                      */
  47. static char **matchbuf;        /* array of matches                     */
  48. static char **matchptr;        /* &matchbuf[matchct]                   */
  49. static char *colonmod;        /* colon modifiers in qualifier list    */
  50. static ino_t old_ino;        /* ) remember old file and              */
  51. static dev_t old_dev;        /* ) position in path in case           */
  52. static int old_pos;        /* ) matching multiple directories      */
  53.  
  54. typedef struct stat *Statptr;     /* This makes the Ultrix compiler happy.  Go figure. */
  55.  
  56. /* modifier for unit conversions */
  57.  
  58. #define TT_DAYS 0
  59. #define TT_HOURS 1
  60. #define TT_MINS 2
  61. #define TT_WEEKS 3
  62. #define TT_MONTHS 4
  63.  
  64. #define TT_BYTES 0
  65. #define TT_POSIX_BLOCKS 1
  66. #define TT_KILOBYTES 2
  67. #define TT_MEGABYTES 3
  68.  
  69. /* max # of qualifiers */
  70.  
  71. typedef int (*TestMatchFunc) _((struct stat *, long));
  72.  
  73. struct qual {
  74.     struct qual *next;        /* Next qualifier, must match                */
  75.     struct qual *or;        /* Alternative set of qualifiers to match    */
  76.     TestMatchFunc func;        /* Function to call to test match            */
  77.     long data;            /* Argument passed to function               */
  78.     int sense;            /* Whether asserting or negating             */
  79.     int amc;            /* Flag for which time to test (a, m, c)     */
  80.     int range;            /* Whether to test <, > or = (as per signum) */
  81.     int units;            /* Multiplier for time or size, respectively */
  82. };
  83.  
  84. /* Qualifiers pertaining to current pattern */
  85. static struct qual *quals;
  86.  
  87. /* Other state values for current pattern */
  88. static int qualct, qualorct;
  89. static int range, amc, units;
  90. static int gf_nullglob, gf_markdirs, gf_noglobdots, gf_listtypes, gf_follow;
  91.  
  92. /* Prefix, suffix for doing zle trickery */
  93. char *glob_pre, *glob_suf;
  94.  
  95. /* pathname component in filename patterns */
  96.  
  97. struct complist {
  98.     Complist next;
  99.     Comp comp;
  100.     int closure;        /* 1 if this is a (foo/)# */
  101.     int follow;         /* 1 to go thru symlinks */
  102. };
  103. struct comp {
  104.     Comp left, right, next, exclude;
  105.     char *str;
  106.     int stat;
  107. };
  108.  
  109. /* Type of Comp:  a closure with one or two #'s, the end of a *
  110.  * pattern or path component, a piece of path to be added.    */
  111. #define C_ONEHASH    1
  112. #define C_TWOHASH    2
  113. #define C_CLOSURE    (C_ONEHASH|C_TWOHASH)
  114. #define C_LAST        4
  115. #define C_PATHADD    8
  116.  
  117. /* Test macros for the above */
  118. #define CLOSUREP(c)    (c->stat & C_CLOSURE)
  119. #define ONEHASHP(c)    (c->stat & C_ONEHASH)
  120. #define TWOHASHP(c)    (c->stat & C_TWOHASH)
  121. #define LASTP(c)    (c->stat & C_LAST)
  122. #define PATHADDP(c)    (c->stat & C_PATHADD)
  123.  
  124. /* Main entry point to the globbing code for filename globbing. *
  125.  * np points to a node in the list list which will be expanded  *
  126.  * into a series of nodes.                                      */
  127.  
  128. /**/
  129. void
  130. glob(LinkList list, LinkNode np)
  131. {
  132.     struct qual *qo, *qn, *ql;
  133.     LinkNode node = prevnode(np);
  134.     char *str;                /* the pattern                   */
  135.     int sl;                /* length of the pattern         */
  136.     Complist q;                /* pattern after parsing         */
  137.     char *ostr = (char *)getdata(np);    /* the pattern before the parser */
  138.                     /* chops it up                   */
  139.  
  140.     MUSTUSEHEAP("glob");
  141.     if (unset(GLOBOPT) || !(str = haswilds(ostr))) {
  142.     untokenize(ostr);
  143.     return;
  144.     }
  145.     if (*str == ':' && str[-1] == Inpar) {
  146.     str[-1] = '\0';
  147.     modify((char **) &getdata(np), &str);
  148.     return;
  149.     }
  150.     str = dupstring(ostr);
  151.     sl = strlen(str);
  152.     uremnode(list, np);
  153.  
  154.     /* Initialise state variables for current file pattern */
  155.     qo = qn = quals = ql = NULL;
  156.     qualct = qualorct = 0;
  157.     colonmod = NULL;
  158.     gf_nullglob = isset(NULLGLOB);
  159.     gf_markdirs = isset(MARKDIRS);
  160.     gf_listtypes = gf_follow = 0;
  161.     gf_noglobdots = unset(GLOBDOTS);
  162.     if (str[sl - 1] == Outpar) {    /* check for qualifiers */
  163.     char *s;
  164.     int sense = 0;            /* bit 0 for match (0)/don't match (1)   */
  165.                     /* bit 1 for follow links (2), don't (0) */
  166.     long data = 0;            /* Any numerical argument required       */
  167.  
  168.     int (*func) _((Statptr, long));
  169.  
  170.     /* Check these are really qualifiers, not a set of *
  171.      * alternatives or exclusions                      */
  172.     for (s = str + sl - 2; s != str; s--)
  173.         if (*s == Bar || *s == Outpar || *s == Inpar
  174.         || (isset(EXTENDEDGLOB) && *s == Tilde))
  175.         break;
  176.     if (*s == Inpar) {
  177.         /* Real qualifiers found. */
  178.         *s++ = '\0';
  179.         while (*s != Outpar && !colonmod) {
  180.         func = (int (*) _((Statptr, long)))0;
  181.         if (idigit(*s)) {
  182.             /* Store numeric argument for qualifier */
  183.             func = qualflags;
  184.             data = 0;
  185.             while (idigit(*s))
  186.             data = data * 010 + (*s++ - '0');
  187.         } else if (*s == ',') {
  188.             /* A comma separates alternative sets of qualifiers */
  189.             s++;
  190.             sense = 0;
  191.             if (qualct) {
  192.             qn = (struct qual *)hcalloc(sizeof *qn);
  193.             qo->or = qn;
  194.             qo = qn;
  195.             qualorct++;
  196.             qualct = 0;
  197.             ql = NULL;
  198.             }
  199.         } else
  200.             switch (*s++) {
  201.             case ':':
  202.             /* Remaining arguments are history-type     *
  203.              * colon substitutions, handled separately. */
  204.             colonmod = s - 1;
  205.             break;
  206.             case Hat:
  207.             case '^':
  208.             /* Toggle sense:  go from positive to *
  209.              * negative match and vice versa.     */
  210.             sense ^= 1;
  211.             break;
  212.             case '-':
  213.             /* Toggle matching of symbolic links */
  214.             sense ^= 2;
  215.             break;
  216. #ifdef S_IFLNK
  217.             case '@':
  218.             /* Match symbolic links */
  219.             func = qualmode;
  220.             data = S_IFLNK;
  221.             break;
  222. #endif
  223. #ifdef S_IFSOCK
  224.             case Equals:
  225.             case '=':
  226.             /* Match sockets */
  227.             func = qualmode;
  228.             data = S_IFSOCK;
  229.             break;
  230. #endif
  231. #ifdef S_IFIFO
  232.             case 'p':
  233.             /* Match named pipes */
  234.             func = qualmode;
  235.             data = S_IFIFO;
  236.             break;
  237. #endif
  238.             case '/':
  239.             /* Match directories */
  240.             func = qualmode;
  241.             data = S_IFDIR;
  242.             break;
  243.             case '.':
  244.             /* Match regular files */
  245.             func = qualmode;
  246.             data = S_IFREG;
  247.             break;
  248.             case '%':
  249.             /* Match special files: block, *
  250.              * character or any device     */
  251.             if (*s == 'b')
  252.                 s++, func = qualisblk;
  253.             else if (*s == 'c')
  254.                 s++, func = qualischar;
  255.             else
  256.                 func = qualisdev;
  257.             break;
  258.             case Star:
  259.             /* Match executable plain files */
  260.             func = qualiscom;
  261.             break;
  262.             case 'R':
  263.             /* Match world-readable files */
  264.             func = qualflags;
  265.             data = 0004;
  266.             break;
  267.             case 'W':
  268.             /* Match world-writeable files */
  269.             func = qualflags;
  270.             data = 0002;
  271.             break;
  272.             case 'X':
  273.             /* Match world-executable files */
  274.             func = qualflags;
  275.             data = 0001;
  276.             break;
  277.             case 'A':
  278.             func = qualflags;
  279.             data = 0040;
  280.             break;
  281.             case 'I':
  282.             func = qualflags;
  283.             data = 0020;
  284.             break;
  285.             case 'E':
  286.             func = qualflags;
  287.             data = 0010;
  288.             break;
  289.             case 'r':
  290.             /* Match files readable by current process */
  291.             func = qualflags;
  292.             data = 0400;
  293.             break;
  294.             case 'w':
  295.             /* Match files writeable by current process */
  296.             func = qualflags;
  297.             data = 0200;
  298.             break;
  299.             case 'x':
  300.             /* Match files executable by current process */
  301.             func = qualflags;
  302.             data = 0100;
  303.             break;
  304.             case 's':
  305.             /* Match setuid files */
  306.             func = qualflags;
  307.             data = 04000;
  308.             break;
  309.             case 'S':
  310.             /* Match setgid files */
  311.             func = qualflags;
  312.             data = 02000;
  313.             break;
  314.             case 't':
  315.             func = qualflags;
  316.             data = 01000;
  317.             break;
  318.             case 'd':
  319.             /* Match device files by device number  *
  320.              * (as given by stat's st_dev element). */
  321.             func = qualdev;
  322.             data = qgetnum(&s);
  323.             break;
  324.             case 'l':
  325.             /* Match files with the given no. of hard links */
  326.             func = qualnlink;
  327.             amc = -1;
  328.             goto getrange;
  329.             case 'U':
  330.             /* Match files owned by effective user ID */
  331.             func = qualuid;
  332.             data = geteuid();
  333.             break;
  334.             case 'G':
  335.             /* Match files owned by effective group ID */
  336.             func = qualgid;
  337.             data = getegid();
  338.             break;
  339.             case 'u':
  340.             /* Match files owned by given user id */
  341.             func = qualuid;
  342.             /* either the actual uid... */
  343.             if (idigit(*s))
  344.                 data = qgetnum(&s);
  345.             else {
  346.                 /* ... or a user name */
  347.                 struct passwd *pw;
  348.                 char sav, *tt;
  349.  
  350.                 /* Find matching delimiters */
  351.                 tt = get_strarg(s);
  352.                 if (!*tt) {
  353.                 zerr("missing end of name",
  354.                      NULL, 0);
  355.                 data = 0;
  356.                 } else {
  357.                 sav = *tt;
  358.                 *tt = '\0';
  359.  
  360.                 if ((pw = getpwnam(s + 1)))
  361.                     data = pw->pw_uid;
  362.                 else {
  363.                     zerr("unknown user", NULL, 0);
  364.                     data = 0;
  365.                 }
  366.                 if ((*tt = sav) != Outpar)
  367.                     s = tt + 1;
  368.                 else
  369.                     s = tt;
  370.                 }
  371.             }
  372.             break;
  373.             case 'g':
  374.             /* Given gid or group id... works like `u' */
  375.             func = qualgid;
  376.             /* either the actual gid... */
  377.             if (idigit(*s))
  378.                 data = qgetnum(&s);
  379.             else {
  380.                 /* ...or a delimited group name. */
  381.                 struct group *gr;
  382.                 char sav, *tt;
  383.  
  384.                 tt = get_strarg(s);
  385.                 if (!*tt) {
  386.                 zerr("missing end of name",
  387.                      NULL, 0);
  388.                 data = 0;
  389.                 } else {
  390.                 sav = *tt;
  391.                 *tt = '\0';
  392.  
  393.                 if ((gr = getgrnam(s + 1)))
  394.                     data = gr->gr_gid;
  395.                 else {
  396.                     zerr("unknown group", NULL, 0);
  397.                     data = 0;
  398.                 }
  399.                 if ((*tt = sav) != Outpar)
  400.                     s = tt + 1;
  401.                 else
  402.                     s = tt;
  403.                 }
  404.             }
  405.             break;
  406.             case 'o':
  407.             /* Match octal mode of file exactly. *
  408.              * Currently undocumented.           */
  409.             func = qualeqflags;
  410.             data = qgetoctnum(&s);
  411.             break;
  412.             case 'M':
  413.             /* Mark directories with a / */
  414.             if ((gf_markdirs = !(sense & 1)))
  415.                 gf_follow = sense & 2;
  416.             break;
  417.             case 'T':
  418.             /* Mark types in a `ls -F' type fashion */
  419.             if ((gf_listtypes = !(sense & 1)))
  420.                 gf_follow = sense & 2;
  421.             break;
  422.             case 'N':
  423.             /* Nullglob:  remove unmatched patterns. */
  424.             gf_nullglob = !(sense & 1);
  425.             break;
  426.             case 'D':
  427.             /* Glob dots: match leading dots implicitly */
  428.             gf_noglobdots = sense & 1;
  429.             break;
  430.             case 'a':
  431.             /* Access time in given range */
  432.             amc = 0;
  433.             func = qualtime;
  434.             goto getrange;
  435.             case 'm':
  436.             /* Modification time in given range */
  437.             amc = 1;
  438.             func = qualtime;
  439.             goto getrange;
  440.             case 'c':
  441.             /* Inode creation time in given range */
  442.             amc = 2;
  443.             func = qualtime;
  444.             goto getrange;
  445.             case 'L':
  446.             /* File size (Length) in given range */
  447.             func = qualsize;
  448.             amc = -1;
  449.             /* Get size multiplier */
  450.             units = TT_BYTES;
  451.             if (*s == 'p' || *s == 'P')
  452.                 units = TT_POSIX_BLOCKS, ++s;
  453.             else if (*s == 'k' || *s == 'K')
  454.                 units = TT_KILOBYTES, ++s;
  455.             else if (*s == 'm' || *s == 'M')
  456.                 units = TT_MEGABYTES, ++s;
  457.               getrange:
  458.             /* Get time multiplier */
  459.             if (amc >= 0) {
  460.                 units = TT_DAYS;
  461.                 if (*s == 'h')
  462.                 units = TT_HOURS, ++s;
  463.                 else if (*s == 'm')
  464.                 units = TT_MINS, ++s;
  465.                 else if (*s == 'w')
  466.                 units = TT_WEEKS, ++s;
  467.                 else if (*s == 'M')
  468.                 units = TT_MONTHS, ++s;
  469.             }
  470.             /* See if it's greater than, equal to, or less than */
  471.             if ((range = *s == '+' ? 1 : *s == '-' ? -1 : 0))
  472.                 ++s;
  473.             data = qgetnum(&s);
  474.             break;
  475.  
  476.             default:
  477.             zerr("unknown file attribute", NULL, 0);
  478.             return;
  479.             }
  480.         if (func) {
  481.             /* Requested test is performed by function func */
  482.             if (!qn)
  483.             qn = (struct qual *)hcalloc(sizeof *qn);
  484.             if (ql)
  485.             ql->next = qn;
  486.             ql = qn;
  487.             if (!quals)
  488.             quals = qo = qn;
  489.             qn->func = func;
  490.             qn->sense = sense;
  491.             qn->data = data;
  492.             qn->range = range;
  493.             qn->units = units;
  494.             qn->amc = amc;
  495.             qn = NULL;
  496.             qualct++;
  497.         }
  498.         if (errflag)
  499.             return;
  500.         }
  501.     }
  502.     }
  503.     if (*str == '/') {        /* pattern has absolute path */
  504.     str++;
  505.     pathbuf[0] = '/';
  506.     pathbuf[pathpos = 1] = '\0';
  507.     } else            /* pattern is relative to pwd */
  508.     pathbuf[pathpos = 0] = '\0';
  509.     q = parsepat(str);
  510.     if (!q || errflag) {    /* if parsing failed */
  511.     if (unset(BADPATTERN)) {
  512.         untokenize(ostr);
  513.         insertlinknode(list, node, ostr);
  514.         return;
  515.     }
  516.     errflag = 0;
  517.     zerr("bad pattern: %s", ostr, 0);
  518.     return;
  519.     }
  520.  
  521.     /* Initialise receptacle for matched files, *
  522.      * expanded by insert() where necessary.    */
  523.     matchptr = matchbuf = (char **)zalloc((matchsz = 16) * sizeof(char *));
  524.     matchct = 0;
  525.  
  526.     /* Initialise memory of last file matched */
  527.     old_ino = (ino_t) 0;
  528.     old_dev = (dev_t) 0;
  529.     old_pos = -1;
  530.  
  531.     /* The actual processing takes place here: matches go into  *
  532.      * matchbuf.  This is the only top-level call to scanner(). */
  533.     scanner(q);
  534.  
  535.     /* Deal with failures to match depending on options */
  536.     if (matchct)
  537.     badcshglob |= 2;    /* at least one cmd. line expansion O.K. */
  538.     else if (!gf_nullglob)
  539.     if (isset(CSHNULLGLOB)) {
  540.         badcshglob |= 1;    /* at least one cmd. line expansion failed */
  541.     } else if (isset(NOMATCH)) {
  542.         zerr("no matches found: %s", ostr, 0);
  543.         free(matchbuf);
  544.         return;
  545.     } else {
  546.         /* treat as an ordinary string */
  547.         untokenize(*matchptr++ = dupstring(ostr));
  548.         matchct = 1;
  549.     }
  550.     /* Sort arguments in to lexical (and possibly numeric) order. *
  551.      * This is reversed to facilitate insertion into the list.    */
  552.     qsort((void *) & matchbuf[0], matchct, sizeof(char *),
  553.            (int (*) _((const void *, const void *)))notstrcmp);
  554.  
  555.     matchptr = matchbuf;
  556.     while (matchct--)        /* insert matches in the arg list */
  557.     insertlinknode(list, node, *matchptr++);
  558.     free(matchbuf);
  559. }
  560.  
  561. /* get number after qualifier */
  562.  
  563. /**/
  564. long
  565. qgetnum(char **s)
  566. {
  567.     long v = 0;
  568.  
  569.     if (!idigit(**s)) {
  570.     zerr("number expected", NULL, 0);
  571.     return 0;
  572.     }
  573.     while (idigit(**s))
  574.     v = v * 10 + *(*s)++ - '0';
  575.     return v;
  576. }
  577.  
  578. /* get octal number after qualifier */
  579.  
  580. /**/
  581. long
  582. qgetoctnum(char **s)
  583. {
  584.     long v = 0;
  585.  
  586.     if (!idigit(**s)) {
  587.     zerr("octal number expected", NULL, 0);
  588.     return 0;
  589.     }
  590.     while (**s >= '0' && **s <= '7')
  591.     v = v * 010 + *(*s)++ - '0';
  592.     return v;
  593. }
  594.  
  595. /* Return the order of two strings, taking into account *
  596.  * possible numeric order if NUMERICGLOBSORT is set.    *
  597.  * The comparison here is reversed.                     */
  598.  
  599. /**/
  600. int
  601. notstrcmp(char **a, char **b)
  602. {
  603.     char *c = *b, *d = *a;
  604.     int cmp;
  605.  
  606. #ifdef HAVE_STRCOLL
  607.     cmp = strcoll(c, d);
  608. #endif
  609.     for (; *c == *d && *c; c++, d++);
  610. #ifndef HAVE_STRCOLL
  611.     cmp = (int)STOUC(*c) - (int)STOUC(*d);
  612. #endif
  613.     if (isset(NUMERICGLOBSORT) && (idigit(*c) || idigit(*d))) {
  614.     for (; c > *b && idigit(c[-1]); c--, d--);
  615.     if (idigit(*c) && idigit(*d)) {
  616.         while (*c == '0')
  617.         c++;
  618.         while (*d == '0')
  619.         d++;
  620.         for (; idigit(*c) && *c == *d; c++, d++);
  621.         if (idigit(*c) || idigit(*d)) {
  622.         cmp = (int)STOUC(*c) - (int)STOUC(*d);
  623.         while (idigit(*c) && idigit(*d))
  624.             c++, d++;
  625.         if (idigit(*c) && !idigit(*d))
  626.             return 1;
  627.         if (idigit(*d) && !idigit(*c))
  628.             return -1;
  629.         }
  630.     }
  631.     }
  632.     return cmp;
  633. }
  634.  
  635. /* add a match to the list */
  636.  
  637. /**/
  638. void
  639. insert(char *s)
  640. {
  641.     struct stat buf, buf2, *bp;
  642.     char *news = s;
  643.     int statted = 0;
  644.  
  645.     if (gf_listtypes || gf_markdirs) {
  646.     /* Add the type marker to the end of the filename */
  647.     statted = -1;
  648.     if (!lstat(unmeta(s), &buf)) {
  649.         mode_t mode = buf.st_mode;
  650.         statted = 1;
  651.         if (gf_follow) {
  652.         if (!S_ISLNK(mode) || stat(unmeta(s), &buf2))
  653.             memcpy(&buf2, &buf, sizeof(buf));
  654.         statted = 2;
  655.         mode = buf2.st_mode;
  656.         }
  657.         if (gf_listtypes || S_ISDIR(mode)) {
  658.         int ll = strlen(s);
  659.  
  660.         news = (char *)ncalloc(ll + 2);
  661.         strcpy(news, s);
  662.         news[ll] = file_type(buf.st_mode);
  663.         news[ll + 1] = '\0';
  664.         }
  665.     }
  666.     }
  667.     if (qualct || qualorct) {
  668.     /* Go through the qualifiers, rejecting the file if appropriate */
  669.     struct qual *qo, *qn;
  670.     int t = 0;        /* reject file unless t is set */
  671.  
  672.     if (statted >= 0 && (statted || !lstat(unmeta(s), &buf))) {
  673.         for (qo = quals; qo && !t; qo = qo->or) {
  674.  
  675.         t = 1;
  676.         for (qn = qo; t && qn && qn->func; qn = qn->next) {
  677.             range = qn->range;
  678.             amc = qn->amc;
  679.             units = qn->units;
  680.             if ((qn->sense & 2) && statted != 2) {
  681.             /* If (sense & 2), we're following links */
  682.             if (!S_ISLNK(buf.st_mode) || stat(unmeta(s), &buf2))
  683.                 memcpy(&buf2, &buf, sizeof(buf));
  684.             statted = 2;
  685.             }
  686.             bp = (qn->sense & 2) ? &buf2 : &buf;
  687.             /* Reject the file if the function returned zero *
  688.              * and the sense was positive (sense&1 == 0), or *
  689.              * vice versa.                                   */
  690.             if ((!((qn->func) (bp, qn->data)) ^ qn->sense) & 1) {
  691.             t = 0;
  692.             break;
  693.             }
  694.         }
  695.         }
  696.     }
  697.     if (!t)
  698.         return;
  699.     }
  700.     if (colonmod) {
  701.     /* Handle the remainder of the qualifer:  e.g. (:r:s/foo/bar/). */
  702.     s = colonmod;
  703.     modify(&news, &s);
  704.     }
  705.     *matchptr++ = news;
  706.     if (++matchct == matchsz) {
  707.     matchbuf = (char **)realloc((char *)matchbuf,
  708.                     sizeof(char **) * (matchsz *= 2));
  709.  
  710.     matchptr = matchbuf + matchct;
  711.     }
  712. }
  713.  
  714. /* Return the trailing character for marking file types */
  715.  
  716. /**/
  717. char
  718. file_type(mode_t filemode)
  719. {
  720.     switch (filemode & S_IFMT) {/* screw POSIX */
  721.     case S_IFDIR:
  722.     return '/';
  723. #ifdef S_IFIFO
  724.     case S_IFIFO:
  725.     return '|';
  726. #endif
  727.     case S_IFCHR:
  728.     return '%';
  729.     case S_IFBLK:
  730.     return '#';
  731. #ifdef S_IFLNK
  732.     case S_IFLNK:
  733.     return /* (access(pbuf, F_OK) == -1) ? '&' :*/ '@';
  734. #endif
  735. #ifdef S_IFSOCK
  736.     case S_IFSOCK:
  737.     return '=';
  738. #endif
  739.     default:
  740.     if (filemode & 0111)
  741.         return '*';
  742.     else
  743.         return ' ';
  744.     }
  745. }
  746.  
  747. /* check to see if str is eligible for filename generation
  748.  * It returns NULL if no wilds or modifiers found.
  749.  * If a leading % is immediately followed by a ?, that single
  750.  * ? is not treated as a wildcard.
  751.  * If str has wilds it returns a pointer to the first wildcard.
  752.  * If str has no wilds but ends in a (:...) type modifier it returns
  753.  * a pointer to the colon.
  754.  * If str has no wilds but ends in (...:...) it returns a pointer
  755.  * to the terminating null character of str.
  756.  */
  757.  
  758. /**/
  759. char *
  760. haswilds(char *str)
  761. {
  762.     char *mod = NULL;
  763.     int parlev = 0;
  764.  
  765.     if ((*str == Inbrack || *str == Outbrack) && !str[1])
  766.     return NULL;
  767.  
  768.     /* If % is immediately followed by ?, then that ? is     *
  769.      * not treated as a wildcard.  This is so you don't have *
  770.      * to escape job references such as %?foo.               */
  771.     if (str[0] == '%' && str[1] == Quest)
  772.     str[1] = '?';
  773.     for (; *str; str++)
  774.     switch (*str) {
  775.     case Inpar:
  776.         parlev++;
  777.         break;
  778.     case Outpar:
  779.         if (! --parlev && str[1])
  780.         mod = NULL;
  781.         break;
  782.     case ':':
  783.         if (parlev == 1 && !mod)
  784.         mod = str;
  785.         break;
  786.     case Bar:
  787.         if (!parlev) {
  788.         *str = '|';
  789.         break;
  790.         } /* else fall through */
  791.     case Star:
  792.     case Inbrack:
  793.     case Inang:
  794.     case Quest:
  795.         return str;
  796.     case Pound:
  797.     case Hat:
  798.         if (isset(EXTENDEDGLOB))
  799.         return str;
  800.     }
  801.     if (!mod || parlev)
  802.     return NULL;
  803.     if (mod[-1] == Inpar)
  804.     return mod;
  805.     return str;
  806. }
  807.  
  808. /* check to see if str is eligible for brace expansion */
  809.  
  810. /**/
  811. int
  812. hasbraces(char *str)
  813. {
  814.     char *lbr, *mbr, *comma;
  815.  
  816.     if (isset(BRACECCL)) {
  817.     /* In this case, any properly formed brace expression  *
  818.      * will match and expand to the characters in between. */
  819.     int bc;
  820.  
  821.     for (bc = 0; *str; ++str)
  822.         if (*str == Inbrace) {
  823.         if (!bc && str[1] == Outbrace)
  824.             *str++ = '{', *str = '}';
  825.         else
  826.             bc++;
  827.         } else if (*str == Outbrace)
  828.         if (!bc)
  829.             *str = '}';
  830.         else if (!--bc)
  831.             return 1;
  832.     return 0;
  833.     }
  834.     /* Otherwise we need to look for... */
  835.     lbr = mbr = comma = NULL;
  836.     for (;;) {
  837.     switch (*str++) {
  838.     case Inbrace:
  839.         if (!lbr) {
  840.         lbr = str - 1;
  841.         while (idigit(*str))
  842.             str++;
  843.         if (*str == '.' && str[1] == '.') {
  844.             str++;
  845.             while (idigit(*++str));
  846.             if (*str == Outbrace &&
  847.             (idigit(lbr[1]) || idigit(str[-1])))
  848.             return 1;
  849.         }
  850.         } else {
  851.         char *s = --str;
  852.  
  853.         if (skipparens(Inbrace, Outbrace, &str)) {
  854.             *lbr = *s = '{';
  855.             if (comma)
  856.             str = comma;
  857.             if (mbr && mbr < str)
  858.             str = mbr;
  859.             lbr = mbr = comma = NULL;
  860.         } else if (!mbr)
  861.             mbr = s;
  862.         }
  863.         break;
  864.     case Outbrace:
  865.         if (!lbr)
  866.         str[-1] = '}';
  867.         else if (comma)
  868.         return 1;
  869.         else {
  870.         *lbr = '{';
  871.         str[-1] = '}';
  872.         if (mbr)
  873.             str = mbr;
  874.         mbr = lbr = NULL;
  875.         }
  876.         break;
  877.     case Comma:
  878.         if (!lbr)
  879.         str[-1] = ',';
  880.         else if (!comma)
  881.         comma = str - 1;
  882.         break;
  883.     case '\0':
  884.         if (lbr)
  885.         *lbr = '{';
  886.         if (!mbr && !comma)
  887.         return 0;
  888.         if (comma)
  889.         str = comma;
  890.         if (mbr && mbr < str)
  891.         str = mbr;
  892.         lbr = mbr = comma = NULL;
  893.         break;
  894.     }
  895.     }
  896. }
  897.  
  898. /* expand stuff like >>*.c */
  899.  
  900. /**/
  901. int
  902. xpandredir(struct redir *fn, LinkList tab)
  903. {
  904.     LinkList fake;
  905.     char *nam;
  906.     struct redir *ff;
  907.     int ret = 0;
  908.  
  909.     /* Stick the name in a list... */
  910.     fake = newlinklist();
  911.     addlinknode(fake, fn->name);
  912.     /* ...which undergoes all the usual shell expansions */
  913.     prefork(fake, isset(MULTIOS) ? 0 : 4);
  914.     /* Globbing is only done for multios. */
  915.     if (!errflag && isset(MULTIOS))
  916.     globlist(fake);
  917.     if (errflag)
  918.     return 0;
  919.     if (nonempty(fake) && !nextnode(firstnode(fake))) {
  920.     /* Just one match, the usual case. */
  921.     char *s = peekfirst(fake);
  922.     fn->name = s;
  923.     untokenize(s);
  924.     if (fn->type == MERGEIN || fn->type == MERGEOUT) {
  925.         if (s[0] == '-' && !s[1])
  926.         fn->type = CLOSE;
  927.         else if (s[0] == 'p' && !s[1]) 
  928.         fn->fd2 = (fn->type == MERGEOUT) ? coprocout : coprocin;
  929.         else {
  930.         while (idigit(*s))
  931.             s++;
  932.         if (!*s && s > fn->name)
  933.             fn->fd2 = zstrtol(fn->name, NULL, 10);
  934.         else if (fn->type == MERGEIN)
  935.             zerr("file number expected", NULL, 0);
  936.         else
  937.             fn->type = ERRWRITE;
  938.         }
  939.     }
  940.     } else if (fn->type == MERGEIN)
  941.     zerr("file number expected", NULL, 0);
  942.     else {
  943.     if (fn->type == MERGEOUT)
  944.         fn->type = ERRWRITE;
  945.     while ((nam = (char *)ugetnode(fake))) {
  946.         /* Loop over matches, duplicating the *
  947.          * redirection for each file found.   */
  948.         ff = (struct redir *)alloc(sizeof *ff);
  949.         *ff = *fn;
  950.         ff->name = nam;
  951.         addlinknode(tab, ff);
  952.         ret = 1;
  953.     }
  954.     }
  955.     return ret;
  956. }
  957.  
  958. /* concatenate s1 and s2 in dynamically allocated buffer */
  959.  
  960. /**/
  961. char *
  962. dyncat(char *s1, char *s2)
  963. {
  964.     /* This version always uses space from the current heap. */
  965.     char *ptr;
  966.     int l1 = strlen(s1);
  967.  
  968.     ptr = (char *)ncalloc(l1 + strlen(s2) + 1);
  969.     strcpy(ptr, s1);
  970.     strcpy(ptr + l1, s2);
  971.     return ptr;
  972. }
  973.  
  974. /* concatenate s1, s2, and s3 in dynamically allocated buffer */
  975.  
  976. /**/
  977. char *
  978. tricat(char *s1, char *s2, char *s3)
  979. {
  980.     /* This version always uses permanently-allocated space. */
  981.     char *ptr;
  982.  
  983.     ptr = (char *)zalloc(strlen(s1) + strlen(s2) + strlen(s3) + 1);
  984.     strcpy(ptr, s1);
  985.     strcat(ptr, s2);
  986.     strcat(ptr, s3);
  987.     return ptr;
  988. }
  989.  
  990. /* brace expansion */
  991.  
  992. /**/
  993. void
  994. xpandbraces(LinkList list, LinkNode *np)
  995. {
  996.     LinkNode node = (*np), last = prevnode(node);
  997.     char *str = (char *)getdata(node), *str3 = str, *str2;
  998.     int prev, bc, comma, dotdot;
  999.  
  1000.     for (; *str != Inbrace; str++);
  1001.     /* First, match up braces and see what we have. */
  1002.     for (str2 = str, bc = comma = dotdot = 0; *str2; ++str2)
  1003.     if (*str2 == Inbrace)
  1004.         ++bc;
  1005.     else if (*str2 == Outbrace) {
  1006.         if (--bc == 0)
  1007.         break;
  1008.     } else if (bc == 1)
  1009.         if (*str2 == Comma)
  1010.         ++comma;    /* we have {foo,bar} */
  1011.         else if (*str2 == '.' && str2[1] == '.')
  1012.         dotdot++;    /* we have {num1..num2} */
  1013.     DPUTS(bc, "BUG: unmatched brace in xpandbraces()");
  1014.     if (!comma && dotdot) {
  1015.     /* Expand range like 0..10 numerically: comma or recursive
  1016.        brace expansion take precedence. */
  1017.     char *dots, *p;
  1018.     LinkNode olast = last;
  1019.     /* Get the first number of the range */
  1020.     int rstart = zstrtol(str+1,&dots,10), rend = 0, err = 0, rev = 0;
  1021.     int wid1 = (dots - str) - 1, wid2 = (str2 - dots) - 2;
  1022.     int strp = str - str3;
  1023.       
  1024.     if (dots == str + 1 || *dots != '.' || dots[1] != '.')
  1025.         err++;
  1026.     else {
  1027.         /* Get the last number of the range */
  1028.         rend = zstrtol(dots+2,&p,10);
  1029.         if (p == dots+2 || p != str2)
  1030.         err++;
  1031.     }
  1032.     if (!err) {
  1033.         /* If either no. begins with a zero, pad the output with   *
  1034.          * zeroes. Otherwise, choose a min width to suppress them. */
  1035.         int minw = (str[1] == '0') ? wid1 : (dots[2] == '0' ) ? wid2 :
  1036.         (wid2 > wid1) ? wid1 : wid2;
  1037.         if (rstart > rend) {
  1038.         /* Handle decreasing ranges correctly. */
  1039.         int rt = rend;
  1040.         rend = rstart;
  1041.         rstart = rt;
  1042.         rev = 1;
  1043.         }
  1044.         uremnode(list, node);
  1045.         for (; rend >= rstart; rend--) {
  1046.         /* Node added in at end, so do highest first */
  1047.         p = dupstring(str3);
  1048.         sprintf(p + strp, "%0*d", minw, rend);
  1049.         strcat(p + strp, str2 + 1);
  1050.         insertlinknode(list, last, p);
  1051.         if (rev)    /* decreasing:  add in reverse order. */
  1052.             last = nextnode(last);
  1053.         }
  1054.         *np = nextnode(olast);
  1055.         return;
  1056.     }
  1057.     }
  1058.     if (!comma && isset(BRACECCL)) {    /* {a-mnop} */
  1059.     /* Here we expand each character to a separate node,      *
  1060.      * but also ranges of characters like a-m.  ccl is a      *
  1061.      * set of flags saying whether each character is present; *
  1062.      * the final list is in lexical order.                    */
  1063.     char ccl[256], *p;
  1064.     unsigned char c1, c2, lastch;
  1065.     unsigned int len, pl;
  1066.  
  1067.     uremnode(list, node);
  1068.     memset(ccl, 0, sizeof(ccl) / sizeof(ccl[0]));
  1069.     for (p = str + 1, lastch = 0; p < str2;) {
  1070.         if (itok(c1 = *p++))
  1071.         c1 = ztokens[c1 - STOUC(Pound)];
  1072.         if ((char) c1 == Meta)
  1073.         c1 = 32 ^ *p++;
  1074.         if (itok(c2 = *p))
  1075.         c2 = ztokens[c2 - STOUC(Pound)];
  1076.         if ((char) c2 == Meta)
  1077.         c2 = 32 ^ p[1];
  1078.         if (c1 == '-' && lastch && p < str2 && (int)lastch <= (int)c2) {
  1079.         while ((int)lastch < (int)c2)
  1080.             ccl[lastch++] = 1;
  1081.         lastch = 0;
  1082.         } else
  1083.         ccl[lastch = c1] = 1;
  1084.     }
  1085.     pl = str - str3;
  1086.     len = pl + strlen(++str2) + 2;
  1087.     for (p = ccl + 255; p-- > ccl;)
  1088.         if (*p) {
  1089.         c1 = p - ccl;
  1090.         if (imeta(c1)) {
  1091.             str = ncalloc(len + 1);
  1092.             str[pl] = Meta;
  1093.             str[pl+1] = c1 ^ 32;
  1094.             strcpy(str + pl + 2, str2);
  1095.         } else {
  1096.             str = ncalloc(len);
  1097.             str[pl] = c1;
  1098.             strcpy(str + pl + 1, str2);
  1099.         }
  1100.         memcpy(str, str3, pl);
  1101.         insertlinknode(list, last, str);
  1102.         }
  1103.     *np = nextnode(last);
  1104.     return;
  1105.     }
  1106.     prev = str++ - str3;
  1107.     str2++;
  1108.     uremnode(list, node);
  1109.     node = last;
  1110.     /* Finally, normal comma expansion               *
  1111.      * str1{foo,bar}str2 -> str1foostr2 str1barstr2. *
  1112.      * Any number of intervening commas is allowed.  */
  1113.     for (;;) {
  1114.     char *zz, *str4;
  1115.     int cnt;
  1116.  
  1117.     for (str4 = str, cnt = 0; cnt || (*str != Comma && *str !=
  1118.                       Outbrace); str++) {
  1119.         if (*str == Inbrace)
  1120.         cnt++;
  1121.         else if (*str == Outbrace)
  1122.         cnt--;
  1123.         DPUTS(!*str, "BUG: illegal brace expansion");
  1124.     }
  1125.     /* Concatenate the string before the braces (str3), the section *
  1126.      * just found (str4) and the text after the braces (str2)       */
  1127.     zz = (char *)ncalloc(prev + (str - str4) + strlen(str2) + 1);
  1128.     ztrncpy(zz, str3, prev);
  1129.     strncat(zz, str4, str - str4);
  1130.     strcat(zz, str2);
  1131.     /* and add this text to the argument list. */
  1132.     insertlinknode(list, node, zz);
  1133.     incnode(node);
  1134.     if (*str != Outbrace)
  1135.         str++;
  1136.     else
  1137.         break;
  1138.     }
  1139.     *np = nextnode(last);
  1140. }
  1141.  
  1142. /* check to see if a matches b (b is not a filename pattern) */
  1143.  
  1144. /**/
  1145. int
  1146. matchpat(char *a, char *b)
  1147. {
  1148.     Comp c;
  1149.     int val, len;
  1150.     char *b2;
  1151.  
  1152.     len = strlen(b);
  1153.     b2 = (char *)alloc(len + 3);
  1154.     strcpy(b2 + 1, b);
  1155.     b2[0] = Inpar;
  1156.     b2[len + 1] = Outpar;
  1157.     b2[len + 2] = '\0';
  1158.     c = parsereg(b2);
  1159.     if (!c) {
  1160.     zerr("bad pattern: %s", b, 0);
  1161.     return 0;
  1162.     }
  1163.     val = domatch(a, c, 0);
  1164.     return val;
  1165. }
  1166.  
  1167. /* do the ${foo%%bar}, ${foo#bar} stuff */
  1168. /* please do not laugh at this code. */
  1169.  
  1170. /* Having found a match in getmatch, decide what part of string
  1171.  * to return.  The matched part starts b characters into string s
  1172.  * and finishes e characters in: 0 <= b <= e <= strlen(s)
  1173.  * (yes, empty matches should work).
  1174.  * Bits 3 and higher in fl are used: the flags are
  1175.  *   8:        Result is matched portion.
  1176.  *  16:        Result is unmatched portion.
  1177.  *        (N.B. this should be set for standard ${foo#bar} etc. matches.)
  1178.  *  32:        Result is numeric position of start of matched portion.
  1179.  *  64:        Result is numeric position of end of matched portion.
  1180.  * 128:        Result is length of matched portion.
  1181.  */
  1182.  
  1183. /**/
  1184. char *
  1185. get_match_ret(char *s, int b, int e, int fl)
  1186. {
  1187.     char buf[80], *r, *p, *rr;
  1188.     int ll = 0, l = strlen(s), bl = 0, t = 0, i;
  1189.  
  1190.     if (fl & 8)            /* matched portion */
  1191.     ll += 1 + (e - b);
  1192.     if (fl & 16)        /* unmatched portion */
  1193.     ll += 1 + (l - (e - b));
  1194.     if (fl & 32) {
  1195.     /* position of start of matched portion */
  1196.     sprintf(buf, "%d ", b + 1);
  1197.     ll += (bl = strlen(buf));
  1198.     }
  1199.     if (fl & 64) {
  1200.     /* position of end of matched portion */
  1201.     sprintf(buf + bl, "%d ", e + 1);
  1202.     ll += (bl = strlen(buf));
  1203.     }
  1204.     if (fl & 128) {
  1205.     /* length of matched portion */
  1206.     sprintf(buf + bl, "%d ", e - b);
  1207.     ll += (bl = strlen(buf));
  1208.     }
  1209.     if (bl)
  1210.     buf[bl - 1] = '\0';
  1211.  
  1212.     rr = r = (char *)ncalloc(ll);
  1213.  
  1214.     if (fl & 8) {
  1215.     /* copy matched portion to new buffer */
  1216.     for (i = b, p = s + b; i < e; i++)
  1217.         *rr++ = *p++;
  1218.     t = 1;
  1219.     }
  1220.     if (fl & 16) {
  1221.     /* Copy unmatched portion to buffer.  If both portions *
  1222.      * requested, put a space in between (why?)            */
  1223.     if (t)
  1224.         *rr++ = ' ';
  1225.     /* there may be unmatched bits at both beginning and end of string */
  1226.     for (i = 0, p = s; i < b; i++)
  1227.         *rr++ = *p++;
  1228.     for (i = e, p = s + e; i < l; i++)
  1229.         *rr++ = *p++;
  1230.     t = 1;
  1231.     }
  1232.     *rr = '\0';
  1233.     if (bl) {
  1234.     /* if there was a buffer (with a numeric result), add it; *
  1235.      * if there was other stuff too, stick in a space first.  */
  1236.     if (t)
  1237.         *rr++ = ' ';
  1238.     strcpy(rr, buf);
  1239.     }
  1240.     return r;
  1241. }
  1242.  
  1243. /* It is called from paramsubst to get the match for ${foo#bar} etc.
  1244.  * Bits of fl determines the required action:
  1245.  *   bit 0: match the end instead of the beginning (% or %%)
  1246.  *   bit 1: % or # was doubled so get the longest match
  1247.  *   bit 2: substring match
  1248.  *   bit 3: include the matched portion
  1249.  *   bit 4: include the unmatched portion
  1250.  *   bit 5: the index of the beginning
  1251.  *   bit 6: the index of the end
  1252.  *   bit 7: the length of the match
  1253.  *   bit 8: match the complete string
  1254.  * *sp points to the string we have to modify. The n'th match will be
  1255.  * returned in *sp. ncalloc is used to get memory for the result string.
  1256.  */
  1257.  
  1258. /**/
  1259. int
  1260. getmatch(char **sp, char *pat, int fl, int n)
  1261. {
  1262.     Comp c;
  1263.     char *s = *sp, *t, sav;
  1264.     int i, j, l = strlen(*sp);
  1265.  
  1266.     c = parsereg(pat);
  1267.     if (!c) {
  1268.     zerr("bad pattern: %s", pat, 0);
  1269.     return 1;
  1270.     }
  1271.     if (fl & 256) {
  1272.     i = domatch(s, c, 0);
  1273.     *sp = get_match_ret(*sp, 0, domatch(s, c, 0) ? l : 0, fl);
  1274.     if (! **sp && (((fl & 8) && !i) || ((fl & 16) && i)))
  1275.         return 0;
  1276.     return 1;
  1277.     }
  1278.     switch (fl & 7) {
  1279.     case 0:
  1280.     /* Smallest possible match at head of string:    *
  1281.      * start adding characters until we get a match. */
  1282.     for (i = 0, t = s; i <= l; i++, t++) {
  1283.         sav = *t;
  1284.         *t = '\0';
  1285.         if (domatch(s, c, 0) && !--n) {
  1286.         *t = sav;
  1287.         *sp = get_match_ret(*sp, 0, i, fl);
  1288.         return 1;
  1289.         }
  1290.         if ((*t = sav) == Meta)
  1291.         i++, t++;
  1292.     }
  1293.     break;
  1294.  
  1295.     case 1:
  1296.     /* Smallest possible match at tail of string:  *
  1297.      * move back down string until we get a match. */
  1298.     for (t = s + l; t >= s; t--) {
  1299.         if (domatch(t, c, 0) && !--n) {
  1300.         *sp = get_match_ret(*sp, t - s, l, fl);
  1301.         return 1;
  1302.         }
  1303.         if (t > s+1 && t[-2] == Meta)
  1304.         t--;
  1305.     }
  1306.     break;
  1307.  
  1308.     case 2:
  1309.     /* Largest possible match at head of string:        *
  1310.      * delete characters from end until we get a match. */
  1311.     for (t = s + l; t > s; t--) {
  1312.         sav = *t;
  1313.         *t = '\0';
  1314.         if (domatch(s, c, 0) && !--n) {
  1315.         *t = sav;
  1316.         *sp = get_match_ret(*sp, 0, t - s, fl);
  1317.         return 1;
  1318.         }
  1319.         *t = sav;
  1320.         if (t >= s+2 && t[-2] == Meta)
  1321.         t--;
  1322.     }
  1323.     break;
  1324.  
  1325.     case 3:
  1326.     /* Largest possible match at tail of string:       *
  1327.      * move forward along string until we get a match. */
  1328.     for (i = 0, t = s; i < l; i++, t++) {
  1329.         if (domatch(t, c, 0) && !--n) {
  1330.         *sp = get_match_ret(*sp, i, l, fl);
  1331.         return 1;
  1332.         }
  1333.         if (*t == Meta)
  1334.         i++, t++;
  1335.     }
  1336.     break;
  1337.  
  1338.     case 4:
  1339.     /* Smallest at start, but matching substrings. */
  1340.     if (domatch(s + l, c, 0) && !--n) {
  1341.         *sp = get_match_ret(*sp, 0, 0, fl);
  1342.         return 1;
  1343.     }
  1344.     for (i = 1; i <= l; i++) {
  1345.         for (t = s, j = i; j <= l; j++, t++) {
  1346.         sav = s[j];
  1347.         s[j] = '\0';
  1348.         if (domatch(t, c, 0) && !--n) {
  1349.             s[j] = sav;
  1350.             *sp = get_match_ret(*sp, t - s, j, fl);
  1351.             return 1;
  1352.         }
  1353.         if ((s[j] = sav) == Meta)
  1354.             j++;
  1355.         if (*t == Meta)
  1356.             t++;
  1357.         }
  1358.         if (s[i] == Meta)
  1359.         i++;
  1360.     }
  1361.     break;
  1362.  
  1363.     case 5:
  1364.     /* Smallest at end, matching substrings */
  1365.     if (domatch(s + l, c, 0) && !--n) {
  1366.         *sp = get_match_ret(*sp, l, l, fl);
  1367.         return 1;
  1368.     }
  1369.     for (i = l; i--;) {
  1370.         if (i && s[i-1] == Meta)
  1371.         i--;
  1372.         for (t = s + l, j = i; j >= 0; j--, t--) {
  1373.         sav = *t;
  1374.         *t = '\0';
  1375.         if (domatch(s + j, c, 0) && !--n) {
  1376.             *t = sav;
  1377.             *sp = get_match_ret(*sp, j, t - s, fl);
  1378.             return 1;
  1379.         }
  1380.         *t = sav;
  1381.         if (t >= s+2 && t[-2] == Meta)
  1382.             t--;
  1383.         if (j >= 2 && s[j-2] == Meta)
  1384.             j--;
  1385.         }
  1386.     }
  1387.     break;
  1388.  
  1389.     case 6:
  1390.     /* Largest at start, matching substrings. */
  1391.     for (i = l; i; i--) {
  1392.         for (t = s, j = i; j <= l; j++, t++) {
  1393.         sav = s[j];
  1394.         s[j] = '\0';
  1395.         if (domatch(t, c, 0) && !--n) {
  1396.             s[j] = sav;
  1397.             *sp = get_match_ret(*sp, t - s, j, fl);
  1398.             return 1;
  1399.         }
  1400.         if ((s[j] = sav) == Meta)
  1401.             j++;
  1402.         if (*t == Meta)
  1403.             t++;
  1404.         }
  1405.         if (i >= 2 && s[i-2] == Meta)
  1406.         i--;
  1407.     }
  1408.     if (domatch(s + l, c, 0) && !--n) {
  1409.         *sp = get_match_ret(*sp, 0, 0, fl);
  1410.         return 1;
  1411.     }
  1412.     break;
  1413.  
  1414.     case 7:
  1415.     /* Largest at end, matching substrings. */
  1416.     for (i = 0; i < l; i++) {
  1417.         for (t = s + l, j = i; j >= 0; j--, t--) {
  1418.         sav = *t;
  1419.         *t = '\0';
  1420.         if (domatch(s + j, c, 0) && !--n) {
  1421.             *t = sav;
  1422.             *sp = get_match_ret(*sp, j, t - s, fl);
  1423.             return 1;
  1424.         }
  1425.         *t = sav;
  1426.         if (t >= s+2 && t[-2] == Meta)
  1427.             t--;
  1428.         if (j >= 2 && s[j-2] == Meta)
  1429.             j--;
  1430.         }
  1431.         if (s[i] == Meta)
  1432.         i++;
  1433.     }
  1434.     if (domatch(s + l, c, 0) && !--n) {
  1435.         *sp = get_match_ret(*sp, l, l, fl);
  1436.         return 1;
  1437.     }
  1438.     break;
  1439.     }
  1440.     /* munge the whole string */
  1441.     *sp = get_match_ret(*sp, 0, 0, fl);
  1442.     return 1;
  1443. }
  1444.  
  1445. /* Add a component to pathbuf: This keeps track of how    *
  1446.  * far we are into a file name, since each path component *
  1447.  * must be matched separately.                            */
  1448.  
  1449. static int addpath _((char *s));
  1450.  
  1451. static int
  1452. addpath(char *s)
  1453. {
  1454.     if ((int)strlen(s) + pathpos + 2 >= PATH_MAX)
  1455.     return 0;
  1456.     while ((pathbuf[pathpos++] = *s++));
  1457.     pathbuf[pathpos - 1] = '/';
  1458.     pathbuf[pathpos] = '\0';
  1459.     return 1;
  1460. }
  1461.  
  1462. /* return full path for s, which has path as *
  1463.  * already added to pathbuf                  */
  1464.  
  1465. /**/
  1466. char *
  1467. getfullpath(char *s)
  1468. {
  1469.     static char buf[PATH_MAX];
  1470.  
  1471.     strcpy(buf, pathbuf);
  1472.     strncpy(buf + pathpos, s, PATH_MAX - pathpos - 1);
  1473.     return buf;
  1474. }
  1475.  
  1476. /* Do the globbing:  scanner is called recursively *
  1477.  * with successive bits of the path until we've    *
  1478.  * tried all of it.                                */
  1479.  
  1480. /**/
  1481. void
  1482. scanner(Complist q)
  1483. {
  1484.     Comp c;
  1485.     int closure;
  1486.     struct stat st;
  1487.  
  1488.     if (!q)
  1489.     return;
  1490.  
  1491.     /* make sure we haven't just done this one. */
  1492.     if (q->closure && old_pos != pathpos &&
  1493.     stat((*pathbuf) ? unmeta(pathbuf) : ".", &st) != -1)
  1494.     if (st.st_ino == old_ino && st.st_dev == old_dev)
  1495.         return;
  1496.     else {
  1497.         old_pos = pathpos;
  1498.         old_ino = st.st_ino;
  1499.         old_dev = st.st_dev;
  1500.     }
  1501.     if ((closure = q->closure))    /* (foo/)# - match zero or more dirs */
  1502.     if (q->closure == 2)    /* (foo/)## - match one or more dirs */
  1503.         q->closure = 1;
  1504.     else
  1505.         scanner(q->next);
  1506.     if ((c = q->comp)) {
  1507.     /* Now the actual matching for the current path section. */
  1508.     if (!(c->next || c->left) && !haswilds(c->str)) {
  1509.         /* It's a straight string to the end of the path section. */
  1510.         if (q->next) {
  1511.         /* Not the last path section. Just add it to the path. */
  1512.         int oppos = pathpos;
  1513.  
  1514.         if (errflag)
  1515.             return;
  1516.         if (q->closure && !strcmp(c->str, "."))
  1517.             return;
  1518.         if (!addpath(c->str))
  1519.             return;
  1520.         if (!closure || exists(pathbuf))
  1521.             scanner((q->closure) ? q : q->next);
  1522.         pathbuf[pathpos = oppos] = '\0';
  1523.         } else if (!*c->str) {
  1524.         if (exists(getfullpath(".")))
  1525.             insert(dupstring(pathbuf));
  1526.         } else {
  1527.         /* Last path section.  See if there's a file there. */
  1528.         char *s;
  1529.  
  1530.         if (exists(s = getfullpath(c->str)))
  1531.             insert(dupstring(s));
  1532.         }
  1533.     } else {
  1534.         /* Do pattern matching on current path section. */
  1535.         char *fn;
  1536.         int dirs = !!q->next;
  1537.         DIR *lock = opendir((*pathbuf) ? unmeta(pathbuf) : ".");
  1538.  
  1539.         if (lock == NULL)
  1540.         return;
  1541.         while ((fn = zreaddir(lock))) {
  1542.         /* Loop through the directory */
  1543.         if (errflag)
  1544.             break;
  1545.         /* skip this and parent directory */
  1546.         if (fn[0] == '.'
  1547.             && (fn[1] == '\0'
  1548.             || (fn[1] == '.' && fn[2] == '\0')))
  1549.             continue;
  1550.         /* prefix and suffix are zle trickery */
  1551.         if (!dirs && !colonmod &&
  1552.             ((glob_pre && !strpfx(glob_pre, fn))
  1553.              || (glob_suf && !strsfx(glob_suf, fn))))
  1554.             continue;
  1555.         if (domatch(fn, c, gf_noglobdots)) {
  1556.             /* if this name matchs the pattern... */
  1557.             int oppos = pathpos;
  1558.  
  1559.             if (dirs) {
  1560.             /* if not the last component in the path */
  1561.             if (closure) {
  1562.                 /* if matching multiple directories */
  1563.                 struct stat buf;
  1564.  
  1565.                 if ((q->follow ?
  1566.                 stat(unmeta(getfullpath(fn)), &buf) :
  1567.                 lstat(unmeta(getfullpath(fn)), &buf)) == -1) {
  1568.                 if (errno != ENOENT && errno != EINTR &&
  1569.                     errno != ENOTDIR) {
  1570.                     zerr("%e: %s", fn, errno);
  1571.                     errflag = 0;
  1572.                 }
  1573.                 continue;
  1574.                 }
  1575.                 if (!S_ISDIR(buf.st_mode))
  1576.                 continue;
  1577.             }
  1578.             /* do next path component */
  1579.             if (addpath(fn))
  1580.                 scanner((q->closure) ? q : q->next);    /* scan next level */
  1581.             pathbuf[pathpos = oppos] = '\0';
  1582.             } else
  1583.             insert(dyncat(pathbuf, fn));
  1584.             /* if the last filename component, just add it */
  1585.         }
  1586.         }
  1587.         closedir(lock);
  1588.     }
  1589.     } else
  1590.     zerr("no idea how you got this error message.", NULL, 0);
  1591. }
  1592.  
  1593. /* Flags passed down to guts when compiling */
  1594. #define GF_PATHADD    1    /* file glob, adding path components */
  1595. #define GF_TOPLEV    2    /* outside (), so ~ ends main match */
  1596.  
  1597. static char *pptr;        /* current place in string being matched */
  1598. static Comp tail;
  1599. static int first;        /* are leading dots special? */
  1600.  
  1601. /* The main entry point for matching a string str against  *
  1602.  * a compiled pattern c.  `fist' indicates whether leading *
  1603.  * dots are special.                                       */
  1604.  
  1605. /**/
  1606. int
  1607. domatch(char *str, Comp c, int fist)
  1608. {
  1609.     pptr = str;
  1610.     first = fist;
  1611.     if (*pptr == Nularg)
  1612.     pptr++;
  1613.     return doesmatch(c);
  1614. }
  1615.  
  1616. #define untok(C)  (itok(C) ? ztokens[(C) - Pound] : (C))
  1617.  
  1618. /* See if pattern has a matching exclusion (~...) part */
  1619.  
  1620. /**/
  1621. int
  1622. excluded(Comp c, char *eptr)
  1623. {
  1624.     char *saves = pptr;
  1625.     int savei = first, ret;
  1626.  
  1627.     first = 0;
  1628.     pptr = (PATHADDP(c) && pathpos) ? getfullpath(eptr) : eptr;
  1629.  
  1630.     ret = doesmatch(c->exclude);
  1631.  
  1632.     pptr = saves;
  1633.     first = savei;
  1634.  
  1635.     return ret;
  1636. }
  1637.  
  1638. /* see if current string in pptr matches c */
  1639.  
  1640. /**/
  1641. int
  1642. doesmatch(Comp c)
  1643. {
  1644.     char *pat = c->str;
  1645.     int done = 0;
  1646.  
  1647.   tailrec:
  1648.     if (ONEHASHP(c) || (done && TWOHASHP(c))) {
  1649.     /* Do multiple matches like (pat)# and (pat)## */
  1650.     char *saves = pptr;
  1651.  
  1652.     if (first && *pptr == '.')
  1653.         return 0;
  1654.     if (doesmatch(c->next))
  1655.         return 1;
  1656.     pptr = saves;
  1657.     first = 0;
  1658.     }
  1659.     done++;
  1660.     for (;;) {
  1661.     /* loop until success or failure of pattern */
  1662.     if (!pat || !*pat) {
  1663.         /* No current pattern (c->str). */
  1664.         char *saves;
  1665.         int savei;
  1666.  
  1667.         if (errflag)
  1668.         return 0;
  1669.         /* Remember state in case we need to go back and   *
  1670.          * check for exclusion of pattern or alternatives. */
  1671.         saves = pptr;
  1672.         savei = first;
  1673.         /* Loop over alternatives with exclusions: (foo~bar|...). *
  1674.          * Exclusions apply to the pattern in c->left.            */
  1675.         if (c->left || c->right)
  1676.         if (!doesmatch(c->left) ||
  1677.             (c->exclude && excluded(c, saves)))
  1678.             if (c->right) {
  1679.             pptr = saves;
  1680.             first = savei;
  1681.             if (!doesmatch(c->right))
  1682.                 return 0;
  1683.             } else
  1684.             return 0;
  1685.         if (*pptr && CLOSUREP(c)) {
  1686.         /* With a closure (#), need to keep trying */
  1687.         pat = c->str;
  1688.         goto tailrec;
  1689.         }
  1690.         if (!c->next)    /* no more patterns left */
  1691.         return (!LASTP(c) || !*pptr);
  1692.         c = c->next;
  1693.         done = 0;
  1694.         pat = c->str;
  1695.         goto tailrec;
  1696.     }
  1697.     /* Don't match leading dot if first is set */
  1698.     if (first && *pptr == '.' && *pat != '.')
  1699.         return 0;
  1700.     if (*pat == Star) {    /* final * is not expanded to ?#; returns success */
  1701.         while (*pptr)
  1702.         pptr++;
  1703.         return 1;
  1704.     }
  1705.     first = 0;        /* finished checking start of pattern */
  1706.     if (*pat == Quest && *pptr) {
  1707.         /* match exactly one character */
  1708.         if (*pptr == Meta)
  1709.         pptr++;
  1710.         pptr++;
  1711.         pat++;
  1712.         continue;
  1713.     }
  1714.     if (*pat == Hat)    /* following pattern is negated */
  1715.         return 1 - doesmatch(c->next);
  1716.     if (*pat == Inbrack) {
  1717.         /* Match groups of characters */
  1718. #define PAT(X) (pat[X] == Meta ? pat[(X)+1] ^ 32 : untok(pat[X]))
  1719. #define PPAT(X) (pat[(X)-1] == Meta ? pat[X] ^ 32 : untok(pat[X]))
  1720.         char ch;
  1721. #ifdef HAVE_STRCOLL
  1722.         char l_buf[2], r_buf[2], ch_buf[2];
  1723.  
  1724.         l_buf[1] = r_buf[1] = ch_buf[1] = '\0';
  1725. #endif
  1726.  
  1727.         if (!*pptr)
  1728.         break;
  1729.         ch = *pptr == Meta ? pptr[1] ^ 32 : *pptr;
  1730. #ifdef HAVE_STRCOLL
  1731.         ch_buf[0] = ch;
  1732. #endif
  1733.         if (pat[1] == Hat || pat[1] == '^' || pat[1] == '!') {
  1734.         /* group is negated */
  1735.         pat[1] = Hat;
  1736.         for (pat += 2; *pat != Outbrack && *pat;
  1737.              *pat == Meta ? pat += 2 : pat++)
  1738.             if (*pat == '-' && pat[-1] != Hat && pat[1] != Outbrack) {
  1739. #ifdef HAVE_STRCOLL
  1740.             l_buf[0] = PPAT(-1);
  1741.             r_buf[0] = PAT(1);
  1742.             if (strcoll(l_buf, ch_buf) <= 0 &&
  1743.                 strcoll(ch_buf, r_buf) <= 0)
  1744. #else
  1745.             if (PPAT(-1) <= ch && PAT(1) >= ch)
  1746. #endif
  1747.                 break;
  1748.             } else if (ch == PAT(0))
  1749.             break;
  1750. #ifdef DEBUG
  1751.         if (!*pat) {
  1752.             zerr("something is very wrong.", NULL, 0);
  1753.             return 0;
  1754.         }
  1755. #endif
  1756.         if (*pat != Outbrack)
  1757.             break;
  1758.         pat++;
  1759.         *pptr == Meta ? pptr += 2 : pptr++;
  1760.         continue;
  1761.         } else {
  1762.         /* pattern is not negated (affirmed? asserted?) */
  1763.         for (pat++; *pat != Outbrack && *pat;
  1764.              *pat == Meta ? pat += 2 : pat++)
  1765.             if (*pat == '-' && pat[-1] != Inbrack &&
  1766.                    pat[1] != Outbrack) {
  1767. #ifdef HAVE_STRCOLL
  1768.             l_buf[0] = PPAT(-1);
  1769.             r_buf[0] = PAT(1);
  1770.             if (strcoll(l_buf, ch_buf) <= 0 &&
  1771.                 strcoll(ch_buf, r_buf) <= 0)
  1772. #else
  1773.             if (PPAT(-1) <= ch && PAT(1) >= ch)
  1774. #endif
  1775.                 break;
  1776.             } else if (ch == PAT(0))
  1777.             break;
  1778. #ifdef DEBUG
  1779.         if (!pat || !*pat) {
  1780.             zerr("oh dear.  that CAN'T be right.", NULL, 0);
  1781.             return 0;
  1782.         }
  1783. #endif
  1784.         if (*pat == Outbrack)
  1785.             break;
  1786.         for (*pptr == Meta ? pptr += 2 : pptr++;
  1787.              *pat != Outbrack; pat++);
  1788.         pat++;
  1789.         continue;
  1790.         }
  1791.     }
  1792.     if (*pat == Inang) {
  1793.         /* Numeric globbing. */
  1794.         unsigned long t1, t2, t3;
  1795.         char *ptr;
  1796.  
  1797.         if (!idigit(*pptr))
  1798.         break;
  1799.         if (*++pat == Outang || 
  1800.         (*pat == '-' && pat[1] == Outang && ++pat)) {
  1801.         /* <> or <->:  any number matches */
  1802.         while (idigit(*++pptr));
  1803.         pat++;
  1804.         } else {
  1805.         /* Flag that there is no upper limit */
  1806.         int not3 = 0;
  1807.         /*
  1808.          * Form is <a-b>, where a or b are numbers or blank.
  1809.          * t1 = number supplied:  must be positive, so use
  1810.          * unsigned arithmetic.
  1811.          */
  1812.         t1 = (unsigned long)zstrtol(pptr, &ptr, 10);
  1813.         pptr = ptr;
  1814.         /* t2 = lower limit */
  1815.         if (idigit(*pat))
  1816.             t2 = (unsigned long)zstrtol(pat, &ptr, 10);
  1817.         else
  1818.             t2 = 0, ptr = pat;
  1819.         if (*ptr != '-' || (not3 = (ptr[1] == Outang)))
  1820.                 /* exact match or no upper limit */
  1821.             t3 = t2, pat = ptr + not3;
  1822.         else        /* t3 = upper limit */
  1823.             t3 = (unsigned long)zstrtol(ptr + 1, &pat, 10);
  1824.         DPUTS(*pat != Outang, "BUG: wrong internal range pattern");
  1825.         pat++;
  1826.         if (t1 < t2 || (!not3 && t1 > t3))
  1827.             break;
  1828.         }
  1829.         continue;
  1830.     }
  1831.     if (*pptr == *pat) {
  1832.         /* just plain old characters */
  1833.         pptr++;
  1834.         pat++;
  1835.         continue;
  1836.     }
  1837.     break;
  1838.     }
  1839.     return 0;
  1840. }
  1841.  
  1842. /* turn a string into a Complist struct:  this has path components */
  1843.  
  1844. /**/
  1845. Complist
  1846. parsepat(char *str)
  1847. {
  1848.     mode = 0;            /* path components present */
  1849.     pptr = str;
  1850.     tail = NULL;
  1851.     return parsecomplist();
  1852. }
  1853.  
  1854. /* turn a string into a Comp struct:  this doesn't treat / specially */
  1855.  
  1856. /**/
  1857. Comp
  1858. parsereg(char *str)
  1859. {
  1860.     remnulargs(str);
  1861.     mode = 1;            /* no path components */
  1862.     pptr = str;
  1863.     tail = NULL;
  1864.     return parsecompsw(GF_TOPLEV);
  1865. }
  1866.  
  1867. /* Parse a series of path components pointed to by pptr */
  1868.  
  1869. /* This function tokenizes a zsh glob pattern */
  1870.  
  1871. /**/
  1872. Complist
  1873. parsecomplist(void)
  1874. {
  1875.     Comp c1;
  1876.     Complist p1;
  1877.     char *str;
  1878.  
  1879.     if (pptr[0] == Star && pptr[1] == Star &&
  1880.         (pptr[2] == '/' || (pptr[2] == Star && pptr[3] == '/'))) {
  1881.     /* Match any number of directories. */
  1882.     int follow;
  1883.  
  1884.     /* with three stars, follow symbolic links */
  1885.     follow = (pptr[2] == Star);
  1886.     pptr += (3 + follow);
  1887.  
  1888.     /* Now get the next path component if there is one. */
  1889.     p1 = (Complist) alloc(sizeof *p1);
  1890.     if ((p1->next = parsecomplist()) == NULL) {
  1891.         errflag = 1;
  1892.         return NULL;
  1893.     }
  1894.     p1->comp = (Comp) alloc(sizeof *p1->comp);
  1895.     p1->comp->stat |= C_LAST;    /* end of path component  */
  1896.     p1->comp->str = dupstring("*");
  1897.     *p1->comp->str = Star;        /* match anything...      */
  1898.     p1->closure = 1;        /* ...zero or more times. */
  1899.     p1->follow = follow;
  1900.     return p1;
  1901.     }
  1902.  
  1903.     /* Parse repeated directories such as (dir/)# and (dir/)## */
  1904.     if (*(str = pptr) == Inpar && !skipparens(Inpar, Outpar, &str) &&
  1905.         *str == Pound && isset(EXTENDEDGLOB) && str[-2] == '/') {
  1906.     pptr++;
  1907.     if (!(c1 = parsecompsw(0)))
  1908.         return NULL;
  1909.     if (pptr[0] == '/' && pptr[1] == Outpar && pptr[2] == Pound) {
  1910.         int pdflag = 0;
  1911.  
  1912.         pptr += 3;
  1913.         if (*pptr == Pound) {
  1914.         pdflag = 1;
  1915.         pptr++;
  1916.         }
  1917.         p1 = (Complist) alloc(sizeof *p1);
  1918.         p1->comp = c1;
  1919.         p1->closure = 1 + pdflag;
  1920.         p1->follow = 0;
  1921.         p1->next = parsecomplist();
  1922.         return (p1->comp) ? p1 : NULL;
  1923.     }
  1924.     } else {
  1925.     /* parse single path component */
  1926.     if (!(c1 = parsecompsw(GF_PATHADD|GF_TOPLEV)))
  1927.         return NULL;
  1928.     /* then do the remaining path compoents */
  1929.     if (*pptr == '/' || !*pptr) {
  1930.         int ef = *pptr == '/';
  1931.  
  1932.         p1 = (Complist) alloc(sizeof *p1);
  1933.         p1->comp = c1;
  1934.         p1->closure = 0;
  1935.         p1->next = ef ? (pptr++, parsecomplist()) : NULL;
  1936.         return (ef && !p1->next) ? NULL : p1;
  1937.     }
  1938.     }
  1939.     errflag = 1;
  1940.     return NULL;
  1941. }
  1942.  
  1943. /* parse lowest level pattern */
  1944.  
  1945. /**/
  1946. Comp
  1947. parsecomp(int gflag)
  1948. {
  1949.     Comp c = (Comp) alloc(sizeof *c), c1, c2;
  1950.     char *cstr, *ls = NULL;
  1951.  
  1952.     /* In case of alternatives, code coming up is stored in tail. */
  1953.     c->next = tail;
  1954.     cstr = pptr;
  1955.  
  1956.     while (*pptr && (mode || *pptr != '/') && *pptr != Bar &&
  1957.        (unset(EXTENDEDGLOB) || *pptr != Tilde ||
  1958.         !pptr[1] || pptr[1] == Outpar || pptr[1] == Bar) &&
  1959.        *pptr != Outpar) {
  1960.     /* Go through code until we find something separating alternatives,
  1961.      * or path components if relevant.
  1962.      */
  1963.     if (*pptr == Hat && isset(EXTENDEDGLOB)) {
  1964.         /* negate remaining pattern */
  1965.         pptr++;
  1966.         c->str = dupstrpfx(cstr, pptr - cstr);
  1967.         if (!(c->next = parsecomp(gflag)))
  1968.         return NULL;
  1969.         return c;
  1970.     }
  1971.     if (*pptr == Star && pptr[1] &&
  1972.         (unset(EXTENDEDGLOB) || pptr[1] != Tilde || !pptr[2] ||
  1973.          pptr[2] == Bar ||
  1974.          pptr[2] == Outpar) && (mode || pptr[1] != '/')) {
  1975.         /* Star followed by other patterns is treated like a closure
  1976.          * (zero or more repetitions) of the single character pattern
  1977.          * operator `?'.
  1978.          */
  1979.         c->str = dupstrpfx(cstr, pptr - cstr);
  1980.         pptr++;
  1981.         c1 = (Comp) alloc(sizeof *c1);
  1982.         *(c1->str = dupstring("?")) = Quest;
  1983.         c1->stat |= C_ONEHASH;
  1984.         if (!(c2 = parsecomp(gflag)))
  1985.         return NULL;
  1986.         c1->next = c2;
  1987.         c->next = c1;
  1988.         return c;
  1989.     }
  1990.     if (*pptr == Inpar) {
  1991.         /* Found a group (...) */
  1992.         char *startp = pptr, *endp;
  1993.         Comp stail = tail;
  1994.         int dpnd = 0;
  1995.  
  1996.         /* Need matching close parenthesis */
  1997.         if (skipparens(Inpar, Outpar, &pptr)) {
  1998.         errflag = 1;
  1999.         return NULL;
  2000.         }
  2001.         if (*pptr == Pound && isset(EXTENDEDGLOB)) {
  2002.         /* Zero (or one) or more repetitions of group */
  2003.         dpnd = 1;
  2004.         pptr++;
  2005.         if (*pptr == Pound) {
  2006.             pptr++;
  2007.             dpnd = 2;
  2008.         }
  2009.         }
  2010.         /* Parse the remaining pattern following the group... */
  2011.         if (!(c1 = parsecomp(gflag)))
  2012.         return NULL;
  2013.         /* ...remembering what comes after it... */
  2014.         tail = dpnd ? NULL : c1;
  2015.         /* ...before going back and parsing inside the group. */
  2016.         endp = pptr;
  2017.         pptr = startp;
  2018.         c->str = dupstrpfx(cstr, pptr - cstr);
  2019.         pptr++;
  2020.         c->next = (Comp) alloc(sizeof *c);
  2021.         if (!(c->next->left = parsecompsw(0)))
  2022.         return NULL;
  2023.         /* Remember closures for group. */
  2024.         if (dpnd)
  2025.         c->next->stat |= (dpnd == 2) ? C_TWOHASH : C_ONEHASH;
  2026.         c->next->next = dpnd ? c1 : (Comp) alloc(sizeof *c);
  2027.         pptr = endp;
  2028.         tail = stail;
  2029.         return c;
  2030.     }
  2031.     if (*pptr == Pound && isset(EXTENDEDGLOB)) {
  2032.         /* repeat whatever we've just had (ls) zero or more times */
  2033.         if (!ls)
  2034.         return NULL;
  2035.         c2 = (Comp) alloc(sizeof *c);
  2036.         c2->str = dupstrpfx(ls, pptr - ls);
  2037.         pptr++;
  2038.         if (*pptr == Pound) {
  2039.         /* need one or more matches: cheat by copying previous char */
  2040.         pptr++;
  2041.         c->next = c1 = (Comp) alloc(sizeof *c);
  2042.         c1->str = c2->str;
  2043.         } else
  2044.         c1 = c;
  2045.         c1->next = c2;
  2046.         c2->stat |= C_ONEHASH;
  2047.         /* parse the rest of the pattern and return. */
  2048.         c2->next = parsecomp(gflag);
  2049.         if (!c2->next)
  2050.         return NULL;
  2051.         c->str = dupstrpfx(cstr, ls - cstr);
  2052.         return c;
  2053.     }
  2054.     ls = pptr;        /* whatever we just parsed */
  2055.     if (*pptr == Inang) {
  2056.         /* Numeric glob */
  2057.         int dshct;
  2058.  
  2059.         dshct = (pptr[1] == Outang);
  2060.         while (*++pptr && *pptr != Outang)
  2061.         if (*pptr == '-' && !dshct)
  2062.             dshct = 1;
  2063.         else if (!idigit(*pptr))
  2064.             break;
  2065.         if (*pptr != Outang)
  2066.         return NULL;
  2067.     } else if (*pptr == Inbrack) {
  2068.         /* Character set: brackets had better match */
  2069.         while (*++pptr && *pptr != Outbrack)
  2070.         if (itok(*pptr))
  2071.             *pptr = ztokens[*pptr - Pound];
  2072.         if (*pptr != Outbrack)
  2073.         return NULL;
  2074.     } else if (itok(*pptr) && *pptr != Star && *pptr != Quest)
  2075.         /* something that can be tokenised which isn't otherwise special */
  2076.         *pptr = ztokens[*pptr - Pound];
  2077.     pptr++;
  2078.     }
  2079.     /* mark if last pattern component in path component or pattern */
  2080.     if (*pptr == '/' || !*pptr ||
  2081.     (isset(EXTENDEDGLOB) && *pptr == Tilde && (gflag & GF_TOPLEV)))
  2082.     c->stat |= C_LAST;
  2083.     c->str = dupstrpfx(cstr, pptr - cstr);
  2084.     return c;
  2085. }
  2086.  
  2087. /* Parse pattern possibly with different alternatives (|) */
  2088.  
  2089. /**/
  2090. Comp
  2091. parsecompsw(int gflag)
  2092. {
  2093.     Comp c1, c2, c3, excl = NULL;
  2094.  
  2095.     c1 = parsecomp(gflag);
  2096.     if (!c1)
  2097.     return NULL;
  2098.     if (isset(EXTENDEDGLOB) && *pptr == Tilde) {
  2099.     /* Matching remainder of pattern excludes the pattern from matching */
  2100.     int oldmode = mode;
  2101.  
  2102.     mode = 1;
  2103.     pptr++;
  2104.     excl = parsecomp(gflag);
  2105.     mode = oldmode;
  2106.     if (!excl)
  2107.         return NULL;
  2108.     }
  2109.     if (*pptr == Bar || excl) {
  2110.     /* found an alternative or something to exclude */
  2111.     c2 = (Comp) alloc(sizeof *c2);
  2112.     if (*pptr == Bar) {
  2113.         /* get the next alternative after the | */
  2114.         pptr++;
  2115.         c3 = parsecompsw(gflag);
  2116.         if (!c3)
  2117.         return NULL;
  2118.     } else {
  2119.         /* mark if end of pattern or path component */
  2120.         if (!*pptr || *pptr == '/')
  2121.         c2->stat |= C_LAST;
  2122.         c3 = NULL;
  2123.     }
  2124.     c2->str = dupstring("");
  2125.     c2->left = c1;
  2126.     c2->right = c3;
  2127.     c2->exclude = excl;
  2128.     if (gflag & GF_PATHADD)
  2129.         c2->stat |= C_PATHADD;
  2130.     return c2;
  2131.     }
  2132.     return c1;
  2133. }
  2134.  
  2135. /* blindly turn a string into a tokenised expression without lexing */
  2136.  
  2137. /**/
  2138. void
  2139. tokenize(char *s)
  2140. {
  2141.     char *t;
  2142.     int bslash = 0;
  2143.  
  2144.     for (; *s; s++) {
  2145.       cont:
  2146.     switch (*s) {
  2147.     case Bnull:
  2148.     case '\\':
  2149.         if (bslash) {
  2150.         s[-1] = Bnull;
  2151.         break;
  2152.         }
  2153.         bslash = 1;
  2154.         continue;
  2155.     case '[':
  2156.         if (bslash) {
  2157.         s[-1] = Bnull;
  2158.         break;
  2159.         }
  2160.         t = s;
  2161.         if (*++s == '^' || *s == '!')
  2162.         s++;
  2163.         while (*s && *++s != ']');
  2164.         if (!*s)
  2165.         return;
  2166.         *t = Inbrack;
  2167.         *s = Outbrack;
  2168.         break;
  2169.     case '<':
  2170.         if (isset(SHGLOB))
  2171.         break;
  2172.         if (bslash) {
  2173.         s[-1] = Bnull;
  2174.         break;
  2175.         }
  2176.         t = s;
  2177.         while (idigit(*++s));
  2178.         if (*s != '-')
  2179.         goto cont;
  2180.         while (idigit(*++s));
  2181.         if (*s != '>')
  2182.         goto cont;
  2183.         *t = Inang;
  2184.         *s = Outang;
  2185.         break;
  2186.     case '^':
  2187.     case '#':
  2188.     case '~':
  2189.         if (unset(EXTENDEDGLOB))
  2190.         break;
  2191.     case '(':
  2192.     case '|':
  2193.     case ')':
  2194.         if (isset(SHGLOB))
  2195.         break;
  2196.     case '*':
  2197.     case '?':
  2198.         for (t = ztokens; *t; t++)
  2199.         if (*t == *s) {
  2200.             if (bslash)
  2201.             s[-1] = Bnull;
  2202.             else
  2203.             *s = (t - ztokens) + Pound;
  2204.             break;
  2205.         }
  2206.     }
  2207.     bslash = 0;
  2208.     }
  2209. }
  2210.  
  2211. /* remove unnecessary Nulargs */
  2212.  
  2213. /**/
  2214. void
  2215. remnulargs(char *s)
  2216. {
  2217.     int nl = *s;
  2218.     char *t = s;
  2219.  
  2220.     while (*s)
  2221.     if (INULL(*s))
  2222.         chuck(s);
  2223.     else
  2224.         s++;
  2225.     if (!*t && nl) {
  2226.     t[0] = Nularg;
  2227.     t[1] = '\0';
  2228.     }
  2229. }
  2230.  
  2231. /* qualifier functions:  mostly self-explanatory, see glob(). */
  2232.  
  2233. /* device number */
  2234.  
  2235. /**/
  2236. int
  2237. qualdev(struct stat *buf, long dv)
  2238. {
  2239.     return buf->st_dev == dv;
  2240. }
  2241.  
  2242. /* number of hard links to file */
  2243.  
  2244. /**/
  2245. int
  2246. qualnlink(struct stat *buf, long ct)
  2247. {
  2248.     return (range < 0 ? buf->st_nlink < ct :
  2249.         range > 0 ? buf->st_nlink > ct :
  2250.         buf->st_nlink == ct);
  2251. }
  2252.  
  2253. /* user ID */
  2254.  
  2255. /**/
  2256. int
  2257. qualuid(struct stat *buf, long uid)
  2258. {
  2259.     return buf->st_uid == uid;
  2260. }
  2261.  
  2262. /* group ID */
  2263.  
  2264. /**/
  2265. int
  2266. qualgid(struct stat *buf, long gid)
  2267. {
  2268.     return buf->st_gid == gid;
  2269. }
  2270.  
  2271. /* device special file? */
  2272.  
  2273. /**/
  2274. int
  2275. qualisdev(struct stat *buf, long junk)
  2276. {
  2277.     junk = buf->st_mode & S_IFMT;
  2278.     return junk == S_IFBLK || junk == S_IFCHR;
  2279. }
  2280.  
  2281. /* block special file? */
  2282.  
  2283. /**/
  2284. int
  2285. qualisblk(struct stat *buf, long junk)
  2286. {
  2287.     junk = buf->st_mode & S_IFMT;
  2288.     return junk == S_IFBLK;
  2289. }
  2290.  
  2291. /* character special file? */
  2292.  
  2293. /**/
  2294. int
  2295. qualischar(struct stat *buf, long junk)
  2296. {
  2297.     junk = buf->st_mode & S_IFMT;
  2298.     return junk == S_IFCHR;
  2299. }
  2300.  
  2301. /* file type is requested one */
  2302.  
  2303. /**/
  2304. int
  2305. qualmode(struct stat *buf, long mod)
  2306. {
  2307.     return (buf->st_mode & S_IFMT) == mod;
  2308. }
  2309.  
  2310. /* given flag is set in mode */
  2311.  
  2312. /**/
  2313. int
  2314. qualflags(struct stat *buf, long mod)
  2315. {
  2316.     return buf->st_mode & mod;
  2317. }
  2318.  
  2319. /* mode matches number supplied exactly  */
  2320.  
  2321. /**/
  2322. int
  2323. qualeqflags(struct stat *buf, long mod)
  2324. {
  2325.     return (buf->st_mode & 07777) == mod;
  2326. }
  2327.  
  2328. /* regular executable file? */
  2329.  
  2330. /**/
  2331. int
  2332. qualiscom(struct stat *buf, long mod)
  2333. {
  2334.     return (buf->st_mode & (S_IFMT | S_IEXEC)) == (S_IFREG | S_IEXEC);
  2335. }
  2336.  
  2337. /* size in required range? */
  2338.  
  2339. /**/
  2340. int
  2341. qualsize(struct stat *buf, long size)
  2342. {
  2343.     unsigned long scaled = buf->st_size;
  2344.  
  2345.     switch (units) {
  2346.     case TT_POSIX_BLOCKS:
  2347.     scaled += 511l;
  2348.     scaled /= 512l;
  2349.     break;
  2350.     case TT_KILOBYTES:
  2351.     scaled += 1023l;
  2352.     scaled /= 1024l;
  2353.     break;
  2354.     case TT_MEGABYTES:
  2355.     scaled += 1048575l;
  2356.     scaled /= 1048576l;
  2357.     break;
  2358.     }
  2359.  
  2360.     return (range < 0 ? scaled < (unsigned long) size :
  2361.         range > 0 ? scaled > (unsigned long) size :
  2362.         scaled == (unsigned long) size);
  2363. }
  2364.  
  2365. /* time in required range? */
  2366.  
  2367. /**/
  2368. int
  2369. qualtime(struct stat *buf, long days)
  2370. {
  2371.     time_t now, diff;
  2372.  
  2373.     time(&now);
  2374.     diff = now - (amc == 0 ? buf->st_atime : amc == 1 ? buf->st_mtime :
  2375.           buf->st_ctime);
  2376.     /* handle multipliers indicating units */
  2377.     switch (units) {
  2378.     case TT_DAYS:
  2379.     diff /= 86400l;
  2380.     break;
  2381.     case TT_HOURS:
  2382.     diff /= 3600l;
  2383.     break;
  2384.     case TT_MINS:
  2385.     diff /= 60l;
  2386.     break;
  2387.     case TT_WEEKS:
  2388.     diff /= 604800l;
  2389.     break;
  2390.     case TT_MONTHS:
  2391.     diff /= 2592000l;
  2392.     break;
  2393.     }
  2394.  
  2395.     return (range < 0 ? diff < days :
  2396.         range > 0 ? diff > days :
  2397.         diff == days);
  2398. }
  2399.  
  2400.