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++) {} 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} 369