posix/fnmatch_loop.c

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