Source code
Revision control
Copy as Markdown
Other Tools
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
/*
* shexp.c: shell-like wildcard match routines
*
* See shexp.h for public documentation.
*/
#include "seccomon.h"
#include "portreg.h"
/* ----------------------------- shexp_valid ------------------------------ */
static int
_valid_subexp(const char *exp, char stop1, char stop2)
{
register int x;
int nsc = 0; /* Number of special characters */
int np; /* Number of pipe characters in union */
int tld = 0; /* Number of tilde characters */
for (x = 0; exp[x] && (exp[x] != stop1) && (exp[x] != stop2); ++x) {
switch (exp[x]) {
case '~':
if (tld) /* at most one exclusion */
return INVALID_SXP;
if (stop1) /* no exclusions within unions */
return INVALID_SXP;
if (!exp[x + 1]) /* exclusion cannot be last character */
return INVALID_SXP;
if (!x) /* exclusion cannot be first character */
return INVALID_SXP;
++tld;
/* fall through */
case '*':
case '?':
case '$':
++nsc;
break;
case '[':
++nsc;
if ((!exp[++x]) || (exp[x] == ']'))
return INVALID_SXP;
for (; exp[x] && (exp[x] != ']'); ++x) {
if (exp[x] == '\\' && !exp[++x])
return INVALID_SXP;
}
if (!exp[x])
return INVALID_SXP;
break;
case '(':
++nsc;
if (stop1) /* no nested unions */
return INVALID_SXP;
np = -1;
do {
int t = _valid_subexp(&exp[++x], ')', '|');
if (t == 0 || t == INVALID_SXP)
return INVALID_SXP;
x += t;
if (!exp[x])
return INVALID_SXP;
++np;
} while (exp[x] == '|');
if (np < 1) /* must be at least one pipe */
return INVALID_SXP;
break;
case ')':
case '|':
case ']':
return INVALID_SXP;
case '\\':
++nsc;
if (!exp[++x])
return INVALID_SXP;
break;
default:
break;
}
}
if ((!stop1) && (!nsc)) /* must be at least one special character */
return NON_SXP;
return ((exp[x] == stop1 || exp[x] == stop2) ? x : INVALID_SXP);
}
int
PORT_RegExpValid(const char *exp)
{
int x;
x = _valid_subexp(exp, '\0', '\0');
return (x < 0 ? x : VALID_SXP);
}
/* ----------------------------- shexp_match ----------------------------- */
#define MATCH 0
#define NOMATCH 1
#define ABORTED -1
static int
_shexp_match(const char *str, const char *exp, PRBool case_insensitive,
unsigned int level);
/* Count characters until we reach a NUL character or either of the
* two delimiter characters, stop1 or stop2. If we encounter a bracketed
* expression, look only for NUL or ']' inside it. Do not look for stop1
* or stop2 inside it. Return ABORTED if bracketed expression is unterminated.
* Handle all escaping.
* Return index in input string of first stop found, or ABORTED if not found.
* If "dest" is non-NULL, copy counted characters to it and NUL terminate.
*/
static int
_scan_and_copy(const char *exp, char stop1, char stop2, char *dest)
{
register int sx; /* source index */
register char cc;
for (sx = 0; (cc = exp[sx]) && cc != stop1 && cc != stop2; sx++) {
if (cc == '\\') {
if (!exp[++sx])
return ABORTED; /* should be impossible */
} else if (cc == '[') {
while ((cc = exp[++sx]) && cc != ']') {
if (cc == '\\' && !exp[++sx])
return ABORTED;
}
if (!cc)
return ABORTED; /* should be impossible */
}
}
if (dest && sx) {
/* Copy all but the closing delimiter. */
memcpy(dest, exp, sx);
dest[sx] = 0;
}
return cc ? sx : ABORTED; /* index of closing delimiter */
}
/* On input, exp[0] is the opening parenthesis of a union.
* See if any of the alternatives in the union matches as a pattern.
* The strategy is to take each of the alternatives, in turn, and append
* the rest of the expression (after the closing ')' that marks the end of
* this union) to that alternative, and then see if the resultant expression
* matches the input string. Repeat this until some alternative matches,
* or we have an abort.
*/
static int
_handle_union(const char *str, const char *exp, PRBool case_insensitive,
unsigned int level)
{
register int sx; /* source index */
int cp; /* source index of closing parenthesis */
int count;
int ret = NOMATCH;
char *e2;
/* Find the closing parenthesis that ends this union in the expression */
cp = _scan_and_copy(exp, ')', '\0', NULL);
if (cp == ABORTED || cp < 4) /* must be at least "(a|b" before ')' */
return ABORTED;
++cp; /* now index of char after closing parenthesis */
e2 = (char *)PORT_Alloc(1 + strlen(exp));
if (!e2)
return ABORTED;
for (sx = 1;; ++sx) {
/* Here, exp[sx] is one character past the preceding '(' or '|'. */
/* Copy everything up to the next delimiter to e2 */
count = _scan_and_copy(exp + sx, ')', '|', e2);
if (count == ABORTED || !count) {
ret = ABORTED;
break;
}
sx += count;
/* Append everything after closing parenthesis to e2. This is safe. */
strcpy(e2 + count, exp + cp);
ret = _shexp_match(str, e2, case_insensitive, level + 1);
if (ret != NOMATCH || !exp[sx] || exp[sx] == ')')
break;
}
PORT_Free(e2);
if (sx < 2)
ret = ABORTED;
return ret;
}
/* returns 1 if val is in range from start..end, case insensitive. */
static int
_is_char_in_range(int start, int end, int val)
{
char map[256];
memset(map, 0, sizeof map);
while (start <= end)
map[tolower(start++)] = 1;
return map[tolower(val)];
}
static int
_shexp_match(const char *str, const char *exp, PRBool case_insensitive,
unsigned int level)
{
register int x; /* input string index */
register int y; /* expression index */
int ret, neg;
if (level > 20) /* Don't let the stack get too deep. */
return ABORTED;
for (x = 0, y = 0; exp[y]; ++y, ++x) {
if ((!str[x]) && (exp[y] != '$') && (exp[y] != '*')) {
return NOMATCH;
}
switch (exp[y]) {
case '$':
if (str[x])
return NOMATCH;
--x; /* we don't want loop to increment x */
break;
case '*':
while (exp[++y] == '*') {
}
if (!exp[y])
return MATCH;
while (str[x]) {
ret = _shexp_match(&str[x++], &exp[y], case_insensitive,
level + 1);
switch (ret) {
case NOMATCH:
continue;
case ABORTED:
return ABORTED;
default:
return MATCH;
}
}
if ((exp[y] == '$') && (exp[y + 1] == '\0') && (!str[x]))
return MATCH;
else
return NOMATCH;
case '[': {
int start, end = 0, i;
neg = ((exp[++y] == '^') && (exp[y + 1] != ']'));
if (neg)
++y;
i = y;
start = (unsigned char)(exp[i++]);
if (start == '\\')
start = (unsigned char)(exp[i++]);
if (isalnum(start) && exp[i++] == '-') {
end = (unsigned char)(exp[i++]);
if (end == '\\')
end = (unsigned char)(exp[i++]);
}
if (isalnum(end) && exp[i] == ']') {
/* This is a range form: a-b */
int val = (unsigned char)(str[x]);
if (end < start) { /* swap them */
start ^= end;
end ^= start;
start ^= end;
}
if (case_insensitive && isalpha(val)) {
val = _is_char_in_range(start, end, val);
if (neg == val)
return NOMATCH;
} else if (neg != ((val < start) || (val > end))) {
return NOMATCH;
}
y = i;
} else {
/* Not range form */
int matched = 0;
for (; exp[y] != ']'; y++) {
if (exp[y] == '\\')
++y;
if (case_insensitive) {
matched |= (toupper(str[x]) == toupper(exp[y]));
} else {
matched |= (str[x] == exp[y]);
}
}
if (neg == matched)
return NOMATCH;
}
} break;
case '(':
if (!exp[y + 1])
return ABORTED;
return _handle_union(&str[x], &exp[y], case_insensitive, level);
case '?':
break;
case '|':
case ']':
case ')':
return ABORTED;
case '\\':
++y;
/* fall through */
default:
if (case_insensitive) {
if (toupper(str[x]) != toupper(exp[y]))
return NOMATCH;
} else {
if (str[x] != exp[y])
return NOMATCH;
}
break;
}
}
return (str[x] ? NOMATCH : MATCH);
}
static int
port_RegExpMatch(const char *str, const char *xp, PRBool case_insensitive)
{
char *exp = 0;
int x, ret = MATCH;
if (!strchr(xp, '~'))
return _shexp_match(str, xp, case_insensitive, 0);
exp = PORT_Strdup(xp);
if (!exp)
return NOMATCH;
x = _scan_and_copy(exp, '~', '\0', NULL);
if (x != ABORTED && exp[x] == '~') {
exp[x++] = '\0';
ret = _shexp_match(str, &exp[x], case_insensitive, 0);
switch (ret) {
case NOMATCH:
ret = MATCH;
break;
case MATCH:
ret = NOMATCH;
break;
default:
break;
}
}
if (ret == MATCH)
ret = _shexp_match(str, exp, case_insensitive, 0);
PORT_Free(exp);
return ret;
}
/* ------------------------------ shexp_cmp ------------------------------- */
int
PORT_RegExpSearch(const char *str, const char *exp)
{
switch (PORT_RegExpValid(exp)) {
case INVALID_SXP:
return -1;
case NON_SXP:
return (strcmp(exp, str) ? 1 : 0);
default:
return port_RegExpMatch(str, exp, PR_FALSE);
}
}
int
PORT_RegExpCaseSearch(const char *str, const char *exp)
{
switch (PORT_RegExpValid(exp)) {
case INVALID_SXP:
return -1;
case NON_SXP:
return (PORT_Strcasecmp(exp, str) ? 1 : 0);
default:
return port_RegExpMatch(str, exp, PR_TRUE);
}
}