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 domatch(const uchar *p, const uchar *text)
  61 {
  62     int matched, special;
  63     uchar ch, prev;
  64
  65 #ifdef WILD_TEST_ITERATIONS
  66     wildmatch_iteration_count++;
  67 #endif
  68
  69     for ( ; (ch = *p) != '\0'; text++, p++) {
  70         if (*text == '\0' && ch != '*')
  71             return FALSE;
  72         switch (ch) {
  73           case '\\':
  74             /* Literal match with following character.  Note that the test
  75              * in "default" handles the p[1] == '\0' failure case. */
  76             ch = *++p;
  77             /* FALLTHROUGH */
  78           default:
  79             if (*text != ch)
  80                 return FALSE;
  81             continue;
  82           case '?':
  83             /* Match anything but '/'. */
  84             if (*text == '/')
  85                 return FALSE;
  86             continue;
  87           case '*':
  88             if (*++p == '*') {
  89                 while (*++p == '*') {}
  90                 special = TRUE;
  91             }
  92             else
  93                 special = FALSE;
  94             if (*p == '\0') {
  95                 /* Trailing "**" matches everything.  Trailing "*" matches
  96                  * only if there are no more slash characters. */
  97                 return special? TRUE : strchr((char*)text, '/') == NULL;
  98             }
  99             for ( ; *text; text++) {
 100                 if ((matched = domatch(p, text)) != FALSE) {
 101                     if (!special || matched != ABORT_TO_STARSTAR)
 102                         return matched;
 103                 }
 104                 else if (!special && *text == '/')
 105                     return ABORT_TO_STARSTAR;
 106             }
 107             return ABORT_ALL;
 108           case '[':
 109             ch = *++p;
 110 #ifdef NEGATE_CLASS2
 111             if (ch == NEGATE_CLASS2)
 112                 ch = NEGATE_CLASS;
 113 #endif
 114             /* Assign literal TRUE/FALSE because of "matched" comparison. */
 115             special = ch == NEGATE_CLASS? TRUE : FALSE;
 116             if (special) {
 117                 /* Inverted character class. */
 118                 ch = *++p;
 119             }
 120             prev = 0;
 121             matched = FALSE;
 122             do {
 123                 if (!ch)
 124                     return ABORT_ALL;
 125                 if (ch == '\\') {
 126                     ch = *++p;
 127                     if (!ch)
 128                         return ABORT_ALL;
 129                     if (*text == ch)
 130                         matched = TRUE;
 131                 }
 132                 else if (ch == '-' && prev && p[1] && p[1] != ']') {
 133                     ch = *++p;
 134                     if (ch == '\\') {
 135                         ch = *++p;
 136                         if (!ch)
 137                             return ABORT_ALL;
 138                     }
 139                     if (*text <= ch && *text >= prev)
 140                         matched = TRUE;
 141                     ch = 0; /* This makes "prev" get set to 0. */
 142                 }
 143                 else if (ch == '[' && p[1] == ':') {
 144                     const uchar *s;
 145                     int i;
 146                     for (s = p += 2; (ch = *p) && ch != ']'; p++) {}
 147                     if (!ch)
 148                         return ABORT_ALL;
 149                     i = p - s - 1;
 150                     if (i < 0 || p[-1] != ':') {
 151                         /* Didn't find ":]", so treat like a normal set. */
 152                         p = s - 2;
 153                         ch = '[';
 154                         if (*text == ch)
 155                             matched = TRUE;
 156                         continue;
 157                     }
 158                     if (CC_EQ(s,i, "alnum")) {
 159                         if (ISALNUM(*text))
 160                             matched = TRUE;
 161                     }
 162                     else if (CC_EQ(s,i, "alpha")) {
 163                         if (ISALPHA(*text))
 164                             matched = TRUE;
 165                     }
 166                     else if (CC_EQ(s,i, "blank")) {
 167                         if (ISBLANK(*text))
 168                             matched = TRUE;
 169                     }
 170                     else if (CC_EQ(s,i, "cntrl")) {
 171                         if (ISCNTRL(*text))
 172                             matched = TRUE;
 173                     }
 174                     else if (CC_EQ(s,i, "digit")) {
 175                         if (ISDIGIT(*text))
 176                             matched = TRUE;
 177                     }
 178                     else if (CC_EQ(s,i, "graph")) {
 179                         if (ISGRAPH(*text))
 180                             matched = TRUE;
 181                     }
 182                     else if (CC_EQ(s,i, "lower")) {
 183                         if (ISLOWER(*text))
 184                             matched = TRUE;
 185                     }
 186                     else if (CC_EQ(s,i, "print")) {
 187                         if (ISPRINT(*text))
 188                             matched = TRUE;
 189                     }
 190                     else if (CC_EQ(s,i, "punct")) {
 191                         if (ISPUNCT(*text))
 192                             matched = TRUE;
 193                     }
 194                     else if (CC_EQ(s,i, "space")) {
 195                         if (ISSPACE(*text))
 196                             matched = TRUE;
 197                     }
 198                     else if (CC_EQ(s,i, "upper")) {
 199                         if (ISUPPER(*text))
 200                             matched = TRUE;
 201                     }
 202                     else if (CC_EQ(s,i, "xdigit")) {
 203                         if (ISXDIGIT(*text))
 204                             matched = TRUE;
 205                     }
 206                     else /* malformed [:class:] string */
 207                         return ABORT_ALL;
 208                     ch = 0; /* This makes "prev" get set to 0. */
 209                 }
 210                 else if (*text == ch)
 211                     matched = TRUE;
 212             } while (prev = ch, (ch = *++p) != ']');
 213             if (matched == special || *text == '/')
 214                 return FALSE;
 215             continue;
 216         }
 217     }
 218
 219     return *text == '\0';
 220 }
 221
 222 /* Find the pattern (p) in the text string (t). */
 223 int wildmatch(const char *p, const char *t)
 224 {
 225 #ifdef WILD_TEST_ITERATIONS
 226     wildmatch_iteration_count = 0;
 227 #endif
 228     return domatch((const uchar*)p, (const uchar*)t) == TRUE;
 229 }