posix/fnmatch_loop.c

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