nsz Git - musl/blob - src/regex/fnmatch.c

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