1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
5 *
6 * THE BSD LICENSE
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are met:
10 *
11 * Redistributions of source code must retain the above copyright notice, this
12 * list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above copyright notice,
14 * this list of conditions and the following disclaimer in the documentation
15 * and/or other materials provided with the distribution.
16 *
17 * Neither the name of the nor the names of its contributors may be
18 * used to endorse or promote products derived from this software without
19 * specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
25 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
28 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
29 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
30 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
31 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 /*
35 * shexp.c: shell-like wildcard match routines
36 *
37 *
38 * See shexp.h for public documentation.
39 *
40 * Rob McCool
41 *
42 */
43
44 #include <ctype.h> /* isalpha, tolower */
45
46 #include "shexp.h"
47
48
49 /*
50 * The observant engineer will notice 2 distinct sets of functions here.
51 * All of the noicmp flavor of functions do case sensitive compares on all
52 * platforms. The other set (public set) does case insensitive compares on NT.
53 */
54 int _shexp_match_noicmp(const char *str, const char *exp) ;
55
56
57 /* ----------------------------- shexp_valid ------------------------------ */
58
59
60 int valid_subexp(const char *exp, char stop)
61 {
62 register int x,y,t;
63 int nsc,np,tld;
64
65 x=0;nsc=0;tld=0;
66
67 while(exp[x] && (exp[x] != stop)) {
68 switch(exp[x]) {
69 case '~':
70 if(tld) return INVALID_SXP;
71 else ++tld;
72 case '*':
73 case '?':
74 case '^':
75 case '$':
76 ++nsc;
77 break;
78 case '[':
79 ++nsc;
80 if((!exp[++x]) || (exp[x] == ']'))
81 return INVALID_SXP;
82 for(++x;exp[x] && (exp[x] != ']');++x)
83 if(exp[x] == '\\')
84 if(!exp[++x])
85 return INVALID_SXP;
86 if(!exp[x])
87 return INVALID_SXP;
88 break;
89 case '(':
90 ++nsc;
91 while(1) {
92 if(exp[++x] == ')')
93 return INVALID_SXP;
94 for(y=x;(exp[y]) && (exp[y] != '|') && (exp[y] != ')');++y)
95 if(exp[y] == '\\')
96 if(!exp[++y])
97 return INVALID_SXP;
98 if(!exp[y])
99 return INVALID_SXP;
100 t = valid_subexp(&exp[x],exp[y]);
101 if(t == INVALID_SXP)
102 return INVALID_SXP;
103 x+=t;
104 if(exp[x] == ')') {
105 break;
106 }
107 }
108 break;
109 case ')':
110 case ']':
111 return INVALID_SXP;
112 case '\\':
113 if(!exp[++x])
114 return INVALID_SXP;
115 default:
116 break;
117 }
118 ++x;
119 }
120 if((!stop) && (!nsc))
121 return NON_SXP;
122 return ((exp[x] == stop) ? x : INVALID_SXP);
123 }
124
125 NSAPI_PUBLIC int shexp_valid(const char *exp) {
126 int x;
127
128 x = valid_subexp(exp, '\0');
129 if (x < 0) {
130 if (x == INVALID_SXP) {
131 //NsprError::setError(PR_INVALID_ARGUMENT_ERROR,
132 // XP_GetAdminStr(DBT_invalidshexp));
133 // TODO
134 }
135 return x;
136 }
137 return VALID_SXP;
138 }
139
140
141 /* ----------------------------- shexp_match ----------------------------- */
142
143
144 #define MATCH 0
145 #define NOMATCH 1
146 #define ABORTED -1
147
148 int _shexp_match(const char *str, const char *exp);
149
150 int handle_union(const char *str, const char *exp)
151 {
152 char *e2 = (char *) MALLOC(sizeof(char)*strlen(exp));
153 register int t,p2,p1 = 1;
154 int cp;
155
156 while(1) {
157 for(cp=1;exp[cp] != ')';cp++)
158 if(exp[cp] == '\\')
159 ++cp;
160 for(p2 = 0;(exp[p1] != '|') && (p1 != cp);p1++,p2++) {
161 if(exp[p1] == '\\')
162 e2[p2++] = exp[p1++];
163 e2[p2] = exp[p1];
164 }
165 for(t=cp+1;(e2[p2] = exp[t]);++t,++p2);
166 if(_shexp_match(str,e2) == MATCH) {
167 FREE(e2);
168 return MATCH;
169 }
170 if(p1 == cp) {
171 FREE(e2);
172 return NOMATCH;
173 }
174 else ++p1;
175 }
176 }
177
178 int handle_union_noicmp(const char *str, const char *exp)
179 {
180 char *e2 = (char *) MALLOC(sizeof(char)*strlen(exp));
181 register int t,p2,p1 = 1;
182 int cp;
183
184 while(1) {
185 for(cp=1;exp[cp] != ')';cp++)
186 if(exp[cp] == '\\')
187 ++cp;
188 for(p2 = 0;(exp[p1] != '|') && (p1 != cp);p1++,p2++) {
189 if(exp[p1] == '\\')
190 e2[p2++] = exp[p1++];
191 e2[p2] = exp[p1];
192 }
193 for(t=cp+1;(e2[p2] = exp[t]);++t,++p2);
194 if(_shexp_match_noicmp(str,e2) == MATCH) {
195 FREE(e2);
196 return MATCH;
197 }
198 if(p1 == cp) {
199 FREE(e2);
200 return NOMATCH;
201 }
202 else ++p1;
203 }
204 }
205
206 int _shexp_match(const char *str, const char *exp)
207 {
208 register int x,y;
209 int ret,neg;
210
211 ret = 0;
212 for(x=0,y=0;exp[y];++y,++x) {
213 if((!str[x]) && (exp[y] != '(') && (exp[y] != '$') && (exp[y] != '*'))
214 ret = ABORTED;
215 else {
216 switch(exp[y]) {
217 case '$':
218 if( (str[x]) )
219 ret = NOMATCH;
220 else
221 --x; /* we don't want loop to increment x */
222 break;
223 case '*':
224 while(exp[++y] == '*');
225 if(!exp[y])
226 return MATCH;
227 while(str[x]) {
228 switch(_shexp_match(&str[x++],&exp[y])) {
229 case NOMATCH:
230 continue;
231 case ABORTED:
232 ret = ABORTED;
233 break;
234 default:
235 return MATCH;
236 }
237 break;
238 }
239 if((exp[y] == '$') && (exp[y+1] == '\0') && (!str[x]))
240 return MATCH;
241 else
242 ret = ABORTED;
243 break;
244 case '[':
245 if((neg = ((exp[++y] == '^') && (exp[y+1] != ']'))))
246 ++y;
247
248 if((isalnum(exp[y])) && (exp[y+1] == '-') &&
249 (isalnum(exp[y+2])) && (exp[y+3] == ']'))
250 {
251 int start = exp[y], end = exp[y+2];
252
253 /* Droolproofing for pinheads not included */
254 if(neg ^ ((str[x] < start) || (str[x] > end))) {
255 ret = NOMATCH;
256 break;
257 }
258 y+=3;
259 }
260 else {
261 int matched;
262
263 for(matched=0;exp[y] != ']';y++)
264 matched |= (str[x] == exp[y]);
265 if(neg ^ (!matched))
266 ret = NOMATCH;
267 }
268 break;
269 case '(':
270 return handle_union(&str[x],&exp[y]);
271 break;
272 case '?':
273 break;
274 case '\\':
275 ++y;
276 default:
277 #ifdef XP_UNIX
278 if(str[x] != exp[y])
279 #else /* XP_WIN32 */
280 if(strnicmp(str + x, exp + y, 1))
281 #endif /* XP_WIN32 */
282 ret = NOMATCH;
283 break;
284 }
285 }
286 if(ret)
287 break;
288 }
289 return (ret ? ret : (str[x] ? NOMATCH : MATCH));
290 }
291
292 int _shexp_match_noicmp(const char *str, const char *exp)
293 {
294 register int x,y;
295 int ret,neg;
296
297 ret = 0;
298 for(x=0,y=0;exp[y];++y,++x) {
299 if((!str[x]) && (exp[y] != '(') && (exp[y] != '$') && (exp[y] != '*'))
300 ret = ABORTED;
301 else {
302 switch(exp[y]) {
303 case '$':
304 if( (str[x]) )
305 ret = NOMATCH;
306 else
307 --x; /* we don't want loop to increment x */
308 break;
309 case '*':
310 while(exp[++y] == '*');
311 if(!exp[y])
312 return MATCH;
313 while(str[x]) {
314 switch(_shexp_match_noicmp(&str[x++],&exp[y])) {
315 case NOMATCH:
316 continue;
317 case ABORTED:
318 ret = ABORTED;
319 break;
320 default:
321 return MATCH;
322 }
323 break;
324 }
325 if((exp[y] == '$') && (exp[y+1] == '\0') && (!str[x]))
326 return MATCH;
327 else
328 ret = ABORTED;
329 break;
330 case '[':
331 if((neg = ((exp[++y] == '^') && (exp[y+1] != ']'))))
332 ++y;
333
334 if((isalnum(exp[y])) && (exp[y+1] == '-') &&
335 (isalnum(exp[y+2])) && (exp[y+3] == ']'))
336 {
337 int start = exp[y], end = exp[y+2];
338
339 /* Droolproofing for pinheads not included */
340 if(neg ^ ((str[x] < start) || (str[x] > end))) {
341 ret = NOMATCH;
342 break;
343 }
344 y+=3;
345 }
346 else {
347 int matched;
348
349 for(matched=0;exp[y] != ']';y++)
350 matched |= (str[x] == exp[y]);
351 if(neg ^ (!matched))
352 ret = NOMATCH;
353 }
354 break;
355 case '(':
356 return handle_union_noicmp(&str[x],&exp[y]);
357 break;
358 case '?':
359 break;
360 case '\\':
361 ++y;
362 default:
363 if(str[x] != exp[y])
364 ret = NOMATCH;
365 break;
366 }
367 }
368 if(ret)
369 break;
370 }
371 return (ret ? ret : (str[x] ? NOMATCH : MATCH));
372 }
373
374 NSAPI_PUBLIC int shexp_match(const char *str, const char *exp)
375 {
376 register int x;
377 char *expbase = NULL;
378
379 for(x=strlen(exp)-1;x;--x) {
380 if((exp[x] == '~') && (exp[x-1] != '\\')) {
381 /* we're done if the negative subexp matches */
382 if(_shexp_match(str,&exp[x+1]) == MATCH)
383 return 1;
384 /* we're done if the only thing in front of the subexp is '*' */
385 if (x == 1 && exp[0] == '*')
386 return 0;
387 /* create a copy so we can strip off the subexp */
388 expbase = STRDUP(exp);
389 expbase[x] = '\0';
390 exp = expbase;
391 break;
392 }
393 }
394 if(_shexp_match(str,exp) == MATCH) {
395 if (expbase)
396 FREE(expbase);
397 return 0;
398 }
399
400 if (expbase)
401 FREE(expbase);
402 return 1;
403 }
404
405 NSAPI_PUBLIC int shexp_match_noicmp(const char *str, const char *exp)
406 {
407 register int x;
408 char *expbase = NULL;
409
410 for(x=strlen(exp)-1;x;--x) {
411 if((exp[x] == '~') && (exp[x-1] != '\\')) {
412 /* we're done if the negative subexp matches */
413 if(_shexp_match_noicmp(str,&exp[x+1]) == MATCH)
414 return 1;
415 /* we're done if the only thing in front of the subexp is '*' */
416 if (x == 1 && exp[0] == '*')
417 return 0;
418 /* create a copy so we can strip off the subexp */
419 expbase = STRDUP(exp);
420 expbase[x] = '\0';
421 exp = expbase;
422 break;
423 }
424 }
425 if(_shexp_match_noicmp(str,exp) == MATCH) {
426 if (expbase)
427 FREE(expbase);
428 return 0;
429 }
430
431 if (expbase)
432 FREE(expbase);
433 return 1;
434 }
435
436 /* ------------------------------ shexp_cmp ------------------------------- */
437
438
439 NSAPI_PUBLIC int shexp_cmp(const char *str, const char *exp)
440 {
441 switch(shexp_valid(exp)) {
442 case INVALID_SXP:
443 return -1;
444 case NON_SXP:
445 #ifdef XP_UNIX
446 return (strcmp(exp,str) ? 1 : 0);
447 #else /* XP_WIN32 */
448 return (stricmp(exp,str) ? 1 : 0);
449 #endif /* XP_WIN32 */
450 default:
451 return shexp_match(str, exp);
452 }
453 }
454
455 /* ------------------------------ shexp_cmp ------------------------------- */
456
457 NSAPI_PUBLIC int shexp_noicmp(const char *str, const char *exp)
458 {
459 switch(shexp_valid(exp)) {
460 case INVALID_SXP:
461 return -1;
462 case NON_SXP:
463 return (strcmp(exp,str) ? 1 : 0);
464 default:
465 return shexp_match_noicmp(str, exp);
466 }
467 }
468
469 /* ---------------------------- shexp_casecmp ----------------------------- */
470
471
472 NSAPI_PUBLIC int shexp_casecmp(const char *str, const char *exp)
473 {
474 char *lstr = STRDUP(str), *lexp = STRDUP(exp), *t;
475 int ret;
476
477 for(t = lstr; *t; t++)
478 if(isalpha(*t)) *t = tolower(*t);
479 for(t = lexp; *t; t++)
480 if(isalpha(*t)) *t = tolower(*t);
481
482 switch(shexp_valid(lexp)) {
483 case INVALID_SXP:
484 ret = -1;
485 break;
486 case NON_SXP:
487 ret = (strcmp(lexp, lstr) ? 1 : 0);
488 break;
489 default:
490 ret = shexp_match(lstr, lexp);
491 }
492 FREE(lstr);
493 FREE(lexp);
494 return ret;
495 }
496
497