git.gag.com Git - debian/tar/blob - gnu/fnmatch_loop.c

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