misc/fnmatch.c

   1 /* Copyright (C) 1991-1993, 1996-1999, 2000 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3
   4    This library is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU Library General Public License as
   6    published by the Free Software Foundation; either version 2 of the
   7    License, or (at your option) any later version.
   8
   9    This library is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    Library General Public License for more details.
  13
  14    You should have received a copy of the GNU Library General Public
  15    License along with this library; see the file COPYING.LIB.  If not,
  16    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17    Boston, MA 02111-1307, USA.  */
  18
  19 # include "system.h"
  20 # include <stdlib.h>
  21
  22 /* Find the first occurrence of C in S or the final NUL byte.  */
  23 static inline char *
  24 __strchrnul (const char *s, int c)
  25 {
  26   const unsigned char *char_ptr;
  27   const unsigned long int *longword_ptr;
  28   unsigned long int longword, magic_bits, charmask;
  29
  30   c = (unsigned char) c;
  31
  32   /* Handle the first few characters by reading one character at a time.
  33      Do this until CHAR_PTR is aligned on a longword boundary.  */
  34   for (char_ptr = (const unsigned char *)s; ((unsigned long int) char_ptr
  35                       & (sizeof (longword) - 1)) != 0;
  36        ++char_ptr)
  37     if (*char_ptr == c || *char_ptr == '\0')
  38       return (void *) char_ptr;
  39
  40   /* All these elucidatory comments refer to 4-byte longwords,
  41      but the theory applies equally well to 8-byte longwords.  */
  42
  43   longword_ptr = (unsigned long int *) char_ptr;
  44
  45   /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
  46      the "holes."  Note that there is a hole just to the left of
  47      each byte, with an extra at the end:
  48
  49      bits:  01111110 11111110 11111110 11111111
  50      bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
  51
  52      The 1-bits make sure that carries propagate to the next 0-bit.
  53      The 0-bits provide holes for carries to fall into.  */
  54   switch (sizeof (longword))
  55     {
  56     case 4: magic_bits = 0x7efefeffL; break;
  57     case 8: magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; break;
  58     default:
  59       abort ();
  60     }
  61
  62   /* Set up a longword, each of whose bytes is C.  */
  63   charmask = c | (c << 8);
  64   charmask |= charmask << 16;
  65   if (sizeof (longword) > 4)
  66     /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
  67     charmask |= (charmask << 16) << 16;
  68   if (sizeof (longword) > 8)
  69     abort ();
  70
  71   /* Instead of the traditional loop which tests each character,
  72      we will test a longword at a time.  The tricky part is testing
  73      if *any of the four* bytes in the longword in question are zero.  */
  74   for (;;)
  75     {
  76       /* We tentatively exit the loop if adding MAGIC_BITS to
  77          LONGWORD fails to change any of the hole bits of LONGWORD.
  78
  79          1) Is this safe?  Will it catch all the zero bytes?
  80          Suppose there is a byte with all zeros.  Any carry bits
  81          propagating from its left will fall into the hole at its
  82          least significant bit and stop.  Since there will be no
  83          carry from its most significant bit, the LSB of the
  84          byte to the left will be unchanged, and the zero will be
  85          detected.
  86
  87          2) Is this worthwhile?  Will it ignore everything except
  88          zero bytes?  Suppose every byte of LONGWORD has a bit set
  89          somewhere.  There will be a carry into bit 8.  If bit 8
  90          is set, this will carry into bit 16.  If bit 8 is clear,
  91          one of bits 9-15 must be set, so there will be a carry
  92          into bit 16.  Similarly, there will be a carry into bit
  93          24.  If one of bits 24-30 is set, there will be a carry
  94          into bit 31, so all of the hole bits will be changed.
  95
  96          The one misfire occurs when bits 24-30 are clear and bit
  97          31 is set; in this case, the hole at bit 31 is not
  98          changed.  If we had access to the processor carry flag,
  99          we could close this loophole by putting the fourth hole
 100          at bit 32!
 101
 102          So it ignores everything except 128's, when they're aligned
 103          properly.
 104
 105          3) But wait!  Aren't we looking for C as well as zero?
 106          Good point.  So what we do is XOR LONGWORD with a longword,
 107          each of whose bytes is C.  This turns each byte that is C
 108          into a zero.  */
 109
 110       longword = *longword_ptr++;
 111
 112       /* Add MAGIC_BITS to LONGWORD.  */
 113       if ((((longword + magic_bits)
 114
 115             /* Set those bits that were unchanged by the addition.  */
 116             ^ ~longword)
 117
 118            /* Look at only the hole bits.  If any of the hole bits
 119               are unchanged, most likely one of the bytes was a
 120               zero.  */
 121            & ~magic_bits) != 0 ||
 122
 123           /* That caught zeroes.  Now test for C.  */
 124           ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask))
 125            & ~magic_bits) != 0)
 126         {
 127           /* Which of the bytes was C or zero?
 128              If none of them were, it was a misfire; continue the search.  */
 129
 130           const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
 131
 132           if (*cp == c || *cp == '\0')
 133             return (char *) cp;
 134           if (*++cp == c || *cp == '\0')
 135             return (char *) cp;
 136           if (*++cp == c || *cp == '\0')
 137             return (char *) cp;
 138           if (*++cp == c || *cp == '\0')
 139             return (char *) cp;
 140           if (sizeof (longword) > 4)
 141             {
 142               if (*++cp == c || *cp == '\0')
 143                 return (char *) cp;
 144               if (*++cp == c || *cp == '\0')
 145                 return (char *) cp;
 146               if (*++cp == c || *cp == '\0')
 147                 return (char *) cp;
 148               if (*++cp == c || *cp == '\0')
 149                 return (char *) cp;
 150             }
 151         }
 152     }
 153
 154   /* This should never happen.  */
 155   return NULL;
 156 }
 157
 158 /* For platform which support the ISO C amendement 1 functionality we
 159    support user defined character classes.  */
 160 #if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
 161 /* Solaris 2.5 has a bug: <wchar.h> must be included before <wctype.h>.  */
 162 # include <wchar.h>
 163 # include <wctype.h>
 164 #endif
 165
 166 /* Comment out all this code if we are using the GNU C Library, and are not
 167    actually compiling the library itself.  This code is part of the GNU C
 168    Library, but also included in many other GNU distributions.  Compiling
 169    and linking in this code is a waste when using the GNU C library
 170    (especially if it is a shared library).  Rather than having every GNU
 171    program understand `configure --with-gnu-libc' and omit the object files,
 172    it is simpler to just do this in the source for each such file.  */
 173
 174 #if defined _LIBC || !defined __GNU_LIBRARY__
 175
 176
 177 # if defined STDC_HEADERS || !defined isascii
 178 #  define ISASCII(c) 1
 179 # else
 180 #  define ISASCII(c) isascii(c)
 181 # endif
 182
 183 #ifdef isblank
 184 # define ISBLANK(c) (ISASCII (c) && isblank (c))
 185 #else
 186 # define ISBLANK(c) ((c) == ' ' || (c) == '\t')
 187 #endif
 188 #ifdef isgraph
 189 # define ISGRAPH(c) (ISASCII (c) && isgraph (c))
 190 #else
 191 # define ISGRAPH(c) (ISASCII (c) && isprint (c) && !isspace (c))
 192 #endif
 193
 194 #define ISPRINT(c) (ISASCII (c) && isprint (c))
 195 #define ISDIGIT(c) (ISASCII (c) && isdigit (c))
 196 #define ISALNUM(c) (ISASCII (c) && isalnum (c))
 197 #define ISALPHA(c) (ISASCII (c) && isalpha (c))
 198 #define ISCNTRL(c) (ISASCII (c) && iscntrl (c))
 199 #define ISLOWER(c) (ISASCII (c) && islower (c))
 200 #define ISPUNCT(c) (ISASCII (c) && ispunct (c))
 201 #define ISSPACE(c) (ISASCII (c) && isspace (c))
 202 #define ISUPPER(c) (ISASCII (c) && isupper (c))
 203 #define ISXDIGIT(c) (ISASCII (c) && isxdigit (c))
 204
 205 # define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
 206
 207 # if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
 208 /* The GNU C library provides support for user-defined character classes
 209    and the functions from ISO C amendement 1.  */
 210 #  ifdef CHARCLASS_NAME_MAX
 211 #   define CHAR_CLASS_MAX_LENGTH CHARCLASS_NAME_MAX
 212 #  else
 213 /* This shouldn't happen but some implementation might still have this
 214    problem.  Use a reasonable default value.  */
 215 #   define CHAR_CLASS_MAX_LENGTH 256
 216 #  endif
 217
 218 #  ifdef _LIBC
 219 #   define IS_CHAR_CLASS(string) __wctype (string)
 220 #  else
 221 #   define IS_CHAR_CLASS(string) wctype (string)
 222 #  endif
 223 # else
 224 #  define CHAR_CLASS_MAX_LENGTH  6 /* Namely, `xdigit'.  */
 225
 226 #  define IS_CHAR_CLASS(string)                                               \
 227    (STREQ (string, "alpha") || STREQ (string, "upper")                        \
 228     || STREQ (string, "lower") || STREQ (string, "digit")                     \
 229     || STREQ (string, "alnum") || STREQ (string, "xdigit")                    \
 230     || STREQ (string, "space") || STREQ (string, "print")                     \
 231     || STREQ (string, "punct") || STREQ (string, "graph")                     \
 232     || STREQ (string, "cntrl") || STREQ (string, "blank"))
 233 # endif
 234
 235 /* Avoid depending on library functions or files
 236    whose names are inconsistent.  */
 237
 238 # if !defined _LIBC && !defined getenv
 239 extern char *getenv ();
 240 # endif
 241
 242 # ifndef errno
 243 extern int errno;
 244 # endif
 245
 246 /* Match STRING against the filename pattern PATTERN, returning zero if
 247    it matches, nonzero if not.  */
 248 static int
 249 #ifdef _LIBC
 250 internal_function
 251 #endif
 252 internal_fnmatch (const char *pattern, const char *string,
 253                   int no_leading_period, int flags)
 254 {
 255   register const char *p = pattern, *n = string;
 256   register unsigned char c;
 257
 258 /* Note that this evaluates C many times.  */
 259 # ifdef _LIBC
 260 #  define FOLD(c) ((flags & FNM_CASEFOLD) ? tolower (c) : (c))
 261 # else
 262 #  define FOLD(c) ((flags & FNM_CASEFOLD) && ISUPPER (c) ? tolower (c) : (c))
 263 # endif
 264
 265   while ((c = *p++) != '\0')
 266     {
 267       c = FOLD (c);
 268
 269       switch (c)
 270         {
 271         case '?':
 272           if (*n == '\0')
 273             return FNM_NOMATCH;
 274           else if (*n == '/' && (flags & FNM_FILE_NAME))
 275             return FNM_NOMATCH;
 276           else if (*n == '.' && no_leading_period
 277                    && (n == string
 278                        || (n[-1] == '/' && (flags & FNM_FILE_NAME))))
 279             return FNM_NOMATCH;
 280           break;
 281
 282         case '\\':
 283           if (!(flags & FNM_NOESCAPE))
 284             {
 285               c = *p++;
 286               if (c == '\0')
 287                 /* Trailing \ loses.  */
 288                 return FNM_NOMATCH;
 289               c = FOLD (c);
 290             }
 291           if (FOLD ((unsigned char) *n) != c)
 292             return FNM_NOMATCH;
 293           break;
 294
 295         case '*':
 296           if (*n == '.' && no_leading_period
 297               && (n == string
 298                   || (n[-1] == '/' && (flags & FNM_FILE_NAME))))
 299             return FNM_NOMATCH;
 300
 301           for (c = *p++; c == '?' || c == '*'; c = *p++)
 302             {
 303               if (*n == '/' && (flags & FNM_FILE_NAME))
 304                 /* A slash does not match a wildcard under FNM_FILE_NAME.  */
 305                 return FNM_NOMATCH;
 306               else if (c == '?')
 307                 {
 308                   /* A ? needs to match one character.  */
 309                   if (*n == '\0')
 310                     /* There isn't another character; no match.  */
 311                     return FNM_NOMATCH;
 312                   else
 313                     /* One character of the string is consumed in matching
 314                        this ? wildcard, so *??? won't match if there are
 315                        less than three characters.  */
 316                     ++n;
 317                 }
 318             }
 319
 320           if (c == '\0')
 321             /* The wildcard(s) is/are the last element of the pattern.
 322                If the name is a file name and contains another slash
 323                this does mean it cannot match.  If the FNM_LEADING_DIR
 324                flag is set and exactly one slash is following, we have
 325                a match.  */
 326             {
 327               int result = (flags & FNM_FILE_NAME) == 0 ? 0 : FNM_NOMATCH;
 328
 329               if (flags & FNM_FILE_NAME)
 330                 {
 331                   const char *slashp = strchr (n, '/');
 332
 333                   if (flags & FNM_LEADING_DIR)
 334                     {
 335                       if (slashp != NULL
 336                           && strchr (slashp + 1, '/') == NULL)
 337                         result = 0;
 338                     }
 339                   else
 340                     {
 341                       if (slashp == NULL)
 342                         result = 0;
 343                     }
 344                 }
 345
 346               return result;
 347             }
 348           else
 349             {
 350               const char *endp;
 351
 352               endp = __strchrnul (n, (flags & FNM_FILE_NAME) ? '/' : '\0');
 353
 354               if (c == '[')
 355                 {
 356                   int flags2 = ((flags & FNM_FILE_NAME)
 357                                 ? flags : (flags & ~FNM_PERIOD));
 358
 359                   for (--p; n < endp; ++n)
 360                     if (internal_fnmatch (p, n,
 361                                           (no_leading_period
 362                                            && (n == string
 363                                                || (n[-1] == '/'
 364                                                    && (flags
 365                                                        & FNM_FILE_NAME)))),
 366                                           flags2)
 367                         == 0)
 368                       return 0;
 369                 }
 370               else if (c == '/' && (flags & FNM_FILE_NAME))
 371                 {
 372                   while (*n != '\0' && *n != '/')
 373                     ++n;
 374                   if (*n == '/'
 375                       && (internal_fnmatch (p, n + 1, flags & FNM_PERIOD,
 376                                             flags) == 0))
 377                     return 0;
 378                 }
 379               else
 380                 {
 381                   int flags2 = ((flags & FNM_FILE_NAME)
 382                                 ? flags : (flags & ~FNM_PERIOD));
 383
 384                   if (c == '\\' && !(flags & FNM_NOESCAPE))
 385                     c = *p;
 386                   c = FOLD (c);
 387                   for (--p; n < endp; ++n)
 388                     if (FOLD ((unsigned char) *n) == c
 389                         && (internal_fnmatch (p, n,
 390                                               (no_leading_period
 391                                                && (n == string
 392                                                    || (n[-1] == '/'
 393                                                        && (flags
 394                                                            & FNM_FILE_NAME)))),
 395                                               flags2) == 0))
 396                       return 0;
 397                 }
 398             }
 399
 400           /* If we come here no match is possible with the wildcard.  */
 401           return FNM_NOMATCH;
 402
 403         case '[':
 404           {
 405             /* Nonzero if the sense of the character class is inverted.  */
 406             static int posixly_correct;
 407             register int not;
 408             char cold;
 409
 410             if (posixly_correct == 0)
 411               posixly_correct = getenv ("POSIXLY_CORRECT") != NULL ? 1 : -1;
 412
 413             if (*n == '\0')
 414               return FNM_NOMATCH;
 415
 416             if (*n == '.' && no_leading_period && (n == string
 417                                                    || (n[-1] == '/'
 418                                                        && (flags
 419                                                            & FNM_FILE_NAME))))
 420               return FNM_NOMATCH;
 421
 422             if (*n == '/' && (flags & FNM_FILE_NAME))
 423               /* `/' cannot be matched.  */
 424               return FNM_NOMATCH;
 425
 426             not = (*p == '!' || (posixly_correct < 0 && *p == '^'));
 427             if (not)
 428               ++p;
 429
 430             c = *p++;
 431             for (;;)
 432               {
 433                 unsigned char fn = FOLD ((unsigned char) *n);
 434
 435                 if (!(flags & FNM_NOESCAPE) && c == '\\')
 436                   {
 437                     if (*p == '\0')
 438                       return FNM_NOMATCH;
 439                     c = FOLD ((unsigned char) *p);
 440                     ++p;
 441
 442                     if (c == fn)
 443                       goto matched;
 444                   }
 445                 else if (c == '[' && *p == ':')
 446                   {
 447                     /* Leave room for the null.  */
 448                     char str[CHAR_CLASS_MAX_LENGTH + 1];
 449                     size_t c1 = 0;
 450 # if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
 451                     wctype_t wt;
 452 # endif
 453                     const char *startp = p;
 454
 455                     for (;;)
 456                       {
 457                         if (c1 == CHAR_CLASS_MAX_LENGTH)
 458                           /* The name is too long and therefore the pattern
 459                              is ill-formed.  */
 460                           return FNM_NOMATCH;
 461
 462                         c = *++p;
 463                         if (c == ':' && p[1] == ']')
 464                           {
 465                             p += 2;
 466                             break;
 467                           }
 468                         if (c < 'a' || c >= 'z')
 469                           {
 470                             /* This cannot possibly be a character class name.
 471                                Match it as a normal range.  */
 472                             p = startp;
 473                             c = '[';
 474                             goto normal_bracket;
 475                           }
 476                         str[c1++] = c;
 477                       }
 478                     str[c1] = '\0';
 479
 480 # if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
 481                     wt = IS_CHAR_CLASS (str);
 482                     if (wt == 0)
 483                       /* Invalid character class name.  */
 484                       return FNM_NOMATCH;
 485
 486                     if (__iswctype (__btowc ((unsigned char) *n), wt))
 487                       goto matched;
 488 # else
 489                     if ((STREQ (str, "alnum") && ISALNUM ((unsigned char) *n))
 490                         || (STREQ (str, "alpha") && ISALPHA ((unsigned char) *n))
 491                         || (STREQ (str, "blank") && ISBLANK ((unsigned char) *n))
 492                         || (STREQ (str, "cntrl") && ISCNTRL ((unsigned char) *n))
 493                         || (STREQ (str, "digit") && ISDIGIT ((unsigned char) *n))
 494                         || (STREQ (str, "graph") && ISGRAPH ((unsigned char) *n))
 495                         || (STREQ (str, "lower") && ISLOWER ((unsigned char) *n))
 496                         || (STREQ (str, "print") && ISPRINT ((unsigned char) *n))
 497                         || (STREQ (str, "punct") && ISPUNCT ((unsigned char) *n))
 498                         || (STREQ (str, "space") && ISSPACE ((unsigned char) *n))
 499                         || (STREQ (str, "upper") && ISUPPER ((unsigned char) *n))
 500                         || (STREQ (str, "xdigit") && ISXDIGIT ((unsigned char) *n)))
 501                       goto matched;
 502 # endif
 503                   }
 504                 else if (c == '\0')
 505                   /* [ (unterminated) loses.  */
 506                   return FNM_NOMATCH;
 507                 else
 508                   {
 509                     c = FOLD (c);
 510                   normal_bracket:
 511                     if (c == fn)
 512                       goto matched;
 513
 514                     cold = c;
 515                     c = *p++;
 516
 517                     if (c == '-' && *p != ']')
 518                       {
 519                         /* It is a range.  */
 520                         char lo[2];
 521                         char fc[2];
 522                         unsigned char cend = *p++;
 523                         if (!(flags & FNM_NOESCAPE) && cend == '\\')
 524                           cend = *p++;
 525                         if (cend == '\0')
 526                           return FNM_NOMATCH;
 527
 528                         lo[0] = cold;
 529                         lo[1] = '\0';
 530                         fc[0] = fn;
 531                         fc[1] = '\0';
 532                         if (strcoll (lo, fc) <= 0)
 533                           {
 534                             char hi[2];
 535                             hi[0] = FOLD (cend);
 536                             hi[1] = '\0';
 537                             if (strcoll (fc, hi) <= 0)
 538                               goto matched;
 539                           }
 540
 541                         c = *p++;
 542                       }
 543                   }
 544
 545                 if (c == ']')
 546                   break;
 547               }
 548
 549             if (!not)
 550               return FNM_NOMATCH;
 551             break;
 552
 553           matched:
 554             /* Skip the rest of the [...] that already matched.  */
 555             while (c != ']')
 556               {
 557                 if (c == '\0')
 558                   /* [... (unterminated) loses.  */
 559                   return FNM_NOMATCH;
 560
 561                 c = *p++;
 562                 if (!(flags & FNM_NOESCAPE) && c == '\\')
 563                   {
 564                     if (*p == '\0')
 565                       return FNM_NOMATCH;
 566                     /* XXX 1003.2d11 is unclear if this is right.  */
 567                     ++p;
 568                   }
 569                 else if (c == '[' && *p == ':')
 570                   {
 571                     do
 572                       if (*++p == '\0')
 573                         return FNM_NOMATCH;
 574                     while (*p != ':' || p[1] == ']');
 575                     p += 2;
 576                     c = *p;
 577                   }
 578               }
 579             if (not)
 580               return FNM_NOMATCH;
 581           }
 582           break;
 583
 584         default:
 585           if (c != FOLD ((unsigned char) *n))
 586             return FNM_NOMATCH;
 587         }
 588
 589       ++n;
 590     }
 591
 592   if (*n == '\0')
 593     return 0;
 594
 595   if ((flags & FNM_LEADING_DIR) && *n == '/')
 596     /* The FNM_LEADING_DIR flag says that "foo*" matches "foobar/frobozz".  */
 597     return 0;
 598
 599   return FNM_NOMATCH;
 600
 601 # undef FOLD
 602 }
 603
 604
 605 int
 606 fnmatch (const char *pattern, const char *string, int flags)
 607 {
 608   return internal_fnmatch (pattern, string, flags & FNM_PERIOD, flags);
 609 }
 610
 611 #endif  /* _LIBC or not __GNU_LIBRARY__.  */