gettext-tools/gnulib-lib/fnmatch_loop.c

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