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