home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / lib / libc / gen / glob.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-07  |  14.4 KB  |  596 lines
  1. /*
  2.  * Copyright (c) 1989 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Guido van Rossum.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)glob.c    5.18 (Berkeley) 12/4/92";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  * glob(3) -- a superset of the one defined in POSIX 1003.2.
  43.  *
  44.  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
  45.  *
  46.  * Optional extra services, controlled by flags not defined by POSIX:
  47.  *
  48.  * GLOB_QUOTE:
  49.  *    Escaping convention: \ inhibits any special meaning the following
  50.  *    character might have (except \ at end of string is retained).
  51.  * GLOB_MAGCHAR:
  52.  *    Set in gl_flags if pattern contained a globbing character.
  53.  * GLOB_NOMAGIC:
  54.  *    Same as GLOB_NOCHECK, but it will only append pattern if it did
  55.  *    not contain any magic characters.  [Used in csh style globbing]
  56.  * GLOB_ALTDIRFUNC:
  57.  *    Use alternately specified directory access functions.
  58.  * gl_matchc:
  59.  *    Number of matches in the current invocation of glob.
  60.  */
  61.  
  62. #include <sys/param.h>
  63. #include <sys/stat.h>
  64. #include <dirent.h>
  65. #include <glob.h>
  66. #include <ctype.h>
  67. #include <errno.h>
  68. #include <string.h>
  69. #include <stdio.h>
  70. #include <stdlib.h>
  71.  
  72. #define    DOLLAR        '$'
  73. #define    DOT        '.'
  74. #define    EOS        '\0'
  75. #define    LBRACKET    '['
  76. #define    NOT        '!'
  77. #define    QUESTION    '?'
  78. #define    QUOTE        '\\'
  79. #define    RANGE        '-'
  80. #define    RBRACKET    ']'
  81. #define    SEP        '/'
  82. #define    STAR        '*'
  83. #define    TILDE        '~'
  84. #define    UNDERSCORE    '_'
  85.  
  86. #define    M_QUOTE        0x8000
  87. #define    M_PROTECT    0x4000
  88. #define    M_MASK        0xffff
  89. #define    M_ASCII        0x00ff
  90.  
  91. #define    CHAR(c)        ((c)&M_ASCII)
  92. #define    META(c)        ((c)|M_QUOTE)
  93. #define    M_ALL        META('*')
  94. #define    M_END        META(']')
  95. #define    M_NOT        META('!')
  96. #define    M_ONE        META('?')
  97. #define    M_RNG        META('-')
  98. #define    M_SET        META('[')
  99. #define    ismeta(c)    (((c)&M_QUOTE) != 0)
  100.  
  101. typedef u_short Char;
  102.  
  103. static int     compare __P((const void *, const void *));
  104. static void     g_Ctoc __P((Char *, char *));
  105. static int     g_lstat __P((Char *, struct stat *, glob_t *));
  106. static DIR    *g_opendir __P((Char *, glob_t *));
  107. static Char    *g_strchr __P((Char *, int));
  108. static int     g_stat __P((Char *, struct stat *, glob_t *));
  109. static int     glob1 __P((Char *, glob_t *));
  110. static int     glob2 __P((Char *, Char *, Char *, glob_t *));
  111. static int     glob3 __P((Char *, Char *, Char *, Char *, glob_t *));
  112. static int     globextend __P((Char *, glob_t *));
  113. static int     match __P((Char *, Char *, Char *));
  114. #ifdef DEBUG
  115. static void     qprintf __P((Char *));
  116. #endif
  117.  
  118. /*
  119.  * The main glob() routine: compiles the pattern (optionally processing
  120.  * quotes), calls glob1() to do the real pattern matching, and finally
  121.  * sorts the list (unless unsorted operation is requested).  Returns 0
  122.  * if things went well, nonzero if errors occurred.  It is not an error
  123.  * to find no matches.
  124.  */
  125. glob(pattern, flags, errfunc, pglob)
  126.     const char *pattern;
  127.     int flags, (*errfunc) __P((char *, int));
  128.     glob_t *pglob;
  129. {
  130.     const u_char *compilepat, *patnext;
  131.     int c, err, oldpathc;
  132.     Char *bufnext, *bufend, *compilebuf, *qpatnext, patbuf[MAXPATHLEN+1];
  133.  
  134.     patnext = (u_char *) pattern;
  135.     if (!(flags & GLOB_APPEND)) {
  136.         pglob->gl_pathc = 0;
  137.         pglob->gl_pathv = NULL;
  138.         if (!(flags & GLOB_DOOFFS))
  139.             pglob->gl_offs = 0;
  140.     }
  141.     pglob->gl_flags = flags & ~GLOB_MAGCHAR;
  142.     pglob->gl_errfunc = errfunc;
  143.     oldpathc = pglob->gl_pathc;
  144.     pglob->gl_matchc = 0;
  145.  
  146.     bufnext = patbuf;
  147.     bufend = bufnext + MAXPATHLEN;
  148.     compilebuf = bufnext;
  149.     compilepat = patnext;
  150.     if (flags & GLOB_QUOTE) {
  151.         /* Protect the quoted characters. */
  152.         while (bufnext < bufend && (c = *patnext++) != EOS) 
  153.             if (c == QUOTE) {
  154.                 if ((c = *patnext++) == EOS) {
  155.                     c = QUOTE;
  156.                     --patnext;
  157.                 }
  158.                 *bufnext++ = c | M_PROTECT;
  159.             }
  160.             else
  161.                 *bufnext++ = c;
  162.     }
  163.     else 
  164.         while (bufnext < bufend && (c = *patnext++) != EOS) 
  165.             *bufnext++ = c;
  166.     *bufnext = EOS;
  167.  
  168.     bufnext = patbuf;
  169.     qpatnext = patbuf;
  170.     /* We don't need to check for buffer overflow any more. */
  171.     while ((c = *qpatnext++) != EOS) {
  172.         switch (c) {
  173.         case LBRACKET:
  174.             c = *qpatnext;
  175.             if (c == NOT)
  176.                 ++qpatnext;
  177.             if (*qpatnext == EOS ||
  178.                 g_strchr(qpatnext+1, RBRACKET) == NULL) {
  179.                 *bufnext++ = LBRACKET;
  180.                 if (c == NOT)
  181.                     --qpatnext;
  182.                 break;
  183.             }
  184.             *bufnext++ = M_SET;
  185.             if (c == NOT)
  186.                 *bufnext++ = M_NOT;
  187.             c = *qpatnext++;
  188.             do {
  189.                 *bufnext++ = CHAR(c);
  190.                 if (*qpatnext == RANGE &&
  191.                     (c = qpatnext[1]) != RBRACKET) {
  192.                     *bufnext++ = M_RNG;
  193.                     *bufnext++ = CHAR(c);
  194.                     qpatnext += 2;
  195.                 }
  196.             } while ((c = *qpatnext++) != RBRACKET);
  197.             pglob->gl_flags |= GLOB_MAGCHAR;
  198.             *bufnext++ = M_END;
  199.             break;
  200.         case QUESTION:
  201.             pglob->gl_flags |= GLOB_MAGCHAR;
  202.             *bufnext++ = M_ONE;
  203.             break;
  204.         case STAR:
  205.             pglob->gl_flags |= GLOB_MAGCHAR;
  206.             /* collapse adjacent stars to one, 
  207.              * to avoid exponential behavior
  208.              */
  209.             if (bufnext == patbuf || bufnext[-1] != M_ALL)
  210.                 *bufnext++ = M_ALL;
  211.             break;
  212.         default:
  213.             *bufnext++ = CHAR(c);
  214.             break;
  215.         }
  216.     }
  217.     *bufnext = EOS;
  218. #ifdef DEBUG
  219.     qprintf(patbuf);
  220. #endif
  221.  
  222.     if ((err = glob1(patbuf, pglob)) != 0)
  223.         return(err);
  224.  
  225.     /*
  226.      * If there was no match we are going to append the pattern 
  227.      * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
  228.      * and the pattern did not contain any magic characters
  229.      * GLOB_NOMAGIC is there just for compatibility with csh.
  230.      */
  231.     if (pglob->gl_pathc == oldpathc && 
  232.         ((flags & GLOB_NOCHECK) || 
  233.          ((flags & GLOB_NOMAGIC) && !(pglob->gl_flags & GLOB_MAGCHAR)))) {
  234.         if (!(flags & GLOB_QUOTE)) {
  235.             Char *dp = compilebuf;
  236.             const u_char *sp = compilepat;
  237.             while (*dp++ = *sp++);
  238.         }
  239.         else {
  240.             /*
  241.              * Copy pattern, interpreting quotes; this is slightly
  242.              * different than the interpretation of quotes above
  243.              * -- which should prevail?
  244.              */
  245.             while (*compilepat != EOS) {
  246.                 if (*compilepat == QUOTE) {
  247.                     if (*++compilepat == EOS)
  248.                         --compilepat;
  249.                 }
  250.                 *compilebuf++ = (u_char)*compilepat++;
  251.             }
  252.             *compilebuf = EOS;
  253.         }
  254.         return(globextend(patbuf, pglob));
  255.     } else if (!(flags & GLOB_NOSORT)) 
  256.         qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
  257.             pglob->gl_pathc - oldpathc, sizeof(char *), compare);
  258.     return(0);
  259. }
  260.  
  261. static int
  262. compare(p, q)
  263.     const void *p, *q;
  264. {
  265.     return(strcmp(*(char **)p, *(char **)q));
  266. }
  267.  
  268. static
  269. glob1(pattern, pglob)
  270.     Char *pattern;
  271.     glob_t *pglob;
  272. {
  273.     Char pathbuf[MAXPATHLEN+1];
  274.  
  275.     /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
  276.     if (*pattern == EOS)
  277.         return(0);
  278.     return(glob2(pathbuf, pathbuf, pattern, pglob));
  279. }
  280.  
  281. /*
  282.  * The functions glob2 and glob3 are mutually recursive; there is one level
  283.  * of recursion for each segment in the pattern that contains one or more
  284.  * meta characters.
  285.  */
  286. static
  287. glob2(pathbuf, pathend, pattern, pglob)
  288.     Char *pathbuf, *pathend, *pattern;
  289.     glob_t *pglob;
  290. {
  291.     struct stat sb;
  292.     Char *p, *q;
  293.     int anymeta;
  294.  
  295.     /*
  296.      * Loop over pattern segments until end of pattern or until
  297.      * segment with meta character found.
  298.      */
  299.     for (anymeta = 0;;) {
  300.         if (*pattern == EOS) {        /* End of pattern? */
  301.             *pathend = EOS;
  302.             if (g_lstat(pathbuf, &sb, pglob))
  303.                 return(0);
  304.         
  305.             if (((pglob->gl_flags & GLOB_MARK) &&
  306.                 pathend[-1] != SEP) && (S_ISDIR(sb.st_mode)
  307.                 || (S_ISLNK(sb.st_mode) &&
  308.                 (g_stat(pathbuf, &sb, pglob) == 0) &&
  309.                 S_ISDIR(sb.st_mode)))) {
  310.                 *pathend++ = SEP;
  311.                 *pathend = EOS;
  312.             }
  313.             ++pglob->gl_matchc;
  314.             return(globextend(pathbuf, pglob));
  315.         }
  316.  
  317.         /* Find end of next segment, copy tentatively to pathend. */
  318.         q = pathend;
  319.         p = pattern;
  320.         while (*p != EOS && *p != SEP) {
  321.             if (ismeta(*p))
  322.                 anymeta = 1;
  323.             *q++ = *p++;
  324.         }
  325.  
  326.         if (!anymeta) {        /* No expansion, do next segment. */
  327.             pathend = q;
  328.             pattern = p;
  329.             while (*pattern == SEP)
  330.                 *pathend++ = *pattern++;
  331.         } else            /* Need expansion, recurse. */
  332.             return(glob3(pathbuf, pathend, pattern, p, pglob));
  333.     }
  334.     /* NOTREACHED */
  335. }
  336.  
  337. static
  338. glob3(pathbuf, pathend, pattern, restpattern, pglob)
  339.     Char *pathbuf, *pathend, *pattern, *restpattern;
  340.     glob_t *pglob;
  341. {
  342.     register struct dirent *dp;
  343.     struct dirent *(*readdirfunc)();
  344.     DIR *dirp;
  345.     int len, err;
  346.     char buf[MAXPATHLEN];
  347.  
  348.     *pathend = EOS;
  349.     errno = 0;
  350.         
  351.     if ((dirp = g_opendir(pathbuf, pglob)) == NULL) {
  352.         /* TODO: don't call for ENOENT or ENOTDIR? */
  353.         if (pglob->gl_errfunc) {
  354.             g_Ctoc(pathbuf, buf);
  355.             if (pglob->gl_errfunc(buf, errno) ||
  356.                 pglob->gl_flags & GLOB_ERR)
  357.                 return (GLOB_ABEND);
  358.         }
  359.         return(0);
  360.     }
  361.  
  362.     err = 0;
  363.  
  364.     /* Search directory for matching names. */
  365.     if (pglob->gl_flags & GLOB_ALTDIRFUNC)
  366.         readdirfunc = pglob->gl_readdir;
  367.     else
  368.         readdirfunc = readdir;
  369.     while ((dp = (*readdirfunc)(dirp))) {
  370.         register u_char *sc;
  371.         register Char *dc;
  372.  
  373.         /* Initial DOT must be matched literally. */
  374.         if (dp->d_name[0] == DOT && *pattern != DOT)
  375.             continue;
  376.         for (sc = (u_char *) dp->d_name, dc = pathend; 
  377.              *dc++ = *sc++;);
  378.         if (!match(pathend, pattern, restpattern)) {
  379.             *pathend = EOS;
  380.             continue;
  381.         }
  382.         err = glob2(pathbuf, --dc, restpattern, pglob);
  383.         if (err)
  384.             break;
  385.     }
  386.  
  387.     if (pglob->gl_flags & GLOB_ALTDIRFUNC)
  388.         (*pglob->gl_closedir)(dirp);
  389.     else
  390.         closedir(dirp);
  391.     return(err);
  392. }
  393.  
  394.  
  395. /*
  396.  * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
  397.  * add the new item, and update gl_pathc.
  398.  *
  399.  * This assumes the BSD realloc, which only copies the block when its size
  400.  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
  401.  * behavior.
  402.  *
  403.  * Return 0 if new item added, error code if memory couldn't be allocated.
  404.  *
  405.  * Invariant of the glob_t structure:
  406.  *    Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
  407.  *    gl_pathv points to (gl_offs + gl_pathc + 1) items.
  408.  */
  409. static int
  410. globextend(path, pglob)
  411.     Char *path;
  412.     glob_t *pglob;
  413. {
  414.     register char **pathv;
  415.     register int i;
  416.     u_int newsize;
  417.     char *copy;
  418.     Char *p;
  419.  
  420.     newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
  421.     pathv = (char **)realloc((char *)pglob->gl_pathv, newsize);
  422.     if (pathv == NULL)
  423.         return(GLOB_NOSPACE);
  424.  
  425.     if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
  426.         /* first time around -- clear initial gl_offs items */
  427.         pathv += pglob->gl_offs;
  428.         for (i = pglob->gl_offs; --i >= 0; )
  429.             *--pathv = NULL;
  430.     }
  431.     pglob->gl_pathv = pathv;
  432.  
  433.     for (p = path; *p++;);
  434.     if ((copy = malloc(p - path)) != NULL) {
  435.         g_Ctoc(path, copy);
  436.         pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
  437.     }
  438.     pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
  439.     return(copy == NULL ? GLOB_NOSPACE : 0);
  440. }
  441.  
  442.  
  443. /*
  444.  * pattern matching function for filenames.  Each occurrence of the *
  445.  * pattern causes a recursion level.
  446.  */
  447. static
  448. match(name, pat, patend)
  449.     register Char *name, *pat, *patend;
  450. {
  451.     int ok, negate_range;
  452.     Char c, k;
  453.  
  454.     while (pat < patend) {
  455.         c = *pat++;
  456.         switch (c & M_MASK) {
  457.         case M_ALL:
  458.             if (pat == patend)
  459.                 return(1);
  460.             do 
  461.                 if (match(name, pat, patend))
  462.                     return(1);
  463.             while (*name++ != EOS);
  464.             return(0);
  465.         case M_ONE:
  466.             if (*name++ == EOS)
  467.                 return(0);
  468.             break;
  469.         case M_SET:
  470.             ok = 0;
  471.             if ((k = *name++) == EOS)
  472.                 return(0);
  473.             if (negate_range = ((*pat & M_MASK) == M_NOT))
  474.                 ++pat;
  475.             while (((c = *pat++) & M_MASK) != M_END)
  476.                 if ((*pat & M_MASK) == M_RNG) {
  477.                     if (c <= k && k <= pat[1])
  478.                         ok = 1;
  479.                     pat += 2;
  480.                 } else if (c == k)
  481.                     ok = 1;
  482.             if (ok == negate_range)
  483.                 return(0);
  484.             break;
  485.         default:
  486.             if (*name++ != c)
  487.                 return(0);
  488.             break;
  489.         }
  490.     }
  491.     return(*name == EOS);
  492. }
  493.  
  494. /* Free allocated data belonging to a glob_t structure. */
  495. void
  496. globfree(pglob)
  497.     glob_t *pglob;
  498. {
  499.     register int i;
  500.     register char **pp;
  501.  
  502.     if (pglob->gl_pathv != NULL) {
  503.         pp = pglob->gl_pathv + pglob->gl_offs;
  504.         for (i = pglob->gl_pathc; i--; ++pp)
  505.             if (*pp)
  506.                 free(*pp);
  507.         free(pglob->gl_pathv);
  508.     }
  509. }
  510.  
  511. static DIR *
  512. g_opendir(str, pglob)
  513.     register Char *str;
  514.     glob_t *pglob;
  515. {
  516.     char buf[MAXPATHLEN];
  517.     char *dirname;
  518.  
  519.     if (!*str)
  520.         strcpy(buf, ".");
  521.     else
  522.         g_Ctoc(str, buf);
  523.     if (pglob->gl_flags & GLOB_ALTDIRFUNC)
  524.         return((*pglob->gl_opendir)(buf));
  525.     return(opendir(buf));
  526. }
  527.  
  528. static int
  529. g_lstat(fn, sb, pglob)
  530.     register Char *fn;
  531.     struct stat *sb;
  532.     glob_t *pglob;
  533. {
  534.     char buf[MAXPATHLEN];
  535.  
  536.     g_Ctoc(fn, buf);
  537.     if (pglob->gl_flags & GLOB_ALTDIRFUNC)
  538.         return((*pglob->gl_lstat)(buf, sb));
  539.     return(lstat(buf, sb));
  540. }
  541.  
  542. static int
  543. g_stat(fn, sb, pglob)
  544.     register Char *fn;
  545.     struct stat *sb;
  546.     glob_t *pglob;
  547. {
  548.     char buf[MAXPATHLEN];
  549.  
  550.     g_Ctoc(fn, buf);
  551.     if (pglob->gl_flags & GLOB_ALTDIRFUNC)
  552.         return((*pglob->gl_stat)(buf, sb));
  553.     return(stat(buf, sb));
  554. }
  555.  
  556. static Char *
  557. g_strchr(str, ch)
  558.     Char *str;
  559.     int ch;
  560. {
  561.     do {
  562.         if (*str == ch)
  563.             return (str);
  564.     } while (*str++);
  565.     return (NULL);
  566. }
  567.  
  568. static void
  569. g_Ctoc(str, buf)
  570.     register Char *str;
  571.     char *buf;
  572. {
  573.     register char *dc;
  574.  
  575.     for (dc = buf; *dc++ = *str++;);
  576. }
  577.  
  578. #ifdef DEBUG
  579. static void 
  580. qprintf(s)
  581.     register Char *s;
  582. {
  583.     register Char *p;
  584.  
  585.     for (p = s; *p; p++)
  586.         (void)printf("%c", CHAR(*p));
  587.     (void)printf("\n");
  588.     for (p = s; *p; p++)
  589.         (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
  590.     (void)printf("\n");
  591.     for (p = s; *p; p++)
  592.         (void)printf("%c", ismeta(*p) ? '_' : ' ');
  593.     (void)printf("\n");
  594. }
  595. #endif
  596.