blob: 8ea29141bd7c5233a25c89aa55ceeafcf7e7529d [file] [log] [blame]
Nguyễn Thái Ngọc Duy5230f602012-10-15 13:25:52 +07001/*
2** Do shell-style pattern matching for ?, \, [], and * characters.
3** It is 8bit clean.
4**
5** Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
6** Rich $alz is now <rsalz@bbn.com>.
7**
8** Modified by Wayne Davison to special-case '/' matching, to make '**'
9** work differently than '*', and to fix the character-class code.
10*/
11
Elijah Newrenb73ecb42023-02-24 00:09:26 +000012#include "git-compat-util.h"
Nguyễn Thái Ngọc Duyfeabcc12012-10-15 13:25:55 +070013#include "wildmatch.h"
14
15typedef unsigned char uchar;
Nguyễn Thái Ngọc Duy5230f602012-10-15 13:25:52 +070016
Phillip Wood91b81b62023-03-20 16:10:02 +000017/* Internal return values */
18#define WM_ABORT_ALL -1
19#define WM_ABORT_TO_STARSTAR -2
20
Nguyễn Thái Ngọc Duy5230f602012-10-15 13:25:52 +070021/* What character marks an inverted character class? */
22#define NEGATE_CLASS '!'
23#define NEGATE_CLASS2 '^'
24
Nguyễn Thái Ngọc Duy5230f602012-10-15 13:25:52 +070025#define CC_EQ(class, len, litmatch) ((len) == sizeof (litmatch)-1 \
26 && *(class) == *(litmatch) \
27 && strncmp((char*)class, litmatch, len) == 0)
28
29#if defined STDC_HEADERS || !defined isascii
30# define ISASCII(c) 1
31#else
32# define ISASCII(c) isascii(c)
33#endif
34
35#ifdef isblank
36# define ISBLANK(c) (ISASCII(c) && isblank(c))
37#else
38# define ISBLANK(c) ((c) == ' ' || (c) == '\t')
39#endif
40
41#ifdef isgraph
42# define ISGRAPH(c) (ISASCII(c) && isgraph(c))
43#else
44# define ISGRAPH(c) (ISASCII(c) && isprint(c) && !isspace(c))
45#endif
46
47#define ISPRINT(c) (ISASCII(c) && isprint(c))
48#define ISDIGIT(c) (ISASCII(c) && isdigit(c))
49#define ISALNUM(c) (ISASCII(c) && isalnum(c))
50#define ISALPHA(c) (ISASCII(c) && isalpha(c))
51#define ISCNTRL(c) (ISASCII(c) && iscntrl(c))
52#define ISLOWER(c) (ISASCII(c) && islower(c))
53#define ISPUNCT(c) (ISASCII(c) && ispunct(c))
54#define ISSPACE(c) (ISASCII(c) && isspace(c))
55#define ISUPPER(c) (ISASCII(c) && isupper(c))
56#define ISXDIGIT(c) (ISASCII(c) && isxdigit(c))
57
Nguyễn Thái Ngọc Duyb0e02872012-10-15 13:25:53 +070058/* Match pattern "p" against "text" */
Nguyễn Thái Ngọc Duy0c528162013-01-01 09:44:06 +070059static int dowild(const uchar *p, const uchar *text, unsigned int flags)
Nguyễn Thái Ngọc Duy5230f602012-10-15 13:25:52 +070060{
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +070061 uchar p_ch;
Nguyễn Thái Ngọc Duy3a078de2013-01-01 09:44:02 +070062 const uchar *pattern = p;
Nguyễn Thái Ngọc Duy5230f602012-10-15 13:25:52 +070063
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +070064 for ( ; (p_ch = *p) != '\0'; text++, p++) {
Nguyễn Thái Ngọc Duyb6a3d332013-01-01 09:44:04 +070065 int matched, match_slash, negated;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +070066 uchar t_ch, prev_ch;
67 if ((t_ch = *text) == '\0' && p_ch != '*')
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +070068 return WM_ABORT_ALL;
Nguyễn Thái Ngọc Duy0c528162013-01-01 09:44:06 +070069 if ((flags & WM_CASEFOLD) && ISUPPER(t_ch))
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +070070 t_ch = tolower(t_ch);
Nguyễn Thái Ngọc Duy0c528162013-01-01 09:44:06 +070071 if ((flags & WM_CASEFOLD) && ISUPPER(p_ch))
Nguyễn Thái Ngọc Duy164bf832012-10-15 13:25:59 +070072 p_ch = tolower(p_ch);
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +070073 switch (p_ch) {
74 case '\\':
75 /* Literal match with following character. Note that the test
76 * in "default" handles the p[1] == '\0' failure case. */
Nguyễn Thái Ngọc Duy5230f602012-10-15 13:25:52 +070077 p_ch = *++p;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +070078 /* FALLTHROUGH */
79 default:
80 if (t_ch != p_ch)
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +070081 return WM_NOMATCH;
Nguyễn Thái Ngọc Duy5230f602012-10-15 13:25:52 +070082 continue;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +070083 case '?':
84 /* Match anything but '/'. */
Nguyễn Thái Ngọc Duyc41244e2013-01-01 09:44:07 +070085 if ((flags & WM_PATHNAME) && t_ch == '/')
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +070086 return WM_NOMATCH;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +070087 continue;
88 case '*':
89 if (*++p == '*') {
Phillip Wood81b26f82023-03-20 16:10:01 +000090 const uchar *prev_p = p;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +070091 while (*++p == '*') {}
Nguyễn Thái Ngọc Duyc41244e2013-01-01 09:44:07 +070092 if (!(flags & WM_PATHNAME))
93 /* without WM_PATHNAME, '*' == '**' */
94 match_slash = 1;
Phillip Wood81b26f82023-03-20 16:10:01 +000095 else if ((prev_p - pattern < 2 || *(prev_p - 2) == '/') &&
Nguyễn Thái Ngọc Duy40bbee02012-10-15 13:26:00 +070096 (*p == '\0' || *p == '/' ||
97 (p[0] == '\\' && p[1] == '/'))) {
Nguyễn Thái Ngọc Duy4c251e52012-10-15 13:26:01 +070098 /*
99 * Assuming we already match 'foo/' and are at
100 * <star star slash>, just assume it matches
101 * nothing and go ahead match the rest of the
102 * pattern with the remaining string. This
103 * helps make foo/<*><*>/bar (<> because
104 * otherwise it breaks C comment syntax) match
105 * both foo/bar and foo/a/bar.
106 */
107 if (p[0] == '/' &&
Nguyễn Thái Ngọc Duy0c528162013-01-01 09:44:06 +0700108 dowild(p + 1, text, flags) == WM_MATCH)
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700109 return WM_MATCH;
110 match_slash = 1;
Nguyễn Thái Ngọc Duye5bbe092018-10-27 10:48:23 +0200111 } else /* WM_PATHNAME is set */
112 match_slash = 0;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700113 } else
Nguyễn Thái Ngọc Duyc41244e2013-01-01 09:44:07 +0700114 /* without WM_PATHNAME, '*' == '**' */
115 match_slash = flags & WM_PATHNAME ? 0 : 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700116 if (*p == '\0') {
117 /* Trailing "**" matches everything. Trailing "*" matches
118 * only if there are no more slash characters. */
Nguyễn Thái Ngọc Duyb6a3d332013-01-01 09:44:04 +0700119 if (!match_slash) {
Junio C Hamanoafe8a902022-05-02 09:50:37 -0700120 if (strchr((char *)text, '/'))
Phillip Wood1f2e05f2023-03-20 16:10:00 +0000121 return WM_ABORT_TO_STARSTAR;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700122 }
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700123 return WM_MATCH;
Nguyễn Thái Ngọc Duy46983442013-01-01 09:44:09 +0700124 } else if (!match_slash && *p == '/') {
125 /*
126 * _one_ asterisk followed by a slash
127 * with WM_PATHNAME matches the next
128 * directory
129 */
130 const char *slash = strchr((char*)text, '/');
131 if (!slash)
Phillip Wood1f2e05f2023-03-20 16:10:00 +0000132 return WM_ABORT_ALL;
Nguyễn Thái Ngọc Duy46983442013-01-01 09:44:09 +0700133 text = (const uchar*)slash;
134 /* the slash is consumed by the top-level for loop */
135 break;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700136 }
137 while (1) {
138 if (t_ch == '\0')
139 break;
Nguyễn Thái Ngọc Duy6f1a31f2013-01-01 09:44:10 +0700140 /*
141 * Try to advance faster when an asterisk is
142 * followed by a literal. We know in this case
Li Peng832c0e52016-05-06 20:36:46 +0800143 * that the string before the literal
Nguyễn Thái Ngọc Duy6f1a31f2013-01-01 09:44:10 +0700144 * must belong to "*".
145 * If match_slash is false, do not look past
146 * the first slash as it cannot belong to '*'.
147 */
148 if (!is_glob_special(*p)) {
149 p_ch = *p;
150 if ((flags & WM_CASEFOLD) && ISUPPER(p_ch))
151 p_ch = tolower(p_ch);
152 while ((t_ch = *text) != '\0' &&
153 (match_slash || t_ch != '/')) {
154 if ((flags & WM_CASEFOLD) && ISUPPER(t_ch))
155 t_ch = tolower(t_ch);
156 if (t_ch == p_ch)
157 break;
158 text++;
159 }
Phillip Wood1f2e05f2023-03-20 16:10:00 +0000160 if (t_ch != p_ch) {
161 if (match_slash)
162 return WM_ABORT_ALL;
163 else
164 return WM_ABORT_TO_STARSTAR;
165 }
Nguyễn Thái Ngọc Duy6f1a31f2013-01-01 09:44:10 +0700166 }
Nguyễn Thái Ngọc Duy0c528162013-01-01 09:44:06 +0700167 if ((matched = dowild(p, text, flags)) != WM_NOMATCH) {
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700168 if (!match_slash || matched != WM_ABORT_TO_STARSTAR)
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700169 return matched;
Nguyễn Thái Ngọc Duyb6a3d332013-01-01 09:44:04 +0700170 } else if (!match_slash && t_ch == '/')
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700171 return WM_ABORT_TO_STARSTAR;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700172 t_ch = *++text;
173 }
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700174 return WM_ABORT_ALL;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700175 case '[':
176 p_ch = *++p;
177#ifdef NEGATE_CLASS2
178 if (p_ch == NEGATE_CLASS2)
179 p_ch = NEGATE_CLASS;
180#endif
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700181 /* Assign literal 1/0 because of "matched" comparison. */
182 negated = p_ch == NEGATE_CLASS ? 1 : 0;
Nguyễn Thái Ngọc Duyb6a3d332013-01-01 09:44:04 +0700183 if (negated) {
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700184 /* Inverted character class. */
185 p_ch = *++p;
186 }
187 prev_ch = 0;
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700188 matched = 0;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700189 do {
190 if (!p_ch)
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700191 return WM_ABORT_ALL;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700192 if (p_ch == '\\') {
193 p_ch = *++p;
194 if (!p_ch)
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700195 return WM_ABORT_ALL;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700196 if (t_ch == p_ch)
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700197 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700198 } else if (p_ch == '-' && prev_ch && p[1] && p[1] != ']') {
199 p_ch = *++p;
200 if (p_ch == '\\') {
201 p_ch = *++p;
202 if (!p_ch)
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700203 return WM_ABORT_ALL;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700204 }
205 if (t_ch <= p_ch && t_ch >= prev_ch)
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700206 matched = 1;
Anthony Ramineb79c0c32013-05-30 12:19:10 +0200207 else if ((flags & WM_CASEFOLD) && ISLOWER(t_ch)) {
208 uchar t_ch_upper = toupper(t_ch);
209 if (t_ch_upper <= p_ch && t_ch_upper >= prev_ch)
210 matched = 1;
211 }
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700212 p_ch = 0; /* This makes "prev_ch" get set to 0. */
213 } else if (p_ch == '[' && p[1] == ':') {
214 const uchar *s;
215 int i;
216 for (s = p += 2; (p_ch = *p) && p_ch != ']'; p++) {} /*SHARED ITERATOR*/
217 if (!p_ch)
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700218 return WM_ABORT_ALL;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700219 i = p - s - 1;
220 if (i < 0 || p[-1] != ':') {
221 /* Didn't find ":]", so treat like a normal set. */
222 p = s - 2;
223 p_ch = '[';
224 if (t_ch == p_ch)
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700225 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700226 continue;
227 }
228 if (CC_EQ(s,i, "alnum")) {
229 if (ISALNUM(t_ch))
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700230 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700231 } else if (CC_EQ(s,i, "alpha")) {
232 if (ISALPHA(t_ch))
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700233 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700234 } else if (CC_EQ(s,i, "blank")) {
235 if (ISBLANK(t_ch))
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700236 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700237 } else if (CC_EQ(s,i, "cntrl")) {
238 if (ISCNTRL(t_ch))
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700239 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700240 } else if (CC_EQ(s,i, "digit")) {
241 if (ISDIGIT(t_ch))
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700242 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700243 } else if (CC_EQ(s,i, "graph")) {
244 if (ISGRAPH(t_ch))
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700245 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700246 } else if (CC_EQ(s,i, "lower")) {
247 if (ISLOWER(t_ch))
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700248 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700249 } else if (CC_EQ(s,i, "print")) {
250 if (ISPRINT(t_ch))
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700251 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700252 } else if (CC_EQ(s,i, "punct")) {
253 if (ISPUNCT(t_ch))
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700254 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700255 } else if (CC_EQ(s,i, "space")) {
256 if (ISSPACE(t_ch))
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700257 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700258 } else if (CC_EQ(s,i, "upper")) {
259 if (ISUPPER(t_ch))
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700260 matched = 1;
Anthony Ramineb79c0c32013-05-30 12:19:10 +0200261 else if ((flags & WM_CASEFOLD) && ISLOWER(t_ch))
262 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700263 } else if (CC_EQ(s,i, "xdigit")) {
264 if (ISXDIGIT(t_ch))
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700265 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700266 } else /* malformed [:class:] string */
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700267 return WM_ABORT_ALL;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700268 p_ch = 0; /* This makes "prev_ch" get set to 0. */
269 } else if (t_ch == p_ch)
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700270 matched = 1;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700271 } while (prev_ch = p_ch, (p_ch = *++p) != ']');
Nguyễn Thái Ngọc Duyc41244e2013-01-01 09:44:07 +0700272 if (matched == negated ||
273 ((flags & WM_PATHNAME) && t_ch == '/'))
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700274 return WM_NOMATCH;
Nguyễn Thái Ngọc Duy327f2f32012-10-15 13:25:54 +0700275 continue;
276 }
Nguyễn Thái Ngọc Duy5230f602012-10-15 13:25:52 +0700277 }
Nguyễn Thái Ngọc Duy5230f602012-10-15 13:25:52 +0700278
Nguyễn Thái Ngọc Duy9b3497c2013-01-01 09:44:05 +0700279 return *text ? WM_NOMATCH : WM_MATCH;
Nguyễn Thái Ngọc Duy5230f602012-10-15 13:25:52 +0700280}
281
282/* Match the "pattern" against the "text" string. */
Ævar Arnfjörð Bjarmason55d34262017-06-22 21:38:08 +0000283int wildmatch(const char *pattern, const char *text, unsigned int flags)
Nguyễn Thái Ngọc Duy5230f602012-10-15 13:25:52 +0700284{
Phillip Wood91b81b62023-03-20 16:10:02 +0000285 int res = dowild((const uchar*)pattern, (const uchar*)text, flags);
286 return res == WM_MATCH ? WM_MATCH : WM_NOMATCH;
Nguyễn Thái Ngọc Duy5230f602012-10-15 13:25:52 +0700287}