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