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