git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/fnmatch.c

   1 /*
   2  * Copyright (c) 1989, 1993, 1994
   3  *      The Regents of the University of California.  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. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 /* OpenBSD: fnmatch.c,v 1.6 1998/03/19 00:29:59 millert */
  34
  35 /*
  36  * Function fnmatch() as specified in POSIX 1003.2-1992, section B.6.
  37  * Compares a filename or pathname to a pattern.
  38  */
  39
  40 /* Version: $Id$ */
  41
  42 /* Define SYS to use the system fnmatch() rather than ours */
  43 /* #define SYS 1 */
  44
  45 #include "bacula.h"
  46 #ifdef SYS
  47 #include <fnmatch.h>
  48 #else
  49 #include "fnmatch.h"
  50 #endif
  51
  52 #undef  EOS
  53 #define EOS     '\0'
  54
  55 #define RANGE_MATCH     1
  56 #define RANGE_NOMATCH   0
  57 #define RANGE_ERROR     (-1)
  58
  59 #define ISSET(x, y) ((x) & (y))
  60 #define FOLD(c) ((flags & FNM_CASEFOLD) && B_ISUPPER(c) ? tolower(c) : (c))
  61
  62 static int rangematch(const char *, char, int, char **);
  63
  64 #ifdef SYS
  65 int xfnmatch(const char *pattern, const char *string, int flags)
  66 #else
  67 int fnmatch(const char *pattern, const char *string, int flags)
  68 #endif
  69 {
  70    const char *stringstart;
  71    char *newp;
  72    char c, test;
  73
  74    stringstart = string;
  75    for ( ;; ) {
  76       switch (c = *pattern++) {
  77       case EOS:
  78          if (ISSET(flags, FNM_LEADING_DIR) && IsPathSeparator(*string))
  79             return (0);
  80          return (*string == EOS ? 0 : FNM_NOMATCH);
  81       case '?':
  82          if (*string == EOS)
  83             return (FNM_NOMATCH);
  84          if (*string == '/' && ISSET(flags, FNM_PATHNAME))
  85             return (FNM_NOMATCH);
  86          if (*string == '.' && ISSET(flags, FNM_PERIOD) &&
  87              (string == stringstart ||
  88               (ISSET(flags, FNM_PATHNAME) && IsPathSeparator(*(string - 1)))))
  89             return (FNM_NOMATCH);
  90          ++string;
  91          break;
  92       case '*':
  93          c = *pattern;
  94          /* Collapse multiple stars. */
  95          while (c == '*')
  96             c = *++pattern;
  97
  98          if (*string == '.' && ISSET(flags, FNM_PERIOD) &&
  99              (string == stringstart ||
 100               (ISSET(flags, FNM_PATHNAME) && IsPathSeparator(*(string - 1)))))
 101             return (FNM_NOMATCH);
 102
 103          /* Optimize for pattern with * at end or before /. */
 104          if (c == EOS) {
 105             if (ISSET(flags, FNM_PATHNAME))
 106                return (ISSET(flags, FNM_LEADING_DIR) ||
 107                        strchr(string, '/') == NULL ? 0 : FNM_NOMATCH);
 108             else
 109                return (0);
 110          } else if (c == '/' && ISSET(flags, FNM_PATHNAME)) {
 111             if ((string = strchr(string, '/')) == NULL)
 112                return (FNM_NOMATCH);
 113             break;
 114          }
 115
 116          /* General case, use recursion. */
 117          while ((test = *string) != EOS) {
 118             if (!fnmatch(pattern, string, flags & ~FNM_PERIOD))
 119                return (0);
 120             if (test == '/' && ISSET(flags, FNM_PATHNAME))
 121                break;
 122             ++string;
 123          }
 124          return (FNM_NOMATCH);
 125       case '[':
 126          if (*string == EOS)
 127             return (FNM_NOMATCH);
 128          if (IsPathSeparator(*string) && ISSET(flags, FNM_PATHNAME))
 129             return (FNM_NOMATCH);
 130          if (*string == '.' && ISSET(flags, FNM_PERIOD) &&
 131              (string == stringstart ||
 132               (ISSET(flags, FNM_PATHNAME) && IsPathSeparator(*(string - 1)))))
 133             return (FNM_NOMATCH);
 134
 135          switch (rangematch(pattern, *string, flags, &newp)) {
 136          case RANGE_ERROR:
 137             /* not a good range, treat as normal text */
 138             goto normal;
 139          case RANGE_MATCH:
 140             pattern = newp;
 141             break;
 142          case RANGE_NOMATCH:
 143             return (FNM_NOMATCH);
 144          }
 145          ++string;
 146          break;
 147       case '\\':
 148          if (!ISSET(flags, FNM_NOESCAPE)) {
 149             if ((c = *pattern++) == EOS) {
 150                c = '\\';
 151                --pattern;
 152             }
 153          }
 154          /* FALLTHROUGH */
 155       default:
 156        normal:
 157          if (FOLD(c) != FOLD(*string)) {
 158             return (FNM_NOMATCH);
 159          }
 160          ++string;
 161          break;
 162       }
 163    }
 164    /* NOTREACHED */
 165 }
 166
 167 static int rangematch(const char *pattern, char test, int flags,
 168                       char **newp)
 169 {
 170    int negate, ok;
 171    char c, c2;
 172
 173    /*
 174     * A bracket expression starting with an unquoted circumflex
 175     * character produces unspecified results (IEEE 1003.2-1992,
 176     * 3.13.2).  This implementation treats it like '!', for
 177     * consistency with the regular expression syntax.
 178     * J.T. Conklin (conklin@ngai.kaleida.com)
 179     */
 180    if ((negate = (*pattern == '!' || *pattern == '^')))
 181       ++pattern;
 182
 183    test = FOLD(test);
 184
 185    /*
 186     * A right bracket shall lose its special meaning and represent
 187     * itself in a bracket expression if it occurs first in the list.
 188     * -- POSIX.2 2.8.3.2
 189     */
 190    ok = 0;
 191    c = *pattern++;
 192    do {
 193       if (c == '\\' && !ISSET(flags, FNM_NOESCAPE))
 194          c = *pattern++;
 195       if (c == EOS)
 196          return (RANGE_ERROR);
 197       if (c == '/' && ISSET(flags, FNM_PATHNAME))
 198          return (RANGE_NOMATCH);
 199       c = FOLD(c);
 200       if (*pattern == '-' && (c2 = *(pattern + 1)) != EOS && c2 != ']') {
 201          pattern += 2;
 202          if (c2 == '\\' && !ISSET(flags, FNM_NOESCAPE))
 203             c2 = *pattern++;
 204          if (c2 == EOS)
 205             return (RANGE_ERROR);
 206          c2 = FOLD(c2);
 207          if (c <= test && test <= c2)
 208             ok = 1;
 209       } else if (c == test)
 210          ok = 1;
 211    } while ((c = *pattern++) != ']');
 212
 213    *newp = (char *) pattern;
 214    return (ok == negate ? RANGE_NOMATCH : RANGE_MATCH);
 215 }
 216
 217 #ifdef TEST_PROGRAM
 218 struct test {
 219    const char *pattern;
 220    const char *string;
 221    const int options;
 222    const int result;
 223 };
 224
 225 static struct test tests[] = {
 226 /*1*/  {"x", "x", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 227        {"x", "x/y", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 228        {"x", "x/y/z", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 229        {"*", "x", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 230 /*5*/  {"*", "x/y", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 231        {"*", "x/y/z", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 232        {"*x", "x", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 233        {"*x", "x/y", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 234        {"*x", "x/y/z", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 235 /*10*/ {"x*", "x", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 236        {"x*", "x/y", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 237        {"x*", "x/y/z", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 238        {"a*b/*", "abbb/.x", FNM_PATHNAME|FNM_PERIOD, FNM_NOMATCH},   /* ??? */
 239        {"a*b/*", "abbb/xy", FNM_PATHNAME|FNM_PERIOD, 0},
 240 /*15*/ {"[A-[]", "A", 0, 0},
 241        {"[A-[]", "a", 0, FNM_NOMATCH},
 242        {"[a-{]", "A", 0, FNM_NOMATCH},
 243        {"[a-{]", "a", 0, 0},
 244        {"[A-[]", "A", FNM_CASEFOLD, FNM_NOMATCH},
 245 /*20*/ {"[A-[]", "a", FNM_CASEFOLD, FNM_NOMATCH},
 246        {"[a-{]", "A", FNM_CASEFOLD, 0},
 247        {"[a-{]", "a", FNM_CASEFOLD, 0},
 248        { "lib", "*LIB*", FNM_PERIOD, FNM_NOMATCH },
 249        { "lib", "*LIB*", FNM_CASEFOLD, 0},              /* ??? */
 250 /*25*/ { "a/b", "a[/]b", 0, 0},                         /* ??? */
 251        { "a/b", "a[/]b", FNM_FILE_NAME, FNM_NOMATCH },
 252        { "a/b", "[a-z]/[a-z]", 0, 0 },                  /* ??? */
 253        { "a/b", "*", FNM_FILE_NAME, FNM_NOMATCH },
 254        { "a/b", "*[/]b", FNM_FILE_NAME, FNM_NOMATCH },
 255 /*30*/ { "[/b", "\\[/b", 0, 0 },                       /* ??? */
 256        { "aa/b", "?\?/b", 0, 0 },                      /* ??? */
 257        { "aa/b", "???b", 0, 0 },                       /* ??? */
 258        { "aa/b", "???b", FNM_FILE_NAME, FNM_NOMATCH },
 259        { ".a/b", "?a/b", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 260 /*35*/ { "a/.b", "a/?b", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 261        { ".a/b", "*a/b", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 262        { "a/.b", "a/*b", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 263        { ".a/b", "[.]a/b", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 264        { "a/.b", "a/[.]b", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 265 /*40*/ { "a/b", "*/?", FNM_FILE_NAME|FNM_PERIOD, 0 },   /* ??? */
 266        { "a/b", "?/*", FNM_FILE_NAME|FNM_PERIOD, 0 },   /* ??? */
 267        { ".a/b", ".*/?", FNM_FILE_NAME|FNM_PERIOD, 0 }, /* ??? */
 268        { "a/.b", "*/.?", FNM_FILE_NAME|FNM_PERIOD, 0 }, /* ??? */
 269        { "a/.b", "*/*", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 270 /*45*/ { "a./b", "*[.]/b", FNM_FILE_NAME|FNM_PERIOD, 0 },  /* ??? */
 271        { "a.b", "a?b", FNM_FILE_NAME|FNM_PERIOD, 0 },      /* ??? */
 272        { "a.b", "a*b", FNM_FILE_NAME|FNM_PERIOD, 0 },      /* ??? */
 273        { "a.b", "a[.]b", FNM_FILE_NAME|FNM_PERIOD, 0 },    /* ??? */
 274 /*49*/ { "a/b", "*a*", FNM_FILE_NAME|FNM_LEADING_DIR, 0 }, /* ??? */
 275 #ifdef FULL_TEST
 276        /* This test takes a *long* time */
 277        {"a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z*",
 278           "aaaabbbbccccddddeeeeffffgggghhhhiiiijjjjkkkkllllmmmm"
 279           "nnnnooooppppqqqqrrrrssssttttuuuuvvvvwwwwxxxxyyyy", 0, FNM_NOMATCH},
 280 #endif
 281
 282        /* Keep dummy last to avoid compiler warnings */
 283        {"dummy", "dummy", 0, 0}
 284
 285 };
 286
 287 #define ntests ((int)(sizeof(tests)/sizeof(struct test)))
 288
 289 int main()
 290 {
 291    bool fail = false;
 292    for (int i=0; i<ntests; i++) {
 293       if (fnmatch(tests[i].pattern, tests[i].string, tests[i].options) != tests[i].result) {
 294          printf("Test %d failed: pat=%s str=%s expect=%s got=%s\n",
 295             i+1, tests[i].pattern, tests[i].string,
 296             tests[i].result==0?"matches":"no match",
 297             tests[i].result==0?"no match":"matches");
 298          fail = true;
 299       } else {
 300          printf("Test %d succeeded\n", i+1);
 301       }
 302    }
 303    return fail;
 304 }
 305 #endif /* TEST_PROGRAM */