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 && strncmp(class, litmatch, len) == 0)
  24
  25 #if defined STDC_HEADERS || !defined isascii
  26 # define ISASCII(c) 1
  27 #else
  28 # define ISASCII(c) isascii(c)
  29 #endif
  30
  31 #ifdef isblank
  32 # define ISBLANK(c) (ISASCII(c) && isblank(c))
  33 #else
  34 # define ISBLANK(c) ((c) == ' ' || (c) == '\t')
  35 #endif
  36
  37 #ifdef isgraph
  38 # define ISGRAPH(c) (ISASCII(c) && isgraph(c))
  39 #else
  40 # define ISGRAPH(c) (ISASCII(c) && isprint(c) && !isspace(c))
  41 #endif
  42
  43 #define ISPRINT(c) (ISASCII(c) && isprint(c))
  44 #define ISDIGIT(c) (ISASCII(c) && isdigit(c))
  45 #define ISALNUM(c) (ISASCII(c) && isalnum(c))
  46 #define ISALPHA(c) (ISASCII(c) && isalpha(c))
  47 #define ISCNTRL(c) (ISASCII(c) && iscntrl(c))
  48 #define ISLOWER(c) (ISASCII(c) && islower(c))
  49 #define ISPUNCT(c) (ISASCII(c) && ispunct(c))
  50 #define ISSPACE(c) (ISASCII(c) && isspace(c))
  51 #define ISUPPER(c) (ISASCII(c) && isupper(c))
  52 #define ISXDIGIT(c) (ISASCII(c) && isxdigit(c))
  53
  54 #ifdef WILD_TEST_ITERATIONS
  55 int wildmatch_iteration_count;
  56 #endif
  57
  58 static int domatch(const unsigned char *p, const unsigned char *text)
  59 {
  60     int matched, special;
  61     unsigned char ch, prev;
  62
  63 #ifdef WILD_TEST_ITERATIONS
  64     wildmatch_iteration_count++;
  65 #endif
  66
  67     for ( ; (ch = *p) != '\0'; text++, p++) {
  68         if (*text == '\0' && ch != '*')
  69             return FALSE;
  70         switch (ch) {
  71           case '\\':
  72             /* Literal match with following character.  Note that the test
  73              * in "default" handles the p[1] == '\0' failure case. */
  74             ch = *++p;
  75             /* FALLTHROUGH */
  76           default:
  77             if (*text != ch)
  78                 return FALSE;
  79             continue;
  80           case '?':
  81             /* Match anything but '/'. */
  82             if (*text == '/')
  83                 return FALSE;
  84             continue;
  85           case '*':
  86             if (*++p == '*') {
  87                 while (*++p == '*') {}
  88                 special = TRUE;
  89             }
  90             else
  91                 special = FALSE;
  92             if (*p == '\0') {
  93                 /* Trailing "**" matches everything.  Trailing "*" matches
  94                  * only if there are no more slash characters. */
  95                 return special? TRUE : strchr(text, '/') == NULL;
  96             }
  97             for ( ; *text; text++) {
  98                 if ((matched = domatch(p, text)) != FALSE) {
  99                     if (!special || matched != ABORT_TO_STARSTAR)
 100                         return matched;
 101                 }
 102                 else if (!special && *text == '/')
 103                     return ABORT_TO_STARSTAR;
 104             }
 105             return ABORT_ALL;
 106           case '[':
 107             ch = *++p;
 108 #ifdef NEGATE_CLASS2
 109             if (ch == NEGATE_CLASS2)
 110                 ch = NEGATE_CLASS;
 111 #endif
 112             /* Assign literal TRUE/FALSE because of "matched" comparison. */
 113             special = ch == NEGATE_CLASS? TRUE : FALSE;
 114             if (special) {
 115                 /* Inverted character class. */
 116                 ch = *++p;
 117             }
 118             prev = 0;
 119             matched = FALSE;
 120             do {
 121                 if (!ch)
 122                     return FALSE;
 123                 if (ch == '\\') {
 124                     ch = *++p;
 125                     if (!ch)
 126                         return FALSE;
 127                     if (*text == ch)
 128                         matched = TRUE;
 129                 }
 130                 else if (ch == '-' && prev && p[1] && p[1] != ']') {
 131                     ch = *++p;
 132                     if (ch == '\\') {
 133                         ch = *++p;
 134                         if (!ch)
 135                             return FALSE;
 136                     }
 137                     if (*text <= ch && *text >= prev)
 138                         matched = TRUE;
 139                     ch = 0; /* This makes "prev" get set to 0. */
 140                 }
 141                 else if (ch == '[' && p[1] == ':') {
 142                     unsigned const char *s = p += 2;
 143                     int i;
 144                     while ((ch = *p) && (ch != ':' || p[1] != ']')) p++;
 145                     if (!ch)
 146                         return FALSE;
 147                     i = p - s;
 148                     ch = *text;
 149                     if ((CC_EQ(s,i, "alnum") && ISALNUM(ch))
 150                      || (CC_EQ(s,i, "alpha") && ISALPHA(ch))
 151                      || (CC_EQ(s,i, "blank") && ISBLANK(ch))
 152                      || (CC_EQ(s,i, "cntrl") && ISCNTRL(ch))
 153                      || (CC_EQ(s,i, "digit") && ISDIGIT(ch))
 154                      || (CC_EQ(s,i, "graph") && ISGRAPH(ch))
 155                      || (CC_EQ(s,i, "lower") && ISLOWER(ch))
 156                      || (CC_EQ(s,i, "print") && ISPRINT(ch))
 157                      || (CC_EQ(s,i, "punct") && ISPUNCT(ch))
 158                      || (CC_EQ(s,i, "space") && ISSPACE(ch))
 159                      || (CC_EQ(s,i, "upper") && ISUPPER(ch))
 160                      || (CC_EQ(s,i,"xdigit") && ISXDIGIT(ch)))
 161                         matched = TRUE;
 162                     p++;
 163                     ch = 0; /* This makes "prev" get set to 0. */
 164                 }
 165                 else if (*text == ch)
 166                     matched = TRUE;
 167             } while (prev = ch, (ch = *++p) != ']');
 168             if (matched == special)
 169                 return FALSE;
 170             continue;
 171         }
 172     }
 173
 174     return *text == '\0';
 175 }
 176
 177 /* Find the pattern (p) in the text string (t). */
 178 int wildmatch(const char *p, const char *t)
 179 {
 180 #ifdef WILD_TEST_ITERATIONS
 181     wildmatch_iteration_count = 0;
 182 #endif
 183     return domatch((const unsigned char*)p, (const unsigned char*)t) == TRUE;
 184 }