portreg.c (12285B)
1 /* This Source Code Form is subject to the terms of the Mozilla Public 2 * License, v. 2.0. If a copy of the MPL was not distributed with this 3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 4 5 /* 6 * shexp.c: shell-like wildcard match routines 7 * 8 * See shexp.h for public documentation. 9 */ 10 11 #include "seccomon.h" 12 #include "portreg.h" 13 14 /* ----------------------------- shexp_valid ------------------------------ */ 15 16 static int 17 _valid_subexp(const char *exp, char stop1, char stop2) 18 { 19 register int x; 20 int nsc = 0; /* Number of special characters */ 21 int np; /* Number of pipe characters in union */ 22 int tld = 0; /* Number of tilde characters */ 23 24 for (x = 0; exp[x] && (exp[x] != stop1) && (exp[x] != stop2); ++x) { 25 switch (exp[x]) { 26 case '~': 27 if (tld) /* at most one exclusion */ 28 return INVALID_SXP; 29 if (stop1) /* no exclusions within unions */ 30 return INVALID_SXP; 31 if (!exp[x + 1]) /* exclusion cannot be last character */ 32 return INVALID_SXP; 33 if (!x) /* exclusion cannot be first character */ 34 return INVALID_SXP; 35 ++tld; 36 /* fall through */ 37 case '*': 38 case '?': 39 case '$': 40 ++nsc; 41 break; 42 case '[': 43 ++nsc; 44 if ((!exp[++x]) || (exp[x] == ']')) 45 return INVALID_SXP; 46 for (; exp[x] && (exp[x] != ']'); ++x) { 47 if (exp[x] == '\\' && !exp[++x]) 48 return INVALID_SXP; 49 } 50 if (!exp[x]) 51 return INVALID_SXP; 52 break; 53 case '(': 54 ++nsc; 55 if (stop1) /* no nested unions */ 56 return INVALID_SXP; 57 np = -1; 58 do { 59 int t = _valid_subexp(&exp[++x], ')', '|'); 60 if (t == 0 || t == INVALID_SXP) 61 return INVALID_SXP; 62 x += t; 63 if (!exp[x]) 64 return INVALID_SXP; 65 ++np; 66 } while (exp[x] == '|'); 67 if (np < 1) /* must be at least one pipe */ 68 return INVALID_SXP; 69 break; 70 case ')': 71 case '|': 72 case ']': 73 return INVALID_SXP; 74 case '\\': 75 ++nsc; 76 if (!exp[++x]) 77 return INVALID_SXP; 78 break; 79 default: 80 break; 81 } 82 } 83 if ((!stop1) && (!nsc)) /* must be at least one special character */ 84 return NON_SXP; 85 return ((exp[x] == stop1 || exp[x] == stop2) ? x : INVALID_SXP); 86 } 87 88 int 89 PORT_RegExpValid(const char *exp) 90 { 91 int x; 92 93 x = _valid_subexp(exp, '\0', '\0'); 94 return (x < 0 ? x : VALID_SXP); 95 } 96 97 /* ----------------------------- shexp_match ----------------------------- */ 98 99 #define MATCH 0 100 #define NOMATCH 1 101 #define ABORTED -1 102 103 static int 104 _shexp_match(const char *str, const char *exp, PRBool case_insensitive, 105 unsigned int level); 106 107 /* Count characters until we reach a NUL character or either of the 108 * two delimiter characters, stop1 or stop2. If we encounter a bracketed 109 * expression, look only for NUL or ']' inside it. Do not look for stop1 110 * or stop2 inside it. Return ABORTED if bracketed expression is unterminated. 111 * Handle all escaping. 112 * Return index in input string of first stop found, or ABORTED if not found. 113 * If "dest" is non-NULL, copy counted characters to it and NUL terminate. 114 */ 115 static int 116 _scan_and_copy(const char *exp, char stop1, char stop2, char *dest) 117 { 118 register int sx; /* source index */ 119 register char cc; 120 121 for (sx = 0; (cc = exp[sx]) && cc != stop1 && cc != stop2; sx++) { 122 if (cc == '\\') { 123 if (!exp[++sx]) 124 return ABORTED; /* should be impossible */ 125 } else if (cc == '[') { 126 while ((cc = exp[++sx]) && cc != ']') { 127 if (cc == '\\' && !exp[++sx]) 128 return ABORTED; 129 } 130 if (!cc) 131 return ABORTED; /* should be impossible */ 132 } 133 } 134 if (dest && sx) { 135 /* Copy all but the closing delimiter. */ 136 memcpy(dest, exp, sx); 137 dest[sx] = 0; 138 } 139 return cc ? sx : ABORTED; /* index of closing delimiter */ 140 } 141 142 /* On input, exp[0] is the opening parenthesis of a union. 143 * See if any of the alternatives in the union matches as a pattern. 144 * The strategy is to take each of the alternatives, in turn, and append 145 * the rest of the expression (after the closing ')' that marks the end of 146 * this union) to that alternative, and then see if the resultant expression 147 * matches the input string. Repeat this until some alternative matches, 148 * or we have an abort. 149 */ 150 static int 151 _handle_union(const char *str, const char *exp, PRBool case_insensitive, 152 unsigned int level) 153 { 154 register int sx; /* source index */ 155 int cp; /* source index of closing parenthesis */ 156 int count; 157 int ret = NOMATCH; 158 char *e2; 159 160 /* Find the closing parenthesis that ends this union in the expression */ 161 cp = _scan_and_copy(exp, ')', '\0', NULL); 162 if (cp == ABORTED || cp < 4) /* must be at least "(a|b" before ')' */ 163 return ABORTED; 164 ++cp; /* now index of char after closing parenthesis */ 165 e2 = (char *)PORT_Alloc(1 + strlen(exp)); 166 if (!e2) 167 return ABORTED; 168 for (sx = 1;; ++sx) { 169 /* Here, exp[sx] is one character past the preceding '(' or '|'. */ 170 /* Copy everything up to the next delimiter to e2 */ 171 count = _scan_and_copy(exp + sx, ')', '|', e2); 172 if (count == ABORTED || !count) { 173 ret = ABORTED; 174 break; 175 } 176 sx += count; 177 /* Append everything after closing parenthesis to e2. This is safe. */ 178 strcpy(e2 + count, exp + cp); 179 ret = _shexp_match(str, e2, case_insensitive, level + 1); 180 if (ret != NOMATCH || !exp[sx] || exp[sx] == ')') 181 break; 182 } 183 PORT_Free(e2); 184 if (sx < 2) 185 ret = ABORTED; 186 return ret; 187 } 188 189 /* returns 1 if val is in range from start..end, case insensitive. */ 190 static int 191 _is_char_in_range(int start, int end, int val) 192 { 193 char map[256]; 194 memset(map, 0, sizeof map); 195 while (start <= end) 196 map[tolower(start++)] = 1; 197 return map[tolower(val)]; 198 } 199 200 static int 201 _shexp_match(const char *str, const char *exp, PRBool case_insensitive, 202 unsigned int level) 203 { 204 register int x; /* input string index */ 205 register int y; /* expression index */ 206 int ret, neg; 207 208 if (level > 20) /* Don't let the stack get too deep. */ 209 return ABORTED; 210 for (x = 0, y = 0; exp[y]; ++y, ++x) { 211 if ((!str[x]) && (exp[y] != '$') && (exp[y] != '*')) { 212 return NOMATCH; 213 } 214 switch (exp[y]) { 215 case '$': 216 if (str[x]) 217 return NOMATCH; 218 --x; /* we don't want loop to increment x */ 219 break; 220 case '*': 221 while (exp[++y] == '*') { 222 } 223 if (!exp[y]) 224 return MATCH; 225 while (str[x]) { 226 ret = _shexp_match(&str[x++], &exp[y], case_insensitive, 227 level + 1); 228 switch (ret) { 229 case NOMATCH: 230 continue; 231 case ABORTED: 232 return ABORTED; 233 default: 234 return MATCH; 235 } 236 } 237 if ((exp[y] == '$') && (exp[y + 1] == '\0') && (!str[x])) 238 return MATCH; 239 else 240 return NOMATCH; 241 case '[': { 242 int start, end = 0, i; 243 neg = ((exp[++y] == '^') && (exp[y + 1] != ']')); 244 if (neg) 245 ++y; 246 i = y; 247 start = (unsigned char)(exp[i++]); 248 if (start == '\\') 249 start = (unsigned char)(exp[i++]); 250 if (isalnum(start) && exp[i++] == '-') { 251 end = (unsigned char)(exp[i++]); 252 if (end == '\\') 253 end = (unsigned char)(exp[i++]); 254 } 255 if (isalnum(end) && exp[i] == ']') { 256 /* This is a range form: a-b */ 257 int val = (unsigned char)(str[x]); 258 if (end < start) { /* swap them */ 259 start ^= end; 260 end ^= start; 261 start ^= end; 262 } 263 if (case_insensitive && isalpha(val)) { 264 val = _is_char_in_range(start, end, val); 265 if (neg == val) 266 return NOMATCH; 267 } else if (neg != ((val < start) || (val > end))) { 268 return NOMATCH; 269 } 270 y = i; 271 } else { 272 /* Not range form */ 273 int matched = 0; 274 for (; exp[y] != ']'; y++) { 275 if (exp[y] == '\\') 276 ++y; 277 if (case_insensitive) { 278 matched |= (toupper((unsigned char)str[x]) == 279 toupper((unsigned char)exp[y])); 280 } else { 281 matched |= (str[x] == exp[y]); 282 } 283 } 284 if (neg == matched) 285 return NOMATCH; 286 } 287 } break; 288 case '(': 289 if (!exp[y + 1]) 290 return ABORTED; 291 return _handle_union(&str[x], &exp[y], case_insensitive, level); 292 case '?': 293 break; 294 case '|': 295 case ']': 296 case ')': 297 return ABORTED; 298 case '\\': 299 ++y; 300 /* fall through */ 301 default: 302 if (case_insensitive) { 303 if (toupper((unsigned char)str[x]) != toupper((unsigned char)exp[y])) 304 return NOMATCH; 305 } else { 306 if (str[x] != exp[y]) 307 return NOMATCH; 308 } 309 break; 310 } 311 } 312 return (str[x] ? NOMATCH : MATCH); 313 } 314 315 static int 316 port_RegExpMatch(const char *str, const char *xp, PRBool case_insensitive) 317 { 318 char *exp = 0; 319 int x, ret = MATCH; 320 321 if (!strchr(xp, '~')) 322 return _shexp_match(str, xp, case_insensitive, 0); 323 324 exp = PORT_Strdup(xp); 325 if (!exp) 326 return NOMATCH; 327 328 x = _scan_and_copy(exp, '~', '\0', NULL); 329 if (x != ABORTED && exp[x] == '~') { 330 exp[x++] = '\0'; 331 ret = _shexp_match(str, &exp[x], case_insensitive, 0); 332 switch (ret) { 333 case NOMATCH: 334 ret = MATCH; 335 break; 336 case MATCH: 337 ret = NOMATCH; 338 break; 339 default: 340 break; 341 } 342 } 343 if (ret == MATCH) 344 ret = _shexp_match(str, exp, case_insensitive, 0); 345 346 PORT_Free(exp); 347 return ret; 348 } 349 350 /* ------------------------------ shexp_cmp ------------------------------- */ 351 352 int 353 PORT_RegExpSearch(const char *str, const char *exp) 354 { 355 switch (PORT_RegExpValid(exp)) { 356 case INVALID_SXP: 357 return -1; 358 case NON_SXP: 359 return (strcmp(exp, str) ? 1 : 0); 360 default: 361 return port_RegExpMatch(str, exp, PR_FALSE); 362 } 363 } 364 365 int 366 PORT_RegExpCaseSearch(const char *str, const char *exp) 367 { 368 switch (PORT_RegExpValid(exp)) { 369 case INVALID_SXP: 370 return -1; 371 case NON_SXP: 372 return (PORT_Strcasecmp(exp, str) ? 1 : 0); 373 default: 374 return port_RegExpMatch(str, exp, PR_TRUE); 375 } 376 }