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