posix/fnmatch_loop.c

   1 /* Copyright (C) 1991-1993, 1996-2000, 2001 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3
   4    The GNU C Library is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU Lesser General Public
   6    License as published by the Free Software Foundation; either
   7    version 2.1 of the License, or (at your option) any later version.
   8
   9    The GNU C 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    Lesser General Public License for more details.
  13
  14    You should have received a copy of the GNU Lesser General Public
  15    License along with the GNU C Library; if not, write to the Free
  16    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  17    02111-1307 USA.  */
  18
  19 /* Match STRING against the filename pattern PATTERN, returning zero if
  20    it matches, nonzero if not.  */
  21 static int FCT (const CHAR *pattern, const CHAR *string,
  22                 const CHAR *string_end, int no_leading_period, int flags)
  23      internal_function;
  24 static int EXT (INT opt, const CHAR *pattern, const CHAR *string,
  25                 const CHAR *string_end, int no_leading_period, int flags)
  26      internal_function;
  27 static const CHAR *END (const CHAR *patternp) internal_function;
  28
  29 static int
  30 internal_function
  31 FCT (pattern, string, string_end, no_leading_period, flags)
  32      const CHAR *pattern;
  33      const CHAR *string;
  34      const CHAR *string_end;
  35      int no_leading_period;
  36      int flags;
  37 {
  38   register const CHAR *p = pattern, *n = string;
  39   register UCHAR c;
  40 #ifdef _LIBC
  41 # if WIDE_CHAR_VERSION
  42   const char *collseq = (const char *)
  43     _NL_CURRENT(LC_COLLATE, _NL_COLLATE_COLLSEQWC);
  44 # else
  45   const UCHAR *collseq = (const UCHAR *)
  46     _NL_CURRENT(LC_COLLATE, _NL_COLLATE_COLLSEQMB);
  47 # endif
  48 #endif
  49
  50   while ((c = *p++) != L('\0'))
  51     {
  52       int new_no_leading_period = 0;
  53       c = FOLD (c);
  54
  55       switch (c)
  56         {
  57         case L('?'):
  58           if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(')
  59             {
  60               int res;
  61
  62               res = EXT (c, p, n, string_end, no_leading_period,
  63                          flags);
  64               if (res != -1)
  65                 return res;
  66             }
  67
  68           if (n == string_end)
  69             return FNM_NOMATCH;
  70           else if (*n == L('/') && (flags & FNM_FILE_NAME))
  71             return FNM_NOMATCH;
  72           else if (*n == L('.') && no_leading_period)
  73             return FNM_NOMATCH;
  74           break;
  75
  76         case L('\\'):
  77           if (!(flags & FNM_NOESCAPE))
  78             {
  79               c = *p++;
  80               if (c == L('\0'))
  81                 /* Trailing \ loses.  */
  82                 return FNM_NOMATCH;
  83               c = FOLD (c);
  84             }
  85           if (n == string_end || FOLD ((UCHAR) *n) != c)
  86             return FNM_NOMATCH;
  87           break;
  88
  89         case L('*'):
  90           if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(')
  91             {
  92               int res;
  93
  94               res = EXT (c, p, n, string_end, no_leading_period,
  95                          flags);
  96               if (res != -1)
  97                 return res;
  98             }
  99
 100           if (n != string_end && *n == L('.') && no_leading_period)
 101             return FNM_NOMATCH;
 102
 103           for (c = *p++; c == L('?') || c == L('*'); c = *p++)
 104             {
 105               if (*p == L('(') && (flags & FNM_EXTMATCH) != 0)
 106                 {
 107                   const CHAR *endp = END (p);
 108                   if (endp != p)
 109                     {
 110                       /* This is a pattern.  Skip over it.  */
 111                       p = endp;
 112                       continue;
 113                     }
 114                 }
 115
 116               if (c == L('?'))
 117                 {
 118                   /* A ? needs to match one character.  */
 119                   if (n == string_end)
 120                     /* There isn't another character; no match.  */
 121                     return FNM_NOMATCH;
 122                   else if (*n == L('/')
 123                            && __builtin_expect (flags & FNM_FILE_NAME, 0))
 124                     /* A slash does not match a wildcard under
 125                        FNM_FILE_NAME.  */
 126                     return FNM_NOMATCH;
 127                   else
 128                     /* One character of the string is consumed in matching
 129                        this ? wildcard, so *??? won't match if there are
 130                        less than three characters.  */
 131                     ++n;
 132                 }
 133             }
 134
 135           if (c == L('\0'))
 136             /* The wildcard(s) is/are the last element of the pattern.
 137                If the name is a file name and contains another slash
 138                this means it cannot match, unless the FNM_LEADING_DIR
 139                flag is set.  */
 140             {
 141               int result = (flags & FNM_FILE_NAME) == 0 ? 0 : FNM_NOMATCH;
 142
 143               if (flags & FNM_FILE_NAME)
 144                 {
 145                   if (flags & FNM_LEADING_DIR)
 146                     result = 0;
 147                   else
 148                     {
 149                       if (MEMCHR (n, L('/'), string_end - n) == NULL)
 150                         result = 0;
 151                     }
 152                 }
 153
 154               return result;
 155             }
 156           else
 157             {
 158               const CHAR *endp;
 159
 160               endp = MEMCHR (n, (flags & FNM_FILE_NAME) ? L('/') : L('\0'),
 161                              string_end - n);
 162               if (endp == NULL)
 163                 endp = string_end;
 164
 165               if (c == L('[')
 166                   || (__builtin_expect (flags & FNM_EXTMATCH, 0) != 0
 167                       && (c == L('@') || c == L('+') || c == L('!'))
 168                       && *p == L('(')))
 169                 {
 170                   int flags2 = ((flags & FNM_FILE_NAME)
 171                                 ? flags : (flags & ~FNM_PERIOD));
 172                   int no_leading_period2 = no_leading_period;
 173
 174                   for (--p; n < endp; ++n, no_leading_period2 = 0)
 175                     if (FCT (p, n, string_end, no_leading_period2, flags2)
 176                         == 0)
 177                       return 0;
 178                 }
 179               else if (c == L('/') && (flags & FNM_FILE_NAME))
 180                 {
 181                   while (n < string_end && *n != L('/'))
 182                     ++n;
 183                   if (n < string_end && *n == L('/')
 184                       && (FCT (p, n + 1, string_end, flags & FNM_PERIOD, flags)
 185                           == 0))
 186                     return 0;
 187                 }
 188               else
 189                 {
 190                   int flags2 = ((flags & FNM_FILE_NAME)
 191                                 ? flags : (flags & ~FNM_PERIOD));
 192                   int no_leading_period2 = no_leading_period;
 193
 194                   if (c == L('\\') && !(flags & FNM_NOESCAPE))
 195                     c = *p;
 196                   c = FOLD (c);
 197                   for (--p; n < endp; ++n, no_leading_period2 = 0)
 198                     if (FOLD ((UCHAR) *n) == c
 199                         && (FCT (p, n, string_end, no_leading_period2, flags2)
 200                             == 0))
 201                       return 0;
 202                 }
 203             }
 204
 205           /* If we come here no match is possible with the wildcard.  */
 206           return FNM_NOMATCH;
 207
 208         case L('['):
 209           {
 210             /* Nonzero if the sense of the character class is inverted.  */
 211             register int not;
 212             CHAR cold;
 213             UCHAR fn;
 214
 215             if (posixly_correct == 0)
 216               posixly_correct = getenv ("POSIXLY_CORRECT") != NULL ? 1 : -1;
 217
 218             if (n == string_end)
 219               return FNM_NOMATCH;
 220
 221             if (*n == L('.') && no_leading_period)
 222               return FNM_NOMATCH;
 223
 224             if (*n == L('/') && (flags & FNM_FILE_NAME))
 225               /* `/' cannot be matched.  */
 226               return FNM_NOMATCH;
 227
 228             not = (*p == L('!') || (posixly_correct < 0 && *p == L('^')));
 229             if (not)
 230               ++p;
 231
 232             fn = FOLD ((UCHAR) *n);
 233
 234             c = *p++;
 235             for (;;)
 236               {
 237                 if (!(flags & FNM_NOESCAPE) && c == L('\\'))
 238                   {
 239                     if (*p == L('\0'))
 240                       return FNM_NOMATCH;
 241                     c = FOLD ((UCHAR) *p);
 242                     ++p;
 243
 244                     if (c == fn)
 245                       goto matched;
 246                   }
 247                 else if (c == L('[') && *p == L(':'))
 248                   {
 249                     /* Leave room for the null.  */
 250                     CHAR str[CHAR_CLASS_MAX_LENGTH + 1];
 251                     size_t c1 = 0;
 252 #if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
 253                     wctype_t wt;
 254 #endif
 255                     const CHAR *startp = p;
 256
 257                     for (;;)
 258                       {
 259                         if (c1 == CHAR_CLASS_MAX_LENGTH)
 260                           /* The name is too long and therefore the pattern
 261                              is ill-formed.  */
 262                           return FNM_NOMATCH;
 263
 264                         c = *++p;
 265                         if (c == L(':') && p[1] == L(']'))
 266                           {
 267                             p += 2;
 268                             break;
 269                           }
 270                         if (c < L('a') || c >= L('z'))
 271                           {
 272                             /* This cannot possibly be a character class name.
 273                                Match it as a normal range.  */
 274                             p = startp;
 275                             c = L('[');
 276                             goto normal_bracket;
 277                           }
 278                         str[c1++] = c;
 279                       }
 280                     str[c1] = L('\0');
 281
 282 #if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
 283                     wt = IS_CHAR_CLASS (str);
 284                     if (wt == 0)
 285                       /* Invalid character class name.  */
 286                       return FNM_NOMATCH;
 287
 288 # if defined _LIBC && ! WIDE_CHAR_VERSION
 289                     /* The following code is glibc specific but does
 290                        there a good job in speeding up the code since
 291                        we can avoid the btowc() call.  */
 292                     if (_ISCTYPE ((UCHAR) *n, wt))
 293                       goto matched;
 294 # else
 295                     if (ISWCTYPE (BTOWC ((UCHAR) *n), wt))
 296                       goto matched;
 297 # endif
 298 #else
 299                     if ((STREQ (str, L("alnum")) && ISALNUM ((UCHAR) *n))
 300                         || (STREQ (str, L("alpha")) && ISALPHA ((UCHAR) *n))
 301                         || (STREQ (str, L("blank")) && ISBLANK ((UCHAR) *n))
 302                         || (STREQ (str, L("cntrl")) && ISCNTRL ((UCHAR) *n))
 303                         || (STREQ (str, L("digit")) && ISDIGIT ((UCHAR) *n))
 304                         || (STREQ (str, L("graph")) && ISGRAPH ((UCHAR) *n))
 305                         || (STREQ (str, L("lower")) && ISLOWER ((UCHAR) *n))
 306                         || (STREQ (str, L("print")) && ISPRINT ((UCHAR) *n))
 307                         || (STREQ (str, L("punct")) && ISPUNCT ((UCHAR) *n))
 308                         || (STREQ (str, L("space")) && ISSPACE ((UCHAR) *n))
 309                         || (STREQ (str, L("upper")) && ISUPPER ((UCHAR) *n))
 310                         || (STREQ (str, L("xdigit")) && ISXDIGIT ((UCHAR) *n)))
 311                       goto matched;
 312 #endif
 313                     c = *p++;
 314                   }
 315 #ifdef _LIBC
 316                 else if (c == L('[') && *p == L('='))
 317                   {
 318                     UCHAR str[1];
 319                     uint32_t nrules =
 320                       _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
 321                     const CHAR *startp = p;
 322
 323                     c = *++p;
 324                     if (c == L('\0'))
 325                       {
 326                         p = startp;
 327                         c = L('[');
 328                         goto normal_bracket;
 329                       }
 330                     str[0] = c;
 331
 332                     c = *++p;
 333                     if (c != L('=') || p[1] != L(']'))
 334                       {
 335                         p = startp;
 336                         c = L('[');
 337                         goto normal_bracket;
 338                       }
 339                     p += 2;
 340
 341                     if (nrules == 0)
 342                       {
 343                         if ((UCHAR) *n == str[0])
 344                           goto matched;
 345                       }
 346                     else
 347                       {
 348                         const int32_t *table;
 349 # if WIDE_CHAR_VERSION
 350                         const int32_t *weights;
 351                         const int32_t *extra;
 352 # else
 353                         const unsigned char *weights;
 354                         const unsigned char *extra;
 355 # endif
 356                         const int32_t *indirect;
 357                         int32_t idx;
 358                         const UCHAR *cp = (const UCHAR *) str;
 359
 360                         /* This #include defines a local function!  */
 361 # if WIDE_CHAR_VERSION
 362 #  include <locale/weightwc.h>
 363 # else
 364 #  include <locale/weight.h>
 365 # endif
 366
 367 # if WIDE_CHAR_VERSION
 368                         table = (const int32_t *)
 369                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEWC);
 370                         weights = (const int32_t *)
 371                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTWC);
 372                         extra = (const int32_t *)
 373                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAWC);
 374                         indirect = (const int32_t *)
 375                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTWC);
 376 # else
 377                         table = (const int32_t *)
 378                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
 379                         weights = (const unsigned char *)
 380                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
 381                         extra = (const unsigned char *)
 382                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
 383                         indirect = (const int32_t *)
 384                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
 385 # endif
 386
 387                         idx = findidx (&cp);
 388                         if (idx != 0)
 389                           {
 390                             /* We found a table entry.  Now see whether the
 391                                character we are currently at has the same
 392                                equivalance class value.  */
 393                             int len = weights[idx];
 394                             int32_t idx2;
 395                             const UCHAR *np = (const UCHAR *) n;
 396
 397                             idx2 = findidx (&np);
 398                             if (idx2 != 0 && len == weights[idx2])
 399                               {
 400                                 int cnt = 0;
 401
 402                                 while (cnt < len
 403                                        && (weights[idx + 1 + cnt]
 404                                            == weights[idx2 + 1 + cnt]))
 405                                   ++cnt;
 406
 407                                 if (cnt == len)
 408                                   goto matched;
 409                               }
 410                           }
 411                       }
 412
 413                     c = *p++;
 414                   }
 415 #endif
 416                 else if (c == L('\0'))
 417                   /* [ (unterminated) loses.  */
 418                   return FNM_NOMATCH;
 419                 else
 420                   {
 421                     int is_range = 0;
 422
 423 #ifdef _LIBC
 424                     int is_seqval = 0;
 425
 426                     if (c == L('[') && *p == L('.'))
 427                       {
 428                         uint32_t nrules =
 429                           _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
 430                         const CHAR *startp = p;
 431                         size_t c1 = 0;
 432
 433                         while (1)
 434                           {
 435                             c = *++p;
 436                             if (c == L('.') && p[1] == L(']'))
 437                               {
 438                                 p += 2;
 439                                 break;
 440                               }
 441                             if (c == '\0')
 442                               return FNM_NOMATCH;
 443                             ++c1;
 444                           }
 445
 446                         /* We have to handling the symbols differently in
 447                            ranges since then the collation sequence is
 448                            important.  */
 449                         is_range = *p == L('-') && p[1] != L('\0');
 450
 451                         if (nrules == 0)
 452                           {
 453                             /* There are no names defined in the collation
 454                                data.  Therefore we only accept the trivial
 455                                names consisting of the character itself.  */
 456                             if (c1 != 1)
 457                               return FNM_NOMATCH;
 458
 459                             if (!is_range && *n == startp[1])
 460                               goto matched;
 461
 462                             cold = startp[1];
 463                             c = *p++;
 464                           }
 465                         else
 466                           {
 467                             int32_t table_size;
 468                             const int32_t *symb_table;
 469 # ifdef WIDE_CHAR_VERSION
 470                             char str[c1];
 471                             unsigned int strcnt;
 472 # else
 473 #  define str (startp + 1)
 474 # endif
 475                             const unsigned char *extra;
 476                             int32_t idx;
 477                             int32_t elem;
 478                             int32_t second;
 479                             int32_t hash;
 480
 481 # ifdef WIDE_CHAR_VERSION
 482                             /* We have to convert the name to a single-byte
 483                                string.  This is possible since the names
 484                                consist of ASCII characters and the internal
 485                                representation is UCS4.  */
 486                             for (strcnt = 0; strcnt < c1; ++strcnt)
 487                               str[strcnt] = startp[1 + strcnt];
 488 #endif
 489
 490                             table_size =
 491                               _NL_CURRENT_WORD (LC_COLLATE,
 492                                                 _NL_COLLATE_SYMB_HASH_SIZEMB);
 493                             symb_table = (const int32_t *)
 494                               _NL_CURRENT (LC_COLLATE,
 495                                            _NL_COLLATE_SYMB_TABLEMB);
 496                             extra = (const unsigned char *)
 497                               _NL_CURRENT (LC_COLLATE,
 498                                            _NL_COLLATE_SYMB_EXTRAMB);
 499
 500                             /* Locate the character in the hashing table.  */
 501                             hash = elem_hash (str, c1);
 502
 503                             idx = 0;
 504                             elem = hash % table_size;
 505                             second = hash % (table_size - 2);
 506                             while (symb_table[2 * elem] != 0)
 507                               {
 508                                 /* First compare the hashing value.  */
 509                                 if (symb_table[2 * elem] == hash
 510                                     && c1 == extra[symb_table[2 * elem + 1]]
 511                                     && memcmp (str,
 512                                                &extra[symb_table[2 * elem + 1]
 513                                                      + 1], c1) == 0)
 514                                   {
 515                                     /* Yep, this is the entry.  */
 516                                     idx = symb_table[2 * elem + 1];
 517                                     idx += 1 + extra[idx];
 518                                     break;
 519                                   }
 520
 521                                 /* Next entry.  */
 522                                 elem += second;
 523                               }
 524
 525                             if (symb_table[2 * elem] != 0)
 526                               {
 527                                 /* Compare the byte sequence but only if
 528                                    this is not part of a range.  */
 529 # ifdef WIDE_CHAR_VERSION
 530                                 int32_t *wextra;
 531
 532                                 idx += 1 + extra[idx];
 533                                 /* Adjust for the alignment.  */
 534                                 idx = (idx + 3) & ~3;
 535
 536                                 wextra = (int32_t *) &extra[idx + 4];
 537 # endif
 538
 539                                 if (! is_range)
 540                                   {
 541 # ifdef WIDE_CHAR_VERSION
 542                                     for (c1 = 0; c1 < wextra[idx]; ++c1)
 543                                       if (n[c1] != wextra[1 + c1])
 544                                         break;
 545
 546                                     if (c1 == wextra[idx])
 547                                       goto matched;
 548 # else
 549                                     for (c1 = 0; c1 < extra[idx]; ++c1)
 550                                       if (n[c1] != extra[1 + c1])
 551                                         break;
 552
 553                                     if (c1 == extra[idx])
 554                                       goto matched;
 555 # endif
 556                                   }
 557
 558                                 /* Get the collation sequence value.  */
 559                                 is_seqval = 1;
 560 # ifdef WIDE_CHAR_VERSION
 561                                 cold = wextra[1 + wextra[idx]];
 562 # else
 563                                 /* Adjust for the alignment.  */
 564                                 idx += 1 + extra[idx];
 565                                 idx = (idx + 3) & ~4;
 566                                 cold = *((int32_t *) &extra[idx]);
 567 # endif
 568
 569                                 c = *p++;
 570                               }
 571                             else if (c1 == 1)
 572                               {
 573                                 /* No valid character.  Match it as a
 574                                    single byte.  */
 575                                 if (!is_range && *n == str[0])
 576                                   goto matched;
 577
 578                                 cold = str[0];
 579                                 c = *p++;
 580                               }
 581                             else
 582                               return FNM_NOMATCH;
 583                           }
 584                       }
 585                     else
 586 # undef str
 587 #endif
 588                       {
 589                         c = FOLD (c);
 590                       normal_bracket:
 591
 592                         /* We have to handling the symbols differently in
 593                            ranges since then the collation sequence is
 594                            important.  */
 595                         is_range = (*p == L('-') && p[1] != L('\0')
 596                                     && p[1] != L(']'));
 597
 598                         if (!is_range && c == fn)
 599                           goto matched;
 600
 601                         cold = c;
 602                         c = *p++;
 603                       }
 604
 605                     if (c == L('-') && *p != L(']'))
 606                       {
 607 #if _LIBC
 608                         /* We have to find the collation sequence
 609                            value for C.  Collation sequence is nothing
 610                            we can regularly access.  The sequence
 611                            value is defined by the order in which the
 612                            definitions of the collation values for the
 613                            various characters appear in the source
 614                            file.  A strange concept, nowhere
 615                            documented.  */
 616                         uint32_t fcollseq;
 617                         uint32_t lcollseq;
 618                         UCHAR cend = *p++;
 619
 620 # ifdef WIDE_CHAR_VERSION
 621                         /* Search in the `names' array for the characters.  */
 622                         fcollseq = collseq_table_lookup (collseq, fn);
 623                         if (fcollseq == ~((uint32_t) 0))
 624                           /* XXX We don't know anything about the character
 625                              we are supposed to match.  This means we are
 626                              failing.  */
 627                           goto range_not_matched;
 628
 629                         if (is_seqval)
 630                           lcollseq = cold;
 631                         else
 632                           lcollseq = collseq_table_lookup (collseq, cold);
 633 # else
 634                         fcollseq = collseq[fn];
 635                         lcollseq = is_seqval ? cold : collseq[(UCHAR) cold];
 636 # endif
 637
 638                         is_seqval = 0;
 639                         if (cend == L('[') && *p == L('.'))
 640                           {
 641                             uint32_t nrules =
 642                               _NL_CURRENT_WORD (LC_COLLATE,
 643                                                 _NL_COLLATE_NRULES);
 644                             const CHAR *startp = p;
 645                             size_t c1 = 0;
 646
 647                             while (1)
 648                               {
 649                                 c = *++p;
 650                                 if (c == L('.') && p[1] == L(']'))
 651                                   {
 652                                     p += 2;
 653                                     break;
 654                                   }
 655                                 if (c == '\0')
 656                                   return FNM_NOMATCH;
 657                                 ++c1;
 658                               }
 659
 660                             if (nrules == 0)
 661                               {
 662                                 /* There are no names defined in the
 663                                    collation data.  Therefore we only
 664                                    accept the trivial names consisting
 665                                    of the character itself.  */
 666                                 if (c1 != 1)
 667                                   return FNM_NOMATCH;
 668
 669                                 cend = startp[1];
 670                               }
 671                             else
 672                               {
 673                                 int32_t table_size;
 674                                 const int32_t *symb_table;
 675 # ifdef WIDE_CHAR_VERSION
 676                                 char str[c1];
 677                                 unsigned int strcnt;
 678 # else
 679 #  define str (startp + 1)
 680 # endif
 681                                 const unsigned char *extra;
 682                                 int32_t idx;
 683                                 int32_t elem;
 684                                 int32_t second;
 685                                 int32_t hash;
 686
 687 # ifdef WIDE_CHAR_VERSION
 688                                 /* We have to convert the name to a single-byte
 689                                    string.  This is possible since the names
 690                                    consist of ASCII characters and the internal
 691                                    representation is UCS4.  */
 692                                 for (strcnt = 0; strcnt < c1; ++strcnt)
 693                                   str[strcnt] = startp[1 + strcnt];
 694 # endif
 695
 696                                 table_size =
 697                                   _NL_CURRENT_WORD (LC_COLLATE,
 698                                                     _NL_COLLATE_SYMB_HASH_SIZEMB);
 699                                 symb_table = (const int32_t *)
 700                                   _NL_CURRENT (LC_COLLATE,
 701                                                _NL_COLLATE_SYMB_TABLEMB);
 702                                 extra = (const unsigned char *)
 703                                   _NL_CURRENT (LC_COLLATE,
 704                                                _NL_COLLATE_SYMB_EXTRAMB);
 705
 706                                 /* Locate the character in the hashing
 707                                    table.  */
 708                                 hash = elem_hash (str, c1);
 709
 710                                 idx = 0;
 711                                 elem = hash % table_size;
 712                                 second = hash % (table_size - 2);
 713                                 while (symb_table[2 * elem] != 0)
 714                                   {
 715                                 /* First compare the hashing value.  */
 716                                     if (symb_table[2 * elem] == hash
 717                                         && (c1
 718                                             == extra[symb_table[2 * elem + 1]])
 719                                         && memcmp (str,
 720                                                    &extra[symb_table[2 * elem + 1]
 721                                                          + 1], c1) == 0)
 722                                       {
 723                                         /* Yep, this is the entry.  */
 724                                         idx = symb_table[2 * elem + 1];
 725                                         idx += 1 + extra[idx];
 726                                         break;
 727                                       }
 728
 729                                     /* Next entry.  */
 730                                     elem += second;
 731                                   }
 732
 733                                 if (symb_table[2 * elem] != 0)
 734                                   {
 735                                     /* Compare the byte sequence but only if
 736                                        this is not part of a range.  */
 737 # ifdef WIDE_CHAR_VERSION
 738                                     int32_t *wextra;
 739
 740                                     idx += 1 + extra[idx];
 741                                     /* Adjust for the alignment.  */
 742                                     idx = (idx + 3) & ~4;
 743
 744                                     wextra = (int32_t *) &extra[idx + 4];
 745 # endif
 746                                     /* Get the collation sequence value.  */
 747                                     is_seqval = 1;
 748 # ifdef WIDE_CHAR_VERSION
 749                                     cend = wextra[1 + wextra[idx]];
 750 # else
 751                                     /* Adjust for the alignment.  */
 752                                     idx += 1 + extra[idx];
 753                                     idx = (idx + 3) & ~4;
 754                                     cend = *((int32_t *) &extra[idx]);
 755 # endif
 756                                   }
 757                                 else if (symb_table[2 * elem] != 0 && c1 == 1)
 758                                   {
 759                                     cend = str[0];
 760                                     c = *p++;
 761                                   }
 762                                 else
 763                                   return FNM_NOMATCH;
 764                               }
 765 # undef str
 766                           }
 767                         else
 768                           {
 769                             if (!(flags & FNM_NOESCAPE) && cend == L('\\'))
 770                               cend = *p++;
 771                             if (cend == L('\0'))
 772                               return FNM_NOMATCH;
 773                             cend = FOLD (cend);
 774                           }
 775
 776                         /* XXX It is not entirely clear to me how to handle
 777                            characters which are not mentioned in the
 778                            collation specification.  */
 779                         if (
 780 # ifdef WIDE_CHAR_VERSION
 781                             lcollseq == 0xffffffff ||
 782 # endif
 783                             lcollseq <= fcollseq)
 784                           {
 785                             /* We have to look at the upper bound.  */
 786                             uint32_t hcollseq;
 787
 788                             if (is_seqval)
 789                               hcollseq = cend;
 790                             else
 791                               {
 792 # ifdef WIDE_CHAR_VERSION
 793                                 hcollseq =
 794                                   collseq_table_lookup (collseq, cend);
 795                                 if (hcollseq == ~((uint32_t) 0))
 796                                   {
 797                                     /* Hum, no information about the upper
 798                                        bound.  The matching succeeds if the
 799                                        lower bound is matched exactly.  */
 800                                     if (lcollseq != fcollseq)
 801                                       goto range_not_matched;
 802
 803                                     goto matched;
 804                                   }
 805 # else
 806                                 hcollseq = collseq[cend];
 807 # endif
 808                               }
 809
 810                             if (lcollseq <= hcollseq && fcollseq <= hcollseq)
 811                               goto matched;
 812                           }
 813 # ifdef WIDE_CHAR_VERSION
 814                       range_not_matched:
 815 # endif
 816 #else
 817                         /* We use a boring value comparison of the character
 818                            values.  This is better than comparing using
 819                            `strcoll' since the latter would have surprising
 820                            and sometimes fatal consequences.  */
 821                         UCHAR cend = *p++;
 822
 823                         if (!(flags & FNM_NOESCAPE) && cend == L('\\'))
 824                           cend = *p++;
 825                         if (cend == L('\0'))
 826                           return FNM_NOMATCH;
 827
 828                         /* It is a range.  */
 829                         if (cold <= fn && fn <= cend)
 830                           goto matched;
 831 #endif
 832
 833                         c = *p++;
 834                       }
 835                   }
 836
 837                 if (c == L(']'))
 838                   break;
 839               }
 840
 841             if (!not)
 842               return FNM_NOMATCH;
 843             break;
 844
 845           matched:
 846             /* Skip the rest of the [...] that already matched.  */
 847             do
 848               {
 849               ignore_next:
 850                 c = *p++;
 851
 852                 if (c == L('\0'))
 853                   /* [... (unterminated) loses.  */
 854                   return FNM_NOMATCH;
 855
 856                 if (!(flags & FNM_NOESCAPE) && c == L('\\'))
 857                   {
 858                     if (*p == L('\0'))
 859                       return FNM_NOMATCH;
 860                     /* XXX 1003.2d11 is unclear if this is right.  */
 861                     ++p;
 862                   }
 863                 else if (c == L('[') && *p == L(':'))
 864                   {
 865                     int c1 = 0;
 866                     const CHAR *startp = p;
 867
 868                     while (1)
 869                       {
 870                         c = *++p;
 871                         if (++c1 == CHAR_CLASS_MAX_LENGTH)
 872                           return FNM_NOMATCH;
 873
 874                         if (*p == L(':') && p[1] == L(']'))
 875                           break;
 876
 877                         if (c < L('a') || c >= L('z'))
 878                           {
 879                             p = startp;
 880                             goto ignore_next;
 881                           }
 882                       }
 883                     p += 2;
 884                     c = *p++;
 885                   }
 886                 else if (c == L('[') && *p == L('='))
 887                   {
 888                     c = *++p;
 889                     if (c == L('\0'))
 890                       return FNM_NOMATCH;
 891                     c = *++p;
 892                     if (c != L('=') || p[1] != L(']'))
 893                       return FNM_NOMATCH;
 894                     p += 2;
 895                     c = *p++;
 896                   }
 897                 else if (c == L('[') && *p == L('.'))
 898                   {
 899                     ++p;
 900                     while (1)
 901                       {
 902                         c = *++p;
 903                         if (c == '\0')
 904                           return FNM_NOMATCH;
 905
 906                         if (*p == L('.') && p[1] == L(']'))
 907                           break;
 908                       }
 909                     p += 2;
 910                     c = *p++;
 911                   }
 912               }
 913             while (c != L(']'));
 914             if (not)
 915               return FNM_NOMATCH;
 916           }
 917           break;
 918
 919         case L('+'):
 920         case L('@'):
 921         case L('!'):
 922           if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(')
 923             {
 924               int res;
 925
 926               res = EXT (c, p, n, string_end, no_leading_period, flags);
 927               if (res != -1)
 928                 return res;
 929             }
 930           goto normal_match;
 931
 932         case L('/'):
 933           if (NO_LEADING_PERIOD (flags))
 934             {
 935               if (n == string_end || c != *n)
 936                 return FNM_NOMATCH;
 937
 938               new_no_leading_period = 1;
 939               break;
 940             }
 941           /* FALLTHROUGH */
 942         default:
 943         normal_match:
 944           if (n == string_end || c != FOLD ((UCHAR) *n))
 945             return FNM_NOMATCH;
 946         }
 947
 948       no_leading_period = new_no_leading_period;
 949       ++n;
 950     }
 951
 952   if (n == string_end)
 953     return 0;
 954
 955   if ((flags & FNM_LEADING_DIR) && n != string_end && *n == L('/'))
 956     /* The FNM_LEADING_DIR flag says that "foo*" matches "foobar/frobozz".  */
 957     return 0;
 958
 959   return FNM_NOMATCH;
 960 }
 961
 962
 963 static const CHAR *
 964 internal_function
 965 END (const CHAR *pattern)
 966 {
 967   const CHAR *p = pattern;
 968
 969   while (1)
 970     if (*++p == L('\0'))
 971       /* This is an invalid pattern.  */
 972       return pattern;
 973     else if (*p == L('['))
 974       {
 975         /* Handle brackets special.  */
 976         if (posixly_correct == 0)
 977           posixly_correct = getenv ("POSIXLY_CORRECT") != NULL ? 1 : -1;
 978
 979         /* Skip the not sign.  We have to recognize it because of a possibly
 980            following ']'.  */
 981         if (*++p == L('!') || (posixly_correct < 0 && *p == L('^')))
 982           ++p;
 983         /* A leading ']' is recognized as such.  */
 984         if (*p == L(']'))
 985           ++p;
 986         /* Skip over all characters of the list.  */
 987         while (*p != L(']'))
 988           if (*p++ == L('\0'))
 989             /* This is no valid pattern.  */
 990             return pattern;
 991       }
 992     else if ((*p == L('?') || *p == L('*') || *p == L('+') || *p == L('@')
 993               || *p == L('!')) && p[1] == L('('))
 994       p = END (p + 1);
 995     else if (*p == L(')'))
 996       break;
 997
 998   return p + 1;
 999 }
