| 1 |
/* |
| 2 |
* An implementation of what I call the "Sea of Stars" algorithm for |
| 3 |
* POSIX fnmatch(). The basic idea is that we factor the pattern into |
| 4 |
* a head component (which we match first and can reject without ever |
| 5 |
* measuring the length of the string), an optional tail component |
| 6 |
* (which only exists if the pattern contains at least one star), and |
| 7 |
* an optional "sea of stars", a set of star-separated components |
| 8 |
* between the head and tail. After the head and tail matches have |
| 9 |
* been removed from the input string, the components in the "sea of |
| 10 |
* stars" are matched sequentially by searching for their first |
| 11 |
* occurrence past the end of the previous match. |
| 12 |
* |
| 13 |
* - Rich Felker, April 2012 |
| 14 |
*/ |
| 15 |
|
| 16 |
#include <string.h> |
| 17 |
#include <fnmatch.h> |
| 18 |
#include <stdlib.h> |
| 19 |
#include <wchar.h> |
| 20 |
#include <wctype.h> |
| 21 |
#include "locale_impl.h" |
| 22 |
|
| 23 |
#define END 0 |
| 24 |
#define UNMATCHABLE -2 |
| 25 |
#define BRACKET -3 |
| 26 |
#define QUESTION -4 |
| 27 |
#define STAR -5 |
| 28 |
|
| 29 |
static int str_next(const char *str, size_t n, size_t *step) |
| 30 |
{ |
| 31 |
if (!n) { |
| 32 |
*step = 0; |
| 33 |
return 0; |
| 34 |
} |
| 35 |
if (str[0] >= 128U) { |
| 36 |
wchar_t wc; |
| 37 |
int k = mbtowc(&wc, str, n); |
| 38 |
if (k<0) { |
| 39 |
*step = 1; |
| 40 |
return -1; |
| 41 |
} |
| 42 |
*step = k; |
| 43 |
return wc; |
| 44 |
} |
| 45 |
*step = 1; |
| 46 |
return str[0]; |
| 47 |
} |
| 48 |
|
| 49 |
static int pat_next(const char *pat, size_t m, size_t *step, int flags) |
| 50 |
{ |
| 51 |
int esc = 0; |
| 52 |
if (!m || !*pat) { |
| 53 |
*step = 0; |
| 54 |
return END; |
| 55 |
} |
| 56 |
*step = 1; |
| 57 |
if (pat[0]=='\\' && pat[1] && !(flags & FNM_NOESCAPE)) { |
| 58 |
*step = 2; |
| 59 |
pat++; |
| 60 |
esc = 1; |
| 61 |
goto escaped; |
| 62 |
} |
| 63 |
if (pat[0]=='[') { |
| 64 |
size_t k = 1; |
| 65 |
if (k<m) if (pat[k] == '^' || pat[k] == '!') k++; |
| 66 |
if (k<m) if (pat[k] == ']') k++; |
| 67 |
for (; k<m && pat[k] && pat[k]!=']'; k++) { |
| 68 |
if (k+1<m && pat[k+1] && pat[k]=='[' && (pat[k+1]==':' || pat[k+1]=='.' || pat[k+1]=='=')) { |
| 69 |
int z = pat[k+1]; |
| 70 |
k+=2; |
| 71 |
if (k<m && pat[k]) k++; |
| 72 |
while (k<m && pat[k] && (pat[k-1]!=z || pat[k]!=']')) k++; |
| 73 |
if (k==m || !pat[k]) break; |
| 74 |
} |
| 75 |
} |
| 76 |
if (k==m || !pat[k]) { |
| 77 |
*step = 1; |
| 78 |
return '['; |
| 79 |
} |
| 80 |
*step = k+1; |
| 81 |
return BRACKET; |
| 82 |
} |
| 83 |
if (pat[0] == '*') |
| 84 |
return STAR; |
| 85 |
if (pat[0] == '?') |
| 86 |
return QUESTION; |
| 87 |
escaped: |
| 88 |
if (pat[0] >= 128U) { |
| 89 |
wchar_t wc; |
| 90 |
int k = mbtowc(&wc, pat, m); |
| 91 |
if (k<0) { |
| 92 |
*step = 0; |
| 93 |
return UNMATCHABLE; |
| 94 |
} |
| 95 |
*step = k + esc; |
| 96 |
return wc; |
| 97 |
} |
| 98 |
return pat[0]; |
| 99 |
} |
| 100 |
|
| 101 |
static int casefold(int k) |
| 102 |
{ |
| 103 |
int c = towupper(k); |
| 104 |
return c == k ? towlower(k) : c; |
| 105 |
} |
| 106 |
|
| 107 |
static int match_bracket(const char *p, int k, int kfold) |
| 108 |
{ |
| 109 |
wchar_t wc; |
| 110 |
int inv = 0; |
| 111 |
p++; |
| 112 |
if (*p=='^' || *p=='!') { |
| 113 |
inv = 1; |
| 114 |
p++; |
| 115 |
} |
| 116 |
if (*p==']') { |
| 117 |
if (k==']') return !inv; |
| 118 |
p++; |
| 119 |
} else if (*p=='-') { |
| 120 |
if (k=='-') return !inv; |
| 121 |
p++; |
| 122 |
} |
| 123 |
wc = p[-1]; |
| 124 |
for (; *p != ']'; p++) { |
| 125 |
if (p[0]=='-' && p[1]!=']') { |
| 126 |
wchar_t wc2; |
| 127 |
int l = mbtowc(&wc2, p+1, 4); |
| 128 |
if (l < 0) return 0; |
| 129 |
if (wc <= wc2) |
| 130 |
if ((unsigned)k-wc <= wc2-wc || |
| 131 |
(unsigned)kfold-wc <= wc2-wc) |
| 132 |
return !inv; |
| 133 |
p += l-1; |
| 134 |
continue; |
| 135 |
} |
| 136 |
if (p[0]=='[' && (p[1]==':' || p[1]=='.' || p[1]=='=')) { |
| 137 |
const char *p0 = p+2; |
| 138 |
int z = p[1]; |
| 139 |
p+=3; |
| 140 |
while (p[-1]!=z || p[0]!=']') p++; |
| 141 |
if (z == ':' && p-1-p0 < 16) { |
| 142 |
char buf[16]; |
| 143 |
memcpy(buf, p0, p-1-p0); |
| 144 |
buf[p-1-p0] = 0; |
| 145 |
if (iswctype(k, wctype(buf)) || |
| 146 |
iswctype(kfold, wctype(buf))) |
| 147 |
return !inv; |
| 148 |
} |
| 149 |
continue; |
| 150 |
} |
| 151 |
if (*p < 128U) { |
| 152 |
wc = (unsigned char)*p; |
| 153 |
} else { |
| 154 |
int l = mbtowc(&wc, p, 4); |
| 155 |
if (l < 0) return 0; |
| 156 |
p += l-1; |
| 157 |
} |
| 158 |
if (wc==k || wc==kfold) return !inv; |
| 159 |
} |
| 160 |
return inv; |
| 161 |
} |
| 162 |
|
| 163 |
static int fnmatch_internal(const char *pat, size_t m, const char *str, size_t n, int flags) |
| 164 |
{ |
| 165 |
const char *p, *ptail, *endpat; |
| 166 |
const char *s, *stail, *endstr; |
| 167 |
size_t pinc, sinc, tailcnt=0; |
| 168 |
int c, k, kfold; |
| 169 |
|
| 170 |
if (flags & FNM_PERIOD) { |
| 171 |
if (*str == '.' && *pat != '.') |
| 172 |
return FNM_NOMATCH; |
| 173 |
} |
| 174 |
for (;;) { |
| 175 |
switch ((c = pat_next(pat, m, &pinc, flags))) { |
| 176 |
case UNMATCHABLE: |
| 177 |
return FNM_NOMATCH; |
| 178 |
case STAR: |
| 179 |
pat++; |
| 180 |
m--; |
| 181 |
break; |
| 182 |
default: |
| 183 |
k = str_next(str, n, &sinc); |
| 184 |
if (k <= 0) |
| 185 |
return (c==END) ? 0 : FNM_NOMATCH; |
| 186 |
str += sinc; |
| 187 |
n -= sinc; |
| 188 |
kfold = flags & FNM_CASEFOLD ? casefold(k) : k; |
| 189 |
if (c == BRACKET) { |
| 190 |
if (!match_bracket(pat, k, kfold)) |
| 191 |
return FNM_NOMATCH; |
| 192 |
} else if (c != QUESTION && k != c && kfold != c) { |
| 193 |
return FNM_NOMATCH; |
| 194 |
} |
| 195 |
pat+=pinc; |
| 196 |
m-=pinc; |
| 197 |
continue; |
| 198 |
} |
| 199 |
break; |
| 200 |
} |
| 201 |
|
| 202 |
/* Compute real pat length if it was initially unknown/-1 */ |
| 203 |
m = strnlen(pat, m); |
| 204 |
endpat = pat + m; |
| 205 |
|
| 206 |
/* Find the last * in pat and count chars needed after it */ |
| 207 |
for (p=ptail=pat; p<endpat; p+=pinc) { |
| 208 |
switch (pat_next(p, endpat-p, &pinc, flags)) { |
| 209 |
case UNMATCHABLE: |
| 210 |
return FNM_NOMATCH; |
| 211 |
case STAR: |
| 212 |
tailcnt=0; |
| 213 |
ptail = p+1; |
| 214 |
break; |
| 215 |
default: |
| 216 |
tailcnt++; |
| 217 |
break; |
| 218 |
} |
| 219 |
} |
| 220 |
|
| 221 |
/* Past this point we need not check for UNMATCHABLE in pat, |
| 222 |
* because all of pat has already been parsed once. */ |
| 223 |
|
| 224 |
/* Compute real str length if it was initially unknown/-1 */ |
| 225 |
n = strnlen(str, n); |
| 226 |
endstr = str + n; |
| 227 |
if (n < tailcnt) return FNM_NOMATCH; |
| 228 |
|
| 229 |
/* Find the final tailcnt chars of str, accounting for UTF-8. |
| 230 |
* On illegal sequences we may get it wrong, but in that case |
| 231 |
* we necessarily have a matching failure anyway. */ |
| 232 |
for (s=endstr; s>str && tailcnt; tailcnt--) { |
| 233 |
if (s[-1] < 128U || MB_CUR_MAX==1) s--; |
| 234 |
else while ((unsigned char)*--s-0x80U<0x40 && s>str); |
| 235 |
} |
| 236 |
if (tailcnt) return FNM_NOMATCH; |
| 237 |
stail = s; |
| 238 |
|
| 239 |
/* Check that the pat and str tails match */ |
| 240 |
p = ptail; |
| 241 |
for (;;) { |
| 242 |
c = pat_next(p, endpat-p, &pinc, flags); |
| 243 |
p += pinc; |
| 244 |
if ((k = str_next(s, endstr-s, &sinc)) <= 0) { |
| 245 |
if (c != END) return FNM_NOMATCH; |
| 246 |
break; |
| 247 |
} |
| 248 |
s += sinc; |
| 249 |
kfold = flags & FNM_CASEFOLD ? casefold(k) : k; |
| 250 |
if (c == BRACKET) { |
| 251 |
if (!match_bracket(p-pinc, k, kfold)) |
| 252 |
return FNM_NOMATCH; |
| 253 |
} else if (c != QUESTION && k != c && kfold != c) { |
| 254 |
return FNM_NOMATCH; |
| 255 |
} |
| 256 |
} |
| 257 |
|
| 258 |
/* We're all done with the tails now, so throw them out */ |
| 259 |
endstr = stail; |
| 260 |
endpat = ptail; |
| 261 |
|
| 262 |
/* Match pattern components until there are none left */ |
| 263 |
while (pat<endpat) { |
| 264 |
p = pat; |
| 265 |
s = str; |
| 266 |
for (;;) { |
| 267 |
c = pat_next(p, endpat-p, &pinc, flags); |
| 268 |
p += pinc; |
| 269 |
/* Encountering * completes/commits a component */ |
| 270 |
if (c == STAR) { |
| 271 |
pat = p; |
| 272 |
str = s; |
| 273 |
break; |
| 274 |
} |
| 275 |
k = str_next(s, endstr-s, &sinc); |
| 276 |
if (!k) |
| 277 |
return FNM_NOMATCH; |
| 278 |
kfold = flags & FNM_CASEFOLD ? casefold(k) : k; |
| 279 |
if (c == BRACKET) { |
| 280 |
if (!match_bracket(p-pinc, k, kfold)) |
| 281 |
break; |
| 282 |
} else if (c != QUESTION && k != c && kfold != c) { |
| 283 |
break; |
| 284 |
} |
| 285 |
s += sinc; |
| 286 |
} |
| 287 |
if (c == STAR) continue; |
| 288 |
/* If we failed, advance str, by 1 char if it's a valid |
| 289 |
* char, or past all invalid bytes otherwise. */ |
| 290 |
k = str_next(str, endstr-str, &sinc); |
| 291 |
if (k > 0) str += sinc; |
| 292 |
else for (str++; str_next(str, endstr-str, &sinc)<0; str++); |
| 293 |
} |
| 294 |
|
| 295 |
return 0; |
| 296 |
} |
| 297 |
|
| 298 |
int fnmatch(const char *pat, const char *str, int flags) |
| 299 |
{ |
| 300 |
const char *s, *p; |
| 301 |
size_t inc; |
| 302 |
int c; |
| 303 |
if (flags & FNM_PATHNAME) for (;;) { |
| 304 |
for (s=str; *s && *s!='/'; s++); |
| 305 |
for (p=pat; (c=pat_next(p, -1, &inc, flags))!=END && c!='/'; p+=inc); |
| 306 |
if (c!=*s && (!*s || !(flags & FNM_LEADING_DIR))) |
| 307 |
return FNM_NOMATCH; |
| 308 |
if (fnmatch_internal(pat, p-pat, str, s-str, flags)) |
| 309 |
return FNM_NOMATCH; |
| 310 |
if (!c) return 0; |
| 311 |
str = s+1; |
| 312 |
pat = p+inc; |
| 313 |
} else if (flags & FNM_LEADING_DIR) { |
| 314 |
for (s=str; *s; s++) { |
| 315 |
if (*s != '/') continue; |
| 316 |
if (!fnmatch_internal(pat, -1, str, s-str, flags)) |
| 317 |
return 0; |
| 318 |
} |
| 319 |
} |
| 320 |
return fnmatch_internal(pat, -1, str, -1, flags); |
| 321 |
} |