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/. */
10 * nsWildCard.cpp: shell-like wildcard match routines
12 * See nsIZipReader.findEntries documentation in nsIZipReader.idl for
13 * a description of the syntax supported by the routines in this file.
19 #include "nsWildCard.h"
21 #include "nsCRTGlue.h"
22 #include "nsCharTraits.h"
24 /* -------------------- ASCII-specific character methods ------------------- */
26 typedef int static_assert_character_code_arrangement
['a' > 'A' ? 1 : -1];
29 static int alpha(T aChar
) {
30 return ('a' <= aChar
&& aChar
<= 'z') || ('A' <= aChar
&& aChar
<= 'Z');
34 static int alphanumeric(T aChar
) {
35 return ('0' <= aChar
&& aChar
<= '9') || ::alpha(aChar
);
39 static int lower(T aChar
) {
40 return ('A' <= aChar
&& aChar
<= 'Z') ? aChar
+ ('a' - 'A') : aChar
;
44 static int upper(T aChar
) {
45 return ('a' <= aChar
&& aChar
<= 'z') ? aChar
- ('a' - 'A') : aChar
;
48 /* ----------------------------- _valid_subexp ---------------------------- */
51 static int _valid_subexp(const T
* aExpr
, T aStop1
, T aStop2
) {
53 int nsc
= 0; /* Number of special characters */
54 int np
; /* Number of pipe characters in union */
55 int tld
= 0; /* Number of tilde characters */
57 for (x
= 0; aExpr
[x
] && (aExpr
[x
] != aStop1
) && (aExpr
[x
] != aStop2
); ++x
) {
60 if (tld
) { /* at most one exclusion */
63 if (aStop1
) { /* no exclusions within unions */
66 if (!aExpr
[x
+ 1]) { /* exclusion cannot be last character */
69 if (!x
) { /* exclusion cannot be first character */
81 if ((!aExpr
[++x
]) || (aExpr
[x
] == ']')) {
84 for (; aExpr
[x
] && (aExpr
[x
] != ']'); ++x
) {
85 if (aExpr
[x
] == '\\' && !aExpr
[++x
]) {
95 if (aStop1
) { /* no nested unions */
100 int t
= ::_valid_subexp(&aExpr
[++x
], T(')'), T('|'));
101 if (t
== 0 || t
== INVALID_SXP
) {
109 } while (aExpr
[x
] == '|');
110 if (np
< 1) { /* must be at least one pipe */
128 if (!aStop1
&& !nsc
) { /* must be at least one special character */
131 return ((aExpr
[x
] == aStop1
|| aExpr
[x
] == aStop2
) ? x
: INVALID_SXP
);
135 int NS_WildCardValid_(const T
* aExpr
) {
136 int x
= ::_valid_subexp(aExpr
, T('\0'), T('\0'));
137 return (x
< 0 ? x
: VALID_SXP
);
140 int NS_WildCardValid(const char* aExpr
) { return NS_WildCardValid_(aExpr
); }
142 int NS_WildCardValid(const char16_t
* aExpr
) { return NS_WildCardValid_(aExpr
); }
144 /* ----------------------------- _shexp_match ----------------------------- */
151 static int _shexp_match(const T
* aStr
, const T
* aExpr
, bool aCaseInsensitive
,
152 unsigned int aLevel
);
155 * Count characters until we reach a NUL character or either of the
156 * two delimiter characters, stop1 or stop2. If we encounter a bracketed
157 * expression, look only for NUL or ']' inside it. Do not look for stop1
158 * or stop2 inside it. Return ABORTED if bracketed expression is unterminated.
159 * Handle all escaping.
160 * Return index in input string of first stop found, or ABORTED if not found.
161 * If "dest" is non-nullptr, copy counted characters to it and null terminate.
164 static int _scan_and_copy(const T
* aExpr
, T aStop1
, T aStop2
, T
* aDest
) {
165 int sx
; /* source index */
168 for (sx
= 0; (cc
= aExpr
[sx
]) && cc
!= aStop1
&& cc
!= aStop2
; ++sx
) {
171 return ABORTED
; /* should be impossible */
173 } else if (cc
== '[') {
174 while ((cc
= aExpr
[++sx
]) && cc
!= ']') {
175 if (cc
== '\\' && !aExpr
[++sx
]) {
180 return ABORTED
; /* should be impossible */
185 /* Copy all but the closing delimiter. */
186 memcpy(aDest
, aExpr
, sx
* sizeof(T
));
189 return cc
? sx
: ABORTED
; /* index of closing delimiter */
192 /* On input, expr[0] is the opening parenthesis of a union.
193 * See if any of the alternatives in the union matches as a pattern.
194 * The strategy is to take each of the alternatives, in turn, and append
195 * the rest of the expression (after the closing ')' that marks the end of
196 * this union) to that alternative, and then see if the resultant expression
197 * matches the input string. Repeat this until some alternative matches,
198 * or we have an abort.
201 static int _handle_union(const T
* aStr
, const T
* aExpr
, bool aCaseInsensitive
,
202 unsigned int aLevel
) {
203 int sx
; /* source index */
204 int cp
; /* source index of closing parenthesis */
209 /* Find the closing parenthesis that ends this union in the expression */
210 cp
= ::_scan_and_copy(aExpr
, T(')'), T('\0'), static_cast<T
*>(nullptr));
211 if (cp
== ABORTED
|| cp
< 4) { /* must be at least "(a|b" before ')' */
214 ++cp
; /* now index of char after closing parenthesis */
215 e2
= (T
*)moz_xmalloc((1 + nsCharTraits
<T
>::length(aExpr
)) * sizeof(T
));
216 for (sx
= 1;; ++sx
) {
217 /* Here, aExpr[sx] is one character past the preceding '(' or '|'. */
218 /* Copy everything up to the next delimiter to e2 */
219 count
= ::_scan_and_copy(aExpr
+ sx
, T(')'), T('|'), e2
);
220 if (count
== ABORTED
|| !count
) {
225 /* Append everything after closing parenthesis to e2. This is safe. */
226 nsCharTraits
<T
>::copy(e2
+ count
, aExpr
+ cp
,
227 nsCharTraits
<T
>::length(aExpr
+ cp
) + 1);
228 ret
= ::_shexp_match(aStr
, e2
, aCaseInsensitive
, aLevel
+ 1);
229 if (ret
!= NOMATCH
|| !aExpr
[sx
] || aExpr
[sx
] == ')') {
240 /* returns 1 if val is in range from start..end, case insensitive. */
241 static int _is_char_in_range(unsigned char aStart
, unsigned char aEnd
,
242 unsigned char aVal
) {
244 memset(map
, 0, sizeof(map
));
245 while (aStart
<= aEnd
) {
246 map
[lower(aStart
++)] = 1;
248 return map
[lower(aVal
)];
252 static int _shexp_match(const T
* aStr
, const T
* aExpr
, bool aCaseInsensitive
,
253 unsigned int aLevel
) {
254 int x
; /* input string index */
255 int y
; /* expression index */
258 if (aLevel
> 20) { /* Don't let the stack get too deep. */
261 for (x
= 0, y
= 0; aExpr
[y
]; ++y
, ++x
) {
262 if (!aStr
[x
] && aExpr
[y
] != '$' && aExpr
[y
] != '*') {
270 --x
; /* we don't want loop to increment x */
273 while (aExpr
[++y
] == '*') {
279 ret
= ::_shexp_match(&aStr
[x
++], &aExpr
[y
], aCaseInsensitive
,
290 if (aExpr
[y
] == '$' && aExpr
[y
+ 1] == '\0' && !aStr
[x
]) {
299 neg
= (aExpr
[y
] == '^' && aExpr
[y
+ 1] != ']');
308 if (::alphanumeric(start
) && aExpr
[i
++] == '-') {
314 if (::alphanumeric(end
) && aExpr
[i
] == ']') {
315 /* This is a range form: a-b */
317 if (end
< start
) { /* swap them */
322 if (aCaseInsensitive
&& ::alpha(val
)) {
323 val
= ::_is_char_in_range((unsigned char)start
, (unsigned char)end
,
328 } else if (neg
!= (val
< start
|| val
> end
)) {
335 for (; aExpr
[y
] != ']'; ++y
) {
336 if (aExpr
[y
] == '\\') {
339 if (aCaseInsensitive
) {
340 matched
|= (::upper(aStr
[x
]) == ::upper(aExpr
[y
]));
342 matched
|= (aStr
[x
] == aExpr
[y
]);
345 if (neg
== matched
) {
354 return ::_handle_union(&aStr
[x
], &aExpr
[y
], aCaseInsensitive
,
366 if (aCaseInsensitive
) {
367 if (::upper(aStr
[x
]) != ::upper(aExpr
[y
])) {
371 if (aStr
[x
] != aExpr
[y
]) {
378 return (aStr
[x
] ? NOMATCH
: MATCH
);
382 static int ns_WildCardMatch(const T
* aStr
, const T
* aXp
,
383 bool aCaseInsensitive
) {
387 if (!nsCharTraits
<T
>::find(aXp
, nsCharTraits
<T
>::length(aXp
), T('~'))) {
388 return ::_shexp_match(aStr
, aXp
, aCaseInsensitive
, 0);
391 expr
= (T
*)moz_xmalloc((nsCharTraits
<T
>::length(aXp
) + 1) * sizeof(T
));
392 memcpy(expr
, aXp
, (nsCharTraits
<T
>::length(aXp
) + 1) * sizeof(T
));
394 int x
= ::_scan_and_copy(expr
, T('~'), T('\0'), static_cast<T
*>(nullptr));
395 if (x
!= ABORTED
&& expr
[x
] == '~') {
397 ret
= ::_shexp_match(aStr
, &expr
[x
], aCaseInsensitive
, 0);
410 ret
= ::_shexp_match(aStr
, expr
, aCaseInsensitive
, 0);
418 int NS_WildCardMatch_(const T
* aStr
, const T
* aExpr
, bool aCaseInsensitive
) {
419 int is_valid
= NS_WildCardValid(aExpr
);
424 return ::ns_WildCardMatch(aStr
, aExpr
, aCaseInsensitive
);
428 int NS_WildCardMatch(const char* aStr
, const char* aXp
, bool aCaseInsensitive
) {
429 return NS_WildCardMatch_(aStr
, aXp
, aCaseInsensitive
);
432 int NS_WildCardMatch(const char16_t
* aStr
, const char16_t
* aXp
,
433 bool aCaseInsensitive
) {
434 return NS_WildCardMatch_(aStr
, aXp
, aCaseInsensitive
);