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 /*
 226  * Note, some of these tests were duplicated from a patch file I found
 227  *  in an email, so I am unsure what the license is.  Since this code is
 228  *  never turned on in any release, it probably doesn't matter at all.
 229  * If by some chance someone finds this to be a problem please let
 230  *  me know.
 231  */
 232 static struct test tests[] = {
 233 /*1*/  {"x", "x", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 234        {"x", "x/y", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 235        {"x", "x/y/z", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 236        {"*", "x", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 237 /*5*/  {"*", "x/y", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 238        {"*", "x/y/z", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 239        {"*x", "x", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 240        {"*x", "x/y", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 241        {"*x", "x/y/z", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 242 /*10*/ {"x*", "x", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 243        {"x*", "x/y", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 244        {"x*", "x/y/z", FNM_FILE_NAME | FNM_LEADING_DIR, 0},
 245        {"a*b/*", "abbb/.x", FNM_PATHNAME|FNM_PERIOD, FNM_NOMATCH},
 246        {"a*b/*", "abbb/xy", FNM_PATHNAME|FNM_PERIOD, 0},
 247 /*15*/ {"[A-[]", "A", 0, 0},
 248        {"[A-[]", "a", 0, FNM_NOMATCH},
 249        {"[a-{]", "A", 0, FNM_NOMATCH},
 250        {"[a-{]", "a", 0, 0},
 251        {"[A-[]", "A", FNM_CASEFOLD, FNM_NOMATCH},
 252 /*20*/ {"[A-[]", "a", FNM_CASEFOLD, FNM_NOMATCH},
 253        {"[a-{]", "A", FNM_CASEFOLD, 0},
 254        {"[a-{]", "a", FNM_CASEFOLD, 0},
 255        { "*LIB*", "lib", FNM_PERIOD, FNM_NOMATCH },
 256        { "*LIB*", "lib", FNM_CASEFOLD, 0},
 257 /*25*/ { "a[/]b", "a/b", 0, 0},
 258        { "a[/]b", "a/b", FNM_FILE_NAME, FNM_NOMATCH },
 259        { "[a-z]/[a-z]", "a/b", 0, 0 },
 260        { "a/b", "*", FNM_FILE_NAME, FNM_NOMATCH },
 261        { "*", "a/b", FNM_FILE_NAME, FNM_NOMATCH },
 262        { "*[/]b", "a/b", FNM_FILE_NAME, FNM_NOMATCH },
 263 /*30*/ { "\\[/b", "[/b", 0, 0 },
 264        { "?\?/b", "aa/b", 0, 0 },
 265        { "???b", "aa/b", 0, 0 },
 266        { "???b", "aa/b", FNM_FILE_NAME, FNM_NOMATCH },
 267        { "?a/b", ".a/b", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 268 /*35*/ { "a/?b", "a/.b", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 269        { "*a/b", ".a/b", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 270        { "a/*b", "a/.b", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 271        { "[.]a/b", ".a/b", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 272        { "a/[.]b", "a/.b", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 273 /*40*/ { "*/?", "a/b", FNM_FILE_NAME|FNM_PERIOD, 0 },
 274        { "?/*", "a/b", FNM_FILE_NAME|FNM_PERIOD, 0 },
 275        { ".*/?", ".a/b", FNM_FILE_NAME|FNM_PERIOD, 0 },
 276        { "*/.?", "a/.b", FNM_FILE_NAME|FNM_PERIOD, 0 },
 277        { "*/*", "a/.b", FNM_FILE_NAME|FNM_PERIOD, FNM_NOMATCH },
 278 /*45*/ { "*[.]/b", "a./b", FNM_FILE_NAME|FNM_PERIOD, 0 },
 279        { "a?b", "a.b", FNM_FILE_NAME|FNM_PERIOD, 0 },
 280        { "a*b", "a.b", FNM_FILE_NAME|FNM_PERIOD, 0 },
 281        { "a[.]b", "a.b", FNM_FILE_NAME|FNM_PERIOD, 0 },
 282 /*49*/ { "*a*", "a/b", FNM_FILE_NAME|FNM_LEADING_DIR, 0 },
 283 #ifdef FULL_TEST
 284        /* This test takes a *long* time */
 285        {"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*",
 286           "aaaabbbbccccddddeeeeffffgggghhhhiiiijjjjkkkkllllmmmm"
 287           "nnnnooooppppqqqqrrrrssssttttuuuuvvvvwwwwxxxxyyyy", 0, FNM_NOMATCH},
 288 #endif
 289
 290        /* Keep dummy last to avoid compiler warnings */
 291        {"dummy", "dummy", 0, 0}
 292
 293 };
 294
 295 #define ntests ((int)(sizeof(tests)/sizeof(struct test)))
 296
 297 int main()
 298 {
 299    bool fail = false;
 300    for (int i=0; i<ntests; i++) {
 301       if (fnmatch(tests[i].pattern, tests[i].string, tests[i].options) != tests[i].result) {
 302          printf("Test %d failed: pat=%s str=%s expect=%s got=%s\n",
 303             i+1, tests[i].pattern, tests[i].string,
 304             tests[i].result==0?"matches":"no match",
 305             tests[i].result==0?"no match":"matches");
 306          fail = true;
 307       } else {
 308          printf("Test %d succeeded\n", i+1);
 309       }
 310    }
 311    return fail;
 312 }
 313 #endif /* TEST_PROGRAM */