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
_valid_subexp(const char * exp,char stop1,char stop2)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
PORT_RegExpValid(const char * exp)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
_scan_and_copy(const char * exp,char stop1,char stop2,char * dest)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
_handle_union(const char * str,const char * exp,PRBool case_insensitive,unsigned int level)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
_is_char_in_range(int start,int end,int val)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
_shexp_match(const char * str,const char * exp,PRBool case_insensitive,unsigned int level)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(str[x]) == toupper(exp[y]));
279 } else {
280 matched |= (str[x] == exp[y]);
281 }
282 }
283 if (neg == matched)
284 return NOMATCH;
285 }
286 } break;
287 case '(':
288 if (!exp[y + 1])
289 return ABORTED;
290 return _handle_union(&str[x], &exp[y], case_insensitive, level);
291 case '?':
292 break;
293 case '|':
294 case ']':
295 case ')':
296 return ABORTED;
297 case '\\':
298 ++y;
299 /* fall through */
300 default:
301 if (case_insensitive) {
302 if (toupper(str[x]) != toupper(exp[y]))
303 return NOMATCH;
304 } else {
305 if (str[x] != exp[y])
306 return NOMATCH;
307 }
308 break;
309 }
310 }
311 return (str[x] ? NOMATCH : MATCH);
312 }
313
314 static int
port_RegExpMatch(const char * str,const char * xp,PRBool case_insensitive)315 port_RegExpMatch(const char *str, const char *xp, PRBool case_insensitive)
316 {
317 char *exp = 0;
318 int x, ret = MATCH;
319
320 if (!strchr(xp, '~'))
321 return _shexp_match(str, xp, case_insensitive, 0);
322
323 exp = PORT_Strdup(xp);
324 if (!exp)
325 return NOMATCH;
326
327 x = _scan_and_copy(exp, '~', '\0', NULL);
328 if (x != ABORTED && exp[x] == '~') {
329 exp[x++] = '\0';
330 ret = _shexp_match(str, &exp[x], case_insensitive, 0);
331 switch (ret) {
332 case NOMATCH:
333 ret = MATCH;
334 break;
335 case MATCH:
336 ret = NOMATCH;
337 break;
338 default:
339 break;
340 }
341 }
342 if (ret == MATCH)
343 ret = _shexp_match(str, exp, case_insensitive, 0);
344
345 PORT_Free(exp);
346 return ret;
347 }
348
349 /* ------------------------------ shexp_cmp ------------------------------- */
350
351 int
PORT_RegExpSearch(const char * str,const char * exp)352 PORT_RegExpSearch(const char *str, const char *exp)
353 {
354 switch (PORT_RegExpValid(exp)) {
355 case INVALID_SXP:
356 return -1;
357 case NON_SXP:
358 return (strcmp(exp, str) ? 1 : 0);
359 default:
360 return port_RegExpMatch(str, exp, PR_FALSE);
361 }
362 }
363
364 int
PORT_RegExpCaseSearch(const char * str,const char * exp)365 PORT_RegExpCaseSearch(const char *str, const char *exp)
366 {
367 switch (PORT_RegExpValid(exp)) {
368 case INVALID_SXP:
369 return -1;
370 case NON_SXP:
371 return (PORT_Strcasecmp(exp, str) ? 1 : 0);
372 default:
373 return port_RegExpMatch(str, exp, PR_TRUE);
374 }
375 }
376