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