1000
1001
1002 static int
1003 internal_function
1004 EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end,
1005      int no_leading_period, int flags)
1006 {
1007   const CHAR *startp;
1008   int level;
1009   struct patternlist
1010   {
1011     struct patternlist *next;
1012     CHAR str[0];
1013   } *list = NULL;
1014   struct patternlist **lastp = &list;
1015   size_t pattern_len = STRLEN (pattern);
1016   const CHAR *p;
1017   const CHAR *rs;
1018
1019   /* Parse the pattern.  Store the individual parts in the list.  */
1020   level = 0;
1021   for (startp = p = pattern + 1; level >= 0; ++p)
1022     if (*p == L('\0'))
1023       /* This is an invalid pattern.  */
1024       return -1;
1025     else if (*p == L('['))
1026       {
1027         /* Handle brackets special.  */
1028         if (posixly_correct == 0)
1029           posixly_correct = getenv ("POSIXLY_CORRECT") != NULL ? 1 : -1;
1030
1031         /* Skip the not sign.  We have to recognize it because of a possibly
1032            following ']'.  */
1033         if (*++p == L('!') || (posixly_correct < 0 && *p == L('^')))
1034           ++p;
1035         /* A leading ']' is recognized as such.  */
1036         if (*p == L(']'))
1037           ++p;
1038         /* Skip over all characters of the list.  */
1039         while (*p != L(']'))
1040           if (*p++ == L('\0'))
1041             /* This is no valid pattern.  */
1042             return -1;
1043       }
1044     else if ((*p == L('?') || *p == L('*') || *p == L('+') || *p == L('@')
1045               || *p == L('!')) && p[1] == L('('))
1046       /* Remember the nesting level.  */
1047       ++level;
1048     else if (*p == L(')'))
1049       {
1050         if (level-- == 0)
1051           {
1052             /* This means we found the end of the pattern.  */
1053 #define NEW_PATTERN \
1054             struct patternlist *newp;                                         \
1055                                                                               \
1056             if (opt == L('?') || opt == L('@'))                               \
1057               newp = alloca (sizeof (struct patternlist)                      \
1058                              + (pattern_len * sizeof (CHAR)));                \
1059             else                                                              \
1060               newp = alloca (sizeof (struct patternlist)                      \
1061                              + ((p - startp + 1) * sizeof (CHAR)));           \
1062             *((CHAR *) MEMPCPY (newp->str, startp, p - startp)) = L('\0');    \
1063             newp->next = NULL;                                                \
1064             *lastp = newp;                                                    \
1065             lastp = &newp->next
1066             NEW_PATTERN;
1067           }
1068       }
1069     else if (*p == L('|'))
1070       {
1071         if (level == 0)
1072           {
1073             NEW_PATTERN;
1074             startp = p + 1;
1075           }
1076       }
1077   assert (list != NULL);
1078   assert (p[-1] == L(')'));
1079 #undef NEW_PATTERN
1080
1081   switch (opt)
1082     {
1083     case L('*'):
1084       if (FCT (p, string, string_end, no_leading_period, flags) == 0)
1085         return 0;
1086       /* FALLTHROUGH */
1087
1088     case L('+'):
1089       do
1090         {
1091           for (rs = string; rs <= string_end; ++rs)
1092             /* First match the prefix with the current pattern with the
1093                current pattern.  */
1094             if (FCT (list->str, string, rs, no_leading_period,
1095                      flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD) == 0
1096                 /* This was successful.  Now match the rest with the rest
1097                    of the pattern.  */
1098                 && (FCT (p, rs, string_end,
1099                          rs == string
1100                          ? no_leading_period
1101                          : rs[-1] == '/' && NO_LEADING_PERIOD (flags) ? 1 : 0,
1102                          flags & FNM_FILE_NAME
1103                          ? flags : flags & ~FNM_PERIOD) == 0
1104                     /* This didn't work.  Try the whole pattern.  */
1105                     || (rs != string
1106                         && FCT (pattern - 1, rs, string_end,
1107                                 rs == string
1108                                 ? no_leading_period
1109                                 : (rs[-1] == '/' && NO_LEADING_PERIOD (flags)
1110                                    ? 1 : 0),
1111                                 flags & FNM_FILE_NAME
1112                                 ? flags : flags & ~FNM_PERIOD) == 0)))
1113               /* It worked.  Signal success.  */
1114               return 0;
1115         }
1116       while ((list = list->next) != NULL);
1117
1118       /* None of the patterns lead to a match.  */
1119       return FNM_NOMATCH;
1120
1121     case L('?'):
1122       if (FCT (p, string, string_end, no_leading_period, flags) == 0)
1123         return 0;
1124       /* FALLTHROUGH */
1125
1126     case L('@'):
1127       do
1128         /* I cannot believe it but `strcat' is actually acceptable
1129            here.  Match the entire string with the prefix from the
1130            pattern list and the rest of the pattern following the
1131            pattern list.  */
1132         if (FCT (STRCAT (list->str, p), string, string_end,
1133                  no_leading_period,
1134                  flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD) == 0)
1135           /* It worked.  Signal success.  */
1136           return 0;
1137       while ((list = list->next) != NULL);
1138
1139       /* None of the patterns lead to a match.  */
1140       return FNM_NOMATCH;
1141
1142     case L('!'):
1143       for (rs = string; rs <= string_end; ++rs)
1144         {
1145           struct patternlist *runp;
1146
1147           for (runp = list; runp != NULL; runp = runp->next)
1148             if (FCT (runp->str, string, rs,  no_leading_period,
1149                      flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD) == 0)
1150               break;
1151
1152           /* If none of the patterns matched see whether the rest does.  */
1153           if (runp == NULL
1154               && (FCT (p, rs, string_end,
1155                        rs == string
1156                        ? no_leading_period
1157                        : rs[-1] == '/' && NO_LEADING_PERIOD (flags) ? 1 : 0,
1158                        flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD)
1159                   == 0))
1160             /* This is successful.  */
1161             return 0;
1162         }
1163
1164       /* None of the patterns together with the rest of the pattern
1165          lead to a match.  */
1166       return FNM_NOMATCH;
1167
1168     default:
1169       assert (! "Invalid extended matching operator");
1170       break;
1171     }
1172
1173   return -1;
1174 }
1175
1176
1177 #undef FOLD
1178 #undef CHAR
1179 #undef UCHAR
1180 #undef INT
1181 #undef FCT
1182 #undef EXT
1183 #undef END
1184 #undef MEMPCPY
1185 #undef MEMCHR
1186 #undef STRCOLL
1187 #undef STRLEN
1188 #undef STRCAT
1189 #undef L
1190 #undef BTOWC