Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : /* *
8 : *
9 : *
10 : * nsWildCard.cpp: shell-like wildcard match routines
11 : *
12 : * See nsIZipReader.findEntries documentation in nsIZipReader.idl for
13 : * a description of the syntax supported by the routines in this file.
14 : *
15 : * Rob McCool
16 : *
17 : */
18 :
19 : #include "nsWildCard.h"
20 : #include "nsXPCOM.h"
21 : #include "nsCRTGlue.h"
22 : #include "nsCharTraits.h"
23 :
24 : /* -------------------- ASCII-specific character methods ------------------- */
25 :
26 : typedef int static_assert_character_code_arrangement['a' > 'A' ? 1 : -1];
27 :
28 : template<class T>
29 : static int
30 0 : alpha(T aChar)
31 : {
32 0 : return ('a' <= aChar && aChar <= 'z') ||
33 0 : ('A' <= aChar && aChar <= 'Z');
34 : }
35 :
36 : template<class T>
37 : static int
38 0 : alphanumeric(T aChar)
39 : {
40 0 : return ('0' <= aChar && aChar <= '9') || ::alpha(aChar);
41 : }
42 :
43 : template<class T>
44 : static int
45 0 : lower(T aChar)
46 : {
47 0 : return ('A' <= aChar && aChar <= 'Z') ? aChar + ('a' - 'A') : aChar;
48 : }
49 :
50 : template<class T>
51 : static int
52 0 : upper(T aChar)
53 : {
54 0 : return ('a' <= aChar && aChar <= 'z') ? aChar - ('a' - 'A') : aChar;
55 : }
56 :
57 : /* ----------------------------- _valid_subexp ---------------------------- */
58 :
59 : template<class T>
60 : static int
61 0 : _valid_subexp(const T* aExpr, T aStop1, T aStop2)
62 : {
63 : int x;
64 0 : int nsc = 0; /* Number of special characters */
65 : int np; /* Number of pipe characters in union */
66 0 : int tld = 0; /* Number of tilde characters */
67 :
68 0 : for (x = 0; aExpr[x] && (aExpr[x] != aStop1) && (aExpr[x] != aStop2); ++x) {
69 0 : switch (aExpr[x]) {
70 : case '~':
71 0 : if (tld) { /* at most one exclusion */
72 0 : return INVALID_SXP;
73 : }
74 0 : if (aStop1) { /* no exclusions within unions */
75 0 : return INVALID_SXP;
76 : }
77 0 : if (!aExpr[x + 1]) { /* exclusion cannot be last character */
78 0 : return INVALID_SXP;
79 : }
80 0 : if (!x) { /* exclusion cannot be first character */
81 0 : return INVALID_SXP;
82 : }
83 0 : ++tld;
84 : MOZ_FALLTHROUGH;
85 : case '*':
86 : case '?':
87 : case '$':
88 0 : ++nsc;
89 0 : break;
90 : case '[':
91 0 : ++nsc;
92 0 : if ((!aExpr[++x]) || (aExpr[x] == ']')) {
93 0 : return INVALID_SXP;
94 : }
95 0 : for (; aExpr[x] && (aExpr[x] != ']'); ++x) {
96 0 : if (aExpr[x] == '\\' && !aExpr[++x]) {
97 0 : return INVALID_SXP;
98 : }
99 : }
100 0 : if (!aExpr[x]) {
101 0 : return INVALID_SXP;
102 : }
103 0 : break;
104 : case '(':
105 0 : ++nsc;
106 0 : if (aStop1) { /* no nested unions */
107 0 : return INVALID_SXP;
108 : }
109 0 : np = -1;
110 0 : do {
111 0 : int t = ::_valid_subexp(&aExpr[++x], T(')'), T('|'));
112 0 : if (t == 0 || t == INVALID_SXP) {
113 0 : return INVALID_SXP;
114 : }
115 0 : x += t;
116 0 : if (!aExpr[x]) {
117 0 : return INVALID_SXP;
118 : }
119 0 : ++np;
120 0 : } while (aExpr[x] == '|');
121 0 : if (np < 1) { /* must be at least one pipe */
122 0 : return INVALID_SXP;
123 : }
124 0 : break;
125 : case ')':
126 : case ']':
127 : case '|':
128 0 : return INVALID_SXP;
129 : case '\\':
130 0 : ++nsc;
131 0 : if (!aExpr[++x]) {
132 0 : return INVALID_SXP;
133 : }
134 0 : break;
135 : default:
136 0 : break;
137 : }
138 : }
139 0 : if (!aStop1 && !nsc) { /* must be at least one special character */
140 0 : return NON_SXP;
141 : }
142 0 : return ((aExpr[x] == aStop1 || aExpr[x] == aStop2) ? x : INVALID_SXP);
143 : }
144 :
145 :
146 : template<class T>
147 : int
148 0 : NS_WildCardValid_(const T* aExpr)
149 : {
150 0 : int x = ::_valid_subexp(aExpr, T('\0'), T('\0'));
151 0 : return (x < 0 ? x : VALID_SXP);
152 : }
153 :
154 : int
155 0 : NS_WildCardValid(const char* aExpr)
156 : {
157 0 : return NS_WildCardValid_(aExpr);
158 : }
159 :
160 : int
161 0 : NS_WildCardValid(const char16_t* aExpr)
162 : {
163 0 : return NS_WildCardValid_(aExpr);
164 : }
165 :
166 : /* ----------------------------- _shexp_match ----------------------------- */
167 :
168 :
169 : #define MATCH 0
170 : #define NOMATCH 1
171 : #define ABORTED -1
172 :
173 : template<class T>
174 : static int
175 : _shexp_match(const T* aStr, const T* aExpr, bool aCaseInsensitive,
176 : unsigned int aLevel);
177 :
178 : /**
179 : * Count characters until we reach a NUL character or either of the
180 : * two delimiter characters, stop1 or stop2. If we encounter a bracketed
181 : * expression, look only for NUL or ']' inside it. Do not look for stop1
182 : * or stop2 inside it. Return ABORTED if bracketed expression is unterminated.
183 : * Handle all escaping.
184 : * Return index in input string of first stop found, or ABORTED if not found.
185 : * If "dest" is non-nullptr, copy counted characters to it and null terminate.
186 : */
187 : template<class T>
188 : static int
189 0 : _scan_and_copy(const T* aExpr, T aStop1, T aStop2, T* aDest)
190 : {
191 : int sx; /* source index */
192 : T cc;
193 :
194 0 : for (sx = 0; (cc = aExpr[sx]) && cc != aStop1 && cc != aStop2; ++sx) {
195 0 : if (cc == '\\') {
196 0 : if (!aExpr[++sx]) {
197 0 : return ABORTED; /* should be impossible */
198 : }
199 0 : } else if (cc == '[') {
200 0 : while ((cc = aExpr[++sx]) && cc != ']') {
201 0 : if (cc == '\\' && !aExpr[++sx]) {
202 0 : return ABORTED;
203 : }
204 : }
205 0 : if (!cc) {
206 0 : return ABORTED; /* should be impossible */
207 : }
208 : }
209 : }
210 0 : if (aDest && sx) {
211 : /* Copy all but the closing delimiter. */
212 0 : memcpy(aDest, aExpr, sx * sizeof(T));
213 0 : aDest[sx] = 0;
214 : }
215 0 : return cc ? sx : ABORTED; /* index of closing delimiter */
216 : }
217 :
218 : /* On input, expr[0] is the opening parenthesis of a union.
219 : * See if any of the alternatives in the union matches as a pattern.
220 : * The strategy is to take each of the alternatives, in turn, and append
221 : * the rest of the expression (after the closing ')' that marks the end of
222 : * this union) to that alternative, and then see if the resultant expression
223 : * matches the input string. Repeat this until some alternative matches,
224 : * or we have an abort.
225 : */
226 : template<class T>
227 : static int
228 0 : _handle_union(const T* aStr, const T* aExpr, bool aCaseInsensitive,
229 : unsigned int aLevel)
230 : {
231 : int sx; /* source index */
232 : int cp; /* source index of closing parenthesis */
233 : int count;
234 0 : int ret = NOMATCH;
235 : T* e2;
236 :
237 : /* Find the closing parenthesis that ends this union in the expression */
238 0 : cp = ::_scan_and_copy(aExpr, T(')'), T('\0'), static_cast<T*>(nullptr));
239 0 : if (cp == ABORTED || cp < 4) { /* must be at least "(a|b" before ')' */
240 0 : return ABORTED;
241 : }
242 0 : ++cp; /* now index of char after closing parenthesis */
243 0 : e2 = (T*)moz_xmalloc((1 + nsCharTraits<T>::length(aExpr)) * sizeof(T));
244 0 : if (!e2) {
245 0 : return ABORTED;
246 : }
247 0 : for (sx = 1; ; ++sx) {
248 : /* Here, aExpr[sx] is one character past the preceding '(' or '|'. */
249 : /* Copy everything up to the next delimiter to e2 */
250 0 : count = ::_scan_and_copy(aExpr + sx, T(')'), T('|'), e2);
251 0 : if (count == ABORTED || !count) {
252 0 : ret = ABORTED;
253 0 : break;
254 : }
255 0 : sx += count;
256 : /* Append everything after closing parenthesis to e2. This is safe. */
257 0 : nsCharTraits<T>::copy(e2 + count, aExpr + cp,
258 0 : nsCharTraits<T>::length(aExpr + cp) + 1);
259 0 : ret = ::_shexp_match(aStr, e2, aCaseInsensitive, aLevel + 1);
260 0 : if (ret != NOMATCH || !aExpr[sx] || aExpr[sx] == ')') {
261 : break;
262 : }
263 : }
264 0 : free(e2);
265 0 : if (sx < 2) {
266 0 : ret = ABORTED;
267 : }
268 0 : return ret;
269 : }
270 :
271 : /* returns 1 if val is in range from start..end, case insensitive. */
272 : static int
273 0 : _is_char_in_range(unsigned char aStart, unsigned char aEnd, unsigned char aVal)
274 : {
275 : char map[256];
276 0 : memset(map, 0, sizeof(map));
277 0 : while (aStart <= aEnd) {
278 0 : map[lower(aStart++)] = 1;
279 : }
280 0 : return map[lower(aVal)];
281 : }
282 :
283 : template<class T>
284 : static int
285 0 : _shexp_match(const T* aStr, const T* aExpr, bool aCaseInsensitive,
286 : unsigned int aLevel)
287 : {
288 : int x; /* input string index */
289 : int y; /* expression index */
290 : int ret, neg;
291 :
292 0 : if (aLevel > 20) { /* Don't let the stack get too deep. */
293 0 : return ABORTED;
294 : }
295 0 : for (x = 0, y = 0; aExpr[y]; ++y, ++x) {
296 0 : if (!aStr[x] && aExpr[y] != '$' && aExpr[y] != '*') {
297 0 : return NOMATCH;
298 : }
299 0 : switch (aExpr[y]) {
300 : case '$':
301 0 : if (aStr[x]) {
302 0 : return NOMATCH;
303 : }
304 0 : --x; /* we don't want loop to increment x */
305 0 : break;
306 : case '*':
307 0 : while (aExpr[++y] == '*') {
308 : }
309 0 : if (!aExpr[y]) {
310 0 : return MATCH;
311 : }
312 0 : while (aStr[x]) {
313 0 : ret = ::_shexp_match(&aStr[x++], &aExpr[y], aCaseInsensitive,
314 : aLevel + 1);
315 0 : switch (ret) {
316 : case NOMATCH:
317 0 : continue;
318 : case ABORTED:
319 0 : return ABORTED;
320 : default:
321 0 : return MATCH;
322 : }
323 : }
324 0 : if (aExpr[y] == '$' && aExpr[y + 1] == '\0' && !aStr[x]) {
325 0 : return MATCH;
326 : } else {
327 0 : return NOMATCH;
328 : }
329 : case '[': {
330 0 : T start, end = 0;
331 : int i;
332 0 : ++y;
333 0 : neg = (aExpr[y] == '^' && aExpr[y + 1] != ']');
334 0 : if (neg) {
335 0 : ++y;
336 : }
337 0 : i = y;
338 0 : start = aExpr[i++];
339 0 : if (start == '\\') {
340 0 : start = aExpr[i++];
341 : }
342 0 : if (::alphanumeric(start) && aExpr[i++] == '-') {
343 0 : end = aExpr[i++];
344 0 : if (end == '\\') {
345 0 : end = aExpr[i++];
346 : }
347 : }
348 0 : if (::alphanumeric(end) && aExpr[i] == ']') {
349 : /* This is a range form: a-b */
350 0 : T val = aStr[x];
351 0 : if (end < start) { /* swap them */
352 0 : T tmp = end;
353 0 : end = start;
354 0 : start = tmp;
355 : }
356 0 : if (aCaseInsensitive && ::alpha(val)) {
357 0 : val = ::_is_char_in_range((unsigned char)start,
358 : (unsigned char)end,
359 : (unsigned char)val);
360 0 : if (neg == val) {
361 0 : return NOMATCH;
362 : }
363 0 : } else if (neg != (val < start || val > end)) {
364 0 : return NOMATCH;
365 : }
366 0 : y = i;
367 : } else {
368 : /* Not range form */
369 0 : int matched = 0;
370 0 : for (; aExpr[y] != ']'; ++y) {
371 0 : if (aExpr[y] == '\\') {
372 0 : ++y;
373 : }
374 0 : if (aCaseInsensitive) {
375 0 : matched |= (::upper(aStr[x]) == ::upper(aExpr[y]));
376 : } else {
377 0 : matched |= (aStr[x] == aExpr[y]);
378 : }
379 : }
380 0 : if (neg == matched) {
381 0 : return NOMATCH;
382 : }
383 : }
384 : }
385 0 : break;
386 : case '(':
387 0 : if (!aExpr[y + 1]) {
388 0 : return ABORTED;
389 : }
390 0 : return ::_handle_union(&aStr[x], &aExpr[y], aCaseInsensitive,
391 0 : aLevel + 1);
392 : case '?':
393 0 : break;
394 : case ')':
395 : case ']':
396 : case '|':
397 0 : return ABORTED;
398 : case '\\':
399 0 : ++y;
400 : MOZ_FALLTHROUGH;
401 : default:
402 0 : if (aCaseInsensitive) {
403 0 : if (::upper(aStr[x]) != ::upper(aExpr[y])) {
404 0 : return NOMATCH;
405 : }
406 : } else {
407 0 : if (aStr[x] != aExpr[y]) {
408 0 : return NOMATCH;
409 : }
410 : }
411 0 : break;
412 : }
413 : }
414 0 : return (aStr[x] ? NOMATCH : MATCH);
415 : }
416 :
417 : template<class T>
418 : static int
419 0 : ns_WildCardMatch(const T* aStr, const T* aXp, bool aCaseInsensitive)
420 : {
421 0 : T* expr = nullptr;
422 0 : int ret = MATCH;
423 :
424 0 : if (!nsCharTraits<T>::find(aXp, nsCharTraits<T>::length(aXp), T('~'))) {
425 0 : return ::_shexp_match(aStr, aXp, aCaseInsensitive, 0);
426 : }
427 :
428 0 : expr = (T*)moz_xmalloc((nsCharTraits<T>::length(aXp) + 1) * sizeof(T));
429 0 : if (!expr) {
430 0 : return NOMATCH;
431 : }
432 0 : memcpy(expr, aXp, (nsCharTraits<T>::length(aXp) + 1) * sizeof(T));
433 :
434 0 : int x = ::_scan_and_copy(expr, T('~'), T('\0'), static_cast<T*>(nullptr));
435 0 : if (x != ABORTED && expr[x] == '~') {
436 0 : expr[x++] = '\0';
437 0 : ret = ::_shexp_match(aStr, &expr[x], aCaseInsensitive, 0);
438 0 : switch (ret) {
439 : case NOMATCH:
440 0 : ret = MATCH;
441 0 : break;
442 : case MATCH:
443 0 : ret = NOMATCH;
444 0 : break;
445 : default:
446 0 : break;
447 : }
448 : }
449 0 : if (ret == MATCH) {
450 0 : ret = ::_shexp_match(aStr, expr, aCaseInsensitive, 0);
451 : }
452 :
453 0 : free(expr);
454 0 : return ret;
455 : }
456 :
457 : template<class T>
458 : int
459 0 : NS_WildCardMatch_(const T* aStr, const T* aExpr, bool aCaseInsensitive)
460 : {
461 0 : int is_valid = NS_WildCardValid(aExpr);
462 0 : switch (is_valid) {
463 : case INVALID_SXP:
464 0 : return -1;
465 : default:
466 0 : return ::ns_WildCardMatch(aStr, aExpr, aCaseInsensitive);
467 : }
468 : }
469 :
470 : int
471 0 : NS_WildCardMatch(const char* aStr, const char* aXp, bool aCaseInsensitive)
472 : {
473 0 : return NS_WildCardMatch_(aStr, aXp, aCaseInsensitive);
474 : }
475 :
476 : int
477 0 : NS_WildCardMatch(const char16_t* aStr, const char16_t* aXp,
478 : bool aCaseInsensitive)
479 : {
480 0 : return NS_WildCardMatch_(aStr, aXp, aCaseInsensitive);
481 9 : }
|
