f3a1731eb04685a39cf01a96f46af7395bb5c970
   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
  57int wildmatch_iteration_count;
  58#endif
  59
  60static 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". */
  64static 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". */
 238static 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. */
 260static 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. */
 288int 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. */
 298int 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"). */
 316int 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"). */
 354int 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}