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