lib/curl_fnmatch.c

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