git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/fnmatch_loop.c

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