?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Git 2.44
[git.git] / wildmatch.c
blob8ea29141bd7c5233a25c89aa55ceeafcf7e7529d
1 /*
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
12 #include "git-compat-util.h"
13 #include "wildmatch.h"
14
15 typedef unsigned char uchar;
16
17 /* Internal return values */
18 #define WM_ABORT_ALL -1
19 #define WM_ABORT_TO_STARSTAR -2
20
21 /* What character marks an inverted character class? */
22 #define NEGATE_CLASS '!'
23 #define NEGATE_CLASS2 '^'
24
25 #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
58 /* Match pattern "p" against "text" */
59 static int dowild(const uchar *p, const uchar *text, unsigned int flags)
60 {
61 uchar p_ch;
62 const uchar *pattern = p;
63
64 for ( ; (p_ch = *p) != '\0'; text++, p++) {
65 int matched, match_slash, negated;
66 uchar t_ch, prev_ch;
67 if ((t_ch = *text) == '\0' && p_ch != '*')
68 return WM_ABORT_ALL;
69 if ((flags & WM_CASEFOLD) && ISUPPER(t_ch))
70 t_ch = tolower(t_ch);
71 if ((flags & WM_CASEFOLD) && ISUPPER(p_ch))
72 p_ch = tolower(p_ch);
73 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. */
77 p_ch = *++p;
78 /* FALLTHROUGH */
79 default:
80 if (t_ch != p_ch)
81 return WM_NOMATCH;
82 continue;
83 case '?':
84 /* Match anything but '/'. */
85 if ((flags & WM_PATHNAME) && t_ch == '/')
86 return WM_NOMATCH;
87 continue;
88 case '*':
89 if (*++p == '*') {
90 const uchar *prev_p = p;
91 while (*++p == '*') {}
92 if (!(flags & WM_PATHNAME))
93 /* without WM_PATHNAME, '*' == '**' */
94 match_slash = 1;
95 else if ((prev_p - pattern < 2 || *(prev_p - 2) == '/') &&
96 (*p == '\0' || *p == '/' ||
97 (p[0] == '\\' && p[1] == '/'))) {
98 /*
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] == '/' &&
108 dowild(p + 1, text, flags) == WM_MATCH)
109 return WM_MATCH;
110 match_slash = 1;
111 } else /* WM_PATHNAME is set */
112 match_slash = 0;
113 } else
114 /* without WM_PATHNAME, '*' == '**' */
115 match_slash = flags & WM_PATHNAME ? 0 : 1;
116 if (*p == '\0') {
117 /* Trailing "**" matches everything. Trailing "*" matches
118 * only if there are no more slash characters. */
119 if (!match_slash) {
120 if (strchr((char *)text, '/'))
121 return WM_ABORT_TO_STARSTAR;
122 }
123 return WM_MATCH;
124 } 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)
132 return WM_ABORT_ALL;
133 text = (const uchar*)slash;
134 /* the slash is consumed by the top-level for loop */
135 break;
136 }
137 while (1) {
138 if (t_ch == '\0')
139 break;
140 /*
141 * Try to advance faster when an asterisk is
142 * followed by a literal. We know in this case
143 * that the string before the literal
144 * 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 }
160 if (t_ch != p_ch) {
161 if (match_slash)
162 return WM_ABORT_ALL;
163 else
164 return WM_ABORT_TO_STARSTAR;
165 }
166 }
167 if ((matched = dowild(p, text, flags)) != WM_NOMATCH) {
168 if (!match_slash || matched != WM_ABORT_TO_STARSTAR)
169 return matched;
170 } else if (!match_slash && t_ch == '/')
171 return WM_ABORT_TO_STARSTAR;
172 t_ch = *++text;
173 }
174 return WM_ABORT_ALL;
175 case '[':
176 p_ch = *++p;
177 #ifdef NEGATE_CLASS2
178 if (p_ch == NEGATE_CLASS2)
179 p_ch = NEGATE_CLASS;
180 #endif
181 /* Assign literal 1/0 because of "matched" comparison. */
182 negated = p_ch == NEGATE_CLASS ? 1 : 0;
183 if (negated) {
184 /* Inverted character class. */
185 p_ch = *++p;
186 }
187 prev_ch = 0;
188 matched = 0;
189 do {
190 if (!p_ch)
191 return WM_ABORT_ALL;
192 if (p_ch == '\\') {
193 p_ch = *++p;
194 if (!p_ch)
195 return WM_ABORT_ALL;
196 if (t_ch == p_ch)
197 matched = 1;
198 } 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)
203 return WM_ABORT_ALL;
204 }
205 if (t_ch <= p_ch && t_ch >= prev_ch)
206 matched = 1;
207 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 }
212 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)
218 return WM_ABORT_ALL;
219 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)
225 matched = 1;
226 continue;
227 }
228 if (CC_EQ(s,i, "alnum")) {
229 if (ISALNUM(t_ch))
230 matched = 1;
231 } else if (CC_EQ(s,i, "alpha")) {
232 if (ISALPHA(t_ch))
233 matched = 1;
234 } else if (CC_EQ(s,i, "blank")) {
235 if (ISBLANK(t_ch))
236 matched = 1;
237 } else if (CC_EQ(s,i, "cntrl")) {
238 if (ISCNTRL(t_ch))
239 matched = 1;
240 } else if (CC_EQ(s,i, "digit")) {
241 if (ISDIGIT(t_ch))
242 matched = 1;
243 } else if (CC_EQ(s,i, "graph")) {
244 if (ISGRAPH(t_ch))
245 matched = 1;
246 } else if (CC_EQ(s,i, "lower")) {
247 if (ISLOWER(t_ch))
248 matched = 1;
249 } else if (CC_EQ(s,i, "print")) {
250 if (ISPRINT(t_ch))
251 matched = 1;
252 } else if (CC_EQ(s,i, "punct")) {
253 if (ISPUNCT(t_ch))
254 matched = 1;
255 } else if (CC_EQ(s,i, "space")) {
256 if (ISSPACE(t_ch))
257 matched = 1;
258 } else if (CC_EQ(s,i, "upper")) {
259 if (ISUPPER(t_ch))
260 matched = 1;
261 else if ((flags & WM_CASEFOLD) && ISLOWER(t_ch))
262 matched = 1;
263 } else if (CC_EQ(s,i, "xdigit")) {
264 if (ISXDIGIT(t_ch))
265 matched = 1;
266 } else /* malformed [:class:] string */
267 return WM_ABORT_ALL;
268 p_ch = 0; /* This makes "prev_ch" get set to 0. */
269 } else if (t_ch == p_ch)
270 matched = 1;
271 } while (prev_ch = p_ch, (p_ch = *++p) != ']');
272 if (matched == negated ||
273 ((flags & WM_PATHNAME) && t_ch == '/'))
274 return WM_NOMATCH;
275 continue;
276 }
277 }
278
279 return *text ? WM_NOMATCH : WM_MATCH;
280 }
281
282 /* Match the "pattern" against the "text" string. */
283 int wildmatch(const char *pattern, const char *text, unsigned int flags)
284 {
285 int res = dowild((const uchar*)pattern, (const uchar*)text, flags);
286 return res == WM_MATCH ? WM_MATCH : WM_NOMATCH;
287 }
The Best VCS Around