lib/curl_fnmatch.c

   1 /***************************************************************************
   2  *                                  _   _ ____  _
   3  *  Project                     ___| | | |  _ \| |
   4  *                             / __| | | | |_) | |
   5  *                            | (__| |_| |  _ <| |___
   6  *                             \___|\___/|_| \_\_____|
   7  *
   8  * Copyright (C) 1998 - 2018, 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_SCHS_DEFAULT = 0,
  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 typedef enum {
  61   CCLASS_OTHER = 0,
  62   CCLASS_DIGIT,
  63   CCLASS_UPPER,
  64   CCLASS_LOWER
  65 } char_class;
  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(ISLOWER(c))
  85         keyword[i] = c;
  86       else if(c == ':')
  87         state = CURLFNM_PKW_DDOT;
  88       else
  89         return SETCHARSET_FAIL;
  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 /* Return the character class. */
 127 static char_class charclass(unsigned char c)
 128 {
 129   if(ISUPPER(c))
 130     return CCLASS_UPPER;
 131   if(ISLOWER(c))
 132     return CCLASS_LOWER;
 133   if(ISDIGIT(c))
 134     return CCLASS_DIGIT;
 135   return CCLASS_OTHER;
 136 }
 137
 138 /* Include a character or a range in set. */
 139 static void setcharorrange(unsigned char **pp, unsigned char *charset)
 140 {
 141   unsigned char *p = (*pp)++;
 142   unsigned char c = *p++;
 143
 144   charset[c] = 1;
 145   if(ISALNUM(c) && *p++ == '-') {
 146     char_class cc = charclass(c);
 147     unsigned char endrange = *p++;
 148
 149     if(endrange == '\\')
 150       endrange = *p++;
 151     if(endrange >= c && charclass(endrange) == cc) {
 152       while(c++ != endrange)
 153         if(charclass(c) == cc)  /* Chars in class may be not consecutive. */
 154           charset[c] = 1;
 155       *pp = p;
 156     }
 157   }
 158 }
 159
 160 /* returns 1 (true) if pattern is OK, 0 if is bad ("p" is pattern pointer) */
 161 static int setcharset(unsigned char **p, unsigned char *charset)
 162 {
 163   setcharset_state state = CURLFNM_SCHS_DEFAULT;
 164   bool something_found = FALSE;
 165   unsigned char c;
 166
 167   memset(charset, 0, CURLFNM_CHSET_SIZE);
 168   for(;;) {
 169     c = **p;
 170     if(!c)
 171       return SETCHARSET_FAIL;
 172
 173     switch(state) {
 174     case CURLFNM_SCHS_DEFAULT:
 175       if(c == ']') {
 176         if(something_found)
 177           return SETCHARSET_OK;
 178         something_found = TRUE;
 179         state = CURLFNM_SCHS_RIGHTBR;
 180         charset[c] = 1;
 181         (*p)++;
 182       }
 183       else if(c == '[') {
 184         unsigned char *pp = *p + 1;
 185
 186         if(*pp++ == ':' && parsekeyword(&pp, charset))
 187           *p = pp;
 188         else {
 189           charset[c] = 1;
 190           (*p)++;
 191         }
 192         something_found = TRUE;
 193       }
 194       else if(c == '^' || c == '!') {
 195         if(!something_found) {
 196           if(charset[CURLFNM_NEGATE]) {
 197             charset[c] = 1;
 198             something_found = TRUE;
 199           }
 200           else
 201             charset[CURLFNM_NEGATE] = 1; /* negate charset */
 202         }
 203         else
 204           charset[c] = 1;
 205         (*p)++;
 206       }
 207       else if(c == '\\') {
 208         c = *(++(*p));
 209         if(c)
 210           setcharorrange(p, charset);
 211         else
 212           charset['\\'] = 1;
 213         something_found = TRUE;
 214       }
 215       else {
 216         setcharorrange(p, charset);
 217         something_found = TRUE;
 218       }
 219       break;
 220     case CURLFNM_SCHS_RIGHTBR:
 221       if(c == '[') {
 222         state = CURLFNM_SCHS_RIGHTBRLEFTBR;
 223         charset[c] = 1;
 224         (*p)++;
 225       }
 226       else if(c == ']') {
 227         return SETCHARSET_OK;
 228       }
 229       else if(ISPRINT(c)) {
 230         charset[c] = 1;
 231         (*p)++;
 232         state = CURLFNM_SCHS_DEFAULT;
 233       }
 234       else
 235         /* used 'goto fail' instead of 'return SETCHARSET_FAIL' to avoid a
 236          * nonsense warning 'statement not reached' at end of the fnc when
 237          * compiling on Solaris */
 238         goto fail;
 239       break;
 240     case CURLFNM_SCHS_RIGHTBRLEFTBR:
 241       if(c == ']')
 242         return SETCHARSET_OK;
 243       state  = CURLFNM_SCHS_DEFAULT;
 244       charset[c] = 1;
 245       (*p)++;
 246       break;
 247     }
 248   }
 249 fail:
 250   return SETCHARSET_FAIL;
 251 }
 252
 253 static int loop(const unsigned char *pattern, const unsigned char *string,
 254                 int maxstars)
 255 {
 256   unsigned char *p = (unsigned char *)pattern;
 257   unsigned char *s = (unsigned char *)string;
 258   unsigned char charset[CURLFNM_CHSET_SIZE] = { 0 };
 259
 260   for(;;) {
 261     unsigned char *pp;
 262
 263     switch(*p) {
 264     case '*':
 265       if(!maxstars)
 266         return CURL_FNMATCH_NOMATCH;
 267       /* Regroup consecutive stars and question marks. This can be done because
 268          '*?*?*' can be expressed as '??*'. */
 269       for(;;) {
 270         if(*++p == '\0')
 271           return CURL_FNMATCH_MATCH;
 272         if(*p == '?') {
 273           if(!*s++)
 274             return CURL_FNMATCH_NOMATCH;
 275         }
 276         else if(*p != '*')
 277           break;
 278       }
 279       /* Skip string characters until we find a match with pattern suffix. */
 280       for(maxstars--; *s; s++) {
 281         if(loop(p, s, maxstars) == CURL_FNMATCH_MATCH)
 282           return CURL_FNMATCH_MATCH;
 283       }
 284       return CURL_FNMATCH_NOMATCH;
 285     case '?':
 286       if(!*s)
 287         return CURL_FNMATCH_NOMATCH;
 288       s++;
 289       p++;
 290       break;
 291     case '\0':
 292       return *s? CURL_FNMATCH_NOMATCH: CURL_FNMATCH_MATCH;
 293     case '\\':
 294       if(p[1])
 295         p++;
 296       if(*s++ != *p++)
 297         return CURL_FNMATCH_NOMATCH;
 298       break;
 299     case '[':
 300       pp = p + 1; /* Copy in case of syntax error in set. */
 301       if(setcharset(&pp, charset)) {
 302         int found = FALSE;
 303         if(!*s)
 304           return CURL_FNMATCH_NOMATCH;
 305         if(charset[(unsigned int)*s])
 306           found = TRUE;
 307         else if(charset[CURLFNM_ALNUM])
 308           found = ISALNUM(*s);
 309         else if(charset[CURLFNM_ALPHA])
 310           found = ISALPHA(*s);
 311         else if(charset[CURLFNM_DIGIT])
 312           found = ISDIGIT(*s);
 313         else if(charset[CURLFNM_XDIGIT])
 314           found = ISXDIGIT(*s);
 315         else if(charset[CURLFNM_PRINT])
 316           found = ISPRINT(*s);
 317         else if(charset[CURLFNM_SPACE])
 318           found = ISSPACE(*s);
 319         else if(charset[CURLFNM_UPPER])
 320           found = ISUPPER(*s);
 321         else if(charset[CURLFNM_LOWER])
 322           found = ISLOWER(*s);
 323         else if(charset[CURLFNM_BLANK])
 324           found = ISBLANK(*s);
 325         else if(charset[CURLFNM_GRAPH])
 326           found = ISGRAPH(*s);
 327
 328         if(charset[CURLFNM_NEGATE])
 329           found = !found;
 330
 331         if(!found)
 332           return CURL_FNMATCH_NOMATCH;
 333         p = pp + 1;
 334         s++;
 335         break;
 336       }
 337
 338       /* Syntax error in set: this must be taken as a regular character. */
 339       /* FALLTHROUGH */
 340     default:
 341       if(*p++ != *s++)
 342         return CURL_FNMATCH_NOMATCH;
 343       break;
 344     }
 345   }
 346 }
 347
 348 /*
 349  * @unittest: 1307
 350  */
 351 int Curl_fnmatch(void *ptr, const char *pattern, const char *string)
 352 {
 353   (void)ptr; /* the argument is specified by the curl_fnmatch_callback
 354                 prototype, but not used by Curl_fnmatch() */
 355   if(!pattern || !string) {
 356     return CURL_FNMATCH_FAIL;
 357   }
 358   return loop((unsigned char *)pattern, (unsigned char *)string, 5);
 359 }