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