lib/wildmatch.c

   1 /*
   2 **  Do shell-style pattern matching for ?, \, [], and * characters.
   3 **  It is 8bit clean.
   4 **
   5 **  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
   6 **  Rich $alz is now <rsalz@bbn.com>.
   7 **
   8 **  Modified by Wayne Davison to special-case '/' matching, to make '**'
   9 **  work differently than '*', and to fix the character-class code.
  10 */
  11
  12 #include "rsync.h"
  13
  14 /* What character marks an inverted character class? */
  15 #define NEGATE_CLASS    '!'
  16 #define NEGATE_CLASS2   '^'
  17
  18 #define FALSE 0
  19 #define TRUE 1
  20 #define ABORT_ALL -1
  21 #define ABORT_TO_STARSTAR -2
  22
  23 #define CC_EQ(class, len, litmatch) ((len) == sizeof (litmatch)-1 \
  24                                     && *(class) == *(litmatch) \
  25                                     && strncmp((char*)class, litmatch, len) == 0)
  26
  27 #if defined STDC_HEADERS || !defined isascii
  28 # define ISASCII(c) 1
  29 #else
  30 # define ISASCII(c) isascii(c)
  31 #endif
  32
  33 #ifdef isblank
  34 # define ISBLANK(c) (ISASCII(c) && isblank(c))
  35 #else
  36 # define ISBLANK(c) ((c) == ' ' || (c) == '\t')
  37 #endif
  38
  39 #ifdef isgraph
  40 # define ISGRAPH(c) (ISASCII(c) && isgraph(c))
  41 #else
  42 # define ISGRAPH(c) (ISASCII(c) && isprint(c) && !isspace(c))
  43 #endif
  44
  45 #define ISPRINT(c) (ISASCII(c) && isprint(c))
  46 #define ISDIGIT(c) (ISASCII(c) && isdigit(c))
  47 #define ISALNUM(c) (ISASCII(c) && isalnum(c))
  48 #define ISALPHA(c) (ISASCII(c) && isalpha(c))
  49 #define ISCNTRL(c) (ISASCII(c) && iscntrl(c))
  50 #define ISLOWER(c) (ISASCII(c) && islower(c))
  51 #define ISPUNCT(c) (ISASCII(c) && ispunct(c))
  52 #define ISSPACE(c) (ISASCII(c) && isspace(c))
  53 #define ISUPPER(c) (ISASCII(c) && isupper(c))
  54 #define ISXDIGIT(c) (ISASCII(c) && isxdigit(c))
  55
  56 #ifdef WILD_TEST_ITERATIONS
  57 int wildmatch_iteration_count;
  58 #endif
  59
  60 static int force_lower_case = 0;
  61
  62 /* Match pattern "p" against the a virtually-joined string consisting
  63  * of "text" and any strings in array "a". */
  64 static int dowild(const uchar *p, const uchar *text, const uchar*const *a)
  65 {
  66     uchar p_ch;
  67
  68 #ifdef WILD_TEST_ITERATIONS
  69     wildmatch_iteration_count++;
  70 #endif
  71
  72     for ( ; (p_ch = *p) != '\0'; text++, p++) {
  73         int matched, special;
  74         uchar t_ch, prev_ch;
  75         while ((t_ch = *text) == '\0') {
  76             if (*a == NULL) {
  77                 if (p_ch != '*')
  78                     return ABORT_ALL;
  79                 break;
  80             }
  81             text = *a++;
  82         }
  83         if (force_lower_case && ISUPPER(t_ch))
  84             t_ch = tolower(t_ch);
  85         switch (p_ch) {
  86           case '\\':
  87             /* Literal match with following character.  Note that the test
  88              * in "default" handles the p[1] == '\0' failure case. */
  89             p_ch = *++p;
  90             /* FALLTHROUGH */
  91           default:
  92             if (t_ch != p_ch)
  93                 return FALSE;
  94             continue;
  95           case '?':
  96             /* Match anything but '/'. */
  97             if (t_ch == '/')
  98                 return FALSE;
  99             continue;
 100           case '*':
 101             if (*++p == '*') {
 102                 while (*++p == '*') {}
 103                 special = TRUE;
 104             } else
 105                 special = FALSE;
 106             if (*p == '\0') {
 107                 /* Trailing "**" matches everything.  Trailing "*" matches
 108                  * only if there are no more slash characters. */
 109                 if (!special) {
 110                     do {
 111                         if (strchr((char*)text, '/') != NULL)
 112                             return FALSE;
 113                     } while ((text = *a++) != NULL);
 114                 }
 115                 return TRUE;
 116             }
 117             while (1) {
 118                 if (t_ch == '\0') {
 119                     if ((text = *a++) == NULL)
 120                         break;
 121                     t_ch = *text;
 122                     continue;
 123                 }
 124                 if ((matched = dowild(p, text, a)) != FALSE) {
 125                     if (!special || matched != ABORT_TO_STARSTAR)
 126                         return matched;
 127                 } else if (!special && t_ch == '/')
 128                     return ABORT_TO_STARSTAR;
 129                 t_ch = *++text;
 130             }
 131             return ABORT_ALL;
 132           case '[':
 133             p_ch = *++p;
 134 #ifdef NEGATE_CLASS2
 135             if (p_ch == NEGATE_CLASS2)
 136                 p_ch = NEGATE_CLASS;
 137 #endif
 138             /* Assign literal TRUE/FALSE because of "matched" comparison. */
 139             special = p_ch == NEGATE_CLASS? TRUE : FALSE;
 140             if (special) {
 141                 /* Inverted character class. */
 142                 p_ch = *++p;
 143             }
 144             prev_ch = 0;
 145             matched = FALSE;
 146             do {
 147                 if (!p_ch)
 148                     return ABORT_ALL;
 149                 if (p_ch == '\\') {
 150                     p_ch = *++p;
 151                     if (!p_ch)
 152                         return ABORT_ALL;
 153                     if (t_ch == p_ch)
 154                         matched = TRUE;
 155                 } else if (p_ch == '-' && prev_ch && p[1] && p[1] != ']') {
 156                     p_ch = *++p;
 157                     if (p_ch == '\\') {
 158                         p_ch = *++p;
 159                         if (!p_ch)
 160                             return ABORT_ALL;
 161                     }
 162                     if (t_ch <= p_ch && t_ch >= prev_ch)
 163                         matched = TRUE;
 164                     p_ch = 0; /* This makes "prev_ch" get set to 0. */
 165                 } else if (p_ch == '[' && p[1] == ':') {
 166                     const uchar *s;
 167                     int i;
 168                     for (s = p += 2; (p_ch = *p) && p_ch != ']'; p++) {} /*SHARED ITERATOR*/
 169                     if (!p_ch)
 170                         return ABORT_ALL;
 171                     i = p - s - 1;
 172                     if (i < 0 || p[-1] != ':') {
 173                         /* Didn't find ":]", so treat like a normal set. */
 174                         p = s - 2;
 175                         p_ch = '[';
 176                         if (t_ch == p_ch)
 177                             matched = TRUE;
 178                         continue;
 179                     }
 180                     if (CC_EQ(s,i, "alnum")) {
 181                         if (ISALNUM(t_ch))
 182                             matched = TRUE;
 183                     } else if (CC_EQ(s,i, "alpha")) {
 184                         if (ISALPHA(t_ch))
 185                             matched = TRUE;
 186                     } else if (CC_EQ(s,i, "blank")) {
 187                         if (ISBLANK(t_ch))
 188                             matched = TRUE;
 189                     } else if (CC_EQ(s,i, "cntrl")) {
 190                         if (ISCNTRL(t_ch))
 191                             matched = TRUE;
 192                     } else if (CC_EQ(s,i, "digit")) {
 193                         if (ISDIGIT(t_ch))
 194                             matched = TRUE;
 195                     } else if (CC_EQ(s,i, "graph")) {
 196                         if (ISGRAPH(t_ch))
 197                             matched = TRUE;
 198                     } else if (CC_EQ(s,i, "lower")) {
 199                         if (ISLOWER(t_ch))
 200                             matched = TRUE;
 201                     } else if (CC_EQ(s,i, "print")) {
 202                         if (ISPRINT(t_ch))
 203                             matched = TRUE;
 204                     } else if (CC_EQ(s,i, "punct")) {
 205                         if (ISPUNCT(t_ch))
 206                             matched = TRUE;
 207                     } else if (CC_EQ(s,i, "space")) {
 208                         if (ISSPACE(t_ch))
 209                             matched = TRUE;
 210                     } else if (CC_EQ(s,i, "upper")) {
 211                         if (ISUPPER(t_ch))
 212                             matched = TRUE;
 213                     } else if (CC_EQ(s,i, "xdigit")) {
 214                         if (ISXDIGIT(t_ch))
 215                             matched = TRUE;
 216                     } else /* malformed [:class:] string */
 217                         return ABORT_ALL;
 218                     p_ch = 0; /* This makes "prev_ch" get set to 0. */
 219                 } else if (t_ch == p_ch)
 220                     matched = TRUE;
 221             } while (prev_ch = p_ch, (p_ch = *++p) != ']');
 222             if (matched == special || t_ch == '/')
 223                 return FALSE;
 224             continue;
 225         }
 226     }
 227
 228     do {
 229         if (*text)
 230             return FALSE;
 231     } while ((text = *a++) != NULL);
 232
 233     return TRUE;
 234 }
 235
 236 /* Match literal string "s" against the a virtually-joined string consisting
 237  * of "text" and any strings in array "a". */
 238 static int doliteral(const uchar *s, const uchar *text, const uchar*const *a)
 239 {
 240     for ( ; *s != '\0'; text++, s++) {
 241         while (*text == '\0') {
 242             if ((text = *a++) == NULL)
 243                 return FALSE;
 244         }
 245         if (*text != *s)
 246             return FALSE;
 247     }
 248
 249     do {
 250         if (*text)
 251             return FALSE;
 252     } while ((text = *a++) != NULL);
 253
 254     return TRUE;
 255 }
 256
 257 /* Return the last "count" path elements from the concatenated string.
 258  * We return a string pointer to the start of the string, and update the
 259  * array pointer-pointer to point to any remaining string elements. */
 260 static const uchar *trailing_N_elements(const uchar*const **a_ptr, int count)
 261 {
 262     const uchar*const *a = *a_ptr;
 263     const uchar*const *first_a = a;
 264
 265     while (*a)
 266             a++;
 267
 268     while (a != first_a) {
 269         const uchar *s = *--a;
 270         s += strlen((char*)s);
 271         while (--s >= *a) {
 272             if (*s == '/' && !--count) {
 273                 *a_ptr = a+1;
 274                 return s+1;
 275             }
 276         }
 277     }
 278
 279     if (count == 1) {
 280         *a_ptr = a+1;
 281         return *a;
 282     }
 283
 284     return NULL;
 285 }
 286
 287 /* Match the "pattern" against the "text" string. */
 288 int wildmatch(const char *pattern, const char *text)
 289 {
 290     static const uchar *nomore[1]; /* A NULL pointer. */
 291 #ifdef WILD_TEST_ITERATIONS
 292     wildmatch_iteration_count = 0;
 293 #endif
 294     return dowild((const uchar*)pattern, (const uchar*)text, nomore) == TRUE;
 295 }
 296
 297 /* Match the "pattern" against the forced-to-lower-case "text" string. */
 298 int iwildmatch(const char *pattern, const char *text)
 299 {
 300     static const uchar *nomore[1]; /* A NULL pointer. */
 301     int ret;
 302 #ifdef WILD_TEST_ITERATIONS
 303     wildmatch_iteration_count = 0;
 304 #endif
 305     force_lower_case = 1;
 306     ret = dowild((const uchar*)pattern, (const uchar*)text, nomore) == TRUE;
 307     force_lower_case = 0;
 308     return ret;
 309 }
 310
 311 /* Match pattern "p" against the a virtually-joined string consisting
 312  * of all the pointers in array "texts" (which has a NULL pointer at the
 313  * end).  The int "where" can be 0 (normal matching), > 0 (match only
 314  * the trailing N slash-separated filename components of "texts"), or < 0
 315  * (match the "pattern" at the start or after any slash in "texts"). */
 316 int wildmatch_array(const char *pattern, const char*const *texts, int where)
 317 {
 318     const uchar *p = (const uchar*)pattern;
 319     const uchar*const *a = (const uchar*const*)texts;
 320     const uchar *text;
 321     int matched;
 322
 323 #ifdef WILD_TEST_ITERATIONS
 324     wildmatch_iteration_count = 0;
 325 #endif
 326
 327     if (where > 0)
 328         text = trailing_N_elements(&a, where);
 329     else
 330         text = *a++;
 331     if (!text)
 332         return FALSE;
 333
 334     if ((matched = dowild(p, text, a)) != TRUE && where < 0
 335      && matched != ABORT_ALL) {
 336         while (1) {
 337             if (*text == '\0') {
 338                 if ((text = (uchar*)*a++) == NULL)
 339                     return FALSE;
 340                 continue;
 341             }
 342             if (*text++ == '/' && (matched = dowild(p, text, a)) != FALSE
 343              && matched != ABORT_TO_STARSTAR)
 344                 break;
 345         }
 346     }
 347     return matched == TRUE;
 348 }
 349
 350 /* Match literal string "s" against the a virtually-joined string consisting
 351  * of all the pointers in array "texts" (which has a NULL pointer at the
 352  * end).  The int "where" can be 0 (normal matching), or > 0 (match
 353  * only the trailing N slash-separated filename components of "texts"). */
 354 int litmatch_array(const char *string, const char*const *texts, int where)
 355 {
 356     const uchar *s = (const uchar*)string;
 357     const uchar*const *a = (const uchar* const*)texts;
 358     const uchar *text;
 359
 360     if (where > 0)
 361         text = trailing_N_elements(&a, where);
 362     else
 363         text = *a++;
 364     if (!text)
 365         return FALSE;
 366
 367     return doliteral(s, text, a) == TRUE;
 368 }