git

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
}
288