lib/curl_fnmatch.c

   1 /***************************************************************************
   2  *                                  _   _ ____  _
   3  *  Project                     ___| | | |  _ \| |
   4  *                             / __| | | | |_) | |
   5  *                            | (__| |_| |  _ <| |___
   6  *                             \___|\___/|_| \_\_____|
   7  *
   8  * Copyright (C) 1998 - 2010, Daniel Stenberg, <daniel@haxx.se>, et al.
   9  *
  10  * This software is licensed as described in the file COPYING, which
  11  * you should have received as part of this distribution. The terms
  12  * are also available at http://curl.haxx.se/docs/copyright.html.
  13  *
  14  * You may opt to use, copy, modify, merge, publish, distribute and/or sell
  15  * copies of the Software, and permit persons to whom the Software is
  16  * furnished to do so, under the terms of the COPYING file.
  17  *
  18  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  19  * KIND, either express or implied.
  20  *
  21  ***************************************************************************/
  22
  23 #include "curl_fnmatch.h"
  24 #include "setup.h"
  25
  26 #define CURLFNM_CHARSET_LEN (sizeof(char) * 256)
  27 #define CURLFNM_CHSET_SIZE (CURLFNM_CHARSET_LEN + 15)
  28
  29 #define CURLFNM_NEGATE  CURLFNM_CHARSET_LEN
  30
  31 #define CURLFNM_ALNUM   (CURLFNM_CHARSET_LEN + 1)
  32 #define CURLFNM_DIGIT   (CURLFNM_CHARSET_LEN + 2)
  33 #define CURLFNM_XDIGIT  (CURLFNM_CHARSET_LEN + 3)
  34 #define CURLFNM_ALPHA   (CURLFNM_CHARSET_LEN + 4)
  35 #define CURLFNM_PRINT   (CURLFNM_CHARSET_LEN + 5)
  36 #define CURLFNM_BLANK   (CURLFNM_CHARSET_LEN + 6)
  37 #define CURLFNM_LOWER   (CURLFNM_CHARSET_LEN + 7)
  38 #define CURLFNM_GRAPH   (CURLFNM_CHARSET_LEN + 8)
  39 #define CURLFNM_SPACE   (CURLFNM_CHARSET_LEN + 9)
  40 #define CURLFNM_UPPER   (CURLFNM_CHARSET_LEN + 10)
  41
  42 typedef enum {
  43   CURLFNM_LOOP_DEFAULT = 0,
  44   CURLFNM_LOOP_BACKSLASH
  45 } loop_state;
  46
  47 typedef enum {
  48   CURLFNM_SCHS_DEFAULT = 0,
  49   CURLFNM_SCHS_MAYRANGE,
  50   CURLFNM_SCHS_MAYRANGE2,
  51   CURLFNM_SCHS_RIGHTBR,
  52   CURLFNM_SCHS_RIGHTBRLEFTBR
  53 } setcharset_state;
  54
  55 typedef enum {
  56   CURLFNM_PKW_INIT = 0,
  57   CURLFNM_PKW_DDOT
  58 } parsekey_state;
  59
  60 #define SETCHARSET_OK     1
  61 #define SETCHARSET_FAIL   0
  62
  63 static int parsekeyword(unsigned char **pattern, unsigned char *charset)
  64 {
  65   parsekey_state state = CURLFNM_PKW_INIT;
  66 #define KEYLEN 10
  67   char keyword[KEYLEN] = { 0 };
  68   int found = FALSE;
  69   int i;
  70   register unsigned char *p = *pattern;
  71   for(i = 0; !found; i++) {
  72     char c = *p++;
  73     if(i >= KEYLEN)
  74       return SETCHARSET_FAIL;
  75     switch(state) {
  76     case CURLFNM_PKW_INIT:
  77       if(ISALPHA(c) && ISLOWER(c))
  78         keyword[i] = c;
  79       else if(c == ':')
  80         state = CURLFNM_PKW_DDOT;
  81       else
  82         return 0;
  83       break;
  84     case CURLFNM_PKW_DDOT:
  85       if(c == ']')
  86         found = TRUE;
  87       else
  88         return SETCHARSET_FAIL;
  89     }
  90   }
  91 #undef KEYLEN
  92
  93   *pattern = p; /* move caller's pattern pointer */
  94   if(strcmp(keyword, "digit") == 0)
  95     charset[CURLFNM_DIGIT] = 1;
  96   else if(strcmp(keyword, "alnum") == 0)
  97     charset[CURLFNM_ALNUM] = 1;
  98   else if(strcmp(keyword, "alpha") == 0)
  99     charset[CURLFNM_ALPHA] = 1;
 100   else if(strcmp(keyword, "xdigit") == 0)
 101     charset[CURLFNM_XDIGIT] = 1;
 102   else if(strcmp(keyword, "print") == 0)
 103     charset[CURLFNM_PRINT] = 1;
 104   else if(strcmp(keyword, "graph") == 0)
 105     charset[CURLFNM_GRAPH] = 1;
 106   else if(strcmp(keyword, "space") == 0)
 107     charset[CURLFNM_SPACE] = 1;
 108   else if(strcmp(keyword, "blank") == 0)
 109     charset[CURLFNM_BLANK] = 1;
 110   else if(strcmp(keyword, "upper") == 0)
 111     charset[CURLFNM_UPPER] = 1;
 112   else if(strcmp(keyword, "lower") == 0)
 113     charset[CURLFNM_LOWER] = 1;
 114   else
 115     return SETCHARSET_FAIL;
 116   return SETCHARSET_OK;
 117 }
 118
 119 /* returns 1 (true) if pattern is OK, 0 if is bad ("p" is pattern pointer) */
 120 static int setcharset(unsigned char **p, unsigned char *charset)
 121 {
 122   setcharset_state state = CURLFNM_SCHS_DEFAULT;
 123   unsigned char rangestart = 0;
 124   unsigned char lastchar   = 0;
 125   bool something_found = FALSE;
 126   register unsigned char c;
 127   for(;;) {
 128     c = **p;
 129     switch(state) {
 130     case CURLFNM_SCHS_DEFAULT:
 131       if(ISALNUM(c)) { /* ASCII value */
 132         rangestart = c;
 133         charset[c] = 1;
 134         (*p)++;
 135         state = CURLFNM_SCHS_MAYRANGE;
 136         something_found = TRUE;
 137       }
 138       else if(c == ']') {
 139         if(something_found)
 140           return SETCHARSET_OK;
 141         else
 142           something_found = TRUE;
 143         state = CURLFNM_SCHS_RIGHTBR;
 144         charset[c] = 1;
 145         (*p)++;
 146       }
 147       else if(c == '[') {
 148         char c2 = *((*p)+1);
 149         if(c2 == ':') { /* there has to be a keyword */
 150           (*p) += 2;
 151           if(parsekeyword(p, charset)) {
 152             state = CURLFNM_SCHS_DEFAULT;
 153           }
 154           else
 155             return SETCHARSET_FAIL;
 156         }
 157         else {
 158           charset[c] = 1;
 159           (*p)++;
 160         }
 161         something_found = TRUE;
 162       }
 163       else if(c == '?' || c == '*') {
 164         something_found = TRUE;
 165         charset[c] = 1;
 166         (*p)++;
 167       }
 168       else if(c == '^' || c == '!') {
 169         if(!something_found) {
 170           if(charset[CURLFNM_NEGATE]) {
 171             charset[c] = 1;
 172             something_found = 1;
 173           }
 174           else
 175             charset[CURLFNM_NEGATE] = 1; /* negate charset */
 176         }
 177         else
 178           charset[c] = 1;
 179         (*p)++;
 180       }
 181       else if(c == '\\') {
 182         c = *(++(*p));
 183         if(ISPRINT((c))) {
 184           something_found = TRUE;
 185           state = CURLFNM_SCHS_MAYRANGE;
 186           charset[c] = 1;
 187           rangestart = c;
 188           (*p)++;
 189         }
 190         else
 191           return SETCHARSET_FAIL;
 192       }
 193       else if(c == '\0') {
 194         return SETCHARSET_FAIL;
 195       }
 196       else {
 197         charset[c] = 1;
 198         (*p)++;
 199         something_found = TRUE;
 200       }
 201       break;
 202     case CURLFNM_SCHS_MAYRANGE:
 203       if(c == '-') {
 204         charset[c] = 1;
 205         (*p)++;
 206         lastchar = '-';
 207         state = CURLFNM_SCHS_MAYRANGE2;
 208       }
 209       else if(c == '[') {
 210         state = CURLFNM_SCHS_DEFAULT;
 211       }
 212       else if(ISALNUM(c)) {
 213         charset[c] = 1;
 214         (*p)++;
 215       }
 216       else if(c == '\\') {
 217         c = *(++(*p));
 218         if(isprint(c)) {
 219           charset[c] = 1;
 220           (*p)++;
 221         }
 222         else
 223           return SETCHARSET_FAIL;
 224       }
 225       else if(c == ']') {
 226         return SETCHARSET_OK;
 227       }
 228       else
 229         return SETCHARSET_FAIL;
 230       break;
 231     case CURLFNM_SCHS_MAYRANGE2:
 232       if(c == '\\') {
 233         c = *(++(*p));
 234         if(!ISPRINT(c))
 235           return SETCHARSET_FAIL;
 236       }
 237       if(c == ']') {
 238         return SETCHARSET_OK;
 239       }
 240       else if(c == '\\') {
 241         c = *(++(*p));
 242         if(ISPRINT(c)) {
 243           charset[c] = 1;
 244           state = CURLFNM_SCHS_DEFAULT;
 245           (*p)++;
 246         }
 247         else
 248           return SETCHARSET_FAIL;
 249       }
 250       if(c >= rangestart) {
 251         if((ISLOWER(c) && ISLOWER(rangestart)) ||
 252            (ISDIGIT(c) && ISDIGIT(rangestart)) ||
 253            (ISUPPER(c) && ISUPPER(rangestart))) {
 254           charset[lastchar] = 0;
 255           rangestart++;
 256           while(rangestart++ <= c)
 257             charset[rangestart-1] = 1;
 258           (*p)++;
 259           state = CURLFNM_SCHS_DEFAULT;
 260         }
 261         else
 262           return SETCHARSET_FAIL;
 263       }
 264       break;
 265     case CURLFNM_SCHS_RIGHTBR:
 266       if(c == '[') {
 267         state = CURLFNM_SCHS_RIGHTBRLEFTBR;
 268         charset[c] = 1;
 269         (*p)++;
 270       }
 271       else if(c == ']') {
 272         return SETCHARSET_OK;
 273       }
 274       else if(c == '\0') {
 275         return SETCHARSET_FAIL;
 276       }
 277       else if(ISPRINT(c)) {
 278         charset[c] = 1;
 279         (*p)++;
 280         state = CURLFNM_SCHS_DEFAULT;
 281       }
 282       else
 283         return SETCHARSET_FAIL;
 284       break;
 285     case CURLFNM_SCHS_RIGHTBRLEFTBR:
 286       if(c == ']') {
 287         return SETCHARSET_OK;
 288       }
 289       else {
 290         state  = CURLFNM_SCHS_DEFAULT;
 291         charset[c] = 1;
 292         (*p)++;
 293       }
 294       break;
 295     }
 296   }
 297   return SETCHARSET_FAIL;
 298 }
 299
 300 static int loop(const unsigned char *pattern, const unsigned char *string)
 301 {
 302   loop_state state = CURLFNM_LOOP_DEFAULT;
 303   register unsigned char *p = (unsigned char *)pattern;
 304   register unsigned char *s = (unsigned char *)string;
 305   unsigned char charset[CURLFNM_CHSET_SIZE] = { 0 };
 306   int rc = 0;
 307
 308   for (;;) {
 309     switch(state) {
 310     case CURLFNM_LOOP_DEFAULT:
 311       if(*p == '*') {
 312         while(*(p+1) == '*') /* eliminate multiple stars */
 313           p++;
 314         if(*s == '\0' && *(p+1) == '\0')
 315           return CURL_FNMATCH_MATCH;
 316         rc = loop(p + 1, s); /* *.txt matches .txt <=> .txt matches .txt */
 317         if(rc == CURL_FNMATCH_MATCH)
 318           return CURL_FNMATCH_MATCH;
 319         if(*s) /* let the star eat up one character */
 320           s++;
 321         else
 322           return CURL_FNMATCH_NOMATCH;
 323       }
 324       else if(*p == '?') {
 325         if(ISPRINT(*s)) {
 326           s++;
 327           p++;
 328         }
 329         else if(*s == '\0')
 330           return CURL_FNMATCH_NOMATCH;
 331         else
 332           return CURL_FNMATCH_FAIL; /* cannot deal with other character */
 333       }
 334       else if(*p == '\0') {
 335         if(*s == '\0')
 336           return CURL_FNMATCH_MATCH;
 337         else
 338           return CURL_FNMATCH_NOMATCH;
 339       }
 340       else if(*p == '\\') {
 341         state = CURLFNM_LOOP_BACKSLASH;
 342         p++;
 343       }
 344       else if(*p == '[') {
 345         unsigned char *pp = p+1; /* cannot handle with pointer to register */
 346         if(setcharset(&pp, charset)) {
 347           int found = FALSE;
 348           if(charset[(unsigned int)*s])
 349             found = TRUE;
 350           else if(charset[CURLFNM_ALNUM])
 351             found = ISALNUM(*s);
 352           else if(charset[CURLFNM_ALPHA])
 353             found = ISALPHA(*s);
 354           else if(charset[CURLFNM_DIGIT])
 355             found = ISDIGIT(*s);
 356           else if(charset[CURLFNM_XDIGIT])
 357             found = ISXDIGIT(*s);
 358           else if(charset[CURLFNM_PRINT])
 359             found = ISPRINT(*s);
 360           else if(charset[CURLFNM_SPACE])
 361             found = ISSPACE(*s);
 362           else if(charset[CURLFNM_UPPER])
 363             found = ISUPPER(*s);
 364           else if(charset[CURLFNM_LOWER])
 365             found = ISLOWER(*s);
 366           else if(charset[CURLFNM_BLANK])
 367             found = ISBLANK(*s);
 368           else if(charset[CURLFNM_GRAPH])
 369             found = ISGRAPH(*s);
 370
 371           if(charset[CURLFNM_NEGATE])
 372             found = !found;
 373
 374           if(found) {
 375             p = pp+1;
 376             s++;
 377             memset(charset, 0, CURLFNM_CHSET_SIZE);
 378           }
 379           else
 380             return CURL_FNMATCH_NOMATCH;
 381         }
 382         else
 383           return CURL_FNMATCH_FAIL;
 384       }
 385       else {
 386         if(*p++ != *s++)
 387           return CURL_FNMATCH_NOMATCH;
 388       }
 389       break;
 390     case CURLFNM_LOOP_BACKSLASH:
 391       if(ISPRINT(*p)) {
 392         if(*p++ == *s++)
 393           state = CURLFNM_LOOP_DEFAULT;
 394         else
 395           return CURL_FNMATCH_NOMATCH;
 396       }
 397       else
 398         return CURL_FNMATCH_FAIL;
 399       break;
 400     }
 401   }
 402 }
 403
 404 int Curl_fnmatch(void *ptr, const char *pattern, const char *string)
 405 {
 406   (void)ptr; /* the argument is specified by the curl_fnmatch_callback
 407                 prototype, but not used by Curl_fnmatch() */
 408   if(!pattern || !string) {
 409     return CURL_FNMATCH_FAIL;
 410   }
 411   return loop((unsigned char *)pattern, (unsigned char *)string);
 412 }